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

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

?

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

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

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

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

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

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

1.1 線性判別分析

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

定義1類間離散度矩陣為

定義2類內離散度矩陣為

Fisher準則定義為

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

1.2 保局投影算法

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

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

步驟1 定義ε鄰域或k鄰域，構造鄰接圖G.

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

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

步驟3 求投影矩陣.最優化表達式為

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

上述最優化問題可轉化為

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

綜上可知：LPP在進行特征提取時關注的是樣本的局部結構，其試圖保持樣本的局部結構在特征提取前后不變.然而，LPP特征提取效率并非最優，因為在特征提取時并未考慮樣本的全局特征.1.3 算法思想

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

定義3 局部散度矩陣為

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

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

定義4 全局散度矩陣為

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

1.4 最優化問題

FEM－GLC算法的最優化表達式為

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

上述最優化問題可通過Lagrange乘子法求解.定義Lagrange函數為

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

令式（14）偏導為零，可得

即

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

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

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

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

步驟1 當xi，xj相鄰時，利用式（9）構造相似度函數.

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

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

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

1.6 復雜性分析

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

2　實驗分析

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

2.1 實驗步驟

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

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

步驟2 利用FEM－GLC算法對訓練樣本進行學習，進而得到投影方向W.

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

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

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

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

2.2 參數k對識別率的影響

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

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

2.3 降維數d對識別率的影響

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

圖3　識別率與參數m的關系Fig.3　Relationship between the recognition accuracies and the parameter m

圖4　識別率與降維數d的關系Fig.4　Relationship between the recognition accuracies and the reduced dimension d

2.4 訓練樣本數對識別率的影響

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

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

表1　識別率與訓練樣本數的關系Tab.1　Relationship between the recognition accuracies and the number of training samples

2.5 時間代價比較

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

表2　PCA，LDA，LPP，FEM－GLC算法的時間代價Tab.2　Time cost of LDA，LDA，LPP，FEM－GLC

3　結束語

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

參考文獻：

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

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

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

［4］CAMACHO J，PIC J，FERRER 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在企業客戶分類中的應用研究［J］.計算機工程與設計，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.

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

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－），男，副教授，博士后，主要從事機器學習的研究.E－mail：liu＿zhongbao＠hotmail.com

中圖分類號：TP 391

文獻標志碼：A

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

doi：10.11830/ISSN.1000－5013.2015.04.0406

收稿日期：2015－04－17

基金項目：國家自然科學基金資助項目（61202311）；山西省高等學?？萍紕撔马椖浚?014142）