基于混合分類和矩形劃分的快速分形編碼方法

摘要：針對分形圖像壓縮中矩形劃分計算量太大的問題，提出了一種混合分類方法并將其應用于圖像的矩不變量，得到了一種基于矩形劃分的快速分形編碼方法。實驗表明，該方法相對于全局搜索，在壓縮比和解碼質量略有下降的基礎上，能極大地提高分形編碼速度；與均勻分類方法相比，混合分類法可進一步提高分形編碼速度并改善解碼圖像質量，可以在一定的條件下取得壓縮比優勢。

關鍵詞：分形圖像壓縮; 迭代函數系統; 矩形劃分; 自適應分類; 混合分類

中圖分類號：TP391．41文獻標志碼：A

文章編號：1001－3695(2007)07－0064－03

0引言

分形圖像壓縮是近十幾年發展起來的一種新的圖像壓縮方法。它以迭代函數系統(Iterated Function System，IFS)為基礎，基于自然景物的自相似性進行數據壓縮。此項研究由M.Barnsley[1]首先提出；Jacquin[2]的基本自動分形圖像編碼(Basic Automation Fractal Image Coding)使分形圖像編碼進入了新時代；此后Y．Fisher[3]又對此方法進行了不斷的改進和完善。前期對值域塊的劃分都是采用正方形，忽略了圖像的灰階均勻性。采用矩形劃分[4]可以避免這種情況，但是采用矩形劃分的計算量相當大，導致編碼時間過長。本文提出了一種混合分類方法并將其應用于圖像的矩不變量，大大提高了編碼速度。

1分形圖像壓縮的基本模型

Jaquin在IFS的基礎上，提出了局部迭代函數系統(Partitioned Iterated Function System，PIFS)[5，6]，并據此第一個提出了全自動的基于分塊的分形編碼方法，它現已成為了分形圖像壓縮的基本模型。其基本過程如下：

對一幅待編碼圖像，先將其劃分為互不重疊的等大小圖像子塊，稱為值域塊(Range Block)，記為R；又將原圖像劃分為可以重疊的等大小的子塊，其尺寸比值域塊稍大(一般為兩倍)，稱為定義域塊(Domain Block)，記為D；所有這些定義域塊組成定義域塊庫(Domain Pool)SD，它構成了搜索空間。分形編碼可描述為對每一個值域塊R，求解如下的最優化問題：

對每一個值域塊，它所對應的最優化問題（式(1)）的解就構成了這個值域塊的編碼參數。其中包括D(此時稱為該值域塊的最優匹配塊)的位置、τi的代號和f的信息。這樣所有值域塊的編碼參數就一起定義了一個PIFS，再對該PIFS的參數進行量化、熵編碼并存儲成文件就完成了整幅圖像的編碼。

分形解碼很簡單，只要對上述得到的文件進行熵解碼、逆量化先恢復出PIFS，再用該PIFS對任意初始圖像反復迭代即可。

2基于矩形劃分的分形編碼方法

與傳統的分形圖像壓縮基本模型相比，基于矩形劃分的分形編碼方法有以下不同：

(1)按照值域塊最小維的大小由大到小進行編碼

編碼時，首先從值域塊庫中選取最小維最大的值域塊，為其尋找最優匹配塊。例如：10×7的塊要先于20×6的塊進行匹配，雖然后者包含的像素數目多于前者。如果當前正在匹配的值域塊尺寸和下一個待匹配塊相同，則為當前值域塊建立的定義域塊庫就可以直接被下一個待匹配塊使用，無須為其重新建立定義域塊庫。

(2)定義域塊只有四種旋轉—反射變換

其包含順時針作0、180°旋轉及沿水平中線、垂直中線反射。

(3)矩形分割標準

于是得到了一系列矩不變量以構成一個特征向量(θ1，θ2，…)。筆者只采用矩不變量的第一維分量。將矩不變量特征值等分成（預先給定的）K個小區間，然后將特征值落在第i個小區間的圖像塊歸為第i類，在搜索時只需要搜索值域塊的特征值所在區間的定義域塊。這樣就減少了搜索次數，提高了編碼速度。筆者稱這種等分特征區間的方法為均勻分類法。

本文中所有實驗都使用標準的256×256的灰度測試圖像Lena；實驗環境為P4 2．6 GHz/256 MB RAM/VC++.NET；定義域塊的大小都取為值域塊的兩倍，相鄰定義域塊的水平和垂直間隔都取為值域塊的大小。在均勻分類的情況下，經過統計，幾乎所有的定義域塊的分布都呈現一種極少數區間包含大多數塊的情況。圖1是9×6和5×4的值域塊對應的定義域塊分布圖，它們對應的定義域塊數目分別為1 107和3 150。

從圖中看出，各個區間定義域塊數目的分布很不均勻，這導致以下后果：當值域塊的矩不變量落在分布數目較多的區間時，搜索此區間相當耗時；而落在分布數目較少的區間時，則很難找到匹配塊，且最終的解碼圖像質量也不理想。為了解決分布數目不均勻的問題，提出了自適應分類方法。

從上面的實驗結果看出，自適應分類幾乎不可能將編碼時間降低到9s以下，而均勻分類卻可以。原因是：在編碼過程中，對不同尺寸的值域塊要分別為其建立不同尺寸的定義域塊庫，而對定義域塊庫自適應分類需要一定的時間。在此引進重復率γ，γ即為具有同樣尺寸的值域塊數目。經過統計，在全局搜索的情況下，重復率為1的值域塊數目為358；在自適應分類下，當均勻度閾值T＝40時，重復率為1的值域塊數目為363。對這種重復率很低的值域塊進行自適應分類所耗費的時間要遠大于通過自適應分類所減少的塊搜索時間，所以相對于均勻分類，自適應分類法編碼速度反而變慢。然而，在全局搜索的情況下，重復率大于等于30的值域塊數目為122；在均勻分類下，當分類數M＝40時，重復率大于等于30的值域塊數目為93。對這種重復率很高的值域塊對應的定義域塊進行自適應分類就會取得比較好的加速效果，而且可以取得比較好的解碼圖像。結合均勻分類和自適應分類的優點，提出了混合分類法。

3．3混合分類

筆者引進臨界因子α，α為實驗統計得出的常數。用α來衡量值域塊是否需要進行自適應分類。當值域塊的重復率大于α時，對此尺寸的值域塊所對應的定義域塊庫進行自適應分類，否則進行均勻分類，稱此分類方法為混合分類法。此方法對任何一種連續特征也是適用的。

4數值實驗及結果分析

實驗參數：均勻度閾值T＝40，臨界因子α＝15，匹配誤差取為30，最小塊尺寸取為3×3，分類數M＝20，30，…，90。

首先用全局搜索法進行編碼，其編碼時間為64．32 s，PSNR為30．12 dB，壓縮比為14．01。均勻分類和混合分類每一步值域塊的劃分都會影響后續值域塊，從而影響最終的結果，所以無法將均勻分類和混合分類統一在同一種塊劃分方案中比較優劣。采取以下比較策略：調整類數M，使均勻分類近似與混合分類的編碼時間相同，比較圖像解碼質量和壓縮比；然后調整M，使兩種分類方法的圖像解碼質量近似相同，比較編碼時間和壓縮比。其結果如表3、4所示。

表3編碼時間基本相同時兩種分類方法的比較

實驗結果分析如下：

（1）相對于全局搜索方法，均勻分類極大地提高了分形編碼的速度。例如，當分類數目為166時，其編碼時間由原來的64．32 s降低為3．331 s，編碼速度提高了近20倍。而解碼圖像質量只有30．12-28．29=1．83 dB的損失。

（2）相對于均勻分類，混合分類法可以在編碼時間基本相同的前提下取得更好的解碼質量；在解碼質量基本相同的前提下取得更快的編碼速度。至于壓縮比，當固定均勻度閾值T時，存在常數N，在分類數M＜N時，均勻分類的壓縮比大于混合分類；當分類數M＞N時，均勻分類的壓縮比就小于混合分類，而且隨著分類數M的增大，混合分類的優勢會越來越明顯。另外，均勻度閾值T也是一個可控參數。一般來說，當分類數M固定時，均勻度閾值T并不是越小編碼速度越快，而是存在常數T0。T由大到小趨近T0，編碼速度會明顯加快，但是圖像解碼質量會有所降低；如果T＜T0后，T繼續減小，編碼時間反而會增加，而且圖像解碼質量也會降低。

5結束語

首先利用圖像的矩不變量實現了均勻分類，針對均勻分類各區間數目分布相當不均勻的問題，提出了自適應分類方法；然后分析了自適應分類方法的缺點，將兩種分類方法結合提出了混合分類方法，得到了一種基于矩形劃分的快速分形編碼方法。在實驗中發現，本文使用的矩形分割標準有一定的缺陷，在今后的工作中打算提出一種新的分割標準進行矩形塊的分割。另外該方法還可與其他加速方法(如特征向量的方法)相結合，以進一步加快編碼速度。

參考文獻：

[1]BARNSLEY M F.Fractals everywhere[M]. 2nd ed. Boston:Academic Press， 1993.

[2]JACQUIN A E. Fractal image coding: a review[J]. Proceedings of the IEEE， 1993，81(10):1451－1465.

[3]FISHER Y. Fractal image compression[J]. Fractals， 1994，2(3):57－59.

[4]FISHER Y， MENLOVE S. Fractal encoding with HV partitions，fractal image compression theory and application[M]. New York: Springer－Verlag， 1994:23－26.

[5]JACQUIN A E. A novel fractal block－coding technique for digital images: proc.of the ICASSP’90[C].[S.l.]:[s.n.]， 1990:2225－2228.

[6]JACQUIN A E. Image coding based on a fractal theory of rerated contractive image transformations[J]. IEEE Transactions on Image Processing， 1992，1(1):18－30.

[7]陳作平，葉正麟，高雪峰，等.一種基于矩不變量的快速分形編碼方法[J].計算機工程與應用，2004，40(33):62－66.

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