QuantizationOverviewQuantizerReview of Quantization ConceptBring in Probability DistributionDerivation of MMSE QuantizerMMSE Quantizer (Lloyd-Max)Example: Gaussian p.d.f.MMSE Quantizer for Uniform DistributionQuantization – A “Lossy Step” in Source CodingThink More About Uniform QuantizerCompandorEncoding Correlated SequenceSlide 21Quantization in Encoding Correlated SequenceDrifting by “Open-Loop” Predictive CoderPredictive Coding (cont’d)More on PredictorVector QuantizationOutline of Core Parts in VQSummary: List of Compression ToolsImage Transform: A Revisit With A Coding PerspectiveWhy Do Transforms?Basic Process of Transform CodingExercise: Express 1-D DFT in Vector FormBasis Vectors and Basis ImagesStandard / “Trivial” BasisSummary of Today’s LectureImage Transform: A Revisit With A Coding Perspective More Details – For Next Lecture1-D DFT and Vector Form1-D Unitary TransformExercise:Properties of 1-D Unitary Transform y = A xProperties of 1-D Unitary Transform (cont’d)M. Wu: ENEE631 Digital Image Processing (Spring'09)Quantization Quantization 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 9 (2/23/2009)Lecture 9 (2/23/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [2]OverviewOverviewLast Time: –Wiener filtering for image restoration–Basic concept and techniques of source compression and codingPCM, Entropy coding, Run-length CodingToday: continue on source coding/compression techniques=> Lossless coding vs. Lossy coding–QuantizationMMSE Quantizer for non-uniform and uniform sourceCompanding: Quantizer with pre- and post- nonlinear transformationQuantizer in predictive codingVector vs. Scalar QuantizerRef. on image restoration based on perceptual error metrics in place of MSE:- S. S. Channappayya, A. C. Bovik, C. Caramanis, and R. W. Heath Jr., “SSIM-optimal linear image restoration,” ICASSP 2008. (info provided by Rick Miller)- Z. Wang and A.C. Bovik, “Mean Squared Error: Love it or Leave it? – A new look at signal fidelity measures,” IEEE Signal Processing Magazine, Jan. 2009.UMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [4]QuantizerQuantizerFrom Jain’s Fig.4.16 and B. Liu PU EE488 F’06Quantizer…M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [6]Review of Quantization ConceptReview of Quantization ConceptL-level Quantization–Minimize errors for this lossy process–What L values to use?–Map what range of continuous values to each of L values?tmintmaxUniform partition–Maximum errors = ( tmax - tmin ) / 2L = A / 2Lover a dynamic range of A–Best solution?Consider minimizing maximum absolute error (min-max) vs. MSEwhat if the value between [a, b] is more likely than other intervals?tmintmaxtktk+1(tmax—tmax)/2Lquantization errorUMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [7]Bring in Probability Distribution Bring in Probability Distribution Minimize error in a probability sense–MMSE (minimum mean square error)assign high penalty to large error and to likely occurring valuessquared error gives convenience in math.: differential, etc.An optimization problem–What {tk} and {rk } to use?–Necessary conditions: by setting partial differentials to zerot1tL+1p.d.f pu(x)r1rL Allocate more reconstruct. values in more probable rangesUMCP ENEE631 Slides (created by M.Wu © 2001)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [8]Derivation of MMSE QuantizerDerivation of MMSE QuantizerMSE of L-level quantizerOptimal (MMSE) quantizer – necessary conditionsM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [9]MMSE Quantizer (Lloyd-Max)MMSE Quantizer (Lloyd-Max)Reconstruction and decision levels need to satisfySolve iteratively–Choose initial values of {tk}(0) , compute {rk}(0) –Compute new values {tk}(1), and {rk}(1) ……For large number of quantization levels–Approx. constant pdf within t [tk, tk+1), i.e. p(t) = p(tk’) for tk’=(tk+tk+1)/2 Reference: S.P. Lloyd: “Least Squares Quantization in PCM”, IEEE Trans. Info. Theory, vol.IT-28, March 1982, pp.129-137UMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [11]Example: Gaussian p.d.f.Example: Gaussian p.d.f.Start 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 quantizer=> Difference: 3.4 dBM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [14]MMSE Quantizer for Uniform DistributionMMSE Quantizer for Uniform DistributionUniform quantizer–Is optimal for uniformly distributed r.v. in MMSE sense–MSE = q2 / 12 with q = A / L <= take-home exerciseSNR of uniform quantizer–Variance of uniform distributed r.v. = A2 / 12 –SNR = 10 log10 (A2 / q2) = 20 log10 L (dB)–If L = 2B, SNR = (20 log102)*B = 6B (dB) “1 bit is worth 6 dB.”Rate-Distortion tradeofft1tL+1A1/Ap.d.f. of uniformdistribution t1tL+1UMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec9 – Basics on Compression [15]Quantization – A “Lossy Step” in Source CodingQuantization – A “Lossy Step” in Source CodingQuantization is a lossy way to data compression–Lloyd-Max quantizer minimizes MSE distortion with a given rateAt least how many # bits needed for certain amount of error? –(information-theoretic) Rate-Distortion theory–Prelim: mutual information I(X; Y) = E{ log [p(X,Y) / (p(X)p(Y))] }Measure the amount of info. that one r.v. contains about another r.vRate distortion function of a r.v.–Minimum average rate RD bits/sample required to represent this r.v. while allowing a fixed distortion D–R(D) = min I(X;X*)minimize over p(X*|X) given a source p(X)–For Gaussian r.v. and MSE1bit more cuts down distortion to ¼ => 6dBDRD2mean) theuse(just ,