多流形的非監督線性差分投影算法*

楊章靜，萬鳴華,2,3+，王巧麗，張凡龍，楊國為

1.南京審計大學 工學院，南京 211815

2.南京理工大學 高維信息智能感知與系統教育部重點實驗室,南京 210094

3.南京曉莊學院 可信云計算與大數據分析重點實驗室，南京 211171

4.南昌航空大學 江西省圖像處理與模式識別重點實驗室，南昌 330063

多流形的非監督線性差分投影算法*

楊章靜1，萬鳴華1,2,3+，王巧麗4，張凡龍1，楊國為1

1.南京審計大學 工學院，南京 211815

2.南京理工大學 高維信息智能感知與系統教育部重點實驗室,南京 210094

3.南京曉莊學院 可信云計算與大數據分析重點實驗室，南京 211171

4.南昌航空大學 江西省圖像處理與模式識別重點實驗室，南昌 330063

YANG Zhangjing,WAN Minghua,WANG Qiaoli,et al.Multi-manifold unsupervised linear differential projection algorithm.Journal of Frontiers of Computer Science and Technology,2016,10(11)：1577-1586.

針對非監督線性差分投影（unsupervised linear differential projection，ULDP）在特征提取過程中存在的不足，提出了基于多流形的非監督線性差分投影（multi-manifold unsupervised linear differential projection，MULDP）算法，并將其應用于人臉識別中。MULDP首先構造出多流形局部近鄰圖和多流形最大全局方差，然后通過多目標最優化問題求解出嵌入在高維空間的低維流形。這種映射不僅能表示全局結構，還能表示局部結構。該算法可以得到嵌入在高維空間的低維流形，更好地實現了局部與全局結構信息的有效保持。在ORL、Yale及AR人臉庫上的實驗結果驗證了所提算法的優越性。

人臉識別；特征提取；多流形；非監督線性差分投影（ULDP）

1 引言

特征提取是人臉識別處理過程的核心，提取有效人臉特征是人臉識別的關鍵步驟，人臉特征的有效性直接影響人臉識別的結果[1-2]。對于人臉識別來說，尋找快速、有效的特征提取方法是人臉識別技術取得突破的關鍵，也是當前研究的熱點[3-4]。

目前，關于特征提取技術[5]的研究正如火如荼，方法也有多種，但概括起來主要有兩大類型：一類是基于全局特征的特征提取，另一類是基于局部特征的特征提取。全局特征是指其特征向量的每一維都包含了人臉圖像所有部分（甚至所有像素）的信息，它反映的是人臉的整體屬性。基于全局的特征方法主要包括PCA（principal component analysis）[6]、LDA（linear discriminant analysis）[7]、2DPCA（two-dimensional PCA）[8]等。與全局特征不同的是，局部特征信息的每一維都只對應人臉圖像的一個局部區域，側重于提取人臉的細節特征。基于局部特征的提取方法主要包括LPP（locality preserving projection）[9]、LLE（locally linear embedding）[10]、LBP（local binary pattern）[11-13]等。局部特征對人臉的光照、表情和遮擋等變化不敏感，因此相對于基于全局特征的提取方法，基于局部特征的提取方法具有更好的魯棒性，在近些年來受到越來越多研究者的關注[14-15]。也有很多研究者提出同時利用全局和局部特征來表示人臉[16-17]。Wan等人在PCA和LLE基礎上，同時考慮樣本分布全局性和局部性，結合PCA和LLE的特點，提出了非監督線性差分投影（unsupervised linear differential projection，ULDP）[16]的特征提取方法；Yang等人在同時考慮局部散度和非局部散度的基礎上，提出了非監督鑒別投影（unsupervised discriminant projection，UDP）[17]的特征提取方法。這些方法在加強數據樣本點之間的關聯性時，能有效地對局部與全局流形結構進行同時保持，也就是說在高維空間保持近鄰的數據點映射到內在低維空間后仍保持近鄰，反之，在高維空間不能保持近鄰的數據點映射到內在低維空間繼續保持其非近鄰的關系，因此應該同時對局部與全局流形結構進行保持，進而發現隱藏于高維空間樣本點間的流形，以提高人臉識別的精度。但這些方法也存在兩個缺陷：一是在學習過程中過分依賴訓練樣本的數目，當遇到小樣本問題時，就嚴重限制了此方法的應用；二是在提取的眾多特征中，無法揭示哪些特征對分類與預測起主導作用。

針對以上問題，本文借鑒ULDP的思想，提出了一種結合多流形的兼顧樣本全局結構與局部結構的特征提取算法，即基于多流形的非監督線性差分投影（multi-manifold unsupervised linear differential projection，MULDP）。MULDP首先將一個樣本分成的局部小塊都構造在同一個流形上，使得每個樣本都有屬于自己的流形，即位于同一個特征子空間；然后分別給出PCA和LLE的多流形表示，優化目標是最大化各個流形的全局方差，最小化流形內的局部嵌入。MULDP相對于ULDP，不僅解決了小樣本問題，而且進一步提高了識別率。在人臉數據庫上的實驗表明，MULDP較其他算法能獲得較好的識別效果。

2 相關知識

2.1 非監督的線性差分投影

基于局部特征的流形學習方法往往只考慮流形上距離相近的數據點，這樣就會導致本來距離很遠的點映射后反而變成距離相近點的情形，因此應該有效地保持局部流形結構同時又保持全局流形結構，尋找出潛藏在高維數據空間中的低維流形結構，以此來提高算法的識別率。

ULDP是一種非監督的算法，該算法首先用流形距離構建全局方差圖和局部近鄰圖，然后用其表征全局結構和局部結構信息，最后求解在約束條件下的優化問題得到的特征向量，以此來表征嵌入在高維空間中的低維子流形。

ULDP算法不僅保持了局部近鄰數據點之間的內在聯系，還保證了相距較遠的數據點之間的非局部散度達到最大，因此該算法有效地實現了既保持數據的局部結構，又保持全局結構。

2.2 ULDP算法描述

其中，λi是上述特征方程的特征值；ωi是對應的特征向量。為了使目標函數最小，只需求解d個最小特征值對應的特征向量組成投影矩陣W=[ω1,ω2,…,ωd]。

3 多流形非監督線性差分投影

根據以上分析，ULDP算法在特征提取時能保持局部近鄰數據點之間的內在聯系，使得相距較遠的數據點之間的非局部散度達到最大。然而針對人臉識別中訓練樣本少的情況，ULDP算法的識別率會顯著下降，識別因此會變得無能為力。

3.1MULDP算法基本思想

將一幅人臉圖像分成t個小塊，此時就變成了很多幅小圖片xit，一張人臉圖像的t張小圖像分布在同一個流形上，就構成一個流形Mi=[xi1,xi2,…,xit]。很多個人的流形，那就是多流形（multi-manifold），用M=[M1,M2,…,MN]表示。現在要對一個由很多個小圖像塊組成的流形Mi=[xi1,xi2,…,xit]進行降維。其中每個圖像塊xir∈Rd,1≤i≤N,1≤r≤t是d維的，多流形判別分析算法的目標就是尋找一個降維矩陣Wi,i=1,2,…,N，將原始訓練樣本的維數降為di維，多流形算法簡化模型如圖1所示。

MULDP算法兼顧樣本全局結構與局部結構，結合了多流形，首先將樣本的局部嵌入和全局方差用多流形形式表示出來，然后在低維子空間最大化各個流形的全局方差，最小化流形內的局部嵌入。

3.2MULDP算法描述

根據前文所述，可得MULDP算法描述如下。

MULDP算法不僅保持局部近鄰數據點之間的內在聯系，還保證了相距較遠的數據點之間的非局部散度達到最大，實現既保持了數據的局部結構又保持了全局結構。為了避免小樣本問題，引入一個平衡參數α(0≤α<1)。

Fig.1 Simplified model of multi-manifold algorithm圖1 多流形算法簡化模型

其中，λi是上述特征方程的特征值;ωi是對應的特征向量。為了使目標函數最小，取前d個最小特征值對應的特征向量組成投影矩陣W=[ω1,ω2,…,ωd]。

3.3 分類

經過以上特征提取后，每一幅原始圖像都得到MULDP的投影矩陣Wi,i=1,2,…,N后，下面就需要對測試樣本進行處理，進而完成識別分類的目標，其具體步驟如下。

（1）求測試樣本的低維子空間表示

給出一個新的測試樣本T，首先將其分成t塊不重復并且不疊加的局部小塊，隨后把這些小塊建模為新的流形Mi=[xi1,xi2,…,xit]，很多個人的流形，那就是多流形，用M=[M1,M2,…,MN]表示。現在要對一個由很多個小圖像塊組成的流形Mi=[xi1,xi2,…,xit]進行降維，那么它到任意一個訓練樣本的距離為d(MT,Mi)。 yi=WiTMi=[yi1,yi2,…,yit]及 yT=WiTMT=[yT1, yT2,…,yTt]分別為流形Mi和MT通過Wi投影后的低維子空間表示。

（2）求測試樣本與訓練樣本之間的距離

對每個yT中的yTj,從yi中找出它的k個近鄰Gk(yTj)，用Gk(yTj)的加權平均去重組yTj，那么yTj到流形Mi的距離為：

其中，cs為近鄰對 yTj的重構系數，。所有的yTj的距離加起來求解平均就是MT到Mi的流形距離，即：

（3）分類

根據求出的N個測試樣本與訓練樣本之間的距離進行對比，找出其中最小的那個距離，這個最小距離如果是測試樣本與第i個訓練樣本之間的距離，那么就可以判定這個測試樣本是第i類樣本，即：

4 實驗及結果分析

為評估所提算法的性能，在ORL、Yale及AR數據庫上進行人臉識別實驗來驗證所提算法的有效性，主要采用識別率作為驗證指標。作為對比，同時還采用了其他典型算法如PCA、LDA、LLE、NPE、LPP、ULDP等進行實驗。在實驗中，由于人臉圖像維數較高，在運行以上算法時，首先采用PCA算法對人臉圖像進行降維預處理，接著采用各算法進行特征提取，最后采用最近鄰分類器進行識別。

4.1 參數α的選取和測試

MULDP算法的目的是求解出嵌入在高維空間的低維子流形，使得投影后不僅保持局部近鄰數據點之間的內在聯系，還保證相距較遠的數據點之間的距離達到最大。為避免出現小樣本問題，加入一個平衡參數α(0<α<1)，參數α的不同取值會產生不同的分類識別率，尤其當α取值不合適時，計算所得的分類無法正確反映樣本的分布信息，從而降低算法的識別性能。因此在原有分類概率計算式中引入參數α，不僅使得計算式更加靈活，而且可以通過調節α使得識別率在某種程度上得到進一步提高。設置α的值從0.1到0.9，間隔為0.1，在ORL、Yale和AR人臉數據庫上選取6個訓練樣本，MULDP的最大平均識別率隨α變化的情況如表1所示。

從表1中實驗結果可以看出，在ORL、Yale和AR庫上，α分別取0.5、0.4和0.6時，MULDP識別率分別為98.57、96.79和97.08，此時識別效果最好。鑒于該實驗結果，后續的3個實驗中，α分別取0.5、0.4和0.6進行實驗。

4.2 ORL人臉庫實驗

ORL人臉庫（http://www.cl.cam.ac.uk/research/dtg/ attarchive/facedatabase.html）包含40個人，其中每個人各擁有10幅分辨率為112×92的圖像。ORL庫中某人的10幅圖像如圖2所示。

Table 1 Recognition rates and corresponding dimensions of MULDP with differentαwhen training number is 6 on ORL,Yale andAR databases表1 ORL、Yale和AR庫上訓練樣本數為6時MULDP在α取不同值時的識別率及投影維數

Fig.2 10 images of one person on ORL database圖2 ORL庫中某人的10幅圖像

實驗中用于訓練的樣本是從ORL庫中隨機抽取的每人3、4、5、6幅圖像，其余的作為測試樣本。對于每一個不同的訓練樣本大小的實驗，為綜合對比，獨立運行50次。為便于比較，表2給出了在ORL人臉庫上不同算法的最大識別率以及對應的特征維數。不同算法的平均最大識別率隨訓練樣本的變化情況如圖3所示。

Fig.3 Recognition rates of MULDP and other algorithms with differentlon ORL database圖3 ORL庫上MULDP與其他算法在l取不同樣本數時的最大識別率對比

Table 2 Optimal recognition rates and corresponding dimensions of MULDP compared with other algorithms on ORL database表2 ORL庫上MULDP與其他算法最佳識別率及特征維數比較

4.3 Yale人臉庫實驗

Yale人臉庫（http://cvc.yale.edu/projects/yalefaces/ yalefaces.html）中包括15人，其中每個人各擁有11幅分辨率為100×80的圖像。Yale庫中某人的11幅圖像如圖4所示。

Fig.4 11 images of one person on Yale database圖4 Yale庫中某人的11幅圖像

實驗中用于訓練的樣本是從Yale庫中隨機抽取的每人2、3、4、5、6幅圖像，其余的作為測試樣本。對于每一個不同的訓練樣本大小的實驗，也獨立運行50次。表3給出了在Yale人臉庫上不同算法的最大識別率以及對應的特征維數。不同算法的平均最大識別率隨訓練樣本的變化情況如圖5所示。

Fig.5 Recognition rates of MULDP and other algorithms with differentlon Yale database圖5 Yale庫上MULDP與其他算法在l取不同樣本數時的最大識別率對比

4.4 AR人臉庫實驗

AR人臉庫（http://rvl1.ecn.purdue.edu/～aleix/aleix_ face_DB.html）中包括120人，其中每個人各擁有不同光照、表情、遮擋的26幅圖像，每人前后13幅圖像分別拍攝2個時期，時間間隔1個月。圖6是AR人臉庫中一個子類的20幅圖像，兩行圖像分別拍攝于不同的時期，前后相差兩個星期。

Table 3 Optimal recognition rates and corresponding dimensions of MULDP compared with other algorithms on Yale database表3 Yale庫上MULDP與其他算法最佳識別率及特征維數比較

Fig.6 20 images of one person from a subclass onAR database圖6 AR人臉庫中一個子類的20幅圖像

在實驗中，選擇AR數據庫的一個子集，包括前40個人，每個人10幅圖像。實驗中用于訓練的樣本是從AR庫中隨機抽取的每人2、3、4、5、6幅圖像，其余的作為測試樣本。表4給出了在AR人臉庫上不同算法的最大識別率以及對應的特征維數。不同算法的平均最大識別率隨訓練樣本的變化情況示意圖如圖7所示。

Table 4 Optimal recognition rates and corresponding dimensions of MULDP compared with other algorithms onAR database表4 AR庫上MULDP與其他算法最佳識別率及特征維數比較

Fig.7 Recognition rates of MULDP and other algorithms with differentlonAR database圖7 AR庫上MULDP與其他算法在l取不同樣本數時的最大識別率對比

4.5 實驗結果與分析

根據實驗結果，可得結論如下：

（1）表1顯示的是ORL、Yale和AR人臉庫上，當訓練樣本為6時，MULDP算法的最大平均識別率隨α的變化情況。從表1可以看出，參數α的選擇對MULDP算法的識別性能有一定影響，不同的α取值會產生不同的識別率。其中Yale數據庫測試樣本數最少，參數α為0.4時識別效果最好；AR數據庫測試樣本數最大，參數α為0.6時識別效果最好。究其原因，主要是由于樣本數少時，多流形最小局部散度JL(Wi)要大于多流形最大全局方差JG(Wi)，反之多流形最小局部散度JL(Wi)則小于多流形最大全局方差JG(Wi)。

（2）MULDP算法是在ULDP基礎上提出的，從表2、表3和表4中的實驗數據及結果可以看出，MULDP算法無論在ORL、Yale還是在AR人臉庫上，其識別率都比ULDP好，MULDP算法性能均要優于ULDP。這主要是由于MULDP算法將每幅圖像分成多幅小圖像，這些小圖像就構成一個流行，多幅圖像就構成了多流行，這就解決了ULDP算法存在的小樣本問題。

（3）從圖3、圖5和圖7中可以看出，隨著訓練樣本個數的增加，所有實驗算法的識別率均得到了進一步的提升。從整體上看，訓練樣本數由2增加到6的過程中，本文所提算法MULDP的識別率在所有算法中都是最高的，體現了該算法的鑒別性能優于其他算法。

（4）MULDP算法是在低維子空間最大化各個流形的全局方差，最小化流形內的局部嵌入，此算法結合多流形，并且兼顧樣本全局結構與局部結構，從而取得了較好的識別效果。

由上述實驗圖表可知，相較于其他算法，MULDP算法整體均取得了最好效果，這進一步驗證了算法的優越性。

5 結束語

針對ULDP算法在處理人臉識別問題時存在的缺陷，提出了多流形的非監督線性差分投影算法MULDP。MULDP結合了PCA與LLE兩種算法的優點，特征提取時同時保留了數據中的全局結構和局部結構，可以更好地提取人臉圖像數據間的鑒別信息，以此來提高算法的分類性能，使得本文算法更加魯棒。通過在ORL、Yale和AR人臉庫上的實驗驗證了本文算法的有效性及優越性。

從實驗結果可知，α的取值與MULDP算法的識別效果有一定聯系，目前如何選擇參數仍然是一個難題。因此在后續工作中，如何對α進行取值，使得算法具有穩定的性能并達到最優識別效果是今后需要重點研究的問題。

[1]Ma Xiaohu,Tan Yanqi.Face recognition based on discriminant sparsity preserving embedding[J].Acta Automatica Sinica,2014,40(1):73-82.

[2]Wan Minghua,Li Ming,Yang Guowei,et al.Feature extraction using two-dimensional maximum embedding difference [J].Information Sciences,2014,274:55-69.

[3]Nixon M,Aguado A S.Feature extraction and image processing[M].2nd ed.Orlando,USA:Academic Press,2008.

[4]Yang Xiaomin,Wu Wei,Qing Linbo,et al.Image feature extraction and matching technology[J].Optics and Precision Engineering,2009,17(9):2276-2282.

[5]Bartlett M S,Lades H M,Sejnowski T J.Face recognition by independent component analysis[J].IEEE Transactions on Neural Networks,2002,13(6):1450-1464.

[6]Turk M,Pentland A.Eigenfaces for recognition[J].Journal of Cognitive Neuroscience,1991,3(1):71-86.

[7]Yu Hua,Yang Jie.A direct LDA algorithm for high-dimensional data-with application to face recognition[J].Pattern Recognition,2001,34(10):2067-2070.

[8]Yang Jian,Zhang D,Frangi A F,et al.Two-dimensional PCA: a new approach to appearance-based face representation and recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(1):131-137.

[9]He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacianfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[10]Roweis S T,Saul L K.Nonlinear dimensional reduction by locally linear embedding[J].Science,2000,290(550):2323-2326.

[11]Ahonen T,HadidA,Pietikainen M.Face description with local binary patterns:application to face recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006,28(12):2037-2041.

[12]Zhang Baochang,Gao Yongsheng,Zhao Sanqiang,et al.Local derivative pattern versus local binary pattern:face recognition with high-order local pattern descriptor[J].IEEE Transactions on Image Processing,2010,19(2):533-544.

[13]Wolf L,Hassner T,Taigman Y.Effective unconstrained face recognition by combining multiple descriptors and learned background statistics[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2011,33(10):1978-1990.

[14]Lai Zhihui,Xu Yong,Chen Qingcai,et al.Multilinear sparse principal component analysis[J].IEEE Transactions on Neural Networks and Learning Systems,2014,25(10):1942-1950.

[15]Lai Zhihui,Xu Yong,Jin Zhong,et al.Human gait recognition via sparse discriminant projection learning[J].IEEE Transactions on Circuits and Systems for Video Technology, 2014,24(10):1651-1662.

[16]Wan Minghua,Lai Zhihui,Jin Zhong.Locally minimizing embedding and globally maximizing variance:unsupervised linear difference projection for dimensionality reduction[J].Neural Processing Letters,2011,33(3):267-282.

[17]Yang Jian,Zhang D,Yang Jingyu,et al.Globally maximizing, locally minimizing:unsupervised discriminant projection with applications to face and palm biometrics[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007,29(4):650-664.

附中文參考文獻：

[1]馬小虎,譚延琪.基于鑒別稀疏保持嵌入的人臉識別算法[J].自動化學報,2014,40(1):73-82.

YANG Zhangjing was born in 1979.He is a lecturer at School of Technology,Nanjing Audit University.His research interests include computer vision and pattern recognition,etc.

楊章靜（1979—），男，江蘇南京人，南京審計大學工學院講師，主要研究領域為計算機視覺，模式識別等。

WAN Minghua was born in 1978.He is an associate professor at School of Technology,Nanjing Audit University. His research interests include pattern recognition and intelligent computation,etc.

萬鳴華（1978—），男，江西南昌人，南京審計大學工學院副教授，主要研究領域為模式識別，智能計算等。

WANG Qiaoli was born in 1990.She is an M.S.candidate at School of Information Engineering,Nanchang Hangkong University.Her research interests include artificial intelligence and intelligent computation,etc.

王巧麗（1990—），女，山東菏澤人，南昌航空大學信息工程學院碩士研究生，主要研究領域為人工智能，智能計算等。

ZHANG Fanlong was born in 1985.He is a lecturer at School of Technology,Nanjing Audit University.His research interests include computer vision and pattern recognition,etc.

張凡龍（1985—），男，山東泰安人，南京審計大學工學院講師，主要研究領域為計算機視覺，模式識別等。

YANG Guowei was born in 1964.He is a professor at School of Technology,Nanjing Audit University.His research interests include pattern recognition and artificial intelligence,etc.

楊國為（1964—），男，江西南昌人，南京審計大學工學院教授，主要研究領域為模式識別，人工智能等。

Multi-Manifold Unsupervised Linear Differential ProjectionAlgorithm?

YANG Zhangjing1,WAN Minghua1,2,3+,WANG Qiaoli4,ZHANG Fanlong1,YANG Guowei1
1.School of Technology,NanjingAudit University,Nanjing 211815,China
2.Key Laboratory of Intelligent Perception and Systems for High-Dimensional Information of Ministry of Education,Nanjing University of Science and Technology,Nanjing 210094,China
3.Key Laboratory of Trusted Cloud Computing and Big Data Analysis,Nanjing Xiaozhuang University,Nanjing 211171,China
4.Key Laboratory of Jiangxi Province for Image Processing and Pattern Recognition,Nanchang Hangkong University,Nanchang 330063,China
+Corresponding author:E-mail:wmh36@nau.edu.cn

To overcome the drawbacks of existing unsupervised linear differential projection(ULDP),this paper proposes a novel algorithm called multi-manifold unsupervised linear differential projection(MULDP)for face recogni-tion.Firstly,multi-manifold local neighborhood graph and the largest global variance are constructed.Nextly,a lowdimensional manifold embedded in high-dimensional space is calculated through the multi-objective optimization.This mapping can represent not only the global structure but also the local structure.MULDP can get the low-dimensional manifolds embedded in a high-dimensional space and maintain the local and global structural information effectively. The experimental results on the ORL,Yale andAR face databases demonstrate the superiority of the proposed algorithm.

face recognition;feature extraction;multi-manifold;unsupervised linear differential projection(ULDP)

10.3778/j.issn.1673-9418.1604045

A

TP391.4

*The Natural Science Foundation of Jiangsu Higher Education Institutions under Grant Nos.15KJB520018,12KJA63001(江蘇省屬高校自然科學基金);the National Natural Science Foundation of China under Grant Nos.61503195,61462064,61203243,61272077 (國家自然科學基金);the Key Laboratory of Intelligent Perception and Systems for High-Dimensional Information of Ministry of Education(Nanjing University of Science and Technology)under Grant No.30920140122006(高維信息智能感知與系統教育部重點實驗室(南京理工大學)基金).

Received 2016-04,Accepted 2016-06.

CNKI網絡優先出版:2016-06-02,http://www.cnki.net/kcms/detail/11.5602.TP.20160602.1144.012.html