多媒体通信技术四-修订ppt课件

第四章视频信息压缩与处理,第四章视频信息压缩与处理,本章主要内容图像信号的相关特点图像处理方法各种实用编码常见的图像压缩编码标准,图像信号的相关特点,通常一幅图像中的各像素之间存在一定的相关性。在活动图像中，由于两幅相邻图像之间的时间间隔很短，因此这两幅图像信息中包含大量相关信息。这些就是图像信息中的冗余。,图像信号的相关特点,多媒体数据压缩的目的就是要去除图像信息中的大量冗余，同时又能保证图像的质量。一般针对不同类型的冗余信息，采取不同的压缩方法。,图像信息中存在的冗余分类,1空间冗余规则物体的物理相关性,2时间冗余视频与动画画面间的相关性,3统计冗余具有空间冗余和时间冗余,6视觉冗余视觉、听觉敏感度和非线性感觉,7知识冗余凭借经验识别,4结构冗余规则纹理、相互重叠的结构表面,5信息熵冗余编码冗余，数据与携带的信息,1.空间冗余空间冗余是在图像数据中经常存在的一种冗余。在任何一幅图像中：均有许多灰度或颜色都相同的邻近像素组成的局部区域，它们之间具有空间上的强相关性，在图像中就表现为空间冗余。,1.空间冗余,颜色相同的区域,对空间冗余的压缩方法就是把这种颜色都相同的邻近像素组成的局部区域当作一个整体，用极少的数据量来表示它，从而节省了存储空间。这种压缩方法叫空间压缩或帧内压缩。,时间冗余：视频信号和动画是基于时间轴的一组连续画面。由于活动图像序列中的任意两幅相邻的图像之间的时间间隔很短，因此两幅图像中存在大量的相关信息,时间冗余,相邻帧包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同,活动图像中的两幅相邻的图像有较大的相关性，这反映为时间冗余。在前一幅图像的基础上，只需改变少量的数据，便可以表示出后一幅图像，达到数据压缩的目的。这种压缩对活动图像往往能得到很高的压缩比，这也称为时间压缩或帧间压缩。,3.统计冗余,空间冗余和时间冗余是将图像信号看作为随机信号时所反映出的统计特征，因此有时把这两种冗余称为统计冗余。,4.信息熵冗余信息熵是针对数据的信息量而言的，它代表从图像信息源中发出的一个符号的平均信息量设某种编码的平均码长单位（符号）的数据量为式中，为分配给第符号的比特数，即二进制位数,由于实际中很难估算各符号出现的概率，我们一般认为它们是等概率的，所以每个符号比特数相同。这种编码的符号的数据量L为最大。但实际各符号出现的概率并不相同。这样所得的L必然大于实际的信源熵H，由此带来的冗余我们称为信息熵冗余或编码冗余。,总结：数据中通常包含很大的冗余，数据的大小与所携带的信息量的关系由下式给出：L=H+RH：信源熵（信息量/符号，代表最小比特数）、L：数据量（平均码长单位，即符号实际的比特数）R：冗余量（即信息冗余量）R=L-H,5.结构冗余有些图像从整体上看存在着非常强的纹理结构。下图为草席图像。是一种规则有序排列的图形，我们称它在结构上存在冗余。是一种结构冗余。,规则有序排列的图形,6.知识冗余有些图像的理解与某些知识有相当大的相关性。比如人脸的图像有固定的结构：嘴的上方有鼻子、鼻子的上方有双眼睛，鼻子位于正脸图像的中线上等等这类规律的结构可由先验知识和背景知识得到，因此这类信息对一般人来说就是冗余信息。这就是知识冗余。,7.视觉冗余由于人眼的视觉特性有所限制，人类的视觉系统不能对图像画面的任何变化都能感觉到。举例：人眼视觉系统的一般分辨率为64灰度等级,而一般图像的量化采用的是256的灰度等级。这种差别就是视觉冗余。,视频压缩编码方法及其分类,图像压缩的基本目标就是减小数据量。至于图像压缩到什么程度而又没有明显的失真,则取决于图像数据的冗余度。所有的这些冗余度都可以被除去而不会引起显著的信息损失。空间冗余和时间冗余是图像信号最常见的冗余。,压缩编码分类,1.按恢复的图像性质划分按恢复的图像性质,数字图像压缩方法可以分为两种：无损压缩编码有损压缩编码,压缩编码分类,无损压缩编码：也称为熵编码、可逆编码或无失真编码。当系统采用此方法进行数据压缩时,在接收端所获得的解码与原图像完全相同。无损压缩不能提供较高的压缩比。一般在2:15:1。,压缩编码分类,有损编码：也称为不可逆编码、熵压缩编码或失真编码。由于压缩了熵，会减少信息而不能再恢复。这种压缩编码具有较高的压缩比。最大可达几百比一。,压缩编码分类,2.按压缩方法的原理划分按压缩原理划分,数字图像压缩方法可以分为以下几种编码:预测编码变换编码标量量化和矢量量化编码信息熵编码子带编码结构编码模型编码,图像压缩编码,无损压缩,有损压缩,霍夫曼编码,行程编码,算术编码,L-Z编码,预测编码:,量化编码:,模型编码:,混合编码:,变换编码:,DPCM；运动补偿,DCT；子带编码,分形编码；知识基编码,JPEG；MPEG；H.26X编码,采样编码；矢量量化编码,图像压缩算法分类,压缩编码分类,（1）预测编码：其典型的压缩方法有DPCM和ADPCM.它们比较适合于图像数据的压缩。它主要是减少图像数据在空间上和时间上的相关性，从而达到数据压缩的目的，但这是一种有失真的压缩方法。,压缩编码分类,（2）变换编码：它是将图像时域信号转换到变换域（系数空间、频域）上进行处理。在实际编码中，常常利用图像的统计特性和人眼的视觉特性，只是选择部分变换系数来进行信息传输，因此恢复的图像中将存在一定的失真。常用的正交变换有：离散傅氏变换DFT、离散余弦变换DCT、离散正弦变换DST和K-L变换。,压缩编码分类,（3）标量量化和矢量量化编码：标量量化指传统的量化，是将具有无限电平的点样值，用有限电平数表示的方法，是一个样点、一个样点地进行量化编码。这里量化器的设计是一个很关键的步骤。,压缩编码分类,（3）标量量化和矢量量化编码：矢量编码是相对标量量化而提出的。矢量编码中一次可以量化多个样点。矢量量化也是一种有损压缩编码。,压缩编码分类,（4）信息熵编码：信息熵编码是一种基于图像统计特性的编码方法。是一种无损压缩编码方法。,压缩编码分类,（4）信息熵编码：它是根据信息熵的原理：用最短的位数表示出现概率大的信息，而出现概率较小的信息则用较长的位数来表示，以此达到压缩数据的目的。常见的熵编码有哈夫曼编码、游程编码和算术编码。,压缩编码分类,（5）子带编码：在子带编码中，首先将图像数据转换到频域，然后按频率分成若干子带，对每个子带用不同的编码器进行抽样、量化和编码，并将各子带输出数据合成为数据码流，从而获得压缩数据。,压缩编码分类,（6）结构编码：结构编码也称为第二代编码。编码时首先求出图像中的边界、轮廓、纹理等结构特征参数，然后保存这些参数信息，进行编码。在解码时则根据这些结构和参数信息进行图像合成，从而恢复出原图像。,压缩编码分类,（7）模型编码：这是一种基于知识的编码。利用人们对自然知识的了解而形成一个规则库，将人脸变化等特征用一系列参数来进行描述。利用参数再加上模型就可以实现人脸的图像编码和解码，达到压缩图像数据的目的。,数据压缩技术的性能指标,1、压缩比用来定义压缩性能。指压缩过程中输入数据量与输出数据量之比。设原图像的平均码长为Lc,压缩后图像的平均码长为L，则压缩比C为,压缩比越大，说明数据压缩的程度越高。,冗余度和编码效率也是衡量信源特性以及编解码设备性能的重要指标，定义如下：冗余度:指冗余量在信息量中占的比例L为平均码字长度H(X)为信源熵。编码效率：指信息量在数据量中占的比例,数据压缩技术的性能指标,2、重现质量：恢复效果要好，要尽可能地恢复原始数据。3、压缩和解压缩速度,无损图像压缩编码方法,无失真（无损）图像压缩编码就是指图像经过压缩、编码后恢复出的图像与原图像完全一样,没有任何失真。无失真压缩编码-熵编码。广泛应用于文本数据和特殊应用场合的图像数据（指纹图像、医学图像、卫星图像等）的压缩。,无损图像压缩编码方法,香农信息论认为,信源中或多或少地含有自然冗余度。这些冗余度既来自于信源本身的相关性,又来自于信源概率分布的不均匀性中。只要找到去除相关性或改变概率分布不均匀性的方法和手段,也就找到了信息熵编码的方法。,无损图像压缩编码方法,例如：在图像中存在着空间上的相关性对运动图像而言存在着帧与帧之间在时间上的相关性。这些都说明存在着颜色的概率分布的不均匀性。,无损图像压缩编码方法,信息熵编码所要解决的问题：如何利用信息熵理论（香农信息论）减少数据在传输和存储时的冗余度。,香农信息论,香农信息论认为：信源所含有的信息熵就是进行无失真编码的理论极限。,香农信息论,低于此极限的无失真编码方法是找不到的,而只要不低于此极限,那就总能找到某种适宜的编码方法任意的逼近信息熵。熵编码的目的就是要使编码后的图像平均码字长度（比特数）L近可能接近这个信息熵H(x),无损图像压缩编码方法,根据：L=H+RH：信源熵（信息量/符号，代表符号的最小比特数）、L：数据量（每个符号实际平均的比特数，也称码字长度）R：冗余量（即信息冗余量）R=L-H无损数据压缩的本质：通过减少冗余量R，减少数据量L，使之接近H。,无损图像压缩编码方法,无损图像压缩编码方法由于其中并没有考虑人眼的视觉特性,因此其所能达到的压缩比非常有限。常用的无失真图像压缩编码有：哈夫曼编码游程编码（行程编码）算术编码,无损图像压缩编码方法,在实际应用中,常将游程编码与哈夫曼编码结合起来使用,例如在H.261、JPEG、MPEG等国际标准中正是采用此种编码技术。而在H.263等国际标准中则采用算术编码技术。,哈夫曼编码,哈夫曼(Huffman)编码方法于1952年问世,迄今为止仍经久不衰,广泛应用于各种数据压缩技术中,且仍不失为熵编码中的最佳编码方法。主要编码思路：对出现频率较大的符号用较短的码来表示，而对于出现频率较小的符号则用较长的码来表示。这样的编码结果所获得的平均码字长度最短。,哈夫曼编码,哈夫曼编码的码长是变化的，即可变长编码(VLC),而且哈夫曼编码通常被称为最优码。最优的含义是：对于给定的符号集和概率模型，找不到任何其它整数码比哈夫曼编码有更短的码长。整数码：指每个符号所对应的码字的位数都是整数。,哈夫曼编码,具体编码过程：1、排序：按符号出现的概率从大到小进行排列。2、赋值：对排在最后的两个符号进行赋值，概率大的赋“1”，概率小的赋“0”。或相反。3、合并：将上述最后的两个符号出现的概率相加合成一个概率。,哈夫曼编码,4、重新排序：将合成后的概率与其它符号概率一起进行重新排序（从大到小）。然后重复步骤2、3的内容，直至概率相加为1为止。5、码字分配：从最后一步开始反向进行码字分配。从而形成一个码字。,哈夫曼编码的基本原理,例：aaaabbbccdeeeeefffffff432157如果不进行特殊的编码，用字符方式（ASCII码）传送，每个字符8位，需要的数据量为：22*8=176bit,哈夫曼编码的基本原理,c,b,a,f,e,7/22,5/22,4/22,2/22,1,0,f=11e=01a=00b=101c=1001d=1000,d,1/22,3/22,6/22,22/22,13/22,9/22,3/22,1,0,1,0,1,0,1,0,哈夫曼编码,哈夫曼编码的基本原理,aaaabbbccdeeeeefffffff432157按照哈夫曼编码的原理进行编码：a=00b=101c=1001d=1000e=01f=11需要的数据量为4*2+3*3+2*4+1*4+5*2+7*2=53bit比22*8=176bit少了123bit平均编码长度L为,哈夫曼编码的基本原理,例设信号源为X=、a、e、I、m、t、c、h、r。若传送一个字符串“Iamateacher”，对应的概率为p=0.22、0.22、0.14、0.07、0.07、0.07、0.07、0.07、0.07,试给出该信源的霍夫曼编码方案。并计算压缩比C、冗余度R和编码效率。,=01a=00e=111I=1101m=1100t=1011c=1010h=1001r=1000出现3次，a出现3次，e出现2次，其它的各出现1次。共需要3*2+3*2+2*3+6*4=42bit,分析:若传送一个字符串“Iamateacher”，共14个字符，其中包括9个不同的字符。（1）若使用自然编码（等长二进制编码），该字符串中有9个不同的符号，至少需要4位二进制才能表示，这样传送该字符串也要56位。（2）Huffman编码只需要42位，平均编码长度为2.98。平均码字长度公式为：,求压缩比、冗余度和编码效率:压缩比C：14个字符，需4位二进制数Lc=4C=Lc/L=4/2.98=1.34:1冗余度R=(L-H)/H=(2.98-2.97)/2.97=0.34%编码效率,哈夫曼编码,例：某信源符号及其对应的概率如下：a1a2a3a4a5a60.40.20.120.150.10.03请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。,哈夫曼编码,例：某信源符号及其对应的概率如下：a1a2a3a4a5a6a7a80.400.040.10.10.070.060.180.04请完成哈夫曼编码，并计算压缩比、冗余度和编码效率。a1:0a2:11100a3:100a4:1111a5:1011a6:1010a7:11101a8:110,哈夫曼编码,特点：（1）虽然哈夫曼码长可变,但却不需要另附同步码。（2）通信双方只要均拥有预先编写的解释各种代码意义的词典(即码本),即可根据码本逐码译出。,哈夫曼编码,哈夫曼编码有几个问题值得注意:一、哈夫曼码没有错误保护功能。如果码串中有错,哪怕仅仅是1位出错,不但该码本身将会译错,更糟糕的是对后面的影响,一错就是一串,一般称这种现象为错误传播。,哈夫曼编码,二、不可调用中间的内容哈夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码;三、接收端需保存一个与发送端相同的霍夫曼码表哈夫曼码还是得到广泛应用,哈夫曼编码毕竟属于最佳编码方法。,游程编码RLC,游程编码（行程编码）RLC（RLE)是一种非常简单的数据压缩编码形式。它在某些场合是非常有效的一种无损压缩编码方法。,游程编码RLC,游程编码编码原则:连续重复的数据值序列（或称为“流”）用一个重复次数和单个数据值来代替。比如：得到的字符串为AAAAAABCDDDDDDDDDBBBBBBBB可压缩为*6ABC*9D*8B,颜色相同的区域,游程编码RLC,不需要存储每一个像素的颜色值，而仅存储一个像素的颜色值以及具有相同颜色的像素数目。或者存储一个像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为游程编码或行程编码。,游程编码RLC,游程编码多用于黑白图像或图形的压缩。具有相同灰度等级的连续的像素数目称为游程长度RL。图像中具有相同灰度的图像块越大越多，压缩的效果就越好。,宽度：263宽度：263高度：300高度：300灰度：4灰度：8,游程编码RLC,RLC特点：编码简单直观，编码/解码速度快，只需要简单地复制字符若干遍即可以了。BMP、TIFF、AVI等格式文件的压缩均采用此方法。在PDF文件格式中也得到应用。存在着不同的实现技术和文件格式。,游程编码RLC的构成,在RLC中用3个字节表示一个字符串：由一个指示符、一个重复次数字节和一个被重复的字符构成的3字节码,思考：RL?时，数据压缩才用意义,3,游程编码RLC方法,例如:字符串RTAAAASDEEEEE经RLE压缩后为：RT*4ASD*5E“*4A”代替了“AAAA”“*5E”代替“EEEEE”指示符采用特殊字符*：指出一个RLC编码的开始，后面的数字表示重复的次数，数字后的单个字符是被重复的字符。,游程编码RLC方法,例:设有数据“AAAABBBBCCCCCCCDAAAAAA”试计算该数据的行程编码。解：A重复4次，B重复4次，C重复7次，D不重复，A重复6次，RLC数据流为：“#4A#4B#7CD#6A”，其中#为指示符。总共占用13个字节，而源数据占用22个字节。游程编码也可以不用指示符:重复与否相同对待，相应的RLC为“3A4B5C1D6A”占用10个字节。,游程编码RLC方法,例：aaaabbbccdeeeeefffffff(共22*8=176bit)4a3b2c1d5e7f(共12*8=96bit)压缩率为：176/96=1.83:1,游程编码,游程编码的压缩率不高，但编码、解码的速度快，仍被得到广泛的应用。特别是在变换编码后再进行游程编码，有很好的效果。在图像数据压缩标准(JPEG)中扮演重要角色。,算术编码,算术编码产生于20世纪60年代初,在图像数据压缩标准中算术编码扮演了重要的角色。能有效地压缩信源冗余度，属于熵编码的一种。该方法实现较为复杂，常与其它有损压缩编码结合使用，在视频数据压缩标准(如H.263)中扮演重要角色。,算术编码,算术编码与哈夫曼编码一样，也是对概率较大的符号采用短码，对概率较小的符号采用长码。它突破了哈夫曼编码每个符号只能按整数比特来逼近信源熵的限制:每个符号的平均编码长度可以按小数比特来逼近信源熵。,算术编码基本思想,算术编码不是将单个信源符号映射成一个码字。而是把整个信源表示为实数线上的0到1之间的一个区间，其长度等于该信源的概率。再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。,算术编码基本步骤,将编码的消息表示成实数0和1之间的一个区间。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，表示这一区间所需的二进制位就越多。消息结束时就最后所得到区间的下边界值表示该消息。,给定符号序列的算术编码步骤如下：（1）初始化：编码器开始时将“当前区间”设置为一。为0，1)（2）按消息（符号序列）中符号的顺序：对每一符号，编码器按步骤（a）和（b）重复进行处理,给定符号序列的算术编码步骤如下：（a）编码器将“当前区间”分为子区间，每一个符号分配一个子区间。一个子区间的大小与符号的概率成比例。（b）对应于一个确切发生的符号，编码器选择其子区间，并使它成为新的“当前区间”。这也称为重新归一化。,给定符号序列的算术编码步骤如下：（3）最后一个符号对应有最后输出的“当前区间”。最后输出的“当前区间”的下边界就是该给定的整个符号序列的算术编码。,算术编码方法,算术编码用到两个基本的参数：符号的概率和它的累积概率。累积概率（下边界值）：设信源符号集为A=a0,a1,a2,am-1相应的概率为Pi，i=0，1，2，m-1。各符号的累积概率Pr为:a0的累积概率为0，a1的累积概率为P0，a2的累积概率为P0+P1,算术编码示例：符号S1、S2、S3、S4十进制概率1/81/41/21/8二进制概率Pi0.0010.010.10.001累积概率Pr00.0010.0110.11101/83/87/8100.0010.0110.1111,现在以符号序列：s3s3s2s4为例来解释编码过程算术编码的基本法则归纳如下:(1)初始状态区间起始点C=0,区间宽度A=1.0。(2)新区间起点C=原起点C+原区间宽度APr,新区间宽度A=原区间宽度APi其中Pr为所编符号si对应的累积概率Pi为所编符号si对应的概率。,对序列s3s3s2s4进行编码的过程如下:初始起点C=0初始区间宽度A=1第1个符号s3:新区间起点：C=0+10.011=0.011新区间宽度：A=10.1=0.1区间终点为0.111新的当前区间范围为：0.011-0.111,第2个符号s3:新区间起点：C=0.011+0.10.011=0.1001新区间宽度：A=0.10.1=0.01区间终点0.1101新的当前区间为：0.1001-0.1101,第3个符号s2:新区间起点：C=0.1001+0.010.001=0.10011新区间宽度：A=0.010.01=0.0001新的当前区间为：0.10011-0.10101第4个符号s4:新区间起点：C=0.10011+0.00010.111=0.1010011新区间宽度：A=0.00010.001=0.0000001取最后符号的当前区间的下边界作为序列的算术编码所以最终编完的码字是0.1010011,算数编码的代码长度L为多少？根据信源熵：得出，算数编码的代码长度L：N代表出现的符号数量代表大于X的最小整数。代码取其值小数点后的L位。若有尾数，就进位到第L位。,如：则取L=3如果最后符号的下边界为0.10110001取：c=0.110传输的二进制代码序列是110,刚才例题最终编完的码字0.1010011传输s3s3s2s4共4个符号，得取7位所以传输的码流为1010011压缩率为：42/7=8/7=1.14:1,算术编码解码过程在解码器中,当收到码字串0.1010011时,这个码字串指向子区间0.011,0.111),解出的第一个符号应为s300.0010.0110.1111.0,算术编码解码过程之后采取与编码过程相反的步骤：即：从码字串中减去已解符号的累积概率,并将差值除以概率值,则得到新码字串。(0.10100111-0.011)(0.1)=0.100011。新码字串仍落在0.011,0.111)区间之内,解出的第2个符号仍为s3。后面的过程以此类推00.0010.0110.1111.0,（0.100011-0.011）/0.1=0.010110.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即：s3s3s2s4解码完毕！00.0010.0110.1111.0,例：假设信源符号为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。,二进制消息序列的输入为：CADACDB。编码：首先输入的符号是C：新区间起点：C=0+10.5=0.5新区间宽度：A=10.2=0.2区间终点:0.5+0.2=0.7新的当前区间范围为：0.5-0.7,二进制消息序列的输入为：CADACDB。新的当前区间范围为：0.5-0.7新区间宽度：A=10.2=0.2第2个符号A:新区间起点：C=0.5+0.20=0.5新区间宽度：A=0.20.1=0.02终点：0.5+0.02=0.52新的当前区间为：0.5-0.52,二进制消息序列的输入为：CADACDB。当前区间为：0.5-0.52新区间宽度：A=0.20.1=0.02第3个符号D:新区间起点：C=0.5+0.020.7=0.514新区间宽度：A=0.020.3=0.006终点：0.514+0.006=0.52新的当前区间为：0.514-0.52,二进制消息序列的输入为：CADACDB。当前区间为：0.514-0.52新区间宽度：A=0.020.3=0.006第4个符号A:新区间起点：C=0.514+0.0060=0.514新区间宽度：A=0.0060.1=0.0006终点：0.514+0.0006=0.5146新的当前区间为：0.514-0.5146,二进制消息序列的输入为：CADACDB。新的当前区间为：0.514-0.5146新区间宽度：A=0.0060.1=0.0006第5个符号C:新区间起点：C=0.514+0.00060.5=0.5143新区间宽度：A=0.00060.2=0.00012终点：0.5143+0.00012=0.51442新的当前区间为：0.5143-0.51442,二进制消息序列的输入为：CADACDB。新的当前区间为：0.5143-0.51442新区间宽度：A=0.00060.2=0.00012第6个符号D:新区间起点：C=0.5143+0.000120.7=0.514384新区间宽度：A=0.000120.3=0.000036终点：0.514384+0.000036=0.51442新的当前区间为：0.514384-0.51442,二进制消息序列的输入为：CADACDB。新的当前区间为：0.514384-0.51442新区间宽度：A=0.000120.3=0.000036第7个符号B:新区间起点：C=0.514384+0.0000360.1=0.5143876新区间宽度：A=0.0000360.4=0.0000144新的当前区间为：0.5143876-0.514402最终编完的码字是0.5143876,根据传输CADACDB，共7个符号取13位最终编完的码字是0.5143876变换的二进制为0.10000011101011所以传输的码流为1000001110110压缩率为：14/13=1.1:1,假设信源符号为A，B，C，D，符号的概率分别为0.1，0.4，0.2，0.3，传输数据序列为：BCBDA，求算术编码及其编码效率。,A，B，C，D，概率0.1，0.4，0.2，0.3，A，B，C，D概率0.10.40.20.3累积概率00.10.50.7,传输数据序列为：BCBDAB:C=0+10.1=0.1A=10.4=0.4C:C=0.1+0.40.5=0.3A=0.40.2=0.08B:C=0.3+0.080.1=0.308A=0.080.4=0.032D:C=0.308+0.0320.7=0.3304A=0.0320.7=0.0096A:C=0.3304+0.00960=0.3304A=0.00960.1=0.00096,输出：0.3304换为二进制数，取的位数为：所以最终输出为：0101010010编码效率为：,算术编码,算术编码的优点：渐近最佳性-当序列无限增长时，平均码长将渐近地等于序列的信源熵值.算术编码具有比哈夫曼编码更好的压缩率,算术编码,在算术编码中有几个问题需要注意：一、算术编码器对整个消息只产生一个码字，这个码字是在间隔0，1中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。二、算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,4.4限失真图像压缩编码方法,在有损图像编码方法中，允许有一定的失真存在，压缩了信源熵，提高压缩比。有损压缩经常压缩图像和视频等。在这一节，我们讨论常用的一些图像信号的有损压缩技术。,有损图像压缩编码预测编码,预测编码主要是减少图像在时间上和空间上的相关性。,有损图像压缩编码预测编码,预测编码就是用已经传输的样本值对当前的样本值进行预测，然后对实际的样本值与预测值的差值（预测误差）进行编码处理和传输。,预测编码,预测编码分为两类：帧内预测：预测可以在一帧图像内进行。针对一幅图像的空间冗余帧间预测：预测在多帧图像之间进行。针对活动图像的时间冗余,预测编码帧内预测,帧内预测编码是针对一幅图像，减少其空间上的相关性来实现数据压缩的。通常采用差分脉冲编码调制(DPCM)来实现。,图中x(n)为采样的图像数据，为x(n)的预测值，是实际值和预测值的差值，是d(n)的量化值，量化的过程会引入量化噪声。是引入量化误差的x(n)。,差分脉冲编码调制(DPCM),在图像信号中应用DPCM时，用作预测的像素和被预测的像素可以在同一行，也可以在不同行（同一帧），分别称为：一维预测：用作预测的样值都与被预测的样值在同一行内。二维预测：用作预测的样值位于相邻的不同行上。,用作预测的样值均与被预测的样值在同一行内(如x1,x2与X),称为一维预测;用作预测的样值位于相邻的不同行上时(如x1,x2，x3,x4与X)则称为二维预测。,被预测像素,一维预测利用了像素之间在水平方向上的相关性。一阶的一维预测值为：黑电平预测误差大五阶的二维预测的预测值：,差分脉冲编码调制(DPCM),优点：算法简单，容易硬件实现缺点：对信道噪声很敏感，会产生误差扩散。压缩率比较低。,预测编码帧间预测编码,帧间预测编码是利用视频图像帧间的相关性，即时间相关性，来达到图像压缩的目的。广泛用于普通电视、会议电视、视频电话、高清晰度电视的压缩编码。,动态图像以每秒25(30)帧播放，在如此短的时间内，画面通常不会有大的变化；在画面中变化的只是运动的部分，静止的部分往往占有较大的面积；即使是运动的部分，也多为简单的平移,活动图像预测编码帧间预测编码,帧间预测：不直接传送当前帧的像素值x，而是传送x和其前一帧或后一帧的对应像素x之间的差值e=x-x。,活动图像预测编码帧间预测编码,估计出云朵运动的方向和速度（位移矢量），可以从云朵在k-1帧的位置推算出它在k帧中的位置来，而背景图像仍以前一帧的背景代替。预测误差小。k-1帧k帧,背景区,活动物体,活动图像预测编码帧间预测编码,活动图像帧间预测编码分为两种：一、具有运动补偿的帧间预测二、帧间内插,具有运动补偿的帧间预测,对运动区域进行预测：首先要估计出运动物体的运动矢量D然后再根据运动矢量进行补偿，即找出物体在下一帧的区域位置。,具有运动补偿的帧间预测,将考虑了运动物体位移矢量D的k-1帧图像作为k帧的预测值，预测误差会变小，从而可以达到更高的数据压缩比。这种预测方法称为具有运动补偿的帧间预测。在帧间预测中引入运动补偿的目的：减少预测误差，提高编码效率。,具有运动补偿的帧间预测编码是视频压缩的关键技术之一。它包括以下几个步骤：一、图像划分：将图像分解成相对静止的背景和若干个运动的物体，各个物体可能有不同的位移，但构成每个物体的所有像素的位移相同。二、运动检测与估值：对每一个运动物体进行运动估值，得到每个物体的运动位移矢量D,三、运动补偿：利用位移矢量D计算经运动补偿后的预测值四、预测编码：对实际值与运动补偿预测值的差值（预测误差）进行量化、编码、传输。,具有运动补偿的帧间预测运动估值,提取位移矢量Dt时刻运动物体的像素值（亮度，彩色）bt可以用在此之前时间的像素值bt-来表示。这两个像素点坐标值之差被称为位移矢量D：bt（z)=bt-(z-D)上式表示，t时刻z位置的像素是t-时刻z-D位置的像素时间运动了矢量D后的结果。,运动补偿运动估值,通常采用的运动矢量估值方法主要分为两大类：像素递归法PRA块匹配法BMA像素递归法PRA：精度高算法复杂,运动估值块匹配法SMA,原理：它将图像划分为许多NN像素的子块，每块看成是一个物体。并认为子块内所有像素的位移量是相同的，这意味着将每个子块视为一个“运动物体”。目前实用的活动图像压缩标准中(如H.261、MPEG等)都选择1616或88大小的图像子块。,运动估值块匹配法SMA,原理：对于当前的图像帧中的某一子块B，如果在另一时间帧中可以找到与其最为相似的子块B*，称为匹配块（最相似块），并认为该子块B是匹配块B*位移后得到的结果。通过B和B*的坐标位置便可以确定位移矢量D。,块匹配法BMA精度低于像素递归法PRA，但其位移跟踪能力强（不低于67像素/帧），实现简单，尤其适合于物体作平移运动，因此应用很广泛。它在活动图像压缩标准H.261、H.263、MPEG-1、MPEG-2及MPEG-4等国际标准中都被采用。,具有运动补偿的帧间预测,具有运动补偿的帧间预测分为三种预测方式：前向预测后向预测双向预测,具有运动补偿的帧间预测,前向预测：帧间预测方法是由第k-1帧来预测第k帧图像的预测方式,这种方式就是前向预测。后向预测：如果待预测的子块是在第k帧，而搜索区处于第k+1帧。也就是从后续的k+1帧图像预测之前的第k帧图像,这种预测方法称为后向预测。,双向预测：预测误差小,传输的数据率低。压缩比大,双向预测：对于k帧中的子块,先从k-1帧中找到它的最佳匹配块,从而得到该子块从k-1到k帧的位移矢量Dl,再利用后向预测得到它从k+1到k帧的位移矢量D2,二者的平均值作为k帧子块的预测值。进一步降低预测误差。,帧间预测双向预测,双向预测所付出的代价是：对每一个子块需要传送2个位移矢量D1、D2给收端,而且k帧的恢复必须等到接收到k+1帧之后才能进行。解码运算的帧顺序是：k-1帧、k+1帧、k帧而图像显示的顺序是k-1、k、k+1。要保持显示的连续性,需要多引入1帧的延时。,帧间预测活动图像帧间内插,在具有运动补偿的帧间预测编码系统中，图像的传输帧率并没有变化，仍与编码前的帧率一样。,帧间预测活动图像帧间内插,在某些应用场合如：可视电话、视频会议活动很慢的图像，对图像传输帧率的要求可适当降低，可以少传一些帧。,活动图像的帧间内插,对于静止图像或活动很慢的图像，可以少传一些帧，如进行隔帧传输。未传输的帧，可以利用接收端的帧存储器中前一帧的数据作为该帧数据，以防止帧频下降引起图像的闪烁和动作不连续。广泛应用于视频电话、视频会议系统中。其图像帧速率一般为1-15帧/秒。,活动图像的帧间内插,存在的问题：当图像中存在运动物体时,出来的结果与真实运动轨迹存在误差,从视觉效果来看，即存在图像模糊现象。,具有运动补偿的帧间内插,即要确定运动物体在丢弃帧中的位置估计出该物体的运动方向和速度-位移矢量D。这种方法可以有效的降低图像模糊现象。,具有运动补偿的帧间内插,具有运动补偿的帧间内插和帧间预测都需要进行运动估值.但二者的目的以及运动估值不准确所带来的影响不相同。,帧间内插运动补偿与帧间预测的运动补偿区别？,帧间预测的运动估值,在帧间预测中引入运动补偿的目的是为了减少预测误差，从而提高编码效率。运动估值的不准确会使预测误差加大，从而使传输的数据率上升。压缩率下降。接收端根据此位移矢量和预测误差进行解码并不会引起图像质量下降。帧间预测的运动估值多采用块匹配法。,帧间内插的运动估值,在帧间内插中引入运动补偿的目的，是使恢复的内插帧中的运动物体不致因为内插而引起图像质量太大的下降，导致图像模糊现象。,帧间内插的运动估值,帧间内插中的位移矢量估值一般要对运动区的每一个像素进行，而不是对一个子块；否则帧间内插同样会引起运动物体边界的模糊现象。因此在帧间内插的运动估值较多使用能够给出单个像素位移矢量的像素递归法。,限失真图像压缩编码变换编码,如果对图像数据进行某种形式的正交变换,并对变换后的数据进行编码,从而达到数据压缩的目的,这就是变换编码。变换编码是一种有效的图像压缩方法,它是所有有损压缩国际标准的基础。,变换编码,变换编码不直接对原图像信号压缩编码,而首先将图像信号从空间域（或时间域）映射到另一个域变换域（或频率域）中。产生一组变换系数。然后对这些系数进行量化、编码、传输。,变换编码,预测编码是在空间域（或时间域）内进行的。变换编码则是在变换域（或频率域）内进行的。,变换编码,在变换域（或频率域）:能量主要集中在低频部分变换后的变换系数之间的相关性大大降低。,变换编码,图像变换编码一般利用了视觉心理编码。一、分块：目的减小运算量。将原始图像分成“若干个子像块”,然后对每个子像块进行变换。一般子图像块的大小选为88或1616。,变换编码,对图像进行子块划分的另一个好处是:可以将传输误差所造成的图像损伤限制在子图像的范围之内,从而避免误码的扩散。,变换编码,二视觉心理编码对每一个变换系数或主要的变换系数进行量化和编码。量化特性和编码的比特数是由人的视觉特性确定的。人眼对不同频率分量的敏感程度是不同的,变换编码,二、视觉心理编码对不同频率系数采用不同的量化台阶，以进一步提高压缩比：低频系数采用的量化台阶小，编码的比特多；高频系数采用的量化台阶大，编码的比特少。,变换编码,变换编码的基本思路：在编码时略去某些能量很小的高频分量，或在量化时对能量较小的分量分配较少的比特数，以降低码率。在接收端经解码、反量化后得到带有一定量化失真的变换系数,再经反变换就可恢复图像信号。变换编码也是一种有损压缩编码。,基本原理,子块1,子块2,子块n,.,.,正变换,滤波,量化,编码,信道,解码,逆变换,综合拼接,源图像（发送）,恢复图像（接收）,变换编码系统原理图,正交变换的类型,变换编码中的关键技术在于正交变换。正交变换的变换核(变换矩阵)是可逆的,且逆矩阵与转置矩阵相等,能够保证解码运算有解且运算方便。所以变换编码总是选用正交变换来做。,正交变换的种类：傅氏变换沃尔什变换哈尔变换离散余弦变换离散正弦变换K-L变换小波变换,离散余弦变换(DCT),正变换：变换系数,逆变换：,f(x,y)实质上是88像素的空间图像（64个抽样值），DCT将其变换成64个正交基信号，是f(x,y)的64个DCT系数。F(u,v)可以表示为,DCT变换可以看成是一个谐波分析器，把f(x,y)分解成为64个正交的信号，分别代表着64种不同频率成分。DCT系数即基信号振幅,方阵中的每个数值不再表示信号在像素点的振幅,而是表示一个DCT系数。能量集中在少数几个低频系数上。,可忽略,图像信号的能量都集中在低频成分中。中频和高频的系数会很小或者为0值。离散余弦变换把信号的能量聚集在最小的空间频率内了。DCT系数矩阵,低頻,中頻,高頻,DC,离散余弦变换(DCT),总结：在数据压缩过程中把中间频率和高频的系数忽略,而只保留低频的系数。这样就可以大大减少数据量,实现数据压缩。,DCT变换编码过程,DCT变换,DCT逆变换,原图像,除以量化矩阵,取整,1）编码过程：,2）解码过程：,压缩图像,乘以量化矩阵,取整,压缩图像,解压图像,量化,DCT变换编码-量化,DCT变换输出的数据F(u,v)还必须进行量化处理。注意：在量化之前,并没有发生数据丢失。如果这时将图像以DCT系数形式传送或保存,然后再逆向变换,原始图像可以准确地再现。是无损变换。,DCT变换编码-量化,量化的目的：减少DCT系数的幅值，增加系数的零值个数，来压缩数据。“量化处理”是压缩编码过程中图像信息产生失真的主要原因。,DCT变换编码-量化,量化：采用均匀量化。但每个系数的量化台阶不同。量化方法：用一个预定义的值去除每个DCT系数来对其标准化。这些预定义的值称为量化步长。即量化台阶。事先存放在一个称为量化步长表的88方块中。也称之为“量化矩阵”“量化步长表”,DCT变换编码-量化,例：,原图像为：,除以量化矩阵，取整,DCT变换编码-量化,人眼对亮度信号比对色差信号更敏感，因此使用了两种量化表：亮度量化步长表色差量化步长表,JPEG标准所推荐的亮度量化表,JPEG标准所推荐的色度量化步长表,DCT变换编码过程,DCT变换,DCT逆变换,原图像,除以量化矩阵,取整,1）编码过程：,2）解码过程：,压缩图像,乘以量化矩阵,取整,压缩图像,解压图像,熵编码,DCT变换编码-压缩编码,为实现进一步的压缩，经过处理后的系数再进行熵编码。编码前首先要进行系数扫描：目的是将矩阵的二维系数展开成一维序列输出。,DCT变换编码-系数扫描方式,DCT变换后，信号能量主要集中在直流和低频区。该区位于矩阵的左上角部分。“Z”字形扫描路径将二维系数展开成一维序列输出。,在DCT系数中包含了直流系数DC和交流系数AC它们的编码方法是不同的。,DCT变换编码-压缩编码,直流系数的编码方法：直流系数存在两个特点：一是系数的数值比较大二是相邻子图像块中的直流系数间存在较大相关性,变化不大。进行单独编码,对各子块的直流系数进行DPCM编码(差分脉冲编码)对相邻图像块之间量化DC系数的差值进行编码。,DCT变换编码-压缩编码,交流系数的压缩编码：最适于进行什么编码？游程编码RLC。,交流系数的压缩编码,DCT变换编码-压缩编码,DPCM编码后的直流DC系数和游程编码RLC后的交流AC系数还可以使用熵编码作进一步的压缩。如：在JPEG有损压缩算法中，使用霍夫曼编码器来减少熵。,DCT变换及压缩编码过程,4.7图像压缩编码标准,活动图像压缩标准:H系列标准和MPEG系列标准静止图像压缩标准:JBIG（联合二值图像专家组）和JPEG标准,静止图像压缩编码标准JPEG,JPEG(JointPhotographicExpertsGroup)，即联合图像专家组，是一个由ISO和ITU两个组织机构联合组成的一个图像专家小组，负责制定静止的数字图像数据压缩编码标准，这个专家组开发的算法称为JPEG算法，并且成为国际上通用的标准，因此又称为JPEG标准。,静止图像压缩编码标准JPEG,在JPEG算法中，共包含四种运行模式：1.无损压缩编码模式2.基于DCT的顺序编码模式3.基于DCT的累进编码模式4.基于DCT的分层编码模式第一种是基于DPCM的无损压缩算法。另外三种是基于离散余弦变换(DCT)和Huffman编码的有损压缩算法,通常压缩20-50倍。,JPEG的运行模式,1.无损压缩编码模式：保证准确恢复数字图像的所有样本数据,与原数字图像相比不会产生任何失真。压缩比为2：12.基于DCT的顺序编码模式：以DCT变换为基础.按照从左到右、从上到下的顺序对原图像数据进行压缩编码。图像还原时,也是按照上述顺序进行。,JPEG的运行模式,3.基于DCT的累进编码模式：以DCT变换为基础,但使用了多次扫描的方法对图像数据进行编码,以由粗到细逐步累加方式进行。解码时,在屏幕上可以先看到图像的大致面貌,然后逐步细化直到全部还原出来为止。,JPEG的运行模式,4.基于DCT的分层编码模式：它以多种分辨率进行图像编码。先从低分辨率开始,逐步提高分辨率直到与原图像分辨率相同为止。解码时，重建图像的过程也是如此,效果与基于DCT的累进编码模式类似,但处理更复杂,压缩比可更高一些。适应不同情况应用。,静止图像压缩编码标准JPEG,JPEG标准包含两种基本的压缩算法：一种是采用基于DPCM的无损压缩算法。一种是基于离散余弦变换DCT的有损压缩算法,JPEG编码DPCM无损压缩编码模式,1.无损压缩编码JPEG选用差分脉冲编码（DPCM）作为无损压缩编码的方法。不带量化器的DPCM线性预测编码，属于无失真编码；带有量化器的DPCM线性预测编码，属于有失真编码。,预测方式有8种。包括一维预测和二维预测,JPEG编码DPCM无损压缩算法,JPEG编码DPCM无损压缩算法特点：这种方法简单、易于实现，重现的图像质量好。但是压缩率低。压缩比大约为2：1。,JPEG编码DTC有损压缩算法,JPEG基于DCT（离散余弦变换）的有损编码算法框图：,JPEG有损压缩编码算法的主要计算步骤如下：（JPEG第二种模式：基于DCT的顺序编码模