基于位長(zhǎng)四叉樹的EZBC改進(jìn)算法

王仁龍，阮雙琛，劉承香，陳俊偉

1)深圳市激光工程重點(diǎn)實(shí)驗(yàn)室深圳大學(xué)電子科學(xué)與技術(shù)學(xué)院先進(jìn)光學(xué)精密制造技術(shù)廣東普通高校重點(diǎn)實(shí)驗(yàn)室，深圳518060;2)深圳大學(xué)機(jī)電與控制工程學(xué)院，深圳518060

目前，典型的內(nèi)嵌小波圖像編碼方法主要包括基于零樹結(jié)構(gòu)與零塊結(jié)構(gòu)的編碼算法［1］.零樹結(jié)構(gòu)編碼算法充分利用不同子帶內(nèi)，相同空間位置的小波系數(shù)之間的相似性進(jìn)行編碼，以Shapiro［2］提出的嵌入式小波零樹 (embedded zerotree wavelet，EZW)編碼方法和Said等［3］提出的集合分裂樹算法 (set partitioning in hierarchical trees，SPIHT)為代表.零塊結(jié)構(gòu)編碼算法充分利用同一子帶內(nèi)不重要系數(shù)的相關(guān)性進(jìn)行編碼，以小波嵌入零塊圖像編碼(wavelet embedded zero block image coding，SPECK)［4］算法為代表.JPEG2000［5］的內(nèi)嵌編碼與最佳截?cái)?(embedded block coding with optimized truncation，EBCOT)［6］利用子帶內(nèi)小波系數(shù)之間的相關(guān)性組織高效的上下文，采用算術(shù)編碼算法進(jìn)行編碼.

Hsiang［7-8］提出的嵌入零塊和上下文模型的圖像編碼(embedded zeroblock coding and context modeling，EZBC)結(jié)合子帶內(nèi)與子帶間系數(shù)的相關(guān)性，把零樹 (或零塊)結(jié)構(gòu)和基于上下文編碼的優(yōu)點(diǎn)有機(jī)結(jié)合在一起，獲得比SPIHT算法更好的壓縮性能;EZBC算法采用簡(jiǎn)單高效的幅值四叉樹編碼結(jié)構(gòu)和基于上下文的位平面編碼算法，比EBCOT算法具有更高的壓縮效率，平均每個(gè)像素使用的編碼符號(hào)少于EBCOT算法.但是EZBC算法在編碼過程中需要建立小波系數(shù)的幅值四叉樹Qk［l］(i，j)、非重要節(jié)點(diǎn)鏈表LIN和重要像素鏈表LSP，在編碼過程需占用大量?jī)?nèi)存，這是EZBC算法硬件實(shí)現(xiàn)的最大障礙;而由于其采用鏈表操作，在編碼過程中需要進(jìn)行大量的鏈表添加和刪除操作，這會(huì)影響其編碼速度.

針對(duì)以上問題，本研究提出一種基于位長(zhǎng)四叉樹的EZBC改進(jìn)算法.該算法在采用EZBC算法的四叉樹編碼結(jié)構(gòu)，與基于上下文的位平面編碼的同時(shí)，利用位長(zhǎng)四叉樹代替EZBC算法中的幅值四叉樹完成編碼過程，并形成算術(shù)編碼器所需的上下文，不僅保持EZBC算法高效壓縮性能，還極大地減少了編碼過程所需內(nèi)存.實(shí)驗(yàn)結(jié)果表明，該算法在保持高信噪比的同時(shí)，加快編碼速度，節(jié)省內(nèi)存占用，易于硬件實(shí)現(xiàn).

1 位長(zhǎng)四叉樹

本算法在進(jìn)行位平面編碼時(shí)，首先建立每個(gè)子帶的位長(zhǎng)四叉樹結(jié)構(gòu).這里的位長(zhǎng)是指量化后的小波系數(shù)絕對(duì)值對(duì)應(yīng)的有效位長(zhǎng)度，不包含符號(hào)位.令第k子帶、第l四叉樹級(jí)、坐標(biāo)(i，j)處的節(jié)點(diǎn)值為 Bk［l］(i，j)，

式 (2)中，Ck(i，j)為子帶k中坐標(biāo)(i，j)處量化后的小波子帶系數(shù);表示x的絕對(duì)值;?x」表示對(duì)x的向下取整運(yùn)算，例如，若x=?3.8」，x≡3;式中“=”用來(lái)賦值，“≡”表示判斷.

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

四叉樹最底層的節(jié)點(diǎn)由每個(gè)子帶量化和縮放后，小波系數(shù)的2×2方塊最大位長(zhǎng)構(gòu)成，上一層四叉樹節(jié)點(diǎn)由當(dāng)前層中相應(yīng)4個(gè)節(jié)點(diǎn)的最大值表示，如圖1(a).最上層的四叉樹節(jié)點(diǎn)表示這個(gè)子帶中所有小波系數(shù)的最大位長(zhǎng).本算法也是從高位平面到低位平面漸進(jìn)編碼.一旦節(jié)點(diǎn)在某位平面被判斷為重要 (即節(jié)點(diǎn)位長(zhǎng)大于位平面位索引值)，它將被分裂為4個(gè)子節(jié)點(diǎn)，此分裂過程遞歸進(jìn)行，直至四叉樹的末梢節(jié)點(diǎn)，如圖1(b).

EZBC算法所建立的是小波系數(shù)的幅值四叉樹Qk［l］(i，j)和兩個(gè)鏈表，而本算法利用子帶系數(shù)絕對(duì)值的位長(zhǎng)建立位長(zhǎng)四叉樹，這與位平面掃描時(shí)采用的位平面位索引值一致，即可通過位長(zhǎng)四叉樹對(duì)小波系數(shù)進(jìn)行快速定位和重要性判斷，大大加快編碼速度，而且省去LIN與LSP.同時(shí)，通常小波系數(shù)的比特位長(zhǎng)度為16 bit，即在EZBC算法中建立的Qk［l］(i，j)每個(gè)節(jié)點(diǎn)需要16 bit存儲(chǔ);本算法中位長(zhǎng)四叉樹的每個(gè)節(jié)點(diǎn)用4 bit存儲(chǔ)，因?yàn)? bit最大表示值為15，表示其最大絕對(duì)值可達(dá)15 bit，即可表示的數(shù)值達(dá)到215-1，為32 767，經(jīng)小波變換后的小波系數(shù)絕對(duì)值小于32 767，即4 bit已足夠用來(lái)表示小波系數(shù)的位長(zhǎng)，從而節(jié)省了編碼過程所需的存儲(chǔ)單元.

2 編碼過程

參數(shù)定義.

ck(i，j)為子帶k內(nèi)坐標(biāo)(i，j)處的小波子帶系數(shù);

Bk［l］(i，j)為第k子帶、l級(jí)中坐標(biāo)(i，j)處的位長(zhǎng)四叉樹級(jí)節(jié)點(diǎn)，其值定義如式(1);

Dk為子帶k的四叉樹級(jí)數(shù);

Dmax為所有子帶四叉樹級(jí)數(shù)的最大值;

K為子帶總數(shù);

Xk為子帶k在原始圖像橫坐標(biāo)中的偏移量，從左向右為正向;

Yk為子帶k在原始圖像縱坐標(biāo)中的偏移量，從上向下為正向;

NthPower為2的n－1次冪;

ScanBL(k，l)為對(duì)子帶k內(nèi)位長(zhǎng)四叉樹第l級(jí)中的不重要節(jié)點(diǎn)進(jìn)行掃描的函數(shù)，前提是它的父節(jié)點(diǎn)在上一位平面已經(jīng)重要;

ScanDescendant(k，l，i，j)為對(duì)節(jié)點(diǎn) Bk［l］(i，j)所有后續(xù)子孫節(jié)點(diǎn)進(jìn)行重要性掃描的函數(shù);

ScanLSP(k)為掃描出子帶k內(nèi)已標(biāo)示重要的小波系數(shù)函數(shù);

OutPutDescendant(k，i，j)為對(duì)已標(biāo)示為重要的2×2方塊內(nèi)的小波系數(shù)進(jìn)行不重要系數(shù)編碼輸出的函數(shù);

OutPutLSP(k，i，j)為對(duì)已標(biāo)示重要的2×2方塊內(nèi)小波系數(shù)進(jìn)行幅值細(xì)化的函數(shù).

具體編碼過程.

①初始化

②編碼最高位平面

③編碼剩下的位平面

具體函數(shù)偽代碼如下.

本算法的編碼主要針對(duì)位長(zhǎng)四叉樹進(jìn)行掃描，建立的位長(zhǎng)四叉樹以2×2方塊為基本單位，這就減少了編碼過程位長(zhǎng)四叉樹所占用的內(nèi)存.由于其建立位長(zhǎng)的底層是從Tk(i，j)，即2×2方塊的最大位長(zhǎng)開始，不是直接從小波系數(shù)的位長(zhǎng)開始，每個(gè)位長(zhǎng)僅用4 bit即可，所以針對(duì)1個(gè)M×N的灰度圖，其編碼過程所占用內(nèi)存僅為(1/4+1/16+1/64+…)×M×N×4≈M×N×4/3 bit.且由于圖像的相關(guān)性，當(dāng)2×2方塊內(nèi)的某一小波系數(shù)為重要時(shí)，基本上其余小波系數(shù)都為重要，這更有利于算法的最優(yōu)截?cái)?

3 實(shí)驗(yàn)結(jié)果分析

本算法與EZBC算法都是在Pentium(R)D CPU 2.80 GHz、2.79 GHz的微機(jī)上用 Visual C++6.0 進(jìn)行驗(yàn)證，選用512×512×8 bit的標(biāo)準(zhǔn)灰度圖像Lena、Goldhill和Barbara與2 048×2 560×8 bit標(biāo)準(zhǔn)灰度圖像Cafe和Woman.采用9/7小波濾波器［9］，邊界處理采用對(duì)稱延拓［10-11］，上下文模型與文獻(xiàn)［7］中EZBC算法相同.表1為本算法與EZBC算法在不同碼率下的峰值信噪比.

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

由表1可知，本算法和EZBC算法具有同樣的峰值信噪比，但EZBC算法是通過小波系數(shù)的幅值四叉樹Qk［l］(i，j)和兩個(gè)鏈表 (LIN和LSP)完成編碼過程，并利用相鄰節(jié)點(diǎn)和父子帶節(jié)點(diǎn)的重要性形成上下文，所以它需要大量?jī)?nèi)存以存儲(chǔ)幅值四叉樹Qk［l］(i，j)和兩個(gè)鏈表，且其所需內(nèi)存隨處理圖像復(fù)雜度和編碼比特率的不同而不同，這增加了硬件實(shí)現(xiàn)的復(fù)雜度.本算法僅利用位長(zhǎng)四叉樹就可以完成編碼，并形成上下文，極大減少編碼過程所需的內(nèi)存.經(jīng)過實(shí)驗(yàn)測(cè)試，對(duì)于512×512×8 bit和2 048×2 560×8 bit的圖像，兩種算法的內(nèi)存占用情況如表2.可見，本算法僅需占用內(nèi)存分別為43 Kbyte和853 Kbyte，大大小于EZBC算法所需的內(nèi)存，相對(duì)EZBC算法節(jié)約90%以上.

表2 兩種算法的內(nèi)存占用Table 2 Memory usage comparison

EZBC算法采用鏈表操作，當(dāng)要求壓縮圖像質(zhì)量不太差時(shí)，編碼過程中需要進(jìn)行大量的鏈表添加和刪除操作，這會(huì)影響其編碼速率.本算法采用位長(zhǎng)四叉樹，利用子帶系數(shù)絕對(duì)值的位長(zhǎng)建立，與位平面掃描時(shí)采用的位平面位索引值一致，可以直接通過位長(zhǎng)四叉樹對(duì)小波系數(shù)進(jìn)行快速定位和重要性判斷，從而達(dá)到快速編碼的目的.

結(jié) 語(yǔ)

本研究提出一種基于位長(zhǎng)四叉樹的EZBC改進(jìn)算法，其利用位長(zhǎng)四叉樹代替EZBC算法中的幅值四叉樹完成編碼過程并形成算術(shù)編碼器所需要的上下文，在保持EZBC算法高效壓縮性能的同時(shí)，極大減少了編碼過程所需內(nèi)存，占用空間不到EZBC算法的10%.由于本算法通過位長(zhǎng)四叉樹對(duì)小波系數(shù)進(jìn)行快速定位和重要性判斷，不再采用鏈表操作，這就加快編碼速度，有利于該算法的硬件實(shí)現(xiàn).

/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)康志偉，廖劍利，何怡剛.基于提升算法的不可分離小波圖像邊緣檢測(cè)［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2006，34(4):56-58，62.

［11］ ZHANG Xu-dong，LU Guo-dong，F(xiàn)ENG Jian.Fundamentals of Image Coding and Wavelet Compressing-Principles，Algorithms and Standards［M］.Beijing:Tsinghua University Press，2004:235-272.(in Chinese)張旭東，盧國(guó)棟，馮 健.圖像編碼基礎(chǔ)和小波壓縮技術(shù)——原理、算法和標(biāo)準(zhǔn) ［M］.北京:清華大學(xué)出版社，2004:235-272.