基于四叉樹的分形圖像壓縮編碼算法的Ｃ＋＋實現

摘要：該文首先介紹了分形圖像壓縮的基本理論，如迭代函數系統，拼貼定理等。然后重點研究了基于四叉樹的分形圖像壓縮編碼算法。最后通過編寫代碼實現此算法，并與基本的分形圖像壓縮算法進行試驗比較，進行總結。

關鍵詞：分形圖像壓縮；迭代函數系統；固定分塊分形圖像壓縮；四叉樹分形圖像壓縮

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)35-2220-03

Based on Quadtree Fractal Image Compression Algorithm for Research and Implementation

JIANG Yu-sheng， SHAO Wei， DING Lan-xin

(College of Communication Engineering， Chongqing University， Chongqing 400044， China)

Abstract: This paper first introduced the basic theory of the fractal image compression ，such as iteration function system(IFS)， collage theorem， and so on. And then focus on the Quadtree based on the fractal image compression algorithm. Finally realizes this algorithm through the compilation code， and carries on the experiment with the basic fractal image compression algorithm to compare， carries on the summary.

Key words: fractal image compression; iteration function system; fixed piecemeal fractal image compression; quadtree fractal image compression

1 引言

1973年，曼德勃羅（B.B.Mandelbrot）首次提出了分維和分形幾何的設想。由于不規則現象在自然界是普遍存在的，因此分形幾何又稱為描述大自然的幾何學[1]。分形幾何建立以后，很快就引起了許多學科的關注，這是由于它不僅在理論上，而且在實用上都具有重要價值。特別隨著計算機技術的發展，分形思想和方法在模式識別、自然圖像的模擬、信號處理等各個領域都取得了巨大的成功。

1988年，Barnsley對幾幅圖像進行分形壓縮編碼，獲得了1000：1的壓縮比，雖然這只是對特定的圖像而言，但足以顯示分形技術在圖像編碼方面的巨大潛力[2]。1990年Jacquin利用圖像間的相似性，提出了一種可用計算機完全自動實現的分形圖像編碼算法，為分形圖像編碼的研究帶來了一次質的飛躍。自Jacquin之后，分形圖像編碼引起了世界各國研究人員的廣泛興趣和關注，成為目前編碼研究的熱點。

2 分形圖像壓縮編碼理論

分形圖像壓縮是一種利用自相識性特點的圖像壓縮方法。為了達到壓縮的目的，Barnsley使用吸引子模型的二維仿射變換描繪原始圖像。在分形圖像壓縮的過程中，他提出迭代函數系統和拼貼定理。目前，這一理論已成為分形圖像壓縮的理論基礎。

壓縮映射：變換是指將一個空間上的點根據某種事先定義的法則，使之與另一個空間上的點相對應，變換有時也稱為映射。從一個空間x1到另一個空間x2的變換通常記為f :x1→x2。設w:X→X是度量空間(x，d)上的一個映射，其中X∈R2是豪斯道夫距離。如果存在一個常數s(0

不動點定義：如果存在xw∈X，使得w(xw)=xw，則稱xw為壓縮映射w的不動點。壓縮變換存在唯一不動點，且不動點可以通過迭代得到。

壓縮映射定理：設w:X→X是完備度量空間(X，d)上的壓縮映射，則存在惟一的不動點xw∈X，對任何x∈X，序列{won(x):n=1，2，…}收斂于xw。即 Ax∈X。

迭代函數系統：完備度量空間(X，d)與壓縮因子分別為s1，s2，…sn的n個壓縮映射wn，構成了一個迭代函數系統(IFS)。其壓縮因子為s=max{s1，s2，…sn}，一個IFS可以表示為{X:w1，w2，…，wn}。

拼貼定理：設(X，d)是完備的度量空間，給定集合L∈H(X)及數ε＞0。如果能選取到一個IFS{X:wj，j=1，2，…，n}，其壓縮因子為s(0，則有：。A為該IFS的不動點(又稱吸引子)。

3 四叉樹分形圖像壓縮編碼

根據第二節的定理，可以得出：一幅具有自相似的圖像可以由一組壓縮變換表示，而這組壓縮變換的吸引子就是該圖像的編碼結果。但是，能將整幅圖像進行上述“自身復制”壓縮變換w，取決于圖像本身的自相似性質 ，并不總是存在。而且，許多圖像并不總是單一的景物，比如一副自然風光圖，畫面中可能有天空的白云，山巒，樹木，河流等。這種圖像如果有自相似性，一般也基本是分別存在畫面內的各個對象自身之中，所以，對于這種圖像采用 分形編碼就必須先把原圖分割成幾個不同的對象，然后再對每個對象提取碼，而這種分割一般需要人機交互才能完成，而且費時費力，難以實時實現。

1990年，Jacqain 提出了全自動的分形圖像壓縮算法——固定分塊分形圖像壓縮[2]，該方法以局部的仿射變換代替全局的仿射變換，基于圖像的分塊，首先把原始圖像分割成一個個尺寸為k×k的不重疊方形像塊，稱為值域塊，記為R1，R2，…， ；同時又把原圖分割成若干尺寸為L×L的可以重疊的方形D2像塊D1，D2，…， ，稱為定義域塊。規定定義域塊的尺寸大于值域塊的尺寸，即L>K，一般取L=2K。通過搜索匹配得到圖像的 。圖1所示為分塊分形圖像壓縮編碼系統框圖[5]。

固定分塊分形圖像編碼的缺點在于尋找Ri和Di兩者的匹配時非常耗時，在圖像還原的時候，還將出現“方塊效應”，會影響圖像的還原質量。

1991年，Fisher 對該方法進行改進，提出了四叉樹分形圖像編碼方法。它具有分塊靈活性高，壓縮比率高的優點，是目前分形圖像壓縮編碼中的主要方法。下面我們將重點介紹四叉樹分形圖像編碼方法[3-4]。

四叉樹方法是一種自適應分塊方法。它將圖像表示成一棵四叉樹，樹根就是原圖像本身。除葉節點外，樹中每個節點均有4個子節點，分別對應于原圖像（或圖像塊）4個象限的子塊。

其分割原理如圖2所示[6]。

圖像自適應分塊的目的是將圖像合理地劃分成不同尺寸的R塊，使任意一塊都能找到合適的D塊與之相應。這樣圖像中粗糙的部分能以較大的圖像塊進行變換壓縮，提高壓縮比；而圖像中精細的部分以較小的圖像塊進行變換壓縮，保證較高的圖像還原質量。和經典的固定分塊分形圖像編碼相比，四叉樹方法能進一步提高壓縮比。

為保證圖像質量同時減少分塊數，一般在分割圖像之前，設定四叉樹最大和最小深度以及最大允許誤差，即設定最小和最大R塊尺寸及尋找匹配塊標準。用四分法按設定的最小深度級分割圖像。針對圖像中與該深度級對應的每一方塊圖像找其最佳匹配塊。如找到，則標為R，對應的匹配塊記為D，并且不再對該方塊進行細分。如某圖像方塊在指定誤差下沒有找到最佳匹配塊，則把該子塊細分成等大小的四塊。再對這四個分塊分別找其匹配塊。該過程不斷進行，直到設定的最大深度級。

具體實現步驟如下[7]：

Step 1、將原始圖像分成四個大小相同的方塊，判斷每個方塊是否滿足一致性標準。

Step 2、設定劃分的深度范圍，即值域塊所允許的最大與最小尺寸。

Step 3、如果滿足劃分的最小深度范圍就不再繼續分裂(即使沒有達到一致性標準)；否則如果不滿足一致性標準就再細分成四個方塊，并對細分得到的方塊作深度范圍和一致性檢驗。

Step 4、重復Step 3，直到所有的方塊都滿足一致性標準才結束。

經過以上方法進行分解后，其最終的值域塊的集合可能包含多種不同尺寸的方塊。雖然從理論上來說，如果塊的大小取1×1或2×2或N×N，是可行的，在分形圖像壓縮中顯然是不合適的。因此，在實際中我們常取最小塊為4×4，最大塊 (N/2)×(N/2)。

4 四叉樹分形編碼的實現及分析

在本為中，我們根據四叉樹分形編碼的算法，利用C++Builder6.0編寫程序代碼，分形編碼的流程圖如3所示，并將一幅256×256的cat的BMP彩色圖像進行試驗。試驗測試平臺：CPU為celeron 1.66G，RAM為1.0G，操作系統為：Windows XP professional。測試圖像如圖4所示，

我們利用固定分塊分形圖像壓縮編碼進行測試結果如圖5所示。

原始圖像 解碼圖像 原始圖像解碼圖像

圖4 四叉樹分形編碼測試圖像 圖5 固定分塊分形圖像壓縮編碼測試圖像

表1給出了兩種不同方法下測試結果的比較：

表1 固定分塊與四叉樹測試結果的比較

從以上的比較可看出，本文編寫的基于四叉樹的分形圖像壓縮程序代碼與固定分塊的分形圖像編碼相比，無論從壓縮比還是壓縮時間和信噪比上，都有了很大的改進，而且從測試圖像上可以看出，解碼圖像的質量也有了很大的改善。

5 結論

雖然基于四叉樹的分形圖像壓縮有了一定的改善，但仍然存在以下缺點：恢復圖像中仍然有較為嚴重的方塊效應；在壓縮時，運算量較大，壓縮時間較長。而造成這種的原因為：沒有考慮圖像的內容和含義，只進行盲目的方塊分割，從而導致較高壓縮比時出現嚴重的方塊效應；人眼視覺系統（HVS）沒有充分考慮。

根據以上分析，我們可以進行針對性的改進，從而得到更好的壓縮效果。相信經過不斷的努力，基于分形的圖像壓縮方法將有著更好的發展前景。

參考文獻：

[1] Barnsley M F，Hurd L P.Fractal image compression[M].Wellesley:AK Peters Ltd，1993.

[2] Jacquin A E.image coding: a review[J].Proceeding of the IEEE，1993，81(10):1451-1465.

[3] Fisher Y.Fractal image compression[M].Fractals，1994.

[4] Fisher Y.Fractal image compression theory and appplication[M].Springer-Verlag，NewYork，1995.

[5] 張春田，蘇育挺，張靜.數字圖像壓縮編碼[M].北京:清華大學出版社，2006

[6] 董云朝，陳賀新.基于四叉樹的自適應門限分形圖像IFS壓縮方法[J].中國圖像圖形學報，2000，5(11).

[7] 鄭運平，陳傳波.一種基于新型四叉樹的快速分形圖像壓縮算法[J].小型微型計算機系統，2007，28(8).