基于不規則區域分割及灰度排序分類的分形壓縮算法

鄭秋梅，趙 敏，王風華，趙景智

(中國石油大學計算機與通信工程學院，山東青島 266580)

高壓縮比和高保真性一直是圖像壓縮追求的目標。從20世紀五六十年代的預測編碼、哈夫曼編碼到七八十年代的變換編碼和矢量量化編碼，再到八十年代末的小波變換理論、分形理論［1］等都在追求這一目標。分形壓縮算法以其高壓縮比、任意尺度下的重構和快速解碼等優越性成為當前研究熱點;但基本分形算法需要龐大的匹配搜索運算，導致編碼時間過長。目前主要通過縮小搜索匹配范圍來提高編碼速度，其中主要方法是對定義域塊和值域塊進行分類［2-3］，把全局匹配搜索改為類內搜索匹配(分類搜索)。當前的分類搜索多以圖像灰度值、紋理等單一特征作為分類依據［4］，這樣雖能在一定程度上縮小搜索范圍，但編碼時間仍不理想。筆者結合不規則區域分割壓縮算法的思想，首次將脈沖耦合神經網絡(pulse coupled neural network，PCNN)分割算法引入分形壓縮，并且在分形壓縮過程中，根據PCNN分割后所得二值圖像的灰度值和原圖像的灰度值兩個特征聯合分類，從而進一步縮小搜索匹配范圍。

1 分形圖像壓縮的編碼算法

20世紀80年代末，Barnsley［5］提出了基于迭代函數系統(iterated function system，IFS)的分形圖像壓縮理論。其基本思想是利用數據的自相似或自仿射特征，構造相應的IFS，然后記錄其中相關參數，并最終用這些參數作為圖像的編碼進行存儲和傳輸，從而只需少量數據就可恢復與原圖像相近的圖像，達到壓縮圖像數據的目的。其原理如圖1所示。

圖1 分形編碼原理圖Fig.1 Fractal coding schematic

具體編碼算法流程如下。

(1)將原圖像分割成若干互不重疊的大小為B×B的Rang塊(記作Ri)和若干可重疊的大小為2B×2B的Domain塊。

(2)對2B×2B的Domain塊進行收縮變換。即對每個Domain塊中相鄰的4個像素進行求和并取平均值，得到大小為B×B的Sub_Domain塊，這種Sub_Domain的全體構成碼本。

(3)獲取分形碼。對每個Rang塊Ri都按以下三步在碼本中尋找其最佳匹配Dm(i):

a)對每個Sub_Domain經過8個等距變換擴大為8個新的子塊;

b)對每個Sub_Domain塊及其8種等距變換得到的子塊，與Rang塊進行匹配，計算其MSE(Mean Square Error)，計算公式為

式中，Ri，j為 Rang 的像素值;Di，j為 Domain 塊的像素值;S為比例因子;O為偏移量。若計算出的MSE小于給定的誤差，則匹配成功，否則繼續匹配，直到找出誤差最小的匹配為止;

c)輸出當前Rang塊Ri的分形碼，即參數Si、Oi、最匹配碼字的下標m(i)以及等距變換序號。

(4)編碼每個Rang塊。對于每個Rang塊Ri，重復步驟(3)直至所有Rang塊完成編碼為止。

(5)保存分形碼，即得到分形編碼文件。

由分形塊編碼過程可見，其耗時多主要是因為搜索匹配的范圍過大。要減少匹配搜索時間，就要縮小搜索匹配范圍。常用的分類法多以圖像的單一特征作為分類依據，但由于Domain塊數量巨大，在相應類中搜索最佳匹配塊所需的時間仍然很長，為解決這一問題，結合不規則區域分割編碼思想對分形壓縮算法進行了改進。

2 算法改進

2.1 算法描述

基于不規則區域分割及灰度排序分類的分形壓縮算法((PCNN-GRAY)):先對原圖像進行不規則區域分割;然后對這些區域進行分形壓縮編碼，將分形壓縮中的全局搜索匹配改為在具有較高相似性不規則區域內的搜索匹配，以達到縮小搜索匹配范圍的目的;最后在分形壓縮過程中加入基于圖像灰度值排序分類的方法，進一步縮小搜索匹配范圍。

2.1.1 基于不規則區域分割編碼

基于不規則區域分割編碼技術的思想是先讓分割區域(或紋理)與原始圖像對應部分在視覺意義上最大程度地接近，再對這些區域(紋理)進行編碼［6］。然而，與傳統規則的分塊相比，不規則區域分割在編碼時需要增加邊緣的位置信息，這樣不僅增加了額外的編碼數據量及編碼時間，且這些邊緣信息不能大幅度壓縮。本文中利用不規則區域分割編碼的思想，首先對原圖像進行不規則區域分割，然后在分割區域中采用分形壓縮算法，從而將分形壓縮中的全局搜索匹配改為區域搜索匹配，達到縮小搜索匹配范圍的目的。

由于PCNN分割模型對圖像分割完全依賴于圖像的自然屬性，且各個分割區域的像素不僅具有相似的灰度值，在空間上也具有一定的相似性，同時原圖像經過PCNN分割后得到的二值圖像中，各個不規則分割區域的像素具有灰度值相似的特征，可作為分形壓縮算法中搜索匹配的分類依據。

2.1.2 PCNN分割模型

PCNN模型是一種基于神經生理學的模型，它由基本神經元組成，其結構如圖2所示。

圖2 PCNN神經元結構圖Fig.2 Structure of PCNN neuron

每個神經元的具體運算如下:

式中，S表示輸入激勵，一般為像素點(i，j)的灰度值，每個像素點對應一個神經元;F對應神經元的輸入部分，L是連接輸入，U對應神經元內部活動項，Y和θ分別為神經元的輸出和動態閾值，M、W對應神經元的內部連接矩陣;V為反饋放大系數;α為衰減時間系數;β為連接系數。當利用PCNN進行圖像分割時，灰度值大的像素點所對應的神經元先點火，輸出脈沖1，該像素點周圍具有近似灰度值的其他像素點所對應的神經元在下次迭代時受連接輸入影響也被激活輸出脈沖1，則具有相似灰度值的區域因受連接域的影響而同步激活，從而實現分割［7-9］。

本文依據PCNN分割后得到的二值圖像中各個分割區域的像素具有相似灰度值這一特征對原圖像塊進行分類，從而避免了對邊緣信息進行編碼。由于二值圖像灰度值只有0、1兩種情形，所以劃分后二值圖像塊R的灰度均值有3類:均值HR=0;均值HR=1;均值0＜HR＜1。在分形壓縮時，原始圖像塊根據對應的二值圖像塊灰度均值分類結果被分成3類，搜索范圍也由全局搜索改為分割區域搜索，最終達到減少算法編碼時間的目的。該方案雖縮小了分形壓縮算法的搜索匹配范圍，但因為分類特征單一，編碼時間仍不理想，所以本文又在PCNN分類基礎上引入了基于圖像灰度值排序分類。

2.1.3 灰度排序分類

圖像灰度值排序分類是將圖像Rang塊和Domain塊分割為上左、上右、下左、下右4個部分(圖3)，并依次記為 A1、A2、A3、A4，計算每個 Ai塊的灰度均值μi。則對任意Rang塊和Domain塊都可通過“反射-旋轉”變換，使μi值排列屬于以下3種情況之一，從而將Rang塊和Domain塊分成3大主類［10］。

主類 1:μ1≥μ2≥μ3≥μ4;

主類 2:μ1≥μ2≥μ4≥μ3;

主類 3:μ1≥μ4≥μ2≥μ3。

在本文算法中，對PCNN分割區域分類處理后的圖像塊再進行灰度排序分類，每一類又被分成3類，則Rang塊和Domain塊圖像塊被分成9類，在匹配時每個Rang塊只需在相同類別的Domain塊中尋找相似匹配塊，進一步縮小了搜索范圍。同時，為了排除對解碼圖像質量造成的影響，改進算法在依據二值圖像塊的灰度均值對原始圖像塊進行分類時，增加灰度均值分類的重疊，以提高圖像的解碼質量。多次實驗表明，二值圖像灰度均值分類取為HR≤0.4;HR≥0.6;0.1≤HR≤0.9時實驗結果最佳。

圖3 按塊的灰度均值分類情況Fig.3 Classification by average of gray value

2.2 算法流程

(1)對原圖像I進行PCNN分割，輸出二值圖像I';

(2)分別將I'和I分割成若干互不重疊大小4×4的BWRang塊和Rang塊(其中BWRang為二值圖像值域塊，Rang為原圖像值域塊);

(3)分別將I'和I分割成若干可重疊、大小為8×8的BWDomain塊和Domain塊(其中BWDomain為二值圖像定義域塊，為Domain原圖像定義域塊);

(4)對于8×8的Domain塊進行收縮變換。即對每個Domain塊中相鄰的4個像素灰度值進行求和并取平均值，得到大小為4×4的Sub_Domain塊;

(5)根據每個BWRang塊的像素值和BWDomain塊的像素值分別將Rang塊和Domain塊分成3類:均值HR≥0.6稱為1值塊類;均值HR≤0.4稱為0值塊類;均值HR在0.9≥8≥0.1稱為中值塊;

(6)將第(5)步中得到的每類按灰度排序分類法再分成3大類，則每個Rang塊和Domain塊被分成了9類;

(7)對每個Rang塊，根據分類結果在相同類別的Domain塊及其8種等距變換的子塊中進行匹配計算;

(8)保存匹配成功時的變換編號、比例因子、偏移量及Domain塊位置。

3 實驗結果分析

實驗采用256×256×8的LENA和Pepper圖像，將原圖像分割成互不重疊的4×4塊，用Matlab7.0編程。將本文中提出的PCNN-GRAY算法與分形塊壓縮算法、灰度排序分類算法進行了對比實驗(為對比說明，本文中也實現了僅基于PCNN分割的分類算法)。實驗結果如表1所示。

表1 不同算法的峰值信噪比rPSN及耗時Table 1 rPSNand time-consuming of different algorithms

由表1可以看出，同分形塊算法和灰度排序分類算法相比，PCNN-GRAY算法中的rPSN雖有一定下降，但編碼時間大幅減少。但圖4(d)中有較明顯的方塊效應，為了消除方塊效應，先對圖像進行均值濾波處理，可是進行濾波處理后，圖像會變得模糊，所以將原圖像和濾波后的圖像灰度值進行相加求平均，如圖5所示。處理后的圖像方塊效應明顯降低，而且優化過程不影響其編碼過程的耗時，對解碼時間的影響也不明顯。

圖4 不同算法解碼圖像效果Fig.4 Decoded image of different algorithms

圖5 平滑處理后的圖像效果Fig.5 Decoded image of algorithms after smoothing

4 結束語

結合傳統的基于分類的分形壓縮和不規則區域分割壓縮算法的優勢，首次將PCNN分割算法引入分形壓縮，提出一種PCNN-GRAY算法，在盡量保證解碼圖像質量的前提下，大幅度縮小了搜索匹配范圍，減少了編碼時間。該算法可在圖像壓縮方面應用推廣，但解碼圖像的質量仍不盡人意，需進一步改進。

［1］ 孟憲偉，晏磊.圖像壓縮編碼方法綜述［J］.影像技術，2007(1):6-8.MENG Xian-wei，YAN Lei.Image compression coding method review ［J］.Imaging Technology，2007(1):6-8.

［2］ JACOBS E W，FISHER Y，BOSS Y D.Image compression:a study of the iterated transform method［J］.Signal Processing，1992，29(3):251-263.

［3］ 秦峰，吳征.分區IFS圖像壓縮編碼［J］.通訊學報，1997，18(5):1-7.QIN Feng，WU Zheng.Area-based IFS image coding［J］.Communications，1997，18(5):1-7.

［4］ 鄭秋梅，呂興會，時公喜.基于多特征集成分類器的人臉表情識別［J］.中國石油大學學報:自然科學版，2011，35(1):174-178.ZHENG Qiu-mei，Lü Xing-hui，SHI Gong-xi.Facial expression recognition based on multi-feature and combining multiple classifiers［J］.Journal of China University of Petroleom(Edition of Natural Science)，2011，35(1):174-1178.

［5］ 李明水，歐珊瑚，張珩.分形圖像壓縮方法研究的新進展［J］.工程圖學學報，2004(2):143-152.LI Ming-shui，OU Shan-hu，ZHANG Heng.The progressof fractal image compression method research［J］.Journal of Engineering Graphics，2004(2):143-152.

［6］ 馬義德，齊春亮，錢志柏，等.基于脈沖耦合神經網絡和施密特正交基的一種新型圖像壓縮編碼算法［J］.電子學報，2006，34(7):1255-1259.MA Yi-de，QI Chun-liang，QIAN Zhi-bo，et al.A novel image compression coding algorithm based on pulse-coupled neural network and Gram-Schmidt orthogonal base［J］.Acta Electronica Sinica，2006，34(7):1255-1259.

［7］ 顧曉東，余道衡.PCNN的原理及其應用［J］.電路與系統學報，2000，6(3):45-49.GU Xiao-dong，YU Dao-heng.PCNN1s principles and applications［J］.Journal of Circuits and Systems，2000，6(3):45-49.

［8］ 馬義德，齊春亮，錢志柏，等.基于PCNN的不規則分割區域壓縮編碼［C］.第十二屆全國圖象圖形學術會議論文集，c2005.

［9］ 黃曉莉，曾黃麟，王秀碧，等.基于脈沖耦合神經網絡的圖像分割［J］.信息技術，2008，32(9):90-91.HUANG Xiao-li，ZENG Huang-lin，WANG Xiu-bi，et al.Image segmentation based on pulse-coupled neural network［J］.Information Technology，2008，32(9):90-91.

［10］ 郭京蕾，吳勇.基于分類方法的分形圖像壓縮［J］.計算機工程與設計，2007，28(4):890-892.GUO Jing-lei，WU Yong.Fractal image compression based on classification method［J］.Computer Engineering and Design，2007，28(4):890-892.