小波零树编码算法的改进与实现.pdf

第3 4 卷第2 期 2 0 0 5 年3 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g8 LT e c h n o l o g y V 0 1 ．3 4N o ．2 M a r ．2 0 0 5 文章编号1 0 0 0 1 9 6 4 2 0 0 5 0 2 0 2 4 2 0 4 小波零树编码算法的改进与实现 陈豫 武汉大学计算机学院，湖北武汉4 3 0 0 7 2 摘要在嵌入式小波零树编码理论的基础上，探讨了一种改进的图像编码算法．通过结合空间方 向树结构的分层树集合分割排序编码理论，继承了原小波零树编码算法的逐次逼近量化的思想． 改进算法仍然采用了一种零树结构，但不仅把零树作为一个集合，而且把剩余树也作为一个集合 进行处理．这样，被去除的节点存储在另一集合里，将不被重复扫描，从而提高了压缩的效率．实 验仿真证明，这种改进编码算法能在一定程度上提高图像压缩效率和编码质量． 关键词小波变换；零树；峰值信噪比；熵编码 中图分类号T N9 1 9 ．8 1文献标识码A I m p r o v e m e n ta n dI m p l e m e n t a t i o n o fW a v e l e tZ e r o T r e eC o d i n gA l g o r i t h m C H E N GY U S c h o o lo fC o m p u t e rS c i e n c e s ，W u h a nU n i v e r s i t y ，W u h a n ，H u b e i4 3 0 0 7 2 ，C h i n a A b s t r a c t B a s e do nt h ee m b e d d e dw a v e l e tz e r o t r e ec o d i n ga l g o r i t h m ，a ni m a g ec o d i n ga l g o r i t h m ， i m p r o v e dw a v e l e tz e r o - t r e ec o d i n ga l g o r i t h m ，w a sp r o p o s e d ．T h r o u g hc o m b i n i n gt h eh i e r a r c h i c a ．1 c l a s s i f i c a t i o nt r e ep a r t i t i o ns o r t i n gc o d i n gp r i n c i p l eo fs p a c ed i r e c t i o nt r e e s ，t h ei m p r o v e da l g o r i t h m i n h e r i t st h es u c c e s s i v ea p p r o x i m a t i o nt h o u g h to ft h e ‘w a v e l e tz e r o - t r e ec o d i n ga l g o r i t h m ．T h i s a l g o r i t h ma l s oa d o p t st h ez e r o - t r e es t r u c t u r e ，b u td i s t i n g u i s h e df r o mi t so r i g i na l g o r i t h m ，i tt a k e s n o to n l yt h ez e r o t r e eb u ta l s ot h er e s tt r e e sa sas e t ．A sar e s u l t ，t h ei m p r o v e da l g o r i t h mc a nr a i s e t h ee f f i c i e n c yo fi m a g ec o m p r e s s i o ns i n c ei tn e e dn o ts c a nt h o s ew i p e d o f fp o i n t ss t o r e di nt h eo t h e r s e t ．T h es i m u l a t i o nh a sp r o v e dt h a tt h ei m p r o v e dw a v e l e tz e r o - t r e ec o d i n ga l g o r i t h mc a ni m p r o v e t h ee f f i c i e n c ya n dq u a l i t yo fc o m p r e s s e di m a g e st os o m ee x t e n t ． K e yw o r d s w a v e l e tt r a n s f o r m ；z e r o - t r e e ；P S N R p e a ks i g n a ln o i s er a t i o ；e n t r o p yc o d i n g 小波变换是一种新的变换分析方法，是近年来 得到迅速发展的一种新的信号处理方法，它解决了 很多传统的傅里叶变换所不能解决的突变信号与 非平稳信号的问题．嵌入式零树小波编码算法是 S h a p i r o 在1 9 9 3 年提出的基于小波变换的逼近量 化的图像编码方法．近年来，随着对零树编码的重 视，已经使得零树方法成为基于小波的图像压缩技 术的研究热点．本文针对原零树小波编码算法的一 些弊端，改进了重要图的表示方法，采用空间方向 树结构，利用分层树集合分割排序编码来改进原有 的零树结构，提高编码的速率和效率． 1 零树编码 零树编码值是较大标志位编码与细节编码之 和．零树编码方法[ 1 ] 由小波变换、零树量化和熵编 码3 部分构成．一幅图像经过小波分解后，其结构 呈金字塔形状，其中的系数则呈树状结构．研究表 明如果一个低频小波系数小于某个阈值丁，则在 空间相同方向和相同位置，较高频率上的所有小波 系数也极有可能小于T ．利用这种相关性，可以由 收稿日期2 0 0 4 0 6 0 1 作者简介陈豫 1 9 7 0 一 ，女，湖南省津市县人，讲师，博士研究生，从事图形图像处理和网络数据库体系结构方面的研究． 万方数据 第2 期陈豫小波零树编码算法的改进与实现2 4 3 低频子带系数来预测高频子带系数，零树编码正是 基于这种相关性的编码方法．简单的说，零树编码 结构就是一个父系数 这里所提到的系数全部是小 波系数 有4 个子系数的树结构．而这些子系数又 依次轮流做为一个父系数，又有4 个子系数，如此 下去，从父到子在一颗零树中的每个系数的绝对值 成递减趋势．这就是小波零树编码算法的一个重要 的特性．因为如果发现某个小波系数是不重要的， 那么它的所有子系数也将是不重要的了，并且这个 分支被确信不包含任何重要的信息了．用这种方 法，整个树结构就会被编码成一个单一的符号，达 到数据压缩的目的．零树编码流程框图如图1 所 示[ 2 1 ． 输入系数 图1 零树编码流程图 F i g ．1 Z e r o - t r e ec o d i n gf l o wc h a r t 一般，小波系数被扫描的次序也是很重要的． 首先，扫描时那些在更低层子带的系数应该优先 于更高层的子带．对于不重要小波系数编码，这种 排序的目的就是利用零树结构获得最大限度的编 码效率．然而，虽然在小波变换系数中，零树是有效 地表示了不重要系数的数据结构，但是它还是存在 着很大的树间冗余，这就给了我们可改进的空间． 2 小波零树算法的改进与实现 采用空间方向树结构，利用分层树集合分割排 序编码来改进原有的零树结构，可以提高编码的速 率和效率[ 3 。5 ] ． 首先，定义几个重要的符号概念 y 1不重要集合表包含所有量值小于预先 设定的阈值丁 丁一2 t t 挖一L l b m a x f ．D { k 川 ．】 的 小波系数，此定义为不重要的系数．但这个集合里 不包括所有的子代根结点，并且至少要有4 个元 素； Y 2 不重要系数表包含单个量值小于阈值 丁的小波系数； Y 3重要系数表包含所有量值大于阈值T 的小波系数； z i ，歹 小波变换后的系数矩阵结点 i ， 歹 ．ⅣⅣ的子代结点； M i ，．j 结点 “．， ．ⅣⅣ的所有子孙结点； N i ，歹结点 i ，_ 『 ⅣⅣ所有子孙结点中除子 代结点外的结点． 算法的具体实现步骤如表1 所示． 表1改进算法的实现步骤 T a b l e1T h ei m p l e m e n ts t e p so fi m p r o v e da l g o r i t h m M 0 ，1 2 。O ． 2 ，1 b 3 ，O 改变类型 2 ，0 到Y 2 2 ，1 到Y 2 3 ，O 到Y 2 y 1 一{ 1 ，0 A ， 1 ，1 A ， 0 ，1 B } y 2 一{ 1 ，O ， 1 ，1 ， O ，3 ， 1 ，Z ， 1 ，3 ， 2 ，O Y 2 { 1 ，O ， 1 ，1 ， 0 。3 ， 1 ，2 ， 1 。3 。 2 ，O ， 2 。1 Y 2 { 1 ，O ， 1 ，1 ， O ，3 ， 1 ，2 ， 1 ，3 ， 2 ，O ， 2 ，1 ， 3 ，0 } 3 ，1 0 3 ，1 到Y 2Y 2 一{ 1 ，o ， 1 ，1 ， o ，3 ， 1 ，2 ， 1 ，3 ， 2 ，o ， 2 ，1 ， 3 ，o ， 3 。1 改变类型 Y 1 { 1 ，1 A ， o ，1 B ． 1 ，0 B 6M 1 ，1 o 无Y 1 一{ 1 ，1 A ， O ，1 B ， 1 ，0 B 7N 0 ，1 0无Y 1 一{ 1 ，1 A ， 0 ，1 B ， 1 ，0 B } 万方数据 2 4 4 中国矿业大学学报第3 4 卷 首先，初始化集合．这里把初始阈值丁。设为 3 2 ．标记 i ，j A 和 i ，j B 指出了集合y 1 的入口是 ‘A ’型还是‘B ’型，A 表示该结点的子代有可能重 要，B 表示该结点的子代不重要，但后面的孙代等 可能重要．另外，集合Y 1 中不包含根结点，例如系 数 o ，o 作为一个根就不包含在内．然后，我们就可 以开始在集合Y 2 中对单个像素的重要性进行编 码．当扫描时发现一个系数大于阈值T 而被确定 为重要的后，则将其放人集合Y 3 中，同时对它的 符号也一样要进行编码 重要的就输出比特位“1 ”， 不重要的就输出比特位“0 ” ．在这里，我们用标记 1 0 和1 1 分别表示一个比特1 后的符号为“ ”和 “一”．在测试了单个像素后，接下来就是整个集合 的测试，依次轮流的考察y 1 中的元素 在表1 中 以黑体字母标出 ．例如，M 0 ，1 是2 0 个系数的集 合，即{ o ，2 ， o ，3 ， 1 ，2 ， 1 ，3 ， 0 ，4 ， 0 ，5 ， 0 ，6 ， 0 ，7 ， 1 ，4 ， 1 ，5 ， 1 ，6 ， 1 ，7 ， 2 ，4 ， 2 ，5 ， 2 ，6 ， 2 ，7 ， 3 ，4 ， 3 ，5 ， 3 ，6 ， 3 ，7 } ． 由于M 0 ，1 是重要的系数，那么我们就将测试它 的4 个子代{ o ，2 ， O ，3 ， 1 ，2 ， 1 ，3 的重要 性．在所有的子代都被测试之后，结点 o ，1 就被移 到了Y 1 中的最后，如表1 所示．同时，‘A ，型就被 改变成了‘B ’型，这也就意味着新的Y 1 人口就由 M o ，1 变成了N 0 ，1 ．接着对于M 1 ，o 重复上 述的做法注意尽管 1 ，o 没有子代是重要的，但由 于N 1 ，o 是重要的，所以M 1 ，o 也是重要的．因 为M 1 ，1 是不重要的，这时我们就没有必要继续 往下测试了． 接下来，在y 1 中进行下一个元素的测试下 一个集合y 1 元素 o ，1 是‘B ，型，所以N 0 ，1 是 被测试过的．应该注意的是坐标 o ，1 从y 1 的开 始往后移，现在又再一次的被测试，但和上一次被 测试的意义已不一样．与上述一样，由于N 1 ，o 是重要的，因此这个集合又被分裂成M 2 ，o ，M 2 ，1 ，M 3 ，o 和M 3 ，1 ，并且新加入到y 1 中． 与此同时， 1 ，0 B 从y 1 中删除．然后对新加入y 1 中的元素进行测试，首先是M 2 ，O ，和前面一样 做同样的处理，子代 2 ，1 被测试．既然这样，因为 N 2 ，1 巧 没有孙代而不是没有子代 ，所以 2 ， 1 A 从y 1 中删除 而不是将它的‘A ’型改为‘B ’ 型 ．于是，测试最后两个新加入的元素M 3 ，o 和 M 3 ，1 ，由于它们是不重要的，因此排序过程在对 y 1 中的最后的元素测试后而结束．将阈值丁减 半，进行新一轮的排序扫描过程，如此下去，直到达 到满意的效果为止． 对于原算法，我们继承了它的逐次逼近量化的 思想，还是采用了一种零树的结构，只是改进的算 法不但把零树作为一个集合，而且把剩余树也作为 一个集合来进行处理．被去除的节点存储在另一集 合里，将不被重复扫描，从而提高了压缩的效率． 此外，如果不进行任何的熵编码，在第一次的 排序过程后编码输出了2 9 个比特位．实验中，我们 采用的是自适应算术编码方法，如下面的仿真实验 结果所示． 3 实验结果 在实验中，我们用原小波零树算法同改进的算 法做比较，用L e n a 2 5 6 2 5 6 比特率在0 ．3B i t s ／ P i x e l 时的压缩效率加以说明．其结果如图2 所示． 图2 是在比特率为0 ．3B i t s ／P i x e l 时的压缩编 码后的效果图，图2 a 是原始图像L e n a 2 5 6 2 5 6 ，图2 b 是经小波三层分解后的小波零树解码 图，图2 c 是经小波零树编码后的恢复图，图2 d 是 经改进的算法编码后的恢复图． 实验结果表明，本文实现的算法较原来编码效 率有进一步提高，比较后的指标参数如表2 所示． 万方数据 第2 期陈豫小波零树编码算法的改进与实现2 4 5 a b c I d 图2 仿真结果 F i g ．2 S i m u l a t i o nr e s u l t 表2 改进算法与原算法的对比[ 2 ] 郑勇，周正华，朱维乐．一种快速零树编码的小波图 T a b l e2T h ec o m p a r eb e t w e e no r i g i na l g o r i t h m a n di m p r o v e da l g o r i t h m 4 结论 实验证明，本文针对原零树小波编码算法的一 些弊端，改进了重要图的表示方法，采用空间方向 树结构，利用分层树集合分割排序编码来改进原有 的零树结构，提高了编码的速率和效率．本文所阐 述的这种算法的实现在一定程度上解决了小波零 树算法在重复扫描重要图以及存在树间冗余等弊 端问题，能够进一步提高图像编码的效率． 参考文献 [ 1 ] 柳斌，田金文，柳健．一种基于零树量化的小波变 换图像压缩方法口] ．华中理工大学学报，2 0 0 0 ，2 8 3 6 8 7 0 ． L i uB ，T i a nJW ，L i uJ ．I m a g ec o m p r e s s i o na l g o r i t h m b a s e do nz e r o t r e eo fw a v e l e tc o e f f i c i e n t s [ J ] ．J ． H u a z h o n gU n i v ．o fS c i T e c h ，2 0 0 0 ，2 8 3 6 8 7 0 ． 像压缩算法[ J ] ．电子科技大学学报，2 0 0 1 ，3 0 4 3 3 1 3 3 4 ． Z h e n gY ，Z h o uZH ，Z h uWL ．Ac o m p r e s s i o n a l g o r i t h mo fw a v e l e ti m a g ew i t hf a s tz e r o t r e ee n c o d i n g [ J ] ．J o u r n a lo fU E S To fC h i n a ，2 0 0 1 ，3 0 4 3 3 1 3 3 4 ． [ 3 ]张素文，杭小庆，王天珍．一种改进的零树编码方法 [ J ] ．武汉理工大学学报，2 0 0 1 ，2 3 3 9 - 1 2 ． Z h a n gSW ，H a n gXQ ，W a n gTZ ．A ni m p r o v e d i m a g ec o m p r e s s i o na l g o r i t h mb a s e do nz e r o t r e eo f w a v e l e tc o e f f i c i e n t s [ J ] ．J o u r n a lo fW u h a nU n i v e r s i t y o fT e c h n o l o g y ，2 0 0 1 ，2 3 3 9 - 1 2 ． [ 4 ] 陈淑珍，刘志军，宋维维，等．改进的静止图像小波零 树编码[ J ] ．武汉大学学报，2 0 0 2 ，4 8 1 1 1 1 1 1 5 ． C h e n SZ ，L i uZJ ，S o n gWW ，e ta 1 ．I m p r o v e d w a v e l e tz e r o t r e es t i l li m a g ec o d i n g [ J ] ．W u h a n U n i v e r s i t yJ o u r n a l ，2 0 0 2 ，4 8 1 1 1 1 - i 1 5 ． [ 5 ] 王祥林，林行刚，吴国威．改进的图像多分辨率零树小 波编码算法[ J ] ．通信学报，1 9 9 7 ，1 8 4 5 0 一5 3 ． W a n gXL ，L i nXG ，W uGW ．I m p r o v e dz e r o t r e e w a v e l e ti m a g ec o d i n gw i t hm u l t i r e s o l u t i o n [ J ] ． J o u r n a lo fC h i n aI n s t i t u t eo fC o m m u n i c a t i o n s ，19 9 7 ， 1 8 4 5 0 5 3 ． 责任编辑邓群 万方数据