CS 414 – Multimedia Systems Design Lecture 7 – Basics of Compression (Part 2)AdministrativeOutlineHuffman EncodingHuffman Encoding (Example)Slide 6Slide 7Slide 8Huffman DecodingHuffman ExampleCharacteristics of SolutionExample Encoding/DecodingEntropy (Theoretical Limit)Average Codeword LengthCode Length Relative to EntropyExampleGroup ExerciseLimitationsArithmetic CodingArithmetic CodingSlide 21Slide 22Adaptive Encoding (Adaptive Huffman)Adaptive Huffman Coding ExampleHybrid Coding (Usage of RLE/Huffman, Arithmetic Coding)Picture PreparationOther Compression StepsAudio Compression and Formats (Hybrid Coding Schemes)Image Compression and FormatsVideo Compression and Formats (Hybrid Coding Schemes)SummarySolutionCS 414 - Spring 2011CS 414 – Multimedia Systems Design Lecture 7 – Basics of Compression (Part 2)Klara NahrstedtSpring 2011CS 414 - Spring 2011Administrative MP1 is postedOutlineStatistical Entropy Coding Huffman codingArithmetic coding CS 414 - Spring 2011Huffman Encoding Statistical encodingTo determine Huffman code, it is useful to construct a binary treeLeaves are characters to be encodedNodes carry occurrence probabilities of the characters belonging to the sub-treeCS 414 - Spring 2011Huffman Encoding (Example)P(C) = 0.09 P(E) = 0.11P(D) = 0.13P(A)=0.16P(B) = 0.51Step 1 : Sort all Symbols according to their probabilities (left to right) from Smallest to largest these are the leaves of the Huffman treeCS 414 - Spring 2011Huffman Encoding (Example)P(C) = 0.09 P(E) = 0.11P(D) = 0.13P(A)=0.16P(B) = 0.51P(CE) = 0.20P(DA) = 0.29P(CEDA) = 0.49P(CEDAB) = 1Step 2: Build a binary tree from left toRight Policy: always connect two smaller nodes together (e.g., P(CE) and P(DA) had both Probabilities that were smaller than P(B),Hence those two did connect firstCS 414 - Spring 2011Huffman Encoding (Example)P(C) = 0.09 P(E) = 0.11P(D) = 0.13P(A)=0.16P(B) = 0.51P(CE) = 0.20P(DA) = 0.29P(CEDA) = 0.49P(CEDAB) = 10 10101Step 3: label left branches of the treeWith 0 and right branches of the treeWith 101CS 414 - Spring 2011Huffman Encoding (Example)P(C) = 0.09 P(E) = 0.11P(D) = 0.13P(A)=0.16P(B) = 0.51P(CE) = 0.20P(DA) = 0.29P(CEDA) = 0.49P(CEDAB) = 10 10101Step 4: Create Huffman CodeSymbol A = 011Symbol B = 1Symbol C = 000Symbol D = 010Symbol E = 0010 1CS 414 - Spring 2011Huffman DecodingAssume Huffman TableSymbol Code X 0 Y 10 Z 11Consider encoded bitstream: 000101011001110CS 414 - Spring 2011What is the decoded string?Huffman ExampleConstruct the Huffman coding tree (in class)Symbol (S) P(S)A 0.25B 0.30C 0.12D 0.15E 0.18Characteristics of Solution Symbol (S) CodeA 01B 11C 100D 101E 00CS 414 - Spring 2011Example Encoding/DecodingEncode “BEAD”110001101Decode “0101100”Symbol (S) CodeA 01B 11C 100D 101E 00CS 414 - Spring 2011Entropy (Theoretical Limit)= -.25 * log2 .25 + -.30 * log2 .30 + -.12 * log2 .12 + -.15 * log2 .15 + -.18 * log2 .18H = 2.24 bitsNiii spspH1)(log)( 2Symbol P(S) CodeA 0.25 01B 0.30 11C 0.12 100D 0.15 101E 0.18 00Average Codeword Length= .25(2) +.30(2) +.12(3) +.15(3) +.18(2)L = 2.27 bitsNiiiscodelengthspL1)()(Symbol P(S) CodeA 0.25 01B 0.30 11C 0.12 100D 0.15 101E 0.18 00Code Length Relative to EntropyHuffman reaches entropy limit when all probabilities are negative powers of 2i.e., 1/2; 1/4; 1/8; 1/16; etc.H <= Code Length <= H + 1Niii spspH1)(log)( 2NiiiscodelengthspL1)()(CS 414 - Spring 2011ExampleH = -.01*log2.01 + -.99*log2.99 = .08L = .01(1) +.99(1) = 1Symbol P(S) CodeA 0.01 1B 0.99 0CS 414 - Spring 2011Group ExerciseCompute Entropy (H)Build Huffman treeCompute averagecode lengthCode “BCCADE”Symbol (S) P(S)A 0.1B 0.2C 0.4D 0.2E 0.1CS 414 - Spring 2011LimitationsDiverges from lower limit when probability of a particular symbol becomes highalways uses an integral number of bitsMust send code book with the datalowers overall efficiencyMust determine frequency distributionmust remain stable over the data setCS 414 - Spring 2011Arithmetic Coding Optimal algorithm as Huffman coding wrt compression ratioBetter algorithm than Huffman wrt transmitted amount of information Huffman – needs to transmit Huffman tables with compressed dataArithmetic – needs to transmit length of encoded string with compressed dataCS 414 - Spring 2011Arithmetic CodingEach symbol is coded by considering the prior dataEncoded data must be read from the beginning, there is no random access possibleEach real number (< 1) is represented as binary fraction 0.5 = 2-1 (binary fraction = 0.1); 0.25 = 2-2 (binary fraction = 0.01), 0.625 = 0.5+0.125 (binary fraction = 0.101) ….CS 414 - Spring 2011CS 414 - Spring 2011CS 414 - Spring 2011Adaptive Encoding (Adaptive Huffman)Huffman code change according to usage of new words and new probabilities can be assigned to individual lettersIf Huffman tables adapt, they must be transmitted to receiver sideCS 414 - Spring 2011Adaptive Huffman Coding ExampleSymbol Code Original probabilities A 001 P(A) = 0.16B 1 P(B) = 0.51C 011 P( C) = 0.09D 000 P(D) = 0.13E 010 P(E) = 0.11Symbol Code New Probabilities (based on new word BACAAB)A 1 P(A) = 0.5B 01 P(B) = 1/3C 001 P(C ) = 1/6D 0000 P(D) = 0E 0001 P(E) = 0CS 414 - Spring 2011Hybrid Coding (Usage of RLE/Huffman, Arithmetic Coding) CS 414 - Spring 2011RLE, HuffmanArithmeticCodingPicture PreparationGeneration of appropriate digital representationImage division into 8x8 blocksFix number of bits per pixel (first level quantization – mapping from real numbers to bit representation)CS 414 - Spring 2011Other Compression Steps Picture processing (Source Coding)Transformation from time to frequency domain (e.g., use Discrete Cosine Transform)Motion vector computation in video Quantization Reduction of precision, e.g., cut least significant bitsQuantization matrix, quantization valuesEntropy Coding Huffman Coding + RLE CS 414 - Spring 2011Audio Compression and Formats (Hybrid Coding Schemes)MPEG-3 ADPCMu-LawReal AudioWindows Media (.wma)Sun (.au)Apple (.aif)Microsoft (.wav)CS 414 - Spring 2011Image Compression and FormatsRLEHuffmanLZWGIFJPEG / JPEG-2000 (Hybrid Coding)FractalsTIFF, PICT, BMP, etc.CS 414 - Spring 2011Video Compression and Formats (Hybrid Coding Schemes)H.261/H.263/H.264Cinepak (early 1992 Apple’s video codec in
View Full Document
Unlocking...