第23页
11.2 信息理论基础
两种编码方法：
1、a,b,c,d用码字00,01,10,11来编码
平均码长： l a v 1 / g 2 * 2 1 /4 * 2 1 /8 * 2 1 /8 * 2 2
平均码长大于信源的熵
2、 a,b,c,d分别用码字0,10,110,111来编码
平均码长：la v1 g /2 * 1 1 /4 * 2 1 /8 * 3 1 /8 * 3 1 .75
第11讲
第27页
11.2 信息理论基础
变长编码定理：若一个离散无记忆信源具有熵，并有r个 码元符号集，则总可以找到一种无失真信源编码，构 成单义可译码，使其平均码长满足：
H(X) LH(X)1
logr
logr
当r=2
H (X)LH (X)1
第11讲
第28页
11.2 信息理论基础
3．变长最佳编码定理 在变长编码中，对出现概率大的信息符号赋予
平均码长等于信源的熵
第11讲
第24页
11.2 信息理论基础
设 X{a,b,c,d}
p (a )0 .4,p 5 (b )0 .2,5 p(c)0 .1,8 p(d)0 .12
则，各信源符号自信息量：
I(a) 1.152I,(b)2,I(c)2.473,9I(d)3.0589
信源熵
H ( X ) 0 . 4 * 1 . 1 5 0 . 5 2 * 2 2 5 0 . 1 * 2 . 4 8 0 7 . 1 * 3 . 0 3 2 1 5 9 . 8
0 0
5 10 15 20 25
1 0.8 0.6 0.4 0.2
0 0
5 10 15 20 25
第12页
11.1.1 数据冗余
3. 心理视觉冗余
主观：因人而异，因应用要求而异 其存在与人观察图象的方式有关
眼睛对某些视觉信息更敏感 人对某些视觉信息更关心 心理视觉冗余与实在的视觉信息有联系 （损失不可逆转）
x 0y 0
第11讲
第16页
11.1.2 图象保真度和质量
2. 主观保真度准则
观察者对图象综合评价的平均
电视图象质量评价尺度
评 分 评 价
说明
1 优 秀 图 象 质 量 非 常 好 ， 如 同 人 能 想 象 出 的 最 好 质 量 。
2 良 好 图 象 质 量 高 ， 观 看 舒 服 ， 有 干 扰 但 不 影 响 观 看 。
第11讲
第26页
11.2 信息理论基础
1．香农信息保持编码定理
香农信息论已证明，信源熵是进行无失真编码的理论极限。低于 此极限的无失真编码方法是不存在的，这是熵编码的理论基础。 而且可以证明，考虑像素间的相关性，使用高阶熵一定可以获得 更高的压缩比。
2．变长编码定理
变长编码定义：对于一个无记忆离散信源中每一个符号，若采 用相同长度的不同码字代表相应符号，就叫做等长编码，例如 中国4位电报码。若对信源中的不同符号，用不同长度的码字表 示就叫做不等长或变长编码。
用第二种编码方法 ，平均码长1.85大于信源熵
l a v 0 . g 4 * 1 5 0 .2 * 2 5 0 .1 * 3 8 0 .1 * 3 2 1 .85
第11讲
第25页
11.2 信息理论基础
可得到几点提示：
➢信源的平均码长lavg>=H(X)；也就是说熵是无失真编码的下界。 ➢如果所有I(xk)都是整数，且l(xk)=I(xk),可以使平均码长等于熵。 ➢对非等概率分布的信源，采用不等长编码其平均码长小于等长编 码的平均码长。 ➢如果信源中各符号的出现概率相等，信源熵值达到最大，这就是 重要的最大离散熵定理。
xk的自信息量 I(xk)logp1k logpk
N
信源熵H(X) H(X) pi lo2gpi i1
第11讲
第21页
11.2 信息理论基础
设 X{a,b,c,d}
p ( a ) p ( b ) p ( c ) p ( d ) 1 /4
则，各信源符号自信息量：
I ( a ) I ( b ) I ( c ) I ( d ) lo 2 4 2 g
3 可 用 图 象 质 量 可 接 受 ， 有 干 扰 但 不 太 影 响 观 看 。
4 刚 可 看 图 象 质 量 差 ， 干 扰 有 些 妨 碍 观 看 ， 观 察 者 希 望 改 进 。
5
差 图 象 质 量 很 差 ， 妨 碍 观 看 的 干 扰 始 终 存 在 ， 几 乎 无 法 观 看 。
-- --
89 AC
输出
(1) (2) (2) (4) (7) (3)
第34页
11.3 LZW编码
LZW解码
输出码字值串 1 2 2 4 7 3 解码后的字串 A B B AB ABA C
信息理论基础
– 自信息量、信源熵 – 变长最佳编码定理 LZW编码 图像处理应用实例
第11讲
第31页
11.3 LZW编码
LZW编码示例 图象
字典前256个码字被分配给灰 度值。第257个位置用于下一
0 0 255 255 个出现的灰度值序列。使用一
0 0 255 255 个9比特512个字的字典，将用
短码字，而对于出现概率小的信息符号赋予长码字。 如果码字长度严格按照所对应符号出现概率大小逆 序排列，则编码结果平均码字长度一定小于任何其 他排列形式.
第11讲
第29页
讨论题
鸡蛋表面的污垢检测，假设污垢面积占鸡 蛋表面有一定的百分比，设计一个检测方 法，写出其具体步骤。
第11讲
第30页
上次课程内容回顾
n1和n2代表2个数据集合中的信息载体单位的个数
n1 相 对 于 n2 n1 = n2 n 1 >> n2 n 1 << n2
C R RD 10 1 0
对 应 的 情 况 第 1种 表 达 相 对 第 2种 表 达 不 含 冗 余 数 据 第 1个 数 据 集 合 含 相 当 多 的 冗 余 数 据 第 2个 数 据 集 合 包 括 比 原 始 表 达 多 得 多 的 数 据
则，各信源符号自信息量：
I ( a ) l2 o 2 1 , I g ( b ) l2 o 4 2 , I g ( c ) I ( d ) l2 o 8 3 g
信源熵
H ( X ) 1 / 2 * 1 1 / 4 * 2 1 / 8 * 3 1 / 8 * 3 1 . 7
第11讲
码本：用来表达一定量的信息或一组事件所 需的一系列符号（如字母、数字等）
码字：对每个信息或事件所赋的码符号序列
码字的长度（字长）： 每个码字里的符号个数
第11讲
第9页
11.1.1 数据冗余
1. 编码冗余 图象中灰度出现的概率
p s ( s k ) n k n
k 0 , 1 , , L 1
不同灰度出现的概率不同
① 把当前前缀P的码字输出到码字流; ② 结束。
第11讲
第33页
11.3 LZW编码
位置 1 字符 A
步骤
1 2 3 4 5 6
第11讲
23 BB 位置
1 2 3 4 6 --
4567 ABAB 词典(码字) (1) A (2) B (3) C (4)A B (5)B B (6) B A (7)A B A (8)A B A C
第11讲
第18页
11.1.3 图象编码模型
第11讲
第19页
11.2 信息理论基础
设一个离散信源X： (x1,x2, ,xN) 其概率分布： {p1,p2, ,pN} 满足
离散信源类型
无记忆信源 有记忆信源
N
pi 1
i 1
第11讲
第20页
11.2 信息理论基础
考虑无记忆信源X ，某个信源符号xk，如果它出现的概率是pk
第11讲
第13页
11.1.2 图象保真度和质量
图象保真度
信息保存型/信息损失型 描述解码图象相对于原始图象的偏离程度 对信息损失的测度
主观保真度准则 主观测量图象的质量，因人而异，应用不方便
客观保真度准则 用编码输入图与解码输出图的某个确定函数表示损 失的信息量， 便于计算或测量
第11讲
第14页
11.1.2 图象保真度和质量
信源熵
H ( X ) 1 / 4 * 2 1 / 4 * 2 1 / 4 * 2 1 / 4 * 2 2
编码方法：a,b,c,d用码字00,01,10,11来编码,每个符号用2个比
特。平均码长也是2比特。
第11讲
第22页
11.2 信息理论基础
设 X{a,b,c,d}
p ( a ) 1 /2 ,p ( b ) 1 /4 ,p ( c ) 1 /8 , p(d)1/8
第11讲
第7页
11.1.1 数据冗余
数据冗余类别
(1) 编码冗余 与灰度分布的概率特性有关
(2) 象素相关冗余 空间冗余，几何冗余
(3) 心理视觉冗余 与主观感觉有关
减少/消除其中的一种/多种冗余，就能取得数据压缩的效果
第11讲
第8页
11.1.1 数据冗余
1. 编码冗余 编码：需建立码本来表达数据
平均比特数
L1
Lavg l(sk)ps(sk)
k0
用较少的比特数表示出现概率较大的灰度级
用较多的比特数表示出现概率较小的灰度级
第11讲
第10页
11.1.1 数据冗余
第11讲
第11页
11.1.1 数据冗余
2. 象素间冗余
直接与象素间相关性联系
规则 冗余大
不规则 冗余小
第11讲
1 0.8 0.6 0.4 0.2