图象压缩与编码要点：
信息量，熵，联合熵，率失真函数
编码效率，冗余度，压缩比
无失真编码，有失真编码
霍夫曼编码
行程编码
预测编码
DCT编码
混合编码图象压缩与编码数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。
如一幅 512x512的黑白图象的比特数为
512x512x8=2,097,152 bit=256k。
再如一部 90分钟的彩色电影，每秒放映
24帧。把它数字化，每帧 512x512象素，
每象素的 R,G,B三分量分别占 8 bit，总比特数为图象压缩与编码
90x60x24x3x512x512x8bit=97,200M。
如一张 CD光盘可存 600兆字节数据，这部电影光图象（还有声音）就需要 160张
CD光盘用来存储。
对图象数据进行 压缩显得非常必要。
本章讨论的问题：在满足一定条件下，
能否减小图象 bit数，以及用什么样的编码方法使之减少。
实 例图象编码 —密码烽火台鸽子头发下稀有语种图象编码 —密码
F
L
A
S
H
一种发型可以代表一种信息。
鼠标指向图像，按右键，选“播放”
少数民族文字女书女书图象编码 —密码恺撒密码图象编码 —密码恺撒密码图象编码 —密码恺撒密码图象编码 —密码恺撒密码英文字母出现相对频率字母
A
B
C
D
E
F
G
H
I
J
K
L
M
百分比
8.2
1.5
2.8
4.3
12.7
2.2
2.0
6.1
7.0
0.2
0.8
4.0
2.4
字母
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
百分比
6.7
7.5
1.9
0.1
6.0
6.3
9.1
2.8
1.0
2.4
0.2
2.0
0.1
英文字母出现相对频率图象编码 —密码点击图片播放视频某个图形或物品也可以作为密码。
图象编码 —密码虹膜与指纹。
图象压缩与编码
1,图象数据压缩是可能的：
一般原始图象中存在很大的冗余度 。
用户通常允许图象失真 。
当信道的分辨率不及原始图象的分辨率时,降低输入的原始图象的分辨率对输出图象分辨率影响不大 。
用户对原始图象的信号不全都感兴趣,可用特征提取和图象识别的方法,丢掉大量无用的信息 。 提取有用的信息,使必须传输和存储的图象数据大大减少 。
图象压缩与编码
2,原始图象越有规则,各象素之间的相关性越强,它可能压缩的数据就越多 。
值得指出的是：当前采用的编码方法得到的结果,离可能压缩的极限还相差很远,这说明图象数据压缩的潜力是很大的,直到目前为止,它还是个正在继续研究的领域 。
图象压缩与编码
3,图象结构的性质,大体上可分为两大类,一类是具有一定图形特征的结构,另一类是具有一定概率统计特性的结构 。
基于不同的图象结构特性,应采用不同的压缩编码方法 。
图象压缩与编码
4,全面评价一种编码方法的优劣,除了看它的 编码效率,实时性 和 失真度 以外,
还要看它的 设备复杂程度,是否 经济与实用 。
常采用混合编码的方案,以求在性能和经济上取得折衷 。
随着计算方法及 VLSI的发展,使许多高效而又比较复杂的编码方法在工程上有实现的可能 。
信源编码的基本概念图象数据压缩的 目的 是在满足一定图象质量条件下,用尽可能少的比特数来表示原始图象,以提高图象传输的效率和减少图象存储的容量,在信息论中称为 信源编码 。
信源编码可分为两大类,一类是 无失真编码,另一类是 有失真编码 或称 限失真编码 。
无失真编码无失真编码 又称 信息保持编码 或 可逆的无误差编码 。
信息量,从 N个相等可能发生的事件中,选出其中一个事件所需的信息度量,称为 信息量 。
无失真编码要辨识 1到 32中选定的某一个数,
可先提问：,是否大于 16？,,得到回答就消去半数可能事件 。 每提问一次得到回答,可以得到 1bit信息量 （
二进制位 ） 。 这里共需 5次,因此所需的信息量为 。532lo g
2?
无失真编码定义信息量,从 N个数选定一个数 s的概率为 p(s),且等概率,p(s)=1/N。
熵,设信源符号表为 s={s1,s2,…,sq}，
其概率分布为 P(s)={p(s1),p(s2),…,p(sq)}
,则信源的 熵 为
)]([)(l o g1l o gl o g)( 222 spIspNNsI
q
i
ii
q
i
ii spIspspspH
11
2 )]([)()(l o g)()( s
无失真编码
s作为灰度,共 q级,出现概率均等时,
p(si)=1/q，
当灰度只有两级时,即 si = 0,1,且 0出现概率为 p1,1出现概率为 p2=1- p1,其熵
qqqH
q
i
2
1
2 lo g
1lo g1)(
s
1
21
1
21 1
1lo g)1(1lo g)(
ppppHs
无失真编码当 p1=1/2,p2=1- p1 =1/2时,H(s)=1为最大值 。 如图所示 。
无失真编码熵的性质：
（ 1） 熵是一个非负数,即总有 H(s)≥0。
（ 2） 当其中一个符号 sj的出现概率 p(sj)=1
时,其余符号 si(i≠ j)的出现概率 p(si) =0，
H(s)=0。
（ 3） 当各个 si出现的概率相同 时,则最大平均信息量为 log2 q。
（ 4） 熵值总有 H(s) ≤ log2 q。
无失真编码
(一 ) 无失真编码定理可以证明,在无干扰的条件下,存在一种无失真的编码方法,使编码的平均长度
L 与 信 源 的 熵 H(s) 任 意 地 接 近,即
L=H(s)+ε,其中 ε为任意小的正数,但以
H(s)为其下限,即 L≥ H(s),这就是 香农
(Shannon)无干扰编码定理 。
L
)( sHL
)( sHL?
无失真编码
(二 ) 熵与相关性,冗余度的关系对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。
原始图象 冗余度 定义为：
1)(1 sH Lr 原始图象的熵原始图象平均码长无失真编码将 编码效率 定义为：
rL
sH
1
1)(?
冗余度接近于 0,或编码效率接近于 1的编码称为 高效码 。
无失真编码若原始图象的平均比特率为 n，编码后的平均比特率为 nd，则 压缩比 C定义为：
dn
nC?
由 Shannon定理,无失真编码 最大可能的数据压缩比 为：
)()( sH
n
sH
nC
M
实 例无失真编码独立信源的熵与马尔可夫信源的熵令 q=2L,其中 L等于自然二进制码的长度 。 可以证明,对于独立信源,等概率分布时,具有最大熵 HM(s)=L比特,因而冗余度 r=L/HM(s)-1=0,不可能压缩 。
讨论
（ 1） 独立信源,又称 无记忆信源,符号 si
的出现,与其他的符号无关 。
q
i
ii spspH
1
2 )(lo g)()( s
无失真编码非等概率分布时的熵，一般有 H1(s)
<HM(s)=L,因而冗余度 r=L/H1(s)-1>0，
还有可能压缩。
（ 2） 有限马尔可夫 (Markov)信源的熵又称 有限记忆信源,它的统计特性要用转移概率 或 条件概率 来描述。
m阶 Markov信源，是指某个符号 si出现的概率只与前面 m个符号有关。
无失真编码设 s={s1,s2,…,sq}，则转移概率
p(si/si1,si2,…,sim)乃是前 m个符号为 si1,si2,…,sim时，第 m+1个符号为 si
的概率。
信息量
I(si/si1,si2,…,sim)=-log2 p(si/si1,si2,…,
sim)
无失真编码对符号表取平均的信息量
)
,,,
(
)
,,,
(l o g)
,,,
(
)
,,,
()
,,,
()
,,,
(
21
1 21
2
21
1 212121
miii
q
i miii
i
miii
i
q
i miiimiiimiii
sss
H
sss
s
p
sss
s
p
sss
I
sss
p
sss
I
s
sss
这是在给定序列 si1,si2,…,sim的条件下,信源的 条件熵。
无失真编码再考虑序列 si1,si2,…,sim发生的概率，
可将 m阶 Markov信源的 熵 定义为：
)
,,,
(l o g),,,,(
)
,,,
(l o g)
,,,
(),,,(
)
,,,
(),,,()(
21
2
1 1
21
1 1
21
2
211 1
21
1 1
1 21
21
1 1
1 2
1 2
1 2
miii
i
q
i
q
i
imiii
q
i
q
i
miii
i
miii
i
q
i
q
i
miii
q
i
q
i
q
i miii
miii
q
i
q
i
sss
s
pssssp
sss
s
p
sss
s
psssp
sss
HssspH
m
m
m
ss
无失真编码在多数情况下，只是相邻的少数符号间的相关性比较大，因此，可以用阶数较低的 Markov过程作为信源近似的数学模型。
特别是对零阶 Markov信源（即独立信源）
只要考虑 q个可能输入值 s1,s2,…,sq出现的概率 p(si),可定义 一级熵,
)(lo g)( 2
1
1 i
q
i
i spspH?
无失真编码对 1阶 Markov信源，要考虑两个相邻符号的联合概率 p(si1,si),可定义 二级熵,
q
i
ii
q
i
ii sspsspH
1
2
1
2
1
11 ),(lo g),(
m+1级熵,
q
i
q
i
q
i
q
i
iimiiiimiim
m
sssspsssspH
1 1 1 1
2221
1 2
11 ),,,,(l o g),,,,(
无失真编码注意,m+1级熵是 m+1个输入值同时编码所需的比特数的下限。
12)(),()( 11
1
HHsHssHssH iii
i
i
因为熵表征符号 si 的,混乱程度,，“
不确定性量度,，若相邻符号之间的相关性越大，则条件熵 H(si/si1)越小,H2越接近
H1。
可以证明,1阶 Markov信源的条件熵无失真编码
1) 相邻符号完全相关,H(si/si1)= 0,H2 =H1；
2) 相邻符号完全不相关时,H(si/si1)=H1,H2
=2H1 ；
一般来说，若 n个相邻符号完全相关时，则
Hn =H1,是最小值 ；
若 n个相邻符号完全不相关时，则 Hn = n H1,
是最大值 ；
可见，相邻符号的相关性使得熵变小，这是熵的基本性质之一。
无失真编码外国的鸿雁传书？
无失真编码
（四） 高效的编码方法无干扰编码定理只指出存在一种无失真的编码，可使 。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。
（ 1） Huffman码它是长度不均匀的，其平均长度最短的即时可译码。其 要点 是对经常出现的符
)( sHL
英文字母出现相对频率字母
A
B
C
D
E
F
G
H
I
J
K
L
M
百分比
8.2
1.5
2.8
4.3
12.7
2.2
2.0
6.1
7.0
0.2
0.8
4.0
2.4
字母
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
百分比
6.7
7.5
1.9
0.1
6.0
6.3
9.1
2.8
1.0
2.4
0.2
2.0
0.1
英文字母出现相对频率国际莫尔斯电码符号
Symbol
A
B
C
D
E
F
G
H
I
J
K
L
M
Code
.-
-…
-.-.
-..
.
..-.
--.
….
..
.---
-.-
.-..
--
Symbol
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Code
-.
---
.--.
--.-
.-.
…
-
..-
… -
.--
-..-
-.--
--..
Symbol
0
1
2
3
4
5
6
7
8
9
Code
-----
.----
..---
… --
…,-
…..
-….
--...
---..
----.
Symbol
.
,
:;
-
/
“
Code
.-.-.-
--..--
..--..
---…
-.-.-.
-… -
-..-.
.-..-.
霍夫曼码与莫尔斯码的区别在哪里？
点击图片播放视频无失真编码号赋予最短的码字,然后按出现概率减少的次序,逐个赋予较长的码字,这样可使码的平均长度
q
i
iilpL
1
具有最小值,pi--si出现概率,li--对 si编码的长度 。
无失真编码信号源 s={s1,s2,s3,s4,s5,s6},其概率分布为 p1=0.4 p2=0.3 p3=0.1 p4=0.1 p5=0.06
p6=0.04,求最佳 Huffman码 。
方法：
i,将信源符号按出现概率从大到小排成一列,然后把最末两个符号的概率相加,
合成一个概率 。
无失真编码方法：
ii,把这个符号的概率与其余符号的概率按从大到小排列,然后再把最末两个符号的概率加起来,合成一个概率 。
iii.重复上述做法,直到最后剩下两个概率为止 。
iv.从最后一步剩下的两个概率开始逐步向前进行编码 。 每步只需对两个分支各赋予一个二进制码,如对概率大的赋予码元 0,对概率小的赋予码元 1。
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S1=1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S2=00
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S3=011
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S4=0100
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S5=01010
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S6=01011
无失真编码
（ 2） B码在某些应用中,编码器输入符号集合的概率分布服从乘幂律,pk=k-r,k=1,2,…,q。
r为正常数,则用 B码,它接近于最佳编码
。 B码是一种非等长码,由两部分组成,
一部分叫,延续比特,,一部分叫,信息比特,。 延续比特的作用是标注一个码字究竟延续多长,信息比特的作用是表示不同的信息符号 。
无失真编码方法：
将信源符号按出现概率从大到小排序,
然后按 B1码的前后顺序分别赋予相应符号
,便得到各符号的 B1码 。 其中信息码是按二进制的长度及数的顺序排列的,即 0,1
,00,01,10,11,000,001,… 。 延续码 C是在编码过程中确定的,可将 C=0赋予前一个码字,将 C=1赋予后一个码字,
再将 C=0赋予下一个码字 。
无失真编码方法：
例如,编码器输入符号序列为 s4s1s5s2…,
则 B1码为：
0001,10,0100,11,…
或者
1011,00,1110,01,…
延续码改变,表示前一个码字结束,后一个码字开始 。
B1码优点,编码方法简单,容易实现 。
无失真编码
（ 3） 移位码 S2
对具有单调减小概率的输入信号相当有效的非等长码 。
S2码由 2bit长的 码字组成,总共包含四个不同的码字,C1=00,C2=01,C3=10，
C4=11,C4的个数用来表示该符号的序数超过 3的次数 。 符号编码：
C1,C2,C3,C4C1,C4C2,C4C3,C4C4C1
,C4C4C2,C4C4C3,…
这种编码方法更简单 。
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
S2码
00
01
10
1100
1101
1110
2.4
0.895
0.115
1.25
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
S2码
00
01
10
1100
1101
1110
2.4
0.895
0.115
1.25
2.14
自然码
000
001
010
011
100
101
3
0.713
0.402
1
2.14
L
限失真编码严格的无失真编码的压缩比一般是不大的 。 编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面,用户通常允许图象有一定的失真,这为图象数据压缩提供了较大的可能性,因此人们非常注意限失真编码问题 。
在给定失真条件下,信源编码所能达到的压缩率的极限码率,称为 率失真函数,
R(D),D为失真上限 。
限失真编码
R(0) ≤H(Y),收到的信号序列不存在相关性时,等号成立 。
D↑,R(D) ↓。
允许失真度 D越小,则所需 率失真函数值 R(D) 就越大,要求信源编码效率也越高 。
p.436
图象编码模型映射变换器 量化器 编码器原始图象 码字图象压缩编码的一般框图图象编码模型映射变换,将输入数据从象素域变换到另一个域,在变换域中则能以较少的比特数对图象进行量化编码 。
对映射变换器的要求,要从数据压缩的有效性,保真度和经济实用方面考虑,应该是
i,高度去相关的,
ii,可逆的,
iii,重现的均方误差最小,
iv,易于实现的 。
图象编码模型
（ 1） 行程编码把沿着扫描行的象素序列 x1,x2,…,xN映射为行程序列 (g1,l1),(g2,l2),…,(gk,lk)。
gi—灰度级 li—gi的行程长度因为象素序列可以根据行程序列来重建
,故行程映射变换是可逆的 。 因它包含灰度鉴别和行程计数,故它是非线性的 。
图象编码模型
（ 2） 差分映射编码矩阵形式：
nn
x
x
x
x
y
y
y
y
3
2
1
3
2
1
1100
0110
0011
0001
图象编码模型或矩阵 A是非奇异的,因而这种映射变换是可逆的 。 差分编码 是一种最简单的线性预测编码 。
AXY?
图象编码模型
（ 3） 正交变换编码各种正交变换都是可逆的线性变换 。 应用正交变换的图象编码常称为 变换编码 。
正交变换有傅立叶变换 (FFT),余弦变换 (DCT),沃尔什 -哈达玛变换 (WHT),小波变换 (DWT)等 。
信息量，熵，联合熵，率失真函数
编码效率，冗余度，压缩比
无失真编码，有失真编码
霍夫曼编码
行程编码
预测编码
DCT编码
混合编码图象压缩与编码数字图象通常要求很大的比特数，这给图象的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。
如一幅 512x512的黑白图象的比特数为
512x512x8=2,097,152 bit=256k。
再如一部 90分钟的彩色电影，每秒放映
24帧。把它数字化，每帧 512x512象素，
每象素的 R,G,B三分量分别占 8 bit，总比特数为图象压缩与编码
90x60x24x3x512x512x8bit=97,200M。
如一张 CD光盘可存 600兆字节数据，这部电影光图象（还有声音）就需要 160张
CD光盘用来存储。
对图象数据进行 压缩显得非常必要。
本章讨论的问题：在满足一定条件下，
能否减小图象 bit数，以及用什么样的编码方法使之减少。
实 例图象编码 —密码烽火台鸽子头发下稀有语种图象编码 —密码
F
L
A
S
H
一种发型可以代表一种信息。
鼠标指向图像，按右键，选“播放”
少数民族文字女书女书图象编码 —密码恺撒密码图象编码 —密码恺撒密码图象编码 —密码恺撒密码图象编码 —密码恺撒密码英文字母出现相对频率字母
A
B
C
D
E
F
G
H
I
J
K
L
M
百分比
8.2
1.5
2.8
4.3
12.7
2.2
2.0
6.1
7.0
0.2
0.8
4.0
2.4
字母
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
百分比
6.7
7.5
1.9
0.1
6.0
6.3
9.1
2.8
1.0
2.4
0.2
2.0
0.1
英文字母出现相对频率图象编码 —密码点击图片播放视频某个图形或物品也可以作为密码。
图象编码 —密码虹膜与指纹。
图象压缩与编码
1,图象数据压缩是可能的：
一般原始图象中存在很大的冗余度 。
用户通常允许图象失真 。
当信道的分辨率不及原始图象的分辨率时,降低输入的原始图象的分辨率对输出图象分辨率影响不大 。
用户对原始图象的信号不全都感兴趣,可用特征提取和图象识别的方法,丢掉大量无用的信息 。 提取有用的信息,使必须传输和存储的图象数据大大减少 。
图象压缩与编码
2,原始图象越有规则,各象素之间的相关性越强,它可能压缩的数据就越多 。
值得指出的是：当前采用的编码方法得到的结果,离可能压缩的极限还相差很远,这说明图象数据压缩的潜力是很大的,直到目前为止,它还是个正在继续研究的领域 。
图象压缩与编码
3,图象结构的性质,大体上可分为两大类,一类是具有一定图形特征的结构,另一类是具有一定概率统计特性的结构 。
基于不同的图象结构特性,应采用不同的压缩编码方法 。
图象压缩与编码
4,全面评价一种编码方法的优劣,除了看它的 编码效率,实时性 和 失真度 以外,
还要看它的 设备复杂程度,是否 经济与实用 。
常采用混合编码的方案,以求在性能和经济上取得折衷 。
随着计算方法及 VLSI的发展,使许多高效而又比较复杂的编码方法在工程上有实现的可能 。
信源编码的基本概念图象数据压缩的 目的 是在满足一定图象质量条件下,用尽可能少的比特数来表示原始图象,以提高图象传输的效率和减少图象存储的容量,在信息论中称为 信源编码 。
信源编码可分为两大类,一类是 无失真编码,另一类是 有失真编码 或称 限失真编码 。
无失真编码无失真编码 又称 信息保持编码 或 可逆的无误差编码 。
信息量,从 N个相等可能发生的事件中,选出其中一个事件所需的信息度量,称为 信息量 。
无失真编码要辨识 1到 32中选定的某一个数,
可先提问：,是否大于 16？,,得到回答就消去半数可能事件 。 每提问一次得到回答,可以得到 1bit信息量 （
二进制位 ） 。 这里共需 5次,因此所需的信息量为 。532lo g
2?
无失真编码定义信息量,从 N个数选定一个数 s的概率为 p(s),且等概率,p(s)=1/N。
熵,设信源符号表为 s={s1,s2,…,sq}，
其概率分布为 P(s)={p(s1),p(s2),…,p(sq)}
,则信源的 熵 为
)]([)(l o g1l o gl o g)( 222 spIspNNsI
q
i
ii
q
i
ii spIspspspH
11
2 )]([)()(l o g)()( s
无失真编码
s作为灰度,共 q级,出现概率均等时,
p(si)=1/q，
当灰度只有两级时,即 si = 0,1,且 0出现概率为 p1,1出现概率为 p2=1- p1,其熵
qqqH
q
i
2
1
2 lo g
1lo g1)(
s
1
21
1
21 1
1lo g)1(1lo g)(
ppppHs
无失真编码当 p1=1/2,p2=1- p1 =1/2时,H(s)=1为最大值 。 如图所示 。
无失真编码熵的性质：
（ 1） 熵是一个非负数,即总有 H(s)≥0。
（ 2） 当其中一个符号 sj的出现概率 p(sj)=1
时,其余符号 si(i≠ j)的出现概率 p(si) =0，
H(s)=0。
（ 3） 当各个 si出现的概率相同 时,则最大平均信息量为 log2 q。
（ 4） 熵值总有 H(s) ≤ log2 q。
无失真编码
(一 ) 无失真编码定理可以证明,在无干扰的条件下,存在一种无失真的编码方法,使编码的平均长度
L 与 信 源 的 熵 H(s) 任 意 地 接 近,即
L=H(s)+ε,其中 ε为任意小的正数,但以
H(s)为其下限,即 L≥ H(s),这就是 香农
(Shannon)无干扰编码定理 。
L
)( sHL
)( sHL?
无失真编码
(二 ) 熵与相关性,冗余度的关系对于无失真图象的编码，原始图象数据的压缩存在一个下限，即平均码组长度不能小于原始图象的熵，而理论上的最佳编码的平均码长无限接近原始图象的熵。
原始图象 冗余度 定义为：
1)(1 sH Lr 原始图象的熵原始图象平均码长无失真编码将 编码效率 定义为：
rL
sH
1
1)(?
冗余度接近于 0,或编码效率接近于 1的编码称为 高效码 。
无失真编码若原始图象的平均比特率为 n，编码后的平均比特率为 nd，则 压缩比 C定义为：
dn
nC?
由 Shannon定理,无失真编码 最大可能的数据压缩比 为：
)()( sH
n
sH
nC
M
实 例无失真编码独立信源的熵与马尔可夫信源的熵令 q=2L,其中 L等于自然二进制码的长度 。 可以证明,对于独立信源,等概率分布时,具有最大熵 HM(s)=L比特,因而冗余度 r=L/HM(s)-1=0,不可能压缩 。
讨论
（ 1） 独立信源,又称 无记忆信源,符号 si
的出现,与其他的符号无关 。
q
i
ii spspH
1
2 )(lo g)()( s
无失真编码非等概率分布时的熵，一般有 H1(s)
<HM(s)=L,因而冗余度 r=L/H1(s)-1>0，
还有可能压缩。
（ 2） 有限马尔可夫 (Markov)信源的熵又称 有限记忆信源,它的统计特性要用转移概率 或 条件概率 来描述。
m阶 Markov信源，是指某个符号 si出现的概率只与前面 m个符号有关。
无失真编码设 s={s1,s2,…,sq}，则转移概率
p(si/si1,si2,…,sim)乃是前 m个符号为 si1,si2,…,sim时，第 m+1个符号为 si
的概率。
信息量
I(si/si1,si2,…,sim)=-log2 p(si/si1,si2,…,
sim)
无失真编码对符号表取平均的信息量
)
,,,
(
)
,,,
(l o g)
,,,
(
)
,,,
()
,,,
()
,,,
(
21
1 21
2
21
1 212121
miii
q
i miii
i
miii
i
q
i miiimiiimiii
sss
H
sss
s
p
sss
s
p
sss
I
sss
p
sss
I
s
sss
这是在给定序列 si1,si2,…,sim的条件下,信源的 条件熵。
无失真编码再考虑序列 si1,si2,…,sim发生的概率，
可将 m阶 Markov信源的 熵 定义为：
)
,,,
(l o g),,,,(
)
,,,
(l o g)
,,,
(),,,(
)
,,,
(),,,()(
21
2
1 1
21
1 1
21
2
211 1
21
1 1
1 21
21
1 1
1 2
1 2
1 2
miii
i
q
i
q
i
imiii
q
i
q
i
miii
i
miii
i
q
i
q
i
miii
q
i
q
i
q
i miii
miii
q
i
q
i
sss
s
pssssp
sss
s
p
sss
s
psssp
sss
HssspH
m
m
m
ss
无失真编码在多数情况下，只是相邻的少数符号间的相关性比较大，因此，可以用阶数较低的 Markov过程作为信源近似的数学模型。
特别是对零阶 Markov信源（即独立信源）
只要考虑 q个可能输入值 s1,s2,…,sq出现的概率 p(si),可定义 一级熵,
)(lo g)( 2
1
1 i
q
i
i spspH?
无失真编码对 1阶 Markov信源，要考虑两个相邻符号的联合概率 p(si1,si),可定义 二级熵,
q
i
ii
q
i
ii sspsspH
1
2
1
2
1
11 ),(lo g),(
m+1级熵,
q
i
q
i
q
i
q
i
iimiiiimiim
m
sssspsssspH
1 1 1 1
2221
1 2
11 ),,,,(l o g),,,,(
无失真编码注意,m+1级熵是 m+1个输入值同时编码所需的比特数的下限。
12)(),()( 11
1
HHsHssHssH iii
i
i
因为熵表征符号 si 的,混乱程度,，“
不确定性量度,，若相邻符号之间的相关性越大，则条件熵 H(si/si1)越小,H2越接近
H1。
可以证明,1阶 Markov信源的条件熵无失真编码
1) 相邻符号完全相关,H(si/si1)= 0,H2 =H1；
2) 相邻符号完全不相关时,H(si/si1)=H1,H2
=2H1 ；
一般来说，若 n个相邻符号完全相关时，则
Hn =H1,是最小值 ；
若 n个相邻符号完全不相关时，则 Hn = n H1,
是最大值 ；
可见，相邻符号的相关性使得熵变小，这是熵的基本性质之一。
无失真编码外国的鸿雁传书？
无失真编码
（四） 高效的编码方法无干扰编码定理只指出存在一种无失真的编码，可使 。它并没有指出具体的编码方法。下面介绍几种具体的编码方法。
（ 1） Huffman码它是长度不均匀的，其平均长度最短的即时可译码。其 要点 是对经常出现的符
)( sHL
英文字母出现相对频率字母
A
B
C
D
E
F
G
H
I
J
K
L
M
百分比
8.2
1.5
2.8
4.3
12.7
2.2
2.0
6.1
7.0
0.2
0.8
4.0
2.4
字母
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
百分比
6.7
7.5
1.9
0.1
6.0
6.3
9.1
2.8
1.0
2.4
0.2
2.0
0.1
英文字母出现相对频率国际莫尔斯电码符号
Symbol
A
B
C
D
E
F
G
H
I
J
K
L
M
Code
.-
-…
-.-.
-..
.
..-.
--.
….
..
.---
-.-
.-..
--
Symbol
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Code
-.
---
.--.
--.-
.-.
…
-
..-
… -
.--
-..-
-.--
--..
Symbol
0
1
2
3
4
5
6
7
8
9
Code
-----
.----
..---
… --
…,-
…..
-….
--...
---..
----.
Symbol
.
,
:;
-
/
“
Code
.-.-.-
--..--
..--..
---…
-.-.-.
-… -
-..-.
.-..-.
霍夫曼码与莫尔斯码的区别在哪里？
点击图片播放视频无失真编码号赋予最短的码字,然后按出现概率减少的次序,逐个赋予较长的码字,这样可使码的平均长度
q
i
iilpL
1
具有最小值,pi--si出现概率,li--对 si编码的长度 。
无失真编码信号源 s={s1,s2,s3,s4,s5,s6},其概率分布为 p1=0.4 p2=0.3 p3=0.1 p4=0.1 p5=0.06
p6=0.04,求最佳 Huffman码 。
方法：
i,将信源符号按出现概率从大到小排成一列,然后把最末两个符号的概率相加,
合成一个概率 。
无失真编码方法：
ii,把这个符号的概率与其余符号的概率按从大到小排列,然后再把最末两个符号的概率加起来,合成一个概率 。
iii.重复上述做法,直到最后剩下两个概率为止 。
iv.从最后一步剩下的两个概率开始逐步向前进行编码 。 每步只需对两个分支各赋予一个二进制码,如对概率大的赋予码元 0,对概率小的赋予码元 1。
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S1=1
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S2=00
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S3=011
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S4=0100
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S5=01010
Huffman编码输入
S1
S2
S3
S4
S5
S6
输入概率
0.4
0.3
0.1
0.1
0.06
0.04
第一步
0.4
0.3
0.1
0.1
0.1
第二步
0.4
0.3
0.2
0.1
第三步
0.4
0.3
0.3
第四步
0.6
0.4
0
1
0
1
0
1
0
1
0
1
S6=01011
无失真编码
（ 2） B码在某些应用中,编码器输入符号集合的概率分布服从乘幂律,pk=k-r,k=1,2,…,q。
r为正常数,则用 B码,它接近于最佳编码
。 B码是一种非等长码,由两部分组成,
一部分叫,延续比特,,一部分叫,信息比特,。 延续比特的作用是标注一个码字究竟延续多长,信息比特的作用是表示不同的信息符号 。
无失真编码方法：
将信源符号按出现概率从大到小排序,
然后按 B1码的前后顺序分别赋予相应符号
,便得到各符号的 B1码 。 其中信息码是按二进制的长度及数的顺序排列的,即 0,1
,00,01,10,11,000,001,… 。 延续码 C是在编码过程中确定的,可将 C=0赋予前一个码字,将 C=1赋予后一个码字,
再将 C=0赋予下一个码字 。
无失真编码方法：
例如,编码器输入符号序列为 s4s1s5s2…,
则 B1码为：
0001,10,0100,11,…
或者
1011,00,1110,01,…
延续码改变,表示前一个码字结束,后一个码字开始 。
B1码优点,编码方法简单,容易实现 。
无失真编码
（ 3） 移位码 S2
对具有单调减小概率的输入信号相当有效的非等长码 。
S2码由 2bit长的 码字组成,总共包含四个不同的码字,C1=00,C2=01,C3=10，
C4=11,C4的个数用来表示该符号的序数超过 3的次数 。 符号编码：
C1,C2,C3,C4C1,C4C2,C4C3,C4C4C1
,C4C4C2,C4C4C3,…
这种编码方法更简单 。
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
S2码
00
01
10
1100
1101
1110
2.4
0.895
0.115
1.25
2.14
L
几种 编码比较输入
S1
S2
S3
S4
S5
S6
r
C
H(s)
概率
0.4
0.3
0.1
0.1
0.06
0.04
霍夫曼码
1
00
011
0100
01010
01011
2.2
0.975
0.025
1.36
2.14
B1码
C0
C1
C0C0
C0C1
C1C0
C1C1
2.6
0.825
0.21
1.15
2.14
S2码
00
01
10
1100
1101
1110
2.4
0.895
0.115
1.25
2.14
自然码
000
001
010
011
100
101
3
0.713
0.402
1
2.14
L
限失真编码严格的无失真编码的压缩比一般是不大的 。 编码效率的提高往往要以采用较复杂的编码方法为代价；另一方面,用户通常允许图象有一定的失真,这为图象数据压缩提供了较大的可能性,因此人们非常注意限失真编码问题 。
在给定失真条件下,信源编码所能达到的压缩率的极限码率,称为 率失真函数,
R(D),D为失真上限 。
限失真编码
R(0) ≤H(Y),收到的信号序列不存在相关性时,等号成立 。
D↑,R(D) ↓。
允许失真度 D越小,则所需 率失真函数值 R(D) 就越大,要求信源编码效率也越高 。
p.436
图象编码模型映射变换器 量化器 编码器原始图象 码字图象压缩编码的一般框图图象编码模型映射变换,将输入数据从象素域变换到另一个域,在变换域中则能以较少的比特数对图象进行量化编码 。
对映射变换器的要求,要从数据压缩的有效性,保真度和经济实用方面考虑,应该是
i,高度去相关的,
ii,可逆的,
iii,重现的均方误差最小,
iv,易于实现的 。
图象编码模型
（ 1） 行程编码把沿着扫描行的象素序列 x1,x2,…,xN映射为行程序列 (g1,l1),(g2,l2),…,(gk,lk)。
gi—灰度级 li—gi的行程长度因为象素序列可以根据行程序列来重建
,故行程映射变换是可逆的 。 因它包含灰度鉴别和行程计数,故它是非线性的 。
图象编码模型
（ 2） 差分映射编码矩阵形式：
nn
x
x
x
x
y
y
y
y
3
2
1
3
2
1
1100
0110
0011
0001
图象编码模型或矩阵 A是非奇异的,因而这种映射变换是可逆的 。 差分编码 是一种最简单的线性预测编码 。
AXY?
图象编码模型
（ 3） 正交变换编码各种正交变换都是可逆的线性变换 。 应用正交变换的图象编码常称为 变换编码 。
正交变换有傅立叶变换 (FFT),余弦变换 (DCT),沃尔什 -哈达玛变换 (WHT),小波变换 (DWT)等 。
