本文给出SPIHT编码的排序扫描代码，排序扫描分为LIP队列扫描和LIS队列扫描两个步骤，其中LIS队列扫描较为复杂，在编程时容易出现错误，要倍加注意。2、LIP队列扫描程序function [Sn,LSP,LIP]=lip_scan(Sn,N,LSP,LIP)% 函数 LIP_SCAN() 检查LIP表的各个表项是否重要，更新列表LIP、LSP和排序位流 Sn% 输入参数：Sn —— 本级编码排序位流，为空表% N —— 本级编码阈值的指数% LSP —— 上一级编码生成的重要系数列表% LIP —— 上一级编码生成的不重要系数列表% 输出参数：Sn —— 对上一级编码生成的LIP列表扫描后更新的排序位流% LSP —— 对上一级编码生成的LIP列表扫描后更新的重要系数列表% LIP —— 经本级LIP扫描处理后更新的不重要系数列表global Mat% Mat是输入的小波分解系数矩阵，作为全局变量，在编码的相关程序中使用rlip=size(LIP,1);% r 是指向 LIP 当前读入表项位置的指针r=1;% 由于循环过程中列表 LIP 的表长会变化，不适合用 for 循环，故采用 while 循环while r<=rlip% 读入当前表项的坐标值 rN=LIP(r,1); cN=LIP(r,2);% 调用 SNOUT() 函数来判断该表项是否重要 if SnOut(LIP(r,:),N) % 若重要，则输入‘1’到 Sn Sn=[Sn,1]; % 输入正负符号‘1’或‘0’到 Sn if Mat(rN,cN)>=0 Sn=[Sn,1]; else Sn=[Sn,0]; end % 将该表项添加到重要系数列表 LSP LSP=[LSP;LIP(r,:)]; % 将该表项从 LIP 中删除 LIP(r,:)=[]; else % 若不重要，则输入‘0’到 Sn Sn=[Sn,0]; % 将指针指向下一个表项 r=r+1; end % 判断当前 LIP 的表长 rlip=size(LIP,1);end3、LIS队列扫描程序function [LSP,LIP,LIS,LisFlag,Sn,N]=lis_scan(N,Sn,LSP,LIP,LIS,LisFlag)% 函数 LIS_SCAN() 检查LIS表的各个表项是否重要，更新列表LIP、LSP、LIS、LisFlag和排序位流 Sn% 输入参数：N —— 本级编码阈值的指数% Sn —— 本级编码排序位流，为空表% LSP —— 上一级编码生成的重要系数列表% LIP —— 上一级编码生成的不重要系数列表% LIS —— 上一级编码生成的不重要子集列表% LisFlag —— 上一级编码生成的不重要子集表项类型列表% 输出参数：LSP —— 本级LIS列表扫描后更新的重要系数列表% LIP —— 经本级LIS扫描处理后更新的不重要系数列表% LIS —— 本级LIS列表扫描后更新的不重要子集列表% LisFlag —— 本级LIS列表扫描后更新的不重要子集表项类型列表% Sn —— 本级LIS列表扫描后更新的排序位流% N —— 下一级编码阈值的指数global Mat rMat cMat% Mat是输入的小波分解系数矩阵，作为全局变量，在编码的相关程序中使用% rMat、cMat是Mat的行、列数，作为全局变量，在编码、解码的相关程序中使用% 读入当前 LIS 的表长rlis=size(LIS,1);% ls 是指向 LIS 当前表项位置的指针，初始位置为1ls=1;% 由于循环过程中列表 LIS 的表长会变化，不适合用 for 循环，故采用 while 循环while ls<=rlis % 读入当前 LIS 表项的类型 switch LisFlag(ls) % ‘D’类表项，包含孩子和非直系子孙 case 'D' % 读入该表项的坐标值 rP=LIS(ls,1); cP=LIS(ls,2); % 生成‘D’型子孙树 chD=coef_DOL(rP,cP,'D'); % 判断该子孙树是否重要 isImt=SnOut(chD,N); if isImt % 如果该子孙树重要，就输入‘1’到 Sn Sn=[Sn,1]; % 生成该表项的孩子树 chO=coef_DOL(rP,cP,'O'); % 分别判断每个孩子的重要性 for r=1:4 % 判断该孩子的重要性和正负符号 [isImt,Sign]=SnOut(chO(r,:),N); if isImt % 如果重要，就输入‘1’和正负标志到 Sn Sn=[Sn,1]; if Sign Sn=[Sn,1]; else Sn=[Sn,0]; end % 将该孩子添加到重要系数列表 LSP LSP=[LSP;chO(r,:)]; else % 如果不重要，就输入‘0’到 Sn Sn=[Sn,0]; % 将该孩子添加到不重要系数列表 LIP % 本级阈值下不重要的系数在下一级编码中可能是重要的 LIP=[LIP;chO(r,:)]; end end % 生成该表项的非直系子孙树 chL=coef_DOL(rP,cP,'L'); if ~isempty(chL) % 如果‘L’型树非空，则将该表项添加到列表 LIS 的尾端等待扫描 LIS=[LIS;LIS(ls,:)]; % 表项类型更改为‘L’型 LisFlag=[LisFlag,'L']; % 至此，该表项的‘D’型LIS扫描结束，在LIS中删除该项及其类型符 LIS(ls,:)=[]; LisFlag(ls)=[]; else % 如果‘L’型树为空集 % 则该表项的‘D’型LIS扫描结束，在LIS中删除该项及其类型符 LIS(ls,:)=[]; LisFlag(ls)=[]; end else % 如果该表项的‘D’型子孙树不重要，就输入‘0’到 Sn Sn=[Sn,0]; % 将指针指向下一个 LIS 表项 ls=ls+1; end % 更新当前 LIS 的表长，转入下一表项的扫描 rlis=size(LIS,1); case 'L' % 对‘L’类表项，不需判断孩子的重要性 % 读入该表项的坐标值 rP=LIS(ls,1); cP=LIS(ls,2); % 生成‘L’型子孙树 chL=coef_DOL(rP,cP,'L'); % 判断该子孙树是否重要 isImt=SnOut(chL,N); if isImt % 如果该子孙树重要，就输入‘1’到 Sn Sn=[Sn,1]; % 生成该表项的孩子树 chO=coef_DOL(rP,cP,'O'); % 将该‘L’类表项从 LIS 中删除 LIS(ls,:)=[]; LisFlag(ls)=[]; % 将表项的四个孩子添加到 LIS 的结尾，标记为‘D’类表项 LIS=[LIS;chO(1:4,:)]; LisFlag(end+1:end+4)='D'; else % 如果该子孙树是不重要的，就输入‘0’到 Sn Sn=[Sn,0]; % 将指针指向下一个 LIS 表项 ls=ls+1; end % 更新当前 LIS 的表长，转入下一表项的扫描 rlis=size(LIS,1); endend% 对 LIS 的扫描结束，将本级阈值的指数减1，准备进入下一级编码N=N-1; LIS队列扫描程序中调用的子程序有：
COEF_DOL() ：根据子孙树的类型'type'来计算点(r,c)的子孙列表；
SNOUT() ：根据本级阈值指数 N 判断坐标集 coefSet 是否重要；
（1）子孙树生成程序function chList=coef_DOL(r,c,type)% 函数 COEF_DOL() 根据子孙树的类型'type'来计算点(r,c)的子孙列表% 输入参数：r,c —— 小波系数的坐标值% type —— 子孙树的类型% 'D'：点(r,c)的所有子孙（包括孩子）% 'O'：点(r,c)的所有孩子% 'L'：点(r,c)的所有非直系子孙，L(r,c)=D(r,c)-O(r,c)% 输出参数：chList —— 点(r,c)的'type'型子孙列表global Mat rMat cMat% Mat是输入的小波分解系数矩阵，作为全局变量，在编码的相关程序中使用% rMat、cMat是Mat的行、列数，作为全局变量，在编码、解码的相关程序中使用[Dch,Och]=childMat(r,c);% 函数 CHILDMAT() 返回点(r,c)的'D'型和'O'型子孙列表Lch=setdiff(Dch,Och,'rows');% 根据关系式 L(r,c)=D(r,c)-O(r,c)求出'L'型子孙列表% Matlab函数 SETDIFF(A,B)计算具有相同列数的两个矩阵A、B中，A有而B无的元素集合% 根据输入参数'type'选择输出参数switch type case 'D' chList=Dch; case 'O' chList=Och; case 'L' chList=Lch;endfunction [trAll,trChl]=childMat(trRows,trCols)% 函数 CHILDMAT() 根据输入的坐标值trRows、trCols 输出其全体子孙 trAll，% 其中包括孩子树 trChl；另外，根据算法原理，还要判断子孙树是否全为零，% 若为全零，则trAll、trChl均为空表global Mat rMat cMat% Mat是输入的小波分解系数矩阵，作为全局变量，在编码的相关程序中使用% rMat、cMat是Mat的行、列数，作为全局变量，在编码、解码的相关程序中使用trAll=treeMat(trRows,trCols);% 调用函数 treeMat() 生成该点的子孙树坐标队列trZero=1;% 用变量 trZero 来标记该点是否具有非零子孙rA=size(trAll,1);% 如果子孙树 trAll 中有系数值不为零，则 trZero=0，表示该点具有非零子孙for r=1:rA if Mat(trAll(r,1),trAll(r,2))~=0 trZero=0; break; endendif trZero trAll=[]; trChl=[];else trChl=trAll(1:4,:); % 函数 treeMat() 输出的全体子孙树 trAll 头四位元素就组成相应的孩子树end 上面调用的函数treeMat() 与EZW算法中使用的程序是一样的，这里就不写出来了，详细代码请参见《嵌入式小波零树（EZW）算法的过程详解和Matlab代码（1）构建扫描次序表》。（2）系数集重要性判别程序function [isImt,Sign]=SnOut(coefSet,N)% 函数 SNOUT() 根据本级阈值指数 N 判断坐标集 coefSet 是否重要 isImt ，对单元素% 的系数集输出该元素的正负符号 Sign 。global Mat% Mat是输入的小波分解系数矩阵，作为全局变量，在编码的相关程序中使用rSet=size(coefSet,1);% 读取坐标集中各元素的系数值for r=1:rSet cMat(r)=Mat(coefSet(r,1),coefSet(r,2));end% 根据系数最大值判断该坐标集是否重要if max(abs(cMat))>=2^N isImt=1;else isImt=0;end% 对单个元素的坐标集，判断该元素的正负符号if cMat(1)>=0 Sign=1;else Sign=0;end
