對(duì)ORL人臉數(shù)據(jù)庫識(shí)別過程中的參數(shù)選擇策略

馮加明

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

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

中圖分類號(hào)：TP183? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

本文使用的數(shù)據(jù)集為ORL人臉數(shù)據(jù)集。采用十次十折交叉實(shí)驗(yàn)求得平均正確率構(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的圖像，則將其展開儲(chǔ)存在一個(gè)a*（b*c）的二維矩陣X內(nèi)（見圖1）。

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

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

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

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

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

1.2 KNN（k近鄰法）[8]

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

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

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

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

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

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

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

2 基于PCA與KNN的人臉識(shí)別實(shí)驗(yàn)

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

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

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

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

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

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

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

⑴ PCA中選取的特征值個(gè)數(shù)N參與以下兩個(gè)過程：創(chuàng)建數(shù)組以及計(jì)數(shù)循環(huán)?？芍绦蜿P(guān)于N的時(shí)間復(fù)雜度為O（N）。

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

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

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

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

2.4 圖搜索的過程

首先，確定一個(gè)搜索起始點(diǎn)，那么對(duì)于這個(gè)點(diǎn)，其搜索方向見圖6。

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

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

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

2.5 結(jié)果分析

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

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

3 結(jié)論

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

要進(jìn)一步提高策略的有效性，可以通過選取其他的搜索算法來實(shí)驗(yàn)。所以后續(xù)的研究可以圍繞不同搜索算法對(duì)參數(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的人臉識(shí)別研究[J].電腦知識(shí)與技術(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