基于質(zhì)心特征和重要敏感區(qū)域分類的分形圖像壓縮算法*

王 麗，劉增力

(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明 650000)

1 引言

隨著數(shù)字技術(shù)的發(fā)展，越來越多的信息通過圖像形式傳遞，對大量圖像數(shù)據(jù)信息進(jìn)行高效的存儲和傳輸是當(dāng)今信息時(shí)代所面臨的重要問題，除硬件本身需要改善外，高性能的圖像壓縮技術(shù)變得越來越重要。以分形為研究對象的分形幾何是現(xiàn)代數(shù)學(xué)的一個(gè)新分支，其本質(zhì)是一種新的世界觀和方法論。

常用的圖像壓縮技術(shù)可以分為有損壓縮和無損壓縮2類，無損壓縮包括Huffman編碼、行程編碼、LZW編碼和算數(shù)編碼等，有損編碼包括預(yù)測編碼、JPEG編碼、變換編碼和矢量編碼等。2種類型的編碼滿足不同需求，無損壓縮完全保留圖像質(zhì)量，而有損壓縮以犧牲一定的圖像質(zhì)量，在確保恢復(fù)效果的前提下，大幅度提高了圖像傳輸速度和存儲量，面對大量的數(shù)據(jù)交互，具有廣闊的應(yīng)用前景。分形編碼是一種有損圖像壓縮技術(shù)，它是圖像壓縮的一個(gè)重要工具。分形圖像壓縮利用了自然景物的自相似性來進(jìn)行數(shù)據(jù)壓縮，以迭代函數(shù)系統(tǒng)為理論基礎(chǔ)。Barnsley等[1]最早給出了分形編碼的大致過程，即利用提取的分形子圖，尋找整體與局部之間存在的某種自放射特征。在實(shí)用化研究中，Jacquin[2]提出了分形塊編碼,通過對圖像的分割分別獲得互不重疊的小方塊和重疊的大方塊，然后對每個(gè)小方塊搜索與之最仿射相似的大方塊。Jacquin型編碼把分形編碼從“專家算法”變成“大眾算法”，分形編碼才真正被運(yùn)用到眾多領(lǐng)域中。

2 相關(guān)研究

近年來，國內(nèi)外涌現(xiàn)出越來越多基于Jacquin型編碼的分形圖像編碼技術(shù)。研究者主要從圖像分割方式、結(jié)合變換域、碼本縮減、匹配方式和解碼方式等方向展開研究，研究的目的都是減少分形編碼時(shí)間過長對編碼效率帶來的影響，以及確保重構(gòu)圖像質(zhì)量。基于變換域的分形圖像編碼方法在分形編碼之前對圖像進(jìn)行處理，對處理后的圖像采用分形編碼，文獻(xiàn)[3 - 5]提出的分形與小波變換結(jié)合的混合編碼方法、謝敏等[6]提出的分形與DCT結(jié)合的混合編碼方法，都取得了良好的圖像恢復(fù)效果。Gupta等[7]提出的空域和頻域結(jié)合的方法，將塊分類轉(zhuǎn)換為空域分類，簡化了分類方式。結(jié)合其它編碼方式的混合分形編碼方法也被研究者嘗試，其中王春梅等[8]將算數(shù)編碼結(jié)合分形編碼的方法很大程度上提高了編碼效率。朱志良等[9]提出的基于像素的三角分割方式，可以對圖像不同紋理分布采取不同大小的塊分割，有效保留了圖像的重要信息?；诖a本縮減的分形編碼方法有很多，其中李高平等[10]提出的方差剔除條件的快速分形圖像編碼方法、何傳江等[11]提出的基于平均偏差排序的快速分形圖像編碼方法、Roy等[12]提出的基于縮放參數(shù)上限的方法，將原始碼本中不符合條件的碼本剔除，減少了匹配次數(shù)，編碼時(shí)間大大縮短。Ismail等[13]提出的結(jié)合布谷鳥搜索優(yōu)化算法的分形編碼算法，改變以往傳統(tǒng)歐氏距離搜索方式，取得了不錯(cuò)的效果。孔玲君等[14]根據(jù)人眼對圖像的視覺選擇特點(diǎn)，提出了感興趣區(qū)域壓縮方式，使得人眼對恢復(fù)圖像視覺效果增強(qiáng)，也間接地縮減了碼本。為了達(dá)到縮短編碼時(shí)間的目的，最直接的方式就是以圖像恢復(fù)質(zhì)量換取編碼時(shí)間。相比直接剔除碼本，塊分類是一種折衷的方法，如汪瑋瑋等[15]提出的分類父塊方法、何傳江等[16,17]提出的叉跡特征分類方式以及張璟等[18]提出的雙交叉和特征分類方法，都實(shí)現(xiàn)了塊分類過程，達(dá)到了縮減編碼時(shí)間的目的。

本文提出一種基于質(zhì)心特征和重要敏感區(qū)域劃分的分類算法，質(zhì)心被廣泛應(yīng)用于目標(biāo)跟蹤和目標(biāo)識別中，可以作為特征使用，本文將質(zhì)心應(yīng)用到灰度塊圖像匹配中，提取子塊不同的質(zhì)心坐標(biāo)，達(dá)到分類塊的目的。同時(shí)，考慮人眼對圖像的整體輪廓和部分細(xì)節(jié)較為敏感，以及對重要區(qū)域選擇關(guān)注的特點(diǎn)，對人眼視覺專注部分著重處理，增加圖像恢復(fù)好感度。

3 本文算法

3.1 基本算法

在基本分形編碼算法中，原始圖像首先被分割成互不重疊且大小為n×n的Range塊(簡稱R塊)和允許重疊且大小為2n×2n的Domain塊(簡稱D塊)。然后，將每個(gè)D塊通過4-鄰域像素平均算子壓縮為n×n的子塊，與R塊大小匹配，而所有壓縮后的D塊經(jīng)過8種等距變換后就構(gòu)成碼本Ω。

在編碼階段，對每一個(gè)R塊，按照全搜索方式在碼本Ω中尋找其最佳匹配D塊和自仿射變換ω，使得ω(D)與R的均方誤差均達(dá)到最小。為了尋找R塊的最佳匹配塊，需要求解下述極小化問題[19]：

‖R-(s·Dm+o·I)‖=

(1)

其中，m表示R塊的最佳匹配塊序號,s表示對比度收縮因子，o表示亮度偏移，I∈Rn×n是所有元素均為1的常值塊。

直接求解式(1)十分困難，耗時(shí)很長，為了降低復(fù)雜度，先忽略內(nèi)層約束|s|<1，將極小化問題(1)轉(zhuǎn)化為下述問題求解：

(2)

問題解為：

(3)

(4)

3.2 質(zhì)心特征

分形編碼的絕大多數(shù)時(shí)間都是花費(fèi)在R塊與碼本中D塊進(jìn)行全局搜索匹配的過程中，特征算法的目的就是避開全局搜索，將搜索過程轉(zhuǎn)換成為局部搜索，每次搜索限定在一定特征下的有限區(qū)域內(nèi)。

質(zhì)心在幾何圖形中可以表示質(zhì)量中心，即重心，對于規(guī)則的均勻物體，質(zhì)心在其幾何中心，圖像同樣存在質(zhì)心。下面證明在分形圖像壓縮編碼中，利用質(zhì)心特征進(jìn)行分類的可行性。假設(shè)子塊G，G(i,j)表示G中(i,j)處的值，其質(zhì)心定義如下：

(5)

定義1子塊G=(G(i,j))∈Rn×n的歸一化定義為:

(6)

取歸一化后的值為特征值，定義子塊x和y方向的質(zhì)心特征如下所示：

(7)

定理1對于R塊和D塊，設(shè)R，D∈Rn×n(n為偶自然數(shù))，則有如式(8)所示的關(guān)于R塊和D塊匹配誤差的不等式成立：

(8)

其中，C′trx(R),C′try(R),C′trx(D),C′try(D)分別是定義的新質(zhì)心特征。

證明過程見附錄。

3.3 質(zhì)心特征選取

用一個(gè)子塊的質(zhì)心特征代表整幅圖像過于寬泛，因此本文采用求取R塊的多個(gè)質(zhì)心的方法，聯(lián)合進(jìn)行特征劃分。假設(shè)圖像塊X=(xi,j)∈Rn×n,n=8，如圖1a所示，將圖像塊X分為如圖1b所示的4個(gè)部分,Xk∈Rm×m,k=1,…,4，m=4，對每一個(gè)Xk求質(zhì)心。大量的實(shí)驗(yàn)表明，圖像質(zhì)心分布于4個(gè)可能的位置，如圖1c中a、b、c、d所示。對于圖像塊X而言，質(zhì)心的分布情況有44=256種。為了減少質(zhì)心分類數(shù)，本文采用如圖1d所示的處在對角線位置的2個(gè)部分的質(zhì)心作為分類標(biāo)準(zhǔn)，將質(zhì)心分布情況減少到42=16種，從實(shí)驗(yàn)中發(fā)現(xiàn)，圖像塊質(zhì)心的分布具有相似性，往往分類不會達(dá)到16種。

Figure 1 Centroid position圖1 質(zhì)心位置

4 重要敏感區(qū)域劃分

4.1 敏感區(qū)域劃分

在分形圖像壓縮中，需要對圖像進(jìn)行分割處理，與整幅圖像相比，子塊的結(jié)構(gòu)比較單一，且往往在很多結(jié)構(gòu)上具有相似性。通常根據(jù)R塊的結(jié)構(gòu)分布可以將R塊劃分為不同的歸屬類，其中一個(gè)評判標(biāo)準(zhǔn)是方差。對于子塊而言，方差小表示該子塊像素值變化波動(dòng)趨于平緩，即結(jié)構(gòu)平滑；方差大表示該子塊像素值變化相對很大，即屬于紋理或邊緣等細(xì)節(jié)區(qū)域。

研究表明，人眼視覺系統(tǒng)對邊緣比對平滑區(qū)域更敏感，也就是說，人眼的注意力會更集中在提供信息的區(qū)域，對于圖像的邊緣、紋理、平滑區(qū)域，人眼敏感程度逐漸遞減。為此，根據(jù)人眼對圖像區(qū)域的敏感程度，將圖像劃分為敏感區(qū)域和非敏感區(qū)域。R塊在碼本中的最佳匹配塊一定與該塊最接近，包括灰度級的接近和灰度變化的接近，非敏感區(qū)域采用均值替代參數(shù)的方式，以此來縮短編碼時(shí)間。假設(shè)R塊的非敏感區(qū)域劃分閾值τ是固定的，R塊劃分方法如下所示：

σ<τ

(9)

其中,σ為R塊方差，若滿足式(9)即可認(rèn)為R滿足非敏感區(qū)域條件，便用均值取代搜索匹配參數(shù)，否則認(rèn)為R塊為敏感區(qū)域。

4.2 重要區(qū)域

人眼視覺能感覺到的重要區(qū)域一般為圖像的中心1/4部分，因此對這部分著重處理會增加人眼對圖像的好感度。這部分圖像往往會被第一眼看到，基于此，本文將原始圖像分為2部分，分別為中心1/4面積部分的重要區(qū)域和其余的非重要區(qū)域。對重要區(qū)域的編碼采用更加精細(xì)的匹配編碼，對該區(qū)域內(nèi)的非敏感區(qū)域劃分使用的閾值τ′不同于式(9)中的閾值τ，二者滿足τ′<τ，這樣可以使得更多處在重要區(qū)域內(nèi)的R塊進(jìn)行全局匹配，進(jìn)而使重要區(qū)域圖像灰度質(zhì)量提高。重要區(qū)域劃分如圖2所示。

Figure 2 Sensitive area圖2 重要區(qū)域

5 算法分析與實(shí)現(xiàn)

對于輸入的R塊和D塊，由式(8)知，如果R塊和D塊的質(zhì)心特征相差較大，則二者的均方誤差Ex(R,D)和Ey(R,D)也相差大，即整體均方誤差E(R,D)也會大，從而導(dǎo)致D塊不能與R塊匹配。對應(yīng)地，如果D塊是R塊的匹配塊，那么二者的整體均方誤差就會較小。因此可以認(rèn)為，如果R塊和D塊互為匹配塊，那么二者也是在質(zhì)心特征下的近鄰。需要指出，R塊和D塊在質(zhì)心特征下相差小，不一定代表E(R,D)也小，從而R塊和D塊在特征意義下的最佳匹配并不能保證D塊是R塊在最小均方誤差下的最佳匹配塊。盡管特征意義下R塊和D塊匹配不能保證均方誤差下二者的匹配，但是最佳匹配D塊距離也不會太遠(yuǎn)。本文采用擴(kuò)大搜索半徑的方法，在特征意義下以最佳匹配D塊為中心，距離L為半徑，步長K進(jìn)行搜索，尋找更大范圍內(nèi)的最佳匹配塊。

(10)

基于以上推導(dǎo)，本文算法的具體步驟如下所示：

步驟1將原始圖像分割成為不重疊的大小為n×n的R塊，以橫縱方向步長為Δ生成可重疊且大小為2n×2n的D塊，采用鄰域平均方法將D塊大小變?yōu)閚×n，并構(gòu)成碼本Ω。

步驟2將原始圖像劃分出重要區(qū)域和非重要區(qū)域，設(shè)置閾值τ′、τ、η、搜索半徑L以及步長K。

步驟3對重要區(qū)域使用閾值τ′進(jìn)行敏感區(qū)域劃分。若R塊滿足σ<τ′，則認(rèn)為其是敏感區(qū)域，求取并存儲其平均值aver作為參數(shù)；若R塊滿足σ>τ′，則認(rèn)為其是非敏感區(qū)域。對敏感區(qū)域R塊在碼本Ω中進(jìn)行質(zhì)心特征匹配，尋找匹配塊Dm，以Dm為中心，L為搜索半徑，K為步長搜索最佳匹配塊D′m，并存儲參數(shù)。當(dāng)滿足E(R,D′m)<η，搜索結(jié)束。

步驟4對非重要區(qū)域使用閾值τ進(jìn)行敏感區(qū)域劃分。滿足σ<τ認(rèn)為是敏感區(qū)域，求取并存儲平均值aver作為參數(shù)；滿足σ>τ認(rèn)為是非敏感區(qū)域。對敏感區(qū)域R塊在碼本Ω中進(jìn)行質(zhì)心特征匹配，尋找匹配塊Dm，以Dm為中心，L為搜索半徑，K為步長搜索最佳匹配塊D′m，并存儲參數(shù)。當(dāng)滿足E(R,D′m)<η，搜索結(jié)束。

步驟5對于所有R塊，重復(fù)步驟2～步驟4，其中將處在重要區(qū)域與非重要區(qū)域邊界的R塊判定為重要區(qū)域。

6 實(shí)驗(yàn)結(jié)果與仿真

實(shí)驗(yàn)中采用的圖像是Matlab標(biāo)準(zhǔn)庫中圖像，大小分別有256×256和512×512，R塊大小取用4×4，D塊大小取用8×8，D塊劃分間隔為8像素，半徑L為40像素，步長K為4像素，圖像恢復(fù)效果采用人眼觀察、峰值信噪比PSNR(Peak Signal to Noise Ratio)、重要區(qū)域峰值信噪比SAPSNR(Sensitive Area Peak Signal to Noise Ratio)、編碼時(shí)間、解碼時(shí)間和壓縮比進(jìn)行評價(jià)。其中SAPSNR值作為重要區(qū)域的峰值信噪比[5]，即等于恢復(fù)圖像中心1/4部分的PSNR。

本文參考2種特征類似的算法，分別是張璟等人在文獻(xiàn)[18]提出的雙交叉和特征算法、何傳江等人在文獻(xiàn)[16,17]中提出的叉跡特征算法，以及基本分形圖像壓縮方法，對重要區(qū)域峰值信噪比(SAPSNR)進(jìn)行對比；同時(shí)為了觀察圖像敏感區(qū)域恢復(fù)效果，計(jì)算恢復(fù)圖像子塊均方根大于4的部分的峰值信噪比。李高平等人在文獻(xiàn)[10]中認(rèn)為均方根小于4的部分的子塊為敏感塊，對比實(shí)驗(yàn)中采用統(tǒng)一閾值τ=4。本文算法非重要區(qū)域采用敏感區(qū)域閾值τ=4，對于重要區(qū)域閾值τ′=3。

(11)

(12)

(13)

SAPSNR=

(14)

恢復(fù)圖像的壓縮比CR(Compression Ratio)的計(jì)算方式如式(15)所示：

(15)

其中，Num1表示圖像經(jīng)過壓縮后傳輸過程中數(shù)據(jù)量，Num2表示圖像不經(jīng)過壓縮直接傳輸所需要數(shù)據(jù)量。

表1所示為基本分形算法、雙交叉和特征算法以及本文質(zhì)心特征算法的實(shí)驗(yàn)結(jié)果，其中C代表Cameraman圖像，L代表Lena圖像，P代表Peppers圖像,PSNR(Sensitive area)代表恢復(fù)圖像中滿足敏感區(qū)域條件的PSNR值的和。從表1可看出，本文算法相比文獻(xiàn)中算法壓縮效果更好。

Table 1 PSNR(Sensitive area) and SAPSNR value comparison

如表2所示，實(shí)驗(yàn)中選用的搜索半徑L與R塊長度相同，步長K為R塊長度的10倍，本文算法在PSNR值可以接受情況下，編碼時(shí)間相較于基本分形圖像壓縮算法，最高可節(jié)省大約64%。

Table 2 Image PSNR,encoding time,decoding time simulation results of C image

分形圖像壓縮算法未劃分敏感區(qū)域和重要區(qū)域，采用全局搜索方法，從表3中可以看出，CR值與塊大小成反比。雙交叉和算法非敏感區(qū)域閾值τ都取4。本文算法中，重要區(qū)域內(nèi)敏感區(qū)域劃分閾值取3，非重要區(qū)域內(nèi)敏感區(qū)域閾值取4。

Table 3 Compression ratio of algorithms under different block sizes

圖3是實(shí)驗(yàn)圖像在不同算法以及不同塊大小下的恢復(fù)圖像，圖像大小分別為256×256,256×256,512×512,512×512，從左至右分別為原始圖像、基本算法恢復(fù)圖像(4×4)、本文算法恢復(fù)圖像(4×4)、交叉和算法恢復(fù)圖像(4×4)、基本算法恢復(fù)圖像(8×8)、本文算法恢復(fù)圖像(8×8)。從圖3中可以看出，本文算法恢復(fù)的圖像效果比雙交叉和算法恢復(fù)的效果更好。

7 結(jié)束語

本文提出了一種質(zhì)心特征和重要敏感區(qū)域分類的分形圖像壓縮算法，利用圖像塊質(zhì)心特征，對相似圖像塊進(jìn)行近似匹配，在分形圖像壓縮編碼階段，利用質(zhì)心特征對R塊和D塊進(jìn)行匹配，有效縮短了編碼階段的時(shí)間。同時(shí)考慮人眼對圖像敏感區(qū)域和重要區(qū)域的選擇，采用重要區(qū)域和敏感區(qū)域劃分方法，增加人眼對恢復(fù)圖像效果的好感度。實(shí)驗(yàn)結(jié)果表明，質(zhì)心特征分類和重要敏感區(qū)域劃分處理的分形圖像壓縮算法相比傳統(tǒng)算法可以在編碼時(shí)間和恢復(fù)圖像效果上取得優(yōu)良效果，同時(shí)分類過程中的參數(shù)可調(diào)整，例如敏感區(qū)域劃分閾值、搜索步長和半徑等，具有較強(qiáng)的靈活性和直觀性，具有較好的應(yīng)用前景。

Figure 3 Recovery results圖3 恢復(fù)結(jié)果