31-08-2017, 10:51 AM
Embedded Zerotrees of Wavelet Transformations (EZW) is a lossy image compression algorithm. At low bit rates, ie high compression ratios, most of the coefficients produced by a subband transform (such as the waveform) will be zero or very close to zero. This occurs because "real-world" images tend to contain mostly low-frequency (highly correlated) information. However, when high-frequency information is produced (such as edges in the image) this is particularly important in terms of human perception of image quality, and therefore must be represented accurately in any coding scheme of high quality.
Considering the coefficients transformed as a tree (or trees) with the lowest frequency coefficients in the root node and with the children of each tree node being the spatially related coefficients in the next higher frequency sub-band, there is a high probability that one or more subtrees will consist entirely of coefficients that are zero or nearly zero, such subtrees are called zerotrees. Because of this, we use the terms node and coefficient indistinctly, and when we refer to the children of a coefficient, we mean the infant coefficients of the node in the tree where that coefficient is. We use children to refer to nodes connected directly in the tree and descendants to refer to all nodes that are under a particular node in the tree, even if they are not directly connected.
In the zerotree-based image compression scheme such as EZW and SPIHT, we try to use the statistical properties of the trees to efficiently encode the locations of the significant coefficients. Since most of the coefficients will be zero or near zero, the spatial locations of the significant coefficients constitute a large part of the total size of a typical compressed image. A coefficient (also 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. Starting with a threshold that is close to the maximum coefficient magnitudes and iteratively decreasing the threshold, it is possible to create a compressed representation of an image that progressively adds finer details. Because of the structure of the trees, it is very likely that if a coefficient in a particular frequency band is insignificant, then all of 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 that is insignificant, but has significant descendants), © a significant positive coefficient, and (d) a significant negative coefficient. The symbols may thus be represented by two binary bits. The compression algorithm consists of a series 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 step encodes the significance of the coefficients that have not yet been found significant in previous iterations, scanning the trees and emitting one of the four symbols. The children of a coefficient are only scanned if the coefficient is significant or if the coefficient is an isolated zero. The subordinate step emits one bit (the most significant bit of each coefficient not yet emitted) for each coefficient that has been found significant in the previous past importance. The subordinate step is, therefore, similar to the binary plane coding.
There are several important features to keep in mind. First, it is possible to stop the compression algorithm at any time and get an approximation of the original image, the larger the number of bits received, the better the image. Second, because of the way in which the compression algorithm is structured as a series of decisions, the same algorithm can be executed in the decoder to reconstruct the coefficients, but with the decisions that are made according to the incoming bit stream . In practical implementations, it would be customary to use an entropy code such as an arithmetic code to further improve the performance of the dominant pitch. The bits of the slave pass are often random enough that the entropy coding does not provide greater coding gain.
Considering the coefficients transformed as a tree (or trees) with the lowest frequency coefficients in the root node and with the children of each tree node being the spatially related coefficients in the next higher frequency sub-band, there is a high probability that one or more subtrees will consist entirely of coefficients that are zero or nearly zero, such subtrees are called zerotrees. Because of this, we use the terms node and coefficient indistinctly, and when we refer to the children of a coefficient, we mean the infant coefficients of the node in the tree where that coefficient is. We use children to refer to nodes connected directly in the tree and descendants to refer to all nodes that are under a particular node in the tree, even if they are not directly connected.
In the zerotree-based image compression scheme such as EZW and SPIHT, we try to use the statistical properties of the trees to efficiently encode the locations of the significant coefficients. Since most of the coefficients will be zero or near zero, the spatial locations of the significant coefficients constitute a large part of the total size of a typical compressed image. A coefficient (also 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. Starting with a threshold that is close to the maximum coefficient magnitudes and iteratively decreasing the threshold, it is possible to create a compressed representation of an image that progressively adds finer details. Because of the structure of the trees, it is very likely that if a coefficient in a particular frequency band is insignificant, then all of 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 that is insignificant, but has significant descendants), © a significant positive coefficient, and (d) a significant negative coefficient. The symbols may thus be represented by two binary bits. The compression algorithm consists of a series 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 step encodes the significance of the coefficients that have not yet been found significant in previous iterations, scanning the trees and emitting one of the four symbols. The children of a coefficient are only scanned if the coefficient is significant or if the coefficient is an isolated zero. The subordinate step emits one bit (the most significant bit of each coefficient not yet emitted) for each coefficient that has been found significant in the previous past importance. The subordinate step is, therefore, similar to the binary plane coding.
There are several important features to keep in mind. First, it is possible to stop the compression algorithm at any time and get an approximation of the original image, the larger the number of bits received, the better the image. Second, because of the way in which the compression algorithm is structured as a series of decisions, the same algorithm can be executed in the decoder to reconstruct the coefficients, but with the decisions that are made according to the incoming bit stream . In practical implementations, it would be customary to use an entropy code such as an arithmetic code to further improve the performance of the dominant pitch. The bits of the slave pass are often random enough that the entropy coding does not provide greater coding gain.