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

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

(1.華中科技大學(xué)計(jì)算機(jī)學(xué)院 武漢 430074)(2.深圳報(bào)業(yè)集團(tuán) 深圳 518009)

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

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

(1.華中科技大學(xué)計(jì)算機(jī)學(xué)院 武漢 430074)(2.深圳報(bào)業(yè)集團(tuán) 深圳 518009)

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

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

Class Number TP391

1 引言

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

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

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

2 圖像壓縮算法

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

2.1.1 四叉樹(shù)分解算法

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

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

圖1 四叉樹(shù)分解示意圖

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

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

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

表1 編碼串示意表

圖2 文獻(xiàn)[5]所給分解及編碼算法

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

以進(jìn)行三次四叉樹(shù)分解為例:首先對(duì)當(dāng)前塊進(jìn)行一般的四叉樹(shù)分解,直至全部分解完畢,之后,對(duì)每?jī)纱畏纸馐褂靡淮紊鲜鼍幋a規(guī)則,如:在圖3中Layer1中的模塊其(D0,D1,d1,d2,d3,d4)分別對(duì)應(yīng)110011。但,其中d1,d2,d3,d4不再表示其是否是葉子節(jié)點(diǎn),而表示其是否存在子樹(shù):若為1,則存在4棵子樹(shù),即該節(jié)點(diǎn)是另外4棵樹(shù)的根。對(duì)于一個(gè)需要進(jìn)行至少3分解(深度為4)的圖片,編碼過(guò)程如圖3所示,其最終編碼為110011000100000。

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

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

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

2.2.1 解碼部分

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

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

圖4 二進(jìn)制譯碼過(guò)程示意圖

2.2.2 圖像重構(gòu)

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

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

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

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

1) 最鄰近法

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

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

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

2) 自然臨近點(diǎn)法

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

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

3 復(fù)雜度分析

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

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

3.2 解碼部分

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

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

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

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)分為兩個(gè)部分:實(shí)驗(yàn)1測(cè)試圖像的有損壓縮性能,分別對(duì)彩色圖像和灰度圖像進(jìn)行有損壓縮測(cè)試;實(shí)驗(yàn)2測(cè)試圖像在無(wú)損壓縮的情況下的壓縮情況。

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

4.2 有損壓縮性能測(cè)試

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

圖9 灰度圖像壓縮效果

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

圖10 彩色圖像壓縮效果

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

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

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

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

4.3 無(wú)損壓縮性能測(cè)試

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

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

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

5 結(jié)語(yǔ)

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

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

[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] 高蘊(yùn)健,李介谷.四叉樹(shù)與數(shù)據(jù)壓縮[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] 過(guò)潔,潘金貴.一種新的基于線性四叉樹(shù)的圖像分割算法[J].系統(tǒng)仿真學(xué)報(bào),2009(1):54-55.

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

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

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

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

[12] 沈劍華.數(shù)值計(jì)算基礎(chǔ)[M].上海:同濟(jì)大學(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日 作者簡(jiǎn)介:陳云鵬,男,研究方向:數(shù)字圖像處理,高維數(shù)據(jù)索引,機(jī)器學(xué)習(xí),圖像壓縮。謝志成,男,碩士,研究方向:信息系統(tǒng)管理。鄭創(chuàng)偉,男,研究方向:信息系統(tǒng)管理。陳宇輝,男,碩士,研究方向:微電子設(shè)計(jì)。曾宇鵬,男,碩士,研究方向:計(jì)算機(jī)網(wǎng)路。杜雪清,女,研究方向:信息系統(tǒng)管理。

TP391

10.3969/j.issn1672-9730.2014.11.010