Embedded zerotrees of wavelet transforms: Difference between revisions

Revision as of 16:01, 5 January 2008

Revision as of 06:47, 21 January 2008

Line 7:

In zerotree based image compression scheme such as EZW and [[SPIHT]], the intent is to use the statistical properties of the trees in order to efficiently code the locations of the significant coefficients. Since most of the coefficients will be zero or close to zero, the spatial locations of the significant coefficients make up a large portion of the total size of a typical compressed image. A coefficient (likewise a tree) is considered '''significant''' if its magnitude (or magnitudes of a node and all its descendants in the case of a tree) is above a particular threshold. By starting with a threshold which is close to the maximum coefficient magnitudes and iteratively decreasing the threshold, it is possible to create a compressed representation of an image which progressively adds finer detail. Due to the structure of the trees, it is very likely that if a coefficient in a particular frequency band is insignificant, then all its descendants (the spatially related higher frequency band coefficients) will also be insignificant.

EZW uses four symbols to represent (a) a zerotree root, (b) an isolated zero (a coefficient which is significantinsignificant, but which has significant descendants), (c) a significant positive coefficient and (d) a significant negative coefficient. The symbols may be thus represented by two binary bits. The compression algorithm consists

of a number of iterations through a '''dominant pass''' and a '''subordinate pass''', the threshold is updated (reduced by a factor of two) after each iteration. The dominant pass encodes the significance of the coefficients which have not yet been found significant in earlier iterations, by scanning the trees and emitting one of the four symbols. The children of a coefficient are only scanned if the coefficient was found to be significant, or if the coefficient was an isolated zero. The subordinate pass emits one bit (the most significant bit of each coefficient not so far emitted) for each coefficient which has been found significant in the previous significance passes. The subordinate pass is therefore similar to bit-plane coding.