Lecture 11. Lossy Image CompressionLecture OutlineSpatial PredictionA Typical Predictive CoderThe Delta ModulatorError Analysis of a Lossy Predictive CoderDesign of the PredictorEstimation of the Correlation CoefficientsNon-Adaptive v.s. Adaptive Predictive CodingDiagrams for Transform Coding SystemTransform CodingTransform Basis DesignBasis Images of DCTDCT on a Real Image BlockQuantization of DCT CoefficientsDefault Normalization Matrix in JPEGExample: Quantized IndicesExample: Quantized CoefficientsExample: Reconstructed ImageZig-Zag Ordering of DCT CoefficientsDCT Coefficient DistributionExampleApproximation by DCT BasisCoding of DCT CoefficientsWhat is JPEGThe 1992 JPEG StandardCoding of Quantized DCT CoefficientsCoding of DC SymbolsJPEG Tables for Coding DCCoding of AC CoefficientsJPEG Tables for Coding AC (Run,Category) SymbolsJPEG Performance for B/W imagesJPEG for Color ImagesRGB <-> YCbCr ConversionChrominance SubsamplingCoding Unit in JPEGDefault Quantization TablePerformance of JPEGJPEG PerformanceJPEG Pros and ConsJPEG2000 FeaturesWhat is Scalability?Quality Scalability of JPEG2000Spatial Scalability of JPEG2000JPEG2000 vs. JPEG: Coding EfficiencyExample ImageAnother ExampleHow J2K Achieves Scalability?Wavelet DecompositionTwo Band Subband DecompositionWavelet Transform = Subband TreeWavelet Transform for ImagesWavelet DecompositionJPEG2000 Codec Block DiagramHomeworkReadingLecture 11. Lossy Image CompressionEL512 Image ProcessingDr. Zhu [email protected]: Part of the materials in the slides are from A. K. Jain’s Fundamentals of Digital Image ProcessingLecture OutlineFall 2003EL512 Image ProcessingLecture 11, Page 2• Introduction• Lossy predicative coding• Transform coding• JPEG• JPEG 2000Spatial PredictionFall 2003EL512 Image ProcessingLecture 11, Page 3AB C DE FGHI J K L$fafbfcfdfKFGHJ=+++Linear Estimator:Optimal MSE Predictor: The coefficients are determined to minimize the mean square prediction error.A Typical Predictive CoderFall 2003EL512 Image ProcessingLecture 11, Page 4QuantizerEntropyCoderPredictorInputSamplesBinaryCodespeˆBefˆepffpEncoderEntropyDecoderPredictorOutputSamplesBinaryCodesDecoderBepeˆfpfˆClosed-loop predictionThe Delta ModulatorFall 2003EL512 Image ProcessingLecture 11, Page 5• The simplest linear prediction.• The quantizer has only two levels.00ˆ<>⎩⎨⎧−=eeeξξ10ˆff =ξ is appropriateξ is too smallError Analysis of a Lossy Predictive CoderFall 2003EL512 Image ProcessingLecture 11, Page 6• Let q represent the quantization error for e, then• Therefore, the error between the original and the reconstructed value efis exactly the same as the quantization error.• Because the error usually has a non-uniform distribution, a non-uniform quantizer optimized for the distribution of the error signal is usually used.• A vector quanitizer can be used for the error.qfqefeffpppp−=−+=+=ˆˆDesign of the PredictorFall 2003EL512 Image ProcessingLecture 11, Page 7• For lossy predictive coders, the optimal predictor should be designed to minimize the MSE between the original f0and the predicted values• Since is related to akand the quantizer in a complicated relation, the precise minimization of the error is difficult.• In practice, one simply assumes that the quantization error is negligible.0ˆf⎭⎬⎫⎩⎨⎧−=∑202|ˆ|kkkpfafEσkfˆEstimation of the Correlation CoefficientsFall 2003EL512 Image ProcessingLecture 11, Page 8• One can use spatial sample averaging to approximate statistical ensemble mean.• To estimate the correlation between a pixel f(m, n) and its neighbor at f(m-k, n-l), denoted by Rf(k, l), one can usewhere Nsis the number of pairs of f(m, n) and f(m-k, n-l) that are included in the summation.∑−−=nmsflnkmfnmfNlkR,),(),(1),(Fall 2003EL512 Image ProcessingLecture 11, Page 9Non-Adaptive v.s. Adaptive Predictive Coding• In non-adaptive coders, a fixed set of prediction coefficients are used across the entire image.• In adaptive coders, one updates the correlation coefficients R(k, l) and hence the prediction coefficient akbased on local samples.– In forward adaptive predictive coder, for each block of pixels, the correlation coefficients are calculated for this block and the optimal coefficients are used.– In backward adaptive predictive coder, the correlation coefficients and consequently the prediction coefficients are updated based on the past reconstructed samples, in both the encoder and decoder.Diagrams for Transform Coding SystemFall 2003EL512 Image ProcessingLecture 11, Page 10BlocktransformQuantization of transform coefficientsCoding of quantized coefficientsfttˆBtEncoderDeCoding of quantized coefficientsDequantizationof transform coefficientsInverseblocktransformftˆBtDecodertˆTransform CodingFall 2003EL512 Image ProcessingLecture 11, Page 11• Represent an image as the linear combination of some basis images and specify the linear coefficients. +t1t2t3t4Transform Basis DesignFall 2003EL512 Image ProcessingLecture 11, Page 12• Optimality Criteria:– Energy compaction: a few basis images are sufficient to represent a typical image.– Decorrelation: coefficients for separated basis images are uncorrelated.• Karhunen Loeve Transform (KLT) is the Optimal transform for a given covariance matrix of the underlying signal.• Discrete Cosine Transform (DCT) is close to KLT for images that can be modeled by a first order Markov process (i.e., a pixel only depends on its previous pixel).Basis Images of DCTFall 2003EL512 Image ProcessingLecture 11, Page 13Low-LowLow-HighHigh-LowHigh-High1,...,1021)(2)12(cos2)12(cos)()(),,,(−==⎪⎩⎪⎨⎧=⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡+=NuuNNuwhereNvnNumvuvunmhαππαα∑∑∑∑−=−=−=−===10101010),,,(),(),(),,,(),(),(NuNvNmNnvunmhvuTnmfvunmhnmfvuTDCT on a Real Image BlockFall 2003EL512 Image ProcessingLecture 11, Page 14>>imblock = lena256(128:135,128:135)-128imblock=54 68 71 73 75 73 71 4547 52 48 14 20 24 20 -820 -10 -5 -13 -14 -21 -20 -21-13 -18 -18 -16 -23 -19 -27 -28-24 -22 -22 -26 -24 -33 -30 -23-29 -13 3 -24 -10 -42 -41 5-16 26 26 -21 12 -31 -40 2317 30 50 -5 4 12 10 5>>dctblock =dct2(imblock)dctblock=31.0000 51.7034 1.1673 -24.5837 -12.0000 -25.7508 11.9640 23.2873113.5766 6.9743 -13.9045 43.2054 -6.0959 35.5931 -13.3692