基于位长四叉树的EZBC改进算法

王仁龙，阮双琛，刘承香，陈俊伟

1)深圳市激光工程重点实验室深圳大学电子科学与技术学院先进光学精密制造技术广东普通高校重点实验室，深圳518060;2)深圳大学机电与控制工程学院，深圳518060

目前，典型的内嵌小波图像编码方法主要包括基于零树结构与零块结构的编码算法［1］.零树结构编码算法充分利用不同子带内，相同空间位置的小波系数之间的相似性进行编码，以Shapiro［2］提出的嵌入式小波零树 (embedded zerotree wavelet，EZW)编码方法和Said等［3］提出的集合分裂树算法 (set partitioning in hierarchical trees，SPIHT)为代表.零块结构编码算法充分利用同一子带内不重要系数的相关性进行编码，以小波嵌入零块图像编码(wavelet embedded zero block image coding，SPECK)［4］算法为代表.JPEG2000［5］的内嵌编码与最佳截断 (embedded block coding with optimized truncation，EBCOT)［6］利用子带内小波系数之间的相关性组织高效的上下文，采用算术编码算法进行编码.

Hsiang［7-8］提出的嵌入零块和上下文模型的图像编码(embedded zeroblock coding and context modeling，EZBC)结合子带内与子带间系数的相关性，把零树 (或零块)结构和基于上下文编码的优点有机结合在一起，获得比SPIHT算法更好的压缩性能;EZBC算法采用简单高效的幅值四叉树编码结构和基于上下文的位平面编码算法，比EBCOT算法具有更高的压缩效率，平均每个像素使用的编码符号少于EBCOT算法.但是EZBC算法在编码过程中需要建立小波系数的幅值四叉树Qk［l］(i，j)、非重要节点链表LIN和重要像素链表LSP，在编码过程需占用大量内存，这是EZBC算法硬件实现的最大障碍;而由于其采用链表操作，在编码过程中需要进行大量的链表添加和删除操作，这会影响其编码速度.

针对以上问题，本研究提出一种基于位长四叉树的EZBC改进算法.该算法在采用EZBC算法的四叉树编码结构，与基于上下文的位平面编码的同时，利用位长四叉树代替EZBC算法中的幅值四叉树完成编码过程，并形成算术编码器所需的上下文，不仅保持EZBC算法高效压缩性能，还极大地减少了编码过程所需内存.实验结果表明，该算法在保持高信噪比的同时，加快编码速度，节省内存占用，易于硬件实现.

1 位长四叉树

本算法在进行位平面编码时，首先建立每个子带的位长四叉树结构.这里的位长是指量化后的小波系数绝对值对应的有效位长度，不包含符号位.令第k子带、第l四叉树级、坐标(i，j)处的节点值为 Bk［l］(i，j)，

式 (2)中，Ck(i，j)为子带k中坐标(i，j)处量化后的小波子带系数;表示x的绝对值;⎿x」表示对x的向下取整运算，例如，若x=⎿3.8」，x≡3;式中“=”用来赋值，“≡”表示判断.

图1 四叉树建立和分解示意图Fig.1 Illustration of quadtree build up and decomposition

四叉树最底层的节点由每个子带量化和缩放后，小波系数的2×2方块最大位长构成，上一层四叉树节点由当前层中相应4个节点的最大值表示，如图1(a).最上层的四叉树节点表示这个子带中所有小波系数的最大位长.本算法也是从高位平面到低位平面渐进编码.一旦节点在某位平面被判断为重要 (即节点位长大于位平面位索引值)，它将被分裂为4个子节点，此分裂过程递归进行，直至四叉树的末梢节点，如图1(b).

EZBC算法所建立的是小波系数的幅值四叉树Qk［l］(i，j)和两个链表，而本算法利用子带系数绝对值的位长建立位长四叉树，这与位平面扫描时采用的位平面位索引值一致，即可通过位长四叉树对小波系数进行快速定位和重要性判断，大大加快编码速度，而且省去LIN与LSP.同时，通常小波系数的比特位长度为16 bit，即在EZBC算法中建立的Qk［l］(i，j)每个节点需要16 bit存储;本算法中位长四叉树的每个节点用4 bit存储，因为4 bit最大表示值为15，表示其最大绝对值可达15 bit，即可表示的数值达到215-1，为32 767，经小波变换后的小波系数绝对值小于32 767，即4 bit已足够用来表示小波系数的位长，从而节省了编码过程所需的存储单元.

2 编码过程

参数定义.

ck(i，j)为子带k内坐标(i，j)处的小波子带系数;

Bk［l］(i，j)为第k子带、l级中坐标(i，j)处的位长四叉树级节点，其值定义如式(1);

Dk为子带k的四叉树级数;

Dmax为所有子带四叉树级数的最大值;

K为子带总数;

Xk为子带k在原始图像横坐标中的偏移量，从左向右为正向;

Yk为子带k在原始图像纵坐标中的偏移量，从上向下为正向;

NthPower为2的n－1次幂;

ScanBL(k，l)为对子带k内位长四叉树第l级中的不重要节点进行扫描的函数，前提是它的父节点在上一位平面已经重要;

ScanDescendant(k，l，i，j)为对节点 Bk［l］(i，j)所有后续子孙节点进行重要性扫描的函数;

ScanLSP(k)为扫描出子带k内已标示重要的小波系数函数;

OutPutDescendant(k，i，j)为对已标示为重要的2×2方块内的小波系数进行不重要系数编码输出的函数;

OutPutLSP(k，i，j)为对已标示重要的2×2方块内小波系数进行幅值细化的函数.

具体编码过程.

①初始化

②编码最高位平面

③编码剩下的位平面

具体函数伪代码如下.

本算法的编码主要针对位长四叉树进行扫描，建立的位长四叉树以2×2方块为基本单位，这就减少了编码过程位长四叉树所占用的内存.由于其建立位长的底层是从Tk(i，j)，即2×2方块的最大位长开始，不是直接从小波系数的位长开始，每个位长仅用4 bit即可，所以针对1个M×N的灰度图，其编码过程所占用内存仅为(1/4+1/16+1/64+…)×M×N×4≈M×N×4/3 bit.且由于图像的相关性，当2×2方块内的某一小波系数为重要时，基本上其余小波系数都为重要，这更有利于算法的最优截断.

3 实验结果分析

本算法与EZBC算法都是在Pentium(R)D CPU 2.80 GHz、2.79 GHz的微机上用 Visual C++6.0 进行验证，选用512×512×8 bit的标准灰度图像Lena、Goldhill和Barbara与2 048×2 560×8 bit标准灰度图像Cafe和Woman.采用9/7小波滤波器［9］，边界处理采用对称延拓［10-11］，上下文模型与文献［7］中EZBC算法相同.表1为本算法与EZBC算法在不同码率下的峰值信噪比.

表1 本算法与EZBC算法在不同码率下峰值信噪比Table 1 PSNR comparison of proposed algorithm and EZBC

由表1可知，本算法和EZBC算法具有同样的峰值信噪比，但EZBC算法是通过小波系数的幅值四叉树Qk［l］(i，j)和两个链表 (LIN和LSP)完成编码过程，并利用相邻节点和父子带节点的重要性形成上下文，所以它需要大量内存以存储幅值四叉树Qk［l］(i，j)和两个链表，且其所需内存随处理图像复杂度和编码比特率的不同而不同，这增加了硬件实现的复杂度.本算法仅利用位长四叉树就可以完成编码，并形成上下文，极大减少编码过程所需的内存.经过实验测试，对于512×512×8 bit和2 048×2 560×8 bit的图像，两种算法的内存占用情况如表2.可见，本算法仅需占用内存分别为43 Kbyte和853 Kbyte，大大小于EZBC算法所需的内存，相对EZBC算法节约90%以上.

表2 两种算法的内存占用Table 2 Memory usage comparison

EZBC算法采用链表操作，当要求压缩图像质量不太差时，编码过程中需要进行大量的链表添加和删除操作，这会影响其编码速率.本算法采用位长四叉树，利用子带系数绝对值的位长建立，与位平面扫描时采用的位平面位索引值一致，可以直接通过位长四叉树对小波系数进行快速定位和重要性判断，从而达到快速编码的目的.

结 语

本研究提出一种基于位长四叉树的EZBC改进算法，其利用位长四叉树代替EZBC算法中的幅值四叉树完成编码过程并形成算术编码器所需要的上下文，在保持EZBC算法高效压缩性能的同时，极大减少了编码过程所需内存，占用空间不到EZBC算法的10%.由于本算法通过位长四叉树对小波系数进行快速定位和重要性判断，不再采用链表操作，这就加快编码速度，有利于该算法的硬件实现.

/References:

［1］ Sudhakar R，Karthiga R，Jayaraman S.Image compression using coding of wavelet coefficients:a survey ［J］.Graphics，Vision and Image Processing，2005，5(6):25-38.

［2］ Shapiro J M.Embedded image coding using zerotrees of wavelet coefficients［J］.IEEE Transactions on Signal Processing，1993，41(12):3445-3462.

［3］ Said A，Pearlman W A.A new，fast，and efficient image codec based on set partitioning in hierarchical trees［J］.IEEE Transactions on Circuits and Systems for Video Technology，1996，6(3):243-250.

［4］ Islam A，Pearlman W A.An embedded and efficient lowcomplexity hierarchical image coder［G］//Visual Communication and Image Processing’99.San Jose(USA):SPIE Press，1999，3653:294-305.

［5］ Rabbani M，Joshi R.An overview of the JPEG2000 still image compression standard ［J］.Signal Processing:Image Communication，2002，17(1):3-48.

［6］ Taubman D.High performance scalable image compression with EBCOT ［J］.IEEE Transactions on Image Processing，2000，9(7):1158-1170.

［7］ Hsiang S T.Highly scalable subband/wavelet image and video coding［D］.New York(USA):Rensselaer Polytechnic Institute，2002.

［8］ Hsiang S T，Woods J W.Embedded image coding using zeroblocks of subband/wavelet coefficients and context modeling［C］//IEEE International Symposium on Circuits and Systems.Geneva(Switzerland):IEEE Press，2000:662-665.

［9］ Anonini M，Barland M，Mathieu P，et al.Image coding using wavelet transform ［J］.IEEE Transactions on Image Processing，1992，2(1):205-220.

［10］ KANG Zhi-wei，LIAO Jian-li，HE Yi-gang.Detection of the image edges of non-separated wavelets based on lifting scheme［J］.Journal of Huazhong University of Science and Technology Nature Science Edition，2006，34(4):56-58，62.(in Chinese)康志伟，廖剑利，何怡刚.基于提升算法的不可分离小波图像边缘检测［J］.华中科技大学学报:自然科学版，2006，34(4):56-58，62.

［11］ ZHANG Xu-dong，LU Guo-dong，FENG Jian.Fundamentals of Image Coding and Wavelet Compressing-Principles，Algorithms and Standards［M］.Beijing:Tsinghua University Press，2004:235-272.(in Chinese)张旭东，卢国栋，冯 健.图像编码基础和小波压缩技术——原理、算法和标准 ［M］.北京:清华大学出版社，2004:235-272.