图像处理第10章其他图像编码方法

第10章

其他图像编码方法图像编码：常借助许多其他数学工具和其他图像技术，又有广泛的应用领域，多年来已经研究出许多特色的方法。有些基于特殊的理论和技术，有些则服务于特殊的领域。有对于频域技术的变换编码方法，有对于空域技术的预测编码方法和其它方法。在图像编码中，压缩率和失真是一对矛盾，对他们的折衷考虑也是许多编码方法的初衷。本章主要内容基于符号编码矢量量化准无损编码比较和评述第10章其他图像编码方法预测编码LZW编码10.1基于符号的编码基本思路：在文本图像编码中，由于许多文字位图会多次反复出现，所以可以考虑将每个文字看作一个基本符号或子图象，而将文本图象看作这些子图象的集合;需要建立一个符号字典，存储所有可能出现的符号（对每个符号赋一个码）;对图象的编码→确定每个符号的码字以及确定符号在图象中的空间位置;一幅图象可用一系列三元组来表示，即{(x1,y1,z1),(x2,y2,z2),……，}.（xi，yi）=位置，li=字典中位置标号编码示例：设在需要编码的图象中有一个6字母的序列“ABABAB”。每个字母由一个7×5的象素矩阵来表示。设将象素矩阵用位图来表示则每个字母，对应一幅含35个象素的位图。图10.1.1基于符号编码的示例图像表10.1.1基于编码的结果将每个字母看作一个基本符号，则符号字典中有两个符号“A”、“B”，分别为标号0和1，以图10.1.1为例，左上角为坐标起点，则字母序列可以用一个三元组（前两个表示符号左上角的坐标，第三个表示符号的坐标）序列表示。编码的压缩率：

原始图象共有7行39列，需7×39=273个比特编码后，原始图象被表示成一个三元组序列。设对每个位置用一个字节（8个比特）来表示，每个三元组需24个比特，现有6个符号，所以需要144个比特。另外，字典需要70个比特，所以编码结果需214个比特。此时压缩率约为1.2757。将此字母序列的长度增加一倍，则压缩率会增加到525/358=1.4665；对于分辨率较高的图像，压缩率也会较高。如上图情况，但将图像水平和垂直方向分辨率都增加1倍，则压缩率2.5755。如果对位图和三元数组也进行编码，则总压缩率还可提高。基于符号的解码非常简单，比编码要快得多。只要读出三元组序列中的各个标号，根据符号字典将对应符号的位图写在相应的坐标位置就可得到解码的图像。在国家标准JBIG2中，要编码的图像先被分割成重叠或不重叠的3个区域：文字区域、半调区域和一般其他区域。对前2个采用基于符号的编码方法。10.2LZW编码

LZW是一种信息保存型的编码方式，能消除或减少图象中的象素间冗余。LZW编码对信源输出的不同长度的符号序列分配固定长度的码字，且不需要有关符号出现概率的知识（与哈夫曼码等不同）。该编码方法是UNIX操作系统中的标准文件压缩方法，也用在GIF、TIFF、PDF中1、LZW编码过程在编码的开始阶段要构造一个对信源符号进行编码的码本（字典）。在编码器顺序地扫描排成串象素的灰度时，算法要确定字典中还没有出现过的灰度值序列的位置（如取下一个尚未用的位置），并建立（增加）一个新的码字。字典的尺寸是一个重要的编码器参数。如果太小，可用于匹配（放置）灰度值序列的位置会不够；如果太大，表达码字的比特数增加将影响对图象压缩的性能。LZW编码过程示例：图10.2.1一幅4×4的示例图像表10.2.1初始字典设使用一个9比特可容纳512个字的字典。先将字典前256个位置（码字）对应分配给灰度初始字典值，后256个位置暂时空着。第257个位置用于下一个（目前尚未）出现的灰度值序列。

编码的各个步骤和结果如书中表10.2.2所示。编码器从左向右、从上向下对每个输入像素扫描，作为编码输入，其灰度值如表中第2列所示。第3列的识别序列依此读取上一个编码输入（开始为空）。第4列的拼接序列是由第2列编码输入和第3列同行中的识别序列相拼接（识别序列在前，称为前缀串；编码输入在后，称为扩展字符）而成的。对每个拼接序列都在字典中搜索，根据搜索结果可分为两种情况：（1）如果找不到/尚没有（如表中步骤2里用“—”表示），就对字典下一个还没有使用的位置（如表中步骤2里从256开始）赋予这个拼接序列作为字典中的下一个新条目，并将同行的识别序列作为（第5列的）编码输出（如表中步骤2里是44）。（2）如果能找到/已有（如表中步骤3里用“+”表示），既不输出字码也不改变字典，而将这个拼接序列作为一个识别序列（如表中步骤4），并继续考虑下一个步骤的编码输入。如果拼接了下一个编码输入后在字典中搜索不到这个新的拼接序列（如步骤4里仍用“—”表示），那么就将此时的识别序列用字典中的相应的码字表示并作为编码输出，同时在字典中下一个还没有使用的位置（如步骤4里是257）加一个新条目，以放置这个新的拼接序列。根据搜索结果分别按上述两种情况进行，直到识别序列不再读到新的编码输入，则将识别序列已有的字符作为最后一个编码输出（如表中步骤17）。最后的编码输出序列为第5列的9个码字。在该例子中，共增加了8个新码字，在编码结束时，字典中共有264个码字，每个码字需9个比特来表示，用着264个码字对全图进行编码。原始图像共有16个像素，每个像素需用8个比特表示，全图共需128个比特来表示。第五列编码输出为9个码字，每个码字需要9个比特来表示，共81个比特，该例中压缩率为128/81≈1.58，或者说压缩比1.58:1

LZW编码的一个重要特性：前缀性，即如果一个码字在字典中，那么它的前缀串也已在字典里。LZW编码方法是一种自适应的压缩方法，但它对输入数据的适应比较慢，因为每次字典中的条目只增加一个，而且这个条目只比原有的条目增加了一个字符。LZW编码中字典的尺寸与要编码图像的尺寸和内容需要配合：在编码初期，由于字典中码字较少，字典对压缩效果的贡献也很少，此时主要进行字典的扩充；编码后期，如果字典的容量有限，图像太大时字典满了，编码效率也会受到限制。2、LZW解码过程LZW编码的特点是在编码的同时建立了一个码本。在LZW解码时也会建立一个同样的解码码本(编码器和解码器同步)。LZW解码的步骤和结果如表10.2.3所示。首先依次读取各个解码输入并判断该码字是否已在字典中（如第2列），然后构建拼接序列（如第3列），在构建字典（见最后两列）的同时依次进行解码（解码输出见第4列）。表10.2.3LZW解码步骤和结果具体解码时，先将第一个解码输入直接作为解码输出，然后从第2个解码输入开始，先考察其是否已在字典中，根据结果有两种情况：（1）如果尚不在字典中，根据编码过程和规则可知，一方面该字码应是上一个解码输入的扩展，所以其前缀串应与上一个解码输入相同；另一方面其扩展字符也应与当前解码输入中的（从左数）第一个字符相同。所以如果当前解码输入为一个新码字，则此时的拼接序列由上一个解码输入后接当前解码输入中的（从左数)第一个字符而构成。据此就可在字典中加入对应当前解码输入的新条目，同时也可得到对应解码输入码字的解码输出。（2）如果已在字典中，就将其直接作为解码输出；此时拼接序列也由上一个解码输入后接当前解码输入的第一个字符而构成，并将其放入字典新位置作为条目。10.3预测编码预测编码也能消除或减少图像的像素间冗余。基本思路是通过仅提取每个像素中的新信息并对他们编码来消除像素间的冗余。可分为无损预测编码和有损预测编码两种。这里一个像素的新信息定义为该像素的当前或现实值与预测值的差。10.3.1无损预测编码图10.3.1无损预测编码系统无损预测编码系统，主要由一个编码器和一个解码器组成，它们各有一个相同的预测器。在无损编码中，3个基本的步骤是预测、误差映射、编码。（首先根据某个像素的周边条件即上下文对该像素的值进行预测，然后计算真实值与预测值的差，将差值进行一定映射后得到映射值，最后对该映射值进行编码。）无损预测编码过程：输入序列：fn

(n=1,2,…)预测输出:（舍入成整数）预测误差：误差编码：在符号编码器中用变长码编码误差，解码器利用接收到的变长码字重建en解压序列：

m阶线性预测：1-D线性预测：m是线性预测器的阶；round是舍入函数；ai是预测系数一阶1-D线性预测：上式表示的预测器也称为前值预测器，所对应的预测编码方法也称为差值编码或前值编码。2-D预测编码中，预测是对图像从左向右、从上向下进行扫描时所扫描到的先前像素的函数，3-D时，预测基于上述像素和前一帧的像素。通过预测可消除相当多的像素间冗余。10.3.2有损预测编码（有损预测编码虽然解码图像有些失真但可获得较大的压缩率）1、有损预测编码系统在无损编码系统上加一个量化器。

图10.3.2有损预测编码系统输入序列：fn

(n=1,2,…)量化输出：预测输入：解压序列：编码误差：相同德尔塔调制（DM）是一种简单的有损预测编码方法。预测器：量化器：预测系数a≤1，常数c>0是一个常数。DM方法得到的码率是1比特/像素。图例10.3.2,10.3.3颗粒噪声：当C远大于输入中的最小变化时，如在n=0到n=3的相对平滑区，DM编码会产生颗粒噪声，即误差正负波动。斜率过载:当c远小于输入中的最大变化时，如在n=5到n=9的相对陡峭区间，DM编码会产生斜率过载，即(gn)变化跟不上fn的变换，有较大的正误差。对大多数图像来说，他们分别会导致图像中目标边缘发生模糊和整个图像产生纹状表面。这与所使用量化和预测方法及他们的相互作用有关，尽管有上面的相互作用，但预测器和量化器在设计中通常是独立的。2、最优预测最优预测器满足限制条件：最小化编码器预测误差：设量化误差可以忽略基于这些条件的预测编码方法称为差值脉冲码调制法（DPCM）设用一个四阶线性预测器来预测：给上式中的系数赋予不同的值，可得到不同的预测器。4个例子如下：g4给出的是一个自适应预测器，它通过计算图像的局部方向性来选择合适的预测值已达到保持图像边缘的目的。系数之和一般设为小于或等于1：这个限制是为了使预测器的输出落入允许的灰度值范围内和减少传输噪声的影响，传输噪声常使重建的图像上出现水平的条纹。减少DPCM解码器对输入噪声的敏感度是很重要的，因为在一定的条件下，只要有一个误差就能影响其后所有的输出而使输出不稳定。3、最优量化梯状函数：

重建电平

判别电平

量化函数

这个函数可完全由在第I象限的L/2个si和ti所描述。这些值给出的转折点确定了函数的不连续性并被称为量化器的判别电平和重建电平。

一个典型的量化函数

根据以上定义，量化器的设计就是要在给定优化准则和输入概率密度函数p(s)的条件选择最优的si和ti。优化准则可以是统计的或心理视觉的准则。如果用最小均方量化误差（即E｛s-ti｝2）作为准则，且p(s)是个偶函数，那么最小误差条件为：(10.3.25)si=-s-iti=-t-i

(10.3.27)

式（10.3.25）表明重建电平是给定判别区间的p(s)曲线下面积的重心，式（10.3.26）指出判别值正好为两个重建值的中指，式（10.3.27）可由q(s)是一个奇函数而得到。对任意L，满足上面三个式子的si和ti在均方误差意义下最优。(10.3.26)10.4矢量量化矢量量化（VQ）:将一个有多个分量的矢量映射为一个只有较少分量的矢量。原则上，空域和频域均可使用。矢量量化既可用于图像编码系统的量化模块中，也可用作一种独立的图像编码方法。他的理论基础是率失真定理。基本思路是把信源符号序列分组作为矢量看待进行编码。矢量量化考虑了以下两个因素：(1)对符号串的压缩比对单符号的压缩更能取得好的效果（矢量编码比标量编码好）；(2)对自然图象，空间上相邻的象素之间有较大的相关性。1、矢量量化流程编码过程如图10.4.1所示。在编码端，先将原始图象划分成小块，用矢量来表示这些小块并对矢量进行量化。构建一个码本对图象块矢量编码，在解码端，根据矢量码字的标号获得码矢量编好码后，将矢量码字的标号进行传输或存储。在解码端，解码器根据矢量码字的标号借助码本获得码矢量，利用码矢量重建出图像块并进而组成解码图像。图10.4.1矢量量化编解码流程2、矢量量化原理(1)将矢量空间分割为有限个子空间，它们覆盖整个矢量空间且互相不相交。常用Voronoi区域划分；(2)对每个子空间选择一个代表矢量（如质心），即码矢量，作为量化结果。图10.4.2Voronoi假设一幅图可分为若干区域，现已知这些区域的重心，对于任意两个重心点p和q，在它们之间都可以画一条对分线，这条对分线将图像分为两半，其中一半包含与p较近的点，另一半包含与q较近的点，如果以p为参考，对所有其他重心点都当做q如上进行，就可得到一个包含p的多边形，就是Voronoi多边形。一个完整的矢量量化过程可看作由编码器C和解码器D两个映射联合构成，可分别写为：其中：是标号集，每个标号对应一个码矢量yi

;Y是码本，包含N个码矢量。C计算输入矢量x与Y中各个码矢量yi间的失真（误差），然后输出一个由映射确定的yi的标号i。D根据接收到的标号i从与编码器相同的码本中找到yi，并用yi代替输入矢量x作为输出矢量y。码矢量标号i被编码成由二进制表示的码字对定长码，为表示N个码矢量标号需要每个码有B=log2N个比特。对L维矢量,比特率（每像素的比特数）为:3、最优码本设计最优的矢量量化应设计出能将平均失真降为最小的包含N个码矢量的码本。这里需要考虑两个条件：(1)给定需量化的矢量x，最优量化选择码矢量yi应能使x和yi间的失真最小(2)最优量化选择的码矢量yi应能使对应子空间内的平均失真最小，即yi为子空间的质心。两个条件表明，对给定的失真测度，确定码矢量和分割子区间是相关的。确定了码矢量，子区间的分割就确定了。反过来，分割了子区间，码矢量也就确定了。典型的码本设计方法是LBG算法（包括4个步骤），码矢量由最小化训练集X中的平均失真T得到：10.5准无损编码

压缩率和保真度常是一对矛盾。提高压缩率常使解码图象的失真加大，而要求高保真度又常使压缩率受到限制。准无损编码可看作对无损编码和有损编码的一种折中，期望能在信息损失相对有损编码不太大的情况下能达到比无损编码更高的压缩性能。

目前国际上以L∞范数来限定准无损编码的压缩率，即要使任意一个象素在压缩前后其灰度差的绝对值都不大于某一预先给定的容限值。1、准无损压缩算法分类（1）基于预测编码的方法对误差量化，即将误差e量化为，然后对进行误差映射和熵编码。例子：（2）基于可逆变换的方法变换部分是无损的，但预处理过程及其逆过程中允许出现误差（但不超过设定的容限值）(3)有损加准无损的方法先对图像进行有损压缩，然后对差值部分进行准无损压缩。2、JPEG-LSJPEG-LS是基于上下文模型的空域压缩算法，对量化误差为0的象素采用游程编码，游程编码过程由游程检测及游程长度编码两步完成。流程图如下：

上下文模型对当前象素进行分类，用以选择编码方式及控制编码各环节。图10.5.2所示为当前编码象素的上下文位置关系，进入游程编码的上下文条件是：图10.5.2JPEG-LS算法中的上下文位置关系3、准无损CALIC算法基于上下文的自适应图像编码（CALIC）是一种典型的无损/准无损压缩方法，也称基于上下文分类的自适应预测熵编码，其基本流程如如图10.5.3所示。各像素按光栅扫描的顺序依次处理。图10.5.3CALIC基本算法流程图预测上下文：水平方向的dh和垂直方向的dv；误差修正上下文w、熵编码上下文s。10.6比较和评述10.6.1不同方法特性的比较●变换编码方法可以较好地保持图象的主观质量；●预测编码方法的特点是用较小的计算代价就可取得较高的压缩率；●矢量量化方法需要使用比较复杂的编码器；●哈夫曼编码把固定数目的符号转变成可变长度的码字；●算术编码把可变数目的符号转变成可变长度的码字；●LZW编码则把可变数目的符号转变成固定长度的码字。

现在我们来讨论熵编码中对图像解码时要考虑的两个特性：即时性和唯一性（1）解码的即时性指对任意一个有限长的码符号串，可以对每个码字分别解码（2）解码的唯一性也称单义性，指对任意一个有限长的码符号串，只有一种分解成其各个码符号的方法（只能以一种方式解）。

即时码一定是唯一可解码，但唯一可解码不一定是即时码（如用算术编码得到的是唯一可解码但它并不是即时码）。不是唯一可解码肯定也不是即时码，但不是即时码并不能确定该码是否为唯一可解码。10.6.2其他编码方法1