基于人工魚群的Gentle Adaboost快速訓(xùn)練算法

許 恒 李 浩 鐘漢亭

（1、浙江省質(zhì)量技術(shù)監(jiān)督檢測(cè)研究院，浙江 杭州 310013 2、上海計(jì)量測(cè)試研究院，上海 200000）

1 引言

人臉檢測(cè)，是指對(duì)于任意一幅給定的圖像，采用一定的策略對(duì)其進(jìn)行搜索以確定其中是否含有人臉的過程，在現(xiàn)代人機(jī)自然交互（HCNI）、身份認(rèn)證和安全防護(hù)中有著廣泛的應(yīng)用[1][2]。Viola和Jones于2001年提出了一種基于Adaboost的人臉檢測(cè)算法[3]，較之以往的算法，這種方法檢測(cè)率高、檢測(cè)速度快，在CMU測(cè)試集上的檢測(cè)率為92.1%，檢測(cè)速度達(dá)到每秒15幀（PIII700MHZ）。目前，Adaboost方法已經(jīng)成為了研究的熱點(diǎn)。在Adaboost算法諸多變種中，Gentle Adaboost算法較少強(qiáng)調(diào)野點(diǎn)，并對(duì)樣本的過適應(yīng)有一定的抑制作用。Rainer Lienhart等通過試驗(yàn)證明Gentle Adaboost運(yùn)用于人臉檢測(cè)領(lǐng)域有較好的性能[4]。Adaboost通過重復(fù)搜索給定的類Haar矩形特征空間來選擇有效的弱分類器，盡管能在每一次迭代過程中取得最優(yōu)的分類特征，但大量的迭代和前向搜索也將消耗巨量的時(shí)間[3]。完全遍歷特征空間中的特征數(shù)量十分巨大，以一張20×20的灰度圖像為例，選取八種矩形特征類型進(jìn)行遍歷，共需計(jì)算64409個(gè)特征。對(duì)于形狀相同、位置相近但長(zhǎng)寬不等的矩形特征而言，特征與特征之間存在著大量相關(guān)性信息，矩形越相似，相關(guān)性越大。因此，在保證有效檢測(cè)性能的基礎(chǔ)上可以通過減少特征空間中不必要的冗余，以縮短訓(xùn)練時(shí)間。

本文提出一種基于人工魚群的Gentle Adaboost快速訓(xùn)練算法。人工魚群是由李曉磊等在2003年提出的一種基于動(dòng)物行為的新型群體智能優(yōu)化算法[5]，通過對(duì)魚群行為的模擬能在解空間快速地得到一個(gè)較優(yōu)值。算法通過模擬人工魚群覓食、聚群、追尾等行為，減少搜索次數(shù)，達(dá)到快速搜索的目的。在對(duì)MIT和FERET人臉庫上部分樣本的仿真實(shí)驗(yàn)表明，該算法在保證檢測(cè)性能的要求下約能將訓(xùn)練時(shí)間縮短至原始訓(xùn)練時(shí)間的1/3。

2 Gentle Adaboost算法的訓(xùn)練機(jī)制

Adaboost算法通過尋找一組在自然界中分類能力一般的弱分類器，針對(duì)它們對(duì)不同樣本的分類能力，賦予不同的權(quán)重，并使用加權(quán)投票機(jī)制，集合成強(qiáng)分類器。在這個(gè)過程中，結(jié)合人工魚群算法在特征空間中挑選分類結(jié)果最好的特征作為弱分類器。

2.1 類Haar矩形特征

基于人臉模式的特定性，Adaboost算法使用類Haar矩形特征實(shí)現(xiàn)對(duì)人臉形態(tài)的描述。圖1顯示了幾類基本的矩形特征，每一類型通過對(duì)矩形尺寸和位置的不同定義構(gòu)建特征空間，訓(xùn)練樣本尺寸越大，特征數(shù)量越多，特征值由矩形覆蓋的象素面積決定，其值等于不同顏色區(qū)域覆蓋象素值之差。

圖1 幾類基本的矩形特征

2.2 弱分類器的選取

Gentle Adaboost根據(jù)不同樣本的分類結(jié)果更新樣本權(quán)重，在分類均方誤差最小準(zhǔn)則下選擇特征作為弱分類器，算法流程如下:

2.2.1初始化樣本權(quán)重

2.2.2 For i=1:n

·歸一化樣本權(quán)重

·計(jì)算每個(gè)特征的均方分類誤差

其中，m為樣本總數(shù)，wk表示第k個(gè)樣本的權(quán)重，yk表示第k個(gè)樣本，正樣本等于你1負(fù)樣本等于-1，j=1，...m。

·選擇均方分類誤差 最小的特征作為弱分類器

·更新樣本權(quán)重

3 基于人工魚群算法的Gentle Adaboost

本文嘗試結(jié)合人工魚群算法減少計(jì)算機(jī)的訓(xùn)練時(shí)間。利用人工魚群的活動(dòng)嘗試接近每次循環(huán)中的最優(yōu)弱分流器。人工魚群算法是一種模擬魚群行為的優(yōu)化算法，通過對(duì)魚群中各個(gè)體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來的目的[6]。人工魚群個(gè)體的全局狀態(tài)可表示為向量 X=(x1，x2，…，xn)，對(duì)于類 Haar矩形特征空間，選取n=5，其中x1～n分別為矩形類型、矩形長(zhǎng)度、矩形寬度、位置橫坐標(biāo)和位置縱坐標(biāo)。在特征的遍歷過程中，同類型特征的上一特征的結(jié)果對(duì)下一特征的結(jié)果有一定延伸性，因此，人工魚群在搜索特征時(shí)，無需遍歷整個(gè)特征空間，就能減少訓(xùn)練時(shí)間，得到較好的結(jié)果。

3.1 人工魚群的行為描述

覓食行為。對(duì)于人工魚群個(gè)體狀態(tài)Xi，在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，如果該狀態(tài)所在位置食物濃度較多（目標(biāo)函數(shù)Yj較優(yōu)），則向該方向前進(jìn)一步，否則重新隨機(jī)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件，在try_number次后仍不滿足前進(jìn)條件時(shí)，則隨機(jī)移動(dòng)一步。

聚群行為。對(duì)于人工魚群個(gè)體狀態(tài)Xi，探索當(dāng)前鄰域內(nèi)，即 di，j

追尾行為。對(duì)于人工魚群個(gè)體狀態(tài)為Xi，探索當(dāng)前鄰域內(nèi)，即di,j

3.2 目標(biāo)函數(shù)的確定

人工魚群算法是通過搜尋目標(biāo)函數(shù)的極值，評(píng)價(jià)尋優(yōu)的狀態(tài)。當(dāng)極值滿足終止條件或搜索次數(shù)時(shí)，搜索過程結(jié)束。Gentle Adaboost按照均方分類誤差最小選擇特征，選擇函數(shù) 作為目標(biāo)函數(shù)，魚群游移時(shí)，記錄最小的 值和相應(yīng)特征。

3.3 初始化和行為策略

參照文獻(xiàn)[7]的方法設(shè)定初始視野，visual=總特征數(shù)/4和初始步長(zhǎng)step=visual/8;并引入衰減因子，隨著迭代的增加減少步長(zhǎng)和視野，增加魚群的尋優(yōu)能力。衰減因子a=exp(-30*(t/Tmax)S)。

魚群按追尾、覓食、聚群的行為策略進(jìn)行游移。即先執(zhí)行追尾行為，如果沒有進(jìn)步則執(zhí)行覓食行為，如果仍然沒有進(jìn)步則執(zhí)行聚群行為。

3.4 算法的終止條件

人工魚群的每一次游移都會(huì)產(chǎn)生新的結(jié)果，考慮按魚群追尾、覓食、聚群的行為策略進(jìn)行循環(huán)，并對(duì)結(jié)果進(jìn)行評(píng)估。如果循環(huán)一定次數(shù)后連續(xù)幾次得到的結(jié)果的均方誤差均小于規(guī)定值，或循環(huán)次數(shù)已滿則跳出循環(huán)。否則程序繼續(xù)進(jìn)行循環(huán)，直到設(shè)定次數(shù)完成為止。

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

實(shí)際檢測(cè)中，Adaboost算法采用級(jí)聯(lián)結(jié)構(gòu)組合強(qiáng)分類器，對(duì)于存在的大量非人臉目標(biāo)，檢測(cè)器只需通過前幾層分類器就能將其快速濾除。并且算法在關(guān)注單級(jí)強(qiáng)分類器的檢測(cè)率（目標(biāo)的正分率）時(shí)，也允許一定誤檢率（非目標(biāo)的誤分率）的存在。

本文使用MIT和FERET人臉數(shù)據(jù)庫進(jìn)行仿真實(shí)驗(yàn)，在每個(gè)數(shù)據(jù)庫中挑選500張人臉樣本和大約2000張左右的非人臉樣本作為訓(xùn)練集，由于只能找到FERET數(shù)據(jù)庫中的人臉樣本，訓(xùn)練中的非人臉樣本是通過Internet獲得的。使用傳統(tǒng)的Gentle Adaboost和基于人工魚群的Gentle Adaboost算法（簡(jiǎn)稱GAB.人工魚群），在MATLB7.0上進(jìn)行實(shí)驗(yàn)，平臺(tái)為Intel Centrino Duo 1.6GHZ、1G內(nèi)存的筆記本計(jì)算機(jī)，構(gòu)建了多級(jí)的級(jí)聯(lián)分類器。

圖2 算法流程

將人工魚群的循環(huán)設(shè)置為10次，終止條件設(shè)置為:連續(xù)得到6次的均方誤差小于0.001或者循環(huán)滿30次，魚群數(shù)目設(shè)置為1000條。

表1顯示了傳統(tǒng)Gentle Adaboost和GAB.人工魚群算法對(duì)MIT和FERET人臉數(shù)據(jù)庫部分樣本的訓(xùn)練結(jié)果。其中對(duì)檢測(cè)率和誤檢數(shù)的結(jié)果是對(duì)MIT人臉數(shù)據(jù)庫中1000張樣本圖片（正負(fù)樣本圖片各為500張）分類得到的結(jié)果。鑒于FERET人臉數(shù)據(jù)庫中樣本尺寸為14×14，因此對(duì)測(cè)試集中圖像做了裁剪處理。通過實(shí)驗(yàn)可知相比傳統(tǒng)算法GAB.人工魚群訓(xùn)練時(shí)間大大縮短，檢測(cè)率和誤檢率基本與其一致，可以滿足應(yīng)用要求。

?

5 結(jié)論

本文提出了一種基于人工魚群的Gentle Adaboost人臉檢測(cè)算法。介紹了Gentle Adaboos選擇特征作為弱分類器的原理，并將分類最小均方誤差作為人工魚群尋優(yōu)的目標(biāo)函數(shù)。人工魚群算法通過設(shè)定魚群相關(guān)參數(shù)，規(guī)定了算法的終止條件，實(shí)現(xiàn)了對(duì)特征的快速搜索，構(gòu)建了級(jí)聯(lián)結(jié)構(gòu)的分類器。在對(duì)MIT和FERET人臉數(shù)據(jù)庫上的仿真實(shí)驗(yàn)表明該算法在保證相當(dāng)檢測(cè)精度的要求下，約能縮短訓(xùn)練時(shí)間至原始訓(xùn)練時(shí)間的1/4。

利用人工魚群算法求解弱分類器雖然能減少整個(gè)算法的訓(xùn)練時(shí)間，保證一定的分類器分類精度。但在魚群求解的過程中，并不能一定保證所得到的弱分類器是當(dāng)前循環(huán)中最優(yōu)的。因此可能導(dǎo)致弱分類器個(gè)數(shù)的增加。因此，在未來的研究工作中，我們將致力于研究更適應(yīng)Adaboost的人工魚群算法，提高魚群獲得精確解的能力，從而求的更為優(yōu)秀的分類器。

[1]孫寧，鄒采榮，趙力.人臉檢測(cè)綜述 [J].電路與系統(tǒng)學(xué)報(bào)，2006，11(6):101-108.

[2]魏冬生，李林青.Adaboost人臉檢測(cè)方法的改進(jìn) [J].計(jì)算機(jī)應(yīng)用 2006，26(3):619-620.

[3]李曉磊.一種新型的智能優(yōu)化算法-人工魚群算法 [D].杭州:浙江大學(xué)，2003.

[4]鄭曉鳴.人工魚群的改進(jìn)及應(yīng)用 [D].上海:上海海事大學(xué)，2006.

[5]王聯(lián)國，洪毅，趙付青，余冬梅.一種改進(jìn)的人工魚群算法[J].計(jì)算機(jī)工程 2008，34(19):192.