一種基于分塊的分形圖像壓縮方法

唐國維，韓鵬宇，王 艾，王苫社，施國俊

（1.東北石油大學計算機與信息技術學院，黑龍江大慶 163318； 2.東北石油大學石油工程學院，黑龍江大慶163318； 3.哈爾濱工業(yè)大學計算機科學與技術學院，黑龍江哈爾濱 150001； 4.大慶油田有限責任公司第八采油廠，黑龍江大慶 163514）

一種基于分塊的分形圖像壓縮方法

唐國維1，韓鵬宇2，王 艾1，王苫社3，施國俊4

（1.東北石油大學計算機與信息技術學院，黑龍江大慶 163318； 2.東北石油大學石油工程學院，黑龍江大慶163318； 3.哈爾濱工業(yè)大學計算機科學與技術學院，黑龍江哈爾濱 150001； 4.大慶油田有限責任公司第八采油廠，黑龍江大慶 163514）

分形編碼具有高壓縮比的特點，但在編碼過程中其匹配搜索時間開銷巨大.提出一種基于分塊的分形圖像壓縮方法：依據人眼視覺特性在PSNR變化不大的情況下，圖像主觀質量感受不明顯的特點，將圖像在空域分割為若干相對較小的塊，對感興趣區(qū)可采取一分為四的方法進一步減小塊的大小，然后對每個塊分別進行分形編碼，并重構.結果表明，在PSNR略有降低的情況下，編碼的匹配搜索時間大幅減少，同時重構圖像的主觀質量并沒有明顯降低.

圖像壓縮；分形；分塊；圖像編碼；迭代函數系統

0 引言

數字圖像數據量巨大，給存儲和傳輸帶來一定困難，需要對其進行壓縮處理［1］.分形編碼是利用圖像自相似性進行壓縮的一種方法，具有壓縮比高、編碼速度快等特點［2－3］.其主要思想是將圖像在空域劃分為若干個規(guī)則的矩形塊，分別稱為值域塊和定義域塊，通過它們之間的匹配產生迭代參數，進而達到圖像壓縮的目的.采用該方法生成的重構圖像，其質量對圖像劃分過分依賴，通常定義域塊劃分得越大，重構圖像的壓縮比也越高，同時圖像質量也隨之下降.此外，若對一幅N×N的灰度圖像編碼，值域塊和定義域塊的匹配搜索的算法復雜性為O（（N）3）～O（（N）4），即若要保證較高的重構圖像質量，需付出匹配搜索時間增加的代價.Bani－Eqbal B定義域塊匹配搜索，構建合適的定義域塊搜索樹結構，以避免全局匹配搜索［4］，使算法復雜性降低，但圖像重構質量也有所下降.Shen Furao等通過內積定義域塊和值域塊之間相似度，規(guī)定只有當相似度小于某一閾值時，才進行匹配運算，使匹配次數大為減少、算法復雜性有效降低［5］，但對相似度的定義缺乏理論依據，且算法難于實現最優(yōu)匹配.在該算法基礎上，Ongwattanakul S等根據概率統計分析，認為與值域塊形成最優(yōu)匹配的定義域塊以較大概率出現在某個固定位置，使匹配搜索算法的復雜性降為多項式級［6］，但重構圖像質量下降較大.人們從不同角度改進分形壓縮方法，但還不能從根本上解決值域塊和定義域塊匹配搜索開銷和重構圖像質量之間的矛盾，多數算法以犧牲重構圖像質量為代價，在一定程度上降低算法的復雜性［7－8］.基于人眼視覺在峰值信噪比（Peak Signal to Noise Ratio，簡稱PSNR）變化不大時，對圖像質量的主觀感受并不明顯這一思想［9－10］，筆者提出基于空域分割的分形圖像壓縮方法，在PSNR略有下降的情況下，較大幅度地降低匹配搜索時間，同時保持一定的主觀圖像質量.

1 Fisher分形編碼方法

分形理論研究表明，灰度圖像和迭代函數系統（Iterated Function System，簡稱IFS）之間存在一一對應關系，既對任意一幅灰度圖像，總存在一個IFS使其吸引子可以任意精度逼近之［11］.分形圖像壓縮的主要任務就是尋找該IFS的全部參數，并對這些參數進行適當編碼.分形圖像壓縮方法中比較經典的是Jac－quin提出的基于劃塊的分形圖像壓縮方法［12］.1994年，Fisher對這一方法進行改進，成為傳統分形編碼中的主流方法［13］，該方法的編解碼過程：

（2）搜索與其自相似的定義域塊Dj，并做縮小、旋轉和平移，且定義域塊尺寸2D×2D＞2R×2R，通過平均—抽樣操作Av，使定義域塊與值域塊具有相同尺寸，可表示為

搜索過程通過改變Π（K，L）和Lp（K，L），使dp達到最小，即利用式（2）并結合最小二乘法求得系數CK，L和hK，L.

（4）對每一個值域塊Ri，改變Π（K，L）和Lp（K，L），找到一個最優(yōu)匹配映射定義域塊Dj，使dp達到最小，記錄為CK，L，hK，L，Π（K，L），Lp（K，L），完成對值域塊Ri的編碼.

（5）對所有值域塊Ri，分別尋找其對應的定義域塊，使圖像A上的每一個值域塊Ri都用其定義域塊覆蓋，完成對整幅圖像的編碼.

解碼過程通過對式（1）的迭代實現，即

2 重構圖像質量影響因素

分形圖像壓縮解碼是利用分形參數不斷迭代的過程，因此重構圖像質量和迭代次數相關.采用C＋＋和Matlab混合編程，選用Cameraman圖像（尺寸為128×128）作為樣本，通過仿真實驗分析文中分形壓縮方法.當值域塊和定義域塊尺寸分別為4×4、8×8時，前6次迭代所對應的重構圖像及其PSNR值見圖1.由圖1可見，在主觀視覺上，重構圖像的質量隨著迭代次數的增加逐漸得到改善并趨于穩(wěn)定.當達到6次迭代后，PSNR值基本不再變化，說明已經收斂并逼近于原始圖像的吸引子.

圖1 Cameraman圖像逐次迭代的重構效果

對Cameraman圖像在值域塊大小不同的情況下分別進行仿真實驗，分形壓縮統計結果見表1，對應的重構圖像見圖2.由表1和圖2可以看出，分形圖像壓縮存在明顯的編解碼不平衡問題.對原始圖像進行劃塊時，如果值域塊劃分得較小，則重構圖像質量高，但匹配搜索開銷大；反之，如果值域塊較大，則重構圖像質量下降，但匹配搜索開銷減小.在分形圖像壓縮編碼中，重構圖像質量和匹配搜索時間是一對難以調和的矛盾，這也是分形圖像壓縮的最大缺陷.

表1 不同尺寸值域塊分形壓縮結果

圖2 不同尺寸值域塊分形壓縮后重構圖像

3 基于分塊的分形圖像編碼

基于仿真實驗分析，在分形圖像壓縮過程中，重構圖像質量主要取決于劃定的值域塊尺寸.如果對原始圖像事先進行分割處理，那么對每塊再進行分形劃塊時，其所包含的塊的數目和大小有所降低，這對提高分形編碼圖像質量和降低搜索時間有利.根據人眼的視覺特性，在PSNR變化不大的情況下，人眼很難感知圖像之間的細微差別［9－10］.因此，在PSNR有所犧牲情況下，以重構圖像質量輕微下降換取匹配搜索時間的大幅降低是可取的.根據文獻［3］，與任意給定的值域塊相匹配的定義域塊以較小的概率出現在距其較遠的區(qū)域.設待壓縮的原始圖像大小為2N×2N，首先將其分割為若干較小的塊，每塊尺寸為2M×2M（2≤M≤N－1）；然后對每部分按照分形編碼方法進行合理的值域塊和定義域塊劃分，并分別進行分形圖像編碼.對感興趣區(qū)域（Region of Interesting，簡稱ROI），根據感興趣程度采取一分為四的方法適當減小值域塊尺寸，以提高該區(qū)域的重構圖像質量.

采用C＋＋和Matlab混合編程，選取Cameraman圖像（尺寸為128×128）進行編碼壓縮.首先將原始圖像直接分割為4個64×64的相對較小的塊，再對每塊分別進行分形編碼.原始分形壓縮算法和基于分塊的壓縮算法重構圖像效果見圖3和圖4.由圖3和圖4可見，主觀視覺上文中壓縮算法和原始壓縮算法相比重構的圖像效果沒有明顯下降.文中基于分塊的分形壓縮算法和原始分形算法重構圖像的PSNR值對比見表2.由表2可見，在值域塊劃分相同情況下，基于分塊的分形壓縮算法的PSNR值有所下降，但下降幅度不大，而編碼效率有較大提高.

圖3 原始分形壓縮算法

圖4 基于分塊的分形壓縮算法

表2不同壓縮算法重構圖像結果

4 結束語

分形圖像編碼是利用圖像自相似性進行壓縮的一種方法，突破傳統圖像壓縮方法的局限，可以獲得較高的壓縮比.在對分形壓縮算法進行仿真實驗分析基礎上，提出基于圖像分塊的分形圖像壓縮方法.結果表明，在PSNR略有降低的情況下，匹配搜索復雜性明顯降低，編碼時間大為減少；同時重構圖像的主觀質量未受到明顯損害，在一定程度上解決分形圖像壓縮中的編解碼不平衡問題.

［1］ 唐國維，顧國昌.基于單窗口掃描的并行EBCOT編碼［J］.哈爾濱工業(yè)大學學報，2008，40（12）：2078－2081.

［2］ 王向陽，于雁春.基于改進K－均值聚類的快速分形圖像編碼算法［J］.計算機科學，2008，35（2）：219－222.

［3］ 楊紅穎，王向陽，于雁春.基于FCM聚類的快速分形圖像編碼算法［J］.小型微型計算機系統，2009，30（3）：493－497.

［4］ Bani－Eqbal B.Speeding up fractal image compression［C］.Proc SPIE：Still－Image Compression 2418，1995：67－74.

［5］ Shen Furao，Osamu Hasegawa.A fastno search fractal image coding method［C］.Signal Processing：Image Communication，2004，19（5）：393－404.

［6］ Ongwattanakul S，Xianwei Wu，Jackson D J.A new searchless fractal image encoding method for a realtime image compression device［C］.Proceedings of the 2004International Symposium on Circuits and System，2004，5（3）：23－26.

［7］ Tong C S，Pi M.Fastfractal image encoding based on adaptive search［J］.IEEE Trans Image Process，2001，10（9）：1269－1277.

［8］ Wang C C，Hsieh C H.An efficientfractal image－coding method using inter－block correlation search［J］.IEEE Trans Circuits，Syst，Video Technol，2001，11（2）：257－261.

［9］ 唐國維，王學春，齊峰.一種改進的基于人眼視覺特性的圖像編碼算法［J］.大慶石油學院學報，2006，30（6）：80－82.

［10］ 潘春華，朱同林，劉浩.圖像質量的HVS評價方法［J］.計算機工程與應用，2010，46（4）：146－151.

［11］ 曾文曲，文有為，孫煒.分形小波與圖像壓縮［M］.沈陽：東北大學出版社，2002.

［12］ 張旭東，盧國棟，馮健.圖像編碼基礎和小波壓縮技術：原理、算法和標準［M］.北京：清華大學出版社，2004.

［13］ 王苫社.基于小波及分形的嵌入式圖像編碼算法研究［D］.大慶：東北石油大學，2010.

A fractal image compression method based on block－dividing／2012，36（3）：100－103

TANG Guo－wei1，HAN Peng－yu2，WANG Ai1，WANG Shan－she3，SHI Guo－jun4
（1.School of Computer and Information Technology，NortheastPetroleum University，Daqing，Heilongjiang163318，China；2.School of Petroleum Engineering，NortheastPetroleum University，Daqing，Heilongjiang163318，China；3.School of Computer Science and Technology，Harbin Institute of Technology，Harbin，Heilongjiang150001，China；4.Oil Recovery PlantNo.8，Daqing Oilfield Corp.Ltd.，Daqing，Heilongjiang163514，China）

For the convenience of store and transmission，itis necessary to conductcompression encoding for digital image.Fractal image coding has the characteristics of high compression，butthe match searching time in the process of encoding is huge.In this paper a fractal image coding method based on block－dividing is proposed.The human vision system is notsensitive to the subjective quality of the reconstructed image in case of a small PSNR change.The original image is divided into small blocks in space domain directly，and to the interesting parts the blocks can be divided further by one－to－four.Then the fractal image coding to each blocks is carried out，and the reconstruction is also conducted ateach block respectively.The experimental results demonstrate thatthe match searching time can be reduced substantially and the subjectimage quality remain unchanged basically，meanwhile the PSNR being decreased slightly.

image segmentation；fractal；block－dividing；image coding；iterated function system

book=3,ebook=84

TP391.41

A

1000－1891（2012）03－0100－04

2012－02－21；編輯：張兆虹

黑龍江省教育廳科學技術研究項目（12521050）

唐國維（1966－），男，博士，教授，主要從事圖像處理與模式識別方面的研究.