图像压缩编码1-2节

1、数字图像的压缩是指在不同用途的图像质量要求数字图像的压缩是指在不同用途的图像质量要求下，用最少的比特数表示一幅图像的技术。下，用最少的比特数表示一幅图像的技术。数字图像的压缩是实现图像存储和传输的基础。数字图像的压缩是实现图像存储和传输的基础。 数字图像压缩目的：数字图像压缩目的： 节省图像存储容量；减少传输信道容量；缩节省图像存储容量；减少传输信道容量；缩短图像加工处理时间。短图像加工处理时间。 6.16.1数字图像压缩编码基础数字图像压缩编码基础 6.1.1 6.1.1 图像压缩的基本概念图像压缩的基本概念 1. 信息相关信息相关 在绝大多数图像的像素之间，在绝大多数图像的像素之间， 各像

2、素行和帧之各像素行和帧之间存在着较强的相关性。从统计观点出发，就是每个间存在着较强的相关性。从统计观点出发，就是每个像素的灰度值（或颜色值）总是和其周围的其它像素像素的灰度值（或颜色值）总是和其周围的其它像素的灰度值（或颜色值）存在某种关系，应用某种编码的灰度值（或颜色值）存在某种关系，应用某种编码方法减少这些相关性就可实现图像压缩。方法减少这些相关性就可实现图像压缩。 图像压缩的基本概念图像压缩的基本概念 1. 信息相关信息相关 引例引例(图图)： 上图的黑白像素序列共上图的黑白像素序列共41位，编码为：位，编码为：1111111111，00000000，111111 5 5位位 1515位

3、位 7 7位位 1111位位 3 3位位 新的编码只需新的编码只需21位：位： 1 1，01010101，11111111，01110111，10111011，0011 0011 由此可见，利用图像中各像素之间存在的信息相由此可见，利用图像中各像素之间存在的信息相关，可实现图像编码信息的压缩。关，可实现图像编码信息的压缩。 图像压缩的基本概念图像压缩的基本概念 2. 信息冗余信息冗余 从信息论的角度来看，从信息论的角度来看， 压缩就是去掉信息中的冗压缩就是去掉信息中的冗余。即保留确定信息，去掉可推知的确定信息，用一种余。即保留确定信息，去掉可推知的确定信息，用一种更接近信息本质的描述来代替原有

4、的冗余描述。更接近信息本质的描述来代替原有的冗余描述。 图像数据存在的冗余可分为三类：图像数据存在的冗余可分为三类： （1）编码冗余；）编码冗余； （2）像素间的冗余；）像素间的冗余； （3）心里视觉冗余。）心里视觉冗余。 图像压缩的基本概念图像压缩的基本概念 2. 信息冗余信息冗余（续（续1 1） （1 1）编码冗余）编码冗余 由于大多数图像的直方图不是均匀由于大多数图像的直方图不是均匀( (水平水平) )的，所的，所以图像中某个（或某些）灰度级会比其它灰度级具有以图像中某个（或某些）灰度级会比其它灰度级具有更大的出现概率，如果对出现概率大和出现概率小的更大的出现概率，如果对出现概率大和出现

5、概率小的灰度级都分配相同的比特数，必定会产生编码冗余。灰度级都分配相同的比特数，必定会产生编码冗余。 图像压缩的基本概念图像压缩的基本概念 2. 信息冗余信息冗余（续（续2） （2 2）像素间的冗余）像素间的冗余 所谓所谓“像素间的冗余像素间的冗余”，是指单个像素携带的信，是指单个像素携带的信息相对较少，单一像素对于一幅图像的多数视觉贡献息相对较少，单一像素对于一幅图像的多数视觉贡献是多余的，是多余的， 它的值可以通过与其相邻的像素的值来它的值可以通过与其相邻的像素的值来推断。推断。 图像压缩的基本概念图像压缩的基本概念 2. 信息冗余信息冗余（续（续3） （3 3）心里视觉冗余）心里视觉冗余

6、 心里视觉冗余是指在正常的视觉处理过程中那些心里视觉冗余是指在正常的视觉处理过程中那些不十分重要的信息。不十分重要的信息。 图像压缩的基本概念图像压缩的基本概念 3. 信源编码及其分类信源编码及其分类 信源编码：信源编码： 图像压缩的目的是在满足一定的图像质量的条件图像压缩的目的是在满足一定的图像质量的条件下，用尽可能少的比特数来表示原图像，以减少图像下，用尽可能少的比特数来表示原图像，以减少图像的存储容量和提高图像的传输效率。的存储容量和提高图像的传输效率。 在信息论中，把这种通过减少冗余数据来实现数在信息论中，把这种通过减少冗余数据来实现数据压缩的过程称为信源编码。据压缩的过程称为信源编码

7、。 图像压缩的基本概念图像压缩的基本概念 3. 信源编码及其分类信源编码及其分类（续（续1 1） 信源编码的分类：信源编码的分类：无失真编码和有失真编码无失真编码和有失真编码 无失真压缩也称为无损压缩，是一种在不引入无失真压缩也称为无损压缩，是一种在不引入任何失真的条件下使表示图像的数据比特率为最小的任何失真的条件下使表示图像的数据比特率为最小的压缩方法。压缩方法。 有失真压缩也称为有损压缩方法，是一种在一有失真压缩也称为有损压缩方法，是一种在一定比特率下获得最佳保真度，或在给定的保真度下获定比特率下获得最佳保真度，或在给定的保真度下获得最小比特率的压缩方法。得最小比特率的压缩方法。 6.1.

8、2 6.1.2 保真度准则保真度准则 1. 客观保真度准则客观保真度准则 当所损失的信息量可表示成原图像与该图像先被当所损失的信息量可表示成原图像与该图像先被压缩而后又被解压缩而获得的图像的函数时，就称该压缩而后又被解压缩而获得的图像的函数时，就称该函数是基于客观保真度准则的。函数是基于客观保真度准则的。 ( , )( , )( , )e x yf x yf x y（6.16.1） 6.1.2 6.1.2 保真度准则保真度准则 1. 客观保真度准则客观保真度准则( (续续1)1) 设设f(x,y)f(x,y)表示原图像，表示原图像， 表示先被压缩而后又被表示先被压缩而后又被解压缩而获得的图像，

9、解压缩而获得的图像，x0 x0，M-1M-1，y0y0，N-1N-1。则。则对于任意的对于任意的x x和和y y，F(x,y)F(x,y)和和 之间的误差定义为：之间的误差定义为： (, )f xy( , )f xy1100 ( , )( , )MNxyf x yf x y两幅图像之间的总误差定义为：两幅图像之间的总误差定义为：6.1.2 6.1.2 保真度准则保真度准则 112 1/2001 ( , )( , ) MNrmsxyef x yf x yMN（6.26.2） 1. 客观保真度准则客观保真度准则( (续续2)2) （1 1）f(x,y)f(x,y)与与 之间的均方根误差之间的均方根

10、误差( , )f x yrmse（2 2）f(x,y)f(x,y)与与 之间的均方根信噪比之间的均方根信噪比( , )f x y（6.36.3） 1120011200( , ) ( , )( , )MNxymsMNxyf x ySNRf x yf x y均方信噪比：均方信噪比： 对式（对式（6.36.3）求平方根就可得到均方根信噪比）求平方根就可得到均方根信噪比rmsSNR6.1.2 6.1.2 保真度准则保真度准则 2. 主观保真度准则主观保真度准则 主观评价的一般方法是，通过给一组观察者提供主观评价的一般方法是，通过给一组观察者提供原图像和典型的解压缩图像，由每个观察者对解压缩原图像和典型

11、的解压缩图像，由每个观察者对解压缩图像的质量给出一个主观的评价，并将他们的评价结图像的质量给出一个主观的评价，并将他们的评价结果进行综合平均，从而得出一个统计平均意义下的评果进行综合平均，从而得出一个统计平均意义下的评价结果。价结果。 评分评分评价评价评价标准描述评价标准描述1 12 23 34 45 56 6优秀优秀良好良好可用可用勉强可用勉强可用差差不能用不能用 图像的质量非常好，达到了人所想象的质量标准图像的质量非常好，达到了人所想象的质量标准和显示效果。和显示效果。 图像质量高，观看效果好，有时有干扰，但不影图像质量高，观看效果好，有时有干扰，但不影响观看效果。响观看效果。 图像的质量

12、尚好，观看效果一般，有干扰，但尚图像的质量尚好，观看效果一般，有干扰，但尚不影响观看。不影响观看。 图像质量较差，干扰有些妨碍观看，但是还可以图像质量较差，干扰有些妨碍观看，但是还可以观看。观看。 图像质量很差，干扰令人讨厌，但观察者还可以图像质量很差，干扰令人讨厌，但观察者还可以忍耐。忍耐。图像质量极差，已经无法观看。图像质量极差，已经无法观看。 表表6.1 6.1 一种典型的图像质量主观保真度评价准则一种典型的图像质量主观保真度评价准则 6.1.2 6.1.2 保真度准则保真度准则 2. 主观保真度准则主观保真度准则 （续（续1 1）6.1.3 6.1.3 图像编码模型图像编码模型 信信

13、源源编码器编码器信信 源源解码器解码器信信 道道解码器解码器信信道道信信 道道编码器编码器编码器编码器解码器解码器),(yxf),(yxf1. 图像编码系统模型图像编码系统模型 6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器信道编码器和信道解码器是一种用来实现抗干扰、信道编码器和信道解码器是一种用来实现抗干扰、 抗噪声的可靠数字通信技术措施。抗噪声的可靠数字通信技术措施。信道编码器是通过向信源编码数据中插入可控制的信道编码器是通过向信源编码数据中插入可控制的 冗余数据来减少对信道噪声的影响的。冗余数据来减少对信道噪声的影响的。 信信 源源编

14、码器编码器信信 源源解码器解码器信信 道道解码器解码器信信道道信信 道道编码器编码器编码器编码器解码器解码器),(yxf),(yxf6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续1 1）汉明信道编码技术的基本原理：汉明信道编码技术的基本原理： 给被编码的数据后面补充足够的位数，以确保各给被编码的数据后面补充足够的位数，以确保各个正确的码字之间的最小距离大于某个给定的值。个正确的码字之间的最小距离大于某个给定的值。 0231bbbh33bh 0132bbbh25bh 0124bbbh16bh 07bh （6.46.4）6.1.3 6.

15、1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续2 2） 设一个设一个4bit4bit的二进制数为的二进制数为 ，当信道编码采，当信道编码采用汉明编码时，对应的用汉明编码时，对应的7 7位汉明码位汉明码 由下由下式确定：式确定：0123bbbb7654321hhhhhhh汉明编码的结果是一个偶数位编码。汉明编码的结果是一个偶数位编码。 6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续3 3） 对汉明码的解码是通过对在编码时建立的偶校验对汉明码的解码是通过对在编码时建立的偶校验的位串进行奇校验

16、并检查校验字的值来实现的。的位串进行奇校验并检查校验字的值来实现的。7653hhhh汉解码结果（汉解码结果（ ）：）：75311hhhhc76322hhhhc76544hhhhc（6.56.5）124ccc对于对于单个比特位的错误来说，是由一个非零的奇偶单个比特位的错误来说，是由一个非零的奇偶校验字校验字 给出。并且：给出。并且： 6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续4 4）例例6.1.1 6.1.1 设信道编码器的输入设信道编码器的输入=(0110)=(0110)。 （1 1）求信道编码器的输出码字值，若信道传输正）求信

17、道编码器的输出码字值，若信道传输正确，请验证并说明奇校验结果正确。确，请验证并说明奇校验结果正确。 （2 2）若在传输过程中第）若在传输过程中第6 6位的值传输错误，请验位的值传输错误，请验证并说明奇校验结果。证并说明奇校验结果。 6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续5 5）例例6.1.1 (1)6.1.1 (1)编码：已知编码：已知20123)0110(bbbb10100231bbbh10100132bbbh00110124bbbh033 bh125 bh116 bh007 bh也即：信道编码器输出的也即：信道编码器输出

18、的7 7个比特位为：个比特位为： 276543211100110hhhhhhh6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道编码器与信道解码器信道编码器与信道解码器（续（续6 6）例例6.1.1 6.1.1 解码：解码： （2 2）当传输正确时，解码器的输入应为：）当传输正确时，解码器的输入应为：276543211100110hhhhhhh且：且：0010175311hhhhc0010176322hhhhc0011076544hhhhc校验码全校验码全0 0，校验结果正确，说明无传输错误。，校验结果正确，说明无传输错误。6.1.3 6.1.3 图像编码模型图像编码模型 2. 信道

19、编码器与信道解码器信道编码器与信道解码器（续（续7 7）例例6.1.1 6.1.1 解码：解码： （3 3）当传输不正确，且假设第）当传输不正确，且假设第6 6位传输错误时，位传输错误时，解码器的输入应为：解码器的输入应为：27654321)1100100(hhhhhhh0010175311hhhhc1000176322hhhhc1001076544hhhhc且：且：2124)110ccc校验码校验码 ，说明第，说明第6 6位传输有错误。位传输有错误。 6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型在信息论中，把通过减少冗余

20、来压缩数据的过程称在信息论中，把通过减少冗余来压缩数据的过程称为信源编码。为信源编码。信源编码器的作用就是减少或消除输入图像中的编信源编码器的作用就是减少或消除输入图像中的编码冗余。码冗余。信信 源源编码器编码器信信 源源解码器解码器信信 道道解码器解码器信信道道信信 道道编码器编码器编码器编码器解码器解码器),(yxf),(yxf6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型信源编码器模型：信源编码器模型：映射变换器的作用：是将输入的图像数据转换为可映射变换器的作用：是将输入的图像数据转换为可以减少输入图像中像素间冗余的表

21、示格式，其输出是以减少输入图像中像素间冗余的表示格式，其输出是比原始图像数据更适合于高效压缩的图像表示形式。比原始图像数据更适合于高效压缩的图像表示形式。 信道编码器信道编码器或信道或信道映射变映射变换换 器器符号编符号编码码 器器量化器量化器),(yxf6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型信源编码器模型信源编码器模型（续（续1 1）：典型的映射变换包括：典型的映射变换包括： （1 1）线性预测变换。如各种正交变换，应用差分映射）线性预测变换。如各种正交变换，应用差分映射图像编码的差分编码等预测编码；图像编码的差分

22、编码等预测编码； （2 2）酉变换。如可将图像能量集中到少数系数上的）酉变换。如可将图像能量集中到少数系数上的DCTDCT变换；变换； （3 3）多分辨率变换。如子带分解和小波变换等；）多分辨率变换。如子带分解和小波变换等； （4 4）其它变换。如二值图像的游程编码等。）其它变换。如二值图像的游程编码等。信道编码器信道编码器或信道或信道映射变映射变换换 器器符号编符号编码码 器器量化器量化器),(yxf6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型信源编码器模型信源编码器模型（续（续2 2）：量化器的作用是产生用于表示被压缩

23、图像的有限数量化器的作用是产生用于表示被压缩图像的有限数量的符号（详见节）。量的符号（详见节）。 信道编码器信道编码器或信道或信道映射变映射变换换 器器符号编符号编码码 器器量化器量化器),(yxf6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型信源编码器模型信源编码器模型（续（续3 3）：符号编码器的作用是对量化器输出的每一个符号分符号编码器的作用是对量化器输出的每一个符号分配一个码字或二进制比特流。配一个码字或二进制比特流。 信道编码器信道编码器或信道或信道映射变映射变换换 器器符号编符号编码码 器器量化器量化器),(yx

24、f6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型符号编码器：符号编码器：符号编码器符号编码器,10nxxxX,21maaaA,10nwwwW其中，输入其中，输入X X称为信源符号集，集合中的每一个元素称为信源符号集，集合中的每一个元素x xi i称为信源符号。输出称为信源符号。输出W W称为代码，集合中的每一个称为代码，集合中的每一个元素元素w wi i称为码字。称为码字。A A称为码元集，集合中的每一个元称为码元集，集合中的每一个元素素a aj j称为码元。称为码元。 6.1.3 6.1.3 图像编码模型图像编码模型 3.

25、 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型符号编码器：符号编码器：符号编码器符号编码器,10nxxxX,21maaaA,10nwwwW符号编码器的功能：是用码元集符号编码器的功能：是用码元集A A中的一组码元中的一组码元a aj j建建立输入的信源符号立输入的信源符号x xi i与输出的码字与输出的码字w wi i之间的关系。也之间的关系。也就是为信源符号集中的每一个元素就是为信源符号集中的每一个元素x xi i分配一个用一组分配一个用一组码元码元a aj j表示的码字表示的码字w wi i。所有的码字。所有的码字w wi i都按规定的编码都按规定的编码方式，由方式，由a

26、aj j来组成。来组成。 6.1.3 6.1.3 图像编码模型图像编码模型 3. 信源编码器模型与信源解码器模型信源编码器模型与信源解码器模型信源解码器模型：信源解码器模型：信道编码器信道编码器或信道或信道),(yxf符符 号号解码器解码器反向映射反向映射变变 换换 器器反量化器反量化器6.1.4 6.1.4 独立信源与信息量独立信源与信息量 ,10nxxxX)(,),(),()(10nxpxpxpXP （6.6）被编码的符号序列中的所有符号构成了信源。被编码的符号序列中的所有符号构成了信源。最简单的信源就是独立信源。最简单的信源就是独立信源。一个独立信源可由一个信源符号集一个独立信源可由一个

27、信源符号集X X和每一个符号和每一个符号出现的概率描述，即：出现的概率描述，即： )(log)()()()(200iniiiniixPxPxIxPXH (6.8) 6.1.4 6.1.4 独立信源与信息量独立信源与信息量 若对一个独立信源中所有可能的符号的信息量取平若对一个独立信源中所有可能的符号的信息量取平均值，就得到信源中每个符号的平均信息量，也称为均值，就得到信源中每个符号的平均信息量，也称为信源的熵，即：信源的熵，即： iLiippHln10 （6.9）6.1.4 6.1.4 独立信源与信息量独立信源与信息量 对于一幅灰度分布为对于一幅灰度分布为X=0X=0，1 1，L-1L-1的数字

28、图的数字图像，其每个灰度出现的概率为像，其每个灰度出现的概率为P=pP=p0 0，p p1 1，p pL-1L-1 。该图像的信息熵定义为：该图像的信息熵定义为： 6.26.2最基本的编码方法最基本的编码方法 6.2.1 6.2.1 变长编码变长编码 变长编码的基本思想是用尽可能少的比特数表示变长编码的基本思想是用尽可能少的比特数表示出现概率尽可能大的灰度级出现概率尽可能大的灰度级, ,以实现数据的压缩编码以实现数据的压缩编码。由于利用这些编码方法得到的码字长度是不相等的。由于利用这些编码方法得到的码字长度是不相等的，所以称为变长编码。，所以称为变长编码。 变长编码变长编码 1. 费诺码费诺码

29、 费诺编码方法认为：在数字形式的码字中的费诺编码方法认为：在数字形式的码字中的0 0和和1 1是相互独立的，因而其出现的概率也应是相等的（为是相互独立的，因而其出现的概率也应是相等的（为0.50.5或接近或接近 0.50.5），这样就可确保传输的每一位码含），这样就可确保传输的每一位码含有有1 1比特的信息量。比特的信息量。 诺设输入的离散信源符号集为诺设输入的离散信源符号集为X=xX=x0 0,x,x1 1,x,xn n ，其出，其出现概率为现概率为P(xP(xi i) )，欲求的费诺码为，欲求的费诺码为W=wW=w0 0,w,w1 1,，w wn n ，则费，则费诺码编码方法的步骤为：诺码

30、编码方法的步骤为： 变长编码变长编码 费诺码编码方法的步骤：费诺码编码方法的步骤： （1 1）把输入的信源符号和其出现的概率按概率值的非）把输入的信源符号和其出现的概率按概率值的非递增顺序从上到下依次并列排列。递增顺序从上到下依次并列排列。 （2 2）按概率之和相等或相近的原则把）按概率之和相等或相近的原则把X X分成两组，并分成两组，并给上面或概率之和较大的组赋值给上面或概率之和较大的组赋值1 1，给下面或概率之和较，给下面或概率之和较小的组赋值小的组赋值0 0。 （3 3）再按概率之和相等或相近的原则把现有的组分成）再按概率之和相等或相近的原则把现有的组分成两组，并给上面或概率之和较大的组

31、赋值两组，并给上面或概率之和较大的组赋值1 1，给下面或概，给下面或概率之和较小的组赋值率之和较小的组赋值0 0。 （4 4）重复（）重复（3 3）的分组和赋值过程，直至每个组只有）的分组和赋值过程，直至每个组只有一个符号为止。一个符号为止。 （5 5）把对每个符号所赋的值依次排列，就可得到信源）把对每个符号所赋的值依次排列，就可得到信源符号集符号集X X的费诺码。的费诺码。 变长编码变长编码 1. 1. 费诺码费诺码例例6.2.1 6.2.1 设有信源符号集设有信源符号集X=xX=x1 1,x,x2 2,x,x8 8 ，其概率分，其概率分布为布为P(xP(x1 1)=0.25)=0.25，P

32、(xP(x2 2)=0.25)=0.25，P(xP(x3 3)=0.125)=0.125，P(xP(x4 4)=0.125)=0.125，P(xP(x5 5)=0.0625)=0.0625，P(xP(x6 6)=0.0625)=0.0625，P(xP(x7 7)=0.0625)=0.0625，P(xP(x8 8)=0.0625)=0.0625，求其费诺码，求其费诺码W=wW=w1 1,w,w2 2,w,w3 3,w,w4 4,w,w5 5,w,w6 6,w,w7 7,w,w8 8 。 即有：即有：P(xP(x1 1)=0.25=1/4 )=0.25=1/4 P(xP(x2 2)=0.25=1/

33、4)=0.25=1/4 P(x P(x3 3)=0.125=1/8 )=0.125=1/8 P(xP(x4 4)=0.125=1/8)=0.125=1/8 P(x P(x5 5)=0.0625=1/16 P(x)=0.0625=1/16 P(x6 6)=0.0625=1/16)=0.0625=1/16 P(x P(x7 7)=0.0625=1/16 P(x)=0.0625=1/16 P(x8 8)=0.0625=1/16)=0.0625=1/16 符号符号 概率概率 编码结果编码结果 1/4 1 111/4 1 11 1/4 1 0 10 1/4 1 0 10 1/8 1 011 1/8 1

34、011 1/8 1 0 010 1/8 1 0 010 1/16 0 1 0011 1/16 0 1 0011 1/16 0 1 0 0010 1/16 0 1 0 0010 1/16 1 0001 1/16 1 0001 1/16 0 0 0000 1/16 0 0 00007x8x)(ixP1x2x3x4x5x6xix变长编码变长编码 例例6.2.1 6.2.1 解：解：平均码字长度：平均码字长度： 81)(iiilxPL4161416141614161381381241241)(432bit变长编码变长编码 2. 霍夫曼编码霍夫曼编码 诺设输入的离散信源符号集为诺设输入的离散信源符号集为

35、X=xX=x0 0,x,x1 1,x,xn n ，其出，其出现概率为现概率为P(xP(xi i) )，欲求的霍夫曼编码为，欲求的霍夫曼编码为W=wW=w0 0,w,w1 1,，w wn n ，则霍夫曼编码方法的步骤为：则霍夫曼编码方法的步骤为： 霍夫曼编码方法的步骤：霍夫曼编码方法的步骤： （1 1）把输入的信源符号和其出现的概率按概率值的大）把输入的信源符号和其出现的概率按概率值的大小顺序从上到下依次并列排列。小顺序从上到下依次并列排列。 （2 2）把最末两个具有最小概率的元素的概率进行相加，）把最末两个具有最小概率的元素的概率进行相加，再把相加得到的概率与其余概率按大小顺序从上到下进行再把

36、相加得到的概率与其余概率按大小顺序从上到下进行排列。排列。 变长编码变长编码 2. 霍夫曼编码霍夫曼编码（续（续1 1） （3 3）重复（）重复（2 2），直到最后只剩下两个概率为止。如），直到最后只剩下两个概率为止。如果再把剩余的两个概率合并作为树根，那么从后向前直至果再把剩余的两个概率合并作为树根，那么从后向前直至每个信源符号（的初始概率）就形成了一棵二叉树。每个信源符号（的初始概率）就形成了一棵二叉树。 （4 4）从最后的二叉树根开始为每个节点的分支逐步向）从最后的二叉树根开始为每个节点的分支逐步向前进行编码，给概率较大（上方）的分支赋予前进行编码，给概率较大（上方）的分支赋予0 0，给

37、概率，给概率较小（下方）的分支赋予较小（下方）的分支赋予1 1。 （5 5）从树根到每个树叶的所有节点上的）从树根到每个树叶的所有节点上的0 0或或1 1就构成了就构成了该树叶，也即对应的信源符号，的编码。该树叶，也即对应的信源符号，的编码。 变长编码变长编码 2. 2. 霍夫曼编码霍夫曼编码（续（续2） 例例6.2.2 6.2.2 设有信源符号集设有信源符号集X=xX=x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,x,x6 6 ，其，其概率分布分别为概率分布分别为P(xP(x1 1)=0.4)=0.4，P(xP(x2 2)=0.3)=0.3，P(xP(x3 3)=0.1)

38、=0.1，P(xP(x4 4)=0.1)=0.1，P(xP(x5 5)=0.06)=0.06，P(xP(x6 6)=0.04)=0.04，求其霍夫曼编码求其霍夫曼编码W=wW=w1 1,w,w2 2,w,w3 3,w,w4 4,w,w5 5,w,w6 6 。 ix0 0 0.10.11 10 0 0.10.11 10 0 0.30.31 10 0 0.3 0.31 10 0 1 1 0.060.06 0.04 0.04 6x)(ixP1x 0.4 0.4 0.4 0.4 0.60.4 0.4 0.4 0.4 0.6 2x 0.3 0.3 0.3 0.30.3 0.3 0.3 0.3 3x 0.

39、1 0.1 0.1 0.1 0.20.2 4x 0.1 0.1 0.1 0.1 5x变长编码变长编码 例例6.2.1 6.2.1 解：编码过程为：解：编码过程为：编码编码w wi i： 1 00 011 0100 01010 010111 00 011 0100 01010 01011信源符号：信源符号： w1 w2 w3 w4 w5 w6概率概率P(xi)： 0.4 0.3 0.1 0.1 0.06 0.04 变长编码变长编码 例例图图6.2.3 6.2.3 例的霍夫编码二叉树例的霍夫编码二叉树 0 0 0 1 0 1 0 1 1 1 3 . 0)(2xp1 . 0)(4xp06. 0)(5

40、xp04. 0)(6xp1 . 0)(3xp4 . 0)(1xp1x3x6x5x4x2x变长编码变长编码 2. 2. 霍夫曼编码霍夫曼编码（续（续4） 霍夫曼编码的优点：霍夫曼编码的优点：当对独立信源符号进行编码时，霍夫曼编码可对每个当对独立信源符号进行编码时，霍夫曼编码可对每个 信源符号产生可能是最少数量（最短）码元的码字。信源符号产生可能是最少数量（最短）码元的码字。霍夫曼编码是所有变长编码中平均码长最短的。如果霍夫曼编码是所有变长编码中平均码长最短的。如果 所有信源符号的概率都是所有信源符号的概率都是2 2的指数，霍夫曼编码的平的指数，霍夫曼编码的平 均长度将达到最低限，即信源的熵。均长

41、度将达到最低限，即信源的熵。 对于二进制的霍夫曼编码，平均码字的平均长度满足对于二进制的霍夫曼编码，平均码字的平均长度满足 关系：关系： 1HLH变长编码变长编码 3. 3. 几种接近最佳的变长编码几种接近最佳的变长编码 输入输入 输出输出WiWi( (信源符号信源符号i)i)二进制编码二进制编码 B1B1码码B2B2码码二进制移位码二进制移位码0 000000000C0C0C00C000000001 100010001C1C1C01C010010012 200100010C0C0C0C0C10C100100103 300110011C0C1C0C1C11C110110114 40100010

42、0C1C0C1C0C00C00C00C001001005 501010101C1C1C1C1C00C01C00C011011016 601100110C0C0C0C0C0C0C00C10C00C101101107 701110111C0C0C1C0C0C1C00C11C00C111110001110008 810001000C0C1C0C0C1C0C01C00C01C001110011110019 910011001C0C1C1C0C1C1C01C01C01C01111010111010101010101010C1C0C0C1C0C0C01C10C01C10111011111011111110

43、111011C1C0C1C1C0C1C01C11C01C11111100111100121211001100C1C1C0C1C1C0C10C00C10C00111101111101131311011101C1C1C1C1C1C1C10C01C10C01111110111110141411101110C0C0C0C0C0C0C0C0C10C10C10C10111111000111111000151511111111C0C0C0C1C0C0C0C1C10C11C10C11111111001111111001 表表6.2.1 几种典型的变长变码几种典型的变长变码,543210 xxxxxxX ,54

44、3210wwwwwwW 543210,wwwwww,543210wwwwwwW )(6 . 2404. 0406. 041 . 041 . 023 . 0204bitL例例 4 . 0)(1xP3 . 0)(2xP1 . 0)(3xP1 . 0)(4xP06. 0)(5xP04. 0)(6xP自学：自学：B1码、码、B2码和二进制移位码码和二进制移位码输入输入( (信信源符号源符号) )移位移位码码输入输入( (信信源符号源符号) )移位移位码码输入输入( (信信源符号源符号) )移位码移位码000011001100111100111100010111011101111101111101101

45、011101110111110111110表表6.3 6.3 每个块只有每个块只有3 3个信源符号的二进制移位码编码个信源符号的二进制移位码编码1x2x3x4x5x6x7x8x9x自学：自学：B1码、码、B2码和二进制移位码码和二进制移位码变长编码变长编码 4. 4. 算术编码算术编码 算术编码假设，对于一个独立信源来说，任一由信源算术编码假设，对于一个独立信源来说，任一由信源符号组成的长度为符号组成的长度为N N的序列的发生概率之和等于的序列的发生概率之和等于1 1。 根据信源符号序列的概率，把根据信源符号序列的概率，把00，11区间划分为互不区间划分为互不重叠的子区间，子区间的宽度恰好等于

46、各符号序列的概率，重叠的子区间，子区间的宽度恰好等于各符号序列的概率，这样，每个子区间内的任意一个实数都可以用来表示对应这样，每个子区间内的任意一个实数都可以用来表示对应的符号。的符号。 显然，一串符号序列发生的概率越大，对应的子区间显然，一串符号序列发生的概率越大，对应的子区间就越宽，表达它所用的比特数就越少，因而相应的码字就就越宽，表达它所用的比特数就越少，因而相应的码字就越短。越短。 变长编码变长编码 4. 4. 算术编码算术编码（续（续1 1）算术编码过程：算术编码过程： （1 1）建立概率模型，即通过扫描统计，获得各信源符）建立概率模型，即通过扫描统计，获得各信源符号的概率大小号的概

47、率大小 （2 2）编码过程，即扫描符号序列，依次分割相应的区）编码过程，即扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。间，最终得到符号序列所对应的码字。 图图6.9 6.9 算术编码过程图示算术编码过程图示变长编码变长编码 4. 4. 算术编码算术编码（续（续2 2）举例举例: :设有一个四信源符号的五符号输入序列设有一个四信源符号的五符号输入序列a a1 1a a2 2a a2 2a a3 3a a4 4。 （1 1）建立信源符号集的概率模型：通过扫描可知信源）建立信源符号集的概率模型：通过扫描可知信源符号符号a a1 1a a2 2a a3 3a a4 4的出现概率依次

48、为的出现概率依次为0.20.2、0.40.4、0.20.2和和0.20.2。 （2 2）编码过程：）编码过程： 编码序列 056.0088.04a3a2a1a2a3a4a3a3a3a3a2a2a2a1a1a1a1a4a4a4a4a0752.008032.00816.012.004.02 .00012a1a2a（K=1，2，N） （6.15a6.15a）111KKKkWALL111)(KKKKkWPALR（6.15b6.15b） KKkLRW（6.15c6.15c） 变长编码变长编码 4. 4. 算术编码算术编码（续（续3 3）举例举例: :（3 3）编码过程的数学描述）编码过程的数学描述 设由

49、设由M M个信源符号个信源符号X=xX=x1 1x x2 2xxm m组成的长度为组成的长度为N N的输入符的输入符号序列中，各信源符号的概率分布为号序列中，各信源符号的概率分布为P Pj j（j=1,2,j=1,2,，M M；k=1,2,Nk=1,2,N；MNMN），），00，1 1）为对输入符号序列进行算）为对输入符号序列进行算术编码的初始区间，则对第术编码的初始区间，则对第k k个输入符号进行算术编码的个输入符号进行算术编码的子分区间子分区间LLk k，R Rk k）定义为：）定义为： 6.26.2最基本的编码方法最基本的编码方法 6.2.2 6.2.2 位平面编码位平面编码 所谓位平面

50、编码，就是将一幅灰度图像或彩色图所谓位平面编码，就是将一幅灰度图像或彩色图像分解为多幅二值图像的过程。像分解为多幅二值图像的过程。 1. 1. 位平面分解位平面分解 一幅一幅m m位的灰度级图像的灰度值可用多项式表示位的灰度级图像的灰度值可用多项式表示为：为： 001122112222xxxxmmmm（6.176.17）其中，其中，x xi i00，11。 位平面编码位平面编码 1. 1. 位平面分解位平面分解( (续续1)1) 举例来说，对于一幅举例来说，对于一幅N NN N的灰度图像，若每个像的灰度图像，若每个像素用素用m m位表示，就可以从每个像素的二进制表示中取位表示，就可以从每个像素

51、的二进制表示中取出相同位置上的一位，这样就形成了一幅出相同位置上的一位，这样就形成了一幅N NN N的二值的二值图像图像，称该二值图像为原灰度图像的一个位平面称该二值图像为原灰度图像的一个位平面。 对于一幅对于一幅256256灰度级的图像来说，每个像素用一灰度级的图像来说，每个像素用一个个8 8位的字节表示，该图像就可以分解成位的字节表示，该图像就可以分解成8 8个位平面，个位平面，平面平面0 0由原图像中像素的最低位组成，平面由原图像中像素的最低位组成，平面1 1由原图像由原图像中像素的此低位组成，中像素的此低位组成，平面，平面7 7由原图像中像素的由原图像中像素的最高位组成。最高位组成。原

52、图像的一个原图像的一个像素对应像素对应8 8位位位平面位平面7 7( (最高位最高位)位平面位平面0 0( (最低位最低位) )01010101 8585灰度图像灰度图像图图6.10 86.10 8位图像的位平面分解图示位图像的位平面分解图示位平面编码位平面编码 1. 1. 位平面分解位平面分解( (续续2)2) 图图6.11 6.11 一幅一幅8 8位图像及其该图像的位图像及其该图像的8 8个位平面二值图像个位平面二值图像位平面编码位平面编码 2. 2. 位平面的格雷码分解编码位平面的格雷码分解编码 多数图像中的大多数相邻像素值具有渐变的特征，但多数图像中的大多数相邻像素值具有渐变的特征，但

53、若采用二进制码进行位平面分解，就会导致各位平面中相若采用二进制码进行位平面分解，就会导致各位平面中相关性的减小。关性的减小。比如，若灰度图像中的两个相邻像素是比如，若灰度图像中的两个相邻像素是127127和和128128，它们显，它们显然比较接近，但其二进制编码却分别为然比较接近，但其二进制编码却分别为 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 和和 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0也即灰度图像中相邻像素间的很小变化，却引起了所有位也即灰度图像中相邻像素间的很小变化，却引起了所有位平面值的突变，从而降低了位平面图像的相关性，也即降平面值的突变，

54、从而降低了位平面图像的相关性，也即降低了位平面图像的压缩效率。低了位平面图像的压缩效率。 位平面编码位平面编码 2. 2. 位平面的格雷码分解编码位平面的格雷码分解编码（续（续1 1） 由于两个相邻值的格雷码之间只有一位是不同的，这由于两个相邻值的格雷码之间只有一位是不同的，这样就可保持相邻像素间较强的相关性，所以一般采用格雷样就可保持相邻像素间较强的相关性，所以一般采用格雷码（码（GrayGray）进行位平面分解编码。）进行位平面分解编码。 位平面编码位平面编码 2. 2. 位平面的格雷码分解编码位平面的格雷码分解编码（续（续1 1） 采用格雷码进行位平面分解编码的思想是，如果用一采用格雷码

55、进行位平面分解编码的思想是，如果用一个个m m位的灰度编码位的灰度编码g gm-1m-1gg2 2g g1 1g g0 0表示图像，那么图像中这个表示图像，那么图像中这个m m位的灰度编码位的灰度编码g gm-1m-1gg2 2g g1 1g g0 0的所有的所有g gi i就组成了第就组成了第i i个位平面个位平面二值图像。二值图像。20mi1iiixxg11mmxg（6.186.18） 设反映灰度值大小的设反映灰度值大小的m m位二进制编码为位二进制编码为x xm-1m-1xx2 2x x1 1x x0 0，与其对应的与其对应的m m位格雷码为位格雷码为g gm-1m-1gg2 2g g1

56、 1g g0 0 ，则有：，则有： 6.26.2最基本的编码方法最基本的编码方法 6.2.3 6.2.3 游程编码游程编码 一般把具有相同灰度值的一些像素组成的序列称一般把具有相同灰度值的一些像素组成的序列称为一个游程。为一个游程。 把取相同灰度值的若干连续像素点的数目称为游把取相同灰度值的若干连续像素点的数目称为游程长度，简称游长。程长度，简称游长。 6.26.2最基本的编码方法最基本的编码方法 6.2.3 6.2.3 游程编码游程编码 在黑白图像中，像素点为黑和白，或者说像素在黑白图像中，像素点为黑和白，或者说像素只取只取0 0和和1 1两个灰度值，这样，就把连续白点和连续黑两个灰度值，这

57、样，就把连续白点和连续黑点的数目分别称为白长和黑长。点的数目分别称为白长和黑长。 因为像素点只取两个灰度值，所以黑白图像与因为像素点只取两个灰度值，所以黑白图像与灰度图像相比，相邻像素点的相关性更强，游程编码灰度图像相比，相邻像素点的相关性更强，游程编码正好利用了这种相关性。正好利用了这种相关性。 游程编码的基本思想是：只存储一个代表某个游程编码的基本思想是：只存储一个代表某个灰度值的码，后面是它的游程长度，这样同样的灰度灰度值的码，后面是它的游程长度，这样同样的灰度值码就不必存储多次。值码就不必存储多次。 游程编码游程编码1. 1. 一维游程编码一维游程编码 在编码时，对每一行的第一个像素要

58、有一个标志在编码时，对每一行的第一个像素要有一个标志码，以区分该行是以白长开始还是以黑长开始，并给码，以区分该行是以白长开始还是以黑长开始，并给出其编码。对于后面的游长，只要给出相应游长的编出其编码。对于后面的游长，只要给出相应游长的编码。码。 决定游程长度值最通常的约定是：决定游程长度值最通常的约定是： （1 1）指定每一行第一个游程的值；）指定每一行第一个游程的值； （2 2）假设每一行从白色游程开始，这个游程长度）假设每一行从白色游程开始，这个游程长度可以为可以为0 0（如果该一行是从黑色游程开始）。（如果该一行是从黑色游程开始）。 游程编码游程编码1. 1. 一维游程编码（续一维游程编

59、码（续1 1） 国际国际 标准标准CCITT T.4CCITT T.4（G3G3）采用的是一维）采用的是一维游程编码。游程编码。 编码方法是：游长的霍夫曼编码分为形成码编码方法是：游长的霍夫曼编码分为形成码和终止码两种。对于位于和终止码两种。对于位于0 06363之间的游长，用单之间的游长，用单个的码字，即终止码表示；对于大于个的码字，即终止码表示；对于大于6363的游长，的游长，用一个形成码和一个终止码的组合来表示，其中用一个形成码和一个终止码的组合来表示，其中，形成码表示实际游长的，形成码表示实际游长的6464的最大倍数值，终止的最大倍数值，终止码表示其余小于码表示其余小于6464的差值。

60、的差值。 表表6.4 6.4 国际国际 标准标准ITUITU（CCITT T.4 G3CCITT T.4 G3）终止码表）终止码表 游长游长 白长码字白长码字 黑长码字黑长码字 0 00110101 0000110111 1 000111 010 2 0111 11 3 1000 10 4 1011 011 5 1100 0011 6 1110 0010 63 00110100 1游程编码游程编码1. 1. 一维游程编码一维游程编码（续（续2 2） 表6.5 国际 标准ITU（CCITT T.4 G3）形成码表 游长游长 白长码字白长码字 （码字）（码字） 黑长码字黑长码字 64 11011