EZW(Embedded Zerotree Wavelet)

EZW combined with Wavelet-based Image Coding , Huffman encoder & with Lempel-Ziv-Welch(LZW)

EZW (Embedded Zerotrees of Wavelet Transforms) is a lossy image compression algorithm. At low bit rates (i.e. high compression ratios) most of the coefficients produced by a subband transform (such as the wavelet transform) will be zero, or very close to zero. This occurs because "real world" images tend to contain mostly low frequency information (highly correlated). However where high frequency information does occur (such as edges in the image) this is particularly important in terms of human perception of the image quality, and thus must be represented accurately in any high quality coding scheme.

By considering the transformed coefficients as a tree (or trees) with the lowest frequency coefficients at the root node and with the children of each tree node being the spatially related coefficients in the next higher frequency subband, there is a high probability that one or more subtrees will consist entirely of coefficients which are zero or nearly zero, such subtrees are called zerotrees. Due to this, we use the terms node and coefficient interchangeably, and when we refer to the children of a coefficient, we mean the child coefficients of the node in the tree where that coefficient is located. We use children to refer to directly connected nodes lower in the tree and descendants to refer to all nodes which are below a particular node in the tree, even if not directly connected.

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.