Embedded Zerotree Of Wavelet Coefficients - MULTIMEDIA

So far, we have described a wavelet - based scheme for image decomposition. However, aside from referring to the idea of quantizing away small coefficients, we have not really addressed how to code the wavelet transform values — how to form a bit stream. This problem is precisely what is dealt with in terms of a new data structure, the Embedded Zerotree.

The Embedded Zerotree Wavelet (EZW) algorithm introduced by Shapiro is an effective and computationally efficient technique in image coding. This work has inspired a number of refinements to the initial EZW algorithm, the most notable being Said and Pearlman's Set Partitioning in Hierarchical Trees (SPIHT) algorithm and Taubman's Embedded Block Coding with Optimized Truncation (EBCOT) algorithm, which is adopted into the JPEG2000 standard.

The EZW algorithm addresses two problems: obtaining the best image quality for a given bitrate and accomplishing this task in an embedded fashion. An embedded code is one that contains all lower - rate codes "embedded" at the beginning of the bitstream. The bits are effectively ordered by importance in the bitstream. An embedded code allows the encoder to terminate the encoding at any point and thus meet any target bitrate exactly. Similarly, a decoder can cease to decode at any point and produce reconstructions corresponding to all lower - rate encodings.

To achieve this goal, the EZW algorithm takes advantage of an important aspect of low - bitrate image coding. When conventional coding methods are used to achieve low bitrates, using scalar quantization followed by entropy coding, say, the most likely symbol, after quantization, is zero. It turns out that a large fraction of the bit budget is spent encoding the significance map, which flags whether input samples (in the case of the 2D discrete wavelet transform, the transform coefficients) have a zero or nonzero quantized value.

The EZW algorithm exploits this observation to turn any significant improvement in encoding the significance map into a corresponding gain in compression efficiency. The EZW algorithm consists of two central components: the zerotree data structure and the method of successive approximation quantization.

The Zerotree Data Structure

The coding of the significance map is achieved using a new data structure called the zerotree. A wavelet coefficient x is said to be insignificant with respect to a given threshold T if | x | < T. The zerotree operates under the hypothesis that if a wavelet coefficient at a coarse scale is insignificant with respect to a given threshold T, all wavelet coefficients of the same orientation in the same spatial location at finer scales are likely to be insignificant with respect to T.

Using the hierarchical wavelet decomposition, we can relate every coefficient at a given scale to a set of coefficients at the next finer scale of similar orientation.

The following figure provides a pictorial representation of the zerotree on a three - stage wavelet decomposition. The coefficient at the coarse scale is called the parent while all corresponding coefficients are the next finer scale of the same spatial location and similar orientation are called children.

For a given parent, the set of all coefficients at all finer scales are called descendants. Similarly, for a given child, the set of all coefficients at all coarser scales are called ancestors.The scanning of the coefficients is performed in such a way that no child node is scanned before its parent.

Given a threshold 7, a coefficient x is an element of the zerotree if it is insignificant and all its descendants are insignificant as well. An element of a zerotree is a zerotree root if it is not the descendant of a previously found zerotree root. The significance map is coded using the zerotree with a four - symbol alphabet. The four symbols are

The zerotree root. The root of the zerotree is encoded with a special symbol indicat­ing that the insignificance of the coefficients at finer scales is completely predictable, Isolated zero. The coefficient is insignificant but has some significant descendants.

Parent - child relationship in a zerotree

Parent - child relationship in a zerotree

  1. Positive significance. The coefficient is significant with a positive value.
  2. Negative significance. The coefficient is significant with a negative value.

The cost of encoding the significance map is substantially reduced by employing the zerotree. The zerotree works by exploiting self-similarity on the transform coefficients. The underlying justification for the success of the zerotree is that even though the image has been transformed using a decorrelating transform, the occurrences of insignificant coefficients are not independent events.

EZW scanning order

EZW scanning order

In addition, the zerotree coding technique is based on the observation that it is much easier to predict insignificance than to predict significant details across scales. This technique focuses on reducing the cost of encoding the significance map so that more bits will be available to encode the expensive significant coefficients.

Successive Approximation Quantization

Embedded coding in the EZW coder is achieved using a method called Successive Approx­imation Quantization (SAQ). One motivation for developing this method is to produce an embedded code that provides a coarse - to - fine, multiprecision logarithmic representation of the scale space corresponding to the wavelet - transformed image. Another motivation is to take further advantage of the efficient encoding of the significance map using the zerotree data structure, by allowing it to encode more significance maps.

The SAQ method sequentially applies a sequence of thresholds T0, ... , T n-1 to deter­mine the significance of each coefficient. The thresholds are chosen such that Ti= T i-1/2. The initial threshold 7n is chosen so that | xj | < 2T0 for all transform coefficients Xj. A dominant list and a subordinate list are maintained during the encoding and decoding pro­cess. The dominant list contains the coordinates of the coefficients that have not yet been found to be significant in the same relative order as the initial scan.

Using the scan ordering shown in the above figure all coefficients in a given subband appear on the initial dominant list prior to coefficients in the next subband. The subordinate list contains the magnitudes of the coefficients that have been found to be significant. Each list is scanned only once for each threshold.

During a dominant pass, coefficients having their coordinates on the dominant list implies that they are not yet significant. These coefficients are compared to the threshold Ti to determine their significance. If a coefficient is found to be significant, its magnitude is appended to the subordinate list, and the coefficient in the wavelet transform array is set to zero to enable the possibility of a zerotree occurring on future dominant passes at smaller thresholds. The resulting significance map is zerotree-coded.

The dominant pass is followed by a subordinate pass. All coefficients on the subordinate list are scanned, and tiieir magnitude, as it is made available to the decoder, is refined to an additional bit of precision. Effectively, the width of the uncertainty interval for the true magnitude of the coefficients is cut in half. For each magnitude on the subordinate list, the refinement can be encoded using a binary alphabet with a 1 indicating that the true value falls in the upper half of the uncertainty interval and a 0 indicating that it falls in the lower half.

The string of symbols from this binary alphabet is then entropy - coded. After the subordinate pass, the magnitudes on the subordinate list are sorted in decreasing order to the extent that the decoder can perform the same sort. The process continues to alternate between the two passes, with the threshold halved before each dominant pass. The encoding stops when some target stopping criterion has been met.

EZW Example

The following example demonstrates the concept of zerotree coding and successive approx­imation quantization. Shapiro presents an example of EZW coding in his paper for an

Coefficients of a three-stage wavelet transform used as input to the EZW algorithm

Coefficients of a three-stage wavelet transform used as input to the EZW algorithm

8 x 8 three - level wavelet transform. However, unlike the example given by Shapiro, we will complete the encoding and decoding process and show the output bitstream up to the point just before entropy coding.

The above figure shows the coefficients of a three - stage wavelet transform that we attempt to code using the EZW algorithm. We will use the symbols p, n, t, and z to denote positive significance, negative significance, zerotree root, and isolated zero respectively.

Since the largest coefficient is 57, we will choose the initial threshold To to be 32. At the beginning, the dominant list contains the coordinates of all the coefficients. We begin scanning in the order shown and determine the significance of the coefficients. The following is the list of coefficients visited, in the order of the scan:

{57, -37, -29, 30, 39, -20, 17, 33, 14, 6, 10, 19, 3, 7,8, 2, 2, 3,12, -9, 33,20, 2,4}

With respect to the threshold T0 = 32, it is easy to see that the coefficients 57 and — 37 are significant. Thus, we output a p and an n to represent them. The coefficient — 29 is insignificant but contains a significant descendant, 33, in LH1. Therefore, it is coded as z. The coefficient 30 is also insignificant, and all its descendants are insignificant with respect to the current threshold, so it is coded as t,

Since we have already determined the insignificance of 30 and all its descendants, the scan will bypass them, and no additional symbols will be generated. Continuing in this manner, the dominant pass outputs the following symbols:

Do ; pnztpttptzttpttt

Five coefficients are found to be significant: 57, — 37, 39, 33, and another 33. Since we know that no coefficients are greater than 2T0 = 64, and the threshold used in the first dominant pass is 32, the uncertainty interval is thus [32, 64). Therefore, we know that the value of significant coefficients lie somewhere inside this uncertainty interval.

The subordinate pass following the dominant pass refines the magnitude of these coef­ficients by indicating whether they lie in the first half or the second half of the uncertainty interval. The output is 0 if the values lie in [32,48) and 1 for values within [48,64). According to the order of the scan, the subordinate pass outputs the following bits: S0 :10000

Now the dominant list contains the coordinates of all the coefficients except those found to be significant, and the subordinate list contains the values (57, 37, 39, 33, 33}. After the subordinate pass is completed, we attempt to rearrange the values in the subordinate list such that larger coefficients appear before smaller ones, with the constraint that the decoder is able do exactly the same.

Since the subordinate pass halves the uncertainty interval, the decoder is able to distin­guish values from [32, 48) and [48,64). Since 39 and 37 are not distinguishable in the decoder, their order will not be changed. Therefore, the subordinate list remains the same after the reordering operation.

Before we move on to the second round of dominant and subordinate passes, we need to set the values of the significant coefficients to 0 in the wavelet transform array so that they do not prevent the emergence of a new zerotree.

The new threshold for a second dominant pass is T1 16. Using the same procedure as above, the dominant pass outputs the following symbols. Note that the coefficients in the dominant list will not be scanned.

D1 : zznptnpttztptttttttttttttptttttt

The subordinate fist is now {57, 37, 39, 33, 33,29, 30,20, 17, 19,20}. The subordinate pass that follows will halve each of the three current uncertainty intervals [48, 64), [32,48), and [16, 32). The subordinate pass outputs the following bits:

S1 : 10000110000

Now we set the value of the coefficients found to be significant to 0 in the wavelet transform array.

The output of the subsequent dominant and subordinate passes is shown below:

D2: zzzzzzzzptpzpptnttptppttpttpttpnppttttttpttttttttttttttt

S2: 01100111001101100000110110

D3 : zzzzzzztzpztztnttptttttptnnttttptttpptppttpttttt

S3: 00100010001110100110001001111101100010

D4: zzzzzttztztzztzzpttpppttttpttpttnpttptptttpt

S4:‘ 1111101001101011000001011101101100010010010101010

D5 : zzzztzttttztzzzzttpttptttttnptpptttppttp

Since the length of the - uncertainty interval in the last pass is 1, the last subordinate pass is unnecessary.

On the decoder side, suppose we received information only from the first dominant and subordinate passes. We can reconstruct a lossy version of the transform coefficients by

Reconstructed transform coefficients from the first dominant and subordinate passes

Reconstructed transform coefficients from the first dominant and subordinate passes

reversing the encoding process. From the symbols in Do we can obtain the position of the significant coefficients. Then, using the bits decoded from S0, we can reconstruct the value of these coefficients using the center of the uncertainty interval. The above figure shows the resulting reconstruction.

It is evident that we can stop the decoding process at any point to reconstruct a coarser representation of the original input coefficients. The following figure shows the reconstruction if the decoder received only Do, So, Di, Si, D2, and only the first 10 bits of Sz The coefficients that were not refined during the last subordinate pass appear as if they were quantized using a coarser quantizer than those that were.

In fact, the reconstruction value used for these coefficients is the center of the uncertainty interval from the previous pass. The heavily shaded coefficients in the figure are those that were refined, while the lightly shaded coefficients are those that were not refined. As a result, it is not easy to see where the decoding process ended, and this eliminates much of the visual artifact contained in the reconstruction.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status