Wavelet Coding and Related IssuesOverview and LogisticsReview: 2-D Subband/DWT DecompositionReview: Key Concepts in EZWRecall: EZW Algorithm and ExampleAfter 1st PassAfter 2nd PassEZW and BeyondA Close Look at Wavelet Transform Haar Transform – unitary Orthonormal Wavelet Filters Biorthogonal Wavelet FiltersConstruction of Haar FunctionsHaar TransformCompare Basis Images of DCT and HaarTime-Freq (or Space-Freq) InterpretationsRecap on Haar TransformOrthonormal FiltersSolutions to Coefficient ExpansionSolutions to Coefficient Expansion (cont’d)Biorthogonal WaveletsSmoothness Conditions on Wavelet FilterJPEG 2000 Image Compression StandardSlide 26JPEG 2000: A Wavelet-Based New StandardExamples JPEG2K vs. JPEGDCT vs. Wavelet: Which is Better?Non-Dyadic Decomposition – Wavelet PacketsBit Allocation in Image Coding Focus on MSE-based optimization; Can further adjust based on HVSBit AllocationSlide 34Details on Reverse Water-filling SolutionKey Result in Rate Allocation: Equal R-D SlopeSummary of Today’s LectureReview: Correlation After a Linear TransformSlide 39Optimal TransformSlide 41K-L Transform (Principal Component Analysis)Properties of K-L TransformKLT Basis RestrictionK-L Transform for ImagesPros and Cons of K-L TransformEnergy Compaction of DCT vs. KLTEnergy Compaction of DCT vs. KLT (cont’d)More on Rate-Distortion Based Bit Allocation in Image CodingBasic Steps in R-D OptimizationBridging the Theory and the PracticeRef: convex hullSlide 60Details on Reverse Water-filling Solution (cont’d)Lagrangian Opt. for Indep. Budget ConstraintSlide 64Bridging the Theory and Ad-hoc PracticeSlide 66M. Wu: ENEE631 Digital Image Processing (Spring'09)Wavelet Coding and Related IssuesWavelet Coding and Related IssuesSpring ’09 Instructor: Min Wu Electrical and Computer Engineering Department, University of Maryland, College Park bb.eng.umd.edu (select ENEE631 S’09) [email protected] Spring’09ENEE631 Spring’09Lecture 13 (3/11/2009)Lecture 13 (3/11/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [2]Overview and LogisticsOverview and LogisticsLast Time:–JPEG Compression–Subband and Wavelet based compressionSubband decomposition; basic ideas of EZW encodingToday–Continue on Subband and Wavelet based compressionExploit the structures between coefficients for removing redundancyMore on wavelet transform, and consideration on filtersAssignment#3 is Due Friday noon March 13–JPEG part may be turned in after spring breakProject#1 Posted. Due Monday April 6UMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [3]UMCP ENEE631 Slides (created by M.Wu © 2004)Review: 2-D Subband/DWT Review: 2-D Subband/DWT DecompositionDecompositionFrom Usevitch’s article in IEEE Sig.Proc. Mag. 9/01Separable transform by successively applying 1-D DWT to rows and columnsM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [4]Review: Key Concepts in EZW Review: Key Concepts in EZW Exploit multi-resolution and self-similarity Parent-children relation among coeff.–Each parent coeff at level k spatially correlates with 4 coeff at level (k-1) of same orientation –A coeff at lowest band correlates with 3 coeff.Coding significance map via zero-tree–Encode “insignificance map” w/ zero-treesAvoid large overhead by coding only significant coefficientsSuccessive approximation quantization–Send most-significant-bits first and gradually refine coefficient value–“Embedded” nature of coded bit-streamget higher fidelity image by adding extra refining bits=> Quality Scalability with fine granularityFrom Usevitch (IEEE Sig.Proc. Mag. 9/01)UMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [5]Recall: EZW Algorithm and ExampleRecall: EZW Algorithm and ExampleInitial threshold ~ 2 ^ floor(log2 xmax)–Put all coeff. in dominant list Dominant Pass (“zig-zag” across bands)–Assign symbol to each coeff. and entropy encode symbolsps – positive significancens – negative significanceiz – isolated zeroztr – zero-tree root–Significant coefficientsMove to subordinate listSet them to zero in dominant listSubordinate Pass–Output one bit for subordinate listAccording to position in up/low half of quantization intervalRepeat with half threshold, until bit budget achieved –E.g. first look for coeff. above 32; then focus on coeff. between 16 and 32Fig. From Usevitch (IEEE Sig. Proc. Mag. 9/01)UMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [6]After 1After 1stst Pass PassFrom Usevitch (IEEE Sig.Proc. Mag. 9/01)Divide quantization interval of [32,64) by half: [32,48) => 40 and [48, 64) => 56UMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [7]After 2After 2ndnd Pass PassFrom Usevitch (IEEE Sig.Proc. Mag. 9/01)[16,24) => 20, [24, 32) => 28; [32,40) => 36, [40,48) => 44; [48, 56) => 52, [56, 64) => 602nd Subordinate Pass:orig. 53  symbol 0  reconstruct 52 34  0  36 -22  0  -20 21  0  20UMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [8]EZW and BeyondEZW and BeyondCan apply DWT to entire images or larger blocks than 8x8Symbol sequence can be entropy encoded –e.g. arithmetic codingCons of EZW–Poor error resilience; Difficult for selective spatial decodingSPIHT (Set Partitioning in Hierarchal Trees)–Further improvement over EZW to remove redundancy–Achieve equal/better performance than EZW w/o arithmetic codingEBCOT (Embedded Block Coding with Optimal Truncation)–Used in JPEG 2000–Address the shortcomings of EZW (random access, error resilience, …)–Embedded wavelet coding in each block + bit-allocations among blocksUMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec13 – Wavelet Coding, etc. [9]A Close Look at Wavelet TransformA Close Look at Wavelet TransformHaar Transform – unitaryHaar Transform – unitaryOrthonormal