Unformatted text preview:

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]OverviewOverviewLast Time:–MMSE Quantizer for non-uniform and uniform source–Companding: Quantizer with pre- and post- nonlinear transformation–Quantizer in predictive codingToday:–Vector vs. Scalar Quantizer –Revisit image transform from a coding and basis perspective=> Unitary transform–DCT transformLogistics: (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 QuantizerQuantize 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 QuantizationEncode a set of values together–Find the representative combinations–Encode the indices of combinationsScalar vs. Vector quantization–SQ is simpler in implementation –VQ allows flexible partition of coding cells–VQ could naturally explore the correlation between elementsStages 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 VQDesign 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 cellSearch for codeword at encoder–Tedious exhaustive search–Design codebook with special structures to speed up encodingE.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 ToolsLossless encoding tools–Entropy coding: Huffman, Arithmetic coding, Lemple-Ziv, …–Run-length codingLossy tools for reducing bit rate–Quantization: scalar quantizer vs. vector quantizer–Truncations: discard unimportant parts of dataFacilitating 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 encoderFacilitating 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 supportConceptual 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 dataFor 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 ImagesA 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
Download Unitary Transform
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Unitary Transform and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Unitary Transform 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?