劉悅婷,　張燕

( 蘭州文理學(xué)院 電子信息工程學(xué)院， 甘肅 蘭州 730000 )

?

CMSFLA-SVM算法在人臉識別中的應(yīng)用

劉悅婷,張燕

( 蘭州文理學(xué)院 電子信息工程學(xué)院， 甘肅 蘭州 730000 )

摘要：針對蛙跳算法(shuffled frog leaping algorithm，SFLA)易陷入局部最優(yōu)，且求解精度較低的問題，提出一種交叉變異的蛙跳算法(crossover and mutation shuffled frog leaping algorithm，CMSFLA).該算法在全局搜索中，青蛙個(gè)體依適應(yīng)度值而選擇不同概率分別進(jìn)行交叉和變異操作.將改進(jìn)的蛙跳算法CMSFLA訓(xùn)練支持向量機(jī)(support vectors machines，SVM)，并將其用于人臉識別中.ORL和CAS-PEAL-R1人臉庫仿真實(shí)驗(yàn)結(jié)果表明，與ASFLA-SVM和KSFLA-SVM方法相比，CMSFLA-SVM算法對人臉識別率更高，速度更快，且在訓(xùn)練樣本不足時(shí)，其識別效果仍能保持良好. 支持向量機(jī)； 蛙跳算法； 交叉； 變異； 人臉識別； 最優(yōu)解 TP391

文獻(xiàn)標(biāo)識碼：A

0引言

人臉識別是生物識別領(lǐng)域的重要研究方向.在人臉識別技術(shù)中，各種人臉特征選擇、特征提取方法和分類器的選擇是決定識別效果的關(guān)鍵，目前常用的人臉識別分類器有最近鄰距離法、人工神經(jīng)網(wǎng)絡(luò)法和支持向量機(jī)技術(shù)(SVM)[1].最近鄰距離分類器是最基本的分類法，被廣泛應(yīng)用于各領(lǐng)域，但該方法在訓(xùn)練樣本較多時(shí)會產(chǎn)生很高的錯誤率；人工神經(jīng)網(wǎng)絡(luò)分類器雖可解決非線性問題，但其依據(jù)風(fēng)險(xiǎn)最小化原則，易出現(xiàn)“過學(xué)習(xí)”現(xiàn)象，導(dǎo)致泛化能力較差；支持向量機(jī)技術(shù)基于結(jié)構(gòu)風(fēng)險(xiǎn)化原理，具有數(shù)學(xué)表達(dá)式簡潔和泛化能力良好的優(yōu)點(diǎn)，在解決分類、非線性和高維模式識別問題中表現(xiàn)出良好的特性.

一般SVM訓(xùn)練方法是將問題分解為許多子問題，然后再對子問題逐一優(yōu)化，但該方法運(yùn)算結(jié)果只有一個(gè)次優(yōu)解，并且分類速度較低[2].近年來，許多學(xué)者提出用仿生優(yōu)化算法訓(xùn)練SVM，以提高最優(yōu)解的質(zhì)量及求解速度，例如：文獻(xiàn)[3]采用遺傳算法優(yōu)化了SVM參數(shù)，文獻(xiàn)[4]提出了用粒子群算法(particle swarm optimization，PSO)訓(xùn)練SVM.這些算法雖然在一定程度上提高了SVM的分類效果，但訓(xùn)練樣本數(shù)較多且維數(shù)較高時(shí)其效果仍不理想.為此，有學(xué)者用蛙跳算法(SFLA)訓(xùn)練SVM[5]，但由于基本SFLA算法在全局搜索中，青蛙個(gè)體只是進(jìn)行混合后再分組，與上下代的信息傳遞較少；因此，本文引入了交叉變異的蛙跳算法(CMSFLA)，該算法能夠依據(jù)適應(yīng)度而選擇不同的概率來分別進(jìn)行交叉和變異操作，既可以繼承上一代的良好信息，又可以小概率變異，從而提高種群的多樣性，便于種群找到最優(yōu)解.本文用CMSFLA訓(xùn)練SVM，將其用于人臉識別中，并對其仿真結(jié)果進(jìn)行了驗(yàn)證和對比.

1支持向量機(jī)

支持向量機(jī)是模式識別的主流分類器，對非線性、高維數(shù)的小樣本人臉識別問題有很好的分類效果.其在結(jié)構(gòu)風(fēng)險(xiǎn)最小化的基礎(chǔ)上，先構(gòu)造最優(yōu)超平面，使分類誤差達(dá)到最小，再通過適當(dāng)?shù)暮撕瘮?shù)將非線性數(shù)據(jù)變換到高維空間，從而獲得最優(yōu)分類面[6].

給定訓(xùn)練樣本(xi，yi) (i=1,2,…,n)， x∈Rd， yi∈{+1,-1}， 滿足

yi[(wxi)+b]-1≥0， i=1,2,…,n.

(1)

(2)

滿足約束條件

(3)

0≤ai≤C ， i=1,2,…,n,

(4)

其中C為線性不可分樣本的分類錯誤懲罰參數(shù)， ai為每個(gè)訓(xùn)練樣本的Lagrange乘子， k(xi,xj)為核函數(shù).

求解以上二次規(guī)劃問題，可從訓(xùn)練樣本中得到對應(yīng)ai≠0的向量，即支持向量，由它們決定最優(yōu)分類面：

(5)

式中s為支持向量集.

2基本蛙跳算法

2003年，MuzaffarEusuff等提出了群體智能優(yōu)化算法——蛙跳算法(SFLA)[7].該算法結(jié)合了模因算法和粒子群算法的優(yōu)點(diǎn)，具有尋優(yōu)能力強(qiáng)和易于實(shí)現(xiàn)的優(yōu)點(diǎn)，已被成功應(yīng)用于資源網(wǎng)絡(luò)優(yōu)化問題、聚類問題、流水調(diào)度問題和考試安排等領(lǐng)域[7].

2.1　初始群體的生成

隨機(jī)生成具有F只青蛙的初始群體(X1,X2,…,XF)， 第i只表示為Xi=(xi1,xi2,…,xi D)， 其中D為解的維數(shù).初始群體生成后，將青蛙按照適應(yīng)度值進(jìn)行降序排列，然后再將青蛙群平均分配到m個(gè)子群，每個(gè)子群有n只，滿足F=m×n.

2.2　局部搜索

子群t次搜索后，最優(yōu)適應(yīng)度和最差適應(yīng)度的青蛙分別表示為Xb(t)、Xw(t)， 群體最優(yōu)適應(yīng)度的青蛙表示為Xg(t).每個(gè)子群進(jìn)行局部搜索后對子群中的Xw(t)進(jìn)行更新操作，更新策略為：

Di=rand()·(Xb-Xw);

(6)

Xw=Xw(當(dāng)前位置)+Di, -Dmax≤Di≤Dmax,

(7)

式中Di是分量i上移動的距離，rand()是0到1的隨機(jī)數(shù)， Dmax為青蛙允許運(yùn)動的最大距離.

進(jìn)行更新后，若得到的解Xw優(yōu)于原來的解Xw(當(dāng)前位置)，則用它取代原種群的解；否則用Xg取代Xb， 重復(fù)執(zhí)行式(6)和(7)；若仍無改進(jìn)，則隨機(jī)產(chǎn)生新解取代原來的Xw.

2.3　全局搜索

綜合青蛙各子群的局部模因信息有利于信息在全局中交流，可使算法向最優(yōu)解的方向繼續(xù)搜索[8-9].當(dāng)所有子群迭代結(jié)束后，將所有子群混合，依適應(yīng)度值降序排列，再平均劃分為子群，繼續(xù)進(jìn)行局部搜索，直到滿足混合迭代次數(shù)，算法停止.

3交叉變異的蛙跳算法訓(xùn)練支持向量機(jī)(CMSFLA-SVM)

3.1　交叉變異的蛙跳算法(CMSFLA)

為了便于種群找到最優(yōu)解，本文借鑒了遺傳算法中交叉和變異的思想，其中交叉概率和變異概率的取值是決定算法收斂性能的關(guān)鍵.交叉概率過大，新個(gè)體產(chǎn)生的速度越快，但會破壞適應(yīng)度值優(yōu)的個(gè)體；交叉概率過小，搜索過程緩慢，可導(dǎo)致算法停止.變異概率過大，算法會變成純粹的隨機(jī)搜索；變異概率過小，則很難產(chǎn)生新個(gè)體.因此，本文提出交叉概率和變異概率的大小隨著適應(yīng)度值改變的自適應(yīng)交叉和變異策略，如式(8)、(9)所示：

(8)

(9)

式中Pc為交叉概率，Pm為變異概率，f為交叉兩個(gè)體中較大的適應(yīng)度，f′為變異個(gè)體的適應(yīng)度，fmax為種群中最大適應(yīng)度，favg為種群中平均適應(yīng)度，k1和k2分別為常數(shù).當(dāng)種群中各個(gè)體的適應(yīng)度值趨向一致或趨于局部最小時(shí)，分別增大交叉概率和變異概率；而當(dāng)種群中各個(gè)體的適應(yīng)度值分散時(shí)，分別減小交叉概率和變異概率.

3.2　CMSFLA算法訓(xùn)練SVM

SVM的訓(xùn)練即為解決二次規(guī)劃問題，求解最優(yōu)的、不為零、非負(fù)的訓(xùn)練樣本點(diǎn)Lagrange乘子ai， 從而求出權(quán)值w和b以獲取分類面.

Lagrange乘子ai=(a1,a2,…,an)是一個(gè)n維向量，因此二次規(guī)劃問題(式(2))可用CMSFLA算法求解.本文用動態(tài)反向?qū)W習(xí)法初始化群體，并引入交叉變異概率來提高最優(yōu)解的質(zhì)量，獲取最優(yōu)ai， 提高SVM的訓(xùn)練速度和性能.采用CMSFLA算法訓(xùn)練SVM的步驟為：

步驟1初始化參數(shù):青蛙群總數(shù)F， 子群數(shù)m， 子群內(nèi)青蛙數(shù)n， 子群內(nèi)搜索次數(shù)Ne， 混合迭代次數(shù)N， 變異和交叉概率中的常數(shù)k1和k2；

步驟2按照CMSFLA方法初始化青蛙群，使每個(gè)青蛙產(chǎn)生一個(gè)滿足約束條件(3)和(4)的ai值；

步驟3用式(2)計(jì)算每個(gè)青蛙個(gè)體的目標(biāo)函數(shù)值，依目標(biāo)函數(shù)值對青蛙群體降序排列，分為m個(gè)子群；

步驟4確定局部搜索的Xb、Xw及全局最優(yōu)Xg.按式(6)、(7)進(jìn)行更新，直到設(shè)定的子群內(nèi)搜索次數(shù)達(dá)到Ne，將更新后的各子群混合，按式(8)、(9)選擇概率值進(jìn)行交叉和變異操作后取代初始群體；

步驟5若所有青蛙的全局最優(yōu)值滿足庫恩-塔克(Kuhn-Tucker)條件或達(dá)到混合迭代次數(shù)N， 則迭代終止，輸出結(jié)果，否則返回步驟3.其中Kuhn-Tucker條件為:

(10)

4仿真實(shí)驗(yàn)

為驗(yàn)證CMSFLA-SVM算法的有效性，實(shí)驗(yàn)分別采用ORL和CAS-PEAL-R1人臉庫作為測試對象，編寫Matlab程序，并與ASFLA-SVM[10]和KSFLA-SVM[11]算法進(jìn)行比較.測試中，參數(shù)取值與文獻(xiàn)[12]相同，種群中青蛙總數(shù)F=200，子群數(shù)m=20，子群內(nèi)搜索總次數(shù)Ne=10，混合搜索總次數(shù)N=400，變異和交叉概率中的常數(shù)k1=0.5，k2=0.5.

4.1　ORL人臉庫測試

ORL人臉庫[13]由40人的人臉圖像組成，其中每個(gè)人有10幅不同圖像，該圖像是每個(gè)人在不同時(shí)間、不同表情、不同光照及不同姿態(tài)下獲取的，每幅圖像為256級灰度、92×112像素，其中某人的10幅圖像如圖1所示.本實(shí)驗(yàn)選擇40人的4種測試模式(對每個(gè)人)： 1) Sub1：前5幅測試，后5幅訓(xùn)練； 2) Sub2：后5幅測試，前5幅訓(xùn)練； 3) Sub3：圖像名編號偶數(shù)的5幅測試，其余5幅訓(xùn)練； 4) Sub4：圖像名編號奇數(shù)的5幅測試，其余5幅訓(xùn)練.

圖1　ORL庫中某人的10幅圖像

測試結(jié)果如圖2、圖3所示.由圖2可知，隨特征維數(shù)的增加，3種方法的識別率都有所提高，但CMSFLA-SVM算法的識別率最高(97.5%)，比其他兩種方法高0.5%~1.6%.因此，說明CMSFLA-SVM算法的識別性能優(yōu)于ASFLA-SVM和KSFLA-SVM算法，同時(shí)也說明了CMSFLA算法訓(xùn)練SVM在人臉識別應(yīng)用中的有效性.圖3顯示了在不同ORL訓(xùn)練組中應(yīng)用不同的交叉變異概率獲取的不同人臉識別性能.從圖3可知，在Sub3和Sub4組中采用交叉變異概率提高了基本SFLA算法最優(yōu)解的性能，用其訓(xùn)練SVM后，可明顯提高人臉識別性能，這說明將交叉變異概率引入到SFLA算法中是有效的.表1顯示了不同ORL訓(xùn)練組的人臉識別性能，實(shí)驗(yàn)使用的特征維數(shù)為40.由表1可知，平均識別1副人臉圖像，KSFLA-SVM算法的識別時(shí)間為0.223 75s，識別率為96.275%；ASFLA-SVM算法的識別時(shí)間為0.203 75s，識別率為96.4%；CMSFLA-SVM算法的識別時(shí)間為0.199 75s，識別率為96.675%.這說明在SFLA算法的全局搜索中引入交叉變異概率可以提高最優(yōu)解的精度，從而提高人臉識別率，因此CMSFLA-SVM算法的識別性能優(yōu)于其他兩種算法.

圖2　3種方法的識別率隨特征維數(shù)的變化

圖3　CMSFLA-SVM算法的識別性能

表1　不同ORL訓(xùn)練組的人臉識別性能

4.2　CAS-PEAL-R1人臉庫測試

CAS-PEAL-R1人臉數(shù)據(jù)庫[13]是CAS-PEAL人臉庫的共享版，包括人臉的正面子庫和姿態(tài)子庫共計(jì)1 040人的30 900幅圖像，其中正面子庫包括標(biāo)準(zhǔn)、表情、光照、飾物、背景、距離和時(shí)間等共計(jì)1 040人的9 060幅圖像，姿態(tài)子庫包括1 040人的21 840幅圖像.本實(shí)驗(yàn)選取100人，每個(gè)人選取5幅表情(Open mouth、Frown、Close eyes、Smile and Surprise)和1副標(biāo)準(zhǔn)(Normal)共6幅，總共600幅人臉圖像，每幅圖像大小為360×480.所選其中某人的表情和標(biāo)準(zhǔn)的6幅測試圖像如圖4所示，佩戴飾物的6幅測試圖像如圖5所示.

圖4　CAS-PEAL-R1庫中表情和標(biāo)準(zhǔn)的人臉圖像

圖6　3種算法的識別率隨特征維數(shù)的變化

用如圖4所示每個(gè)人任意3幅圖像作測試，其余3幅作訓(xùn)練，測試結(jié)果如圖6所示.由圖6可知，CMSFLA-SVM算法的識別率高于其他兩種方法.當(dāng)特征維數(shù)為5時(shí)，CMSFLA-SVM算法的識別率為93.8%；當(dāng)特征維數(shù)為40時(shí)，CMSFLA-SVM算法的人臉識別率達(dá)到97.7%：因此，說明CMSFLA-SVM算法優(yōu)于其他兩種方法，并且CMSFLA-SVM算法對臉部表情變化具有很好的魯棒性，說明用CMSFLA算法訓(xùn)練SVM效果良好.

用如圖5所示佩戴飾物的100人的人臉圖像作為測試對象，取特征維數(shù)為60，訓(xùn)練樣本不足時(shí)3種方法的平均識別率如表2所示.表2中“2”表示每個(gè)人作為訓(xùn)練樣本有2幅圖像，測試樣本有其余4幅圖像.由表2可知，當(dāng)每個(gè)人的訓(xùn)練樣本都為“4”時(shí)，CMSFLA-SVM算法的平均識別率達(dá)到了96.5%,說明當(dāng)訓(xùn)練樣本不足時(shí)，CMSFLA-SVM算法仍能提高佩戴飾物人臉圖像的識別率.

表2　訓(xùn)練樣本不足時(shí)3種方法的平均識別率

5結(jié)束語

本文用改進(jìn)的蛙跳算法CMSFLA訓(xùn)練SVM，并將其用于人臉識別中，ORL和CAS-PEAL-R1人臉庫實(shí)驗(yàn)仿真結(jié)果表明：CMSFLA-SVM方法比ASFLA-SVM和KSFLA-SVM方法識別率更高，速度更快，且在訓(xùn)練樣本不足時(shí)仍能保持良好的識別效果.在優(yōu)化人臉識別問題時(shí)，CMSFLA-SVM算法中各參數(shù)的設(shè)置仍較薄弱，今后將對此作進(jìn)一步的研究.

參考文獻(xiàn)：

[1]ZHAO W, Chellappa R, Philips P J, et al. Face recognition: a literature survey[J]. ACM Computing Surveys, 2003,35(4):399-458.

[2]聶會星，梁坤，徐樅巍.基于小波變換和支持向量機(jī)的人臉識別研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，34(2)：208-211.

[3]汪世義，陶亮，王華彬.支持向量機(jī)和遺傳算法的人臉識別方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(12)：164-166.

[4]Tang Faming， Chen Mianyun， Wang Zhongdong. An improved approach to training support vectors machine[J]. Journal of Systems Engineering and Electronics, 2006，17(1):200-205.

[5]張瀟丹，黃程韋，趙力，等.應(yīng)用改進(jìn)混合蛙跳算法的實(shí)用語音情感識別[J].聲學(xué)學(xué)報(bào)，2014，51(2)：271-280.

[6]謝賽琴，沈福明，邱雪娜.基于支持向量機(jī)的人臉識別方法[J].計(jì)算機(jī)工程，2009，35(16)：186-188.

[7]Eusuff M M， Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Sources Planning and Management, 2003，129(3):210-225.

[8]Elbeltagi E， Hegazy T， Grierson D. A modified shuffled frog-leaping optimization algorithm： application to project management[J]. Structure and Infrastructure Engineering, 2007，3(1):53-60.

[9]姜建國，張麗媛，蘇仟.一種利用動態(tài)搜索策略的混合的蛙跳算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，41(4)：66-71.

[10]葛宇，王學(xué)平，梁靜.自適應(yīng)混沌變異蛙跳算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28(3)：945-947.

[11]李輝.交叉變異蛙跳算法[J].魯東大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，31(1)：16-20.

[12]Elbeltagi E， Hegazy T， Grierson D. Comparison among five evolutionary-based optimization algorithms[J]． Advanced Engineering Informatics， 2005，19(1)：43-53．

[13]田海軍.基于支持向量機(jī)的人臉識別技術(shù)研究與實(shí)現(xiàn)[D].長沙：國防科學(xué)技術(shù)大學(xué)，2009.

Application of CMSFLA-SVM algorithm in face recognition

LIU Yueting,ZHANG Yan

(SchoolofElectronicsandInformationEngineering，LanzhouUniversityofArtsandScience，

Lanzhou730000，China)

Abstract：Because of shuffled frog leaping algorithm (SFLA) such as local optimal and low precision solution，a crossover and mutation shuffled frog leaping algorithm is presented. In the global search， each of frog individuals according to the fitness will choose different probability of crossover and mutation operations. A face recognition algorithm using CMSFLA to train SVM is proposed. The simulation results of experiments on the ORL and CAS-PEAL-R1 face database show that compared with ASFLA-SVM and KSFLA-SVM， CMSFLA-SVM has higher recognition rate and higher speed. In the lack of training samples， CMSFLA-SVM also has good recognition effect.

Keywords：support vectors machines (SVM)； shuffled frog leaping algorithm (SFLA)； crossover； mutation； face recognition； optimal solution

文章編號：1004-4353(2015)04-0337-06

作者簡介：劉悅婷(1979—)，女，副教授，研究方向?yàn)殡娮?、自動控?

收稿日期：2015-11-03基金項(xiàng)目： 甘肅省高等學(xué)校科研項(xiàng)目(2015B-132)