多媒体通信技术四-修订

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 视频信息压缩与处理,2024/8/9,1,第四章 视频信息压缩与处理,本章主要内容,图像信号的相关特点,图像处理方法,各种实用编码,常见的图像压缩编码标准,2024/8/9,2,图像信号的相关特点,通常一幅图像中的各像素之间存在一定的相关性。,在活动图像中，由于两幅相邻图像之间的时间间隔很短，因此这两幅图像信息中包含大量相关信息。,这些就是图像信息中的冗余。,2024/8/9,3,图像信号的相关特点,多媒体数据压缩的目的就是要去除图像信息中的大量冗余，同时又能保证图像的质量。,一般针对不同类型的冗余信息，采取不同的压缩方法。,2024/8/9,4,图像信息中存在的冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,1011 0001 1100,1011 0001 1100,0101 1010 1010,1011 1100,0101 1111 1010,2,24,色,2,8,色,2024/8/9,5,1.空间冗余,空间冗余是在图像数据中经常存在的一种冗余。,在任何一幅图像中：,均有许多灰度或颜色都,相同的邻近像素组成的,局部区域,，它们之间具有空间上的强相关性，在图像中就,表现为空间冗余。,2024/8/9,6,1.,空间冗余,2024/8/9,7,颜色相同的区域,2024/8/9,8,对空间冗余的压缩方法就是把这种,颜色都,相同的邻近像素组成的,局部区域,当作一个整体，用极少的数据量来表示它，从而节省了存储空间。,这种压缩方法叫,空间压缩,或,帧内压缩,。,2024/8/9,9,时间冗余,：视频信号和动画是基于时间轴的一组连续画面。由于活动图像序列中的任意两幅相邻的图像之间的时间间隔很短，因此两幅图像中存在大量的相关信息,时间冗余,2024/8/9,10,2024/8/9,11,相邻帧包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同,2024/8/9,12,活动图像中的两幅相邻的图像有较大的相关性，这反映为,时间冗余,。,在前一幅图像的基础上，只需改变少量的数据，便可以表示出后一幅图像，达到数据压缩的目的。,这种压缩对活动图像往往能得到很高的压缩比，这也称为,时间压缩,或,帧间压缩,。,2024/8/9,13,3.,统计冗余,空间冗余和时间冗余是将图像信号看作为随机信号时所反映出的统计特征，因此有时把这两种冗余称为,统计冗余,。,2024/8/9,14,4.信息熵冗余,信息熵是针对数据的信息量而言的，它代表从图像信息源中发出的一个符号的平均信息量,设某种编码的平均码长单位（符号）的,数据量,为,式中，为分配给第 符号的比特数，即二进制位数,2024/8/9,15,由于实际中很难估算各符号出现的概率，我们一般认为它们是等概率的，所以每个符号比特数相同。,这种编码的符号的数据量L为最大。,但实际各符号出现的概率并不相同。,这样所得的L必然大于实际的信源熵H，由此带来的冗余我们称为,信息熵冗余,或,编码冗余,。,2024/8/9,16,总结：,数据中通常包含很大的冗余，数据的大小与所携带的信息量的关系由下式给出：,L=H+R,H：信源熵（信息量/符号，代表最小比特数）、,L：数据量（平均码长单位，即符号实际的比特数）,R：冗余量（即信息冗余量）,R=L-H,2024/8/9,17,5.结构冗余,有些图像从整体上看存在着非常强的纹理结构。,下图为草席图像。是一种,规则有序排列的图形，,我们称它在结构上存在冗余。是一种结构冗余。,规则有序排列的图形,2024/8/9,18,6.知识冗余,有些图像的理解与某些知识有相当大的相关性。,比如人脸的图像有固定的结构：,嘴的上方有鼻子、鼻子的上方有双眼睛，鼻子位于正脸图像的中线上等等,这类规律的结构可由先验知识和背景知识得到，因此这类信息对一般人来说就是冗余信息。这就是知识冗余。,2024/8/9,19,7.视觉冗余,由于人眼的视觉特性有所限制，人类的视觉系统不能对图像画面的任何变化都能感觉到。,举例：,人眼视觉系统的一般分辨率为64灰度等级,而一般图像的量化采用的是256的灰度等级。,这种差别就是视觉冗余。,2024/8/9,20,视频压缩编码方法及其分类,图像压缩的基本目标就是减小数据量。,至于图像压缩到什么程度而又没有明显的失真,则取决于图像数据的冗余度。,所有的这些冗余度都可以被除去而不会引起显著的信息损失。,空间冗余,和,时间冗余,是图像信号最常见的冗余。,2024/8/9,21,压缩编码分类,1.按恢复的图像性质划分,按恢复的图像性质,数字图像压缩方法可以分为两种：,无损压缩编码,有损压缩编码,2024/8/9,22,压缩编码分类,无损压缩编码：,也称为熵编码、可逆编码或无失真编码。,当系统采用此方法进行数据压缩时,在接收端所获得的解码与原图像完全相同。,无损压缩不能提供较高的压缩比。,一般在2:15:1。,2024/8/9,23,压缩编码分类,有损编码：,也称为不可逆编码、熵压缩编码或失真编码。,由于压缩了熵，会减少信息而不能再恢复。,这种压缩编码具有较高的压缩比。,最大可达几百比一。,2024/8/9,24,压缩编码分类,2.,按压缩方法的原理划分,按压缩原理划分,数字图像压缩方法可以分为以下几种编码,:,预测编码,变换编码,标量量化和矢量量化编码,信息熵编码,子带编码,结构编码,模型编码,2024/8/9,25,图像压缩编码,无损压缩,有损压缩,霍夫曼编码,行程编码,算术编码,L-Z,编码,预测编码,:,量化编码:,模型编码,:,混合编码,:,变换编码,:,DPCM,；运动补偿,DCT,；子带编码,分形编码；知识基编码,JPEG,；,MPEG,；,H.26X,编码,采样编码；矢量量化编码,2024/8/9,26,图像压缩算法分类,2024/8/9,27,压缩编码分类,（1）预测编码：,其典型的压缩方法有DPCM和ADPCM.它们比较适合于图像数据的压缩。,它主要是减少图像数据在,空间上,和,时间上,的相关性，从而达到数据压缩的目的，但这是一种有失真的压缩方法。,2024/8/9,28,压缩编码分类,（2）变换编码：,它是将图像,时域信号,转换到,变换域,（系数空间、频域）上进行处理。,在实际编码中，常常利用图像的统计特性和人眼的视觉特性，只是选择部分变换系数来进行信息传输，因此恢复的图像中将存在一定的失真。,常用的正交变换有：离散傅氏变换DFT、离散余弦变换DCT、离散正弦变换DST和K-L变换。,2024/8/9,29,压缩编码分类,（3）标量量化和矢量量化编码：,标量量化指传统的量化，是将具有无限电平的点样值，用有限电平数表示的方法，是一个样点、一个样点地进行量化编码。,这里量化器的设计是一个很关键的步骤。,2024/8/9,30,压缩编码分类,（3）标量量化和矢量量化编码：,矢量编码是相对标量量化而提出的。,矢量编码中一次可以量化多个样点。,矢量量化也是一种有损压缩编码。,2024/8/9,31,压缩编码分类,（4）信息熵编码：,信息熵编码是一种基于图像统计特性的编码方法。,是一种无损压缩编码方法。,2024/8/9,32,压缩编码分类,（4）信息熵编码：,它是根据信息熵的原理：,用最短的位数表示出现概率大的信息，而出现概率较小的信息则用较长的位数来表示，以此达到压缩数据的目的。,常见的熵编码有,哈夫曼编码,、,游程编码,和,算术编码,。,2024/8/9,33,压缩编码分类,（5）子带编码：,在子带编码中，首先将图像数据转换到频域，然后按频率分成若干子带，对每个子带用不同的编码器进行抽样、量化和编码，并将各子带输出数据合成为数据码流，从而获得压缩数据。,2024/8/9,34,压缩编码分类,（6）结构编码：,结构编码也称为第二代编码。,编码时首先求出图像中的边界、轮廓、纹理等结构特征参数，然后保存这些参数信息，进行编码。,在解码时则根据这些结构和参数信息进行图像合成，从而恢复出原图像。,2024/8/9,35,压缩编码分类,（7）模型编码：,这是一种基于知识的编码。,利用人们对自然知识的了解而形成一个规则库，将人脸变化等特征用一系列参数来进行描述。,利用参数再加上模型就可以实现人脸的图像编码和解码，达到压缩图像数据的目的。,2024/8/9,36,数据压缩技术的性能指标,1、压缩比,用来定义压缩性能。指压缩过程中输入数据量与输出数据量之比。,设原图像的平均码长为Lc,压缩后图像的平均码长为L，则压缩比C为,压缩比越大，说明数据压缩的程度越高。,2024/8/9,37,冗余度,和,编码效率,也是衡量信源特性以及编解码设备性能的重要指标，定义如下：,冗余度,:,指冗余量在信息量中占的比例,L,为平均码字长度,H(X),为信源熵。,编码效率,：指信息量在数据量中占的比例,2024/8/9,38,数据压缩技术的性能指标,2、重现质量：,恢复效果要好，要尽可能地恢复原始数据。,3、压缩和解压缩速度,2024/8/9,39,无损图像压缩编码方法,无失真（无损）图像压缩编码就是指图像经过压缩、编码后恢复出的图像与原图像完全一样,没有任何失真。,无失真压缩编码-熵,编码,。,广泛应用于文本数据和特殊应用场合的图像数据（指纹图像、医学图像、卫星图像等）的压缩。,2024/8/9,40,无损图像压缩编码方法,香农信息论认为,信源中或多或少地含有自然冗余度。,这些冗余度既来自于信源本身的相关性,又来自于信源概率分布的不均匀性中。,只要找到去除相关性或改变概率分布不均匀性的方法和手段,也就找到了信息熵编码的方法。,2024/8/9,41,无损图像压缩编码方法,例如：,在图像中存在着空间上的相关性,对运动图像而言存在着帧与帧之间在时间上的相关性。,这些都说明存在着颜色的概率分布的不均匀性。,2024/8/9,42,无损图像压缩编码方法,信息熵编码所要解决的问题：,如何利用信息熵理论（香农信息论）减少数据在传输和存储时的冗余度。,2024/8/9,43,香农信息论,香农信息论认为：,信源所含有的信息熵就是进行无失真编码的理论极限。,2024/8/9,44,香农信息论,低于此极限的无失真编码方法是找不到的,而只要不低于此极限,那就总能找到某种适宜的编码方法任意的逼近信息熵。,熵编码的目的就是要使编码后的图像,平均码字长度（比特数）,L,近可能接近这个,信息熵,H(x),2024/8/9,45,无损图像压缩编码方法,根据：,L=H+R,H,：信源熵（信息量,/,符号，代表符号的最小比特数）、,L,：数据量（每个符号实际平均的比特数，也称,码字长度,）,R,：冗余量（即信息冗余量）,R=L-H,无损数据压缩的本质：通过减少冗余量,R,，减少数据量,L,，使之接近,H,。,2024/8/9,46,无损图像压缩编码方法,无损图像压缩编码方法由于其中并没有考虑人眼的视觉特性,因此其所能达到的压缩比非常有限。,常用的无失真图像压缩编码有：,哈夫曼编码,游程编码（行程编码）,算术编码,2024/8/9,47,无损图像压缩编码方法,在实际应用中,常将游程编码与哈夫曼编码结合起来使用,例如在,H.261,、,JPEG,、,MPEG,等国际标准中正是采用此种编码技术。,而在,H.263,等国际标准中则采用算术编码技术。,2024/8/9,48,哈夫曼编码,哈夫曼,(Huffman),编码方法于,1952,年问世,迄今为止仍经久不衰,广泛应用于各种数据压缩技术中,且仍不失为熵编码中的最佳编码方法。,主要编码思路：,对,出现频率较大,的符号用,较短的码,来表示，,而对于,出现频率较小,的符号则用,较长的码,来表示。,这样的编码结果所获得的平均码字长度最短。,2024/8/9,49,哈夫曼编码,哈夫曼编码的码长是变化的，即可变长编码(VLC),而且哈夫曼编码通常被称为最优码。,最优的含义是：,对于给定的符号集和概率模型，找不到任何其它整数码比哈夫曼编码有更短的码长。,整数码：指每个符号所对应的码字的位数都是整数。,2024/8/9,50,哈夫曼编码,具体编码过程：,1,、排序：按符号出现的概率从大到小进行排列。,2,、赋值：对排在最后的两个符号进行赋值，概率大的赋,“,1,”,，概率小的赋,“,0,”,。或相反。,3,、合并：将上述最后的两个符号出现的概率相加合成一个概率。,2024/8/9,51,哈夫曼编码,4,、重新排序：将合成后的概率与其它符号概率一起进行重新排序（从大到小）。然后重复步骤,2,、,3,的内容，直至概率相加为,1,为止。,5,、码字分配：从最后一步开始反向进行码字分配。从而形成一个码字。,2024/8/9,52,哈夫曼编码的基本原理,例：,aaaa,bbb,cc,d,eeeee,fffffff,4 3 2 1 5 7,如果不进行特殊的编码，用字符方式（ASCII码）传送，每个字符8位，需要的数据量为：,22*8=,176,bit,2024/8/9,53,哈夫曼编码的基本原理,c,b,a,f,e,7/22,5/22,4/22,2/22,1,0,f=11 e=01 a=00 b=101 c=1001 d=1000,d,1/22,3/22,6/22,22/22,13/22,9/22,3/22,1,0,1,0,1,0,1,0,2024/8/9,54,哈夫曼编码,原始符号,各符号出现概率,组成的二进制码,码长,L,a,4/22,00,2,b,3/22,101,3,c,2/22,1001,4,d,1/22,1000,4,e,5/22,01,2,f,7/22,11,2,2024/8/9,55,哈夫曼编码的基本原理,aaaa,bbb,cc,d,eeeee,fffffff,4 3 2 1 5 7,按照哈夫曼编码的原理进行编码：,a=00 b=101 c=1001 d=1000 e=01 f=11,需要的数据量为,4*,2,+3*,3,+2*,4,+1*,4,+5*,2,+7*,2,=,53,bit,比,22*8=176bit,少了,123,bit,平均编码长度,L,为,2024/8/9,56,哈夫曼编码的基本原理,例 设信号源为X=、a、e、I、m、t、c、h、r。若传送一个字符串,“,I am a teacher,”,，对应的概率为,p=,0.22,、,0.22,、,0.14,、,0.07,、,0.07,、,0.07,、,0.07,、,0.07,、,0.07,试给出该信源的霍夫曼编码方案。,并计算压缩比C、冗余度R和编码效率。,2024/8/9,57,2024/8/9,58,=,01,a=,00,e=,111,I=,1101,m=,1100,t=,1011,c=,1010,h=,1001,r=,1000,出现,3,次，,a,出现,3,次，,e,出现,2,次，其它的各出现,1,次。,共需要,3*,2,+3*,2,+2*,3,+6*,4,=,42,bit,2024/8/9,59,分析:,若传送一个字符串,“,I am a teacher,”,，共14个字符，其中包括9个不同的字符。,（1）若使用自然编码（等长二进制编码），该字符串中有,9,个不同的符号，至少需要,4,位二进制才能表示，这样传送该字符串也要,56,位。,（2）Huffman编码只需要,42位,，平均编码长度为,2.98,。,平均码字长度公式为：,2024/8/9,60,求压缩比、冗余度和编码效率:,压缩比C：,14个字符，需4位二进制数 Lc=4,C=Lc/L=4/2.98=,1.34:1,冗余度R,=(L-H)/H=(2.98-2.97)/2.97=0.34%,编码效率,2024/8/9,61,哈夫曼编码,例：某信源符号及其对应的概率如下：,a1 a2 a3 a4 a5 a6,0.4 0.2 0.12 0.15 0.1 0.03,请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。,2024/8/9,62,哈夫曼编码,例：某信源符号及其对应的概率如下：,a1,a2,a3,a4,a5,a6,a7,a8,0.40 0.04 0.1 0.1 0.07 0.06 0.18 0.04,请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。,a1:,0,a2:,11100,a3:,100,a4:,1111,a5:,1011,a6:,1010,a7:,11101,a8:,110,2024/8/9,63,哈夫曼编码,特点：,（1）虽然哈夫曼码长可变,但却不需要另附同步码。,（2）,通信双方只要均拥有预先编写的解释各种代码意义的,词典,(即,码本,),即可根据,码本,逐码译出。,2024/8/9,64,哈夫曼编码,哈夫曼编码有几个问题值得注意:,一、哈夫曼码没有错误保护功能。,如果码串中有错,哪怕仅仅是1位出错,不但该码本身将会译错,更糟糕的是对后面的影响,一错就是一串,一般称这种现象为错误传播。,2024/8/9,65,哈夫曼编码,二、不可调用中间的内容,哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;,三、接收端需保存一个与发送端相同的霍夫曼码表,哈夫曼码还是得到广泛应用,哈夫曼编码毕竟属于最佳编码方法。,2024/8/9,66,游程编码,RLC,游程编码（行程编码）,RLC,（,RLE),是一种非常简单的数据压缩编码形式。它在某些场合是非常有效的一种无损压缩编码方法。,2024/8/9,67,游程编码,RLC,游程编码编码原则:,连续重复的数据值序列（或称为,“,流,”,）用一个重复次数和单个数据值来代替。,比如：得到的字符串为AAAAAABCDDDDDDDDDBBBBBBBB,可压缩为*6ABC*9D*8B,2024/8/9,68,颜色相同的区域,2024/8/9,69,游程编码,RLC,不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数目。,或者存储一个像素的颜色值，以及具有相同颜色值的行数。,这种压缩编码称为,游程编码,或,行程编码,。,2024/8/9,70,游程编码,RLC,游程编码多用于黑白图像或图形的压缩。,具有相同灰度等级的连续的像素数目称为,游程长度RL,。,图像中具有相同灰度的图像块越大越多，压缩的效果就越好。,2024/8/9,71,宽度：263 宽度：263,高度：300 高度：300,灰度：4 灰度：8,2024/8/9,72,游程编码,RLC,RLC特点：,编码简单直观，编码/解码速度快,，,只需要简单地复制字符若干遍即可以了。,BMP、TIFF、AVI,等格式文件的压缩均采用此方法。在,PDF,文件格式中也得到应用。,存在着不同的实现技术和文件格式。,2024/8/9,73,游程编码,RLC,的构成,在RLC中用3个字节表示一个字符串：,由一个指示符、一个重复次数字节和一个被重复的字符构成的3字节码,指示符,重复次数,RL,被重复字符,思考：,RL,?,时，数据压缩才用意义,3,2024/8/9,74,游程编码,RLC,方法,例如:字符串,RTAAAASDEEEEE,经RLE压缩后为：,RT*4ASD*5E,“,*4A,”,代替了,“,AAAA,”,“,*5E,”,代替,“,EEEEE,”,指示符采用特殊字符,*,：,指出一个RLC编码的开始，后面的数字表示重复的次数，数字后的单个字符是被重复的字符。,2024/8/9,75,游程编码,RLC,方法,例:设有数据,“,AAAABBBBCCCCCCCDAAAAAA,”,试计算该数据的行程编码。,解：,A,重复,4,次，,B,重复,4,次，,C,重复,7,次，,D,不重复，,A,重复,6,次，,RLC数据流为：,“,#4A#4B#7CD#6A,”,，其中,#,为指示符。总共占用,13,个字节，而源数据占用,22,个字节。,游程编码也可以不用指示符:,重复与否相同对待，相应的RLC为,“,3A4B5C1D6A,”,占用,10,个字节。,2024/8/9,76,游程编码,RLC,方法,例：,aaaa,bbb,cc,d,eeeee,fffffff,(共22*8=176 bit),4a3b2c1d5e7f,(共12*8=96 bit),压缩率为：176/96=1.83:1,2024/8/9,77,游程编码,游程编码的压缩率不高，但编码、解码的速度快，仍被得到广泛的应用。,特别是在,变换编码,后再进行,游程编码,，有很好的效果。在图像数据压缩标准(JPEG)中扮演重要角色。,2024/8/9,78,算术编码,算术编码产生于20世纪60年代初,在图像数据压缩标准中算术编码扮演了重要的角色。能有效地压缩信源冗余度，属于熵编码的一种。,该方法实现较为复杂，常与其它有损压缩编码结合使用，在视频数据压缩标准(如H.263)中扮演重要角色。,2024/8/9,79,算术编码,算术编码与哈夫曼编码一样，也是对概率较大的符号采用短码，对概率较小的符号采用长码。,它突破了哈夫曼编码每个符号只能按整数比特来逼近信源熵的限制:,每个符号的平均编码长度可以按,小数比特,来逼近信源熵。,2024/8/9,80,算术编码基本思想,算术编码不是将单个信源符号映射成一个码字。,而是把,整个信源,表示为实数线上的,0,到,1,之间的一个区间，其长度等于该,信源,的概率。,再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。,2024/8/9,81,算术编码基本步骤,将编码的消息表示成实数0和1之间的一个区间。,消息序列中的每个元素都要用来缩短这个区间。,消息序列中元素越多，所得到的区间就越小，当区间变小时，表示这一区间所需的二进制位就越多。,消息结束时就最后所得到区间的下边界值表示该消息。,2024/8/9,82,给定符号序列的算术编码步骤如下：,（1）初始化：,编码器开始时将,“,当前区间,”,设置为一。,为0，1),（2）按消息（符号序列）中符号的顺序：,对每一符号，编码器按步骤,（a）,和,（b）,重复进行处理,2024/8/9,83,给定符号序列的算术编码步骤如下：,（a）,编码器将,“,当前区间,”,分为,子区间,，每一个符号分配一个子区间。一个子区间的大小与符号的概率成比例。,（b）,对应于一个确切发生的符号，编码器选择其子区间，并使它成为,新的,“,当前区间,”,。,这也称为重新归一化。,2024/8/9,84,给定符号序列的算术编码步骤如下：,（3）最后一个符号对应有最后输出的,“,当前区间,”,。,最后输出的,“,当前区间,”,的下边界就是该给定的整个符号序列的算术编码。,2024/8/9,85,2024/8/9,86,算术编码方法,算术编码用到两个基本的参数：符号的概率和它的累积概率。,累积概率（下边界值）：,设信源符号集为,A=,a,0,a,1,a,2,a,m-1,相应的概率为,Pi，i=0，1，2，,，m-1。,各符号的累积概率,P,r,为:,a,0,的累积概率为0，,a,1,的累积概率为,P,0,，a,2,的累积概率为,P,0,+P,1,2024/8/9,87,算术编码示例：,符号 S1、S2、S3、S4,十进制概率 1/8 1/4 1/2 1/8,二进制概率,P,i,0.001 0.01 0.1 0.001,累积概率,P,r,0 0.001 0.011 0.111,0 1/8 3/8 7/8 1,0 0.001 0.011 0.111 1,S1,S2,S3,S4,2024/8/9,88,现在以符号序列：,s3 s3 s2 s4,为例来解释编码过程,算术编码的基本法则归纳如下:,(1)初始状态,区间起始点,C=0,区间宽度,A=1.0,。,(2),新区间起点C,=原起点C+原区间宽度A,P,r,新区间宽度A,=原区间宽度A,Pi,其中,P,r,为所编符号si对应的,累积概率,Pi,为所编符号si对应的,概率,。,2024/8/9,89,对序列,s3 s3 s2 s4,进行编码的过程如下:,初始起点C=0 初始区间宽度A=1,第1个符号,s3,:,新区间起点：,C,=0+1,0.011,=0.011,新区间宽度,：,A,=1,0.1,=0.1,区间终点为,0.111,新的,当前区间,范围为：0.011-0.111,2024/8/9,90,第2个符号,s3,:,新区间起点：C,=0.011+0.1,0.011=0.1001,新区间宽度,：,A,=0.1,0.1,=0.01,区间终点0.1101,新的,当前区间,为：0.1001-0.1101,2024/8/9,91,第3个符号,s2,:,新区间起点：C,=0.1001+0.01,0.001,=0.10011,新区间宽度：A,=0.01,0.01,=0.0001,新的,当前区间,为：0.10011-0.10101,第4个符号,s4:,新区间起点：C,=0.10011+0.0001,0.111,=0.1010011,新区间宽度：A,=0.0001,0.001,=0.0000001,取最后符号的当前区间的下边界作为序列的算术编码,所以最终编完的码字是,0.1010011,2024/8/9,92,算数编码的代码长度L为多少？,根据信源熵：,得出，算数编码的代码长度L：,N 代表出现的符号数量,代表大于X的最小整数。,代码取其值小数点后的L位。若有尾数，就进位到第L位。,2024/8/9,93,如：,则取 L=3,如果最后符号的下边界为0.10110001,取：c=0.110,传输的二进制代码序列是,110,2024/8/9,94,刚才例题最终编完的码字0.1010011,传输,s3 s3 s2 s4,共4个符号，得,取7位,所以传输的码流为,1010011,压缩率为：,4,2/7=8/7=1.14:1,2024/8/9,95,算术编码解码过程,在解码器中,当收到码字串,0.1010011,时,这个码字串指向子区间,0.011,0.111),解出的第一个符号应为,s3,0 0.001 0.011 0.111 1.0,S1,S2,S3,S4,2024/8/9,96,算术编码解码过程,之后采取与编码过程相反的步骤：,即：从码字串中减去,已解符号,的,累积概率,并将,差值,除以,概率值,则得到新码字串。,(0.10100111,-,0.011),(0.1)=,0.100011,。,新码字串仍落在0.011,0.111)区间之内,解出的第2个符号仍为,s3,。,后面的过程以此类推,0 0.001 0.011 0.111 1.0,S1,S2,S3,S4,2024/8/9,97,（0.100011-0.011）/0.1=0.01011,0.01011在,0.001，0.011）,所以是s2区间,解出的第3个符号为,s2,第四步：（0.01011-0.001）/0.01=0.111,因为0.111在0.111，1.0）是s4区间,解出的第4个符号为,s4,所以（0.111-0.111）/0.001=0,即：,s3 s3 s2 s4,解码完毕！,0 0.001 0.011 0.111 1.0,S1,S2,S3,S4,2024/8/9,98,例：假设信源符号为,A,，,B,，,C,，,D,，这些符号的概率分别为,0.1,，,0.4,，,0.2,，,0.3,，,根据这些概率可把间隔,0,，,1,）分成,4,个子间,0,，,0.1,）、,0.1,，,0.5,）、,0.5,，,0.7,）、,0.7,，,1,），,其中,x,，,y,）表示半开放间隔，即包含,x,不包含,y,。,符号,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,）,累积概率,0,0.1,0.5,0.7,2024/8/9,99,2024/8/9,100,二进制消息序列的输入为：,C A D A C D B。,编码：,首先输入的符号是,C,：,新区间起点：C,=0+1,0.5,=0.5,新区间宽度：A,=1,0.2,=0.2,区间终点:0.5+0.2=0.7,新的当前区间范围为：0.5-0.7,2024/8/9,101,二进制消息序列的输入为：,C A D A C D B。,新的当前区间范围为：0.5-0.7,新区间宽度：A,=1,0.2,=0.2,第2个符号,A:,新区间起点：C,=0.5+0.2,0,=0.5,新区间宽度：A,=0.2,0.1,=0.02,终点：0.5+0.02=0.52,新的当前区间为：0.5-0.52,2024/8/9,102,二进制消息序列的输入为：,C A D A C D B。,当前区间为：0.5-0.52,新区间宽度：A,=0.2,0.1,=0.02,第3个符号,D:,新区间起点：C,=0.5+0.02,0.7,=0.514,新区间宽度：A,=0.02,0.3,=0.006,终点：0.514+0.006=0.52,新的当前区间为：0.514-0.52,2024/8/9,103,二进制消息序列的输入为：,C A D A C D B。,当前区间为：0.514-0.52,新区间宽度：A,=0.02,0.3,=0.006,第4个符号,A:,新区间起点：C,=0.514+0.006,0,=0.514,新区间宽度：A,=0.006,0.1,=0.0006,终点：0.514+0.0006=0.5146,新的当前区间为：0.514-0.5146,2024/8/9,104,二进制消息序列的输入为：,C A D A C D B。,新的当前区间为：0.514-0.5146,新区间宽度：A,=0.006,0.1,=0.0006,第5个符号,C:,新区间起点：C,=0.514+0.0006,0.5,=0.5143,新区间宽度：A,=0.0006,0.2,=0.00012,终点：,0.5143+0.00012=0.51442,新的当前区间为：0.5143-0.51442,2024/8/9,105,二进制消息序列的输入为：,C A D A C D B。,新的当前区间为：0.5143-0.51442,新区间宽度：A,=0.0006,0.2,=0.00012,第6个符号,D:,新区间起点：C,=0.5143+0.00012,0.7,=0.514384,新区间宽度：A,=0.00012,0.3,=0.000036,终点：,0.514384+0.000036=0.51442,新的当前区间为：0.514384-0.51442,2024/8/9,106,二进制消息序列的输入为：,C A D A C D B。,新的当前区间为：0.514384-0.51442,新区间宽度：A,=0.00012,0.3,=0.000036,第7个符号,B:,新区间起点：C,=0.514384+0.000036,0.1,=0.5143876,新区间宽度：A,=0.000036,0.4,=0.0000144,新的当前区间为：0.5143876-0.514402,最终编完的码字是 0.5143876,2024/8/9,107,2024/8/9,108,根据,传输,CADACDB,，共,7,个符号,取,13,位,最终编完的码字是,0.5143876,变换的二进制为,0.10000011101011,所以传输的码流为,1000001110110,压缩率为：,14/13=1.1:1,2024/8/9,109,假设信源符号为 A，B，C，D，,符号的概率分别为 0.1，0.4，0.2，0.3，,传输数据序列为：B C B D A，,求算术编码及其编码效率。,2024/8/9,110,A，B，C，D，,概率 0.1，0.4，0.2，0.3，,A，B，C，D,概率 0.1 0.4 0.2 0.3,累积概率 0 0.1 0.5 0.7,2024/8/9,111,传输数据序列为：,B C B D A,B:,C=,0+1,0.1=0.1,A,=1,0.4=0.4,C:,C,=0.1+0.4,0.5=0.3,A=0.4,0.2=0.08,B:,C,=0.3+0.08,0.1=0.308,A,=0.08,0.4=0.032,D:,C,=0.308+0.032,0.7=0.3304,A,=0.032,0.7=0.0096,A:,C,=0.3304+0.0096,0=0.3304,A,=0.0096,0.1=0.00096,2024/8/9,112,输出：,0.3304,换为二进制数，取的位数为：,所以最终输出为：,0101010010,编码效率为：,2024/8/9,113,算术编码,算术编码的优点：,渐近最佳性-,当序列无限增长时，平均码长将渐近地等于序列的信源熵值.,算术编码具有比哈夫曼编码更好的压缩率,2024/8/9,114,算术编码,在算术编码中有几个问题需要注意：,一、算术编码器对整个消息只产生一个码字，这个码字是在间隔,0,，,1,中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。,二、算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,2024/8/9,115,4.4 限失真图像压缩编码方法,在有损图像编码方法中，允许有一定的失真存在，压缩了信源熵，提高压缩比。,有损压缩经常压缩图像和视频等。,在这一节，我们讨论常用的一些图像信号的有损压缩技术。,2024/8/9,116,有损图像压缩编码,预测编码,预测编码主要是减少图像在,时间上,和,空间上,的相关性。,2024/8/9,117,有损图像压缩编码,预测编码,预测编码就是用已经传输的样本值对当前的样本值进行预测，然后对实际的样本值与预测值的,差值（预测误差）,进行编码处理和传输。,2024/8/9,118,预测编码,预测编码分为两类：,帧内预测,：,预测可以在一帧图像内进行。,针对一幅图像的空间冗余,帧间预测,：预测在多帧图像之间进行。,针对活动图像的时间冗余,2024/8/9,119,预测编码,帧内预测,帧内预测编码是针对一幅图像，减少其空间上的相关性来实现数据压缩的。,通常采用差分脉冲编码调制(DPCM)来实现。,2024/8/9,120,图中,x,(,n,)为采样的图像数据，为,x,(,n,)的预测值，,是实际值和预测值的差值，,是,d,(,n,)的量化值，量化的过程会引入量化噪声。,是引入量化误差的,x,(,n,)。,2024/8/9,121,差分脉冲编码调制,(DPCM),在图像信号中应用DPCM时，用作预测的像素和被预测的像素可以在同一行，也可以在不同行（同一帧），分别称为：,一维预测：,用作预测的样值都与被预测的样值在同一行内。,二维预测：,用作预测的样值位于相邻的不同行上。,2024/8/9,122,用作预测的样值均与被预测的样值在同一行内(如,x1,x2与X),称为一维预测;,用作预测的样值位于相邻的不同行上时(如,x1,x2，x3,x4,与,X,)则称为二维预测。,被预测像素,2024/8/9,123,一维预测利用了像素之间在水平方向上的相关性。,一阶的一维预测值为：黑电平 预测误差大,五阶的,二维预测,的预测值：,2024/8/9,124,差分脉冲编码调制(DPCM),优点：,算法简单，容易硬件实现,缺点：,对信道噪声很敏感，会产生误差扩散。,压缩率比较低。,2024/8/9,125,预测编码,帧间预测编码,帧间预测编码,是利用视频图像帧间的相关性，即时间相关性，来达到图像压缩的目的。,广泛用于普通电视、会议电视、视频电话、高清晰度电视的压缩编码。,2024/8/9,126,动态图像以每秒25(30)帧播放，在如此短的时间内，画面通常不会有大的变化；,在画面中变化的只是运动的部分，静止的部分往往占有较大的面积；,即使是运动的部分，也多为简单的平移,2024/8/9,127,活动图像预测编码,帧间预测编码,帧间预测：,不直接传送当前帧的像素值,x,，而是传送,x,和其前一帧或后一帧的对应像素,x,之间的差值,e=x-x,。,2024/8/9,128,活动图像预测编码,帧间预测编码,估计出云朵运动的方向和速度（位移矢量），可以从云朵在k-1帧的位置推算出它在k帧中的位置来，而背景图像仍以前一帧的背景代替。,预测误差小。,k-1帧 k帧,背景区,活动物体,2024/8/9,129,活动图像预测编码,帧间预测编码,活动图像帧间预测编码分为两种：,一、具有运动补偿的帧间预测,二、帧间内插,2024/8/9,130,具有运动补偿的帧间预测,对运动区域进行预测：,首先要估计出运动物体的运动矢量D,然后再根据运动矢量进行补偿，即找出物体在下一帧的区域位置。,2024/8/9,131,具有运动补偿的帧间预测,将考虑了运动物体位移矢量D的k-1帧图像作为k帧的预测值，预测误差会变小，从而可以达到更高的数据压缩比。这种预测方法称为具有运动补偿的帧间预测。,在帧间预测中引入运动补偿的目的：,减少预测误差，提高编码效率。,2024/8/9,132,具有运动补偿的帧间预测编码是视频压缩的关键技术之一。,它包括以下几个步骤：,一、图像划分：,将图像分解成相对静止的背景和若干个运动的物体，各个物体可能有不同的位移，但构成每个物体的所有像素的位移相同。,二、运动检测与估值：,对每一个运动物体进行运动估值，得到每个物体的运动位移矢量D,2024/8/9,133,三、运动补偿：,利用位移矢量D计算经运动补偿后的预测值,四、预测编码：,对实际值与运动补偿预测值的差值（预测误差）进行量化、编码、传输。,2024/8/9,134,具有运动补偿的帧间预测,运动估值,提取位移矢量D,t时刻运动物体的像素值（亮度，彩色）,b,t,可以用在此之前,时间的像素值,b,t-,来表示。这两个像素点坐标值之差被称为位移矢量D：,b,t,（z)=,b,t-,(z-,D),上式表示，,t,时刻,z,位置的像素是,t-,时刻,z-D,位置的像素,时间运动了矢量D后的结果。,2024/8/9,135,运动补偿,运动估值,通常采用的运动矢量估值方法主要分为两大类：,像素递归法PRA,块匹配法BMA,像素递归法PRA：精度高 算法复杂,2024/8/9,136,运动估值,块匹配法,SMA,原理：,它将图像划分为许多N,N像素的子块，每块看成是一个物体。并认为子块内所有像素的位移量是相同的，这意味着将每个子块视为一个,“,运动物体,”,。,目前实用的活动图像压缩标准中(如H.261、MPEG等)都选择,16,16或8,8,大小的图像子块。,2024/8/9,137,运动估值,块匹配法,SMA,原理：,对于当前的图像帧中的某一子块,B,，如果在另一时间帧中可以找到与其最为相似的子块,B*,，称为,匹配块,（最相似块），并认为该子块,B,是匹配块,B*,位移后得到的结果。,通过B和B*的坐标位置便可以确定位移矢量D。,2024/8/9,138,块匹配法BMA,精度低于,像素递归法,PRA，,但其位移跟踪能力强（不低于67像素/帧），,实现简单，尤其适合于物体作平移运动，因此应用很广泛。,它在活动图像压缩标准H.261、H.263、MPEG-1、MPEG-2及 MPEG-4等国际标准中都被采用。,2024/8/9,139,具有运动补偿的帧间预测,具有运动补偿的帧间预测分为三种预测方式：,前向预测,后向预测,双向预测,2024/8/9,140,具有运动补偿的帧间预测,前向预测：,帧间预测方法是由第k-1帧来预测第k帧图像的预测方式,这种方式就是,前向预测,。,后向预测：,如果待预测的子块是在第k帧，而搜索区处于第k+1帧。也就是从后续的k+1帧图像预测之前的第k帧图像,这种预测方法称为,后向预测,。,2024/8/9,141,双向预测：,预测误差小,传输的数据率低。压缩比大,2024/8/9,142,双向预测：,对于k帧中的子块,先从k-1帧中找到它的最佳匹配块,从而得到该子块从k-1到k帧的位移矢量Dl,再利用后向预测得到它从k+1到k帧的位移矢量D2,二者的平均值作为k帧子块的预测值。,进一步降低预测误差。,2024/8/9,143,帧间预测,双向预测,双向预测所付出的代价是：,对每一个子块需要传送2个位移矢量D1、D2给收端,而且k帧的恢复必须等到接收到k+1帧之后才能进行。,解码运算的帧顺序是：k-1帧、k+1帧、k帧,而图像显示的顺序是k-1、k、k+1。,要保持显示的连续性,需要多引入1帧的延时。,2024/8/9,144,帧间预测,活动图像帧间内插,在,具有运动补偿的帧间预测编码系统中，图像的传输帧率并没有变化，仍与编码前的帧率一样。,2024/8/9,145,帧间预测,活动图像帧间内插,在某些应用场合如：,可视电话、视频会议,活动很慢的图像，对图像传输帧率的要求可适当降低，可以少传一些帧。,2024/8/9,146,活动图像的帧间内插,对于静止图像或活动很慢的图像，可以少传一些帧，如进行隔帧传输。,未传输的帧，可以利用接收端的帧存储器中前一帧的数据作为该帧数据，以防止帧频下降引起图像的闪烁和动作不连续。,广泛应用于视频电话、视频会议系统中。,其图像帧速率一般为1-15帧/秒。,2024/8/9,147,活动图像的帧间内插,存在的问题：,当图像中存在运动物体时,出来的结果与真实运动轨迹存在误差,从视觉效果来看，即存在图像模糊现象。,2024/8/9,148,具有运动补偿的帧间内插,即要确定运动物体在丢弃帧中的位置,估计出该物体的运动方向和速度-位移矢量D。,这种方法可以有效的降低图像模糊现象。,2024/8/9,149,具有运动补偿的帧间内插,具有运动补偿的帧间内插和帧间预测都需要进行运动估值.,但二者的目的以及运动估值不准确所带来的影响不相同。,帧间内插运动补偿,与,帧间预测的运动补偿,区别？,2024/8/9,150,帧间预测的运动估值,在帧间预测中引入运动补偿的目的是为了减少预测误差，从而提高编码效率。,运动估值的不准确会使预测误差加大，从而使传输的数据率上升。压缩率下降。,接收端根据此位移矢量和预测误差进行解码并不会引起图像质量下降。,帧间预测的运动估值多采用,块匹配法,。,2024/8/9,151,帧间内插的运动估值,在帧间内插中引入运动补偿的目的，是使恢复的内插帧中的运动物体不致因为内插而引起图像质量太大的下降，导致图像模糊现象。,2024/8/9,152,帧间内插的运动估值,帧间内插中的位移矢量估值一般要对运动区的每一个像素进行，而不是对一个子块；否则帧间内插同样会引起运动物体边界的模糊现象。,因此在帧间内插的运动估值较多使用能够给出单个像素位移矢量的,像素递归法,。,2024/8/9,153,限失真图像压缩编码,变换编码,如果对图像数据进行某种形式的正交变换,并对变换后的数据进行编码,从而达到数据压缩的目的,这就是变换编码。,变换编码是一种有效的图像压缩方法,它是所有有损压缩国际标准的基础。,2024/8/9,154,变换编码,变换编码不直接对原图像信号压缩编码,而首先将图像信号从,空间域（或时间域）,映射到另一个域,变换域（或频率域）,中。,产生一组变换系数。,然后对这些系数进行量化、编码、传输。,2024/8/9,155,变换编码,预测编码是在空间域（或时间域）内进行的。,变换编码则是在,变换域（或频率域）内进行的。,2024/8/9,156,变换编码,在,变换域（或频率域）:,能量主要集中在低频部分,变换后的变换系数之间的相关性大大降低。,2024/8/9,157,变换编码,图像变换编码一般利用了视觉心理编码。,一、分块：,目的减小运算量。,将原始图像分成,“,若干个子像块,”,然后对每个子像块进行变换。,一般子图像块的大小选为,8,8或16,16。,2024/8/9,158,变换编码,对图像进行子块划分的另一个好处是:,可以将传输误差所造成的图像损伤限制在子图像的范围之内,从而避免误码的扩散。,2024/8/9,159,变换编码,二视觉心理编码,对每一个变换系数或主要的变换系数进行量化和编码。,量化特性和编码的比特数是由人的视觉特性确定的。,人眼对不同频率分量的敏感程度是不同的,2024/8/9,160,变换编码,二、,视觉心理编码,对不同频率系数采用不同的量化台阶，以进一步提高压缩比：,低频系数采用的量化台阶小，编码的比特多；高频系数采用的量化台阶大，编码的比特少。,2024/8/9,161,变换编码,变换编码的基本思路：,在编码时略去某些能量很小的高频分量，或在量化时对能量较小的分量分配较少的比特数，以降低码率。,在接收端经解码、反量化后得到带有一定,量化失真,的变换系数,再经反变换就可恢复图像信号。,变换编码也是一种有损压缩编码。,2024/8/9,162,基本原理,子块,1,子块,2,子块,n,.,.,正变换,滤波,量化,编,码,信道,解,码,逆变换,综合,拼接,源图像（发送）,恢复图像（接收）,变换编码,系统原理图,2024/8/9,163,正交变换的类型,变换编码中的关键技术在于,正交变换。,正交变换的变换核,(,变换矩阵,),是可逆的,且逆矩阵与转置矩阵相等,能够保证解码运算有解且运算方便。,所以变换编码总是选用正交变换来做。,2024/8/9,164,正交变换的种类：,傅氏变换,沃尔什变换,哈尔变换,离散余弦变换,离散正弦变换,K-L,变换,小波变换,2024/8/9,165,离散余弦变换,(DCT),正变换：变换系数,逆变换：,2024/8/9,166,f,(x,y)实质上是8,8像素的空间图像（64个抽样值），DCT将其变换成64个正交基信号，是f(x,y)的64个DCT系数。F(u,v)可以表示为,2024/8/9,167,DCT,变换可以看成是一个谐波分析器，把,f(x,y),分解成为,64,个正交的信号，分别代表着,64,种不同频率成分。,DCT,系数即基信号振幅,2024/8/9,168,方阵中的每个数值不再表示信号在像素点的振幅,而是表示一个,DCT,系数。,能量集中在少数几个低频系数上。,可忽略,2024/8/9,169,图像信号的能量都集中在低频成分中。,中频和高频的系数会很小或者为0值。,离散余弦变换把信号的能量聚集在最小的空间频率内了。,DCT系数矩阵,低頻,中頻,高頻,DC,2024/8/9,170,离散余弦变换,(DCT),总结,：,在数据压缩过程中把中间频率和高频的系数忽略,而只保留低频的系数。这样就可以大大减少数据量,实现数据压缩。,2024/8/9,171,DCT变换编码过程,DCT,变换,DCT,逆变换,原图像,除以量化矩阵,取整,1,）编码过程：,2,）解码过程：,压缩图像,乘以量化矩阵,取整,压缩,图像,解压,图像,量化,2024/8/9,172,DCT,变换编码,-,量化,DCT变换输出的数据F(u,v)还必须进行量化处理。,注意：,在量化之前,并没有发生数据丢失。,如果这时将图像以DCT系数形式传送或保存,然后再逆向变换,原始图像可以准确地再现。,是无损变换。,2024/8/9,173,DCT,变换编码,-,量化,量化的目的：,减少DCT系数的幅值，增加系数的零值个数，来压缩数据。,“,量化处理,”,是压缩编码过程中图像信息产生失真的主要原因。,2024/8/9,174,DCT,变换编码,-,量化,量化：采用均匀量化。,但每个系数的量化台阶不同。,量化方法：,用一个预定义的值去除每个DCT系数来对其标准化。,这些预定义的值称为量化步长。即量化台阶。,事先存放在一个称为量化步长表的8,8方块中。,也称之为,“,量化矩阵,”“,量化步长表,”,2024/8/9,175,DCT,变换编码,-,量化,例：,原图像为：,DCT,变换,除以量化矩阵，取整,2024/8/9,176,DCT,变换编码,-,量化,人眼对亮度信号比对色差信号更敏感，因此使用了两种量化表：,亮度量化步长表,色差量化步长表,2024/8/9,177,JPEG,标准所推荐的亮度量化表,