張愛(ài)華，唐婷婷，汪瑋瑋，張 璟

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

0 引 言

在如今以計(jì)算機(jī)技術(shù)為基礎(chǔ)的信息化社會(huì)[1]，圖像資源豐富了人們的生活，圖像通信的需求日益增長(zhǎng)，所以對(duì)準(zhǔn)確、高效的圖像壓縮方法的需求也更為迫切。分形是對(duì)沒(méi)有特征長(zhǎng)度但具有一定意義下的自相似圖像和結(jié)構(gòu)的總稱。隨著多媒體信息的發(fā)展，生活中對(duì)于圖像壓縮的需求日益增加。傳統(tǒng)編碼研究已經(jīng)比較成熟，但圖像質(zhì)量和編碼效率難以提高。因此許多新的圖像壓縮編碼相繼提出，基于分形的圖像壓縮編碼就是其中一種。它利用圖像的自相似性及比例特性[2]進(jìn)行圖像壓縮，通過(guò)減少圖像幾何冗余來(lái)實(shí)現(xiàn)壓縮。把像素點(diǎn)灰度值的順序排列看成向量是圖像壓縮編碼中常見(jiàn)的做法，在分形壓縮編碼中，傳統(tǒng)特征向量法具有維數(shù)高[3]的缺點(diǎn)，高維時(shí)鄰近搜索效果也不好，導(dǎo)致編碼耗時(shí)過(guò)長(zhǎng)。

主成分分析法[4]是統(tǒng)計(jì)學(xué)的一種重要方法，用于數(shù)據(jù)集簡(jiǎn)化，可由線性變換將原始數(shù)據(jù)變換為一組各維度線性無(wú)關(guān)的表示，用于提取數(shù)據(jù)的主要特征分量，適用于對(duì)各種高維數(shù)據(jù)進(jìn)行降維。主成分分析法近年來(lái)在圖像識(shí)別、去噪、重構(gòu)方面都有應(yīng)用，在圖像壓縮上主成分分析法可以排除眾多信息互相重疊造成的冗余[5]。因此文中基于基本分形圖像壓縮理論，用主成分分析法構(gòu)造圖像特征，減少了搜索時(shí)間，為解決分形圖像編碼耗時(shí)過(guò)長(zhǎng)的缺點(diǎn)提供了有效的方法。

1 基本分形算法

在基本分形算法[6-7]，把待編碼的圖像I分割成一組互不重疊的大小為n×n的R塊以及尺寸為2n×2n的D塊(D塊允許有重疊)。求像素平均，將D塊收縮為R塊大小與R塊匹配，所有收縮過(guò)的D塊經(jīng)過(guò)8個(gè)等距變換后構(gòu)成碼本Ω。為了尋求R塊的最佳匹配塊，需要解決下面的極小化問(wèn)題：

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

(1)

其中，m為R塊的最佳匹配塊序號(hào)；s為對(duì)比度因子；o為亮度偏移。

通常解決問(wèn)題1是十分困難的，在實(shí)際應(yīng)用中，通常忽略式1中的約束|s|<1，對(duì)不滿足約束的對(duì)比因子作截?cái)嗵幚硪匝a(bǔ)償[8]。因此，式1的內(nèi)層約束極小化問(wèn)題轉(zhuǎn)化為下述問(wèn)題進(jìn)行求解：

(2)

此時(shí)，匹配誤差為：

(3)

接著用全搜索法求解問(wèn)題1的外層極小化問(wèn)題：

(4)

文中先對(duì)圖像子塊做標(biāo)準(zhǔn)化處理[10-11]，然后做主成分分析處理，也就是先求出其協(xié)方差，通過(guò)求協(xié)方差的特征值和特征向量，找到最大特征值對(duì)應(yīng)的向量，作為原圖像子塊的主成分，通過(guò)求主成分對(duì)應(yīng)向量來(lái)定義圖像規(guī)范塊的特征。在搜索匹配塊時(shí)，在初始匹配塊的鄰域內(nèi)搜索主成分特征接近的匹配塊，搜索大小由預(yù)先設(shè)置的剔除條件確定。

2 算法理論依據(jù)

2.1 主成分特征的理論基礎(chǔ)

在基本分形做法中，圖像塊被讀取的形式往往是矩陣。而在矩陣?yán)碚撝校卣髦荡砹诵畔⒘?。特征值和特征向量求法眾多，圖像子塊特征[12]往往與搜索的準(zhǔn)確性以及解碼圖像質(zhì)量息息相關(guān)，因而選好圖像塊的特征是關(guān)鍵。主成分分析過(guò)程能夠去除圖像的相關(guān)性[13]，能夠?qū)D像信息進(jìn)行有效降維。文中采用如下方式來(lái)定義圖像塊的特征：

定義1：設(shè)大小為n×n的圖像塊X=(xi,j)∈RN×N，對(duì)數(shù)據(jù)X做標(biāo)準(zhǔn)化處理，即對(duì)每一個(gè)指標(biāo)分量做標(biāo)準(zhǔn)化處理：

(5)

其中樣本均值和樣本標(biāo)準(zhǔn)差為：

(6)

(7)

也就是主成分分析法求解了如下的特征問(wèn)題：

λiui=Cui,i=1,2,…,n

(8)

其中，λi為C的一個(gè)特征值；ui為相應(yīng)的特征向量。

對(duì)特征向量按特征值大小降序排列，僅需要k個(gè)主成分時(shí)，主成分分析法的變換表示為：

(9)

定義2(最大主成分特征)：一個(gè)圖像子塊X=(xi,j)n×n的主成分特征可以定義為：

(10)

理論基礎(chǔ)為下述定理并給出證明：

定理：設(shè)R,D∈RN×N，則有不等式:

(11)

證明：定義子塊B=[bi,j]n×n∈RN×N為：

可以得到‖B‖2=2N。

由柯西—許瓦茲[16]不等式知：|〈x,y〉|2≤〈x,x〉〈y,y〉或|〈x,y〉|≤‖x‖·‖y‖。

|S(R)-S(D)|2=

(12)

由式4和式12可知：

E(R,D)2=

(13)

2.2 搜索方案

上式表明：若D塊和R塊的主成分特征相差較大，則匹配誤差也較大，此時(shí)D不能匹配R；反之，如果D匹配R，即E(R,D)最小，由式11可知S(D)應(yīng)該與S(R)非常接近。它表明R塊的最佳匹配D塊在主成分特征意義下一定是與R最相近的Dc∈Ω(Dc稱為初始匹配塊)的近鄰。搜索時(shí)，先將碼本中的D塊求取其主成分特征，再按升序進(jìn)行排列[18]，即滿足S(Di)≤S(DI+1)。再使用二分法在主成分特征中搜索與S(R)相差最小的初始匹配塊:

Dc={D∈Ω|min|S(D)-S(R)||}

(14)

最后，在鄰域N(Dc)={DI∈Ω:l≤|i-c|≤r}中搜索最佳匹配塊Dm(i)，使匹配誤差E(R,Dm(i))<ε(ε為誤差閾值)。顯然N(Dc)∈Ω，將搜索空間變?yōu)榫钟蛩阉?。編碼時(shí)間會(huì)因搜索空間縮小而減少，從而達(dá)到加快編碼速度的效果。

此外，研究表明，碼本Ω中的小方差碼本塊可以預(yù)先排除[19]，不僅能減少碼本容量，而且可以提高解碼圖像的質(zhì)量。因此，可用縮減后的容許碼本Ωη={D∈Ω:σD≥η}去置換碼本Ω。

2.3 仿真算法描述

(1)把圖像分成互不重疊的B×B塊，記為R塊，其中每個(gè)像素點(diǎn)的灰度值做標(biāo)準(zhǔn)化處理R∈N。以縱橫方向步長(zhǎng)均為δ的像素生成尺寸為2B×2B的D塊，再對(duì)每個(gè)圖像塊采用4-鄰域像素平均得到B×B大小的塊，考慮8種等距變換，組成子塊集合構(gòu)成碼本Ω。

(2)設(shè)定初始化參數(shù)τ>0，碼本塊的標(biāo)準(zhǔn)閾值為η，誤差閾值設(shè)為ε，初始鄰域半徑為k，擴(kuò)域步長(zhǎng)為L(zhǎng)。

(3)設(shè)定碼本閾值η>0，把縮減后的容許碼本記為Ωη：Ωη={D∈Ω|σD≥η}。

(4)計(jì)算每個(gè)D∈Ωη的主成分特征S(D)，并按照S(D)進(jìn)行升序排列。

(5)計(jì)算R的標(biāo)準(zhǔn)差。如果σR≥τ，則計(jì)算R塊的主成分特征S(R)，用二分搜索法在碼本Ωη中找到與R特征接近的初始匹配DC塊，搜索過(guò)程在DC的左右方向進(jìn)行，直到滿足E(R,Dm(i))<ε(ε為誤差閾值)為止。

(7)對(duì)其他的R塊(σR≥τ)，重復(fù)步驟5、6。

3 仿真實(shí)驗(yàn)及結(jié)果

圖像仿真采用方塊分割,實(shí)驗(yàn)對(duì)象為三幅不同類型512×512標(biāo)準(zhǔn)測(cè)試圖像，它們分別是Lena,Boats,Peppers。選取R塊大小為8×8，D塊大小為16×16，步長(zhǎng)σ=8，仿真程序使用MATLAB 2009編寫，測(cè)試參數(shù)為編碼時(shí)間(s)，峰值信噪比PSNR(dB)[20]。

通過(guò)實(shí)驗(yàn)將文中算法與基本算法的編碼性能進(jìn)行比較。主成分特征算法的編碼時(shí)間與解碼圖像質(zhì)量跟R塊的分類閾值τ，容許碼本閾值參數(shù)η，搜索效果與鄰域半徑大小k有關(guān)。對(duì)于參數(shù)τ和η，固定其取值，默認(rèn)τ=4，η=30。根據(jù)三幅圖像的仿真數(shù)據(jù)，將文中算法同基本算法的結(jié)果列表進(jìn)行比較分析。

表1 文中算法隨鄰域k變化的實(shí)驗(yàn)結(jié)果

下面針對(duì)選用的三幅圖像，在相同實(shí)驗(yàn)條件下，測(cè)試基本分形編碼方法與文中方法(τ=4，η=30)的編碼性能優(yōu)劣，實(shí)驗(yàn)結(jié)果見(jiàn)表1。從表中數(shù)據(jù)可以看出，在k=100重構(gòu)圖像質(zhì)量平均下降1.41 dB的情況下，可以加快平均編碼速度48倍以上。文中給出在k=100時(shí)，三幅測(cè)試圖的基本分形算法結(jié)果和文中分形算法結(jié)果，見(jiàn)圖1。

圖1 算法結(jié)果

從表1和圖1可知，主成分特征算法與基本分形算法相比，從主觀上看，基于主成分特征算法基本上不改變重構(gòu)圖像的質(zhì)量；從客觀上看，基本算法、文中算法可以在不影響高信噪比的基礎(chǔ)上，減少運(yùn)算時(shí)間，提高結(jié)構(gòu)相似度。綜上所述，文中算法可以在保證一定圖像質(zhì)量的前提下，大幅提高編碼速度和結(jié)構(gòu)相似度。

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

傳統(tǒng)分形壓縮編碼中通常具有提取的圖像特征冗余過(guò)多的缺點(diǎn)，文中提出了一種基于主成分分析法的分形壓縮改進(jìn)方法，通過(guò)對(duì)圖像子塊盡可能提取有效信息，然后用該信息定義圖像特征，在不影響圖像質(zhì)量的前提下，提高了編碼速度。全局搜索通常耗時(shí)較長(zhǎng)，文中引進(jìn)鄰域搜索，可以根據(jù)搜索情況來(lái)調(diào)節(jié)搜索范圍，有較強(qiáng)的靈活性。實(shí)驗(yàn)結(jié)果表明，該算法相對(duì)基本分形算法更加簡(jiǎn)潔有效。

參考文獻(xiàn)：

[1] 馮澤森,王崇國(guó).計(jì)算機(jī)與信息技術(shù)基礎(chǔ)[M].第3版.北京:電子工業(yè)出版社,2007.

[2] FALCONER K.分形幾何:數(shù)學(xué)基礎(chǔ)及其應(yīng)用[M].第2版.北京:人民郵電出版社,2007.

[3] 李高平.分形法圖像壓縮編碼[M].成都:西南交通大學(xué)出版社,2010.

[4] 劉 濤,楊風(fēng)暴.主成分分析在圖像壓縮中的應(yīng)用[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào),2008,24(4):69-72.

[5] 魯書山,沈小林,樊凱強(qiáng).主成分分析法在數(shù)字圖像壓縮中的的應(yīng)用[J].科技與創(chuàng)新,2016(23):98.

[6] JACQUIN A E.Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing,1992,1(1):18-30.

[7] HE Chuanjiang,XU Xiaozeng,YANG Jing.Fast fractal im-

age encoding using one-norm of normalised block[J].Chaos Solitons & Fractals,2006,27(5):1178-1186.

[8] 楊興全.基于分形理論的圖像壓縮研究[D].哈爾濱:黑龍江大學(xué),2008.

[9] BARNSLEY M F,SLOAN A D,ELTON J H,et al.Fractal transform compression board:US,US5384867A[P].1995.

[10] 張 敏,李陶深,鐘淑瑛.基于Matlab的主成分分析方法(PCA)的實(shí)現(xiàn)[J].廣西大學(xué)學(xué)報(bào):自然科學(xué)版,2005,30:74-77.

[11] 趙慧琳,王林泉,葛 元.人臉圖像定位與標(biāo)準(zhǔn)化算法[J].計(jì)算機(jī)工程,2003,29(22):158-160.

[12] 袁宗文,魯業(yè)頻,楊漢生.半叉跡特征的快速分形圖像編碼[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(3):197-201.

[13] 姜 虹.主成分分析的圖像壓縮與重構(gòu)[J].電子設(shè)計(jì)工程,2012,20(5):126-128.

[14] 李俊秀.基于主成分分析的半局部塊匹配圖像降噪算法研究[D].太原:中北大學(xué),2014.

[15] ZHANG Lin,ZHANG Lei,MOU Xuanqin.FSIM:a feature similarity index of image quality assessment[J].IEEE Transactions on Image Processing,2011,20(8):2378-2386.

[16] 周一鳴,張 超,張?jiān)?基于圖像子塊特征的快速分形圖像編碼算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(2):458-459.

[17] 何傳江,黃席樾.基于圖像塊叉跡的快速分形圖像編碼算法[J].計(jì)算機(jī)學(xué)報(bào),2005,28(10):1753-1758.

[18] HE C,YANG S X,HUANG X.Variance-based accelerating scheme for fractal image encoding[J].Electronics Letters,2004,40(2):115-116.

[19] 莊振靜,何傳江,申小娜.基于規(guī)范塊半范數(shù)的快速分形編碼算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(2):170-173.

[20] 汪明華,李高平.基于相似比的變鄰域搜索的快速分形編碼算法[J].西南民族大學(xué)學(xué)報(bào):自然科學(xué)版,2016,42(6):682-687.