2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
1
7.4 统计编码高效编码的主要方法是尽可能去除信源中的冗余成份,
从而以最少的数码率传递最大的信息量 。 冗余度存在于像素间的相关性及像素值出现概率的不均等性之中,对于有记忆性信源来说首先要去除像素间的相关性,从而达到压缩数码率的目的 。 对于无记忆性信源来说,像素间没有相关性,可以利用像素灰度值出现概率的不均等性,采用某种编码方法,也可以达到压缩数码率的目的 。 这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫统计编码 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
7.4.1 离散图像信息的熵一幅图像如果有 s1,s2,…,sq共 q种幅度值，并且出现的概率分别为 P1,P2,…,Pq，那么每一种幅值所具有的信息量分别为 log2(1/P1),log2(1/P2),…,log2(1/Pq)。
由此，其平均信息量可由下式表示：
把这个平均信息量叫做熵 。
如果一个图像信源能输出 K个独立的消息,当这些消息出现的概率彼此相等时,那么这个信源的熵最大 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
7.4.2编码效率与冗余度为了确定一个衡量编码方法优劣的准则,首先讨论一下编码效率与冗余度的问题 。 设某个无记忆信源共有 M 个消息,记作 {u1,u2,…,uM}。 其中消息 ui(i=1,2,…,M） 各自出现的概率分别为 {P1,P2,… PM}。 可把这个信源用下式表示：
根据该信源的消息集合，在字母集 A={a1,a2,…,a n}中选取 ai进行编码。一般情况下取二元字母集 A∈ {0,1}。
通常，这一离散信源中的各个消息出现的概率并不相等。
根据信息论中熵的定义，可计算出该信源的熵如下式：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
式中 H(X)代表熵,Pi代表第 i个消息出现的概率 。
例如,设一离散信源如下：
可算出该信源的熵：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
设对应于每个消息的码字由 Ni个符号组成 。 也就是说每个消息所对应的码字长度各为 Ni,那么,每个消息的平均码长可用下式表示：
式中 代表平均码长,M为信源中包含的消息的个数，
Pi为第 i个消息出现的概率,Ni为第 i个消息对应的码长。
平均而言，每个符号所含有的熵为
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
编码符号是在字母集 A中选取的。如果编码后形成一个新的等概率的无记忆信源，如果字母数为 n，那么，
它的最大熵应为 log2n比特／符号，因此，这是极限值。
如果则可认为编码效率已达到 100％,若不然,则可认为编码效率较低 。
由上述概念,编码效率如下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
式中 η代表编码效率,H（ x）为信源的熵,为平均码长,n为字母集合中的字母数。
根据上述定义，如果 η≠100％，就说明还有冗余度。
因此，冗余度如下式表示：
Rd=1-η
统计编码要研究的问题就在于设法减小,使 η尽量趋近于 1,Rd趋近于 0。 显然 值有一个理论最低限,当 η=l
时,的最低限就是 H(X)/log2n。 可以根据这－准则来衡量编码方法的忧劣 。 下面举例加以说明 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
例：－个信源 X为使用的字母集合 A为：
A={0,1,2,3}
可求得信源 X的熵为
H（ X） =7/4
平均码长为
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
所以
η =(7/4)/1× log24=7/8
Rd=1-η =1-7/8=1/8
显然,编码后还有 1/8的冗余度,没有达到最低限 。
如果取 A={0,1},n=2,那么可以编成如下等长码：
u1=00 u2=01 u3=10 u4=11
此时
η =(7/4)/1× log22=7/8
Rd=1-η =1-7/8=1/8
同样有 1/8的冗余度 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
上例中的两种编码方法,其特点是码字长度均相等,
这种码叫等长码 。 显然此例中的两种等长码均没有达到最低限 。 怎样才能使信源编码达到最低限呢？ 再看下例的编码方法 。 仍选 A={0,1},n=2作为编码字符集 。
在这种编码中,不用等长码,而是采用下面的原则来编码,即 Pi大的消息编短码,Pi小的消息编长码 。
例 u1=0 u2=10 u3=110 u4=111
可计算出平均码长其效率
η =(7/4)/((7/4)× log22)=1
冗余度
Rd=1-η=0
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
由此可见，这种编码法的码字平均长度达到了最低限。
这说明用变长编码法可达到较高的效率。采用这种编码方法，信源中的消息与码字是一一对应的，因而译码时也是准确无误的。在编、译码过程中并不损失任何信息。
它是一种信息保持编码法。
7.4.3 常用的统计编码法变长编码是统计编码中最为主要的一种方法。变长编码的目标就是使平均码长达到低限，也就是使 最优，
但是，这种最优必须在一定的限制下进行，编码的基本限制就是码字要有单义性和非续长性。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
单义性代码是指任意一个有限长的码字序列只能被分割成一个一个的码字,而任何其他分割方法都会产生一些不属于码字集合中的码字 。 符合这个条件的代码就叫单义代码 。
非续长代码是指任意一个码字都不是其他码字的续长 。
换句话说,就是码字集合中的任意一个码字都不是由其中一个码字在后面添上一些码元构成的 。 很咨易看出非续长代码一定是单义的,但是,单义代码却不一定是非续长的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
最为常用的变长编码方法是 Huffman(霍夫曼 )码和
Shannon-Fano (仙农 -费诺）码。下面详细地讨论－下这两种码的构成方法。
1,Huffman码
Huffman变长编码方法能得到一组最优的变长码，其过程是：
（ 1）把信源 X中的消息按出现的概率从大到小的顺序排列。
（ 2）把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少一个，并同时再次将信源中的消息概率从大到小排列一次。
（ 3）重复上述步骤，直到信息源最后为两个信息源为止。
（ 4）将被合并的消息分别从 1和 0或 0和 1。对最后的信息源也相应的赋予 1和 0或 0和 1。
通过上述步骤就可以构成最优变长码（ Huffman 码）。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
例：有信源如下
Huffman 编码的过程图示如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
如果合并的消息赋以 1,0值，则会得到下表所示的另一组编码。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
计算信源的熵，平均码长，效率及冗余度如下。
平均码长为,
η =2.42/(2.45× log22)=0.98=98%
Rd=1-η =1-=98%=2%
所以,对于信源 X的 Huffman码的编码效率为 98％,尚有 2
％ 的冗余度 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
2,Shannon-Fano码另外一种常用的变长编码是 Shannon-Fano码 。 这种码有时也可以得到最优编码性能 。 它的编码准则要符合非续长条件,在码字中 1和 0是独立的,而且是 （ 或差不多是 ）
等概率的 。 这样的准则一方面可保证无需用间隔来区分码字,同时又保证每传输 1位码就有 1bit的信息量 。
Shannon-Fano的编码程序可由下述几个步骤来完成：
（ 1） 设信源 X有非递增的概率分布其中 P1≥P 2≥ … ≥P M。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
把 X分成两个子集合，得并使
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
（ 2） 给两个子集中的消息赋值,一个子集赋 1,一个子集赋 0。
（ 3） 重复第一步和第二步,直至每个子集内只包含一个消息为止 。 对每个消息所赋过的值依次排列出来就可以构成
Shanno- Fano编码 。
下面举例说明 Shannon-Fano码的具体构成方法 。
例设有信源
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
其编码流程图如下图所示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
编码表如表所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
如果对各子集赋以另外一种值,即 1,0,那么,同样会得到另一种编码结果,其编码表如下表所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
下面计算一下 Shannon-Fano码的平均码长，效率及冗余度。信源的熵可计算于下：
平均码长为
η =2.45/(2.45× log22)=1
Rd=1-1=0
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
由于 η =1,Rd=0,效率已达到 100％ 。 实际上,对于
Shannon-Fano码来说,如果满足下式：
P(ui)=2-Ni
且就会使编码效率达到 100％。式中的 P(ui)为消息 ui出现的概率,Ni是码字的长度。如果不满足上述条件就不会有 100％
的效率。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
例设有一信源：
编码流程及形成的码字如下图所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
可以计算出信源的熵为
H(X)=2.313
平均码长效率 η =0.993
冗余度 Rd=0.007
由此例可见,由于信源不满足式条件,编码效率不能达到 100％ 。 然而从结果上看,它仍然是一种相当好的编码 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
经过上面的讨论来看,统计编码是一种无损高效编码法 。 但是,它也有一些缺点,其一是它的码字不是等长的,在使用中需要用数据缓存单元收集可变比特率的代码,并以较慢的平均速率传输,这对使用来说不太方便 。 其次,这几种码都缺乏构造性,也就是说它们都不能用数学方法建立一一对应关系,而只能通过查表的方法来实现对应关系 。 如果消息数目太多,表就会很大,
所需要的存储器也越多,相对的设备也就越复杂 。 再有一个难题就是在编码过程中应知道每种消息可能出现的概率 。 在图像编码中就是要知道每种图像信息出现的概率 。 实际上这种概率很难估计或测量,如果不能恰当地利用这种概率便会使编码性能明显下降,因此,目前使用的方法多在基本编码基础上做进一步改进 。
(C)
1
7.4 统计编码高效编码的主要方法是尽可能去除信源中的冗余成份,
从而以最少的数码率传递最大的信息量 。 冗余度存在于像素间的相关性及像素值出现概率的不均等性之中,对于有记忆性信源来说首先要去除像素间的相关性,从而达到压缩数码率的目的 。 对于无记忆性信源来说,像素间没有相关性,可以利用像素灰度值出现概率的不均等性,采用某种编码方法,也可以达到压缩数码率的目的 。 这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫统计编码 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
7.4.1 离散图像信息的熵一幅图像如果有 s1,s2,…,sq共 q种幅度值，并且出现的概率分别为 P1,P2,…,Pq，那么每一种幅值所具有的信息量分别为 log2(1/P1),log2(1/P2),…,log2(1/Pq)。
由此，其平均信息量可由下式表示：
把这个平均信息量叫做熵 。
如果一个图像信源能输出 K个独立的消息,当这些消息出现的概率彼此相等时,那么这个信源的熵最大 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
7.4.2编码效率与冗余度为了确定一个衡量编码方法优劣的准则,首先讨论一下编码效率与冗余度的问题 。 设某个无记忆信源共有 M 个消息,记作 {u1,u2,…,uM}。 其中消息 ui(i=1,2,…,M） 各自出现的概率分别为 {P1,P2,… PM}。 可把这个信源用下式表示：
根据该信源的消息集合，在字母集 A={a1,a2,…,a n}中选取 ai进行编码。一般情况下取二元字母集 A∈ {0,1}。
通常，这一离散信源中的各个消息出现的概率并不相等。
根据信息论中熵的定义，可计算出该信源的熵如下式：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
式中 H(X)代表熵,Pi代表第 i个消息出现的概率 。
例如,设一离散信源如下：
可算出该信源的熵：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
设对应于每个消息的码字由 Ni个符号组成 。 也就是说每个消息所对应的码字长度各为 Ni,那么,每个消息的平均码长可用下式表示：
式中 代表平均码长,M为信源中包含的消息的个数，
Pi为第 i个消息出现的概率,Ni为第 i个消息对应的码长。
平均而言，每个符号所含有的熵为
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
编码符号是在字母集 A中选取的。如果编码后形成一个新的等概率的无记忆信源，如果字母数为 n，那么，
它的最大熵应为 log2n比特／符号，因此，这是极限值。
如果则可认为编码效率已达到 100％,若不然,则可认为编码效率较低 。
由上述概念,编码效率如下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
式中 η代表编码效率,H（ x）为信源的熵,为平均码长,n为字母集合中的字母数。
根据上述定义，如果 η≠100％，就说明还有冗余度。
因此，冗余度如下式表示：
Rd=1-η
统计编码要研究的问题就在于设法减小,使 η尽量趋近于 1,Rd趋近于 0。 显然 值有一个理论最低限,当 η=l
时,的最低限就是 H(X)/log2n。 可以根据这－准则来衡量编码方法的忧劣 。 下面举例加以说明 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
例：－个信源 X为使用的字母集合 A为：
A={0,1,2,3}
可求得信源 X的熵为
H（ X） =7/4
平均码长为
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
所以
η =(7/4)/1× log24=7/8
Rd=1-η =1-7/8=1/8
显然,编码后还有 1/8的冗余度,没有达到最低限 。
如果取 A={0,1},n=2,那么可以编成如下等长码：
u1=00 u2=01 u3=10 u4=11
此时
η =(7/4)/1× log22=7/8
Rd=1-η =1-7/8=1/8
同样有 1/8的冗余度 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
上例中的两种编码方法,其特点是码字长度均相等,
这种码叫等长码 。 显然此例中的两种等长码均没有达到最低限 。 怎样才能使信源编码达到最低限呢？ 再看下例的编码方法 。 仍选 A={0,1},n=2作为编码字符集 。
在这种编码中,不用等长码,而是采用下面的原则来编码,即 Pi大的消息编短码,Pi小的消息编长码 。
例 u1=0 u2=10 u3=110 u4=111
可计算出平均码长其效率
η =(7/4)/((7/4)× log22)=1
冗余度
Rd=1-η=0
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
由此可见，这种编码法的码字平均长度达到了最低限。
这说明用变长编码法可达到较高的效率。采用这种编码方法，信源中的消息与码字是一一对应的，因而译码时也是准确无误的。在编、译码过程中并不损失任何信息。
它是一种信息保持编码法。
7.4.3 常用的统计编码法变长编码是统计编码中最为主要的一种方法。变长编码的目标就是使平均码长达到低限，也就是使 最优，
但是，这种最优必须在一定的限制下进行，编码的基本限制就是码字要有单义性和非续长性。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
单义性代码是指任意一个有限长的码字序列只能被分割成一个一个的码字,而任何其他分割方法都会产生一些不属于码字集合中的码字 。 符合这个条件的代码就叫单义代码 。
非续长代码是指任意一个码字都不是其他码字的续长 。
换句话说,就是码字集合中的任意一个码字都不是由其中一个码字在后面添上一些码元构成的 。 很咨易看出非续长代码一定是单义的,但是,单义代码却不一定是非续长的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
最为常用的变长编码方法是 Huffman(霍夫曼 )码和
Shannon-Fano (仙农 -费诺）码。下面详细地讨论－下这两种码的构成方法。
1,Huffman码
Huffman变长编码方法能得到一组最优的变长码，其过程是：
（ 1）把信源 X中的消息按出现的概率从大到小的顺序排列。
（ 2）把最后两个出现概率最小的消息合并成一个消息，从而使信源的消息数减少一个，并同时再次将信源中的消息概率从大到小排列一次。
（ 3）重复上述步骤，直到信息源最后为两个信息源为止。
（ 4）将被合并的消息分别从 1和 0或 0和 1。对最后的信息源也相应的赋予 1和 0或 0和 1。
通过上述步骤就可以构成最优变长码（ Huffman 码）。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
例：有信源如下
Huffman 编码的过程图示如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
如果合并的消息赋以 1,0值，则会得到下表所示的另一组编码。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
计算信源的熵，平均码长，效率及冗余度如下。
平均码长为,
η =2.42/(2.45× log22)=0.98=98%
Rd=1-η =1-=98%=2%
所以,对于信源 X的 Huffman码的编码效率为 98％,尚有 2
％ 的冗余度 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
2,Shannon-Fano码另外一种常用的变长编码是 Shannon-Fano码 。 这种码有时也可以得到最优编码性能 。 它的编码准则要符合非续长条件,在码字中 1和 0是独立的,而且是 （ 或差不多是 ）
等概率的 。 这样的准则一方面可保证无需用间隔来区分码字,同时又保证每传输 1位码就有 1bit的信息量 。
Shannon-Fano的编码程序可由下述几个步骤来完成：
（ 1） 设信源 X有非递增的概率分布其中 P1≥P 2≥ … ≥P M。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
把 X分成两个子集合，得并使
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
（ 2） 给两个子集中的消息赋值,一个子集赋 1,一个子集赋 0。
（ 3） 重复第一步和第二步,直至每个子集内只包含一个消息为止 。 对每个消息所赋过的值依次排列出来就可以构成
Shanno- Fano编码 。
下面举例说明 Shannon-Fano码的具体构成方法 。
例设有信源
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
其编码流程图如下图所示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
编码表如表所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
如果对各子集赋以另外一种值,即 1,0,那么,同样会得到另一种编码结果,其编码表如下表所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
下面计算一下 Shannon-Fano码的平均码长，效率及冗余度。信源的熵可计算于下：
平均码长为
η =2.45/(2.45× log22)=1
Rd=1-1=0
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
由于 η =1,Rd=0,效率已达到 100％ 。 实际上,对于
Shannon-Fano码来说,如果满足下式：
P(ui)=2-Ni
且就会使编码效率达到 100％。式中的 P(ui)为消息 ui出现的概率,Ni是码字的长度。如果不满足上述条件就不会有 100％
的效率。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
例设有一信源：
编码流程及形成的码字如下图所示
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
可以计算出信源的熵为
H(X)=2.313
平均码长效率 η =0.993
冗余度 Rd=0.007
由此例可见,由于信源不满足式条件,编码效率不能达到 100％ 。 然而从结果上看,它仍然是一种相当好的编码 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
经过上面的讨论来看,统计编码是一种无损高效编码法 。 但是,它也有一些缺点,其一是它的码字不是等长的,在使用中需要用数据缓存单元收集可变比特率的代码,并以较慢的平均速率传输,这对使用来说不太方便 。 其次,这几种码都缺乏构造性,也就是说它们都不能用数学方法建立一一对应关系,而只能通过查表的方法来实现对应关系 。 如果消息数目太多,表就会很大,
所需要的存储器也越多,相对的设备也就越复杂 。 再有一个难题就是在编码过程中应知道每种消息可能出现的概率 。 在图像编码中就是要知道每种图像信息出现的概率 。 实际上这种概率很难估计或测量,如果不能恰当地利用这种概率便会使编码性能明显下降,因此,目前使用的方法多在基本编码基础上做进一步改进 。
