融合全局和局部特征的圖像特征提取方法

張雅清，劉忠寶.太原學(xué)院數(shù)學(xué)系，山西太原0300；.中北大學(xué)計算機與控制工程學(xué)院，山西太原03005）

?

融合全局和局部特征的圖像特征提取方法

張雅清1，劉忠寶2
1.太原學(xué)院數(shù)學(xué)系，山西太原030012；
2.中北大學(xué)計算機與控制工程學(xué)院，山西太原030051）

摘要：針對圖像特征提取無法同時利用樣本的全局和局部特征的問題，提出融合全局和局部特征的特征提取方法.該方法充分利用線性判別分析和保局投影算法分別在特征提取中保持樣本全局特征和局部特征方面的優(yōu)勢，進(jìn)一步提高圖像特征提取效率.首先，引入全局散度矩陣和局部散度矩陣分別表征樣本的全局特征和局部特征.然后，基于同類樣本盡可能緊密，異類樣本盡可能遠(yuǎn)離的思想，構(gòu)造最優(yōu)化問題.比較實驗表明：與傳統(tǒng)的主成分分析、線性判別分析、保局投影算法相比，文中方法的工作效率有一定提高.

關(guān)鍵詞：特征提??；線性判別分析；保局投影算法；全局特征；局部特征

特征提取是模式識別、數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域研究的重點問題之一，近年來受到眾多研究人員的廣泛關(guān)注［1］.特征提取是指原始特征空間根據(jù)某種準(zhǔn)則變換得到低維投影空間的過程［2－3］.當(dāng)前主流的特征提取方法主要包括線性方法和非線性方法.其中，線性方法有主成分分析（PCA）［4］、奇異值分解（SVD）［5］、非負(fù)矩陣分解（NMF）［6］、獨立成分分析（ICA）［7］、線性判別分析（LDA）［8］；非線性方法有多維縮放（MDS）［9］、局部線性嵌入（LLE）［10］、保局投影（LPP）［11］.此外，還有核主成分分析（KPCA）［12］、核線性判別分析（KLDA）［13－14］、拉普拉斯特征映射（Laplacian eigenmap）等［15］.當(dāng)前主流的特征提取方法主要基于兩種思路：一是基于樣本的全局特征突出樣本間的差異性；二是利用樣本的局部特征保證特征提取前后樣本局部結(jié)構(gòu)的一致性.當(dāng)前圖像特征提取相關(guān)研究面臨的最大問題是無法同時利用樣本的全局特征和局部特征.鑒于此，本文提出融合全局和局部特征的特征提取方法（FEM－GLC）.

1　融合全局和局部特征的特征提取方法

1.1 線性判別分析

線性判別分析（LDA）是模式世界中一種經(jīng)典的有監(jiān)督學(xué)習(xí)方法，是提取鑒別特征的有效判別方法之一，為各種線性判別分析方法的提出奠定基礎(chǔ)，因此，LDA也被稱為FLDA（fisher linear discriminant analysis）.LDA的基本思想是保證特征提取后的同類樣本盡可能緊密，而異類樣本盡可能遠(yuǎn)離.LDA在引入人類建離散度矩陣和類內(nèi)離散度矩陣的基礎(chǔ)上，利用Fisher準(zhǔn)則，建立最優(yōu)化問題.

定義1類間離散度矩陣為

定義2類內(nèi)離散度矩陣為

Fisher準(zhǔn)則定義為

利用Fisher準(zhǔn)則得到的最優(yōu)投影矩陣Wopt保證特征提取后的樣本具有最大的類間離散度和最小的類內(nèi)離散度.當(dāng)SW非奇異時，Wopt滿足等式的解.LDA及其改進(jìn)算法具有以下2點優(yōu)勢：1）LDA及其改進(jìn)算法將原最優(yōu)化問題轉(zhuǎn)化為廣義特征值求解問題，可以得到全局最優(yōu)解，避免其他方法可能得到的局部最優(yōu)解；2）LDA無需事先給定參數(shù)，因而不存在參數(shù)選擇問題，克服了神經(jīng)網(wǎng)絡(luò)等方法的不足.然而，隨著應(yīng)用的深入，LDA本身也有一些問題亟待解決，制約其效率進(jìn)一步提升的關(guān)鍵問題是LDA在特征提取時僅關(guān)注樣本的全局特征，并未考慮局部特征.

1.2 保局投影算法

保局投影算法（LPP）作為一種重要的特征提取方法，更注重樣本的局部流形結(jié)構(gòu).LPP有效地克服了非線性方法的不足，在特征提取時，很好地保留了原始樣本之間的非線性結(jié)構(gòu).LPP的基本思想是保證原始空間相鄰的樣本在特征提取后相對關(guān)系盡量不變.

LPP的算法流程有以下3個步驟.

步驟1 定義ε鄰域或k鄰域，構(gòu)造鄰接圖G.

1）ε近鄰：當(dāng)樣本xi，xj滿足相鄰，并將兩者連接起來.

2）k近鄰：當(dāng)樣本xi是樣本xj的k個近鄰之一，則將兩者連接起來.其中，k為事先給定參數(shù).步驟2 計算鄰接圖G中邊的權(quán)重.相似度函數(shù)描述樣本xi，xj的相似度，其定義為上式中：t為常數(shù).

步驟3 求投影矩陣.最優(yōu)化表達(dá)式為

式（4），（5）中：W為投影矩陣；Si，j為相似度函數(shù)；

上述最優(yōu)化問題可轉(zhuǎn)化為

式（6），（7）中：L＝D－S.

綜上可知：LPP在進(jìn)行特征提取時關(guān)注的是樣本的局部結(jié)構(gòu)，其試圖保持樣本的局部結(jié)構(gòu)在特征提取前后不變.然而，LPP特征提取效率并非最優(yōu)，因為在特征提取時并未考慮樣本的全局特征.1.3 算法思想

為了充分利用樣本的內(nèi)在特征并有效提高特征提取效率，提出融合全局和局部特征的特征提取方法FEM－GLC.該方法受到LDA算法在Fisher準(zhǔn)則基礎(chǔ)上保證類間離散度與類內(nèi)離散度之比最大，以及LPP保持樣本的局部流形結(jié)構(gòu)不變的啟發(fā)，引入局部散度矩陣和全局散度矩陣這兩個重要概念，分別刻畫樣本的局部特征和全局特征.

定義3 局部散度矩陣為

式（8）中：相似度函數(shù)Si，j定義為式（9）中：ε是一個很小的正數(shù)，經(jīng)驗性取值為0.001.

由式（8），（9）可知：局部散度矩陣反映的是樣本xi，xj的相似度.特征提取的目的是保證相鄰樣本在特征提取前后相對關(guān)系保持不變.

定義4 全局散度矩陣為

由式（10）可知：全局散度矩陣在特征提取前后均彼此遠(yuǎn)離.基于以上分析，F(xiàn)EM－GLC算法保證找到的投影方向滿足類間差異度和類內(nèi)相似度均盡可能大.

1.4 最優(yōu)化問題

FEM－GLC算法的最優(yōu)化表達(dá)式為

式（11），（12）中：目標(biāo)函數(shù)中的WTGW，WTLW分別表示投影后的異類數(shù)據(jù)盡可能遠(yuǎn)離，而同類數(shù)據(jù)盡可能緊密；常數(shù)k為平衡因子，其取值為正數(shù)，k反映了在特征提取過程中全局特征和局部特征對最終結(jié)果的影響程度；約束條件WWT將投影矩陣進(jìn)行歸一化處理.

上述最優(yōu)化問題可通過Lagrange乘子法求解.定義Lagrange函數(shù)為

式（13）中：λ為Lagrange乘子.J（W，k）對W求偏導(dǎo)，可得

令式（14）偏導(dǎo)為零，可得

即

求解式（16）等價于求解矩陣G－kL的特征值問題.

為了保證投影方向同時滿足類間差異度和類內(nèi)相似度最大，亦可做類似于LDA基于Fisher準(zhǔn)則的處理，即

上述優(yōu)化問題求解方法類似于LDA，其存在矩陣L奇異的問題，即當(dāng)矩陣L奇異時，L－1不存在，則無法求得投影方向W.因此，最優(yōu)化問題采用L1形式具有更好的健壯性.1.5 算法描述

輸入：訓(xùn)練樣本集X＝［x1，x2，…，xN］，用戶事先給定的降維數(shù)d.輸出：降維后的樣本集Y＝［y1，y2，…，yN］.

步驟1 當(dāng)xi，xj相鄰時，利用式（9）構(gòu)造相似度函數(shù).

步驟2 利用式（8）和式（10）分別計算局部散度矩陣和全局散度矩陣.

步驟3 求解投影方向W.求矩陣G－kL對應(yīng)的特征值和特征向量，將特征值按由大到小順序排列，選取最大的d個特征值對應(yīng)的特征向量作為投影方向W.

步驟4 對于新進(jìn)樣本x，利用y＝WTx可得其在投影方向W上的特征提取結(jié)果.

1.6 復(fù)雜性分析

FEM－GLC算法解決一個具有線性約束的二次規(guī)劃問題，其計算對象主要包括大小為N×N矩陣的轉(zhuǎn)置運算，以及QP問題求解運算.大小為N×N矩陣轉(zhuǎn)置運算的時間復(fù)雜度為O（N2log（N）），QP問題求解的時間復(fù)雜度為O（N2）.因此，F(xiàn)EM－GLC算法的時間復(fù)雜度為O（N2log（N））＋O（N2）.由于O（N2log（N））≥O（N2），F(xiàn)EM－GLC算法的時間復(fù)雜度可近似表示為O（N2log（N））.此外，F(xiàn)EM－GLC算法的空間復(fù)雜度為O（N2）.以上復(fù)雜度計算中，N表示訓(xùn)練樣本總數(shù).

2　實驗分析

為驗證FEM－GLC算法的有效性，在標(biāo)準(zhǔn)人臉數(shù)據(jù)集上進(jìn)行仿真實驗.硬件環(huán)境為CPU：Inter（R）Core（TM）i3－2350M2.3GHz，RAM：4.0G；軟件環(huán)境為Matlab 2014；操作系統(tǒng)為Windows 7.算法中參數(shù)k利用網(wǎng)格搜索法獲得，其取值范圍為｛0，1，1.5，2，2.5，3，3.5，4，4.5，5｝.

2.1 實驗步驟

實驗驗證采用如圖1，2所示的ORL和Yale人臉數(shù)據(jù)庫，具體有以下4個步驟.

步驟1 分別選取每人前m幅照片作為訓(xùn)練樣本，剩余照片作為測試樣本.

步驟2 利用FEM－GLC算法對訓(xùn)練樣本進(jìn)行學(xué)習(xí)，進(jìn)而得到投影方向W.

步驟3 將測試樣本逐個投影到W上得到降維后的樣本Y.

步驟4 利用最近鄰分類法（NN）對特征提取后的測試樣本與訓(xùn)練樣本進(jìn)行比對，得到識別結(jié)果.

圖1　ORL人臉數(shù)據(jù)庫部分人臉圖像Fig.1　Part of face images on the ORL dataset

圖2　Yale人臉數(shù)據(jù)庫部分人臉圖像Fig.2　Part of face images on the Yale dataset

2.2 參數(shù)k對識別率的影響

選取ORL人臉庫中每人前4幅照片作為訓(xùn)練樣本，剩下的6幅照片作為測試樣本.當(dāng)降維數(shù)為100時，識別率η與參數(shù)m的關(guān)系，如圖3所示.

由圖3可知：當(dāng)m＝1時，識別率取得最小值為0.82；當(dāng)m＝4時，識別率取得最大值為0.89.從識別率角度看，參數(shù)m不論如何取值對識別率的影響基本可以接受，即FEM－GLC可以較好地完成特征提取任務(wù).

2.3 降維數(shù)d對識別率的影響

選取ORL人臉庫中每人前4幅照片作為訓(xùn)練樣本，剩下的6幅照片作為測試樣本.不失一般性，選取m＝2，識別率η與降維數(shù)d的關(guān)系，如圖4所示.由圖4可知：隨著降維數(shù)的增加，識別率呈上升趨勢；當(dāng)降維數(shù)d＝40時，識別率達(dá)到最大值0.895.

圖3　識別率與參數(shù)m的關(guān)系Fig.3　Relationship between the recognition accuracies and the parameter m

圖4　識別率與降維數(shù)d的關(guān)系Fig.4　Relationship between the recognition accuracies and the reduced dimension d

2.4 訓(xùn)練樣本數(shù)對識別率的影響

選取ORL人臉庫中每人前m（m＝3，4，5，6，7，8）幅照片，以及Yale人臉庫中每人前m′（m′＝4，5，6，7，8，9）幅照片作為訓(xùn)練樣本，剩余照片作為測試樣本.與傳統(tǒng)的特征提取方法PCA，LDA，LPP比較，驗證FEM－GLC的有效性.由于存在小樣本問題，LDA實為PCA＋LDA.訓(xùn)練樣本數(shù)對識別率（η）的影響，如表1所示.表1中：FEM－GLC算法識別率后的括號表示參數(shù)k的取值.

由表1可知：隨著訓(xùn)練樣本數(shù)的增加，識別率不斷提高.在大多情況下，較之傳統(tǒng)特征提取方法，F(xiàn)EM－GLC的識別率具有一定優(yōu)勢.當(dāng)選取ORL人臉庫中每人前3，4幅照片作為訓(xùn)練樣本時，LDA識別率最高，F(xiàn)EM－GLC與LPP均次之；當(dāng)選取Yale人臉庫中每人前4幅照片作為訓(xùn)練樣本時，LPP識別率最高，F(xiàn)EM－GLC次之.在以上兩種情況下，F(xiàn)EM－GLC算法效率僅次于LDA，LPP，但仍具有較高的識別率.綜上所述，從平均性能角度看，較之傳統(tǒng)方法，F(xiàn)EM－GLC可以更好地完成特征提取任務(wù).

表1　識別率與訓(xùn)練樣本數(shù)的關(guān)系Tab.1　Relationship between the recognition accuracies and the number of training samples

2.5 時間代價比較

選取ORL人臉庫中每人前m（m＝3，4，5，6，7，8）幅照片作為訓(xùn)練樣本，剩余照片作為測試樣本.各算法的時間代價（t），如表2所示.由表2可知：與PCA，LDA，LPP相比，F(xiàn)EM－GLC的時間代價更大，因為在特征提取時考慮了樣本的全局特征以及局部特征.因此，F(xiàn)EM－GLC能在可接受的時間范圍內(nèi)高效地完成特征提取任務(wù).

表2　PCA，LDA，LPP，F(xiàn)EM－GLC算法的時間代價Tab.2　Time cost of LDA，LDA，LPP，F(xiàn)EM－GLC

3　結(jié)束語

特征提取方法是模式識別、數(shù)據(jù)挖掘、機器學(xué)習(xí)等領(lǐng)域研究的重點問題之一.經(jīng)過近年的發(fā)展，先后涌現(xiàn)出不少有效算法.為了進(jìn)一步提高特征提取效率，提出融合全局和局部特征的特征提取方法FEMGLC.該方法引入局部散度矩陣和全局散度矩陣兩個重要概念，分別刻畫樣本的局部特征和全局特征，保證找到的投影方向滿足類間差異度和類內(nèi)相似度均盡可能大.在ORL，Yale人臉庫上的實驗驗證了所提方法的有效性.FEM－GLC的算法效率對參數(shù)的選取有一定依賴，如何快速準(zhǔn)確獲取相關(guān)參數(shù)，以及如何對參數(shù)進(jìn)行優(yōu)化等問題是今后研究的方向.

參考文獻(xiàn)：

［1］羅學(xué)剛，呂俊瑞，王華軍，等.基于超像素的互惠最近鄰聚類彩色圖像分割［J］.廣西大學(xué)學(xué)報：自然科學(xué)版，2013，38（2）：374－378.

［2］劉忠寶.基于核的降維和分類方法及其應(yīng)用研究［D］.無錫：江南大學(xué)，2012：1－2.

［3］陳新泉，蘇錦細(xì).基于半監(jiān)督學(xué)習(xí)的k平均聚類框架［J］.廣西大學(xué)學(xué)報：自然科學(xué)版，2014，39（5）：1074－1082.

［4］CAMACHO J，PIC J，F(xiàn)ERRER A.Data understanding with PCA：Structural and variance information plots［J］.Chemometrics and Intelligent Laboratory Systems，2010，100（1）：48－56.

［5］LIPOVETSKY S.PCA and SVD with nonnegative loadings［J］.Pattern Recognition，2009，42（1）：68－76.

［6］LEE D D，SEUNG H S.Learning the parts of objects by non－negative matrix factorization［J］.Nature，1999，401 （6755）：788－791.

［7］RADULOVIC J，RANKOVIC V.Feedforward neural network and adaptive network－based fuzzy inference system in study of power lines［J］.Expert Systems with Applications，2010，37（1）：165－170.

［8］PETER N B，JOAO P H，DAVID J K，et al.Fisherfaces：Recognition using class specific linear projection［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，1997，19（7）：711－720.

［9］杜家杰，段會川.MDS在企業(yè)客戶分類中的應(yīng)用研究［J］.計算機工程與設(shè)計，2011，32（5）：1658－1660.

［10］ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290 （5500）：2323－2326.

［11］HE Xiao－feng，NIYOGI P.Locality preserving projections［C］∥Advances in Neural Information Processing Systems.Vancouver：［s.n.］，2003：153－160.

［12］LOPEZ M M，RAMIREZ J，ALVAREZ I，et al.SVM－based CAD system for early detection of the Alzheimer′s disease using kernel PCA and LDA［J］.Neuroscience Letters，2009，464（3）：233－238.

［13］MIKA S，RATSCH G，WESTON J，et al.Constructing descriptive and discriminative nonlinear features：Rayleigh coefficients in kernel feature spaces［J］.Pattern Analysis and Machine Intelligence，2003，25（5）：623－628.

［14］HSUAN Y M.Kernel eigenfaces vs kernel fisherfaces：Face recognition using kernel methods［C］∥Processing of the 5th IEEE International Conference on Automatic Face and Gesture Recognition.Washington D C：IEEE Press，2002：215－220.

［15］BELKIN M，NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering［C］∥Processing of Advances in Neural Information Processing Systems.Cambridge：MIT Press，2001：585－591.

（責(zé)任編輯：錢筠 英文審校：吳逢鐵）

Research on Image Feature Exaction Method by Combining Global and Local Features

ZHANG Ya－qing1，LIU Zhong－bao2

（1.School of Mathematics，Taiyuan University，Taiyuan 030012，China；2.School of Computer and Control Engineering，North University of China，Taiyuan 030051，China）

Abstract：With the development of application，the main problem of image feature extraction is almost no study taking both global and local features into consideration.In view of this，feature exaction approach by combining global and local characteristics（FEM－GLC）is proposed in this paper.The advantages of linear discriminant analysis（LDA）in extracting the global feature and locally preserving projections（LPP）in preserving the local feature are taken into consideration in FEM－GLC which tries to improve the efficiencies of feature extraction.In FEM－GLC，the global divergence matrix and the local divergence matrix are introduced which respectively represents the global feature and local feature.The optimization problem of FEM－GLC is constructed based on the close relation between samples of the same class and far away between different classes.The comparative experiments with PCA，LDA and LPP on the ORL dataset and Yale dataset verify the effectiveness of FEM－GLC.

Keywords：feature exaction；linear discriminant analysis；locally preserving projections；global feature；local feature

通信作者：劉忠寶（1981－），男，副教授，博士后，主要從事機器學(xué)習(xí)的研究.E－mail：liu＿zhongbao＠hotmail.com

中圖分類號：TP 391

文獻(xiàn)標(biāo)志碼：A

文章編號：1000－5013（2015）04－0406－06

doi：10.11830/ISSN.1000－5013.2015.04.0406

收稿日期：2015－04－17

基金項目：國家自然科學(xué)基金資助項目（61202311）；山西省高等學(xué)?？萍紕?chuàng)新項目（2014142）