機器/深度學習: 物件偵測 Non-Maximum Suppression (NMS)
基本上在影像物件偵測領域上，都是先會選出物件候選人，然後在物件候選人中判斷是不是物件，但有可能一個物件被很多候選框給選到(如下圖)，下左圖就是一個例子假設算法抓到這麼多框都是物件，這時候要怎麼處理，幾乎最後的作法都是用Non-Maximum Suppression的方法去消除多餘物件框找到最佳的框，所以這篇要介紹的就是NMS這個方法。
這個選出來的框叫做Bounding Box/Boundary Box (也有人稱BBox)，每個BBox除了框的中心(x, y)和長寬(h, w)外，幾乎都會有一個confidence score。
這個score代表的就是這個框是background還是foreground的信心程度，基本上介於0~1，白話說Score=1代表這個框可以肯定是一個物件，但這個物件是什麼類別要在看相對應的分類機率。
所以一般每個BBox實際上帶有的資訊 (假設我們只偵測2個物件(貓和狗))，一般算法至少包含: BBox中心位置(x, y)、BBox長寬(h, w)、confidence score、BBox相對應是貓的機率和BBox相對應是狗的機率，共5+2=7。(如果演算法要做100類的偵測，那機率部分就會有100個輸出，那這個BBox總共會有5+100=105個輸出)。
一般文章會寫到NMS的演算法流程如下圖，坦白說很難懂。
NMS實際做法真的很簡單，這邊我會舉兩個例子說明，上面演算法參考就好了。
- 第一個例子，有兩隻狗，我們怎麼用NMS將偵測到的物件框將把兩隻狗框出來。
- 第二個例子，有1隻狗1隻貓，我們怎麼用NMS將偵測到的物件框將把貓和狗框出來。
第一個例子，有兩隻狗，我們怎麼用NMS將偵測到的物件框將把兩隻狗框出來
前面提到每個BBox會帶有BBox中心位置(x, y)、BBox長寬(h, w)、confidence score、BBox相對應是貓的機率和BBox相對應是狗的機率，但範例一我只看怎麼抓出狗，所以範例一我們只用到五個資訊
1. BBox中心位置(x, y)和BBox長寬(h, w): 這邊是算IoU用的。
2. confidence score。
Note: IOU怎麼算可以參考這篇「深度學習系列: 什麼是AP/mAP?」最後面有寫怎麼計算IOU (intersection over union)
這邊還要對IoU計算設定一個閾值(threshold)，也就是兩個框如果框太近(IoU值太大)，那就要刪掉一個框。
所以步驟是
1. 先看哪個BBox的信心程度最高，那個BBox會進去「確定是物件集合」(途中的selected objects)內
2. 其他BBox和剛選出來的BBox算IoU，然後算出來的IoU大於設定好的閾值的BBox，那些BBox的信心度會被設定為0(也就是這個BBox重複計算要刪掉)。
然後在Repeat 1和2步驟直到所有的BBox都被處理完，這時候被存在「確定是物件集合」的物件就是最後結果。
實際流程如下圖:
- 「確定是物件集合」= {空集合}
- Run 1: 先將BBox依照信心程度排序，信心程度最高的BBox (紅色) 會被選入「確定是物件集合」內，其他BBox會看這步驟選出最高的BBox進行IoU計算，如果粉紅色的IoU為0.6大於我們設定的0.5，所以將粉紅色的BBox信心度設置為0。「確定是物件集合」= {紅色BBox }
- Run 2: 不考慮信心度為0和已經在「確定是物件集合」的BBox，剩下來的物件繼續選出最大信心程度的BBox，將此BBox(黃色)丟入「確定是物件集合」，剩下的BBox和Run2選出的最大信心程度的BBox計算IoU，其他BBox都大於0.5，所以其他的BBox信心度設置為0。「確定是物件集合」= {紅色BBox; 黃色BBox}
- 因為沒有物件信心度>0，所以結束NMS。
「確定是物件集合」= {紅色BBox; 黃色BBox}。
這邊衍生一個問題，為什麼IoU設定是0.5，不能在高一點嗎?
剛剛的例子我這邊舉一個IoU閾值是0.7的例子(下圖)，看會發生什麼問題?
由此可以知道，如果IoU閾值設定太高，可能會造成物件重複偵測的問題。
第二個例子，有1隻狗1隻貓，我們怎麼用NMS將偵測到的物件框將把貓和狗框出來
前面的範例一是標準的NMS程序，這邊要搭配一下分類來看，範例二和標準NSM作法一樣，先將「確定是物件集合」選出來，此例是NMS選出的BBox是{紫色BBox ; 紅色BBox}。
這時候在搭配一下分類的機率，就可以把每個NMS選出的BBox做類別判斷了(如下圖，每個BBox都會帶有一組機率)。
看完上面圖解法後，應該對NMS很了解了阿。
這邊附上實際做法，還會先用一個閾值先初步去掉一些候選的BBox，不然假設一張圖預選出一萬個BBox，後面用CPU計算NMS會很花時間，所以會依據BBox的confidence score先去掉一些沒用的BBox，然後再做NMS，如下圖。
這邊稍微提一下
如果是two stage算法，通常在選出BBox只會帶有BBox中心位置(x, y)、BBox長寬(h, w)和confidence score，不會有類別的機率，因為程序是先選出BBox，在將選出BBox的feature map做rescale (一般用ROI pooling)，然後再用分類器分類。
但如果是one stage作法，是直接BBox帶有BBox中心位置(x, y)、BBox長寬(h, w)和confidence score，以及相對應的分類機率，相對於two stage少了後面rescale和分類的程序，所以計算量相對小。
因為如果two stage選出300個物件，後面ROI pooling只能用CPU算，很花時間的，NMS也只能用CPU算，所以one stage的做法是目前主流，要做到又快又好，計算量(參數量)和mAP兩個目前是trade offs，若能計算量小(參數量也小)，然後mAP 同時高，這就是演算法開發的目標，目前的關鍵是模型壓縮法，這部分論文方法超多(如: Pruning、Quantization、Low-rank factorization、Transferred/compact convolutional filters和Knowledge distillation，可以參考這篇文章「A Survey of Model Compression and Acceleration for Deep Neural Networks」)。
Note: 文章都是我自己看論文和一些部落格整理出來的，所以不一定都對，如果有錯誤麻煩指教一下，感恩。
