多级树集合分裂（SPIHT）算法的过程详解与Matlab实现（7）解码过程——扫描解码

提示：任何排序算法的执行路径都是使用分支点的比较结果进行定义的。如果解码器和编码器使用相同的排序算法，则对于编码器输入的系数比较结果，解码器通过执行相同的路径就可获得排序信息。

所以，只需将编码器数学表述中的“输出”改为“输入”，解码器即可恢复数据的排序信息；在恢复数据排序信息的同时，解码器还要负责图像的重构，对于确认恢复的重要系数，通过排序扫描和精细扫描两个步骤更新系数的量化值，逐步提高逼近精度和重构图像的质量。

global rMat cMat
% rMat、cMat是Mat的行、列数，作为全局变量，在编码、解码的相关程序中使用

% 读入当前 LIS 的表长
rlis=size(LIS,1);
% ls 是指向 LIS 当前表项位置的指针，初始位置为1
ls=1;
while ls<=rlis
% 读入当前 LIS 表项的类型
switch LisFlag(ls)
% ‘D’类表项，包含孩子和非直系子孙
case 'D'
% 读入该表项的坐标值
rP=LIS(ls,1);
cP=LIS(ls,2);
% 根据 Sn 判断该表项‘D’型子孙树是否重要
if Sn(1)==1
% 每次判断都是读入 Sn 的首位数，判断后立即删除这一位数
Sn(1)=[];
% 生成该表项的孩子树
chO=coef_DOL(rP,cP,'O');
% 分别判断每个孩子的重要性
for r=1:4
% 读入孩子的坐标值
rO=chO(r,1);
cO=chO(r,2);
% 判断该孩子的重要性
if Sn(1)==1
Sn(1)=[];
% 判断该孩子的正负符号
if Sn(1)==1
Sn(1)=[];
% 生成该孩子的系数值
DecodeMat(rO,cO)=1.5*2^N;
else
Sn(1)=[];
DecodeMat(rO,cO)=-1.5*2^N;
end
% 将该孩子添加到重要系数列表 LSP
LSP=[LSP;chO(r,:)];
else
% 如果不重要，则这个孩子的系数值为 0
DecodeMat(rO,cO)=0;
Sn(1)=[];
% 将该孩子添加到不重要系数列表 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’型子孙树不重要，则先删除读入的 Sn 值
Sn(1)=[];
% 然后将指针指向下一个 LIS 表项
ls=ls+1;
end
% 更新当前 LIS 的表长，转入下一表项的扫描
rlis=size(LIS,1);
case 'L'
% 对‘L’类表项，不需判断孩子的重要性
% 读入该表项的坐标值
rP=LIS(ls,1);
cP=LIS(ls,2);
% 判断该表项的‘L’型子孙树是否重要
if Sn(1)==1
% 如果该子孙树重要
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
% 如果该表项的‘L’型子孙树不重要，则先删除读入的 Sn 值
Sn(1)=[];
% 然后将指针指向下一个 LIS 表项
ls=ls+1;
end
% 更新当前 LIS 的表长，转入下一表项的扫描
rlis=size(LIS,1);
end
end
% 对 LIS 的扫描结束，将本级阈值的指数减1，准备进入下一级编码
N=N-1;

4、精细扫描解码程序

function DecodeMat=decRefine(DecodeMat,Rn,N,LSP_Old)
% 函数 DECREFINE()为精细解码程序，对上一级解码产生的重要系数列表LSP_Old，根据输入的
% 精细位流 Rn 提高重要系数值的重构精度
% 输入参数：DecodeMat —— 经排序扫描解码后的重构系数矩阵
% Rn —— 精细扫描输出位流
% N —— 本级解码阈值的指数
% LSP_Old —— 上一级解码产生的重要系数列表
% 输出参数：DecodeMat —— 提高重要系数精度后的重构矩阵

rlsp=size(LSP_Old,1);
if ~isempty(LSP_Old)
for r=1:rlsp
dMat=DecodeMat(LSP_Old(r,1),LSP_Old(r,2));
% 首先读取重构矩阵中重要系数的值 dMat
rMat=abs(dMat)+(-1)^(1+Rn(1))*2^(N-1);
% 对 dMat 的绝对值，如果 Rn = 1，则加上2^(N-1)，否则减去2^(N-1)，结果存入 rMat
if dMat<=0
rMat=-rMat;
end
% 如果 dMat 为负数，则 rMat 也转为负数
Rn(1)=[];
% 消去所读取的Rn信息
DecodeMat(LSP_Old(r,1),LSP_Old(r,2))=rMat;
% 将提高了精度的重要系数值返回重构矩阵中
end
end

OK！SPIHT算法的编码、解码程序到这就基本完成啦，下一篇文章我们就用这些程序来做个实例演示。

2、LIP扫描解码程序

function [DecodeMat,Sn,LSP,LIP]=lip_decode(DecodeMat,Sn,N,LSP,LIP)
% 函数 LIP_DECODE() 根据排序位流 Sn，更新列表LIP、LSP和重构系数矩阵 DecodeMat
% 输入参数：DecodeMat —— 上一级解码后生成的重构系数矩阵
% Sn —— 本级解码排序位流
% N —— 本级解码阈值的指数
% LSP —— 上一级解码生成的重要系数列表
% LIP —— 上一级解码生成的不重要系数列表
% 输出参数：DecodeMat —— 本级LIP扫描后更新的重构系数矩阵
% Sn —— 对LIP列表扫描后更新的排序位流
% LSP —— 对LIP列表扫描后更新的重要系数列表
% LIP —— 本级LIP扫描后更新的不重要系数列表

rlip=size(LIP,1);
% r 是指向 LIP 当前读入表项位置的指针
r=1;
% 解码路径与编码路径基本一致，不过解码是根据排序位流 Sn 来判断系数是否重要
while r<=rlip
% 读入当前表项的坐标值
rN=LIP(r,1);
cN=LIP(r,2);
% 根据 Sn 判断该表项是否重要
% 根据 Sn 的生成原理，每次判断都是读入 Sn 的首位数，判断后立即删除这一位数
if Sn(1)==1
% 若Sn(1)=1，则表示当前表项是重要的
Sn(1)=[];
% 读入后即删除该位 Sn 数据，使 Sn(2)变为 Sn(1)，进入下一次判断
% 这时的 Sn(1) 是正负符号位
if Sn(1)==1
% Sn(1)=1，则相应的系数为正数，其值为本级解码阈值的1.5倍
DecodeMat(rN,cN)=1.5*2^N;
Sn(1)=[];
else
% Sn(1)=0，则相应的系数为负数
DecodeMat(rN,cN)=-1.5*2^N;
Sn(1)=[];
end
% 将该表项添加到重要系数列表 LSP
LSP=[LSP;LIP(r,:)];
% 将该表项从 LIP 中删除
LIP(r,:)=[];
else
% 若不重要，则相应的系数值为 0
DecodeMat(rN,cN)=0;
Sn(1)=[];
% 将指针指向下一个表项
r=r+1;
end
% 判断当前 LIP 的表长
rlip=size(LIP,1);
end

3、LIS扫描解码程序

function [LSP,LIP,LIS,LisFlag,DecodeMat,N]=lis_decode(DecodeMat,N,Sn,LSP,LIP,LIS,LisFlag)
% 函数 LIS_DECODE() 根据排序位流 Sn，更新列表LIP、LSP和重构系数矩阵 DecodeMat
% 输入参数：DecodeMat —— 本级 LIP 扫描后更新的重构系数矩阵
% N —— 本级解码阈值的指数
% Sn —— 经本级 LIP 扫描截取后的排序位流
% LSP —— 经本级 LIP 扫描后更新的重要系数列表
% LIP —— 经本级 LIP 扫描后更新的不重要系数列表
% LIS —— 上一级编码生成的不重要子集列表
% LisFlag —— 上一级编码生成的不重要子集表项类型列表
% 输出参数：LSP —— 本级 LIS 扫描后更新的重要系数列表
% LIP —— 经本级 LIS 扫描处理后更新的不重要系数列表
% LIS —— 本级 LIS 扫描后更新的不重要子集列表
% LisFlag —— 本级 LIS 扫描后更新的不重要子集表项类型列表
% DecodeMat —— 本级 LIS 扫描后更新的重构系数矩阵
% N —— 下一级解码阈值的指数