Non-Maximum Suppression (NMS) — 消除多餘 bounding box
經常可以發現在實現物體偵測後，會出現目標物被很多重疊的 bounding box 包圍住的情況 (如同上圖)。這個問題不論是使用傳統影像處理的技術或是深度學習的技術都會碰到同樣的問題，因此我們就需要 Non-maximum suppression (NMS) 幫助我們處理 bounding box 互相重疊的問題。
Felzenszwalb et al.
首先要介紹的方法是 Felzenszwalb et al. 團隊發表的方法 [1,2]，算是 Greedy algorithm 的一種，底下直接附上程式碼。(他們也有建立自己的 Matlab code 可以使用)
[註] Greedy algorithm 在解決最佳化問題的方法中，是一種很簡單且直覺的演算法。想法是每一步都採用當前狀態下最好或是最佳的選擇來得出最終解，不過由於每一步都只會考慮當下的狀況，因此最終解並不一定會等於最佳解。即便如此，在一般情況下都可以得出還不錯的結果。
雖然看起來很複雜但其實想法很簡單，我們一步一步來看...
把 bounding box 輸入 function 後，會在 23-26 行取出 bounding box 的左上角與右下角的座標 (轉換成 float 的資料型態是因為後面有除法計算)，並且在 29 行計算出每一個 bounding box 的面積。接著在 32 行對右下角位置的 y 座標做排序，這就是剛剛提到的 Greedy algorithm 的想法。
第 35 行開始的迴圈，每一輪都會挑選出右下角 y 座標最大的 bounding box 作為此輪迴圈的考慮對象，並且放入 pick 這個 list 當中 。pick 代表最終要保留的 bounding box，與之相對的是在 47 行定義的 suppress，代表會捨棄的 bounding box。
第 50 行開始的迴圈則是在檢查此輪考慮的 bounding box 與其他 bounding box 重疊的部分有沒有大於 overlapThresh，如果有的話就將拿來比較的 bounding box 放入 suppress 當中，並且在第 72 行從 sort_index 刪除。
Malisiewicz et al.
其實此演算法是 Felzenszwalb et al. 方法的變形，只差在 Malisiewicz et al. 將第二個迴圈拿掉來加快運算速度 (據他們所說，加快了 100 倍！)，底下就來看程式碼 (他們提供的 Matlab code) [3]
在 49-52 行中，可以發現到不像 Felzenszwalb et al. 是使用 for 迴圈一個一個計算 bounding box 重疊的區域，而直接一次把所有重疊的部分算完。在 55、56 行會計算這些重疊部分的面積是多少並比較重疊比例有沒有超過 overlapThresh。最後在第 62 行考慮要刪除哪些 bounding box 時，別忘了將已經挑選的 bounding box 也一起刪除，才不會重複考慮。
Resource:
[1] Pedro Felzenszwalb, David McAllester, and Deva Ramanan. “A discriminatively trained, multiscale, deformable part model.” 2008 IEEE conference on computer vision and pattern recognition. IEEE, 2008.
[2] Pedro F. Felzenszwalb, et al. “Object detection with discriminatively trained part-based models.” IEEE transactions on pattern analysis and machine intelligence 32.9 (2009): 1627–1645.
[3] Tomasz Malisiewicz, Abhinav Gupta, and Alexei A. Efros. “Ensemble of exemplar-svms for object detection and beyond.” 2011 International conference on computer vision. IEEE, 2011.
[4] PyImageSearch — Non-Maximum Suppression for Object Detection in Python
[5] PyImageSearch — (Faster) Non-Maximum Suppression in Python
