《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 一種基于小波域的分形圖像編碼改進(jìn)算法
一種基于小波域的分形圖像編碼改進(jìn)算法
來(lái)源:電子技術(shù)應(yīng)用2010年第7期
婁 莉
西安石油大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安710065
摘要: 提出了一種基于小波域的分形圖像編碼改進(jìn)算法。該算法首先將圖像分解到小波域,然后根據(jù)各子圖像所包含能量的大小和所代表的方向等信息,采用不同大小、形狀和類(lèi)別的圖像塊及相似塊,進(jìn)行分形編碼。在編碼過(guò)程中按照零樹(shù)結(jié)構(gòu)在同方向不同分辨率的各個(gè)子帶圖像上確定要預(yù)測(cè)的圖像塊,同時(shí)在同方向低一級(jí)分辨率的子帶圖像上尋找與其最佳分形匹配的相似塊,并由各級(jí)相似塊構(gòu)成預(yù)測(cè)樹(shù)。實(shí)驗(yàn)證明,這種改進(jìn)算法能夠大大提高分形編碼的速度,并取得較高的壓縮比。
中圖分類(lèi)號(hào): TP919
文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2010)07-0134-03
Fractal image coding improved algorithms based on wavelet domain
LOU Li
Computer college, Xi′an Shiyou University, Xi′an 710065, China
Abstract: A new improved algorithm of fractal image coding based on wavelet domain is proposed in this paper. Through the algorithm , the image is decomposed into subimages by the wavelet transform .Then, according to the energy and orientation information, every subimage is encoded using fractal coding with range block and domain block of different size, shape and sort. During the fractal coding ,we pick out the range blocks to be predicted based on zero-trees from subimages of the same orientation but different resolutions.For each range block, we look for its optimum fractal-matched domain block in the subimages of the same orientation but lower resolution . These domain blocks of all levels are used to construct the predictive trees. The experimental results indicate that the improved algorithm of fractal image coding based on wavelet domain in the paper can enhance the speed of fractal coding greatly and achieve a higher compression rate.
Key words : wavelet domain; fractal; image coding

    小波圖像編碼分形圖像編碼是兩種不同的圖像編碼方法,二者各有其特點(diǎn),又都存在一定的局限性[1-3]。一幅圖像經(jīng)過(guò)小波變換后,其相同方向但不同分辨率的子圖像具有較強(qiáng)的相似性,這種相似性正好與分形編碼的特點(diǎn)具有互補(bǔ)性。自1995年以來(lái),Rinaldo和Calvagno首次提出并實(shí)現(xiàn)了一種小波與分形圖像編碼相結(jié)合的算法[4]。此后,又出現(xiàn)多種小波變換與分形相結(jié)合的圖像編碼算法[5-8]。這些算法,有的證明了小波域的分形圖像解碼可以通過(guò)低分辨率小波系數(shù)向高分辨率系數(shù)連續(xù)外推實(shí)現(xiàn),即解碼無(wú)需循環(huán)迭代,是無(wú)條件收斂的;有的通過(guò)采用平滑小波基消除重構(gòu)圖像在高壓縮比時(shí)的方塊效應(yīng);有的推導(dǎo)出仿射變換的收縮因子取值不受限制,能保證解碼收斂;同時(shí)小波系數(shù)的樹(shù)狀結(jié)構(gòu)提供了自然高效的Domain塊分類(lèi)方法等[9]。此外,還有一些研究集中在分形塊的類(lèi)別劃分[10]以及基于小波零樹(shù)結(jié)構(gòu)的分形預(yù)測(cè)[11]等。
    本文在此基礎(chǔ)上,通過(guò)分析基本分形圖像編碼的壓縮算法,提出一種基于小波域的分形圖像編碼改進(jìn)算法。這種改進(jìn)算法包括兩部分:(1)根據(jù)圖像小波分解后各子圖像包含的不同能量,考慮各子圖像所代表的方向、紋理特征等信息,對(duì)各子圖采用非均勻的分形編碼方案,即在進(jìn)行小波域的分形編碼時(shí),分形塊的選取不一定全是正方形,對(duì)于不同方向的紋理特征的小波子圖像選取不同形狀的分形塊; (2)根據(jù)圖像的小波變換系數(shù)在同一方向不同分辨率、同一分辨率不同方向之間都存在相關(guān)性,對(duì)每一圖像塊,在同一方向低一級(jí)分辨率的子帶圖像上尋找與其最佳分形匹配的相似塊,由這些相似塊形成一棵一棵預(yù)測(cè)樹(shù),解碼端通過(guò)對(duì)預(yù)測(cè)樹(shù)的分形預(yù)測(cè)恢復(fù)出各級(jí)圖像塊。實(shí)驗(yàn)證明,這種改進(jìn)算法能夠大大提高分形編碼的速度,并取得較高的壓縮比。
1 基本分形編碼壓縮算法
  基本分形編碼壓縮算法的主要內(nèi)容:將待編碼的圖像分割成互不重疊的子塊(Range Block),稱(chēng)為圖像塊R,同時(shí)將圖像分割成可以相互重疊的大一些的塊(Domain Block),稱(chēng)為相似塊D。對(duì)分割后的R塊和D塊進(jìn)行分類(lèi),如:變換平緩的平滑區(qū)域、變換突然的邊緣區(qū)域和變換緩和的中間型區(qū)域等,使相匹配的塊具有相同的區(qū)域性質(zhì)。對(duì)分類(lèi)后相同區(qū)域的每一個(gè)R塊Rj尋找可以匹配的D塊Dj,使得Dj通過(guò)仿射函數(shù)ψj可以近似于Rj,由此可以得到一組仿射變換組ψ1,ψ2…ψN,即分形迭代系統(tǒng)。只要該系統(tǒng)的變換是收斂的,且比原系統(tǒng)簡(jiǎn)單,就實(shí)現(xiàn)了分形壓縮[12]。基本分形編碼算法主要在圖像分割后對(duì)R塊和D塊進(jìn)行搜索匹配的過(guò)程,其壓縮比較高,但是壓縮時(shí)的計(jì)算量較大,編碼壓縮時(shí)間很長(zhǎng)。
2 基于小波域的分形圖像編碼改進(jìn)算法
    本文的改進(jìn)算法包括兩部分:小波域分形編碼過(guò)程中分形塊形狀的選取以及分形預(yù)測(cè)樹(shù)的形成。
2.1 小波域分形編碼過(guò)程中分形塊形狀的選取
    在上述基本分形壓縮編碼過(guò)程中,在確定R塊和D塊的形狀時(shí),對(duì)各小波分解子圖取的均是正方形。由于圖像小波分解后,各子圖包含的能量有所不同,其代表的方向、紋理等特征信息也不相同,因此,可以考慮在進(jìn)行小波域的分形編碼時(shí),分形塊的選取可以不選正方形,而是依據(jù)小波分解子圖的不同方向的紋理特征選取不同形狀的子塊。
 以512×512的8 bit圖1為例進(jìn)行實(shí)驗(yàn),計(jì)算結(jié)果表明,不同方向的子圖由于其紋理特征信息不同,在LH、HL、HH區(qū)域中,其水平和垂直方向的相關(guān)性不相同,所以在不同方向的分解子圖像中采用不同形狀的塊進(jìn)行分形編碼,可使其編碼時(shí)間更短,圖像恢復(fù)效果更好。例如,在LH區(qū)域,通過(guò)計(jì)算分析,行相關(guān)長(zhǎng)度大于列相關(guān)長(zhǎng)度,圖像以水平紋理為主,可采用4×2的矩形進(jìn)行R塊和D塊的分割;在HL區(qū)域,行相關(guān)長(zhǎng)度小于列相關(guān)長(zhǎng)度,圖像以豎直紋理為主,可采用2×4的矩形進(jìn)行R塊和D塊的分割;而在HH區(qū)域,行相關(guān)長(zhǎng)度與列相關(guān)長(zhǎng)度接近,則可以采用正方形來(lái)分割。同時(shí),由于左上角的低頻子圖包含了圖像的大部分能量,因此仍采用2×2正方形子塊的選取,不參加計(jì)算。圖像塊的分割方法如圖2所示。應(yīng)用均勻分塊和非均勻分塊的壓縮效果比較如圖3 所示。

2.2 分形預(yù)測(cè)樹(shù)的形成過(guò)程
    分形預(yù)測(cè)樹(shù)的形成原理是:應(yīng)用Davis把零樹(shù)的概念引入到分形圖像編碼的理論,把分形圖像編碼中的相似塊和圖像塊擴(kuò)大到相似樹(shù)(Domain Tree)和圖像樹(shù)(Range Tree),從而使得相似塊與圖像塊之間的分形匹配轉(zhuǎn)化為相似樹(shù)與圖像樹(shù)之間的分形匹配。在此基礎(chǔ)上,可以在各級(jí)小波分解的子圖像中尋找與圖像塊R最佳分形匹配的代表塊,再由各級(jí)代表塊按照零樹(shù)結(jié)構(gòu)產(chǎn)生一棵代表樹(shù),通過(guò)計(jì)算比較各級(jí)圖像樹(shù)R與代表樹(shù)的距離,確定距離最小的代表樹(shù)就是圖像樹(shù)R的預(yù)測(cè)樹(shù)。
 結(jié)合小波域圖像分割形狀的分析,對(duì)圖1進(jìn)行如圖2所示的小波域分割,得到基于小波域的分形預(yù)測(cè)樹(shù)的形成圖如圖4 所示。具體過(guò)程是:

    (1) 首先對(duì)圖像進(jìn)行多次小波變換,產(chǎn)生各個(gè)子帶圖像。通過(guò)對(duì)圖像行、列相關(guān)性的計(jì)算分析,確定各子帶小波域圖像分割的形狀。為了保證信噪比,對(duì)最低分辨率的子帶圖像LL1、HL1、LH1、HH1不編碼。
    (2) 同時(shí)在水平、垂直、對(duì)角線3個(gè)方向上形成一棵一棵圖像樹(shù),即零樹(shù)。如LH方向上的R=(R1,R2,R3,R4)就是其中一棵圖像樹(shù),而D=(D1,D2,D3,D4)表示HL方向上的相似樹(shù)。然后在LH1中尋找與圖像塊R2最佳分形匹配的代表塊E1,再由E1按照零樹(shù)結(jié)構(gòu)產(chǎn)生一棵代表樹(shù)E=(E1,E2,E3)。同理,在LH2中尋找與圖像塊R3最佳分形匹配的代表塊F2,并生成代表樹(shù)F=(F1,F(xiàn)2,F(xiàn)3)。在LH3中尋找與圖像塊R4最佳分形匹配的代表塊G3,并生成代表樹(shù)G=(G1,G2,G3)。
    (3)分別計(jì)算圖像樹(shù)R與3棵代表樹(shù)E、F、G的距離,距離最小的代表樹(shù)就是圖像樹(shù)R的預(yù)測(cè)樹(shù)。然后將預(yù)測(cè)樹(shù)在相應(yīng)層次的位置以及經(jīng)歷的幾何變換和仿射變換作為圖像樹(shù)R的分形預(yù)測(cè)編碼。
    (4) HL、HH方向按同樣方式編碼,只是構(gòu)成的R塊和D塊的形狀大小不同。這樣,在改進(jìn)算法中,編碼只需對(duì)代表樹(shù)中的一個(gè)代表塊進(jìn)行分形編碼。而解碼時(shí),又可依據(jù)這個(gè)代表塊通過(guò)零樹(shù)結(jié)構(gòu)推出其他代表塊,再分形預(yù)測(cè)圖像塊R。
    由于前面針對(duì)小波分解圖的能量分配特性已經(jīng)采用了非均勻的分形塊形狀的選取,再結(jié)合這種分形預(yù)測(cè)編碼方法,其結(jié)果大大提高了分形編碼的速度,縮短了編碼時(shí)間,在提高壓縮比方面也取得了良好的效果。
3 實(shí)驗(yàn)結(jié)果
 實(shí)驗(yàn)采用圖1所示圖像,分別用基本分形編碼方法和本文的改進(jìn)算法進(jìn)行實(shí)驗(yàn),其重建圖像如圖5所示?;痉中尉幋a時(shí)各子圖中圖像塊大小為4×4,相似塊大小為8×8,改進(jìn)算法中對(duì)小波分解圖像塊的分割方法如圖2所示,相似塊大小取為圖像塊大小的2×2倍,實(shí)驗(yàn)結(jié)果如表1所示。

 本文提出基于小波域的分形圖像編碼改進(jìn)算法是將小波域分形與分形預(yù)測(cè)方法相結(jié)合,由表1可知,與基本分形算法相比,在恢復(fù)圖像質(zhì)量接近的情況下,壓縮比提高約2倍,信噪比下降2 dB,而編碼時(shí)間大大縮短,提高了編碼速度,表明在提高壓縮比方面,效果良好。
參考文獻(xiàn)
[1]  余松煜,張文軍,孫軍.現(xiàn)代圖像信息壓縮技術(shù)[Ml.北京:科學(xué)出版社,1998.
[2]  陳守吉,張立明.分形與圖像壓縮[M].上海:上海科技教育出版社,1998.
[3]  BRENDT W,GERHARD D J. A review of the fractal image coding literature[J]. IEEE Transactions on Image  Processing, 1999, 8(12):1716-1729.
[4]  RINALDO R, CALVAGNO G. Image coding by block  prediction of multiresolution subimages[J]. IEEE Transaction On    Image Processing ,1995, IP-4(7):909-920.
[5]  DAVIS G. A wavelet-based analysis of fractal image compression[J]. IEEE Transactions on Image Processing, 1998,7(2):141-154.
[6]  DAVIS G. Adaptive self-quantization of wavelet subtrees: a wavelet-based theory of fractal images compression[C]. SPIE Conf. on Mathematical Imaging: Wavelet application in Signal and Image Processing, San Diego:1995:265-279.
[7]  WALLE A V D. Merging fractal image compression and  wavelet transform methods[C]. In Fractal Image Coding  Analysis: A NATO Series Book, Yuval Fisher, Ed. New  York: Springer Verlag,1996:523-597.
[8]  KRUPNIK H, MALAH D, KARNIN E. Fractal representation of images via the discrete wavelet transform[C]. In  IEEE 18th Conference of  EE, Israel: 1995,3:187-191.
[9]  張宗念,馬義德,余英林.基于方向性零樹(shù)小波的分形圖像編碼[J].電子科學(xué)學(xué)刊,2000,22(5):780-783.
[10] 周艷, 吳敏金.基于方向剖分的小波域分形圖像壓縮[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2002,3(9):20-23.
[11]  謝鑫,馬爭(zhēng)鳴.基于小波系數(shù)零樹(shù)結(jié)構(gòu)的分形預(yù)測(cè)圖像編碼[J].中國(guó)圖像圖形學(xué)報(bào),2000,5(11):920-924.
[12]  JACQUIN A E. Fractal image coding: A Review[J]. Proc.     of IEEE, 1993, 81(10):1451-1465.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。