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 .. 68 69 70 71 72 73 < 74 > 75 76 77 78 79 80 .. 100 >> Next

I(CX) = NMPS(I(CX));
>
return D;
>
• RenormalizationDEC(): As shown in Figure 7.10, a decoder renormalization procedure is needed after calling either MPX_EXCHANGE() or LPS-EXCHANGEQ. The counter CT keeps track of the number of compressed bits remaining in the Clow section of the C register. If CT is down to zero, a new compressed byte will be brought in using the Byteln() procedure.
Renormalizat ionDEC()
{
do
{
if ( CT == 0 ) call BytelnO ;
A = A « 1;
C = C « 1;
CT = CT - 1;
> while ( A < 0x8000 )
>
7.4 TIER-2 CODING IN JPEG2000
In JPEG2000 standard [5], the Tier-2 coding engine is responsible for efficiently representing layer and block summary information for each code-block, including:
• The bitstream layers to which the code-block contributes the compressed codewords; this is also known as the “inclusion information.”
196
CODING ALGORITHMS IN JPEG2000
• The length of these codewords.
• The most significant magnitude bit-plane at which any sample in the code-block is nonzero, also known as the zero bit-planes information.
• The truncation points between the bitstream layers, that is, the number of coding passes information.
This information is known to the encoder. The decoder receives this information in an encoded format, which combines two Tag Trees (one for the inclusion information and the other for the zero bit-planes information) in the encoding procedure.
Tag Tree is a particular type of quad-tree data structure, which provides the framework for efficiently representing information in the Tier-2 coding engine of JPEG2000. Size of the header included in the compressed file in the JPEG2000 standard is much larger than in the JPEG standard and contains lots of important information. The Tag Tree coding mechanism helps in representing the layer and block summary information for each code-block to be included in the header of the compressed file. In this section, we first discuss the basic Tag Tree compression technique. Then we discuss the bitstream formation methodology and how the Tag Trees are integrated in Tier-2 coding in detail.
7.4.1 Basic Tag Tree Coding
7.4.1.1 Basic Data Structure A Tag Tree is a way to represent a two-dimensional array of nonnegative integers in a hierarchical way. Consider the two-dimensional array of integers of dimension 6 x 3 in Figure 7.11(a) as an example. Figures 7.11(b)-(d) are the reduced resolution levels of these two-dimensional arrays. The elements in an array at level n are formed by selecting the minimum of each 2x2 subarray (other than the boundary elements) from the two-dimensional array at level n + 1 as shown in Figure 7.11. For example, the elements in the array in level 2 (Figure 7.11(b)) are generated from the array in level 3 (Figure 7.11(a)) as follows.
92(0,0) = min{<73(0,0), 9з(1,0), 9з(0,1), 93(1,1)} = 1,
92(1,0) = min{<73(2,0), 9з(3,0), 9з(2,1), 9з(3,1)} = 1,
92(2,0) = min{93(4,0), 9з(5,0), 9з(4,1), 9з(5,1)} = 2,
92(0,1) = min{<73(0,2), 9з(1,2)} = 2,
92(1,1) = min{93(2,2), 9з(3,2)} = 2,
92(2,1) = min{93(4,2), 9з(5,2)} = 1.
Similarly, the elements in the array in level 1 (Figure 7.11(c)) are generated from the array in level 2 (Figure 7.11(b)) as follows.
9i.(0, 0) = min{92(0,0), 92(1, 0), 92(0,1), 92(1,1)} = 1, 9i(l,0) = min{92(2,0), 92(2,1)} = 1
TIER-2 CODING IN JPEG2000
197
and
<?o(l,0) = min{g1(0,0), <?i(l,0)} = 1.
Figure 7.12 is a compact representation of Figure 7.11 into a quad-tree data structure. The leaf nodes contain elements from the original two-dimensional array (Figure 7.11(a)), and the internal nodes represent the elements of the reduced dimension arrays in different levels Figures 7.11(b)-(d)). The notation, qi(x,y), is the value at the node that is the (x + l)th from the left and (y + l)th from the top of the two-dimensional array, at the zth level. Level 0 is the lowest level; it contains only the root node. This quad-tree-like data structure is the basic data structure for Tag Tree coding.
7.4.1.2 Basic Coding Procedure The coding procedure for a Tag Tree is very simple. Each node is encoded as d number of 0’s followed by a 1, where d is the difference between the current node and its parent node. For the root node, the parent node is assumed to be a 0 value node. However, nodes at higher levels cannot be encoded until their parent nodes at lower levels are entirely encoded. The first row of the table in Figure 7.13 shows part of the bitstream generated for the example in Figure 7.11, and the second row in the table shows the corresponding encoded node(s). For example, the code for the number at 53(0,0) would be 01111. The first two bits (01) imply that the value of the root node at 90 (0,0) is 1. The third bit (1) implies that the value at node 91 (0,0) is also 1. The forth bit (1) implies that the value at node 92(0,0) is also 1. And the final bit (1) implies that the value at the target node 53(0,0) is also 1. To encode the next node 93(1,0), the code would be
Previous << 1 .. 68 69 70 71 72 73 < 74 > 75 76 77 78 79 80 .. 100 >> Next