1、第第4章章 多媒体数据压缩与编码技术多媒体数据压缩与编码技术本章重点：本章重点：编码模型编码模型 编码压缩方法分类编码压缩方法分类 统计编码的基本原理统计编码的基本原理 预测编码的基本原理预测编码的基本原理 变换编码的基本原理变换编码的基本原理 视频编码的基本原理视频编码的基本原理第第4 4章章 多媒体数据压缩与编码技术多媒体数据压缩与编码技术4.1 4.1 编码压缩的必要性与可能性编码压缩的必要性与可能性 4.2 4.2 编码模型编码模型 4.3 4.3 编码压缩方法分类编码压缩方法分类 4.4 4.4 统计编码统计编码 4.5 4.5 预测编码预测编码 4.6 4.6 变换编码变换编码 4
2、.7 4.7 其他编码其他编码 4.8 4.8 视频编码视频编码 4.9 4.9 本章小结本章小结4.1 4.1 编码压缩的必要性与可能性编码压缩的必要性与可能性4.1.1 4.1.1 编码压缩的必要性编码压缩的必要性4.1.2 4.1.2 编码压缩的可能性编码压缩的可能性 4.1.1 4.1.1 编码压缩的必要性编码压缩的必要性n众所周知，图像量化所需数据量大。图像和视众所周知，图像量化所需数据量大。图像和视频的庞大数据对计算机的处理速度、存储容量频的庞大数据对计算机的处理速度、存储容量都提出过高的要求。因此必须进行数据量压缩。都提出过高的要求。因此必须进行数据量压缩。n从传送的角度来看，在
3、信道带宽、通信链路容从传送的角度来看，在信道带宽、通信链路容 量一定的前提下，采用编码压缩技术，减少量一定的前提下，采用编码压缩技术，减少传输数据量，是提高通信速度的重要手段。因传输数据量，是提高通信速度的重要手段。因此，更要求数据量压缩。此，更要求数据量压缩。4.1.2 4.1.2 编码压缩的可能性编码压缩的可能性 众所周知，视频由一帧一帧的图像组成，众所周知，视频由一帧一帧的图像组成，而图像的各像素之间，无论是在行方向还是在而图像的各像素之间，无论是在行方向还是在列方向，都存在着一定的相关性，即冗余度。列方向，都存在着一定的相关性，即冗余度。应用某种编码方法提取或减少这些冗余度，便应用某种
4、编码方法提取或减少这些冗余度，便可以达到压缩数据的目的。可以达到压缩数据的目的。常见的静态图像数据冗余包括：常见的静态图像数据冗余包括：n1.1.空间冗余空间冗余 这是静态图像存在的最主要的一种数据冗这是静态图像存在的最主要的一种数据冗余。一幅图像记录了画面上可见景物的颜色。余。一幅图像记录了画面上可见景物的颜色。同一景物表面上各采样点的颜色之间往往存在同一景物表面上各采样点的颜色之间往往存在着空间连贯性，从而产生了空间冗余。着空间连贯性，从而产生了空间冗余。4.1.2 4.1.2 编码压缩的可能性编码压缩的可能性n2.2.时间冗余时间冗余 在视频的相邻帧间，往往包含相同的背景在视频的相邻帧间
5、，往往包含相同的背景和移动物体，因此，后一帧数据与前一帧数据和移动物体，因此，后一帧数据与前一帧数据有许多共同的地方，即在时间上存在大量的冗有许多共同的地方，即在时间上存在大量的冗余。余。n3.3.结构冗余结构冗余 在有些图像的纹理区，图像的像素值存在在有些图像的纹理区，图像的像素值存在着明显的分布模式。例如，方格状的地板图案着明显的分布模式。例如，方格状的地板图案等。我们称这种冗余为结构冗余。等。我们称这种冗余为结构冗余。n4.4.知识冗余知识冗余 有些图像的理解与某些知识有相当大的相有些图像的理解与某些知识有相当大的相关性。例如，人脸的图像有固定的结构。这类关性。例如，人脸的图像有固定的结
6、构。这类4.1.2 4.1.2 编码压缩的可能性编码压缩的可能性 规律性的结构可由先验知识和背景知识得到，规律性的结构可由先验知识和背景知识得到，我们称此类冗余为知识冗余。我们称此类冗余为知识冗余。n5.5.视觉冗余视觉冗余 事实表明，人类的视觉系统对图像场的敏事实表明，人类的视觉系统对图像场的敏感性是非均匀的和非线性的。然而，在记录原感性是非均匀的和非线性的。然而，在记录原始图像数据时，通常假定视觉系统是线性的和始图像数据时，通常假定视觉系统是线性的和均匀的，对视觉敏感和不敏感的部分同等对待，均匀的，对视觉敏感和不敏感的部分同等对待，从而产生了比理想编码更多的数据，这就是视从而产生了比理想编
7、码更多的数据，这就是视觉冗余。觉冗余。n6.6.图像区域的相同性冗余图像区域的相同性冗余 是指在图像中的两个或多个区域所对应的所有是指在图像中的两个或多个区域所对应的所有4.1.2 4.1.2 编码压缩的可能性编码压缩的可能性 像素值相同或相近，从而产生的数据重复性存像素值相同或相近，从而产生的数据重复性存储，这就是图像区域的相似性冗余。储，这就是图像区域的相似性冗余。n7.7.纹理的统计冗余纹理的统计冗余 有些图像纹理尽管不严格服从某有些图像纹理尽管不严格服从某分布规分布规律，但是它在统计的意义上服从该规律。利用律，但是它在统计的意义上服从该规律。利用这种性质也可以减少表示图像的数据量，所以
8、这种性质也可以减少表示图像的数据量，所以我们称之为纹理的统计冗余。我们称之为纹理的统计冗余。4.2 4.2 编码模型编码模型 n4.2.1 4.2.1 信源编码器和信源解码器信源编码器和信源解码器n4.2.2 4.2.2 信道编码器和解码器信道编码器和解码器4.2 4.2 编码模型编码模型 如图如图4.14.1所示，一个压缩系统包括两个不所示，一个压缩系统包括两个不同的结构块：一个编码器和一个解码器。图像同的结构块：一个编码器和一个解码器。图像f f（x x，y y）输入到编码器中，这个编码器可以）输入到编码器中，这个编码器可以根据输入数据生成一组符号。在通过信道进行根据输入数据生成一组符号。
9、在通过信道进行传输之后，将经过编码的表达符号送入解码器，传输之后，将经过编码的表达符号送入解码器，经过重构后，就生成了输出图像。经过重构后，就生成了输出图像。4.2.1 4.2.1 信源编码器和信源解码器信源编码器和信源解码器 信源编码器的任务是减少或消除输入图像信源编码器的任务是减少或消除输入图像中的冗余。编码的框图如图下图中的冗余。编码的框图如图下图(a)(a)所示。所示。从原理来看主要分为三个阶段，第一阶段从原理来看主要分为三个阶段，第一阶段将输入数据转换为可以减少输入图像中像素间将输入数据转换为可以减少输入图像中像素间冗余的数据的集合。第二阶段设法去除原图象冗余的数据的集合。第二阶段设
10、法去除原图象信号的相关性，例如对电视信号就可以去掉帧信号的相关性，例如对电视信号就可以去掉帧内各种相关，还可以去除帧间相关。这样有利内各种相关，还可以去除帧间相关。这样有利 4.2.1 4.2.1 信源编码器和信源解码器信源编码器和信源解码器 于编码压缩。第三阶段就是找一种更近于熵，于编码压缩。第三阶段就是找一种更近于熵，又利于计算机处理的编码方式。又利于计算机处理的编码方式。下图下图(b)中显示的信源解码器仅包含两部中显示的信源解码器仅包含两部分：一个符号解码器和一个反向转换器。这些分：一个符号解码器和一个反向转换器。这些模块的运行次序与编码器的符号编码器和转换模块的运行次序与编码器的符号编
11、码器和转换模块的操作次序相反。模块的操作次序相反。4.2.2 信道编码器和解码器信道编码器和解码器 当信道带有噪声或易于出现错误时，信道编当信道带有噪声或易于出现错误时，信道编码器和解码器就在整个译码解码处理中扮演了码器和解码器就在整个译码解码处理中扮演了重要的角色。重要的角色。最有用的最有用的种信道编码技术是由种信道编码技术是由R Rw wHammingHamming提出的。该技术基于这样的思提出的。该技术基于这样的思想，即向被编码数据中加入足够的位数以确保想，即向被编码数据中加入足够的位数以确保可用的码字间变化的位数最小。例如，利用可用的码字间变化的位数最小。例如，利用HammingHam
12、ming码将码将3 3位冗余码加到位冗余码加到4 4位字上，使得任位字上，使得任意两个有效码字间的距离为意两个有效码字间的距离为3 3，则所有的一位，则所有的一位错误都可以检测出来并得到纠止。与错误都可以检测出来并得到纠止。与4 4位二进位二进制数制数b3b2b1b0b3b2b1b0相联系的相联系的7 7位位Hamming(7Hamming(7，4)4)码字码字 4.2.2 信道编码器和解码器信道编码器和解码器h1h2h5h6h7h1h2h5h6h7是：是：这里表示异或运算。这里表示异或运算。h1h1，h2h2和和h4h4位分别是位分别是位字段位字段b3b2b0b3b2b0，b3b1b0b3b
13、1b0和和b2b1b0b2b1b0的偶校验位。的偶校验位。4.2.2 信道编码器和解码器信道编码器和解码器 为了将汉明（为了将汉明（HammingHamming）编码结果进行解）编码结果进行解码，信道解码器必须为先前设立的偶校验的各码，信道解码器必须为先前设立的偶校验的各个位字段进行奇校验并检查译码值。一位错误个位字段进行奇校验并检查译码值。一位错误由一个非零奇偶校验字由一个非零奇偶校验字c4c2c1c4c2c1给出，这里，给出，这里，4.3 编码压缩方法分类编码压缩方法分类 数据压缩的目标是去除各种冗余。根据压数据压缩的目标是去除各种冗余。根据压缩后是否有信息丢失，多媒体数据压缩技术可缩后是
14、否有信息丢失，多媒体数据压缩技术可分为无损压缩技术和有损压缩技术两类。数据分为无损压缩技术和有损压缩技术两类。数据压缩编码分类如图压缩编码分类如图4.34.3所示。所示。常见的无损压缩技术有：常见的无损压缩技术有：n霍夫曼编码霍夫曼编码n算术编码算术编码n行程编码行程编码n词典编码词典编码 4.3 编码压缩方法分类编码压缩方法分类 常用的一些有损压缩技术包括：常用的一些有损压缩技术包括：n预测编码预测编码n变换编码变换编码n基于模型编码基于模型编码n分形编码分形编码n其他编码其他编码4.3 编码压缩方法分类编码压缩方法分类4.4 统计编码统计编码 统计编码属无损编码，它是根据消息出现统计编码属
15、无损编码，它是根据消息出现概率的分布特性而进行的压缩编码。统计编码概率的分布特性而进行的压缩编码。统计编码又可分为定长码和变长码。又可分为定长码和变长码。常用的统计编码有常用的统计编码有Huffman编码、行程编码和算术编码三种。编码、行程编码和算术编码三种。4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码 4.4.2 4.4.2 香农香农-费诺编码费诺编码4.4.3 4.4.3 算术编码算术编码4.4.4 4.4.4 游程编码（游程编码（RLCRLC）4.4.5 LZW4.4.5 LZW编码编码4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffma
16、n）编码）编码 在一幅图像中，有些图像数据出现的频率在一幅图像中，有些图像数据出现的频率高，有些图像数据出现的频率低。如果对那些高，有些图像数据出现的频率低。如果对那些出现频率高的数据用较少的位数来表示，而出出现频率高的数据用较少的位数来表示，而出现频率低的数据用较多的位数来表示，这样从现频率低的数据用较多的位数来表示，这样从总的效果来看还是节省了存储空间。这种编码总的效果来看还是节省了存储空间。这种编码思想首先由香农（思想首先由香农（ShannonShannon）提出，哈夫曼后）提出，哈夫曼后来对它提出了一种改进的编码方法，用这种方来对它提出了一种改进的编码方法，用这种方法得到的编码称为法得
17、到的编码称为HuffmanHuffman编码，编码，HuffmanHuffman编码编码是一种变长编码。是一种变长编码。4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码n1.理论基础理论基础 一个事件集合一个事件集合x1,x2,，xn处于一个基处于一个基本概率空间，其相应概率为本概率空间，其相应概率为p1,p2,，pn，且且p1+p2+pn=1。每一个信息的信息量。每一个信息的信息量为为 （4-3）定义在概率空间中每定义在概率空间中每事件的概率不相等事件的概率不相等时的平均信息量为信息熵，则信息熵时的平均信息量为信息熵，则信息熵H可采用可采用如下公式计算：如下公
18、式计算：（4-4）()log()kakI xp11()()lognnkkkkakkkHE I xp I xpp4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码【例例4.14.1】信息熵的计算。信息熵的计算。设设8 8个随机变量具有同等概率为个随机变量具有同等概率为1/81/8，则熵：，则熵：即计算出即计算出H=3H=3比特。比特。n2.Huffman编码编码 Huffman编码是编码是1952年由年由Huffman提出提出的一种编码方法。它在变长编码方法中是最佳的一种编码方法。它在变长编码方法中是最佳的。的。82111()log388jH Xbit 4.4.1
19、4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码设信源设信源A A的信源空间为：的信源空间为：其中其中 ，现用现用r个码符号的码符号集个码符号的码符号集 对信源对信源A中的每个符号中的每个符号 （i1，2，N）进行编码。具体编码的方法是：）进行编码。具体编码的方法是：(1)(1)把信源符号按其出现概率的大小顺序排列起把信源符号按其出现概率的大小顺序排列起来；来；(2)(2)把最末两个具有最小概率的元素之概率加起把最末两个具有最小概率的元素之概率加起来；来；1212:():()()()NNAaaaA PP AP aP aP a1()1NiiPa12:,rX xxxia4.4.
20、1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码 (3)(3)把该概率之和同其余概率由大到小排把该概率之和同其余概率由大到小排队，然队，然 后再把两个最小概率加起来，再重后再把两个最小概率加起来，再重新排队；新排队；重复步骤重复步骤,直到最后只剩下两个概率为止。直到最后只剩下两个概率为止。在上述工作完毕之后，从最后两个概率开在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的赋予始逐步向前进行编码。对于概率大的赋予0 0，小的赋予小的赋予1 1。4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码4.4.1 4.4.1 哈夫曼
21、（哈夫曼（HuffmanHuffman）编码）编码 经霍夫曼编码后，平均码长为：经霍夫曼编码后，平均码长为：=0.410.3020.14+0.065+0.045=2.20（bit）61()iiiBPwn4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编码n3.Huffman3.Huffman编码的几点说明编码的几点说明 （1 1）HuffmanHuffman编码是最佳的，虽然构造出编码是最佳的，虽然构造出来的码不唯一，但其平均码长却相同，所以不来的码不唯一，但其平均码长却相同，所以不影响编码效率和数据压缩性能。影响编码效率和数据压缩性能。（2 2）由于）由于Huff
22、manHuffman码的码长参差不齐，因码的码长参差不齐，因此，存在一个输入、输出速率匹配问题。解决此，存在一个输入、输出速率匹配问题。解决的办法是设置一定容量的缓冲存储器。的办法是设置一定容量的缓冲存储器。（3 3）HuffmanHuffman码在存储或传输过程中，如码在存储或传输过程中，如果出现误码，可能会引起误码的连续传播，果出现误码，可能会引起误码的连续传播，1bit1bit的误码可能把一大串码字全部破坏，因此，的误码可能把一大串码字全部破坏，因此，限制了限制了HuffmanHuffman码的使用。码的使用。4.4.1 4.4.1 哈夫曼（哈夫曼（HuffmanHuffman）编码）编
23、码 （4 4）HuffmanHuffman编码对不同信源其编码效率编码对不同信源其编码效率也不尽相同。当信源概率是也不尽相同。当信源概率是2 2的负次幂时，的负次幂时，HuffmanHuffman码的编码效率达到码的编码效率达到100100；当信源概率；当信源概率相等时，其编码效率最低。这表明在使用相等时，其编码效率最低。这表明在使用HuffmanHuffman方法编码时，只有当信源概率分布很方法编码时，只有当信源概率分布很不均匀时，不均匀时，HuffmanHuffman码才会收到显著的效果。码才会收到显著的效果。（5 5）HuffmanHuffman编码应用时，均需要与其他编码应用时，均需要
24、与其他编码结合起来使用，才能进一步提高数据压缩编码结合起来使用，才能进一步提高数据压缩比。例如，在静态图像处理标准比。例如，在静态图像处理标准JPEGJPEG中，先对中，先对图像像素进行图像像素进行DCTDCT变换、量化、变换、量化、Z Z形扫描、游程形扫描、游程编码后，再进行霍夫曼编码。编码后，再进行霍夫曼编码。4.4.24.4.2香农香农-费诺编码费诺编码 具体编码方法如下：具体编码方法如下：（1 1）把）把 按概率由大到小、从上到下排成按概率由大到小、从上到下排成一列，然后把一列，然后把 分成两组分成两组 ，并，并使这两组符号概率和相等或几乎相等，即：使这两组符号概率和相等或几乎相等，即
25、：（2）把两组分别按）把两组分别按0，1赋值赋值,例如将第一组赋值例如将第一组赋值为为0，则第二组赋值为，则第二组赋值为1。然后分组、赋值，不。然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是所赋的值依次排列起来就是香农香农-费诺编码。费诺编码。1,.,nxx1,.,nxx1,.,kxxnkxx,.,111()()knijijkP xP x4.4.24.4.2香农香农-费诺编码费诺编码 以前面的数据为例，香农以前面的数据为例，香农-编码费诺如图编码费诺如图4.54.5所所示。示。4.4.3 4.4.3 算术编码算术编码
26、理论上，用理论上，用HuffmanHuffman方法对源数据流进行编方法对源数据流进行编码可达到最佳编码效果。但由于计算机中存储、码可达到最佳编码效果。但由于计算机中存储、处理的最小单位是处理的最小单位是“位位”，因此，在一些情况，因此，在一些情况下，实际压缩比与理论压缩比的极限相去甚远。下，实际压缩比与理论压缩比的极限相去甚远。算术编码把要压缩处理的整段数据映射算术编码把要压缩处理的整段数据映射到到段实数半开区间段实数半开区间00，11内的某一区段，构内的某一区段，构造出小于造出小于1 1且大于或等于且大于或等于0 0的数值。这个数值是的数值。这个数值是输入数据流的唯输入数据流的唯可译代码。
27、可译代码。4.4.3 4.4.3 算术编码算术编码 下面通过一个例子来说明算术编码的方法。下面通过一个例子来说明算术编码的方法。对一个对一个5 5符号信源符号信源A Aa1a1，a2a2，a3a3，a2a2，a4a4，各字符出现的概率和设定的取值范围如下表各字符出现的概率和设定的取值范围如下表4.24.2：4.4.3 4.4.3 算术编码算术编码 为讨论方便起见，假定有为讨论方便起见，假定有 式中式中NsNs为新子区间的起始位置；为新子区间的起始位置；FsFs为前子为前子区间的起始位置，区间的起始位置，ClCl当前符号的区间左端；当前符号的区间左端；NeNe为新子区间的结束位置；为新子区间的结
28、束位置；FeFe为前子区间的结为前子区间的结束位置；束位置；CrCr当前符号的区间右端；当前符号的区间右端；L L为前子区为前子区间的长度。间的长度。按上述区间的定义，最终结果如表按上述区间的定义，最终结果如表4.34.3：LCFNlss*eerN F C L 4.4.3 4.4.3 算术编码算术编码 给定事件序列的算术编码步骤如下：给定事件序列的算术编码步骤如下：（1 1）编码器在开始时将）编码器在开始时将“当前间隔当前间隔”L L，H H 设置为设置为00，1 1）。）。（2 2）对每一事件，编码器按步骤（）对每一事件，编码器按步骤（a a）和（）和（b b）进行处理进行处理4.4.3 4
29、.4.3 算术编码算术编码 （a a）编码器将）编码器将“当前间隔当前间隔”分为子间隔，分为子间隔，每一个事件一个。每一个事件一个。（b b）一个子间隔的大小与下一个将出现的）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新下一个确切发生的事件相对应，并使它成为新的的“当前间隔当前间隔”。最后输出的最后输出的“当前间隔当前间隔”的下边界就是该的下边界就是该给定事件序列的算术编码。给定事件序列的算术编码。4.4.3 4.4.3 算术编码算术编码 在算术编码中有几个问题需要注意：在算术编码中有几
30、个问题需要注意：n由于实际的计算机的精度不可能无限长，一个由于实际的计算机的精度不可能无限长，一个明显的问题是运算中出现溢出，但多数机器都明显的问题是运算中出现溢出，但多数机器都有有1616、3232或者或者6464位的精度，因此这个问题可使位的精度，因此这个问题可使用比例缩放方法解决。用比例缩放方法解决。n算术编码器对整个消息只产生一个码字，这个算术编码器对整个消息只产生一个码字，这个码字是在间隔码字是在间隔00，11中的一个实数，因此译码中的一个实数，因此译码器在接收到表示这个实数的所有位之前不能进器在接收到表示这个实数的所有位之前不能进行译码。行译码。n算术编码也是一种对错误很敏感的编码
31、方法，算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译如果有一位发生错误就会导致整个消息译错。错。4.4.4 4.4.4 游程编码（游程编码（RLCRLC）游程编码是一种利用空间冗余度压缩图像游程编码是一种利用空间冗余度压缩图像的方法，相对比较简单，也属于统计编码类。的方法，相对比较简单，也属于统计编码类。设图像中的某一行或某一块像素经采样或设图像中的某一行或某一块像素经采样或经某种方法变换后的系数为经某种方法变换后的系数为 ，如图，如图4.74.7所示。某一行或某一块内像素值所示。某一行或某一块内像素值 可分为可分为k k段，长度段，长度 为的连续串，每个串具有相
32、同的值，为的连续串，每个串具有相同的值，那么，该图像的某一行或某一块可由下面偶对那么，该图像的某一行或某一块可由下面偶对 来表示：来表示：，其中，其中 为每个串内为每个串内的代表值，的代表值，为串的长度。为串的长度。12(,)Mx xxixil(,)iig l,1ik 1 21 12 2(,)(,),(,),(,)Mk kx xxg l g lg ligil4.4.4 4.4.4 游程编码（游程编码（RLCRLC）4.4.4 4.4.4 游程编码（游程编码（RLCRLC）串长串长l li i就是游程长度（就是游程长度（Run-lengthRun-length），简），简写为写为RLRL，即由字
33、符或采样值或灰度值构成的数，即由字符或采样值或灰度值构成的数据流中各个字符等重复出现而形成的字符串的据流中各个字符等重复出现而形成的字符串的长度。基本结构如图长度。基本结构如图4.84.8所示。所示。4.4.4 4.4.4 游程编码（游程编码（RLCRLC）游程编码分为定长游程编码和变长游程编游程编码分为定长游程编码和变长游程编码两类。定长游程编码是指码两类。定长游程编码是指 RLRL位数是固定的。位数是固定的。变长游程编码是指变长游程编码是指 RLRL位数是不固定的。位数是不固定的。游程编码一般不直接应用于多灰度图像，游程编码一般不直接应用于多灰度图像，但比较适合于二值图像的编码。例如黑白传
34、真但比较适合于二值图像的编码。例如黑白传真图像的编码等。为了达到较好的压缩效果，有图像的编码等。为了达到较好的压缩效果，有时游程编码和其他一些编码方法混合使用。时游程编码和其他一些编码方法混合使用。定义游程和游程长度后，就可以把任何二定义游程和游程长度后，就可以把任何二元序列变换成游程长度的序列，简称游程序列。元序列变换成游程长度的序列，简称游程序列。这一变换是可逆的，一一对应的。这一变换是可逆的，一一对应的。4.4.5 LZW4.4.5 LZW编码编码 LZWLZW压缩编码是一种无损压缩编码。压缩编码是一种无损压缩编码。LZWLZW的的基本思想是用符号代替一串字符，这一串字符基本思想是用符号
35、代替一串字符，这一串字符可以是有意义的，也可以是无意义的。在编码可以是有意义的，也可以是无意义的。在编码中仅仅把字符串看成是一个号码，而不去管它中仅仅把字符串看成是一个号码，而不去管它代表什么意思。代表什么意思。n1.编码算法编码算法 LZWLZW编码是围绕称为词典的转换表来完成编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀（的。这张转换表用来存放称为前缀（PrefixPrefix）的字符序列，并且为每个表项分配一个码字的字符序列，并且为每个表项分配一个码字（Code wordCode word），或者叫做序号。），或者叫做序号。4.4.5 LZW4.4.5 LZW编码编码LZ
36、WLZW编码算法的具体执行步骤如下：编码算法的具体执行步骤如下：步骤步骤1 1：开始时的词典包含所有可能的根（：开始时的词典包含所有可能的根（RootRoot），而当前前缀），而当前前缀P P是空的；是空的；步骤步骤2 2：当前字符（：当前字符（C C）：）：=字符流中的下一个字符；字符流中的下一个字符；步骤步骤3 3：判断缀：判断缀-符串符串P+CP+C是否在词典中是否在词典中 如果如果“是是”：P P：=P+C=P+C，即用，即用C C扩展扩展P P）；）；如果如果“否否”把代表当前前缀把代表当前前缀P P的码字输出到码字流；的码字输出到码字流；把缀把缀-符串符串P+CP+C添加到词典；添
37、加到词典；令令P P：=C=C，即现在的，即现在的P P仅包含一个字符仅包含一个字符C C；步骤步骤4 4：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译 如果如果“是是”，就返回到步骤，就返回到步骤2 2；如果如果“否否”把代表当前前缀把代表当前前缀P P的码字输出到码字流；的码字输出到码字流；结束。结束。LZWLZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字。个码字。4.4.5 LZW4.4.5 LZW编码编码【例例4.44.4】256256个字符的码字的伪码形式表示：个字符的码字的伪码形式
38、表示：Dictionaryj all n single-character，j1，2，n jn+1 Prefix read first Character in Charstream while（C next Character）!=NULL）Begin If Prefix.C is in Dictionary Prefix Prefix.C else Codestream cW for Prefix DictionaryjPrefix.C jn+1 Prefix C end Codestream cW for Prefix 4.4.5 LZW4.4.5 LZW编码编码n2.2.译码算法译码算
39、法 LZWLZW译码算法中还用到另外两个术语：译码算法中还用到另外两个术语：当前码字（当前码字（Current code wordCurrent code word）：指当前正）：指当前正在处理的码字，用在处理的码字，用cWcW表示，用表示，用string.cWstring.cW表示表示当前缀当前缀-符串；先前码字（符串；先前码字（Previous code Previous code wordword）：指先于当前码字的码字，用）：指先于当前码字的码字，用pWpW表示，表示，用用string.pWstring.pW表示先前缀表示先前缀-符串。符串。LZWLZW译码算法开始时，译码词典与编码词
40、译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根典相同，它包含所有可能的前缀根（roots）。）。4.4.5 LZW4.4.5 LZW编码编码LZW译码算法的具体执行步骤如下：译码算法的具体执行步骤如下：步骤步骤1：在开始译码时词典包含所有可能的前缀根（：在开始译码时词典包含所有可能的前缀根（Root）；）；步骤步骤2：cW：=码字流中的第一个码字；码字流中的第一个码字；步骤步骤3：输出当前缀：输出当前缀-符串符串string.cW到码字流；到码字流；步骤步骤4：先前码字：先前码字pW：=当前码字当前码字cW；步骤步骤5：当前码字：当前码字cW：=码字流中的下一个码字；码字流中的
41、下一个码字；步骤步骤6：判断先前缀：判断先前缀-符串符串string.pW是否在词典中是否在词典中 如果如果“是是”：把先前缀把先前缀-符串符串string.pW输出到字符流；输出到字符流；当前前缀当前前缀P：=先前缀先前缀-符串符串string.pW；当前字符当前字符C：=当前前缀当前前缀-符串符串string.cW的第一个字符；的第一个字符；把缀把缀-符串符串P+C添加到词典；添加到词典；如果如果“否否”：当前前缀当前前缀P：=先前缀先前缀-符串符串string.pW；当前字符当前字符C：=当前缀当前缀-符串符串string.cW的第一个字符；的第一个字符；输出缀输出缀-符串符串P+C到字
42、符流，然后把它添加到词典中。到字符流，然后把它添加到词典中。步骤步骤7：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译 如果如果“是是”，就返回到步骤，就返回到步骤4；如果如果“否否”，结束。，结束。4.4.5 LZW4.4.5 LZW编码编码 【例例4.64.6】编码字符串如表编码字符串如表4.64.6所示，编码过程如表所示，编码过程如表4.74.7所示。现说明如下：所示。现说明如下：“步骤步骤”栏表示编码步骤；栏表示编码步骤；“位位置置”栏表示在输入数据中的当前位置；栏表示在输入数据中的当前位置；“词典词典”栏表栏表示添加到词典中的缀示添加到词典中的缀-符串，它的索引在括号中；
43、符串，它的索引在括号中；“输输出出”栏表示码字输出。栏表示码字输出。4.4.5 LZW4.4.5 LZW编码编码 表表4.84.8解释了译码过程。每个译码步骤译码器读一解释了译码过程。每个译码步骤译码器读一个码字，输出相应的缀个码字，输出相应的缀-符串，并把它添加到词典中。符串，并把它添加到词典中。例如，在步骤例如，在步骤4 4中，先前码字（中，先前码字（2 2）存储在先前码字）存储在先前码字（pWpW）中，当前码）中，当前码字（字（cW）是（）是（4），），当前缀当前缀-符串符串 4.4.5 LZW4.4.5 LZW编码编码 string.cWstring.cW是输出（是输出（“A B”A
44、B”），先前缀），先前缀-符串符串string.pWstring.pW （BB）是用当前缀）是用当前缀-符串符串string.cWstring.cW （AA）的第一个字符，其结果（的第一个字符，其结果（B AB A）添加到词典中，它添加到词典中，它的索引号是（的索引号是（6 6）。）。4.5 4.5 预测编码预测编码 n4.5.1 4.5.1 概述概述 n4.5.2 4.5.2 无损预测编码无损预测编码n4.5.3 4.5.3 有损预测编码有损预测编码4.5.1 4.5.1 概述概述n预测编码是根据离散信号之间存在着一定的相预测编码是根据离散信号之间存在着一定的相关性，利用前面的一个或多个信号
45、对下一信号关性，利用前面的一个或多个信号对下一信号进行预测，然后对实际值和预测值的差（预测进行预测，然后对实际值和预测值的差（预测误差）进行编码。误差）进行编码。n预测编码中典型的压缩方法有脉冲编码调制预测编码中典型的压缩方法有脉冲编码调制（PCMPCM，Pulse Code ModulationPulse Code Modulation）、差分脉冲）、差分脉冲编码调制（编码调制（DPCMDPCM，Differential Pulse Code Differential Pulse Code ModulationModulation）、自适应差分脉冲编码调制）、自适应差分脉冲编码调制（ADPC
46、MADPCM，Adaptive Differential Pulse Adaptive Differential Pulse Code ModulationCode Modulation）等。）等。n预测编码可分为无损预测编码和有损预测编码。预测编码可分为无损预测编码和有损预测编码。4.5.2 4.5.2 无损预测编码无损预测编码 无损预测编码器的工作原理图和预测原理无损预测编码器的工作原理图和预测原理如图如图4.94.9和图和图4.104.10所示。其中所示。其中f（i,j）的预测值的预测值为为 ，将，将 的差值进行无损熵编码，熵的差值进行无损熵编码，熵编码器可采用霍夫曼编码或算术编码。图编
47、码器可采用霍夫曼编码或算术编码。图4.10给出了像素（给出了像素（i，j）的预测图，图中给出了（）的预测图，图中给出了（i，j）的三个相邻像素，）的三个相邻像素，由先前三点预测，定由先前三点预测，定义为：义为：其中其中a a1,1,a a2,2,a a3 3称预测系数，都是待定参数。如果预测器中预称预测系数，都是待定参数。如果预测器中预测系数是固定不变的常数，称之为线性预测。测系数是固定不变的常数，称之为线性预测。(,)f i j(,)(,)f i jf i j(,)f i j),1()1,1()1,(),(321jifajifajifajif4.5.2 4.5.2 无损预测编码无损预测编码图
48、4.9 无损预测编码器工作原理压缩源图像预测器熵编码器编码表4.5.2 4.5.2 无损预测编码无损预测编码 预测误差计算公式如下：预测误差计算公式如下：设设a=fa=f（i,j-1i,j-1），），b=fb=f（i-1,ji-1,j）,c=f,c=f（i-i-1,j-11,j-1），），的预测方法如图的预测方法如图4.114.11所示，可有所示，可有8 8种选择方法。种选择方法。(,)(,)(,)ei jf i jf i j123(,)(,1)(1,1)(1,)f i jaf i jaf ijaf ij (,)f i j4.5.2 4.5.2 无损预测编码无损预测编码4.5.2 4.5.2
49、无损预测编码无损预测编码 【例例4.74.7】设有一幅图像，设有一幅图像，f f（i-1,j-1i-1,j-1），），f f（i-1,ji-1,j），），f f（i,j-1i,j-1），），f f（i,ji,j）的灰度值分别为）的灰度值分别为253,252,253,255253,252,253,255，用图，用图4.114.11第四种选择方法预测第四种选择方法预测 f f（i,ji,j）的灰度值，并计算预测误差。的灰度值，并计算预测误差。解：解：=a+b-ca+b-c=f=f（i,j-1i,j-1）+f+f（i-1,ji-1,j）-f-f（i-1,j-1i-1,j-1）=253+252-252
50、=253=253+252-252=253 预测误差预测误差 =255-253=2=255-253=2 (,)f i j(,)(,)(,)e i jf i jf i j4.5.3 4.5.3 有损预测编码有损预测编码 如果不是直接对差值信号进行编码，而是如果不是直接对差值信号进行编码，而是对差值信号进行量化后再进行编码就称之为有对差值信号进行量化后再进行编码就称之为有损预测编码。有损预测方法有多种，其中差分损预测编码。有损预测方法有多种，其中差分脉冲编码调制（脉冲编码调制（Differential Pulse Code Differential Pulse Code ModulationModu
