多媒体数据压缩技术(共80张PPT).pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,07 十一月 2021,第,6,章 多媒体数据压缩技术,数据压缩的基本概念,数据压缩的发展历程,数据压缩的技术基础,常用的无损数据压缩方法,常用的有损数据压缩方法,数据压缩国际标准,第1页，共80页。,数据压缩,通俗地说，数据压缩就是用最少的数码来表示信号其作用是：能较快地传输各种信号，如传真、,Modem,通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如,CD-ROM,、,VCD,和,DVD,等；降低发信机功率，这对于多媒体移动通信系统尤为重要。由此看来，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的原因。,第2页，共80页。,6.1,多媒体数据压缩概述,数据压缩的重要性,压缩的可能性,冗余的种类,压缩方法分类,第3页，共80页。,6.1.1,数据压缩的重要性,多媒体数据为什么要进行压缩，主要原因有：,1.,原始采样的媒体数据量巨大;,2.,有效利用存储器存储容量;,3.提高通信线路的传输效率;,4.消除计算机系统处理视频,I/O,瓶颈,第4页，共80页。,6.1.2,压缩的可能性,多媒体数据就像海绵一样是可以压缩的，因为多媒体数据包括两部分内容：信息和冗余数据，信息是有用的数据，而冗余数据就是无用的内容，可以压缩掉。,冗余的具体表现就是相同或者相似信息的重复。,冗余为数据压缩技术的应用提供了可能,第5页，共80页。,6.1.3,冗余的种类,1.,空间冗余,静态图像中存在的最主要的一种数据冗余。同一景物表面上采样点的颜色之间往往存在着空间连贯性，但是基于离散像素采样来表示物体颜色的方式通常没有利用这种连贯性。例如：图像中有一片连续的区域，其像素为相同的颜色，空间冗余产生。,第6页，共80页。,6.1.3,冗余的种类,2.,时间冗余,序列图像中经常包含的冗余。一组连续的画面之间往往存在着时间和空间的相关性，但是基于离散时间采样来表示运动图像的方式通常没有利用这种连贯性。例如：房间里的两个人在聊天，在这个聊天的过程中，背景（房间和家具）一直是相同的，同时也没有移动，而且是同样的两个人在聊天，只有动作和位置的变化。,第7页，共80页。,6.1.3,冗余的种类,3.,结构冗余,在某些场景中，存在着明显的图像分布模式，这种分布模式称作结构。图像中重复出现或相近的纹理结构，结构可以通过特定的过程来生成。例如：方格状的地板，蜂窝，砖墙，草席等图结构上存在冗余。已知分布模式，可以通过某一过程生成图像。,第8页，共80页。,6.1.3,冗余的种类,4.,知识冗余,有些图像的理解与某些知识有相当大的相关性。例如：人脸的图像有固定的结构，嘴的上方是鼻子，鼻子的上方是眼睛，鼻子位于正脸图像的中线上。这类规律性的结构可以由先验知识和背景知识得到。根据已有的知识，对某些图像中所包含的物体，我们可以构造其基本模型，并创建对应各种特征的图像库，进而图像的存储只需要保存一些特征参数，从而大大减少数据量。知识冗余是模型编码的基础。,第9页，共80页。,6.1.3,冗余的种类,5.,视觉冗余,人类的视觉系统对图像场的敏感性是非均匀和非线性的。对亮度变化敏感，而对色度的变化相对不敏感；在高亮度区，人眼对亮度变化敏感度下降；对物体边缘敏感，内部区域相对不敏感；对整体结构敏感，而对内部细节相对不敏感。可以根据这些视觉特性对图像信息进行取舍。,第10页，共80页。,6.1.3,冗余的种类,6.,图像区域的相同性冗余,图像中的两个或者多个区域所对应的所有像素值相同或者相近，从而产生数据重复性存储。记录了一个区域中各像素的颜色值，则与其相同或相近的其他区域就不再记录其中各像素的值。这种冗余是向量量化的基础。,7.,纹理的统计冗余,有些图像纹理尽管不严格服从某个分布规律，但是在统计意义上服从这种规律。,第11页，共80页。,6.1.5,压缩方法分类,根据解码后数据与原始数据是否完全一致，数据压缩方法划分为两类,：,无损压缩法,，无损压缩是指使用压缩后的数据可以解压缩，且解压之后的数据与原来的数据完全相同。它利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为2:1到5:1。,如,Huffman,编码、算术编码、行程长度编码等。,有损压缩法,，是指使用压缩后的数据进行解压缩，解压之后的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解。,常用的有变换编码和预测编码。,第12页，共80页。,6.1.4,压缩原理,数据压缩方法的分类,第13页，共80页。,6.1.5,压缩方法分类,根据压缩方法的原理，可将其划分为以下几种：,1.,预测编码（适用于空间冗余和时间冗余）,预测编码的方法是从相邻像素之间有较强的相关性特点考虑，比如当前像素的灰度或颜色信号，数值上与其相邻像素总是比较接近，除非处于边界状态，那么，当前像素的灰度或颜色信号的数值，可用前面已出现的像素的值进行预测（估计），得到一个预测值（估计值），将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法称为预测编码方法。预测编码方法分,线性预测,和,非线性预测编码,两种。,第14页，共80页。,6.1.5,压缩方法分类,2.,变换编码,变换编码不是直接对空域图像信号进行编码，而是首先将空域图像信号映射变换到另一个正交矢量空间（变换域或频域），产生一批变换系数，然后对这些变换系数进行编码处理。其中关键问题是在时域或空域描述时，数据之间相关性大，数据冗余度大，经过变换在变换域中描述，数据相关性大大减少，数据冗余量减少，参数独立，数据量少，这样再进行量化，编码就能得到较大的压缩比。目前常用的正交变换有：傅立叶,(Fouries),变换、沃尔什,(Walsh),变换、哈尔,(Haar),变换、斜,(Slant),变换、余弦变换、正弦变换、,K-L(Karhunen-Loeve),变换等。,第15页，共80页。,6.1.5,压缩方法分类,3.,量化与向量量化编码,量化过程就是将连续的模拟量通过采样，离散化为数字量的过程。对像素进行量化时，可以一次量化多个点，这种方法就是向量量化。例如，可以每次量化相邻的两个点，这样就可将这两点用一个量化码字表示，达到数据压缩的目的。其数据压缩能力与预测编码方法相近，本质上也是针对统计冗余的压缩。,第16页，共80页。,6.1.5,压缩方法分类,4.,信息熵编码,信息熵编码就是利用信息的相关性压缩冗余度。它根据信息熵原理，对出现概率大的用短的码字表示，反之用较长的码字表示，目的是减少符号序列的冗余度，提高码字符号的平均信息量。最常见的方法有哈夫曼编码、行程编码和算术编码。,5.,混合编码,它是变换编码和预测编码的结合编码方法，通常有两种形式：一种方法是在某一方向进行酉变换，在另一方向上用,DPCM对变换系数进行预测编码；另一种是二维变换加上时间方向上的,DPCM,预测。,第17页，共80页。,6.1.4,压缩原理,1.,图像压缩系统的组成,变换器,量化器,编码器,输入,图像,二进制位流,第18页，共80页。,6.1.4,压缩原理,A.,变换器,变换器把输入的图像数据加上一对一的映射，经过变换以后所形成的图像数据比原始图像数据更有利于压缩。,映射的方法有三种：,1.,线性预测映射,：将像素值映射到它和预测值之间的差。,2.,单映射,：如离散余弦变换（,DCT,），把图像映射到若干个系数。,3.,多映射,：如子带分解和小波变换。,第19页，共80页。,6.1.4,压缩原理,B.,量化器,量化器用来生成一组有限个符号用来表示压缩的图像。量化是多到一的映射，是丢失信息和不可逆的。,有两种量化方式：,1.,标量量化,：对像素逐个量化。,2.,矢量量化,:,多个像素为一组同时量化。,第20页，共80页。,6.1.4,压缩原理,C.,编码器,编码器给量化器输出的每个符号指定一个码字，即生成二进制位流。,有两种编码方式：,1.,定长编码,：每个符号指定的码字具有相同的长度。,2.,变长编码（熵编码）,：根据符号出现的频率来决定为其指定码字的长度，频率高则码字短，反之则长。,第21页，共80页。,6.1.4,压缩原理,2.,图像压缩说明,视频压缩与语音相比，语音的数据量较小，且基本压缩方法已经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。,压缩处理过程有两个过程，,编码过程,是将原始数据经过编码进行压缩，以便存储与传输；,解码过程,是对编码数据进行解码，还原为可以使用的数据。,第22页，共80页。,6.1.4,压缩原理,3.,判断一种压缩方法优劣的标准,衡量一种数据压缩技术的好坏有四个重要的指标：,压缩比大,：即压缩前后所需要的信息存储量之比要大。,算法简单,：实现压缩的算法简单，压缩、解压速度快，尽可能地做到实时压缩解压。,恢复效果好,：恢复效果好，要尽可能地恢复原始数据。,压缩能否用硬件实现,.,第23页，共80页。,6.2,数据压缩的发展历程,1952,年提出有效的压缩方法,Huffman,编码；,80,年代，设计出更能接近信息论中“熵”极限的编码方法,算术编码。,1984,年，,Terry Welch,实现了,LZ78,算法的一个变种,LZW,80,年代中期以后，人们对,LZ77,进行了改进，目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的,PKZip,到现在的,WinZip,，特别是随着,Internet,上文件传输的流行，,ZIP,格式成为了事实上的标准，,第24页，共80页。,6.3,数据压缩的技术基础,熵的概念,数据压缩模型,数据压缩编码,第25页，共80页。,6.3.1,熵的概念,数据压缩不仅起源于,40,年代由,Claude Shannon,首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“,熵,”,(Entropy),来表示一条信息中真正需要编码的信息量，即数据压缩的理论极限。对于任何一种无损数据压缩，最终的数据量一定大于信息熵，数据量越接近于熵值，说明其压缩效果越好，假定一种无损数据压缩之后数据量小于信息熵，只能说明一个问题，说明其数据压缩肯定出错了。,第26页，共80页。,行程编码（RLE，Run-length encoding）是一种统计编码，属于无损压缩编码。,量化过程就是将连续的模拟量通过采样，离散化为数字量的过程。,图像中的两个或者多个区域所对应的所有像素值相同或者相近，从而产生数据重复性存储。,d=i=0N-1Pib(yi),压缩比大：即压缩前后所需要的信息存储量之比要大。,在高亮度区，人眼对亮度变化敏感度下降；,解码过程是对编码数据进行解码，还原为可以使用的数据。,有些图像，尤其是计算机生成的图形往往有许多颜色相同的图块。,算法简单：实现压缩的算法简单，压缩、解压速度快，尽可能地做到实时压缩解压。,原始采样的媒体数据量巨大;,3333 到，c 从 0.,表6-12 静态统计模型的算术解码过程,对于上面的例子中并不知道任何一个字符的概率，只能采用自适应统计模型，最初概率都为相等的，即Pa=1/3，Pb=1/3，Pc1/3。,6.3.1,熵的概念,信息熵是指一组数据所携带的信息量,，,它定义为：,H=-,i=,0,N-1,P,i,log,2,P,i,N,为数据类数或码元个数,，,P,i,为码元,y,i,发生的概率.,为使信息编码单位数据量,d,接近于或等于,H,，,应设：,d=,i=,0,N-1,P,i,b(y,i,),其中,b(y,i,),是分配给码元,y,i,的比特数，理论上应取,b(y,i,)=-,log,2,P,i,.,实际一般取,b(y,0,)=b(y,1,)=b(y,K-1,),.,第27页，共80页。,6.3.1,熵的概念,举个例子,:,字符串：,aabbaccbaa,字符串长度为,10,字符,a,、,b,、,c,分别出现了,5,、,3,、,2,次，则,a,、,b,、,c,在信息中出现的概率分别为、，他们的熵分别为：,Ea=-log2(0.5)=1,该信息源的熵为：,E=Ea*0.5+Eb*0.3+Ec*0.2=1.4855,位,第28页，共80页。,6.3.2,数据压缩模型,在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做数据压缩模型，主要有,静态统计模型,和,自适应模型,。,预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩术语里叫做“,静态统计模型,”。,在实际应用中，“,静态统计模型,”应用的很少。,第29页，共80页。6.3.2,数据压缩模型,真正的压缩程序中使用的大多是一种叫“,自适应模型,”的东西。,自适应模型,可以说是一台具有学习功能的自动机。它是在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，它统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。,第30页，共80页。,6.3.2,数据压缩模型,上面提到的模型可以统称为“,统计模型,”，因为它们都是基于对每个字符出现次数的统计得到字符概率的。另一大类模型叫做“,字典模型,”。他并不直接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息。匹配越长，压缩效果越好。事实上，字典模型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。,第31页，共80页。,6.3.3,数据压缩编码,通过模型，已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。最先被考虑的问题是，如果对,a,用,3,个二进制位就可以表示，而对,b,用,4,个二进制位就可以表示，那么，,在解码时，面对一连串的二进制流，怎么知道哪三个位是,a,，哪四个位是,b,呢？,第32页，共80页。,6.3.3,数据压缩编码,于是有了一种叫“,前缀编码,”的技术。,该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位,0,或,1,组成。电话号码就是遵循着“前缀编码”技术来实现的，避免了,8,位的电话号码拨了,5,位就打通了另一个电话。,第33页，共80页。,6.3.3,数据压缩编码,一个最简单的例子如下表（,表,6-1,）,第34页，共80页。,6.3.3,数据压缩编码,有了上面的码表，一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：即,DABBDCEAAB,下一个问题是：象上面这样的前缀编码只能表示整数位的符号，对几点几位的符号只能用近似的整数位输出，,那么怎样输出小数位数呢？,(,将在后面对算术编码作详细的讨论。,),第35页，共80页。,6.3.3,数据压缩编码,不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的编码方法，尽量接近期望得到的熵值。所以，压缩效果的好坏一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。,换句话说，,压缩,=,模型,+,编码,第36页，共80页。,6.4,常用的无损数据压缩方法,香农-范诺与哈夫曼编码,算术编码,行程RLE编码(run length encoding),词典编码(dictionary encoding),第37页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,香农,-,范诺编码（,Shannon-Fano,）,香农,-,范诺编码算法步骤：,将待编码的符号按符号出现概率从大到小排序。,将排好序的符号分成两组，使这两组符号概率和相等或尽可能的相近。,将第一组赋值为,0,，第二组赋值为,1,。,对每一组，只要不是一个符号，就重复步骤,2,的操作，否则操作完毕。,第38页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,：,有一串由,6,个字母组成的长度为,50,的字符串，字母分别,A,、,B,、,C,、,D,、,E,和,F,，其中,A,出现,3,次，,B,出现,5,次，,C,出现,15,次，,D,出现,11,次，,E,出现,12,次，,F,出现,4,次，请使用香农,-,范诺对其进行编码。,第39页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,解题步骤：,使用表,6-2,列出字母在字符串中的概率统计（这里使用的是出现次数，因为出现次数和概率成比例，也就是出现次数大则概率也大）：,第40页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,:,例,6-1,解题步骤：,对符号按出现次数的多少进行排序，得表,6-3,所示：第41页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,解题步骤：,然后对符号进行分组，将其分为概率和最接近的两组即为（,C,、,E,）和（,D,、,B,、,F,、,A,），其中（,C,、,E,）赋值为,0,，（,D,、,B,、,F,、,A,）赋值为,1,，依次递归下去。使用二叉树左支为,0,，右支为,1,来进行编码，其最终实现如图,6-6,所示：,第42页，共80页。,第43页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,解题步骤：,使用香农,-,范诺编码算法得到的编码表，如表,6-4,所示：,第44页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,解题步骤：,总共需要,43+35+215+211+212+44=119,位，而如果用,ASCII,来进行表示的话，至少要用到,508=400,位；如果用等长码,3,位二进制来表示六个字母的话，这样需用到,503=150,位，从这两方面都实现数据压缩。,第45页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-1,解题步骤：,再来看一看压缩效果如何，这时就需来计算数据压缩的极限,熵的值：,这就是说每个符号用位表示，,50,个像素需用,118,位。,第46页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,哈夫曼编码,（,Huffman,）,哈夫曼（,Huffman编码算法步骤：,初始化，根据符号出现的次数按由大到小顺序对符号进行排序。,把概率最小的两个符号组成一个节点，节点为两符号次数之和，去掉已取出的两个节点，加入这两节点之和，重新排序，直至只有一个数据且该数据的值所有符号出现的总次数相同为止，跳向,4,步骤。,第47页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,哈夫曼（,Huffman,）编码算法步骤：,重复步骤,2,，得到新节点，形成一棵“树”。,从根节点开始到相应于每个符号的“树叶”，从上到下标上“,0”,或“,1”,。通常左支标为,0,，右支标为,1,。,从根节点开始顺着树枝到每个叶子分别写出每个符号的代码。,第48页，共80页6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,：,就上面关于,Shannon-Fano,编码的例子：,有一串由,6,个字母组成的长度为,50,的字符串，字母分别,A,、,B,、,C,、,D,、,E,和,F,，其中,A,出现,3,次，,B,出现,5,次，,C,出现,15,次，,D,出现,11,次，,E,出现,12,次，,F,出现,4,次，请使用哈夫曼对其进行编码。,第49页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,对符号按出现次数的多少进行排序，得表,6-4,所示：,第50页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：然后选择其中最小的两个符号，组成一个节点，如图,6-7,所示：,出现次数最少的,两个符号组成的二叉树,图,6-7,第51页，共80页。,预测编码的方法是从相邻像素之间有较强的相关性特点考虑，比如当前像素的灰度或颜色信号，数值上与其相邻像素总是比较接近，除非处于边界状态，那么，当前像素的灰度或颜色信号的数值，可用前面已出现的像素的值进行预测（估计），得到一个预测值（估计值），将实际值与预测值求差，对这个差值信号进行编码、传送，这种编码方法称为预测编码方法。,1，因此它的间隔就取，0.,平均码长=熵，但都是接近熵，而且越接近熵，说明压缩效率越高。,在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做数据压缩模型，主要有静态统计模型和自适应模型。,对于任何一种无损数据压缩，最终的数据量一定大于信息熵，数据量越接近于熵值，说明其压缩效果越好，假定一种无损数据压缩之后数据量小于信息熵，只能说明一个问题，说明其数据压缩肯定出错了。,如上图所示圆圈标识第三步。,译码过程如表6-12所示：,对整体结构敏感，而对内部细节相对不敏感。,有些图像，尤其是计算机生成的图形往往有许多颜色相同的图块。,译码过程如表6-12所示：,在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做数据压缩模型，主要有静态统计模型和自适应模型。,1 香农-范诺与哈夫曼编码,对于上面的例子中并不知道任何一个字符的概率，只能采用自适应统计模型，最初概率都为相等的，即Pa=1/3，Pb=1/3，Pc=1/3。,消除计算机系统处理视频I/O瓶颈,2048 到，c 从 0.,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,去掉刚才的两个符号，加入它们的和，重新排序如表,6-5,所示：,第52页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,继续选择其中最小的两个符号，组成一个新节点，如图,6-8,所示：,第二次取次数最少的,两个符号继续组成二叉树,图,6-8,第53页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例6-2,解题步骤：,依次类推，进行递归，排序的表如,6-6,所示：,生成的二叉树如图,6-9,所示,图,6-9,第54页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,依次类推，进行递归，排序的表如,6-7,所示：,第55页，共80页。,生成的二叉树如图,6-10,所示,图,6-10,第56页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,依次类推，进行递归，排序的表如,6-8,所示：,生成的二叉树如图,6-11,所示,图,6-11,第57页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,图,6-11,图,6-12,对其进行编码，,左为,0,，右为,1,，,如图,6-12,所示：,例,6-2,解题步骤：,第58页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,使用,Huffman,编码算法得到的编码表，如表：,第59页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,例,6-2,解题步骤：,总共需要,43+35+215+211+212+44=119,位，与香农,-,范诺编码算法得到的最后数据相同，也同样实现了压缩，但是这只是巧合，,通常情况下哈夫曼编码比香农,-,范诺编码的效率要高一些。,第60页，共80页。,6.4.1,香农,-,范诺与哈夫曼编码,香农,-,范诺编码和,huffman,编码：,平均码长,=,熵，但都是接近熵，而且越接近熵，说明压缩效率越高。,保证解码的唯一性，短字码不构成长字码的前缀。,在接收端需要一个与发送端相同的代码表。,第61页，共80页。,6.4.2,算术编码,算术编码的基本原理,将编码的消息表示成实数,0,和,1,之间的一个间隔，取间隔中的一个数来进行表示消息，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。,通常情况下，如采用概率统计模型为静态统计模型，算术编码用到两个基本的参数：,符号的概率,和它的,编码间隔,。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在,0,到,1,之间。编码过程中的间隔决定了符号压缩后的输出；如采用概率统计模型为自适应统计模型，则最初的信源概率均等。,第62页，共80页。,6.4.2,算术编码,自适应统计模型的算术编码与解码,例,6-3,：假设某条信息中可能出现的字符只有,a,、,b,、,c,三种，要压缩保存的信息为,abba,。,例,6-3,解题步骤：,对于上面的例子中并不知道任何一个字符的概率，只能采用自适应统计模型，最初概率都为相等的，即,Pa=1/3,，,Pb=1/3,，,Pc=1/3,。并将,0-1,区间按照概率的比例分配给三个字符，即,a,从,0,到，,b,从,0.3333,到，,c,从,0.6667,到。如图,6-13,所示圆圈标识,第一步。,第63页，共80页。,图,6,13,自适应算术编码,第64页，共80页。,6.4.2,算术编码,例,6-3,解题步骤：,当第一个字符,a,出现时，就可以确定其数据间隔区域一定是在他的概率间隔范围内，如下图中的,0,到，这时由于多了字符,a,，三个字符的概率分布变成：,Pa=2/4,，,Pb=1/4,，,Pc=1/4,。这时的总的概率区间将不是参照,0,到,1,之间，而是在已经确定第一个字符出现之后的概率区间，即,0,到,0.3333,这一区间。此时的,a,从,0,到，,b,从,0.1667,到，,c,从,0.25,到。如上图所示圆圈标识,第二步,。,第65页，共80页。,6.4.2,算术编码,例,6-3,解题步骤：,当第二个字符,b,出现时，就可以确定其数据间隔区域为,0.1667,到，这时由于多了字符,b,，三个字符的概率分布变成：,Pa=2/5,，,Pb=2/5,，,Pc=1/5,。就按照新的概率分布比例划分,0.1667,到,0.25,这一区间，此时的,a,从,0.1667,到，,b,从,0.2,到，,c,从,0.2333,到。如上图所示圆圈标识,第三步,。,第66页，共80页。,6.4.2,算术编码,例,6-3,解题步骤：,当第三个字符,b,出现时，就可以确定其数据间隔区域为,0.2,到，这时由于多了字符,b,，三个字符的概率分布变成：,Pa=1/3,，,Pb=1/2,，,Pc=1/6,。就按照新的概率分布比例划分,0.2,到,0.2333,这一区间，此时的,a,从,0.2,到，,b,从,0.2111,到，,c,从,0.2278,到。如上图所示圆圈标识,第四步,。,第67页，共80页。,6.4.2,算术编码,例,6-3,解题步骤：,当第四个字符,a,出现时，就可以确定其数据间隔区域为,0.2,到，这时由于多了字符,a,，三个字符的概率分布变成：,Pa=3/7,，,Pb=3/7,，,Pc=1/7,。就按照新的概率分布比例划分,0.2,到,0.2111,这一区间，此时的,a,从,0.2,到，,b,从,0.2048,到，,c,从,0.2095,到。以后的字符依次类推，但由于第四个字符为最后一个字符，可以看出最后的输出间隔为,0.2,到，在这个区间内随便选择一个能方便的表示成二进制的数，即，二进制数为，去掉前面的,0,和小数点，最后的输出,001101,，这就是信息被压缩后的结果。如上图所示圆圈标识,第五步,。,第68页，共80页。,6.4.2,算术编码,解码：,对于算术编码如何实现解码，例,6-3,刚才的输出是,001101,，首先对其加上,0,和小数点得到，即十进制的。仍然假定三个字符的概率相等，并得出,0,到,1,之间的概率分布。在,0,到之间，确定其第一个符号为,a,，后面的字符的解压缩可以想象的作出来了吧，依次类推，可以完整实现解压缩的全部过程。,第69页，共80页。,6.4.2,算术编码,静态统计模型的算术编码与解码,例,6-4,：假设信源符号为,a,，,b,，,c,，,d,，这些符号的概率分别为，,0.3,，根据这些概率可把间隔,0,，,1,分成,4,个子间隔：,0,，,0.1,，,0.5,，,0.7,，,1,，其中,x,，,y,表示半开放间隔，即包含,x,不包含,y,。上面的信息表示在,表,6-10,中统计了每个符号的概率和初始编码间隔。,第70页，共80页。,如果二进制消息序列的输入为：,cadacdb,。编码时首先输入的符号是,c,，找到它的编码范围是，,0.7,。由于消息中第二个符号,a,的编码范围是,0,，,0.1,，因此它的间隔就取，,0.7,的第一个十分之一作为新间隔，,0.52,。依此类推，编码第,3,个符号,d,时取新间隔为，,0.52,，编码第,4,个符号,a,时，取新间隔为，,0.5146,，,。,第71页，共80页。,6.4.2,算术编码,消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图,6-14,所示。,图,6-14,静态统计模型的算术编码,第72页，共80页。,6.4.2,算术编码,编码过程如表,6-11,所示：,表,6-11,静态统计模型的算术编码过程,第73页，共80页。,6.4.2,算术编码,译码过程如表,6-12,所示：,表,6-12,静态统计模型的算术解码过程,第74页，共80页。,6.4.2,算术编码,算术编码的特点,算术编码的模式选择直接影响编码效率，有固定模式，也有自适应模式。,算术编码的自适应模式无需先定义概率模型，对无法进行概率统计的信源合适，在这点上优越于哈夫曼编码。,在信源符号概率接近时，算术编码比哈夫曼编码效率高。,算术编码的硬件实现比哈夫曼编码要复杂些。算术编码在,JPEG,的扩展系统中被推荐代替哈夫曼编码。,第75页，共80页。,6.4.2,算术编码,在算术编码中有几个问题需要注意,由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有,16,，,32,或者,64,位的精度，因此这个问题可使用比例缩放方法解决。,算术编码器对整个消息只产生一个码字，这个码字是在间隔,0,，,1,中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。,算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,第76页，共80页。,6.4.3,行程,RLE,编码,行程编码（,RLE,，,Run-length encoding,）是一种统计编码，属于无损压缩编码。它的基本原理是：用一个符号值和串长代替具有相同值的连续符号，使符号长度少于原始数据的长度。,例,6-5,：,8888888666665555552222233333333,行程编码为：(,8,7)(6,5)(5,6)2,5)(3,8),。,可见，行程编码的位数远远少于原始字符串的位数，原先数字串需用到,31,个数字，而压缩后只需,10,个数。,第77页，共80页。,6.4.3,行程,RLE,编码,有些图像，尤其是计算机生成的图形往往有许多颜色相同的图块。在这些图块中，许多连续的扫描行都具有同一种颜色，或者同一扫描行上有许多连续的像素都具有相同的颜色值。在这些情况下就可以不需要存储每一个像素的颜色值，而仅仅存储一个像素值以及具有相同颜色的像素数目。这样可大幅度减少数据量。,第78页，共80页。,6.4.3,行程,RLE,编码,行程编码可以分为定长和变长行程编码两种方式。,定长行程编码时，行程长度的最大值固定，若灰度值连续相同的个数超过了固定的这个最大值，则超过部分进行下一轮行程编码。,变长行程编码时，对不同范围的行程用不同的行程长度编码，这时需要增加标志位来说明长度使用的二进制位数。,行程编码对传输差错很敏感，一位符号出错就会改变行程编码的长度，使整个图像出现偏移，因此，一般要用行同步、列同步的方法，把差错控制在一行一列之内。,第79页，共80页。,6.4.3,行程,RLE,编码,行程编码一般不直接用于多灰度图像,(,彩色图像,),中，适用于二值图像的编码。它有时和其它的编码方法混合使用。,RLE,压缩编码尤其适用于计算机生成的图形图像，对减少存储容量很有效。然而，对自然图像来说就完全不同。由于自然图像的颜色往往是五光十色，它的行程长度非常短，若用,RLE,对它进行编码，不仅不能把图像数据压缩，反而越压越多，要用更多的代码来表示。因此对复杂的图像都不能单纯地采用,RLE,进行编码。,第80页，共80页。,