多媒体信息编码.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章多媒体信息编码,1,第一页，共128页。,第,3,章 多媒体信息编码,3,.1,引言,无损数据压缩,3.3,有损压缩编码,2,第二页，共128页。,一、,什么是数据压缩,数据压缩就是在一定的精度损失条件下，以最少的数码表示信源所发出的信号,.,数据压缩处理一般由两个过程组成,:,一是编码过程,即对原始数据进行编码压缩,以便存储和传输,;,二是解码过程,即对压缩的数据进行解压,恢复成可用的数据。,信源,编码,信道,编码,信道,信道,译码,信源,译码,信源,信宿,3.1,引言,3,第三页，共128页。,压缩,/,解压的过程,Encoder,Decoder,Input,Message,Output,Message,Compressed,Message,aaaaaaaaaaaaaaaaaaaa,20a,aaaaaaaaaaaaaaaaaaaa,CODEC,4,第四页，共128页。,二、多媒体数据压缩编码的必要性,压缩编码的必要性和重要性,1.,多媒体系统技术,:,面向三维图形、立体声、彩色全屏幕运动画面的处理技术；,多种媒体承载的由模拟量转化成数字量信息的获取、表示、存储、传输、表现。,2.,未压缩的数字化信息量,1,页,B5,文件数据量约为,6.61MB/P180255mm,2,12,2,像素,/mm,2,8bit1B/8bit=6.61MB/P650MB,的,CDROM,存放,98Pages,5,第五页，共128页。,二、多媒体数据压缩编码的必要性,CD-A,激光唱盘每秒采样位为,1.41Mbps44kHz16bit/Hz,样本,2(,声道,),1.41Mbps650MB,的,CDROM,存放,1,小时音乐,数字音频磁带,(DAT),每秒采样位为,768kbps48kHz16bit/Hz,样本,=768kbps650MB,的,CDROM,存放,2,小时节目,数字电视图像,SIF(Source input format),格式、,NFSC,制、彩色、,4:4:4,采样每帧,:3522403B=253KB,每秒,:253KB30=7.603MBps,每片,CDROM:650MB253kB=2569,帧,/,片 分,/,片,6,第六页，共128页。,二、多媒体数据压缩编码的必要性,2.,未压缩的数字化信息量,数字电视图像,ICCR(International Consultative Committee for Radio),格式、,PAL,制、,4:4:4,采样每帧,:7205763B=1.24MB,每秒,:1.24MB25=31.1MBps,每片,CDROM:650MB1.24MB=524,帧,/,片 秒,/,片,陆地卫星,(LandSat-3),分辨率,23403240,、,4,波段、,7,位采样精度每幅,:2340324074=212Mb,每天,:212Mb30=6.36Gbit,每年,:6.36Gbit365=2321.4Gbit=290GB,7,第七页，共128页。,三、多媒体数据压缩的可能性,多媒体数据压缩的可能性,（,1,）图像数据表示中大量冗余（,2,）图像数据压缩技术,:,利用图像数据冗余性减少数据量方法,1.,空间冗余,静态图像存在的主要冗余,;,采样点颜色之间的空间连贯性,:,区域中各点光强、色彩、饱和度同,;,离散像素采样表示颜色没有利用这种空间连贯性,;,改变颜色的像素存储方式,利用空间连贯性,减少数据量,.,8,第八页，共128页。,图,Bitmap,颜色相同的块,帧内压缩,帧内压缩,例如，在静态图像中有一块表面颜色均匀的区域，在此区域中所有点的光强和色彩以及饱和度都是相同的，因此数据有很大的,空间冗余,。,9,第九页，共128页。,2.,时间冗余,序列图像,(,电视、运动图像,),表示常包含的冗余,;,相邻帧记录了相邻时刻的同一场景画面,移动物位置稍不同,.,运动图像一般为位于一时间轴区间的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为,时间冗余。,同理，语音数据中也存在着时间冗余。,10,第十页，共128页。,时间冗余,11,第十一页，共128页。,3.,视觉冗余,人类的视觉系统由于受生理特性的限制，对于图像场的注意是非均匀的，人对细微的颜色差异感觉不明显。,例如，人类视觉的一般分辨能力为,26,灰度等级，而一般的图像的量化采用的是,28,灰度等级，即存在视觉冗余。,人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允许范围的变化，人也感觉不出来。,(1).,人类视觉系统对图像场的敏感性是非均匀的和非线性的,;,(2).,记录图像时假定视觉系统是均匀和线性的,对不同敏感区同样对待,产生了视觉冗余,.,应对不同敏感部分分开编码,;,12,第十二页，共128页。,(3).,视觉的非均匀性,.,视觉系统对图像的亮度和色彩度的敏感性相差很大，,RGBNTSC,的,YIQ,后发现,视觉系统的亮度,y,的敏感度远高于色度,(I,Q),的敏感度,可对,IQ,允许误差大于,y,的允许误差,;,亮度增加时,视觉系统对量化误差的敏感度降低,人眼辨别能力与物体周围的背景亮度成反比,.,在高亮度区,灰度值的量化可粗糙一些,;,人眼的视觉系统能把图像的边缘和非边缘区域分开处理,边缘区和非边缘区分别编码的依据,;,人眼的视觉系统是把视网膜上的图像分解成若干个空间有向的视频通道后再进行处理,编码时把图像分解成符合这一规律,(,视觉内在特性,),的频率通道,可获大的压缩比,;,小波编码的特性,.,13,第十三页，共128页。,4.,结构冗余,图像纹理区的像素值存在着分布模式,:,如方格状地板图案,;,已知分布模式,可通过某一过程生成图像,.,5.,知识冗余,有些图像的理解与某些知识有相当大的相关性,如人脸的图像有固定结构,;,规律性结构可由先验知识和背景知识获得,知识冗余,;,由已有知识,对图像中物体构造其基本模型,创建对应各种特征的图像库,:,存储时只需保存图像的一些特征参数,;,知识冗余是模型编码主要利用的特征,.,6.,图像区域的相同性冗余,图像中多个区域所对应的像素值相同或者相近,产生重复性存储,;,向量量化,(Vector quantization),是针对这种冗余的压缩编码方法,.,14,第十四页，共128页。,时间域压缩迅速传输媒体信源,频率域压缩并行开通更多业务,空间域压缩降低存储费用,能量域压缩降低发射功率,四、数据压缩的好处,多媒体数据压缩的必要性,数据存储,传输带宽,15,第十五页，共128页。,五,、,压缩编码算法的性能评价指标,数据压缩编码算法的评估指标包括：,压缩比,保真度,算法复杂性,时延,一个好的算法还要考虑：,多媒体系统的软、硬件适应能力。,应用环境,技术标准,16,第十六页，共128页。,压缩编码算法的性能评价指标,压缩比：,压缩比压缩前数据量,/,压缩后数据量,理论上讲，在保证压缩后图像质量的前提下，压缩比越高越好。,保真性：,保真是一个对压缩质量进行评价的参数，分为主观保真度和客观保真度。,客观保真度用重建信号质量与原信号之间的均方误差来衡量：,x,i,和,x,i,分别对应原信号和重建信号，,N,2,为总信息数量。,17,第十七页，共128页。,压缩编码算法的性能评价指标,保真性：,客观保真性：将均方误差作为由数据压缩而产生的噪声能量，定义压缩信噪比为,主观保真性：在规定的观测条件（图像尺寸、对比度、亮度、观测距离等）下，对一组标准图像压缩前后的质量进行对比的主观评定标准。具体做法是对重建信号的特性进行按等级评分，然后根据下式计算平均分,MOS,：,其中，,k,为级别数，,n,i,为该类别的人数，,c,i,为分数。,18,第十八页，共128页。,六、压缩分类（,1,）,1,、按照压缩方法是否产生失真分类,(1),无失真压缩,无失真压缩要求解压以后的数据和原始数据完全一致。解压后得到的数据是原数据的复制，是一种可逆压缩。,无失真压缩法去掉或减少数据中的冗余，恢复时再重新插到数据中，因此是可逆过程,根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的,1/2,1/4,。一些常用的无损压缩算法有赫夫曼,(Huffman),算法和,LZW(Lenpel-Ziv&Welch),压缩算法,19,第十九页，共128页。,(2),有失真压缩,解压以后的数据和原始数据不完全一致，是不可逆压缩方式。有失真压缩还原后，不影响信息的表达。,例如，图像、视频、音频数据的压缩就可以采用有损压缩方法，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。图像、视频、音频数据的压缩比可高达,100:1,，但人的主观感受仍不会对原始信息产生误解。,20,第二十页，共128页。,多媒体信息编码技术主要侧重于有损压缩编码的研究。经过多年的研究与开发,已经出台了一系列有关的国际标准。其中,最著名的是国际标准组织（ISO）制定的JPEG和MPEG。JPEG是静止图像的压缩标准,其压缩比可达401。MPEG（MPEG-1、MPEG-2及MPEG-4）是动态图像的压缩标准,采用MPEG-2标准对NTSC质量视频进行压缩后,网络带宽需求可降低到3.36 Mb/s。其它的标准还有国际电信联合会（ITU）制定的用于可视 、会议电视的和H.263;用于音频的、等。,21,第二十一页，共128页。,六、压缩分类（,2,）,根据码词长度是否相等,分类,定长码（,fixed-length code,）,采用相同的位数（,bit,）对数据进行编码,大多数存储数字信息的编码系统都采用定长码,变长码（,variable-length code,）,采用不相同的位数（,bit,）对数据进行编码，以节省存储空间,示例：,赫夫曼编码,22,第二十二页，共128页。,六、压缩分类（,3,）,按照压缩方法的原理分类,预测编码：,基本思想是利用已被编码的点的数据值，预测邻近的一个像素点的数据值,变换编码,:,基本思想是将图像的光强矩阵变换到系数空间上，然后对系数进行编码压缩,统计编码：,根据信息出现概率的分布特性而进行的压缩编码,*无失真编码*,分析合成编码：,基元和特征参数,混合编码：,混合压缩是利用了各种单一压缩的长处，以求在压缩比、压缩效率及保真度之间取得最佳折衷,23,第二十三页，共128页。,多媒体数据压缩编码方法,PCM,固 定,自适应,自适应,预测编码,固 定,DPCM,M,ADPCM,运动补偿,变换编码,傅立叶,(DFT),离散余弦,(DIT),离散正弦,(DST),沃尔什,-,哈达马,哈 尔,斜变换,卡胡南,-,苏夫,(K,L),小波变换,子带编码,统计编码,(,熵编码,)(,无损,),哈夫曼,算术编码,费 诺,香 农,游程,(RLC),LZW,静图像编码,方块,逐渐浮现,逐层内插,位平面,抖动,电视图像编码,帧内预测,帧间编码,运动估计,运动补偿,条件补充,内 插,帧间预测,基于重要性,矢量量化,滤 波,子 采 样,模型编码,分形编码,混合编码,JPEG,MPEG,图,3-1,多媒体数据压缩编码方法,24,第二十四页，共128页。,无损数据压缩,数据压缩的理论基础为,Shannon,信息论。它一方面给出了数据压缩的理论极限，另一方面又指明了数据压缩的技术途径。,香农,-,范诺,霍夫曼编码,算术编码,RLE,编码,词典编码,统计编码,25,第二十五页，共128页。,信息熵及基本概念,1,信息量与信息熵,信息量,式中，,P(xj),是信源,X,发出,xj,的概率。,I(xj),的含义是，信源,X,发出,xj,这个消息（随机事件）后，接收端收到信息量的量度。,26,第二十六页，共128页。,信源,X,的,“,熵,”,：,信源,X,发出的,x,j,（,j=1,2,n,）共,n,个随机事件的自信息统计平均，即,等概率事件的熵最大,：,当,P(x,1,),1,时，,P(x,2,),P(x,3,),P(x,j,),0,，此时熵为,由上可得熵的范围为：,27,第二十七页，共128页。,平均码长与熵,如果信源,X,输出为一个随机变量序列,a,j,，对,a,j,的编码长度为,L,j,，则,X,的平均码长为：,对信源编码的最小平均码长为该信源的熵，为：,P,j,表示符号,a,j,在,X,中出现的概率,28,第二十八页，共128页。,在编码中用熵值来衡量是否为最佳编码。若以,Lc,表示编码器输出码字的平均码长，则当,LcH(X),有冗余，不是最佳。,Lc,H(X),不可能。,Lc,H(X),最佳编码（,Lc,稍大于,H(X),）。,熵值为平均码长,Lc,的下限。,平均码长,Lc,的计算公式为：,（,j=1,2,n,）,其中：,P(xj),是信源,X,发出,xj,的概率，,L(xj),为,xj,的编码长。,29,第二十九页，共128页。,Entropy Example,【,例,1】,【,例,2】,一幅用,256,级灰度表示的图像，如果每一个象素点灰度的概率均为,P,i,=1/256,，,编码每一个象素点就需要,8,位。,30,第三十页，共128页。,【,例,3】,有一幅,40,个象素组成的灰度图像，灰度共有,5,级，,40,个象素中出现灰度,A,、,B,、,C,、,D,、,E,的象素数如表所示。如果用,3,个位表示,5,个等级的灰度值，也就是每个象素用,3,位表示，编码这幅图像总共需要,120,位。,H,(,S,)=(15/40)log,2,(40/15)+(7/40)log,2,(40/7)+(5/40)log,2,，每个符号用位表示，,40,个象素需用位。,符 号,b,A,B,C,D,E,出现次数,15,7,7,6,5,31,第三十一页，共128页。,2,冗余度、编码效率与压缩比,设原图像的平均码长为,L,，熵为,H(X),，压缩后图像的平均码长为,Lc,，则定义冗余度为：,编码效率：,压缩比：,在数字图像通信系统中，冗余度、编码效率与压缩比是衡量信源特性以及编解码设备性能的重要指标。,32,第三十二页，共128页。,统计编码的基本思想：,其宗旨在于找到一种编码使得平均码长到达熵极限，基本思想就是,对于无记忆的信源，根据码字出现的概率分布特性寻找概率与码字长度间的最优化匹配。,对出现概率较大的符号取较短的码长，而对出现概率较小的符号取较大的码长,，据此对信息进行压缩,。,统计编码,(,信息熵编码,),信息熵编码也称为统计编码，是利用信息源出现的概率来进行编码，常见的信息熵编码包括哈夫曼编码、香农,-,范诺编码、行程编码和算术统计编码等。,33,第三十三页，共128页。,统计编码,统计编码是一种无损编码，常用于图像、文档等要求无损失的压缩中。,实现原理：有些媒体（如图像，文档）数据中各样点值的出现概率在编码前可以统计出，结合其出现概率进行的编码可以充分降低数据量，同时又保证了媒体的质量。,由于在编码过程中仅仅将这些媒体数据看成是一串数据，没有深入到其物理意义中去研究，所以压缩比率并不高。,34,第三十四页，共128页。,1,、仙农,-,范诺,(Shannon-Fano),编码,最早阐述和实现这种编码的是,Shannon(1948,年,),和,Fano(1949,年,),，采用,从上到下,的方法进行编码。,按照符号出现的频度或概率排序,使用递归方法分成两个部分，每一部分具有近似相同的次数，,0,分在上，,1,分在下,35,第三十五页，共128页。,例子,1,例如，,A,，,B,，,C,，,D,和,E,符号,出现的次数,(P,i,),log,2,(1/P,i,),分配的代码,需要的位数,A,15(0.375),1.4150,00,30,B,7(0.175),2.5145,01,14,C,7(0.175),2.5145,10,14,D,6(0.150),2.7369,110,18,E,5(0.125),3.0000,111,15,A,B,C,D,E,0,0,1,1,1,1,0,36,第三十六页，共128页。,例子,2,Symbol Count Code,A15 0 0,B7 0 1,D5 1 1 0,C6 1 0,E5 1 1 1,First division,2,nd division,3,rd division,4,th division,37,第三十七页，共128页。,符号,频率,信息量,总信息量,A,15,1.38,20.68,B,7,2.48,17.35,C,6,2.70,16.20,D,6,2.70,16.20,E,5,2.96,14.82,编码,码长,Bit,数,00,2,30,01,2,14,10,2,12,110,3,18,111,3,15,Total,85.25 bits,Total,89,bits,38,第三十八页，共128页。,2.,霍夫曼编码,基本思想：,对于出现概率较大的符号取较短的码长，而对概率较小的符号则取较长的码长。,霍夫曼编码（,Huffman Encoding,）又称变长度编码，或最优编码，即遵照霍夫曼编码原则的结果一定是平均码长最短。,霍夫曼编码的特点：只适用于有限个离散信源；且实现起来相当复杂。,39,第三十九页，共128页。,具体的编码步骤如下：,（,1,）将信源符号出现的概率按由大到小的顺序排序。,（,2,）将两处最小的概率进行组合相加，形成一个新的概率。,（,3,）将新出现的概率与未编码的字符一起重新排序。,（,4,）重复步骤（,2,）、（,3,），直到出现的概率和为,1,。,（,5,）分配代码。代码分配从最后一步开始反向进行，对最后两个概率一个赋予,0,代码，一个赋予,1,代码。如此反向进行到开始的概率排列。在此过程中，若概率不变则采用原代码。,40,第四十页，共128页。,例,4,：,设输入图像的灰度级,a1,a2,a3,a4,a5,a6,出现的概率分别是、。试进行哈夫曼编码，并计算编码效率、压缩比、冗余度。,编码步骤：,（,1,）初始化，根据符号概率的大小按由大到小顺序对符号进行排序，如图,4-2,所示。,（,2,）把概率小的两个符号组成一个节点，如图,4-2,中的,a5,、,a6,组成节点,P1,。,（,3,）重复步骤,2,，得到节点,P2,、,P3,、,P4,、,P5,，形成一棵,“,树,”,，其中,P5,为根节点。,（,4,）从根节点,P5,开始到相应于每个符号的,“,树叶,”,，从上到下标上,1,（上枝）或者,0,（下枝），至于哪个为,1,哪个为,0,则无关紧要，最后的结果仅仅是分配的代码不同，而代码的平均长度是相同的。,最终编码结果为：,a1=1,a2=000,a3=011,a4=001,a5=0100,a6=0101,41,第四十一页，共128页。,由公式（,4-6,）可求得图像信源熵是：,H(X)=,=-,（,log,2,log,2,log,2,0.12+,log,2,log,2,log,2,）,=2.25 bit,根据哈夫曼编码过程图给出的结果，可求出它的平均码字长度：,编码效率为：,压缩之前,8,个符号需要,3,个比特量化，经过压缩之后的平均码字长度为，其压缩比为：,冗余度为：,r=1-=3.4%,42,第四十二页，共128页。,Huffman Coding,的问题,错误传播,(error propagation),：霍夫曼码没有错误保护功能。在译码时，如果码串中没有错误，就能一个接一个地正确译出代码。但如果码串中发生错误，不但这个码本身译错，更糟糕的是一错一大串。,霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑,(,必须在存储代码前先进行译码,),。尽管如此，霍夫曼码还是得到广泛应用。,由于一个节点的上下两个分支即可以赋值,“,0,”,，也可以赋值,“,1,”,，因此同一信源对应的霍夫曼编码并不唯一，但平均码长是相同的。,43,第四十三页，共128页。,霍夫曼编码,霍夫曼编码为唯一可译码，即码的任意一串有限长的码符号序列只能被唯一译成所对应的信源符号。,霍夫曼对不同的信源，其编码效率是不同的。当信源概率分布很不均匀时，霍夫曼码会具有显著效果。,如果信源的实际概率模型与构码时所假设的概率模型有差异，实际的平均码字将大于预期值，编码效率将下降。这种情况下，唯一的解决办法就是更换码表，使之与实际概率模型匹配。,44,第四十四页，共128页。,Huffman,与,Shannon-Fano,特点,霍夫曼编码与仙农,-,范诺编码这两种方法都自含同步码，即在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。,霍夫曼编码方法的编码效率比仙农,-,范诺编码效率高一些。,Theorem:,The Huffman algorithm generates an optimal prefix code.,45,第四十五页，共128页。,Huffman Coding Example,Character,X6,X3,X4,X5,X1,X7,X2,Probability,0.25,0.2,0.15,0.15,0.1,0.1,0.05,0.45,0.25,0.15,0.3,1.0,0.55,Char,X6,X3,X4,X5,X1,X7,X2,Code,10,11,001,011,010,0000,0001,1,1,1,0,0,0,1,0,1,0,0,1,错误,正确,46,第四十六页，共128页。,3.,算术编码,在算术编码中，消息用,0,到,1,之间的实数进行编码。,图像数据压缩标准如,JPEG,中扮演重要角色,不必预先定义概率模型，自适应模式具有独特的点；,信源符号概率接近时，建议使用算术编码，这种情况,下其效率高于,Huffman,编码,(,约,5%),。,JPEG,扩展系统采用。,基本思想：,类似于,Huffman,编码，对概率较大的符号采用短码，对概率较小的符号采用长码，但,Huffman,编码只能使用整数比特，而它可以利用分数比特逼近于信源。,注意,:,在算术编码的使用中存在版权问题。,JPEG,标准说明的算术编码的一些变体方案属于,IBM,，,AT&T,和,Mitsubishi,拥有的专利。,47,第四十七页，共128页。,分类：,(1).,静态算术编码：信源符号概率是固定的算术编码。,(2).,自适应算术编码：信源符号概率是动态变化的算术编码。,首先假定各符号概率的初始值相同，然后其概率根据出现的情况做相应的改变。,自适应模式可以不预先定义概率模型，但要求编码器和译码器使用相同的概率模型。,自适应算术编码的编码效率很高，当信源符号概率比较接近时，可优于,Huffman,编码。,48,第四十八页，共128页。,基本原理：,两个基本参数：符号的概率和它的编码间隔。,信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在,0,到,1,之间。,(1).,根据信源中出现不同符号序列的概率不同，把,0,1),区间划分为互不重叠、宽度恰好是各符号序列的概率的子区间。,(2).,信源中的各符号序列将可用各子区间中的任意一个实数表示，这个数就是该符号所对应的码。,算术编码步骤：,(1).,建立信源概率表。,(2).,扫描信源发出的符号序列，对其进行编码。,49,第四十九页，共128页。,算术编码的伪代码描述,set,Low,to 0,set,High,to 1,while there are input,symbols,do,take a,symbol,CodeRange,=,High,Low,High,=,Low,+,CodeRange,*,HighRange(symbol),Low,=,Low,+,CodeRange,*,LowRange(symbol),end of while,output,Low,50,第五十页，共128页。,算术解码的伪代码描述,get encoded number,do,find,symbol,whose range straddles the encoded number,output the,symbol,range=symbol.LowValue,symbol.HighValue,substract symbol.LowValue from encoded number,divide encoded number by range,until no more symbols,51,第五十一页，共128页。,算术编码举例,采用固定模式符号概率分配如下：,字符,：,a e i o u,概率,：,范围,：,0,，,0.2),，,0.5),，,0.6),，,0.8),，,1.0),编码数据串为,eai,。令,high,间隔的高端，,low,为低端，,range,为间隔的长度，,rangelow,为编码字符分配的间隔低端，,rangehigh,为编码字符分配的间隔高端,。,初始,high=1,，,low=0,，,range=high-low,，,一个字符编码后新的,low,和,high,按下式计算：,low=low+rangerangelow,；,high=low+rangerangehigh,。,52,第五十二页，共128页。,(1),在第一个字符,e,被编码时，,e,的，因此：,此时分配给,e,的范围为，,0.5),(2),第二个字符,a,编码时使用新生成范围，,0.5),，,a,的,rangelow=0,，因此：,范围变成，,0.26),53,第五十三页，共128页。,(3),对下一个字符,i,编号，,i,的，则：,结果,：用，,0.236),表示数据串,eai,，如果解码器知道最后范围是，,0.236),，它马上可解得一个字符为,e,，然后依次得到惟一解,a,、,i,，最终得到,eai,。,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,算术编码过程表示,54,第五十四页，共128页。,算术编码举例,信源符号,a,i,a,1,a,2,a,3,a,4,概率,P,i,P,1,=0.5,P,2,=0.25,P,3,=0.125,P,4,=0.125,初始编码间隔,0,0.5),0.5,0.75),0.75,0.875),0.875,1),输入序列为,xn:a2,a1,a3,。,编码结果：,10011,55,第五十五页，共128页。,译码,输入：,10011,接受的数字,间隔,译码输出,1,0.5,1),-(,可能有三种值）,0,0.5,0.75),a,2,0,0.5,0.609375),a,1,1,0.5625,0.609375),-,1,0.59375,0.609375),a,3,56,第五十六页，共128页。,在算术编码中需要注意的几个问题,：,（,1,）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有,16,位、,32,位或者,64,位的精度，因此这个问题可使用比例缩放方法解决。,（,2,）算术编码器对整个消息只产生一个码字，这个码字是在间隔,0,1),中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。,（,3,）算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,57,第五十七页，共128页。,4,、行程编码,(,游程编码,),RLE(Run Length Encoding),编码,现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。,58,第五十八页，共128页。,在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的,像素数目,就可以，或者存储像素的颜色值，以及具有相同颜色值的行数。,这种压缩编码称为,行程编码,(run length encoding,，,RLE),，具有相同颜色并且是连续的像素数目称为,行程长度。,例如,字符串,AAABCDDDDDDDDBBBBB,，,利用,RLE,原理可以压缩为,3ABC8D5B,RLE,编码简单直观，编码,/,解码速度快，因此许多图形和视频文件，如及,AVI,等格式文件的压缩均采用此方法,.,59,第五十九页，共128页。,RLE,行程编码：不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值以及具有相同颜色值的行数。,行程长度：具有相同颜色并且是连续的象素数目。,控制符,重复次数,被重复字符,60,第六十页，共128页。,由于一幅图像中有许多颜色相同的图块，用一整数对存储一个像素的颜色值及相同颜色像素的数目（长度）。例如：,（,G,，,L,）,长度,颜色值,编码时采用从左到右，从上到下的排列，,每当遇到一串相同数据时就用该数据及,重复次数代替原来的数据串。,000000003333333333,222222222226666666,888888888888888888,555555555555553333,222222222222222222,(0,8)(3,10)(2,11)(6,7),(1,18)(1,6)(5,12)(8,18),(5,14)(3,4)(2,18),18*7,的像素颜色仅用,11,对数据,例题：,61,第六十一页，共128页。,游程长度编码特点：,直观，经济；,是一种无损压缩；,压缩比取决于图像本身特点，相同颜色图像块越大，图像块数目越少，压缩比越高。,适用于计算机生成的图像，例如。,BMP,、,TIF,等，不适于颜色丰富的自然图像。,这并不是说,RLE,编码方法不适用于自然图像的压缩，相反，在自然图像的压缩中少不了,RLE,，只不过是不能单纯使用,RLE,一种编码方法，需要和其他的压缩编码技术联合应用。,62,第六十二页，共128页。,、词典编码,词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是,利用了信源符号之间的相关性。,字符串与代号的对应表就是词典。,实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。,属于通用编码技术,和,无损压缩技术,有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。,词典编码：不需要知道统计特性,词典编码分类,第一类词典编码,第二类,词典编码,63,第六十三页，共128页。,1.,第一类词典编码,第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的,“,指针,”,。,LZ77,算法,LZSS,算法,.,吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。,64,第六十四页，共128页。,LZ77,算法,第一类词典编码里：所指的“词典”是指用以前处理过的数据来表示编码过程中遇到的重复部分。,这类编码中的所有算法都是以,Abraham Lempel,和,Jakob Ziv,在,1977,年开发和发表的称为,LZ77,算法为基础的,Jacob Ziv,Abraham Lempel,A Universal Algorithm for Sequential Data Compression,IEEE Transactions on Information Theory,23(3):337-343,May 1977.,一般来说，现在流行的,winzip,，,winrar,以及,unix,下的,compress,使用的都是该算法,-LZ77,65,第六十五页，共128页。,LZ77,算法,LZ77,算法在某种意义上又可以称为,“,滑动窗口压缩,”,，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。,使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。,“,词典,”,是隐含的，指用以前处理过的数据。,66,第六十六页，共128页。,LZ77,算法,首先介绍算法中用到的几个术语：,输入数据流,(input stream),：要被压缩的字符序列。,字符,(character),：输入数据流中的基本单元。,编码位置,(coding position),：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。,前向缓冲存储器,(Lookahead buffer),：存放从编码位置到输入数据流结束的字符序列的存储器。,窗口,(window),：指包含,W,个字符的窗口，字符从编码位置开始向后数，也就是最后处理的字符数。,指针,(pointer),：指向窗口中的匹配串且含长度的指针。,A,A,B,C,B,B,A,B,C,A,W=5,已编码,未编码,B=4,67,第六十七页，共128页。,LZ77（及其变体）的压缩算法使用了两个缓存：滑动 缓存包含了前面处理过的N个源字符，前向缓存包含了将要处理的下面L个字符。算法尝试将前向缓存开始的两个或多个字符与滑动 缓存中的字符串相匹配。如果没有发现匹配，前向缓存的第一个字符输出并且移入滑动窗口，滑动窗口中最久的字符被移出。如果找到匹配，算法继续扫描以找出最长的匹配。然后匹配字符串作为三元组输出（指示标记、指针和长度）。对于K个字符的字符串，滑动窗口中最久的K个字符被移出，并且被编码的K个字符被移入窗口。,68,第六十八页，共128页。,LZ77,编码的基本流程,1,、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤,2,，否则进行步骤,3,。,2,、输出三元符号组,(off,len,c),。其中,off,为窗口中匹配字符串相对窗口边界的偏移，,len,为可匹配的长度，,c,为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动,len+1,个字符，继续步骤,1,。,3,、输出三元符号组,(0,0,c),。其中,c,为下一个字符。然后将窗口向后滑动,1,个字符，继续步骤,1,。,69,第六十九页，共128页。,LZ77,算法,70,第七十页，共128页。,例子,位置,1,2,3,4,5,6,7,8,9,字符,A,A,B,C,B,B,A,B,C,C,B,A,B,B,C,B,A,A,编码步骤,编码位置,匹配串,前向缓冲中第一个字符,输出,(ptr,len)ch,1,1,-,A,(0,0)A,2,2,A,B,(1,1)B,3,4,-,C,(0,0)C,4,5,B,B,(2,1)B,5,7,A B,C,(5,2)C,W=5,B=2,每次移动窗口和编码位置,Len+1,Len=0,Len=1,Len=0,Len=1,71,第七十一页，共128页。,LZSS,算法,1982,年由,Storer,和,Szymanski,改进,LZ77,LZ77,的问题,:,LZ77,通过输出真实字符解决了在窗口