文档介绍：多媒体信息的数据压缩
第一页，共46页。
多媒体数据的冗余类型
图像数据表示中存在着大量的冗
余，图像数据压缩技术就是利用图像
数据的冗余性来减少图像数据量的方
法。常见图像数据冗余类型如下：
1. 空间冗余
大量时间，而且保存一份概率表也使压缩后的文件增大了不少。所以，在实际应用中，“静态统计模型”应用的很少。
第十页，共46页。
真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。自适应模型可以说是一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。
第十一页，共46页。
编码
通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。
最先被考虑的问题是，如果对 a 用 3 个二进制位就可以表示，而对 b 用 4 个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是 a，哪四个位是 b 呢？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成。看一下前缀编码的一个最简单的例子
第十二页，共46页。
符号 编码 A 0
B 10
C 110
D 1110
E 11110
有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：
11100101011101********** - DABBDCEAAB
第十三页，共46页。
无损压缩
无损压缩常用在原始数据的存档，
如文本数据、程序以及珍贵的图片和图
像等。
其原理是统计压缩数据中的冗余
(重复的数据)部分。常用的有：
RLE (run length encoding)行程编码
Huffman 编码
算术编码
LZW (lempel-ziv-welch)编码
第十四页，共46页。
Shannon-Fano 编码 讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息( 40 个字符长 ): cabcedeacacdeddaaabaababaaabbacdebaceada 五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。 Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：
第十五页，共46页。
Shannon-Fano 编码 进入 Huffman 先生构造的神奇二叉树之前，我们先来看一下它的前身，由 Claude Shannon 和 两人提出的 Shannon-Fano 编码。 讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字符的信息( 40 个字符长 ): cabcedeacacdeddaaabaababaaabbacdebaceada 五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。 Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：
第十六页，共46页。
1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：
a - 16
b - 7
c - 6
d - 6
e - 5
2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：
a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1。
4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：