2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
1
7.5算术编码算术编码 (Arithmetic Coding) 的 概 念 最 早 由
J.Rissanen在 1976年引入,与 Huffman编码不同,算术编码是一种有记忆非分组编码方法,它用某个实数区间来表示若干被编码的信息,用该实数区间对应的二进制码作为编码输出 。 算术码的编码过程,实际上就是依据字符的发生概率对码区间的分割过程,我们举例说明算术编码的原理 。
设 信 源 符 号 集 为 {a,b,c,d},其 概 率 分 布 为
{0.2,0.2,0.4,0.2}。
（ 1） 若对该信源进行 Huffman编码,可得其平均码长为 L=2.0bit/字符 。
（ 2） 若信源发出序列 {b,c,a,b,d},算术编码过程如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
各数据符号在半封闭实数区间 ［ 0,1)内按概率进行赋值范围设定为
a=[0.0,0.2),b=[0.2,0.4),c=[0.4,0.8),d=[0.8,1.0)
第一个信源符号为,b”,取值区间变为 [0.2,0.4)。
第二个信源符号,c”,对取值区间 [0.2,0.4)进行划分找出对应于,c”的区间,计算新的取值区间范围 。
起始值 =取值区间左端
+取值区间长度 × 当前符号的赋值区间左端结束值 =取值区间左端
+取值区间长度 × 当前符号的赋值区间右端计算得出新的取值区间为
[0.2+0.2× 0.4,0.2+0.2× 0.8)= [0.28,0.36)
依次类推,第三个符符号,a”,编码后的取值区间为
[0.28,0.296)。 最终划分结果见下表 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
至此,信源序列 {bcabd}已被映射为一个实数区间
[0.28576,0.2864),或者说在 [0.28576,0.2864)内的任何一个实数均代表该序列 。
例子消息,BILL GATES”会有一个如下的概率分布：
字符 概率空格 1/10
A 1/10
B 1/10
E 1/10
G 1/10
I 1/10
L 2/10
S 1/10
T 1/10
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
用到的九个字符的符号集给出数值范围如下：
字符 概率 范围空格 1/10 0.00≤r ＜ 0.10
A 1/10 0.10≤r ＜ 0.20
B 1/10 0.20≤r ＜ 0.30
E 1/10 0.30≤r ＜ 0.40
G 1/10 0.40≤r ＜ 0.50
I 1/10 0.50≤r ＜ 0.60
L 2/10 0.60≤r ＜ 0.80
S 1/10 0.80≤r ＜ 0.90
T 1/10 0.90≤r ＜ 1.00
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
每个字符都赋值成 0到 1范围内与之出现概率相关联的那部分 。
算术编码的消息的最高有效部分属于第一个符号一或者说在消息,BILL GATES”中的 B。 为了正确地译码第一个字符,最终编码后的消息必须是一个大于等于 0.20并且小于 0.30的数值 。 要编码成这个数值,
寻找它可能在的范围,在编码第一个字符后,这个范围的底限是 0.20,并且高限是 0.30。 编码过程的剩余部分中,每个新符号将进一步限制输出数值的可能范围,下一个将要编码的字符,字母 I,拥有新的子范围
0.2到 0.3中的范围 0.50到 0.60。 使用上面的计算公式,
执行这个过程而产生的结论如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
新字符 低值 高值
0.0 1.0
B 0.20 0.30
I 0.25 0.26
L 0.256 0.258
L 0.2572 0.2576
空格 0.25720 0.25724
G 0.257216 0.257220
A O.2572164 0.2572168
T O.25721676 0.2572168
E O.257216772 0.257216776
S 0.2572167752 0.2572167756
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
这样,最终的低值 2572167752将用于唯一地编码消息,BILL GATES”。 在译码过程中,通过查看哪一个符号拥有编码的消息所在的空间,就可以找到消息中的第一个符号,由于 0.2572167752在 2到 3之间,所以第一个字符必须是 B,之后,从要编码的数值中删掉 B,因为我们知道,B范围的上下限,所以通过把它放入过程的逆过程可以消除它的影响 。 首先减去 B的低值,得到 0572167752；之后除以 B范围的宽度,即
0.1,得到值 0.572167752；再后,计算下一个字母的范围,字母 I,依此类推,可以译出其他字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
“BILL GATES”消息的译码进行情况如下：
编码了的数 输出符号 低限 高限 范围
O.2572167752 B 0.2 0.3 0.1
0.572167752 I 0.5 0.6 0.1
0.72167752 L 0.6 0.8 0.2
0.6083876 L 0.6 0.8 0.2
0.041938 空格 O.O O.1 0.1
0.41938 G 0.4 0.5 0.1
0.1938 A O.1 0.2 0.1
0.938 T 0.9 1.0 0.1
0.38 E O.3 0.4 0.1
O.8 S 0.8 0.9 0.1
0.O
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
总之,编码过程只是用每个新符号来缩小可能数值的范围 。 新范围是与相应于该符号的预定义的概率成正比的 。
译码是反过程,范围扩展是与每个被抽取的符号的概率成正比的 。
算术编码的最大优点之一在于它具有自适应性和高编码效率,当信源符号概率比较接近时,使用算术编码效果较好,因为此时霍夫曼编码的结果趋于定长码,效率不高 。
事实上,JPEG小组测试过,对于许多实际图像,算术编码的压缩效果优于霍夫曼编码 5%～ 10%。 在 JPEG的扩展系统中,已经用算术编码取代霍夫曼编码 。 但在实际上,算术编码要比霍夫曼编码复杂,特别是硬件实现 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
根据对各类图像的统计分析,发现图像信源中像素的空域相关性比较强 。 在经过采样和量化形成数字彩色图像后,其相邻像素的相关性体现在相邻像素亮度取值变化不大 。 对于黑白文本图像,其像素取值只有两种可能,非黑即白 。 对典型黑白文本图像进行分析发现,前－像素为白色像素时,当前像素取值为白的条件概率 P(W/W)平均都在 97%以上,而由白像素变为黑像素的概率 P(B/W)仅为 3%；
类似地,前一像素为黑像素,当前像素为黑的条件概率 P(B/B)平均为 75%,而黑像素变白像素的概率
P(W/B)为 25%。 可以看出相邻像素之间存在很强的相关性 。
7.6 游 程编码（ Run-length Encoding,RLE ）
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
不难想象,在两值文本图像所形成的数据流中,必然存在多个像素同时黑 (或白 )的情况,表现在数据上即为数据流中某一符号连续多次重复 。 如果我们对重复出现的字符,字符连续重复的个数以及起始位置进行编码,就能恢复该字符串 。 RLE(游程长度编码 )就是用二进制码字表示上述信息的编码方式 。 RLE的基本数据结构如下图所示 。
其中,游程标志,主要用于表明在该位置处有重复字符串 。
从上图可知,一个 RLE基本数据占用 3字节,即只有当重复字符串长度大于 24(即连续有 24个像素取值相同 )时,才有数据压缩效益 。 因此在编码时,先要判断游程长度,再决定是否使用 RLE；而在译码时需要判断前一个字符是否为
,游程标志,,再来决定字符的含义 。
游程标志 重复字符 游程长度
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
游程编码（ RLE）从根本上说仍是通过去除图像像素间的相关性达到数据压缩的目的。游程编码不仅仅只利用一个相邻像素的信息，它实际上利用了图像多个像素间的相关性。将游程编码应用于二值文本图像的压缩，
结合 Huffman编码，对不同游程长度的黑长和白长按其经验概率分布进行最佳编码，取得了很好的效果，在实际运用中受到广泛的运用。游程编码已成为 CCITT的系列文件压缩编码标准中数字传真机压缩编码标准的一个重要组成部分。二值文本图像游程编码分为一维 MH编码和二维 MR编码。一维 MH编码在每一个扫描行内进行，
它只利用了扫描图像在水平方向上的相关性。但其编码效率高（据统计平均编码效率达到 86.9%）、差错灵敏度低，易于扩展且基本上适合中文文本传真，被 CCITT
推荐作为文件传真三类机的压缩国际标准。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
二维 MRC是在一维 MH编码方案的基础上进一步考虑了像素在垂直方向上的相关性，并且只对少量的五种关键迁移像素（由黑变白或由白变黑的第一个像素）进行编码，进一步提高了图像压缩比，被推荐作为第四类传真机的压缩标准。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
7.7 LZW编码方法
7.7.1 基于字典的压缩方法使用统计模型来编码单个符号 。 它们通过将符号编码成比原符号使用更少位数的位串来达到压缩的目的 。 压缩质量的好坏依赖于统计模型的好坏 。 模型不仅精确地预言符号的概率,
而且所预言的概率必须脱离均匀值,脱离得越大,所获得的压缩越好 。
但基于字典的压缩方法使用完全不同的方法来压缩数据 。
这种方法并不是将单个符号编码成可变长度的位串,而是将可变长度的符号串编码成一个单个的单词,该单词形成短语字典的一个索引 。 如果单词小于它所替代的短语,则产生了压缩 。
在许多方面,基于字典的压缩方法更容易为人们所理解,它代表了程序员所熟悉的一种方法一 -在数据库中用索引来检索大量的存储 。 在日常生活中,我们使用电话号码,和邮政编码将较长的正文串编码 。 这正是一个基于字典的编码器实质上所做的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
7.7.2 LZ78算法
Ziv和 Lempel开发了－个基于字典的压缩算法 。 这个算法广泛地称作 LZ78,发表在 1978 年 9 月,IEEE
Transactions on Information Theory,上,论文的题目为,Compressing of Individual Sequence via
Variable-Rate Coding”（ 通过可变比率编码压缩单个序列 ） 。
使用 LZ78算法时,编码器和译码器都是从一个几乎为空的字典开始的 。 通过定义,字典有一个单个的已编码字符串一空字符串 （ null）,随着每个字符的读入,
将这些字符增加到当前字符串中,只要当前字符串匹配字典中的某个短语,这一过程就继续反复执行 。 到最后,
该字符串再也没有字典中的一个相应的短话了,此时,
LZ78输出一个单词和一个字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
编码过程中，字符串直到最后一个字符读入之前，在字典中是一直有着一个匹配短语的，因此，
当前字符串定义成加入一个新的字符的最后的匹配字符串，这就是 LZ78所输出的：前一个匹配的索引和结束匹配的字符。编码过程中，新短语不断入到字典中，这个短语的下一次出现，就可以用它来建立更长的短语。
下面给出一个例子,输入的文本是一个字符串 。
LZ78在字典中没有短语的情况下开始编码；因此,
从输入文本中读入的第一个字符,D”建立了在字符中没有匹配的字符串,之后编码器还输出一个短语 /
字符对,0和 D,字典是以定义成空短语的 0（ null）
开始的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
输入文本：,DAD DADA DADDY DADO …”
输出短语 输出字符 编码后的字典项 字典项序号
0,D”,D” 1
0,A”,A” 2
1,?,,D?,3
1,A”,DA” 4
4,?,,DA?,5
4,D”,DAD” 6
1,Y”,DY” 7
0,?,,?,8
6,O”,DADO” 9
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
在编码中,输出短语中用,0”表示此新字典项没有利用其他的字典项,其他的数字表示此新字典项利用了哪个其他已经建立的字典项 。 输出字符为建立新字典项时加入的字符 。
经过编码器的头两个字符,D和 A是以前未出现的,每个字符都将编码成一个短语 0+字符的对,字符 D加入到字典中作为短语 1,字符 A作为短语 2。
当第三个字符 D读入时,它匹配一个已存在的字典短语 。,,字符是下一个读入的字符,由于在字典中没有匹配,它建立了一个新的短语,D,。
LZ78为前面的匹配 (D字符串 )将输出代码 1,之后是
,” 字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
随着编码的继续,字典很快建立起－些相当长的短语。
当然,由于这些来自字典的词条是按字母顺序排序的,
建立短语的速度要比一般的情况快,仅仅读入并编码
17个字符之后,字典的情况如下所示：
0,(null)”
1,D”
2,A”
3,D?,
4,DA”
5,DA?,
6,DAD”
7,DY”
8,?,
9,DADO”
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
7.7.3 LZ78实现
LZ78可以人为地设置短语字典的大小,但实际计算时,必须考虑输出单词中为短语代码而申请的位数,同时也必须考虑管理字典要占用多少 CPU时间 。
从理论上看,随着字典大小的增加,LZ78应该压缩得更好,但这一点也只有在输入的文本长度趋于无限时才有可能 。
LZ78的真正困难之处是对字典的管理 。 例如,
如果为短语索引使用 16位代码,则可以容纳 65536
个短语,其中包括空代码 （ null） 。 代码可以在长度上有很大的变化,包括由单个字符重复不同个数组成的短语,可以有 65536种可能性 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
这些短语通常存贮在－棵多叉树中,树从根结点 0
（ 即空字符串 ） 开始,每个可以加入到空字符串中的可能的字符就是树的一个新分枝,这样建立的每个短语都有一个新结点号 。
使用这样一棵树,存在的一个原字符串与字典的比较是简单的,只要遍历一棵树,为短语中的每个字符遍历树中的单个结点,如果短语终止在一个特殊的结点,则我们得到一个匹配；如果再没有短语了,但我们已到达一个叶结点,则不存在匹配 。 编码符号之后,将它加入到叶给点中也是简单的一 -只不过是增加空间到后继列表,之后在最后匹配的结点处插入一个新的后继结点 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
存在的一个问题是字典的填满 。 不管字典空间有多大,它迟早要填满 。 如果我们使用的是
16位的代码,那么定义 65535个短语之后,字典将填满 。
对于一个填满的字典,可以停止加入新的短语放弃它,重新建立新的字典,也可以继续使用它 。 可以通过监视文件的压缩率来管理满字典问题 。 如果压缩率开始开始下降,则放弃已有字典,否则,继续使用存在的字典,虽然没有加入新的短语 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
,null,
,,,A,,D,
8 2 1
,,,A,,Y,
3 4 7
,,,D,
5 6
,O,
9
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
7.7.4 LZW压缩算法
1984年,Terry Welch在,IEEE Computer,杂志上发表论文,A Technique for High-
Performance Data Compression”（ 高性能数据压缩技术 ）,产生了 LZW压缩技术 。
LZW压缩算法的主要改变是预加载短语字典,
对于字符文本压缩,字典中的单个符号短语与字母表中的符号数相同 。 这样,就不存在不能立即进行编码的符号,即使该符号在输入流中没有出现过 。
下面,给出一个样例来示范算法,假定输入一个字符串,WED WE WEE WEB WET”。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
首先，检查是否字符串,W”在表中，因为它不在表中，所以输出,”代码，并且将字符串
,W”加入到字典中。由于字典已将代码 0到 255
定义成 256个可能的单个字符串，所以加入的第一个字典项赋值为代码 256。第三个字符,E”读入之后，第二个字符串,WE”加入到字典中，并且输出字符,W”的代码。在第二个英文单词中，
字符,”和,W”读入，匹配字符串号码 256，之后代码 256输出，并且－个三字符的字符串加入到字典中，这个过程继续进行，直到字符串终止并且输出了所有代码。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
具体编码过程如下：
输入串：,WED WE WEE WEB WET”
字符输入 代码输出 新字典项和相关串
,? W”,?,256=“? W”
“E”,W” 257=“WE”
“D”,E” 258=“ED”
“?,,D” 259=“D?,
“WE” 256 260=“? WE”
“?,,E” 261=“E?,
“WEE” 260 262=“? WEE”
“? W” 261 263=“E? W”
“EB” 257 264=“WEB”
“?,,B” 265=“B?,
“WET” 260 266=“? WET”
＜ EOP＞ T
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
可以看到,字典项快速地增加,因为－个代码的每一次输出,一个新的字典项就加入 。 在这个例子中,
输出了五个替代代码和七个字符,如果为输出使用 9
位代码,19个字符的输入字符串减少到 13.5个字节的输出字符串 。 当然,这个例子是经过选择用来示范的,
在实际计算时,压缩通常是直到一个相当大的字典建立以后才开始,－般至少是在读入一百个字节左右之后,较大的字典才建立好 。
7.7.5 解压的实现在解压缩时,使用压缩算法的输出代码流,并用它们重新建立压缩算法精确的输入流 。 LZW算法高效的一个原因,是它不必将字典传递给解压器 。 字典可以使用输入流作为数据,在解压缩过程中精确地建立 。
所以被压缩的数据不负担运载－个大字典的任务 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
在解压缩的过程中,每次读入一个新的代码,
它增加一个新的字符串到不断建立的字典中 。 另外,
它将每个新读入的代码译成一个字符串并将它送到输出流中 。
下面是一个例子,给出的输入是由前面的压缩例子产生的 。 最后的字典表与压缩时建立的字典一样,输出字符串与压缩算法的输入字符串相同 。 其中,前 256个代码已经定义为翻译单个字符的字符串,这同压缩代码中的情况一样 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
30
输入代码：,WED＜ 256＞ E＜ 260＞＜ 26l＞＜ 257＞ B＜ 260＞ T”
输入代码 输出代码 字典项
,?,,?,
,W”,W” 256=“? W”
“E”,E” 257=“WE”
“D”,D” 258=“ED”
256,? W” 259=“D?,
“E”,E” 260=“? WE”
260,? WE” 261=“E?,
261,E?,262=“? WEE”
257,WE” 263=“E? W”
“B”,B” 264=“WEB”
260,? WE” 265=“B?,
“T”,T”
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
31
解码时字典项是自动产生的 。 产生的方法是,使用前面的输出字符或字符串,同当前输出的字符或字符串的第 1个字符构成新的字典项,这些字典项可能在后继的解码中用到 。
由于解码已结束,所以编码时字典中的 266=“? WET”
没有产生,但它在解码也并不起作用 。
(C)
1
7.5算术编码算术编码 (Arithmetic Coding) 的 概 念 最 早 由
J.Rissanen在 1976年引入,与 Huffman编码不同,算术编码是一种有记忆非分组编码方法,它用某个实数区间来表示若干被编码的信息,用该实数区间对应的二进制码作为编码输出 。 算术码的编码过程,实际上就是依据字符的发生概率对码区间的分割过程,我们举例说明算术编码的原理 。
设 信 源 符 号 集 为 {a,b,c,d},其 概 率 分 布 为
{0.2,0.2,0.4,0.2}。
（ 1） 若对该信源进行 Huffman编码,可得其平均码长为 L=2.0bit/字符 。
（ 2） 若信源发出序列 {b,c,a,b,d},算术编码过程如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
各数据符号在半封闭实数区间 ［ 0,1)内按概率进行赋值范围设定为
a=[0.0,0.2),b=[0.2,0.4),c=[0.4,0.8),d=[0.8,1.0)
第一个信源符号为,b”,取值区间变为 [0.2,0.4)。
第二个信源符号,c”,对取值区间 [0.2,0.4)进行划分找出对应于,c”的区间,计算新的取值区间范围 。
起始值 =取值区间左端
+取值区间长度 × 当前符号的赋值区间左端结束值 =取值区间左端
+取值区间长度 × 当前符号的赋值区间右端计算得出新的取值区间为
[0.2+0.2× 0.4,0.2+0.2× 0.8)= [0.28,0.36)
依次类推,第三个符符号,a”,编码后的取值区间为
[0.28,0.296)。 最终划分结果见下表 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
至此,信源序列 {bcabd}已被映射为一个实数区间
[0.28576,0.2864),或者说在 [0.28576,0.2864)内的任何一个实数均代表该序列 。
例子消息,BILL GATES”会有一个如下的概率分布：
字符 概率空格 1/10
A 1/10
B 1/10
E 1/10
G 1/10
I 1/10
L 2/10
S 1/10
T 1/10
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
用到的九个字符的符号集给出数值范围如下：
字符 概率 范围空格 1/10 0.00≤r ＜ 0.10
A 1/10 0.10≤r ＜ 0.20
B 1/10 0.20≤r ＜ 0.30
E 1/10 0.30≤r ＜ 0.40
G 1/10 0.40≤r ＜ 0.50
I 1/10 0.50≤r ＜ 0.60
L 2/10 0.60≤r ＜ 0.80
S 1/10 0.80≤r ＜ 0.90
T 1/10 0.90≤r ＜ 1.00
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
每个字符都赋值成 0到 1范围内与之出现概率相关联的那部分 。
算术编码的消息的最高有效部分属于第一个符号一或者说在消息,BILL GATES”中的 B。 为了正确地译码第一个字符,最终编码后的消息必须是一个大于等于 0.20并且小于 0.30的数值 。 要编码成这个数值,
寻找它可能在的范围,在编码第一个字符后,这个范围的底限是 0.20,并且高限是 0.30。 编码过程的剩余部分中,每个新符号将进一步限制输出数值的可能范围,下一个将要编码的字符,字母 I,拥有新的子范围
0.2到 0.3中的范围 0.50到 0.60。 使用上面的计算公式,
执行这个过程而产生的结论如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
新字符 低值 高值
0.0 1.0
B 0.20 0.30
I 0.25 0.26
L 0.256 0.258
L 0.2572 0.2576
空格 0.25720 0.25724
G 0.257216 0.257220
A O.2572164 0.2572168
T O.25721676 0.2572168
E O.257216772 0.257216776
S 0.2572167752 0.2572167756
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
这样,最终的低值 2572167752将用于唯一地编码消息,BILL GATES”。 在译码过程中,通过查看哪一个符号拥有编码的消息所在的空间,就可以找到消息中的第一个符号,由于 0.2572167752在 2到 3之间,所以第一个字符必须是 B,之后,从要编码的数值中删掉 B,因为我们知道,B范围的上下限,所以通过把它放入过程的逆过程可以消除它的影响 。 首先减去 B的低值,得到 0572167752；之后除以 B范围的宽度,即
0.1,得到值 0.572167752；再后,计算下一个字母的范围,字母 I,依此类推,可以译出其他字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
“BILL GATES”消息的译码进行情况如下：
编码了的数 输出符号 低限 高限 范围
O.2572167752 B 0.2 0.3 0.1
0.572167752 I 0.5 0.6 0.1
0.72167752 L 0.6 0.8 0.2
0.6083876 L 0.6 0.8 0.2
0.041938 空格 O.O O.1 0.1
0.41938 G 0.4 0.5 0.1
0.1938 A O.1 0.2 0.1
0.938 T 0.9 1.0 0.1
0.38 E O.3 0.4 0.1
O.8 S 0.8 0.9 0.1
0.O
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
总之,编码过程只是用每个新符号来缩小可能数值的范围 。 新范围是与相应于该符号的预定义的概率成正比的 。
译码是反过程,范围扩展是与每个被抽取的符号的概率成正比的 。
算术编码的最大优点之一在于它具有自适应性和高编码效率,当信源符号概率比较接近时,使用算术编码效果较好,因为此时霍夫曼编码的结果趋于定长码,效率不高 。
事实上,JPEG小组测试过,对于许多实际图像,算术编码的压缩效果优于霍夫曼编码 5%～ 10%。 在 JPEG的扩展系统中,已经用算术编码取代霍夫曼编码 。 但在实际上,算术编码要比霍夫曼编码复杂,特别是硬件实现 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
根据对各类图像的统计分析,发现图像信源中像素的空域相关性比较强 。 在经过采样和量化形成数字彩色图像后,其相邻像素的相关性体现在相邻像素亮度取值变化不大 。 对于黑白文本图像,其像素取值只有两种可能,非黑即白 。 对典型黑白文本图像进行分析发现,前－像素为白色像素时,当前像素取值为白的条件概率 P(W/W)平均都在 97%以上,而由白像素变为黑像素的概率 P(B/W)仅为 3%；
类似地,前一像素为黑像素,当前像素为黑的条件概率 P(B/B)平均为 75%,而黑像素变白像素的概率
P(W/B)为 25%。 可以看出相邻像素之间存在很强的相关性 。
7.6 游 程编码（ Run-length Encoding,RLE ）
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
不难想象,在两值文本图像所形成的数据流中,必然存在多个像素同时黑 (或白 )的情况,表现在数据上即为数据流中某一符号连续多次重复 。 如果我们对重复出现的字符,字符连续重复的个数以及起始位置进行编码,就能恢复该字符串 。 RLE(游程长度编码 )就是用二进制码字表示上述信息的编码方式 。 RLE的基本数据结构如下图所示 。
其中,游程标志,主要用于表明在该位置处有重复字符串 。
从上图可知,一个 RLE基本数据占用 3字节,即只有当重复字符串长度大于 24(即连续有 24个像素取值相同 )时,才有数据压缩效益 。 因此在编码时,先要判断游程长度,再决定是否使用 RLE；而在译码时需要判断前一个字符是否为
,游程标志,,再来决定字符的含义 。
游程标志 重复字符 游程长度
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
游程编码（ RLE）从根本上说仍是通过去除图像像素间的相关性达到数据压缩的目的。游程编码不仅仅只利用一个相邻像素的信息，它实际上利用了图像多个像素间的相关性。将游程编码应用于二值文本图像的压缩，
结合 Huffman编码，对不同游程长度的黑长和白长按其经验概率分布进行最佳编码，取得了很好的效果，在实际运用中受到广泛的运用。游程编码已成为 CCITT的系列文件压缩编码标准中数字传真机压缩编码标准的一个重要组成部分。二值文本图像游程编码分为一维 MH编码和二维 MR编码。一维 MH编码在每一个扫描行内进行，
它只利用了扫描图像在水平方向上的相关性。但其编码效率高（据统计平均编码效率达到 86.9%）、差错灵敏度低，易于扩展且基本上适合中文文本传真，被 CCITT
推荐作为文件传真三类机的压缩国际标准。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
二维 MRC是在一维 MH编码方案的基础上进一步考虑了像素在垂直方向上的相关性，并且只对少量的五种关键迁移像素（由黑变白或由白变黑的第一个像素）进行编码，进一步提高了图像压缩比，被推荐作为第四类传真机的压缩标准。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
7.7 LZW编码方法
7.7.1 基于字典的压缩方法使用统计模型来编码单个符号 。 它们通过将符号编码成比原符号使用更少位数的位串来达到压缩的目的 。 压缩质量的好坏依赖于统计模型的好坏 。 模型不仅精确地预言符号的概率,
而且所预言的概率必须脱离均匀值,脱离得越大,所获得的压缩越好 。
但基于字典的压缩方法使用完全不同的方法来压缩数据 。
这种方法并不是将单个符号编码成可变长度的位串,而是将可变长度的符号串编码成一个单个的单词,该单词形成短语字典的一个索引 。 如果单词小于它所替代的短语,则产生了压缩 。
在许多方面,基于字典的压缩方法更容易为人们所理解,它代表了程序员所熟悉的一种方法一 -在数据库中用索引来检索大量的存储 。 在日常生活中,我们使用电话号码,和邮政编码将较长的正文串编码 。 这正是一个基于字典的编码器实质上所做的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
7.7.2 LZ78算法
Ziv和 Lempel开发了－个基于字典的压缩算法 。 这个算法广泛地称作 LZ78,发表在 1978 年 9 月,IEEE
Transactions on Information Theory,上,论文的题目为,Compressing of Individual Sequence via
Variable-Rate Coding”（ 通过可变比率编码压缩单个序列 ） 。
使用 LZ78算法时,编码器和译码器都是从一个几乎为空的字典开始的 。 通过定义,字典有一个单个的已编码字符串一空字符串 （ null）,随着每个字符的读入,
将这些字符增加到当前字符串中,只要当前字符串匹配字典中的某个短语,这一过程就继续反复执行 。 到最后,
该字符串再也没有字典中的一个相应的短话了,此时,
LZ78输出一个单词和一个字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
编码过程中，字符串直到最后一个字符读入之前，在字典中是一直有着一个匹配短语的，因此，
当前字符串定义成加入一个新的字符的最后的匹配字符串，这就是 LZ78所输出的：前一个匹配的索引和结束匹配的字符。编码过程中，新短语不断入到字典中，这个短语的下一次出现，就可以用它来建立更长的短语。
下面给出一个例子,输入的文本是一个字符串 。
LZ78在字典中没有短语的情况下开始编码；因此,
从输入文本中读入的第一个字符,D”建立了在字符中没有匹配的字符串,之后编码器还输出一个短语 /
字符对,0和 D,字典是以定义成空短语的 0（ null）
开始的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
输入文本：,DAD DADA DADDY DADO …”
输出短语 输出字符 编码后的字典项 字典项序号
0,D”,D” 1
0,A”,A” 2
1,?,,D?,3
1,A”,DA” 4
4,?,,DA?,5
4,D”,DAD” 6
1,Y”,DY” 7
0,?,,?,8
6,O”,DADO” 9
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
在编码中,输出短语中用,0”表示此新字典项没有利用其他的字典项,其他的数字表示此新字典项利用了哪个其他已经建立的字典项 。 输出字符为建立新字典项时加入的字符 。
经过编码器的头两个字符,D和 A是以前未出现的,每个字符都将编码成一个短语 0+字符的对,字符 D加入到字典中作为短语 1,字符 A作为短语 2。
当第三个字符 D读入时,它匹配一个已存在的字典短语 。,,字符是下一个读入的字符,由于在字典中没有匹配,它建立了一个新的短语,D,。
LZ78为前面的匹配 (D字符串 )将输出代码 1,之后是
,” 字符 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
随着编码的继续,字典很快建立起－些相当长的短语。
当然,由于这些来自字典的词条是按字母顺序排序的,
建立短语的速度要比一般的情况快,仅仅读入并编码
17个字符之后,字典的情况如下所示：
0,(null)”
1,D”
2,A”
3,D?,
4,DA”
5,DA?,
6,DAD”
7,DY”
8,?,
9,DADO”
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
7.7.3 LZ78实现
LZ78可以人为地设置短语字典的大小,但实际计算时,必须考虑输出单词中为短语代码而申请的位数,同时也必须考虑管理字典要占用多少 CPU时间 。
从理论上看,随着字典大小的增加,LZ78应该压缩得更好,但这一点也只有在输入的文本长度趋于无限时才有可能 。
LZ78的真正困难之处是对字典的管理 。 例如,
如果为短语索引使用 16位代码,则可以容纳 65536
个短语,其中包括空代码 （ null） 。 代码可以在长度上有很大的变化,包括由单个字符重复不同个数组成的短语,可以有 65536种可能性 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
这些短语通常存贮在－棵多叉树中,树从根结点 0
（ 即空字符串 ） 开始,每个可以加入到空字符串中的可能的字符就是树的一个新分枝,这样建立的每个短语都有一个新结点号 。
使用这样一棵树,存在的一个原字符串与字典的比较是简单的,只要遍历一棵树,为短语中的每个字符遍历树中的单个结点,如果短语终止在一个特殊的结点,则我们得到一个匹配；如果再没有短语了,但我们已到达一个叶结点,则不存在匹配 。 编码符号之后,将它加入到叶给点中也是简单的一 -只不过是增加空间到后继列表,之后在最后匹配的结点处插入一个新的后继结点 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
存在的一个问题是字典的填满 。 不管字典空间有多大,它迟早要填满 。 如果我们使用的是
16位的代码,那么定义 65535个短语之后,字典将填满 。
对于一个填满的字典,可以停止加入新的短语放弃它,重新建立新的字典,也可以继续使用它 。 可以通过监视文件的压缩率来管理满字典问题 。 如果压缩率开始开始下降,则放弃已有字典,否则,继续使用存在的字典,虽然没有加入新的短语 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
,null,
,,,A,,D,
8 2 1
,,,A,,Y,
3 4 7
,,,D,
5 6
,O,
9
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
7.7.4 LZW压缩算法
1984年,Terry Welch在,IEEE Computer,杂志上发表论文,A Technique for High-
Performance Data Compression”（ 高性能数据压缩技术 ）,产生了 LZW压缩技术 。
LZW压缩算法的主要改变是预加载短语字典,
对于字符文本压缩,字典中的单个符号短语与字母表中的符号数相同 。 这样,就不存在不能立即进行编码的符号,即使该符号在输入流中没有出现过 。
下面,给出一个样例来示范算法,假定输入一个字符串,WED WE WEE WEB WET”。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
首先，检查是否字符串,W”在表中，因为它不在表中，所以输出,”代码，并且将字符串
,W”加入到字典中。由于字典已将代码 0到 255
定义成 256个可能的单个字符串，所以加入的第一个字典项赋值为代码 256。第三个字符,E”读入之后，第二个字符串,WE”加入到字典中，并且输出字符,W”的代码。在第二个英文单词中，
字符,”和,W”读入，匹配字符串号码 256，之后代码 256输出，并且－个三字符的字符串加入到字典中，这个过程继续进行，直到字符串终止并且输出了所有代码。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
具体编码过程如下：
输入串：,WED WE WEE WEB WET”
字符输入 代码输出 新字典项和相关串
,? W”,?,256=“? W”
“E”,W” 257=“WE”
“D”,E” 258=“ED”
“?,,D” 259=“D?,
“WE” 256 260=“? WE”
“?,,E” 261=“E?,
“WEE” 260 262=“? WEE”
“? W” 261 263=“E? W”
“EB” 257 264=“WEB”
“?,,B” 265=“B?,
“WET” 260 266=“? WET”
＜ EOP＞ T
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
可以看到,字典项快速地增加,因为－个代码的每一次输出,一个新的字典项就加入 。 在这个例子中,
输出了五个替代代码和七个字符,如果为输出使用 9
位代码,19个字符的输入字符串减少到 13.5个字节的输出字符串 。 当然,这个例子是经过选择用来示范的,
在实际计算时,压缩通常是直到一个相当大的字典建立以后才开始,－般至少是在读入一百个字节左右之后,较大的字典才建立好 。
7.7.5 解压的实现在解压缩时,使用压缩算法的输出代码流,并用它们重新建立压缩算法精确的输入流 。 LZW算法高效的一个原因,是它不必将字典传递给解压器 。 字典可以使用输入流作为数据,在解压缩过程中精确地建立 。
所以被压缩的数据不负担运载－个大字典的任务 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
在解压缩的过程中,每次读入一个新的代码,
它增加一个新的字符串到不断建立的字典中 。 另外,
它将每个新读入的代码译成一个字符串并将它送到输出流中 。
下面是一个例子,给出的输入是由前面的压缩例子产生的 。 最后的字典表与压缩时建立的字典一样,输出字符串与压缩算法的输入字符串相同 。 其中,前 256个代码已经定义为翻译单个字符的字符串,这同压缩代码中的情况一样 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
30
输入代码：,WED＜ 256＞ E＜ 260＞＜ 26l＞＜ 257＞ B＜ 260＞ T”
输入代码 输出代码 字典项
,?,,?,
,W”,W” 256=“? W”
“E”,E” 257=“WE”
“D”,D” 258=“ED”
256,? W” 259=“D?,
“E”,E” 260=“? WE”
260,? WE” 261=“E?,
261,E?,262=“? WEE”
257,WE” 263=“E? W”
“B”,B” 264=“WEB”
260,? WE” 265=“B?,
“T”,T”
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
31
解码时字典项是自动产生的 。 产生的方法是,使用前面的输出字符或字符串,同当前输出的字符或字符串的第 1个字符构成新的字典项,这些字典项可能在后继的解码中用到 。
由于解码已结束,所以编码时字典中的 266=“? WET”
没有产生,但它在解码也并不起作用 。
