基于圖像子塊特征的快速分形圖像編碼算法

摘要:根據圖像子塊的像素分布特征，提出了一種基于方差和DCT變換的混合快速分形圖像編碼算法，并在此基礎上引入了平滑塊的概念。該算法在大幅度提高分形圖像編碼速度的同時，很好地改善了壓縮率和解碼圖像的質量。實驗表明該方法具有優良的性能，在編碼時間優于方差快速編碼方法的前提下，解碼圖像的質量和壓縮率可以好于基本分形圖像編碼算法。

關鍵詞:分形圖像編碼; 方差; 離散余弦變換; 平滑塊

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001－3695(2008)02－0458－02

分形圖像編碼算法是一種很有發展前途的新型數字圖像編碼技術，它的最大優點是可以在獲得高壓縮率的前提下，比較好地維持解碼圖像的質量。隨著當今計算機相關領域信息處理量的日趨膨脹，基本分形圖像編碼算法(BFC)有著很高的研究價值;但其編碼時間過長，不實用。為了解決這個問題，C.K.Lee等人[1]，何傳江等人[2，3]，C.M.Lai等人[4]提出了基于方差的快速分形圖像編碼(VFC)算法，大幅提升了分形編碼的速度，但解碼圖像的質量也有了比較明顯的下降。針對方差編碼算法中存在的問題，本文提出了一種基于選擇策略的混合編碼算法。這種算法具有以下優點:a)引入了平滑塊的概念。如果輸入區塊的方差值小于一個預先設定的閾值，則被認為是一個平滑塊，無須參加匹配搜索，僅需保存該區塊的像素平均值，可以有效地加快編碼速度并提高壓縮率。b)引入了最小化均方誤差閾值。對于不適合分形圖像編碼的區塊采用DCT變換進行編碼，有效地提升了解碼圖像的質量。對于一般的圖像來說，不適合分形編碼的區塊僅占全部圖像子塊的很小部分，采用此種選擇策略對快速編碼的速度影響很小。同時，這一小部分區塊也是造成分形解碼圖像質量下降的主要因素，對這些區塊采用DCT變換編碼可以有效地提升解碼圖像質量。

1分形圖像編碼算法概述

1.1基本分形圖像編碼算法(BFC)

基本分形圖像編碼基于壓縮映射定理和局部迭代函數系統(partitioned iterated function system，PIFS)，利用一組惟一收斂的自仿射映射參數來重建與原圖像高度逼近的分形吸引子圖像。其主要算法流程如圖1所示，R為區塊，D為域塊，分別通過滑動窗口方法獲得。

在分形圖像編碼算法中，影響編碼速度的主要因素是區塊R和對應域塊D的匹配搜索過程。在基本編碼算法中，匹配搜索采用的是全局遍歷的方法，因此需要很長的編碼時間。在匹配搜索過程中，區塊和與其匹配的域塊需要最小化以下等式:

E(R，D)=‖R-(s×D+oI)‖(1)

其中:s代表自仿射結構中的壓縮因子;o代表仿射偏移量;‖·‖是二泛數。

根據上述算法流程，存儲所有的匹配映射參數即完成對整幅圖像的分形編碼，因為存儲這些參數需要的存儲量很小，因此分形圖像編碼可以獲得很高的壓縮率。

1.2方差快速分形圖像編碼算法(VFC)

為了解決基本分形編碼算法中編碼時間過長的問題，C.K.Lee等人由式(1)，通過最小二乘法導出式(2):

其中:r是區塊R的平均值;d是域塊D的平均值。

根據式(2)，可以認為當一個區塊和一個域塊是最優匹配時，它們的方差應當是接近的。因此，可以根據一個預設的方差閾值對區塊和域塊進行一個預分類，對每一個區塊，根據方差閾值選取一些與之接近的域塊，并僅在其中搜索與之匹配的最佳域塊，避免全局遍歷搜索。因此可以大幅加快分形編碼的速度，但方差編碼算法也帶來了比較明顯的解碼圖像質量下降。

2最小化均方誤差閾值分類法(MFC)

上述的分形圖像編碼算法選取的都是如下的整體自仿射映射結構，通過對這個結構的分析不難發現，對于內部像素值波動較小的區塊—域塊對，自仿射結構一般會取得比較好的匹配結果;對于內部像素值波動較大的區塊—域塊對，自仿射映射結構就有可能變得很不適應，具有模糊效應，可能產生很大的匹配誤差。

針對上述問題，筆者提出了一類基于最小化均方誤差閾值分類法的編碼算法:首先，設置一個最小化均方誤差閾值ε，在對所有的區塊采用方差算法找到合適的區塊—域塊對后，將每個區塊對應的E(R，D)與ε比較。當E(R，D)<ε時，認為該區塊適用自仿射映射分形結構進行編碼;當E(R，D)>ε時，則認為雖然D在整幅圖像中是該區塊的最佳匹配塊，但D經過自仿射映射結構后來表達該區塊的效果并不理想，對于這樣的區塊，本文采用DCT變換編碼來代替分形編碼。

采用最小化均方誤差閾值進行分類具有兩方面好處:a)通過設置合適的閾值，原圖像中大部分區塊仍采用自仿射映射分形結構，這樣可以保持分形編碼的高壓縮率和方差快速算法的快速性。b)通過實驗可知，少數不適合自仿射映射分形結構編碼的區塊是造成分形解碼圖像質量下降的主要原因。對這些區塊采用DCT變換編碼，可以有效提升解碼圖像的質量，同時又基本不會對壓縮率和編碼時間造成影響。

3平滑塊方法

不難得出，當一個區塊的內部像素值波動較小時，其方差往往較小;當一個區塊的內部像素值波動較大時，其方差往往較大。因此，可以設置一個方差閾值η，并依據它對區塊進行分類。當一個區塊R的方差小于η時，R被標記為平滑塊，無須參加分形匹配搜索過程，將R的均值作為其編碼，代替R中所有的像素值;當R的方差大于η時，R被標記為非平滑塊，參加分形匹配搜索過程。基于最小化均方誤差閾值分類法和平滑塊法，就可以設計出如圖2所示的混合編碼算法(AMFC)。

該混合算法除了具有最小化均方誤差閾值分類法的優點外，平滑塊方法的采用可以進一步加快編碼速度和提高壓縮率，因此可以更加增進分形編碼的實用性。

4實驗結果

實驗采用了256×256，8 bit的Lena圖像來驗證所提出編碼算法的性能，所有實驗均運行在P4 2.8 GHz CPU，512 MB內存，Windows XP的PC上，采用VC++ 6.0的編程語言。

實驗中，區塊大小為4×4，域塊大小為8×8，參數s和o分別按4和6 bit進行量化，編碼完成后，對得到的分形碼和DCT變換系數采用Huffman編碼。實驗設置了三個參數來控制編碼的質量和時間，即方差搜索窗口w%，平滑塊閾值η和最小化均方誤差閾值ε，一般來說，w%=5%。

表1顯示出了最小化均方誤差閾值分類法的編碼性能。首先可以看到，相對于BFC算法和VFC算法，MFC可以得到更好的解碼圖像質量，且編碼時間基本等于VFC算法的編碼時間;特別是當ε=2 500時，解碼圖像質量達到最大值。但另一方面，MFC降低了整體編碼的壓縮率，從一定程度上降低了編碼的性能，減小了分形圖像編碼的優勢。

引入更多的ε值，可以得到PSNR隨ε變化的曲線如圖3所示，可以得到，當ε在2 500附近時，PSNR可以取得最大值。

圖4顯示了壓縮率隨著ε變化的曲線，壓縮率隨著ε的增大先減小再升高，最終趨于VFC算法的壓縮率。可以看到，當ε在2 500附近時，壓縮率最低。但相比于VFC算法來說，壓縮率只下降了0.5左右，因此，MFC算法對于壓縮率的影響并不是很大。

表2顯示出了基于最小化均方誤差閾值分類和平滑塊方法的編碼算法(AMFC)的優秀性能，可以看到，隨著η的增大，編碼時間減少，壓縮率增大。當η=900時，AMFC算法的PSNR與BFC相當，但編碼時間比VFC快大約三倍，壓縮率提高2.2。因此，AMFC算法相對于BFC#65380;VFC算法，具有更好的性能。

5結束語

通過對圖像子塊的像素分布特點的分析，基于最小化均方誤差閾值分類法和平滑塊方法，本文提出了一種有效混合分形圖像編碼算法。該算法通過引入DCT變換編碼，有效地解決了以往分形圖像編碼算法單純依靠自仿射結構所難以克服的質量瓶頸;同時，通過平滑塊方法，有效地提升了壓縮率，進一步加快了編碼的速度。大量實驗結果表明，相對于BFC和VFC算法，該算法具有更好的性能和更高的應用價值。

參考文獻:

[1]LEE C K， LEE W K. Fast fractal image block coding based on local variances[J]. IEEE Trans on Image Processing， 1998，7(6):888－891.

[2]HE Chuan－jiang， YANG S X， HUANG X. Variance－based accelerating scheme for fractal image encoding[J]. Electronics Letters， 2004，40(2):115－116.

[3]何傳江，蔣海軍，黃席樾.快速分形圖像編碼局部方差算法的改進[J].計算機仿真，2004，21(6):141－144.

[4] LAI C M， LAM K M， SIU W C. Improved searching scheme for fractal image coding[J]. Electronics Letters， 2002，38(25):1653－1654.

[5]FISHER Y. Fractal image compression－theory and application[M]. New York: Springer－Verlag， 1994.

[6]JACQUIN A E. Fractal image coding: a review[C]//Proc of the IEEE. 1993:1451－1456.

[7]WU Yun－gi， HUANG Ming－zhi， WEN Yu－ling. Fractal image compression with variance and mean[C]//Proc of IEEE ICME. Maryland:[s.n.]， 2003:353－356.

[8]SAUPE D， JACOB S. Variance－based quadtrees in fractal image compression[J]. Electronics Letters， 1997，33(1):46－48.

[9]LEE S M. A fast variance－ordered domain block search algorithm for fractal encoding[J]. IEEE Trans on Consumer Electronics， 1999，45(2):275－277.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”