几种图像压缩算法

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,补充：几种图像压缩算法,1.图像数据压缩方法的分类,数据压缩的任务在不影响或少影响图像质量的前提下，尽量设法减少图像数据中的数据量。其首要任务是设法去掉各种冗余的数据。,数据压缩实际是一个编码的过程，即将原始数据进行编码压缩。数据解压缩是数据压缩的逆过程，即将经过压缩的数据还原成原始数据。因此数据压缩方法也称编码方法。,评价压缩方法的优劣主要从以下3个方面来衡量。,（1）压缩比：压缩比指原始图像经A/D转换后未经压缩所产生的数据量与经压缩所产生的数据量之比。,（2）图像质量：还原出来的图像质量比原始图像有多大失真，一般采用人的视觉效果和信噪比两个方法。前者是通过人在两米内观察所作的评价，后者通过仪器测量。,（3）实现难度：即实现压缩及还原算法的难易程度，亦即完成压缩所需要的时间与空间开销或硬件实现的复杂性。,压缩的方法主要有以下几种（见图3.3）。,无损编码可以完全恢复原始图像而不引入失真，它利用数据的统计特性来进行数据压缩，解压缩后的还原图像与原始图像完全一致。有损编码不能完全恢复原始数据，而是利用人的视觉特性使解压缩后的图像和原来一样。把上述方法结合起来即为混合方法。,下面介绍几种常用的压缩方法。,2 霍夫曼编码,霍夫曼编码是无损编码的一种，是一种基于统计特性的可变字长的编码方法。属于无损编码的还有行程编码、算术编码等。下面来看霍夫曼编码。,设被编码的符号如下。,s,1，,s,2，,s,3，,s,n,它们出现的概率分别为：,p,1，,p,2，,p,3，,p,n,假设采用不等字长编码，每个符号的码长分别为：,m,1，,m,2，,m,3，,m,n,数学上可以证明，符号序列,s,i 的任何一种编码方案，其平均码长必定大于或等于,H,。也就是说，,H,是该符号序列的理想最小平均码长。平均码长越接近,H,，我们说该编码方案越好。,数学上还可以证明，在可变字长编码中，对于出现概率大的符号编码成短字长的编码，对于概率小的符号，编以较长的字长编码。如果码字长严格按照所对应符号的出现概率的大小逆序列排列，则平均码长一定小于其他任何符号顺序方式，即这是一种最接近于熵值的“最佳编码”。,霍夫曼编码是实现上述最佳编码的一种算法。下面看一个示例。,大部分数字信息的编码都是采用定长编码。意即采用相同的位数对数据进行编码。如常用的ASCII就是定长编码，它用7位二进制数来表示每一个字符。但是实际上在文章中每个字符出现的概率并不相等。我们现在假设有,a,，,b,，,c,，,d,，,e,5个字符。其出现概率分别为0.12,0.40,0.15,0.08，0.25。用以下方法来求得其霍夫曼编码。,将5个字符按其概率大小排序，然后把最小的两项的概率值相加，归并成新的一项。然后再选最小的两项合并，一直重复作到只剩最后一项为止。本例实现过程参见图3.4。,下面再来构造霍夫曼编码树。这是一棵二叉树，我们从图3.5中的右方开始向左取值，根结点概率为1.0，以下左分枝取概率小的项，右分枝取概率大的项。对于归并项，按此规则一直分解到最右方为止。如图3.5所示为构造好的霍夫曼编码树。,如图3.5所示，我们给每个左分枝标以0，给每个右分枝标以1，则从根结点至每个叶结点的路径即为该叶结点代表字符的编码。如图3.5右方所示。,本例中熵的值为2.09，编码的平均码长为2.15，非常接近。,霍夫曼编码的优点是简单易行，缺点是解码时必须知道所使用的码表，这给存储和通信带来不便。另一个缺点是它依赖于原始数据的概率，这在实际应用中受到许多限制。,编码实例(16色bmp数据)：,第一行：,24 24 24 30 60 40 09 224646,第二行：,64 65 67 88 88 88 88 90 78,00 00：表示该行图像数据已结束,00 01：表示整个图像结束,00 02：用来转义后面两个字节，即表示其后的两个字节分别表示下一个像素从当前位置开始的水平与垂直位移,00 N：表示从当前位置起，图像数据存在连续N个不同的值（存放于N/2个字节中）,3.行程长度编码,5个,行程编码原理,在给定的图像数据中寻找连续重复的数值，然后用两个字符值取代这些连续值,“aaabbbbccccddd”=”3a4b4c3d”,处理包含大量重复信息时可以得到很好的压缩效率，但在连续重复数据少时效果差,PCX图像文件的RLE压缩算法,4 预 测 编 码,预测编码用于图像编码时与声音的压缩编码很类似，它也是根据过去已编码的像素（也称为参考像素）来预测当前的像素值（称为预测值），然后对当前的像素值与预测值之差进行编码，这就是差分编码（DPCM）。这种编码是利用图像本身的相关性及视觉的差值灵敏度特性，差值大时，可以粗量化。图像编码用地较多的是二维预测，如图3.6所示。,LZW压缩算法,LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。,LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如print 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串print，在解压缩时，串表可以根据压缩数据重新生成。,压缩算法的简单示例,对原始数据ABCCAABCDDAACCDB进行LZW压缩,原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示为:45A4CDDAA5DB,JPEG编码,二、JPEG算法的主要计算步骤 JPEG压缩编码算法的主要计算步骤如下：,（1）正向离散余弦变换（FDCT）。,（2）量化（Quantization）。,（3）Z字形编码（Zigzag Scan）。,（4）使用差分脉冲编码调制（Differential Pulse Code Modulation，DPCM)对直流系数(DC)进行编码。,（5）使用行程长度编码（Run-Length Encoding，RLE）对交流系数（AC）进行编码。,（6）熵编码（Entropy Eoding）。,1.,正向离散余弦变换,（1）对每个单独的彩色图像分量，把整个分量图像分成若干个88的图像块，如图所示，并作为两维离散余弦变换DCT的输入。通过DCT变换，把能量集中在少数几个系数上。,（2）DCT变换使用下式计算：它的逆变换使用下式计算：上面两式中，C(u)，C(v)=(2)-1/2，当u,v=0；C(u)，C(v)=1，其他。f(i,j)经DCT变换之后，F(0，0)是直流系数，其他为交流系数。,（3）在计算两维的DCT变换时，可使用下面的计算式把两维的DCT变换变成一维的DCT变换：,2、量化,量化是对经过FDCT变换后的频率系数进行量化。量化的目的是减小非“0”系数的幅度以及增加“0”值系数的数目。量化是图像质量下降的最主要原因。对于有损压缩算法，JPEG算法使用如下图所示的均匀量化器进行量化，量化步距是按照系数所在的位置和每种颜色分量的色调值来确定。因为人眼对亮度信号比对色差信号更敏感，因此使用了两种量化表：亮度量化值和色差量化值。此外，由于人眼对低频分量的图像比对高频分量的图像更敏感，因此图中的左上角的量化步距要比右下角的量化步距小。下面2个表中的数值对CCIR 601标准电视图像已经是最佳的。如果不使用这两种表，你也可以把自己的量化表替换它们。亮度量化值表和色度量化值表,3、Z字形编排,量化后的系数要重新编排，目的是为了增加连续的“0”系数的个数，就是“0”的游程长度，方法是按照Z字形的式样编排，如下图所示。这样就把一个88的矩阵变成一个164的矢量，频率较低的系数放在矢量的顶部。量化DCT系数序号 0 1 5 6 14 15 27 25 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63,4、直流系数的编码,88图像块经过DCT变换之后得到的DC直流系数有两个特点，一是系数的数值比较大，二是相邻88图像块的DC系数值变化不大。根据这个特点，JPEG算法使用了差分脉冲调制编码（DPCM）技术，对相邻图像块之间量化DC系数的差值（Delta）进行编码。DeltaDC(0,0)k-DC(0,0)k-1,5、交流系数的编码,量化AC系数的特点是164矢量中包含有许多“0”系数，并且许多“0”是连续的，因此使用非常简单和直观的游程长度编码(RLE)对它们进行编码。JPEG使用了1个字节的高4位来表示连续“0”的个数，而使用它的低4位来表示编码下一个非“0”系数所需要的位数，跟在它后面的是量化AC系数的数值。,6、熵编码,使用熵编码还可以对DPCM编码后的直流DC系数和RLE编码后的交流AC系数作进一步的压缩。在JPEG有损压缩算法中，使用霍夫曼编码器来减少熵。使用霍夫曼编码器的理由是可以使用很简单的查表（Lookup Table）方法进行编码。压缩数据符号时，霍夫曼编码器对出现频度比较高的符号分配比较短的代码，而对出现频度较低的符号分配比较长的代码。这种可变长度的霍夫曼码表可以事先进行定义。,7、组成位数据流,JPEG编码的最后一个步骤是把各种标记代码和编码后的图像数据组成一帧一帧的数据，这样做的目的是为了便于传输、存储和译码器进行译码，这样的组织的数据通常称为JPEG位数据流（JPEG bitstream）。,