1、CS 414 Multimedia Systems Design Lecture 7 Basics of Compression(Part 1)CS 414-Spring 2014Administrative nMP1 is postednSee Class website and compassnMP1 lecture will be on February 7 in class.Please,read the MP1 before attending the classnMP1 due February 19(Wednesday)5pm.Question on DLP 3D Glasses
2、nDLP=Digital Light Processing nDLP=projection technology nDLP=A Texas Instrument process of projecting video images using a light source reflecting off an array of tens of thousands of microscopic mirrors.CS 414-Spring 2014Today Introduced ConceptsnNeed for compression and compression algorithms cla
3、ssificationnBasic Coding ConceptsFixed-length coding and variable-length codingCompression RatioEntropynRLE Compression(Entropy Coding)nHuffman Compression(Statistical Entropy Coding)CS 414-Spring 2014Reading nMedia Coding and Content Processing,Steinmetz,Nahrstedt,Prentice Hall,2002Data Compression
4、 chapter 7nBasic coding concepts Sections 7.1-7.4 and lecture notesCS 414-Spring 2014Integrating Aspects of MultimediaCS 414-Spring 2014Image/VideoCaptureImage/Video InformationRepresentationMediaServerStorageTransmissionCompressionProcessingAudio/VideoPresentationPlaybackAudio/Video Perception/Play
5、backAudio InformationRepresentationTransmissionAudioCaptureA/V PlaybackNeed for CompressionnUncompressed audion8 KHz,8 bit8K per second30M per hourn44.1 KHz,16 bit88.2K per second317.5M per hourn100 Gbyte disk holds 315 hours of CD quality musicnUncompressed videon640 x 480 resolution,8 bit color,24
6、 fps7.37 Mbytes per second26.5 Gbytes per hourn640 x 480 resolution,24 bit(3 bytes)color,30 fps27.6 Mbytes per second99.5 Gbytes per hourn1980 x 1080 resolution,24 bits,60 fps(384,912 MBps)1,385 Gbyte per 1 hour of HDTVCS 414-Spring 2014Broad ClassificationnEntropy Coding(statistical)lossless;indepe
7、ndent of data characteristicse.g.RLE,Huffman,LZW,Arithmetic codingnSource Codinglossy;may consider semantics of the datadepends on characteristics of the datae.g.DCT,DPCM,ADPCM,color model transformnHybrid Coding(used by most multimedia systems)combine entropy with source encodinge.g.,JPEG-2000,H.26
8、4,MPEG-2,MPEG-4,MPEG-7CS 414-Spring 2014Data CompressionnBranch of information theoryminimize amount of information to be transmittednTransform a sequence of characters into a new string of bits same information contentlength as short as possibleCS 414-Spring 2014ConceptsnCoding(the code)maps source
9、 messages from alphabet(A)into code words(B)nSource message(symbol)is basic unit into which a string is partitionedcan be a single letter or a string of lettersnEXAMPLE:aa bbb cccc ddddd eeeeee fffffffggggggggA=a,b,c,d,e,f,g,spaceB=0,1CS 414-Spring 2014Taxonomy of CodesnBlock-blocksource msgs and co
10、de words of fixed length;e.g.,ASCIInBlock-variablesource message fixed,code words variable;e.g.,Huffman codingnVariable-blocksource variable,code word fixed;e.g.,RLEnVariable-variablesource variable,code words variable;e.g.,ArithmeticCS 414-Spring 2014Example of Block-BlocknCoding“aa bbb cccc ddddd
11、eeeeee fffffffgggggggg”nRequires 120 bitsSymbolCode worda000b001c010d011e100f101g110space111Example of Variable-VariablenCoding“aa bbb cccc ddddd eeeeee fffffffgggggggg”nRequires 30 bits dont forget the spacesSymbolCode wordaa0bbb1cccc10ddddd11eeeeee100fffffff101gggggggg110space111Concepts(cont.)nA
12、code isdistinct if each code word can be distinguished from every other(mapping is one-to-one)uniquely decodable if every code word is identifiable when immersed in a sequence of code wordsne.g.,with previous table,message 11 could be defined as either ddddd or bbbbbbCS 414-Spring 2014Static CodesnM
13、apping is fixed before transmissionmessage represented by same codeword every time it appears in message(ensemble)Huffman coding is an examplenBetter for independent sequencesprobabilities of symbol occurrences must be known in advance;CS 414-Spring 2014Dynamic CodesnMapping changes over timealso re
14、ferred to as adaptive codingnAttempts to exploit locality of referenceperiodic,frequent occurrences of messagesdynamic Huffman is an examplenHybrids?build set of codes,select based on inputCS 414-Spring 2014Traditional Evaluation CriterianAlgorithm complexityrunning timenAmount of compressionredunda
15、ncycompression rationHow to measure?CS 414-Spring 2014Measure of InformationnConsider symbols si and the probability of occurrence of each symbol p(si)nIn case of fixed-length coding,smallest number of bits per symbol needed is L log2(N)bits per symbolExample:Message with 5 symbols need 3 bits(L log
16、25)CS 414-Spring 2014Variable-Length Coding-EntropynWhat is the minimum number of bits per symbol?nAnswer:Shannons result theoretical minimum average number of bits per code word is known as Entropy(H)nEntropy measure of uncertainty in random variableniiispsp1)(log)(2CS 414-Spring 2014Entropy Exampl
17、enAlphabet=A,Bp(A)=0.4;p(B)=0.6nCompute Entropy(H)-0.4*log2 0.4+-0.6*log2 0.6=.97 bitsCS 414-Spring 2014Compression RationCompare the average message length and the average codeword lengthe.g.,average L(message)/average L(codeword)nExample:aa,bbb,cccc,ddddd,eeeeee,fffffff,ggggggggAverage message len
18、gth is 5If we use code-words from slide 11,then nWe have 0,1,10,11,100,101,110 nAverage codeword length is 2.14.BitsCompression ratio:5/2.14=2.336CS 414-Spring 2014SymmetrynSymmetric compressionrequires same time for encoding and decodingused for live mode applications(teleconference)nAsymmetric com
19、pressionperformed once when enough time is availabledecompression performed frequently,must be fastused for retrieval mode applications(e.g.,an interactive CD-ROM)CS 414-Spring 2014Entropy Coding Algorithms(Content Dependent Coding)nRun-length Encoding(RLE)Replaces sequence of the same consecutive b
20、ytes with number of occurrencesNumber of occurrences is indicated by a special flag(e.g.,!)Example:nabcccccccccdeffffggg (20 Bytes)nabc!9def!4ggg(13 bytes)CS 414-Spring 2014Variations of RLE(Zero-suppression technique)nAssumes that only one symbol appears often(blank)nReplace blank sequence by M-byt
21、e and a byte with number of blanks in sequenceExample:M3,M4,M14,nSome other definitions are possibleExample:nM4=8 blanks,M5=16 blanks,M4M5=24 blanksCS 414-Spring 2014Huffman Encoding nStatistical encodingnTo determine Huffman code,it is useful to construct a binary treenLeaves are characters to be e
22、ncodednNodes carry occurrence probabilities of the characters belonging to the subtreenExample:How does a Huffman code look like for symbols with statistical symbol occurrence probabilities:P(A)=8/20,P(B)=3/20,P(C)=7/20,P(D)=2/20?CS 414-Spring 2014Huffman Encoding(Example)P(C)=0.09P(E)=0.11P(D)=0.13
23、P(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 2014Huffman Encoding(Example)P(C)=0.09P(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 b
24、inary 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 2014Huffman Encoding(Example)P(C)=0.09P(E)=0.11P(D)=0.13P(A)=0.16P(B)=0.51P(CE)=0.20P(DA)=0.29P(CEDA)=0.4
25、9P(CEDAB)=1010101Step 3:label left branches of the treeWith 0 and right branches of the treeWith 101CS 414-Spring 2014Huffman Encoding(Example)P(C)=0.09P(E)=0.11P(D)=0.13P(A)=0.16P(B)=0.51P(CE)=0.20P(DA)=0.29P(CEDA)=0.49P(CEDAB)=1010101Step 4:Create Huffman CodeSymbol A=011Symbol B=1Symbol C=000Symbol D=010Symbol E=00101CS 414-Spring 2014Summary nCompression algorithms are of great importance when processing and transmitting AudioImagesVideo CS 414-Spring 2014
