搞了一年人臉識別，尋思著記錄點什么，于是想寫這么個系列，介紹人臉識別的四大塊：Face detection, alignment, verification and identification(recognization)，本別代表從一張圖中識別出人臉位置，把人臉上的特征點定位，人臉校驗和人臉識別。（后兩者的區(qū)別在于，人臉校驗是要給你兩張臉問你是不是同一個人，人臉識別是給你一張臉和一個庫問你這張臉是庫里的誰。

今天先介紹第一部分和第二部分。 主要說三篇頂會文章。

人臉檢測（detection）在opencv中早就有直接能拿來用的haar分類器，基于Viola-Jones算法。但是畢竟是老掉牙的技術(shù)，Precision/Recall曲線渣到不行，在實際工程中根本沒法給boss看，作為MSRA腦殘粉，這里介紹一種MSRA在14年的最新技術(shù)：Joint Cascade Face Detection and Alignment（ECCV14)。這篇文章直接在30ms的時間里把detection和alignment都給做了，PR曲線彪到很高，時效性高，內(nèi)存占用卻非常低，在一些庫上虐了Face++和Google Picasa，正好契合這篇想講的東西。可以作為本節(jié)的主線。

人臉校準（alignment）是給你一張臉，你給我找出我需要的特征點的位置，比如鼻子左側(cè)，鼻孔下側(cè)，瞳孔位置，上嘴唇下側(cè)等等點的位置。如果覺得還是不明白，看下圖：

圖中紅色框框就是在做detection，白色點點就是在做alignment。

如果知道了點的位置做一下位置驅(qū)動的變形，臉就成正的了，如何驅(qū)動變形不是本節(jié)的重點，在此省略。

首先介紹一下下面正文要寫的東西，由于干貨非常多所以可能會看著看著就亂了，所以給出框架圖：

?

=================================

作者建立了一個叫post classifier的分類器，方法如下：

1.樣本準備：首先作者調(diào)用opencv的Viola-Jones分類器，將recal閥值設到99%，這樣能夠盡可能地檢測出所有的臉，但是同時也會有非常多的不是臉的東東被檢測出來。于是，檢測出來的框框們被分成了兩類：是臉和不是臉。這些圖片被resize到96*96。

2.特征提取：接下來是特征提取，怎么提取呢？作者采用了三種方法：

第一種：把window劃分成6*6個小windows，分別提取SIFT特征，然后連接著36個sift特征向量成為圖像的特征。

第二種：先求出一個固定的臉的平均shape（27個特征點的位置，比如眼睛左邊，嘴唇右邊等等），然后以這27個特征點為中心提取sift特征，然后連接后作為特征。

第三種：用他們組去年的另一個成果Face Alignment at 3000 FPS via Regressing Local Binary Features (CVPR14) ，也就是圖中的3000FPS方法，回歸出每張臉的shape，然后再以每張臉自己的27個shape points為中心做sift，然后連接得到特征。

3.分類：將上述的三種特征分別扔到線性SVM中做分類，訓練出一個能分辨一張圖是不是臉的SVM模型。

緊接著作者將以上三種方法做出的分類器和初始分類器進行比對，畫了一個樣本分布的圖：

?

這個圖從左到右依次是原始級聯(lián)分類器得到的樣本分類分布和第一種到第三種方法提取的特征得到的樣本分類分布。可見做一下shape alignment可以得到一個更好的分類效果。但是問題來了：如果把所有的windows都做一下alignment，即使是3000 faces per second的速度一張圖可能也要處理上1秒，這無法滿足一般一秒30幀的實時需求。作者也說，用opencv分類器，參數(shù)設成99%的recall率將會帶來很嚴重的效率災難——一張圖能找出來3000個框，處理一張圖都要好幾秒。

這么渣的效率可咋辦呢？以上內(nèi)容已經(jīng)證明了alignment確實對detection的preciseness有幫助，這就夠啦，對下面的工作也是個啟發(fā)——能不能在做detection的同時把alignment做了呢？alignment的中間結(jié)果是否能給detection帶來一些幫助呢？后面慢慢講。先說兩個通用的面部檢測和矯正的模型：

1.級聯(lián)檢測分類器（bagging）：不失一般性，一個簡單的級聯(lián)分類器是這樣的：

圖中的Ci代表的是第i個弱分類器。x代表的是特征向量，f代表分類得分。每個Ci會根據(jù)自己的分類方法對x輸出一個分類結(jié)果，比如是一張臉或者不是一張臉，而fn（n=1~N)都會對應一個thresholdΘi，讓任意一個fn小于對應的Θi的時候，樣本就會被拒絕。通常不是一張臉的圖片在經(jīng)過前幾個弱分類器的判斷后就會被拒絕，根本不用做后面的判斷，所以速度很快。

2.級聯(lián)回歸校準：這里介紹的是另一個人在10年發(fā)的文章：Cascaded Pose Regression (CVPR10)，給圖像一個初始shape（通常采用平均shape），然后通過一次一次的回歸把shape回歸到正確的地方。算法結(jié)構(gòu)很簡單，但是效果確實非常好：

?

回歸過程如下：首先提取特征，原作者采用的是Pose-Indexed point features，然后根據(jù)特征訓練回歸函數(shù)（可以用線性回歸，CART，隨機森林等等），原作者采用了一個叫Random Fern Regressor的東西，這里翻譯成隨機蕨好了（這名字…)，回歸出這一階段的偏移量，然后shape加上這個偏移量，反復這一過程，直到迭代上限或者shape錯誤率不再下降。隨機蕨的算法過程和隨機森林類似，他是一個半樸素貝葉斯模型。首先選取M組每組K個特征建立M個蕨（弱分類器），然后假設蕨內(nèi)特征是相關(guān)的，蕨間特征是獨立的，這樣從統(tǒng)計學上隨機蕨是一個完整的把樸素貝葉斯分類器，讓計算變得簡單：

式中C代表分類，ci代表第I類，M代表蕨數(shù)量。

綜上，這樣回歸的過程可以總結(jié)成如下形式：

S代表shape，St代表在回歸第t階段的shape，他等于上一階段的shape加上一個偏置，這個偏置就是上述回歸方法之一搞定的。比如隨機森林或者隨機蕨，或者線性回歸。

現(xiàn)在再說說怎么訓練得到這個回歸Rt。

有兩種思路：一種是像剛才隨機蕨那樣，每個每個蕨的葉子節(jié)點存儲一個偏移量，計算訓練的時候落入這個葉子節(jié)點的樣本偏移之平均，然后作為最終的葉子節(jié)點偏移量。其實就是在優(yōu)化一個如下目標函數(shù)：

然而MSRA組在3000fps中采用的是另一種方法，形狀的偏移量ΔδS為：

目標函數(shù)是：

其實也是同樣的思路，Φ代表特征提取函數(shù)，論文中稱Φ的輸出為局部二值特征（LBF），W為線性回歸參數(shù)矩陣，其實就是把提取出來的特征映射到一個二維的偏移量上，是一個2*lenth(特征空間維數(shù))的變換矩陣。

首先講Φ是怎么訓練的：Φ其實就是一個隨機森林。輸入像素差特征（pixel-difference features），輸出一個offest。訓練的時候隨機給每個根節(jié)點像素差特征中的一部分。非葉節(jié)點的分裂依據(jù)是從輸入的pixel-difference features中找出能夠做到最大的方差衰減的feature。在最后的葉子節(jié)點上寫上落在葉子節(jié)點上的樣本偏移量，這個偏移量在之前說到的fern里有用，但是在這里沒啥用，因為作者最后不是用這個做回歸的而是用LBF，詳細的得往下看。如果有多個樣本都落在這里，則求平均。這樣訓練出來的東西就是下面這個公式所表達的東西：

可能有讀者看到這就會不懂了，不用管這個公式，等下面的看完了就會懂了。

但是我只想要其中的Φ，于是這里給出了LBF（local binary feature）的定義，直接簡單粗暴地統(tǒng)計所有樹葉節(jié)點是否被該樣本落入，如果落入了就記為1否則記為0，然后把所有的01串連起來就是LBF了。還是看圖說話：

?

先看b，隨機森林的三棵樹，樣本經(jīng)過三棵樹后分別落在了第1,2,3個葉子節(jié)點上，于是三棵樹的LBF就是1000,0100,0010.連接起來就是100001000010.然后看a，把27個特征點的lbf都連接起來形成總的LBF就是Φ了。

接下來是訓練w：之前已經(jīng)得到了wΦ（I,S)以及Φ（I,S),現(xiàn)在想求w，這還不容易嗎，直接算呀。不過作者又調(diào)皮了，他說他不想求w，而是想求一個總的大W=[w1,w2,w3,…,w27].怎么求呢？得做二次回歸。至于為什么要這么做下面會介紹。目標函數(shù)：

后面加了個L2項，因為W是炒雞sparse的，防止過擬合。做線性回歸即可得到W。

現(xiàn)在解釋一下為啥不直接用w1w2w3…而是要再回歸出來一個W：原因有兩個：

1. 再次回歸W可以去除原先小wi葉子節(jié)點上的噪聲，因為隨機森林里的決策樹都是弱分類器嘛噪聲多多滴；

2.大W是全局回歸（之前的一個一個小w也就是一個一個特征點單獨的回歸是local回歸），全局回歸可以有效地實施一個全局形狀約束以減少局部誤差以及模糊不清的局部表現(xiàn)。

這樣一來，測試的時候每輸入一張圖片I，先用隨機森林Φ求出它的LBF，然后在用W乘一下就得到了下一個stage的shape，然后迭代幾次就得到了最終的shape。所以效率十分的快。

好了，兜了一大圈該回來了，剛才講的是兩個uniform的model來做detection和shape regression的。接下來該講作者是怎么邊detection邊regression shape的了！

作者建立了一個分類回歸樹，就叫CRT好了。這個CRT在距離根節(jié)點比較近的幾層偏重于分類，在接近葉子節(jié)點的幾層偏重于回歸，具體實現(xiàn)上，每個節(jié)點究竟用于回歸還是分類呢？用一個概率p表示用于分類的概率，自然回歸就是1-p了。而這個p隨著深數(shù)的深度減小，作者采用了一個經(jīng)驗公式：

知道了CRT怎么建立，那就直接就看算法細節(jié)吧！邊測試是不是臉邊做特征點回歸的算法如下：

?

這個模型的訓練方法如下：

?

這樣就算完了嗎？不，既然要實現(xiàn)，就要細看一下以上用到的各類算法細節(jié)：

部分摘自其他博客，詳見參考文獻。

1.CART（Classification And Regression Tree）
思想：遞歸地將輸入空間分割成矩形
優(yōu)點：可以進行變量選擇，可以克服missing data，可以處理混合預測
缺點：不穩(wěn)定

分類訓練過程：

?

?

就這樣不斷分割之后可以建立如下這樣的決策樹：

?

2.Bagging (Breiman1996): 也稱bootstrap aggregation
Bagging的策略：
- 從樣本集中用Bootstrap采樣選出n個樣本
- 在所有屬性上，對這n個樣本建立分類器（CART or SVM or ...）
- 重復以上兩步m次，i.e.build m個分類器（CART or SVM or ...）
- 將數(shù)據(jù)放在這m個分類器上跑，最后vote看到底分到哪一類
Fit many large trees to bootstrap resampled versions of the training data, and classify by majority vote.
下圖是Bagging的選擇策略，每次從N個數(shù)據(jù)中采樣n次得到n個數(shù)據(jù)的一個bag，總共選擇B次得到B個bags，也就是B個bootstrap samples.

流程圖如下：

?

3.隨機森林：

隨機森林，指的是利用多棵樹對樣本進行訓練并預測的一種分類器。該分類器最早由Leo Breiman和Adele Cutler提出，并被注冊成了商標。簡單來說，隨機森林就是由多棵CART（Classification And Regression Tree）構(gòu)成的。對于每棵樹，它們使用的訓練集是從總的訓練集中有放回采樣出來的，這意味著，總的訓練集中的有些樣本可能多次出現(xiàn)在一棵樹的訓練集中，也可能從未出現(xiàn)在一棵樹的訓練集中。在訓練每棵樹的節(jié)點時，使用的特征是從所有特征中按照一定比例隨機地無放回的抽取的，根據(jù)Leo Breiman的建議，假設總的特征數(shù)量為M，這個比例可以是sqrt(M),1/2sqrt(M),2sqrt(M)。

因此，隨機森林的訓練過程可以總結(jié)如下：

(1)給定訓練集S，測試集T，特征維數(shù)F。確定參數(shù)：使用到的CART的數(shù)量t，每棵樹的深度d，每個節(jié)點使用到的特征數(shù)量f，終止條件：節(jié)點上最少樣本數(shù)s，節(jié)點上最少的信息增益m

對于第1-t棵樹，i=1-t：

(2)從S中有放回的抽取大小和S一樣的訓練集S(i)，作為根節(jié)點的樣本，從根節(jié)點開始訓練

(3)如果當前節(jié)點上達到終止條件，則設置當前節(jié)點為葉子節(jié)點，如果是分類問題，該葉子節(jié)點的預測輸出為當前節(jié)點樣本集合中數(shù)量最多的那一類c(j)，概率p為c(j)占當前樣本集的比例；如果是回歸問題，預測輸出為當前節(jié)點樣本集各個樣本值的平均值。然后繼續(xù)訓練其他節(jié)點。如果當前節(jié)點沒有達到終止條件，則從F維特征中無放回的隨機選取f維特征。利用這f維特征，尋找分類效果最好的一維特征k及其閾值th，當前節(jié)點上樣本第k維特征小于th的樣本被劃分到左節(jié)點，其余的被劃分到右節(jié)點。繼續(xù)訓練其他節(jié)點。有關(guān)分類效果的評判標準在后面會講。

(4)重復(2)(3)直到所有節(jié)點都訓練過了或者被標記為葉子節(jié)點。

(5)重復(2),(3),(4)直到所有CART都被訓練過。

利用隨機森林的預測過程如下：

對于第1-t棵樹，i=1-t：

(1)從當前樹的根節(jié)點開始，根據(jù)當前節(jié)點的閾值th，判斷是進入左節(jié)點(
=th)，直到到達，某個葉子節(jié)點，并輸出預測值。

(2)重復執(zhí)行(1)直到所有t棵樹都輸出了預測值。如果是分類問題，則輸出為所有樹中預測概率總和最大的那一個類，即對每個c(j)的p進行累計；如果是回歸問題，則輸出為所有樹的輸出的平均值。

注：有關(guān)分類效果的評判標準，因為使用的是CART，因此使用的也是CART的平板標準，和C3.0,C4.5都不相同。

對于分類問題（將某個樣本劃分到某一類），也就是離散變量問題，CART使用Gini值作為評判標準。定義為Gini=1-∑(P(i)*P(i)),P(i)為當前節(jié)點上數(shù)據(jù)集中第i類樣本的比例。例如：分為2類，當前節(jié)點上有100個樣本，屬于第一類的樣本有70個，屬于第二類的樣本有30個，則Gini=1-0.7×07-0.3×03=0.42，可以看出，類別分布越平均，Gini值越大，類分布越不均勻，Gini值越小。在尋找最佳的分類特征和閾值時，評判標準為：argmax（Gini-GiniLeft-GiniRight），即尋找最佳的特征f和閾值th，使得當前節(jié)點的Gini值減去左子節(jié)點的Gini和右子節(jié)點的Gini值最大。

對于回歸問題，相對更加簡單，直接使用argmax(Var-VarLeft-VarRight)作為評判標準，即當前節(jié)點訓練集的方差Var減去減去左子節(jié)點的方差VarLeft和右子節(jié)點的方差VarRight值最大。

Random Forest與Bagging的區(qū)別在于：Bagging每次生成決策樹的時候從全部的屬性Attributes里面選擇，而Random Forest是隨機從全部Attributes的集合里面生成一個大小固定的子集，相對而言需要的計算量更小一些。

4.Boosting(Freund & Schapire 1996):
boosting在選擇hyperspace的時候給樣本加了一個權(quán)值，使得loss function盡量考慮那些分錯類的樣本（i.e.分錯類的樣本weight大）。
怎么做的呢？
- boosting重采樣的不是樣本，而是樣本的分布，對于分類正確的樣本權(quán)值低，分類錯誤的樣本權(quán)值高（通常是邊界附近的樣本），最后的分類器是很多弱分類器的線性疊加（加權(quán)組合），分類器相當簡單。

結(jié)構(gòu)如圖：

?

AdaBoost和RealBoost是Boosting的兩種實現(xiàn)方法。general的說，Adaboost較好用，RealBoost較準確。由于Boosting算法在解決實際問題時有一個重大的缺陷,即他們都要求事先知道弱分類算法分類正確率的下限,這在實際問題中很難做到。后來 Freund 和 Schapire提出了 AdaBoost 算法,該算法的效率與 Freund 方法的效率幾乎一樣,卻可以非常容易地應用到實際問題中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整個訓練集上維護一個分布權(quán)值向量 D( x) t ,用賦予權(quán)重的訓練集通過弱分類算法產(chǎn)生分類假設 Ht ( x) ,即基分類器,然后計算他的錯誤率,用得到的錯誤率去更新分布權(quán)值向量 D( x) t ,對錯誤分類的樣本分配更大的權(quán)值,正確分類的樣本賦予更小的權(quán)值。每次更新后用相同的弱分類算法產(chǎn)生新的分類假設,這些分類假設的序列構(gòu)成多分類器。對這些多分類器用加權(quán)的方法進行聯(lián)合,最后得到?jīng)Q策結(jié)果。這種方法不要求產(chǎn)生的單個分類器有高的識別率,即不要求尋找識別率很高的基分類算法,只要產(chǎn)生的基分類器的識別率大于 015 ,就可作為該多分類器序列中的一員。

尋找多個識別率不是很高的弱分類算法比尋找一個識別率很高的強分類算法要容易得多,AdaBoost 算法的任務就是完成將容易找到的識別率不高的弱分類算法提升為識別率很高的強分類算法,這也是 AdaBoost 算法的核心指導思想所在,如果算法完成了這個任務,那么在分類時,只要找到一個比隨機猜測略好的弱分類算法,就可以將其提升為強分類算法,而不必直接去找通常情況下很難獲得的強分類算法。通過產(chǎn)生多分類器最后聯(lián)合的方法提升弱分類算法,讓他變?yōu)閺姷姆诸愃惴?也就是給定一個弱的學習算法和訓練集,在訓練集的不同子集上,多次調(diào)用弱學習算法,最終按加權(quán)方式聯(lián)合多次弱學習算法的預測結(jié)果得到最終學習結(jié)果。包含以下2點:

樣本的權(quán)重
AdaBoost 通過對樣本集的操作來訓練產(chǎn)生不同的分類器,他是通過更新分布權(quán)值向量來改變樣本權(quán)重的,也 就是提高分錯樣本的權(quán)重,重點對分錯樣本進行訓練。

(1) 沒有先驗知識的情況下,初始的分布應為等概分布,也就是訓練集如果有 n個樣本,每個樣本的分布概率為1/ n。(2) 每次循環(huán)后提高錯誤樣本的分布概率,分錯的樣本在訓練集中所占權(quán)重增大,使得下一次循環(huán)的基分類器能夠集中力量對這些錯誤樣本進行判斷。

弱分類器的權(quán)重
最后的強分類器是通過多個基分類器聯(lián)合得到的,因此在最后聯(lián)合時各個基分類器所起的作用對聯(lián)合結(jié)果有很大的影響,因為不同基分類器的識別率不同,他的作用就應該不同,這里通過權(quán)值體現(xiàn)他的作用,因此識別率越高的基分類器權(quán)重越高,識別率越低的基分類器權(quán)重越低。權(quán)值計算如下: 基分類器的錯誤率: e = ∑( ht ( x i) ≠yi) Di (1) 基分類器的權(quán)重:W t = F( e) ,由基分類器的錯誤率計算他的權(quán)重。2.3 算法流程及偽碼描述 算法流程描述 算法流程可用結(jié)構(gòu)圖 1 描述,如圖 1 所示 AdaBoost重復調(diào)用弱學習算法(多輪調(diào)用產(chǎn)生多個分類器) ,首輪調(diào)用弱學習算法時,按均勻分布從樣本集中選取子集作為該次訓練集,以后每輪對前一輪訓練失敗的樣本,賦予較大的分布權(quán)值( Di 為第i 輪各個樣本在樣本集中參與訓練的概率) ,使其在這一輪訓練出現(xiàn)的概率增加,即在后面的訓練學習中集中對比較難訓練的樣本進行學習,從而得到 T個弱的基分類器, h1 , h2 , …, ht ,其中 ht 有相應的權(quán)值 w t ,并且其權(quán)值大小根據(jù)該分類器的效果而定。最后的分類器由生成的多個分類器加權(quán)聯(lián)合產(chǎn)生。

參考文章：

[1]Joint Cascade Face Detection and Alignment（ECCV14)

[2]Face Alignment at 3000 FPS via Regressing Local Binary Features (CVPR14)

[3]Cascaded Pose Regression (CVPR10)

[4]Fast Keypoint Recognition in Ten Lines of Code

[5]女神的博文：