東南大學《圖像處理》chap7--compression第一頁，共54頁。數據編碼信源編碼提高數據表達效率（壓縮）信道編碼提高數據存貯/傳輸可靠性第二頁，共54頁。一些信號的原始數據量信源數據量電話(200Hz–3.4kHz)8k/s×12bits=96kb/s寬帶語音(50Hz–7kHz)16k/s×14bits=224kb/s寬帶音頻(20Hz–20kHz)44.1k/s×2通道×16bits=1.412Mb/s圖像512×512×24bits=6Mb視頻640×480×24bits×30/s=221Mb/s高清晰度電視1280×720×24bits×60/s=1.3Gb/s第三頁，共54頁。數據壓縮的依據–存在數據冗余時間冗余–時間軸上的相關性空間冗余–像素間的相關性信息熵冗余–數據表示的效率知識冗余–先驗知識的利用心理視覺冗余–合理的分辨率第四頁，共54頁。codingredundancyRedundancy:R=1–L/mApproaches:--StandardHuffman--ShiftedHuffman--ArithmeticCodingNoredundancy:8bit第五頁，共54頁。InterpixelredundancySpatialredundancyApproaches:--RunLengthcoding--intraframepredicativecoding--LZWcoding第六頁，共54頁。InterpixelredundancySpatial,timeredundancyApproaches:--interframepredicativecoding(motionprediction)

第七頁，共54頁。PsychovisualredundancyOriginal25%quality15%quality45,339b3,905b3,197bRemoveLessimportantinformationApproaches:--quantization(lossy),DCT

第八頁，共54頁。CompressionsystemmodelTwoparts:Encoder,DecoderSourceencoder:removeredundancyChannelencoder:reducenoise第九頁，共54頁。Sourceencoderanddecoder

Mapper:transforminputdatatoaspecialformatforreducinginterpixelredundancy第十頁，共54頁。數據編碼分類無損壓縮(lossless):~變長編碼（Huffman)~行程編碼~算術編碼醫學或商用數據的壓縮第十一頁，共54頁。有損數據壓縮(lossy)預測編碼變換編碼（Cosine,Wavelet)視頻數據的壓縮第十二頁，共54頁。Run-LengthEncoding(1D)Originaldata:05,05,05,05,11,11,1A,1A,1A,1A,20,22,22,22,22Encoding:05,04,11,02,1A,04,20,01,22,04Application:besuitableforuniformgrayimages,FAXcoding第十三頁，共54頁。Run-LengthEncoding(2D)05,02,05,01,10,01,21,04,05,01,10,01,10,04,21,02,31,02,10,02,10,02,15,01,31,02,31,01,15,01,31,01Rules:◆basicunit--maximalsquare◆left->right,top->bottom

第十四頁，共54頁。LZWcoding根據數據本身包含有重復的字符串(不一定要求空間上相鄰)每接收一個字符系列，判斷以前是否出現過，然后用出現過的字符串代替該重復的部分，輸出對應的“指針”（位置）例如：“aabbccddee”的指針是0100，以后每次出現該字符串，就用0100代替。第十五頁，共54頁。LZWNotesDictionaryisnotnullatfirst,singlesymbolBuildingdecompressiondictionaryisneededApplication:GIF(graphicinterchangeformat)TIFF(taggedimage)PDF(portabledocumentformat)

第十六頁，共54頁。Huffmancoding灰度01234567概率0.050.050.100.150.250.200.150.050.100.150.250.300.450.551.001001010101011編碼011000110110010100110100111編碼:從根節點開始到葉子節點!!第十七頁，共54頁。StandardHuffmancodingAveragebits:2.2 Entropy:2.14efficiency:0.973第十八頁，共54頁。StandardHuffmandisadvantagesEvenif1biterror,aseriesoferrors,nosolutions(exampleinnextpage)Whendecoding,failtoabstractcontentsfromrandomlypositionComputation:k-2sourcerankingTosymbolwithlessprobability:codelengthistoolong(max:k-1bits)--shiftedHuffman第十九頁，共54頁。ErrordecodingexampleofHuffmanCode:011,1,01010,0100,01011,00Gray:a1a2a3a4a5a6a3,a1,a2,a2,a6...010100111100*Encoding:GrayCodeDecoding:CodeGray00101000111100...010100101100...a3,a6,a2,a2,a2,a2,a6...a3,a5,a6...*Add0:errordecoding*011->010,第二十頁，共54頁。ShiftedHuffmanencoding1Truncate:90%(main)--standardHuffmanDivideblocks:assignaprefixtoeachblockShift:prefix+standardHuffmancode第二十一頁，共54頁。ShiftedHuffmanencoding2主區間[120150]，編碼為：c120~c150119=sum(0~119)，低界碼c119151=sum(151~255)，高階碼c151c119和c151分別作為正、負區間碼第二十二頁，共54頁。ShiftedHuffmanencoding30區間：[120150]，120~1501區間：[151181]，c151+0區間中對應位置的編碼，如170-->139,編碼為：c151c1392區間：[182212]，區間碼為：c151

c151

-1區間：[89119]，區間碼為：c119第二十三頁，共54頁。算術編碼(ArithmeticEncoding)將信息量的增加映射為實數精度的提高編碼過程將[0，1）區間不斷細分第二十四頁，共54頁。SymbolABCDProb0.10.40.20.3Interval[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)符號序列：C,A,D,A,C,D,B,...010.50.7C0.520.5A0.5140.52D0.5140.5146A...第二十五頁，共54頁。LossycompressionLossless:8:1lossy:100:1~200:1,quantization10：1to100：1sameinhumaneyesJPEG,MPEG,H.263~Lossypredictivecoding~Transformbasedcoding第二十六頁，共54頁。Lossypredictivecoding第二十七頁，共54頁。DPCM(differentialpulsecodemodulation)Difference:Predictor:第二十八頁，共54頁。Deltamodulation(DM)Simplestpredictor:m=1Quantier1bit/pixel

Problems:

Slopeoverload:whengrayvalueschangerapidlydistortionedgeblurredGranularnoise:whengrayvalueschangesmall

spotnoise第二十九頁，共54頁。Problemsofdeltamodulation第三十頁，共54頁。Optimalpredictor

Minimizing:第三十一頁，共54頁。Optimalpredictor

第三十二頁，共54頁。GlobalpredicatorFixedpredictivecoefficients:第三十三頁，共54頁。Comparisonoffourpredicatorsm=1,2,3,1,階數增加,誤差減小

第三十四頁，共54頁。TransformbasedcodingPrinciple:~Magnitudenear0inhigherfrequency~Datacompressionremovingthosedatanear0,samevisualresult

正交變換

DFT，DCT，Wavelet,第三十五頁，共54頁。Transformbasedcodingmodel能量最高的系數被最細量化，而能量較低的系數就被粗量化或被簡單地舍去。優點：變換系數的編碼誤差只影響該系數所在的塊，不會擴散到其他的子塊，故變換編碼的抗干擾能力優于預測編碼。第三十六頁，共54頁。subimagesizeSize:largerthan8*8saturation

第三十七頁，共54頁。ImageCompressionStandardsJointPhotographicsExpertsGroup(JPEG)

reordering第三十八頁，共54頁。JPEGCoderDC:F(0,0),DPCMAC:RLC,HuffmanDCTcoefficients:Zig-Zigreordering

第三十九頁，共54頁。originalimagesize:66616bytesJPEGcompressedsize：8181bytesqualityfactor:0.6第四十頁，共54頁。originalimagesize:66616bytesJPEGcompressedsize：2742bytesqualityfactor:0.1第四十一頁，共54頁。視頻編碼技術國際電聯(ITU-T),~標準有:H.261、H.262、H.263、H.263+國際標準化組織(ISO)~標準有MPEG-1、MPEG-2、MPEG-4、MPEG-7由兩個組織聯合組建的聯合視頻組(JVT)共同制定的新數字視頻編碼標準:~H.264,MPEG-4part10(>100:1)第四十二頁，共54頁。●四種圖像I-圖像

幀內圖，每個圖像群組由此類型的圖像開始。編碼時獨立編碼（JPEG），解碼時不參考其他幀；P-圖像

預測圖，用前面的I圖或P圖像進行預測編碼得到，并可以作為下一個預測（B圖像或P圖像）的參照圖像。B-圖像

插補圖(雙向預測圖)，預測時,需要用先前及后續的若干個圖像作參考，并作運動補償和運動估計；D-圖像，用于快速進帶。僅由DC直流分量構造的圖像，可在低比特率的時候做瀏覽用。MPEG第四十三頁，共54頁。●視頻流的組成:允許編碼端自行選擇I圖像的使用頻率和在視頻流中的位置。允許編碼端自行選擇任意兩幀參考圖像（I-圖或P-圖）之間的B圖像數。編碼端的視頻流記錄格式可以和圖像顯示順序不同。顯示的順序：I

BBPBB

PB

BP

BB

P

B

B

I……

12345678910111213141516……視頻流順序：IPBBPBBPBBPBBIBB……14237561089131112161415……MPEG第四十四頁，共54頁。“I-圖像”