第八章 小波分析理论及应用
? D(i, j)：节点(i, j)的后继的集合； ? L(i, j) = D(i, j) – O(i, j).
除了根节点外，对所有有子节点的节点(i, j) O(i, j) = {(2i, 2j), (2i, 2j+1), (2i+1, 2j), (2i+1, 2j+1)}. 集划分规则是：
1）初始分割由集合{(i, j)}和D(i, j)形成，其中?i,j??H;
2）如果D(i, j)是有效的，则把它分割成L(i, j)和四个单元素集，每个元素
?k,l??O?i,j?；
3）如果L(i, j)是有效的，那么把它分割成四个集合D(k, l)， 其中?k,l??O?i,j?。 它的基本运算是集测试：
??1,Sn?T?????maxci,j?i,j??T???2n (8.6-1)
0,otherwise,判断某集合是否有效就是看式(8.6-1)集测试的结果，若值为1则表示有效，否则表示是无效的。
使用了三个链表来记录相关信息：
? LIS：无效集合链表(List of insignificant sets) ? LIP：无效象素链表(List of insignificant pixels) ? LSP：有效象素链表(List of significant pixels) LIP和LSP都是记录坐标信息，而LIS记录的是集合信息，或者为D(i, j)，标记为A， 或者为L(i, j)，标记为B。
8.6.2.2 编码算法 完整的编码算法是： 步骤1. 初始化：
输出n??log2max?i,j?ci,j?；置有效系数链表LSP为空，把所有根节点坐标加入无效系数链表LIP中，并且把有后继的根节点标记为类型A加入无效系数集链表LIS中。
????步骤2. 排序过程
步骤2.1 对LIP中的每一表项(i, j)，进行如下操作
输出Sn?i,j?；
如果Sn?i,j??1，把(i, j)移至LSP，输出ci,j的符号；
步骤2.2 对LIS中的每一个表项(i, j)，进行如下操作 步骤2..2.1 如果该表项具有类型A，那么， * 输出Sn?D?i,j??； * 如果Sn?D?i,j??=1，那么
41
第八章 小波分析理论及应用
对每一个?k,l??O?i,j?，进行如下操作， - 输出Sn?k,l?； - 若Sn?k,l??1，那么把(k, l)加入LSP，输出ci,j的符号； - 如果Sn?k,l??0，那么把(k, l)加至LIP的尾部； 如果L?i,j???，把(i, j)移到LIS的尾部，并且标记为类型B； 否则，把(i, j)从LIS中删除； 步骤2.2.2 如果该表项具有类型B，那么进行如下操作， * 输出Sn?L?i,j??； * 如果Sn?L?i,j???1，那么， 对每一个?k,l??O?i,j?，将其标记为类型A，并将之加到LIS尾部； 把(i, j)从LIS中删除。
步骤3. 细化过程：对LSP中的每一个表项(i, j)， 不包含刚才步骤2中加入的，输出系数ci,j的二进制表示的第n位有效位；
步骤4. 量化级更新：把n减1，并转向步骤2，直到达到要求的压缩比。
8.6.2.3 译码算法 A. Said和 W. A. Pearlman并没有明确给出译码算法，为完整起见，这里把译码算法也列出：
步骤1. 初始化：
读入n??log2max?i,j?ci,j中。
步骤2. 排序过程 步骤2.1 对LIP中的每一表项(i, j)，进行如下操作 读出一比特Sn?i,j?； 如果Sn?i,j??1，把(i, j)移至LSP，并且读出ci,j的符号；
?????；置有效系数链表LSP为空，把所有根节点坐标加入无
效系数链表LIP中，并且把有后继的根节点标记为类型A加入无效系数集链表LIS
?i,j?1.5?2n；若为负，令c?i,j??1.5?2n； 若符号为正，令c步骤2.2 对LIS中的每一个表项(i, j)，进行如下操作 步骤2..2.1 如果该表项具有类型A，那么， * 读出Sn?D?i,j??； * 如果Sn?D?i,j??=1，那么 对每一个?k,l??O?i,j?，进行如下操作， - 读出Sn?k,l?；
- 若Sn?k,l??1，那么把(k, l)加入LSP，读出ci,j的符号；
?i,j?1.5?2n；若为负，令c?i,j??1.5?2n； 若符号为正，令c
- 如果Sn?k,l??0，那么把(k, l)加至LIP的尾部；
42
第八章 小波分析理论及应用
如果L?i,j???，把(i, j)移到LIS的尾部，并且标记为类型B； 否则，把(i, j)从LIS中删除； 步骤2.2.2 如果该表项具有类型B，那么进行如下操作， * 读出Sn?L?i,j??； * 如果Sn?L?i,j???1，那么， 对每一个?k,l??O?i,j?，将其标记为类型A，并将之加到LIS尾部； 把(i, j)从LIS中删除；
步骤3. 细化过程：对LSP中的每一个表项(i, j)， 不包含刚才步骤2中加入的，读出系
?i,j中加上2n?1，数ci,j的二进制表示的第n位有效位；若为1，则向c否则，从中减去2n?1。
步骤4. 量化级更新：把n减1，并转向步骤2，直到达到要求的压缩比。 比较编码和译码算法，可知二者的结构是一样的，这是一个非常重要的特点，它使得该算法不必传送有效系数的位置信息，它们已被隐含在算法的处理过程之中。 8.6.3 有效系数树编码的性能分析 Shapiro和Said在使用零树编码时都是假定在一棵子树中的系数可能会同时很小，在小波变换下，这种假设与实际情况符合的很好，因而两种算法都获得了很好的性能。对小波变换解相关能力的分析表明，小波变换具有很强的去相关能力，变换域系数的能量大部分集中在低频子带上，通过采用子树结构对系数进行划分，把那些可能很小的系数组织在一起，形成一系列零树，对零树只用很少的比特进行编码，大幅度地提高了编码性能。下面利用信息论来分析它们为何是有效的。 8.6.3.1 离散信源的熵
X:?0,1??? 设有离散信源： ?p?x?:?1?p,p? 信源熵H(p)定义为：H?p????plogp??1?p?log?1?p? (8.6-2)
0.8Entropy Function1
H(p)0.40.200
0.60.20.4p0.60.81图8.6-2 熵函数H(p)
图8.6-2表明熵函数H(p)是上凸函数，当p为0.5时取最大值。信源熵给出信源信息
43
第八章 小波分析理论及应用
量的度量，只有信源符号均匀分布时，其熵才取最大值，否则表示还存在冗余。对于只取0或1的离散简单信源，即使p不为0.5，因对单个信源符号进行编码时不可能采用非整数比特，只能是1比特，说明冗余很大。由于实际信源通常都是空间或时间的离散序列，形成所谓的扩展信源，对扩展信源进行编码可使每个信源符号的平均编码率为非整数，从而逼近信源熵，算术编码就是其中的一种。依据此思想，可对有效系数树编码算法的性能进行分析。 8.6.3.2 性能分析 设有数据集U??X1,X2,?,XK?，其中Xi表示取值为0或1的独立同分布的随机变量，取值为1的概率为p, 取值为0的概率为1-p，当p远小于1时，各变量的熵很小，若对各变量独立进行编码，需要K比特，冗余很大，为此，定义一个随机变量W，当集合U有效时，也就是U中的任意元素取值为1时，W取值为1，否则，W取值为0，这与SPIHT算法中的集测试是一样的，当W取值为1时，才对X的各元素进行编码。 W取值为1的概率是p1?1??1?p?K，对W进行编码要用1比特，当W为1时，对U的各元素编码要用K比特，每符号的平均比特率为
C?1?p1K1??p1 (8.6-3) KK单独对X的元素进行编码的平均比特率是1比特，所以，若 1C??p1?1
K?1?即当p?1????K?1/K时，上述处理方法就是有效的，例如若K=4，只要p<0.293时就能提
高编码效率，在小波变换中，这是很容易达到的。
当p足够小时，可把K2个U集合按如上方式组合起来，进一步减小编码冗余，为方便把式(8.6-3)中的K记为K1，这时每符号的平均比特率为
?1??1?p2K2??p1??K?1?p2K2C1?1??1?p???C2???p2?1?
K2K2K2K?1?同理可得
C3??1?1??1????p3??p?p2?1?? ?K3?K1???K2若重复J次以上过程，得
J11JCJ???pn (8.6-4) ?KJm?1Km?1n?m式中K0?1。
44
第八章 小波分析理论及应用
Cost Unit:bit图8.6-3表示了J=3时编码效率的改善。
0.90.80.70.60.50.40.30.200.010.020.03p0.040.050.06图例： * K=2 K=4
图8.6-3 编码效率的改善
文献[8]表明，在小波变换下，变换系数的值90%以上都集中在0附近，也就是说量化后，系数为0的概率是很大的，为1的概率很小，如图8.6-3所示，当系数为1的概率p很小时，采用如上所述的编码方式进行编码，编码效率能获得较大的改善。
8.6.4实验结果
8.6.4.1 SPIHT算法与常规小波变换编码方式的比较 用Radarsat-1在1997年4月22日 22点01分44秒获取的我国山东半岛及渤海湾区域的C波段、2视、50米分辨率SAR图像进行了实验，选取了一块海区，一块含城区的陆地，共二块区域，作为对比，还选取了IEEE标准测试图Lena。
表8.6-1 SAR图像的压缩实验结果 比特/象素 常规小波变换 SAR海区图像 SPIHT 无算术编码 SPIHT 有算术编码 常规小波变换 SAR陆地图像 SPIHT 无算术编码 SPIHT 有算术编码 0.08 0.125 0.25 0.5 1 2 4 22.16 22.70 24.21 26.32 30.37 36.87 48.05 21.89 22.45 23.73 25.74 29.41 47.22 52.35 22.10 22.74 24.05 26.32 30.30 37.07 48.08 22.17 23.00 24.48 27.01 30.77 35.98 47.65 22.11 22.86 24.43 26.76 30.21 36.27 47.21 22.31 23.09 24.76 27.21 30.89 37.00 47.97
45
小波分析及其应用（精品教程）
