摘要：在人臉識別過程中，從檢測到辨認往往需要進行大量的數(shù)據(jù)運算和存儲，為有效利用硬件資源，通過分析遺傳算法的理念并引入到人臉識別過程中，利用遺傳特性尋找最相近的人臉特征，與目前常見方法進行性能對比，證明了遺傳算法在不降低準(zhǔn)確率的前提可以大幅減少運算時間。

關(guān)鍵詞：人臉識別；遺傳算法

中圖分類號：TP18 文獻標(biāo)識碼：A 文章編號：1009-3044（2013）12-2857-03

人臉識別技術(shù)以其非接觸采集特性和良好的用戶體驗成為生物識別領(lǐng)域一個重要分支。尤其自上世紀90年代以來，研究該領(lǐng)域的各國學(xué)者針對不同的用戶環(huán)境開發(fā)出很多識別技術(shù)[1]，如基于幾何特征的方法，基于模板匹配的方法，基于代數(shù)特征的方法，基于神經(jīng)網(wǎng)絡(luò)的方法，基于支持向量機的方法等等。這些方法中采用頻率較高的特征提取技術(shù)有主成分分析（PCA）[2]、小波分析（Gabor變換、Mallat算法）、線性判別分析（LDA）[3]等，在這些基礎(chǔ)方法上還發(fā)展出來了KPCA[4]、二維Gabor小波變換、FSLDA以及多種技術(shù)的組合等眾多方法，近幾年還出現(xiàn)了三維人臉建模技術(shù)[5]。無論哪種方法都需要高效的計算和存儲平臺作硬件支撐。

如果能夠在保證識別效果的基礎(chǔ)上有效降低存儲和計算量，使這一技術(shù)推廣到常見的便攜移動設(shè)備上，如利用智能手機進行銀行轉(zhuǎn)帳時，使用SIM+人臉鑒定的雙重保險，將會給人們帶來更加安全便捷的數(shù)字化服務(wù)。為與人臉識別過程相結(jié)合，在分析了遺傳算法的基本過程和要素后，給出遺傳算法在應(yīng)用于人臉識別時的一種適應(yīng)度評價方式和三個重要算子，通過實驗分析，證實此方法效果明顯。

1 基于遺傳算法（GA）的人臉特征提取

遺傳算法是Holland教授[6]于1975年提出的一種模擬生物體進化的抽象算法，具有“生成+檢測”的特性。它利用編碼空間代替問題參數(shù)空間，以適應(yīng)函數(shù)作為評價依據(jù)，以編碼群體為進化基礎(chǔ)，并對群體中的個體進行遺傳操作來實現(xiàn)選擇和遺傳機制，形成循環(huán)迭代，由群體中個體的不斷進化逐漸接近問題的最優(yōu)解。遺傳算法的整個進化過程操作是隨機的，但它所顯現(xiàn)的特性并非完全隨機，它在搜索過程中它能有效利用歷史信息推測下一代，得到期望性能有所提高的尋優(yōu)點集。

一般的遺傳算法包含五大要素[7]：

1）參數(shù)編碼（二進制編碼、序列編碼、樹編碼、自適應(yīng)編碼、大字符集等）；

2）初始群體的敲定；

3）適應(yīng)度函數(shù)的設(shè)計；

4）遺傳操作的設(shè)計（遺傳算子：選擇、交叉、變異）；

5）控制參數(shù)的設(shè)定。

其中遺傳算子的作用就是模擬生物系統(tǒng)中“適者生存”，淘汰不能適應(yīng)的染色體，把更有益的信息遺傳到子代。

在生物模擬系統(tǒng)中，DNA由遺傳的染色體構(gòu)成，染色體在遺傳算法中表示為比特序列。其中每個染色體用n位來表示。在執(zhí)行遺傳算法的第一步就是對各類中的每個個體進行編碼，即編排單個個體的比特序列。在這里，對染色體的編碼是通過獲取個體的十進制值后轉(zhuǎn)化為二進制編碼來實現(xiàn)的，它是由0和1組成的序列。例如，對于已知的單個個體由8位（n=8）來表示時，則它的染色體為：X=x8， x7， x6， x5， x4， x3， x2， x1。

對群體中個體的染色體進行操作的三個算子：選擇、交叉、變異。

選擇算子，作用就是選擇適應(yīng)值較好的個體以生成交配池。這里采用輪盤賭（roulette whell）的方法來實現(xiàn)，以保證每個父代都有同等的概率Ps被選擇。

交叉算子，在GA中模仿了自然界有性繁殖的基因重組過程，目的是將原有的優(yōu)良基因遺傳給子代。交叉操作一般分為三步：

從交配池中隨機抽取出一對要交配的個體。

根據(jù)位串長度L，對要交配的一對個體進行長度[1，L-1]的位置交叉；

根據(jù)設(shè)定的交叉概率Pc（0 < Pc ≤ 1）實施交叉操作。從而生成一對新的個體。這里實驗采用單點交叉的方式，設(shè)定Pc=0.6。

設(shè)在交配池中隨機抽取一對個體：S1=a1，a2，a3，...，aL，S2=b1，b2，b3，...，bL，隨機抽取交叉位x∈{1，2，...，L-1}，此處以L=5，X=3為例對兩個個體右側(cè)部分染色體位串進行交換，得到兩個新個體S1’= a1，a2， b3，b4，b5，S2’=b1，b2， a3，a4，a5 。

變異算子，模擬的是自然界生物體進化中染色體某位基因發(fā)生突變的現(xiàn)象。在GA中，通過設(shè)定變異概率Pm隨機反轉(zhuǎn)某位的二進制字符值來實現(xiàn)。即，產(chǎn)生一個隨機數(shù)P，若P

GA（后面提及的GA都是限定遺傳算法在人臉識別中的應(yīng)用）工作流程如下：

迭代開始： [t=0]

初始化： [P（0）={a（0）1，a（0）2，...，a（0）n}]

適應(yīng)性評價：[P0={f（a（0）1），f（a（0）2），...，f（a（0）n）}]

do {

選擇： [P'（t）=s（P（t），Ps）]

交叉： [P''（t）=c（P'（t），Pc）]

變異： [P'''（t）=m（P''（t），Pm）]

生成新一代： [P（t+1）=P'''（t），t=t+1]

適應(yīng)性評價： [P（t+1）={f（a（t+1）1），f（a（t+1）2），...，f（a（t+1）n）}]

} while（ [T（P（t））=true]）

2 應(yīng)用示例

設(shè)有L類樣本，定義：

訓(xùn)練集X={X1，X2，X3，...XL}

第i個類的子集Xi={x1（i）， x2（i），...， xNi（i）}

其中x1（i）， x2（i）為i類的第1和第2個訓(xùn)練樣本個體（圖像），Ni為第i類樣本的訓(xùn)練樣本總數(shù)。所有圖像訓(xùn)練樣本的總數(shù)量N=N1+N2+...NL

1）對所有圖像轉(zhuǎn)換為列矢量，即，把每個位置的染色體變?yōu)橄蛄?。每個向量代表一個個體，位數(shù)取決于染色體所代表圖像的灰度級，即圖像像素的編碼。假設(shè)一個灰度級為256的圖像，其染色體應(yīng)為8位（28=256），如圖1，為一個m×n像素的圖像。

2） 每個類的初始種群從Ni中產(chǎn)生。因為交叉操作需成對進行，所以當(dāng)Ni為奇數(shù)時，需要取一個測試圖像進行配對交叉（僅對屬于同一類的所有個體設(shè)置進行交叉操作，產(chǎn)生的新個體仍屬于此類中）。

3） 對每個類中的所有個體設(shè)置一個適應(yīng)度函數(shù)，這里采用歐氏距離來衡量。設(shè)測試用例為q，與xij（第i類中的第j個個體）的適應(yīng)度函數(shù)為：[d（j）i=q-x（j）iq，（1≤j≤2Ni）]

4） 新生成的類中的每個個體Ni都將符合最低適應(yīng)度函數(shù)。

5） 迭代遞增+1。

6） 如果算法執(zhí)行超過最大迭代數(shù)T，或者群體產(chǎn)生的個體已達到最高適應(yīng)度值，則認為此測試用例屬于該類。否則，轉(zhuǎn)到步驟3。

為說明交叉操作，設(shè)有某類中一對將要配對的個體a和b，在第4比特位進行切割交叉，將產(chǎn)生兩個新個體c和d，如圖2：

3 實驗分析

實驗使用了劍橋ORL庫（共有40人，每人10幅，每幅92×112像素的256灰度級圖片），實驗機器平臺為清華同方X46H型號，使用[8]的方法與遺傳算法進行比較，先后進行了10次實驗，取平均值得到結(jié)果如表1和表2：

表1 識別率對比

[訓(xùn)練樣本 Ni＼&GA識別率＼&PCA識別率＼&5＼&91.1%＼&90.0%＼&6＼&92.5%＼&91.7%＼&7＼&94.1%＼&93.3%＼&]

表2 運算時間對比

[訓(xùn)練樣本Ni＼&GA耗時（s）＼&PCA＼&前期處理時間（s）＼&識別時間（s）＼&總時間（s）＼&5＼&12.0＼&119.6＼&5.6＼&125.2＼&6＼&13.4＼&125.8＼&5.7＼&131.5＼&7＼&15.3＼&129.3＼&5.8＼&135.1＼&]

從實驗結(jié)果看，兩種方法的識別率比較接近。首先，對比所用時間，兩種方法在訓(xùn)練和識別同一組人臉時，在L=40，T<10，Pm<0.01，Pc=0.6的情況下，使用PCA方法的總耗時是GA的十倍。其次，對比存儲空間，PCA方法在前期的預(yù)處理過程中，占用資源要比GA方法大很多。例如一幅92×112的圖像，產(chǎn)生的協(xié)方差矩陣大小為10304×10304，如果協(xié)方差矩陣所表示的基本像素單元為8字節(jié)，那么6幅圖像需要占用存儲量6×10304^2×8b，相當(dāng)于4.7GB的存儲空間，要比普通的電腦全部內(nèi)存還大；而GA即使在256灰度級圖片上進行編碼，存儲6幅圖像所占用空間為：92×112×6×8×2約966Kb，遠遠小于PCA。

4 總結(jié)

利用遺傳算法良好的“生成+檢測”特性來尋找優(yōu)化問題的最優(yōu)解，并在人臉識別中進行一次有效嘗試，實驗結(jié)果表明在不降低識別率的情況下，無論是計算時間還是所占在存儲容量GA都要明顯少于PCA。但本方法只適合在非固定用戶群使用，這里使用單一的PCA降維方式進行實驗對比只是為了更明顯分析遺傳算法的特點，并非反映PCA方法低效，相反，在固定用戶群體的情況下，PCA只需進行一次前期訓(xùn)練即可完成以后的快速識別，這是GA所不能及的。相信在其他優(yōu)化問題求解上，遺傳算法會有更好的拓展空間。

參考文獻：

[1] 王映輝.人臉識別：原理、方法與技術(shù)[M].北京：科學(xué)出版社，2010.

[2] Turk M， Pentland A. Eigenfaces for Recognition， Journal of Cognitive Neurosicence， 1991，3（1）：71-86.

[3] Zhao W， Krishnaswamy A， Chellappa R， et al. Discriminant Analysis of Principal Components for Face Recognition， Face Recognition： From Theory to Applications， H. Wechsler， P.J. Phillips， V. Bruce， F.F. Soulie， and T.S. Huang， eds.， Springer-Verlag， Berlin， 1998：73-85.

[4] Yang M Q， Ahuja N， Kriegman D.Face recognition using kernel eigenfaces. Proc.ICIP，1：37-40.

[5] Lee J， Moghaddam B， Pfister H， et al. Finding Optimal Views for 3D Face Shape Modeling， Proc. of the International Conference on Automatic Face and Gesture Recognition， FGR2004， 17-19 May 2004， Seoul， Korea， pp. 31-36.

[6] Holland J H. Outline for a logical theory of adaptive systems. Journal of the Association fo Computing Machinery， 1962，9（3）：297-314.

[7] 李敏強，寇紀淞，林丹，等. 遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.

[8] Moon H， Phillips P J. Computational and Performance aspects of PCA-based Face Recognition Algorithms， Perception， 2001（30）：303-321.