东南大学《图像处理》chap7-compression

东南大学《图像处理》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-图像”