Chap图象压缩与编码实用.pptx

《Chap图象压缩与编码实用.pptx》由会员分享，可在线阅读，更多相关《Chap图象压缩与编码实用.pptx（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图象压缩与编码图象压缩与编码 数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。如一幅512x512的黑白图象的比特数为 512x512x8=2,097,152 bit2,097,152 bit=256k256k。再如一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R R、GG、B B三分量分别占8 bit，总比特数为第1页/共64页图象压缩与编码图象压缩与编码 90 x60 x24x3x512x512x8bit=97,200M97,200M。如一张CD光盘可存600兆字节数据，这部电影光图象（还有声音）就需

2、要160160张CD光盘用来存储。对图象数据进行压缩显得非常必要。本章讨论的问题：在满足一定条件下，能否减小图象bit数，以及用什么样的编码方法使之减少。第2页/共64页英文字母出现相对频率英文字母出现相对频率字母字母A AB BC CD DE EF FGGH HI IJ JK KL LMM百分比百分比8.28.21.51.52.82.84.34.312.712.72.22.22.02.06.16.17.07.00.20.20.80.84.04.02.42.4字母字母N NOOP PQQR RS ST TU UV VWWX XY YZ Z百分比百分比6.76.77.57.51.91.90.10

3、.16.06.06.36.39.19.12.82.81.01.02.42.40.20.22.02.00.10.1第3页/共64页英文字母出现相对频率英文字母出现相对频率第4页/共64页图象编码图象编码密码密码点点击击图图片片播播放放视视频频某个图形或物品也可以作为密码。某个图形或物品也可以作为密码。第5页/共64页图象编码图象编码密码密码虹膜与指纹。虹膜与指纹。第6页/共64页图象压缩与编码图象压缩与编码1图象数据压缩是可能的：一般原始图象中存在很大的冗余度。用户通常允许图象失真。当信道的分辨率不及原始图象的分辨率时，降低输入的原始图象的分辨率对输出图象分辨率影响不大。用户对原始图象的信号不全

4、都感兴趣，可用特征提取和图象识别的方法，丢掉大量无用的信息。提取有用的信息，使必须传输和存储的图象数据大大减少。第7页/共64页图象压缩与编码图象压缩与编码2原始图象越有规则，各象素之间的相关性越强，它可能压缩的数据就越多。值得指出的是：当前采用的编码方法得到的结果，离可能压缩的极限还相差很远，这说明图象数据压缩的潜力是很大的，直到目前为止，它还是个正在继续研究的领域。第8页/共64页图象压缩与编码图象压缩与编码3图象结构的性质，大体上可分为两大类，一类是具有一定图形特征的结构，另一类是具有一定概率统计特性的结构。基于不同的图象结构特性，应采用不同的压缩编码方法。第9页/共64页图象压缩与编码

5、图象压缩与编码4全面评价一种编码方法的优劣，除了看它的编编码码效效率率、实实时时性性和失失真真度度以外，还要看它的设备复杂程度设备复杂程度，是否经济与实用经济与实用。常采用混合编码的方案，以求在性能和经济上取得折衷。随着计算方法及VLSI的发展，使许多高效而又比较复杂的编码方法在工程上有实现的可能。第10页/共64页信源编码的基本概念信源编码的基本概念 图象数据压缩的目目的的是在满足一定图象质量条件下，用尽可能少的比特数来表示原始图象，以提高图象传输的效率和减少图象存储的容量，在信息论中称为信源编码信源编码。信源编码可分为两大类，一类是无无失失真真编编码码，另一类是有有失失真真编编码码或称限失

6、真编码限失真编码。第11页/共64页无失真编码无失真编码 无失真编码又称信息保持编码或可逆的无误差编码。信息量：从N个相等可能发生的事件中，选出其中一个事件所需的信息度量，称为信息量。第12页/共64页 无失真编码无失真编码 要辨识1到32中选定的某一个数，可先提问：“是否大于16？”，得到回答就消去半数可能事件。每提问一次得到回答，可以得到1bit信息量（二进制位）。这里共需5次，因此所需的信息量为 。第13页/共64页无失真编码无失真编码 定定义义信信息息量量：从N个数选定一个数s的概率为p(s)，且等概率，p(s)=1/N。熵熵：设信源符号表为 s=s1,s2,sq，其概率分布为P(s)

7、=p(s1),p(s2),p(sq)，则信源的熵熵为第14页/共64页无失真编码无失真编码 s作为灰度，共q级，出现概率均等时，p(si)=1/q，当灰度只有两级时，即si=0,1，且0出现概率为p1，1出现概率为p2=1-p1，其熵第15页/共64页无失真编码无失真编码 当p1=1/2，p2=1-p1=1/2时，H(s)=1为最大值。如图所示。第16页/共64页无失真编码无失真编码熵的性质：熵的性质：（1）熵是一个非负数，即总有H(s)0。（2）当其中一个符号sj的出现概率p(sj)=1时，其余符号si(ij)的出现概率p(si)=0，H(s)=0。（3）当各个si出现的概率相同时，则最大平

8、均信息量为log2 q。（4）熵值总有H(s)log2 q。第17页/共64页无失真编码无失真编码(一)无失真编码定理 可以证明，在无干扰的条件下，存在一种无失真的编码方法，使编码的平均长度 L与信源的熵H(s)任意地接近，即L=H(s)+，其中为任意小的正数，但以H(s)为其下限，即LH(s)，这就是香香农农(Shannon)(Shannon)无无干干扰扰编码定理编码定理。第18页/共64页无失真编码无失真编码(二)熵与相关性、冗余度的关系熵与相关性、冗余度的关系 对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原

9、始图象的熵。原始图象冗余度冗余度定义为：第19页/共64页无失真编码无失真编码 将编码效率定义为：冗余度接近于0，或编码效率接近于1的编码称为高效码。第20页/共64页无失真编码无失真编码 若原始图象的平均比特率为n，编码后的平均比特率为nd，则压缩比压缩比C定义为：由Shannon定理，无失真编码最大可能的数据压缩比最大可能的数据压缩比为：第21页/共64页无失真编码无失真编码 独立信源的熵与马尔可夫信源的熵独立信源的熵与马尔可夫信源的熵 令q=2L，其中L等于自然二进制码的长度。可以证明，对于独立信源，等概率分布时，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能

10、压缩。讨论讨论（1）独立信源独立信源，又称无记忆信源无记忆信源，符号si 的出现，与其他的符号无关。第22页/共64页无失真编码无失真编码 非等概率分布时的熵，一般有H1(s)0，还有可能压缩。（2）有限马尔可夫有限马尔可夫(Markov)(Markov)信源的熵信源的熵 又称有限记忆信源有限记忆信源，它的统计特性要用转移概率转移概率或条件概率条件概率来描述。m阶Markov信源，是指某个符号si出现的概率只与前面m个符号有关。第23页/共64页无失真编码无失真编码 设s=s1,s2,sq，则转移概率 p(si/si1,si2,sim)乃是前m个符号为si1,si2,sim时，第 m+1个符号

11、为si的概率。信息量 I(si/si1,si2,sim)=-log2 p(si/si1,si2,sim)第24页/共64页无失真编码无失真编码 对符号表取平均的信息量 这是在给定序列si1,si2,sim的条件下，信源的条件熵。第25页/共64页无失真编码无失真编码 再考虑序列si1,si2,sim发生的概率，可将mm阶阶MarkovMarkov信源的信源的熵熵定义为：第26页/共64页无失真编码无失真编码（四）高效的编码方法高效的编码方法 无干扰编码定理只指出存在一种无失真的编码，可使 。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。（1）HuffmanHuffman码码 它是长度

12、不均匀的，其平均长度最短的即时可译码。其要点要点是对经常出现的符第27页/共64页英文字母出现相对频率英文字母出现相对频率字母字母A AB BC CD DE EF FGGH HI IJ JK KL LMM百分比百分比8.28.21.51.52.82.84.34.312.712.72.22.22.02.06.16.17.07.00.20.20.80.84.04.02.42.4字母字母N NOOP PQQR RS ST TU UV VWWX XY YZ Z百分比百分比6.76.77.57.51.91.90.10.16.06.06.36.39.19.12.82.81.01.02.42.40.20.2

13、2.02.00.10.1第28页/共64页英文字母出现相对频率英文字母出现相对频率第29页/共64页国际莫尔斯电码符号国际莫尔斯电码符号SymboSymbol lA AB BC CD DE EF FGGH HI IJ JK KL LMMCodeCode.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-SymboSymbol lN NOOP PQQR RS ST TU UV VWWX XY YZ ZCodeCode-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.SymboSymbol l0 01 12 23 34 45 56 67 78 89

14、 9CodeCode-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.SymboSymbol l.,?:;-/“CodeCode.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.第30页/共64页无失真编码无失真编码号赋予最短的码字，然后按出现概率减少的次序，逐个赋予较长的码字，这样可使码的平均长度具有最小值，pi-si出现概率，li-对si编码的长度。第31页/共64页无失真编码无失真编码 信信号号源源 s s=s=s1 1,s s2 2,s s3 3,s s4 4,s s5 5,s s6 6，其其概概率率分分布布为为p p1 1=0

15、.4=0.4 p p2 2=0.3=0.3 p p3 3=0.1=0.1 p p4 4=0.1 p=0.1 p5 5=0.06 p=0.06 p6 6=0.04=0.04，求最佳，求最佳HuffmanHuffman码。码。方法：方法：i.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。第32页/共64页无失真编码无失真编码方法：方法：ii.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。iii.重复上述做法，直到最后剩下两个概率为止。iv.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个

16、二进制码，如对概率大的赋予码元0，对概率小的赋予码元1。第33页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第34页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第35页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第36页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.1

17、0.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第37页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4第38页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101第39页/共64页H

18、uffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1第40页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00第41页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.0

19、4第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011第42页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100第43页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.3

20、0.3第四步0.60.40101010101S5=01010第44页/共64页Huffman编码编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011第45页/共64页无失真编码无失真编码（2）B B码码 在某些应用中，编码器输入符号集合的概率分布服从乘幂律：pk=k-r,k=1,2,q。r为正常数，则用B码，它接近于最佳编码。B码是一种非等长码，由两部分组成，一部分叫“延延续续比比特特”，一部分叫“信信息息比比特特”。延续比

21、特的作用是标注一个码字究竟延续多长，信息比特的作用是表示不同的信息符号。第46页/共64页无失真编码无失真编码方法：方法：将信源符号按出现概率从大到小排序，然后按B1码的前后顺序分别赋予相应符号，便得到各符号的B1码。其中信息码是按二进制的长度及数的顺序排列的，即0，1，00，01，10，11，000，001，。延续码C是在编码过程中确定的，可将C=0赋予前一个码字，将C=1赋予后一个码字，再将C=0赋予下一个码字。第47页/共64页无失真编码无失真编码方法：方法：例如，编码器输入符号序列为s4s1s5s2,则B1码为：0 000 01，1 10，0 010 00，1 11，或者 1 101

22、11，0 00，1 111 10，0 01，延续码改变，表示前一个码字结束，后一个码字开始。B B1 1码优点：码优点：编码方法简单，容易实现。第48页/共64页无失真编码无失真编码（3）移位码移位码S S2 2 对具有单调减小概率的输入信号相当有效的非等长码。S2码由2bit长的码字组成，总共包含四个不同的码字：C1=00，C2=01，C3=10，C4=11，C4的个数用来表示该符号的序数超过3的次数。符号编码：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，这种编码方法更简单。第49页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6

23、rCH(s)概率0.40.30.10.10.060.04第50页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14第51页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14第52页/共64页几种

24、几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14第53页/共64页几种几种编码比较编码比较输入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼码100011010001010010112.20.9750.0251.362.14B1码C0C1C

25、0C0C0C1C1C0C1C12.60.8250.211.152.14S2码0001101100110111102.40.8950.1151.252.14自然码00000101001110010130.7130.40212.14第54页/共64页限失真编码限失真编码 严格的无失真编码的压缩比一般是不大的。编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面，用户通常允许图象有一定的失真，这为图象数据压缩提供了较大的可能性，因此人们非常注意限失真编码问题。在给定失真条件下，信源编码所能达到的压缩率的极限码率，称为率率失失真函数真函数，R R(D D)，D为失真上限。第55页/共64页限失真

26、编码限失真编码 R(0)H(Y)，收到的信号序列不存在相关性时，等号成立。D，R(D)。允许失真度D越小，则所需率失真函数值R(D)就越大，要求信源编码效率也越高。第56页/共64页p.436p.436第57页/共64页图象编码模型图象编码模型映射变换器量化器编码器原始图象码字图象压缩编码的一般框图第58页/共64页图象编码模型图象编码模型 映映射射变变换换：将输入数据从象素域变换到另一个域，在变换域中则能以较少的比特数对图象进行量化编码。对映射变换器的要求，要从数据压缩的有效性、保真度和经济实用方面考虑，应该是i.高度去相关的、ii.可逆的、iii.重现的均方误差最小、iv.易于实现的。第5

27、9页/共64页图象编码模型图象编码模型（1 1）行程编码）行程编码 把沿着扫描行的象素序列x1,x2,xN映射为行程序列(g1,l1),(g2,l2),(gk,lk)。gi灰度级 ligi的行程长度 因为象素序列可以根据行程序列来重建，故行程映射变换是可逆的。因它包含灰度鉴别和行程计数，故它是非线性的。第60页/共64页图象编码模型图象编码模型（2 2）差分映射编码）差分映射编码 矩阵形式：第61页/共64页图象编码模型图象编码模型 或 矩阵A是非奇异的，因而这种映射变换是可逆的。差差分分编编码码是一种最简单的线性预测编码。第62页/共64页图象编码模型图象编码模型（3 3）正交变换编码）正交变换编码 各种正交变换都是可逆的线性变换。应用正交变换的图象编码常称为变变换编码换编码。正交变换有傅立叶变换(FFT)、余弦变换(DCT)、沃尔什-哈达玛变换(WHT)、小波变换(DWT)等。第63页/共64页感谢您的欣赏！第64页/共64页