邊航 汪友生

（北京工業(yè)大學(xué)電子信息與控制工程學(xué)院北京100124）

基于遺傳算法和AdaboostSVM的人臉檢測(cè)算法?

邊航 汪友生

（北京工業(yè)大學(xué)電子信息與控制工程學(xué)院北京100124）

將遺傳算法用于以SVM為弱分類器的Adaboost人臉檢測(cè)算法。先根據(jù)樣本訓(xùn)練集中的人臉和非人臉樣本訓(xùn)練出弱分類器SVM，然后利用Adaboost算法將多個(gè)SVM弱分類器級(jí)聯(lián)組合成一個(gè)強(qiáng)分類器，并且在組合的過程中采用遺傳算法對(duì)各個(gè)弱分類器權(quán)值進(jìn)行全局尋優(yōu)，最終得到檢測(cè)結(jié)果。通過與傳統(tǒng)Adaboost以及AdaboostSVM進(jìn)行對(duì)比試驗(yàn)，表明論文方法具有更高的檢測(cè)效果。

Adaboost；SVM；人臉檢測(cè)；遺傳算法

Class NumberTP391

1 引言

針對(duì)人臉檢測(cè)的算法有很多。1989年，Schap?ire最早提出了Boosting算法［1］，一年以后Freund提出了一種效率更高的Boosting算法［2］。1995年Freund和Schapire改進(jìn)Boosting算法，提出了Ada?boost（Adaptive Boosting）［3］，即自適應(yīng)學(xué)習(xí)算法。1999年，Robert E.Schapire和Yoram Singer提出了更具一般性的Adaboost形式［4］，采用自信率來(lái)改善Adaboost的性能，并設(shè)計(jì)出能夠解決多標(biāo)簽問題的Adaboost.MH和Adaboost.MR算法。2001年Viola.P和Jones.M提出了Cascade級(jí)聯(lián)方式［5］，每一級(jí)的特征從少到多，在粗檢的幾級(jí)就排除了大量的非人臉區(qū)域，因此該系統(tǒng)有效地提高了Adaboost的檢測(cè)速度，但誤檢率高。由于SVM算法［6］對(duì)于人臉和非人臉的兩類分類問題具有較好的魯棒性，因此可以考慮將兩種方法結(jié)合起來(lái)，其次，為使集成后的強(qiáng)分類器具有更好的精確度，采用遺傳算法對(duì)弱分類器的權(quán)值進(jìn)行優(yōu)化，使弱分類的分類精度既能略大于隨機(jī)猜測(cè)，又能和其他弱分類器有盡可能大的差異性，提高強(qiáng)分類器的泛化能力。該方法可以有效解決Adaboost方法中的精度和多樣性的兩難問題。

2 Adaboost算法及其局限性

Adaboost人臉檢測(cè)［7］實(shí)際上是一種基于積分圖、級(jí)聯(lián)檢測(cè)器和Adaboost算法的方法。Adaboost算法的核心思想就是針對(duì)不同的訓(xùn)練集訓(xùn)練出識(shí)別率不高的弱分類器，然后將這些大量的分類能力一般的弱分類器通過一定的方法集合起來(lái)，構(gòu)成一個(gè)強(qiáng)分類器的過程。

傳統(tǒng)的基于Adaboost算法的人臉檢測(cè)方法具有較好的檢測(cè)效果，它有效地提高了人臉檢測(cè)精度和速度。但同時(shí)也存在著問題，雖然Adaboost算法通過樣本權(quán)值的調(diào)節(jié)加強(qiáng)了分類器對(duì)錯(cuò)分樣本的學(xué)習(xí)能力，但它同時(shí)也導(dǎo)致了過學(xué)習(xí)的問題，導(dǎo)致算法性能的下降。而SVM算法對(duì)于兩類分類問題表現(xiàn)出了良好的魯棒性，它作為Adaboost算法的弱學(xué)習(xí)分類器能夠有效地改善其在特征選擇和泛化能力方面的效果，達(dá)到降低Adaboost算法復(fù)雜性的要求，比較適合用于區(qū)分人臉和非人臉這種兩類分類預(yù)測(cè)問題。

3 支持向量機(jī)算法

支持向量機(jī)理論［8］（Support Vector Machine，SVM）最早是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來(lái)的一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的模式識(shí)別方法。其基本思想就是尋找到一個(gè)最優(yōu)超平面，能夠使得分類間隙最大，從而將不同類樣本分開。為避免高維空間的計(jì)算，SVM利用事先定義好的核函數(shù)實(shí)現(xiàn)樣本到特征空間的映射。核函數(shù)的選擇工作大致分為兩步：一是核函數(shù)類型的選擇，二是核函數(shù)相關(guān)參數(shù)的選定。目前常用的核函數(shù)有：線性核函數(shù)、多項(xiàng)式核函數(shù)、徑向基核函數(shù)（RBF）、傅里葉核函數(shù)、樣條核函數(shù)和Sigmoid核函數(shù)。

4 AdaboostSVM算法

本文選用RBFSVM作為Adaboost的弱分類器。RBFSVM有兩個(gè)參數(shù)，分別為高斯寬度α以及規(guī)則化參數(shù)C。通過調(diào)整兩個(gè)參數(shù)可以影響RBFS?VM分類器分類能力的強(qiáng)弱。通過對(duì)分類器性能分析發(fā)現(xiàn)：如果C的取值很小，訓(xùn)練器的分類精度不好，會(huì)出現(xiàn)欠學(xué)習(xí)的情況，但是當(dāng)C過大時(shí)又會(huì)出現(xiàn)過學(xué)習(xí)狀況。如果α過大，就會(huì)導(dǎo)致SVM弱分類器性能太弱，分類精度達(dá)不到50%，即不能滿足Adaboost對(duì)弱分類器的要求；若α值過小，將會(huì)導(dǎo)致SVM分類器性能過強(qiáng)，每個(gè)弱分類器的差異性會(huì)變小，無(wú)法進(jìn)行進(jìn)一步的增強(qiáng)，Adaboost集成將會(huì)失去意義。本文采用一種折中的方法來(lái)調(diào)整參數(shù)C和α的值。首先定義第m個(gè)弱分類器的多樣性值為［9］

其中，gm(xi)為第m個(gè)弱分類器對(duì)樣本i進(jìn)行分類的結(jié)果，f(xi)為除去第m個(gè)弱分類器之外的其他所有分類器對(duì)樣本i進(jìn)行分類的結(jié)果。假設(shè)M個(gè)分類器對(duì)N個(gè)樣本進(jìn)行分類的多樣性可以表示為

傳統(tǒng)Adaboost算法只是簡(jiǎn)單將弱分類器加權(quán)求和，沒有考慮它們之間的差異性對(duì)集成造成的影響。當(dāng)訓(xùn)練一個(gè)新的SVM弱分類器時(shí)，需要同時(shí)計(jì)算弱分類器的多樣性值，若所求得的多樣性值小于預(yù)先設(shè)定的閾值并且小于給定的精度，則認(rèn)為該分類器不符合要求，那么就拋棄它；反之，則采用它。這樣產(chǎn)生的分類器集在分類精度和復(fù)雜度上是折中的。

5 AdaboostSVM算法的優(yōu)化改進(jìn)

遺傳算法［10］是模擬生物在自然環(huán)境中優(yōu)勝劣汰、適者生存的遺傳和進(jìn)化過程而形成的一種具有自適應(yīng)能力以及全局性的概率搜索算法。近年來(lái)，遺傳算法作為一種尋優(yōu)方法已成為解決各類復(fù)雜問題的有力工具。遺傳算法中的每一個(gè)解決方案都對(duì)應(yīng)著其中一條染色體，因此從一個(gè)基因組到其解的適應(yīng)度就形成了一個(gè)映射。當(dāng)初始種群產(chǎn)生之后，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體基因交叉變異，產(chǎn)生子代，逐代演化產(chǎn)生最優(yōu)個(gè)體，經(jīng)過解碼即為問題的近似最優(yōu)解。也就是把遺傳算法的過程看作是一個(gè)在多元函數(shù)里面求最優(yōu)解的過程。

為了把一個(gè)問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間［11］，本文選用浮點(diǎn)數(shù)編碼方式，基因組表示為Y={w1，w2，…，wM}，其中：

基因組的初始化為Adaboost已經(jīng)得到的權(quán)值。

為了更好地選擇優(yōu)質(zhì)個(gè)體而拋棄劣質(zhì)個(gè)體，提高全局收斂性和計(jì)算效率，本文采用基于概率模型的選擇算子［12］，每個(gè)基因被選擇的概率為

其中，q表示最好的基因被選擇的概率，r表示為基因的等級(jí)。

遺傳算法中產(chǎn)生新個(gè)體的主要操作過程即為交叉運(yùn)算。本文采用非均勻交叉算子［13］，首先從父親基因Y中隨機(jī)選取一個(gè)元素wk，通過計(jì)算得到新的基因組Y′={w1，w2，…，wk′，…，wM}，其中：

式中，r1，r2為由均勻分布得到的隨機(jī)數(shù)；G為當(dāng)前代基因總數(shù)；Gmax為全部代中最大的基因數(shù)；b為控制函數(shù)f(G)形狀的因子。

變異是防止個(gè)體過早收斂，陷入局部?jī)?yōu)化的算子。本文選用的是啟發(fā)式交叉算子［13］：

每次僅產(chǎn)生一個(gè)新的子代個(gè)體Y′，且Y的適應(yīng)度大于X，式中r∈(0，1)。

遺傳算法優(yōu)化弱分類器權(quán)值的流程圖如圖1所示。

圖1遺傳算法優(yōu)化弱分類器權(quán)值流程圖

6 試驗(yàn)結(jié)果及分析

試驗(yàn)運(yùn)行環(huán)境：硬件平臺(tái)為：AMD Athlon（tm）Dual Core Processor 5200B 2.70GHz，2GB內(nèi)存；軟件平臺(tái)：Windows XP Professional；采用VS2010以及OpenCV2.4.10作為開發(fā)工具。

從一些人臉庫(kù)以及網(wǎng)絡(luò)圖片中選取5000張人臉圖像以及10000張非人臉圖像作為訓(xùn)練樣本集。訓(xùn)練前對(duì)樣本圖像進(jìn)行預(yù)處理，主要包括尺寸的調(diào)整以及灰度歸一化等，圖2為部分訓(xùn)練集。試驗(yàn)采用130張圖像作為測(cè)試集，每張圖像包含一張或多張人臉，共431張人臉。遺傳算法的參數(shù)設(shè)置如下：種群最大迭代次數(shù)為100，交叉概率0.9，變異率0.001，適應(yīng)度函數(shù)設(shè)為識(shí)別的正確率。

圖2部分訓(xùn)練樣本

在試驗(yàn)中，分別采用了Adaboost算法、Ada?boostSVM算法以及結(jié)合遺傳算法的AdaboostSVM算法訓(xùn)練的分類器進(jìn)行試驗(yàn)，均采用相同的訓(xùn)練樣本。結(jié)果如表1所示。

表1 算法定量比較結(jié)果

從該表的數(shù)據(jù)中可以看出，本文算法的訓(xùn)練識(shí)別率相比傳統(tǒng)的Adaboost和AdaboostSVM算法有所提高，并且在保證檢出率的基礎(chǔ)上誤檢率比前兩者減少了一個(gè)數(shù)量級(jí)，使得檢測(cè)率和誤檢率都有較大的改進(jìn)，這說(shuō)明通過本文的算法，分類器的性能得到了有效的提高。本文算法部分檢測(cè)結(jié)果如圖3、圖4所示。

圖3單人人臉檢測(cè)結(jié)果

圖4多人人臉檢測(cè)結(jié)果

7 結(jié)語(yǔ)

本文在Adaboost算法的基礎(chǔ)上，提出一種結(jié)合Adaboost和SVM來(lái)構(gòu)建弱分類器，并引入遺傳算法對(duì)弱分類器的權(quán)值進(jìn)行全局尋優(yōu)的人臉檢測(cè)方法。這種方法采用RBFSVM作為分量分類器，通過調(diào)整RBF核的參數(shù)，從而使每個(gè)分量分類器在準(zhǔn)確率和差異性之間得到平衡，再通過遺傳算法對(duì)分量分類器的權(quán)值進(jìn)行優(yōu)化，最后通過Adaboost算法把這些分量分類器整合起來(lái)，構(gòu)建成一個(gè)強(qiáng)分類器。試驗(yàn)結(jié)果表明，該算法能夠有效地提高正確檢出率同時(shí)降低誤檢率。

［1］SCHAPIRE R E.The Strength of Weak Learnability［J］. Machine Learning，1990，5（2）：197-227.

［2］FREUND Y.Boosting a Weak Learning Algorithm by Ma?jority［J］.Information and Computation，1995，121（2）：256-285.

［3］FREUND Y，SCHAPIRE R.A decision-theoretic Gener?alization of On-line Learning and an Application to Boost? ing［J］.Journal of Computer and System Sciences，1997，55（1）：119-139.

［4］SCHAPIRE R，SINGER Y.Improved Boosting Algorithms Using Confidence-rated Predictions［J］.Machine Learn?ing，1999，37（3）：297-336.

［5］VIOLA P，JONES M.Rapid Object Detection Using a BoostedCascade of Simple Features［C］//Proceedings of the 2001 IEEE Computer Society Conference.Kauai：IEEE，2001：511-518.

［6］Burges CJC.A tutorial on support wector machines for pat?tern recognition［J］.Data Mining and Knowledge Discov?ery，1998，2（2）：121-167.

［7］李闖，丁曉青，吳佑壽.一種基于直方圖特征和Ada?Boost的圖像中的文字定位算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2006，11（3）. LI Chuang，DING Xiaoqing，WU Youshou.A histogram feature and AdaBoost based text localization algorithm of the image［J］.Journal of image and graphics，2006，11（3）.

［8］Li Xuchun，Wang Lei Sung Eric.A Study of Adaboost with SVM basedweak Learners［C］//Proceedings of internation?al Joint on Neural Net-works.Montreal Canada，2005：196-201.

［9］MELVILLEP，MOONEY R J.Creating Diversity in Ensem?bles Using Artificial Data［J］.Information Fusion，2005，6（1）：99-111.

［10］HOUK C R，JOINES J，KAY M.A Genetic Algorithm for Function Optimization：A Matlab Implementation［R］. North Carolina State University，1995.

［11］馬永杰，云文霞.遺傳算法研究進(jìn)展［J］.計(jì)算機(jī)研究與應(yīng)用，2012，4（29）. MA Yongjie，YUN Wenxia.The development of Genetic algorithm［J］.Research and application of computer，2012，4（29）.

［12］KIM H C，PANG S，JE H M，et al.Constructing Support Vector Machine Ensemble［J］.Pattern Recognition，2003，36（12）：2757-2767.

［13］GAO G H，ZHANG Y Z，ZHU Y，et al.Hybrid Support Vector Machines-based Multi-fault Classification［J］. Journal of China University of Mining and Technology，2007，17（2）：246-250.

Face Detection Based on Genetic Algorithms and AdaboostSVM Algorithm

BIAN HangWANG Yousheng
（College of Electronic and Control Engineering，Beijing University of Technology，Beijing100124）

An algorithm using genetic algorithm to improve the face detection in Adaboost with SVM based weak classifiers is proposed.Firstly，the method trains the weak classifier of support vector machine（SVM）according to human face samples and nonface samples in the training sample set，then uses Adaboost algorithm to embody the weak classifiers into a strong classifier，while using genetic algorithm to optimize weights of weak classifiers for global optimization，and final detection result is given.Experimen?tal result demonstrates that GA-AdaboostSVM achieved better detection performance than the traditional Adaboost and AdaboostS?VM methods.

Adaboost，SVM，face detection，genetic algorithm

TP391

10.3969/j.issn.1672-9722.2017.07.037

2017年1月11日，

2017年2月23日

邊航，女，碩士研究生，研究方向：像處理分析等。汪友生，男，博士，副教授，研究方向：像處理、模式識(shí)別等。