基于不規(guī)則區(qū)域分割及灰度排序分類(lèi)的分形壓縮算法

鄭秋梅，趙 敏，王風(fēng)華，趙景智

(中國(guó)石油大學(xué)計(jì)算機(jī)與通信工程學(xué)院，山東青島 266580)

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

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

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

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

具體編碼算法流程如下。

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

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

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

a)對(duì)每個(gè)Sub_Domain經(jīng)過(guò)8個(gè)等距變換擴(kuò)大為8個(gè)新的子塊;

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

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

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

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

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

由分形塊編碼過(guò)程可見(jiàn)，其耗時(shí)多主要是因?yàn)樗阉髌ヅ涞姆秶^(guò)大。要減少匹配搜索時(shí)間，就要縮小搜索匹配范圍。常用的分類(lèi)法多以圖像的單一特征作為分類(lèi)依據(jù)，但由于Domain塊數(shù)量巨大，在相應(yīng)類(lèi)中搜索最佳匹配塊所需的時(shí)間仍然很長(zhǎng)，為解決這一問(wèn)題，結(jié)合不規(guī)則區(qū)域分割編碼思想對(duì)分形壓縮算法進(jìn)行了改進(jìn)。

2 算法改進(jìn)

2.1 算法描述

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

2.1.1 基于不規(guī)則區(qū)域分割編碼

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

由于PCNN分割模型對(duì)圖像分割完全依賴(lài)于圖像的自然屬性，且各個(gè)分割區(qū)域的像素不僅具有相似的灰度值，在空間上也具有一定的相似性，同時(shí)原圖像經(jīng)過(guò)PCNN分割后得到的二值圖像中，各個(gè)不規(guī)則分割區(qū)域的像素具有灰度值相似的特征，可作為分形壓縮算法中搜索匹配的分類(lèi)依據(jù)。

2.1.2 PCNN分割模型

PCNN模型是一種基于神經(jīng)生理學(xué)的模型，它由基本神經(jīng)元組成，其結(jié)構(gòu)如圖2所示。

圖2 PCNN神經(jīng)元結(jié)構(gòu)圖Fig.2 Structure of PCNN neuron

每個(gè)神經(jīng)元的具體運(yùn)算如下:

式中，S表示輸入激勵(lì)，一般為像素點(diǎn)(i，j)的灰度值，每個(gè)像素點(diǎn)對(duì)應(yīng)一個(gè)神經(jīng)元;F對(duì)應(yīng)神經(jīng)元的輸入部分，L是連接輸入，U對(duì)應(yīng)神經(jīng)元內(nèi)部活動(dòng)項(xiàng)，Y和θ分別為神經(jīng)元的輸出和動(dòng)態(tài)閾值，M、W對(duì)應(yīng)神經(jīng)元的內(nèi)部連接矩陣;V為反饋放大系數(shù);α為衰減時(shí)間系數(shù);β為連接系數(shù)。當(dāng)利用PCNN進(jìn)行圖像分割時(shí)，灰度值大的像素點(diǎn)所對(duì)應(yīng)的神經(jīng)元先點(diǎn)火，輸出脈沖1，該像素點(diǎn)周?chē)哂薪苹叶戎档钠渌袼攸c(diǎn)所對(duì)應(yīng)的神經(jīng)元在下次迭代時(shí)受連接輸入影響也被激活輸出脈沖1，則具有相似灰度值的區(qū)域因受連接域的影響而同步激活，從而實(shí)現(xiàn)分割［7-9］。

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

2.1.3 灰度排序分類(lèi)

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

主類(lèi) 1:μ1≥μ2≥μ3≥μ4;

主類(lèi) 2:μ1≥μ2≥μ4≥μ3;

主類(lèi) 3:μ1≥μ4≥μ2≥μ3。

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

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

2.2 算法流程

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

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

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

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

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

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

(7)對(duì)每個(gè)Rang塊，根據(jù)分類(lèi)結(jié)果在相同類(lèi)別的Domain塊及其8種等距變換的子塊中進(jìn)行匹配計(jì)算;

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

結(jié)合傳統(tǒng)的基于分類(lèi)的分形壓縮和不規(guī)則區(qū)域分割壓縮算法的優(yōu)勢(shì)，首次將PCNN分割算法引入分形壓縮，提出一種PCNN-GRAY算法，在盡量保證解碼圖像質(zhì)量的前提下，大幅度縮小了搜索匹配范圍，減少了編碼時(shí)間。該算法可在圖像壓縮方面應(yīng)用推廣，但解碼圖像的質(zhì)量仍不盡人意，需進(jìn)一步改進(jìn)。

［1］ 孟憲偉，晏磊.圖像壓縮編碼方法綜述［J］.影像技術(shù)，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，F(xiàn)ISHER Y，BOSS Y D.Image compression:a study of the iterated transform method［J］.Signal Processing，1992，29(3):251-263.

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

［4］ 鄭秋梅，呂興會(huì)，時(shí)公喜.基于多特征集成分類(lèi)器的人臉表情識(shí)別［J］.中國(guó)石油大學(xué)學(xué)報(bào):自然科學(xué)版，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ìn)展［J］.工程圖學(xué)學(xué)報(bào)，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］ 馬義德，齊春亮，錢(qián)志柏，等.基于脈沖耦合神經(jīng)網(wǎng)絡(luò)和施密特正交基的一種新型圖像壓縮編碼算法［J］.電子學(xué)報(bào)，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的原理及其應(yīng)用［J］.電路與系統(tǒng)學(xué)報(bào)，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］ 馬義德，齊春亮，錢(qián)志柏，等.基于PCNN的不規(guī)則分割區(qū)域壓縮編碼［C］.第十二屆全國(guó)圖象圖形學(xué)術(shù)會(huì)議論文集，c2005.

［9］ 黃曉莉，曾黃麟，王秀碧，等.基于脈沖耦合神經(jīng)網(wǎng)絡(luò)的圖像分割［J］.信息技術(shù)，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］ 郭京蕾，吳勇.基于分類(lèi)方法的分形圖像壓縮［J］.計(jì)算機(jī)工程與設(shè)計(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.