Object Detection — HOG + SVM

防疫期間記得戴口罩... (Image by icsilviu from Pixabay)

此方法出自於 Histograms of Oriented Gradients for Human Detection [1]，早在 2005 年就已被發表出來，不過到現在依然有機會被使用，甚至有許多物體偵測的技術是由此方法衍生而來。

本篇主要是學習使用 OpenCV 內建訓練好的 SVM model 作行人偵測，我們先從演算法說起吧！

Algorithm

HOG + SVM 這項物體偵測技術可以拆成特徵提取與模型訓練這兩個部分。

HOG 的全名是 Histograms of Oriented Gradients，是一種特徵提取的技術，透過區塊中 Gradient 方向來分別統計累積的 Gradient 強度，並以此作為該區塊的特徵。這樣說起來有點拗口，沒關係...等等會有更仔細的說明。

SVM 的全名是 Support Vector Machine ，是一種機器學習的技術。簡單來說， SVM 是希望能找出超平面 (hyperplane) 正確區分不同類別的資料。

總結 HOG + SVM 的流程就是透過 HOG 提取影像當中的特徵，再丟入 SVM 判斷是否有行人出現在該區塊。

底下著重在了解 HOG 提取特徵的過程，我們一步一步慢慢來~ (網路上有找到一篇寫得不錯的文章，說明 HOG 的方式會跟 Histogram of Oriented Gradients explained using OpenCV 一模一樣，有興趣看原版的很推薦可以看看 [3])

HOG 計算的流程圖 (Image from Navneet Dalal [2])

Step 1 : Preprocessing

從原影像切出的 ROI (Image from Satya Mallick [3])

先從原影像切出此次要作 HOG 的 ROI，根據他們的實驗結果，ROI 大小設定為 64 x 128 會有最好的成果 [1]，但還是要視自己情況作調整。除此之外，作者為了避免受到 ROI 的顏色影響，會加入 Gamma correction 調整對比度，不過他們有提到或許是後面還會作 Normalization 的關係，所以做 Gamma correction 對結果影響不大。

Step 2 : Calculate the Gradient Images

接下來計算 Gradient，在影像上計算 Gradient 能夠凸顯影像的輪廓與邊緣，經由這些資訊我們就能了解影像當中的物體是什麼。平滑區域因為沒有輪廓資訊，Gradient 計算出來也會很小，因此在後續的分析中也就不會佔有一席之地。

Gradient 計算使用的 kernels (Image from Satya Mallick [3])

經過實驗後由以上這兩個 kernel 作 Gradient 計算能夠有較好的成效 [1]，左邊是計算 x 方向的 Gradient，右邊則是計算 y 方向的 Gradient，並且透過底下的計算就可以知道 Gradient 在每一個位置的強度與方向。

底下呈現對 ROI 計算 Gradient 後的結果

左邊是 x 方向 Gradient 的絕對值，中間是 y 方向 Gradient 的絕對值，右邊則是每一個位置的 Gradient 強度 (Image from Satya Mallick [3])

可以發現對 x 方向計算的 Gradient 會凸顯縱向方向的 edge，對 y 方向計算的 Gradient 會凸顯橫向方向的 edge，而合起來考慮的 Gradient 強度就會凸顯所有的 edge，至於較為平滑的區域就不會被顯現出來。

在 [3] 這篇中有提到，如果影像是有三個通道的 (ex. RGB)，就會選擇三個通道中 Gradient 強度最大的通道作為代表，而方向就由該通道的 Gradient 強度來計算得出。

Step 3 : Calculate Histogram of Gradients in 8 x 8 cells

再來就從這些 Gradient 提取出我們想要的特徵，一般來說會分成區塊來作分析，比較能夠避免受到單一 pixel 數值的影響，也能很有效的降低雜訊干擾。

至於為何選擇 1 個 cell 是 8 x 8 個 pixels？其實只是實驗過後發現結果較好~(如果應用在不同的題目上需選擇適當的大小)

左邊是將影像切成好幾個 cell，而中間就是把其中一個 cell 單獨拉出來看。可以發現除了很熟悉的 pixel 值外還有箭頭，這些箭頭就代表 Gradient 的強度與方向，箭頭越長則代表 Gradient 強度越大。右邊是各個 pixel 的 Gradient 強度與方向 (Image from Satya Mallick [3])

接下來進入重頭戲，也是此演算法會稱作 Histograms of Oriented Gradients 的原因。首先作者將 Gradient 角度分類成 0, 20, 40, 60, …, 140, 160 這 9 個類別組成的特徵向量。

這時候問題又來了，怎麼不分成 0–360 呢？一方面是因為 0–180 與 181–360 只差在方向不同，但 Gradient 強度是相同的，所以就沒有必要分成 0–360。另一方面則是 … 對 … 經過實驗證實 0–360 的結果沒有比較好 …，當然這方面的設定也可以依自己的情況而定。

選擇好要分成 0–180 之後 (其中 0 跟 180 因為只差在方向，所以用 0 代替)，現在就只要將每個 pixel 的 Gradient 強度填入特徵向量中對應的 Gradient 方向即可。底下提供兩個例子作說明：

以藍色圈起來的 pixel 為例，由於此 pixel 對應的 Gradient 方向是 80，所以就將此 pixel 對應的 Gradient 強度填入特徵向量中的 80 即可。紅色圈起來的 pixel 可以發現其 Gradient 方向是 10，介於 0 與 20 之間，因此就將其 Gradient 強度平均分配給 0 與 20。(Image from Satya Mallick [3])

由於 Gradient 方向是 165，所以 會是 0 (180) 與 160 作插值來看 Gradient 強度要如何分配 (Image from Satya Mallick [3])

將每一個 cell (8 x 8 pixels) 計算完後，會得到各個 Gradient 方向的 Gradient 強度加總。

一個 cell 累加 Gradient 強度的結果，其中橫軸代表 Gradient 方向 (Image from Satya Mallick [3])

Step 4 : 16 x 16 Block Normalization

一次對一個 block 作 Normalization。綠色框起來的為一個 cell，藍色框起來的為一個 block。block 每次只會移動一個 cell，因此 block 與 block 之間是有重疊的部分的 (Image from Satya Mallick [3])

由於 Gradient 的計算很容易受到影像的明亮度影響，影像越亮 Gradient 強度也就越大，因此需要作 Normalization 降低影像明亮度的影響。不過不是只對一個 cell 作 Normalization，而是由 4 個 cell 組成的 block 一起作 Normalization，也就是說一次會有 4 個特徵向量一起作 Normalization ，得出 36 x 1 的特徵向量代表 block。

Step 5 : Calculate the HOG feature vector

最終合併結果 (Image from Satya Mallick [3])

把每一個 block 都 Normalize 成 36 x 1 的特徵向量後，再將這些特徵向量全部接在一起變成一個很大的特徵向量來代表這個 ROI。以 ROI 大小為 64 x 128 為例，總共可以分成 8 x 16 個 cell，會有 7 x 15 個 block，因此就會產生 7 * 15 * 36 = 3780 維度的特徵向量！

Step 6 : Linear SVM

有了特徵向量後，就將特徵向量輸入 SVM 作訓練，最終訓練出能夠正確判斷行人的 SVM model。

真的很感謝 Satya Mallick 分享的 HOG 教學，真的讓我獲益良多，也是因為有這篇文章的幫助才讓我了解到 HOG 的細節！

附上 Navneet Dalal 針對不同參數所作的實驗結果 [1]

Image from Navneet Dalal [1]

Code

直接上程式碼，使用 OpenCV 內建訓練好的 model 作行人偵測

首先載入影像並且調整影像大小，主要是為了降低運算時間與降低 False Positive 的情況發生。第 8 行則是將影像複製到另一個變數，等等會用到。

在 1-8 行是 HOG+SVM 的相關參數設定，為了方便這裡直接使用 OpenCV 內建訓練好的 SVM model。

其實此方法雖然說可以得到比 Haar Feature-based Cascade Classifiers 更小的誤判率，但其實此演算法能不能完美偵測到目標物，一樣會很依賴 detectMultiScale 設定的參數好不好，尤其是 winStride 與 scale 這兩個參數。

winStride 是表示 window 與 window 之間的起始位置要間距多少，會輸入一個 tuple，分別代表 x 與 y 方向上的間距。如果設定的越大就代表 window 的間距越大，也就只有較少的 window 使用 HOG 尋找特徵，程式執行速度就會較快但成效較差；如果設定的越小則代表 window 的間距越小，就會有較多的 window 使用 HOG 尋找特徵，程式執行速度會較慢但成效較好。

scale 就如同 Haar Feature-based Cascade Classifiers 的 scaleFactor。簡單來說，設定的數值越小就有較多的影像要作分析，因此執行速度較慢但成效較好，反之則相反。

padding 是在使用 HOG 尋找特徵之前，會先在周圍貼 0。而根據 [1] 的實驗結果，如果有設定 padding 會讓物體偵測的效果更好。

至於 detectMultiScale 除了會回傳搜索到的 bounding box 座標之外，還有一個變數 weights，代表 SVM model 對這些 bounding box 的信心程度。

最後將找到的 bounding box 畫在影像上，不過可能會得到像底下的結果，會有 bounding box 重疊的狀況發生，但卻是偵測到同一個人... 明顯的這不是我們想要的...

可以發現在中間的地方有一個比較大的 bounding box 中有另一個小的 bounding box，但這並不會是我們想要的結果

這時候就可以透過 Non-Maximum Suppression 這項技術協助我們解決 bounding box 重疊的問題！我有寫一篇比較詳細的內容在 Non-Maximum Suppression，這裡就不多作說明 (其實那篇的影像跟這裡是相同的)。

在 3、4 行是將 bounding box 處理成可輸入 non_maximum_suppression 的形式。 overlapThresh 建議不要設定太小，畢竟行人之間的距離有時會很近，如果設定太小會使有些行人不被偵測到。

最後即可消除重疊的 bounding box 得到以下的結果。

重疊的 bounding box 被處理掉了且都有確實偵測到行人，這才是我們希望得到的結果！

[後記]：由於本篇是簡單的使用 OpenCV 內建訓練好的 model，所以整個過程看起來非常容易。不過如果需要客製化自己的訓練的話，可能會需要調整 window 大小，而這可以在 cv2.HOGDescriptor() 做修改。

另一點需要注意的是並不是每次執行 HOG+SVM 時都會產生 bounding box 重疊的狀況，這會根據設定的參數來決定。如果有出現該情況的話，再使用 Non-Maximum Suppression 處理掉即可。

Resource:

[1] Navneet Dalal and Bill Triggs. “Histograms of oriented gradients for human detection.” 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR’05). Vol. 1. Ieee, 2005.

[2] Navneet Dalal. Finding People in Images and Videos. Human-Computer Interaction [cs.HC]. Institut National Polytechnique de Grenoble — INPG, 2006. English. ￿tel-00390303

[3] Satya Mallick — Histogram of Oriented Gradients explained using OpenCV

[4] PyImageSearch — Pedestrian Detection OpenCV