多媒体3c.ppt

1
熵编码
引例:小张掷一个骰子,让眼被蒙住的小李猜骰子向上的点数。由于正方体骰子六个侧面是等价的, 1、2、3、4、5、6点向上的概率相同都等于1/6,所以小李猜对的概率是1/6。如果提供如下消息:  a: 骰子的点数是偶数。  b: 骰子的点数不是2。  c: 骰子的点数是1,2,3,4,5,6中的一个。  d: 骰子的点数是4。
①当小李只得到其中的一条消息后,他猜对的概率分别为1/3(a) ,1/5(b), 1/6(c), 1(d)。  ②当小李依次得到a ,b或b ,a这两条消息,那么他猜对的概率均为1/2。
上面的例子说明:概率反映了事件发生不确定性的大小,而信息是可以改变不确定性的;消息中所含有用“信息”的量(信息量)是不同的,“信息量”是可以数量化的。在定量地描述“信息量”之前必须对事件的不确定性给出确切的量度。
2
(一)信息熵及基本概念
1. 信息量和信息熵
信源编码器模型
信源
X = {x1, x2, …, xn}
编码器
编码输出集
Z = {z1, z2, …, zn}
符号集
Am={a1, a2, …, am}
X 是消息集,由n个信号单元xj构成(j=1, 2, …, n)
Z 是输出集,由n个码字zj构成(j=1, 2, …, n),zj和xj一一对应。
Am是符号集,由m个码元ai构成(i=1, 2, …, m),符号集中的码元组成输出的码字。(比如二进制编码的话,m=2)
3
香农信息论认为,信息量是指从N个相等的可能事件中选出一个事件所需要的信息度量或含量。一个消息可能性越小,其信息越多;而消息的可能性越大,则其信息越少。
香农信息论把一个事件(xi)所携带的信息量定义为:
I(xi) = log2 (1/pi) = -log2 pi (bit)
其中pi为事件发生(字符出现)的概率。
I(xi)即随机变量X取值为xi时所携带的信息量。
信源X发出的xj(j=1,2,…,n)共n个随机事件的信息统计平均,即
H(X)称为信源X的“熵”,即信源X发出任意一个随机变量的平均信息量。
4
香农的信息熵是指信息中排除了冗余后的平均信息量。

用Lc表示编码器输出码字的平均码长,计算公式为:
(j=1,2,…,n)
其中: 是信源S发出的概率,
为的编码长度。
5
结论:无损压缩的平均编码长度不能小于信息熵公式给出的结果。
可以证明,
为了衡量编码的效果,引入编码的效率和压缩比C :
L为原图像的平均码长
6
在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长,则当
Lc>> 有冗余,不是最佳。
Lc< 不可能。
Lc= 最佳编码(Lc稍大于)。
熵值为平均码长Lc的下限。
7
1. 最佳编码定理:
在变长码中,对于出现概率大的信息符号编以短字长的码,对于出现概率小的信息符号编以长字长的码,如果码字长度严格按照符号概率大小相反的顺序排列,则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。
二、霍夫曼(Huffman)编码
8
2. 具体的编码步骤如下:
(1)将信源符号出现的概率按由小到大的顺序排序。
(2)将两处最小的概率进行组合相加,形成一个新的概率。
(3)将新出现的概率与未编码的字符一起重新排序。
(4)重复步骤(2)、(3),直到出现的概率和为1。
(5)分配代码。代码分配从最后一步开始反向进行,对最后两个概率一个赋予0代码,一个赋予1代码。如此反向进行到开始的概率排列。
9
例:设输入图像的灰度级{a1,a2,a3,a4,a5,a6}、、、、、。试进行哈夫曼编码,并计算编码效率、压缩比。
编码步骤:
(1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序。
(2)把概率小的两个符号组成一个节点,如图中的a5、a6组成节点P1。
(3)重复步骤2,得到节点P2、P3、P4、P5,形成一棵“树”,其中P5为根节点。
(4)从根节点P5开始到相应于每个符号的“树叶”,从上到下标上1(上枝)或者0(下枝),至于哪个为1哪个为0则无关紧要,最后的结果仅仅是分配的代码不同,而代码的平均长度是相同的。
最终编码结果为:a1 =1, a2 =000 , a3 =011,
a4 =001, a5 =0100, a6 =0101
10
由公式可求得图像信源熵是:
H(X)=
= -(×+×+×+
×+×+×)
= bit