數(shù)字圖像處理壓縮基礎(chǔ)知識課件

CS414–MultimediaSystemsDesign

Lecture7–BasicsofCompression(Part1)

CS414-Spring2014AdministrativeMP1ispostedSeeClasswebsiteandcompassMP1lecturewillbeonFebruary7inclass.Please,readtheMP1beforeattendingtheclassMP1dueFebruary19(Wednesday)5pm.QuestiononDLP3DGlassesDLP=DigitalLightProcessingDLP=projectiontechnologyDLP=ATexasInstrumentprocessofprojectingvideoimagesusingalightsourcereflectingoffanarrayoftensofthousandsofmicroscopicmirrors….CS414-Spring2014TodayIntroducedConceptsNeedforcompressionandcompressionalgorithmsclassificationBasicCodingConceptsFixed-lengthcodingandvariable-lengthcodingCompressionRatioEntropyRLECompression(EntropyCoding)HuffmanCompression(StatisticalEntropyCoding)CS414-Spring2014ReadingMediaCodingandContentProcessing,Steinmetz,Nahrstedt,PrenticeHall,2002DataCompression–chapter7Basiccodingconcepts–Sections7.1-7.4andlecturenotesCS414-Spring2014IntegratingAspectsofMultimediaCS414-Spring2014Image/VideoCaptureImage/VideoInformationRepresentationMediaServerStorageTransmissionCompressionProcessingAudio/VideoPresentationPlaybackAudio/VideoPerception/PlaybackAudioInformationRepresentationTransmissionAudioCaptureA/VPlaybackNeedforCompressionUncompressedaudio8KHz,8bit8Kpersecond30Mperhour44.1KHz,16bit88.2Kpersecond317.5Mperhour100Gbytediskholds315hoursofCDqualitymusicUncompressedvideo640x480resolution,8bitcolor,24fps7.37Mbytespersecond26.5Gbytesperhour640x480resolution,24bit(3bytes)color,30fps27.6Mbytespersecond99.5Gbytesperhour1980x1080resolution,24bits,60fps(384,912MBps)1,385Gbyteper1hourofHDTVCS414-Spring2014BroadClassificationEntropyCoding(statistical)lossless;independentofdatacharacteristicse.g.RLE,Huffman,LZW,ArithmeticcodingSourceCodinglossy;mayconsidersemanticsofthedatadependsoncharacteristicsofthedatae.g.DCT,DPCM,ADPCM,colormodeltransformHybridCoding(usedbymostmultimediasystems)combineentropywithsourceencodinge.g.,JPEG-2000,H.264,MPEG-2,MPEG-4,MPEG-7CS414-Spring2014DataCompressionBranchofinformationtheoryminimizeamountofinformationtobetransmittedTransformasequenceofcharactersintoanewstringofbitssameinformationcontentlengthasshortaspossibleCS414-Spring2014ConceptsCoding(thecode)mapssourcemessagesfromalphabet(A)intocodewords(B)Sourcemessage(symbol)isbasicunitintowhichastringispartitionedcanbeasingleletterorastringoflettersEXAMPLE:aabbbccccdddddeeeeeefffffffggggggggA={a,b,c,d,e,f,g,space}B={0,1}CS414-Spring2014TaxonomyofCodesBlock-blocksourcemsgsandcodewordsoffixedlength;e.g.,ASCIIBlock-variablesourcemessagefixed,codewordsvariable;e.g.,HuffmancodingVariable-blocksourcevariable,codewordfixed;e.g.,RLEVariable-variablesourcevariable,codewordsvariable;e.g.,ArithmeticCS414-Spring2014ExampleofBlock-BlockCoding“aabbbccccdddddeeeeeefffffffgggggggg”Requires120bitsSymbolCodeworda000b001c010d011e100f101g110space111ExampleofVariable-VariableCoding“aabbbccccdddddeeeeeefffffffgggggggg”Requires30bitsdon’tforgetthespacesSymbolCodewordaa0bbb1cccc10ddddd11eeeeee100fffffff101gggggggg110space111Concepts(cont.)Acodeisdistinctifeachcodewordcanbedistinguishedfromeveryother(mappingisone-to-one)uniquelydecodable

ifeverycodewordisidentifiablewhenimmersedinasequenceofcodewordse.g.,withprevioustable,message11couldbedefinedaseitherdddddorbbbbbbCS414-Spring2014StaticCodesMappingisfixedbeforetransmissionmessagerepresentedbysamecodewordeverytimeitappearsinmessage(ensemble)HuffmancodingisanexampleBetterforindependentsequencesprobabilitiesofsymboloccurrencesmustbeknowninadvance;CS414-Spring2014DynamicCodesMappingchangesovertimealsoreferredtoasadaptivecodingAttemptstoexploitlocalityofreferenceperiodic,frequentoccurrencesofmessagesdynamicHuffmanisanexampleHybrids?buildsetofcodes,selectbasedoninputCS414-Spring2014TraditionalEvaluationCriteriaAlgorithmcomplexityrunningtimeAmountofcompressionredundancycompressionratioHowtomeasure?CS414-Spring2014MeasureofInformationConsidersymbols

siandtheprobabilityofoccurrenceofeachsymbolp(si)Incaseoffixed-lengthcoding,smallestnumberofbitspersymbolneededisL≥log2(N)bitspersymbolExample:Messagewith5symbolsneed3bits(L≥log25)CS414-Spring2014Variable-LengthCoding-EntropyWhatistheminimumnumberofbitspersymbol?Answer:Shannon’sresult–theoreticalminimumaveragenumberofbitspercodewordisknownasEntropy(H)Entropy–measureofuncertaintyinrandomvariableCS414-Spring2014EntropyExampleAlphabet={A,B}p(A)=0.4;p(B)=0.6ComputeEntropy(H)-0.4*log20.4+-0.6*log20.6=.97bitsCS414-Spring2014CompressionRatioComparetheaveragemessagelengthandtheaveragecodewordlengthe.g.,averageL(message)/averageL(codeword)Example:{aa,bbb,cccc,ddddd,eeeeee,fffffff,gggggggg}Averagemessagelengthis5Ifweusecode-wordsfromslide11,thenWehave{0,1,10,11,100,101,110}Averagecodewordlengthis2.14..BitsCompressionratio:5/2.14=2.336CS414-Spring2014SymmetrySymmetriccompressionrequiressametimeforencodinganddecodingusedforlivemodeapplications(teleconference)Asymmetriccompressionperformedoncewhenenoughtimeisavailabledecompressionperformedfrequently,mustbefastusedforretrievalmodeapplications(e.g.,aninteractiveCD-ROM)CS414-Spring2014EntropyCodingAlgorithms(ContentDependentCoding)Run-lengthEncoding(RLE)ReplacessequenceofthesameconsecutivebyteswithnumberofoccurrencesNumberofoccurrencesisindicatedbyaspecialflag(e.g.,!)Example:abcccccccccdeffffggg(20Bytes)abc!9def!4ggg(13bytes)CS414-Spring2014VariationsofRLE(Zero-suppressiontechnique)Assumesthatonlyonesymbolappearsoften(blank)ReplaceblanksequencebyM-byteandabytewithnumberofblanksinsequenceExample:M3,M4,M14,…SomeotherdefinitionsarepossibleExample:M4=8blanks,M5=16blanks,M4M5=24blanksCS414-Spring2014HuffmanEncodingStatisticalencodingTodetermineHuffmancode,itisusefultoconstructabinarytreeLeavesarecharacterstobeencodedNodescarryoccurrenceprobabilitiesofthecharactersbelongingtothesubtreeExample:HowdoesaHuffmancodelooklikeforsymbolswithstatisticalsymboloccurrenceprobabilities:P(A)=8/20,P(B)=3/20,P(C)=7/20,P(D)=2/20?CS414-Spring2014HuffmanEncoding(Example)P(C)=0.09P(E)=0.11P(D)=0.13P(A)=0.16P(B)=0.51Step1:SortallSymbolsaccordingtotheirprobabilities(lefttoright)fromSmallesttolargestthesearetheleavesoftheHuffmantreeCS414-Spring2014HuffmanEncoding(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)=1Step2:BuildabinarytreefromlefttoRightPolicy:alwaysconnect