陳云鵬 謝志成 鄭創(chuàng)偉 陳宇輝 曾宇鵬 杜雪清

(1.華中科技大學(xué)計算機學(xué)院 武漢 430074)(2.深圳報業(yè)集團 深圳 518009)

一種基于四叉樹的數(shù)字圖像壓縮算法*

陳云鵬1謝志成2鄭創(chuàng)偉2陳宇輝2曾宇鵬2杜雪清2

(1.華中科技大學(xué)計算機學(xué)院 武漢 430074)(2.深圳報業(yè)集團 深圳 518009)

基于四叉樹的數(shù)字圖像壓縮算法是一種利用四叉樹結(jié)構(gòu)對圖像中平滑區(qū)域進行壓縮編碼的技術(shù)。而現(xiàn)有的壓縮算法由于存在諸多缺陷,使得其效果很難與諸如Jpeg2000的主流壓縮算法相比擬。論文基于現(xiàn)有的四叉樹分割算法,提出了一種高效的編碼方式來記錄四叉樹的結(jié)構(gòu)信息,同時引入了泰森多邊形方法和自然鄰點插值法來解決四叉樹重構(gòu)時的平滑問題。實驗結(jié)果表明,該算法在盡可能小的失真前提下,最大限度地保留了圖像的細節(jié)信息,且具有較高的壓縮比,其整體效果可以與Jpeg2000比擬。

圖像壓縮; 四叉樹; 四叉樹分解; 多邊形插值; 圖像壓縮編碼

Class Number TP391

1 引言

隨著互聯(lián)網(wǎng)的普及和多媒體技術(shù)的快速發(fā)展,數(shù)字圖像正以指數(shù)級的速度增長。如在線圖像分享站點www.fichr.com僅至2009年,分享上傳的圖片數(shù)量就已突破了40億張[1]。如何有效地壓縮數(shù)字圖像,去除數(shù)據(jù)中的沉余信息,減少數(shù)據(jù)存儲空間實現(xiàn)數(shù)字圖像的海量存儲與快速傳輸,已成為數(shù)字圖像處理領(lǐng)域中一項重要問題。由于在實際應(yīng)用中,所接觸到的圖像其大部分區(qū)域都是平滑的,只有部分邊緣區(qū)域灰度值劇烈變化,因此一種較好的圖像壓縮方式就是將圖像不斷分割成一塊塊平滑區(qū)域,之后利用算法對每個區(qū)域進行編碼。由于高度的邊緣信息被分割為許多平滑的小區(qū)域,因此除了需要保存其顏色信息,還需要記錄其結(jié)構(gòu)信息。

針對這一問題,一種有效解決辦法是利用四叉樹來表示這些小區(qū)域的結(jié)構(gòu)位置信息?；谒牟鏄涞姆纸馑惴ㄖT如文獻[2～6],其主要思想是將圖像分塊成許多小塊,每一個小塊作為四叉樹的一個葉子節(jié)點以灰度值表示,或者是由一個特征向量所表示。但這些算法均存在壓縮率較低,難以適應(yīng)大尺寸圖像等限制,使得其壓縮效果很難與現(xiàn)有的主流壓縮算法相比擬。

本文基于現(xiàn)有的四叉樹分割算法,提出了一種高效的編碼方式來記錄四叉樹的結(jié)構(gòu)信息,同時引入了泰森多邊形方法和自然鄰點插值法來解決四叉樹重構(gòu)時的平滑問題。實驗結(jié)果表明,本文提出的算法可以有效解決圖像壓縮問題,其在盡可能小的失真前提下,最大限度地保留了圖像的邊緣信息,同時達到了較高的壓縮比,總體效果可以與Jpeg2000比擬。

2 圖像壓縮算法

2.1 圖像編碼系統(tǒng)

2.1.1 四叉樹分解算法

四叉樹分解將原始圖像逐步分成小塊,操作的目標(biāo)是將具有一致性的像素分到同一小塊中,通常這些小塊都是方塊[7],只有少數(shù)情況分成長方形或三角形[8]。一般來說,對一幅任意尺寸的圖像進行四叉樹分解前,需對圖像進行歸一化操作,通過簡單的縮放使得圖像變?yōu)榉叫?且像素點的個數(shù)是2的整數(shù)次冪時,以便四叉樹分解。

進行四叉樹分解的具體過程是:首先把原始圖像視為原始子塊,如果當(dāng)前子塊滿足一致性標(biāo)準(zhǔn),則存儲該整體子塊的像素值;否則將方形的原始圖像繼續(xù)分成四個大小相同的方塊,再視每一子塊為一原始圖像重復(fù)上述過程,直至所有子塊均滿足一致性標(biāo)準(zhǔn)才停止。現(xiàn)有的一致性檢驗標(biāo)準(zhǔn)很多,如QRH[5]和紋理特征等。本文采用標(biāo)準(zhǔn)差作為一致性檢驗標(biāo)準(zhǔn),該方法有算法復(fù)雜度低、算法簡單、可以有效地表示子塊中圖像的邊緣信息等諸多優(yōu)點,其分割效果如圖1所示。

圖1 四叉樹分解示意圖

2.1.2 四叉樹的結(jié)構(gòu)編碼

在四叉樹的存儲中,除了要保存葉子節(jié)點的顏色信息,還需要保存四叉樹本身的結(jié)構(gòu)信息。如在指針形式中,每一結(jié)點需4個或5個指針場。在三元組(L,X,Y)存儲形式中,對每個結(jié)點需要指出它所在的層次L及它在該層中所處的位置(X,Y)。但是該方法需要的存儲空間過大,因此文獻[2～3]中,作者提出了兩種對二值圖像進行編碼的方式,但盡管該方法可以推廣至多值圖像,其實現(xiàn)需要較繁瑣的位操作且需存儲每一結(jié)點的地址;在文獻[4]中作者提出一種改進方法,即每個結(jié)點用一個字節(jié)表示灰度,并設(shè)一個結(jié)點屬性標(biāo)志位的方式節(jié)省存儲空間,但仍需要至少半個字節(jié)來存取位置信息。

本文受到文獻[5]的啟發(fā),通過對四叉樹的子結(jié)構(gòu)進行編碼,以達到節(jié)省存儲量的效果。對于每兩次四叉樹的分解,可以使用一組二進制數(shù)進行編碼(D0,D1,d1,d2,d3,d4),如圖2(b)所示。D0代表當(dāng)前塊是否分解,若分解則為1,否則為0;如果D0=1,那么第二個D1則代表該4x4的塊是否繼續(xù)分解成至少8x8的塊,或者到此為止。如果D1=1那么d1,d2,d3,d4則表示圖中按行序編號的子塊“1”、“2”、“3”、“4”是否再繼續(xù)分解成另4x4的塊。文獻[5]中作者指出,該方法平均每個結(jié)點的顏色信息只需0.003bit來存儲其位置信息。

表1 編碼串示意表

圖2 文獻[5]所給分解及編碼算法

盡管該方法可以高效保存四叉樹的位置信息,但由于其模板所能代表的結(jié)構(gòu)類型有限,樹的深度最多只能達到三層,這使得其并不使用的大尺寸圖像的壓縮。為了彌補這一不足,本文對其進行了改進,使其可以表示兩次以上的四叉樹分解,其具體思想如下:

以進行三次四叉樹分解為例:首先對當(dāng)前塊進行一般的四叉樹分解,直至全部分解完畢,之后,對每兩次分解使用一次上述編碼規(guī)則,如:在圖3中Layer1中的模塊其(D0,D1,d1,d2,d3,d4)分別對應(yīng)110011。但,其中d1,d2,d3,d4不再表示其是否是葉子節(jié)點,而表示其是否存在子樹:若為1,則存在4棵子樹,即該節(jié)點是另外4棵樹的根。對于一個需要進行至少3分解(深度為4)的圖片,編碼過程如圖3所示,其最終編碼為110011000100000。

完成對樹結(jié)構(gòu)的編碼信息后,只需進行簡單的層次遍歷,即可將其轉(zhuǎn)化為物理存儲形式。且在實際編碼時,由于最后一層往往全部為0,因此可以不存儲最后一層的結(jié)構(gòu)信息(因為前一層的信息已經(jīng)足夠表示最后一層的信息了),以此進一步壓縮存儲空間。實驗表明,對于一個需要兩次以上分解的圖像,平均每個結(jié)點的顏色信息只需0.03bit來存儲其位置信息;而對于一個僅需兩次以下分解的圖像,該方法可以退化為原有算法,即平均每個結(jié)點的顏色信息只需0.003bit來存儲其位置信息。

圖3 樹的結(jié)構(gòu)編碼示意圖

2.2 圖像解碼系統(tǒng)

2.2.1 解碼部分

圖像的解碼包含二進制譯碼和樹的結(jié)構(gòu)重構(gòu)這兩部分。二進制譯碼即讀取四叉樹位置信息的二進制代碼,根據(jù)事先定義好的模板(字典)查找,對連續(xù)的二進制位進行分割、提取并將其保存為諸如序號的存儲形式,使其與事先定義好的模板(字典)相關(guān)聯(lián),其具體過程如圖4所示。樹的結(jié)構(gòu)重構(gòu)即根據(jù)二進制譯碼結(jié)果,利用相應(yīng)模板的結(jié)構(gòu)信息,利用按層遍歷或先序遍歷等方式重構(gòu)樹的結(jié)構(gòu)信息,使其形成四叉鏈表等易于操作存儲結(jié)構(gòu),以便于后期對圖像的重構(gòu),期間需利用棧和列隊或遞歸過程。

總體思路可簡單描述為:首先將二進制位置信息進行譯碼,使其與相應(yīng)的子樹結(jié)構(gòu)相對應(yīng)。其次,重構(gòu)四叉樹的結(jié)構(gòu):通過先驗知識計算最初曾的節(jié)點數(shù),依次讀取最初層的所有節(jié)點,計算其子樹的個數(shù),作為下一層讀取的結(jié)點個數(shù),如此迭代。

圖4 二進制譯碼過程示意圖

2.2.2 圖像重構(gòu)

“圖像重構(gòu)”即根據(jù)恢復(fù)出的四叉樹結(jié)構(gòu)信息,利用四叉樹的葉子上的顏色信息或特征向量,恢復(fù)原始圖像的過程。簡單來說,它是對圖像分解的一個逆過程?，F(xiàn)有的插值算法多是基于均勻值塊方式,即將整個正方形區(qū)域填充為單一顏色(純色),其會產(chǎn)生明顯的馬賽克,因此其視覺效果并不理想。而插值法(又稱“內(nèi)插法”),是利用函數(shù)f(x)在某區(qū)間中若干點的函數(shù)值,作出適當(dāng)?shù)奶囟ê瘮?shù),在這些點上取已知值,在區(qū)間的其他點上用這特定函數(shù)的值作為函數(shù)f(x)的近似值[10]。其具有計算精度高,能產(chǎn)生較清晰光滑的圖像并不丟失其邊緣信息的特點,并廣泛應(yīng)用到各種圖像縮放算法中。然而數(shù)字圖像處理中現(xiàn)有的插值方法,諸如最鄰近插值、線性插值、雙線性插值均要求像素成點陣的形式分布,而叉樹分解出來的塊大小不一分布上也沒有規(guī)律,因此不適用。

本文受到地球科學(xué)的啟發(fā),引入了泰森多邊形及其插值算法來解決四叉樹分解圖像的插值問題,如圖5所示。

圖5 泰森多邊形及其插值算法

泰森多邊形最早是由荷蘭氣候?qū)W家A.H.Thiessen提出的一種根據(jù)離散分布的氣象站的降雨量來計算平均降雨量的方法。但其實際應(yīng)用范圍卻十分廣泛,凡是涉及定性分析、統(tǒng)計分析、鄰近分析等的問題均可以使用基于泰森多邊形的方法解決?，F(xiàn)有的基于泰森多邊形的插值方式有Kriging、Nearest Neighbor、Natural Neighbor等。其中Kriging方法,相比于后兩種方法,算法復(fù)雜度較高,不適合于對數(shù)據(jù)點較密的數(shù)字圖像進行插值。本文分別采用了最鄰近法和自然臨近點法對四叉樹圖像進行重構(gòu)。

1) 最鄰近法

最近鄰點插值法(NearestNeighbor)又稱泰森多邊形方法,是由荷蘭氣象學(xué)家A.H.Thiessen提出的一種分析方法。最初用于從離散分布氣象站的降雨量數(shù)據(jù)中計算平均降雨量。實際上,最近鄰點插值的一個隱含的假設(shè)條件是任一網(wǎng)格點p(x,y)的屬性值都使用距它最近的位置點的屬性值,用每一個網(wǎng)格節(jié)點的最鄰點值作為待插值的節(jié)點值[11]。

盡管理論上最鄰近法仍會存在塊與塊之間沒有過度的問題,但針對四叉樹分解圖像重構(gòu)這一問題,由于點與點之間的間隔很小,其仍然可以達到很好的效果,如圖6所示。

圖6 應(yīng)用最鄰近點插值法后效果圖

2) 自然臨近點法

自然鄰點插值法(NaturalNeighbor)是對最近鄰點插值法的一種改進算法,它克服了最鄰近點法中塊與塊之間無過渡的問題,達到了更佳的插值效果。其廣泛應(yīng)用于一些研究領(lǐng)域中,它的基本原理是對于一組泰森多邊形,當(dāng)在數(shù)據(jù)集中加入一個新的數(shù)據(jù)點(目標(biāo))時,就會修改這些泰森多邊形,而使用鄰點的權(quán)重平均值將決定待插點的權(quán)重,待插點的權(quán)重和目標(biāo)泰森多邊形成比例[12]。實際上,在這些多邊形中,有一些多邊形的尺寸將縮小,并且沒有一個多邊形的大小會增加。同時,自然鄰點插值法在數(shù)據(jù)點凸起的位置并不外推等值線(如泰森多邊形的輪廓線)。針對四叉樹的圖像重構(gòu)問題,其插值結(jié)果如圖7所示。

圖7 應(yīng)用自然近點插值法后效果圖

3 復(fù)雜度分析

3.1 編碼部分的復(fù)雜度

編碼部分包括:標(biāo)準(zhǔn)四叉樹分解算法和本文提出的四叉樹結(jié)構(gòu)編碼方式,其中標(biāo)準(zhǔn)的四叉樹分解算法的時間復(fù)雜度為O(n^2),四叉樹的結(jié)構(gòu)編碼的時間復(fù)雜度為O(n),因此編碼部分的時間復(fù)雜度為O(n^2)。

3.2 解碼部分

圖像的編碼系統(tǒng)包括:譯碼重構(gòu)部分和圖像重構(gòu)部分,譯碼部分的時間復(fù)雜度為O(n),樹的結(jié)構(gòu)重建的時間復(fù)雜度為O(n^2);圖像重構(gòu)部分的時間復(fù)雜度根據(jù)所選算法的不同而有所差異,其中均勻快法的時間復(fù)雜度為O(n^2),最鄰近法的時間復(fù)雜度為O(n^2),而自然臨近法的時間復(fù)雜度為O(n^3)。

(a)編碼系統(tǒng)結(jié)構(gòu)框圖

(b)解碼系統(tǒng)結(jié)構(gòu)框圖

4 實驗結(jié)果

4.1 實驗設(shè)計

本實驗分為兩個部分:實驗1測試圖像的有損壓縮性能,分別對彩色圖像和灰度圖像進行有損壓縮測試;實驗2測試圖像在無損壓縮的情況下的壓縮情況。

實驗所使用的測試圖像集為Standard_Test_Images[13];其中利用釋義峰值信噪比(PSNR)、均方誤(ERMS)作為定量評價標(biāo)準(zhǔn),人眼視覺感受作為定性評價標(biāo)準(zhǔn)。

4.2 有損壓縮性能測試

本實驗測試圖像的有損壓縮性能,灰度圖像的測試結(jié)果如圖9所示;彩色圖像的測試結(jié)果如圖10所示;表2列出了上述所有測試圖像的具體參數(shù)與有損測試結(jié)果。

圖9 灰度圖像壓縮效果

通過對圖像的觀察可以看出,本文提出的圖像壓縮算法均能有效地壓縮圖像并盡可能地保留了圖像的內(nèi)容,其中:均勻塊法恢復(fù)的圖像有馬賽克的感覺,而另外兩種插值算法恢復(fù)出的圖像即不失細節(jié)紋理又十分平滑,視覺效果更佳。

圖10 彩色圖像壓縮效果

圖11和圖12分別給出lena_gray_512.tif的釋義峰值信噪比(PSNR)、均方誤(ERMS)曲線,橫軸為壓縮率(bit/pixel)?？梢钥闯霰疚奶岢龅乃惴ㄆ涓黜椫笜?biāo)可以與Jpeg2000比擬,其中均勻快法(Blocks)的效果最好,而插值法(Nerarest)的效果較差,這主要是由于插值曲線不完全擬合造成的。

圖11 PSNR測試結(jié)果曲線

圖12 ERMS測試結(jié)果曲線

文件名尺寸BMP壓縮后壓縮率cameraman.tif512×512256kb18kb0.0708woman_darkhair.tif512×512256kb6kb0.0246lena_color_512.tif512×512768kb52kb0.0714mandril_color.tif512×512768KB253kb0.3333

4.3 無損壓縮性能測試

本實驗測試圖像的無損壓縮性能,測試所用圖像與實驗1相同。表3列出了上述所有測試圖像的具體參數(shù)與無損壓縮測試結(jié)果。

表3 無損壓縮數(shù)據(jù)表

從表3可以看出,本文提出的四叉樹結(jié)構(gòu)編碼規(guī)則可以高效地保存四叉樹的結(jié)構(gòu)信息,同時使得位置信息的空間占用率盡可能的小。即使在無損壓縮這種四叉樹結(jié)構(gòu)最復(fù)雜的情況下,仍能使得空間信息占用率小于3%。

5 結(jié)語

本文介紹并分析了現(xiàn)有的幾種四叉樹壓縮算法,分別指出了其優(yōu)缺點,并在此基礎(chǔ)上,提出了一種高效的編碼方式來記錄四叉樹的結(jié)構(gòu)信息,該編碼方式可以高效保留四叉樹的結(jié)構(gòu)信息,具有算法實現(xiàn)簡單,算法復(fù)雜度低等優(yōu)點;此外,本文還將泰森多邊形方法和自然鄰點插值法引入到發(fā)雜圖像的重構(gòu)的問題上來,以此解決四叉樹分解圖像重構(gòu)時的平滑問題。

實驗結(jié)果表明,本文提出的算法可以有效解決圖像壓縮問題,其在盡可能小的失真前提下,最大限度地保留了圖像的細節(jié)信息,同時也達到了較高的壓縮比,總體效果可以與Jpeg2000比擬。然而,泰森多邊形方法和自然鄰點插值法的引入使得算法的時間復(fù)雜度為O(n^3),使得該算法并不適用于較大的圖像壓縮,同時也使其難以應(yīng)用于實時的圖像壓縮系統(tǒng)中。因此,如何進一步降低算法的時間、空間復(fù)雜度將成為下一步的工作重點。

[1] Wang J Z, Geman D, Luo J, et al. Real-world image annotation and retrieval: An introduction to the special section[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2008,30(11):1873-1876.

[2] Gargantini I. An effective way to represent quadtree[J]. Comm. of ACM,1982(12):905-910.

[3] Kawaguchi E, Endo T. On a method of binary-picture representation and its application to data compression[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on,1980(1):27-35.

[4] 高蘊健,李介谷.四叉樹與數(shù)據(jù)壓縮[J].機器人,1987,9(4):38-42.

[5] Keissarian F. A new quad-tree segmented image compression scheme using histogram analysis and pattern matching[C]//Computer and Automation Engineering(ICCAE), 2010 The 2nd International Conference on. IEEE,2010,5:694-698.

[6] El-Harby A A, Behery G M. Qualitative image compression algorithm relying on quadtree[J]. Mansoura University, Faculty of Science, Math. Dept., ICGST-GVIP,2008,8(3):2-3.

[7] 過潔,潘金貴.一種新的基于線性四叉樹的圖像分割算法[J].系統(tǒng)仿真學(xué)報,2009(1):54-55.

[8] 朱志良,趙玉麗,于海.基于像素分布與三角形分割的快速分形圖像壓縮算法[J].計算機應(yīng)用,2010(2):337-340.

[9] 徐雨明,文雙春.數(shù)字圖像插值算法的分析與實現(xiàn)[J].福建電腦,2007(1):94-94.

[10] 劉慕溪.數(shù)值分析中常見插值法的淺析[J].科技致富向?qū)?2011(24):33-33.

[11] 李慶揚,關(guān)治.數(shù)值計算原理[M].北京:清華大學(xué)出版社有限公司,2000.

[12] 沈劍華.數(shù)值計算基礎(chǔ)[M].上海:同濟大學(xué)出版社,2004,8.

[13] "Standard" test images[EB/OL]. http://www.imageprocessingplace.com/root_files_V3/image_databases.htm.

Image Compression Based on Quad-tree Coding with Voronoi-Interpolation

CHEN Yunpeng1XIE Zhicheng2ZHENG Chuangwei2CHEN Yuhui2ZENG Yupeng2DU Xueqing2

(1. School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074) (2. Shenzhen Newspaper Group, Wuhan 518009)

Quadtree-based image compression technique is a typical method which aims to exploit the redundancy in an image such that the smaller number of bits can be used to represent the image while remaining detail information. However, most of existing approaches to this problem do not work well due to its own limitations. Here a new approach to code quad-tree decomposed Image with a novel codebook and then be reconstructed by voronoi interpolation is described that provides a "satisfying" visual quality comparing with Jpeg2000.

image compression, quadtree, quadtree decomposition, voronoi-interpolation, image coding

2014年5月5日,

2014年6月25日 作者簡介:陳云鵬,男,研究方向:數(shù)字圖像處理,高維數(shù)據(jù)索引,機器學(xué)習(xí),圖像壓縮。謝志成,男,碩士,研究方向:信息系統(tǒng)管理。鄭創(chuàng)偉,男,研究方向:信息系統(tǒng)管理。陳宇輝,男,碩士,研究方向:微電子設(shè)計。曾宇鵬,男,碩士,研究方向:計算機網(wǎng)路。杜雪清,女,研究方向:信息系統(tǒng)管理。

TP391

10.3969/j.issn1672-9730.2014.11.010