数据压缩技术PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章,多媒体技术,MULTIMEDIA TECHNOLOGY,1,第,5,章,多媒体数据压缩技术,5.1,数据压缩基本原理,5.1.1,信息、数据与编码,5.1.2,数据压缩的条件,5.1.3,数据冗余,5.2,数据压缩算法,5.2.1,数据压缩算法分类,5.2.2,预测编码原理,5.2.3,变换编码原理,5.2.4,统计编码原理,5.2.5,霍夫曼编码原理,5.2.6,行程编码原理,5.2.7,算术编码原理,5.2.8 LZW,压缩编码,5.3,静态图像,JPEG,压缩编码技术,5.3.1 JPEG标准的由来,5.3.2 JPEG,压缩算法,5.3.3,无失真预测编码,5.3.4,有失真,DCT,压缩编码,5.4,动态图像,MPEG,压缩编码技术,5.4.1,基本原理,5.4.2 MPEG,技术标准,2,数据压缩基本原理,5.1,数据压缩的对象是数据。数据是信息的载体，用来记录和传送信息。真正有用的不是数据本身，而是数据所携带的信息。大的数据量并不代表含有大的信息量。,而对于去掉冗余的数据对信息没有本质的影响称为压缩。,数据压缩,原理,3,5.1.1,信息、数据与编码,我们了解的东西，描述它用的信息量少，不了解的东西，描述它用的信息量大。,在信息论中，可以说：信息是用不确定的度量来定义的；一个消息的可能性越小，其信息含量越大；消息的可能性越大，则信息含量越小。,例,自然现象,4,数据压缩基本原理,5.1,5.1.1,信息、数据与编码,1,信息和熵,信息量的大小和消息有一定的关系。在数学上，消息是其出现概率,的单调下降函数。信息量越大，消息的可能性越小，反之亦然。,信息量：为了从,N,个相等的可能事件中挑选出一个事件所需的信息,度量和含量，所提问,“,是或否,”,的次数。也就是说，在,N,个事件中辨,识特定的一个事件要询问,“,是或否,”,次数。,要从,256,个数中选定某一个数，可以先提问“是否大于,128,？”，不论,回答是与否，则半数的可能事件被取消。如果继续询问下去，每次,询问将对应一个,1bit,的信息量。,例,5,例,随着每次询问，有半数的可能事件被取消，这个过程由公式表示：,可看出：对于,256,个数的询问只要进行,8,次，即可确定一个具体的数。,设,：从,N,个数中选定任意一个数,x,的概率为,p,(,x,),，假定选定任意一个数,的概率都相等，即,p,(,x,)=1/,N,，则信息量为：,log,2,256=8 bit,如果将信息源所有可能事件的信息量进行平均，即可得到信息的“,熵,”,(,熵,是平均信息量,),，信息源,X,的符号集为,x,i(,i,=1,2,N,),。,设：,x,i,出现的概率为,p,(,x,i),，则信息源,X,的熵为：,Ix,)=log,2,N,=-log,2,1,N,=-log,2,p,(,x,)=,I,p,(,x,),H,(,x,)=,P(x,i,),log,2,p,(,x,i,),P(x,i,)I p(x,i,),=-,n,i=1,n,i=1,6,信息与数据,2.,信息可以用函数表示，该函数由信息论创始人,C.E.Shannon,香农,提出，,以概率论的观点对信息进行定量描述，具体的信息函数表达式为：,I,(,a,i,)=-log,2,P,i,(,i,=1,2,r,),公式中，,P,i,(i,=1,2,r,),是随机消息组合,X,a,1,a,2,a,r,中的,消息,a,i,(i,=1,2,r,),的先验概率。,P,i,可以度量,a,i,(i,=1,2,r,),所含的信息量。,而,I(,a,i,)(,i,=1,2,r,),在,X,的先验概率空间,P,p,1,p,2,p,r,中的,统计平均值为信息源,X,的熵：,信息源,X,的熵用来度量,X,中每种消息所包含的平均信息量。信息熵,主要表示信息系统的有序程度，而不是热力学中系统的无序程度。,H,(,X,)=,H,p,1,p,2,p,r,=-,P,i,log,2,p,i,n,i=1,7,例,2-1,设信源有,16,种符号，其出现的概率相同，即,P,（,X,i,）,=1/16,。计算其平均信息熵。,例,8,例,2-2,某信源有,8,种符号，其出现的概率如下：,例,9,信源中含有自然冗余度，这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性，,只要找到去除相关性或改变概率分布不均匀性的手段和方法，也就找到了信息熵编码的方法,。,但信源所含有的平均信息量（熵）是进行无失真编码的理论的极限，,只要不低于此极限,，,就能找到某种适宜的编码方法,，去逼近信息熵，实现数据压缩。,香侬理论的要点,2.,10,多媒体信息的数据量,3.,1),文本,假设屏幕显示分辨率为,1024768,，字符为,1616,点阵，,每个字符用,4,个字节表示，则显示一屏字符所需要的存储空间为：,（,1024/16,）,（,768/16,）,4 B=12288 B,（约合,12KB,）,2),图像,假定图像显示在,1024768,分辨率的屏幕上，则满屏幕,像点所占用的空间为：,1024768log,2,256=768 KB,3),音频,假定模拟声音频率,22050 Hz,，其数字采样频率,44100 Hz,，,采样精度为,16bit,，双声道立体声模式，则,1min,所需数据量为：,44100Hz2B(16bit,采样精度,)2(,双声道,)60s=10 MB/min,4),视频,采用带宽为,5MHz,的,PAL,制视频信号，扫描速度,25,帧,/s,，,样本宽度,24bit,，采样频率最低,10MHz,，则一帧数字化图像所占用的,最少存储空间为10(,采样频率,)25(,扫描速度,)24(,样本宽度,)=9.6Mbit(,合,1.2 MB),11,考虑,一,张,640,480,的全彩影像,640,480,3,8=,7,372,800,Bits,调制解调器,(,Modem,),为,36Kbps,7372800/36000=204.8(sec)=3.41(min),假设压缩算法,(,JPEG,),的压缩,率,为,1:,12,(7372800/12)/36000=17.1(sec),对图片压缩,效果,较,好，但,对,色彩,单纯的图形,則,效果一般不很理想。,例,12,数据压缩的条件,5.1.2,数据冗余度,(,重复数据、可忽略数据,)信息传输与存储的限制,(,压缩 传输或存储 解压缩,),44.1kHz/Stereo,1.3MB,22.0kHz/Mono,0.3MB,Stop,重复数据,可忽略数据,人类不敏感因素,(,颜色、亮度、细节等,),2,24,颜色,(16,777,216,色,),2,8,颜色,(256,色,),音频不敏感因素,(,试听,),颜色,不敏感因素,13,数据冗余,5.1.3,冗余基本概念,冗余,信息所具有的各种性质中多余的无用空间,冗余度,多余的无用空间的程度,I=D,du,I,信息量,D,数据量,du,冗余量，包含在,D,中,信息量与冗余的关系,冗余举例,播音员,180,字,/,分钟，,2Byte,一个字，,360Byte,(,合,0.35KB,/,分钟,),音频数据,8kHz,采样,8bit60,秒,=3840KBit(,合,480KB,/,分钟,),14,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,15,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,16,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,17,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,18,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,1011 0001 1100,1011 0001 1100,0101 1010 1010,1011 1100,0101 1111 1010,19,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,2,24,色,2,8,色,20,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,印度金庙泰姬陵,21,冗余分类,1,空间冗余,规则物体的物理相关性,2,时间冗余,视频与动画画面间的相关性,3,统计冗余,具有空间冗余和时间冗余,6,视觉冗余,视觉、听觉敏感度和非线性感觉,7,知识冗余,凭借经验识别,4,结构冗余,规则纹理、相互重叠的结构表面,5,信息熵冗余,编码冗余，数据与携带的信息,8,其他冗余,上述,7,种以外的冗余,声音频率,文字组句,色彩渐变,主观意识,:,:,22,数据压缩算法,5.2,5.2.1,数据压缩算法分类,无损压缩编码,压缩数据还原后，与,原始数据一致，无损失。,(,可逆编码,),霍夫曼编码,行 程 编 码,算 术 编 码,有损压缩编码,压缩后再还原的,数据有损失。,(,不可逆编码,),预测编码,变换编码,统计编码,行程编码,算数编码,LZW,编码,压缩比：,2:1,5:1,压缩比：,1,：,100,23,视频压缩算法结构图,视频,压缩,无损,压缩,有损,压缩,霍夫曼编码,行程编码,算术编码,LZW,编码,预测编码,变换编码,模型编码,基于重要性,混合编码,DPCM,ADPCM,运动编码,DCT,变换,小波变换,子带编码,分形变换,滤波,子采样,矢量量化,H.261,MPEG,24,预测编码原理,5.2.2,预测编码,有损压缩编码，主要对统计冗余进行压缩。,1,预测编码的基本原理,用原样本值对新样本进行预测，得到新样本的预测值。接着，取新,样本的实际值和预测值进行比较，二者相减得到差值，然后对差值,进行编码。,2,预测编码的应用,预测编码用于图像的传输和存储。对于连续的多帧图像，新一帧通,常保留前一帧的部分内容。首先存储当前内容，如像点、帧或线。,然后与下一帧图像进行比较（预测），把不同点存储或传输，而相,同点则是数据冗余，予以剔除。,对于语音，就是通过预测去除语音信号时间上的相关性。例如语音中,的,LPC(linear Predictive Coding,，线性预测,),。,例,25,变换编码原理,5.2.3,变换编码,(Transform coding),有损压缩编码，用于对统计冗余,(,图像数据,),的压缩。,工作原理,首先对时域上的信号进行,函数运算,，并变换到频域上，,然后在频域上对变换后的信号进行编码。在频域上，,信息是按照频谱的能量和频率分布进行排列的。,卡胡南,劳埃夫变换,离散傅里叶变换,离散余弦变换,WHT,变换,例如，声音中的频谱分析实际上是对语音波形进行了,快速傅里叶变换（,FFT,）,，将时域信号变到了频域中，可以清楚地看到能量集中在哪些频率范围内。,例,26,5.2.4,统计编码原理,统计编码,无损压缩编码。根据消息出现的概率分布特性，在消息和码字之间确定严格的对应关系，以便准确无误地恢复数据。,一般而言，图像中某些数据出现概率比较高，而另一些出现概率较低。对出现概率高的数据分配短码，对出现概率低的数据分配长码。此种方式不舍弃数据冗余，只改变编码分配的长度，因此总数据流量降低。,27,霍夫曼编码原理,5.2.5,霍夫曼编码,无损编码。,编码特点,1,编码长度可变，压缩与解压缩较慢。,2,硬件实现困难。,3,编码效率取决于信号源的数据出现概率。,编码原理,出现频率高的数据编码长度短，反之亦然。,1,信号源的数据按照出现概率递减的顺序排列。,2,合并两个最小出现概率，作为新数据出现概率。,3,重复进行,12,，直至概率相加为,1,为止。,4,合并运算时，概率大者取,0,，概率小者取,1,。,5,记录概率为,1,处到信号源的,0,、,1,序列。,28,设信号源为,X=,、,a,、,e,、,I,、,m,、,t,、,c,、,h,、,r,。,对应的概率为,p=O.22,、,0.22,、,0.14,、,O.07,、,0.07,、,0.07,、,0.07,、,0.07,、,0.07,试给出该信源的霍夫曼编码方案。,解：,若传送一个串字符串,“,I am a teacher,”,，共,14,个字符。若用,ASCII,传送，每个字符,8,位，共需,112,位。该字符串中有,9,个不同的符号，至少需要,4,位二进制才能表示，这样传送该字符串也要,56,位。若用刚计算的,Huffman,编码，只需要,42,位。,霍夫曼编码举例,29,霍夫曼编码过程,可以得到：,a,的编码,00 e,的编码,111 I,的编码,1101 m,的编码,1100,t,的编码,1011 c,的编码,1010 h,的编码,1001 r,的编码,1000,原字符串（二进制）长度：,=112,（,148,）位,Huffman,编码长度：,=42,位,（,01 00 111 1101 1100 1011 1010 1001 1000,）,30,行程编码原理,5.2.6,行程编码（,Run Length Coding,）,无损压缩编码。,例,一个字符串：,5 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 1,行程编码：,(5,6)(7,5)(3,3)(2,4)(1,7),可见，行程编码的位数远远少于原始字符串的位数。,基本原理,用一个符号值或串代替具有相同值的连续符号，使符号长度少于,原始数据的长度。,在对图像数据进行编码时，沿一定方向排列的，具有相同灰度值的,像素被看成是连续符号，并用字串代替这些连续符号，可大幅度减,少数据量。,31,设有数据流,“,AAABBBBCCCCCDAAAAAA,”,，试计算该数据的行程编码。,解：,A,重复,3次，,B,重复,4,次，,C,重复,5,次，,D,不重复，,A,重复,6,次，,RLC,数据流为,：,“,SA3SB4SC5DSA6,”,，其中,S,为指示符。总共占用,13,个字节，而源数据占用,19,个字节。,有时行程编码不用指示符，重复与否相同对待，则相应的,RLC,为,“,A3B4C5D1A6,”,占用,10,个字节。,例,32,算术编码原理,5.2.7,算术编码,无损压缩编码，属于统计编码。,20,世纪,60,年代由,Elias,提出，某些方面优于霍夫曼编码。因此，,在,JPEG,标准的扩展系统中，算术编码已经取代了霍夫曼编码。,基本原理,将被编码的信息表示成实数轴上,0,和,1,之间的间隔，信息越长，间隔越小，,表示这一间隔所需的二进制位数就越多。,特点,1),算术编码有基于概率统计的固定模式，也有相对灵活的自适应模式。,2),自适应模式适用于不进行概率统计的场合。,3),当信号源符号的出现概率接近时，算术编码的效率高于霍夫曼编码。,4),算术编码的实现相应地比霍夫曼编码复杂，但在图像测试中表明，,算术编码效率比霍夫曼编码效率高,5,左右。,33,LZW,压缩编码,5.2.8,LZW,（,Lempel Ziv Welch,）无损压缩编码，用于图像数据的压缩。,LZW,（,Lempel Ziv Welch,）是一种字典式无损压缩编码。,1977,年两位以色列教授,Lempel,和,Ziv,提出了查找冗余字符和用较短的符号标记替代冗余字符的概念。,1985,年美国人,Welch,将该技术发展到实际运用阶段，命名为,LZW,技术,。,LZW,把数据流中复杂的数据用简单的代码来表示，并把代码和数据的对应关系建立一个转换表（“字符串表”）。该转换表是在压缩或解压缩过程中动态生成的表,并用于压缩和解压缩过程中。,LZW,被广泛用于图像压缩领域。,34,LZW,压缩编码,基本原理,把复杂的数据用简单的代码表示，并把代码和数据的对应关系建立转换,表，又叫“字符串表”。转换表记录了代码和数据的对应关系。在压缩和,解压缩过程中，,LZW,压缩编码会生成两个完全相同的转换表，数据以严,格对应的方式被压缩和还原。,特点,1),对于可预测性不大的数据效果较好，常用于,GIF,格式的图像压缩。,2),对于数据流中连续重复出现的字节和字串，具有很高的压缩比。,3),被用于文本程序等数据压缩领域。,4),有很多变体，如常见的,ARC,、,RKARC,、,PKZIP,高效压缩程序。,5),压缩和解压缩速度较快，对硬件条件要求不高。,35,静态图像,JPEG,压缩编码技术,5.3,5.3.1 JPEG,标准的由来,1991,年，联合专家组提出了,ISO CD,建议草案,，后经过国际电子技术委员,会,ISO/IEC,的批准，正式成为第,10918,号标准，并正式命名为“,JPEG,高质,量静止图像压缩编码标准”，简称“,JPEG,标准”。,多灰度静止图像的数字压缩编码标准,计算机业内人士探寻一种压缩比大、图像质量高的压缩编码。在这种,背景下,压缩标准成为急待解决的问题。,1986,年,CCITT,和,ISO,共同成立了,JPEG,联合图像专家组，从事图像压缩的工业标准和学术意义的研究、探索。,提出了,ISO CD,建议草案、即多灰度静止图像的数字压缩编码标准。,36,JPEG,算法概述,JPEG,算法根据,人眼对亮度和颜色变化比较敏感的原理,，在对图像数据进行压缩时，只保存亮度和颜色变化的数据部分，而舍弃人眼不敏感的成分，以达到压缩的目的。,在图像还原时，并不重新建立原始图像，而是生成类似图像，该图像保留了人眼敏感的色彩和亮度。,JPEG,适合于连续色调、多级灰度、彩色或黑白图像的数据压缩。,37,JPEG,压缩算法,5.3.2,适用于连续色调、多级灰度、彩色或黑白图像的数据压缩。,无损压缩比：大约为,4:1,。,有损压缩比：在,10:1100:1,之间。不大于,40:1,时，还原的图像在色彩、,清晰度、颜色分布等方面与原始图像相比，误差不大，,基本上保持了原始图像的风貌。,特点,1),对图像进行帧内编码，每帧色调连续，随机存取。,2),在宽范围内调节图像的压缩比和保真度，解码器可参数化。,3),对图像进行压缩时，可随意选择期望的压缩比值。,4),对于硬件环境要求不高，只要有一般的,CPU,运算速度即可。,5),可运行四种编码模式：,DCT,顺序编码模式、,DCT,递增模式、无失真,编码模式和分层编码模式。,JPEG,算法更多,38,无失真预测编码,5.3.3,无失真预测编码,无损压缩，压缩比一般为,2:1,。,原始图像数据经过无失真,编码器进行预测编码，然,后把压缩图像数据存储在,介质中或传送出去。,在使用图像时，经过解码,器解码，建立与原始图像,一致的不失真图像。,原理,预测器,图像数据,熵编码器,码表说明,解码器,压缩图像数据,无失真编码器,还原图像数据,采用了简单的线性预测编码方法，,DPCM,压缩算法和霍夫曼压缩算法，,硬件容易实现，重新建立的图像质量与原始图像无差别。,特点,39,有失真,DCT,压缩编码,5.3.4,采用,DCT,（,Discrete Cosine Transform,）离散余弦变换的压缩算法。,1,DCT,离散余弦变换,原理,源图像在输入到编码器之前，被分割成一系列顺序排列的由,88,像点,构成的数据块，把原始采样数据中无符号整数转换成有符号整数，进,行正变换。,还原图像时，解码器输出端经过逆变换，重新建立图像。由于运算误,差和系数的量化，因而重建不很精确，与源图像存在差异。,2,DCT,系数的量化,量化依据量化表进行，量化表中的元素由开发人员根据人类视觉特性,制作。量化的定义：,C,Q(,u,v,)=Integer Round,F,(,u,v,)/,Q,(,u,v,),解量化是量化过程的逆运算，其公式为：,C,Q,(,u,v,)=,CQ,(,u,v,),Q,(,u,v,),40,有失真,DCT,压缩编码,5.3.4,3,图像的质量与压缩比,采用,DCT,算法存在失真，但是，只要量化表中的元素更科学、更,符合人类视觉敏感度，则压缩后的图像不会产生过大的视觉变化。,压缩结果,bit/,像素,图像质量的主观评价,假定某图像的像素采用,8bit,编码，则压缩结果和图像效果见下表。,1.5 2.0,0.75 1.5,0.5 0.75,0.25 0.5,色彩、灰阶过度、清晰度等与原始图像差别不大。,图像质量良好，灰阶过度和层次略感有损失。,图像质量中等，灰阶过度、层次、色彩稍差。,图像质量一般，色彩和灰阶与原始图像相比有明,显差别,41,动态图像,MPEG,压缩编码技术,5.4,5.4.1,基本原理,1,动态图像压缩主要解决的问题,1),正确区分静止图像和动态图像。,2),提取动态图像中的活动成分。,3),进行帧之间的预测，提供压缩的依据。,2,帧的预测编码,1),条件像素补充法,比较两帧对应位置的像素亮度，若亮度差超过预先规定的阀值，,则认为两个像素有变化，传送像素。若亮度差未超过阀值，不处理。,2),运动补偿法,跟踪画面上的活动元素，并进行向量计算，加以补偿，然后再,利用帧间预测进行压缩。适用于活动元素少的可视电话和电视会议。,42,图像的分类,3.,MPEG,标准根据处理图像的性质，把图像分成以下三类：,1),帧内图像（,Intra pictures,）,又称“,I,图像”，,JPEG,标准按照静止图像的模式进行压缩处理。,主要利用静止图像自身的相关性进行编码，实现数据压缩的目的。,帧内图像的压缩比属于中度压缩，典型的压缩像素编码为,2 bit,。,2),预测图像（,Predicted pictures,）,又称“,P,图像”，通过对最近的前一帧,I,图像或者,P,图像进行预测的,“前向预测”过程，把前面图像作为预测下一帧图像的参照物，使图像,编码的数据量减少。预测图像有较高的压缩比，但会增加失真。,3),双向图像（,Bidirestional pictures,）,又称“,B,图像”，可使用前一帧图像和后一帧图像作参照物，进行,双向预测。双向预测可以采用四种编码技术，即帧内图像编码、前向,预测编码、后向预测编码、双向预测编码。,43,MPEG,技术标准,5.4.2,MPEG-,标准,诞生于,1991,年，主要特点：,1),以,1.5Mb/s,的速率传输视频信号，即压缩信号带宽为,1.5Mb/s,。,2),以单通道,64kb/s,、,128kb/s,和,192kb/s,的传输速率传输音频信号。,3),可通过差值运算，在,352240,画面分辨率上显示活动图像。4),分三个组成部分：视频、音频和系统。,5),对于帧内图像，采用二维余弦变换、自适应算术编码、行程编码、,变字长编码，以及差分脉冲编码（,DPCM,）进行压缩。,6),帧间压缩采用运动补偿预测编码和运动补偿内插编码。,允许采用多种存储介质，如,CD-ROM,、数字录音带、磁盘、,CD-R,、,CD-RW,、,M.O.,，以及,ISDN,集成服务数字网络、,LAN,局域网络等。,设计,MPEG,压缩算法时，要考虑随机访问、快进快退、检索、声像,同步、容错、延时控制、可编辑特性以及视频窗口设置的灵活性等。,44,MPEG,技术标准,5.4.2,MPEG-,标准,主要特点,1),压缩信号带宽为,415Mb/s,，即信号传输速率为,415Mb/s,。,2),支持,NTSC,制,720480,画面分辨率，,PAL,制,720576,画面分辨率，,画面质量达到广播级，适用于,HDTV,高质量电视信号的传送与播放。,3),解码器同时支持,MPEG-,和,MPEG-,两种标准。,4),视频信号的传输速率为,30,帧,/s,，音频信号的质量达到,CD,级。,5),为了在画面质量、数据量和带宽之间寻求最佳值，允许在一定范围,内调整压缩比。,6),最高压缩比为,200:1,，但由于画面中活动内容的多少和人为调整压缩,比等因素的影响，大多数情况下达不到最高压缩比。,7)MPEG-,用于,DVD,视频信号的压缩，,DVD,音频信号的压缩随制式的,不同而不同：,PAL,制采用,MPEG-,；,NTSC,制采用,AC3,压缩标准。,45,第,5,章 多媒体数据压缩技术,小结,5.1,数据压缩基本原理,5.1.1,信息、数据与编码,5.1.2,数据压缩的条件,5.1.3,数据冗余,5.2,数据压缩算法,5.2.1,数据压缩算法分类,5.2.2,预测编码原理,5.2.3,变换编码原理,5.2.4,统计编码原理,5.2.5,霍夫曼编码原理,5.2.6,行程编码原理,5.2.7,算术编码原理,5.2.8 LZW,压缩编码,5.3,静态图像,JPEG,压缩编码技术,5.3.1 JPEG,标准的由来,5.32 JPEG,压缩算法,5.3.3,无失真预测编码,5.3.4,有失真,DCT,压缩编码,5.4,动态图像,MPEG,压缩编码技术,5.4.1,基本原理,5.4.2 MPEG,技术标准,46,习题五,5.1,数据压缩的理由有哪些？,5.2,什么是数据冗余？,5.3,冗余有多少种？分别是什么？,5.4,无损压缩编码指的是什么？,5.5,数据压缩具备哪两个过程？,5.6,霍夫曼编码的特点是什么？,5.7,采用,JPEG,压缩格式的静态图像具有哪些主要特点？,5.8,动态图像压缩主要解决哪些问题？,5.9 MPEG-,标准具有哪些主要特点？,47,香农,1948,年则创立了信息论,(information theory),。,克劳德,香农在公众中并不特别知名，但他是使我们的世界能进行即时通信的少数科学家和思想家之一。他是美国科学院院士、美国工程院院士、英国皇家学会会员、美国哲学学会会员。他获得过许多荣誉和奖励。例如,1949,年,Morris,奖、,1955,年,Ballantine,奖、,1962,年,Kelly,奖、,1966,年的国家科学奖章、,IEEE,的荣誉奖章、,1978,年,Jaquard,奖、,1983,年,Fritz,奖、,1985,年基础科学京都奖。,香农,克劳德,香农,(Claude Elwood Shannon,，,1916-2001)1916,年,4,月,30日诞生于美国密西根州的,Petoskey,。,2001,年,2,月,24,日，香农在马萨诸塞州,Medford,辞世，享年,85,岁。香农被信息界誉为信息论及数字通信时代的奠基人。,返回,48,Huffman,树的定义,构造,Huffman,树,Huffman,编码,Huffman(,哈夫曼）编码,49,Huffman,树也称为最优树，是一类带权路径最短的二叉树。,树的带权路径长度定义为：,WPL =w,k,l,k,k=1,n,其中：,n,树中叶结点的个数,w,i,第,i,个结点的权值,l,i,第,i,个结点的路径长度,Huffman,树的定义,50,以下有三棵树：,WPL,a,=,7x2+5x2+2x2+4x2,=36,WPLb=,7x3+5x3+2x1+4x2,=46,WPLc=,7x1+5x2+2x3+4x3,=35,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,（,a,）,（,b,）,（,c,）,a,b,c,d,a,b,c,d,a,c,b,d,7,7,7,5,5,5,2,2,2,4,4,4,Huffman,树举例,51,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数,0,59 60,69 70,79 80,89 90,100,比例数,0.05 0.15 0.40 0.3 0.10,根据正态分布规律，在,60,90,之间的分数占,85%,，而不及格和优秀是少数。,应用举例,52,判定树比较：,若输入,1,万个数据：,按,A,的判定过程进行操作，约需比较,3.2,万次,而按,B,比较,则仅需,2.2,万次。,a60?,a70?,a80?,a90?,不及格,及格,中等,良好,优秀,Y,Y,Y,Y,N,N,N,N,a80?,a70?,a90?,a60?,不及格,优秀,良好,中等,中等,及格,不及格,Y,Y,Y,N,N,N,N,Y,Y,(A),(B),将百分制转换成五分制,53,构造,Huffman,树算法步骤：,Step1,将,n,个带权值,w,i,（,in,）的结点构成,n,棵二叉树的集合,T=T,1,，,T,2T,n,，每棵二叉树只有一个根结点。,Step2,在,T,中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；,Step3,在,T,中删除这两棵树，将新构成的树加入到,T,中；,Step4,重复,2,）、,3,）步的操作，直到,T,中只含一棵树为止，该树就是,Huffman,树。,构造,Huffman,树,54,以权值分别为,7,，,5,，,2,，,4,的结点,a,、,b,、,c,、,d,构造,Huffman,树。,T=a b c d,c,d,T,3,2,4,6,b,T,3,T,2,6,5,11,b,T,2,6,5,11,c,d,2,4,18,a,T,2,7,11,T,1,6,18,a,7,T,1,b,T,3,T,2,5,11,18,a,7,T,1,b,5,11,c,d,2,6,4,（,d,）,T=T,1,（,c,）,T=a T,2,（,b,）,T=a b T,3,（,a,）,T=a b c d,代入,T,2,代入,T,3,代入,T,1,示例,构造,Huffman,树举例,55,编码：用二进制数的不同组合来表示字符的方法。,前缀编码：一种非等长度的编码,(,任一个字符的编码都不是另一个字符编码的前缀,),。,Huffman,编码：一种非等长度的编码。以给定权值的结点构造,Huffman,树，按二进制前缀编码的方式构成的编码为,Huffman,编码。,a,0,b,0,1,c,d,0,1,1,编码：,a,（,0,）,b,（,01,）,c,（,011,）,d,（,111,）,方法约定：,1,）左分支为,0,2,）右分支为,1,3,）,由叶到根,路径上字符组成的二进制串就是该叶结点的编码。,Huffman,编码,56,在某系统的通信联络中可能出现,8,种字符，其频率分别为,0.05,、,0.29,、,0.07,、,0.08,、,0.14,、,0.23,、,0.03,、,0.11,，设权值分别为,5,，,29,，,7,，,8,，,14,，,23,，,3,，,11,，,n=8,，其,Huffman,树为：,0,0,0,0,0,0,01,1,1,1,1,1,1,5,3,7,8,14,29,11,23,42,58,100,Huffman,编码为：,A 5 0110,B 29 01,C 7 0111,D 8 1111,E 14 011,F 23 00,G 3 1110,H 11 010,返回,Huffman,编码举例,57,JPEG,算法的四种编码模式,1)DCT,顺序编码模式,基本操作模式，也称基本系统，所有,JPEG,编码解码器都必须支持基本系统，采用二维余弦变换的编码方案。,2)DCT,递增模式，该模式又叫累进模式。,3),无失真编码模式。,4),分层编码模式。,基线编码系统。,面向大多数有损压缩的应用，采用,DCT,变换压缩,。输入图像精度,8,位,/,像素,/,色，,顺序模式,，采用,Huffman,或算术编码；,扩展编码系统,。,为满足更广泛领域的应用而设置的，从低分辨率到高分辨率逐步递进传递的应用。输入图像精度,12,位,/,像素,/,色，,累进模式,，采用,Huffman,或算术编码；,独立编码系统,。,面向无损压缩的应用，采用无损预测压缩。输入图像精度,2-16,位,/,像素,/,色，顺序模式，采用,Huffman,或算术编码。,一个产品或系统必须包括对基线系统的支持。,JPEG,算法的三种压缩系统,58,顺序模式,累进模式,顺序模式和累进模式,59,有失真,DCT,压缩编码,采用,DCT,（,Discrete Cosine Transform,）离散余弦变换,的压缩算法。,1,DCT,离散余弦变换,原理,源图像在输入到编码器之前，被分割成一系列顺序排列的由,88,像点,构成的数据块，把原始采样数据中无符号整数转换成有符号整数，进,行正变换。,还原图像时，解码器输出端经过逆变换，重新建立图像。由于运算误,差和系数的量化，因而重建不很精确，与源图像存在差异。,2,DCT,系数的量化,量化依据量化表进行，量化表中的元素由开发人员根据人类视觉特性,制作。量化的定义：,C,Q(,u,v,)=Integer Round,F,(,u,v,)/,Q,(,u,v,),解量化是量化过程的逆运算，其公式为：,C,Q,(,u,v,)=,CQ,(,u,v,),Q,(,u,v,),60,正向离散余弦变换,(Forward Discrete Cosine Transform,，,FDCT),把空间域表示的图像变换为频率域表示的图像。,量化,DCT,系数,用加权函数对,DCT,系数进行量化，该加权函数对于人视觉系统是最佳的。,Huffman,编码,用,Huffman,可变字长编码器对量化系数进行编码。,译码或者叫做解压缩的过程与压缩编码过程相反。,有失真压缩三个步骤,61,DCT,变换是数字图像处理中的重要变换。但对于大尺寸的二维数值矩阵，若采用普通,DCT,变换，其花费的时间将是让人难以忍受甚至无法达到实用。,解决方案，关注快速,DCT,变换的算法研究。目前而言，,DCT,变换的快速算法有以下两种方式：,1,快速,FFT,算法,。直接利用,FFT,来实现,DCT,变换的快速算法。特点是实现相对较容易，但计算过程会涉及到,复数运算,。由于,DCT,变换前后的数据都是实数，而引入复数，显然是增加了运算量，也给硬件存储提出了更高的要求。,2,直接在实数域进行,DCT,快速变换,。显然，这种方法相比于前一种而言，计算量和硬件要求都要优于前者。,鉴于此，一般采用第二种方法来实现,DCT,变换的快速算法,。,DCT,变换存在的问题,62,DCT,变换是一种实数域变换，其变换核心为实数的余弦函数。变换