AI 從頭學（三五）：DPM
Object Detection with Discriminatively Trained Part-Based Models
2017/07/27
前言：
本篇為 R-CNN 的熱身之一。
Summary：
本次講解的論文，主要是利用 Latent SVM (L-SVM) 進行的物件偵測 [1]。
之所以選擇這篇論文閱讀，起因是之前一篇論文 [2]，引用的 R-CNN [3]，用到了 Selective Search [4] 跟 L-SVM [1]。
[1] 跟它前一個版本 [5]，都使用了 Histograms of Oriented Gradients (HOG) 作為特徵擷取的方法 [6], [7]。SIFT [8] 跟 HOG 類似，本文將藉助它來闡述 HOG 的原理。
[6] 處理的是概略的人體輪廓，[1], [5] 則利用 [9], [10] 計算出局部的框架，除了有較高的辨識率，也可適應各種不同物體的偵測。
L-SVM 可以說是一種 Energy-Based Model [11]，也可說是一種 MI-SVM [12]。限於篇幅，本文將只會講解簡單的 SVM 概念 [13] ，並不會對 L-SVM 著墨太多（其實是作者還在努力K書中）。
-----
本文將分成八個小節進行。
Q1: What is L-SVM?
Q2: What is AOL?
Q3: What is HOG?
Q4: What is SIFT?
Q5: What is SVM?
Q6: What is the Pyramid Structure?
Q7: What is the flowchart of the object detection algorithm?
Q8: What is the result?
-----
Q1: What is L-SVM?
A1:
圖1.1上方是測試的圖片，下方則是訓練出來的 L-SVM 模型。
圖1.1a可以看到一個粗略的人體形狀，這是 Linear SVM 訓練出來的 HOG filter [6]。
圖1.1b則是在 [6] 的基礎上，加上局部的 filters。由於局部位置並沒有標籤，所以在訓練時它們必須被視為 latent (hidden) variables [1]。
圖1.1c則是最後的模型，顯示為空間權重的表現。
技術細節在本文內稍後會討論。
Fig. 1.1. Detections obtained with a single component person model, p. 2 [1].
-----
圖1.2是不同種類物件的模型，此處列出的有瓶子、汽車、沙發、腳踏車。
圖1.3列出的有人、瓶子、貓、汽車。我們可以看到人與瓶子、貓與汽車有類似的模型。
這邊值得注意的是舊版本跟新版本的差異：新版的每個種類有兩個子模型來輔助偵測，稱為 mixture model。
Fig. 1.2. Some models learned from the PASCAL VOC 2007 dataset, p. 6 [5].
Fig. 1.3. Some of the models learned on the PASCAL 2007 data set, p. 1641 [1].
---
Q2: What is AOL?
A2:
AOL 是 2015年一篇論文標題的縮寫 [2]，參考圖2。[2] 主要引用了 R-CNN [3]、ZFNet、DQN，都是相當經典的論文。
R-CNN [3] 主要又引用了 Selective Search [4] 與 L-SVM [1]，這便是此次報告 [1] 的緣故。
Fig. 2. Related research.
-----
Q3: What is HOG?
A3:
HOG 是 Histograms of Oriented Gradients 的縮寫，這篇發表於 2005 的論文 [6]，截至作者撰寫文章之時，獲得 19606 次引用。[1] 的基本架構即根植於此。所以本篇先簡介一下 HOG。
圖3.1a是資料庫內的圖片，大小統一為 64 x 128，參考圖3.1b。
Fig. 3.1a. Some sample images from the new human detection database, p. 3 [6].
Fig. 3.1b. The image resolution is 64 x 128, p. 2 [6].
-----
此處假設讀者已有 SVM 的基礎。稍後在 Q5 會簡介 SVM。
圖3.2a是全部圖片的平均值，由於圖片在處理時左右反過來也用了，所以看到的是一個對稱的圖形。
圖3.2b跟3.2c是 Linear SVM 訓練完後，向量最大權重的顯示，分別是「人」與「非人」。這邊一個 pixel 代表一個 8 x 8 的向量（的最大值），對應於圖3.2e則是 HOG descriptor，在 8 x 8 的矩陣內，有九個方向的線條，線條的強度則以明暗表示（可參考下方的放大圖）。
圖3.2d是測試圖片。
圖3.2d經過HOG的計算後，得到圖3.2e。分別乘上 (b)與(c)，則得到 (f)與(g)。
更詳細的介紹，可以參考 Q7。
Fig. 3.2. The HOG detectors cue mainly on silhouette contours, p. 7 [6].
Fig. 3.2e. It’s computed R-HOG descriptor, p. 7 [6].
-----
圖3.3是完整的流程圖，有六個步驟。其中第一跟第四的 normalization 可以參考 [7]，本文會介紹步驟二、三、五、六。
Fig. 3.3. An overview of the feature extraction and object detection chain, p. 2 [6].
-----
Q4: What is SIFT?
SIFT 是 Scale-Invariant Feature Transform [8] 的縮寫。它跟 HOG 「有點像」。
圖4.1左邊看到最小的是 n x n 的 pixel cells，接下來是 4 x 4 的 grids，然後 2 x 2 的 grids 組成一個 descriptor。這邊可以看到強度是由箭頭的長度顯示，HOG則是明暗。另外 SIFT有八個方向。HOG 在論文中則選九個方向。
計算的公式可以參考圖4.2。
Fig. 4.1. SIFT: A keypoint descriptor is created, p. 101 [8].
Fig. 4.2. SIFT: For each image sample, the gradient magnitude and orientation is precomputed using pixel differences, p. 99 [8].
-----
SIFT 簡介完後，回到 HOG。
圖4.3a 顯示的是 [1] 中訓練完後的 36 (9 x 4) 個 eigenvector，每個 eigenvector 是 36 (9 x 4) 維的向量。
這個圖可以跟圖3.2e一起看。也就是，圖3.2e中的每個「雪花」可以用這36個（或部分） eigenvectors 組成。概念上每個雪花由四個小雪花組成，每個小雪花有九個方向，每個方向有其強度值，四個小雪花，所以是 9 x 4。
圖4.3b、c、d則是輔助的文字說明。
Fig. 4.3a. PCA of HOG features, p. 1638 [1].
Fig. 4.3b. HOG: A 4 x 9 matrix, p. 1639 [1].
Fig. 4.3c. HOG: A vector of length 9 x 4, p. 2 [5].
Fig. 4.3d. HOG vs. SIFT, p. 6 [6].
-----
計算梯度的方法，在 [6] 中試了好幾個，以 [-1, 0, 1] 最佳，參考圖4.4a。
圖4.4b則是 HOG 計算方向的方法。可以跟 SIFT 比較不同之處。
Fig. 4.4a. HOG: Simple 1-D [-1, 0, 1] masks work best, p. 4 [6].
Fig. 4.4b. HOG: Gradient orientation and magnitude, p. 1638 [1].
-----
Q5: What is SVM?
A5:
這邊簡介一下 Support Vector Machine (SVM) 支持向量機 [13]。
圖5.1的 D(x) 是一個「超平面」。w 是一個 n 維的向量。
圖5.2是一個線性SVM，φ（x）= x。維度為 2，以此為例。
有兩類資料散佈在平面上（大致聚集成兩團），其值分別被標誌為 1 與 -1。
從中取出訓練集，找出 D(x) 使得 M 為最大，也就是找出D(x)=0兩旁虛線上的幾個向量，連帶找出 w （以及）b。這幾個向量就稱為支持向量。
在 [6] 中把訓練圖形的 HOG 計算出來後，則可以使用此處介紹的 Linear SVM 加以分類。
Fig. 5.1. The decision function in the direct space, p. 145 [13].
Fig. 5.2. Maximum margin linear decision function D(x), p. 146 [13].
-----
Q6: What is the Pyramid Structure?
A6:
參考圖6.1。其實這邊的金字塔只有兩層。
淺藍色的部分跟 [6] 一樣，是單純的行人檢測。
[1], [5] 與 [6] 的不同之處，在於加上了局部的結構，就是黃色的框框。
圖6.2則是測試圖與 L-SVM 訓練出來的模型。
Fig. 6.1. The HOG feature pyramid, p. 2 [5].
Fig. 6.2. Example detection obtained with the person model, p. 1 [5].
-----
這邊有個疑問就是 bounding box（圖6.3虛線部分）是如何找出來的。
[6] 是固定大小整張的 64 x 128，沒什麼問題。然後人都在中間部分。
在 [5] 跟 [1] 裡面，bounding box 是由資料庫提供，參考圖 6.4a與6.4b。
有疑問的在圖6.4c，根據 [4] 的說法，[1] 是用窮舉法把所有可能的位置都試過。可以參考圖7.1，filters 整張圖滑過，找出兩個人。
有關 bounding box 如何找出來，[4] 提供了很好的演算法，有機會報告 [4] 的時候再討論。
Fig. 6.3. The dotted box is the bounding box label provided in the PASCAL training set, p. 5 [5].
Fig. 6.4a. The dotted box is the bounding box label provided in the PASCAL training set, p. 5 [5].
Fig. 6.4b. Training models from images labeled with bounding boxes, p. 1636 [1].
Fig. 6.4c. Exhaustive search, p. 155 [4].
-----
圖6.5顯示一個較好的 bounding box 是 [1] 的副產品。
Fig. 6.5. A car detection and the bounding box predicted from the object configuration, p. 1640 [1].
-----
Q7: What is the flowchart of the object detection algorithm?
A7:
圖7.1是圖片偵測演算法的流程圖。
右上方是訓練好的模型。
計算出 HOG之後，大致就是整體與局部的加總。
主要的重點有二：
第一，局部的小框框，要用 [8], [9] 先找出來，參考圖7.2（[14], [15]）。
第二，局部的權重要經過 [8] 的轉換，參考圖7.3（[14]）。
這兩篇論文不在本篇的討論範圍內。
Fig. 7.1. The matching process at one scale, p. 1633 [1].
Fig. 7.2. Best locations of the parts, p. 1631 [1].
Fig. 7.3. Generalized distance transform, p. 1632 [1].
-----
[5] 跟 [6] 的主要差別。
[5] 多了局部，bounding box 大小在不同圖片中也不一樣。
Fig. 7.4. L-SVM vs. HOG, p. 1628 [1].
-----
[1] 跟 [5] 的主要差別。
同一類別中，[1] 訓練兩個（以上？）的 model，稱為 mixture model。
另外演算法改進了很多。
Fig. 7.5. L-SVM 2010 vs. L-SVM 2008, p. 1630 [1].
-----
Q8: What is the result?
A8:
圖8.1是一個腳踏車的模型，可以看到正面跟側面。
圖8.2是汽車的模型，顯示了從整體再到「整體加局部」的訓練過程。
圖8.3跟8.4是部分測試結果，有部分錯誤是因為條件設定的關係。
Fig. 8.1. Detections obtained with a two-component bicycle model, p.1629 [1].
Fig. 8.2. The result of Phase 1 (a), (b) and Phase 3 (c) of the initialization process, p. 1637 [1].
Fig. 8.3. Examples of high-scoring detections on the PASCAL 2007 data set, p. 1642 [1].
Fig. 8.4. Some results from the PASCAL 2007 dataset, p. 7 [5].
-----
結論：
HOG + SVM 曾經引領風騷很久，在目前 Deep Learning 大行其道之時，仍有很高的研究價值。
-----
References
[1] 2010_Object detection with discriminatively trained partbased models
[2] 2015_Active object localization with deep reinforcement learning
[3] 2014_Rich feature hierarchies for accurate object detection and semantic segmentation
[4] 2013_Selective search for object recognition
[5] 2008_A discriminatively trained, multiscale, deformable part model
[6] 2005_Histograms of oriented gradients for human detection
[7] 目標檢測的圖像特徵提取之（一）HOG特徵
http://alex-phd.blogspot.tw/2014/03/hog.html
[8] 2004_Distinctive image features from scale-invariant keypoints
[9] 2004_Distance transforms of sampled functions
[10] 2005_Pictorial structures for object recognition
[11] 2006_A tutorial on energy-based learning
[12] 2003_Support vector machines for multiple-instance learning
[13] 1992_A training algorithm for optimal margin classifiers
