四川大学 计算机学院 陈 虎 huchen@scu.edu.cn 多媒体技术基础 四川大学 计算机学院 陈 虎 huchen@scu.edu.cn.

Presentation on theme: "四川大学 计算机学院 陈 虎 huchen@scu.edu.cn 多媒体技术基础 四川大学 计算机学院 陈 虎 huchen@scu.edu.cn."— Presentation transcript:

1 四川大学 计算机学院 陈 虎 huchen@scu.edu.cn
多媒体技术基础 四川大学 计算机学院 陈 虎

2 数字化原理 1

3 模拟信号 模拟信号指幅度的取值是连续的（幅值可由无限个数值表示）。 现实中涉及的许多媒体对象是模拟信号 例如：声音、图像、视频等

4 数字信号 数字信号是人为抽象出来的在时间上的不连续信号，是离散时间信号的数字化表示，通常由模拟信号获得。
计算机处理的对象是数字信号（二进制数 “0” 和 “1” ） 例如：英文字符以的 ASCII 代码，汉字字符的国标 GB 代码表示都是二进制数字串

5 多媒体系统的数模与模数转换 传感器 A/D 计算机（数字） 输出设备 输出设备 D/A (声音、图像、视频等--模拟） （数字）
（声音、电视--等模拟） D/A

6 模数转换-采样 概念： 从连续时间信号中提取离散样本的过程；或者说在某些离散的时间点上提取连续时间信号值的过程称为采样。
采样按采样间隔可分为:均匀采样与非均匀采样。

7 采样的必要性 采样是连续时间信号和离散时间信号之间的桥梁，对连续信号而言，随着数字处理技术的发展，越来越迫切地要求连续信号的离散化。
例如，电影的连续画面，实际上是由一组时间样本快速播放实现的，数字通信系统，微处理器系统对连续时间信号的处理，都是通过采样来实现的。

8 采样示例

9 采样 当取出的样本一样时，样本对应的连续时间函数却不是唯一的。

10 采样 此外，对同一个连续时间信号，当采样间隔不同时也会得到不同的样本序列。
结论：没有任何条件限制的情况下，从连续时间信号采样所得到的样本序列，不能唯一地确定原来的连续时间信号，即：一个连续时间信号必须在某一种条件下才能由其样本来表示。

11 采样分析 采样函数： 采样样本：

12 采样分析 原连续时间信号： 采样函数频谱： 已采样信号的频谱：

13 采样分析 对连续时间信号在时域理想采样，就相当于在频域以采样频率s为周期延拓，幅值减小1/T。要使频谱不混迭，就必须使信号带限，且
上述即为时域采样的约束条件 从而我们得到怎样抽取样本，样本才能唯一地表征原信号的取样条件，下面为上述分析的一个完整总结－－采样定理。

14 采样定理 设 是某一个带限信号，在||> M时，X（j）=0。如果采样频率  s>2  M ，其中 s ＝2/T, 那么 就唯一地由其样本 所确定。 已知这些样本值，我们能用如下办法重建：让采样后的信号通过一个增益为T, 截止频率大于M，而小于（ s  M）的理想滤波器，该滤波器的输出就是 。 2  M称为奈奎斯特率 ；  M称为奈奎斯特频率。

15 2 数据压缩

16 压缩的必要性 音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。
例如：一幅中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为0.9MB/帧，若要达到每秒25帧的全动态显示要求，每秒所需的数据量约为22MB。对于声音也是如此，CD音质的声音每秒将有约为172KB的数据量。

17 信息论 1948年 C.E.Shannon 香农 发表了题为“通信的数学理论”的论文。
运用通信技术与概率论、随机过程、数理统计的方法系统讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论： 1.阐明通信系统传递的对象就是信息 2.对信息给予科学的定量描述 3.提出了信息熵的概念

18 信息论科学体系 香农信息论 压缩理论 传输理论 保密理论 有噪声 网络信道 有失真信源编码 无失真信源编码 保密系统的 信息理论
信道编码理论 率失真理论 网络信息理论 等长编码 定理 变长编码 定理 最优码构成 Huffman码 Fano码 码构成 网络最佳码 压缩编码 保密码 纠错码 代数编码 卷积码

19 信息论之父 The Father of Information Theory—— Claude Elwood Shannon
Born: 30 April 1916 in Gaylord, Michigan, USA Died: 24 Feb 2001 in Medford, Massachusetts, USA

20 熵 定义： 设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x) x∈X，则该随机变量的取值不确定程度，即其熵为： 当使用log2时，熵的单位为比特 反映一个信源发出不同信号，具有的平均信息量。

21 熵

22 为什么能够进行压缩 信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度（信息熵冗余）。

23 冗余的基本概念 指信息存在的各种性质的多余度 举例： （1）广播员读文稿时每分钟约读180字，一个汉字占两个 字节；文本数据量为360B；
（2）如果对语音录音，由于人说话的音频范围为20Hz到 4kHz，即语音的带宽为4kHz，若设量化位数为8bit,则一秒钟 的数据量为： 4×2×8=64kbit/s= 8KB/s 则一分钟的数据是480KB。 360B KB

24 数据冗余的类别 空间冗余 时间冗余 统计冗余 信息熵冗余 结构冗余 知识冗余 视觉冗余 听觉冗余

25 数据冗余的类别 规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数据冗余。
●空间冗余 规则物体和规则背景的表面物理特性都具有相关性，数字化后表现为数据冗余。 ●时间冗余 序列图像（如电视图像和运动图像）和语音数据的前后有着很强的相关性，经常包含着冗余。在播出该序列图像时，时间发生了推移，但若干幅画面的同一部位没有变化，变化的只是其中某些地方，这就形成了时间冗余。

26 数据冗余的类别 空间冗余和时间冗余是把图像信号看作概率信号时反应出的统计特性，因此，这两种冗余也被称为统计冗余。
●统计冗余 空间冗余和时间冗余是把图像信号看作概率信号时反应出的统计特性，因此，这两种冗余也被称为统计冗余。 ●信息熵冗余 信息熵实际情况又称编码冗余。信息熵是指一组数所 携带的信息量。 ●结构冗余 数字化图像中的物体表面纹理等结构往往存在着冗余

27 数据冗余的类别 人类的视觉系统对于图像场的注意在非均匀和非线性的，视觉系统并不是对图像的任何变化都能感知。
●知识冗余 由图像的记录方式与人对图像的知识差异所产生的冗余称为知识冗余。 ●视觉冗余 人类的视觉系统对于图像场的注意在非均匀和非线性的，视觉系统并不是对图像的任何变化都能感知。 ●听觉冗余 人耳对不同频率的声音的敏感性是不同的，并不能察觉所有频率的变化，对某些频率不必特别关注，因此存在听觉冗余。

28 信息冗余 从信息论关系中图像信息中冗余信息，如果一个图像的灰度级编码，使用了多于实际需要的编码符号，则该图像包含了信息冗余
例：如果用8位表示下面图像的像素，我们就说该图像存在着编码冗余，因为该图像的像素只有两个灰度，用一位即可表示。

29 统计冗余 从统计的观点，某点像素的灰度与其邻域灰度有密切关系。因此任何给定的像素值，原理上都可以通过它的相邻像素预测到，单个像素携带的信息相对是小的。对于一个图像，很多单个像素对视觉的贡献是冗余的。 例：原图像数据： 压缩后数据：

30 空间冗余 规则物体表面有相关性， 数字化后表现出冗余。 图像相邻像素之间色彩、 明度相同或相似，产生信息 （有意义的内容）冗余

31 时间冗余 时间发生了推移，若干幅画面的同一部位没有变化，于是产生了冗余

32 结构冗余 数字化图像中具有 规则纹理的表面产生的 冗余。 取其中一块编码， 其余只记录坐标

33 视觉心理冗余 一些信息在一般视觉的处理中比其它信息的相对重要程度要小，可以忽略不计，这种信息就被称为视觉心理冗余。 33K 15K

34 数据压缩的评价-压缩比 设：n1和n2是输入数据和输出数据 压缩比为：CR = n1 / n2 例如：图像 512×480， 24位
输入＝(512×480×24)/8=737280B 输出15000B 压缩比＝737280/15000＝49 相对数据冗余： RD = 1 – 1/CR=(n1-n2)/n2

35 数据压缩的评价-压缩质量 客观质量评价：压缩过程对信息的损失能够表示为原始信息与压缩并解压缩后信息的函数。（信噪比（SNR）） 例如，图像中

36 数据压缩的评价-压缩质量 主观质量评价： 以人的主观感受作为评价标准。
例如：通过视觉比较两个图像，给出一个定性的评价，如很粗、粗、稍粗、相同、稍好、较好、很好等，可以对所有人的感觉评分计算平均感觉分来衡量。 评分 评价 说明 1 优秀的 优秀的具有极高质量的图像 2 好的 是可供观赏的高质量的图像，干扰并不令人讨厌 3 可通过的 图像质量可以接受，干扰不讨厌 4 边缘的 图像质量较低，希望能加以改善，干扰有些讨厌 5 劣等的 图像质量很差，尚能观看，干扰显著地令人讨厌 6 不能用 图像质量非常之差，无法观看

37 压缩解压缩速度 算法复杂 － 压缩解压慢，压缩效果好 算法简单 － 压缩解压快，压缩效果差
在许多应用中，压缩和解压可能不同时用，在不同的位置不同的系统中。所以，压缩、解压速度分别估计。 例如静态图像中，压缩速度没有解压速度严格；动态图像中，压缩、解压速度都有要求，因为需实时地从摄像机或其他设备中抓取动态视频。

38 压缩编码的分类 数据压缩(data compression) 与信号编码(signal coding)往往含义相同
解压缩/还原/重构(decompress) 编码(encode/coding) 解码/译码(decode) 相关学科：信息论、数学、信号处理、数据压缩、编码理论和方法

39 压缩编码的分类 编码压缩的方法目前有很多，其分类方法根据出发点不同而有差异。一般根据根据解码后数据与原始数据是否完全一致将编码压缩分为： 无损压缩编码 有损压缩编码

40 压缩编码的分类 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。 有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。图像、声音

41 压缩编码的分类 行程编码 LZW编码 哈夫曼编码 算术编码 无损压缩 无损预测编码 位平面编码 K-L变换 Haar变换
有损压缩 无损压缩 行程编码 LZW编码 哈夫曼编码 算术编码 无损预测编码 位平面编码 有损预测编码 分形编码 模型编码 子带编码 神经网络编码 变换编码 K-L变换 Haar变换 Walsh.Hadamard变换 离散余弦变换 离散傅立叶变换 斜变换 小波变换

42 压缩编码的分类 从信息语义角度分为：熵编码、源编码和混合编码
熵编码(entropy encoding)（也称平均信息量编码） 熵编码是一种泛指那些不考虑被压缩信息的性质的无损编码。它是基于平均信息量的技术把所有的数据当作比特序列，而不根据压缩信息的类型优化压缩。也就是说，平均信息量编码忽略被压缩信息的语义内容。如RLE（run length encoding行程编码）、LZW（Lempel-Ziv-Walch 基于词典的编码算法）、Huffman编码。

43 压缩编码的分类 源编码(Source Coding)
源编码的冗余压缩取决于初始信号的类型、前后的相关性、信号的语义内容等。源编码比严格的平均信息量编码的压缩率更高。当然压缩的程度主要取决于数据的语义内容，比起平均信息量编码，它的压缩比更大。简而言之，利用信号原数据在时间域和频率域中的相关性和冗余进行压缩的有语义编码。如： 预测编码：DM、ADPCM 变换编码：DCT、DWT 分层编码：如子采样、子带编码 其他编码：如矢量量化、运动补偿、音感编码

44 压缩编码的分类 混合编码(hybrid coding) 混合编码= 熵编码 + 源编码
大多数压缩标准都采用混合编码的方法进行数据压缩，一般是先利用信源编码进行有损压缩，再利用熵编码做进一步的无损压缩。如H.261、H.263、JPEG、MPEG等。

45 压缩编码的分类 此外，也可根据不同的依据对数据的压缩算法 进行其它不同的分类，如： 按作用域在空间域或频率域：空间方法、变换方法、混合方法
按是否自适应：自适应性编码和非适应性（静态）编码 按码长：定长码和变长码

46 香农-范诺 香农-范诺编码(Shannon–Fano coding) 在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量
在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)” 。“位”是1948年Shannon首次使用的术语。 最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon- Fano)编码法

47 香农-范诺编码举例 有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1 (1) 计算该图像可能获得的压缩比的理论值 (2) 对5个符号进行编码 (3) 计算该图像可能获得的压缩比的实际值 符号 A B C D E 出现的次数 15 7 6 5 出现的概率 15/40 7/40 6/40 5/40

48 香农-范诺编码举例 理论值 按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，…，100表示E，其余3个代码 (101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为

49 香农-范诺编码举例 这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.84≈1.37:1，实际上就是3:2.196≈1.37

50 香农-范诺编码举例 (2) 符号编码 对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，然后使用递归方法分成两个部分，每一部分具有近似相同的次数

51 香农-范诺编码举例 （3）压缩比的实际值 按照这种方法进行编码需要的总位数为 ＝91，实际的压缩比为120:91≈1.32 : 1

52 霍夫曼编码 霍夫曼编码(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法
根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中

53 霍夫曼编码 基本原理 通过减少编码冗余来达到压缩的目的。 统计符号的出现概率，建立一个概率统计表 将最常出现(概率大的)的符号用最短的编码，
最少出现的符号用最长的编码。

54 霍夫曼编码 具体步骤： 步骤①：按照符号出现概率大小的顺序对符号进行排序 步骤②：把概率最小的两个符号组成一个节点P1
步骤③：重复步骤②，得到节点P2，P3，P4，……， PN，形成一棵树，其中的PN称为根节点 步骤④：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要 步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码

55 aaaa bbb cc d eeeee fffffff 4 3 2 1 5 7
霍夫曼编码举例 aaaa bbb cc d eeeee fffffff （共22*8=176 bits)

56 霍夫曼编码举例 e a b c 编码形式不唯一 d f f=00 e=10 a=11 b=011 c=0100 d=0101
7/22 13/22 1 f 9/22 1 e 5/22 1 22/22 a 4/22 3/22 6/22 1 b 3/22 1 2/22 c 编码形式不唯一 1/22 d f=00 e=10 a=11 b= c= d=0101 4/22)*log2(22/4)+(3/22)*log2(22/3)+(2/22)*log2(22/2)+(1/22)*log2(22/1)+(7/22)*log2(22/7)+(5/22)*log2(22/5)＝2.3678

57 霍夫曼编码举例 aaaa bbb cc d eeeee fffffff （共22*8=176 bits) 4 3 2 1 5 7
经过Huffman编码之后的数据为： (共 7*2+5*2+4*2+3*3+2*4+1*4=53 bits)

58 霍夫曼编码 码字 码长 0.39 1 a a a a a a a 1 1 1.00 1 0.61 0.26 1 平均码长： 熵：2.58

59 霍夫曼编码局限性 利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限。
输入符号数受限于可实现的码表尺寸 译码复杂 需要实现知道输入符号集的概率分布 没有错误保护功能

60 应用举例 在图像的编码中 首先计算频率并以二叉树方式进行排序来获得编码值，其次用编码值取代图像数据进入图像文件中。 编码值的不唯一性
灰度分布很不均匀和很均匀时的效率 构造性差 常用的且有效的方法是： 将图像分割成若干的小块，对每块进行独立的Huffman编码。例如：分成 8×8 的子块，就可以大大降低不同灰度值的个数（最多是64而不是256）。

61 应用举例 8*8分块的编码效率为47.27% 16*16分块的编码效率约为61% 全图的编码效率为91.47%

62 霍夫曼编码 Huffman编码讨论 Huffman编码是唯一可译码。短的码不会成为更长码的启始部分； Huffman编码的平均码长接近于熵
缺点：需要多次排序，耗费时间

63 算术编码 Huffman 编码的局限性： Huffman 编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 位编码，但 Huffman 编码一定会为其分配一位0或一位1的编码。可以想象，整个信息的 80% 在压缩后都几乎相当于理想长度的3倍左右。

64 算术编码 例1： 在信源的符号数目很小的情况 X: a b P(X): H = 0.469 a b 1 a=0, b=1

65 算术编码 例2：信源的符号的概率严重不对称：
A = {a, b, c}, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03 H = bits/symbol Huffman编码： a 0 b 11 c 10 l = 1.05 bits/symbol 冗余（Redundancy） = l - H = bits/sym (213%!)

66 算术编码 基本思想： 考虑对两个字母序列而不是单个字母编码 l = 1.222/2 = 0.611
Letter Probability Code aa 0.9025 ab 0.0190 111 ac 0.0285 100 ba 1101 bb 0.0004 110011 bc 0.0006 110001 ca 101 cb 110010 cc 0.0009 110000 l = 1.222/2 = 0.611 冗余 = bits/symbol （27%）

67 算术编码 该思想还可以继续扩展 理论上：考虑更长的序列能提高编码性能 实际上：
考虑长度为n的所有可能的mn 序列 (已做了32) 理论上：考虑更长的序列能提高编码性能 实际上： 字母表的指数增长将使得这不现实 例如：对长度为3的ASCII序列：2563 = 224 = 16M 需要对长度为n的所有序列产生码本 很多序列的概率可能为0 分布严重不对称是真正的大问题： A = {a, b, c}, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03 H = bits/symbol l1 = 1.05, l2 = 0.611, … 当n = 8时编码性能才变得可接受 但此时|alphabet| = 38 = 6561 !!!

68 算术编码 基本思想：算术编码不是将单个信源符号映射成一个码字，而是把整个消息表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。 采用算术编码每个符号的平均编码长度可以为小数

69 算术编码 符号串编码：将串中使用的符号表按原编码（如字符的ASCII编码、数字的二进制编码）从小到大顺序排列成表。计算表中每种符号si出现的概率pi，然后依次根据这些符号概率大小pi来确定其在[0, 1)期间中对应的小区间范围[xi, yi)： 其中，p0 = 0，显然，符号si所对应的小区间的宽度就是其概率pi

70 算术编码 输入串编码：设串中第j个符号cj为符号表中的第i个符号si，则可根据si在符号表中所对应区间的上下限xi和yi，来计算编码区间
Ij = [lj,rj)。 其中，dj = rj - lj为区间Ij的宽度，初值l0 = 0，r0 = 1，d0 = 1。显然，lj↑而dj与rj↓。 串的最后一个符号所对应区间的下限ln就是该符号串的算术编码值.

71 算术编码 通常，对任意序列x = x1x2…xn 只需知道信源的cdf，即信源的概率模型
只需知道信源的cdf，即信源的概率模型 算术编码：编码和解码过程都只涉及算术运算（加、减、乘、除）

72 举例2 字符 概率 a 0.3 b 0.7 要编的字符串 aba

73 算术编码 1.划分范围 a b 1 0.3 a [0,0.3) b [0.3,1) 2.开始编码 “aba”
0.3 a [0,0.3) b [0.3,1) 2.开始编码 “aba” 第一个为a，编码范围限制在0～0.3范围内 a b 1 0.3

74 算术编码 对已知区间进行再次分割 a b 1 0.3 a b 0.3 0.09 第二个为b，编码范围限制在0.09～0.3范围内 a b
0.3 a b 0.3 0.09 第二个为b，编码范围限制在0.09～0.3范围内 a b 0.3 0.09

75 算术编码 对已知区间进行再次分割 a b 0.3 0.09 a b 0.09 0.153 0.3 第3个为a，编码范围限制在[0.09,0.153)范围内 a b 0.09 0.3 0.153

76 算术编码 在[0.09,0.153) 中任选一个浮点数来标识这个区间，如0.15，即可表示我们要编的消息为“aba”
把该浮点数转变为二进制编码: 0010 特性： 区间越窄，说明符号串越长，二进制码长越长

77 举例2 假设信源符号为{00, 01, 10, 11}，它们的 概率分别为{ 0.1, 0.4, 0.2, 0.3 }
对二进制消息序列 … 进行算术编码

78 算术编码 初始化：根据信源符号的概率把间隔[0, 1)分成如表2- 4所示的4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)。其中[x, y)的表示半开放间隔， 即包含x不包含y，x称为低边界或左边界，y 称为高边界或右边界 符号 00 01 10 11 概率 0.1 0.4 0.2 0.3 初始区间 [0, 0.1) [0.1, 0.5) [0.5, 0.7) [0.7, 1)

79 算术编码 确定符号的编码范围 编码时输入第1个符号是10，找到它的编码范围是 [0.5, 0.7]
消息中第2个符号00的编码范围是[0, 0.1)，它的间隔 就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52) 编码第3个符号11时，取新间隔为[0.514, 0.52) 编码第4个符号00时，取新间隔为[0.514, ) 依此类推…… 消息的编码输出可以是最后一个间隔中的任意数

80 算术编码

81 算术编码

82 算术编码

83 算术编码

84 算术编码 长度为n的序列的算术编码的平均码长为： 算术编码的效率高：当信源符号序列很长，平均码长接近信源的熵

85 算术编码 在算术编码中需要注意的问题： 由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。 算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。 算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。

86 算术编码 算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改。 开发动态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。

87 带缩放的算术编码 编码器： 解码器 一旦我们到达1. 或2.，就可以忽略[0,1)的另一半 还需要告知解码器标识所在的半区间：
发送0/1 比特用来指示下上界所在区间 将标识区间缩放到[0, 1): E1: [0, 0.5) => [0, 1); E1(x) = 2x E2: [0. 5,1) => [0, 1); E2(x) = 2(x-0.5) 注意：在缩放过程中我们丢失了最高位 但这不成问题—我们已经发送出去了 解码器 根据0/1比特并相应缩放 与编码器保持同步

88 带缩放的算术编码 考虑随机变量X(ai) = i 对序列1 3 2 1编码： Input: -321 Input: 1321
Input: 1321 Output: Input: -321 Output: 1

89 带缩放的算术编码 Input: --21 Output: 11 Input: ---1 Output: 1100 Input: ---1
Input: --21 Output: 11 Input: ---1 Output: 1100 Input: ---1 Output: 110 Input: ---1 Output: 11000

90 带缩放的算术编码 假设码字长为6 0.1100012 = 0.76562510 第1位：1 输入：110001100000
Output: 1 Input: ( ) Input: Output: 132 Output: 13 Input: (左移) Input: (左移) Input: (左移)

91 带缩放的算术编码 此时解码最后一个符号 Input: -----100000 Input: ----01100000 (左移)
Output: 1321 Input: (左移)

92 语义依赖 应用背景： 对于“局部冗余”的特殊类型。 主要应用于图象表达、处理。 原因： 数字化的image有大量的“局部冗余” 占空间大
（一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。）

93 语义依赖 典型： 行程编码（run-length encoding:RLE） 差异映射(difference mapping)
词典编码(Dictionary Encoding)

94 语义依赖 差异映射： 算法思想： 例[Laeser et al.1986]
图象表示为相邻像素在亮度/颜色上的差异阵列，而不是像素本身的亮度/颜色值 例[Laeser et al.1986] 8 bits/pixel (256 brightness)3 bits/pixel

95 语义依赖 词典编码 词典： 编码方法： 全部词语（words） 常用词语+词语结束符号 指向词典的指针表
指向词典的指针表（常用词语）+编码（不常用词语）

96 分解与编码 源信息代码（长度）： block -> block block -> variable
variable -> block variable -> variable

97 例：“aa bbb cccc ddddd eeeeee fffffffgggggggg”
block -> block (120) Source massage codeword a b c d e f g space

98 variable -> variable (30)
分解与编码 例："aa bbb cccc ddddd eeeeee fffffffgggggggg” variable -> variable (30) Source massage codeword aa 0 bbb 1 ccccc 10 ddddd 11 eeeeeee 100 fffffff gggggggg 110 space

99 分解与编码 “定义字”与“自由分解”方法 定义字（defined-word）方式 自由分解（free-parse）方式
源信息分解的长度在编码调用之前已确定 自由分解（free-parse）方式 编码算法本身决定源信息分解的长度（变长）

100 分解与编码 典型算法 定义字方式的： 自由分解方式的： Shannon-Fano coding Huffman coding
Universal codes (通用码) Arithmetic coding (算术编码) 自由分解方式的： Lempel-Ziv codes Algorithm BSTW

101 行程编码（RLE） 基本原理： 它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。

102 行程编码（RLE） 行程编码(RLE）算法:
x1, x2, …… xn ---->( c1 ,l1 ), ( c2,l2 ), …… ( ck,lk ) ci: 亮度/颜色 li :第i行程（相同亮度/颜色的像素的序列）的长度 不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以；或者存储一个象素的颜色值，以及具有相同颜色值的行数。 具有相同颜色并且是连续的象素数目称为行程长度。

103 行程编码（RLE） 例： 代码字为： （0，8),（1，3),（8，50),（1，4),(0，8）

104 行程编码（RLE） RLE所能获得的压缩比——主要是取决于图像本身的特点。 RLE是无损压缩技术。
如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。 RLE是无损压缩技术。

105 行程编码（RLE） 应用： 尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。（对颜色丰富的自然图像不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。） 商业数据处理（如连续多个0，空格）

106 行程编码（RLE） 特点： 利用两个字节代替连续出现的同一数据。通常需要在表示重复次数的字节中利用前一位或两位作为标志位，提示应用程序中随后的极为表示次数，另一字节表示重复数据的值。 举例说明： aaaa bbb cc d eeeee fffffff (共22*8=176 bits) 4a3b2c1d5e7f (共12*8=96 bits)

107 BMP行程编码 BI_RLE8的编码方式： 由2个字节组成，第一个字节指定使用相同颜色的象素数目，第二个字节指定使用的颜色索引。此外，这个字节对中的第一个字节可设置为0，联合使用第二个字节的值表示： 第二个字节的值为0：行的结束。 第二个字节的值为1：图象结束。 第二个字节的值为2：其后的两个字节表示下一个象素从当前开始的水平和垂直位置的偏移量。

108 BMP行程编码 例如： E0001 这些压缩数据可解释为： 从当前位置右移5个位置后向下移一行 行结束 091E 1E1E1E1E1E1E1E1E1E 编码图象结束

109 PCX行程编码 PCX简介：真彩色图像以行为单位，按色面存放 128字节的文件头 图像数据 调色板

110 PCX行程编码 图像数据以字节为单位进行编码 按行进行压缩 长度在前，灰度值在后 单像素没有长度值
以最高两位作为判断是重复数还是原像素。 最高两位为1（B0除外），说明是重复数，否则，说明是原像素值

111 PCX行程编码 重复像素长度iC最大值为26-1 = 63，如果遇到iC大于63的情况，则分为小于63的几段，分别处理。
如果P < 0xC0（192） 直接存入该像素值， 否则先存入长度1，再存入像素值 （ 之间的单像素图像不减反增）

112 PCX行程编码 例 0X15····0X15 0X5A 0X67 0X5F 0X71 0X69 11
0X35····0X35 0XD7 0XD9 0XCC 80 [0XCB 0X15]0X5A 0X67 0X5F 0X71 0X69 [0XFF 0X35][0XD1 0X35][0XC1 0XD7][0XC1 0XD9][0XC1 0XCC]

113 行程编码（RLE） 对于有大面积色块的图像，压缩效果很好
对于纷杂的图像，压缩效果不好，最坏情况下（图像中每两个相邻点的颜色都不同 ），会使数据量加倍，所以现在单纯采用行程编码的压缩算法用得并不多

114 二维行程编码 二维行程编码要解决的核心问题是：将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码
两种典型的二维行程编码的排列方式

115 二维行程编码 数据量：64*8=512(bit)

116 二维行程编码 如果按照方式(a)扫描的顺序排列的话，数据分布为：
130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127

117 二维行程编码 行程编码为： 数据量：43*（3+8）=473(bit) (94.22%)
（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），（1，127），（1，129），（1，131），（1，130），（1，132），（2，134），（2，133），（1，132），（1，130），（1，129），（1，128），（1，127），（1，128），（1，127），（1，128），（1，127），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，131），（1，129），（2，130），（1，129），（3，130），（1，129），（1，130），（2，132），（2，131），（1，130），（1，126），（2，128），（2，127） 数据量：43*（3+8）=473(bit) (94.22%)

118 比特平面编码 思想： 对于灰度或彩色图像，如果每个像素用k位表示，将相同位上的0，1取出，就可以形成k个N*N的二值图像。将每一个二值图像称为一个比特平面。 希望连续的0/1出现的概率增大.

119 比特平面编码

120 二值图像压缩标准 静止图像（still images）包括两类： 黑白（二值）静止图像 连续色调（彩色或灰度）静止图像。
二值图像压缩方法主要用于不包含任何连续色调信息的文档，或者连续色调信息(大多数为图片)可以用黑白的模式来获取的应用。例如办公／商业文档，手写文本、线条图形、工程图等。

121 二值图像压缩标准 二值图像压缩的标准： 3 类（CCITT Group 3）数字传真标准 4类（CCITT Group 4）数字传真标准
JBIG（Joint Bi-level Image experts Group，二值图像联合专家组）标准

122 二值图像压缩标准 G3和G4－由CCITT国家电话电报咨询委员会(consultative committee of the international telephone and telegraph)的两个小组(Group3和Group4)负责制定的，最初为传真应用而设计 （1）G3采用一维行程长度编码； （2）行程采用Huffman编码； （3）0－63之间的行程，用单个码字即终止码表示； （4）大于63的游长用一个形成码和一个终止码组合表示。形成码表示实际行程对64的倍数； （5）G3能达到15：1的压缩比； （6）G4采用二维行程程度编码，压缩比比G3提高30％。

123 二值图像压缩标准 一维压缩 基本思想： 行首：用一个白行程码开始。如果行首是黑像素，则 用零长度的白00110101开始。
一维压缩 基本思想： 1）每一行行首、尾编码 行首：用一个白行程码开始。如果行首是黑像素，则 用零长度的白 开始。 行尾：用行尾编码字(EOL) 结束。 2）图像首、尾编码 图像首行：用一个EOL开始。 图像结尾：用连续6个EOL结束。 3）图像内部编码 内部编码：长度小于63的用哈夫曼编码，大于63的用组合编码：大于63的长度编码 + 小于63的余长度编码

124 二值图像压缩标准 长度小于63的哈夫曼编码 行程长度 白编码 黑编码 0 00110101 0000110111 1 000111 010
行程长度 白编码 黑编码

125 二值图像压缩标准 长度大于63的组合编码 行程长度 白编码 黑编码 64 11011 0000001111
行程长度 白编码 黑编码

126 二值图像压缩标准 b1 b2 a0 a1 a2 二维压缩 1) 基本思想： 利用上一行相同改变元素的位置，来为当前行编码
假设相临两行改变元素位置相似的情况很多 且上一行改变元素距当前行改变元素的距离，小于行程的长度，从而可以降低编码长度 b1 b2 参考行 当前行 a0 a1 a2

127 二值图像压缩标准 b1 b2 a0 a1 a2 2) 定义几个重要符号： 参 考 行：当前处理行的前一行。
参 考 行：当前处理行的前一行。 改变元素：与前一个像素值不同的像素 参考元素：一共有5个（当前行3个，参考行2个）： a0：当前处理行上，与前一个像素值不同的像素。 行首元素是本行的第一个a0 a1：a0右边下一个改变元素。 a2：a1右边下一个改变元素。 b1：参考行上在a0右边，且与a0值相反的改变元素 b2： b1右边下一个改变元素。 b1 b2 参考行 当前行 a0 a1 a2

128 二值图像压缩标准 b1 b2 a0 a1 a2 3) 编码方法：对三种情况的三种编码方式： （1）通过编码方式：
编码：0001， 动作：把a0移到b2的下面 b1 b2 新a0 a0 a1 a2

129 二值图像压缩标准 a1 b1 b1 b2 a0 a1 a2 3) 编码方法：对三种情况的三种编码方式： （2）水平编码方式：
编码：001+M(a0a1)+M(a1a2) ， M：一维行程编码 动作：把a0移到a2。 a1 b1 b1 b2 a0 a1 a2

130 二值图像压缩标准 b1 b2 a0 a1 a2 3）编码方法：对三种情况的三种编码方式： （3）垂直编码方式：
条件：a1到b1之间的距离小于等于3，利用上一行编码。 编码：见CCITT二维编码表（下页） 动作：把a0移到a1 a1b1 b1 b2 a0 a1 a2

131 二值图像压缩标准 4) CCITT二维编码表 a1与b1的距离 编码： a1在b1下面： 1 a1在b1右边1个 001

132 二值图像压缩标准 CCITT Group3 基本思想： Group3标准应用了一种非适应的，一维和二维混合的行程编码技术
在该编码中，每一个K行组的最后K-1行（K = 2或4），有选择地用二维编码方式。

133 二值图像压缩标准 CCITT Group4 基本思想： Group4标准是Group3标准简化或改进版本
只用二维压缩编码。且为非适应二维编码方法 每一个新图像的第一行的参考行是一个虚拟的白行

134 二值图像压缩标准 JBIG是“二值图像联合专家组（Joint Bi-level Image experts Group）”的简称。它建立于1988年，是一个由国际标准实体和主要公司提名产生的专家组，致力于制订二值图像编码标准。 “联合”指的是他们同时为ISO、IEC和ITU-T制订标准。JBIG的正式名称，在ISO和IEC叫ISO/IEC JTC1 SC29 第一工作组，在ITU-T，则称为ITU-T SG8。 JBIG和JPEG一同工作，同时为JPEG和JBIG制订标准。人们常常将他们制订的这两种标准分别简称为JPEG标准和JBIG标准，或直接称为JPEG和JBIG。

135 二值图像压缩标准 JBIG1在性能上有很大提高 JBIG1结合了预测建模、自适应和无损编码等技术
选择算术编码作为数字压缩的基础，能够适应所遇到的图像统计概率。 用细化网格里的黑色像素密度代表灰度，因为人眼的分辨能力很有限，人的视觉系统会把这些小点平滑地联起来。 对计算机生成的图像。JBIG1采用干净自然的图像边缘来改善性能。

136 二值图像压缩标准 缺省的传输模式是顺序模式
在顺序模式中，全分辨率图像ID从左边进入，图像经过一连串的降低分辨率达到ID-1，…，I0。最低分辨率的水平称为底层，所有的高一点的分辨率水平称为差分层。描述底层的信息最先发送，然后是逐步向上的差分层信息。除非接收到信号中止这个过程，这样一直到全分辨率。

137 无损预测编码 预测编码： 数字图像或者音频按照行或列从新排列后可以得到一个一位信号序列。预测编码就是根据这个信号序列的一些已知情况来预测以后信号可能发生的情况，然后对预测的误差进行编码而不是直接对信号进行。当预测比较准确、误差较小是，这种编码方式就能达到数据压缩的目的。

138 无损预测编码 基本思想 图像相邻像素间存在很强的相关性，通过观察其相邻像素取值，可预测一像素的大概情况。
预测值和实际值存在误差，称为预测误差。 预测误差的方差必然比原图像像素的方差小，因此对预测误差编码必然压缩其平均码长。 对预测误差进行编码的技术称为DPCM（差分脉冲编码调制）。

139 无损预测编码

140 无损预测编码

141 无损预测编码 预测误差的熵 对比一幅图像和其差分图像的标准差和熵。 不同图像的差分图像直方图分布形态大致相同，只是方差有所不同。

142 无损预测编码 预测方程式 线性预测： 如果ai是常数，则为时不变线性预测，否则为自适应线性预测（ADPCM） 最简单的预测方程：

143 无损预测编码 预测器 整数 舍入 符号编 码器 符号解 S 源数据 压缩数据 恢复数据 预测误差, en fn f^n en + + -

144 无损预测编码 为实现无失真编码，通常对差分进行熵编码（通常是Huffman编码）；
预测误差熵编码的步骤：建立码表和编码。通常采用一个通用码表，节省建立专用码表时间，由此带来压缩比损失较小； 编码：若对差分所有灰度建立码表，则项数较多。通常对－16~16采用Huffman编码，其他直接用前缀＋实际灰度值。

145 无损预测编码 一副数字图像或一段音频可以看成一个空间点阵，图像信号不仅在水平方向是相关的，在垂直方向也是相关的。根据已知样值与待预测样值间的位置关系，可以分为： （1）一维预测（行内预测）：利用同一行上相邻的样值进行预测。 （2）二维预测（帧内预测）：利用同一行和前面几行的数据进行预测。 （3）三维预测（帧间预测）：利用相邻几帧（或不同波段）上的取样值进行预测

146 无损预测编码 举例：公式： 中取： m = 2，a1 = a2 = 1/2
举例：公式： 中取： m = 2，a1 = a2 = 1/2 f = {154,159,151,149,139,121,112,109,129} 预测值 f2 = 1/2 * ( )  e2 = 151 – 156 = -5 f3 = 1/2 * ( ) = e3 = 149 – 155 = -6 f4 = 1/2 * ( ) = e4 = 139 – 150 = -11 f5 = 1/2 * ( ) = e5 = 121 – 144 = -23 f6 = 1/2 * ( ) = e6 = 112 – 130 = -18 f7 = 1/2 * ( )  e7 = 109 – 116 = -7 f8 = 1/2 * ( )  e8 = 129 – 110 = 19

147 无损预测编码 这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。 c b d a x 三邻域预测法
选择值 预测值 非预测 1 a 2 b 3 c 4 a+b-c 5 a+(b-c)/2 6 b+(a-c)/2 7 (a+b)/2 c b d a x 三邻域预测法 这种压缩算法被应用到JPEG标准的无损压缩模式之中，中等复杂程度的图像压缩比可达到2:1。

148 无损预测编码 视频信号的冗余度主要体现在空间相关性（帧内）、时间相关性（帧间）和色度空间表示上的相关性。
对于每秒30帧的视频信号，其相继帧之间存在极强的相关性。据统计256级灰度的黑白图像序列，帧间差值超过3的象素数不超过4％。所以在活动图像序列中可以利用前面的帧来预测后面的帧，以实现数据压缩。 帧间预测编码技术被广泛应用到H.261、H.263、MPEG-1和MPEG-2等视频压缩标准之中。

149 无损预测编码 - 运动补偿预测将前一个画面的数值作为后一个画面的预测值。 编码器 运动 补偿 图像输入 运动矢量输出 译码器 帧 缓存 估计
预测误差输出

150 无损预测编码

151 无损预测编码

152 无损预测编码

153 无损预测编码

154 无损预测编码

155 无损预测编码

156 无损预测编码

157 词典编码 文本中的词用它在词典中表示位置的号码代替的一种无损数据压缩方法。
采用静态词典编码技术时，编码器需要事先构造词典，解码器要事先知道词典。 采用动态辞典编码技术时, 编码器将从被压缩的文 本中自动导出词典，解码器解码时边解码边构造解码词典。

158 词典编码 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余

159 第一类编码算法 第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。

160 LZ77算法 LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。

161 LZ77算法 1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符，即不匹配的第一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。 3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 1 个字符，继续步骤 1。

162 LZ77算法

163 LZ77算法 A B C 步骤 位置 匹配串 输出 1 －－ 0, 0, A 2 A 1, 1, B 3 4 0, 0, C 5 B

164 LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符

165 LZSS算法 1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len >= MIN_LENGTH），则进行步骤 2，否则进行步骤 3。 2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。 3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。

166 LZSS算法 输入数据流： 1 2 3 4 5 6 7 8 9 10 11 A B C 编码过程 MIN_LEN =2 步骤 位置 匹配串
字符 A B C 步骤 位置 匹配串 输出 1 －－ A 2 3 B 4 5 C 6 BB （3，2） 7 8 AAB （7，3） 11 编码过程 MIN_LEN =2

167 LZSS算法 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。

168 第二类词典编码 第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。

169 LZ78算法 LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。

170 LZ78算法 步骤1：将词典和当前前缀P都初始化为空。 步骤2：当前字符C:=字符流中的下一个字符。 步骤3：判断P＋C是否在词典中
（1）如果“是”，则用C扩展P，即让P:=P＋C，返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W和当前字符C， 即（W，C）； 将P＋C添加到词典中； 令P:=空值，并返回到步骤2

171 LZ78算法 输入数据流： 1 2 3 4 5 6 7 8 9 A B C 编码过程： 步骤 位置 词典 输出 1 A (0, A) 2 B
字符 A B C 编码过程： 步骤 位置 词典 输出 1 A (0, A) 2 B (0, B) 3 BC (2, C) 4 5 BCA (3, A) 8 BA (2, A)

172 LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章。在他们的研究基础上，Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。 在编码原理上，LZW与LZ78相比有如下差别： LZW只输出代表词典中的字符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符。即在编码匹配时，至少可以在词典中找到长度为1的匹配串。 LZW编码是围绕称为词典的转换表来完成的。

173 LZW算法 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(String)。

174 LZW算法 步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。 步骤2：当前字符C:=字符流中的下一个字符。
（1）如果“是”，则用C扩展P，即让P:=P＋C，返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W； 将P＋C添加到词典中； 令P:=C，并返回到步骤2

175 LZW算法 1 2 3 4 5 6 7 8 9 A B C 输入数据流： 位置 字符 步骤 位置 码字 词典 输出 1 A 2 B 3 C
BB 6 BA 7 ABA 8 ABAC －

176 LZW算法 LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式、TIFF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。 LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。

177 GIF 例子：GIF和TIFF都使用LZW压缩法。下面以GIF为例进行介绍： 1）GIF简介（多图像、256色） 文件结构：
屏幕描述 ：屏幕长、宽、背景色等 全局调色板：长度（256x3）//三个256色的调色板

178 GIF 图 象 描 述： 描述图像块在屏幕上的左上角位置及宽高 文件头信息 屏幕描述 局部调色板:
长度（256x3）//三个256色的调色板，每个图像可有一个 图像数据： 用LZW方式压缩，用256字节的块来 存放 扩充块描述：有四种扩充块 文件头信息 LZW压缩图像数据 全局调色板 屏幕描述 图像描述 局部调色板 扩充数据块

179 GIF 初始化字典 输出清除标记 LZW_CLEAR Temp = 空串 k = 从输入流中读一个字符 是结尾标志吗？ 输出结束标记
Temp = Temp+k 输出结束标记

180 GIF 编码举例：设字符集{a,b,c,d}， 串：aabdaadaa 压缩字典 临时串 输入串 编码 0 a T=temp + a
压缩字典 临时串 输入串 编码 a T=temp + a b T= a + a c T= a + b d T= b + d aa T= d + a ab T= a + a bd T= aa + d da T= d + a aad T= da + a daa T= a

181 通用码(universal codes) 通用码： 优点： 平均码长≤ c1H + c2 当c1=1，为渐近最优码
不需精确的概率值，只需要概率次序排列 代码字集合固定，编码、译码简单

182 通用码(universal codes) 基本思想： 应用： 概率递减—— >代码长度递增 通用静态编码方法（代替Huffman 码）
动态方法的辅助编码方法

183 (Apostolico & Fraenkel [1985])
通用码(universal codes) 二类通用码： Elias codes (Elias [1975]) γ code δ code Fibonacci codes (Apostolico & Fraenkel [1985])

184 Elias codes γ code 编码方法： 整数x ∟ log x ｣个0，后跟x的二进制值。 δ code 编码方法：

185 Elias codes γ δ 1 2 010 0100 3 011 0101 4 00100 01100 5 00101 01101 6 00110 01110 7 00111 01111 8 16 17 32

186 Elias codes(码长=161) 例：“aa bbb cccc ddddd eeeeee fffffffgggggggg”
Source message frequency rank Codeword(δ) g 8 1 f 7 2 0100 e 6 3 0101 d 5 4 01100 ◇ 01101 c 01110 b 01111 a

187 2阶Fibonacci数 (Fi : i =0,1,2,…):
Fibonacci codes m阶Fibonacci数定义: F-m+1 ~ F0 =1; Fk =前m个 F之和；（k≥1） 2阶Fibonacci数 (Fi : i =0,1,2,…): 1，1，2，3，5，8，13，21,……

188 N  R(N) = ∑ik=0 di Fi (di 为0 或 1，k≤N)
Fibonacci codes Fibonacci codes编码方法： 整数N  F(N) N  R(N) = ∑ik=0 di Fi (di 为0 或 1，k≤N) Fibonacci数定义 2阶Fibonacci数 (Fi : i =0,1,2,…): 1，2，3，5，8，13，21,…… D = d0 d1 d2 …… dk F(N) = D1 (D后跟1)

189 Fibonacci codes N R(N) F(N) 1 11 2 1 0 011 3 1 0 0 0011 4 1 0 1 1011 5
00011 6 10011 7 01011 8 000011 16 32

190 Fibonacci codes (码长=153) 例：“aa bbb cccc ddddd eeeeee fffffffgggggggg”
Source message frequency rank Codeword(F) g 8 1 F(1)=11 f 7 2 F(2)= 011 e 6 3 F(3)= 0011 d 5 4 F(4)= 1011 ◇ F(5)= 00011 c F(6)= 10011 b F(7)= 01011 a F(8)=

191 Fibonacci codes 2阶Fibonacci编码中每个数N的编码连续出现1的个数不超过2个。
用同样的方法，可以得到m阶Fibonacci编码，其中，每个数N的编码连续出现1的个数不超过m个。 Fibonacci编码是一种变长编码，它便于字符的异步传输，并且能提高字符传输的正确率。更重要的是，相对于二进制的整数编码方案，Fibonacci编码可以用比较少的位来表示前面几个数，用更多的位来表示大于34的数，因为34的Fibonacci编码为 ，共9位。

192 BSTW编码（algorithm BSTW)
Bentley,Sleator,Tarjan,and Wei[1986] ——动态自适应方法 局部性：一段时间频繁出现，而后长时间不出现 算法基本思想： 以一个依据字符出现构成的“自组织线性表”（self-organizing list)为辅助数据结构，表前面的字符以较短代码字表示。

193 BSTW编码（algorithm BSTW)
算法实现： “自组织线性表”采用“move-to-front” （移动到最前面）策略维护； 字符在“自组织线性表”的位置，映射成以Elias codes编码的代码字。

194 BSTW编码（algorithm BSTW)
“move-to-front” 策略： 表初始为空； 如果当前字符ai在表中，则传ai的当前位置序号；然后修改表，将ai移到表的第1位，表中其余字符顺序后移一位； 如果当前字符ai不在表中，则传位置序号k+1(当前表长为k)，后跟字符ai本身编码；然后修改表，将ai放到表的第1位，表中其余字符顺序后移一位；

195 BSTW编码（algorithm BSTW)
例1：“abcadeabfd” 结果： 1 a 2 b 3 c 3 4 d 5 e f 5

196 BSTW编码（algorithm BSTW)
例2：“aa bbb cccc ddddd eeeeee fffffffgggggggg” 结果： 1 a 1 2 ◇ 3 b c d e f g 以Elias code δ 做表位置映射，每个字符3 位（a-g 和◇ ），码长=81

197 BSTW编码（algorithm BSTW)
评价： 只需读一遍源信息 码长接近静态Huffman码（never much larger than ） 局部自适应