多级树集合分裂(SPIHT)算法的过程详解和Matlab实现(4)编码过程——排序扫描

时间:2022-05-26 07:41:50

 本文给出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);
end

3、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 当前表项位置的指针,初始位置为1
ls=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);
    end
end
% 对 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;
end

function [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;
    end
end
if 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是输入的小波分解系数矩阵,作为全局变量,在编码的相关程序中使用
allMat=[];
isImt=0;
Sign=0;
% 默认坐标集是不重要的,且首位元素是负值
rSet=size(coefSet,1);
% 读取坐标集中各元素的系数值
for r=1:rSet
    allMat(r)=Mat(coefSet(r,1),coefSet(r,2));
    if abs(allMat(r))>=2^N
        isImt=1;
        break;
    end
end
% 对单个元素的坐标集,判断该元素的正负符号
% 由于函数 childMat() 对子孙全零的点会返回空表,所以要检查allMat是否为空
if ~isempty(allMat)&&(allMat(1)>=0)
    Sign=1;
end