数字图像处理翟瑞芳第9章imagecoding

1、designed by ruifang zhai 华中农业大学计算机科学与技术系数数 字字 图图 像像 处处 理理 digital image processingdigital image processing翟瑞芳翟瑞芳designed by ruifang zhai 华中农业大学计算机科学与技术系第第9 9章章 图像编码图像编码 9.1 图像编码概述图像编码概述 9.2 无损编码无损编码9.3 有损编码有损编码 9.4 jpeg编码实例编码实例9.5 主流编码技术主流编码技术designed by ruifang zhai 华中农业大学计算机科学与技术系9.1 9.1 图像编码概述图像编

2、码概述 9.1.1 图像编码基本原理与方法图像编码基本原理与方法 1. 图像数据冗余图像数据冗余图像数据是高度相关的，即存在冗余（图像数据是高度相关的，即存在冗余（redundancy）信）信息。数字图像的冗余主要表现为以下几种形式：空间冗余、时间息。数字图像的冗余主要表现为以下几种形式：空间冗余、时间冗余、视觉冗余、冗余、视觉冗余、 信息熵冗余、结构冗余和知识冗余。信息熵冗余、结构冗余和知识冗余。designed by ruifang zhai 华中农业大学计算机科学与技术系2 图像编码方法图像编码方法 是否存在信息损耗：有损压缩和无损压缩；是否存在信息损耗：有损压缩和无损压缩； 根据编码原

3、理：熵编码、预测编码、变换编码和根据编码原理：熵编码、预测编码、变换编码和混合编码等。混合编码等。3 图像编码评价图像编码评价编码效率编码效率编码质量编码质量算法复杂度和适用范围算法复杂度和适用范围designed by ruifang zhai 华中农业大学计算机科学与技术系无损压缩编码无损压缩编码 9.2 huffman编码编码 (略略)9.3 香农香农-范诺范诺(shannon-fannon)编码编码 (略略)9.5 行程长度编码行程长度编码(run length encoding,rle) (略略)designed by ruifang zhai 华中农业大学计算机科学与技术系9.4

4、算算 术术 编编 码码 算术编码在图像数据压缩标准中扮演了重要的角算术编码在图像数据压缩标准中扮演了重要的角色。在算术编码中，消息用色。在算术编码中，消息用0 0到到1 1之间的实数进行编码，之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编算术编码用到两个基本的参数：符号的概率和它的编码间隔。码间隔。designed by ruifang zhai 华中农业大学计算机科学与技术系符号符号00000101101011 11 概率概率0.10.10.40.40.20.20.3 0.3 初始编码间隔初始编码间隔0, 0.1)0, 0.1)0.1, 0.5)0.1, 0.5)0.5,

5、 0.7)0.5, 0.7)0.7, 1) 0.7, 1) 假设信源符号为假设信源符号为00, 01, 10, 1100, 01, 10, 11，这些符号的概率分，这些符号的概率分别为别为 0.1, 0.4, 0.2, 0.3 0.1, 0.4, 0.2, 0.3 上面的信息可综合在下表中。上面的信息可综合在下表中。假设二进制消息序列的输入为：假设二进制消息序列的输入为：10 00 11 00 10 11 0110 00 11 00 10 11 01。designed by ruifang zhai 华中农业大学计算机科学与技术系算术编码示意图算术编码示意图startn=startb+left

6、cl endn=startb+rightcl designed by ruifang zhai 华中农业大学计算机科学与技术系步骤步骤 输入输入符号符号编码间隔编码间隔 编码判决编码判决1 110100.5, 0.7)0.5, 0.7)符号的间隔范围符号的间隔范围0.5, 0.7) 0.5, 0.7) 2 200000.5, 0.52)0.5, 0.52)0.5, 0.7)0.5, 0.7)间隔的第一个间隔的第一个1/101/103 311110.514, 0.52)0.514, 0.52)0.5, 0.52)0.5, 0.52)间隔的最后间隔的最后3 3个个1/101/104 400000.

7、514, 0.5146)0.514, 0.5146)0.514, 0.52)0.514, 0.52)间隔的第一个间隔的第一个1/101/105 510100.5143, 0.5143, 0.51442)0.51442)0.514, 0.5146)0.514, 0.5146)间隔的第五个间隔的第五个1/101/10开始，二开始，二个个1/101/106 611110.514384, 0.514384, 0.51442)0.51442)0.5143, 0.51442)0.5143, 0.51442)间隔的最后间隔的最后3 3个个1/101/107 701010.5143836, 0.5143836

8、, 0.514402)0.514402)0.514384, 0.51442)0.514384, 0.51442)间隔的间隔的4 4个个1/101/10，从第，从第1 1个个1/101/10开始开始8 8从从0.5143876, 0.5144020.5143876, 0.514402中选择一个数作为输出：中选择一个数作为输出：0.51438760.5143876designed by ruifang zhai 华中农业大学计算机科学与技术系步步骤骤 间隔间隔译码符译码符号号 译码判决译码判决 1 10.5, 0.7)0.5, 0.7)10100.514390.51439在间隔在间隔 0.5, 0

9、.7)0.5, 0.7)2 20.5, 0.52)0.5, 0.52)00000.514390.51439在间隔在间隔 0.5, 0.7)0.5, 0.7)的第的第1 1个个1/101/103 30.514, 0.52)0.514, 0.52)11110.514390.51439在间隔在间隔0.5, 0.52)0.5, 0.52)的第的第7 7个个1/101/104 40.514, 0.5146)0.514, 0.5146)00000.514390.51439在间隔在间隔0.514, 0.52)0.514, 0.52)的第的第1 1个个1/101/105 50.5143, 0.51442)0.

10、5143, 0.51442)10100.514390.51439在间隔在间隔0.514, 0.5146)0.514, 0.5146)的第的第5 5个个1/101/106 60.514384, 0.514384, 0.51442)0.51442)11110.514390.51439在间隔在间隔0.5143, 0.51442)0.5143, 0.51442)的第的第7 7个个1/101/107 70.51439, 0.51439, 0.5143948)0.5143948)01010.514390.51439在间隔在间隔0.51439, 0.5143948)0.51439, 0.5143948)的第

11、的第1 1个个1/101/107 7译码的消息：译码的消息：10 00 11 00 10 11 0110 00 11 00 10 11 01designed by ruifang zhai 华中农业大学计算机科学与技术系9.6 lzw编码编码 1. 词典编码的两种思想词典编码的两种思想（1）寻找正在压缩的字符序列是否在以前输入的数据中出现过，）寻找正在压缩的字符序列是否在以前输入的数据中出现过，用已出现过的字符串替代重复的过程，它的输出为指针。用已出现过的字符串替代重复的过程，它的输出为指针。（2）从输入的数据中创建一个）从输入的数据中创建一个“短语词典（短语词典（dictionary of

12、the phrases）”，它可以是任意字符的组合。在编码过程中，当遇，它可以是任意字符的组合。在编码过程中，当遇到词典中已出现的到词典中已出现的“短语短语”，则输出，则输出“短语短语”的索引号。的索引号。 lzw编码属于第二种编码思想。编码属于第二种编码思想。designed by ruifang zhai 华中农业大学计算机科学与技术系2. lzw编码编码（1）相关术语）相关术语 字符流（字符流（charstream）：被编码的数据序列；）：被编码的数据序列； 字符（字符（character）：字符流中的基本数据单元；）：字符流中的基本数据单元； 前缀（前缀（prefix）：在一个字符之前

13、的字符序列；）：在一个字符之前的字符序列； 缀缀-符串（符串（string）：前缀字符；）：前缀字符； 码字（码字（code word）：码字流中基本数据单元，代表词典中的）：码字流中基本数据单元，代表词典中的一串字符；一串字符； 码字流（码字流（code stream）：编码器输出的数据序列；）：编码器输出的数据序列；designed by ruifang zhai 华中农业大学计算机科学与技术系（1）相关术语）相关术语词典（词典（dictionary）：缀）：缀-符串表；符串表；当前前缀（当前前缀（current prefix）：当前正在处理的前缀，用）：当前正在处理的前缀，用p表示；表示

14、；当前字符（当前字符（current character）：当前前缀之后的字符，用）：当前前缀之后的字符，用c表示；表示；当前码字（当前码字（current code word）：译码过程中当前正在处理的）：译码过程中当前正在处理的码字；码字；前缀根（前缀根（root）：字符流中的所有单个字符串。）：字符流中的所有单个字符串。designed by ruifang zhai 华中农业大学计算机科学与技术系（2）lzw的编码算法的编码算法具体步骤：具体步骤：1) 词典初始化过程；词典初始化过程；2) 当前字符（当前字符（c）:=码字流中第一个字符；码字流中第一个字符；3) 判断缀判断缀-符串符串

15、p+c是否在词典中；是否在词典中；a. 若是，若是，p:=p+c（用（用c扩展扩展p）；）；b. 若否：若否：a) 把代表当前前缀把代表当前前缀p的码字输出到码字流；的码字输出到码字流；b) 把缀把缀-符串符串p+c添加到词典；添加到词典；c) 令令p:=c（现在的（现在的p仅包含一个字符仅包含一个字符c）;designed by ruifang zhai 华中农业大学计算机科学与技术系4) 判断字符流中是否还有字符要编码；判断字符流中是否还有字符要编码；a. 若是，返回若是，返回2)；b. 若否：若否：a) 把代表当前前缀把代表当前前缀p的码字输出到码字流；的码字输出到码字流；b) 结束。结

16、束。designed by ruifang zhai 华中农业大学计算机科学与技术系（3）lzw的编码实例的编码实例 输入字符流：输入字符流：a b a b c b a b a b a a a a a a a 输出码字流：输出码字流：(1) (2) (4) (3) (5) (8) (1) (10) (11) (1) designed by ruifang zhai 华中农业大学计算机科学与技术系lzw编编码码流流程程图图初始化词典初始化词典p=nullc:=下一个字符下一个字符p+c是否在词典中是否在词典中输出输出p的码字的码字p+c添入词典添入词典p:=c是否结束是否结束结束结束p:=p+c是是否否是是否否designed by ruifang zhai 华中农业大学计算机科学与技术系 例：有垂直边缘图像如下例：有垂直边缘图像如下 设有设有512字带有初始内容的字典：字带有初始内容的字典：designed by ruifang zhai 华中农业大学计算机科学与技术系designed by ruifang zhai 华中农业大学计算机科学与技术系 photoshop中中 未压缩未压缩tiff版本：版本：286740字