Unitary TransformOverviewRecap: Scalar QuantizerRecap: MMSE Quantizer Example – Gaussian SourceVector QuantizationOutline of Core Parts in VQRecap: List of Compression ToolsImage Transform: A Revisit With A Coding PerspectiveWhy Do Transforms?Basic Process of Transform CodingBasis Vectors and Basis ImagesStandard / “Trivial” BasisMatrix/Vector Form of 1-D DFTMatrix/Vector Form of 1-D DFT (cont’d)1-D Unitary TransformExercise:Properties of 1-D Unitary Transform y = A xProperties of 1-D Unitary Transform (cont’d)1-D Discrete Cosine Transform (DCT)Periodicity Implied by DFT and DCTExample of 1-D DCTExample of 1-D DCT (cont’d): N = 82-D DCT2-D Transform: General Case2-D Separable Unitary TransformsBasis Images for Separable TransformExercise on Basis ImagesReview: 2-D DFTVisualizing Fourier Basis Images8x8 DFT Basis ImagesSummary and ReviewSummary and Review (cont’d)Summary of Today’s LectureM. Wu: ENEE631 Digital Image Processing (Spring'09)Unitary Transform Unitary Transform Spring ’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 10 (2/25/2009)Lecture 10 (2/25/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [2]OverviewOverviewLast Time:–MMSE Quantizer for non-uniform and uniform source–Companding: Quantizer with pre- and post- nonlinear transformation–Quantizer in predictive codingToday:–Vector vs. Scalar Quantizer –Revisit image transform from a coding and basis perspective=> Unitary transform–DCT transformLogistics: (1) mid-term exam (2) Assign#3 to be postedUMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [3]Recap:Recap:Scalar QuantizerScalar QuantizerQuantize one sample at a timeQuantizer…quantization error…………Input/Output responseInput xOutput Q(x)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [4]Recap: MMSE Quantizer Recap: MMSE Quantizer Example – Gaussian SourceExample – Gaussian SourceStart with uniform quantizer Use iterative algorithm. optimum thresholds (red) and reconstruction values (blue)From B. Liu PU EE488 F’06Truncated Gaussian N(0,1) with L=16 quantizerM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [5]Vector QuantizationVector QuantizationEncode a set of values together–Find the representative combinations–Encode the indices of combinationsScalar vs. Vector quantization–SQ is simpler in implementation –VQ allows flexible partition of coding cells–VQ could naturally explore the correlation between elementsStages to build vector quantizer– Codebook design– Encoder– DecoderFrom Bovik’s Handbook Sec.5.3vector quantization of 2 elementsUMCP ENEE631 Slides (created by M.Wu © 2001)scalar quantization of 2 elementsSignal Sample-1Signal Sample-2M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [6]Outline of Core Parts in VQOutline of Core Parts in VQDesign codebook–Optimization formulation is similar to MMSE scalar quantizer–Given a set of representative points“Nearest neighbor” rule to determine partition boundaries–Given a set of partition boundaries“Probability centroid” rule to determine representative points that minimizes mean distortion in each cellSearch for codeword at encoder–Tedious exhaustive search–Design codebook with special structures to speed up encodingE.g., tree-structured VQReference:A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer Publisher. R. M. Gray, ``Vector Quantization,'' IEEE ASSP Magazine, pp. 4--29, April 1984. vector quantization of 2 elementsUMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [7]Recap: List of Compression ToolsRecap: List of Compression ToolsLossless encoding tools–Entropy coding: Huffman, Arithmetic coding, Lemple-Ziv, …–Run-length codingLossy tools for reducing bit rate–Quantization: scalar quantizer vs. vector quantizer–Truncations: discard unimportant parts of dataFacilitating compression via Prediction–Convert the full signal to prediction residue with smaller dynamic range–Encode prediction parameters and residues with less bits–Be careful: use quantized version available to decoder when designing encoderFacilitating compression via Transforms–Transform into a domain with improved energy compactionUMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [8]Image Transform: A RevisitImage Transform: A RevisitWith A Coding PerspectiveWith A Coding PerspectiveUMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [9]Why Do Transforms?Why Do Transforms?Fast computation–E.g., convolution vs. multiplication for filter with wide supportConceptual insights for various image processing–E.g., spatial frequency info. (smooth, moderate change, fast change, etc.)Obtain transformed data from measurement–E.g., blurred images, radiology images (medical and astrophysics)–Often need to perform an inverse transform to obtain the actual dataFor efficient storage and transmission–Pick a few “representatives” (basis) –Just store/send the major “contribution” from some basis image/vector=> Examine a segment of signal samples togetherUMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [10]Basic Process of Transform CodingBasic Process of Transform CodingUMCP ENEE631 Slides (created by M.Wu © 2004)Figure is from slides at Gonzalez/ Woods DIP book website (Chapter 8)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec10 – Unitary Transform [11]Basis Vectors and Basis ImagesBasis Vectors and Basis ImagesA basis for a vector space ~ a set of vectors that is–Linearly independent ~ ai vi = 0 if and only if all ai=0–Uniquely represent every vector in the space by their linear combination ~ bi vi ( “spanning set” {vi} )Orthonormal basis–Orthogonality ~ inner product <x, y> = y*T x= 0 –Normalized length ~ || x ||2 = <x,
View Full Document