算术编码示例
编码来自1个4-符号信源{a1, a2, a3, a4}的由5个符号组成 的符号序列：b1b2b3b4b5 = a1a2a3a3a4
信源符号 概率 0.2 0.2 0.4 0.2 初始子区间 [0 , 0.2] [0.2 , 0.4] [0.4 , 0.8] [0.8 , 1.0]
a1 a2
解码过程
0.068
(1)0.068 在区间[0 ,0.2] ，可知第一个源符号为a1 (2) (3) (4) (5)
0.068 0 0.34 0.2
30 10 20 40 20 40 0 20
20 20 30 30 20 40 40 20
霍夫曼编码的特点：
(1) 霍夫曼编码构造出来的编码值不是唯一的。（在编码时， 可以大概率为’1’，小概率为’0’，也可相反） (2) 当图像灰度值分布很不均匀时，霍夫曼编码的效率就高， 反之，编码效率低。 (3) 霍夫曼编码必须先计算出图像数据的概率特性形成编码 后，才能对数据进行编码，必须通过查表方法建立对应关 系。
6.1 概述 6.1.1 图像数据压缩的必要性与可能性 数据压缩的研究内容包括数据的表示、传输、 变换和编码方法，目的是减少存储数据所需的空 间和传输所用的时间。 图像编码与压缩就是对图像数据按一定的规 则进行变换和组合，达到以尽可能少的代码（符 号）来表示尽可能多的图像信息。
6.1.2 图像的数据冗余
霍夫曼编码 费诺.仙侬编码 行程编码 算术编码
预测编码 变换编码 其它编码
6.2 图像保真度准则
描述解码图像相对原始图像偏离程度的测度一般称为 保真度。常用的保真度准则可分为两大类：客观保真度准 则和主观保真度准则。 6.2.1 客观保真度准则 最常用的客观保真度准则是原图像和解码图像之间的 均方根误差和均方根信噪比两种。 6.2.2 主观保真度准则 很多解压图最终是供人观看的，一种常用的方法是让 一组（不少于20人）观察者观察图像并给该图像评分，将 他们对该图像的评分取平均，作为这幅图像的质量。
W w1 , w2 , w3 , w4 , w5 , w6
霍夫曼编码算法基于一种称为“编码树”（coding tree） 的技术。算法步骤如下： （1）初始化，根据符号概率的大小按由大到小顺序对符号 进行排序。 （2）把概率最小的两个符号组成一个新符号（节点），即 新符号的概率等于这两个符号概率之和。 （3）重复第2步，直到形成一个符号为止（树），其概率 最后等于1。 （4）从编码树的根开始回溯到原始的符号，并将每一下分 枝赋值为1，上分枝赋值为0。 在上述工作完毕之后，从最后两个概率开始逐步向前 进行编码。对于概率大的消息赋予0，小的赋予1。
a3
a4
a1a2a3a3a4
a1 [0,0.2]
a1a2
StartN=Start+but×L EndN=Start+top×L
[0.2*0.2, 0.2*0.4 ]=[0.04, 0.08]
a1a2a3
a1a2a3a3
[0.04+0.04*0.4, 0.04+0.04*0.8 ]=[0.056, 0.072]
s6
S5
1101
s7
S6
1110
S0
00
S1
01
S2
100
S3
101
S7
1111
6.3.4 算术编码
使用霍夫曼编码方式进行编码时，很多 时候不能得到最佳的压缩效果。 与前述的变长编码不同，算术编码生 的是非块码。算术编码给整个信源符号序 列分配一个单一的算术码字。这个码字本 身定义了一个介于0和1之间的实数间隔。
• 费诺.仙侬编码与Huffman编码相反，采用从上到 下的方法。香农-范诺编码算法步骤： • （1）按照符号出现的概率减少的顺序将待编码的 符号排成序列。 • （2）将符号分成两组，使这两组符号概率和相等 或几乎相等。 • （3）将第一组赋值为0，第二组赋值为1。
• （4）对每一组，重复步骤2的操作。
图象质量非常好，如同人能想象出的最好质量。 图象质量高，观看舒服，有干扰但不影响观看。 图象质量可接受，有干扰但不太影响观看。 图象质量差，干扰有些妨碍观看，观察者希望改进。 图象质量很差，妨碍观看的干扰始终存在，几乎无法观看。 图象质量极差，不能使用。
6.2.3 图像冗余度和编码效率
根据Shannon无干扰信息保持编码定理，若对原始 图像数据的信息进行无失真图像编码，压缩后平均码 长存在一个下限，这个下限是图像信息熵H。理论上最 佳信息保持编码的平均码长可以无限接近图像信息熵H。 但总是大于或等于图像的熵H。信息熵定义：
霍夫曼码 01 10 11 001 0001 00000 000010 000011
b3
b4
b5 b6 b7 b8
1100 00000 1101 00001 1110 00010 1111 00011 2.73 2.73
11001 000001 2.78 2.75
熵 平均长度
2.65 2.7
6.3.2费诺.仙侬编码（Fano-Shannon）
1/8
11 111 S1 00 0 S4 11 111
110 10
30 10 20 40
霍夫曼编码举例二
20 40 0
20
20 20 30 30 20 40 40 20
(1)统计出每级灰度出现的频率：
灰度值 出现频率 20 7/16
1
40 4/16
30 3/16
10 1/16
0 1/16
1
9/16 7/16 5/16 4/16 2/16 3/16
• 霍夫曼编码举例一 • 输入数据流:S1 S2 S1 S3 S2 S1 S1 S4
符号 S1 S2 S3 S4
出现概率
等长编码 霍夫曼 数据流源 等长编码 霍夫曼 S1 00 0
1/2
00 0 S2 01 10
1/4
01 10 S1 00 0 S3 10
1/8
10 110 S2 01 S1 00 0
数字化后的图像信息数据量非常大，图像压缩 利用图像数据存在冗余信息，去掉这些冗余信息 后可以有效压缩图像。常见图像的冗余类型主要 表现在： 1）空间冗余 2）视觉冗余（心理视觉冗余） 3）编码冗余 与灰度布的概率特性有关
减少/消除其中的一种/多种冗余，就能取得数 据压缩的效果
11.5.1 位平面的分解
ቤተ መጻሕፍቲ ባይዱ
块号 第一块
信源符号
b1 b2
概率 0.25 0.21 0.19 0.16 0.08 0.06 0.03 0.02
截断霍夫曼码 01 10 000 001 01 10 11 001
平移霍夫曼码 01 10 000 001 1101 1110 11000 01 10 11 001 00001 00010 00011
S6 0.05
S7 0.04
s0,s1,s2,s3,s4,s5,s6,s7
1 0.22 1 0.13 1 0 0.09 1
s0,s1
0 1 0
s2,s3,s4,s5,s6,s7 s1
0
s0
s2,s3 s2 s3
s4,s5,s6,s7 s4,s5
0 1 0
s6,s7
1
s4
灰度值 香浓-范诺码
s5
S4
1100
例：设一副灰度级为8的图象中，各灰度所对应的概率分别为0.04，0.05， 0.06，0.07，0.10，0.10，0.18，0.40，现在对其进行二分法费诺.仙侬编码？
灰度值 出现频率 S0 0.40 S1 0.18
0.58 0 0.20
S2 0.10
0.42
S3 0.10
S4 0.07
S5 0.06
H pi log 2 pi
i 0
L 1
平均码长定义 B
i

i 0
L 1
i
pi
是灰度值为i的编码长度，pi为灰度值为 i 的概率
冗余度为
B r 1 H
H 1 编码效率为 B 1 r
6.3 统计编码方法
6.3.1 霍夫曼编码 Huffman编码是1952年由Huffman提出的一种编码方法。 这种编码方法是根据信源数据符号发生的概率进行编码的。 思想：在信源数据中出现概率越大的符号，编码以后相应 的码长越短；出现概率越小的符号，其码长越长。 （理论最佳）。 设输入编码为 ，其频率分 布分别为P(x1)=0.4 X x2)=0.3，P(x35 , x6 ，P(x 1 , x2 , x3 , x4 , x )=0.1，P(x4) =0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼编码
[0.056+0.016*0.4, 0.056+0.016*0.8 ]=[0.0624, 0.0688]
a1a2a3a3a4
编码序列 b 1= a 1 1 a4 a3 a2 0 a1
[0.0624+0.0064*0.8, 0.056+0.0064*1 ]=[0.06752, 0.0688]
b2= a 2 0.2 a4 a3 a2 0 a1 0.04 b3 = a 3 0.08 a4 a3 a2 a1 0.056 b4 = a 3 0.072 a4 a3 a2 a1 0.062 4 b 5= a4 0.068 8 0.067 52 a4 a3 a2 a1
1. 客观保真度准则
（归一化）信噪比：令
1 f MN
M 1 N 1 x 0 y 0

f ( x, y )
M 1 N 1 2 f ( x, y ) f 单位：分贝（dB） x 0 y 0 SNR 10 lg M 1 N 1 ˆ f ( x, y ) f ( x, y ) x 0 y 0