Haar特征與積分圖

1. Adaboost方法的引入

1.1 Boosting方法的提出和發(fā)展

        在了解Adaboost方法之前，先了解一下Boosting方法。

        回答一個是與否的問題，隨機猜測可以獲得50%的正確率。如果一種方法能獲得比隨機猜測稍微高一點的正確率，則就可以稱該得到這個方法的過程為弱學習；如果一個方法可以顯著提高猜測的正確率，則稱獲取該方法的過程為強學習。1994年，Kearns和Valiant證明，在Valiant的PAC（Probably ApproximatelyCorrect）模型中，只要數(shù)據(jù)足夠多，就可以將弱學習算法通過集成的方式提高到任意精度。實際上，1990年，SChapire就首先構(gòu)造出一種多項式級的算法，將弱學習算法提升為強學習算法，就是最初的Boosting算法。Boosting意思為提升、加強，現(xiàn)在一般指將弱學習提升為強學習的一類算法。1993年，Drucker和Schapire首次以神經(jīng)網(wǎng)絡(luò)作為弱學習器，利用Boosting算法解決實際問題。前面指出，將弱學習算法通過集成的方式提高到任意精度，是Kearns和Valiant在1994年才證明的，雖然Boosting方法在1990年已經(jīng)提出，但它的真正成熟，也是在1994年之后才開始的。1995年，Freund提出了一種效率更高的Boosting算法。

1.2 AdaBoost算法的提出

        1995年，F(xiàn)reund和Schapire提出了Adaboost算法，是對Boosting算法的一大提升。Adaboost是Boosting家族的代表算法之一，全稱為Adaptive Boosting。Adaptively，即適應地，該方法根據(jù)弱學習的結(jié)果反饋適應地調(diào)整假設(shè)的錯誤率，所以Adaboost不需要預先知道假設(shè)的錯誤率下限。也正因為如此，它不需要任何關(guān)于弱學習器性能的先驗知識，而且和Boosting算法具有同樣的效率，所以在提出之后得到了廣泛的應用。

首先，Adaboost是一種基于級聯(lián)分類模型的分類器。級聯(lián)分類模型可以用下圖表示：

級聯(lián)分類器介紹：級聯(lián)分類器就是將多個強分類器連接在一起進行操作。每一個強分類器都由若干個弱分類器加權(quán)組成，

例如，有些強分類器可能包含10個弱分類器，有些則包含20個弱分類器，一般情況下一個級聯(lián)用的強分類器包含20個左右的弱分類器，然后在將10個強分類器級聯(lián)起來，就構(gòu)成了一個級聯(lián)強分類器，這個級聯(lián)強分類器中總共包括200弱分類器。因為每一個強分類器對負樣本的判別準確度非常高，所以一旦發(fā)現(xiàn)檢測到的目標位負樣本，就不在繼續(xù)調(diào)用下面的強分類器，減少了很多的檢測時間。因為一幅圖像中待檢測的區(qū)域很多都是負樣本，這樣由級聯(lián)分類器在分類器的初期就拋棄了很多負樣本的復雜檢測，所以級聯(lián)分類器的速度是非?？斓?；只有正樣本才會送到下一個強分類器進行再次檢驗，這樣就保證了最后輸出的正樣本的偽正(false positive)的可能性非常低。

 也有一些情況下不適用級聯(lián)分類器，就簡單的使用一個強分類器的情況，這種情況下一般強分類器都包含200個左右的弱分類器可以達到最佳效果。不過級聯(lián)分類器的效果和單獨的一個強分類器差不多，但是速度上卻有很大的提升。

 級聯(lián)結(jié)構(gòu)分類器由多個弱分類器組成，每一級都比前一級復雜。每個分類器可以讓幾乎所有的正例通過，同時濾除大部分負例。這樣每一級的待檢測正例就比前一級少，排除了大量的非檢測目標，可大大提高檢測速度。

其次，Adaboost是一種迭代算法。初始時，所有訓練樣本的權(quán)重都被設(shè)為相等，在此樣本分布下訓練出一個弱分類器。在第（  =1,2,3, …T，T為迭代次數(shù)）次迭代中，樣本的權(quán)重由第  -1次迭代的結(jié)果而定。在每次迭代的最后，都有一個調(diào)整權(quán)重的過程，被分類錯誤的樣本將得到更高的權(quán)重。這樣分錯的樣本就被突出出來，得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進行訓練，得到新的弱分類器。經(jīng)過T次循環(huán)，得到T個弱分類器，把這T個弱分類器按照一定的權(quán)重疊加起來，就得到最終的強分類器。

2. 矩形特征

2.1 Haar特征\矩形特征

AdaBoost算法的實現(xiàn)，采用的是輸入圖像的矩形特征，也叫Haar特征。下面簡要介紹矩形特征的特點。

影響Adaboost檢測訓練算法速度很重要的兩方面是特征的選取和特征值的計算。臉部的一些特征可以由矩形特征簡單地描繪。用圖2示范：

上圖中兩個矩形特征，表示出人臉的某些特征。比如中間一幅表示眼睛區(qū)域的顏色比臉頰區(qū)域的顏色深，右邊一幅表示鼻梁兩側(cè)比鼻梁的顏色要深。同樣，其他目標，如眼睛等，也可以用一些矩形特征來表示。使用特征比單純地使用像素點具有很大的優(yōu)越性，并且速度更快。

在給定有限的數(shù)據(jù)情況下，基于特征的檢測能夠編碼特定區(qū)域的狀態(tài)，而且基于特征的系統(tǒng)比基于象素的系統(tǒng)要快得多。
矩形特征對一些簡單的圖形結(jié)構(gòu)，比如邊緣、線段，比較敏感，但是其只能描述特定走向（水平、垂直、對角）的結(jié)構(gòu)，因此比較粗略。如上圖，臉部一些特征能夠由矩形特征簡單地描繪，例如，通常，眼睛要比臉頰顏色更深；鼻梁兩側(cè)要比鼻梁顏色要深；嘴巴要比周圍顏色更深。

對于一個 24×24 檢測器，其內(nèi)的矩形特征數(shù)量超過160,000 個，必須通過特定算法甄選合適的矩形特征，并將其組合成強分類器才能檢測人臉。

常用的矩形特征有三種：兩矩形特征、三矩形特征、四矩形特征，如圖：

由圖表可以看出，兩矩形特征反映的是邊緣特征，三矩形特征反映的是線性特征、四矩形特征反映的是特定方向特征。

特征模板的特征值定義為：白色矩形像素和減去黑色矩形像素和。接下來，要解決兩個問題，1：求出每個待檢測子窗口中的特征個數(shù)。2：求出每個特征的特征值。

子窗口中的特征個數(shù)即為特征矩形的個數(shù)。訓練時，將每一個特征在訓練圖像子窗口中進行滑動計算，獲取各個位置的各類矩形特征。在子窗口中位于不同位置的同一類型矩形特征，屬于不同的特征。可以證明，在確定了特征的形式之后，矩形特征的數(shù)量只與子窗口的大小有關(guān)^[11]。在24×24的檢測窗口中，矩形特征的數(shù)量約為160,000個。

特征模板可以在子窗口內(nèi)以“任意”尺寸“任意”放置，每一種形態(tài)稱為一個特征。找出子窗口所有特征，是進行弱分類訓練的基礎(chǔ)。

2.2子窗口內(nèi)的條件矩形，矩形特征個數(shù)的計算

如圖所示的一個m*m大小的子窗口，可以計算在這么大的子窗口內(nèi)存在多少個矩形特征。

以 m×m 像素分辨率的檢測器為例，其內(nèi)部存在的滿足特定條件的所有矩形的總數(shù)可以這樣計算：
對于 m×m 子窗口，我們只需要確定了矩形左上頂點A(x1,y1)和右下頂點B(x2,63) ，即可以確定一個矩形；如果這個矩形還必須滿足下面兩個條件（稱為(s, t)條件，滿足(s, t)條件的矩形稱為條件矩形）：

1) x 方向邊長必須能被自然數(shù)s 整除（能均等分成s 段）；
2) y 方向邊長必須能被自然數(shù)t 整除（能均等分成t 段）；
則 ， 這個矩形的最小尺寸為s×t 或t×s， 最大尺寸為[m/s]·s×[m/t]·t 或[m/t]·t×[m/s]·s；其中[ ]為取整運算符。

2.3條件矩形的數(shù)量

我們通過下面兩步就可以定位一個滿足條件的矩形：

由上分析可知，在m×m 子窗口中，滿足(s, t)條件的所有矩形的數(shù)量為：

實際上，(s, t)條件描述了矩形特征的特征，下面列出了不同矩形特征對應的(s, t)條件：

下面以 24×24 子窗口為例，具體計算其特征總數(shù)量：

下面列出了，在不同子窗口大小內(nèi)，特征的總數(shù)量：

3. 積分圖

3.1 積分圖的概念

在獲取了矩形特征后，要計算矩形特征的值。Viola等人提出了利用積分圖求特征值的方法。積分圖的概念可用圖3表示：

坐標A(x,y)的積分圖是其左上角的所有像素之和（圖中的陰影部分）。定義為：

其中ii(x,y)表示積分圖，i(x,y)表示原始圖像，對于彩色圖像，是此點的顏色值；對于灰度圖像，是其灰度值，范圍為0~255。

在上圖中，A(x,y)表示點(x,y)的積分圖；s(x,y)表示點(x,y)的y方向的所有原始圖像之和。積分圖也可以用公式（2）和公式（3）得出：

3.2 利用積分圖計算特征值

3.3 計算特征值

由上一節(jié)已經(jīng)知道，一個區(qū)域的像素值，可以由該區(qū)域的端點的積分圖來計算。由前面特征模板的特征值的定義可以推出，矩形特征的特征值可以由特征端點的積分圖計算出來。以“兩矩形特征”中的第二個特征為例，如下圖，使用積分圖計算其特征值：

級聯(lián)分類器與檢測過程

1. 弱分類器

在確定了訓練子窗口中的矩形特征數(shù)量和特征值后，需要對每一個特征f ，訓練一個弱分類器h(x,f,p,O) 。

在CSDN里編輯公式太困難了，所以這里和公式有關(guān)的都用截圖了。

特別說明：在前期準備訓練樣本的時候，需要將樣本歸一化和灰度化到20*20的大小，這樣每個樣本的都是灰度圖像并且樣本的大小一致，保證了每一個Haar特征（描述的是特征的位置）都在每一個樣本中出現(xiàn)。

2. 訓練強分類器

在訓練強分類器中，T表示的是強分類器中包含的弱分類器的個數(shù)。當然，如果是采用級聯(lián)分類器，這里的強分類器中的弱分類器的個數(shù)可能會比較少，多個強分類器在級聯(lián)起來。

在c(2)步驟中，“每個特征f”指的是在20*20大小的訓練樣本中所有的可能出現(xiàn)的矩形特征，大概要有80,000中，所有的這些都要進行計算。也就是要計算80,000個左右的弱分類器，在選擇性能好的分類器。

訓練強分類器的步驟如圖：

3. 再次介紹弱分類器以及為什么可以使用Haar特征進行分類

對于本算法中的矩形特征來說，弱分類器的特征值f(x)就是矩形特征的特征值。由于在訓練的時候，選擇的訓練樣本集的尺寸等于檢測子窗口的尺寸，檢測子窗口的尺寸決定了矩形特征的數(shù)量，所以訓練樣本集中的每個樣本的特征相同且數(shù)量相同，而且一個特征對一個樣本有一個固定的特征值。

對于理想的像素值隨機分布的圖像來說，同一個矩形特征對不同圖像的特征值的平均值應該趨于一個定值k。
這個情況，也應該發(fā)生在非人臉樣本上，但是由于非人臉樣本不一定是像素隨機的圖像，因此上述判斷會有一個較大的偏差。

對每一個特征，計算其對所有的一類樣本(人臉或者非人臉)的特征值的平均值，最后得到所有特征對所有一類樣本的平均值分布。

下圖顯示了20×20 子窗口里面的全部78,460 個矩形特征對全部2,706個人臉樣本和4,381 個非人臉樣本6的特征值平均數(shù)的分布圖。由分布看出，特征的絕大部分的特征值平均值都是分布在0 前后的范圍內(nèi)。出乎意料的是，人臉樣本與非人臉樣本的分布曲線差別并不大，不過注意到特征值大于或者小于某個值后，分布曲線出現(xiàn)了一致性差別，這說明了絕大部分特征對于識別人臉和非人臉的能力是很微小的，但是存在一些特征及相應的閾值，可以有效地區(qū)分人臉樣本與非人臉樣本。

為了更好地說明問題，我們從78,460 個矩形特征中隨機抽取了兩個特征A和B，這兩個特征遍歷了2,706 個人臉樣本和4,381 個非人臉樣本，計算了每張圖像對應的特征值，最后將特征值進行了從小到大的排序，并按照這個新的順序表繪制了分布圖如下所示：

可以看出，矩形特征A在人臉樣本和非人臉樣本中的特征值的分布很相似，所以區(qū)分人臉和非人臉的能力很差。

下面看矩形特征B在人臉樣本和非人臉樣本中特征值的分布：

可以看出，矩形特征B的特征值分布，尤其是0點的位置，在人臉樣本和非人臉樣本中差別比較大，所以可以更好的實現(xiàn)對人臉分類。

由上述的分析，閾值q 的含義就清晰可見了。而方向指示符p 用以改變不等號的方向。

一個弱學習器（一個特征）的要求僅僅是：它能夠以稍低于50%的錯誤率來區(qū)分人臉和非人臉圖像，因此上面提到只能在某個概率范圍內(nèi)準確地進行區(qū)分就
已經(jīng)完全足夠。按照這個要求，可以把所有錯誤率低于50%的矩形特征都找到（適當?shù)剡x擇閾值，對于固定的訓練集，幾乎所有的矩形特征都可以滿足上述要求）。每輪訓練，將選取當輪中的最佳弱分類器（在算法中，迭代T 次即是選擇T 個最佳弱分類器），最后將每輪得到的最佳弱分類器按照一定方法提升（Boosting）為強分類器

4 弱分類器的訓練及選取

訓練一個弱分類器（特征f）就是在當前權(quán)重分布的情況下，確定f 的最優(yōu)閾值，使得這個弱分類器（特征f）對所有訓練樣本的分類誤差最低。
選取一個最佳弱分類器就是選擇那個對所有訓練樣本的分類誤差在所有弱分類器中最低的那個弱分類器（特征）。

對于每個特征 f，計算所有訓練樣本的特征值，并將其排序。通過掃描一遍排好序的特征值，可以為這個特征確定一個最優(yōu)的閾值，從而訓練成一個弱分類器。具體來說，對排好序的表中的每個元素，計算下面四個值：

5. 強分類器

注意，這里所說的T=200個弱分類器，指的是非級聯(lián)的強分類器。若果是用級聯(lián)的強分類器，則每個強分類器的弱分類器的個數(shù)會相對較少。

一般學術(shù)界所說的級聯(lián)分類器，都是指的是級聯(lián)強分類器，一般情況有10個左右的強分類器，每個強分類有10-20個弱分類器。當然每一層的強分類器中弱分類器的個數(shù)可以不相等，可以根據(jù)需要在前面的層少放一些弱分類器，后面的層次逐漸的增加弱分類器的個數(shù)。

6. 圖像檢測過程

在對輸入圖像進行檢測的時候，一般輸入圖像都會比20*20的訓練樣本大很多。在Adaboost 算法中采用了擴大檢測窗口的方法，而不是縮小圖片。

為什么擴大檢測窗口而不是縮小圖片呢，在以前的圖像檢測中，一般都是將圖片連續(xù)縮小十一級，然后對每一級的圖像進行檢測，最后在對檢測出的每一級結(jié)果進行匯總。然而，有個問題就是，使用級聯(lián)分類器的AdaBoost的人臉檢測算法的速度非常的快，不可能采用圖像縮放的方法，因為僅僅是把圖像縮放11級的處理，就要消耗一秒鐘至少，已經(jīng)不能達到Adaboost 的實時處理的要求了。

因為Haar特征具有與檢測窗口大小無關(guān)的特性（想要了解細節(jié)還要讀一下原作者的文獻），所以可以將檢測窗口進行級別方法。

在檢測的最初，檢測窗口和樣本大小一致，然后按照一定的尺度參數(shù)（即每次移動的像素個數(shù)，向左然后向下）進行移動，遍歷整個圖像，標出可能的人臉區(qū)域。遍歷完以后按照指定的放大的倍數(shù)參數(shù)放大檢測窗口，然后在進行一次圖像遍歷；這樣不停的放大檢測窗口對檢測圖像進行遍歷，直到檢測窗口超過原圖像的一半以后停止遍歷。因為 整個算法的過程非?？欤词故潜闅v了這么多次，根據(jù)不同電腦的配置大概處理一幅圖像也就是幾十毫秒到一百毫秒左右。

在檢測窗口遍歷完一次圖像后，處理重疊的檢測到的人臉區(qū)域，進行合并等操作。