EZW算法的过程详解和Matlab代码

EZW算法的过程详解和Matlab代码（1）构建扫描次序表（修正小波树结构）我们以一幅16*16的Lena局部图像经过3级小波分解后的小波数据为例详细的说明EZW算法的编解码过程，并给出相应的Matlab代码。原始图像如下分解后的小波图像数据为：一、在开始编码之前，首先要求出初始阈值T1：MaxDecIm=max(max(abs(DecIm)));T=zeros(1,codeDim);T(1)=2^flor(log2(MaxDecIm));二、然后是建立小波树结构，构建扫描次序表。这个扫描次序表非常重要，后面的编码、解码过程都要按照扫描次序表逐个处理数据矩阵的各个元素。构建过程如下：用（r，c）表示数据矩阵上各元素的位置。row、col作为全局变量，表示数据矩阵的行、列数。1、小波树结构的特点：（1）对于LL-N低频子带的点(r,c)，有3个孩子：(r,c+W)、(r+H,c)和(r+H,c+W)，其中W、H分别是LL-N子带的宽和高；（2）第N~2高频子带(LH、HL、HH)的点都有4个孩子，即：tp=[2*r-1,2*c-1;2*r-1,2*c;2*r,2*c-1;2*r,2*c];（3）第1高频子带的点没有孩子。根据小波树的这个特点，可编写如下“小波树”函数treeMat()，输入矩阵内任一点的位置（r，c），给出该点的子孙列表cp。functioncp=treeMat(r,c)%这个函数是一个递归函数globalrowcoldim%dim是小波分解级数HLL=row/2^dim;WLL=col/2^dim;if(r=HLL)&&(c=WLL)tp1=[r,c+WLL;r+HLL,c;r+HLL,c+WLL];cP=[tp1;treeMat(r,c+WLL);treeMat(r+HLL,c);treeMat(r+HLL,c+WLL)];elseif(rrow/2)||(ccol/2)cP=[];elsetp=[2*r-1,2*c-1;2*r-1,2*c;2*r,2*c-1;2*r,2*c];tm1=[];tm2=[];tm3=[];tm4=[];if(tp(4,1)=row/2)&&(tp(4,2)=col/2)t1=treeMat(tp(1,1),tp(1,2));tm1=[tm1;t1];t2=treeMat(tp(2,1),tp(2,2));tm2=[tm2;t2];t3=treeMat(tp(3,1),tp(3,2));tm3=[tm3;t3];t4=treeMat(tp(4,1),tp(4,2));tm4=[tm4;t4];endcP=[tp;tm1;tm2;tm3;tm4];end示例，当row=8，col=8，dim=2时，LL-N低频子带的点(1,1)(1,2)(2,1)(2,2)的子孙分布如下：由这个小波树列表tree_p，我们可以进一步构建函数childMat()，给出矩阵数据Mat和矩阵任一点的位置（r，c），返回该点的子孙数据列表chMat。functionchMat=childMat(Mat,chRows,chCols)globalrowcoldimchPoint=treeMat(chRows,chCols);chMat=[];[mRows,mCols]=size(chPoint);foriRows=1:mRowschMat=[chMat;chPoint(iRows,1),chPoint(iRows,2),Mat(chPoint(iRows,1),chPoint(iRows,2))];end2、构建扫描次序表本文EZW算法的扫描次序为Morton式，其特征是从（1，1）开始，每4个点组成一个“Z”型扫描单元，从微观到宏观上都是严格的“Z”型结构，可以用递归方法来构建扫描次序表。扫描次序表scanlist由两部分组成，一个是将数据矩阵Mat按照morton扫描次序转换成数据列表matlist，一个是按照扫描次序组成的矩阵各点位置的（r，c）列表lsorder。functionscanlist=morton(Mat)globalrowcolmatlist=mat2list(Mat);scanorder=listorder(row,col,1,1);scanlist=[];fori=1:row*colscanlist=[scanlist;iscanorder(i,:)matlist(i)];endfunctionmls=mat2list(Mat)%该函数为递归函数[r,c]=size(Mat);if(r==2)&&(c==2)mls=[Mat(1,1);Mat(1,2);Mat(2,1);Mat(2,2)];elseM1=Mat(1:r/2,1:c/2);M2=Mat(1:r/2,c/2+1:c);M3=Mat(r/2+1:r,1:c/2);M4=Mat(r/2+1:r,c/2+1:c);lt1=mat2list(M1);lt2=mat2list(M2);lt3=mat2list(M3);lt4=mat2list(M4);mls=[lt1;lt2;lt3;lt4];endfunctionlsorder=listorder(mr,mc,pr,pc)%该函数为递归函数lso=[pr,pc;pr,pc+mc/2;pr+mr/2,pc;pr+mr/2,pc+mc/2];mr=mr/2;mc=mc/2;lm1=[];lm2=[];lm3=[];lm4=[];if(mr1)&&(mc1)ls1=listorder(mr,mc,lso(1,1),lso(1,2));lm1=[lm1;ls1];ls2=listorder(mr,mc,lso(2,1),lso(2,2));lm2=[lm2;ls2];ls3=listorder(mr,mc,lso(3,1),lso(3,2));lm3=[lm3;ls3];ls4=listorder(mr,mc,lso(4,1),lso(4,2));lm4=[lm4;ls4];endlsorder=[lso;lm1;lm2;lm3;lm4];len=length(lsorder);lsorder=lsorder(len-mr*mc*4+1:len,1:2);嵌入式小波零树（EZW）算法的过程详解和Matlab代码（2）编码过程首先根据实际需要确定扫描次数D=codeDim，然后进行D次主扫描和辅扫描。1、初始化首先获取扫描次序表scanlist，表中每行的数字依次是该元素的（1）扫描序号、（2）对应于数据矩阵中位置的行号r、（3）对应于数据矩阵中位置的列号c、（4）值Mat（r，c），即scanlist(i)=[i,r,c,Mat(r,c)]编码扫描的对象就是次序表scanlist，而非数据矩阵Mat。然后构建初始符号矩阵flagMat，其中每个元素均为字符“Z”。2、主扫描在第d次（1=d=codeDim）扫描中，输入阈值为T（d），首先依次对次序表的每一行scanlist(i)按照如下步骤扫描：（1）如果上一次扫描得到的flagMat中，处于位置（r，c）的符号为“O”，则表示相应的Mat（r，c）是重要的，不需要通过本次扫描再次编码，故作跳过处理。（2）将scanlist(i,4)（即Mat(r,c)）的绝对值与阈值T(d)比较，如果是重要的系数，则令flagMat(r,c)的值为P或N，并存入主扫描表scancode中，并将Mat(r,c)的值以及相应的行、列数（r，c）存入重要数列表imptvalue中，将符号P或N存入重要数符号列表imptflag中。（3）如果是不重要的系数，则首先检查flagMat(r,c)，若是符号“X”，则表示这个点是不重要的，作跳过处理不再扫描。（4）如果点（r，c）处于第一分解级，即rrow/2或ccol/2，没有子孙系数，且其系数是不重要的，则该点flagMat的符号为Z，存入主扫描表scancode中。（5）如果点（r，c）满足rrow/2且ccol/2，则检查其子孙系数中是否有重要系数。有，则flagMat(r,c)的值为字符Z，存入主扫描表scancode中；否则flagMat(r,c)的值为T，存入主扫描表scancode中，并令其所有子孙系数相应的flagMat(r’,c’)值为字符X，不再作下一次扫描。至此，扫描结束。然后，将扫描后得到的符号矩阵flagMat转存到scanflag中，再将flagMat中的字符P、N都置换为O，字符X和T都置换为Z，使得flagMat的元素只有字符O、Z两种，作为输出到下一次扫描中使用。function[imptvalue,imptflag,scancode,scanflag,flaglist]=mainscan(Mat,scanlist,flaglist,imptvalue,imptflag,threshold)globalrowcolscancode=[];fori=1:row*colifflaglist(scanlist(i,2),scanlist(i,3))=='O'continue;elseifabs(scanlist(i,4))=thresholdifscanlist(i,4)=0flaglist(scanlist(i,2),scanlist(i,3))='P';scancode=[scancode'P'];imptvalue=[imptvalue;abs(scanlist(i,4)),scanlist(i,2),scanlist(i,3)];imptflag=[imptflag'P'];elseflaglist(scanlist(i,2),scanlist(i,3))='N';scancode=[scancode'N'];imptvalue=[imptvalue;abs(scanlist(i,4)),scanlist(i,2),scanlist(i,3)];imptflag=[imptflag'N'];endelseifflaglist(scanlist(i,2),scanlist(i,3))=='X'continue;elseifirow*col/4scancode=[scancode'Z'];else[chImt,chMat]=childImportant(Mat,scanlist(i,2),scanlist(i,3),threshold,flaglist);ifchImtflaglist(scanlist(i,2),scanlist(i,3))='Z';scancode=[scancode'Z'];elseflaglist(scanlist(i,2),scanlist(i,3))='T';scancode=[scancode'T'];[rowch,colch]=size(chMat);forr=1:rowchifflaglist(chMat(r,1),chMat(r,2))~='O'flaglist(chMat(r,1),chMat(r,2))='X';endendendendendendscanflag=flaglist;forr=1:rowforc=1:colswitchflaglist(r,c)case{'P','N'}flaglist(r,c)='O';case{'X','T'}flaglist(r,c)='Z';endendendfunction[chImt,chMat]=childImportant(Mat,chRows,chCols,threshold,flaglist)globalrowcolchMat=childMat(Mat,chRows,chCols);ifmax(abs(chMat(:,3)))=thresholdchImt=1;elsechImt=0;end3、辅扫描辅扫描是对输出符号为P和N的系数进行量化，并将量化符号存入辅扫描表quantiflag中。在主扫描中，将输出符号为P和N的系数的符号信息和