AdaBoost人臉檢測定點型優化算法

周振華

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

AdaBoost人臉檢測定點型優化算法

周振華

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

提出一種AdaBoost人臉檢測的定點型優化算法，該算法以AdaBoost人臉檢測原型算法為基礎，分析了Cascade瀑布式級聯分類器中弱分類器與強分類器分類計算的特點，有效分解了弱分類器與強分類器的計算過程，從而現實了強分類器與弱分類器相關模型參數有效分離標定。優化算法進一步利用圖像積分圖及弱分類器計算特點，完成對弱分類器計算過程及相關模型參數的定點型轉化；同時，利用強分類器浮點的計算精度要求，完成強分類器計算過程及相關模型參數的定點型轉化。該定點型AdaBoost人臉檢測方法計算精度逼近原浮點型算法計算精度，保持了較高的人臉檢測正確率，并利于后期的SIMD并行計算方法優化，同時，也利于算法在定點型嵌入式設備上的移植與優化。

AdaBoost; 人臉檢測; 圖像積分圖; 強分類器; 弱分類器

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

1 AdaBoost人臉檢測算法

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

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

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

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

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

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

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

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

1.1 Harr特征計算

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

類型0計算方法：

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

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

類型1計算方法：

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

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

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

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

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

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 瀑布式級聯分類器

瀑布式級聯分類器由機器學習訓練得到，其級聯形式如圖4所示，包含數級強分類器(節點分類器)，每級強分類器又包含不同級數的弱分類器。所選取的Harr特征先進行弱分類器分類，分類結果經強分類器加權求和得到該級強分類器的分類結果。如不是人臉，將退出，并做出“不是人臉”的判斷；如是人臉，將進入下一級分類器再進行分類判斷，直至完成所有分類器的分類判斷，即所有強分類器均判定為人臉，則瀑布式級聯分類器做出最終判斷“該區域為人臉”。

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

式中，

式中，

圖4 基于AdaBoost算法的級聯式人臉檢測器

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

強分類器利用若干個弱分類器進行分類，強分類器可表示為：

其中，式中，ht(x)為弱分類器的分類結果；αt為對應強分類器的模型參數；α_th為該強分類器閾值。αt和α_th均通過大量樣本訓練得到，為浮點數。

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

在瀑布式級聯分類器中，對弱分類器和強分類器的訓練均是以分類器的最小錯誤率tβ達到最小的方式，對分類器進行訓練，而tβ為浮點數，通常tβ≤0.5，因此，弱分類器和強分類器的模型參數s、θ、αt和α_th均為浮點數。通常，為保證檢測正確率，需訓練較大規模的瀑布式級聯分類器，如設計的級聯分類器包含數個強分類器，呈級聯形式；每級強分類器又包含多個弱分類器。因此，分類器模型參數s、θ、αt和α_th為較龐大的數據集合，轉化為定點數并實現定點運算具有較大難度。

2 AdaBoost人臉檢測定點型算法優化

本文根據級聯分類器計算特點提出一種浮點計算轉化為定點計算的方法。該方法在保證計算精度的前提下，主要對弱分類器和強分類器的模型參數s、θ、αt和α_th進行浮點數轉化為32位整型數，并將相關運算由浮點運算轉化為定點運算，同時，避免除法運算。

2.1 模型參數分離及部分參數的獨立標定

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

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

2.2 弱分類器模型參數的整型化與計算的定點化

該部分需完成模型參數θ的整型化及弱分類器計算的定點化。

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

即對于弱分類器模型參數定點化處理為：

2.3 強分類器模型參數的整型化與計算的定點化

該部分需完成模型參數αt和α_th的整型化及強分類器計算的定點化計算。

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

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

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

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

3 優化算法流程

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

1) 對AdaBoost人臉檢測算法相關參數進行分類。

根據AdaBoost人臉檢測器中分類器的計算特點，對強、弱分類器參數進行分類，并獨立進行浮點型參數的整型化處理。因此，強分類器相關參數為αt和α_th；弱分類器參數為θ、p；相關計算量為s。在算法實現程序中，對相關參數做如下定義。

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

強分類器：long ac_alphas：強分類器模型參數；long ac_thresh：強分類器閾值；long value_int：級聯分類器模型參數的累加值。

2) 對瀑布式級聯分類器中弱分類器參數及運算進行定點化轉換。

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

對弱分類器的參數的整型化處理及計算的定點化處理主要表現為對式(11)的處理，有：

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

式中，

針對pad參數，取624對625逼近，注意：624= 16×39，選擇16的主要原因為方便快速計算，有：

s的計算轉化為：

則最后的整型化計算式為：

3) 對瀑布式級聯分類器中強分類器相關參數及運算進行定點化轉換。

對強分類器相關參數αt和α_th進行整型化處理；按上文2.3中的優化方法，取αt=10，即表明弱分類器檢測正確率為99.999 999 99%，為非常高的檢測正確率，因此，可以選擇：

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

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

4 實驗結果

根據上文所述，完成了對原AdaBoost人臉檢測浮點算法的定點型優化，并與原浮點算法進行檢測效率評測實驗，實驗平臺為Ti DM648@900 MHz，相同編譯環境完成算法代碼編譯，采用相同的待檢測圖像，圖像大小為352×288，進行全圖像區域檢測，統計出檢測出圖像中所有人臉所需時間。

圖5 人臉檢測效率測試圖

圖5a待測圖像，原浮點算法完成人臉檢測時間為565.952 ms，定點型優化算法完成人臉檢測時間為171.563 ms，約為原浮點算法計算時間的30.31%；圖5b待測圖像，原浮點算法完成人臉檢測時間為720.981 ms，定點型優化算法完成人臉檢測時間為203.708 ms，約為原浮點算法計算時間的28.25%。

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

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

以上實驗表明，本文定點優化算法人臉檢測耗時約為原浮點算法的30%左右。

5 結 束 語

本文從AdaBoost人臉檢測原型算法出發，提出一種原型算法的定點型優化方法，從AdaBoost人臉檢測算法的瀑布式級聯分類器入手，分析了強分類器及弱分類器的計算特點，對各自計算過程進行分解，實現了強、弱分類器相關參數的有效分離，即可獨立進行定點型標定；再利用圖像積分圖計算特點，完成弱分類器相關浮點參數的定點處理；最后，利用強分類器浮點運算特點及計算精度要求完成強分類器計算過程及相關模型參數的定點型轉化。實驗證明，該方法在保持原浮點型算法檢測正確率的基礎，實現了算法的定點型處理優化。經實驗測試，優化算法計算耗時約為原浮點算法的30%左右，有效地提高了檢測算法的實時性能，并利于后期的SIMD優化。

[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] 索璐靜, 陸小鋒, 陸亨立, 等. 實時視頻中的快速人臉檢測方法[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]. 計算機工程, 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算法的硬件實時人臉檢測[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] 張彥峰, 何佩琨. 一種改進的AdaBoost算法——M-asy AdaBoost[J]. 北京理工大學學報, 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 ? )，男，高級工程師，主要從事圖像處理及算法優化方面的研究.