即時找到人臉：滑動視窗、Haar 特徵與 Boosting

分類 vs 偵測：加上「在哪裡」

在前兩篇導讀中，我們做出了一台機器，它對「整張圖」回答一個問題：「這是人臉嗎？」餵給它一張裁切得很緊的照片，它就回傳一個標籤。這就是分類，也是你已經熟悉的傳統辨識流程的最後一格：把影像轉成特徵向量，再把向量交給分類器。但真實照片不是乾淨的裁切圖。一張旅遊快照裡可能有三張臉、一隻狗，和一大片天空。分類對這種場景毫無辦法，因為它只能對整個畫面說一個字。

偵測加上了第二個、也更困難的問題：不只是圖裡有什麼，還要問在哪裡——而且答案可能不只一個。「在哪裡」的答案是一個邊界框（bounding box）：四個數字（例如左、上、寬、高），在某個物體周圍畫出一個剛好框住它的矩形。因此偵測器的輸出是一串框，每個框都附帶一個標籤，通常還有一個信心分數。偵測嚴格來說比分類更難，因為它必須定位每一個物體實例，而且不能在沒有東西的地方憑空畫框。

從分類到偵測，有一座美麗而簡單的橋。如果你已經有一個好的分類器，你可以讓它在每一個可能的位置反覆回答同一個問題，把它變成偵測器。把一個小框在影像上滑動——由左到右、由上到下——每停一格，就把那塊子視窗裁出來，丟給分類器跑一次。只要分類器大喊「人臉！」，你就記下一個框。這就是滑動視窗偵測；概念上整件事就是這樣：偵測變成了套用在數百萬個小視窗上的分類。

還有一個我們從一開始就需要的想法：我們到底怎麼判定一個預測框是「正確」的？偵測器很少把框對準到精確的像素；它只是接近。所以我們用一個叫做交集比聯集（Intersection-over-Union, IoU）的數字，來衡量預測框與真實框的重疊程度——粗略地說，就是兩個矩形有多一致，範圍從 0（毫無重疊）到 1（完全吻合）。我們會在最後一節精確定義它，但請先記住：IoU 是兩把尺，一把用來決定哪些框算命中，之後另一把用來清理重複的偵測。

滑動視窗與影像金字塔

讓我們把這場搜尋講具體。先選一個固定的視窗大小——比方說 24×24 像素，這正是 Viola-Jones 用在人臉上的尺寸。把視窗放在左上角，裁出底下的像素，轉成特徵向量，用分類器評分。然後把視窗移動幾個像素（這個位移叫做步幅 stride），再做一次。到了右邊緣，就往下挪一個步幅，開始下一列。這樣掃過整張圖，你就在視窗能停的每一個位置都問過分類器一次了。

但一個 24×24 的視窗，永遠只能對上大約 24 像素高的臉。一張塞滿整個畫面的臉，根本放不進這個視窗。解法是影像金字塔（image pyramid）：視窗大小不變，但反覆把影像縮小——比方說每一步縮 10～20%——並在每一張更小的副本上重新掃描。一張在原始解析度下太大的臉，往金字塔下走幾層後就變成 24 像素高，視窗終於對上了它。把原圖加上一張張縮小的副本疊起來，形狀就像金字塔，名字由此而來。於是「試所有大小」就變成了「在金字塔的每一層，試所有位置」。

每一個視窗、在每一層，都走同一條小流程：裁切 → 特徵向量 → 分類器 → 一個分數。把所有分數超過門檻的視窗收集起來，你就得到一份候選框的原始清單。這就是一個完整、可運作的偵測器。唯一的問題是速度——而要看清它有多糟，我們來數一數。

\text{total work}\;\approx\;\underbrace{(W\cdot H)}_{\text{positions}}\;\times\;\underbrace{S}_{\text{scales}}\;\times\;\underbrace{c}_{\text{cost per window}}

樸素滑動視窗偵測的概略成本估算。

把它讀成：總計算量大約等於視窗位置數，乘上尺度數，再乘上判斷一個視窗的成本。這裡 W 和 H 是影像的寬與高（以像素計），所以 W·H（步幅為 1 時）數的是視窗左上角能停的位置有多少——對一張 640×480 的影像來說約 300,000 個位置。S 是你掃描的金字塔層數，也許 10～30。c 則是對單一視窗萃取特徵並評分的成本。這幾個因子相乘，是因為工作是巢狀的：每一個尺度你都要走遍所有位置，而在每一個位置你都要付出完整的每視窗成本 c。代入數字——300,000 × 20 × c——就算 c 便宜到只有幾千次運算，每一幀也會炸成數百億次運算。在 2001 年的硬體上，這對即時處理完全沒指望。請注意我們恰好有兩個旋鈕可以轉：把 c 縮小（讓每個視窗更便宜地評估），以及把有效視窗數縮小（幾乎瞬間就把絕大多數視窗丟掉）。Viola-Jones 用 Haar 特徵與積分影像對付第一個，用注意力級聯對付第二個。

# Naive sliding-window detector over an image pyramid (pseudocode)
boxes = []
scale = 1.0
img = original_image
while img.height >= WINDOW and img.width >= WINDOW:   # build the pyramid on the fly
    for y in range(0, img.height - WINDOW, STRIDE):
        for x in range(0, img.width - WINDOW, STRIDE):
            patch    = img[y:y+WINDOW, x:x+WINDOW]    # crop one window
            features = extract(patch)                 # -> feature vector
            score    = classifier(features)           # -> confidence
            if score > THRESHOLD:
                # map the box back to ORIGINAL-image coordinates
                boxes.append((x/scale, y/scale, WINDOW/scale, WINDOW/scale, score))
    img   = shrink(img, factor=0.83)                  # next pyramid level (~20% smaller)
    scale = scale * 0.83
# 'boxes' still has many overlapping duplicates -> cleaned up later by NMS

整個樸素偵測器就是三層巢狀迴圈；昂貴的那一行是 classifier(features)，每個視窗都要跑一次。

類 Haar 特徵與積分影像技巧

Viola-Jones 不用一般的特徵向量，而用一族極其便宜的特徵，叫做類 Haar 特徵（Haar-like features）。每一個就是蓋在視窗上的一組相鄰白色與黑色矩形圖案。它的值是白色矩形底下像素亮度的總和，減去黑色矩形底下的總和。這一個數字衡量的是一種對比：兩矩形的特徵對邊緣有反應（亮挨著暗），三矩形的特徵對線條有反應（兩塊亮區之間夾一條暗紋），四矩形的則對對角線或中央─周圍圖案有反應。

為什麼這麼粗糙的圖案找得到臉？因為人臉共享一些穩固的局部對比。眼睛區域可靠地比正下方的臉頰更暗——所以一個上面是暗帶（蓋住眼睛）、下面是亮帶（蓋住臉頰）的兩矩形特徵，幾乎對任何正面直立的臉都會強烈反應，不分膚色與身分。同理，鼻樑比兩側的眼窩更亮，這由一個三矩形的「線條」特徵捕捉。沒有任何單一特徵是人臉偵測器，但少數幾個放對位置，就能畫出一個可辨識的特徵簽名。

但這裡有個幾乎扼殺這個想法的關鍵問題。在單一個 24×24 視窗裡，你可以把這些矩形圖案放在各種位置與大小上，產生超過 160,000 個可能的特徵。而你必須在每一個滑動視窗、每一個尺度裡，評估被選中的那些。樸素地做，把矩形底下的像素加總，就意味著把它裡面所有像素都加起來——一個 12×12 的矩形是 144 次加法——而你會為了重疊的矩形把這件事重做數十億次。這正是我們需要碾碎的那個每視窗成本 c。

拯救之道是積分影像（integral image，也叫累積面積表）。在做任何偵測之前，我們先為每一個像素位置預先算好：它左上方所有像素的總和（包含它自己）。

II(x,y)\;=\;\sum_{x'\le x,\;y'\le y} I(x',y')

定義：每一個積分影像格存的是它左上方整個矩形的總和。

用白話說：I(x',y') 是原始影像在第 x' 欄、第 y' 列那個像素的亮度。這個總和涵蓋每一個欄 x' 不超過 x 且列 y' 不超過 y 的像素——也就是從影像左上角一路到 (x,y) 的整個矩形區塊。所以 II(x,y) 是一個累計值：「左方加上方，全部加起來」。如果影像右下角的像素存的是 II，它就等於整張影像的總和。直接照定義算 II 本身會很慢，但有一個單次掃描的遞迴式。

II(x,y)\;=\;I(x,y)\;+\;II(x-1,y)\;+\;II(x,y-1)\;-\;II(x-1,y-1)

積分影像用相鄰格在一次掃描中建好。

這是用我們已經算好的——正左、正上、左上對角——三格的值來建出 II。直覺上：(x,y) 左上方的區塊，幾乎就是它左方的區塊 II(x−1,y)，加上它上方的區塊 II(x,y−1)。但這兩個區塊重疊了——它們共享 (x−1,y−1) 左上方的整片區域，所以那塊共同的角落被算了兩次。我們減掉一次 II(x−1,y−1) 來抵銷重複計算，再加上目前這個像素 I(x,y) 本身。結果就是：整張積分影像一次掃描就填好，每個像素只做固定量的工作。這個成本每張影像（或每層金字塔）只付一次，然後被每一個視窗重複使用。

\text{sum}(\text{rect})\;=\;II(D)\;-\;II(B)\;-\;II(C)\;+\;II(A)

任意矩形的像素總和由它的四個角算出——四次查表，與大小無關。

這就是回報。把矩形的四個角標為 A（左上）、B（右上）、C（左下）、D（右下）。II(D) 是矩形遠角左上方一切的總和——那個大區塊已經包含我們的矩形，但也多含了三條不要的長條。II(B) 扣掉矩形上方那塊高條；II(C) 扣掉矩形左方那塊寬條。但 A 左上方的那個角落區域如今被扣了兩次（它同時在 B 的區塊和 C 的區塊裡），所以我們把 II(A) 加回來一次。剩下的，正好是矩形的總和——用四次查表、三次算術算出，不管矩形多大。一個 4×4 矩形和一個 400×400 矩形花同樣的代價。這是每矩形 O(1)，也是把每視窗成本 c 從數百次加法變成一個小常數的那個單一技巧——即時偵測之所以可能，全靠它。

一個小小的範例。取一塊 3×3 的亮度，逐列為：上 [1, 2, 3]、中 [4, 5, 6]、下 [7, 8, 9]。它的積分影像（每格＝左上方總和，從 1 起算）算出來是：上 [1, 3, 6]、中 [5, 12, 21]、下 [12, 27, 45]——而 45 確實就是 1+2+…+9，整塊的總和。現在要求右下角那個 2×2 區塊 {5,6,8,9} = 28 的總和。用角落規則，對應這個矩形的四角：D 是右下格 II=45，B 是區塊右上正上方那格 II(第1列,第3欄)=6，C 是區塊起點左下那格 II(第3列,第1欄)=12，A 是對角那格 II(第1列,第1欄)=1。於是 45 − 6 − 12 + 1 = 28。對上了，而且只用四次查表，而不是把四個像素加起來——矩形越大，省下的越多。

AdaBoost：簡單規則組成的委員會

我們現在有了便宜的特徵，但還沒有分類器。Viola-Jones 用提升法（boosting）做出一個，具體來說是 AdaBoost。系統的原子是一個弱學習器（weak learner）：取一個 Haar 特徵，算出它的值，跟一個門檻比較——「如果『眼帶減臉頰帶』的對比超過 θ，就投人臉，否則投非人臉」。這是一條一行的規則。單獨來看它只比擲硬幣好一點點；可能 55% 的時候是對的。神奇之處在於把數百條這種弱規則組合成一條強的。

AdaBoost 一輪一輪地進行。先準備一個標好的訓練集，裡面有人臉與非人臉視窗，並給每個範例相同的權重。每一輪：(1) 在整個特徵池裡搜尋，找出在目前加權範例上表現最好的那一個弱學習器；(2) 算出它的加權誤差，再把誤差轉成一個投票權重；(3) 提高它答錯範例的權重，逼下一輪去專注在那些前輩一直漏掉的難例上。經過許多輪後，最終的「強」分類器，就是一路上被選中的所有弱學習器的加權投票。

H(x)\;=\;\operatorname{sign}\!\left(\sum_{t=1}^{T}\alpha_t\,h_t(x)\right)

強分類器是 T 個弱學習器的加權投票。

一塊一塊地解。輸入 x 是一個影像視窗。每個 h_t(x) 是第 t 個弱學習器的裁決，輸出 +1（「人臉」）或 −1（「非人臉」）。數字 α_t（alpha）是那個學習器的投票權重——它在委員會裡的嗓門有多大。我們把帶正負號的投票 α_t·h_t(x) 在全部 T 輪上加總，再取總和的正負號：如果加權投票偏正，H(x) = +1，我們判定是人臉；偏負就不是。所以 α_t 大的學習器能左右決定，嗓門弱的幾乎推不動它。取正負號之前那個總和的大小，還順便當作一個粗略的信心分數，之後用來給框排名很有用。

\alpha_t\;=\;\tfrac{1}{2}\ln\!\left(\frac{1-\varepsilon_t}{\varepsilon_t}\right)

弱學習器的投票權重隨其加權誤差縮小而增大。

這裡 ε_t（epsilon）是第 t 輪弱學習器的加權誤差——它分類錯的範例的總權重，介於 0 與 1 之間。這條公式把誤差轉成投票權重 α_t。把比值 (1−ε_t)/ε_t 讀成「對的頻率比上錯的頻率」。如果學習器近乎完美，ε_t 很小，比值很大，對數又大又正，α_t 就大——一個有力的嗓音。如果學習器只是瞎猜，ε_t = 0.5，比值是 1，ln(1) = 0，α_t = 0——它的票被忽略，這是對的，因為它什麼都不懂。關鍵是 ε_t 必須低於 0.5：比擲硬幣還差的學習器會給出負的 α_t。（其實這也沒關係——負權重只是說「相信它說的相反面」——但慣例是挑比瞎猜好的學習器。）算個數：ε_t = 0.2 得 α_t = ½·ln(0.8/0.2) = ½·ln 4 ≈ 0.69。

D_{t+1}(i)\;\propto\;D_t(i)\,\exp\!\big(-\alpha_t\,y_i\,h_t(x_i)\big)

重新加權：本輪答錯的範例，在下一輪變得更重要。

這是讓後面的學習器專精化的那一步。D_t(i) 是訓練範例 i 進入第 t 輪時的權重——演算法對它投注多少注意力。真實標籤 y_i 是 +1 或 −1，h_t(x_i) 是第 t 輪學習器對那個範例的預測。看乘積 y_i·h_t(x_i)：如果學習器對了，真實與預測的正負號相同，乘積是 +1，指數 −α_t·(+1) 為負，所以 exp(...) < 1，權重縮小。如果學習器錯了，正負號不同，乘積是 −1，指數 −α_t·(−1) = +α_t 為正，exp(...) > 1，權重增大。於是每一輪聚光燈都打到剛被漏掉的範例上，而且（因為 α_t 在縮放它）越有自信的錯誤被罰得越重。那個「∝」表示我們接著把所有權重重新正規化，讓它們加起來為 1。

注意力級聯：刻意偷懶

我們已經讓每個特徵幾乎免費（積分影像），讓每個分類器準確（AdaBoost）。但我們每一幀仍要面對數百萬個視窗，就算是一個快速、比方說 200 個特徵的強分類器，跑遍每一個也太慢。Viola-Jones 偵測器再加上一個近乎哲學的想法：刻意偷懶。絕大多數視窗——天空、牆壁、衣服——明顯不是人臉。為了排除每一個而花上 200 個特徵，實在愚蠢。我們應該在容易否決的視窗上幾乎不花成本，把力氣留給那些罕見、模稜兩可的視窗。

這個機制就是注意力級聯（attentional cascade），也叫 Haar 級聯分類器。把一連串「階段」依複雜度遞增排好，每一個階段本身是一個小型 AdaBoost 分類器。一個視窗先丟給第 1 階段；如果第 1 階段否決它，我們立刻停手，這個視窗被判為非人臉——後面的階段都不跑。只有當它通過時，才往第 2 階段、再第 3 階段……一個視窗必須通過每一個階段，才會最終被判定為人臉。這是一連串關卡的試煉：任何一關失敗就出局；全部存活才算過關。

巧妙之處在於排序。第一階段用非常少的特徵——Viola-Jones 著名地在第 1 階段只用了兩個——並調到極度寬鬆：它幾乎絕不能否決一張真臉，但它會一眼就爽快地丟掉，比方說，50% 的背景視窗。既然大多數視窗是背景，這一個便宜的測試就瞬間消除了大約一半的工作量。後面每一個階段用更多特徵、更嚴格，但它只會看到通過所有先前濾網而存活下來的那一小部分視窗。昂貴的 200 個特徵的推理，只在那些罕見、有希望的候選上跑，而不在數百萬個明顯該否決的視窗上跑。

D\;=\;\prod_{k=1}^{K} d_k \qquad\qquad F\;=\;\prod_{k=1}^{K} f_k

整體偵測率與假陽性率，是各階段對應比率的乘積。

這兩個乘積解釋了為什麼級聯能在每一步都寬鬆、整體卻又很緊。K 是階段數。對第 k 階段，d_k 是它的偵測率（它正確放行的真臉比例），f_k 是它的假陽性率（它誤放行的非臉比例）。因為一個視窗必須在所有階段存活，這些機率會相乘，就像通過一連串獨立的閘門：整體偵測率 D 是每一階段 d_k 的乘積，整體假陽性率 F 是每一階段 f_k 的乘積。代入數字：設計 10 個階段，每個都放行一半的背景，f_k = 0.5。那麼 F = 0.5^10 ≈ 0.001——到最後只有大約千分之一的背景視窗存活，儘管沒有任何單一階段是嚴格的。同時讓每個 d_k 都很高，比方說 0.995；那麼 D = 0.995^10 ≈ 0.95，所以我們仍能抓到約 95% 的臉。這就是級聯的整筆交易：許多溫和濾網疊出極小的假陽性率，又不至於把真臉丟掉。

收尾：非極大值抑制與偵測器評分

跑完級聯，你會得到一個雜亂的結果：在每一張真臉周圍，偵測器會在一叢重疊視窗上發出反應——稍微位移、稍微縮放的各種版本全都過了關。一張臉產生十幾個近乎重複的框。我們希望每張臉恰好一個框，所以需要一個清理步驟。這個步驟就是非極大值抑制（non-maximum suppression, NMS）：在一堆重疊的框裡，留下最強的那個，並抑制其餘與它重疊太多的框。

要精確地說「重疊太多」，我們重新用上第 1 節的 IoU。它的定義如下。

\mathrm{IoU}(A,B)\;=\;\frac{\operatorname{area}(A\cap B)}{\operatorname{area}(A\cup B)}

交集比聯集：兩個框的共有面積，除以它們合併起來的面積。

A 和 B 是兩個框。交集 A∩B 是重疊的區域——想像把一個矩形滑到另一個上面；它們覆蓋同一批像素的那個小矩形就是交集，其面積是寬乘高（若不相觸則為零）。聯集 A∪B 是兩者合在一起覆蓋的總面積，共有的部分只算一次；一個方便的算法是 area(A) + area(B) − area(A∩B)，把交集減掉以免重複計算。IoU 把共有面積除以合併面積，得到一個從 0（完全沒重疊）到 1（兩框完全重合）的數字。建立一點感覺：兩個一模一樣的框 IoU = 1；兩個重疊一半的框大概是 0.3～0.4；勉強擦邊的框接近 0。妙就妙在，IoU 上的單一門檻在本篇身兼兩職——它決定 NMS 把哪些框當成重複而抑制，也（在評分時）決定一個預測框是否與真實框重疊得夠多，足以算作一次正確偵測。

收集偵測器發出的所有候選框，每個都帶著它的信心分數，並挑一個 IoU 門檻（常用 0.5）。
把這些框依分數排序，最高的排前面。
取出分數最高的框，接受它作為一個最終偵測，並把它從清單中移除。
計算那個被接受的框與每一個剩餘框的 IoU；丟掉所有 IoU 超過門檻的框（它們是同一張臉的重複）。
帶著存活下來的框回到第 3 步，重複到清單為空為止。

這是貪婪式（greedy） NMS：每一回合它都認定當下最好的框，清掉所有擠在它旁邊的，然後往下走。說它貪婪，是因為它從不回頭重新考慮先前的選擇。結果是每個物體一個乾淨的框——每一叢裡分數最高的代表。（一個陷阱：IoU 門檻設太低，你會把真正分開、靠得很近的臉也抑制掉；設太高，又會留下重複。這個門檻是要針對場景調的旋鈕。）

最後，我們怎麼判定一個偵測器好不好？我們把第 2 篇導讀的評分框架直接延伸到偵測。首先，用 IoU 把每個預測框與一個真實框配對：一個對上某個尚未被配對的真實框、IoU ≥ 0.5 的預測，是真陽性（true positive, TP）；一個沒對上任何真東西的預測，是假陽性（false positive, FP）；一張沒有任何預測覆蓋到的真臉，是假陰性（false negative, FN）。由這些計數，得到和之前一樣的兩個量：精確率（precision） = TP /（TP + FP），「我畫的框裡，有多少是真臉？」；以及召回率（recall） = TP /（TP + FN），「真臉裡，我找到了多少？」。

兩者之間永遠有取捨：把偵測器的信心門檻調低，它就接受更多框——召回率上升，但精確率下降；調高則相反。把門檻掃過它的整個範圍，就描出一條精確率─召回率曲線（precision-recall curve）（以及與第 2 篇那條密切相關的 ROC 曲線），用一張圖總結每一個操作點的表現；曲線下的面積就是一個單一的品質數字。這正是整條脈絡的回報：當初用來評斷一個滑動視窗分類器的同一套精確率／召回率語言，如今用來評斷一個 Viola-Jones 偵測器畫出的框——從分類一路到偵測，都是同一把一致的尺。