EZW编码

小波变换的EZW编解码以一个8×8的原始图像为例，左图是它经过三级小波变换后所得的系数矩阵。一、要实现EZW算法，首先要了解EZW算法中的一个重要概念：零树图（1）：一幅8×8图象三级小波变换后的系数矩阵1．对图（1）颜色笔所示的路径给出了树的概念，由于小波变换要进行隔行隔列抽取，所以前一尺度的4点只能抽成后一尺度的一点，这种1∶4的关系，就形成了基本的树状结构。15106-7-1223130000000000000005-4-3232-21000140000000000000300002000000000图（1）:一幅8×8图像三级小波变换后的系数矩阵在EZW算法中，一个系数x的直接后代或称孩子节点有三种情况：（1）最低频子带LLn（n为小波变换的级数），如图（2）所示LL3的任一个系数x在HL3、LH3、HH3中的对应位置均有一个孩子节点，即LLn子带的系数共有3个孩子节点或称直接代；（2）最高频的三个子带HL1、LH1、HH1，均无后代：（3）除上述两种情况外，其它各子带的一个系数x在相邻高频子带的相应位置都有4个系数与之对应，且称该4个系数为孩子节点或直接后代。图（2）：一幅图象三级小波变换后的系数结构LL3HL3HH3LH3HL2HL1HH2LH2LH1HH1有了这三种基本情况，当我们把一个系数x作为一个树根考察时，它的后代就包括直接后代（也称孩子节点）以及这些孩子节点的后代。根据考察点的位置不同，这棵树的层次（或高矮）也不一样，可以是中的一种，或者是或它的扩展。●●●2．重要系数与不重要系数对于一给定的阈值T1，如果系数x的绝对|x|≥T1，则称x为重要系数，否则，为不重要系数。3．零树的概念、对于一给定的阈值T1，如果该系数x本身和它的所有后代都小于T1，则称这棵树为一零树，该系数就为零树根。必须注意：在有了被称为零树根的节点x后，它的所有后代节点就不能再是零树根，如例子中的及23456和0000000002000030他们相对于阈值T1≈8来说，都不重要，所以6是一个零树根，但对于－4和它的后代，对8来说也都不重要，但这时不能说－4是零树根，因为－4是零树根6的后代。0200158P108P-128-78I68Z根283818Z根Z根Z根N3828-2818ZZZI根根根58-48-3828跳跳全跳跳跳跳000000008148ZZZ干干干干080800000000000000000P38028000000080000083808000跳跳ZZZZ枝枝孤孤二、EZW算法的基本步骤：（1）设定阈值T1→用来判断重要性，即T1=2n，n=（2）主扫描→找出XT1的重要系数，并放入副表中；（3）副扫描→对放入副表中的重要系数以1.5T1为界，高者编1，低者编0。目的是将区间细分，为解码复原创造条件。max2log||2X（一）首先计算阈值T1，对例子中的系数矩阵，∵Xmax=15:而n=∴T1=23=8（二）接着进行第一轮主扫描：扫描顺序如图（3）箭头所示，从低频子块到高频子块，在每个子块里都从左到右从上到下一行一行地扫描。图（3）：扫描顺序215log32|x|≥T符号？是零树根的后代？该系数的所有后代还有无重要系数？YNY跳过，不予编码N无用ZTR对x编码有用IZ对x编码－+用POS对x编码并把绝对值放入副表中用NEG对x编码并把绝对值放入副表中对系数x图（4）：编码扫描每个系数x时的处理流程规则：①对大于T的正值编成P，负值编成N;②对小于T的零树，大小之根都编成ZTR，而对零树的干枝叶都跳过不编；③对孤立零不论那级的都编成IZ（即为根）（即为孤零）有扫描顺序和对扫描点系数的处理流程，下面对例子进行第一轮主扫描。①对LL3：∵|15|T1=8且是“+”号∴将15编成POS并放入副表中；②对HL3：∴|10|8且是“+”号∴将10编成POS，并放入副表中；③对LH3：∵|－7|8又不是零树根的后代而它的后代，8无重要系数但有1223000000000000000140000|14|8，即该系数-7的后代中有重要系数14∴将-7编码成IZ④对HH3：∵|6|8又不是零树根的后代而它的后代8都无重要系数∴将6编码成ZTR030054002083200000000和⑤对HL2：∵|―12|8且是“－”号∴将-12编成NEG，并放入副表中∵|2|8又不是零树根的后代而它的后代8都无重要系数∴将2编成ZTR∵|3|8又不是零树根的后代而它的后代8都无重要系数∴将3编成ZTR∵|1|8又不是零树根的后代而它的后代8都无重要系数∴将1编成ZTR000000000000⑥对LH2：∵|3|8又不是零树根的后代而它的后代8都无重要系数∴将3编成ZTR∵|2|8又不是零树根的后代而它的后代中的|14|8,∴将2编成IZ∵|-2|8又不是零树根的后代而它的后代8都无重要系数∴将-2编成ZTR∵|1|8又不是零树根的后代而它的后代8都无重要系数∴将1编成ZTR00000000000001400⑦对HH2：∵|5|8∵|―4|8∵|―3|8∵|2|8⑧对HL1：∵|3|8又不是零树根的后代且它已无后代∴将3编成ZTR∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR又都是零树根6的后代，∴跳过，不予编码；∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR需要说明的是在这里，HL1为：所划圈的三个部分已分别是HL2子带中2，3，1系数的后代，且这三个系数已编码为零树根，所以划圈的这三部分都不进行编码。3000000000000000⑨LH1：与HL1相似，它的中所划圈的这三个部分已是零树根3，―2，1系数的后代，因此不需编码，所以只对未划圈的4个系数编码。即：∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR∵|14|8且是“+”号∴将14编成POS，并放入副表中0014000014000000000000∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR∵|0|8又不是零树根的后代且它已无后代∴将0编成ZTR⑩HH1：因为HH1子代中所有系数都是HH3子带中系数6的后代，而6已被编码为零树根，所以对这HH1中的系数均跳过，不予编码。到此为止，第一轮主扫描工作已做完。即已把XT1的重要系数放入副表中。（三）．第一轮副扫描：对T1=8时，其副表中的绝对值肯定处于8—16之间，为此我们把处于12（即1.5T1）以下的实际值编为0，处于12及以上的实际值编为1，以对区间进行细化，其编码规则如图（5）所示，结果如表（1）所示。最后将这些0，1序列排在原已编过码的四类符号之后，对前例而言，经一轮编码后的码字就为PPIZ；NZZZ；ZIZZ；ZZZZ；ZPZZ；1011。即15,10,-7,6；-12,2,3,1；3,2,-2,1；3,0,0,0；0,14,0,0；15,10,-12,14。为了把更重要的信息放在更前面，在每次副扫描后都要进行副表的重排序工作，为使编、解码对应，应从解码方的角度对副表进行重排序。例如，这里我们通过对副扫描的0、1编码已经知道：15、12、14被编码为1，是处[12~16）区间，而10被编码为0，则处于[8~12）区间，我们认为系数绝对值越大的就越重要，所以应把原副表进行重排序，显然，被编码成0的10应排到副表最后。而对于12和14，因为都编码为1，这时从解码方的角度就还无法辨别其大小，所以它们之间的顺序仍保持不变。则经重排序后的结果如表（2）所示。（四）．第二轮主扫描：这里需要注意的是，对前面扫描过程中已经确定的重要系数就不再扫描，且他的细节信息在随副扫描进行而增加，并把它对应的位置赋成0。为了与原来的0有所区别，这里用表示，在下轮中是值为0，而不是零树的跟，最多是零树中干、枝、叶的一部分。如图（6）所示。并设第二轮的阀值。128422TT-7464243414Z根Z根Z3424-2414ZZZ根根根54-4=4-3424跳跳跳跳000000000004000004000004040000034042404000000400000404340240跳跳N根ZPPNZ根Z根跳ZZZZZZZZ跳跳ZZZZ根①对LL3：是不予编码②对HL3：是不予编码③对LH3：∵|―7|4且是“－”号∴将-7编成NEG，并放入副表中。④对HH3：∵|6|4且是“+”号∴将6编成POS，并放入副表中。⑤对HL2：∵不予编码∵|2|4又不是零树根的后代而它的后代4都无重要系数∴将2编成ZTR0000∵|3|4又不是零树根的后代而它的后代4都无重要系数∴将3编成ZTR∵|1|4又不是零树根的后代而它的后代4都无重要系数∴将1编成ZTR⑥对LH2：|3|4又不是零树根的后代而它的后代4都无重要系数∴将3编成ZTR|2|4∵不是零树根的后代而它的后代4都无重要系数∴将2编成ZTR0000000000000000表示:|―2|4∵不是零树根的后代而它的后代4都无重要系数∴将-2编成ZTR|1|4∵不是零树根的后代而它的后代4都无重要系数∴将1编成ZTR00000000⑦对HH2：|5|4且是“+”号∴将5编成POS，并放入副表中|―4|=4且是“－”号∴将-4编成NEG，并放入副表中|―3|4∵不是零树根的后代而它的后代4都无重要系数∴将-3编成ZTR|2|4∵不是零树根的后代而它的后代4都无重要系数∴将2编成ZTR00000000⑧对HL1：注意，这里所划圈的部分均是子带HL2中零树根2，3，1的后代，所以不予扫描，而对于剩下的，因它的父节点HL2处是个，虽然我们对此已赋值为0，但该轮未对它进行扫描即它肯定不是零树根，所以对的后代4个系数还要进行扫描编码。|3|4∵不是零树根的后代且它已无后代且它已对无后代∴将3编成ZTR；00033000000000000000|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR；|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR；|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR。⑨对LH1：均是零树根的后代，所以无需编码⑩对HH1：因划圈部分分别是HH2子带中0000000000000000300002000000000零树根―3和2的后代，所以不予编码，对剩下的8个系数，因它的父节点在HH2处不是零树根，所以还得编码。|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR|3|4∵不是零树根的后代且它已无后代∴将3编成ZTR|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR|0|4∵不是零树根的后代且它已无后代∴将0编成ZTR|2|4∵不是零树根的后代且它已无后代∴将2编成ZTR