AdaBoost人臉檢測定點(diǎn)型優(yōu)化算法

周振華

(河南省水文水資源局 鄭州 450003)

AdaBoost人臉檢測定點(diǎn)型優(yōu)化算法

周振華

(河南省水文水資源局 鄭州 450003)

提出一種AdaBoost人臉檢測的定點(diǎn)型優(yōu)化算法，該算法以AdaBoost人臉檢測原型算法為基礎(chǔ)，分析了Cascade瀑布式級聯(lián)分類器中弱分類器與強(qiáng)分類器分類計(jì)算的特點(diǎn)，有效分解了弱分類器與強(qiáng)分類器的計(jì)算過程，從而現(xiàn)實(shí)了強(qiáng)分類器與弱分類器相關(guān)模型參數(shù)有效分離標(biāo)定。優(yōu)化算法進(jìn)一步利用圖像積分圖及弱分類器計(jì)算特點(diǎn)，完成對弱分類器計(jì)算過程及相關(guān)模型參數(shù)的定點(diǎn)型轉(zhuǎn)化；同時，利用強(qiáng)分類器浮點(diǎn)的計(jì)算精度要求，完成強(qiáng)分類器計(jì)算過程及相關(guān)模型參數(shù)的定點(diǎn)型轉(zhuǎn)化。該定點(diǎn)型AdaBoost人臉檢測方法計(jì)算精度逼近原浮點(diǎn)型算法計(jì)算精度，保持了較高的人臉檢測正確率，并利于后期的SIMD并行計(jì)算方法優(yōu)化，同時，也利于算法在定點(diǎn)型嵌入式設(shè)備上的移植與優(yōu)化。

AdaBoost; 人臉檢測; 圖像積分圖; 強(qiáng)分類器; 弱分類器

人臉檢測是人臉分析的首要環(huán)節(jié)，它確認(rèn)當(dāng)前圖像(或視頻)是否存在人臉，并對存在的人臉進(jìn)行定位。人臉檢測技術(shù)一直是模式識別和計(jì)算機(jī)視覺等領(lǐng)域的研究熱點(diǎn)[1-6]，具有十分廣泛的應(yīng)用前景。在人臉檢測研究領(lǐng)域，以文獻(xiàn)[1]提出的AdaBoost算法為里程碑，使人臉檢測技術(shù)走向?qū)嵱肹7-9]。AdaBoost人臉檢測算法與以往的人臉檢測算法相比具有較高檢測精度及較小的計(jì)算量，已成為許多實(shí)時系統(tǒng)的首選算法[10-11]。但由于該算法存在較多浮點(diǎn)運(yùn)算，在許多浮點(diǎn)計(jì)算能力較弱的嵌入式系統(tǒng)中，檢測實(shí)時性仍然達(dá)不到要求。本文提出AdaBoost人臉檢測的定點(diǎn)型優(yōu)化算法，將算法中所有浮點(diǎn)運(yùn)算轉(zhuǎn)化為定點(diǎn)運(yùn)算，從而提高算法的檢測性能。

1 AdaBoost人臉檢測算法

文獻(xiàn)[1]提出的AdaBoost人臉檢測算法是原型算法，其算法流程為：對當(dāng)前圖像以一定縮小比例進(jìn)行縮小，直至接近24×24，并用各圖像組成金字塔形圖像集合，在所有圖像集合中，以一定步進(jìn)規(guī)則，按24×24大小，使用AdaBoost算法搜索人臉圖像，如搜索到人臉圖像，標(biāo)定人臉位置，并記錄所在的金字塔圖像及縮小比例，所有圖像搜索完畢后，按記錄位置及縮小比例換算到與原始圖像大小對應(yīng)的位置，該位置即為檢測到的人臉位置。圖1為基于AdaBoost算法的人臉檢測流程。圖2為用縮放算法得到的金字塔圖像集合。

圖1 基于AdaBoost算法的人臉檢測流程

圖2 用縮放算法得到的金字塔圖像集合

人臉檢測算法流程中，AdaBoost人臉檢測器是最關(guān)鍵的部分，由積分圖像計(jì)算、歸一化均值及均方差檢測、Harr特征計(jì)算和瀑布式級聯(lián)分類器組成。

積分圖像及平方積分圖是對圖像內(nèi)一點(diǎn)A(x,y)，定義其積分圖為：

式中，ii(x′, y′)為點(diǎn)(x′, y′)處的“原始圖”，即Y分量，其值為0～255。

對于圖像內(nèi)一點(diǎn)A(x,y)，定義其平方積分圖為：

積分圖像和平方積分圖像均由迭代方法求出。

1.1 Harr特征計(jì)算

利用積分圖像計(jì)算5種Harr特征，分別如圖3a～圖3e所示。

類型0計(jì)算方法：

BCEF?ABDE=(B+F?C?E)?(A+E?B?D)=

D+F?A?C+2(B?E)

類型1計(jì)算方法：

BCEF?ABDE=(B+F?C?E)?(A+E?B?D)= D+F?A?C+2(B?E)

類型2計(jì)算方法：CDGH+ABEF?2BCFG=ADEH?3BCFG=

A+H?D?E+3(C+F?B?G)類型3計(jì)算方法：

CDGH+ABEF?2BCFG=ADEH?3BCFG=

A+H?D?E+3(C+F?B?G)類型4計(jì)算方法：

ABDE+EFHI?BCEF?DEGH= A+E?B?D+E+I?H?F+E+G?D?H+E+C?B?F=

4E–2(B+D?H?F)+A+C+G+I

圖3 5種Harr特征

1.2 瀑布式級聯(lián)分類器

瀑布式級聯(lián)分類器由機(jī)器學(xué)習(xí)訓(xùn)練得到，其級聯(lián)形式如圖4所示，包含數(shù)級強(qiáng)分類器(節(jié)點(diǎn)分類器)，每級強(qiáng)分類器又包含不同級數(shù)的弱分類器。所選取的Harr特征先進(jìn)行弱分類器分類，分類結(jié)果經(jīng)強(qiáng)分類器加權(quán)求和得到該級強(qiáng)分類器的分類結(jié)果。如不是人臉，將退出，并做出“不是人臉”的判斷；如是人臉，將進(jìn)入下一級分類器再進(jìn)行分類判斷，直至完成所有分類器的分類判斷，即所有強(qiáng)分類器均判定為人臉，則瀑布式級聯(lián)分類器做出最終判斷“該區(qū)域?yàn)槿四槨薄?/p>

一個弱分類器h(x,f,p,s,θ)由特征f、閾值θ和指示不等號方向的p組成，弱分類器的分類結(jié)果為：

式中，

式中，

圖4 基于AdaBoost算法的級聯(lián)式人臉檢測器

h(x,f,p,s,θ)為在選定Harr特征條件下，弱分類器的分類結(jié)果，其利用大量樣本進(jìn)行訓(xùn)練，并使該弱分類器的最小錯誤率αt最小。上述參數(shù)中，f(x)為選定的Harr特征，參數(shù)θ和p為訓(xùn)練該弱分類器得到的參數(shù)；me、sq為積分圖和平方積分圖的計(jì)算結(jié)果，為整型；s、θ均為浮點(diǎn)數(shù)；p指示不等號方向，為整型數(shù)。

強(qiáng)分類器利用若干個弱分類器進(jìn)行分類，強(qiáng)分類器可表示為：

其中，式中，ht(x)為弱分類器的分類結(jié)果；αt為對應(yīng)強(qiáng)分類器的模型參數(shù)；α_th為該強(qiáng)分類器閾值。αt和α_th均通過大量樣本訓(xùn)練得到，為浮點(diǎn)數(shù)。

從上面AdaBoost人臉檢測算法的計(jì)算過程可以看出，積分圖像、平方積分圖像、Harr特征的計(jì)算由于是利用所選的24×24的灰度圖像作為輸入進(jìn)行計(jì)算，而灰度圖像通常以整型數(shù)表示(0～255)，所以以上計(jì)算結(jié)果也可用整型數(shù)表示，不存在計(jì)算誤差。

在瀑布式級聯(lián)分類器中，對弱分類器和強(qiáng)分類器的訓(xùn)練均是以分類器的最小錯誤率tβ達(dá)到最小的方式，對分類器進(jìn)行訓(xùn)練，而tβ為浮點(diǎn)數(shù)，通常tβ≤0.5，因此，弱分類器和強(qiáng)分類器的模型參數(shù)s、θ、αt和α_th均為浮點(diǎn)數(shù)。通常，為保證檢測正確率，需訓(xùn)練較大規(guī)模的瀑布式級聯(lián)分類器，如設(shè)計(jì)的級聯(lián)分類器包含數(shù)個強(qiáng)分類器，呈級聯(lián)形式；每級強(qiáng)分類器又包含多個弱分類器。因此，分類器模型參數(shù)s、θ、αt和α_th為較龐大的數(shù)據(jù)集合，轉(zhuǎn)化為定點(diǎn)數(shù)并實(shí)現(xiàn)定點(diǎn)運(yùn)算具有較大難度。

2 AdaBoost人臉檢測定點(diǎn)型算法優(yōu)化

本文根據(jù)級聯(lián)分類器計(jì)算特點(diǎn)提出一種浮點(diǎn)計(jì)算轉(zhuǎn)化為定點(diǎn)計(jì)算的方法。該方法在保證計(jì)算精度的前提下，主要對弱分類器和強(qiáng)分類器的模型參數(shù)s、θ、αt和α_th進(jìn)行浮點(diǎn)數(shù)轉(zhuǎn)化為32位整型數(shù)，并將相關(guān)運(yùn)算由浮點(diǎn)運(yùn)算轉(zhuǎn)化為定點(diǎn)運(yùn)算，同時，避免除法運(yùn)算。

2.1 模型參數(shù)分離及部分參數(shù)的獨(dú)立標(biāo)定

弱分類器的計(jì)算過程如式(3)所示，強(qiáng)分類器的計(jì)算過程如式(7)所示。

強(qiáng)分類器是依據(jù)弱分類器的結(jié)果進(jìn)行分類計(jì)算，注意到ht(x)的取值為1或0，即弱分類器中f(x)、s、θ的計(jì)算并不會直接引入到強(qiáng)分類器的計(jì)算中。因此，弱分類器模型參數(shù)的整型化與計(jì)算的定點(diǎn)化可與強(qiáng)分類器的整型化與計(jì)算的定點(diǎn)化可分別獨(dú)立進(jìn)行，采用不同的方案，有利于保持各部分的定點(diǎn)化計(jì)算精度。

2.2 弱分類器模型參數(shù)的整型化與計(jì)算的定點(diǎn)化

該部分需完成模型參數(shù)θ的整型化及弱分類器計(jì)算的定點(diǎn)化。

由式(3)有()pfxpsθ<，其中f(x)為Harr特征，由積分圖像計(jì)算獲得，積分圖像為32位整型數(shù)，因此，f(x)也為32位整型數(shù)；p指示不等號方向，為整型數(shù)，取1或?1； s與θ為浮點(diǎn)數(shù)，可認(rèn)為psθ結(jié)果為兩個浮點(diǎn)數(shù)之積，也為浮點(diǎn)數(shù)?？紤]一個整型數(shù)與一個浮點(diǎn)數(shù)進(jìn)行比較，即()pfxpsθ<，則對sθ進(jìn)行ceil上取整運(yùn)算即可保持計(jì)算精度，即pf(x)

即對于弱分類器模型參數(shù)定點(diǎn)化處理為：

2.3 強(qiáng)分類器模型參數(shù)的整型化與計(jì)算的定點(diǎn)化

該部分需完成模型參數(shù)αt和α_th的整型化及強(qiáng)分類器計(jì)算的定點(diǎn)化計(jì)算。

強(qiáng)分類器的計(jì)算過程如式(7)所示，由于ht(x)取值為1或0，而：

當(dāng)取tβ=0.000 1時，即表示正確檢測率為99.99%，αt=4，所以，可以近似估計(jì)0<αt<10。通常則0< αth<2000。因此，模型參數(shù)αt和α_th的整型化方法為：

αt_int=(int)(αt×1 000 000)<232

αth_int=(int)(αth×1 000 000)<232

3 優(yōu)化算法流程

按照AdaBoost人臉檢測算法構(gòu)建算法流程，完成瀑布式級聯(lián)分類器的設(shè)計(jì)及相關(guān)參數(shù)的訓(xùn)練，并實(shí)現(xiàn)AdaBoost人臉檢測算法原型。本文采用的AdaBoost人臉檢測分類器由22級強(qiáng)分類器級聯(lián)而成，遵循圖3所示的分類原則。每級強(qiáng)分類器包含若干級弱分類器，各強(qiáng)分類器包含弱分類器的級數(shù)分別為：7,15,30,30,50,50,50,100,120,140,160,180,200, 200,200,200, 200,200,200,200,200,200，共計(jì)2 932個弱分類器。具體步驟如下：

1) 對AdaBoost人臉檢測算法相關(guān)參數(shù)進(jìn)行分類。

根據(jù)AdaBoost人臉檢測器中分類器的計(jì)算特點(diǎn)，對強(qiáng)、弱分類器參數(shù)進(jìn)行分類，并獨(dú)立進(jìn)行浮點(diǎn)型參數(shù)的整型化處理。因此，強(qiáng)分類器相關(guān)參數(shù)為αt和α_th；弱分類器參數(shù)為θ、p；相關(guān)計(jì)算量為s。在算法實(shí)現(xiàn)程序中，對相關(guān)參數(shù)做如下定義。

弱分類器：long f1_int：Harr特征值；unsigned long ex_int：積分圖值me；unsigned long sq_int：平方積分圖sq；long sq_long_sqrt：平方根積分圖；long s_thresh：弱分類器閾值。

強(qiáng)分類器：long ac_alphas：強(qiáng)分類器模型參數(shù)；long ac_thresh：強(qiáng)分類器閾值；long value_int：級聯(lián)分類器模型參數(shù)的累加值。

2) 對瀑布式級聯(lián)分類器中弱分類器參數(shù)及運(yùn)算進(jìn)行定點(diǎn)化轉(zhuǎn)換。

在AdaBoost人臉檢測算法原型中，可得到Harr特征f1_int取值范圍為1 175 040～1 175 040；弱分類器θ參數(shù)取值范圍為?195.095 001≤θ≤224.759 003。

對弱分類器的參數(shù)的整型化處理及計(jì)算的定點(diǎn)化處理主要表現(xiàn)為對式(11)的處理，有：

按上文2.2中優(yōu)化方法完成對θ參數(shù)的整型化處理，即：θint=(ceil(θ))4，整型化處理共涉及2 932個參數(shù)，則有：

式中，

針對pad參數(shù)，取624對625逼近，注意：624= 16×39，選擇16的主要原因?yàn)榉奖憧焖儆?jì)算，有：

s的計(jì)算轉(zhuǎn)化為：

則最后的整型化計(jì)算式為：

3) 對瀑布式級聯(lián)分類器中強(qiáng)分類器相關(guān)參數(shù)及運(yùn)算進(jìn)行定點(diǎn)化轉(zhuǎn)換。

對強(qiáng)分類器相關(guān)參數(shù)αt和α_th進(jìn)行整型化處理；按上文2.3中的優(yōu)化方法，取αt=10，即表明弱分類器檢測正確率為99.999 999 99%，為非常高的檢測正確率，因此，可以選擇：

該αt_int參數(shù)整型化處理共涉及2 932個參數(shù)；同樣，可以選擇：

該α_thint參數(shù)整型化處理共涉及22個。

4 實(shí)驗(yàn)結(jié)果

根據(jù)上文所述，完成了對原AdaBoost人臉檢測浮點(diǎn)算法的定點(diǎn)型優(yōu)化，并與原浮點(diǎn)算法進(jìn)行檢測效率評測實(shí)驗(yàn)，實(shí)驗(yàn)平臺為Ti DM648@900 MHz，相同編譯環(huán)境完成算法代碼編譯，采用相同的待檢測圖像，圖像大小為352×288，進(jìn)行全圖像區(qū)域檢測，統(tǒng)計(jì)出檢測出圖像中所有人臉?biāo)钑r間。

圖5 人臉檢測效率測試圖

圖5a待測圖像，原浮點(diǎn)算法完成人臉檢測時間為565.952 ms，定點(diǎn)型優(yōu)化算法完成人臉檢測時間為171.563 ms，約為原浮點(diǎn)算法計(jì)算時間的30.31%；圖5b待測圖像，原浮點(diǎn)算法完成人臉檢測時間為720.981 ms，定點(diǎn)型優(yōu)化算法完成人臉檢測時間為203.708 ms，約為原浮點(diǎn)算法計(jì)算時間的28.25%。

圖6 單人臉對比檢測測試圖

使用圖6進(jìn)行單人臉對比檢測測試，采用文獻(xiàn)[6]方法與本文方法進(jìn)行對比測試。對于單人臉圖像(320×240)，文獻(xiàn)[6]方法檢測時間約為40 ms，文獻(xiàn)[6]也對經(jīng)典AdaBoost檢測進(jìn)行實(shí)驗(yàn)，檢測時間約為67 ms，本文也對經(jīng)典AdaBoost檢測算法進(jìn)行了驗(yàn)證，與文獻(xiàn)[6]所述檢測時間接近，檢測時間約為70 ms；采用本文方法進(jìn)行單人臉檢測，檢測時間約為22 ms，約為AdaBoost經(jīng)典方法檢測時間的30%。與文獻(xiàn)[6]的改進(jìn)AdaBoost人臉檢測算法相比，檢測時間約為50%。

以上實(shí)驗(yàn)表明，本文定點(diǎn)優(yōu)化算法人臉檢測耗時約為原浮點(diǎn)算法的30%左右。

5 結(jié) 束 語

本文從AdaBoost人臉檢測原型算法出發(fā)，提出一種原型算法的定點(diǎn)型優(yōu)化方法，從AdaBoost人臉檢測算法的瀑布式級聯(lián)分類器入手，分析了強(qiáng)分類器及弱分類器的計(jì)算特點(diǎn)，對各自計(jì)算過程進(jìn)行分解，實(shí)現(xiàn)了強(qiáng)、弱分類器相關(guān)參數(shù)的有效分離，即可獨(dú)立進(jìn)行定點(diǎn)型標(biāo)定；再利用圖像積分圖計(jì)算特點(diǎn)，完成弱分類器相關(guān)浮點(diǎn)參數(shù)的定點(diǎn)處理；最后，利用強(qiáng)分類器浮點(diǎn)運(yùn)算特點(diǎn)及計(jì)算精度要求完成強(qiáng)分類器計(jì)算過程及相關(guān)模型參數(shù)的定點(diǎn)型轉(zhuǎn)化。實(shí)驗(yàn)證明，該方法在保持原浮點(diǎn)型算法檢測正確率的基礎(chǔ)，實(shí)現(xiàn)了算法的定點(diǎn)型處理優(yōu)化。經(jīng)實(shí)驗(yàn)測試，優(yōu)化算法計(jì)算耗時約為原浮點(diǎn)算法的30%左右，有效地提高了檢測算法的實(shí)時性能，并利于后期的SIMD優(yōu)化。

[1] VIOLA P, MICHAEL J. Rapid object detection using a boosted cascade of simple features[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Kauai, Hawaii, USA: IEEE, 2001.

[2] KEARNS M, VALIANT L G. Learning boolean formulae for finite automata is as hard as factoring[R]. Cambridge: Aiken Computation Laboratory, Harvard University, TR-1488, 1998.

[3] ABDEL-MOTTALEB M, ELGAMMAL A. Face detection in complex environments from color images[C]// Proceedings of IEEE Conference on Image Processing. [S.l.]: IEEE, 1999, 3: 622-626.

[4] KARLEKAR J, DESAI U B. Finding faces in color images using wavelet transform[C]//Proceedings of IEEE Conference on Image Analysis and Processing. Venice, Italy: IEEE, 1999: 1085-1088.

[5] ZHANG Z Q, ZHU L, LI S Z, et al. Real-time multi-view face detection[C]//Proceedings of The 5th International Conference on Automatic Face and Gesture Recognition. Washington, DC, USA: [s.n.], 2002.

[6] 索璐靜, 陸小鋒, 陸亨立, 等. 實(shí)時視頻中的快速人臉檢測方法[J]. 計(jì)算機(jī)工程, 2011, 37(20): 166-168. SUO Lu-jing, LU Xiao-feng, LU Heng-li, et al. Fast face detection method in real-time video[J]. Computer Engineering, 2011, 37(20): 166-168.

[7] 劉曉克, 孫燮華, 周永霞. 基于新Haar-like特種的多角度人臉檢測[J]. 計(jì)算機(jī)工程, 2009, 35(19): 195-197. LIU Xiao-ke, SUN Xie-hua, ZHOU Yong-xia. Multi-angle face detection based on new Haar-like feature[J]. Computer Engineering, 2009, 35(19): 195-197.

[8] 唐奇, 蘇光大. 基于AdaBoost算法的硬件實(shí)時人臉檢測[J]. 計(jì)算機(jī)工程, 2008, 34(7): 248-250. TANG Qi, SU Guang-da. Real time hardware face detection based on AdaBoost algorithm[J]. Computer Engineering, 2008, 34(7): 248-250.

[9] 徐建軍, 張蓉, 畢篤彥, 等. 一種新的AdaBoost視頻跟蹤算法[J]. 控制與決策, 2012, 27(5): 681-685. XU Jian-jun, ZHANG Rong, BI Du-yan, et al. An new AdaBoost video tracking algorithm[J]. Control and Decision, 2012, 27(5): 681-685.

[10] 張彥峰, 何佩琨. 一種改進(jìn)的AdaBoost算法——M-asy AdaBoost[J]. 北京理工大學(xué)學(xué)報(bào), 2011, 31(1): 64-68, 73. ZHANG Yan-feng, HE Pei-kun. A revised AdaBoost algorithm—M-asy AdaBoost[J]. Transactions of Beijing Institute of Technology, 2011, 31(1): 64-68, 73.

[11] 姚旭, 王曉丹, 張玉璽, 等. 基于AdaBoost和匹配追蹤的選擇性集成算法[J]. 控制與決策, 2014, 29(2): 208-214. YAO Xu, WANG Xiao-dan, ZHANG Yu-xi, et al. Selective ensemble algorithm based on AdaBoost and matching pursuit[J]. Control and Decision, 2014, 29(2): 208-214.

編輯漆 蓉

Fixed-Point Optimization Algorithm of AdaBoost Face Detection

ZHOU Zhen-hua
(Hydrology and Water Resources Bureau of Henan Province Zhengzhou 450003)

A new fixed-point optimized algorithm for AdaBoost face detection is proposed. Based on the AdaBoost face detection prototype algorithm, the characteristics of classification calculation of the weak classifiers and strong classifiers in waterfall cascade classifier is analyzed, the computing process of the weak classifiers and the strong classifiers is effectively decomposed, and the effective separation and calibration of the model parameters of the strong classifiers and the weak classifiers are realized. By using integral image and the calculation characteristics of the weak classifier and according to the accuracy requirements of the floating point calculation of strong classifiers, the proposed algorithm realizes the classifier calculation and the transformation of related model parameters. The AdaBoost algorithm has the calculation accuracy approximate to that of the original floating-point algorithm and therefore maintains the higher accuracy of face detection, which will be beneficial for the optimization of SIMD parallel computing method and the transplantation and optimization of the algorithm in the fixed point type of embedded equipments.

AdaBoost; face detection; integral image; strong classifier; weak classifier

TP391.41

A doi:10.3969/j.issn.1001-0548.2015.04.019

2014 ? 06? 03；

2014 ? 09 ?12

周振華(1969 ? )，男，高級工程師，主要從事圖像處理及算法優(yōu)化方面的研究.