多媒体数据压缩编码技术.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012-9-16,#,第,3,章 多媒体数据压缩编码技术,本章概要,多媒体数据压缩编码的重要性和分类,统计编码,预测编码,变换编码,4,1,2,3,多媒体数据压缩编码的国际标准,5,1.,多媒体数据压缩编码的重要性和分类,信息时代的重要特征是信息的数字化，数字化了的信息带来了“信息爆炸”。,数字计算机面临的是数值、文字、语言、音乐、图形、动画、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大非常惊人。,多媒体数据存在大量的冗余，通过去除那些冗余数据可以使原始数据极大地减少，因此，多媒体数据压缩编码技术就是研究如何利用多媒体数据的冗余性来减少数据量的方法。,1.1,重要性,一页印在,B5,纸上的文件，若以中等分辨率（,300dpi,约,12,像素点,/mm,）扫描采样，其数据量约,6.61MB/,页，一片,650MB,的,CD-ROM,可存放,98,页。,双通道立体声激光唱盘,(CD-DA),，采样频率为,44.1kHz,，采样精度,16,位,/,样本，一个,650MB,的,CD-ROM,可存储约一个小时的音乐。,数字音频磁带,(DAT),，采样频率,48kHz,，采样精度,16,位,/,样本，一个,650M,的,CD-ROM,，可存约,2,小时的节目。,1.1,重要性,源输入格式,(source input formation,，,SIF),，,NTSC,制、色彩、,4:4:4,采样：,-,每帧数据量,3522403=253KB,-,每秒数据量,(,位率,)25330=7.603MB/s,-,一片,CD-ROM,节目时间,(6507.706)/60=1.42,分,/,片,国际无线电咨询委员会,(international consultative committee for radio,ICCR),格式，,PAL,制、,4:4:4,采样：,-,每帧数据量,7205763=1.24MB,-,每秒数据量,1.2425=31.3MB/s,-,一片,CD-ROM,节目时间,65031.1=20.9,秒,/,片,1.1,重要性,这样大的数据量，无疑给存储器的存储容量、通信干线的信道传输率以及计算机的速度都增加了极大的压力。,解决这一问题，单纯用扩大存储器容量、增加通信干线的传输率的办法是不现实的。数据压缩技术是个行之有效的方法。,通过数据压缩手段把信息数据量压下来，以压缩形式存储和传输，既紧缩节约了存储空间，又提高了通信干线的传输效率，同时使计算机实时处理音频、视频信息，以保证播放出高质量的视频、音频节目成为可能。,1.2,可能性,空间冗余,-,同一景物表面上各采样点的颜色之间往往存在着空间连贯性，但是基于离散像素采样来表示物体颜色的方式通常没有利用景物表面颜色的这种空间连贯性，从而产生了,空间冗余,。,-,可以通过改变物体表面颜色的像素存储方式来利用空间连贯性，达到减少数据量的目的。,1.2,可能性,时间冗余,-,这是序列图像（电视图像、运动图像）表示中经常包含的冗余。,-,序列图像一般为位于一时间轴区间内的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为,时间冗余,。,1.2,可能性,结构冗余,-,在有些图像的纹理区，图像的像素值存在着明显的分布模式，例如，方格状的地板图案等。我们称此为,结构冗余,。,-,已知分布模式，可以通过某一过程生成图像。,1.2,可能性,知识冗余,-,有些图像的理解与某些知识有相当大的相关性。例如，人脸的图像有固定的结构。这类规律性的结构可由先验知识和背景知识得到，我们称此类冗余为,知识冗余,。,-,根据已有的知识，对某些图像中所包含的物体，我们可以构造其基本模型，并创建对应各种特征的图像库，进而图像的存储只需要保存一些特征参数，从而可以大大减少数据量。知识冗余是模型编码主要利用的特性。,1.2,可能性,视觉冗余,-,事实表明，人类的视觉系统对图像场的敏感性是非均匀和非线性的。然而，在记录原始的图像数据时，通常假定视觉系统是线性和均匀的，对视觉敏感和不敏感的部分同等对待，从而产生了比理想编码（即把视觉敏感和不敏感的部分区分开来编码）更多的数据，这就是,视觉冗余,。,-,通过大量实验，发现以下视觉的非均匀特征。,视觉系统对图像的亮度和色彩度的敏感性相差很大；,随着亮度的增加，视觉系统对量化误差的敏感度降低；,人眼的视觉系统在图像的边缘和非边缘区域分开来处理；,人类的视觉系统总是把视网膜上的图像分解成若干个空间有向的频率通道后再进一步处理。,1.2,可能性,图像区域的相同性冗余,-,它是指在图像中的两个或多个区域所对应的所有像素值相同或相近，从而产生的数据重复性存储，这就是,图像区域的相似性冗余,。,-,在以上的情况下，记录了一个区域中各像素的颜色值，则与其相同或相近的其他区域就不在记录其中各像素的值。,-,向量量化方法就是针对这种冗余性的图像压缩编码方法。,1.2,可能性,纹理的统计冗余,-,有些图像纹理尽管不严格服从某一分布规律，但是它在统计的意义上服从该规律。利用这种性质也可以减少表示图像的数据量，所以我们称之为,纹理的统计冗余,。,1.3,多媒体数据压缩方法的分类,根据质量有无损失可分为：有损失编码和无损失编码。,按照骑作用域在空间域或频率域上分为：空间方法、变换方法和混合方法。,根据是否自适应分为自适应性编码和非自适应性编码。一般来说，每一个编码方法都有其相应的自适应方法。,1.3,多媒体数据压缩方法的分类,1.3,多媒体数据压缩方法的分类,脉冲编码调制,-,数据编码方式之一。主要过程是将话音、图像等模拟信号每隔一定时间进行取样，使其离散化，同时将抽样值按分层单位四舍五人取整量化，同时将抽样值按一组二进制码来表示抽样脉冲的幅值。,预测编码,-,编码器记录的不是样本的真实值，而是它对预测值的差。这种编码方式称为差值脉冲编码调制（,DPCM,）。预测值由欲编码图像信号的过去信息决定。通常采用线性预测。由于空间相关性，真实值与预测值的差值的变化范围远远小于真实值的变化范围，因而可以彩较少的位数来表示。另外，若利用人的视觉特性对差值进行非均匀量化，则会获得更高的压缩比。,1.3,多媒体数据压缩方法的分类,变换编码,-,其主要思想是利用图像块内像素值之间的相关性，把图像变换到一组新的基上，使得能量集中在少数变换系数上，通过存储这些系数从而达到压缩图像的目的。在变换编码中，由于对整幅图进行变换的计算量太大，所以一般把原始图像分成许多个矩形区域子图像独立进行变换。如,DCT,变换。,统计编码,-,最常用的统计编码是,Huffman,编码。其基本原理是根据信源的频率进行编码。对于出现频率大的符号用较少的位数来表示，而对于出现频率小的符号用较多位数来表示。这种方法的压缩率取决符号的分布频率，分布越集中压缩效果越好。,-,还有一种算术编码方法，也是统计编码。算术编码适合于信源符号概率比较接近的情况。在,JPEG,的扩展系统中，用算术编码代替,Huffman,编码。,1.3,多媒体数据压缩方法的分类,混合编码,-,一般是将预测编码和变换编码合并使用。比如在一个方向上进行变换，在另一个方向上用,DPCM,对变换系数进行预测编码。或是对动态图像二维变换加上时间方向上的,DPCM,预测。,2.,统计编码,数据压缩技术的理论基础是信息论。根据信息论的原理，可以找到最佳数据压缩编码方法，数据压缩的理论极限是,信息熵,。,如果要求在编码过程中不丢失信息量，即要求保存信息熵，这种信息保持编码又叫做熵保存编码，或者,熵编码,。熵编码是无失真数据压缩，用这种编码结果经解码后可无失真的恢复出原图像。,当考虑到人眼对失真不易觉察的生理特征时，有些图像编码不严格要求熵保存，信息可允许部分失真以换取高的数据压缩比，这种编码是有失真压缩，通常运动图像的数据压缩是有失真编码，这就是著名的,香农（,Shannon,）率失真理论,，即信息编码率与允许的失真关系的理论。,根据信源符号出现概率的分布特性而进行的压缩编码。熵编码是无失真数据压缩编码，在编码过程中不丢失信息量，熵编码是建立在随机过程的统计特性基础上的。,在信息论中，熵被用来衡量一个随机变量出现的期望值。它代表了在被接收之前，信号传输过程中损失的信息量，又被称为信息熵。信息熵也称信源熵、平均自信息量。,2.1,统计编码原理,信息编码器模型,其中：,X,是消息集，由几个信号单元,x,j,构成,(,j,=1,2,n),Z,是输出集，由几个码字,z,j,构成,(,j,=1,2,n),，,z,j,与,x,j,一一对应。,A,m,是符号集，由,m,个码元,a,i,构成,(i=1,2,m),，符号集中的码元组成输出码字。,编码器,信源（消息集）,编码输出集（接收端）,符号集,当信源发出某个随机事件（消息）,x,j,后，接收端收到一个相应的码字,z,j,，从数量上说，所收到的码字中包含多大的信息量，或者说多少有用的信息呢？,2.1,统计编码原理,信息是用不确定性的量度定义的。一个消息的可能性越小，其信息越多；而消息的可能性越大，则其信息越少。,在数学上，所传输的消息是其出现概率的单调下降函数,。,所谓,信息量,是指从,N,个相等可能事件中选出一个时间所需要信息量或含量，也就是在辨识,N,个事件中特定的一个事件的过程中需要提问“是或否”的最少次数,。,2.1,统计编码原理,2.1,统计编码原理,例子：要从,164,个数中选定某一个数，不论回答是或否都消去了半数的可能事件，这样继续问下去，只要提问,6,次这类问题，就能从,64,个数中选定某一个。这是因为每提问一次都会得到,1,比特的信息量。,因此，在,64,个数中选定某一个数所需要的信息量是,设从,N,个数中选定任一个数,x,的概率为,p,(x),，假定选定任意一个数的概率都相等，即,p,(x)=1/N,，因此信息量为,2.1,统计编码原理,信息论定义了一种度量信息量的方法：,其中，,P(x,j,),是信源,X,发出,x,j,的先验概率。,I(x,j,),的含义是，信源,X,发出,x,j,这个消息（随机事件）后，接收端收到信息量的量度；或者说接收端可能收到信源发出的是哪一个随机事件的不确定性。,当随机事件,x,j,发生的先验概率,P(x,j,),大时，,I(x,j,),小，那么这件事发生的可能性大，不确定性小，信息量少。反之，人们没有估计到的事件，一旦发生，,I(x,j,),大，包含的信息量很大，即所谓爆炸性新闻。,I(x,j,),称,x,j,发生后的自信息量，它也是一个随机变量。,2.1,统计编码原理,信源,X,发出的,x,j,(j=1,2,n),，共,n,个随机事件的自信息统计平均（求数学期望），即,H(X),在信息论中称为信源,X,的“熵”，它的含义是信源,X,发出任意个随机变量的平均信息量。,-,当,取,2,时，,H(X),的单位为比特,(bit),；,-,当,取,e,时，,H(X),的单位为奈特,(Net);,-,图像编码中，,取,2.,2.1,统计编码原理,熵的范围,在编码中用熵值衡量是否为最佳编码。若以 表示编码器输出码字的平均长度，则,当 有冗余，不是最佳；,当 不可能；,当 最佳编码（稍大于 ）,熵值是平均码长 的下限,。,2.1,统计编码原理,熵的计算。,例：,1.,若,n=8,，所有随机事件等概率发生，则求熵。,2.,若,n=8,，其中某一事件必然发生，其他事件不发生，求熵。,解：,1.,p,(x,1,)=,p,(x,2,)=,p,(x,3,)=,p,(x,4,)=,p,(x,5,)=,p,(x,6,)=,p,(x,7,)=,p,(x,8,)=1/8,2.,p,(x,1,)=,1,p,(x,2,)=,p,(x,3,)=,p,(x,4,)=,p,(x,5,)=,p,(x,6,)=,p,(x,7,)=,p,(x,8,)=0,等概率事件的熵最大,。,2.2,霍夫曼,(Huffman),编码,最佳编码定理,定理,：在变字长码中，对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。,2.2,霍夫曼,(Huffman),编码,Huffman,编码方法问世于,1952,年，广泛应用于各种数据压缩技术中，且仍不失为熵编码中的最佳编码方法。,Huffman,编码方法就是利用了最佳编码定理，把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。,2.2,霍夫曼,(Huffman),编码,Huffman,编码的具体步骤如下：,概率统计（如对一幅图像，或,m,幅同种类型图像作灰度信号统计），得到,n,个不同概率的信息符号；,将,n,个信源信息符号的,n,个概率，按概率大小排列；,将,n,个概率中，最后两个小概率相加，这是概率个数减为,n-1,个；,将,n-1,个概率，按大小重新排序；,重复,3,，将新排序后的最后两个小概率再相加，相加和与其余概率再排序；,如此反复重复,n-2,次，得到只剩两个概率序列；,以二进制码元,(0,1),赋值，构成霍夫曼码字。,编码结束。,2.2,霍夫曼,(Huffman),编码,Huffman,编码举例,X,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,P(X),0.20,0.19,0.18,0.17,0.15,0.10,0.005,0.005,信源,X,的符号及其概率：,编码过程：,x,1,0.20,x,2,0.19,x,3,0.18,x,4,0.17,x,5,0.15,x,6,0.10,x,7,0.005,x,8,0.005,1,0,0.01,1,0,0.11,1,0,0.26,1,0,0.35,1,0,0.39,1,0,0.61,1,0,1,编码结果：,01,00,111,110,101,1001,10001,10000,符号,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,码字,(W,i,),w,1,01,w,2,00,w,3,111,w,4,110,w,5,101,w,6,1001,w,7,10001,w,8,10000,码长,2,2,3,3,3,4,5,5,编码结果：,平均码长：,熵：,2.2,霍夫曼,(Huffman),编码,例：设一组信源符号为,X1,，,X2,，,X3,，,X4,，,X5,，,X6,，,X7,，,X8,，这些符号出现的概率分别为,0.40,，,0.18,，,0.10,，,0.10,，,0.07,，,0.06,，,0.05,，,0.04,，求它们的,Huffman,编码。,上述编码的平均码子长度：,R=,=0.401+0.183+0.103+0.104+0.074+0.064+0.055+0.045=2.61,0.04,X8,0.06,0.05,X7,0.09,0.07,0.06,X6,0.10,0.10,0.09,0.07,X5,0.18,0.13,0.10,0.10,0.10,X4,0.23,0.19,0.18,0.13,0.10,0.10,X3,0.4,0.37,0.23,0.19,0.18,0.18,0.18,X2,1.0,0.6,0.40,0.40,0.40,0.40,0.40,0.40,X1,概率,信息符号,第七步,第六步,第五步,第四步,第三步,第二步,第一步,输入,输入,0,1,0,1,0,1,0,1,0,1,0,1,0,1,码字 码长,1 1,001 3,011 3,0000 4,0100 4,0101 4,00010 5,00011 5,2.2,霍夫曼,(Huffman),编码,如果上表中，首次对缩减信源最后两个概率最小的符号用码符号标记为,0,1,时，也可反过来标记为,1,0,，则可得到另一组霍夫曼码。,上述过程的等价编码树：,w,7,w,8,0,1,w,6,0,1,0,1,w,5,w,3,w,4,0,1,0,1,w,1,w,2,0,1,0,1,注意：,霍夫曼编码的特点,：,形成的编码不是惟一的，但他们的平均码长是相同的，不存在本质上的区别。,对不同信源的编码效率不同。当信源概率为,2,的负幂次方时，效率最高。当信源概率相等时，效率最低。,编码后，形成一个,Huffman,编码表，解码时必须参照该表，该表在存储和传输时都会占有一定的空间和信道。,2.2,霍夫曼,(Huffman),编码,2.3,行程编码,由字符（或信号采样值）构成的数据流中相同的字符（或字符串）会连续重复出现，连续出现的次数称为,游程长度,RL(Run Length),。,行程编码,(Run Length Coding,RLC),将重复的数据值序列（或称为“流”）用重复次数和单个数据值来代替。行程编码又称“运行长度编码”或“游程编码”。,2.3,行程编码,在实际应用中，有多种形式的,RLC,编码。,使用指示符的行程编码,例如：字符串“,RTSAAAAEEEEEQQBBB,”其行程编码字符串为“*,1R,*,1T,*,1S,*,4A,*,5E,*,2Q,*,3B,”,从编码中看出，一个,RLC,编码串的长度为,3,，所以，只有当,RL3,时数据压缩才有意义。,不使用指示符的行程编码,不使用指示符的行程编码仅用出现的字符和其连续重复的次数表示这串字符。,例如：字符串“,8888888555555222224440000000009,”其行程编码序列为“,875625430991,”,压缩指示符,重复的字符,重复次数,2.3,行程编码,在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，使用行程编码，可大幅度减少数据量。,行程编码分为定长行程编码和不定长行程编码两种类型。,行程编码的压缩比与数据流中字符重复出现的概率及长度有关。在数据中字符重复出现次数相同的情况下，重复字符串的平均长度越长，压缩比就越高；在重复字串的平均长度相同的情况下，重复字符出现的次数越多，压缩比也越高。,2.4,算术编码,算术编码,(Arithmetic Coding,AC),是,20,世纪,60,年代由,P.Elias,提出的，其基本原理是将编码的消息表示成实数,01,之间的一个间隔，取间隔中的一个数表示消息。消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位数就越多。,2.4,算术编码,算术编码的具体步骤如下：,编码器在开始时将“当前间隔”设置为,0,，,1),；,根据信源符号的概率，将“当前间隔”分为子间隔，每个符号一个子间隔，子间隔大小为信源符号的概率；,根据信源符号序列，编码器选择子间隔对应于下一个符号，并使它成为新的“当前间隔”，编码将“当前间隔”分为子间隔，子间隔的大小与下一个符号的概率成比例；,重复步骤,3,，直到符号序列的最后一位，消息的编码输出可以是最后一个间隔中的任意数。,编码结束。,例：采用固定模式符号概率分配如下：,字符,:a e i o u,概率,:0.2 0.3 0.1 0.2 0.2,范围,:,0,0.2),0.2,0.5),0.5,0.6),0.6,0.8),0.8,1.0),编码数据串为,eai,编码结果用,0.23,0.236),表示数据串,eai,。,字符,:a e i o u,概率,:0.2 0.3 0.1 0.2 0.2,范围,:,0,0.2),0.2,0.5),0.5,0.6),0.6,0.8),0.8,1.0),1,e 0.5,ea 0.26,0.236,0.8,0.6,0.5,0.2,0,u,o,i,e,a,u,o,i,e,a,u,o,i,e,a,u,o,i,e,a,0.2,0.2,0.23,eai,具体编码过程：,初始,high=1,low=0,range=high-low,每个字符编码后新的,low1,和,high1,按以下公式计算：,Low1=low+range rangelow,high1=low+range rangehigh,（,1,）对,e,进行编码，此时,rangelow=0.2,，,rangehigh=0.5,，因此：,Low1=0+1 0.2=0.2,High1=0+1 0.5=0.5,Range=high1 low1=0.3,此时，得到,e,的范围为,0.2,，,0.5),（,2,）再对,a,编码，使用新的生成范围,0.2,，,0.5),，,a,的,rangelow=0,，,rangehigh=0.2,，因此：,Low1=0.2+0.3 0=0.2,High1=0.2+0.3 0.2=0.26,Range=high1 low1=0.06,此时，得到的范围为,0.2,，,0.26),（,3,）,最后，对,i,编码，使用新范围,0.2,，,0.26),，,i,的,rangelow=0.5,，,rangehigh=0.6,，因此：,Low1=0.2+0.06 0.5=0.23,High1=0.2+0.06 0.6=0.236,此时，得到最终的范围为,0.23,，,0.236),，我们用这个范围来表示数据串,eai,。,例：如上例题中，如果解码器知道最后范围是,0.23,0.236),，它马上可解得一个字符为,e,，然后依次得到唯一解,a,、,i,，最终得到,eai,。,具体解码过程如下：,（,1,）由最终的范围,0.23,0.236),，对照题目可以看到此范围包含在,e,的范围内，所以可以解得一个字符,e,。,（,2,）根据公式，,e,的,low=0.2,，,high=0.5,，,range=0.5 0.2=0.3,，解码第二个字符,rangelow,，,rangehigh,）,0.23=0.2+0.3 rangelow,则,rangelow=0.1,0.236=0.2+0.3 rangehigh,则,rangehigh=0.12,由范围,0.1,，,0.12,）可知是字符,a,。,（,3,）,此时范围为,0.1,，,0.12,），根据公式，,a,的,low=0,，,high=0.2,，,range=0.2 0=0.2,，解码第三个字符,rangelow,，,rangehigh,）,0.1=0+0.2 rangelow,则,rangelow=0.5,0.12=0+0.2 rangehigh,则,rangehigh=0.6,由范围,0.5,，,0.6,）可知是字符,i,。,至此，全部解码可知范围,0.23,，,0.236,）表示字符串,eai,。,2.4,算术编码,算术编码举例,信源符号，概率和初始编码间隔：,符号,A,B,C,D,概率,0.1,0.4,0.2,0.3,初始编码间隔,0,0.1),0.1,0.5),0.5,0.7),0.7,1,如果二进制消息序列的输入为：,CADACDB,则编码过程：,信源符号,11,10,01,00,0.5,C,输入,0,1,A,0.7,0.52,0.5,D,0.52,0.514,A,0.5146,0.514,C,0.51442,0.5143,D,0.51442,0.514384,0.514402,0.5143876,B,输出为期间任意数,2.4,算术编码,上述编码过程可由下表详细说明：,步骤,输入符号,编码间隔,编码判决,1,C,0.5,0.7,符号的间隔范围,0.5,0.7,2,A,0.5,0.52,0.5,0.7,间隔的第,1,个,1/10,3,D,0.514,0.52,0.5,0.52,间隔的最后,3,个,1/10,4,A,0.514,0.5146,0.514,0.52,间隔的第,1,个,1/10,5,C,0.5143,0.51442,0.514,0.5146,间隔从第,5,个,1/10,开始的,2,个,1/10,6,D,0.514384,0.51442,0.5143,0.51442,间隔的最后,3,个,1/10,7,B,0.5143876,0.514402,0.514384,0.51442,间隔从第,1,个,1/10,开始的,4,个,1/10,8,从,0.5143876,0.514402,中选择一个数作为输出：,0.5143876,2.4,算术编码,解码过程可由下表详细说明：,步骤,间隔,译码符号,译码判决,1,0.5,0.7,C,0.51439,在间隔,0.5,0.7),2,0.5,0.52,A,0.51439,在间隔,0.5,0.7),的第,1,个,1/10,3,0.514,0.52,D,0.51439,在间隔,0.5,0.52),的第,7,个,1/10,4,0.514,0.5146,A,0.51439,在间隔,0.514,0.52,的第,1,个,1/10,5,0.5143,0.51442,C,0.51439,在间隔,0.514,0.5146,的第,5,个,1/10,6,0.514384,0.51442,D,0.51439,在间隔,0.5143,0.51442,的第,7,个,1/10,7,0.51439,0.5143948,B,0.51439,在间隔,0.51439,0.5143948,的第,1,个,1/10,8,译码的消息：,C A D A C D B,算术编码的特点：,算术编码有基于概率统计的固定模式，也有相对灵活的自适应模式。所谓自适应模式的工作方式是：为各个符号设定相同的概率初始值，然后根据出现的符号做相应的改变。自适应模式适用于不进行概率统计的场合。,当信号源符号的出现概率接近时，算术编码的效率高于霍夫曼编码。,算术编码的实现相应地比霍夫曼编码复杂，但在图像测试中表明，算术编码效率比霍夫曼编码效率高,5,左右。,2.4,算术编码,2.5 LZW,编码,LZW(Lempel Ziv Welch),压缩编码是一种字典式无损压缩编码，主要用于图像数据的压缩。,LZW,压缩技术把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系建立一个转换表，又叫“字符串表”。压缩过程中生成的转换表，记录了代码和数据的对应关系，并且只用于压缩过程。在解压过程中，,LZW,压缩编码会生成另一个用于解压缩的转换表，该表与压缩时产生的转换表完全相同，数据以严格对应的无损方式被还原。,2.5 LZW,编码,LZW,编码的具体步骤如下：,开始时的词典（转换表）包括所有可能的词根,(Root),，即基本符号的编码，而当前前缀,P,是空的；,当前字符,C=,字符流中的下一个字符；,判断“前缀,-,当前字符”串,P+C,是否在词典中：,如果“是”：,P=P+C,；,/P+C,作为新的前缀,如果“否”：,把代表当前前缀,P,的码字输出到码字流；,/,输出前缀,P,的代码,把“前缀,-,当前字符”串,P+C,添加到词典中；,令,P=C,。,/,当前字符,C,成为新的前缀并编码,判断输入字符流中是否还有码字要译：,如果“是”，就返回到,2,；,如果“否”：,把代表当前前缀,P,的码字输入到码字流；,结束。,编码结束。,2.5 LZW,编码,LZW,编码的特点：,LZW,压缩技术的处理过程比较复杂，该过程完全可逆，对于简单图像和平滑且噪声小的信号源具有较高的压缩比，并且有较高的压缩和解压缩速度；,LZW,压缩技术对于可预测性不大的数据具有较好的处理效果，常用于,GIF,格式的图像压缩，其平均压缩比在,2:1,以上，最高压缩比可达,3:1,。,除用于图像数据处理以外，,LZW,压缩技术还被用于文本程序等数据压缩领域。对于数据流中连续重复出现的字节和字串，,LZW,压缩技术具有很高的压缩比。,PCM,编码是等长二进制码，其编码率不够小，比如，对于,256,级灰度的黑白图像，每像素需,8,位；对于彩色图像，每像素需,24,位。所以直接以,PCM,编码、存储或传送数字图像，其总数据量还是太庞大，无法实现，因此需要采用更高压缩比的压缩编码方法。预测编码方法是一种较为实用广泛采用一种压缩编码方法。,3.,预测编码,预测编码（,Predictive Coding,）是统计冗余数据压缩理论的三个重要分支之一，它的理论基础是现代统计学和控制论。,预测编码主要是减少了数据在时间和空间上的相关性，因而对于时间序列数据有着广泛的应用价值。在数字通信系统中，例如语音的分析与合成，图像的编码与解码，预测编码已得到了广泛的实际应用。,3.,预测编码,预测编码是根据某一模型利用以往的样本值对于新样本值进行预测，然后将样本的实际值与预测值相减得到一个误差值，对这一误差值进行编码。如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号，从而可以用较少的电平类对其差值量化得到较大的数据压缩结果。,预测编码方法原理,：从相邻像素之间有强的相关性特点考虑的。比如当前像素的灰度或颜色信号，数值上与其相邻像素总是比较接近，除非处于边界状态。那么，当前像素的灰度或颜色信号的数值，可用前面一出现的像素的值，进行预测（估计），得到一个预测值（估计值）将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法称为预测编码方法。,3.1.1 DPCM,的基本原理,线性预测编码方法，也称差值脉冲编码调制法,(Different Pulse Code Modulation,DPCM),。,-,一幅二维静止图像，设空间坐标,像素点的实际灰度为,是根据以前已出现的像素点的灰度对该点的预测灰度，也称预测值或估计值。计算预测值的像素，可以是同一扫描行的前几个像素，或者是前几行上的像素，甚至是前几帧的相邻像素。实际值和预测值之间的差值，以下式表示：,将此差值定义为预测误差。由于图像像素之间有极强的相关性，所以这个预测误差是很小的。编码时，不是对像素点的实际灰度 进行编码，而是对预测误差信号 进行量化、编码、发送，由此而得名为差值脉冲编码调制法。,3.1.1 DPCM,的基本原理,DPCM,系统包括发送、接收和信道传输,3,个部分。,-,发送端由编码器、量化器、预测器和加减法器组成；,-,接收端包括解码器和预测器等；,-,信道传送以虚线表示。,DPCM,系统具有结构简单，容易用硬件实现（接收端的预测器和发送端的预测器完全相同）的优点。,3.1.2,最佳线性预测,如图为像素 的预测域图，途中标出 像素的,3,个相邻像素，由先前（同行一点，上一行两点）三点预测，定义为,构成三阶预测器。,其中，,a,1,，,a,2,，,a,3,称预测系数，都是待定参数。如果预测器中预测系数是固定不变的常数，称之为线性预测。,3.1.2,最佳线性预测,3.1.2,最佳线性预测,预测误差,线性预测器中，,a,1,，,a,2,，,a,3,是待定参数，当,a,1,，,a,2,，,a,3,满足使预测误差最小，且保持固定不变时，便构成,最佳线性预测器,。,3.1.2,最佳线性预测,应用均方误差最小准则，求出预测系数,a,1,，,a,2,，,a,3,以获得 的最佳线性预测值,均方误差的表达式为,将预测值与实际值之间的均方误差 ，对,a,1,，,a,2,，,a,3,求偏导，令,解方程，得,a,1,，,a,2,，,a,3,，即为最佳线性预测系数。,3.2,自适应预测编码,在,DPCM,系统中，是预测系数和量化器参数一次设计好后不再改变，对于图像平坦区和边缘处会导致令人讨厌的噪声，因此引入自适应差值脉冲编码调制,(Adaptive DPCM,ADPCM),系统。,自适应技术的概念是预测器的预测系数和量化器的量化参数，能够根据图像的局部区域分布特点而自动调整。,ADPCM,系统包括：自适应预测，即预测系数的自适应调整；自适应量化，即量化器参数的自适应调整两部分。,3.2.1,自适应预测,一个三阶预测器的预测值计算公式为,现在增加一个可变参数“,m,”，得,式中,m,是一个自适应参数，,m,的取值依据量化误差的大小自适应调整。,3.2.1,自适应预测,设量化器最大输出为 ，最小输出为 ，某一个预测误差的量化输出为,当,m,不变,m,自动变大,m,自动减小,M,自动增大，使 随之增大，预测误差减小，使斜率过载尽快收敛；,m,自动减小，使 随之减小，预测误差加大，使量化器输出不致正负跳变，减轻颗粒噪声。,3.2.2,自适应量化,自适应量化的概念是，根据图像局部区域的特点，自适应地修改和调整量化器的参数，包括量化器输出的动态范围，量化器判决电平（量化器步长）等。,实际上是在量化器分层确定后，当预测误差值小时，将量化器的输出动态范围减小，量化器步长减小；当预测误差大时，将量化器的输出范围扩大，量化器步长扩大。参数改变的原则，是量化误差低于该误差下的视觉阈值，将误差掩盖。,3.2.2,自适应量化,自适应量化的具体实现方法是：,先定义一视觉掩盖函数,M,这个掩盖函数的含义是，当,4,个差值,e,1,，,e,2,，,e,3,，,e,4,中有一个较大数值，那么对预测,f,时所形成的量化误差，构成“掩盖效应”，即掩盖量化噪声，使人眼难以察觉。,3.2.2,自适应量化,设量化分层级数为,16,，确定以下,4,种情况下的量化输出电平值。,当视觉掩盖函数,M20,时，只取,|e|=0,两侧的,16,个量化分层，量化器步长较细；,当视觉掩盖函数,，,M=20,，可见度阈值约,3.5,以内的量化误差可掩盖,当,36 M72,时，,M=72,的可见度阈值约,7.5,3.3,帧间预测编码,帧间编码技术处理的对象是序列图像（也称为运动图像）。是把几帧的图像存储起来做实时处理，利用帧间的时间相关性进一步消除图像信号的冗余度，提高压缩比。,基于预测技术的帧间预测编码方法：条件补充法和运动补偿技术。,3.3,帧间预测编码,时间,B,C,A,X,帧,B,C,A,X,帧,3.3.1,条件补充法,Mounts,，,Pease,等人提出条件像素补充法规定，若帧间各对应像素的亮度差超过阈值，则把这些像素存在缓冲存储器中，并以恒定的传输速度传送；而阈值以下的像素则不传送，在接收端用上一帧相应像素值来代替。这样一幅电视图像可能只传送其中较少部分的像素，且传送的只是帧间差值，可以得到较好的压缩比。,条件补充法还可以和内插法相结合应用，称为条件次取样。在时间轴采用次取样，对于未取样的当前场某点，可以用隔场的,4,邻点的亮度的均值作为该点亮度的预测值。,3.3.2,运动补偿技术,在标准化视频编码方案,MPEG,中，运动补偿技术是其使用的主要技术之一。尤其对于运动部分只占整个画面较小的会议电视和可视电视，引入运动补偿技术后，压缩比可以提高很多。,运动补偿方法是跟踪画面内的运动情况对其加以补偿之后再进行帧间预测。这项技术的关键是运动向量的计算。,3.3.2,运动补偿技术,运动向量的估值方法：块匹配算法,把图像分成若干子快图像，设子图像是,MN,的矩形块。设当前帧图像亮度信号为,f,k,(m,n),，前一次传送的图像为,f,k-Ns,(m,n),，这里,N,s,为帧差数目。通常帧差,N,s,可能是,1,，,3,或,7.,我们假定当前帧中的一个,MN,子块是从第,k-N,s,帧平行移动而来，并设,MN,子块内所有像素都具有同一个位移值,(i,j),。假定运动物体在,N,s,帧差时间内水平和垂直最大位移均为,L,，这样我们可以在第,k-N,s,帧搜索区,SR,内进行搜索，这里,SR,搜索区为,(M+2L,N+2L),。,4.,变换编码,变换编码不是直接对空域图像信号编码，而是首先将空域图像信号影射变换到另一个正交矢量空间（变换域或频域），产生一批变换系数，然后对这些变换系数，进行编码处理。,在发送端将原始图像分隔成,1,到,n,个子图像块，每个子图像块送入正交变换器做正交变换，变换器输出变换系数经滤波、量化、编码后送信道传输到达接收端，接收端作解码、逆变换、综合拼接，恢复出空域图像。,4.,变换编码,子块,1,子块,2,子块,n,正变换,滤波,量化,编码,信道,逆变换,解码,综合拼接,原始图像,（发送）,恢复图像,4.1,变换编码的基本原理,变换编码技术已有近,30,年的历史，技术上比较成熟，理论