《教学课件第5章 图像编码（第5 - 2讲）（研究生学位课）ppt（全）.ppt》由会员分享，可在线阅读，更多相关《教学课件第5章 图像编码（第5 - 2讲）（研究生学位课）ppt（全）.ppt（110页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、教学课件第5章图像编码（第5-2讲）（研究生学位课）数字图像处理学数字图像处理学第第5章章 图像编码图像编码（第二讲）（第二讲）阮秋琦教授阮秋琦教授5.4 5.4 统计编码统计编码高效编码的主要方法是尽可能去除信源中的冗余成份，从而以最少的数码率传递最大的信息量。冗余度存在于像素间的相关性及像素值出现概率的不均等性之中。对于有记忆性信源来说首先要去除像素间的相关性，从而达到压缩数码率的目的。对于无记忆性信源来说，像素间没有相关性，可以利用像素灰度值出现概率的不均等性，采用某种编码方法，也可以达到压缩数码率的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫统计编码。5.4.1 5.4
2、.1 编码效率与冗余度编码效率与冗余度(5-21)可把这个信源用下式表示可把这个信源用下式表示 (5-22)式中 H(X)代表熵，Pi 代表第i个消息出现的概率。例如，设一离散信源如下 由式(5-23)可算出该信源的熵 (5-23)设对应于每个消息的码字由 Ni 个符号组成。也就是说每个消息所对应的码字长度各为 Ni。那么，每个消息的平均码长可用下式表示(5-24)(5-25)(5(5-26)26)(5-27)例:一个信源X和一个字母集合A如下 上例中的两种编码方法，其特点是码字长度均相等，这种码叫等长码。显然此例中的两种等长码均没有达到最低限。怎样才能使信源编码达到最低限呢？再看下例的编码方
3、法选 A=0,1,n=2，作为编码字符集。在这种编码中，不用等长码，而是采用下面的原则来编码，即 Pi 大的消息编短码，Pi 小的消息编长码。例：可计算出平均码长其效率冗余度 由此可见，这种编码法的码字平均长度达到了最低限。这说明用变长编码法可达到较高的效率。采用这种编码方法，信源中的消息与码字是一一对应的，因而译码时也是准确无误的。在编、译码过程中并不损失任何信息。它是一种信息保持编码法。5.5.4.2 4.2 常用的统计编码法常用的统计编码法 单义性代码是指任意一个有限长的码字序列只能被分割成一个一个的码字，而任何其他分割方法都会产生一些不属于码字集合中的码字。符合这个条件的代码就叫单义代
4、码。非续长代码是指任意一个码字都不是其他码字的续长。换句话说，就是码字集合中的任意一个码字都不是由其中一个码字在后面添上一些码元构成的。很容易看出非续长代码一定是单义的，但是，单义代码却不一定是非续长的。例如，在表5-5中，列出四种代码，码：显然码缺乏单义可译性。码：也缺乏单义可译性，又是可续长的。码：既具备单义可译性又是非续长的码，它是 可用的。码也具有单义可译性，但是却缺乏非续长性。最为常用的变长编码方法是霍夫曼（Huffman）码和仙农费诺（Shannon-Fano）码。下面详细地讨论一下这两种码的构成方法 1.1.霍夫曼码霍夫曼码霍夫曼码变长编码法能得到一组最优的变长码。设原始信源有个
5、消息，即 (5-28)可用下述步骤编出霍夫曼码：第一步，把信源中的消息按出现的概率从大到小的顺序排列，即 第二步，把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少一个，并同时再次将信源中的消息的概率从大到小排列一次，得 (5-29)(5-30)通过上述步骤就可以构成最优变长码（霍夫曼码）。下面举例说明具体构成方法。例：求下述信源的霍夫曼码由上述步骤，合并最小的两项做一个新的信源重排得重排得重排得0.450.300.55码字 消息 概率 0 11 01 10 0 00 0 1 00 0 1 10.250.250.200.150.100.050 1010.250.250.200
6、10.300.250101图5-18 信源X的霍夫曼编码图0.150.45 如对合并的消息赋以1，0值，则会得到如表5-7所示的另外一组码。表5-6信源X的霍夫曼编码表 表5-7 信源X的另一组霍夫曼编码表 表5-6信源X的霍夫曼编码表表5-7 信源X的另一组霍夫曼编码表下面计算一下信源的熵，平均码长，效率及冗余度。所以，对于信源 X 的霍夫曼码的编码效率为98，尚有2的冗余度。2 2.香农费诺码香农费诺码另外一种常用的变长编码是仙农费诺码。这种码有时也可以得到最优编码性能。它的编码准则要符合非续长条件，在码字中1和0是独立的，而且是（或差不多是）等概率的。这样的准则一方面可保证无需用间隔来区
7、分码字，同时又保证每传输位码就有bit的信息量。仙农费诺码的编码程序可由下述几个步骤来完成：第一步：设信源有非递增的概率分布 (5-31)(5-32)成立或差不多成立。并且保证(5-34)(5-33)第二步：给两个子集中的消息赋值，X1 赋1，X2 赋 0，或给 X1 赋 0，X2 赋 1。第三步：重复第一步骤，将两个子集 X1，X2 再细分为2个子集，并且也同样使两个小子集里消息的概率之和相等或近似相等。然后，重复第二步骤赋值。以这样的步骤重复下去，直到每个子集内只包含一个消息为止。对每个消息所赋过的值依次排列出来就可以构成仙农费诺码 下面举例说明仙农费诺码的具体构成方法例：设有信源其编码流
8、程图如图5-19所示。编码表如表5-8所示。如果对各子集赋以另外一种值，即1，0，那么，同样会得到另一种编码结果，其编码表如表5-9所示。图5-19 仙农-费诺码编码流程图表5-8 香农-费诺码编码表 表5-9 另一种仙农-费诺码编码表 下面计算一下仙农费诺码的平均码长，效率及冗余度。信源的熵可计算于下：平均码长 (5-35)且 (5(5-36)36)由此例可见，由于信源不满足式(5-35)和(5-36)的条件，编码效率不能达到100。然而从结果上看，它仍然是一种相当好的编码。冗余度 效率 图5-20 编码流程图特点：特点：1）、Huffman码和Shannon Fano码不是唯一的；2）、H
9、uffman码和Shannon Fano码缺乏构造性，即，不能用数学方法建立一一对应关系，只能通过查表的方法构成对应关系。如果消息数目很大，所需的存储器就大，设备就复杂。3）、非等长码在传输、译码、存储都不方便。一般在实用中用查表来实现。编码表可参见网站附件中的ITU-T建议的彩色图像编码标准中的编码表5 5.4.3.4.3 算术编码（算术编码（Arithmetic codingArithmetic coding）算术编码的概念最早由J.Rissaner在1976年以后入先出的编码形式引入，1979年他和G.G.Langdom 一起将其系统化。由于省去了乘法，因此，处理比较简单。1981年又将
10、其推广用于二值图像编码。对于二元平稳马尔可夫信源，效率可高于95%。在国际编码标准中，JPEG，JBIG都有算术编码的应用。与Huffman码不同，算术编码是一种非分组编码方法，或叫非块码。正因为算术编码不是分组编码。因此，其译码也是一个字符一个字符的译码。1.算术编码的基本原理算术编码的基本原理概率区间表示概率大小概率区间表示概率大小边界值累积概率边界值累积概率图 5-22 算术编码图示1.00.1110.0110.00100.0010.1110.11010.10010.01110.0110.00010.11010.110010.101010.100110.10010.0000010.101
11、010.10100110.10011110.10011010.100110.0000001a4a3a2a1a4a3a2a1a4a3a2a1a4a3a2a1指向下端点因此，得到码字0.011。后续的符号编码将在前面编码指向的字区间内进行。后续符号的编码将在前面符号编码指向的子区间进行。指向下端点指向下端点指向下端点 上述递归过程，可将算术编码的基本原理 总结如下：（1）初始状态 编码原点（指针所指之处）C0=0 区间宽度为 A0=1.0（2）新编码点 C1=原编码点原区间宽度Pi 新区间宽度 A1=原区间宽度A0pi 其中 pi 为所编符号 ai 对应的概率，Pi 为 ai 的累积概率。因此，a
12、3 a3 a2 a4 的编码过程如下：第一个符号：a3原编码点原区间宽度(a3)符号累积概率原区间宽度符号概率(a3)区间宽度编码指向下端点第二个符号：a3a3 的累积概率原编码点原编码点区间宽度区间宽度区间宽度新原区间宽度新原区间宽度符号概率符号概率(a3)编码指向下端点第三个符号：a2a2 的累积概率编码原编码点原编码点区间宽度区间宽度区间宽度新原区间宽度新原区间宽度符号概率符号概率(a2)指向下端点第四个符号：a4以上是编码过程。编码编码原编码点原编码点区间宽度区间宽度a4 的累积概率区间宽度区间宽度新原区间宽度新原区间宽度(a4)符号概率符号概率指向下端点解码过程是：（收到的码字串（收
13、到的码字串)(已解符号子区间的下端点）已解符号子区间的下端点）（字符概率（字符概率)累积概率累积概率2.解解码码原理：原理：在解码过程中，当收到码字串0.1010011时，由于这个码字串指向子区间0.011,0.111，因此，解出的第一个符号应为 a3，然后用相反的步骤，从码字串中减去已解符号子区间下端点的数值（累积概率），并将差值除以该子区间的宽度（概率值）则得到码字串，即：由下图所示，该字串仍然落在0.011,0.111区间内，因此，解出的第二个字符为 a3收到码字串收到码字串a3累积概率累积概率a3字符概率字符概率第三个字符：a3 的累积概率 a3的子区间宽度(概率)字符落在字符落在0.001,0.0110.001,0.011之间之间因此是因此是 a2收到码字串收到码字串第四个字符a2 的区间下端点数值a2的概率收到码字串收到码字串字符落在0.111,1.0之间因此是 a4以上就是解码过程。在算术编码中，值得注意的问题是进位问题。在Huffman码中没有这类问题。如上述的例子，编完第3个符号之后得到的码字是0.10011，对第四个符号编码时前3位0.100就变成0.101。(a2 0.10011,a4 0.1010011)这就是相加过程中的进位引起的。