唐國(guó)維，韓鵬宇，王 艾，王苫社，施國(guó)俊

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

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

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

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

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

圖像壓縮；分形；分塊；圖像編碼；迭代函數(shù)系統(tǒng)

0 引言

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

1 Fisher分形編碼方法

分形理論研究表明，灰度圖像和迭代函數(shù)系統(tǒng)（Iterated Function System，簡(jiǎn)稱(chēng)IFS）之間存在一一對(duì)應(yīng)關(guān)系，既對(duì)任意一幅灰度圖像，總存在一個(gè)IFS使其吸引子可以任意精度逼近之［11］.分形圖像壓縮的主要任務(wù)就是尋找該IFS的全部參數(shù)，并對(duì)這些參數(shù)進(jìn)行適當(dāng)編碼.分形圖像壓縮方法中比較經(jīng)典的是Jac－quin提出的基于劃塊的分形圖像壓縮方法［12］.1994年，F(xiàn)isher對(duì)這一方法進(jìn)行改進(jìn)，成為傳統(tǒng)分形編碼中的主流方法［13］，該方法的編解碼過(guò)程：

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

搜索過(guò)程通過(guò)改變?chǔ)埃↘，L）和Lp（K，L），使dp達(dá)到最小，即利用式（2）并結(jié)合最小二乘法求得系數(shù)CK，L和hK，L.

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

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

解碼過(guò)程通過(guò)對(duì)式（1）的迭代實(shí)現(xiàn)，即

2 重構(gòu)圖像質(zhì)量影響因素

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

圖1 Cameraman圖像逐次迭代的重構(gòu)效果

對(duì)Cameraman圖像在值域塊大小不同的情況下分別進(jìn)行仿真實(shí)驗(yàn)，分形壓縮統(tǒng)計(jì)結(jié)果見(jiàn)表1，對(duì)應(yīng)的重構(gòu)圖像見(jiàn)圖2.由表1和圖2可以看出，分形圖像壓縮存在明顯的編解碼不平衡問(wèn)題.對(duì)原始圖像進(jìn)行劃塊時(shí)，如果值域塊劃分得較小，則重構(gòu)圖像質(zhì)量高，但匹配搜索開(kāi)銷(xiāo)大；反之，如果值域塊較大，則重構(gòu)圖像質(zhì)量下降，但匹配搜索開(kāi)銷(xiāo)減小.在分形圖像壓縮編碼中，重構(gòu)圖像質(zhì)量和匹配搜索時(shí)間是一對(duì)難以調(diào)和的矛盾，這也是分形圖像壓縮的最大缺陷.

表1 不同尺寸值域塊分形壓縮結(jié)果

圖2 不同尺寸值域塊分形壓縮后重構(gòu)圖像

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

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

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

圖3 原始分形壓縮算法

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

表2不同壓縮算法重構(gòu)圖像結(jié)果

4 結(jié)束語(yǔ)

分形圖像編碼是利用圖像自相似性進(jìn)行壓縮的一種方法，突破傳統(tǒng)圖像壓縮方法的局限，可以獲得較高的壓縮比.在對(duì)分形壓縮算法進(jìn)行仿真實(shí)驗(yàn)分析基礎(chǔ)上，提出基于圖像分塊的分形圖像壓縮方法.結(jié)果表明，在PSNR略有降低的情況下，匹配搜索復(fù)雜性明顯降低，編碼時(shí)間大為減少；同時(shí)重構(gòu)圖像的主觀(guān)質(zhì)量未受到明顯損害，在一定程度上解決分形圖像壓縮中的編解碼不平衡問(wèn)題.

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

［2］ 王向陽(yáng)，于雁春.基于改進(jìn)K－均值聚類(lèi)的快速分形圖像編碼算法［J］.計(jì)算機(jī)科學(xué)，2008，35（2）：219－222.

［3］ 楊紅穎，王向陽(yáng)，于雁春.基于FCM聚類(lèi)的快速分形圖像編碼算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，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］ 唐國(guó)維，王學(xué)春，齊峰.一種改進(jìn)的基于人眼視覺(jué)特性的圖像編碼算法［J］.大慶石油學(xué)院學(xué)報(bào)，2006，30（6）：80－82.

［10］ 潘春華，朱同林，劉浩.圖像質(zhì)量的HVS評(píng)價(jià)方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（4）：146－151.

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

［12］ 張旭東，盧國(guó)棟，馮健.圖像編碼基礎(chǔ)和小波壓縮技術(shù)：原理、算法和標(biāo)準(zhǔn)［M］.北京：清華大學(xué)出版社，2004.

［13］ 王苫社.基于小波及分形的嵌入式圖像編碼算法研究［D］.大慶：東北石油大學(xué)，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；編輯：張兆虹

黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目（12521050）

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