袁宗文　陳初俠

摘要：盡管更快的圖像解碼方法應用更為廣泛，但在某些特殊的應用場合，需要漸進可控的圖像解碼方法.在保證最終解碼圖像不變的前提下，將傳統(tǒng)壓縮映射的固定參數(shù)改為可變參數(shù)，通過調節(jié)這些參數(shù)實現(xiàn)解碼過程漸進可控.實驗結果表明，傳統(tǒng)分形解碼約迭代8次即已收斂，提出的算法可實現(xiàn)迭代8到36次解碼收斂，實現(xiàn)了解碼過程靈活可控，而且該算法可更多地展現(xiàn)解碼圖像序列的生成過程.

關鍵詞：分形;解碼;收斂;可控

中圖分類號：TP391? 文獻標識碼：A? 文章編號：1673-260X（2019）09-0059-03

分形圖像編碼因其較高的壓縮比、分辨率無關性、迭代解碼的新穎思想而受到人們廣泛關注.分形圖像編碼是非對稱的，即編碼較為耗時，解碼又非?？?在近二十多年中，學者們發(fā)表了大量的論文[1-11]，大都圍繞怎樣加快分形圖像編碼速度，但仍也有少量論文討論了如何加快分形解碼速度[12-13].然而在某些特殊的應用場合，如卡通的計算機輔助制作、圖像解碼的教學、信號的窄帶漸進傳輸，需要一種較慢的可以控制的漸進解碼方式.JPEG2000支持漸進圖像傳輸技術，它解決了在窄帶信道中以漸進的方式傳輸圖像信息，即先以較低的碼流傳輸圖像的輪廓信息，然后同樣以較低的碼流逐漸傳輸圖像的細節(jié)信息，這樣既可解決窄帶用戶焦躁的等待問題，又可滿足用戶對圖像質量的不同要求.分形圖像編碼還沒有漸進傳輸上的應用，重要原因是傳統(tǒng)的分形解碼無法控制，它從初始圖像到吸引子需要的迭代次數(shù)比較固定，一般都在7到8步左右.本文提出一種漸進可控的分形解碼算法，可以將解碼迭代的次數(shù)控制在8到36步之間.

1 算法分析

1.1 改進的不動點定理

不動點定理[14]：定義圖像空間（，||·||）上的變換W：→.如果存在0≤s<1使得

||（W（C），W（B））||≤s||C，B||，C<B∈? （1）

則稱W為壓縮映射.設圖像序列{Un}滿足Un+1=W（Un），n≥0，U0=U，U是空間（，||·||）中的任意圖像，則在壓縮映射W作用下的圖像序列有唯一不動點U*=U∞，也就是說存在唯一圖像U*，使得W（U*）=U*.

改進的不動點定理：定義圖像空間（，||·||）上的變換S：→，滿足

因為0≤s<1，所以0≤w1+sw2+s2w3<1，所以S是壓縮映射的.另一方面，設U*為W的不動點，則

從而U*也是s的不動點.所以，S是壓縮映射的且與W具有相同的不動點.

證畢.

1.2 算法的實現(xiàn)方案

傳統(tǒng)的分形解碼是由分形碼描述的壓縮映射W對任意一幅圖像U反復迭代完成的，根據(jù)拼貼定理，其不動點U*就是原圖像Uorg的一個近似圖像.即：

通常情況下，不論原圖像是什么，滿足式（3）中的N約為8，所以這是一個不能控制的迭代過程.基于改進的定理，我們使用壓縮映射S代替W，通過改變加權系數(shù)，可以很好地實現(xiàn)對迭代過程的控制，而且其不動點也是原圖像的一個近似圖像，即最終的解碼圖像質量是相同的.實現(xiàn)的方案如圖1（b）所描述.

當然在此基礎上，還可以構造更為復雜的漸進解碼方案，例如可以構造變換

式中加權系數(shù)w1，w2，w3，…，wN∈[0，1）且w1+w2+w3+…+wN=1，可以證明該S也是壓縮映射的且與W具有相同的不動點，不過可以預見，這樣的解碼方案會因其復雜性反而降低其實用性.此外，改進方案中因為包含了兩次壓縮映射W，所以當預設的迭代次數(shù)N為奇數(shù)時，前（N-1）/2次采用本方案，對于最后一次即第（N-1）/2+1次，可令w3=0，w2=1-w1，而w1保持不變，再進行迭代解碼，這樣就可以使得迭代次數(shù)能任意設置，同時保證了不動點圖像不變.

2 實驗結果分析

改進方案的加權系數(shù)w1，w2，w3中只有兩個變量是獨立的，我們可以任意改變其中兩個系數(shù)實現(xiàn)對解碼速度的控制.為顯示該系數(shù)對解碼的影響，實驗中，我們取了512×512的Lena灰度圖像，編碼采用傳統(tǒng)方案，圖像采用固定分割，值域塊大小為8×8，解碼時令w2、w3取不同值，得到漸進解碼結果如圖2所示.

圖2中，圖例baseline曲線表示傳統(tǒng)分形解碼，其他曲線為改進方案解碼.可見改進方案解碼比傳統(tǒng)解碼速度更為緩慢，改進方案解碼具有更多的選擇和解碼可控的特點.為了主觀感受改進方案漸進解碼的特點，我們可以從圖2中任取一條非baseline曲線，以圖像序列的方式展示它的解碼過程，譬如取w2=0.2，w3=0.2對應的曲線，得到的解碼圖像序列如圖3所示.初始圖像為全黑圖像，其中圖3（k）為第36次迭代，其PSNR=30.26dB，與不動點圖像的PSNR=30.31dB相差0.05dB，表明已基本收斂（見圖2（a））.

作為對比，同樣從圖2中取出baseline曲線以展示解碼過程，即傳統(tǒng)分形解碼過程，得到的圖像序列如圖4所示，圖4（e）為第8次迭代，其PSNR=30.28dB，表明已基本收斂.可見改進方案解碼較傳統(tǒng)方案解碼的收斂速度要慢得多，而且如果調整加權系數(shù)，可以實現(xiàn)不同的收斂速度，特別地如果令w2=1，則改進方案就變成傳統(tǒng)的方案.

我們還計算了改進方案相鄰解碼圖像的差值圖像，以顯示其細節(jié)的增加情況.設Un表示第n次迭代解碼圖像，圖5從左到右，從上到下，依次為：U2-U0、U4-U2、U6-U4、…、U18-U16.結果表明，解碼圖像序列細節(jié)以較均勻的比例逐漸增加.如果我們改變系數(shù)，可以得到更多的細節(jié)增加特點.

3 結論

基于傳統(tǒng)分形解碼的過程不能控制的特點，提出了一種可以控制的漸進分形解碼算法，而且這種解碼算法不需要改變原有的編碼算法，實現(xiàn)過程簡單.對于一些特殊的應用場合具有潛在的應用價值.

——————————

參考文獻：

〔1〕Barnsley M F. Fractal everywhere[M].Academic Press，1988：375-377.

〔2〕Jacquin A E. Image coding based on a fractal theory of iterated contractive image? transformations[J]. IEEE Trans. Image Process，1992，1 （1）： 18-30.

〔3〕Davis G M. A wavelet-based analysis of fractal image compression[J].IEEE Transaction on Image Processing，F(xiàn)ebruary，1988，7（2）：141-154.

〔4〕Fisher Y， Jacobs E W， Boss R D. Image compression：a study of the iterated transform method[J].Signal Processing，1992，29（3）：251-263.

〔5〕Hurtgen B， Stiller C. Fast hierarchical codebook search for fractal coding of still image[C].Berlin，Germany，1993.397-408.

〔6〕Martio P， Michele N. Speed up in fractal image coding：comparison of methods[J].IEEE Trans. on Image Processing，2000，9（6）：1002-1009.

〔7〕He C J， Yang S X， Huang X Y. Variance-based accelerating scheme for fractal image encoding[J].IEE Electronics Letters， 2004，40（2）： 115-116.

〔8〕Lai C， Lam K， Siu W. Improved searching scheme for fractal image coding[J].IEE Electronics Letters， 2002， 38（25）： 1653-2654.

〔9〕Lai C， Lam K， Siu W. A fast fractal image coding based on kick-out and zero contrast conditions[J]. IEEE Transactions on Image Processing， 2003，12（11）：1398-1403.

〔10〕Wohlberg B， Jager G D. A review of the fractal image coding literature[J].IEEE Transactions on Image Processing，1999，8（12）： 1716-1729.

〔11〕Lototskiy R V.Images fractal compression optimization by means of artificial Kohonen neural networks[J].Journal of Automation and Informfation? Sciences，2003，35（1）：50-60.

〔12〕Moon Y H， Kim H S， Kim J H. A fast fractal decoding algorithm based on the selection of an initial image[J].IEEE Trans. Image Process， 2000，9（5）： 941-945.

〔13〕丁政建，袁宗文，繆東升.基于對比度因子調節(jié)的快速分形解碼算法[J].蘭州理工大學學報，2007，33（4）：110-112.

〔14〕夏道行，嚴紹宗，舒五昌.泛函分析第二教程[M].北京：高等教育出版社，2009.338-345.