馮加明

摘? 要： 對ORL人臉數(shù)據(jù)庫的識別大致分為兩步驟：使用PCA對訓(xùn)練集降維提取特征向量和使用KNN對樣本集進(jìn)行分類。在該過程中，有兩個參數(shù)直接影響著人臉識別的準(zhǔn)確率：PCA選取的特征向量數(shù)目n和KNN中的k值。如果對它們的選取沒有一個良好的策略，就會出現(xiàn)正確率太低、時間復(fù)雜度太高、過擬合等問題。文章采用狀態(tài)空間搜索找到準(zhǔn)確率與時間復(fù)雜度中的平衡點，得到了有效的搜索結(jié)果。

關(guān)鍵詞： 人臉識別; PCA; KNN; 圖搜索

中圖分類號：TP183? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2021）02-27-04

Parameter selection strategy for recognition of ORL face database

Feng Jiaming

（Dalian Maritime University， DaLian， LiaoNing 116026， China）

Abstract： The recognition of ORL face database is roughly divided into two parts： using PCA to reduce the dimension of the training set， extracting feature vectors， and using KNN to classify the sample set. In the processes， two parameters directly affect the accuracy of face recognition： the number of feature vectors n selected by PCA and the K value in KNN. If there is no good strategy for their selection， there will be problems such as low accuracy， high time complexity， over fitting and so on. This paper uses state space search to find the balance between accuracy and time complexity， and effective search results has been obtained.

Key words： face recognition; PCA; KNN; graph search

0 引言

人臉識別是模式識別圖像處理中一個重要的方向。1965年，Bledose等人在PanoramicResearchInc上首次發(fā)表了一篇關(guān)于人臉識別的報告[1]，開創(chuàng)了人臉識別研究的先河。1965年至1990年，人臉識別的主要方法是基于幾何結(jié)構(gòu)特征和模板匹配。1991年，麻省理工學(xué)院的Turk等人提出了一種”特征臉Eigenface”[2]，被稱為后來其他大多數(shù)人臉識別算法的基準(zhǔn)。1992年，Brunelli等人的實驗結(jié)果表明基于模板匹配的方法一般優(yōu)于基于幾何特征的方法[3]。1997年，Belhumeur等人提出了Fisherface[4]，一種基于子空間分析的人臉識別算法。二十一世紀(jì)出現(xiàn)了許多對局部領(lǐng)域圖像進(jìn)行手工特征提取的方法，例如對人臉比較有效的基于無監(jiān)督學(xué)習(xí)的特征LeamingDescriptors[5]與GaborFace、LBPFace[6]等。

本文使用的數(shù)據(jù)集為ORL人臉數(shù)據(jù)集。采用十次十折交叉實驗求得平均正確率構(gòu)造K-N-正確率矩陣并繪制三維圖像。

1 相關(guān)技術(shù)

1.1 PCA主成分分析

PCA本質(zhì)上是一種線性降維的方法[7]。

PCA的主要思想是將原本的高維特征映射到低維度上，即全新的正交特征，亦稱主成分。PCA的工作就是從原始的空間中順序地找一組相互正交的坐標(biāo)軸，新的坐標(biāo)軸的選擇與數(shù)據(jù)本身是密切相關(guān)的。利用正交變換作為映射矩陣，其具體步驟如下。

⑴ 假設(shè)一共有a張b*c的圖像，則將其展開儲存在一個a*（b*c）的二維矩陣X內(nèi)（見圖1）。

⑵ 將X的每一行的每個值減去該行的平均值。這兩步統(tǒng)稱數(shù)據(jù)標(biāo)準(zhǔn)化。

⑶ 求出協(xié)方差矩陣C：

⑷ 使用pythonnumpy庫中的linalg.eig函數(shù)對協(xié)方差矩陣C進(jìn)行奇異向量分解，求出其特征值矩陣和特征向量。由于本文是對ORL人臉數(shù)據(jù)庫的分析，所以求出的特征值可以展開為特征臉，用于構(gòu)造判別空間的基向量（見圖2）。

⑸ 按降序?qū)μ卣髦颠M(jìn)行排序并選擇前N個特征向量。

⑹ 利用選擇出的特征向量轉(zhuǎn)換原始數(shù)據(jù)集，得到N維特征子空間。

1.2 KNN（k近鄰法）[8]

KNN（k-Nearest Neighbors）是一種分類算法，最初由Cover和 Hart 在1968年提出。其應(yīng)用場景較為廣泛，包括文字匹配，圖像識別，文本分類等。

該方法的核心思路為：在與測試集樣本中按某種距離（此處為歐氏距離）最相似的K個點中，屬于某一類的點最多，則該測試集樣本也屬于這個類別。

歐式距離在本文問題中的變形：

其中S表示的是第i個訓(xùn)練集樣本T和第j個測試集樣本t之間的歐氏距離。N為PCA中選取的特征數(shù)量。

1.3 GBFS貪婪最佳優(yōu)先算法[9]

GBFS的搜索策略與深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）并沒有本質(zhì)上的區(qū)別。但GBFS引入了“優(yōu)先隊列”的數(shù)據(jù)結(jié)構(gòu)概念。在GBFS的節(jié)點刪除中使用代價函數(shù)h（p）來作為判斷節(jié)點優(yōu)先級的標(biāo)準(zhǔn)。在本文中，其含義為從原點到點p所需的代價。

GBFS也有一定的缺點：當(dāng)遇到局部搜索障礙的時候，GBFS無法找到最優(yōu)路徑甚至最終無法找到最優(yōu)解。所以在本次實驗中將選取多個搜索起始點以減小該因素帶來的不利影響。

2 基于PCA與KNN的人臉識別實驗

2.1 數(shù)據(jù)來源

ORL人臉數(shù)據(jù)集為40組每組10張共400張112*92的黑白灰度色值圖像（見圖3）。在1992年4月至1994年4月期間由英國劍橋的Olivetti研究實驗室創(chuàng)建。

每一個類別的人臉圖像，都是在不同的情況下采集的。所有的圖像都是在較暗的均勻背景下拍攝的正臉或有輕微偏移的圖像[10]。

2.2 Python實現(xiàn)流程（如圖4）

求得的正確率（TP）隨著K-N變化的矩陣三維圖如圖5所示。

2.3 h（p）函數(shù)的選取

由于本文的主旨是尋求時間復(fù)雜度與準(zhǔn)確率之間的平衡點，所以分別對PCA與KNN的時間復(fù)雜度進(jìn)行分析。

⑴ PCA中選取的特征值個數(shù)N參與以下兩個過程：創(chuàng)建數(shù)組以及計數(shù)循環(huán)。可知程序關(guān)于N的時間復(fù)雜度為O（N）。

⑵ 而KNN的時間復(fù)雜度同時依賴于樣本的特征維度與K值的選擇，所以最終求得KNN的時間復(fù)雜度為O（N*K）[11]。

主程序中，PCA與KNN是兩個完全獨立的過程，所以，程序的總時間復(fù)雜度為二者的累加，即

h（p）=TP-e（N+N*K）

其中e為一個常數(shù)，用于將h（p）的值調(diào)整至0到1的范圍內(nèi)。

2.4 圖搜索的過程

首先，確定一個搜索起始點，那么對于這個點，其搜索方向見圖6。

為了降低GBFS受到局部最優(yōu)陷阱的影響，本文采用橫坐標(biāo)從0到20步長為2，縱坐標(biāo)0到200步長為20的11個起始點進(jìn)行多次搜索。程序判斷下一搜索方向的點的h（p）值是否大于當(dāng)前搜索點，并選擇其最大點替換。

搜索邊界為：當(dāng)搜索點周圍不存在比搜索點h（p）值更高的點時，或者搜索到矩陣邊界的時候停止，返回該搜索點。

最終得到搜索結(jié)果，如圖7所示。

2.5 結(jié)果分析

從圖7可以看出，在11個起始點中，數(shù)目最多的搜索結(jié)果是[3，320]，故確定在該h（p）函數(shù)下的最優(yōu)結(jié)果為[3，320]。

最優(yōu)點選取的特征向量個數(shù)N較少，而KNN中的K值卻偏大。其原因是N影響時間復(fù)雜度的程度更大，而K值影響正確率的程度更大。所以在人臉識別的過程中，可以適當(dāng)?shù)亟档蚇，適當(dāng)?shù)靥岣逰，在保證正確率的同時降低花費的時間。

3 結(jié)論

本文對ORL人臉數(shù)據(jù)庫進(jìn)行了分類處理，并綜合正確率矩陣與時間復(fù)雜度得到了較為有效的參數(shù)選取策略。

要進(jìn)一步提高策略的有效性，可以通過選取其他的搜索算法來實驗。所以后續(xù)的研究可以圍繞不同搜索算法對參數(shù)選取策略的影響來研究。

參考文獻(xiàn)（References）：

[1] BledsoeW W.Man-machine facial recognition[J]. Rep. PRI，1966，22

[2] Turk M， Pentland A. Eigenfaces for recognition[J].Journalof cognitive neuro science，1991，3（1）：71-86

[3] Brunelli R， PoggioT. Face recognition： features versustemplates[J]. IEEE transactions on pattem analysis and machine intelligence，1993，15（10）：1042-1052

[4] Belhumeur P N， Hespanha J P， Kriegman D J.Eigenfacesvs. fisherfaces： Recognition using class specific linear projection[J].IEEE Transaction sonpattem analysis and machine intelligence，1997，19（7）：711-720

[5] Winder S A J， Brown M， Learning Local? Image Descriptors[C]//Computer Visionand Pattem Recognition，2007.CVPR'07.IEEE Conferenceon.IEEE，2007：1-8

[6] Chen D.CaoX，WenF，etal.Blessing of dimensionality： High-dimensional feature and its efficient compression for face verification[C]//Proceedings of the IEEE Conferenceon Computer Vision and Pattern Recognition，2013：3025-3032

[7] 付氐，陳中舉，杜友福.基于PCA和SVM的人臉識別研究[J].電腦知識與技術(shù)，2019（3）：209-211

[8] 平原2018.機(jī)器學(xué)習(xí)之KNN（k近鄰）算法詳解.CSDN，2018-07-03

[9] 鬼木士.路徑規(guī)劃|圖搜索算法：DFS、BFS、GBFS、Dijkstra、A*.知乎，2021.2.2

[10] fengbingchun. ORL Faces Database介紹.CSDN，2018-01-09