多媒体数据压缩技术1.ppt

第四章 多媒体数据压缩技术 第四章 数据压缩技术Data Compression Technologies 本章主要介绍目前用得最多和技术最成熟的数据压缩编码技术。数据压缩可分成两种类型，一种叫做无损(lossless)压缩，另一种叫做有损(lossy)压缩。 无损压缩编码技术包括霍夫曼编码、算术编码、RLE编码和词典编码。 有损压缩技术如离散余弦变换、小波变换等。 内容提纲 4.1 数据压缩技术概述 4.2 霍夫曼(Huffman)编码算法 4.3 算术(Arithmetic)编码算法 4.4 RLE编码(Run Length Encoding)算法 4.5 词典(Dictionary)编码算法 作业 运用Huffman, 算术编码，LZ77分别对下段文字进行编解码： (Huffman编码可设置码表) 参考文献 题名：多媒体数据压缩技术 丛编题名：全国高技术重点图书 ISBN号：7-5053-2206-0 出版项：北京 电子工业出版社 1994.4 著者：高文 题名：数据压缩技术及其应用 丛编题名：计算机科学大众丛书 ISBN号： 7-5053-3253-8 出版项：北京 电子工业出版社 1995 著者：袁玫,袁文 题名：数据压缩技术原理与范例 ISBN号： 7-03-004846-6 出版项：北京 科学出版社 1995 著者： (美)Mark Nelson 题名：数据压缩技术及其应用 ISBN号：7-115-03835-X 出版项：北京 人民邮电出版社 1989.6 著者：(美)林　奇(Lynch,T.J.) 数据压技术缩概述An Introduction to Data Compression 基本概念与定义 数据压缩技术的分类 常用的数据压缩方法 数据压缩的必要性 数据通信 数据存储 … 考虑的因素 不能失真 磁盘文件 。。。 允许失真 在不影响“质量”的情况下 基本概念 无损压缩(Lossless Compression)是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同。 有损压缩(Lossy Compression)是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。 数据压缩技术的分类 统计编码中“熵”的基本概念 熵(Entropy) 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。 某个事件的信息量用 表示 ， 其中pi为第i个事件的概率，0 pi ≤ 1 。 信源s的熵的定义：按照香农(Shannon)的理论，信源s的熵定义为 其中： pi 为 si 在 s 中出现的概率， 表示包含在 si 中的信息量，也就是编码所需要的位数，例如，一幅用256级灰度表示的图像，如果每一个象素点灰度的概率均为 pi = 1/256，编码每一个象素点就需要8位 。 常用的压缩方法 统计编码 图像 。。。 预测编码 音频 。。。 变换编码 图像 。。。 混合编码 标准 霍夫曼编码Huffman Encoding System 霍夫曼(Huffman)在1952年提出的一种编码方法，即从下到上的编码方法。该方法根据待编码信息的统计特征(熵)，先按出现频率的大小从下到上构建编码树；然后按类似于前序(后序)遍历的方法赋予树的每条边一个码值，“0”或“1”；最后探索根到叶结点，根到叶所经历边码的序列即为该字符的“码值”。 霍夫曼编码分为定长编码和变长编码两种。后者的应用比较广泛。此外，霍夫曼编码自含同步码，码串中不需要另加标记。 编码算法 主要步骤 (可变长编码) 统计各字符出现的频率 根据贪心策略构建编码树 按类似于前序遍历的方法递归地遍历编码树，对于连接左子树的边赋予边码为“0”，连接右树的边码为“1”。反过来亦可。 即算从“根”到“叶”的边码序列，得到某字符的编码。 编码方法 Huffman编码举例 霍夫曼编码小结 霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码(自含同步码，在编码之后的码串中都不须要另外添加标记符号)。 例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。 如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码 采用霍夫曼编码时有两个问题值得注意： 霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪仅是