数字图像处理及应用：第五章图像编码.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章,图像编码,第一讲,模拟图像信号在传输过程中极易受到各种噪声的干扰，而且模拟图像信号一旦受到污染则很难完全得到恢复。另外，在模拟领域中，要进行人与机器（计算机或智能机），机器与机器之间的信息交换以及对图像进行诸如压缩、增强、恢复、特征提取和识别等一系列处理都是比较困难的。,所以无论从完成图像通信与数据通信网的结合方面来看，还是从对图像信号进行各种处理的角度来看，图像信号数字化都是首当其冲的重要问题。图像数字化的关键是编码。本章将对图像编码进行较为详细的讨论。,5.1,信源编码,图像编码属于信源编码范畴。其特点是利用图像信号的统计特性及人眼睛的生理和心理特性对图像进行高效编码。,在信息论中将数字通信过程概括为图,51,的形式。,信源,信源编码,信道编码,调制,传输信道,噪声,解调,信道解码,信源解码,信宿,图,51,数字通信系统模型,图,51,所示的模型是一个数字通信系统模型。在这样一个模型中有二次编、译码，,信源编码、信源译码,信道编码、信道译码。,信源编码的主要任务是解决有效性问题，,也就是对信源实现压缩处理，使处理后的信号更适宜数字通信系统。解决有效性问题就是在编码过程中尽量提高编码效率，也就是力求用最少的数码传递最大的信息量。,信道编码的任务是解决可靠性问题,。也就是尽量使处理过的信号在传输过程中不出错或少出错，既使出了错也要有能力尽量纠正错误。因此，在信道编码中往往引进用作误差控制的数码，以实现自动检错和纠错。,图像编码主要是要研究压缩数码率，,即高效编码问题。,编码是信息处理科学中的经典研究课题，就图像编码而言，已有近五十年的历史。近年来，,M.Kunt,提出第一代、第二代编码的概念。,M.Kunt,把,1948,年至,1988,年这四十年中研究的以去除冗余为基础的编码方法称为第一代编码，如：,PCM,、,DPCM,、,M,、亚取样编码法，变换域的,DFT,、,DCT,、,Walsh-,Hadamard,变换编码等方法以及以此为基础的混合编码法均属于经典的第一代编码法。,第二代编码,方法多是八十年代以后提出的新的编码方法，如金字塔编码法、,Fractal,编码、基于神经元网络的编码方法、小波变换编码法、模型基编码法等。,现代编码法的特点是：,充分考虑人的视觉特性；,恰当地考虑对图像信号的分解与表述；,采用图像的合成与识别方案压缩数据,率。,这种分法尽管并没得到图像编码界全体同仁的广泛认可，但笔者认为对了解图像编码发展进程是有益的。,图像编码这一经典的研究课题，经五十多年的研究已有多种成熟的方法得到应用，特别是所谓的第一代编码更是如此。,随着多媒体技术的发展已有若干编码标准由,ITU-T,制定出来，如,JPEG,、,H.261,、,H.263,、,MPEG1,、,MPEG2,、,MPEG4,、,MPEG7,、,JBIG(,二值图像压缩,)(Joint Bo-level Image Coding Expert Group),等。,信源编码的目的是提高编码效率。,是否能提高编码效率？,回答是肯定的。,从信息论的角度看，各种信源都存在大量的冗余成分。如果去掉这些冗余成分，就能提高编码效率。所以，所谓第一代编码就是围绕着去除冗余度这一中心思想实现数据压缩的。,冗余度在那里？,冗余度主要存在于两个主要方面：,1）、存在于信源的相关性之中；,2）、存在于图像信源各个元素出现概率的不均等之中。,因此，无论是记忆性信源还是无记忆性信源都由压缩的可能。,去掉了冗余成分的信源固然精练了，但是，也变得脆弱了。抗干扰性能也变差了。因此，在传书过程中，还要加入一些冗余成分以增加抗干扰能力。这就是信道编码的任务了。,图像编码的分类,图像编码大致可分位三类：,1）、,匹配编码；,2）、变换编码；,3）、识别编码：,（1）、匹配编码,这种编码方法是使代码长度与图像信源的概率分布相匹配。如：出现概率大的编短码，概率小的编长码，总的码率就会下降。,这种编码的长短不一，使得传输、译码、存储均不方便，另一个缺点是编码的先决条件是要知道图像信源的概率分布。,解决办法：,1）、寻找一个大体上能代表图像信源的数学模型，如正态分布，指数分布等；,2）、实际统计图像信源的概率分布，这种方法更切合实际，但是，往往找不到合适的数学模型，给分析带来不便。,（,2）、变换编码,首先把图像信源从一个空间变换到另外一个空间，然后对变换系数进行编码。变换方式大体上可分为两类;,预测变换,函数变换,（3)、识别编码,这种方法的关键是识别。基本原理是用另外一套符号代替原来的信源中的消息，如：电报、速记等均可认为是识别编码的例子。,主要方法：,a),关联识别，需要一定数量的样本。信息与样本比较，判别相似程度。,b)、,逻辑识别,没有样本，是用逻辑表达式判别被识别对象。,这种编码方法与实际应用还有距离。,从压缩的角度也可以分为;,1)、熵压缩法：不可逆的编码法，压缩中有信息损失，但在视觉角度看失去的信息是无关紧要的信息。,2）、无失真编码：是可逆的编码方法。没有信息损失。,另外，如果从目前已有的实用方案的角度来分类，可以分为三大类，即预测编码，变换编码及统计编码。而这些方法既适用于静止图像编码，也适用于电视信号编码。就具体编码方法而言可简略地概括在表,51,中。,表,51,图 象 高 效 编 码 法,PCM,预测法 正交变换法 统计编码 其他方法,常规编码法,亚奈氏取样编码法,标准法,自适应法,标准法,自适应法,标准法,自适应法,行程编码,轮廓编码,DPCM,M,K-L,HT,DWT,DFT,ST,DCT,霍夫曼,仙农,费诺,最后需要着重提及的是，上述各种具体方案并不是孤立的、单一的使用，往往是各种方法重迭、交叉使用，以达到更高的编码效率，在,ITU-T,的建议标准中这一点尤为突出。,5.2,图像编码中的保真度准则,图像信号在编码和传输过程中会产生误差，尤其是在熵压缩编码中，产生的误差应在允许的范围之内。在这种情况下，保真度准则可以用来衡量编码方法或系统质量的优劣。通常，这种衡量的尺度可分为客观保真度准则和主观保真度准则。,5.2,.1,客观保真度准则,5.2,.2,主观保真度准则,5.2,.1,客观保真度准则,通常使用的客观保真度准则有输入图像和输出图像的均方根误差；输入图像和输出图像的均方根信噪比两种。输入图像和输出图像的均方根误差是这样定义的。设输入图像是由,N,X,N,个像素组成，令其为,f,(,x,y,),，,其中,x,y,=0,1,2,3.,N,-1 。,这样一幅图像经过压缩编码处理后，送至受信端，再经译码处理，重建原来图像。这里令重建图像为,g,(,x,y,)。,它同样包含,N,N,个像素，并且,x,y,=0,1,2,N,-1,在 0,1,2,3.,N,-1,范围内(,x,y,),处,的任意值，输入像素和对应的输出图像之间的误差可用下式表示,而包含,N,x,N,象素的图像之均方误差为,(52),(51),由式,(52),可得到均方根误差为,(53),如果把输入、输出图像间的误差看作是噪声，那么，重建图像,g,（,x,，,y,）,可由下式表示,(54),在这种情况下，另一个客观保真度准则,重建图像的均方信噪比如下式表示,(55),均方根信噪比为,(56),5.2.2,主观保真度准则,图像处理的结果，绝大多数场合是给人观看，由研究人员来解释的，因此，图像质量的好坏与否，既与图像本身的客观质量有关，也与人的视觉系统的特性有关。,有时候客观保真度完全一样的两幅图像可能会有完全不相同的视觉质量，所以又规定了主观保真度准则。这种方法是把图像显示给观察者，然后把评价结果加以平均，以此来评价一幅图像的主观质量。,一种方法是规定一种绝对尺度，例如：,（）优秀的：具有极高质量的图像；,（）好的：是可供观赏的高质量的图像，干扰并不令人讨厌；,（）可通过的：图像质量可以接受，干扰不讨厌；,（）边缘的：图像质量较低，希望能加以改善，干扰有些讨厌；,（）劣等的：图像质量很差，尚能观看，干,扰显著地令人讨厌；,（）不能用：图像质量非常之差，无法观看。,另外常用的还有两种准则，即妨害准则和品质准则。,妨害准则如下五级：,（）没有妨害感觉；,（）有妨害，但不讨厌；,（）能感到妨害，但没有干扰；,（）妨害严重，并有明显干扰；,（）不能接收信息。,品质准则如下七级：,（）非常好；,（）好；,（）稍好；,（）普通；,（）稍坏；,（）恶劣；,（）非常恶劣。,除此之外，还可以采用成对比较法，也就是同时出示两幅图像，让观察者表示更喜欢哪一幅图像，借此排出图像质量的等级。也有采用随机抽取法来评定图像质量的。这种方法是把数量相等的原始图像和经编译码后的图像混杂在一起，然后让观察者挑出他认为质量差的图像。,质量较差的图像可定义为处理过的图像，然后统计错挑的概率，显然错挑概率越大说明图像经处理后的劣化越小。总之，主观保真度评价方法的准则可不同，但其基本原理都一样，当然，对观察者的视觉条件应有一定的要求。,5.3,编码,5.3,.1,PCM,编码的基本原理,5.3,.2,PCM,编码的量化噪声,5.3,.3,编码器、译码器,5.3,.1,PCM,编码的基本原理,脉冲编码调制（,Pulse coding ModulationPCM,）是将模拟图像信号变为数字信号的基本手段。图像信号的,PCM,编码与语音信号,PCM,编码相比并没有原则上的区别。但是，图像信号，特别是电视信号占的频带宽，要求响应速度快，因此，电路设计与实现上有较大的难度。,图像信号,PCM,编、译码原理方框图如图,52,所示。图像信号,PCM,编码由前置低通滤波器、取样保持电路、量化器、编码器组成。,图像,低通滤波,取样保持,编码,传输信道,解码,低通滤波,解码图像,量化,图,53,PCM,编、译码原理方框图,前置低通滤波器的作用：,1）、为满足取样定理的带限要求，以减少折,迭误差；,2）、对杂散噪声也有一定的抑制作用。,取样保持电路：,将完成把时间上连续的模拟信号进行时间离散化的任务。取样周期由奈奎斯特（,Nyquist,）定理限定。,量化器：,把模拟信号的幅值离散化，经取样与量化处理后就可产生多值数字信号。,编码：,把多值的数字信号变成二进制的数字的多比特信号，以便传输或进行后续处理。,译码器的原理比较简单，它包括一个译码电路和一个低通滤波器。,译码器：,把数字信号恢复为模拟信号，这个模拟信号就是在接收端的解码图像信号。,滤波器：,内插和平滑作用。,5.3,.2,PCM,编码的量化噪声,量化是对时间离散的模拟信号进行幅度离散化的过程，这个过程是去零取整的过程。量化后的样值与原信号相比大部分是近似关系。这样，把连续的数值限制在固定的台阶式的变化之下必然会带来畸变。这种畸变在接收端是无法克服的，只能使其尽量减小。,图,54,量化噪声与过载噪声的形成,由量化带来的噪声可分为量化噪声和过载噪声。以正弦波输入为例，输入幅度较大和输入幅度较小时的量化噪声如图,53,所示。,(,a),是输入信号超过编码范围时的量化噪声和过载噪声的形成；,(,b),是信号未超过编码范围，只有量化噪声的情况。,在,PCM,编码中，量化噪声主要取决于码的位数，码位数越多（即量化阶数多）量化噪声的功率越小。一个量化阶的电压可由下式表示：,(57),式中：,V,为输入信号电压；,n,为样值用二进制数表示的比特数。,如果在整个输入幅度内量化阶是一个常数，就称这个量化为均匀量化，否则就是非均匀量化。线性,PCM,编码中均采用均匀量化法。在均匀量化中，设量化阶为,，量化噪声在 内可看成是均匀分布的，因此，其功率可由下式表示：,(58),对于过载噪声，当量化特性输入过载点为,V,时，由下式表示,(59),式中 为过载噪声，,x,是输入信号值，,p,(,x,),为输入幅度的概率密度。如果用信噪比作为客观保真度准则的话，可推得,PCM,编码在均匀量化下的量化信噪比如下：,因为,所以,(510),由信噪比的概念，则：,（,511,）,由式,(511),可见，,每增加一位码可得到,6,dB,的信噪比得益。,值得注意的是量化噪声不同于其他噪声，它的显著特点是仅在有信号输入时才出现，所以它是数字化中特有的噪声。一般情况下，直接测量比较困难。,5.4,.3,编码器、译码器,编码器的任务是把一个多值的数字量用多比特的二进制量来表示。如果量化器输出,M,个值，那么，对应于,个值中的任何一个值编码器将给定一个二进制码字。这个码字将由,m,个二进制数组成。通常情况下 。编码器的输入与输出关系是一一对应的，其过程是可逆的，因此，不会引入任何误差。,线性,PCM,编码一般采用等长码，也就是说每一个码字都有相同的比特数。其中用得最为普遍的是自然二进码，也有用格雷码的。以,M,=8,为例的自然二进码和格雷码列入表,(52),。,表,5.2 M=8,的自然二进码和格雷码,输入,自然二进码,格雷码,0 0 0,0 0 0,0 0 1,0 0 1,0 1 0,0 1 1,0 1 1,0 1 0,1 0 0,1 1 0,1 0 1,1 1 1,1 1 0,1 0 1,1 1 1,1 0 0,(a)(b),(c)(d),(e)(f),图,54,编码位数对画面质量的影响,534 非线性,PCM,编码,在线性,PCM,编码中，量化阶是均匀的。这样，在小信号输入的情况下信噪比较低，在大信号输入的情况下信噪比较高。为了改善小信号在量化过程中的信噪比，采用一种瞬时压缩扩张技术。,这种技术实际上是降低大信号时的信噪比提高小信号时的信噪比，其结果是在不增加数码率的情况下，使信号在整个动态范围内有较均衡的信噪比。,瞬时压扩技术基本有两种方案。一种是如图57所示的方案。在这种方案中，首先将取样后的,PAM,信号进行非线性压缩，然后对压缩后的,PAM,信号进行线性编码。在接收端，首先进行线性译码，然后再送入瞬时扩张器进行非线性扩张，恢复原来的,PAM,信号。,量化,压缩,取样,编码,扩张,译码,输出,该方案一般采用二极管电压、电流的非线性特性来实现。通常采用图58所示的修正的对数特性。在图58中，对于压缩器来说，,X,表示输入，,Y,表示输出。对于扩张器来说，,Y,表示输入，,表示输出。参变量是表示压缩或扩张程度的量。显然，当=0时就是线性编码了。*,另外一种方案是数字化非线性压扩技术，,这种方案是把编码与压缩，译码与扩张都分别在编码和译码中一次完成。,数字式非线性编码的压扩特性有,特性、,A,特性等等。根据,CCITT1970,年的建议，通常采用,13,折线,(,A,=87.6),的压扩特性。,量化,采样,低通,编码及压缩,低通,译码及扩张,输出,13,折线压扩特性如图,510,所示。各折线的斜率列于表,53,中。由图中可见，各段折线的斜率是不一样的；,4,至,8,段的小信号区的信噪比都得到了改善。图中的表示压缩器的输入，表示压缩器的输出，,V,为过载点电压。,1,7/8,5/8,4/8,3/8,2/8,2/8,（,1,）,（,2,）,（,3),（,4,）,（,5,）,（,6,）,（,7,）,（,8,）,图,510 13,折线压扩特性,(,信号为正时的八段,),6/8,表,53,各种线段斜率表,折线段,1 2 3 4 5 6 7 8,斜 率,图,510,只画出了信号在正半周时的情况，负半周时也一样。由于正半周的,7,、,8,两段和负半周的,7,、,8,两段斜率都一样，所以在整个特性中这四段连成一条直线。因此，总共有,13,条直线段，简称,13,折线。,如果令 ，上述,13,折线可用下式近似表示,(514),(515),式中,A,是一常数，不同的,A,值可决定一条不同的曲线。在原点处的斜率由下式表示,(516),当原点处的斜率为,16,时，则,可求得,A,=87.6,。图,510,所示的折线就是,A,=87.6,的,13,折线压缩特性。,总的来说，如果采用第一种方案，当,=100,时，在输入信号最小情况下信噪比可提高,26dB,，,当采用第二种方案时，在,A,=87.6,的情况，最小信号输入时的信噪比改善大约,24dB,。,5.4,统计编码,高效编码的主要方法是尽可能去除信源中的冗余成份，从而以最少的数码率传递最大的信息量。冗余度存在于像素间的相关性及像素值出现概率的不均等性之中。对于有记忆性信源来说首先要去除像素间的相关性，从而达到压缩数码率的目的。,对于无记忆性信源来说，像素间没有相关性，可以利用像素灰度值出现概率的不均等性，采用某种编码方法，也可以达到压缩数码率的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫统计编码。,5.4.2,几种常用的统计编码法,5.4.,1,编码效率与冗余度,5.4.1,编码效率与冗余度,为了确定一个衡量编码方法优劣的准则，首先讨论一下编码效率与冗余度的问题。设某个无记忆信源共有,个消息，记作 。其中消息各自出现的概率分别为 。,(5,22),可把这个信源用下式表示,根据该信源的消息集合，在字母集中选取符号进行编码 。一般情况下取二元字母集,A,1,0,。通常，这一离散信源中的各个消息出现的概率并不相等。根据信息论中熵的定义，可计算出该信源的熵如下式,(5,23),式中,H,(,X,),代表熵，,P,i,代表第,i,个消息出现的概率。,例如，设一离散信源如下,由式,(5,23),可算出该信源的熵,比特,/,消息,设对应于每个消息的码字由,N,i,个符号组成。也就是说每个消息所对应的码字长度各为,N,i,。,那么，每个消息的平均码长可用下式表示,(5,24),式中 代表平均码长，,为信源中包含的消息的个数，,P,i,为第,i,个消息出现的概率，,N,i,为第,i,个消息对应的码长。就平均而言，每个符号所含有的熵为,(5,25),编码符号是在字母集,A,中选取的。如果编码后形成一个新的等概率的无记忆信源，字母数为,n,，那么，它的最大熵应为 比特,/,符号，因此，这是极限值。,如果 ，则可认为编码效率已达到,100,，若 ，则可认为编码效率较低。,由上述概念，编码效率如下式表示：,式中 代表编码效率，,H,(,X,),为信源的熵，为平均码长，,n,为字母集合中的字母数。,(5,26),如果以比特（,bit,）作单位，的底为,2,，根据上述定义，则,显然，如果 ，就说明还有冗余度。因此，冗余度如下式表示,(5,27),统计编码要研究的问题就在于设法减小 ，使 尽量趋近于,1,，趋近于,0,。显然 值有一个理论最低限，当,=1,时，的最低限就是 。可以根据这一准则来衡量编码方法的优劣。下面举例加以说明。,例,:,一个信源,X,和一个字母集合,A,如下,平均码长,bit/,消息,可求得信源,X,的熵,所以,显然，编码后还有,bit,的冗余度，没有达到 的最低限。,如果取,此时,那么可以编成如下等长码,的冗余度。,同样有,上例中的两种编码方法，其特点是码字长度均相等，这种码叫等长码。显然此例中的两种等长码均没有达到最低限。怎样才能使信源编码达到最低限呢？,再看下例的编码方法选,A=,0,1,n=,2,，作为编码字符集。在这种编码中，不用等长码，而是采用下面的原则来编码，即,P,i,大的消息编短码，,P,i,小的消息编长码。,例：,可计算出平均码长,其效率,冗余度,由此可见，这种编码法的码字平均长度达到了最低限。这说明用变长编码法可达到较高的效率。采用这种编码方法，信源中的消息与码字是一一对应的，因而译码时也是准确无误的。在编、译码过程中并不损失任何信息。它是一种信息保持编码法。,5.,4.2,几种常用的统计编码法,变长编码是统计编码中最为主要的一种方法。变长编码的目标就是使平均码长达到低限，也就是使 最优，但是，这种最优必须在一定的限制下进行。编码的基本限制就是码字要有,单义性,和,非续长性,。,单义性,代码是指任意一个有限长的码字序列只能被分割成一个一个的码字，而任何其他分割方法都会产生一些不属于码字集合中的码字。符合这个条件的代码就叫单义代码。,非续长,代码是指任意一个码字都不是其他码字的续长。换句话说，就是码字集合中的任意一个码字都不是由其中一个码字在后面添上一些码元构成的。,很容易看出,非续长代码一定是单义的，但是，单义代码却不一定是非续长的,。,表,54,四种代码表,信 源,概 率,码,码,码,码,0,0,0,0,0,1,1 0,0 1,1,0 0,1 1 0,0 1 1,1 0,1 1,1 1 1,0 1 1 1,例如，在表,54,中，列出四种代码，,码,：,显然码,缺乏单义可译性。,码,：,也缺乏单义可译性，又是可续长的。,码,：,既具备单义可译性又是非续长的码，它是,可用的。,码,也具有单义可译性，但是却缺乏非续长性。,从上面的例子可知，使 最短的码只是在单义可译性和非续长性的约束下才有意义。至于变长码的存在定理以及 的最低限是否存在等问题，在信息论中都有详细的定理加以证明及讨论，在此不加赘述了。,最为常用的变长编码方法是霍夫曼（,Huffman,）码和仙农费诺（,Shannon-,Fano,）码。下面详细地讨论一下这两种码的构成方法,5.4.3,霍夫曼码,霍夫曼码变长编码法能得到一组最优的变长码。设原始信源有,个消息，即,(5,28),可用下述步骤编出霍夫曼码：,第一步，把信源中的消息按出现的概率从大到小的顺序排列，,即,第二步，把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少一个，并同时再次将信源中的消息的概率从大到小排列一次，得,(5,29),第三步，重复上述步骤，直到信源最后为 形式为止。这里 有如下形式,(5,30),第四步，将被合并的消息分别赋以,1,和,0,或,0,和,1,。对最后,X,0,也对 和 对应地赋以,1,和,0,或,0,和,1,。,通过上述步骤就可以构成最优变长码（霍夫曼码）。下面举例说明具体构成方法。,例：求下述信源的霍夫曼码,由上述步骤，合并最小的两项做一个新的信源,这样可给 赋,0,，赋,1,，其中 。中消息的概率大小顺序正好符合从大到小的规律，故不必重排。再做新的信源,重排得,将 赋,0,，赋,1,。将 和 合并构成新的信源,重排得,将,赋,0,，,赋,1,。最后则,赋,1,。编码结果可,总结于表,5,5,中。编码图如图,5,17,所示。,赋,0,，,赋,1,。最后,赋,0,，,重排得,0.45,0.30,0.55,码字 消息 概率,0 1,1 0,1 1,0 0 0,0 0 1 0,0 0 1 1,0.25,0.25,0.20,0.15,0.10,0.05,0,1,0,1,0.25,0.25,0.20,0,1,0.30,0.25,0,1,0,1,图,517,信源,X,的,霍夫曼编码图,0.15,0.45,如对合并的消息赋以,1,，,0,值，则会得到如表,56,所示的另外一组码。表,55,信源,X,的霍夫曼编码表 表,56,信源,X,的另一组霍夫曼编码表,码 字,消 息,概 率,码 字,消 息,概 率,0 1,u,1,0.25,1 0,u,1,0.25,1 0,u,2,0.25,0 1,u,2,0.25,1 1,u,3,0.20,0 0,u,3,0.20,0 0 0,u,4,0.15,1 1 1,u,4,0.15,0 0 1 0,u,5,0.10,1 1 0 1,u,5,0.10,0 0 1 1,u,6,0.05,1 1 0 0,u,6,0.05,下面计算一下信源的熵，平均码长，效率及冗余度。,所以，对于信源,X,的霍夫曼码的编码效率为,98,，尚有,2,的冗余度。,5.,4.4,仙农费诺码,另外一种常用的变长编码是仙农费诺码。这种码有时也可以得到最优编码性能。它的编码准则要符合非续长条件，在码字中,1,和,0,是独立的，而且是（或差不多是）等概率的。,这样的准则一方面可保证无需用间隔来区分码字，同时又保证每传输位码就有,bit,的信息量。,仙农费诺码的编码程序可由下述几个步骤来完成：,第一步：设信源,有非递增的概率分布,(5,31),其中,。,把,X,分成两个子集合，得,(5,32),(5,34),成立或差不多成立。,并且保证,(5,33),第二步：给两个子集中的消息赋值，,X,1,赋,1,，,X,2,赋,0,，或给,X,1,赋,0,，,X,2,赋,1,。,第三步：重复第一步骤，将两个子集,X,1,，,X,2,再细分为,2,个子集，并且也同样使两个小子集里消息的概率之和相等或近似相等。,然后，重复第二步骤赋值。以这样的步骤重复下去，直到每个子集内只包含一个消息为止。对每个消息所赋过的值依次排列出来就可以构成仙农费诺码,下面举例说明仙农费诺码的具体构成方法,例：设有信源,其编码流程图如图,518,所示。编码表如表,57,所示。如果对各子集赋以另外一种值，即,1,，,0,，那么，同样会得到另一种编码结果，其编码表如表,58,所示。,码字 消息 概率,00,01,100,101,1100,1101,1110,1111,图,518,仙农,-,费诺码编码流程图,1/8,1/8,1/16,1/16,1/16,1/16,0,1,0,1,0,1,0,1,0 1,0 1,0 1,表,5,7,仙农,-,费诺码编码表 表,5,8,另一种仙农,-,费诺码编码表,消 息,概 率,码 字,消 息,概 率,码 字,0 0,1 1,0 1,1 0,1 0 0,0 1 1,1 0 1,0 1 0,1 1 0 0,0 0 1 1,1 1 0 1,0 0 1 0,1 1 1 0,0 0 0 1,1 1 1 1,0 0 0 0,下面计算一下仙农费诺码的平均码长，效率及冗余度。信源的熵可计算于下：,比特,/,消息,平均码长,显然，,效率已达到,100,。这一结果并不奇怪，对于仙农费诺码来说，如果满足下式,(5,35),且,(5,36),就会使编码效率达到,100,。式中的 为消息 出现的概率，是码字的长度。如果不满足上述条件就不会有,100,的效率，如下例中图,519,所示。,例：设有一信源,编码流程及形成的码字如图,5,19,所示。可以计算出信源的熵为,平均码长,由此例可见，由于信源不满足式,(535),和,(536),的条件，编码效率不能达到,100,。然而从结果上看，它仍然是一种相当好的编码。,冗余度,效率,编码 消息 概率,图,519,编码流程图,0,100,101,1100,1101,1110,11110,111110,111111,0.49,0.14,0.14,0.07,0.07,0.04,0.02,0.02,0.01,0,1,0,1,0 1,0,1,0,1,0 1,0 1,0 1,在,ITU-T,建议的彩色图像编码标准中的编码表如表,513,所示。,表,53 AC,系数,Huffman,码表,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,码长 码字 码长 码字,0/0,0/1,0/2,0/3,0/4,0/5,0/6,0/7,0/8,0/9,0/A,1/1,4,2,2,3,4,5,7,8,10,16,16,4,1010,00,01,100,1011,11010,1111000,11111000,1111110110,1111111110000010,1111111110000011,1100,2,2,3,4,5,5,6,7,9,10,12,4,00,01,100,1010,11000,11001,111000,1111000,111110100,1111110110,111111110100,1011,表,513,（续）,AC,系数,Huffman,码表,游程,/,尺寸,亮度,AC,系数,色度,AC,系数,码长 码字 码长 码字,1/2,1/3,1/5,1/6,1/7,1/8,1/9,1/A,2/1,2/2,2/3,5,7,9,11,16,16,16,16,16,5,8,10,11011,1111001,111110110,11111110110,1111111110000100,1111111110000101,1111111110000110,1111111110000111,1111111110000000,11100,11111001,1111110111,6,8,9,11,12,16,16,16,16,5,8,10,111001,11110110,111110101,11111110110,111111110101,1111111110001000,1111111110001001,1111111110001010,1111111110001011,11010,11110111,1111110111,码长 码字 码长 码字,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,表,513,（续）,AC,系数,Huffman,码表,2/4,2/5,2/6,2/7,2/8,2/9,2/A,3/1,3/2,3/3,3/5,12,16,16,16,16,1,6,16,6,9,12,16,16,111111110100,1111111110001001,1111111110001010,1111111110001011,1111111110001100,1111111110001101,1111111110001110,111010,111110111,111111110101,1111111110001111,1111111110010000,12,15,16,16,16,16,16,5,8,10,12,16,111111110110,111111111000010,1111111110001100,1111111110001110,1111111110001110,1111111110001111,1111111110010000,11011,11111000,1111111000,111111110111,1111111110010001,表,513,（续）,AC,系数,Huffman,码表,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,码长 码字 码长 码字,3/6,3/7,3/8,3/9,3/A,4/1,4/2,4/3,4/4,4/5,4/6,4/7,4/8,16,16,16,16,16,6,10,16,16,16,16,16,16,1111111110010001,1111111110010010,1111111110010011,1111111110010100,1111111110010101,111011,1111111000,1111111110010110,1111111110010111,1111111110011000,1111111110011001,1111111110011010,1111111110011011,16,16,16,16,16,6,9,16,16,16,16,16,16,1111111110010010,1111111110010011,1111111110010100,1111111110010101,1111111110010110,111010,111110110,1111111110010111,1111111110011000,1111111110011001,1111111110011010,1111111110011011,1111111110011100,表,513,（续）,AC,系数,Huffman,码表,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,码长 码字 码长 码字,4/9,4/A,5/1,5/2,5/3,5/4,5/5,5/6,5/7,5/8,5/9,5/A,6/1,16,16,7,11,16,16,16,16,16,16,16,16,7,1111111110011100,1111111110011101,1111010,11111110111,1111111110011110,1111111110011111,1111111110100000,1111111110100001,1111111110100010,1111111110100011,1111111110100100,1111111110100101,1111011,16,16,6,10,16,16,16,16,16,16,16,16,7,1111111110011101,1111111110011110,111011,1111111001,1111111110011111,1111111110100000,1111111110100001,1111111110100010,1111111110100011,1111111110100100,1111111110100101,1111111110100110,1111001,表,513,（续）,AC,系数,Huffman,码表,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,码长 码字 码长 码字,6/2 12 111111110110 11 11111110111,6/3 16 1111111110100110 16 1111111110100111,6/4 16 1111111110100111 16 1111111110101000,6/5 16 1111111110101000 16 1111111110101001,6/6 16 1111111110101001 16 1111111110101010,6/7 16 1111111110101010 16 1111111110101011,6/8 16 1111111110101011 16 1111111110101100,6/9 16 1111111110101100 16 1111111110101101,6/A 16 1111111110101101 16 1111111110101110,7/1 8 111110101 7 1111010,7/2 12 111111110111 11 11111111000,7/3 16 1111111110101110 16 1111111110101111,7/4 16 1111111110101111 16 1111111110110000,7/5 16 1111111110110000 16 1111111110110001,7/6 16 1111111110110001 16 1111111110110010,7/7 16 1111111110110010 16 1111111110110011,7/8 16 1111111110110011 16 1111111110110100,表,513,（续）,AC,系数,Huffman,码表,游程,/,尺寸 亮度,AC,系数 色度,AC,系数,码长 码字 码长 码字,7/9 16 1111111110110100 16 1111111110110101,7/A 16 1111111110110101 16 1111111110110110,8/1 9 111111000 8 11111001,8/2 15 111111111000000 16 1111111110110111,8/3 16 1111111110110110 16 1111111110111000,8/4 16 1111111110110111 16 1111111110111001,8/5 16 1111111110111000 16 1111111110111010,8/6 16 1111111110111001 16 1111111110111011,8/7 16 1111111110111010 16 1111111110111100,8/8 16 1111111110111011 16 1111111110111101,8/9 16 1111111110111100 16 1111111110111110,8/A 16 1111111110111101 16 1111111110111111,9/1 9 111111001 9 111110111,9/2 1