摘  要： 圖像經過多級小波分解后，各級小波子帶具有明顯的相似性，可利用小波變換和分形編碼的優勢進行圖像壓縮編碼。對最低分辨率子帶進行失真較小的均勻量化編碼。對高分辨率子帶，將水平、垂直和對角3個方向的小波子帶結合起來考慮，形成小波樹結構，設定一個閾值，小波樹所有系數小于等于閾值則直接置零；大于閾值的小波樹采用四叉樹算法進行分形編碼，如果誤差小于等于閾值，則記錄分形編碼參數，否則進行四叉樹分裂。對算法進行了Matlab仿真，結果表明，在保證一定解碼圖像質量的情況下，運算速度有較大提高。
關鍵詞： 小波樹；分形編碼；四叉樹；壓縮比

　分形圖像編碼是近年來發展起來的一種編碼技術，它以分形理論為數學基礎[1]。BARNSLEY M于1988年首先提出基于塊的編碼方案[2]，分形編碼就作為一種新的圖像編碼技術受到人們的廣泛關注。隨后他的學生JACQUIN A提出一個基于仿射變換的完全自動的圖像編碼方案[3]，分形編碼的計算復雜性由值域塊的匹配塊的搜索過程決定。由于分形編碼運算復雜度太大，編碼時間過長，極大地限制了其應用。因此，縮短分形編碼時間是分形編碼技術面臨的一個重要問題。
　圖像經過多級小波分解后，各級小波子帶具有明顯的相似性，可利用小波變換和分形編碼的優勢進行圖像壓縮編碼。
　小波和分形的混合編碼比較經典的算法有兩類：RINALDO R等人提出代表性的基于小波變換的分形預測圖像編碼算法[4]，低分辨率圖像預測高分辨率圖像的編碼仍采用仿射變換，但不需收縮映射，解碼時不需迭代且可直接估計均方差；DAVIS G M把零樹概念引入到分形圖像編碼[5]，把相似塊與圖像塊之間的分形匹配轉化為相似樹與圖像樹之間的分形匹配，通過小波變換產生子圖之間的相似性，用分形方法來開發這些相似性。
1 圖像小波變換和分形編碼
1.1 圖像小波變換
　一幅圖像經過小波變換后，可分解為不同方向、不同分辨率的子帶圖像。二維Mallat小波分解和重構算法的公式為：

1.2 圖像分形壓縮編碼
    分形編碼的主要理論基礎是迭代函數系統理論、不動點定理和拼貼定理，所要解決的主要問題是把待編碼的圖像作為吸引子時如何得到IFS參數。基本算法的主要步驟如下：

2 相關算法研究
　參考文獻[6]提出小波域內相鄰子圖的分形預測編碼算法。在低分辨率子帶水平、垂直和對角3個方向上分別進行分形編碼，用此編碼對在水平、垂直和對角3個方向上預測得到高分辨率子帶的分形編碼，但是沒有給出具體如何預測。參考文獻[7]提出對得到的低分辨率子帶的分形編碼進行適當的比例變換以得到高分辨率子帶的分形編碼，其壓縮效果較好，但是獲得高分辨率子帶上的分形編碼時，依據不是很充分，在壓縮比較大時解碼圖像質量有所下降。參考文獻[8]提出一種基于小波域的分形圖像編碼改進算法。該算法首先將圖像分解到小波域，然后根據各子圖像所包含能量的大小和所代表的方向等信息，采用不同大小、形狀和類別的圖像塊及相似塊進行分形編碼。在編碼過程中按照零樹結構在同方向不同分辨率的各個子帶圖像上確定要預測的圖像塊，同時在同方向低一級分辨率的子帶圖像上尋找與其最佳分形匹配的相似塊，并由各級相似塊構成預測樹。算法取得較高的壓縮比，解碼質量也有所下降。參考文獻[9]提出基于方向性零樹小波的分形圖像編碼，將小波零樹與分形編碼的優勢相結合。
3 基于小波樹和四叉樹的圖像分形編碼算法研究
　圖像經過小波變換后，除去最后一級小波變換產生的4個最低分辨率子帶，對其他高分辨率子帶按照小波樹結構形成一棵棵小波樹，所形成的即為待編碼的小波樹，記為值域樹。值域樹根節點所在子帶低一級分辨率子帶上，也可以形成小波樹結構，去掉它們在第一級小波變換的小波系數節點，則與值域樹有相同的大小、相同的層次，記為定義域樹。
算法的主要步驟如下：
　（1）對256像素×256像素大小的灰度圖像經過多級小波變換，分解成多級小波子帶，如進行4級小波分解。
　（2）對最低分辨率子帶，也就是最后一級小波分解產生的低頻子帶LL4和水平HL4、垂直LH4、對角HH43個高頻子帶，進行失真較小的編碼，采用均勻量化編碼。
　（3）對高分辨率子帶按照小波樹結構形成一棵棵小波樹，即為待編碼的小波樹，記為值域樹。小波樹的根可以是單個系數，也可以是2×2的小波系數塊等。設定一個閾值，當小波樹的所有小波系數都小于等于閾值時直接置0，不進行分形編碼。
　（4）對小波系數大于閾值的值域樹進行分形編碼。分形編碼就是搜索值域樹最匹配的定義域樹，搜索的范圍在值域樹根的位置按小波樹結構對應到低一級位置鄰近的一個區域，不采用全局搜索，以加快算法的速度。

　（5）對根節點在第2級小波子帶上的小波樹進行分形編碼，如果誤差小于等于設定的誤差閾值，則記錄分形參數；如果大于設定的誤差閾值，則設立標志位，對大于小波系數閾值的系數進行均勻量化編碼。
編碼算法流程圖如圖2所示。

　解碼是編碼的逆過程，由LL4、HL4、LH4、HH4逐級外推解碼出3級、2級、1級小波子帶，最后進行多級小波重構，恢復出原圖像。
4 實驗結果與分析
　對Lena、cameraman和couple 3幅256×256的標準測試灰度圖像進行了分形編碼解碼實驗，實驗環境為Core i3 M330 CPU，2GB內存，Windows XP系統。用Matlab進行仿真實驗，并將基本算法、參考文獻[8]算法與本文算法進行了比較。
　實驗1
　分別用上述3種方法對標準測試圖像Lena進行分形編碼解碼，結果如圖3所示。可以看出本文算法還存在一定的塊效應，這是由于對某些小波系數直接置0所引起的。
　實驗2
　對標準的測試圖像cameraman進行分形編碼解碼，結果如圖4所示。可以看出本文算法存在塊效應，同時人物的手部不是很清晰，還有改進的余地。
　實驗3
　對標準的測試圖像couple進行分形編碼解碼，結果如圖5所示。

　最后列出了各算法的編碼時間、PSNR和壓縮比，如表1所示。

　從表1可以看出，與基本算法相比，本文算法在解碼圖像質量上，Lena圖像在根采用單節點時PSNR略有提高，在根采用2×2塊時略有下降；couple圖像的PSNR值略微下降；cameraman圖像在根采用單節點時PSNR值提高了約1.8 dB，在根采用2×2塊時也提高了1.1 dB。與參考文獻[8]算法相比，3幅圖像的PSNR值都有很大提高，平均提高了5 dB。但是本文算法在一些圖像細節邊緣上不夠清晰，存在一定的塊效應，還有待改進，如考慮減小閾值或者設置感興趣區域。
　由于搜索匹配樹是在值域樹相應的鄰近區域搜索，沒有采用全局搜索，且沒有進行8種仿射變換，運算速度有很大改善，運算時間大約為基本算法的1/40，為參考文獻[8]算法的1/12。
從壓縮比來看，參考文獻[8]算法最高，本文算法次之，基本算法最低。對本文算法，根采用2×2塊時與根采用單節點相比，在解碼圖像略微降低的情況下，提高了壓縮比。
　將小波變換與分形編碼相結合對圖像進行壓縮編碼，發揮兩者的優勢是值得研究的方向。小波分解形成3個方向的子帶，自然地對分形編碼中的定義域塊和值域塊進行了分類，從而減少了編碼搜索的時間。同時，小波分解產生的各級子帶間具有較強的相似性，分形的優勢正好在于自相似性強的圖像，如何利用分形開采這種相似性，提高圖像解碼質量，有待于深入地研究。
參考文獻
[1] 夏良正，李久賢.數字圖像處理（第2版）[M].南京：東南大學出版社，2006.
[2] BARNSLEY M. Fractal everywhere[M]. San Diego， CA： Academic Press， 1988.
[3] JACQUIN A. A Fractal theory of iterated markov operators with application to digital image coding[D]. Atlanta： Georgia Institute of Technology， 1989.
[4] RINALDO R， CALVAGNO G. Image coding by block prediction of multiresolution subimages[J]. IEEE Transactions on Image Processing， 1995， 4（7）： 909-920.
[5] DAVIS G M. A wavelet-based analysis of fractal image compression[J]. IEEE Transactions on Image Processing， 1998，7（2）： 141-154
[6] 謝永華，傅德勝，任衛華.一種基于小波變換的圖象分形編碼壓縮算法的研究[J].中國圖象圖形學報，2003，8（7）：839-842.
[7] 張梁斌，奚李峰.一種基于小波域的分形編碼預測方法[J].計算機應用與軟件，2007，24（6）：68-70.
[8] 婁莉.一種基于小波域的分形圖像編碼改進算法[J].計算機技術與應用，2010（7）：134-136.
[9] 張宗念，馬義德，余英林.基于方向性零樹小波的分形圖像編碼[J].電子科學學刊，2000，22（5）：780-784.