基于主成分特征的快速分形圖像壓縮算法

張愛華，唐婷婷，汪瑋瑋，張 璟

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

0 引 言

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

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

1 基本分形算法

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

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

(1)

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

通常解決問題1是十分困難的，在實際應用中，通常忽略式1中的約束|s|<1，對不滿足約束的對比因子作截斷處理以補償[8]。因此，式1的內層約束極小化問題轉化為下述問題進行求解：

(2)

此時，匹配誤差為：

(3)

接著用全搜索法求解問題1的外層極小化問題：

(4)

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

2 算法理論依據(jù)

2.1 主成分特征的理論基礎

在基本分形做法中，圖像塊被讀取的形式往往是矩陣。而在矩陣理論中，特征值代表了信息量。特征值和特征向量求法眾多，圖像子塊特征[12]往往與搜索的準確性以及解碼圖像質量息息相關，因而選好圖像塊的特征是關鍵。主成分分析過程能夠去除圖像的相關性[13]，能夠對圖像信息進行有效降維。文中采用如下方式來定義圖像塊的特征：

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

(5)

其中樣本均值和樣本標準差為：

(6)

(7)

也就是主成分分析法求解了如下的特征問題：

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

(8)

其中，λi為C的一個特征值；ui為相應的特征向量。

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

(9)

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

(10)

理論基礎為下述定理并給出證明：

定理：設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塊的主成分特征相差較大，則匹配誤差也較大，此時D不能匹配R；反之，如果D匹配R，即E(R,D)最小，由式11可知S(D)應該與S(R)非常接近。它表明R塊的最佳匹配D塊在主成分特征意義下一定是與R最相近的Dc∈Ω(Dc稱為初始匹配塊)的近鄰。搜索時，先將碼本中的D塊求取其主成分特征，再按升序進行排列[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)榫钟蛩阉?。編碼時間會因搜索空間縮小而減少，從而達到加快編碼速度的效果。

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

2.3 仿真算法描述

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

(2)設定初始化參數(shù)τ>0，碼本塊的標準閾值為η，誤差閾值設為ε，初始鄰域半徑為k，擴域步長為L。

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

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

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

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

3 仿真實驗及結果

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

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

表1 文中算法隨鄰域k變化的實驗結果

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

圖1 算法結果

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

4 結束語

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

參考文獻：

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

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

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

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

[5] 魯書山,沈小林,樊凱強.主成分分析法在數(shù)字圖像壓縮中的的應用[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].哈爾濱:黑龍江大學,2008.

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

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

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

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

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

[14] 李俊秀.基于主成分分析的半局部塊匹配圖像降噪算法研究[D].太原:中北大學,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] 周一鳴,張 超,張曾科.基于圖像子塊特征的快速分形圖像編碼算法[J].計算機應用研究,2008,25(2):458-459.

[17] 何傳江,黃席樾.基于圖像塊叉跡的快速分形圖像編碼算法[J].計算機學報,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].計算機工程與應用,2010,46(2):170-173.

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