小波混合分形預(yù)測(cè)圖像壓縮編碼方法

陳新 張楠 王洪信

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

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

1 引言

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

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

2 小波樹(shù)

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

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

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

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

算法如下：

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

[1]劉文耀.小波圖像編碼與專用VLSI設(shè)計(jì)[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]包紅強(qiáng).一種快速小波子帶分形圖像壓縮編碼方法[J].蘭州大學(xué)學(xué)報(bào)，2002（05）.

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