《图像压缩编码数字图像处理.ppt》由会员分享，可在线阅读，更多相关《图像压缩编码数字图像处理.ppt（107页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章章 图像压缩编码图像压缩编码图像压缩编码图像压缩编码数据压缩与信息论基础数据压缩与信息论基础图像压缩与编码基本概念图像压缩与编码基本概念信息论基础信息论基础图像压缩编码图像压缩编码无损压缩无损压缩有损压缩有损压缩图像压缩编码图像压缩编码主要国际标准主要国际标准静止图像压缩编码标准静止图像压缩编码标准-JPEG运动图像压缩编码标准运动图像压缩编码标准-MPEG 一一.图像压缩与编码基本概念图像压缩与编码基本概念 为什么要为什么要进行进行图像压缩图像压缩 图像数据压缩的可能性图像数据压缩的可能性 数据冗余数据冗余 图像压缩的目的图像压缩的目的 图像数据压缩技术的重要指标图像数据压缩技术的重
2、要指标 图像数据压缩的应用领域图像数据压缩的应用领域 图像编码中的保真度准则图像编码中的保真度准则 信息论基础信息论基础 图像压缩模型图像压缩模型1.1.为什么要进行图像压缩？为什么要进行图像压缩？数字图像通常要求很大的比特数，这给图像的数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。花很高的费用。如一幅如一幅512*512的灰度图象的比特数为的灰度图象的比特数为 512*512*8=256k256k 再如一部再如一部9090分钟的彩色电影，每秒放映分钟的彩色电影，每秒放映2424帧。帧。把它数字
3、化，每帧把它数字化，每帧512*512象素，每象素的象素，每象素的R R R R、G G G G、B B B B三分量分别占三分量分别占8 bit8 bit，总，总比特数为比特数为 90*60*24*3*512*512*8bit=97,200M97,200M。如一张如一张CDCD光盘可存光盘可存600600兆字节数据，这部电兆字节数据，这部电影光图像（还有声音）就需要影光图像（还有声音）就需要160160160160张张CDCD光盘用来光盘用来存储。存储。对图像数据进行压缩显得非常必要。对图像数据进行压缩显得非常必要。2.2.图像数据压缩的可能性图像数据压缩的可能性 一般原始图像中存在很大的冗
4、余度。一般原始图像中存在很大的冗余度。用户通常允许图像失真。用户通常允许图像失真。当当信信道道的的分分辨辨率率不不及及原原始始图图像像的的分分辨辨率率时时，降降低低输输入入的的原原始始图图像像的的分分辨辨率率对对输输出出图图像像分分辨辨率率影影响不大。响不大。用用户户对对原原始始图图像像的的信信号号不不全全都都感感兴兴趣趣，可可用用特特征征提提取取和和图图像像识识别别的的方方法法，丢丢掉掉大大量量无无用用的的信信息息。提提取取有有用用的的信信息息，使使必必须须传传输输和和存存储储的的图图像像数数据据大大减少。大大减少。设：设：n1和和n2是在两个表达相同信息的数据集中，所携是在两个表达相同信息
5、的数据集中，所携带的单位信息量。带的单位信息量。压缩率压缩率：描述压缩算法性能描述压缩算法性能CR=n1/n2其中，其中，n1是压缩前的数据量，是压缩前的数据量，n2是压缩后的数据量是压缩后的数据量相对数据冗余相对数据冗余：RD=11/CR例：例：CR=20;RD=19/20描述信源的数据是信息量（信源熵）和信息冗余量之和。描述信源的数据是信息量（信源熵）和信息冗余量之和。3.3.数据冗余数据冗余1 1）数据冗余的基本概念）数据冗余的基本概念A.A.编码冗余：编码冗余：2 2）常见的数据冗余）常见的数据冗余在数字图像压缩中，常有在数字图像压缩中，常有3种基本的数据冗余：编码冗种基本的数据冗余：
6、编码冗余、像素间的冗余以及心理视觉冗余余、像素间的冗余以及心理视觉冗余为表达图像数据需要用一系列符号，用这些符号根据为表达图像数据需要用一系列符号，用这些符号根据一定的规则来表达图像就是对一定的规则来表达图像就是对图像编码图像编码。对每个信息或事件所赋的符号序列称为对每个信息或事件所赋的符号序列称为码字码字，而每个，而每个码字里的符号个数称为码字里的符号个数称为码字的长度码字的长度。设定义在设定义在0,1区间的离散随机变量区间的离散随机变量sk代表图像的灰度代表图像的灰度值，每个值，每个sk以概率以概率ps(sk)出现出现Ps(sk)=nk/nk=0,1,2,L-1其中其中L为灰度级数，为灰度
7、级数，nk是第是第k个灰度级出现的次数，个灰度级出现的次数，n是图像中像素总个数。设用来表示是图像中像素总个数。设用来表示sk的每个数值的比的每个数值的比特数是特数是，那么为表示每个像素所需的平均比特数，那么为表示每个像素所需的平均比特数就是就是编码所用的符号构成的集合称为编码所用的符号构成的集合称为码本码本。等长码：对于一个消息集合中的不同消息，用相同长度等长码：对于一个消息集合中的不同消息，用相同长度的不同码字表示，的不同码字表示，编解码简单，编码效率不高编解码简单，编码效率不高。变长码：与等长码相对应，对于一个消息集合中的不变长码：与等长码相对应，对于一个消息集合中的不同消息，也可以用不
8、同长度的码字表示，同消息，也可以用不同长度的码字表示，编码效率高编码效率高，编码解码复杂。，编码解码复杂。例：如果用例：如果用8 8位表示该图像的像素，我们就说该位表示该图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。个灰度，用一位即可表示。如果一个图像的灰度级编码，使用了多于实际如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。需要的编码符号，就称该图像包含了编码冗余。B.B.像素冗余：像素冗余：由于任何给定的像素值，原理上都可以通过它由于任何给定的像素值，原理上都可以通过它的邻
9、居预测到，单个像素携带的信息相对是小的。的邻居预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是对于一个图像，很多单个像素对视觉的贡献是冗余的。这是建立在对邻居值预测的基础上。冗余的。这是建立在对邻居值预测的基础上。原始图像越有规则，各像素之间的相关性越强，原始图像越有规则，各像素之间的相关性越强，它可能压缩的数据就越多。它可能压缩的数据就越多。例：原图像数据：例：原图像数据：234223231238235压缩后数据：压缩后数据：23411-8-73相同的目标相同的目标相同的直方图相同的直方图象素间的相象素间的相关性不同关性不同类似还有：类似还有：图像彩色光谱空间的
10、冗余；图像彩色光谱空间的冗余；视频图像信号在时间上的冗余；视频图像信号在时间上的冗余；一些信息在一般视觉处理中比其它信息的相对重要程一些信息在一般视觉处理中比其它信息的相对重要程度要小，这种信息就被称为视觉心理冗余。度要小，这种信息就被称为视觉心理冗余。(3)(3)视觉心理冗余：视觉心理冗余：33K15K4.4.图像压缩的目的图像压缩的目的 图像数据压缩的目的是在满足一定图像质量图像数据压缩的目的是在满足一定图像质量条件下，用尽可能少的比特数来表示原始图像，条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量。以提高图像传输的效率和减少图像存储的容量。在信息论中称
11、为信源编码。在信息论中称为信源编码。图图像像从从结结构构上上大大体体上上可可分分为为两两大大类类，一一类类是是具具有有一一定定图图形形特特征征的的结结构构，另另一一类类是是具具有有一一定定概概率率统计特性的结构。统计特性的结构。基基于于不不同同的的图图像像结结构构特特性性，应应采采用用不不同同的的压压缩缩编码方法。编码方法。5.5.图像数据压缩技术的重要指标图像数据压缩技术的重要指标（1 1）压缩比压缩比：图像压缩前后所需的信息存储量之比，：图像压缩前后所需的信息存储量之比，压缩比越大越好。压缩比越大越好。（2 2）压缩算法压缩算法：利用不同的编码方式，实现对图：利用不同的编码方式，实现对图像
12、的数据压缩。像的数据压缩。（3 3）失真性失真性：压缩前后图像存在的误差大小。：压缩前后图像存在的误差大小。全全面面评评价价一一种种编编码码方方法法的的优优劣劣，除除了了看看它它的的编编码码效效率率、实实时时性性和和失失真真度度以以外外，还还要要看看它它的的设备复杂程度设备复杂程度，是否，是否经济与实用经济与实用。常常采采用用混混合合编编码码的的方方案案，以以求求在在性性能能和和经经济上取得折衷。济上取得折衷。随随着着计计算算方方法法的的发发展展，使使许许多多高高效效而而又又比比较复杂的编码方法在工程上有实现的可能。较复杂的编码方法在工程上有实现的可能。1）办公自动化；）办公自动化；2）医学图
13、像处理；）医学图像处理；3）卫星遥感遥测系统；）卫星遥感遥测系统；4）高清晰度电视）高清晰度电视HDTV；5）可视电话、会议电视；）可视电话、会议电视；6）移动多媒体图像及视频传输：）移动多媒体图像及视频传输：彩信业务，手机视频；彩信业务，手机视频；凡是涉及到图像数据的传输、交换与存储的领域均凡是涉及到图像数据的传输、交换与存储的领域均要求进行图像数据的压缩。要求进行图像数据的压缩。6 6 图像数据压缩的应用领域图像数据压缩的应用领域7.7.图像编码中的保真度准则图像编码中的保真度准则 图像信号在编码和传输过程中会产生误差，图像信号在编码和传输过程中会产生误差，尤其是在有损压缩编码中，产生的误
14、差应在尤其是在有损压缩编码中，产生的误差应在允许的范围之内。在这种情况下，保真度准允许的范围之内。在这种情况下，保真度准则可以用来衡量编码方法或系统质量的优劣。则可以用来衡量编码方法或系统质量的优劣。通常，这种衡量的尺度可分为通常，这种衡量的尺度可分为客观保真度准客观保真度准则则和和主观保真度准则主观保真度准则。通常使用的客观保真度准则有输入图像和输出通常使用的客观保真度准则有输入图像和输出图像的图像的均方根误差均方根误差；输入图像和输出图像的；输入图像和输出图像的均方根均方根信噪比信噪比两种。两种。均方根误差均方根误差:设输入图像是由设输入图像是由N NN N个像素组成，个像素组成，令其为令
15、其为f(x,y)f(x,y)，其中其中x,y=0,1,2,x,y=0,1,2,N-1,N-1。这样一这样一幅图像经过压缩编码处理后，送至受信端，再经译幅图像经过压缩编码处理后，送至受信端，再经译码处理，重建原来图像，这里令重建图像为码处理，重建原来图像，这里令重建图像为g(x g(x,y),y)。它同样包含它同样包含N NN N个像素，并且个像素，并且x x,y=0,1,2,y=0,1,2,N-1,N-1。(1)(1)客观保真度准则客观保真度准则在在0,1,2,0,1,2,N-1,N-1范围内范围内x,yx,y的任意值，输入像素和对应的输的任意值，输入像素和对应的输出图像之间的误差可用下式表示
16、：出图像之间的误差可用下式表示：而包含而包含N NN N像素的图像之均方误差为像素的图像之均方误差为:由式可得到均方根误差为由式可得到均方根误差为 如果把输入、输出图像间的误差看作是噪声，那么，如果把输入、输出图像间的误差看作是噪声，那么，重建图像重建图像g(x,y)g(x,y)可由下式表示：可由下式表示：在这种情况下，另一个客观保真度准则在这种情况下，另一个客观保真度准则重建图重建图像的均方信噪比如下式表示：像的均方信噪比如下式表示：图像处理的结果图像处理的结果,大多是给人观看，由研究人员大多是给人观看，由研究人员来解释的，因此，图像质量的好坏，既与图像本身来解释的，因此，图像质量的好坏，既
17、与图像本身的客观质量有关，也与视觉系统的特性有关。的客观质量有关，也与视觉系统的特性有关。有时候，客观保真度完全一样的两幅图像可能有时候，客观保真度完全一样的两幅图像可能会有完全不相同的视觉质量，所以又规定了主观保会有完全不相同的视觉质量，所以又规定了主观保真度准则，这种方法是把图像显示给观察者，然后真度准则，这种方法是把图像显示给观察者，然后把评价结果加以平均，以此来评价一幅图像的主观把评价结果加以平均，以此来评价一幅图像的主观质量。质量。(2)(2)主观保真度准则主观保真度准则评分评分评价评价说明说明1优优秀的秀的优优秀的具有极高秀的具有极高质质量的量的图图像像2好的好的 是可供观赏的高质
18、量的图像，干扰并不令人讨厌是可供观赏的高质量的图像，干扰并不令人讨厌 3可通可通过过的的 图图像像质质量可以接受，干量可以接受，干扰扰不不讨厌讨厌4边缘边缘的的图图像像质质量量较较低，希望能加以改善，干低，希望能加以改善，干扰扰有些有些讨厌讨厌5劣等的图像质量很差，尚能观看，干扰显著地令人讨厌6不能用不能用图图像像质质量非常之差，无法量非常之差，无法观观看看另外一种方法是规定一种绝对尺度，如：另外一种方法是规定一种绝对尺度，如：表表6.1 6.1 电视图像质量评价尺度电视图像质量评价尺度8.8.信息理论信息理论（一）、信源空间概述（一）、信源空间概述1 1、信息：事物运动状态或存在方式的不确定
19、性的、信息：事物运动状态或存在方式的不确定性的描述；描述；2 2、信源空间：随机符号及其出现概率的空间；、信源空间：随机符号及其出现概率的空间；3 3、信源的分类：、信源的分类：（1 1）连续信源）连续信源离散信源离散信源混合信源；混合信源；（2 2）无记忆信源）无记忆信源有记忆信源（相关信源）有记忆信源（相关信源）有有限长度记忆信源（限长度记忆信源（MarkovMarkov信源）信源）（二）、信息的度量（二）、信息的度量1、信息公理、信息公理（1）信息由）信息由不确定性程度不确定性程度进行度量；进行度量；确定事件的信息量为零。确定事件的信息量为零。（2）不确定性程度）不确定性程度越高越高信息
20、量信息量越大越大；（3）相互独立性与信息量可加性；）相互独立性与信息量可加性；独立事件的联合信息等于两个独立事件的信息总和。独立事件的联合信息等于两个独立事件的信息总和。满足上述公理的函数为：满足上述公理的函数为：2、离散无记忆信源（、离散无记忆信源（DNMS）的信息量度量：的信息量度量：（1）信源符号）信源符号 的自信息量定义为：的自信息量定义为：(a)非负性；非负性；(b)信息量的单位：信息量的单位：底为底为2时时单位为：比特（单位为：比特（bit）底为底为e时时单位为：奈特（单位为：奈特（Nat）底为底为10时时单位为：哈特单位为：哈特（2）、信源平均自信息量（信息熵）、信源平均自信息量
21、（信息熵）离散无记忆信源离散无记忆信源A的平均自信息量（信息熵）定义为：的平均自信息量（信息熵）定义为：例例:设设8个随机变量具有同等概率为个随机变量具有同等概率为18，计算信息，计算信息熵熵H。解解:根据公式根据公式4-10可得：可得：H=8*-1/8*(log2(1/8)=8*-1/8*(-3)=3图像熵指该图像的平均信息量，即表示图像中各个图像熵指该图像的平均信息量，即表示图像中各个灰度级比特数的统计平均值，等概率事件的熵最灰度级比特数的统计平均值，等概率事件的熵最大。大。3、平均码字长、平均码字长借助熵的概念可以定义量度任何特定码的性能的准借助熵的概念可以定义量度任何特定码的性能的准则
22、，即平均码字长度。则，即平均码字长度。其中其中i为灰度级为灰度级di所对应的码字长度。所对应的码字长度。的单位也的单位也是比特是比特/字符。字符。4、编码效率、编码效率编码符号是在字母集合编码符号是在字母集合A=a1,a2,a3,am中选取的。中选取的。如果编码后形成一个新的等概率的无记忆信源，字母数如果编码后形成一个新的等概率的无记忆信源，字母数为为n，则它的最大熵应为，则它的最大熵应为logn比特比特/符号。因此这是一个符号。因此这是一个极限值。如果极限值。如果H(d)/=logn，则可以认为编码效率已，则可以认为编码效率已经达到经达到100%，如果，如果H(d)/logn，则可认为编码，
23、则可认为编码效率较低。效率较低。编码效率编码效率冗余度冗余度根据信息熵编码理论，可以证明在根据信息熵编码理论，可以证明在 H条件下，总条件下，总可以设计出某种无失真编码方法。可以设计出某种无失真编码方法。若编码结果使若编码结果使远大于远大于H，表明这种编码效率很低，表明这种编码效率很低，占用的比特数太多。占用的比特数太多。若编码结果使若编码结果使等于或接近于等于或接近于H，这种状态的编码方这种状态的编码方法称为最佳编码。法称为最佳编码。若要求编码结果使若要求编码结果使H，则必然丢失信息而引起图像则必然丢失信息而引起图像失真。这就是在允许失真条件下的一些失真编码方法。失真。这就是在允许失真条件下
24、的一些失真编码方法。5、压缩比、压缩比压缩比是衡量数据压缩程度的指标之一。目前常用的压缩比是衡量数据压缩程度的指标之一。目前常用的压缩比定义为压缩比定义为 其中其中LB为源代码长度，为源代码长度，Ld为压缩后代码长度，为压缩后代码长度，Pr为压为压缩比。缩比。压缩比的物理意义是被压缩掉的数据占据源数据的百压缩比的物理意义是被压缩掉的数据占据源数据的百分比。当压缩比分比。当压缩比Pr接近接近100%时压缩效果最理想。时压缩效果最理想。6、互信息、互信息信源编码输出为信源编码输出为bk给出的关于给出的关于ai的信息量究竟为多少呢的信息量究竟为多少呢？为此将引入另外一个信息量度互信息？为此将引入另外
25、一个信息量度互信息对给定的两个离散信源对给定的两个离散信源X和和Y，Y中事件中事件bk的发生给出关的发生给出关于于X中事件中事件ai的互信息的互信息I(ai:bk)定义为：定义为：其中，其中，p(ai|bk)表示信源编码输出为表示信源编码输出为bk，估计信源输入，估计信源输入为为ai的条件概率。的条件概率。I(ai|bk)称为条件自信息量，表示在发称为条件自信息量，表示在发现信源编码输出为现信源编码输出为bk，对信源输入为，对信源输入为ai的不确定性的猜的不确定性的猜测或知道测或知道bk后后ai还保留的信息量。还保留的信息量。I(ai)表示表示ai的不确定的不确定性。两者值差即为性。两者值差即
26、为bk解除的解除的ai不确定性的多少。不确定性的多少。设一幅灰度级为设一幅灰度级为K K的图像，图像中第的图像，图像中第k k级灰度出级灰度出现的概率为现的概率为p pk k，图像大小为图像大小为M MN N，每个像素用每个像素用d d比特表示，每两帧图像间隔比特表示，每两帧图像间隔t t 数字图像的熵H图像的平均码字长度R为：编码效率定义为：信息冗余度为：每秒钟所需的传输比特数bps为：压缩比r为：图像信息源图像信息源图像预处理图像预处理图像信源编码信道编码调制信道传输解调信道解码图像信源解码显示图像9.9.图像的压缩模型图像的压缩模型源数据编码：完成原数据的压缩。源数据编码：完成原数据的压
27、缩。通道编码：通道编码：为了抗干扰，增加一些容错、校验位，为了抗干扰，增加一些容错、校验位，实际上是增加冗余。实际上是增加冗余。通通 道：道：如如InternetInternet、广播、通讯、可移动介质广播、通讯、可移动介质源数据源数据编码编码通道通道编码编码通道通道通道通道解码解码源数据源数据解码解码源数据编码的模型源数据编码的模型源数据解码的模型源数据解码的模型映射器映射器量化器量化器符号符号编码器编码器符号符号解码器解码器反向反向映射器映射器源数据编码与解码的模型源数据编码与解码的模型映射器映射器 ：减少像素冗余减少像素冗余，如使用，如使用RLERLE编码。编码。或进行图像变换或进行图像
28、变换量化器量化器 ：减少视觉心理冗余减少视觉心理冗余，仅用于有损，仅用于有损压缩压缩符号编码器：符号编码器：减少编码冗余减少编码冗余，如使用哈夫曼，如使用哈夫曼编码编码源数据编码与解码的模型源数据编码与解码的模型预测编码图像编码无损压缩编码有损压缩编码哈夫曼编码行程编码算术编码 频率域方法 其他编码方法二.常用的图像压缩编码方法 无损压缩算法中删除的仅仅是图像数据中冗余的信无损压缩算法中删除的仅仅是图像数据中冗余的信息，因此在解压缩时能精确恢复原图像，无损压缩的压息，因此在解压缩时能精确恢复原图像，无损压缩的压缩比很少有能超过缩比很少有能超过3 3：1 1的的,常用于要求高的场合。常用于要求高
29、的场合。1.无损压缩编码有有损损压压缩缩是是通通过过牺牺牲牲图图像像的的准准确确率率以以实实现现较较大大的的压压缩缩率率，如如果果容容许许解解压压图图像像有有一一定定的的误误差差，则则压压缩缩率率可可显显著著提提高高。有有损损压压缩缩在在压压缩缩比比大大于于3030：1 1时时仍仍然然可可重重构构图图像像，而而如如果果压压缩缩比比为为10:110:1到到20:120:1，则则重重构构的的图图像像与与原图几乎没有差别原图几乎没有差别2.有损压缩编码3.哈夫曼编码哈夫曼编码等长码：对于一个消息集合中的不同消息，用相同长度等长码：对于一个消息集合中的不同消息，用相同长度的不同码字表示，的不同码字表示
30、，编解码简单，编码效率不高编解码简单，编码效率不高。变长码：与等长码相对应，对于一个消息集合中的不变长码：与等长码相对应，对于一个消息集合中的不同消息，也可以用不同长度的码字表示，同消息，也可以用不同长度的码字表示，编码效率高编码效率高，编码解码复杂。，编码解码复杂。哈夫曼编码是一种利用信息符号概率分布特性的变字长的编码方法。对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。方法方法方法方法：I.I.将将信信源源符符号号按按出出现现概概率率从从大大到到小小排排成成一一列列，然然后后把把最末两个符号的概率相加，合成一个概率。最末两个符号的概率相加，合成一个概率。II
31、.II.把这个符号的概率与其余符号的概率按从大到小排把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一列，然后再把最末两个符号的概率加起来，合成一个概率。个概率。III.III.重复上述做法，直到最后剩下两个概率为止。重复上述做法，直到最后剩下两个概率为止。IV.IV.从最后一步剩下的两个概率开始逐步向前进行编码。从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码率大的赋予码0 0，对概率小的赋予码，对概率小的赋予码1 1。Huffman编码输入S1S2S3S4
32、S5S6输入概率0.40.30.10.10.060.04Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.
33、10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman编
34、码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30
35、.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman编码输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011哈夫曼编码效率哈夫曼编码效率信源熵为：
36、信源熵为：H=-Pilog2Pi=-(0.4log20.4+0.3log20.3+2*0.1log20.1+0.06log20.06+0.04log20.04)=2.14比特比特/符号符号平均码字长度：平均码字长度：R=iPi码字码字长度长度R=iPi=0.41+0.3 2+0.1 3+0.1 4+0.06 5+0.04 5=2.2比特比特/符号符号编码效率：编码效率：=H/R(%)=H/R=2.14/2.2=0.973=97.3%编码举例cbafe01f=00 e=10 a=11 b=010 c=0110 d=0111d01010101作业：作业：1.有如下信源x，u1 u2 u3 u4 u
37、5 u6 u7 u8 P1 P2 P3 P4 P5 P6 P7 P8其中：P10.21,P20.09,P30.11,P40.13,P50.07,P60.12,P70.08,P80.19。将该信源进行哈夫曼编码。2.设一幅灰度级为设一幅灰度级为8（分别用（分别用S0、S1、S2、S3、S4、S5、S6、S7表示）的图像中，各灰度所对表示）的图像中，各灰度所对应的概率分别为应的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04。现对其进行哈夫曼编码。现对其进行哈夫曼编码X3.设有一信源X=x1,x2,x3,x4，对应概率P=0.5,0.1975,0.1775,
38、0.125.进行霍夫曼编码(要求大概率的赋码字0,小概率的赋码字1)，给出码字，平均码长，编码效率;对码串10101011010110110000011110011解码.由于霍夫曼编码法需要多次排序，当很多时十分不便，为此费诺(Fano)和香农(Shannon)分别单独提出类似的方法，使编码更简单。具体编码方法如下：把 按概率由大到小、从上到下排成一列，然后把 分成两组 ，并使得 把两组分别按0，1赋值。然后分组、赋值，不断反复，直到每组只有一种输入为止。将每个所赋的值依次排列起来就是费诺香农编码。补充：补充：香农费诺编码香农费诺编码以前面哈夫曼编码的例子进行香农费诺编码以前面哈夫曼编码的例子
39、进行香农费诺编码：输入输入概率概率x10.400 x20.31010 x30.11001100 x40.111101x50.06101110 x60.04111114.算术编码算术编码从理论上分析，采用哈夫曼编码可以获得最佳信从理论上分析，采用哈夫曼编码可以获得最佳信源字符编码效果源字符编码效果;实际应用中，由于信源字符出现的概率并非满足实际应用中，由于信源字符出现的概率并非满足2 2的负幂次方，因此往往无法达到理论上的编码效的负幂次方，因此往往无法达到理论上的编码效率和信息压缩比率和信息压缩比;以信源字符序列x，y为例设字符序列设字符序列xx，yy对应的概率为对应的概率为1/31/3，2/3
40、2/3，NxNx和和NyNy分别表示字符分别表示字符x x和和y y的最佳码长，则根据信息的最佳码长，则根据信息论有：论有：字符字符x x、y y的最佳码长分别为的最佳码长分别为1.58bit1.58bit和和0.588bi;0.588bi;这表明，要获得最佳编码效果，需要采用小数码字这表明，要获得最佳编码效果，需要采用小数码字长度长度,这是不可能实现的这是不可能实现的;即采用哈夫曼方法对即采用哈夫曼方法对xx，yy的码字分别为的码字分别为0 0和和1 1，也，也就是两个符号信息的编码长度都为就是两个符号信息的编码长度都为1 1。对于出现概率。对于出现概率大的字符大的字符y y并未能赋予较短的
41、码字并未能赋予较短的码字;实际编码效果往往不能达到理论效率实际编码效果往往不能达到理论效率;为提高编码效率，为提高编码效率，EliasElias等人提出了算术编码算法。等人提出了算术编码算法。算术编码的特点算术编码的特点 算术编码是信息保持型编码，它不像哈夫曼编码，无算术编码是信息保持型编码，它不像哈夫曼编码，无需为一个符号设定一个码字需为一个符号设定一个码字;算术编码分为固定方式和自适应方式两种编码算术编码分为固定方式和自适应方式两种编码;选择不同的编码方式，将直接影响到编码效率选择不同的编码方式，将直接影响到编码效率;自适应算术编码的方式，无需先定义概率模型，适合自适应算术编码的方式，无需
42、先定义概率模型，适合于无法知道信源字符概率分布的情况于无法知道信源字符概率分布的情况;当信源字符出现的概率比较接近时，算术编码效率高当信源字符出现的概率比较接近时，算术编码效率高于哈夫曼编码的效率，在图像通信中常用它来取代哈于哈夫曼编码的效率，在图像通信中常用它来取代哈夫曼编码夫曼编码;实现算术编码算法的硬件比哈夫曼编码复杂。实现算术编码算法的硬件比哈夫曼编码复杂。编码原理编码原理算术编码方法是将被编码的信源消息表示成算术编码方法是将被编码的信源消息表示成0-10-1之间之间的一个间隔，即小数区间，消息越长，编码表示它的的一个间隔，即小数区间，消息越长，编码表示它的间隔就越小间隔就越小;以小数
43、表示间隔，表示的间隔越小所需的二进制位数以小数表示间隔，表示的间隔越小所需的二进制位数就越多，码字就越长。反之，间隔越大，编码所需的就越多，码字就越长。反之，间隔越大，编码所需的二进制位数就少，码字就短。二进制位数就少，码字就短。算术编码将被编码的图像数据看作是由多个符号组成算术编码将被编码的图像数据看作是由多个符号组成的字符序列，对该序列递归地进行算术运算后，成为的字符序列，对该序列递归地进行算术运算后，成为一个二进制分数一个二进制分数;接收端解码过程也是算术运算，由二进制分数重建图接收端解码过程也是算术运算，由二进制分数重建图像符号序列。像符号序列。编码举例编码举例设图像信源编码可用设图像
44、信源编码可用a a、b b、c c、d d这这4 4个符号来表示，个符号来表示，若图像信源字符集为若图像信源字符集为 dacbadacba，信源字符出现的概信源字符出现的概率分别如下表所示，采用算术编码对图像字符集率分别如下表所示，采用算术编码对图像字符集编码。编码。信源字符信源字符a ab bc cd d出现概率出现概率0.40.40.20.20.20.20.20.2算术编码的基本步骤算术编码的基本步骤(1)(1)根据已知条件和数据可知，信源各字根据已知条件和数据可知，信源各字符在区间符在区间00，11内的子区间间隔分别如下：内的子区间间隔分别如下：a=0.0 a=0.0，0.4)b=0.4
45、 0.4)b=0.4，0.6)0.6)c=0.6 c=0.6，0.8)d=0.8 0.8)d=0.8，1.0)1.0)(2)(2)计算中按如下公式产生新的子区间：计算中按如下公式产生新的子区间：(3)(3)第第1 1个被压缩的字符为个被压缩的字符为“d”d”，其初始子区间其初始子区间为为0.8 0.8，1.0)1.0)(4)(4)第第2 2个被压缩的字符为个被压缩的字符为“a”a”，由于其前面的由于其前面的字符取值区间为字符取值区间为0.8 0.8，1.0)1.0)范围，因此，字符范围，因此，字符“a”a”应在前一字符区间间隔应在前一字符区间间隔0.8 0.8，1.0)1.0)的的0.0 0.
46、0，0.4)0.4)子区间内，根据公式子区间内，根据公式(8-15)(8-15)可得：可得：=0.8+0.0(1.0-0.8)=0.8=0.8+0.0(1.0-0.8)=0.8 =0.8+0.4(1.0-0.8)=0.88 =0.8+0.4(1.0-0.8)=0.88(5)(5)第第3 3个被压缩的字符为个被压缩的字符为“c”c”，由于其前面的由于其前面的字符取值区间为字符取值区间为0.8 0.8，0.88)0.88)范围内，因此，字范围内，因此，字符符“c”c”应在前一字符区间间隔应在前一字符区间间隔0.8 0.8，0.88)0.88)的的0.6 0.6，0.8)0.8)子区间内，根据子区间
47、内，根据(8-15)(8-15)可得：可得：=0.8+0.6(0.88-0.8)=0.848=0.8+0.6(0.88-0.8)=0.848 =0.8+0.8(0.88-0.8)=0.864 =0.8+0.8(0.88-0.8)=0.864(6)(6)第第4 4个被压缩的字符为个被压缩的字符为“b”b”，由于其前面的由于其前面的字符取值区间为字符取值区间为0.848 0.848，0.864)0.864)范围内，因此，范围内，因此，字符字符“b”b”应在前一字符区间间隔应在前一字符区间间隔0.848 0.848，0.864)0.864)的的0.4 0.4，0.6)0.6)子区间内，根据子区间内，
48、根据(8-15)(8-15)可得：可得：=0.848+0.4(0.864-=0.848+0.4(0.864-0.848)=0.8544 0.848)=0.8544 =0.848+0.6(0.864-=0.848+0.6(0.864-0.848)=0.8576 0.848)=0.8576(7)(7)第第5 5个被压缩的字符为个被压缩的字符为“a”a”，由于其前面的由于其前面的字符取值区间为字符取值区间为0.8544 0.8544，0.8)0.8)范围内，因此，范围内，因此，字符字符“a”a”应在前一字符区间间隔应在前一字符区间间隔0.8544 0.8544，0.8576)0.8576)的的0.0
49、 0.0，0.4)0.4)子区间内，根据子区间内，根据(8-15)(8-15)可可得：得：=0.8544+0.0(0.8576-=0.8544+0.0(0.8576-0.8544)=0.8544 0.8544)=0.8544 =0.8544+0.4(0.8576-=0.8544+0.4(0.8576-0.86544)=0.85568 0.86544)=0.85568经过上述计算，字符集经过上述计算，字符集 dacbadacba 被描述在实数被描述在实数0.8544 0.8544，0.85568)0.85568)子区间内，即该区间内的任子区间内，即该区间内的任一实数值都惟一对应该符号序列一实数值
50、都惟一对应该符号序列 dacbadacba；因此，可以用因此，可以用0.8544 0.8544，0.85568)0.85568)内的一个实数内的一个实数表示字符集表示字符集 dacbadacba。0.8544 0.8544，0.85568)0.85568)子区间的二进制表示形式为：子区间的二进制表示形式为：0.1101101010000110 0.1101101010000110，0.1101101100001101)0.1101101100001101)；在该区间内的最短二进制代码为在该区间内的最短二进制代码为0.110110110.11011011，去掉，去掉小数点及其前的字符，从而得到该