[OPENCV] FaceDectection - (二) 深入研究

深入研究演算法

為了能夠即時地計算出Face, 使用了三個的方式來達到目的

1. Integral Image

2. AdaBoost

3. Cascade filter

Integral Image - 積分圖

當計算一個圖像當中某個區域的積分

按照正常的方法, 開始累加每一點的值

這樣子計算量跟所要計算的區域成正比, 如果是一個 NxN的圖案, 那麼複雜度會是 O(N^2)
integral image提供了一種方式可以將計算複雜度簡化到一個常數 O(c)
怎麼做到的呢?

一開始要將這一個 image重新計算出一個新的image, 姑且就叫做 integral image.
新的image上面每一個點, 都是這一個點到左上角所圍起來區域的積分值
將 integral image每一點的表達方式取名為 ii(x,y), 而原本的點稱為 img(x,y), 則

這樣子我們再回頭看一下當初要計算的那個區域, 可以先將其分為四個區塊

所要計算的區域是 D,而在 integral image上, D 四個角所代表的意思是

1(x,y) = A+C
2(x',y') = A+B
3(x,y') = A
4(x',y) = A+B+C+D

將上面式子整理一下可以得到
D = 4 - 1 - 2  + 3

當有了積分圖像之後, 每一個區域積分都可以使用這種方式計算, 計算複雜度就是常數
可是... 得出 integral image需要一點計算,
其實想一想, 當要計算積分圖時, 每一點的計算其實也是 4-1-2+3的方式
因此得出一個積分圖是需要 O(N^2),
有了積分圖之後, 要計算某一個區域只需要查表即可 (複雜度O(c))

這積分圖的演算法, 喵解釋完畢
可是為什麼這個跟人臉偵測有關, 就得要往下看才能知道
這邊喵先說一些, 因為判斷的方式, 就是用不同區塊之間的差異大小來判斷 (很簡單的邏輯...)

AdaBoost - 三個臭皮匠勝過一個諸葛亮

這是一個比較偏難的部分, 之所以比較難的原因, 是因為這邊要講述的是一個分類器(classifier)的設計方法
AdaBoost也是基於一個簡單的邏輯
先使用弱分類器, 有多弱呢, 只要比隨機猜測的結果 50%還要來得好就可以了
(對歐 就是很弱的分類器)
簡單的說, 就像是猜測明天下不下雨, 這弱分類器告訴你下雨的機率只比你丟銅版來的高一些

喵的勒~ 那這麼弱的分類器要拿來幹嘛?
這就是一個中國人常常說的
三個臭皮匠勝過一個諸葛亮

不過呢, 這每個臭皮匠都是根據前一個臭皮匠分析結果上再做分析
舉個例子, 一樣用明天下不下雨來當作題目, 如果有三個弱分類器, 每一個都對於明天做下預測
而分類器猜錯的機率是 40%, 所以當三個弱分類器都說明天會下雨
那猜錯的機率就是 40% * 40% * 40% = 6.4%  (對...就是這麼低)

接著我們來看詳細操作內容, 如何使用AdaBoost概念訓練出一個分類器
1. 給定訓練樣本集合S,其中X和Y分別為正例樣本與負例樣本, T為訓練的最大循環次數
2. 初始化每一個樣本的權重為 1/N, 總共樣本數為N
3. 開始進行迭代, 直到停止迭代或者是達到最大循環次數
    3.1. 套入弱分類器
    3.2. 查看錯誤分類的樣本, 將錯誤範本的權重加起來成為 error
    3.3. 如果 error > 0.5 則停止迭代 (錯誤太多)
    3.4. 利用 Error重新計算出錯誤的點應該有的新權重, 一開始 D0 = 1/N
        D1 = D0 *(1 - error) / error
    3.5. 計算出這一個分類器的權重 a
        a = 1/2 * ln(( 1 - error) / error)
    3.6 繼續下一次迭代
4. 迭代結束之後, 每一個弱分類器都有了分類器的權重a, 因此可以將每一個分類器的權重相加成為一個強分類器

我理解這光看文字敘述, 是有點難理解
因此大家看一下這篇文章或許會有幫助多
http://blog.csdn.net/iemyxie/article/details/40423907

喵有空再把這部分補齊

Cascade Filter

有了以上這些基礎之後, 最關鍵的還是辨識的速度要提上來

AdaBoost雖然提供了簡易的方式可以製作出分類器

但是一個簡單的24x24的圖像, 用到的分類器就可以有幾萬種
要判斷一個圖像有沒有人臉要將幾萬個分類器跑過一次...
顯然這不是個好方法, 為了更快速的檢驗
這時候就得分層而治

什麼意思呢

打個比喻就是在河中掏金

首先就是先用大的篩子, 快速地先篩過一次, 接著再用比較小的篩子在篩一次

慢慢地 就可以篩出金沙了

講完金沙的例子, 還是回到分層的概念繼續往下說
這第一層主要就是要快速, 但是也要有效

通常第一層就使用幾個 (通常3~5個) 分類器做篩選
每一層分類器都有個基本的指標

1. false negative (漏報) 低於 1%

2. false positive (誤報) 不能高於40%

意思就是,  寧可錯殺, 也不可錯放

把錯誤判斷人臉的責任往後面遞延

但是要盡量降低漏報的機率

那什麼叫做漏報跟誤報
舉個例子就是, 假設大家都要去醫院檢測有沒有肝炎, 醫院會向上級機關報告肝炎人數
接著上級機關會列表在冊, 定期派人追蹤調查

那檢驗報告出來了
1. 報告說沒有, 但是其實你有, 所以漏報了你 (漏報)
2. 報告說有, 但是其實你沒有 (誤報)

好, 那再回頭說一下 cascade filter

為了要嚴加把關得出正確的結果,因此後面每一層就越來越嚴格
測試的項目也越來越多

在openCV的當中, 喵所寫的例子

[OPENCV] FaceDetection - (一) 初步探索

就使用了22層總計 2135個feature 做分類

但是第一層卻只有3個簡易的分類
這樣就可以很快速的掃描過整張image

借用一下論文當中的圖片再說明一下這些概念

上方的兩個Mask, 是根據AdaBoost所製作出眾多features當中, 選出來在放在第一層的兩個
這兩個遮罩循序掃過待辨識的圖片上做運算
運算的方式是將白色區塊的像素減去黑色區塊的像素(這邊運用到integral image)
第一個Mask可以在額頭眼睛部位得到較大值
第二個Mask則可以在眼睛跟鼻子部分得到較大值
在這兩個mask的運算結果上加上閥值, 就可以尋找影像當中跟人臉相關的部分

還有一點事...

說完了演算法, 其實少說了一點東西是

在做人臉偵測的時候, 人在整張圖片上的大小, 並不是一定的

簡而言之, 一開始在做分類器的時候, 其實有預設好樣品集合的圖案大小

就像是全部的圖案大小都是 24x24

所以在分析一張圖案上面的人臉時, 是使用window的概念

window一開始是整張圖案的大小, 接著慢慢縮小

當縮得比原本圖案小的話, 則會逐步做平移window來遍歷整個圖案.

這樣子才能夠找到非固定大小的人臉

接著的章節, 該是回頭把openCV這詳細的過程再講多一點

FaceDectection - (三) 實務剖析