文档介绍：统计编码
高效编码的主要方法是尽可能去除信源中的冗余成份,从而以最少的数码率传递最大的信息量。冗余度存在于像素间的相关性及像素值出现概率的不均等性之中,对于有记忆性信源来说首先要去除像素间的相关性,从而达到压缩数码率的目的。对于无记忆性信源来说,像素间没有相关性,可以利用像素灰度值出现概率的不均等性,采用某种编码方法,也可以达到压缩数码率的目的。这种根据像素灰度值出现概率的分布特性而进行的压缩编码叫统计编码。
11/10/2017
1
数字图象处理演示稿纪玉波制作(C)
离散图像信息的熵
一幅图像如果有s1,s2,…,sq共q种幅度值,并且出现的概率分别为P1,P2,…,Pq,那么每一种幅值所具有的信息量分别为log2(1/P1),log2(1/P2),…,log2(1/Pq)。由此,其平均信息量可由下式表示:
把这个平均信息量叫做熵。
如果一个图像信源能输出K个独立的消息,当这些消息出现的概率彼此相等时,那么这个信源的熵最大。
11/10/2017
2
数字图象处理演示稿纪玉波制作(C)
为了确定一个衡量编码方法优劣的准则,首先讨论一下编码效率与冗余度的问题。设某个无记忆信源共有M 个消息,记作{u1,u2,…,uM}。其中消息ui(i=1,2,…,M)各自出现的概率分别为{P1,P2,…PM}。可把这个信源用下式表示:
根据该信源的消息集合,在字母集A={a1,a2,…,an}中选取ai进行编码。一般情况下取二元字母集A∈{0,1}。通常,这一离散信源中的各个消息出现的概率并不相等。根据信息论中熵的定义,可计算出该信源的熵如下式:
11/10/2017
3
数字图象处理演示稿纪玉波制作(C)
式中H(X)代表熵,Pi代表第i个消息出现的概率。
例如,设一离散信源如下:
可算出该信源的熵:
11/10/2017
4
数字图象处理演示稿纪玉波制作(C)
设对应于每个消息的码字由Ni个符号组成。也就是说每个消息所对应的码字长度各为Ni,那么,每个消息的平均码长可用下式表示:
式中代表平均码长,M为信源中包含的消息的个数,Pi为第i个消息出现的概率,Ni为第i个消息对应的码长。平均而言,每个符号所含有的熵为
11/10/2017
5
数字图象处理演示稿纪玉波制作(C)
编码符号是在字母集A中选取的。如果编码后形成一个新的等概率的无记忆信源,如果字母数为n,那么,它的最大熵应为log2n比特/符号,因此,这是极限值。如果
则可认为编码效率已达到100%,若不然,则可认为编码效率较低。
由上述概念,编码效率如下式表示:
11/10/2017
6
数字图象处理演示稿纪玉波制作(C)
式中η代表编码效率,H(x)为信源的熵, 为平均码长,n为字母集合中的字母数。
根据上述定义,如果η≠100%,就说明还有冗余度。因此,冗余度如下式表示:
Rd=1-η
统计编码要研究的问题就在于设法减小,使η尽量趋近于1,Rd趋近于0。显然值有一个理论最低限,当η=l时, 的最低限就是H(X)/log2n。可以根据这-准则来衡量编码方法的忧劣。下面举例加以说明。
11/10/2017
7
数字图象处理演示稿纪玉波制作(C)
例:-个信源X为
使用的字母集合A为:
A={0,1,2,3}
可求得信源X的熵为
H(X)=7/4
平均码长为
11/10/2017
8
数字图象处理演示稿纪玉波制作(C)
所以
η=(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的冗余度。
11/10/2017
9
数字图象处理演示稿纪玉波制作(C)
上例中的两种编码方法,其特点是码字长度均相等,这种码叫等长码。显然此例中的两种等长码均没有达到最低限。怎样才能使信源编码达到最低限呢?再看下例的编码方法。仍选A={0,1},n=2作为编码字符集。在这种编码中,不用等长码,而是采用下面的原则来编码,即Pi大的消息编短码,Pi小的消息编长码。
例 u1=0 u2=10 u3=110 u4=111
可计算出平均码长
其效率
η=(7/4)/((7/4)×log22)=1
冗余度
Rd=1-η=0
11/10/2017
10
数字图象处理演示稿纪玉波制作(C)