改進的ISOMAP 算法在人臉識別中的應用

郭海鳳，陳月霞，孫周寶

(1.金陵科技學院信息技術學院，江蘇 南京 211169;2.河海大學計算機與信息學院，江蘇 南京 210098)

0 引言

隨著互聯(lián)網技術的飛速發(fā)展，其蘊含的圖片數量呈爆炸式的增長，而絕大部分的圖像沒有任何的標簽類別信息，而且圖像檢索所面臨的主要難題是“語義鴻溝”，即低層圖像特征與高層用戶語義間的巨大差異，從而使得圖像檢索的效果很難讓用戶滿意。目前圖像檢索的方法主要是基于內容的圖像檢索。

在圖像檢索過程中，一幅大小為64 ×64 的人臉圖像在空間中需要用4096 維的向量進行表示，顯而易見的是這個向量太大，導致任何算法在處理時都非常困難，為了避免維數災難問題，需要對圖像進行降維處理。傳統(tǒng)的降維方法包括主成分分析(PCA)［1］、獨立分量分析(ICA)［2］以及多尺度變化(MDS)［3］等，從幾何學角度來看，這些線性的降維方法首先都假設數據具有全局的線性結構，而人臉圖像的集合可以看作是以位置、姿態(tài)、光照等為參數的一個高維數據空間，當人臉在表情和姿態(tài)有變化的時候會帶來很多非線性變形，其相應的特征變化可看作嵌入在高維人臉圖像空間中的一個低維非線性子流形，這時傳統(tǒng)的降維方法則無法揭示非線性高維數據的內在本質結構。流形是一種非歐幾何空間，用已知的局部逼近未知的全局幾何結構，目的是在流形空間結構下挖掘非線性高維數據的內在結構及規(guī)律。所以流形學習技術能夠真正地揭示人臉圖像空間的內在低維結構，可以有效地用來對人臉圖像進行識別。目前，應用比較廣泛的流形學習方法包括ISOMAP(Isometric Mapping)［4-5］、LLE (Locally Linear Embedding)［6-14］以及LE(Laplacian Eigenmap)［15］等。相比傳統(tǒng)的降維方法，流形學習方法具有很多優(yōu)勢:參數較少，只有近鄰參數k 及內在維數估計參數d;其次是計算性能對數據的非線性流形結構具有一定的自適應性。

人臉圖像的識別主要包括特征提取和人臉識別2 部分。

1)特征提取主要是抽取出具有最大像素分類特征的像素點，從而降低人臉識別過程的復雜度;

2)人臉識別主要是利用提取的特征及人臉信息進行比較，采用分類算法進行分類，達到識別的目的。

本文結合特征提取算法SIFT［16-17］及改進的流形學習方法ISOMAP，在ORL 標準人臉數據集上進行人臉識別實驗。利用SIFT 算法提取人臉圖像的局部描述子，在獲取每張人臉圖像的128 維高維特征向量后，使用改進的ISOMAP 算法進行降維，并使用最近鄰分類器分類。本文在使用ISOMAP 算法過程中，主要分析探討近鄰參數以及內在本征維數的大小對人臉圖像識別效果的問題。

1 SIFT 與ISOMAP 算法

1.1 SIFT 概述

SIFT 特征是哥倫比亞大學的David Lower 于1999 年提出的局部特征描述子，2004 年David Lower又對SIFT 進行更深層次的研究和擴展，SIFT 分辨力強，信息量大，具有很好的仿射不變性。SIFT 基本思想是通過高斯核進行濾波提取圖像的尺度空間中的穩(wěn)定點。這種方式獲得的特征點具有旋轉、縮放、平移和部分仿射不變性，進一步將特征向量的長度歸一化。SIFT 特征提取算法用于人臉識別時，相似的人臉的SIFT 特征是比較接近的，不相似的人臉其特征則差別較大。SIFT 特征是圖像的局部特征，描述的是圖像關鍵區(qū)域的梯度直方圖分布情況，SIFT 算法的實質是從人臉圖像中提取SIFT 關鍵點(keypoints)的過程，算法包括4 個主要的步驟:

1)尺度空間的構建與極值檢測;

2)特征點精確定位;

3)特征點主方向確定;

4)SIFT 描述子生成。

具體過程參見文獻［7-8］。針對ORL 人臉圖像中最后一個人的數據集，使用SIFT 算法，在其中2 張圖像上生成的關鍵點和描述子及匹配情況如圖1 所示。

圖1 關鍵點及匹配情況

1.2 ISOMAP 算法

ISOMAP 算法是利用局部近鄰距離對全局流形測地線距離進行估計，通過建立原數據的測地距離與降維數據空間距離的對等關系，實現數據降維。ISOMAP 算法可以挖掘出高維數據本質對應的低維嵌入結構，主要是因為其使用的測地距離能夠內在地反映數據的本質流形幾何特征。算法主要步驟如下:

1)運用ε-鄰域或k 近鄰方法對原始數據構建近鄰圖G;

2)計算任意節(jié)點對在近鄰圖G 中的最短路徑，用來逼近相應的測地距離;

3)將步驟2)中獲得的測地距離矩陣作為輸入，應用MDS 算法計算數據的低維空間表示，將數據映射到低維可視空間中。

對于給定的人臉數據集，通過使用SIFT 特征提取算法獲得高維的人臉特征向量后，ISOMAP 能否成功地降維取決于鄰域大小k 的選擇，以及人臉圖像的內在維數d 的估計是否合適，因為只有合適的k 才可以保證對測地距離的計算及逼近，如果k 過大，則可能嚴重破壞原始流形的連通性;如果k 過小，則可能導致流形結構被劃分成許多包含“孔洞”的不連通區(qū)域。在近鄰因子k 的大小選取時，為了自適應確定最優(yōu)鄰域參數k，在可以有效保持拓撲結構不變的前提下，對于給定的鄰域因子的范圍k1，k2，…，ki，…，kn，計算每個 ki的映射損失函數 L (ki)=‖τ(DG)-τ(DY)‖2，取最小的L(ki)所對應的k 組成初始候選集合Z，對每個k∈Z，使用改進后的LLE算法并計算相應的誤差，誤差標準采用公式(1):

在內在維數d 的估計過程中，如果d 過小，則高維空間中的點在映射到低維空間中會有重疊等現象，從而導致數據不能正確識別;相反，則可能包含噪聲數據在內的多余信息，為后續(xù)的識別造成不可估計的影響。本文采用向量的重構殘差(1 -，其中ρ為測地距離矩陣DX(K)和低維空間中的歐式距離矩陣D(Y)的相關系數)以及最大似然估計2 種方法來估計內在維數的大小。通過建立近鄰間距離的似然函數，得到本征維數的極大似然函數，從而得到最后的極大似然估計值。對人臉空間中的樣本隨機采樣X1，X2，…，Xn，構造泊松分布:

對于給定的鄰域k，則點xi的內在維數最大似然估計為:

采用極大似然估計法對式(2)中的x 進行遍歷，可得到n 個局部本征維數的估計值，然后取其平均值作為內在的嵌入維數，即:。最大似然估計法從人臉數據的局部結構性質出發(fā)，通過一定的描述方式來估計本征維數，并采用概率統(tǒng)計方法，可較好地估計數據的內在維數，計算速度也較快。

2 實驗結果與分析

本文在ORL 人臉數據集上進行實驗分析。該數據庫共包含40 個人的400 張人臉圖像，每人平均10張圖像，尺寸為92 ×112 像素。這些人臉圖像經過了中心化和標準化，由于該數據集不涉及到光照，所以人臉圖像的變化主要是姿態(tài)和表情，圖2 為數據集中某個人的人臉圖像。因為不同的訓練樣本數對識別的結果有著重要的影響，所以本實驗采用隨機選取每個人10 張中的5 張作為訓練樣本，剩余5 張圖像作為測試集。實驗中，選擇使用簡單方便的最近鄰分類器來判別特征提取算法的分類效果。實驗環(huán)境為128 核的CPU，63 G 內存，實驗平臺為Matlab 7.1。

圖2 部分ORL 人臉圖像

2.1 特征提取

針對ORL 人臉圖像數據集，本文首先通過SIFT算法對人臉圖像進行特征提取。對于獲得的128 維特征向量，使用流形學習中的等距映射算法ISOMAP進行降維，在200 張人臉測試數據集上進行測試，并且將該算法與直接使用ISOMAP 算法得到的結果進行比較，在降維過程中，嵌入的維數和近鄰參數默認為10，測試結果如表1 所示。

表1 ORL 人臉數據集上2 種算法比較

由表1 可以看出，在嵌入維數與構建近鄰圖時近鄰參數設置相同的情況下，基于SIFT 算法提取的特征在使用ISOMAP 算法后具有更高的識別率，因為SIFT 算法在對人臉圖像特征提取時，其仿射不變性發(fā)揮了重要的作用，可以有效提取描述人臉圖像的關鍵點。

在相同的近鄰參數及嵌入維數情況下，訓練樣本的個數不同對識別率有著一定的影響。對于2 種方法，實驗中分別選取3 個、4 個、5 個、6 個、7 個、8 個樣本作為訓練集，剩余的7 個、6 個、5 個、4 個、3 個、2個作為測試樣本，并且每次實驗重復10 次取平均值作為識別結果，此時的近鄰參數及嵌入維數仍設置為10，實驗結果如圖3 所示。

圖3 識別率與訓練樣本數關系

2.2 近鄰參數的選擇

ISOMAP 算法是建立在局部線性假設的基礎上，在計算低維流形結構時，其成功與否的關鍵在很大程度上取決于近鄰參數的選擇。在確定一個樣本點線性近鄰時通常包括2 個方面:測度距離和近鄰參數的大小選擇。在上述實驗中，選擇近鄰參數為10，圖4則為不同的近鄰參數值對人臉圖像數據的識別率的影響。

圖4 識別率與近鄰數關系

由圖4 可知，近鄰參數的大小選擇對嵌入的結果有著很大影響。在固定嵌入維數(取值為10)時，算法在近鄰值為5 時取得較好的識別效果。

2.3 嵌入維數的選擇

樣本數據的本征維數是嵌入在高位空間中低維流形的維數，本征維數的大小對低維空間的嵌入結果有著巨大的影響。因此，在流形降維的過程中需要解決高維數據的本征維數及嵌入到低維空間的維數的估計問題。在ORL 人臉圖像上，本實驗采用向量重構殘差以及最大似然估計2 種方法進行維數的估計，實驗結果如圖5 所示。

圖5 識別率、殘差與嵌入維數關系

圖5 對應的實驗測試了該算法的識別率與嵌入維數、殘差與嵌入維數的關系。本實驗中固定近鄰參數值設置為10。由圖5(a)可知，在保持近鄰數不變的情況下，隨著嵌入維數的增加，識別率會逐步上升，但最后會趨于一個極限值附近，而ORL 人臉數據集在嵌入維數為10 時即可達到一個較高的識別率，圖5(b)反映了嵌入維數估計時殘差與維數之間的關系，可見ORL 人臉數據庫的本征維數遠比Swiss Roll或Yale 人臉數據集復雜，因為它包含了40 個人的不同姿態(tài)和表情人臉，這些與人們對人臉圖像的理解也是一致的。

3 結束語

本文結合SIFT 特征提取算法與流形學習算法ISOMAP，在ORL 人臉圖像數據集上進行圖像檢索實驗。由實驗可知，基于SIFT 算法提取的特征在使用ISOMAP 降維后具有更好的識別效果。在降維過程中，針對ISOMAP 算法依賴于近鄰參數k 以及內在維數d 的大小難以選取的問題，本文使用最小殘差及最大似然估計的方法來估計和選擇近鄰參數及內在維數的大小。由實驗還可知，合適的近鄰參數及內在維數對識別效果有著巨大的影響。

［1］Jolliffe I.Principal Component Analysis［M］.2nd ed.New York:Springer Verlag，2002.

［2］Comon Pierre.Independent component analysis:A new concept?［J］.Signal Processing，1994，36(3):287-314.

［3］Cox T F，Cox M A A.Multidimensional Scaling［M］.2nd ed.Chapman and Hall/CRC，2000.

［4］Tenenbaum J B，Silva V D，Langford J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290(5500):2319-2323.

［5］Tenenbaum J B.Mapping a manifold of perceptual observations［C］// Advances in Neural Information Processing Systems.1998，10:682-688.

［6］Wen Guihua，Jiang Lijun，Wen Jun.Kernel relative transformation with applications to enhancing locally linear embedding［C］// Proceedings of the International Joint Conference on Neural Networks.2008:3401-3406

［7］Roweis S T，Saul L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2001，2909(5500):2323-2326.

［8］Wang Heyong，Zheng Jie，Yao Zhengan，et al.Improved locally linear embedding through new distance computing［C］// Advances in Neural Networks.2006:1326-1333.

［9］Chang H，Yeung D.Robust locally linear embedding［J］.Pattern Recognition，2006，39(6):1053-1065.

［10］Valencia-Aguirre J，álvarez-Mesa A，Daza-Santacoloma G，et al.Automatic choice of the number of nearest neighbors in locally linear embedding［C］// Progress in Pattern Recognition，Image Analysis，Computer Vision，and Applications.2009:77-84.

［11］Eftekhari A，Abrishami-Moghaddam H，Babaie-Zadeh M.k/K-Nearest neighborhood criterion for improvement of locally linear embedding［C］// Computer Analysis of Images and Patterns.2009:808-815.

［12］Goldberg Y，Ritov Y.LDR-LLE:LLE with low-dimensional neighborhood representation［C］// Advances in Visual Computing.2008:43-54.

［13］Zhang Shiqing.Enhanced supervised locally linear embedding［J］.Pattern Recognition Letters，2009，30(13):1208-1218.

［14］Hou Chenqing，Zhang Changhui，Wu Yi，et al.Stable local dimensionality reduction approaches［J］.Pattern Recognition，2009，42(9):2054-2066.

［15］Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003，15(6):1373-1396.

［16］Lowe D G.Object recognition from local scale-invariant features［C］// Proceeding of IEEE International Conference on Computer Vision.1999，2:1150-1157.

［17］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.