機器/深度學習: 物件偵測 Non-Maximum Suppression (NMS)

Tommy Huang
7 min readSep 28, 2018

--

基本上在影像物件偵測領域上,都是先會選出物件候選人,然後在物件候選人中判斷是不是物件,但有可能一個物件被很多候選框給選到(如下圖),下左圖就是一個例子假設算法抓到這麼多框都是物件,這時候要怎麼處理,幾乎最後的作法都是用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的演算法流程如下圖,坦白說很難懂。

source

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)

我們假設這張圖我們捉到5個BBox(如上圖),每個BBox帶有一個socre,代表他是foreground的信心度。

這邊還要對IoU計算設定一個閾值(threshold),也就是兩個框如果框太近(IoU值太大),那就要刪掉一個框。

所以步驟是
1. 先看哪個BBox的信心程度最高,那個BBox會進去「確定是物件集合」(途中的selected objects)內
2. 其他BBox和剛選出來的BBox算IoU,然後算出來的IoU大於設定好的閾值的BBox,那些BBox的信心度會被設定為0(也就是這個BBox重複計算要刪掉)。

然後在Repeat 1和2步驟直到所有的BBox都被處理完,這時候被存在「確定是物件集合」的物件就是最後結果。

實際流程如下圖:

  1. 「確定是物件集合」= {空集合}
  2. Run 1: 先將BBox依照信心程度排序,信心程度最高的BBox (紅色) 會被選入「確定是物件集合」內,其他BBox會看這步驟選出最高的BBox進行IoU計算,如果粉紅色的IoU為0.6大於我們設定的0.5,所以將粉紅色的BBox信心度設置為0。「確定是物件集合」= {紅色BBox }
  3. Run 2: 不考慮信心度為0和已經在「確定是物件集合」的BBox,剩下來的物件繼續選出最大信心程度的BBox,將此BBox(黃色)丟入「確定是物件集合」,剩下的BBox和Run2選出的最大信心程度的BBox計算IoU,其他BBox都大於0.5,所以其他的BBox信心度設置為0。「確定是物件集合」= {紅色BBox; 黃色BBox}
  4. 因為沒有物件信心度>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: 文章都是我自己看論文和一些部落格整理出來的,所以不一定都對,如果有錯誤麻煩指教一下,感恩。

--

--

Tommy Huang

怕老了忘記這些吃飯的知識,開始寫文章記錄機器/深度學習相關內容。Medium現在有打賞功能(每篇文章最後面都有連結),如果覺得寫的文章不錯,也可以Donate給個Tipping吧。黃志勝 Chih-Sheng Huang (Tommy), mail: chih.sheng.huang821@gmail.com