Books
in black and white
Main menu
Home About us Share a book
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

- Acharya T.

Acharya T. - John Wiley & Sons, 2000. - 292 p.
ISBN 0-471-48422-9
Download (direct link): standardforImagecompressioncon2000.pdf
Previous << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 100 >> Next

162 JPEG2000 STANDARD
32. D. S. Taubman, “High Performance Scalable Image Compression with EBCOT,” IEEE Transaction Image Processing, Vol. 9, No. 7, pp. 1158" 1170, July 2000.
33. ISO/IEC 14492-1, “Lossy/Lossless Coding of Bi-level Images,” 2000.
7
Coding Algorithms in JPEG2000
7.1 INTRODUCTION
As shown in Section 6.6, Figure 6.2(a), after the DWT and quantization, the encoding phase in JPEG2000 is divided into two steps—Tier-1 coding and Tier-2 coding. In Tier-1 coding, each code-block is entropy encoded independently. In Tier-2 coding, the information of the compressed codewords generated in the Tier-1 coding step are encoded using a Tag Tree coding mechanism, which will be discussed in great detail in this chapter.
Entropy coding in JPEG2000 [5] is combination of fractional bit-plane coding (BPC) [1] and binary arithmetic coding (BAC) [2] as opposed to the classical Huffman coding [3] and run-length coding in current JPEG [4]. Combination of BPC and BAC is known as Tier-1 coding in JPEG2000. In this chapter, we will explain this new paradigm of fractional bit-plane coding technique and implementation of the MQ-coder for binary arithmetic coding. We shall also discuss the Tag Tree coding mechanism used in Tier-2 coding with examples. Tag Tree is a particular type of quad-tree data structure, which provides the framework for efficiently representing information of the codeblocks and their compressed codewords, such as the number of leading-zero MSB (most significant bit) planes in a code-block, etc., in the Tier-2 coding engine in JPEG2000.
163
164 CODING ALGORITHMS IN JPEG2000
7.2 PARTITIONING DATA FOR CODING
During entropy encoding, each wavelet subband is further divided into a number of code-blocks. At this stage all the elements in all the subbands are represented in sign and magnitude representation of integers instead of two’s complement. Dimension of the code-blocks is always a power of 2 with the minimum height and width being 4 and maximum height and width being 1024. Further restriction in dimension of a code-block is that if height of a code-block is 2X and width of the code-block 2y then x + y is limited to be less than or equal to 12. Typical choice of code-block size is 64 x 64 or 32 x 32. It has been found experimentally that the compression performance degrades when the code-block size is chosen below 16 x 16. It should be noted that the profile-0 of JPEG2000 Part 1 amendments further restricts the code-block size to be either 32 x 32 or 64 x 64.
During the coding phase, each code-block is decomposed into a number of bit-planes. If the precision of the subband is P bits, then each code-block in the subband is decomposed into P number of bit-planes. Bit-plane coding (BPC) is applied on each bit-plane of the code-blocks to generate intermediate data in the form of a context and a binary decision value. The intermediate data is input to the binary arithmetic coding (BAC) step to generate the final compressed bitstream.
7.3 TIER-1 CODING IN JPEG2000
In JPEG2000, the Embedded Block Coding with Optimized Truncation (EBCOT) algorithm by David S. Taubman [1, 7] has been adapted to implement the BPC. This algorithm has been built to exploit the symmetries and redundancies within and across the bit-planes so as to minimize the statistics to be maintained and minimize the coded bitstream that BAC would generate. EBCOT encodes each bit-plane in three passes, with a part of the bit-plane being coded in each of these passes without any overlapping with the other two passes. That is the reason why this bit-plane coding is also called fractional bit-plane coding. The three passes in the order they are performed on each bit-plane are:
• Significance Propagation Pass (SPP): Bit positions that have a magnitude of 1 for the first time (i.e., the most significant bit of the corresponding sample coefficients) are coded in this pass.
• Magnitude Refinement Pass (MRP): Bit positions that have not been coded in SPP and that have had magnitude of 1 in previous bitplanes (i.e., the current bit is not the most significant bit of the corresponding sample coefficient) are coded in this pass.
TIER-1 CODING IN JPEG2000
165
• Cleanup pass (CUP): Bit positions that have not been coded in either of the two earlier passes are coded in this pass. This pass also incorporates a form of run-length coding to help in coding a string of zeros.
7.3.1 Fractional Bit-Plane Coding
In order to make it easy for readers to understand this complex algorithm, we first provide the definition of terms used to describe the algorithm, followed by the explanation of four basic coding operations and three coding passes. Then we provide a simple example to illuminate the detailed process of the BPC coder.
7.3.1.1 Definition of Terms
• Code-Block (y): A code-block is a two-dimensional array that consists of integers (wavelet coefficients with or without quantization). Each code-block has width and height that specify its size. Each integer of the code-block can be either positive, zero, or negative. Each of the elements of a code-block are associated with a, a1, and tj to indicate their coded states (see a, a1, and rj for detailed descriptions).
Previous << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 100 >> Next