對ORL人臉數據庫識別過程中的參數選擇策略

馮加明

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

關鍵詞： 人臉識別; PCA; KNN; 圖搜索

中圖分類號：TP183? ? ? ? ? 文獻標識碼：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上首次發表了一篇關于人臉識別的報告[1]，開創了人臉識別研究的先河。1965年至1990年，人臉識別的主要方法是基于幾何結構特征和模板匹配。1991年，麻省理工學院的Turk等人提出了一種”特征臉Eigenface”[2]，被稱為后來其他大多數人臉識別算法的基準。1992年，Brunelli等人的實驗結果表明基于模板匹配的方法一般優于基于幾何特征的方法[3]。1997年，Belhumeur等人提出了Fisherface[4]，一種基于子空間分析的人臉識別算法。二十一世紀出現了許多對局部領域圖像進行手工特征提取的方法，例如對人臉比較有效的基于無監督學習的特征LeamingDescriptors[5]與GaborFace、LBPFace[6]等。

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

1 相關技術

1.1 PCA主成分分析

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

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

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

⑵ 將X的每一行的每個值減去該行的平均值。這兩步統稱數據標準化。

⑶ 求出協方差矩陣C：

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

⑸ 按降序對特征值進行排序并選擇前N個特征向量。

⑹ 利用選擇出的特征向量轉換原始數據集，得到N維特征子空間。

1.2 KNN（k近鄰法）[8]

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

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

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

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

1.3 GBFS貪婪最佳優先算法[9]

GBFS的搜索策略與深度優先搜索（DFS）和廣度優先搜索（BFS）并沒有本質上的區別。但GBFS引入了“優先隊列”的數據結構概念。在GBFS的節點刪除中使用代價函數h（p）來作為判斷節點優先級的標準。在本文中，其含義為從原點到點p所需的代價。

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

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

2.1 數據來源

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

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

2.2 Python實現流程（如圖4）

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

2.3 h（p）函數的選取

由于本文的主旨是尋求時間復雜度與準確率之間的平衡點，所以分別對PCA與KNN的時間復雜度進行分析。

⑴ PCA中選取的特征值個數N參與以下兩個過程：創建數組以及計數循環。可知程序關于N的時間復雜度為O（N）。

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

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

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

其中e為一個常數，用于將h（p）的值調整至0到1的范圍內。

2.4 圖搜索的過程

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

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

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

最終得到搜索結果，如圖7所示。

2.5 結果分析

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

最優點選取的特征向量個數N較少，而KNN中的K值卻偏大。其原因是N影響時間復雜度的程度更大，而K值影響正確率的程度更大。所以在人臉識別的過程中，可以適當地降低N，適當地提高K，在保證正確率的同時降低花費的時間。

3 結論

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

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

參考文獻（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].電腦知識與技術，2019（3）：209-211

[8] 平原2018.機器學習之KNN（k近鄰）算法詳解.CSDN，2018-07-03

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

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