Generating lists of positions of coefficients in a code...

Details Generating lists of positions of coefficients in a code... Generating lists of positions of coefficients in a code...

2001-08-13

2003-04-08

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C382S240000, C341S051000

Reexamination Certificate

active

06545618

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates generally to data compression and decompression, and, in particular to a method and apparatus for entropy coding. The present invention also relates to a computer program product comprising a computer program for entropy coding.
BACKGROUND ART
A call for proposals for the new JPEG-2000 standard was recently issued and a draft standard has been published entitled “Information Technology—JPEG 2000 Image coding System—JPEG 2000 Committee Draft version 1.0, Dec. 9, 1999” (herein after referred to as JPEG2000).
JPEG2000 proposes that the whole image be divided into one or more image tile components, each of which are then 2-D discrete wavelet transformed. The transform coefficients of each image tile component are then grouped into sub-bands, which sub-bands are further partitioned into rectangular code blocks before each code block is then entropy encoded. The transform coefficients of each code block are expressed in a sign-magnitude representation prior to entropy coding. The entropy encoding consists of two parts: a context generator and an arithmetic coder. The arithmetic coder takes as input the bit symbol of a coefficient to be encoded and the context of that bit symbol. The context of a bit symbol of a coefficient, which bit symbol is to be coded by the arithmetic coder, is based on the ‘significance’ states of the 8 surrounding coefficients in the same bit-plane of the code block. The ‘significance’ state of a coefficient is a binary-valued variable S
i
[m,n], which is initialised to 0, but transitions to 1 immediately after the coefficient's first non-zero bit value is encoded.
FIG. 1
shows the neighbouring significance states S
i
[m−1,n−1], S
i
[m−1,n] S
i
[m−1,n+1], S
i
[m,n−1] S
i
[m,n+1], S
i
[m+1,n−1], S
i
[m+1,n] and S
i
[m+1,n+1] of the 8 surrounding coefficients of a coefficient “X[m,n]”, where m,n are the row and column numbers respectively of the code block and S
i
[ ] is the significance state immediately prior to the encoding of the bit symbol i of the coeficient X[m,n]. These neighbouring significance states are sometimes referred to as the significance states of the 3×3 neighbourhood of the coefficient X[m,n].
The arithmetic coder first codes all the bit symbols of the most significant bit-plane of a code block, then all the bit symbols of the next lower bit-plane of the code block and so on to a least significant bit-plane. Within each bit-plane of a code block, the arithmetic coder codes the bit symbols of the coefficients in three passes in a predetermined order.
The first pass of a bitplane is called the significance propagation pass (SP pass), the second pass of the bitplane is called the magnitude refinement pass (MR pass), and the third and last pass of the bitplane is called the cleanup pass (N pass). During the SP pass, a bit symbol of the bitplane is encoded if the bit symbol to be encoded has a neighbouring bit symbol, which has a significance state of one(1) but has itself a significance state of zero(0). During the MR pass, a bit symbol of the bitplane is encoded, if not already encoded, if the coefficient of that bit symbol is already significant in the previous encoded bitplane. During the N pass, the remaining bit symbols of the bitplane that have not already been encoded are then encoded.
The context is delivered to the arithmetic coder along with the bit to be encoded and the encoded symbol is output to the bitstream. If the value of this bit symbol to be coded is one (1) and the significance state is zero then the significance state is set to one (1) once the bit symbol is coded and the next immediate bit symbol to be coded is the sign bit for the coefficient. Otherwise, the significance state remains zero (0). When the contexts of successive coefficients and passes are considered, the most current significance state for this coefficient is used.
The arithmetic coder codes the bit symbols of a bitplane in the three passes (SP, MR, and N) in the same predetermined order. The arithmetic coder first proceeds to the highest bitplane that has a non-zero bit in it and skips the SP, MR passes and commences with the N pass. The arithmetic coder then proceeds to the next lower bit plane and codes the bit symbols in the three passes (SP, MR, and N) in that order. It then proceeds to the next lower bit plane and codes the bit symbols in the same order of passes (SP, MR, and N) and so on to the least significant bitplane.
In addition, each bitplane of a code block is scanned in a particular order. Starting at the top left, the first four bit symbols of the column are scanned. Then the first four bit symbols of the second column, until the width of the code-block has been covered. Then the second four bit symbols of the first column are scanned and so on. A similar scan is continued for any leftover rows on the lowest code blocks in the sub-band.
FIG. 2
shows an example of the code-block scan pattern for a code block having 64 transform coefficients arranged in an 8×8 block. As can be seen in this example, the scanning is performed in consecutive strips of four rows. The code block is not limited to a 8×8 block and larger code blocks are envisaged, such as 64×64 code block. In the latter case, there will 16 consecutive strips of four rows. For ease of explanation, this scanning order is herein after referred to as the JPEG2000 scanning order.
The entropy decoding described in JPEG2000 is a mirror image of the entropy encoding. For instance, the decoder decodes the symbols in the same order that they were encoded. The entropy decoding also comprises two sections: a context generator and an arithmetic decoder. The arithmetic decoder takes as input the symbol to be decoded and the context of that symbol to be decoded. The context of a symbol to be decoded, which symbol is to be decoded by the arithmetic decoder, is based on the ‘significance’ states of the 8 surrounding coefficients in the same bit-plane of the code block. The ‘significance’ state of a coefficient is a binary-valued variable S[m,n], which is initialised to 0, but transitions to 1 when the coefficient's first non-zero bit-plane value is decoded. In this fashion, the significance states of the coefficients during the decoding phase mirrors the significance states of the coefficients during the encoding phase (see FIG.
2
).
In JPEG2000 the arithmetic coding and decoding is performed bit-plane by bit-plane, from the most significant bit plane to the least significant bit plane. In the beginning the coding/decoding skips over all the bit planes with only zeroes in them, and would only begin operation on the first bit plane with non-zero elements in it. Once it reaches there, the codec operates on each successive bit-plane in three passes: significance propagation pass, magnitude refinement pass and cleanup pass.
A entropy codec has been proposed for implementing JPEG2000, which has the codec scanning through the whole bit-plane, and locating positions that have a certain characteristics. For example, in the significance propagation pass, the codec looks for positions that are not significant themselves, but have at least one significant coefficient in its 3×3 neighbourhood. In the magnitude refinement pass, the codec looks for positions that are significant already. In the cleanup pass, the codec looks for positions that are not coded/decoded before. Therefore, in the proposed codec every bit plane is scanned three times. This implies that the maximum throughput is one symbol per three cycles.
As we can see from the above, the main problem in the proposed codec is that for each pass the codec needs to scan through all the positions and decides whether they are coded/decoded in the current pass. That means that cycles are wasted scanning through positions that need not be coded.
SUMMAR

Affiliated with

Also associated with

Rating

Generating lists of positions of coefficients in a code... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Generating lists of positions of coefficients in a code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating lists of positions of coefficients in a code... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3017898