陳新 張楠 王洪信

摘 要：根據(jù)小波樹和分形理論的特點，提出一種基于小波樹的分形預(yù)測編碼。圖像經(jīng)小波變換后，形成小波樹。根據(jù)小波子樹結(jié)構(gòu)相似的特點，把塊預(yù)測搜索范圍限制在子樹附近，減少了分形編碼時間；對較低分辨率子帶中分形預(yù)測誤差較大的塊，直接記錄其值，進行無失真編碼，以加快編碼速度，提高恢復(fù)圖像質(zhì)量。實驗證明，該方法在保證恢復(fù)圖像的質(zhì)量的前提下，提高了編碼效率。

關(guān)鍵詞：圖像壓縮；小波樹；分形；預(yù)測

1 引言

小波用于壓縮技術(shù)始于1986年，J.W.Woods等人利用小波技術(shù)構(gòu)造了一個真正意義上的小波圖像編碼器。[1]1988年，Daubechies提出了具有緊支集的光滑正交小波基。1989年Mallat提出的快速小波變換算法使小波從理論研究邁向?qū)拸V的應(yīng)用領(lǐng)域。分形是在波蘭美籍?dāng)?shù)學(xué)家B.B.Mandelbrot建立的分形幾何理論的基礎(chǔ)上發(fā)展起來的一種編碼方法?；诜中蔚膲嚎s技術(shù)始于1988年，Barnsley將迭代函數(shù)系統(tǒng)應(yīng)用到圖像壓縮編碼中[2]，該方法對某些特定圖像的壓縮比高達10000：1。Barnsley的博士生Jaquin首次實現(xiàn)不需人工操作的自動分形壓縮編碼[3]。小波與分形編碼都屬于第二代編碼方法，它們擁有各自的特點，二者結(jié)合能夠?qū)崿F(xiàn)更好的壓縮效率。

小波變換把圖像分解為不同空間頻帶上的子圖像，而不同層對應(yīng)的子圖像結(jié)構(gòu)之間存在著很大的相似性。按照其相似性進行圖像分割后，圖像的R塊池與D塊池的圖像塊大大減少[4]。在小波變換后的高層子圖像內(nèi)進行基本分形壓縮，根據(jù)分形的特點，利用不同子圖像之間的相似性[5]，由高層分形編碼構(gòu)造低層子圖像分形編碼；在R塊池與D塊池內(nèi)的圖像塊數(shù)量減少后，匹配所用的搜索時間大大減少，從而實現(xiàn)壓縮。

2 小波樹

圖像經(jīng)小波分解后，除LL子帶及最高分辨率的3個高頻子帶以外，對于任意一個系數(shù)節(jié)點 （i，j）， 它的同方向的高分辨率子帶的4個節(jié)點（2i，2j），（2i+1，2j），（2i，2j+1）， （2i+1，2j+1）稱為（i，j）的4個子節(jié)點；反過來，節(jié)點 （i，j）稱為4個子節(jié)點的父節(jié)點。如果i，j∈LL，則它有3個子節(jié)點：i+WLL，j），（i，j+HLL），（i，+wLL，j+HLL），其中WLL，HLL分別為LL子帶的寬和高。依照此父子關(guān)系進行遞歸定義，即可以將所有的小波系數(shù)組織成樹形的數(shù)據(jù)結(jié)構(gòu)，形成小波樹。

圖1 小波樹的父子關(guān)系

3 基于小波樹的分形預(yù)測編碼

基于小波樹的分形預(yù)測改變了傳統(tǒng)方法中，搜索過程對上一級分辨率子帶內(nèi)所有的塊進行全面搜索的策略，而是根據(jù)小波樹具有結(jié)構(gòu)相似性的特點，即同方向不同分辨率相同位置的塊具有較強的相似性，限制搜索范圍在小波樹附近。這種搜索策略大幅度減少了搜索時間，加快了編碼速度。通過實驗發(fā)現(xiàn)，對于低分辨率的子帶，分形預(yù)測誤差較大，而低分辨率子帶在圖像恢復(fù)中起著重要的作用，為了保證恢復(fù)圖像的質(zhì)量，我們選擇對低分辨率子帶分形預(yù)測進行誤差判斷，誤差較小的可進行分形編碼，誤差較大的，不進行分形編碼，而是直接保存其值，進行無失真編碼。

算法如下：

（1）將圖像做5級小波分解，對第4級分解得到的低頻子帶進行分形預(yù)測誤差判斷，如果誤差大于閥值，則不對子帶進行編碼，反之則進行分形編碼。

（2）對其余子帶，進行分形編碼。每一級定義域取自上級同方向子帶。定義域塊大小和值域塊大小一致，搜索范圍限定在小波樹內(nèi)。

4 仿真實驗

實現(xiàn)選擇512*512*8的lena圖，實驗平臺為Pentium（R） 2.60G，實驗中小波分解層數(shù)為5級，對第4級小波分解的低頻子帶做誤差限判定，對第4級高頻子帶做分形預(yù)測編碼，分形匹配塊的大小根據(jù)分辨率變化而變化，從低到高分別為：4×4，8×8，12×12，24×24。

實驗結(jié)果將小波分形混合編碼方法與四叉樹分形壓縮編碼方法[5]做對比如表1。

表1 小波分形混合壓縮方法lena圖實驗結(jié)果

從表1可知，小波分形混合壓縮方法與四叉樹分割方法在壓縮比和恢復(fù)圖像質(zhì)量方面相差不大，而編碼時間大幅縮短，編碼效率提高較大。

5 結(jié)論

綜上所述，本文提出的小波與分形預(yù)測混合編碼方面，在保證恢復(fù)圖像質(zhì)量的前提下，縮短了圖像壓縮編碼的時間，提高了編碼效率。

參考文獻

[1]劉文耀.小波圖像編碼與專用VLSI設(shè)計[M].北京：電子工業(yè)出版社，2006.77-80.

[2]M.F.Barnsley，A.D.Sloan.A better way to compress image Byte，Jan，1988.

[3]A.E.Jacquin，Image coding based on a fractal theory of iterated contractive image transformations.IEEE Trans.Image Processing，January，1992.

[4]李高平.分形法圖像壓縮編碼[M].成都：西南交通大學(xué)出版社，2010.24-25.

[5]包紅強.一種快速小波子帶分形圖像壓縮編碼方法[J].蘭州大學(xué)學(xué)報，2002（05）.

[6]陳曉棠.基于四叉樹分割和多分辨率相關(guān)的快速小波分形編碼[J].計算機應(yīng)用研究，2000（03）.