图像编码与压缩技术.ppt

《图像编码与压缩技术.ppt》由会员分享，可在线阅读，更多相关《图像编码与压缩技术.ppt（164页珍藏版）》请在三一文库上搜索。

1、第6章 图像编码与压缩技术,教学目的,了解图象编码的目的和常用方法； 理解图象编码的基本概念和理论； 掌握熵编码方法、预测编码、变换编码的基本方法； 理解图象编码的国际标准。,6.1 概述,一.数据压缩的目的 数据压缩就是要减少描述图像的数据量，从而达到这样几个目的： 节省图像存储器的容量 减少传输时占用的通信话路 缩短图像处理时间，提高实时处理的速度。,典型图像的数据量,二.数据压缩的可能性,1. 图像作为信源有很大的冗余度，通过编码的方法减少或去掉这些冗余信息后可以有效压缩图像，同时又不会损害图像的有效信息。数字图像的冗余主要表现为以下几种形式： 空间冗余：规则物体或规则背景的物体表面特性

2、具有的相关性，这种相关性使图像结构趋于有序和平滑。内部相邻像素之间存在较强的相关性。 频间相关性：多频段图像中各频段图像对应像素之间灰度相关性很强。 时间冗余：视频图像序列中的不同帧之间的相关性很强，很多局部甚至完全相同，或变化极其微妙。由此造成的冗余。 信息熵冗余：也称编码冗余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余 结构冗余：是指图像中存在很强的纹理结构或自相似性。 知识冗余：是指在有些图像中还包含与某些先验知识有关的信息。 视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 其他冗余。,数据压缩主要是通过编码来实现的。,三.图像编

3、码的方法,1.根据编码过程中是否存在信息损耗可将图像编码分为有损压缩和无损压缩。 无损压缩无信息损失，解压缩时能够从压缩数据精确地恢复原始图像； 有损压缩不能精确重建原始图像，存在一定程度的失真。,2.根据编码原理可以将图像编码分为熵编码、预测编码、变换编码和混合编码等。 （1）熵编码。熵编码是纯粹基于信号统计特性的编码技术，是一种无损编码。熵编码的基本原理是给出现概率较大的符号赋予一个短码字，而给出现概率较小的符号赋予一个长码字，从而使得最终的平均码长很小。常见的熵编码方法有行程编码、哈夫曼编码和算术编码。 （2）预测编码。预测编码是基于图像数据的空间或时间冗余特性，用相邻的已知像素（或像素

4、块）来预测当前像素（或像素块）的取值，然后再对预测误差进行量化和编码。预测编码可分为帧内预测和帧间预测，常用的预测编码有差分脉码调制（DPCM）和运动补偿法。,（3）变换编码。变换编码通常是将空间域上的图像经过正交变换映射到另一变换域上，使变换后的系数之间的相关性降低。图像变换本身并不能压缩数据，但变换后图像的大部分能量只集中到少数几个变换系数上，采用适当的量化和熵编码就可以有效地压缩图像。 （4）混合编码。混合编码是指综合了熵编码、变换编码或预测编码的编码方法，如JPEG标准和MPEG标准，JBIG，H261。,3.根据对压缩编码后的图像进行重建的准确程度，可将常用的图像编码方法分为三类：

5、（1）信息保持编码：也称无失真编码，它要求在编解码过程中保证图像信息不丢失，从而可以完整地重建图像。信息保持编码的压缩比较低，一般不超过3：1，主要应用在图像的数字存储方面，常用于医学图像编码中。 常见的有：哈夫曼编码，算术编码，行程编码，FANO编码等。,（2）保真度编码：主要利用人眼的视觉特性，在允许的失真（Lossy）条件下或一定的保真度准则下，最大限度地压缩图像。保真度编码可以实现较大的压缩比，主要用于数字电视技术、静止图像通信、娱乐等方面。对于这些图像，过高的空间分辨率和过多的灰度层次，不仅增加了数据量，而且人眼也接收不到。因此在编码过程中，可以丢掉一些人眼不敏感的信息，在保证一定的

6、视觉效果条件下提高压缩比。 常见的有： 预测编码：DPCM,运动补偿 频率域方法：正交变换编码(如DCT），子带编码 模型方法：分形编码，模型基编码 基于重要性：滤波，子采样，比特分配，向量量化,（3）特征提取：在图像识别、分析和分类等技术中，往往并不需要全部图像信息，而只要对感兴趣的部分特征信息进行编码即可压缩数据。例如，对遥感图像进行农作物分类时，就只需对用于区别农作物与非农作物，以及农作物类别之间的特征进行编码，而可以忽略道路、河流、建筑物等其他背景信息。,四.图像编码新技术,图像编码已经发展了几十年，人们不断提出新的压缩方法。如，利用人工神经网络（Artificial Neural N

7、etwork，ANN）的压缩编码、分形编码（Fractal Coding）、小波编码（Wavelet Coding）、基于对象的压缩编码（Object Based Coding）和基于模型的压缩编码（Model Based Coding）等等。,1)分形编码 分形编码是在分形几何理论的基础上发展起来的一种编码方法。分形编码最大限度地利用了图像在空间域上的自相似性（即局部与整体之间存在某种相似性），通过消除图像的几何冗余来压缩数据。 M.Barnsley将迭代函数系统用于描述图像的自相似性，并将其用于图像编码，对某些特定图像获得了10 000: 1的压缩比。分形编码过程十分复杂，而解码过程却很简

8、单，故通常用于对图像编码一次，而需译码多次的信息传播应用中。,图 分形图像,给出一个稍微复杂的树模型：,设图形 为一条单位长直线段，在第一个三等分点上各向两边 角的方向延伸出两条 长的线段，在中点处向左以 延伸 出 长的线段，再在第二个三等分点处向右方以 延伸出 的 线段。得到图形 。将 的每5个分支做同样的变换，得到 。,Koch曲线,设 为单位直线段，将其三等分后，中间一段用与其组成等边三角形的另两边代替，得到 。对 的每条线段重复以上做法得到 。当n趋向于无穷时，所得的曲线就是Koch曲线。,用计算机生成的分形图象,最典型的例子是一片蕨子所对应的迭代函数系统：,从上例可以看出，要产生一个

9、复杂的图形需要的数据并不多。蕨子叶对应的迭代函数系统只有24个系数。如果以8比特代表一个系数，那么192比特就可以代表一片蕨子叶了，可见其压缩比是很大的。曾有人扬言，它实现过10000：1的压缩，分形图像压缩的潜力是无疑的。,因此从分形的角度，许多视觉上感觉非常复杂的图像其信息量并不大，可以用算法和程序集来表示，再借助计算机可以显示其结合状态，这就是可以用分形的方法进行图像压缩的原因。 分形最显著的特点是自相似性，即无论几何尺度怎样变化，景物的任何一小部分的形状都与较大部分的形状极其相似。这种尺度不变性在自然界中广泛存在。例如，晶状的雪花、厥类植物的叶子等，这些图形都是自相似的。可以说分形图之

10、美就在于它的自相似性，而从图像压缩的角度，正是要恰当、最大限度地利用这种自相似性。,2)小波编码 1989年，S.G.Mallat首次将小波变换用于图像编码。经过小波变换后的图像，具有良好的空间方向选择性，而且是多分辨率的，能够保持原图像在各种分辨率下的精细结构，与人的视觉特性十分吻合。,图 子图排序示意图,(,c,),Woman二级小波分解图,3)模型编码 模型编码是近几年发展起来的一种很有前途的低比特率编码方法，其基本出发点是在编、解码两端分别建立起相同的模型，编码时利用先验模型抽取图像中的主要信息并用模型参数的形式表示，解码时则利用所接收的模型参数重建图像.,五.数据压缩系统组成框图,图

11、像压缩编码系统的组成框图：,三个环节： 变换器：将原始图像表示在另一个量化和编码数据较少的域中，变换器应高度去相关，重建均方差最小，可逆的和方法简便的。有线性预测，正交变换，游程变换等； 量化器：按一定规则使量化器输出幅值的大小为有限个数。 编码器：为量化器输出端的每个符号分配一个码字或二进制比特流。,一般说来，评价图像压缩算法的优劣主要有以下4个方面。 1)算法的编码效率 算法的编码效率通常有几种表现形式： 图像熵（H）， 平均码字长度（R）， 图像的压缩比（rate，r）， 编码效率（）， 这些表现形式很容易相互转换。,6.2图像压缩编码评价,设一幅灰度级为N的图像，图像中第k级灰度出现的

12、概率为 ，每个像素用d比特表示，定义数字图像的熵H由下式定义：,（图像熵H表示各灰度级比特数的统计平均值。）,对于一种图像编码方法，设第k级灰度的码字长度为 ，则该图像的平均码字长度R为 :,定义编码效率为 :,压缩比r为: ，,(d表示压缩前图像每象素的平均比特数),由于同一压缩算法对不同图像的编码效率会有所不同，因此常需定义一些“标准图像”，如国际上流行的三幅图像Lena、Barbara和Mandrill。一般通过测量不同压缩算法对同一组“标准图像”的编码性能来评价各图像压缩算法的编码效率.,2）编码图像的质量 压缩前后图像质量评价可分为客观质量评价和主观质量评价。最常用的客观质量评价指标

13、是均方误差（MSE）和峰值信噪比（PSNR），其定义如下：,主观质量评价是指由一批观察者对编码图像进行观察并打分，然后综合所有人的评判结果，给出图像的质量评价。客观质量评价能够快速有效地评价编码图像的质量，但符合客观质量评价指标的图像不一定具有较好的主观质量。主观质量评价能够与人的视觉效果相匹配，但其评判过程缓慢费时。,3)算法的适用范围 特定的图像编码算法具有其相应的适用范围，并不对所有图像都有效。一般说来，大多数基于图像信息统计特性的压缩算法具有较广的适用范围，而一些特定的编码算法的适用范围较窄，如分形编码主要用于自相似性高的图像.,4)算法的复杂度 算法的复杂度即指完成图像压缩和解压缩所

14、需的运算量和硬件实现该算法的难易程度。 优秀的压缩算法要求有较高的压缩比，压缩和解压缩快，算法简单，易于硬件实现，还要求解压缩后的图像质量较好。选用编码方法时一定要考虑图像信源本身的统计特性、多媒体系统(硬件和软件产品)的适应能力、应用环境以及技术标准。,图像编码主、客观评价的内在关系,6.3 统计编码,统计编码 根据信源的概率分布特性，分配具有惟一可译性的可变长码字，降低平均码字长度，以提高信息的传输速度，节省存储空间。 基本原理 在信号概率分布情况已知的基础上，概率大的信号对应的码字短，概率小的信号对应的码字长，这样就降低了平均码字长度。,变长最佳编码定理：如果码字长度严格按照对应符号出现

15、的概率大小逆序排列，则其平均码字长度为最小。 变长最佳编码定理是哈夫曼编码的理论基础。,根据信源编码理论，当平均码长R大于或等于图像熵H时，总可以设计一种无失真的编码方法。 当平均码长R远远大于图像熵H时，表明该编码方法效率低。 当平均码长R等于或按照大于方向很接近图像熵H时，则为最佳编码方法，并不会引起图像失真。,熵是无失真图像编码的下界。,结论：信源符号的码字长度是由信源符号自身出现的概率决定的。,等长编码与可变长编码,例：假设一文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7,若采用等长编码，则每种符号编码至少需要3bit，则编码成 S0=000,s1=001,s2=0

16、10,s3=011,s4=100,s5=101,s6=110,s7=1 则符号序列s0 s1 s7 s0 s1 s6 s2 s2 s3 s4 s5 s0 s0 s1编码为 000 001 111 000 001 110 010 010 011 100 101 000 000 001（共42bit) 若采用编码方案为 S0=01,s1=11,s2=101,s3=0000,s4=0010,s5=0001,s6=0011,s7=100 则上述序列编码为 01 11 100 01 11 0011 101 101 0000 0010 0001 01 01 11（共39bit),哈夫曼编码是一种利用信息符

17、号概率分布特性的变字长的编码方法。对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。霍夫曼编码是一种变长编码，也是一种无失真编码。,6.3.1 Huffman编码,1.步骤： (1).先将符号按出现概率由大到小顺序排列（相同概率的符号可以任意颠倒位置）。 (2).将概率最小的两个符号的出现概率相加合并成一个概率，与其它概率形成一个新的集合，称为缩减信源，再将缩减信源中各概率由大到小顺序排列。 (3).如此重复直到最后只剩下两个概率为止。 (4).分配码字，从最后一个缩减信源开始逐步向前分配码字，每一步只对一个分支赋一个二进制码，如对概率大的赋予0，对概率小的赋予1

18、（也可将概率大的赋予1码，概率小的赋予0码）。 (5).最后将二进制从后向前串起来就得到Huffman码。,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,2.举例：,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,2.举例：,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,2.举例：,输入 S

19、1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,2.举例：,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,2.举例：,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步

20、0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,2.举例：,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S1=1,2.举例：,S1=1,码字,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0

21、.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S2=00,2.举例：,S1=1,码字,S2=00,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S3=011,2.举例：,S1=1,码字,S2=00,S3

22、=011,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S4=0100,2.举例：,S1=1,S2=00,S3=011,S4=0100,码字,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3

23、0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S5=01010,2.举例：,S1=1,S2=00,S3=011,S4=0100,S5=01010,码字,输入 S1 S2 S3 S4 S5 S6,输入概率 0.4 0.3 0.1 0.1 0.06 0.04,第一步 0.4 0.3 0.1 0.1 0.1,第二步 0.4 0.3 0.2 0.1,第三步 0.4 0.3 0.3,第四步 0.6 0.4,0 1,0 1,0 1,0 1,0 1,S6=01011,2.举例：,S1=1,S2=00,S3=011,S4=0100,S5=01010,S6=01011,码字,编码效果：

24、 信源熵为：,平均码长,3Huffman编码的性能,优点： 实现Huffman编码的基础是统计源数据集中各信号的概率分布。 Huffman编码在无失真的编码方法中效率优于其他编码方法，是一种最佳变长码，其平均码长接近于熵值。 缺点： 当信源数据成分复杂时，庞大的信源集致使Huffman码表较大，码表生成的计算量增加，编译码速度相应变慢 不等长编码致使硬件译码电路实现困难。上述原因致使Huffman编码的实际应用受到限制。,4准变长编码,实际编码中，常采用准变长编码。(性能稍差，实现方便） 规则： 对概率大的符号用长码，概率小的用短码。同时在 短码字集中留出一个作为长码字的字头，保证码字集的非续

25、长性。常用的有3/6bit双字长编码。 例：P146 适用情况：符号集中，各符号出现概率可以明显分为 高，低两类，效果较好。,6.3.2 Fano编码,Fano(费诺)编码方法也是一种典型的可变字长编码。 步骤: (1)先将符号按出现概率从大到小顺序排列。 (2)将信源符号划分成两大组，使每组的概率和近于相同，并各赋一个二元码0和1。 (3)再将每一大组再分成两组，使两组概率和近似相等，并又分别赋一个二元码。 (4)依次下去直到每小组只剩下一个符号为止。 (5)将符号在各组中的二元码连起来就是编得的Fano码。,例1,已知,例2,从编码后的结果看，Fano码和Huffman码得到的平均码长相同

26、，但是Fano码的缺点是当符号较多时。如何分组可有许多方案，每种方案最后的结果可能不同，所以Fano码本身有一个最佳分组方法的问题，这就使编码方法变得十分繁琐，不如Huffman实用。,作业： 一幅8*8的数字图像为： 对该图像进行Huffman编码，并计算编码效率和压缩比。 对该图像进行Fano编码，并计算编码效率和压缩比。,6.3.3 算术编码,1.算术编码特点 算术编码是信息保持型编码，它不像霍夫曼编码，无需为一个符号设定一个码字。算术编码可分为固定方式编码和自适应方式编码两种。 自适应编码方式，无需先定义概率模型，适合于无法知道信源字符概率分布情况。 当信源出现的概率比较接近时，算术编

27、码效率优于霍夫曼编码效率。 实现算术编码的硬件比霍夫曼编码复杂。,2.编码原理 算术编码的方法是将被编码的信源消息表示成01之间的一个间隔，即小数区间，消息越长，编码表示它的间隔就越小，由于以小数表示间隔，因而表示的间隔越小，所需的二进制位数就越多，码字就越长。反之，间隔越大，所需的二进制位数就越小，码字就越短。信源中连续符号根据某一模式所生成概率的大小来缩小间隔，可能出现的符号要比不太可能出现的符号缩小范围小，只增加了较少的比特。,3.编码实例 设图像信源编码可用a,b,c,d这4个符号来表示，若图像信源字符集为dacba,信源符号集a,b,c,d出现的概率分别为0.4,0.2,0.2,0.

28、2。 算术编码的基本步骤如下： （1）根据已知条件可知，信源各字符在区间0,1内的子区间间隔分别如下： a=0.0,0.4;b=0.4,0.6 c=0.6,0.8;d=0.8,1.0 (2)计算中按如下公式产生新的子区间；,(3)编码： 字符d，初始子区间0.8,1.0); 字符a ，新子区间0.8,0.88); 字符c ，新子区间0.848,0.864); 字符b ，新子区间0.8544,0.8576); 字符a ，新子区间0.8544,0.85568); 字符集dacba 被描述在实数0.8544,0.85568); 用二进制形式表示为0.110110011011, 0.110110100

29、001。编码为11011011；,解码： （1）0.11011011对应十进制为0.8555； （2）0.8555对应字符d; （3）(0.8555-0.8)/0.2=0.2775，对应字符a; （4）(0.2775-0.0)/0.4=0.69375，对应字符c; （5）(0.69375-0.6)/0.2=0.46875，对应字符b; （6）(0.46875-0.4)/0.2=0.34375，对应字符a;,信源符号集a,b,c,d出现的概率分别为0.4,0.2,0.2,0.2。a=0.0,0.4;b=0.4,0.6； c=0.6,0.8;d=0.8,1.0；,算术编码的效能： 编码110110

30、11唯一代表字符序列dacba平均码字长度为： R=8/5=1.6(bit/字符),例2：,给定一组给定的信源符号及其概率(p(a1)=0.5,p(a2)=0.25,p(a3)=0.125,p(a4)=0.125)，试根据该表 对符号序列 进行算术编码。,解：先根据表中字符概率，将区间0，1.0）分为4个子区间，每个子区间的长度分别为0.5,0.25,0.125,0.125.,图 区间概率分布图,区间子分过程,随着输入符号越来越多，子区间分割越来越精细，左端点的数值的有效位数越来越多，若等到整个符号序列输入完毕后，再将最终得到的左端点输出，将遇到两个问题： 一，当符号序列很长时，将不能实时编解

31、码； 二，有效位太长的数实际是无法表示的。,解决方法： 采用两个有限精度的寄存器存放码字的最新部分，当某个地区的左端点（low)和右端点(High)中的最高位相同后，在划分区间时就不会再变了，因此可以把不变的最高位数字移出，并向输出流中写一个数字。,应用： 被最新的图像和视频编码标准所采用：JPEG2000、MPEG4、H.264等。,作业,有三个符号 概率分别为 试对由以上三个符号组成的符号序列” ”进行算术编码。,6.3.4 二值图像编码,二值图像的相邻像素之间也存在很强的相关性。这种相关性突出表现为，图像中的黑点或白点都是以很大的概率连续出现。 1.行程编码(又称游程长度编码) 把若干取

32、同样值的连续像素的数目叫做游程长度（简称游长）。 连续白点的数目叫白长。 连续黑点的数目叫黑长。,图4.2白长与黑长,基本思想： 对每一行交替出现的白长和黑长进行统计，得到每种白长和黑长的发生概率，然后对其进行变长编码。在进行变长编码时，经常采用霍夫曼编码。,白3 黑3 白5 黑4 白5,这里的概率，可分为两种情况，一种是白长和黑长各自的概率分布；需分别建立白长和黑长的霍夫曼码表。 另一种只是游长的概率分布，而不区分白长和黑长。只需建立一个对游长的霍夫曼码表。 在编码时，对每一行的第一个像素要有一个标志码，以区分该行是以白长还是以黑长开始，对后面的游长，只是按照其值，去查相应的霍夫曼码表，并输

33、出对应的码字。,应用：ITU(CCITT)为传真制订的G3标准.,行程长度编码RLE（Run Length Encoding）： 由于一幅图像中有许多灰度相同的图块，用一整数对存储一个像素的灰度值及相同灰度像素的数目（长度）。例如： （G ，L）,长度 灰度值,编码时采用从左到右，从上到下的排列， 每当遇到一串相同数据时就用该数据及 重复次数代替原来的数据串。,000000003333333333 222222222226666666 111111111111111111 111111555555555555 888888888888888888 555555555555553333 2222

34、22222222222222,(0,8) (3,10) (2,11) (6,7) (1,18) (1,6) (5,12) (8,18) (5,14) (3,4) (2,18),18*7的像素颜色仅用11对数据,RLE 编码Run Length Encoding 分析： 对于有大面积色块的图像，压缩效果很好 直观，经济,是一种无损压缩 对于纷杂的图像，压缩效果不好，最坏情况下，会加倍图像,适合行程编码的图,2.方块编码,提出：实际的大多数二值图像都是白色背景占大部分，黑像素只占图像像素总数的很少一部分，因此分解的子块中像素为全白的概率远大于其他情况，如果跳过白色区域，只传黑色像素信息，就可使每个

35、像素的平均比特数下降。跳过白色块（WBS）编码就是基于这一思想提出的。,WBS的编码方法：对于出现概率大的全白子块，分配最短码字，用1比特码字“0”表示；对有N个黑色像素的子块用N+1比特的码字表示，第一个比特为前缀码“1”，其余N个比特采用直接编码，白为0，黑为1。,例：,某段像素值 相应编码 黑白白黑 11001 白白白白 0,将一维WBS的像素段推广为像素块，按照m*n的方块进行编码，称为二维WBS,N=m*n. WBS编码的码字平均长度，则比特率 为：,为N个像素为全白的子块的概率，可由试验确定。,若能根据图像的局部结构或统计特性改变段或子块的大小，进行自适应编码，可进一步改善编码效果

36、。,以上huffman及算术编码等各编码方法都使数据得到了压缩，但为了使编码后占用的字节数进一步减少，往往先对输入图像灰度级进行某种映射，也就是在编码器前加上一个映射变换器。,映射变换的作用就是将输入数据从象素域变换到另一个域中，如果这种变换本身能减少图像的相关性，再对变换后的图像进行某种编码就将进一步压缩图像的数据量，所以从数据压缩来考虑，映射变换必须是高度去相关的。 预测编码和变换编码就是利用此原理来进行数据压缩。,5.3 预测编码,预测编码的基本思想： 在某种模型的指导下，根据过去的样本序列推测当前的信号样本值，然后用实际值与预测值之间的误差值进行编码。 一幅图像中相邻象素的灰度值相差不

37、多或基本相同。因此，相邻灰度级的差值比灰度级在数量上要少，那么在编码时占用的比特数也就要少。 如果模型与实际情况符合得比较好且信号序列的相关性较强，则误差信号的幅度将远远小于样本信号。,5.3.1 预测编码基本原理,图像相邻像素间有较强的相关性，每个像素可用前几个已知的像素值来做预测。 对实际值与预测值之间的误差值进行编码 差分脉冲编码调制 Differential Pulse Code Modulation DPCM,例.设有一幅图像，f(i-1,j-1),f(i-1,j),f(i,j-1),f(i,j)的灰度值分别为253，252，253，255.用 来预测f(i,j)的灰度值，并计算预测

38、误差。 解： 252+253-253=252 预测误差e(x,y)= =255-252=3 显然，对3进行编码比对255直接编码将占用更少的比特数。,DPCM系统的组成,预测值为： 预测误差为： 量化误差为： 如果信号在传输中不产生误差，则有 则输入信号 与接收信号 间的误差为： 接收端与发送端的误差由发送端量化器产生，它会使图像质量有所下降。,5.3.2 最佳线性预测编码,线性预测就是选择ai（i 1，2，N 1）使预测值 讨论适当的ai 使差值en的均方值为最小的编码方法为最佳线性预测编码。预测误差 为 。 预测信号的均方误差（MSE）定义为 Een = E(xn - xn) 2,设计最佳

39、预测的系数ai，采用MMSE,最小均方误差准则(MMSE)。可以令 定义xi和xj的自相关函数 R（i，j）= Exi，xj 写成矩阵形式为Yule-Walker方程组,若R（i）已知，该方程组可以用递推算法来求解ai。,在最佳预测的前提下，可以证明预测误差的均方值为：,通过分析可以得出以下结论：,图像的相关性越强，相关函数 越大， 越小于 ，压缩效果越好。 当原图像互不相关时，即 ，则 ，说明原图像一点也不能压缩，这就说明预测编码是利用图像的相关性进行压缩的。 预测阶数N-1不是越大越好，如果当某一个阶数值已经能使误差信号的自相关函数 ，这时的 就已经达到最小值，即使再增加预测阶数，压缩效果

40、也不会继续提高。 若xi是平稳m阶Markov过程序列，则m阶线性预测器就是在MMSE意义下的最佳预测器。,当前像素与邻近像素的位置关系,当前像素为 ，邻近像素用 表示。,常用预测器方案,前值预测：用x0同一行的最近邻近像素来预测 =x1 一维预测：如上图中的x1、x5。 二维预测：如上图中的 x1、x2、x3、x4、x5、x6、x7等。 三维预测,5.3.3 自适应预测编码,自适应预测 预测参数 根据信号的统计特性来确定，以达到最佳预测。前面的DPCM多采用固定的预测参数，往往预测效果较差。 预测编码的优点 直观快捷、便于实现,适用于具有实时性的硬件结构中，在传输速率较高的场合多采用。 预测

41、编码的缺点 压缩比不够高,5.4 变换编码,5.4.1 变换编码的基本原理 变换编码就是将空间域里描述的图像，先经过正交变换，在变换域里进行描述，一般来说，在频域里描述要比在空间域里简单，而且图像相关性明显下降，再对变换域中的系数进行高效编码，就可以进一步压缩数据，对变换处理后的变换系数解压缩后再施以逆变换，即可恢复空间域图像。,变换编码基本思想：,因为，空域图像经过某种变换(如傅立叶变换、 离散余弦变换、 沃尔什变换等)可在变换域中进行描述。 这样可以将图像能量在空间域的分散分布变为在变换域的相对集中分布， 便于用“Z”(zig-zag)字形扫描、 自适应量化、 变长编码等进一步处理， 完成

42、对图像信息的有效压缩。 变换本身不能直接减少数码率，只有通过适当的编码，才能利用变换来压缩图像数据。,先从一个实例来看一个域的数据变换到另一个域后其分布是如何改变的。 以相邻两个像素组成的子图像为例， 每个像素3比特编码， 取07共8个灰度级， 两个像素有64种可能的灰度组合， 由下图5.10（a）中的64个坐标点表示。 一般图像相邻像素之间存在着很强的相关性（下图）， 绝大多数的子图像中相邻两像素灰度级相等或很接近， 也就是说在x1=x2直线附近出现的概率大， 如下图5.10（a）中的阴影区所示。,为什么用正交变换可以减小图像的相关性呢？,图像间相关性统计图,图5.10 变换编码的物理意义

43、(a) 子图像在阴影区的概率较大； (b) 旋转变换后,在原坐标系中各子图像的两个像素具有相同的方差 ， 但变换后的坐标系中， 。,这时如果只保留方差较大的分量 就可以获得很大的数据压缩，而这个坐标旋转就是一个酉变换。,满足,所以是正交矩阵，这个旋转就是一个酉变换，正交变换使得原来图像的相关性得到减小。,信息论的研究表明， 变换前后图像的信息量并无损失， 可以通过反变换得到原来的图像值。 统计分析表明， 正交变换后， 数据的分布向新坐标系中的少数坐标集中， 集中于少数的直流或低频分量的坐标点。 正交变换并不压缩数据量， 但它去除了大部分相关性， 数据分布相对集中， 可以依据人的视觉特性， 对变

44、换系数进行量化， 允许引入一定量的误差， 只要它们在重建图像中造成的图像失真不明显， 或者能达到所要求的观赏质量就行。 量化可以增加许多不用编码的0系数， 然后再对量化后的系数施行变长编码。,若将整个图像作为一个二维矩阵， 变换编码的计算量太大。 所以将一幅图像分成一个个小图像块， 通常是88或1616小方块， 每个图像块可以看成为一个二维数据矩阵， 变换编码以这些小图像块为单位进行， 变换编码把统计上密切相关的像素构成的矩阵通过线性正交变换， 变成统计上较为相互独立， 甚至完全独立的变换系数所构成的矩阵。,具体的正交变换编码方法: a) 区域抽样法 选择能量集中的区域进行编码，而将其它区域中

45、的系数置零，既不编码，也不传输（相当于对变换系数作二维低通过滤）。 b) 区域编码法 把变换系数矩阵分成若干子区域，在每个区域内，按系数的能量分配比特数。例如，对幅度大的系数赋8、7 或6 比特码；对幅度小的系数按顺序减少比特数，甚至不予编码。 c) 非线性量化 对每个系数使用不同的量化器，根据方差和人眼对空间频率的敏感程度，给系数分配不同的比特数。 采用以上方法进行编码，必须保证恢复图像的质量，从主观视觉心理上，应观察不出明显失真。,5.4.2 实际采用的变换编码系统 典型的变换编码系统如图5-11 所示。 图5-11 正交变换编码模型,编码部分包括4 个操作模块： 分块（生成子图像）：为了

46、减少变换计算的复杂度，需先将一幅 图像分解成尺寸为 的子图像。 正变换：目的是解除每个子图像内部像素之间的相关性，或充分集中能量，将尽可能多的信息集中到尽可能少的变换系数上。变换结果，得到 个 的子图像变换数组。 量化：有选择性地消除或较粗糙的量化能量小的系数，以达到减小心理视觉冗余的目的。这些系数携带的信息很少，对解码恢复的图像质量影响很小。 编码（符号编码）：对量化了的系数进行编码，常采用变字长编码法。,解码部分： 进行与编码部分相反的逆操作，因量化是不可逆的，故没有相应的逆操作。 影响系统性能的主要因素是： 正交变换类型； 子图像大小； 量化策略。,5.4.3 变换方法选择 (1) KL

47、T（卡-洛变换） 性能：对平稳随机过程，KLT 是最佳正交变换，表现在： a) 变换系数互不相关； b) 变换域中能量高度集中。 因此，可在允许失真度下，获得最好的压缩效果。 实现：变换与输入数据有关，计算复杂，计算量大，实时处理有困难。原因是变换核是原图像协方差矩阵的特征矢量，且因图像不同而异（变换核不固定性），又不存在可分离性，目前尚无快速算法。,(2) DFT 性能：若图像是平稳马尔可夫过程，当N 时，DFT 的渐进特性与KLT一样，当N 为有限值时，能量集中特性比KLT 差。 实现：变换核具有可分离性，可利用一维FFT 实现。 缺点： a) 因有复数运算，导致硬件实现结构复杂； b)

48、子图像拼接处有Gibbs 效应（出现周期性花纹），使 恢复图像呈现明显方块效应。 因此，DFT 已不再应用于压缩编码，然而，DFT 仍是正交变换的基础，在理论上有重要价值。,(3) DCT 性能：业已证明，在原始图像序列的协方差矩阵为Toeplitz 矩阵、相关系数为 的条件下，DCT 接近KLT，因而是次最佳变换。 实现：有快速算法，只含实数运算。构造对称的数据序列，避免了图像边界处的跳跃，减小了边界处的Gibbs 效应。 (4) DWT、DHT 等方波型变换 与DFT 相比，算法简单，运算速度快，容易硬件实现，适用于高速实时系统，但因变换性能一般，较少用于变换编码。 结论 DCT 的信息集中能力和计算复杂性两者综合性能较好，在变换编码中主要选用DCT。如JPEG压缩标准,5.4.4 子图像尺寸选择 (1) 从计算量考虑： 设整幅图像尺寸为 ，子图像尺寸为 ，采用快速变换算法，乘法次数约为 式中， 为子图像总数。上式表明， ，计算量 ，允许失真度一定时，压缩比也小（若压缩比