Embedded Zerotree Wavelet - An Image Coding AlgorithmAgendaOverview (2-1)Overview (2-2) - Embedded Zerotree Wavelet (EZW)AgendaDiscrete Wavelet Transform (2-1)Slide Number 7Zerotree Coding (3-1)Slide Number 9Slide Number 10SAQ (3-1)Slide Number 12Slide Number 13Adaptive Arithmetic CodingRelationship to Other Coding AlgorithmsAgendaSlide Number 17Slide Number 18Slide Number 19ConclusionReferencesSlide Number 22Embedded Zerotree Wavelet22 - 1Embedded Zerotree Wavelet - An Image Coding AlgorithmShufang Wu http://www.sfu.ca/[email protected], June 14, 2002Embedded Zerotree Wavelet22 - 2Agenda• Overview• Discrete Wavelet Transform• Zerotree Coding of Wavelet Coefficients• Successive-Approximation Quantization (SAQ)• Adaptive Arithmetic Coding• Relationship to Other Coding Algorithms• A Simple Example• Experimental Results• Conclusion• References• Q & AEmbedded Zerotree Wavelet22 - 3Overview (2-1)• Two-fold problem– Obtaining best image quality for a given bit rate– Accomplishing this task in an embedded fashion• What is Embedded Zerotree Wavelet (EZW) ?– An embedded coding algorithm– 2 properties, 4 features and 2 advantages (next page)• What is Embedded Coding?– Representing a sequence of binary decisions that distinguish an image from the “null” image– Similar in spirit to binary finite-precision representations of real numberEmbedded Zerotree Wavelet22 - 4• 2 Properties– Producing a fully embedded bit stream – Providing competitive compression performance • 4 Features– Discrete wavelet transform– Zerotree coding of wavelet coefficients– Successive-approximation quantization (SAQ)– Adaptive arithmetic coding• 2 Advantages– Precise rate control– No training of any kind requiredOverview (2-2) - Embedded Zerotree Wavelet (EZW)Embedded Zerotree Wavelet22 - 5Agenda• Overview• Discrete Wavelet Transform• Zerotree Coding of Wavelet Coefficients• Successive-Approximation Quantization (SAQ)• Adaptive Arithmetic Coding• Relationship to Other Coding Algorithms• A Simple Example• Experimental Results• Conclusion• References• Q & AEmbedded Zerotree Wavelet22 - 6Discrete Wavelet Transform (2-1)• Identical to a hierarchical subband system– Subbands are logarithmically spaced in frequency– Subbands arise from separable application of filtersLL1LH1HL1HH1First stageLH1HL1HH1Second stageLL2LH2HL2HH2Embedded Zerotree Wavelet22 - 7Discrete Wavelet Transform (2-2)• Wavelet decomposition (filters used based on 9-tap symmetric quadrature mirror filters (QMF))In the frequency domainImage wavelet representationsDf1Df1D32jfwywxEmbedded Zerotree Wavelet22 - 8Zerotree Coding (3-1)• A typical low-bit rate image coder– Large bit budget spent on encoding the significance map True cost of encoding the actual symbols:Total Cost = Cost of Significance Map+ Cost of Nonzero ValuesBinary decision as to:whether a coefficient has a zero or nonzero quantized valueEmbedded Zerotree Wavelet22 - 9Zerotree Coding (3-2)• What is zerotree?– A new data structure– To improve the compression of significance maps of wavelet coefficients• What is insignificant?a wavelet coefficient x is said to be insignificant with respect to a given threshold T if :|x| < T• Zerotree is based on an empirically true hypothesis• Parent-child dependencies (descendants & ancestors)• Scanning of the coefficients• An element of a zerotree for threshold T• A zerotree rootIF:A wavelet coefficient at a coarse scale is insignificant with respect to a given threshold T,THEN:All wavelet coefficients of the same orientation in the same spatial location at finer scales are likely to be insignificant with respect to T.Parent:The coefficient at the coarse scale.Child:All coefficients corresponding to the same spatial location at the next finer scale of similar orientation.Parent-child dependencies of subbandsScanning rule:No child node is scanned before its parent.Scanning order of the subbandsA coefficient x isIFitself and all of its descendents are insignificant with respect to T.An element of a zerotree for threshold T isIFIt is not the descendant of a previously found zerotree root for threshold T.Embedded Zerotree Wavelet22 - 10Zerotree Coding (3-3)• EncodingEmbedded Zerotree Wavelet22 - 11SAQ (3-1)• Successive-Approximation Quantization (SAQ)– Sequentially applies a sequence of thresholds T0 ,···,TN-1 to determine significance• Thresholds – Chose so that Ti = Ti-1 /2 – T0 is chosen so that |xj | < 2T0 for all coefficients xj• Two separate lists of wavelet coefficients– Dominant list– Subordinate listDominant list contains:The coordinates of those coefficients that have not yet been found to be significant in the same relative order as the initial scan.Subordinate list contains:The magnitudes of those coefficients that have been found to be significant.Embedded Zerotree Wavelet22 - 12SAQ (3-2)• Dominant pass• Subordinate pass• Encoding processDuring a dominant pass:coefficients with coordinates on the dominant list are compared to the threshold Ti to determine their significance, and if significant, their sign.During a subordinate pass:all coefficients on the subordinate list are scanned and the specifications of the magnitudes available to the decoder are refined to an additional bit of precision.SAQ encoding process:FOR I = T0 TO TN-1 Dominant Pass;Subordinate Pass (generating string of symbols) ;String of symbols is entropy encoded;Sorting (subordinate list in decreasing magnitude);IF (Target stopping condition = TRUE) break;NEXT;Embedded Zerotree Wavelet22 - 13SAQ (3-3)• Decoding– Each decode symbol, during both passes, refines and reduces the width of the uncertainty interval in which the true value of the coefficient ( or coefficients, in the case of a zerotree root)• Reconstruction value – Can be anywhere in that uncertainty interval– Practically, use the center of the uncertainty interval• Good feature– Terminating the decoding of an embedded bit stream at a specific point in the bit stream produces exactly the same image that would have resulted had that point been the initial target rateEmbedded Zerotree Wavelet22 - 14Adaptive Arithmetic Coding• Based on [3], encoder is separate from the model– which is basically a histogram• During the dominant passes– Choose one of four histograms depending on• Whether the