《图像压缩的几种常见算法介绍》由会员分享，可在线阅读，更多相关《图像压缩的几种常见算法介绍（7页珍藏版）》请在金锄头文库上搜索。
1、图像压缩的几种常见算法介绍1 哈夫曼编码2 预测编码3 LZW 编码4 算术编码5 变换编码1 哈夫曼编码哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(Variable-Length Coding, VLC)的一种。Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作 Huffman 编码。以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中， “哈夫曼编码”是一种一致性编码法（又称熵编码法 ） ，用于数据的无损耗压缩。这一术语是指使
2、用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的） 。这种方法是由 David. A. Huffman 发展起来的。 例如，在英文中，字母 e 的出现概率很高，而 z 的出现概率最低。当利用哈夫曼编码对一篇英文进行压缩时，e 极有可能用 1 比特(bit)来表示，而 z 则可能花去 25 比特（不是 26） 。用普通的表示方法时，每个英文字母均占用一个字节（byte） ，即
3、8 位。二者相比，e 使用了一般编码的 1/8 的长度，z 则使用了 3 倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 哈夫曼压缩是无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。图 1 霍夫曼信源化简图 2 霍夫曼编码分配过程2 预测编码预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号预测下一个信号，然后对实际值和预测值的差（预测误差）
4、进行编码。如果预测比较准确，误差就会很小。在同等精度要求的条件下，就可以用比较少的比特进行编码，达到压缩数据的目的 3。 预测编码中典型的压缩方法有脉冲编码调制（Pulse Code Modulation, PCM） 、差分脉冲编码调制（Differential Pulse Code Modulation, DPCM） 、自适应差分脉冲编码调制（Adaptive Differential Pulse Code Modulation, ADPCM）等.它们较适合于声音、图像数据的压缩，因为这些数据由采样得到，相邻样值之间的差相差不会很大，可以用较少的位来表示。这里我们着重介绍 DPCM 编码。在
5、 PCM 系统中，原始的模拟信号经过采样后得到的每一个样值都被量化成为数字信号。为了压缩数据，可以不对每一样值都进行量化，而是预测下一样值，并量化实际值与预测值之间的差值，这就是 DPCM（Differential Pulse Code Modulation，差分脉冲编码调制） 。1952 年贝尔（Bell）实验室的 C. C. Cutler 取得了差分脉冲编码调制系统的专利，奠定了真正实用的预测编码系统的基础。其中编码器和解码器分别完成对预测误差量化值的熵编码和解码。 常用的线性预测，又称线性预测编码（Linear Predictive Coding, LPC） 。LPC 在语音处理中得到广
6、泛应用，并在此基础上发展了许多算法，典型的有：多脉冲线性预测编码（MPLPC） ，规则脉冲激励编码（ RPE） ，码激励线性预测（CELP） ，代数激励线性预测（ACELP） ，矢量和激励线性预测（ VSELP） ，QCELP（Qualcomm CELP，变速率 CELP） ，低延时码激励线性预测（LD-CELP ） ，共轭结构代数激励线性预测（CS-ACELP ） ，混合激励线性预测（ MELP） ，间隔同步更新码激励线性预测（PSI-CELP ） ，松弛码激励线性预测（ RCELP） ，残差激励线性预测（RELP） ，规则脉冲激励长时预测（ RPE-LTP）等。 在 DPCM 中， “1
7、位量化”的特殊情况称为增量调制（ 调制） 。为了能够正确恢复被压缩的信号，不仅在接收端有一个与发送端相同的预测器，而且其输入信号也要相同（都是 xk，而不是 xk） ，动作也与发送端的预测器环路（即发送端本地的反量化和解码部分）完全相同。 在图像信号中应用 DPCM 时，用作预测的像素和被预测的像素可以在同一行，也可以在不同行（同一帧） ，甚至在不同帧，分别称为一维预测、二维预测和三维预测。声音信号中的预测只是一维预测。DPCM 的优点是算法简单，容易硬件实现，缺点是对信道噪声很敏感，会产生误差扩散。即某一位码出错，对图像一维预测来说，将使该像素以后的同一行各个像素都产生误差；而对二维预测，该
8、码引起的误差还将扩散到以下的各行。这样，将使图像质量大大下降。同时，DPCM 的压缩率也比较低。随着变换编码的广泛应用，DPCM 的作用已很有限。图 3 DPCM 原理图3 LZW 编码LZW（Lempel Ziv Welch）压缩编码是一种先进的数据压缩技术，属于无损压缩编码，该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比，并且有较高的压缩和解压缩速度。(1)LZW 压缩算法的基本原理提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多
9、，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.(2)LZW 算法LZW 算法基于转换串表（字典）T，将输入字符串映射成定长（通常为 12位）的码字。在 12 位的 4096 种可能的代码中，256 个代表单字符，剩下 3840给出现的字符串。(3)LZW 压缩的特点LZW 码可以有效地利用字符出现频率冗余度进行压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。具体特点如下：l) LZW 压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF 格式的图像压缩，其平均压缩比在 2:1 以上，最
10、高压缩比可达到 3:1。2) 对于数据流中连续重复出现的字节和字串，LZW 压缩技术具有很高的压缩比。3) 除了用于图像数据处理以外，LZW 压缩技术还被用于文本程序等数据压缩方面。4) LZW 压缩技术有很多变体，例如常见的有 ARC、RKARC、PKZIP 等高效压缩程序。5) 对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。6) 对机器硬件条件要求不高，在 Intel 80386 的计算机上即可进行压缩和解压缩。4 算术编码算术压缩和霍夫曼编码压缩方法类似，只不过比霍夫曼编码更加有效。算术压缩适合于相同的重复序列组成的文件，算术压缩接近压缩理论的理论极限。这种
11、方法是将不同的序列映像到 0 至 1 之间的区域内，该区域表示成可变精度（位数）的二进制小数，越不常见的数据要求精度越高，这种方法比较复杂，因而不太常用。图 4 说明了算术编码的基本过程。这里，一个五符号序列（或称消息）ABBCD 是来自一个编码的四符号信源。在编码处理的开始，消息被假定为占据整个半开区间0,1)。这个区间开始时根据每个信源符号的出现概率分成四个区域。例如，符号 n对应子区间0,0.2)。因为 是消息中进行编码的1a第一个符号，消息的间隔开始被限制在0,0.2)的窄区间内。因此，在图 4 中，区间0,0.2)被扩展到图形的全高度，并且在区间的末端用这个狭窄域的值进行了标注。这个
12、窄域再根据初始信源符号的出现概率进行细分，而后接着处理下一个消息符号。用这种方式，符号 将子区间变窄为0.04,0.12) ， 进一步将2a3a子区间变窄为0.056,0.088)，如此进行下去。最后的消息符号必须被保留以作为特定的消息结束指示符，它将子区间变窄为0.08032,0.0816)。当然，在这个子区间内的任何数字（例如，0. 081）都可以被用来表示这个消息。图4 算术编码过程在图 4 中的算术编码消息中，使用三个十进制数字表示五符号消息。这样的转换得到每信源符号 3/5 或 0.6 个十进制数字，而与之相比的信源的熵为 0.58个十进制数字或 10 元单元，符号。当编码序列的长度
13、不断增加的时候，得到的算术编码也接近无噪声编码定理所设定的界限。实际上，有两个因素使编码的效能无法达到这个界限：(1)为了将一个消息同其他的消息分离开，增加了消息结束指示符，(2)使用的算法精度是有限的。算术编码的实际实现通过引入尺度策略和舍人策略解决第二个问题（Langdon 和 Risssanen） 。尺度策略在根据符号出现概率将子区间进行再次细分之前，将每个子区间重新归一化回0,1区间的范围内。舍入策略保证根据算法的有限精度进行的截尾不会影响根据正确的表示对子区间进行编码。5 变换编码图 5 所示为变换编码基本系统框图。进行编码时，首先将图像划分成规定大小的像块，一个 的像块由相邻的 行
14、，每行 个相邻的像素组成，划分nn像块的工作用存储器很易实现。然后将一个像块的 个样值同时由存储器取出，2进行正交变换。变换得到的 个变换系数经量化、编码后送人信道传输。接收2端则是一个恢复图像的逆过程，将变换系数经过反变换重新得到 个空间域的2n图像样值（但是含有量化误差） ，再将由此得到的解码像块拼接成重建图像。形成像块 编码量化逆变换恢复行结构光栅解码信道编码输入解码输出图 5 变换编码系统框图变换编码的性能和效率以及计算复杂性取决于多个因素，包括正交变换类型的选择、像块尺寸的选择、量化和比特分配的策略、统计编码的技巧以及是否采用和如何采用自适应技术等等。这里先讨论一下像块尺寸的选择，其
15、他因素将在后面陆续讨论。在大多数的应用场合，出于计算量和存储量的考虑以及图像信号本身相关半径的局限，图像的正交变换编码要分块进行，即首先要把图像分成一个个彼此不重叠的、尺寸较小的像块，然后每个像块单独进行变换编码。解码时再将反变换复原的各个像块重新拼成与原图同样大小的重建图像。像块的大小对变换编码的重建误差和计算复杂性有重要影响。一般计算复杂性和压缩比都随块尺寸的增大而增大。块的尺寸通常由以下两方面决定：相邻像块间的相关性（冗余度）随块尺寸的增大而下降，已经接近了一个可以接受的水平下限，换句话说，继续增大像块不再能明显提高压缩比；为计算方便，像块的尺寸应为 2 的整数次幂。n对于自然图像，像块
16、尺寸选 88 或 1616 是合适的。像块尺寸取得再大，需要的计算量和存储量增加很多，而压缩效率增加不多，图像质量改善也不大；而像块再小，压缩效率明显下降。在 H.261，H.263，MPEG-1，MPEG-2 等国际标准中都采用 88 的像块作 DCT。3 . 53 . 02 . 52 . 01 . 51 . 00 . 52 2 4 4 8 8 1 6 1 6 3 2 3 2像块尺寸均方误差D F TW H TD C T图 6 正交变换像块尺寸图 6 所示为像块尺寸对变换编码重建图像误差的影响。对于 8b-PCM 自然图像分别分割成 22，44 ， 88，1616，3232 大小的象块进行变换，在舍弃 75%的变换系数后，进行反变换重建图像，计算重建图像误差，进行比较的有DFT，WHT 和 DCT。由图可见，对于 WHT 和 DCT，当像块尺寸大于 88 后曲线走势变平；而对于 DFT，在这一范围内曲线快速下降。将曲线外推到更
