第6章-图像压缩(1)-数字图像处理课件.ppt

第 6章 图像压缩 第6章 图像压缩 6.1 图像编码概述图像编码概述 6.2 统计编码统计编码 哈夫曼编码哈夫曼编码 香农编码香农编码 算术编码算术编码 行程编码行程编码 LZW编码编码 6.3 预测编码预测编码6.4 变换编码变换编码6.5 量化量化第 6章 图像压缩 6.1 图像压缩编码概述图像压缩编码概述 需求：需求：图像信号（尤其视频信号）数字化后的数据量很大，通 信和存储困难，必须压缩。压缩编码：压缩编码：寻找一种有效地表示图像信息的符号代码，力求用 最少的数码传递最大的信息量。属于信源编码的范畴。信源信源编码信道编码传输信道用户信源译码信道译码 图6-1 图像通信系统模型第 6章 图像压缩 表表6-1 几种常见应用的码率几种常见应用的码率 压缩效果：压缩效果：压缩比分别为47.2,21,18.25,71,92.8第 6章 图像压缩 6.1.1 图像压缩编码的基本依据图像压缩编码的基本依据数据冗余数据冗余（冈327)数据：数据：是信息传送的手段，对相同数量的信息可以用不同数量 的数据表示。数据压缩：数据压缩：用较少的数据量表示给定的信息量。数据和信息两个概念的意义是不同的。三种基本的数据冗余三种基本的数据冗余:编码冗余编码冗余 像素间冗余像素间冗余 心理视觉冗余心理视觉冗余 在数字图像压缩中，当这三种冗余中的一种或多种得到减少或消除时，就实现了数据压缩。第 6章 图像压缩 第 6章 图像压缩 2.像素间冗余像素间冗余像像素素间间冗冗余余：来自图像中对象之间的结构或几何关系，可用自相关函数描述。包括空间冗余、几何冗余、帧间冗余等都用来表示这些像素间的依赖性。空空间间冗冗余余：图像内部相邻像素之间存在较强的相关性所造成的冗余。因此单个像素的值可以用相邻的像素值进行推测。时间冗余：时间冗余：视频图像中的不同帧之间的相关性所造成的冗余。结构冗余：结构冗余：是指图像中存在很强的纹理结构或自相似性。解解决决的的思思路路：将二维像素阵列变换（或映射）为更有效的形式。如行程编码、变换编码、预测编码等。第 6章 图像压缩 3.视觉冗余视觉冗余视视觉觉冗冗余余：是指人眼不能感知或不敏感的那部分图像信息。这些冗余在不会削弱图像感知质量的情况下可以消除。例如，利用人眼对蓝光不敏感的视觉特性，在对彩色图像编码时，就可以用较低的精度对蓝色分量进行编码。解解决决的的思思路路：“量化”，表示从一个范围很广的输入值集合到有限的输出值的映射。由于这种映射是不可逆的，会导致一定量信息的丢失，为有损压缩。第 6章 图像压缩 4.图像的统计特性（朱图像的统计特性（朱161）（1）图像的自相关函数）图像的自相关函数图像的相关系数：直接反映任意两个像素之间的相关性。当两个像素在同一行时图像的一维自相关函数可近似为：图像的二维自相关函数可近似为：结论：二维自相关函数由中心向四周按指数规律衰减。结论：二维自相关函数由中心向四周按指数规律衰减。第 6章 图像压缩 第 6章 图像压缩（3）频率域上的统计特性频率域上的统计特性自相关函数和功率谱密度是一对傅立叶变换：结论：结论：对大多数图像，其能量的主要成分集中在频率域的 低频部分。第 6章 图像压缩 图图像像编编码码的的目目的的：就是充分利用图像中存在的各种冗余信息，特别是信息熵冗余、空间冗余、时间冗余以及视觉冗余，以尽量少的比特数来表示图像。问问题题：充分描述一幅图像且没有信息丢失的最小数据量是多少？丢失一定信息时的最小数据量是多少？解决：解决：信息论提供了理论框架，回答上述2个问题。第 6章 图像压缩 第 6章 图像压缩 实际的图像信源是一种有记忆信源，不能把一阶熵作为编码的数码率下界。假如N个符号之间存在关联性，设新符号为Bi(N)，每个符号的平均熵为有记忆信源的符号序列的熵值低于无记忆时的熵值。bit/符号第 6章 图像压缩 第 6章 图像压缩 对有记忆信源按符号来编码效率是不高的。熵的高阶估计和一阶估计之间的差异表明了是否存在像素间冗余。为此进行一些变换（包括预测差值的变换等）去除相关，然后再对新的符号逐个编码达到信源的熵值。如可以建立一种映射，从图像表达中去掉额外的1.811.250.56比特/像素。第 6章 图像压缩 例8.11 使用映射减少熵使用映射减少熵（冈350)通过相邻列相减构造一个差异阵列。新阵列的熵的一阶估计：1.41比特/像素；结论：由于结论：由于1.811.411.25,说明映射减少熵，但还可找说明映射减少熵，但还可找到更好的映射。到更好的映射。图像压缩的过程：映射符号编码量化 无损 无损 有损第 6章 图像压缩 第 6章 图像压缩 在信源一定的情况下，p(ai)是确定的，编码方法的选择实际上是改变条件概率Q(bj|ai)，它同时也决定了引入的失真的大小。我们希望找出在一定允许失真我们希望找出在一定允许失真D条件下的最低平均互条件下的最低平均互信息量，称之为率失真函数，记为信息量，称之为率失真函数，记为R(D):R(D)是在平均失真是在平均失真D小于允许失真小于允许失真D以内能够编码的码率下界。以内能够编码的码率下界。或者说，当数码率小于率失真函数时，无论采用何种编码方法，其平均失真必大于D。平均失真通常可用均方误差表示。.率失真函数对信源编码具有指导意义。第 6章 图像压缩 对有记忆信源对有记忆信源有记忆信源的率失真函数低于无记忆信源的率失真函数；对有记忆信源可经去相关的处理后，再按独立信源来对待，这就是图像编码中的两类基本方法：变换编码和预测编码。对于有记忆信源，当按符号序列组成编码，且序列长度很大时，就能趋于率失真函数的码率界限。由此得到高效的编码方法：矢量量化。第 6章 图像压缩 6.1.3 图像编码的分类图像编码的分类 自从提出图像编码技术这一研究方向40多多年年来来己经取得了巨大的进展，目前已有40多多种种图像压缩编码算法面世。至于这些方法哪些更好或者哪些不好，还很难评价，而且各个算法的压缩效率也是与具体的图像数据密切相关，无法下统一的结论。根根据据编编码码原原理理可可以以将将图图像像编编码码分分为为熵熵编编码码、预预测测编编码码、变换编码和混合编码等。变换编码和混合编码等。根根据据编编码码过过程程中中是是否否存存在在信信息息损损耗耗可可将将图图像像编编码码分分为为有损压缩和无损压缩。有损压缩和无损压缩。第 6章 图像压缩 1.根据编码原理分类根据编码原理分类（1）熵熵编编码码 熵编码是纯粹基于信号统计特性的编码技术，是一种无损编码。熵编码的基本原理是给出现概率较大的符号赋予一个短码字，而给出现概率较小的符号赋予一个长码字，从而使得最终的平均码长很小。哈夫曼编码 香农编码 算术编码 行程编码（Run Length Encoding）第 6章 图像压缩 （2）预预测测编编码码。预测编码是基于图像数据的空间或时间冗余特性，用相邻的已知像素来预测当前像素的取值，然后再对预测误差进行量化和编码。预测编码可分为帧内预测和帧间预测；常用的预测编码有差分脉码调制（Differential Pulse Code Modulation，DPCM）和运动补偿法。第 6章 图像压缩 第 6章 图像压缩 2.根据编码过程中是否存在信息损耗分类根据编码过程中是否存在信息损耗分类 根据对压缩编码后的图像进行重建的准确程度，可将常用的图像编码方法分为二类：（1）信信息息保保持持编编码码：也称无无失失真真编编码码，它要求在编解码过程中保证图像信息不丢失，从而可以完整地重建图像。信息保持编码的压缩比较低，一般不超过3:1，主要应用在图像的数字存储方面，常用于医学图像和遥感图像编码中。第 6章 图像压缩 （2）保保真真度度编编码码：主要利用人眼的视觉特性，在允许的失真（Lossy）条件下或一定的保真度准则下，最大限度地压缩图像。保真度编码可以实现较大的压缩比，主要用于数字电视技术、静止图像通信、娱乐等方面。对于这些图像，过高的空间分辨率和过多的灰度层次，不仅增加了数据量，而且人眼也接收不到。因此在编码过程中，可以丢掉一些人眼不敏感的信息，在保证一定的视觉效果条件下提高压缩比。第 6章 图像压缩 3.图像编码新技术图像编码新技术 图像编码已经发展了几十年，人们不断提出新的压缩方法。如：人工神经网络（Artificial Neural Network，ANN）分形编码（Fractal Coding）小波编码（Wavelet Coding）基于对象的压缩编码（Object Based Coding）基于模型的压缩编码（Model Based Coding）等等。第 6章 图像压缩 第 6章 图像压缩 小波编码小波编码 1989年，S.G.Mallat首次将小波变换用于图像编码。经过小波变换后的图像，具有良好的空间方向选择性，而且是多分辨率的，能够保持原图像在各种分辨率下的精细结构，与人的视觉特性十分吻合。模型编码模型编码 模型编码是近几年发展起来的一种很有前途的低比特率编码方法，其基本出发点是在编、解码两端分别建立起相同的模型，编码时利用先验模型抽取图像中的主要信息并用模型参数的形式表示，解码时则利用所接收的模型参数重建图像。第 6章 图像压缩 6.1.4 图像编码评价图像编码评价 随着众多图像压缩算法的出现，如何评价图像压缩算法就成为重要的课题。一般说来，评价图像压缩算法的优劣主要有以下4个参数个参数。1）算法的算法的编码效率编码效率 2）编码图像的编码图像的质量质量 3）算法的算法的适用范围适用范围 4）算法的算法的复杂度复杂度第 6章 图像压缩 第 6章 图像压缩 设一幅灰度级为N的图像，图像中第k级灰度出现的概率为Pk，图像大小为NxNy，每个像素用d比特表示，每两帧图像间隔t，则按信息论中信息熵的定义，数字图像的熵H由下式定义：由此可见，图像熵H表示各灰度级比特数的统计平均值。对于一种图像编码方法，设第k级灰度的码字长度为Bk，则该图像的平均码字长度R为（9.29）第 6章 图像压缩 于是，可定义编码效率为 每秒钟所需的传输比特数bps为 压缩比r为 由于同一压缩算法对不同图像的编码效率会有所不同，因此常需定义一些“标标准准图图像像”，如国际上流行的三幅图像Lena、Barbara和Mandrill。一般通过测量不同压缩算法对同一组“标准图像”的编码性能来评价各图像压缩算法的编码效率。第 6章 图像压缩 2）编码图像的质量编码图像的质量 图像质量评价分为客观质量评价和主观质量评价。最常用的客观质量评价指标是：均方误差均方误差峰值信噪比峰值信噪比主观质量评价是指由一批观察者对编码图像进行观察并打分，然后综合所有人的评判结果，给出图像的质量评价。第 6章 图像压缩 3）算法的适用范围算法的适用范围 特定的图像编码算法具有其相应的适用范围，并不对所有图像都有效。一般说来，大多数基于图像信息统计特性的压缩算法具有较广的适用范围。而一些特定的编码算法的适用范围较窄，如分形编码主要用于自相似性高的图像。第 6章 图像压缩 4）算法的复杂度算法的复杂度 算法的复杂度即指完成图像压缩和解压缩所需的运算量和硬件实现该算法的难易程度。优秀的压缩算法要求有较高的压缩比，压缩和解压缩快，算法简单，易于硬件实现，还要求解压缩后的图像质量较好。选用编码方法时一定要考虑图像信源本身的统计特性、多媒体系统(硬件和软件产品)的适应能力、应用环境以及技术标准。第 6章 图像压缩 6.2 统计编码统计编码现介绍几个定义：（1)唯一可译码唯一可译码：所编码字序列能被唯一的译出来。采用非续长代码。（2)非续长代码非续长代码。码字集合0,10,110,111 编码：00111.译码：0,0,0,110,0,0,10,0,0,0,111 第 6章 图像压缩 6.2.1 哈夫曼编码哈夫曼编码 1.哈夫曼编码的理论基础哈夫曼编码的理论基础 根据信息论中信源编码理论，若平均码长R大于等于图像熵H时，总可设计出一种无失真编码。当平均码长远大于图像熵时，该编码方法效率很低；当当平平均均码码长长等等于于或或很很接接近近于于图图像像熵熵时时，称称此此编编码码方方法法为最佳编码，为最佳编码，此时不会引起图像失真；此时不会引起图像失真；当平均码长小于图像熵时，压缩比较高，但会引起图像失真。第 6章 图像压缩 变长最佳编码定理：变长最佳编码定理：在变长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度为最小，这就是变长最佳编码定理。变长最佳编码定理是哈夫曼编码的理论基础。设D为编码所使用的数制，则变长最佳编码的平均码字长度R的范围为 第 6章 图像压缩 2.哈夫曼编码算法哈夫曼编码算法 哈夫曼编码是以信源概率分布为基础的。哈夫曼编码的一般算法如下：（1）首先统计信源中各符号出现的概率，按符号出现的概率从大到小排序。从大到小排序。（2）把最小的两个概率相加最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。第 6章 图像压缩 （3）对对新新的的概概率率集集合合重重新新排排序序，再次把其中最小的两个概率相加，组成新的概率集合。如此重复进行，直到最后两个概率的和为1。（4）分分配配码码字字。码字分配从最后一步开始反向进行，对于每次相加的两个概率，给大的赋“0”，小的赋“1”（也可以全部相反，如果两个概率相等，则从中任选一个赋“0”，另一个赋“1”即可），读出时由该符号开始一直走到最后的概率和“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。第 6章 图像压缩 例例：设一幅灰度级为8（分别用S0、S1、S2、S3、S4、S5、S6、S7表示）的图像中，各灰度所对应的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04。现对其进行哈夫曼编码 编码过程如图9-1所示，具体步骤如下：(1)首先对信源概率从大到小排序，选出最小的两个概率（0.04和0.05），相加得0.09，与其他概率组成新的概率集合0.40，0.18，0.10，0.10，0.07，0.06，0.09。第 6章 图像压缩 (2)对新的概率集合重新排序，选出最小的两个概率（0.06和0.07），相加得0.13，组成新的概率集合0.40，0.18，0.10，0.10，0.09，0.13。(3)对新的概率集合重新排序，选出最小的两个概率（0.10和0.09），相加得0.19，组成新的概率集合0.40，0.18，0.13，0.10，0.19。(4)对新的概率集合重新排序，选出最小的两个概率（0.13和0.10），相加得0.23，组成新的概率集合0.40，0.19，0.18，0.23。第 6章 图像压缩 (5)对新的概率集合重新排序，选出最小的两个概率（0.19和0.18），相加得0.37，组成新的概率集合0.40，0.23，0.37。(6)对新的概率集合重新排序，选出最小的两个概率（0.23和0.37），相加得0.60，组成新的概率集合0.40，0.60。(7)直到最后两个概率（直到最后两个概率（0.60和和0.40）相加和为）相加和为1。第 6章 图像压缩 (8)分分配配码码字字。从最后一步反向进行，首先给最后相加的两个概率（0.60和0.40）分配码字，由于0.60大于0.40，于是给0.60赋“0”，给0.40赋“1”。如此依次给每次相加的两个概率分配码字。(9)最后写出每个符号的哈夫曼编码。以符号S1（对应的概率为0.18）为例，在从0.18到1.0的路径上，它所遇到的赋值（“0”或“1”）依次为1、0、0，将其反向排列成“001”，于是就形成了符号S1的哈夫曼码字“001”。第 6章 图像压缩 图9.8哈夫曼编码过程 第 6章 图像压缩 哈夫曼编码的编码效率哈夫曼编码的编码效率 平均码长 数字图像的熵 第 6章 图像压缩 哈夫曼编码的编码效率是相当高的，其冗余度只有2.2%。如果采用等长编码，由于有8种灰度级，则每种灰度级别至少需要3比特来表示，对于例中的图像而言 压缩比压缩比 3/2.61=1.15 对不同概率分布的信源，编码效率有所差别。哈夫曼编码的编码效率哈夫曼编码的编码效率为为 第 6章 图像压缩 10-2 啥夫曼编码在不同概率分布下的编码效果对比啥夫曼编码在不同概率分布下的编码效果对比 第 6章 图像压缩 在表10-2中，第二种情况的概率分布也服从2的负幂次方，故其编码效率也可以达到100%，但由于它服从均匀分布，其熵最大，平均编码长度很大，因此从其他指标看（如，压缩比r），其编码效果最低。也就是说，在信源概率接近于均匀分布时，一般不使用哈夫曼编码。当当信信源源概概率率为为2的的负负幂幂次次方方时时，哈哈夫夫曼曼编编码码的的编编码码效率可达效率可达100%，其平均码字长度也很短，其平均码字长度也很短；当信源概率为均匀分布时，当信源概率为均匀分布时，其压缩比明显降低。其压缩比明显降低。第 6章 图像压缩 6.2.2 香农编码香农编码（自学）（自学）香农（Shannon）编码也是一种常见的可变字长编码。与哈夫曼编码相似，当信源符号出现的概率正好为2-i（i3为特例。第 6章 图像压缩 除此之外，除此之外，还有二分法香农编码方法。其步骤如下：还有二分法香农编码方法。其步骤如下：（1）首先统计出每个符号出现的概率；首先统计出每个符号出现的概率；（2）从左到右对上述概率从大到小排序；从左到右对上述概率从大到小排序；（3）从从这这个个概概率率集集合合中中的的某某个个位位置置将将其其分分为为两两个个子子集集合合，并并尽尽量量使使两两个个子子集集合合的的概概率率和和近近似似相相等等，给给前前面面一一个个子子集集合合赋赋值值为为0，后面一个子集合赋值为后面一个子集合赋值为1；（4）重复步骤重复步骤3，直到各个子集合中只有一个元素为止；，直到各个子集合中只有一个元素为止；（5）将每个元素所属的子集合的值依次串起来，即可得到将每个元素所属的子集合的值依次串起来，即可得到各个元素的香农编码。各个元素的香农编码。第 6章 图像压缩 表表10-4 二分法香农编码二分法香农编码 第 6章 图像压缩 6.2.3 算算 术术 编编 码码 在算术编码前，主要的统计编码是游程编码和霍夫曼编码。理论上讲，霍夫曼编码可以得到最佳的编码效果，但实际上却不行。由于计算机的限制，霍夫曼编码必须用整数个的二进制“位(bit)”编码，这就使理论上计算得到如:0.33bit,l.lbit的码长时，都只能用lbit来表示，使其编码性能大打折扣。第 6章 图像压缩 而算术编码的出现，解决了这个问题，由此提高了数据压缩的效果。算术编码用一个介于0-1之间的小数来表示对符号编码的结果，不论待编码的数据有多少，其编码结果都是一个数，且是介于0-1间的小数，表示取值区间的宽度，信息越长，它所对应的区间越窄，编码表示它的二进制位就越多。所以当连续的符号被加进来时，这一区间被不断变窄，出现概率小的符号比出现概率大的符号使区间变窄的速度快，因此增加的比特位更多.第 6章 图像压缩 算术编码有两种模式：一种是基于信源概率统计特性的固固定定编编码码模模式式；另一种是针对未知信源概率模型的自适应模式自适应模式。算术编码一般要优于Huffman编码，它比Huffman编码效率提高10%左右。取得了许多重要的应用，在JPEG扩展系统中，就用算术编码取代了哈夫曼编码，JPEG2000采用了算术编码；编码复杂性较大。第 6章 图像压缩 方法：将被编码的信源消息表示成实数轴上方法：将被编码的信源消息表示成实数轴上01之间之间 的一个间隔（或子区间）。的一个间隔（或子区间）。消息越长，编码表消息越长，编码表 示它的间隔就越小。示它的间隔就越小。算术编码的主要步骤如下算术编码的主要步骤如下:1)首先把“当前区间”定义为0,1。2)对输入流中的每个符号s,重复下面的两步:把当前区间分割为长度正比于符号概率的子区间。为s选择一个子区间，并将其定义为新的当前区间。3)当把整个输入流处理完后，输出的即为能唯一确定当前区间的数字。第 6章 图像压缩 例例1：假设信源符号的集合为a,b,c，这些符号的概率分别为0.1，0.4，0.5。如果输人序列为：caccb，确定算术编码。步骤：1)把区间0，1)分成3个子区间：0，0.1)，0.1，0.5)，0.5，1)2)第一个待编码符号为c，找到其编码区间：0.5，1)。第二个待编码符号为a，它的概率区间是0，0.1)，所以取 0.5，1)的第一个1/10作为新区间，即0.5，0.55)。依此类推，编码第三个符号c时取新区间为0.525，0.55)，编码第四个符号c时取新区间为0.5375，0.55)，等等。3)编码输出是最新区间中的某一数。该实例编码和译码的全部过程如表5.1和表5.2所示。第 6章 图像压缩 表表5.1 编码过程编码过程步骤输入符 号编码区间编码判决1c0.5,1）符号的区间范围符号的区间范围0.5,1）2a0.5,0.55）0.5,1）区间的第）区间的第1个个1/103c0.525,0.55）0.5,0.55）区间的最后）区间的最后5个个1/10，后，后124c0.5375,0.55）0.525,0.55）区间的最后）区间的最后5个个1/105b0.53875,0.54375)0.5375,0.55）区间的）区间的4个个1/10,从第从第2个个1/10开开始始6选择选择0.53875,0.54375）中的某一值作为最终输出：）中的某一值作为最终输出：0.54第 6章 图像压缩 表表5.2 译码过程译码过程 步骤步骤区区 间间译码符号译码符号译码判决译码判决10.5,1）c0.54在区间在区间 0.5,1）20.5,0.55）a0.54在区间在区间0.5,1）第）第1个个1/1030.525,0.55）c0.54在区间在区间0.5,0.55）的第）的第8个个1/1040.5375,0.55）c0.54在区间在区间0.525,0.55）的第）的第7个个1/1050.53875,0.54375）b0.54在区间在区间0.5375,0.55）的第）的第3个个1/106译码的信息：译码的信息：caccb第 6章 图像压缩 为便于计算，为便于计算，给出给出一组关系式一组关系式：StartN、EndN分别表示新间隔（或称之为区间）的起始位置和结束位置;StartB表示前一间隔的起始位置;L为前一间隔的长度;LeftC、RightC分别表示当前编码符号的初始区间的左端和右端。StartN=StartB+LeftCL EndN=StartB+RightCL 第 6章 图像压缩 例例2：设一待编码的数据序列为“dacab”，信源中各符号出现的概率依次为P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。首先，数据序列中的各数据符号在区间0,1内的间隔设定为a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d=0.8,1.0）。第一个被压缩的符号为“d”，其初始间隔为0.8,1.0)；第二个被压缩的符号为“a”，由于前面的符号“d”的取值区间被限制在0.8,1.0)范围内，所以“a”的取值范围应在前一符号间隔0.8,1.0)的0,0.4)子区间内，根据上式可知 第 6章 图像压缩 即即“a”的实际编码区间在的实际编码区间在0.8,0.88)之间。之间。第第三三个个被被压压缩缩的的符符号号为为“c”，其其编编码码取取值值范范围围应应在在0.8,0.88)区间的区间的0.6,0.8)的子区间内，据上式可知的子区间内，据上式可知 第四个被压缩的符号为第四个被压缩的符号为“a”，同理，根据上式可知，同理，根据上式可知 StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.848)=0.8544 StartN=0.8+0(1.0-0.8)=0.8EndN=0.8+0.4(1.0-0.8)=0.88 第 6章 图像压缩 第五个被压缩的符号为“b”，同理，根据上式可知 StartN=0.848+0.4(0.8544-0.848)=0.850 56EndN=0.848+0.6(0.8544-0.848)=0.851 84 至至此此，数数据据序序列列“dacab”已已被被描描述述为为一一个个实实数数区区间间0.850 56,0.851 84，或或者者说说在在此此区区间间内内的的任任一一实实数数值值都都惟惟一一对对应应该该数数据据序序列列。即即可可用用一一个个实实数数表表示示这这一一数数据据序序列列。把把区区间间0.850 56,0.851 84 用用 二二 进进 制制 形形 式式 表表 示示 为为 0.110110011011,0.110110100001。从从这这个个区区间间可可以以看看出出，0.1101101位位于于这这个个区区间间内内并并且且其其编编码码最短，最短，故把其作为数据序列故把其作为数据序列“dacab”的编码输出。的编码输出。第 6章 图像压缩 考考虑虑到到算算术术编编码码中中任任一一数数据据序序列列的的编编码码都都含含有有“0.”，在在编编码码时时可可以以不不考考虑虑“0.”，于于是是把把作作为为本本例例中中的的数数据据序序列列的的算算术术编码。编码。编编码码效效率率：数数据据序序列列“dacab”用用7比比特特的的二二进进制制代代码就可以表示，码就可以表示，平均码长为平均码长为1.4比特字符比特字符。解解码码是是编编码码的的逆逆过过程程，根根据据编编码码时时的的概概率率分分配配表表和和压压缩缩后后数据代码所在的范围，确定代码所对应的每一个数据符号。数据代码所在的范围，确定代码所对应的每一个数据符号。第 6章 图像压缩 6.2.4 行行 程程 编编 码码 行程编码又称行程长度编码（Run Length Encoding，RLE），是一种熵编码，编编码码原原理理：具具有有相相同同值值的的连连续续串串用用其其串串长长和和一一个个代代表表值值来来代代替替，该该连连续续串串就就称称为为行行程程，串串长长,称称为为行行程程长长度。度。例如，有一字符串“aabbbcddddd”，则经行程长度编码后，该字符串可以只用“2a3b1c5d”来表示。第 6章 图像压缩 一个4040的棋盘图象的行程编码演示第 6章 图像压缩 原始图象的大小原始图象的大小:Name Size Bytes Class It 40 x40 12800 double arrayGrand total is 1600 elements using 12800 bytes压缩图象的大小压缩图象的大小:Name Size Bytes Class P 1x400 3200 double arrayGrand total is 400 elements using 3200 bytes 图象的压缩比图象的压缩比:12800/3200=4，图象可以完全无失真恢复图象可以完全无失真恢复 行程编码要依据图象本身的特点，若相同颜色块越大，压行程编码要依据图象本身的特点，若相同颜色块越大，压缩比越高，反之越小。缩比越高，反之越小。第 6章 图像压缩 行行程程编编码码比比较较适适合合于于二二值值图图像像的的编编码码，一一般般用用于于量量化化后后出出现现大大量量零零系系数数连连续续的的场场合合，用用行行程程来来表表示示连连零零码码。如如果果图图像像是是由由很很多多块块颜颜色色或或灰灰度度相相同同的的大大面面积积区区域域组组成成的的，那那么么采采用用行行程程编码可以达到很高的压缩比。编码可以达到很高的压缩比。如如果果图图像像中中的的数数据据非非常常分分散散，则则行行程程编编码码不不但但不不能能压压缩缩数数据据，反而会增加图像文件的大小。反而会增加图像文件的大小。为为了了达达到到较较好好的的压压缩缩效效果果，一一般般不不单单独独采采用用行行程程编编码码，而而是是和和其其他他编编码码方方法法结结合合使使用用。例例如如，在在JPEG中中，先先对对图图像像作作分分块块处处理理，再再对对这这些些分分块块图图像像进进行行离离散散余余弦弦变变换换（DCT），对对变变换换后后的的频频域域数数据据进进行行量量化化并并作作Z字字形形扫扫描描，接接着着对对扫扫描描结结果果作作行行程编码，程编码，对行程编码后的结果再作哈夫曼编码。对行程编码后的结果再作哈夫曼编码。第 6章 图像压缩 6.2.5 LZW编码编码字串表编码字串表编码 LZW（Lempel-Ziv&Welch）编码又称字串表编码，属于无损编码。LZW编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。LZW编编码码的的基基本本思思想想是是：在在编编码码过过程程中中，将将所所遇遇到到的的字字符符串串建建立立一一个个字字符符串串表表，表表中中的的每每个个字字符符串串都都对对应应一一个个索索引引，编编码码时时用用该该字字符符串串在在字字串串表表中中的的索索引引来代替原始的数据串。来代替原始的数据串。第 6章 图像压缩 LZW编码实例编码实例 设有一来源于4色（以a、b、c、d表示）图像的数据流aabcabbbbd，现对其进行LZW编码。编码前，首先需要初始化一个字符串表。由于图像中只有四种颜色，因而我们可以只用4比特表示字符串表中每个字符串的索引，表中的前4项代表4种颜色，后两项分别表示初始化和图像结束标志，建立的初始化字符串表如表10-5所示。接着把S1和S2初始化为空（即NULL），输出LZW_CLEAR的在字符串表中的索引值4H，接下来是对图像数据的编码。第 6章 图像压缩 表10-5 初始化字符串表 字符串 索引 a 0 H b1 H c2 H d3 H LZW_CLEAR 4 H LZW_EOI 5 H 第 6章 图像压缩 表表10-6 GIF-LZW编码过程编码过程 第 6章 图像压缩 表表10-7 GIF-LZW解码过程解码过程 第 6章 图像压缩 应应用用：GIF（Graphics Interchange Format）最最初初是是由由美美国国CompuServe 于于1987年年开开发发的的一一种种压压缩缩位位图图格格式式。它它可可支支持持多多达达 256 种种的的颜颜色色，具具有有极极佳佳的的压压缩缩效效率率，已已成成为为Internet 上上一一种种流流行行的的文文件件格格式式。GIF图图像像文文件件采采用用的的是是一一种种改改良良的的LZW压压缩缩算算法法，通通常常称称为为GIF-LZW压压缩缩算算法法。GIF图图像像文文件件以以块块（又又称称为为区区域域结结构构）的的方方式式来来存存储储图图像像相相关关的的信信息息，具具体体的的文文件件格格式式可可参考图像文件格式的相关书籍。参考图像文件格式的相关书籍。第 6章 图像压缩 6.2.6 位平面编码（比特面编码）位平面编码（比特面编码）1.基本思路基本思路 将一幅多级将一幅多级(单色的或彩色的单色的或彩色的)图像分解为一系列二图像分解为一系列二值图像，并通过几种熟知的二值图像压缩方法，对每幅值图像，并通过几种熟知的二值图像压缩方法，对每幅二值图像进行压缩。二值图像进行压缩。包括包括位平面分解位平面分解和和二值图像压缩二值图像压缩两部分。两部分。第 6章 图像压缩 2.位平面分解方法位平面分解方法 一幅m比特的灰度图像具有的灰度级可以用以2为底的多项式进行表示：1 0 .1 1 基于这种性质，将这类图像分解成一个二值图像集的一种简单方法就是：将多项式的m个系数分离到m个1比特的位平面之中。零级位平面是通过收集每个像素的a0位生成的；而第(m1)级位平面包含am-1系数。第 6章 图像压缩 于是，图像完全可以用一组共8个比特面来表示。第 6章 图像压缩 PCM编码存在的缺点：对于二值图像的编码，主要是利用其存在连续的“0”和连续的“l”这样的统计特性。通常，数字化后像素的电平值都是PCM自然二进制码，其特点是高位最重要的比特面图像简单，但重要性稍差的比特面图像相当复杂，尤其是低位最不重要的比特面噪声为主要成分。在这样的比特面中，“0”、“1”交替出现的情况较多，各比特平面中相关性减小，因而使得压缩效率降低。其原因是PCM编码中，若相邻像素的灰度值变化一个等级，其编码可能相差好几个比特。例如，如果一个亮度为127(01111111)的像素与一个亮度为128(10000000)的像素相邻，每个位平面将包含一个对应0到1的转换。第 6章 图像压缩 解决的方法：解决的方法：采用格雷采用格雷(Gray)码来表示像素的灰度值码来表示像素的灰度值。两个相邻值的格雷码之间只有一个比特是不同的，这就保持了两个相邻值的格雷码之间只有一个比特是不同的，这就保持了相邻像素间较强的相关性。相邻像素间较强的相关性。例如，对应127和128的灰度编码分别为和。当灰度级127和128相邻的时候，只有第7个位平面含有一次0到1的转换。自然二进制码和格雷码之间的转换规则如下：第 6章 图像压缩 PCM自然二进制码自然二进制码 格雷格雷(Gray)码码第 6章 图像压缩 第 6章 图像压缩 第 6章 图像压缩 PCM自然二进制码自然二进制码 格雷格雷(Gray)码码第 6章 图像压缩 图显示了小孩图像中的8个二值格雷码编码的位平面。高阶位平面比它们对应的低阶部分要简单得多。即，这些位平面中包含大块的均匀区域，其中的图像细节相当少、忙乱或随意性较小。高位平面中格雷码比自然二进制码呈现了更好的像素相关性。对于两种码字，低位平面的像素间相关性都很差，因此，从整体来说，格雷码的压缩效率高于自然二进制码。第 6章 图像压缩 3.二值图像的编码方法二值图像的编码方法（1）常数值区域编码）常数值区域编码 压缩二值图像或位平面的一种简单但有效的方法是使用压缩二值图像或位平面的一种简单但有效的方法是使用指定的码字识别大片连续的指定的码字识别大片连续的1和和0区域。这样一种方法称为常区域。这样一种方法称为常数区域编码数区域编码(CAC).图像被分成大小为图像被分成大小为pq个像素的不同块，这些块被分个像素的不同块，这些块被分成成全白色、全黑色或混合亮度全白色、全黑色或混合亮度等不同的类。出现可能性最大或等不同的类。出现可能性最大或最频繁的类被分配给最频繁的类被分配给l比特码字比特码字0，另两个类分给，另两个类分给2比特码比特码10和和11。因为通常用于表示每个常数区域的。因为通常用于表示每个常数区域的pq比特被比特被1比特或比特或2比比特码字代替，所以可以实现压缩。当然，分配给混合亮度类特码字代替，所以可以实现压缩。当然，分配给混合亮度类的编码被作为一个前缀使用，这个前缀的后面跟着块的的编码被作为一个前缀使用，这个前缀的后面跟着块的pq比比特模式。特模式。第 6章 图像压缩(2)一维行程编码一维行程编码 对常数区域进行编码的一种有效的替代方法是用一长度序对常数区域进行编码的一种有效的替代方法是用一长度序列表示图像或位平面的每一行，这些长度描绘了对黑色和白列表示图像或位平面的每一行，这些长度描绘了对黑色和白色像素的连续行程。这种技术称为行程编码。色像素的连续行程。这种技术称为行程编码。基本概念是，对从左到右扫描一行时所遇到的基本概念是，对从左到右扫描一行时所遇到的1或或0的连接的连接组，使用这些连接组的长度进行编码，并且建立决定行程值组，使用这些连接组的长度进行编码，并且建立决定行程值的约定。的约定。尽管行程长度编码本身是一种压缩图像的有效方法，但其尽管行程长度编码本身是一种压缩图像的有效方法，但其他的压缩方法通常可以通过对行程长度本身进行变长编码实他的压缩方法通常可以通过对行程长度本身进行变长编码实现。现。第 6章 图像压缩（3）二维行程长度编码）二维行程长度编码 一维行程长度编码概念很容易扩展得到各种二维编码过程。一维行程长度编码概念很容易扩展得到各种二维编码过程。其中较为熟知的一种方法是相对地址编码其中较为熟知的一种方法是相对地址编码(RAC)。这种方法是。这种方法是以记录每次黑色和白色行程开始和结束的二值转换的原理为基以记录每次黑色和白色行程开始和结束的二值转换的原理为基础的。础的。类似行程长度编码，相对地址编码要求按惯