数字图像处理~图像编码.ppt

《数字图像处理~图像编码.ppt》由会员分享，可在线阅读，更多相关《数字图像处理~图像编码.ppt（101页珍藏版）》请在三一办公上搜索。

1、图像编码,1 图像编码概述2 图像保真度3 图像编码的基本知识 哈夫曼编码 香农范诺编码6 行程编码 LZW编码 算术编码,为什么需要压缩：举例1：一张A4(210mm297mm)大小的照片，若用中等分辨率(300dpi)的扫描仪按真彩色扫描，其数据量为多少？（注：dpi表示每英寸像素，1英寸25.4mm）若按每像素3个字节计算，上述结果为约?M举例2：目前的WWW互联网包含大量的图像信息，如果图像信息的数据量太大，会使本来就已经非常紧张的网络带宽变得更加不堪重负（World Wide Web变成了World Wide Wait）,视频数据量：对于电视画面的分辨率640*480的彩色图像，每秒

2、30帧，则一秒钟的数据量为：?实时传输：在10M带宽网上实时传输的话，需要压缩到原来数据量的?存储：1张CD可存640M，如果不进行压缩，1张CD则仅可以存放?秒的数据可见，单纯依靠增加存储器容量和改善信道带宽无法满足需求，必须进行压缩,1 图像编码概述,数字化后的图像信息数据量非常大，图像压缩利用图像数据存在冗余信息，去掉这些冗余信息后可以有效压缩图像。,数据冗余：设：n1和n2是指原始图像和编码后图像每个像素的平均比特数压缩率（压缩比）用于描述图像压缩效果CR=n1/n2其中，n1是压缩前的数据量，n2是压缩后的数据量相对数据冗余：RD=1 1/CR=(n1-n2)/n2分为几种冗余：编码

3、冗余像素冗余视觉冗余,编码冗余,如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余.编码时一般不利用概率特性就会产生编码冗余.例：如果用8位表示下面图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。,灰度冗余,由于任何给定的像素值，原理上都可以通过它的相邻像素预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。例：原图像数据：234 223 231 238 235压缩后数据：234 11-8-7 3，我们可以对一些接近于零的像素不进行存储，从而减小了数据量,视觉

4、冗余,人眼不能感知或不敏感的那部分图像信息，人类视觉系统对图像的敏感度是非均匀的。,感的部分同等对待，,系统是近似线性的和均匀的，,但是，在记录原始的图像数据时，,从而产生视觉冗余。,通常假定视觉,对视觉敏感和不敏,保真度标准评价压缩算法的标准客观保真度标准：图像压缩过程对图像信息的损失能够表示为原始图像与压缩并解压缩后图像的函数。一般表示为输出和输入之差：两个图像之间的总误差：均方根误差：主观保真度标准：通过视觉比较两个图像，给出一个定性的评价，如很粗、粗、稍粗、相同、稍好、较好、很好等，可以对所有人的感觉评分计算平均感觉分来衡量,图像保真度,图像传输中的压缩模型源数据编码：完成原数据的压缩

5、。通道编码：为了抗干扰，增加一些容错、校验位、版权保护，实际上是增加冗余。通道：如Internet、广播、通讯、可移动介质。,信息熵冗余：编码冗余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余。结构冗余：图像中存在很强的纹理结构或自相似性。知识冗余：有些图像中还包含与某些先验知识有关的信息。,图像编码的目的就是尽量减小各种冗余信息，特别是 空间冗余、视觉冗余，以少的比特数来表示图像。,图像编码基本知识,2.信息量和信息熵,数据压缩技术的理论基础是信息论。,从信息论的角度来看，压缩就是去掉信息,信息（可推知的）。,中的冗余，即保留不确定的信息，去掉确定的,（1）数据压缩

6、的理论极限,信息论中信源编码理论解决的主要问题：,（2）数据压缩的基本途径,信息量等于数据量与冗余量之差,I=D-du,数据是用来记录和传送信息的，或者说数据,是信息的载体。,数据所携带的信息。,信息量与数据量的关系：,du冗余量,I 信息量,D 数据量,真正有用的不是数据本身，而是,信息量,个符号的某条消息编码，,En=-log2(Pn),即表示该符号所需的位数,考虑用 0 和 1 组成的二进制数码为含有 n,息中重复出现的概率为 Pn，,假设符号 Fn 在整条消,则该符号的信息量,输入字符串:aabbaccbaa,a、b、c 出现的概率分别为 0.5、0.3和 0.2，他们的信息量分别为：

7、,Ea=-log2(0.5)=1,Eb=-log2(0.3)=1.737,Ec=-log2(0.2)=2.322,总信息量也即表达整个字符串需要的位数为：,E=Ea*5+Eb*3+Ec*2=14.855 位,举例说明:,如果用二进制等长编码,需要多少位?,20位,如果将信源所有可能事件的信息量进行,Entropy(熵)的概念,平均，就得到了信息熵(entropy)。,信息熵就是平均信息量。,平均码长与熵,如果对字符aj的编码长度为Lj，则信号L的,平均码长为：,m:信号中所出现不同字符的个数。,平均码长H(X)(稍大于H(X):,平均码长H(X):,平均码长H(X):,熵值是平均码长的下限。,

8、有冗余,不是最佳;,不可能,是最佳编码,请计算出该数据流的信息熵及相应编码方式的平均码长?,示例,输入数据流:S1S2S1S3S2S1S1S4,H(X)=1.75 L1=2 L2=1.75,总 结,数据压缩的理论极限是信息熵。,只要信源不是等概率分布，就存在着数据压缩的可能性。,数据压缩的基本途径之一：使各字符的编码长度尽量等于字符的信息量。,图像压缩编码的方法 图像压缩编码分为有损压缩和无损压缩。无损压缩无信息损失，解压缩时能够从压缩数据精确地恢复原始图像；有损压缩不能精确重建原始图像，存在一定程度的失真。根据编码原理将图像编码分为：（1）熵编码：无损编码，给出现概率较大的符号赋予一个短码字

9、，而给出现概率较小的符号赋予一个长码字，从而使得最终的平均码长很小。,（2）预测编码：基于图像数据的空间或时间冗余特性，用相邻的已知像素（或像素块）来预测当前像素（或像素块）的取值，然后再对预测误差进行量化和编码。（3）变换编码：将空间域上的图像变换到另一变换域上，变换后图像的大部分能量只集中到少数几个变换系数上，采用适当的量化和熵编码就可以有效地压缩图像。,图像编码的方法,（1）信息保持编码：要求在编解码过程中保证图像信息不丢失，可以完整地重建图像。（2）保真度编码：利用人眼的视觉特性，在允许的失真条件下，最大限度地压缩图像。可以实现较大的压缩比。（3）特征提取：对感兴趣的部分特征信息进行编

10、码即可压缩 数据。,图像编码的方法,根据对压缩编码后的图像进行重建的准确程度，可把常用的图像编码方法分为三类：,图像编码新技术 利用人工神经网络（Artificial Neural Network，ANN）的压缩编码、分形编码（Fractal Coding）、小波编码（Wavelet Coding）、基于对象的压缩编码（Object Based Coding）和基于模型的压缩编码（Model Based Coding）等等。,图像编码评价 评价图像压缩算法的优劣主要有以下4个参数：1）算法的编码效率 2）编码图像的质量 3）算法的适用范围 4）算法的复杂度,(1)Huffman编码原理:,整体

11、的大部分字符是由较短的编码,从而保证文件,出现频率高低的顺序分别赋以由短到长的代码，,先统计数据中各字符出现的概率，,再按字符,所构成。,哈夫曼编码,编码思想,将信源符号按概率递减顺序排列；,将两个最小的概率加起来作为新符号的概率；,重复步骤和，直到概率和等于1；,完成上述步骤后沿路径返回进行编码。寻找,从每一信源符号到概率为1处的路径,每层有两个分,支，分别大的概率赋予0和小的概率为1，从而得到每个符号的编码。,H(X)=1.75 L1=2 L2=1.75,霍夫曼编码举例一,输入数据流:S1S2S1S3S2S1S1S4,(1)统计出每级灰度出现的频率：灰度值：0 10 20 30 40 出现

12、频率：1/16 1/16 7/16 3/16 4/16,霍夫曼编码举例二,哈夫曼编码,(2)从左到右把上述频率按从小到大的顺序排列。灰度值：0 10 30 40 20 出现频率：1/16 1/16 3/16 4/16 7/16,哈夫曼编码,(3)选出频率最小的两个值（1/16，1/16）作为二叉树的两个叶子节点，将频率和2/16作为它们的根节点,新的根节点再参与其它频率排序：2/16 3/16 5/16 7/16,哈夫曼编码,（4）选出频率最小的两个值（2/16，3/16）作为二叉树的两个叶子节点，将频率和5/16作为它们的根节点,新的根节点再参与其它频率排序：4/16 5/16 7/16,哈

13、夫曼编码,（5）选出频率最小的两个值（4/16，5/16）作为二叉树的两个叶子节点将频率和9/16作为它们的根节点,新的根节点再参与其它频率排序：7/16 9/16,哈夫曼编码,（6）最后两个频率值（7/16，9/16）作为二叉树的两个叶子节点，将频率和1作为它们的根节点。,哈夫曼编码,（7）分配码字。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各级灰度的编码.,哈夫曼编码,各灰度的编码如下：灰度值：20 40 30 10 0哈夫曼编码：0 10 111 1101 1100则图所示的图像哈夫曼编码为：共用了32比特，原图像占1

14、28比特，压缩比较高。,假设某个字符的出现概率为 80%，该字符只,需要-log2(0.8)=0.322 位编码，但 Huffman,编码一定会为其分配,由此可得知，整个信息的 80%在压缩后几,乎相当于理想长度的 3 倍左右。,一位 0 或一位 1 的编码。,存在问题分析:,霍夫曼编码的局限性,没有错误保护功能,需要事先知道输入符号集的概率分布,为可变长度码,译码复杂,问题：把某地区天气预报的内容看作一个信源，它有6种可能的天气：晴天（概率为0.30）、阴天（概率为0.20）、多云（概率为0.15）、雨天（概率为0.13）、大雾（概率为0.12）和下雪（概率为0.10），如何用霍夫曼编码对其

15、进行编码？平均码长分别是多少？,香农-范诺编码,香农-范诺编码的理论基础是符号的码字长度Ni完全由该符号出现的概率来决定，即,式中，D为编码所用的数制。,香农范诺编码与Huffman编码相反，采用从上到下的方法。,香农范诺（二分法）编码具体步骤：,(1)首先将编码字符集中的字符按照出现频度和概率进行排序。,后面的赋值为1直至不可再分，即每一个叶子对应一个字符。,(3)编码(从根结点开始)。,(2)用递归的方法分成两部分，使两个部分,的概率和接近于相等。给前一个子集合赋值为0，,如：设一副灰度级为8的图象中，各灰度所对应的概率分别为0.04，0.05，0.06，0.07，0.10，0.10，0.

16、18，0.40，现在对其进行二分法香农范诺编码？,编码举例一,s0,s1,s2,s3,s4,s5,s6,s7,s2,s3,s4,s5,s6,s7,s0,s1,0.58,0.42,s2,s3,s4,s5,s6,s7,s0,s1,s4,s5,s6,s7,s2,s3,s4,s5,s6,s7,s0,0.40,s1,s2,s3,s4,s5,s6,0.18,0.10,0.10,0.07,s7,0.06,0.05,0.04,0.20,0.22,0.13,0.09,0,1,0,1,0,1,0,1,0,1,0,1,0,1,S0:00,S1:01,S2:100,S3:101,S4:1100,S5:1101,S6:

17、1110,S7:1111,编码举例二,夫曼编码和香农范诺如何实现压缩?并求出它们的平均码长？,有一幅40个像素组成的灰度图像,灰度共,分5级,分别用符A,B,C,D和E表示,40个像素中,出现灰度A的像素数有15个,出现灰度B的像素,数有7个,出现灰度C的像素数有7个,请问用霍,0,1,0,1,0,0,1,1,香农范诺编码举例,整个图像表示所需要的位数为:91位,平均码长为:,91/40,编码方案取决于分组方案的效果是否最佳，,香农范诺编码效率不如霍夫曼编码。,将是一件费力的事。,当信源中消息的数量较多时，寻找最佳分组方案,行 程 编码,行程编码基本方法（RLE）行程编码又称行程长度编码（Ru

18、n Length Encoding，RLE），是一种熵编码，其编码原理是将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。,RLE编码简单直观，编码/解码速度快，因此许多图形、,均采用此方法。,图像和视频文件，如.BMP、.TIFF及AVI等格式文件的压缩,定长行程编码:编码的行程长度所用的二进制位数固定。变长行程编码:不同范围的行程长度用不同编码位，需要增加标志位来表明所使用的二进制位数。,行程编码基本方法,例如：aabbbcddddd的行程长度编码为2a3b1c5d。,二值图变长行程编码的一种方法,3 12 4 9 1 11 1100 100 1001

19、1（不知道各行程应在何处分断）可以定义：可表示行程长度值 编码 编码长度 1-4 0?3 5-8 10?5 9-16 110?7 17-32 1110?9 33-64 11110?11 65-128 111110?13 如：1100的编码为：1100-1=1011（十进制11）？行程编码为：1101011,01011010110111101000000,3 12 4 9 1 11 1100 100 1001 1 10 1011 11 1000 0010 1101011 011 1101000 000,还原方法：从符号串左端开始往右搜索，遇到第一个0时停下来，计算这个0的前面有几个1。设1的个数

20、为K，则在0后面读K+2个符号，这K+2个符号所表示的二进制数加上1的值就是第1个行程的长度。,开始搜索,第一个0,该0前1的个数为0,读0+2个字符,10+01=11,第二个0,该0前1的个数为2,读2+2个字符,1011+0001=1100,第三个0,该0前1的个数为0,读0+2个字符,11+01=100,第四个0,该0前1的个数为2,读2+2个字符,1000+0001=1001,第五个0,该0前1的个数为0,读0+2个字符,00+01=01(1),0,10,11,1011,0,11,11,1000,0,00,0,0,0,0,0,0,0,开始搜索,第一个0,该0前1的个数为0,读0+2个字

21、符,10+01=11,第二个0,该0前1的个数为2,读2+2个字符,1011+0001=1100,第三个0,该0前1的个数为0,读0+2个字符,11+01=100,第四个0,该0前1的个数为2,读2+2个字符,1000+0001=1001,第五个0,该0前1的个数为0,读0+2个字符,00+01=01(1),0,10,11,1011,0,11,11,1000,0,00,0,0,0,0,0,0,0,RLE所能获得的压缩比主要取决于图像,反之，压缩比就越小。,块越大，,本身的特点。若图像中具有相同颜色的图像,图像块数目越少，,则压缩比就越高，,行程编码适合于对二值图像的编码，如果图像是由很多块颜色

22、或灰度相同的大面积区域组成的，采用行程编码可以达到很大的压缩比。通常，为了达到比较好的压缩效果，一般不单独使用行程编码，而是和其他编码方法结合使用。如：在JPEG中，就综合使用了行程编码以及哈夫曼编码。,1977年,以色列人Lempel和Ziv共同提出了查找冗余字符,和用较短的符号标记替代冗余字符的概念，简称LZ压缩技术。,1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,简称LZW压缩技术。广泛用于图象压缩领域。,LZW（Lempel-Ziv&Welch）编码又称字串表编码，属于一种无损编码，LZW编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特

23、定字符串以及与之对应的索引字符串表。,LZW编码,压缩的数据并与一个字典库(库开始是空的)中,字符串插入字典中。,字符串数据在字典库中的位置索引，,的字符串对比，,LZW压缩使用字典库查找方案。,它读入待,如有匹配的字符串，则输出该,否则将该,步骤1：将词典初始化为包含所有可能的单字,步骤2：当前字符C:=字符流中的下一个字符。,字符，当前前缀P初始化为空。,LZW编码算法,令P:=C，现在的P仅包含一个字符C,步骤3：判断PC是否在词典中,（1）如果“是”，则用C扩展P，即让P:=PC,（2）如果“否”，则,输出与当前前缀P相对应的码字；,将PC添加到词典中；,步骤4：判断码字流中是否还有码

24、字要译,（1）如果“是”，就返回到步骤2；,（2）如果“否”,把代表当前前缀P的码字输出到码字流；,结束。,LZW编码举例,输入数据流：,编码过程：,初始化字符串表,LZW编码实例 aabcabbbbd,输入数据S2,S1+S2,输出结果,S1,生成的新字符串及索引,NULL,a,a,b,c,a,b,b,b,b,d,NULL,NULL,a,a,a,aa,4H,0H,0H,ab,bc,ca,ab,abb,bb,bb,bbd,1H,2H,7H,1H,BH,3H,5H,b,c,a,ab,b,b,bb,d,aa,ab,bc,ca,abb,bb,bbd,S1为NULL,故输出结果为空,S1+S2在字符表

25、中,S1=S1+S2,aa不存在,故输出S1=“a”的索引0H,S1+S2不在字符表中,S1=S2=“a”,ab不存在,故输出S1=“a”的索引0H,S1+S2不在字符表中,S1=S2=“b”,S1+S2结果已存在,故输出结果为空,S1+S2在字符表中,S1=S1+S2,此时已无输入,输出S1的索引3H,输出LZW_EOI标志的索引,LZW编码步骤,设来源于二色系统的图像数据源：aabbbaabb（1）根据图像中使用的颜色数初始化一个字符串表，字符串表中的每个颜色对应一个索引。在初始字符串表的LZW_CLEAR和LZW_EOI分别为字符表 初始化标志和编码结束标志。,LZW编码步骤,（2）输出

26、LZW_CLEAR在字串表中的索引2H。,LZW编码步骤,（3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=”a”在字符串表中，则S1=S1+S2=“a”,LZW编码步骤,（4）读下一个字符a，将其赋给S2。判断S1+S2=”aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“aa”添加索引4H，且S1=S2=“a”,LZW编码步骤,（5）读下一个字符b赋给S2。判断S1+S2=”ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“ab”添加索引5H，且S1=S2=“b”,

27、LZW编码步骤,（6）读下一个字符b赋给S2。S1+S2=”bb”不在字符串表中，输出S1=“b”在字串表中的索引1H，并在字符串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”。,LZW编码步骤,（7）读字符b赋给S2。S1+S2=”bb”在字符串表中，则S1=S1+S2=“bb”。,LZW编码步骤,（8）读字符a赋给S2。S1+S2=”bba”不在字符串表中，输出S1=“bb”在字串表中的索引6H，并在字符串表末尾为S1+S2=“bba”添加索引7H，且S1=S2=“a”,LZW编码步骤,（9）读字符a赋给S2。S1+S2=”aa”在字符串表中，则S1=S1+S2=“aa”,

28、LZW编码步骤,（10）读字符b赋给S2。S1+S2=”aab”不在字符串表中，输出S1=“aa”在字串表中的索引4H，并在字符串表末尾为S1+S2=“aab”添加索引8H，且S1=S2=“b”,LZW编码步骤,（11）读字符b赋给S2。S1+S2=”bb”，在字符串表中，则 S1=S1+S2=“b”,LZW编码步骤,（12）输出S1中的字符串”b”在字串表中的索引1H,LZW编码步骤,（13）输出结束标志LZW_EOI的索引3H，编码完毕,解码步骤,1）读第一个编码code=2H,无输出2）读code=0H,输出0H对应的a,oldcode=code=0H3)code=0H,输出0H对应的a

29、,然后将oldcode=0H所对应的字符串“a”加上code=0H对应的字符串的第一个字符”a”,即”aa”添加到字典中，其索引为4H，同时oldcode=code=0H,4)读入code=1H,输出“b”,然后将oldcode=0H所对应的字符串“a”加上code=1H对应的字符串的第一个字符”b”,即”ab”添加到字典中，其索引为5H，同时oldcode=code=1H5)读入code=6H,由于字典中不存在该索引，将oldcode=1H所对应的字符串“b”加上oldcode=1H对应的字符串的第一个字符”b”,即”bb”添加到字典中，其索引为6H，同时oldcode=code=6H,6)

30、读入code=4H,输出“aa”,然后将oldcode=6H所对应的字符串“bb”加上code=4H对应的字符串的第一个字符”a”,即”bba”添加到字典中，其索引为7H，同时oldcode=code=4H7)读入code=6H,输出“bb”,然后将oldcode=4H所对应的字符串“aa”加上code=6H对应的字符串的第一个字符”b”,即”aab”添加到字典中，其索引为8H，同时oldcode=code=6H8)读入code=3H,解码完毕。,解码过程,由于LZW算法的关键是通过翻译表来实,对LZW算法的分析,增加表中长串的数量，则压缩比也就越高，即串越长，输出越少。,串，然后对其进行编码

31、，,现压缩的，而且每次找出的串是在表中最长的,因此，如果我们设法,串表中的每一个串均具有前缀特性，即：,则字的前缀K一定在串表中（称之为前缀条件）。,如果Kx(K为一个串，x为一个字符）在串表中，,算 术 编 码,是一种从整个符号序列出发，采用递推形式连续编码的方法，与建立在符号和码字对应基础上的块码不同，在算术编码中，源符号和码字间的一一对应关系并不存在。1个算术码字要赋给整个信源符号码字，而每个码字本身确定了0和1之间的1个实数区间。,算术编码具体方法是将被编码的信源消息表示成实数轴0-1之间的一个间隔，消息越长，编码表示的间隔就越小，即这一间隔所,采用算术编码每个符号的平均编码长度可以为

32、小数。,需的二进制位数就越多。,算 术 编 码,待编码的数据序列为“dacab”，信源中各符号出现的概率依次为P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。,数据序列中的各数据符号在区间0,1内的间隔（赋值范围）设定为:,a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d=0.8,1.0,a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d0.8,1.0）,输入d:,其初始间隔为0.8,1.0),输入a:,其初始间隔为0,0.4),StartN=0.8+0()=0.8,“a”的实际编码区间在0.8,0.88)之间,“a”的取值范围应在前一符号

33、间隔0.8,1.0)的0,0.4)子区间内,EndN=0.8+0.4()=0.88,a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d0.8,1.0）,输入c:,其初始间隔为0.6,0.8),StartN=0.8+0.6()=0.848,“c”的取值范围应在前一符号间隔0.8,0.88)的0.6,0.8)子区间内,EndN=0.8+0.8()=0.864,“c”的实际编码区间在0.848,0.864)之间,a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d0.8,1.0）,输入a:,其初始间隔为0,0.4),StartN=0.848+0()=0.848,“a”取值范

34、围应在前一符号间隔0.848,0.864)的0,0.4)子区间内,EndN=0.848+0.4()=0.8544,“a”的实际编码区间在0.848,0.8544)之间,a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d0.8,1.0）,输入b:,其初始间隔为0.4,0.6),StartN=0.848+0.4()=0.85056,“b”取值范围应在前一符号间隔0.848,0.8544)的0.4,0.6)子区间内,EndN=0.848+0.6()=0.85184,“b”的实际编码区间在0.85056,0.85184)之间,设待编码的数据序列为“dacab”，信源中各符号出现的概率依次

35、为P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。数据序列中的各数据符号在区间0,1内的间隔（赋值范围）设定为a=0,0.4）,b=0.4,0.6）,c=0.6,0.8）,d0.8,1.0）,新间隔的起始位置和结束位置,表示前一间隔的起始位置,前一间隔的长度,当前编码符号的初始区间的左端和右端,第一个被压缩的符号为“d”，其初始间隔为0.8,1.0)；第二个被压缩的符号为“a”，由于前面的符号“d”的取值区间被限制在0.8,1.0)范围内，所以“a”的取值范围应在前一符号间隔0.8,1.0)的0,0.4)子区间内，根据上式可知,StartN=0.8+0(1.0-0.8)

36、=0.8EndN=0.8+0.4(1.0-0.8)=0.88,“a”的实际编码区间在0.8,0.88)之间。,第三个被压缩的符号为“c”，其编码取值范围应在0.8,0.88)区间的0.6,0.8)的子区间内.,第四个被压缩的符号为“a”，,StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.848)=0.8544,第五个被压缩的符号为“b”,StartN=0.848+0.4(0.8544-0.848)=0.850 56EndN=0.848+0.6(0.8544-0.848)=0.851 84,数据序列“dacab”已被描述为一个实数区

37、间0.85056,0.851 84，在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。把区间0.85056,0.85184用二进制形式表示为。,。0.1101101位于这个区间内并且其编码最短，故把其作为数据序列“dacab”的编码输出。不考虑“0.”，把1101101作为本例中的数据序列的算术编码。由此可见，数据序列“dacab”用7比特的二进制代码就可以表示，平均码长为1.4比特字符。,算 术 编 码,对信源“baacc”进行算术编码,（1）计算信源中各符号出现的概率P(a)=0.4，P(b)=0.2，P(c)=0.4。（2）将数据序列中的各数据符号在区间

38、0,1内的间隔（赋值范围）设定为a=0,0.4）,b=0.4,0.6）,c=0.6,1.0。,算 术 编 码,(3)第一个被压缩的符号为“b”，其初始间隔为0.4,0.6)；(4)第二个被压缩的符号为“a”，由于前面的符号“b”的取值 区间被限制在0.4,0.6)范围内，所以“a”的取值范围 应在前一符号间隔0.4,0.6)的0,0.4)子区间内:起始位为0.4+0(0.6-0.4)=0.4 终止位为0.4+0.4(0.6-0.4)=0.48 即“a”的实际编码区间在0.4,0.48)之间。,算 术 编 码,(5)第三个被压缩的符号为“a”，由于前面的符号“a”的取值 区间被限制在0.4,0.

39、48)范围内，所以“a”的取值范围 应在前一符号间隔0.4,0.48)的0,0.4)子区间内:起始位为0.4+0(0.48-0.4)=0.4 终止位为0.4+0.4(0.48-0.4)=0.432 即“a”的实际编码区间在0.4,0.432)之间。,算 术 编 码,(6)第四个被压缩的符号为“c”，其取值范围应在前一符号 间隔0.4,0.432)的0.6,1子区间内:起始位为0.4+0.6(0.432-0.4)=0.4192 终止位为0.4+1(0.432-0.4)=0.432 即“c”的实际编码区间在0.4192,0.432之间。,算 术 编 码,(6)第五个被压缩的符号为“c”，其取值范围应在前一符号 间隔0.4192,0.432)的0.6,1子区间内:起始位为0.4192+0.6(0.432-0.4192)=0.42688 终止位为0.4192+1(0.432-0.4192)=0.432 即“c”的实际编码区间在0.42688,0.432之间。,算 术 编 码,(7)把区间0.42688,0.432用二进制形式表示为。(8)在这个区间中找出其编码最短的二进制作为算术编码。可以看出，0.0110111是此区间最短的编码，且算术 编码中任一数据序列的编码都含有“0.”，在编码时，可以不考虑“0.”，故把0110111其作为数据序列“baacc”的算术编码。,