CH3 图像压缩编码

图像通信原理与技术第3章图像压缩编码第

3

章图像压缩编码3.1图像压缩编码的分类3.2数据压缩与信息论基础

3.2.1数据压缩与数据冗余

3.2.2图像压缩编码系统的基本构成

3.2.3信息论基础3.3霍夫曼编码3.4游程长度编码第

3

章图像压缩编码（续）3.4.1二值图像的游程编码

3.4.2一维游程编码

3.4.3二维游程编码

3.4.4游程编码综述3.5算术编码

3.5.1算术编码原理

3.5.2算术码分析第

3

章图像压缩编码（续）3.5.3算术编码的效率*3.6LZW字典编码

3.1图像压缩编码的分类(1)冗余度压缩方法，也称无损压缩、信息保持编码或熵编码。熵编码是纯粹基于信号统计特性的一种编码方法。它利用图像信源概率分布的不均匀性，通过变长编码来减少信源数据冗余，解码后的重建图像和压缩编码前的原始图像完全相同，没有失真。

无损压缩中经常采用的方法有霍夫曼(Huffman)编码、游程编码(Run-lengthcode)、算术编码（ArithmeticCoding）和字典LZW编码等。(2)信息量压缩方法，也称有损压缩、失真度编码或熵压缩编码。该方法利用了人类视觉对图像中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息。常用的有损压缩方法有：脉冲编码调制(PCM)、预测编码(DPCM、运动补偿)、变换编码（DFT、DCT、K-L变换、Walsh-Hadamard变换、小波变换）等，以及灰度图像的方块编码、比特平面分层编码及抖动编码等。还有一种按照描述图像或视频源的信源模型来进行分类的方法，可分为基于波形编码和基于内容编码两大类。基于波形编码的信源模型通常是采用像素来表示图像的，像素是最基本单元，尽可能精确地用像素值表示在该像素点的光强和颜色值，不考虑一组像素可能代表一个具体物理对象这一事实情况。

另一类是其信源模型的基本单元不是像素而是对象的编码方法，称为基于内容(对象)的编码技术。基于对象的分析综合编码、物体基编码、模型基和语义基编码都属于这一类。显然。以对象特征信息来描述图像是一种比用像素来描述的更高层次的编码方法，可以达到更高的压缩率。

3.2数据压缩与信息论基础3.2.1数据压缩与数据冗余

数据压缩，就是以最少的数码表示信源所发送的信号，减少容纳给定消息集合或数据采样集合的信号空间。图像数据中存在着大量的冗余，即图像的各像素数据之间存在着极强的相关性。利用这些相关性，一部分像素的数据可以由另一部分像素的数据推导出来，如此可使图像数据量极大地压缩。经过分析发现，图像数据压缩机理来自两个方面：一是图像信号中存在大量冗余可供压缩，并且这种冗余度在解码后还可无失真地恢复；二是利用人眼的视觉特性，在不被主观视觉察觉的范围内，通过减少表示信号的精度，以一定的客观失真换取数据压缩。

图像信号的冗余度存在于结构和统计两方面。正如我们在第二章中图像的统计特性中分析的，图像信号结构上的冗余度表现为很强的空间（帧内的）和时间（帧间的）上的相关性。

若用相同码长表示不同出现概率的符号，则会造成比特数的浪费。如果采用可变长编码技术，对出现概率大的符号用短码字表示，对出现概率小的符号用长码字表示，则可去除信号统计上的冗余，从而节约码字。

信号统计上的冗余度来源于被编码信号概率密度分布的不均匀。3.2.2图像压缩编码系统的基本构成图3-2图像压缩编码系统组成框图图3-3信源编码器与解码器的组成框图

在以上框图中，不同的图像编码系统可能采用上述框图中的不同组合，变换器和编码器是可逆的，而量化器是不可逆的。所以，无失真的信源编码器不能包含量化器，在大多数实用情况下，为了得到期望的比特率，必须允许图像质量有少许的下降，有损压缩方法既利用了图像的结构冗余和统计冗余，同时又利用了其视觉冗余特性。3.2.3信息论基础1.信源模型及其熵

（1）独立信源最简单的信源就是独立信源，在一个独立信源中，连续发生的各个符号都是统计独立的。信息量定义为：

若对一个独立信源中所有可能符号的信息量取平均，就得到信源中每个符号的平均信息量，又叫做熵

可以证明，对于具有一定数目的符号的任一独立信源，当各个符号的发生概率都相等时，其熵取最大值。（2）马尔可夫信源在实际中，信源发出的各个符号之间往往并不是相互独立，而是具有统计的关联性。2.无失真编码定理与最佳编码

无失真编码定理：对于离散信源，对其编码时每个符号能达到的平均码长满足以下不等式该定理一方面指出了每个符号平均码长的下限为信源的熵，另一方面说明存在任意接近该下限的编码。对于独立信源，该定理适用于对单个符号编码的情况，也适用于对符号块编码的情况；对于N阶的马尔可夫信源，只适用于对不少于N个符号的符号块编码的情况。对离散信源进行编码时，可以通过等长与不等长编码实现。等长编码对于一个消息集合中的不同消息，若采用相同长度的不同码字去代表，就叫做等长编码。（2）变长码的基本分析与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度的码字来表示。当每个符号的码长都等于其信息量时，编码的平均码长可达到其下限，即信源的熵。当然，这只有当每个符号的信息量都是整数时才可能实现。按照信息量的定义，这相当于，应为概率较大的符号分配较短的码字，而为概率较小的符号分配较长的码字，这正是变长编码的基本原则。采用变长码可以提高编码效率，即对相同信息量所需的平均编码长度可以短一些。采用等长编码的优点是编码过程和解码过程简单。但由于这种编码方法没有考虑各个符号出现的概率，实际上就是将它们当作等概率事件来处理的，因而它的编码效率较低。变长编码方法中，表示符号的码字的长度不是固定不变的，而是随符号出现的概率而变化：给出现概率高的符号分配较短的码字，给出现概率低的符号分配较长的码字。可以证明，在非均匀符号概率分布的情况下，变长编码总的编码效率要高于等字长编码。但是，变长码在编码时要预先知道各种消息符号出现的概率，而解码也远比等长码复杂：对于等长码只要使不同的消息对应不同的码字，而收端只要能正确识别出一个码字的起始位置就能正确译码；但对变长码要正确识别码字起点就不那么容易，并且还存在唯一可译性、译码实时性及与匀速输入输出匹配的缓存问题。（3）编码效率编码效率是信源的熵与平均码长之比，（4）压缩比压缩比是编码前后平均码长之比（5）比特率通常指编码的平均码长，借助熵的概念可以定义量度任何特定码性能的准则，即平均码字长度，单位也是比特/字符。3.3霍夫曼编码在变长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度为最小，这就是变长最佳编码定理。变长最佳编码定理是霍夫曼编码的理论基础。要注意的是，变长编码是一种信息保持型编码(熵编码)，即编解码的过程并不引起信息量的损失，因为它的符号和码字之间是唯一对应的。霍夫曼编码的基本步骤如下：

(1)按概率从大到小的顺序排列信源符号。

(2)把最小的两个概率相加合并成新的概率，与剩余的概率组成新的概率集合。(3)对新的概率集合重新按照从大到小排序，再次把其中最小的两个概率相加，组成新的概率集合。如此重复进行，直到最后两个概率的和为1。(4)分配码字。码字分配从最后一步开始反向进行，对于每次相加的两个概率，给大概率分配“0”，小概率分配“1”(也可以全部相反，如果两个概率相等，则从中任选一个赋“0”，另一个赋“1”即可)，读出时由最终一个符号开始，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。需要注意：①霍夫曼编码的算法是确定的，但编出的码并非是唯一的。②由于霍夫曼编码的依据是信源符号的概率分布，故其编码效率取决于信源的统计特性。霍夫曼编码的局限性在于，该编码方法只适用于离散信源，即信源符号个数为有限数；编码时需要知道输入符号集的概率分布；在进行Huffman编码压缩时，计算量大而复杂，尤其是译码复杂度较高。由于码长不等，还存在一个输入与输出的速率匹配问题。3.4游程长度编码游程长度编码(Run-Lengthcoding，RLC)的基本思想，是将具有相同数值的、连续出现的信源符号构成的符号串用其数值及串的长度表示。3.4.1二值图像的游程编码二值图像游程编码的基本思想是，当按照二值图像从左到右的扫描顺序观察每一行时发现，二值图像的每一扫描行均由交替出现的白像素游程(称作自长)和黑像素游程(称作黑长)组成。白游程的后面必然是黑游程，反之亦然，黑游程的后面必然是白游程。因而只要知道了各扫描线的头一个游程是黑还是白，就不再需要指示游程黑白的信息了。进一步对不同长度的白长和黑长按其出现概率的不同分别配以不同长度的码字，就是二值图像的RLC。图3-7游程编码示意图3.4.2一维游程编码下面介绍传真三类机（G3）所采用的改进型Huffman编码（ModifiedHuffman）的方法。视觉特性根据一维游程编码原理，一维游长编码规则如下：①当RL=0～63，用一个相应的终止码表示；②当RL=64～l728，用一个终止码加一个起始码。③规定每行都从白游程开始，若实际扫描行由黑开始，则需在行首加零长度白游程；行结束要加行同步码EOL(见表3-2)。3.4.3二维游程编码

二维游程编码方法，不是直接对游程长度本身进行编码，而是对扫描行之间游程长度变化的差值进行编码。由于图像所存在的相关性。这种编码的数码率一定会下降。图3-9二维游程编码示意图3.4.4游程编码综述游程编码的优点是算法简单、易于实现，由于是将信源符号序列中的相同字符转换成一个计数字段再加上一个重复字符标志，所以对于二值图像最为有效；缺点是对于特定的不连续符号序列，会出现编码后数据量增加的情况。此外，变长码的固有缺点仍然存在，即需要较大容量的缓冲和较低误码的优质信道。3.5算术编码3.5.1算术编码原理算术编码是一种从整个符号系列出发，采用递推形式连续编码的方法。在算术编码中，字母表中的符号和码字间不再存在一一对应关系，一个算术码字要赋给整个信源符号序列（即不是一次编一个号），而码字本身确定0和1之间的一个实数区间。算术编码和上述霍夫曼块编码的区别就在于：在算术编码中，输入序列（即被赋给单个码字的符号块）的长度，是可变的，可以说，算术编码是将可变长码字赋给可变长符号块。正是由于算术编码不需要为定长符号块分配整数长的码字，理论上能达到无损编码定理所规定的最低限。算术编码在编码过程中，尽管在计算时有乘法运算，但可以通过移位实现，即通过加法和移位实现算术运算。在解码时，要除以符号区间概率，也可以通过移位实现，即通过减法和移位实现算术解码。这正是把这种编码方法称为算术码的原因。3.5.2算术码分析算术编码跳出了分组编码的范畴，从全序列出发，采用递推形式的连续编码，它不是将单个的信源符号映射成一个码字，而是将整个符号序列映射为实数轴上[0,1）区间内的一个小区间，其长度等于该序列的概率。从小区间内选择一个代表性的二进制小数，作为实际的编码输出，从而达到高效编码的目的。不论是否是二元信源，也不论数据的概率分布如何，其平均码长均能逼近信源的熵。随着输入符号越来越多，子区间分割越来越精细，因此表示其左端点的数值的有效位数也越来越多。如果等整个符号序列输入完毕后再将最终得到的左端点输出，将遇到两个问题：第一，当符号序列很长时，将不能实时编解码；第二，有效位太长的数难以表示。

为了解决这个问题，通常采用两个有限精度的移位寄存器存放码字的最新部分，随着序列中符号的不断输入，不断地将其中的高位移出到信道上，以实现实时编解码。3.5.3算术编码的效率算术编码的最大优点之一在于它具有自适应性和高编码效率。算术编码的模式选择直接影响编码效率。其模式有固定模式和自适应模式两种。固定模式是基于概率分布模型的，而在自适应模式中，其各符号的初始概率都相同，但随着符号顺序的出现而改变，在无法进行信源概率模型统计的条件下，非常适于使用自适应