Embedded zerotrees of wavelet transforms

Embedded zerotrees of wavelet transforms, usually shortened to EZW, is a lossy image compression algorithm built for the low bit rates at which most coefficients produced by a wavelet or other subband transform are zero or very close to zero. It treats the transformed coefficients as a tree whose root holds the lowest frequency coefficient and whose children are the spatially related coefficients in the next higher frequency subband. Because an insignificant coefficient very probably has insignificant descendants, whole subtrees called zerotrees can be coded with a single symbol. EZW works through repeated dominant and subordinate passes, halving a significance threshold each time and emitting one of four symbols for each coefficient: zerotree root, isolated zero, significant positive or significant negative. The subordinate pass sends refinement bits, much like bit-plane coding. The result is an embedded bit stream that can be cut off at any point to give an approximation of the image, with more bits giving a better picture. The article credits J. Shapiro with developing the method in 1993 and notes that its coding performance has since been exceeded by SPIHT and its derivatives.