1、自动化工程学院电子工程系教研室王汉萍 主讲6 图像编码基础6.1 数据冗余和压缩6.2 图像保真度6.3 无失真编码定理6.4 哈夫曼编码 6.5 算术编码6.6 位平面编码6.7 无损预测编码6.8 有损预测编码图像压缩方法分类： 信息保存型和信息损失型信息保存型和信息损失型。简 介 网上的许多信息是以图像形式存储的，所以对于存储和通信的需求是无限的。而数据压缩方法比起数据的存储和传输具有更为突出的实用价值和商用意义实用价值和商用意义。 图像压缩所解决的问题是尽量减少表示数字图像时尽量减少表示数字图像时需要的数据量需要的数据量，减少数据量的基本原理是除去其中多余除去其中多余的数据的数据。以数
2、学观点来看，实际上就是将二维像素阵列将二维像素阵列变换为一个在统计上无关联的数据集合变换为一个在统计上无关联的数据集合。6.1 数据冗余和压缩解码图像原始图像编码编码结果存储传输解码图像编解码过程图像编码：为表达图像数据需要使用一系列的符号(如字母、数字等)，用这些符号根据一定的规则来表达图像就是对图像编码。码本：编码所用符号的集合称为码本。 如二元码本0、1码字：对每个信息或事件所赋的符号序列称为码字。码字长度：每个码字里的符号个数称为码字长度。自然码：m bit的二元码中的一个。 不论灰度级的大小，赋予相同的码字长度。基本概念RDCR1121/nnCR），）和（，分别在开区间（和10DRR
3、C其中CR为压缩率：表达无用信息的数据表达无用信息的数据就叫数据冗余。数据冗余可用数学定量的描述。设n1和n2分别代表用来表达相同信息的两个数据集合中的信息载体单位的个数，那么第一个数据集合（相对于第二个数据集合）的相对数据冗余RD定义为：数据冗余与信息 在数字图像压缩中，可以确定三种基本的数据冗余：编码冗余、像素间冗余、心理视觉冗余。当这三种冗余的一种或多种得到了减少或消除时，就实现了数据压缩。1. 编码冗余1,2, 1 ,0)(Lknnrpkkr说明：L是灰度级数，nk是第k个灰度级在图像中出现的次数，n是图像中的像素总数。随即变量rk0，1表示图像的灰度级。 利用图像的灰度级直方图来深入
4、了解编码结构，从而减少表达图像所需的数据量。数据冗余的分类 设用来表示sk的每个数值的比特数是l(rk)，那么为表示每个像素所需的平均比特数(平均码字长度)是：10)()(lkkrkavgrprlL 自然码是每个随机事件用来自m比特二进制技术序列的2m个m比特二进制码的其中一个来表示，是等长码。当一幅图像的灰度级直接用自然二进制编码来表示时，冗余总是存在的。如何消除编码冗余呢？采用变长编码，比如哈夫曼编码，香农编码等。 像素间冗余也称空间冗余或几何冗余，来自图像中对象之间的结构或几何关系。2. 像素间冗余如何消除像素间冗余呢？ 利用相邻像素间的差异描绘图像，这种变化被认为是映射。比如行程编码。
5、 心理视觉冗余产生是由于眼睛并不是对所有视觉信息有相同的敏感度。有些信息在通常的视感觉过程中与另外一些信息相比来说不那么重要，这些信息可以认为有心理视觉冗余，去除这些信息不会明显的降低所感受到的图像质量。3. 心理视觉冗余如何消除心理视觉冗余呢？ 通过“改进灰度级量化”过程消除心理视觉冗余，量化的结果导致数据的有损压缩。6.2 图像保真度和质量 在信息损失型压缩编码中，由于损失了细节或者不太重要的内容，导致解码图像和原始图像有误差。对信息损失的测度以描述解码图像相对于原始图像的偏离程度，这些测度一般称为保真度准则，或者说需要测试解码图像的质量的测度。 常用的有两大类：客观保真度准则和主观保真度
6、准则。信息保存型：解码图像和原始图像完全一样。信息损失型：解码图像和原始图像不一样，有偏差。3) 均方根信噪比2/110102),(),(1MxNyrmsyxfyxfMNe1010210102),(),(),(MxNyMxNymsyxfyxfyxfSNR1010210102),(),(),(MxNyMxNyrmsyxfyxfyxfSNR1. 客观保真度准则1) 均方根误差2) 均方信噪比4) 峰值信噪比10102max2),(),(1lg10MxNyyxfyxfMNfPSNR其中， 1, 2 , 1 , 0, 1, 2 , 1 , 0),(maxmaxNyMxyxff 常用方法是对一组精心挑选
7、的观察者展示以傅典型的图像并将它们对该图的评价综合平均起来以得到一个统计的质量评价结果。2. 主观保真度准则表8.3 电视图像的等级量表值 等级 描 述 1 极好极好 具有极高品质的图像，和希望的一样好 2 好好 高品质的图像，感觉良好，其中的干扰可以接受 3 过得去过得去 具有可接受的品质。其中的干扰不是不可以接受 4 勉强可以勉强可以 品质不良的图像；希望能得到改进。干扰在某种程度上难于接受 5 差差 非常不好的图像，但还可以看。有明显不能接受的干扰 6 不可用不可用 差到无法观看的图像6.3 无失真编码定理信息论简介信息论是研究编解码的基础。I. 什么是图像压缩的极限？(熵）II.什么是
8、图像传输率的最终极限？（信道容量）有关图像压缩的基本问题：基本概念：熵)(log)()(2xPxPXH自信息)(log)(EPEI零记忆信源完全用（B,u）描述，信源符号统计独立的信源就成为零记忆信源。）称为信源符号（JbbbbBjJ,1,2,j,21TJbPbPbPu )()()(21香农第一定理（无失真编码定理）：无损信源编码编码的平均码字长度可以接近信源的熵，但不能小于信源的熵。这也是无损信源压缩的极限香农第二定理（有失真编码定理）：在给定保真度准则的前提下，如何来确定最小的编码所用数据率（每像素的平均比特数）？如果允许最大可能的失真，就可获得最小的信息率。如果不允许失真，什么是图像传输
9、率的最终极限？)(limuHnLavgn通俗的说，允许的失真度越大，图像的压缩率就越高。根据该信源的消息集合，在字母集 中选取ai进行编码。一般情况下取二元字母集 根据信息论中熵的定义，可算出该信源的熵为： 设某个无记忆信源共有M个消息，记作 。其中消息 ，各自出现的概率分别为： 可把这个信源用下式表示：6.4 哈夫曼编码,21Muuu), 2 , 1(Miui,21MPPPMMPPPuuuX,2121,21naaaA1 , 0AMiiiPPXH12log)( 变长编码是基于统计模型的，也有人称熵编码，可以减少图像的编码冗余。基本概念熵：熵：冗余度：冗余度：MiiiNPN1nNXH2log)(
10、nNXHnNRd22log)(log1统计编码的目的就是要设法减小 ，使得 。显然 有一个最低限，当 时， 的最低限 。可以根据这一准则来衡量编码方法的优劣。N1N1NnXH2log/ )(平均码长：平均码长：设对应于每个消息的码字由Ni个符号组成，也就是说每个消息对应的码字长度各为Ni。编码效率：编码效率：设原始信源有M个消息，即可用下述步骤编出哈夫曼码：第一步，把信源X中出现的消息按出现的概率从大到小的顺序排列即 。第二步，把最后出现概率最小的消息合并成一个消息，从而使信源的消息数减少一个，同时把信源中的消息的概率从大到小排列一次。得MMPPPuuuX,2121MPPP21, , , ,
11、1211211MMPPPuuuX最常用的变长变码方法有哈夫曼编码和香农-法诺编码。6.4.1 霍夫曼编码第三步，重复上述步骤，直到信源最后为X0为止第四步，将被合并的消息分别赋以1和0或0和1。对最后的X0也即对 对应的赋以1和0或0和1。重复上述步骤就可以构成哈夫曼编码。0201uu 和例 求下述信源的哈夫曼码：3 . 004. 01 . 006. 04 . 01 . 0365421uuuuuuX020102010PPuuX 0.6 0.4输入概率 u2 u6 u1 u4 u3 u50.40.30.10.10.060.04 0.4 0.3 0.2 0.1 0.4 0.3 0.30101010
12、10.40.30.10.10.101哈夫曼编码过程变长码都是基于统计模型的，哈夫曼编码和香农-法诺编码都是所谓的块码，因为它们都将每个信源符号映射成一组固定次序的码符号，这样在编码时可以一次编一个符号。 从解码的角度：人们常关注两个特性：即时性和唯一性。（1）即时性（也称非续长性） 任意一个码字都不是其它码字的续长。（2）唯一性（单义性） 任意一个有限长的码字序列只能被分割成一个一个的码字，而任何其他分割方法都会产生一些不属于码字集合中的码字。符合这个条件的代码叫单义代码。 非续长代码一定是单义的，单义代码却不一定是非续长代码。6.4.2 变长码的特性 根据哈夫曼方法的原理，当需要对大量符号进
13、行编码时，构造最优哈夫曼码的计算量会很大，此时常采用一些亚最优的变长编码方法。下面仅介绍两种基于哈夫曼方法的截断哈夫曼码和平移哈夫曼码。1.截断哈夫曼码 截断哈夫曼码是对哈夫曼码的一种改型。只对最可能出现的M个符号进行哈夫曼编码，而对其它的码都用在一个合适的定长码前加一个前缀码来表示。2. 平移哈夫曼码 平移码由以下几个步骤产生：重新排列信源符号使得它们的概率单减；将符号总数分成相同大小的符号块；对所有的块中的各个元素采用同样方法编码；对每个 块加上专门的平移符号以区别它们。6.4.3 亚最优变长码香农-法诺编码 香农-法诺编码的编码准则要符合非续长条件，在码字中1和0时独立的，而且是或者差不
14、多是等概率的。主要步骤为：第一步，设信源X有非递增的概率分布；MMPPPPuuuuX,321321其中， 把X分成两个集合，得：MPPP21kkPPPPuuuuX,3213211MkkkMkkkPPPPuuuuX,3213212并且保证kiMkiiiPP11第二步，给两个子集中的消息赋值，X1赋0，X2赋1。第三步，重复第一个步骤，将两个子集X1，X2再细分成两个子集，并且也同样使两个子集里的消息的概率之和相等或近似相等，然后重复第二步骤赋值。直到每个子集里只包含一个消息为止。例 求下述信源的香农-费诺编码3 . 004. 01 . 006. 04 . 01 . 0365421uuuuuuX码
15、字 1 2 3 4 5符号 概率u2 0.4u6 0.3u1 0.1u4 0.1u3 0.06u5 0.04010000111101011011101111011111练 习1. 求下述信源的哈夫曼编码，以及熵、平均码长、效率和冗余度。05. 010. 015. 020. 025. 025. 0654321uuuuuuX2. 求下述信源的香农-法诺编码，以及熵、平均码长、效率和冗余度。0625. 00625. 0125. 0125. 025. 025. 0654321uuuuuuX6.5 算术编码 算术编码仅用到了算术运算和移位运算，这就是其名称的由来，它的解码过程可以借助于编码过程来进行。
16、a1 a2 a3 a4 0.2 0.4 0.8 10,0.2）0.2,0.4）0.4,0.8)0.8,1)0,0.04)0.04,0.08)0.08,0.16)0.16,0.2)0.04,0.048)0.048,0.056)0.056,0.072)0.072,0.08)0.056,0.0592)0.0592,0.0624)0.0624,0.0688)0.0688,0.072)0.0624,0.06368)0.06368,0.06624)0.06624,0.06752)0.06752,0.0688)算术编码的过程：6.6 位平面编码二值分解001122112222aaaammmm6.6.1 位平
17、面分解 位平面编码是一种基于将多灰度值图像分解成一系列二值图，然后对每一幅二值图再用二元压缩方法进行压缩的技术。这种技术能够消除编码冗余和像素间冗余。 把一幅灰度图分成一系列二值图集合的一种简单方法是把上述多项式的m个系数分别m个1比特的位平面中去，将每个像素的第I个比特集合在一起就得到图像的第个位平面。这种分解方法的固有缺点是：像素灰度值的微小变化可能对位平面的复杂度产生较明显的影响。灰度码分解1201miamiaagiiii用灰度码表达的位平面复杂度较低，但具有视觉意义信息的位面图数量更多。 压缩位平面图的一种简单而有效的方法是用专门的码字表达全是1或0的区域。常数块编码将图像分成全白、全
18、黑或混合的mn尺寸的块。出现频率最高的赋予1比特码字0，其他两类分别赋予2比特码字10和11。由于原来需要mn比特表示的常数块现在只用1比特或2比特的码字表示，就达到了压缩的目的。当然这里赋给混合块的码只是作为前缀，后面还需跟上该块的用mn比特表示的模式。6.6.2 位平面的编码常数块编码（constant area coding,CAC）1-D游程编码（run length coding,RLC） 基本思路是对一组从左向右扫描得到的连续的0或1游程用他们的长度来编码。这里需要确定游程值的协定，常用的方法是：指出每行第一个游程的值或者设定每行都由白色游程开始。设每行均由白色（0）游程开始，对第
19、2位平面（最高位）：4 2 2，3 3 2，3 4 1，4 2 21-D游程编码（run length coding,RLC）第 2 位平面 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 2-D游程编码的一种常用的方法称为相对地址编码（relative address coding,RAC），它的基本原理是跟踪各个黑色和白色游程的起始和终结过渡点。2-D游程编码对RAC距离进行变长编码示例6.7 无损预测编码 预测编码（predictive coding）的基本思想是通过仅对每个像素中提取的新信息编码来消除像素间
20、的冗余。这里1个像素的新信息定义为该像素的当前或现实值与它预测值的差。预测编码分为无损预测和有损预测两类。 借助预测器可将原来对原始图像序列的编码转换成对预测误差的编码。当预测较准确时，预测误差的动态范围会小于原始图像序列的动态范围，所以对于预测误差的编码所需的比特数会大大减少，这样预测编码可获得数据压缩的效果。nnnffennnfef1. 无损预测编码系统2.线性预测器1miininfaroundfM称为线性预测器的阶，round是舍入函数，ai是预测系数。N可认为指示了图像的空间坐标。 ),(),(1miinyixfaroundyxf最简单的线性预测器前值预测器：), 1(yxafroun
21、dfn6.8 有损预测编码1. 有损预测编码系统2. DM编码（Delta modulation）1nnf af其它对ccenn0eA是预测系数，c是1个正的常数3. 最优预测器（optimal predictor）) 1, 1(), 1() 1, 1() 1,(),(4321yxfayxfayxfayxfayxf其中，11miia6.9 变换编码1. 基于DCT的变换编码2. 基于DWT的变换编码输入图像小波变换符号编码符号解码压缩图像解压图像量 化小波反变换压缩图像1. 搞清下面概念：变长编码（Huffman编码、香农编码）、自适应编码、二值图像的游程编码、预测编码、变换编码；2. 参考附录中的图像压缩标准，进一步理解上述编码方法；3. 阅读一篇关于编码的论文，综合理解所有的概念：编码方法、图像的保真读准则、创新点等等。
