多级树集合分裂（SPIHT）算法的过程详解和Matlab实现（2）数学表述

上一篇文章我们讨论了SPIHT算法与EZW算法的关系，介绍了SPIHT算法的树结构、分集规则和有序表的构建。在此基础上，我们接下来讨论算法的编码原理。下文给出了比较详细的数学描述，吃透了这一过程，就比较容易写出程序代码了。

SPIHT算法的编码过程如下：
（1）初始化
输出初始阈值T的指数 N = floor ( log2 ( max{| Cr,c |} ) ) （Matlab函数 floor( num ) 给出不大于数值 num 的最大整数）
定义： LSP 为空集
LIP = {(r,c) | (r,c)∈H }
LIS = {D(r,c) | (r,c)∈H 且(r,c)具有非零子孙}
初始的LIS中各表项类型均为‘D’， LIS 和 LIP 中 (r,c) 的排列顺序与EZW算法零树结构的扫描顺序相同（即按从上到下、从左到右的“Z”型次序排列）。
（2）排序扫描
1）扫描LIP队列
对LIP队列的每个表项 (r,c) ：
① 输出SnOut（r,c）（函数SnOut判断(r,c)的重要性）；
② 如果SnOut（r,c）= 1，则向排序位流Sn输出‘1’和（r,c）的符号位（由‘1’、‘0’表示），然后将（r,c）从LIP队列中删除，添加到LSP队列的尾部。
③ 如果SnOut（r,c）= 0，则向排序位流Sn输出‘0’。
2）扫描LIS队列
对LIS队列的每个表项 (r,c) ：
① 如果（r,c）是‘D’型表项
输出SnOut（D (r,c)）；
* 如果SnOut（D (r,c)）= 1
向排序位流Sn输出‘1’；
对每个(rO,cO) ∈O (r,c)
输出SnOut（rO,cO）
* 如果SnOut（rO,cO）= 1，则向排序位流Sn输出‘1’和（rO,cO）的符号位，将（rO,cO）添加到LSP的尾部；
* 如果SnOut（rO,cO）= 0，则向排序位流Sn输出‘0’，将（rO,cO）添加到LIP的尾部。
判断L (r,c) 是否为空集
如果L (r,c) 非空，则将（r,c）作为‘L’型表项添加到LIS的尾部；
如果L (r,c)为空集，则将‘D’型表项（r,c）从LIS中删除。
* 如果SnOut（D (r,c)）= 0
则向排序位流Sn输出‘0’。
② 如果（r,c）是‘L’型表项
输出SnOut（L (r,c)）；
* 如果SnOut（L (r,c)）= 1，则向排序位流Sn输出‘1’，然后将(r,c)的4个孩子（rO,cO）作为‘D’型表项依次添加到LIS的尾部，将‘L’型表项（r,c）从LIS中删除；
* 如果SnOut（L (r,c)）= 0，则向排序位流Sn输出‘0’。
（3）精细扫描
将上一级扫描后的LSP列表记为LSP_Old，对于（r,c）∈ LSP_Old ，
将系数Cr,c的绝对值转换为二进制表示Br,c；
输出Br,c中第N个最重要的位（即对应于2^N权位处的符号‘1’或‘0’）到精细位流Rn。
（4）更新阈值指数
将阈值指数N减至N—1，返回到步骤（2）进行下一级编码扫描。