几种图像压缩算法PPT学习课件.ppt

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