Image Compression OverviewDigital imagesDiscrete image intensitiesMultiple image componentsSome classes of imageryLossless compressionLossy compressionLossy compression: measuring distortionGamma correctionsRGB g-characteristicEffect of a small errorMeasures of compressionTypical bit-rates after compressionHow does compression work?Statistical redundancyJoint histogram of two horizontally adjacent pixelsEntropyVisual IrrelevanceIrrelevance in Color ImageryCompression as a global mappingCompression as a global mapping (cont.)Typical structured compression systemVariable length codingQuantizationTransformsCompression with predictive feedbackin the transform domainCompression with predictive feedbackin the image domainReading AssignmentBernd Girod: EE398A Image Communication I Image Compression Overview no. 1Image Compression Overview Goal of this chapter: provide a first introduction of some key terms and ideas of image compression, without rigorous treatment Lossless vs lossy compression Measuring distortion and compression Statistical redundancy and entropy Compression as a vector quantization problem Quantization Transforms Compression with predictive feedbackBernd Girod: EE398A Image Communication I Image Compression Overview no. 2Digital images A digital image is a two-dimensional sequence of samples[]12 1 1 2 2, , 0 , 0 xn n n N n N≤< ≤<21N−11N −0101 22n2[]12,xn n1nBernd Girod: EE398A Image Communication I Image Compression Overview no. 3Discrete image intensities Unsigned B-bit imagery Signed B-bit imagery Most common: B=8, but larger B are used in medical, military, or scientific applications. Useful interpretation[]{}12,0,1,,21Bxn n∈−…[]{}11 112,2,21,,21BB Bxn n−− −∈−−+ −…[][]12 12,2,Bxn n x nn′=Real-valued intensities, range 0…1 or –1/2…+1/2Rounding to nearest integerBernd Girod: EE398A Image Communication I Image Compression Overview no. 4Multiple image components Color images typically represented by three values per sample location, for red, green and blue primary components General multi-component image Examples:z Color printing: cyan, magenta, yellow, black dyes, sometimes morez Hyperspectral satellite imaging: 100s of channels[][][]12 12 12, , , , , RGBxnn xnn xnn[]12, , 1,2, , Cxnn c C= …Bernd Girod: EE398A Image Communication I Image Compression Overview no. 5Some classes of imagery “Natural” image Text image GraphicsBernd Girod: EE398A Image Communication I Image Compression Overview no. 6Lossless compression Minimize number of bits required to represent original digital image samples w/o any loss of information. All B bits of each sample must be reconstructed perfectly. Achievable compression usually rather limited. Applicationsz Binary images (facsimile)z Medical imagesz Master copy before editingz Palettized color imagesBernd Girod: EE398A Image Communication I Image Compression Overview no. 7Lossy compression Some deviation of decompressed image from original(“distortion”) is often acceptable:z Human visual system might not perceive loss, or tolerate it.z Digital input to compression algorithm is imperfect representation of real-world scene Much higher compression than with lossless. Lossy compression used widely for natural images (e.g. JPEG) and motion video (e.g. MPEG).Bernd Girod: EE398A Image Communication I Image Compression Overview no. 8Lossy compression: measuring distortion Most commonly employed: Mean Squared Error. . . or, equivalently, Peak Signal to Noise Ratio Advantagesz Easy calculationz Mathematical tractability in optimization problems Disadvantagez Neglects properties of human vision[][]()121211212 1200121ˆMSE= , ,NNnnxn n xn nNN−−==−∑∑()21021PSNR=10log dBMSEB−Gamma correctionBernd Girod: EE398A Image Communication I Image Compression Overview no. 9 Display devices (e.g. CRTs) highly nonlinear Cameras compensate by γ-predistortion circuitry IEC 61966-2-1 standard for γ-predistorted color space sRGB (“standard RGB”), each normalized linear RGB component mapped by~ , 1.8 2.8Lxγγ= …Screen luminance()1/if 01if 1lin linlin lingx xxxxγεββε≤≤⎧′=⎨+−≤≤⎩()()2.4, 0.055, , 1111gγββγβ εεγβγ⎛⎞⎜⎟⎜⎟== = =⎜⎟−⎛⎞−−⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠Bernd Girod: EE398A Image Communication I Image Compression Overview no. 10sRGB γ-characteristiclinxx′LinearpieceBernd Girod: EE398A Image Communication I Image Compression Overview no. 11Effect of a small errorlinxx′dx′lindx()()111/linlindx x dxxdxγγγγ−−′′=′=Roughly matchesWeber’s Law.PSNR distortionmeasure only usefulin the γ-correcteddomain.Bernd Girod: EE398A Image Communication I Image Compression Overview no. 12Measures of compression Image represented by “bit-stream” c of length ||c||. Compare no. of bits w/ and w/o compression Alternatively For lossy compression, bit-rate more meaningful than compression ratio, as B is somewhat arbitrary.12compression ratio =NNBc12bit-rate = bits/pixelNNcBernd Girod: EE398A Image Communication I Image Compression Overview no. 13Typical bit-rates after compression Substantially dependent on image content: consider typical natural images Lossless compression: (B-3) bpp (bits per pixel) Assume viewing on computer monitor, 90 pixels/inch. Lossy compression, z high quality: 1 bppz moderate quality: 0.5 bppz usable quality: 0.25 bpp  Perceived distortion depends on sampling density and contrastBernd Girod: EE398A Image Communication I Image Compression Overview no. 14How does compression work? Exploit statistical redundancy.z Take advantage of patterns in the signal.z Describe frequently occuring events efficiently.z Lossless coding: only statistical redundancy Introduce acceptable deviations.z Omit “irrelevant” detail that humans cannot perceive.z Match the signal resolution (in space, time, amplitude) to the applicationz Lossy coding: exploit statistical and visual redundancyBernd Girod: EE398A Image Communication I Image Compression Overview no. 15Statistical redundancy Trivial example: Given two B-bit integers (e.g., representing two adjacent pixels) Assume that only takes on values {0,1}z Compression to 1 bpp Further assume, that z Compression to 0.5 bpp Hope: bit-rate increases only slightly, as long as the above assumptions hold with