1CSEP 590Data CompressionAutumn 2007Scalar QuantizationVector QuantizationCSEP 590 - Lecture 8 - Autumn 2007 2Lossy Image Compression Methods• DCT Compression– JPEG• Scalar quantization (SQ).• Vector quantization (VQ).• Wavelet Compression– SPIHT– GTW– EBCOT– JPEG 2000CSEP 590 - Lecture 8 - Autumn 2007 3Scalar Quantization01n-1...codebookiindex of a codeword01n-1...codebooksource imagedecoded imageCSEP 590 - Lecture 8 - Autumn 2007 4Scalar Quantization Strategies• Build a codebook with a training set. Encode and decode with fixed codebook.– Most common use of quantization• Build a codebook for each image. Transmit the codebook with the image.• Training can be slow.CSEP 590 - Lecture 8 - Autumn 2007 5Distortion• Let the image be pixels x1, x2, … xT.• Define index(x) to be the index transmitted on input x.• Define c(j) to be the codeword indexed by j.TDMSEn)(Distortio))c(index(x(xD2iT1ii=−=∑=CSEP 590 - Lecture 8 - Autumn 2007 6Uniform Quantization Example• 512 x 512 image with 8 bits per pixel.• 8 codewords0 31 63 95 127 159 191 223 255 Codebook23920717514311179471676543210IndexCodewordboundary codeword2CSEP 590 - Lecture 8 - Autumn 2007 7Uniform Quantization ExampleEncoder111110101100011010001000224-255192-223160-191128-15996-12764-9532-630-31inputcode239207175143111794716111110101100011010001000DecodercodeoutputBit rate = 3 bits per pixelCompression ratio = 8/3 = 2.67 CSEP 590 - Lecture 8 - Autumn 2007 8Example• [0,100) with 5 symbols• Q = 20M50201/2)(22050230201/2)(12030110201/2)(020100Decode Encode =⋅+==⋅+==⋅+=0 20 40 60 80 100 0 1 2 3 4CSEP 590 - Lecture 8 - Autumn 2007 9Alternative Uniform Quantization Calculation with Push to Zero• Range = [min, max)• Target is S symbols• Choose Q = (max – min)/S• Encode x• Decode s += 1/2QxsQ sx'=CSEP 590 - Lecture 8 - Autumn 2007 10Example• [0,90) with 5 symbols• Q = 20M402021/22049.992202011/22029.99102001/2209.990Decode Encode =⋅+==⋅+==⋅+=0 10 30 50 70 90 0 1 2 3 4CSEP 590 - Lecture 8 - Autumn 2007 11Improving Bit Rate0 31 63 95 127 159 191 223 255 qj= the probability that a pixel is coded to index jPotential average bit rate is entropy.Frequency of pixel values)q1(logqHj270jj∑==CSEP 590 - Lecture 8 - Autumn 2007 12Example• 512 x 512 image = 216,144 pixels9,14418,00010,00010,00010,00090,000100,00025,000224-255192-223160-191128-15996-12764-9532-630-31indexinputfrequency0 1 2 3 4 5 6 735 462107Huffman TreeABR= (100000 x 1+90000 x 2 +43000 x 4 +39144 x 5)/216144=2.997Arithmetic coding should workbetter.3CSEP 590 - Lecture 8 - Autumn 2007 13Improving Distortion• Choose the codeword as a weighted average0 31 63 95 127 159 191 223 255 Let pxbe the probability that a pixel has value x.Let [Lj,Rj) be the input interval for index j. c(j) is the codeword indexed j)pxround(c(j)jjRxLx∑<≤⋅=CSEP 590 - Lecture 8 - Autumn 2007 14Example01020304010010010015141312111098pixel valuefrequency16000311021201130 Distortion Old1000041032021301140 DistortionNew 11 Codeword Old10 )4000151014201330124011100101009 1008round( CodewordNew 2222222=⋅+⋅+⋅==⋅+⋅+⋅+⋅===⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅=All pixels have the same index.CSEP 590 - Lecture 8 - Autumn 2007 15An Extreme Case0 31 63 95 127 159 191 223 255 Frequency of pixel valuesOnly two codewords are ever used!!CSEP 590 - Lecture 8 - Autumn 2007 16Non-uniform Scalar Quantization0 255Frequency of pixel valuescodewordboundary between codewordsCSEP 590 - Lecture 8 - Autumn 2007 17Lloyd Algorithm• Lloyd (1957)• Creates an optimized codebook of size n.• Let pxbe the probability of pixel value x. – Probabilities might come from a training set• Given codewords c(0),c(1),...,c(n-1) and pixel x let index(x) be the index of the closest code word to x.• Expected distortion is• Goal of the Lloyd algorithm is to find the codewordsthat minimize distortion.• Lloyd finds a local minimum by an iteration process.2xx))c(index(x)(xpD −=∑CSEP 590 - Lecture 8 - Autumn 2007 18Lloyd AlgorithmChoose a small error tolerance ε > 0.Choose start codewords c(0),c(1),...,c(n-1)Compute X(j) := {x : x is a pixel value closest to c(j)}Compute distortion D for c(0),c(1),...,c(n-1) RepeatCompute new codewordsCompute X’(j) = {x : x is a pixel value closest to c’(j)}Compute distortion D’ for c’(0),c’(1),...,c’(n-1)if |(D – D’)/D| < ε then quitelse c := c’; X := X’, D := D’End{repeat})/ppxround(:(j)c'X(j)xX(j)x∑∈⋅=4CSEP 590 - Lecture 8 - Autumn 2007 19Example01020304010010010076543210pixel valuefrequencyInitially c(0) = 2 and c(1) = 5 57)/60)06105204round((30(1)c'13)/340)40210011000round((100(0)c'580D(1)D(0) D40140D(1) 540; 21001140 D(0)[4,7]X(1) [0,3], X(0)222=⋅+⋅+⋅+⋅==⋅+⋅+⋅+⋅==+==⋅==⋅+⋅===CSEP 590 - Lecture 8 - Autumn 2007 20Example01020304010010010076543210pixel valuefrequencyD':D;X':X;c':c.31400)/580(580)/DD'(D400(1)D'(0)D'D'200240140 (1)D'200 1200 (0)D'[3,7](1)X' [0,2]; (0)X'5(1)c' 1;(0)c'222====−=−=+==⋅+⋅==⋅=====CSEP 590 - Lecture 8 - Autumn 2007 21Example01020304010010010076543210pixel valuefrequency 47)/100)06105204303round((40(1)c'12)/300)10011000round((100(0)c'400D[3,7]X(1) [0,2]; X(0)5c(1) 1;c(0)=⋅+⋅+⋅+⋅+⋅==⋅+⋅+⋅======CSEP 590 - Lecture 8 - Autumn 2007 22Example01020304010010010076543210pixel valuefrequencyD':D;X':X;c':c.17300)/580(400)/DD'(D300(1)D'(0)D'D'100210160 (1)D'200 1200 (0)D'[3,7](1)X' [0,2]; (0)X'4(1)c' 1;(0)c'222====−=−=+==⋅+⋅==⋅=====CSEP 590 - Lecture 8 - Autumn 2007 23Example01020304010010010076543210pixel valuefrequency 47)/100)06105204303round((40(1)c'12)/300)10011000round((100(0)c'400D[3,7]X(1) [0,2]; X(0)4c(1) 1;c(0)=⋅+⋅+⋅+⋅+⋅==⋅+⋅+⋅======CSEP 590 - Lecture 8 - Autumn 2007 24Example01020304010010010076543210pixel valuefrequency4.c(1) and 1 c(0)
View Full Document
Unlocking...