第十五讲 图像的编码和压缩.

1、 Lecture 15 Image Coding and CompressionPurposen 图像压缩的概念、目的和意义图像压缩的概念、目的和意义n 图像的霍夫曼编码、香农编码、算术编码、图像的霍夫曼编码、香农编码、算术编码、行程编码方法行程编码方法Explain Contentsn 了解图像压缩的目的和意义，熟悉图像保真了解图像压缩的目的和意义，熟悉图像保真度准则度准则n 掌握图像霍夫曼编码、香农编码、算术编码、掌握图像霍夫曼编码、香农编码、算术编码、行程编码方法行程编码方法n 图像压缩图像压缩(Image Compression)的概念的概念 数据压缩的研究内容包括数据的表示、传数据压

2、缩的研究内容包括数据的表示、传输、变换和编码方法，目的是减少存储数据所输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。需的空间和传输所用的时间。 图像压缩图像压缩就是在一个可以接受的还原状况就是在一个可以接受的还原状况的前提下用尽可能少的比特数来表示源信号，的前提下用尽可能少的比特数来表示源信号，即把需要存储或传输的图像数据的比特数减少即把需要存储或传输的图像数据的比特数减少到最少程度。图像压缩是通过到最少程度。图像压缩是通过编码编码实现的。实现的。 概述概述n 图像数据压缩的必要性图像数据压缩的必要性 图像数据的特点之一是信息量大。海量数据需要巨大图像数据的特点之一是信息量

3、大。海量数据需要巨大的存储空间。如多媒体中的海量图像数据，不进行编码压的存储空间。如多媒体中的海量图像数据，不进行编码压缩处理，一张缩处理，一张600M字节的光盘，只能存放字节的光盘，只能存放20秒左右的秒左右的640 480像素的图像。没有编码压缩，多媒体信息保存像素的图像。没有编码压缩，多媒体信息保存有多么困难是可想而知的。有多么困难是可想而知的。 在现代通信中，图像传输已成为重要内容之一。采用在现代通信中，图像传输已成为重要内容之一。采用编码压缩技术，减少传输数据量，是提高通信速度的重要编码压缩技术，减少传输数据量，是提高通信速度的重要手段。可见，没有图像编码与压缩技术的发展，大容量图手

4、段。可见，没有图像编码与压缩技术的发展，大容量图像信息的存储与传输是难以实现的，多媒体、信息高速公像信息的存储与传输是难以实现的，多媒体、信息高速公路等新技术在实际中的应用会遇到很大困难。路等新技术在实际中的应用会遇到很大困难。概述概述n 图像数据压缩的可能性图像数据压缩的可能性概述概述 从信息论观点看，描述图像信源的数据由有从信息论观点看，描述图像信源的数据由有用数据和冗余数据两部分组成。用数据和冗余数据两部分组成。duDI信息量信息量数据量数据量冗余量冗余量 冗余量是可以压缩的冗余量是可以压缩的，在实际应用中应尽量保证去除，在实际应用中应尽量保证去除冗余量而不会减少信息量，即压缩数据在一定

5、条件可以近冗余量而不会减少信息量，即压缩数据在一定条件可以近似恢复。似恢复。Data compression is achieved when one or more of these redundancies are reduced or eliminated.Types of redundancyIn digital image compression, we discuss three basic data redundancies:1. Coding redundancy;2. Interpixel redundancy;3. Psychovisual redundancy.数据冗余数

6、据冗余(Data Redundancy)n 编码冗余编码冗余(Coding Redundancy)等长编码等长编码 平均码长为平均码长为3 3变长编码变长编码 平均码长为平均码长为2.72.7Illustration of variable-length coding不等长编码数据冗余数据冗余n 像素间冗余像素间冗余(Interpixel Redundancy) 图像是由按一定规则排列起来的像素组成，图像中相图像是由按一定规则排列起来的像素组成，图像中相邻像素的灰度往往相同或相近，这就称为像素间冗余或空邻像素的灰度往往相同或相近，这就称为像素间冗余或空间冗余。间冗余。数据冗余数据冗余n 心理视

7、觉冗余心理视觉冗余(Psychovisual Redundancy) 175K 1.46M 受生理和心理上的影响，人眼对黑白和彩色信息的受生理和心理上的影响，人眼对黑白和彩色信息的分辨率是有限的。光学上不一致的图像在视觉上可能是分辨率是有限的。光学上不一致的图像在视觉上可能是一样。一样。Psychovisual redundancy (视觉冗余)The human eye does not respond with equal sensitivity to all visual information, certain information simply has less relative

8、importance than other information in normal visual processing. This information is said to be psychovisually redundant. It can be eliminated without significantly impairing the quality of image perception. The elimination of psychovisually redundant data results in a loss of quantitative information

9、, so it is commonly referred to as quantization. It is an irreversible operation (visual information is lost), quantization results in lossy data compression.Characteristics of quantization图像压缩系统模型图像压缩系统模型信源信源 信源信源编码器编码器信道信道编码器编码器通信线路通信线路或或存储介质存储介质信源信源解码器解码器信道信道解码器解码器信宿信宿 压缩的有效性压缩的有效性编码的可靠性编码的可靠性The

10、 source encoder and decoderMapper is designed to reduce interpixel redundancies. (eg. Run-length coding). Quantizer reduces psychovisual redundancies, this operation is irreversible. Symbol encoder reduces coding redundancy, this operation is reversible.Three part of the source encoder图像保真度准则图像保真度准则

11、描述解码图像相对原始图像偏离程度的测度一般称为描述解码图像相对原始图像偏离程度的测度一般称为保真保真度度。常用的保真度准则可分为两大类：客观保真度准则和。常用的保真度准则可分为两大类：客观保真度准则和主观保真度准则。主观保真度准则。n 客观保真度准则客观保真度准则 最常用的客观保真度准则是原图像和解码图像之间的最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪比两种。均方根误差和均方根信噪比两种。n 主观保真度准则主观保真度准则 很多解压图最终是供人观看的，一种常用的方法是让很多解压图最终是供人观看的，一种常用的方法是让一组（不少于一组（不少于20人）观察者观察图像并给该图像

12、评分，人）观察者观察图像并给该图像评分，将他们对该图像的评分取平均，作为这幅图像的质量。将他们对该图像的评分取平均，作为这幅图像的质量。信息论要素信息论要素(Elements of Information Theory)n 熵熵(Entropy)MkkkPPH12logMkkkPR1根据根据Shannon无干扰信息保持编码定理，若对原始图像数据的信息进无干扰信息保持编码定理，若对原始图像数据的信息进行无失真图像编码，压缩后平均码长存在一个下限，这个下限是图像行无失真图像编码，压缩后平均码长存在一个下限，这个下限是图像信息熵信息熵H。理论上最佳信息保持编码的平均码长可以无限接近图像信息。理论上最

13、佳信息保持编码的平均码长可以无限接近图像信息熵熵H。但总是大于或等于图像的熵。但总是大于或等于图像的熵H。n 平均码长平均码长(Average Code Length)平均信息量度，图像中各灰度级比特数的统计平均值。平均信息量度，图像中各灰度级比特数的统计平均值。M: 灰度级数Pk:灰度级Wk出现的概率出现的概率灰度级制代码的位数）对应的码字长度（二进灰度级kkkkWPW:For an information source producing J possible source symbols a1,a2,aj, each with probability P(aj), then the av

14、erage information per source output obtained from the source z, denoted H(z), isJjjjaPaPH1)(log)()(zH(z) is called the uncertainty or entropy of the source.The entropy (熵熵)of the sourcen 编码效率编码效率Coding Efficiencyn 冗余度冗余度Redundancy1)()(xHxRrrxRxH11)()(熵编码目的：使熵编码目的：使R尽量减少至尽量减少至H 信息论要素信息论要素(Elements of

15、 Information Theory)例题例题设一离散信源如下：设一离散信源如下： 00211WX01412W10813W11814W信源信源概率概率编码编码求信源求信源X的熵、平均码长和编码效率。的熵、平均码长和编码效率。解：解： 412logkkkPPH熵：4781log8181log8141log4121log212222比特比特平均码长：平均码长：编码效率：编码效率：比特比特281281241221241kkkPR%5 .8787247RHn 变长最佳编码定理变长最佳编码定理 对概率大的消息符号赋予短码字，而对概率小的信对概率大的消息符号赋予短码字，而对概率小的信息符号赋予长码字，则

16、编码的平均码长一定最短。息符号赋予长码字，则编码的平均码长一定最短。 如：如： Wm Wn Pm tn tm：长码：长码 tn：短码：短码22nmmnmmnntPtPtPtP 02222222222mnmnmnmnmnttPPtPPtPPnmmnmmnntPtPtPtP符合定理的平均码长符合定理的平均码长不符合定理的平均码长不符合定理的平均码长n 唯一可译编码唯一可译编码 所编码字序列能唯一地译出来。所编码字序列能唯一地译出来。单义性、非续长码单义性、非续长码是是唯一可译编码。唯一可译编码。单义性代码单义性代码：任意一个有限长的码字序列只能被唯一：任意一个有限长的码字序列只能被唯一地分割成一个

17、个码字。地分割成一个个码字。非续长代码非续长代码：集合中的码字不能由其他码字在后面添：集合中的码字不能由其他码字在后面添加码元构成。加码元构成。如：如： 信源信源 概率概率 码码I 码码II 码码III 码码IV W1 1/2 0 0 0 0 W2 1/4 0 1 10 01 W3 1/8 1 00 110 011 W4 1/8 10 11 111 0111码码I：非单义性、续长码：非单义性、续长码 如如： 00110 W1W2W3W4 W1W1W3W3W1 W1W1W3W3W2码码II：非单义性、续长码：非单义性、续长码 如：如： 010011 W1W2W3W4 W1W2W1W1W4 W1W

18、2W1W3W2W2 W1W2W1W1W2W2码码III：单义性、非续长码：单义性、非续长码 如如： 010110111 W1W2W3W4码码IV：单义性、续长码：单义性、续长码 如如： 0010110111 W1W2W3W4单义非续长代码平均码长最短单义非续长代码平均码长最短单义代码的充要条件：单义代码的充要条件：D：代码中的码元种类；：代码中的码元种类； n：代码中的码字个数；：代码中的码字个数；ti：第：第i个码字的码长；个码字的码长；如上例：如上例：11nitiD单义码：码单义码：码非单义码：码非单义码：码11615222221222221232222214722222432141332

19、141221141211141ititititiiiiIVIIIIII图像编码压缩的分类图像编码压缩的分类图像压缩图像压缩无损编码无损编码有损编码有损编码霍夫曼编码霍夫曼编码行程编码行程编码算术编码算术编码预测编码预测编码变换编码变换编码其它编码其它编码根据解压重建后的图像和原始图像之间是否具有误差，根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩分为图像编码压缩分为无损无损（亦称无失真、无误差、信息保（亦称无失真、无误差、信息保持）编码和持）编码和有损有损（有失真或有误差）编码两大类。（有失真或有误差）编码两大类。1. Information preserving: allow

20、an image to be compressed and decompressed without losing information.It is used in the storage of legal or medical records.2. Information lossy: provide higher levels of data reduction but result in a less than perfect reproduction of the original image. It is useful in applications such as broadca

21、st television, facsimile transmission, and videoconferencing.Categories of compression techniques Huffman编码是编码是1952年由年由Huffman提出的一种编码提出的一种编码方法。这种编码方法是根据信源数据符号发生的概率进行方法。这种编码方法是根据信源数据符号发生的概率进行编码的。编码的。霍夫曼编码霍夫曼编码(Huffman Coding)思想：思想： 在信源数据中出现概率越大的符号，编码以后相应的在信源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长，从而

22、达到码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符表示信源数据。它在无损变长编码方法用尽可能少的码符表示信源数据。它在无损变长编码方法中是最佳的。中是最佳的。1. 把输入符号按出现的概率从大到小排列起来把输入符号按出现的概率从大到小排列起来,接着把概接着把概 率最小的两个符号的概率求和率最小的两个符号的概率求和;2. 把它（概率之和）同其余符号概率由大到小排序把它（概率之和）同其余符号概率由大到小排序,然后然后把两个最小概率求和把两个最小概率求和;3. 重复重复2,直到最后只剩下两个概率为止。直到最后只剩下两个概率为止。在上述工作完毕之后，从最后两个概率开始逐步向前进行编码

23、。对于在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予概率大的消息赋予0，小的赋予，小的赋予1。在反向进行的过程中，若概率不。在反向进行的过程中，若概率不变，保留原码字；若概率分裂为两个，前几位保留原码字，最后一位变，保留原码字；若概率分裂为两个，前几位保留原码字，最后一位一个赋一个赋“0”，另一个赋，另一个赋“1”码。码。 编码方法编码方法：符号集符号集x1x2x3x4x5x6概率分布概率分布0.4010.090.08Huffman编码编码符号集符号集经排序的经排序的概率分布概率分布 第一次合第一次合并后排序并后排序第二次合第二次合并后排序并

24、后排序第三次合第三次合并后排序并后排序第四次合第四次合并后排序并后排序第五次合第五次合并后排序并后排序x10.400.400.400.400.601x30.370.40 x00.23x7x50.090.11x60.08符号集符号集经排序经排序的概率的概率分布分布 第一次第一次合并后合并后排序排序第二次第二次合并后合并后排序排序第三次第三次合并后合并后排序排序第四次第四次合并后合并后排序排序第五次第五次合并后合并后排序排序x10.400.400.400.400.601x30.370.40 x30.12

25、3x7x50.090.11x60.0801100010100000111100000000101001101001100100011符号集符号集x1x2x3x4x5x6概率分布概率分布0.4010.090.08Huffman编码编码100001001100100011 用二叉树方法实现用二叉树方法实现Huffman编码方法也较为便利。编码方法也较为便利。 计算该信源的熵、编码后的平均码长，并思考对计算该信源的熵、编码后的平均码长，并思考对于同一图像采用于同一图像采用Huffman编码，编码是否唯一？编码，编码是否唯一？0.23

26、0.4 x10.6 0.11 x4 1 0 1 00.37 0.20 x2 0.08 x60 .09 x50.17 1 0 1 0 1 00.12 x3Steps of Huffman codingSource reduction principle: ordering the probabilities of the symbol in a descending order and combining the lowest probability symbols into a single symbol.Huffman codingThe average length of this cod

27、e is:Lavg = (0.4)(1) + (0.3)(2) + (0.1)(3) + (0.1)(4) + (0.06)(5) + (0.04)(5) = 2.2 bits/symbolThe entropy of the source is:H(z) = -0.4log2(0.4)-0.3log2(0.3)-20.1log2(0.1)-0.06log2(0.06)-0.04log2(0.04) = 2.1435Huffman code efficiency is:9743. 02 . 21435. 2)(avgLH z香农编码香农编码(Shannon Coding)1P-logPlog-

28、i2i2it编码方法：编码方法：1、将输入灰度级按出现的概率由大到小排列；、将输入灰度级按出现的概率由大到小排列；2、按、按 计算各概率对应的码长；计算各概率对应的码长；3、计算各灰度级对应的累加概率：、计算各灰度级对应的累加概率：4、把各个累加概率由十进制数转换成二进制数：、把各个累加概率由十进制数转换成二进制数：转换规则：乘转换规则：乘2取整，先取的整数为高位，后取的整数为低位。取整，先取的整数为高位，后取的整数为低位。5、将二进制表示的累加概率去掉多于、将二进制表示的累加概率去掉多于ti的尾数，即得的尾数，即得Wi对应的码字对应的码字。1212131210PPPaPPaPaaiii04.

29、005.006.007.010.010.018.040.0概率87654321WWWWWWWW灰度级55544432it平均码长96.091.085.078.068.058.040.000.0dia11110111011101111001010100101100bia11110111011101111001010100101100码字812logkkkPPH熵：55. 2)04. 0log04. 005. 0log05. 006. 0log06. 007. 0log07. 010. 0log10. 010. 0log10. 018. 0log18. 040. 0log40. 0(2222222

30、217. 304. 0505. 0506. 0507. 0410. 0410. 0418. 0340. 0281kkkPR%4 .8017. 355. 2RH算术编码算术编码(Arithmetic Coding)思想：思想： 按照符号序列的出现概率区间分割，用一个实数按照符号序列的出现概率区间分割，用一个实数代表一个数据流的输入符号，再将这个实数转化为一代表一个数据流的输入符号，再将这个实数转化为一定位数的二进制代码。对于较长的消息，二进制代码定位数的二进制代码。对于较长的消息，二进制代码的位数也会增加。的位数也会增加。它们是通过算术运算逐步形成码字它们是通过算术运算逐步形成码字的，因而得名。

31、的，因而得名。 设四阶设四阶Markov信源符号集为信源符号集为a, b, c, d，其概率分，其概率分布为布为0.2, 0.2, 0.4, 0.2。（1）若对该信源进行）若对该信源进行Huffman编码，可得其平均码长为编码，可得其平均码长为2.0比特比特/字符字符（2）若信源发出序列为）若信源发出序列为b, c, a, c, d，算数编码过程，算数编码过程如下：如下：各个数据符号在半封闭实数区间各个数据符号在半封闭实数区间0，1）内按概率进行赋）内按概率进行赋值范围设定为值范围设定为)0 . 1 , 8 . 0),8 . 0 , 4 . 0),4 . 0 , 2 . 0),2 . 0 ,

32、0 . 0dcba数据流数据流bcacd编码区间编码区间0.2,0.4 ） 0.28,0.36 ） 0.28,0.296 ）0.2864,0.2928 ）0.29152,0.2928 ）区间长度区间长度0.20.080.0160.00640.00128新子区间左端前一子区间左端新子区间左边累加概率新子区间左端前一子区间左端新子区间左边累加概率前子区间长度前子区间长度新子区间长度当前区间概率新子区间长度当前区间概率前子区间长度前子区间长度Arithmetic codingSource A contains a1 a2 a3 a4, p(a1) = 0.2; p(a2) = 0.2; p(a3)

33、= 0.4; p(a4) = 0.2Basic thinking: An entire sequence of source symbols (or message) is assigned a single arithmetic code word.A message is generated from the above four symbol code as: a1a2a3a3a4Coding steps: assign intervals according to source symbol probability and message length. The longer, the

34、 message, the smaller, the interval.Source A contains a1 a2 a3 a4, p(a1) = 0.2; p(a2) = 0.2; p(a3) = 0.4; p(a4) = 0.2Any number in this range represents the message a1a2a3a3a4 . For example, 0.068 can be used to do so.Result: The entropy H(z) = 0.58, a 5-symbol message reduces to 068, that is 3 symbols, this translates to 3/5 = 0.6 decimal digits per source symbol, which is close to the entropy.Arithmetic coding行程编码行程编码(Run-length Coding)思想：思想： 有些图像具有许多颜色相同的图块，在这些图块中，许多连续的有些图像具有许多颜色相同的图块，在这些图块中，许多连续的扫描行都具有同一颜色，或者同一扫描行上有许多连续的像素都具有扫描行都具有同一颜色