Image CompressionOUTLINE:Exploiting coding redundancy, interpixelredundancy, and psychovisual redundancyLossy and lossless methodsImage CompressionPictures take up a lot of storage space (either disk or memory).A 1000x1000 picture with 24 bits per pixel takes up 3 megabytes.The Encyclopaedia Brittanica scannned at 300 pixels per inch and 1 bit per pixelrequires 25,000 pages × 1,000,000 bytes per page = 25 gigabytes.Video is even bulkier: 90 minute movie at 640×480 resolution spatially, 24 bit perpixel, 24 frames per second, requires 90×60×24×640×480×3=120 gigabytes.Applications: HDTV, film, remote sensing and satellite image transmission,network communication, image storage, medical image processing, fax.How can we save space?Three approaches:Reduce Coding Redundancy - some pixel values more common than others.Reduce Interpixel Redundancy - neighboring pixels have similar values.Reduce Psychovisual Redundancy - some color differences are imperceptible.Trade Off Quality Against CompressionLossless compression (information preserving)- original can be recovered exactly.Higher quality, bigger.Lossy compression- only an approximation of the original can be recovered.Lower quality, smaller.errorsizelosslesslossyExploiting Coding RedundancyThese methods, from information theory, are not limited to images,but apply to any digital information. So we speak of “symbols”instead of “pixel values” and “sources” instead of “images”.The idea: instead of natural binary code, where each symbol isencoded with a fixed-length code word, exploit nonuniformprobabilities of symbols (nonuniform histogram) and use avariable-length code.Entropy H = -Σ Prob[symboli] log2 (Prob[symboli]) is a measure ofthe information content of a source. If source is an independentrandom variable then you can’t compress to fewer than H bits persymbol.Assign the more frequent symbols short bit strings and the lessfrequent symbols longer bit strings. Best compression whenredundancy is high (entropy is low, histogram is highly skewed).Two common methods: Huffman coding and LZW coding.Huffman Coding• Codebook is precomputed and static.• Compute probabilities of each symbol by histogramming source.• Process probabilities to precompute codebook: codei.• Encode source symbol-by-symbol: symboli →codei.The need to preprocess the source before encoding begins is adisadvantage of Huffman coding.Huffman Coding ExampleProbi.4 .2 .1 .1 .09 .06 .05 0symboli010 100 111 000 101 001 011 110codei 0 100 110 1010 1011 1110 1111 -.11.19.21.39.61000000111111sum of probabilities belowcode bit forbranch in treeEntropy=2.43Bits per symbol:Natural binary: 3.0Huffman: 2.5Lempel-Ziv-Welch (LZW) codingCodebook is computed on the fly (dynamic), an advantage over Huffman.If source uses 2k symbols, create table of length 2j mapping strings to codes, j>>k.(for 8-bit pixels, k=8, use j =12, perhaps)Initialize table with the 2k possible symbols.S ← “” (null string)while there are more symbols in inputP ← current symbolif string SP is in table, S ← SPelseoutput j-bit code for Sadd SP to table if there is roomS ← Poutput j-bit code for SExploiting Interpixel Redundancy, 1Neighboring pixel values are similar and correlated, both in spaceand in time, i.e. pixels are not independent random variables.Note: on certain images, the following methods cause expansion, not compression.Hybrid methods switch between basic methods depending on which gives bestcompression for a given scan line or image region.Three spatial methods for low-noise images:Run-Length Coding (RLC, RLE).Output value1, run-length1, value2, run-length2, ...Good compression if most horizontal neighbor pixels are the same.Poor compression if picture is noisy. Can be done in 1-D or 2-D (the CCITT†FAX standard uses both).Quadtrees: recursively subdivide until cells are constant color.Good if picture has large regions of constant color with horz. & vert. boundaries.Region Encoding: encode boundary curves of constant-color regions.Good if picture has large regions of constant color.† International Telegraph and Telephone Consultative CommitteeExploiting Interpixel Redundancy, 2Three spatial methods that tolerate noise better:Predictive Coding: predict next pixel based on previous, output differencebetween actual and predicted.Fractal Image Compression: decribe image in terms of recursive affinetransformations.Transform Coding: transform to a frequency or other domain wherecorrelation is lower.Examples: Discrete Cosine Transform (DCT), DFT, Karhunen-Loeve Transform.Used in JPEG.Temporal method:Motion Compensation: exploit interframe coherence.Exploit similarity between corresponding pixels of successive frames of motionsequence. Used in MPEG.JPEG & Discrete Cosine TransformThe discrete cosine transform (DCT) is frequently used for lossy compression. Likea DFT, but all real (uses cosines instead of complex exponentials).JPEG (Joint Photographic Experts Group) still picture compressionstandard uses the following steps:– subdivide image into N×N subimages (blocks), N=8 is common– DCT each block– quantize, zigzag order, and run-length code the coefficients– use variable length coding (e.g. Huffman coding)JPEG can compress many computer-generated pictures to 1-2 bits per pixel, andnatural images to about 4 bits per pixel, with little visible error.Fuv cucv f xyxuNyvNcu N u NyNxN( , ) ( ) ( ) ( , )cos()cos()() / , /=++===−=−∑∑2122121020101ππwhere if otherwiseGoals of MPEG Digital Video StandardMPEG (Motion Picture Experts Group) video compression standardhad the following goals:• VHS-quality video for 1.5 Mbits/sec– (a naive encoding might use 640 × 480 × 24 × 30 = 221 Mbits!)• random access• fast forward/reverse, play backward• audio/video synchronization• robust to errors• editable• flexible format (size & frame rate)• real time encoder implementable in 1990 hardwareMPEG Digital Video StandardMPEG compression steps build on JPEG:• motion compensation using 16x16 pixel blocks• discrete cosine transform (DCT) of 8x8 blocks• quantization• run-length coding of zig-zag scan of DCT coefficients• Huffman codingTo exploit temporal coherence, three frame types:I = Intrapictureself-contained (a JPEG, basically) - biggest, easiest to decodeP = Predicted picturedescribed relative to previous I or P frame using motion vectors on image blocks,and JPEG-like coding of differencesB = bidirectional
View Full Document
Unlocking...