四、 霍夫曼编码（P124）
例：设有一信源A={a1, a2, a3, a4, a5, a6}，对应概率P={0.1, 0.4, 0.06, 0.1, 0.04, 0.3}. （1）进行霍夫曼编码（要求大概率的赋码字0，小概率的赋码字1），给出码字； （2）计算平均码长，信源熵和编码效率。 解：
（1）编码步骤
1）缩减信源符号数量
将信源符号按出现概率从大到小排列，然后结合
初始信源信源的消减步骤
符号概率1234
a20.40.40.40.40.6
a60.30.30.30.30.4
a10.10.10.20.3 a40.10.10.1 a30.060.1 a50.04
2）对每个信源符号赋值
从（消减到）最小的信源开始，逐步回到初始信源
初始信源对消减信源的赋值
符号概率码字1234
a20.410.410.410.410.60
a60.3000.3000.3000.3000.41
a10.10110.10110.20100.301
a40.101000.101000.1011
a30.06010100.10101
a50.0401011
由此可得哈夫曼编码结果见下表 符号 a1 a2 a3 a4 a5 a6 概率 0.1 0.4 0.06 0.1 0.04 0.06 编码结果 011 1 01010 0100 01011 00
平均码长B??L?1?ipi?0.4?1?0.3?2?0.1?3?0.1?4?0.0.06?5?0.0.04?5?2.2
i?0（其中，?i是灰度值为i的编码长度，pi为灰度值为ai的概率，L为灰度级数） L?1信源熵H???pilog2pi?2.14
i?0编码效率??H2.B?142.2?0.973
6
五、 费诺—仙农编码（P126）
费诺—仙农编码与Huffman编码相反，采用从上到下的方法。香农-范诺编码算法步骤： （1）按照符号出现的概率减少的顺序将待编码的符号排成序列。 （2）将符号分成两组，使这两组符号概率和相等或几乎相等。 （3）将第一组赋值为0，第二组赋值为1。 （4）对每一组，重复步骤2的操作。
例：设一副灰度级为8的图象中，各灰度所对应的概率分别为0.04，0.05，0.06，0.07，0.10，0.10，0.18，0.40，要求对其进行费诺.仙侬编码。 灰度值 S0 S1 S2 S3 S4 S5 S6 S7 出现频率 0.40 0.18 0.10 0.10 0.07 0.06 0.05 0.04 解：根据费诺—仙农编码的方法进行分组和赋值如下图所示
0.580.42s0,s1,s2,s3,s4,s5,s6,s7010.200.22s0,s1s2,s3,s4,s5,s6,s70101s0s1s2,s30.13s4,s5,s6,s70.090101s2s3s4,s5s6,s70101s4s5s6s7 所得编码结果如下表
灰度值 S0 S1 S2 S3 S4 S5 S6 S7 费诺—仙农码 00 01 100 101 1100 1101 1110 1111
7
六、 算术编码（P127）
例：编码来自1个4-符号信源{a1, a2, a3, a4}的由5个符号组成的符号序列：b1b2b3b4b5 = a1a2a3a3a4
信源符号概率初始子区间a10.2[0 , 0.2]a20.2[0.2 , 0.4]a30.4[0.4 , 0.8]a40.2[0.8 , 1.0]
解：由
Ns?Fs?Cl*L（新子区间的起始位置=前子区间的起始位置+当前符号的区间左端*前子区间长度）Ne?Fs?Cr*L（新子区间的结束位置=前子区间的起始位置+当前符号的区间右端*前子区间长度）可得，对于｛a1，a2，a3，a3，a4｝，有 a1 [0，0.2] a1a2 [0.2*0.2，0.2*0.4]=[0.04，0.08] a1a2a3 [0.04+0.04*0.4，0.04+0.04*0.8]=[0.056，0.072] a1a2a3a3 [0.056+0.016*0.4，0.056+0.016*0.8]=[0.0624，0.0688] a1a2a3a3a4 [0.0624+0.0064*0.8，0.056+0.0064*1]=[0.06752，0.0688]
解码过程 0.068
(1)0.068 在区间[0 ,0.2] ，可知第一个源符号为a1(2) 0.068?00.2?0.34在区间[0.2-0.4]中，第二个为a2(3)0.34?0.2 0.2?0.7在区间[0.4-0.8]中，第三个为a3(4)0.7?0.4 0.4?0.75在区间[0.4-0.8]中，第四个为a3(5)0.75?0.4 0.4?0.875在区间[0.8-1]中，第五个为a4
8
七、 区域分割
状态法（峰谷法、灰度阈值法）（P155）
基本思想是，确定一个合适的阈值T。将大于等于阈值的像素作为物体或背景，生成一个二值图像。阈值的选定可以通过如下图中灰度直方图确定。
方法：首先统计最简单图像的灰度直方图，若直方图呈双峰且有明显的谷，则将谷所对应的灰度值T作为阈值，按图右侧的等式进行二值化，就可将目标从图像中分割出来。这种方法适用于目标和背景的灰度差较大、有明显谷的情况。
g(x,y)???0?1在四邻域中有背景的像素，既是边界像素。
例：对下面的图像用状态法进行二值化，并计算二值图像的欧拉数。
0 1 3 2 1 3 2 1 0 5 7 6 2 5 6 7 1 6 0 6 1 6 3 4 2 6 7 5 3 5 6 5 3 2 2 7 2 6 1 6 2 6 5 0 2 7 5 0 1 2 3 2 1 2 1 2 3 1 2 3 1 2 2 1
解：（1）首先根据已知列出灰度级分布表
灰度级 0 1 2 3 4 5 6 7 像素个数 5 12 16 8 1 7 10 5 （2）画出图像的直方图
161412108642001234567
f(x,y)?T f(x,y)?T9
?0f(x,y)?T（3）由此可确定阈值T = 4，根据g(x,y)???1f(x,y)?T，二值化的图像如下：
0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
（4）在二值图像中，1像素连接成分数C减去孔数H的差值叫做这幅图像的欧拉数。
本题从图中可以看出，其取值为1的像素的连接成分数C = 2，孔数H = 2，所以这幅图像的欧拉数为E = C – H = 2 – 2 = 0
10