Viola-jones人臉檢測算法是一種基于滑動窗口的目標檢測算法，但它卻克服了滑動窗口檢測帶來的低效問題，可以用于實時人臉檢測，主要歸功于以下三點：

1. 利用一種新的數(shù)據(jù)結(jié)構(gòu)”積分圖像“來快速計算Haar-like特征

2. 利用adaboost對候選特征進行篩選，找出具有更強分辨力的特征

3. 利用attention cascade將更多更為細致的計算應用至感興趣的區(qū)域

我參考論文[1]實現(xiàn)了Viola Jones中提到的attention cascade檢測框架，此處是github傳送門。

下面進一步詳細介紹整個檢測原理。

基于滑窗的目標檢測

基于滑窗的目標檢測基本原理很簡單，首先構(gòu)建一個classifier（分類器），以人臉檢測為例，分類器的工作是判斷給定大小的圖像的是否為人臉，用該分類器從左至右從上到下掃描整幅圖像，掃描獲取的部分圖像稱為子窗（文章中子窗大小為24x24像素），當分類器判斷子窗是人臉時，即完成了人臉檢測。

這樣處理有個問題，如果圖像中包含的人臉變大了，此時采用固定大小的子窗就無法進行檢測。通常有兩種解決方法，1. 采用image-pyramid（圖像金字塔），也就是通過resize獲得多種不同大小圖像并堆疊在一起，用固定大小分類器同時對所有圖像進行掃描；2. 采用不同大小的分類器進行掃描。文章中用到的是第二種方法，盡管如此，雖然避免了調(diào)整圖像大小帶來的計算開銷，但不同大小的分類器意味著有更多子窗需要進行處理。

如何構(gòu)建一個足夠快的分類器來對每個子窗進行快速判斷。

Haar-like特征

分類器的構(gòu)建有兩種方式，一種是pixel-based（基于像素），另一種是feature-based（基于特征）。當把神經(jīng)網(wǎng)絡作為圖像分類器時，輸入是圖像的像素值，即基于像素的分類器。用圖像像素作為輸入不包含任何和待分類目標有關(guān)的特定信息，往往訓練這種分類器需要大量數(shù)據(jù)，并且分類過程較慢?；谔卣鞯姆诸惼骶褪窍柔槍D像進行特征提?。℉OG特征，SIFT特征等），再利用獲取的特征進行分類。這種分類器不需要大量訓練數(shù)據(jù)，且計算量一般會在特征計算部分，相對較小。

文章采用的是基于特征的分類器，選取了一種較為簡單的特征即haar-like特征。利用矩形個數(shù)對可以將haar-like特征分為三類，分別由兩個，三個，和四個大小相同的矩形組成。全部列舉出來可以分為以下(a)(b)(c)(d)(e)五類（注意是五類不是五個，具體有多少個haar-like特征是由子窗大小決定的）。如下圖所示（文章[1]中的圖）。

當子窗大小給定后，我們可以用五個參數(shù)唯一確定一個haar-like特征，即特征種類（a/b/c/d/e），左上角x軸坐標，左上角y軸坐標，矩形的長，矩形的寬。對應的特征值等于位于白色矩形框中像素值總和減去位于黑色矩形框中的像素值總和。文章中用到的子窗大小為24x24像素，可以計算出來總共有162336個特征（把在子窗中所有可能位置和可能大小的特征全部列舉出來）。利用haar-like特征進行分類只需兩步：

1. 計算對應的特征值；

2. 將特征值與門限進行比較（此處需考慮極性，即大于門限的樣本為正還是負）獲得分類結(jié)果。

haar-like特征有兩個優(yōu)點，第一是它是scale-invariant(不隨圖片大小而改變)的，第二是可以通過積分圖像快速計算。簡單的說下第一點的含義，例如我們用24x24像素的訓練樣本訓練獲取一組haar-like特征和對應的門限值，當對圖像進行掃描時，子窗大小調(diào)整為SxS像素，此時只需將特征中的矩形大小按同樣比例進行縮放（門限值同樣需要縮放），計算所得的特征值依然是有效的。
積分圖像是受卷積的微分性質(zhì)啟發(fā)而定義一種數(shù)據(jù)結(jié)構(gòu)。積分圖像定義：

其中 為積分圖像，為原圖像。積分圖像中位置處的像素值等于原圖中位于的左側(cè)和上方的所有像素值之和。有了積分圖像我們就可以快速計算haar-like特征，以特征（a）為例，如下圖所示。

S1到S6是積分圖像在這六個頂點上的值。該特征值等于位于A中的像素總和減去位于B中的像素總和，而A中像素總和等于S5+S1-S2-S4，B中像素總和等于S6+S2-S3-S5，并且無論矩形多大，我們總能在固定時間內(nèi)計算出特征值（6次索引操作和少量的加法乘法計算）。積分圖像只需計算一次后續(xù)可以一直使用，事實上在算法實現(xiàn)時，我們只需保存樣本的積分圖像，原圖像反而不用保存。

現(xiàn)在找到了一類特征用于構(gòu)建分類器，和快速計算該類特征的方法。分類器是由一組特征構(gòu)成的，而不是一個，如何找到一組有效的特征。

AdaBoost算法

文章列舉了前人的一些特征選取方法（此處就不列舉了），它們雖然取得了一定的效果，但最終選出來的特征數(shù)量還是太多。文章將adaBoost算法用于特征選取（創(chuàng)新點），即每次訓練的弱分類器的過程看做特征選取的過程，一次從162336個特征中選取一個特征（同時還包括了對應的門限值，極性，加權(quán)誤差）。

adaboost算法就不詳細介紹了，它的基本思想是訓練一系列“弱”分類器，組成一個committee（即每個弱分類器都有投票權(quán)，但是權(quán)重不同，加權(quán)誤差越小的弱分類器權(quán)重越大）。adaboost采用迭代訓練方式，給定一個t階committee，如何尋找第t+1個弱分類器和對應的權(quán)重，以最小化在一定分布下的訓練樣本的加權(quán)指數(shù)損失。這個優(yōu)化過程可以轉(zhuǎn)換為對訓練樣本的分布進行調(diào)整（即增大上一輪錯誤判斷的樣本的權(quán)重，減小正確判斷的樣本權(quán)重），在調(diào)整后的樣本分布下尋找最小化加權(quán)0-1損失的弱分類器并計算對應的加權(quán)0-1損失。

可以利用adaboost找到一組特征構(gòu)成分類器，使得該分類器有極高的準確率和召回率（這種分類器勢必會有較大的計算量），這樣會導致圖像中的每一個子窗都享有同等的計算量，掃描一整幅圖會有幾十萬甚至上百萬子窗，總體計算量依然很大。實際上一幅圖像中只有極少可能包含人臉的位置是我們感興趣的，其他不包含人臉的子窗我們希望能夠快速篩除，將更精細的計算用于包含人臉的子窗。

Attention cascade

文章引入了attention-cascade的機制（注意力級聯(lián)），即訓練多個分類器進行級聯(lián)，替代單一的分類器。結(jié)構(gòu)如下圖所示（文章[3]中的圖）。

上圖所示的分類器有三級，上一級的輸出是下一級的輸入，只有預測為正的樣本才能傳遞給下一級，預測為負的樣本直接舍棄。大部分非人臉子窗往往在前幾級分類器就被舍棄，這樣使得掃描每個子窗所需的平均計算量大大減小。

分類器是一級一級訓練之后級聯(lián)起來的，訓練分類器時，整個級聯(lián)分類器的假負率（fpr_overall）有一個訓練目標（文章[1]中設(shè)置為10e-7），同時每一級有一對訓練目標，即假正率和假負率。每級分類器訓練的思想是在假負率極低的情況下（文章[1]中設(shè)置為0.005）盡量得到一個較低的假正率（文章中[1]中設(shè)置為0.5），即我們保證在正樣本盡可能多的通過該級分類器的情況下盡量篩除更多的負樣本。文章[3]通過一個松弛量來調(diào)節(jié)假正率和假負率。

下一級用到的訓練數(shù)據(jù)是由所有的正樣本和上一級輸出的假正樣本組成的，這樣訓練的好處是可以讓處于級聯(lián)后半部分的分類器“看到”更多負樣本數(shù)據(jù)，缺點是訓練后期假正樣本很難獲取，訓練時間會比較長。

盡管我們獲取了一個級聯(lián)分類器，但依然不能保證對同一幅圖中的一張人臉只會檢測到一次（子窗相對人臉有所便宜或者縮放子窗大小都可能導致重復檢測），如何消除重復檢測，獲得更好的檢測效果。

檢測后處理

文章[3]中說的較為簡略，主要是針對檢測框構(gòu)建并查集，并對并查集中的候選框求平均得出最終的檢測框。

文章[1]中是采用連通分量算法，計算每種大小檢測框的置信度，根據(jù)置信度選取最終結(jié)果，但前提是檢測器在圖像中掃描的步進必須是1個像素，處理時間可能會比較長。

算法不足之處

只能用于正臉檢測，如果人臉朝屏幕內(nèi)外或者在屏幕平面上旋轉(zhuǎn)均有可能失效
在背景較亮，人臉較暗的情況下可能失效。
在有遮擋的情況下大概率失效。

參考文章

1. An Analysis of the Viola-Jones Face Detection Algorithm

2. Robust Real-Time Face Detection

3. Rapid Object Detection using a Boosted Cascade of Simple Features