3.2.3 Zerotree Entropy Coding

Zerotree Entropy(ZTE) coding is the key element on compression in recent years. ZTE is applied to wavelet coefficients[7].

In the ZTE technique, a block structure which is shown in Figure 11. is formed by collecting subband coefficients corresponding to the same spatial positions which are linked with each other by arrows as shown in Figure 10. from the image which has been decomposed in subbands. It has already known that there is a correlation between coefficients which are linked with each other by arrows in Figure 10. excepting the highest frequency subbands.

The whole relation of the coefficients that are linked with each other by arrows in Figure 10 is referred to as "trees". One coefficient of each of the subbands (LH3, HL3, HH3) having a frequency one level higher than that of one coefficient of the lowest frequency subband (LL3) corresponds thereto (for example, “b1”, “b2” and “b3” correspond to “a0” in Figure 10.). Besides , four coefficients of each of the subbands (LH2, HL2, HH2) having a frequency one level higher than that of each of these coefficients correspond its lower frequency (for example, c11, c12, c13, c14 correspond to b1 in Figure 10). Finally, sixteen coefficients of each of the subbands (LH1, HL1, HH1) having a frequency one level higher than that of each of four coefficients correspond lower frequency. Trees with respect to coefficient a is shown in Figure 12. White circles “o” and solid black circle “●” in Figure 12. denote coefficients in each subband. The trees in upper area comprise coefficients of the subbands having a lower resolution while the trees in lower area comprise coefficients of the subbands having a higher resolution.

 
Figure 10. Zerotree Hierarchy.

In such a tree structure, the coefficients having lower resolution are referred to as "parents" and the coefficients having next higher resolution in the same spatial position as designated by arrows are referred to as "children". In Figure 12., for example, coefficient a0 is a parent for coefficients b1, b2 and b3, which are in turn children for coefficient a0. Coefficient b1 is a parent for coefficients c11, c12, c13 and c14.

All coefficients having higher resolution in the same spatial position which are linked with each other by arrows with respect to one parent are referred to as "descendants" and all coefficients having a lower resolution in the same spatial position which are linked with each other by arrows with respect to one child are referred to as "ancestors". In Figure 12., for example, the coefficients encircled with a dotted line are descendants for coefficient b1 and coefficients c11, b1 and a0 are ancestors for coefficient d1111.

 
Figure 11. ZTE blocks in wavelet domain.

Quantization process is explicit. So we go directly to the symbol assignment. Three symbols are assigned to each node of the trees for representing whether the quantization coefficient is zero or non-zero.

The coefficient having the lowest frequency among the coefficients in which one coefficient in a tree is zero and the coefficients of its descendants are all zero is referred to as zero-tree-root (ZTR). Since this coefficient and the coefficients having a higher resolution than that of the former coefficient are all zero at this time, it would be unnecessary to code the coefficients of its descendant if ZTR appear in a tree. When any one coefficient in a tree is not zero, but the coefficients of its descendant are all zero, the coefficient in interest is referred to as valued zero-tree root (VZTR). If there is any one non-zero coefficient in the descendant, its coefficient is referred to as "Value".

 
Figure 12. ZTE Structure.

White and solid black circles denote the coefficients which the quantizing value is zero and non-zero, respectively in Figure 12. In this case, the coefficients which require coding are shown in Figure 13. Since a has a quantizing value which is not "zero" in Figure 13, the symbol Value is assigned to code the quantizing value. Since b1 and its descendants (c11 through c14, d1111 through d1114 through d1144) are all zero, symbol ZTR is assigned to b1 and it is not necessary to code the quantizing value. Since it can be found that the value of b1 is zero due to the fact that b1 is ZTR, it is never necessary to code the information on the descendants of b1.

Since b2 has a quantizing value which is not zero, but its descendants all have a quantizing value which is zero, symbol VZTR is assigned for coding only the quantizing value of b2. Concerning the descendants of b2, same as those of b1, it is not necessary to code their information. Since b3 has a non-zero quantizing value and there are some descendants which have a non-zero quantizing value, symbol Value is assigned for coding the quantizing value. VZTR is assigned for c31 and ZTR is assigned for c32. Value is assigned for c33 and c34. Only the quantizing values of the coefficients having the highest frequency (d3331 through d3344) are coded without assigning a symbol to the coefficients, As mentioned above, the information to be coded on this block comprises: symbol information including Value, ZTR, VZTR, Value, VZTR, ZTR, Value, Value, Value, Value, Value,........., Value and coefficient information including Q (a0), Q(b2), Q(b3), Q(c31), Q(c33), Q(c34), Q(d3331), Q(d3332), Q(d3333), ........, Q(d3344), wherein Q(a0) denotes the quantizing value of the coefficient a0. The contents of coded data are shown in Figure 14.

Figure 13. Symbols and coefficients in ZTE.

When the symbol is VZTR or Value, it is necessary to code the quantizing values of the coefficients. Since there are generally a lot of coefficients having a quantizing value which is zero in the high frequency subband, many ZTRs are generated so that it is unnecessary to code the coefficient value. Therefore high coding efficiency is achieved.

As mentioned above, in the ZTE technique the order of coding of the coefficients does not shift subband by subband, the symbol information and the coefficient information in the block basis is completely coded and thereafter coding of next block is initiated.

 
Figure 14. ZTE coded one frame.