目标檢測的NMS（非極大值抑制，Non-Maximum Suppression）

非極大值抑制NMS

• 概述
• 一、NMS
• • 1.原理
  • 2.代碼示例
• 二、NMS loss
• 三、Soft-NMS

概述

非極大值抑制（Non-Maximum Suppression，NMS），顧名思義就是抑制不是極大值的元素，可以了解為局部最大搜尋。這個局部代表的是一個鄰域，鄰域有兩個參數可變，一是鄰域的維數，二是鄰域的大小。

用于目标檢測中提取分數最高的視窗的。例如在行人檢測中，滑動視窗經提取特征，經分類器分類識别後，每個視窗都會得到一個分數。但是滑動視窗會導緻很多視窗與其他視窗存在包含或者大部分交叉的情況。這時就需要用到NMS來選取那些鄰域裡分數最高（是行人的機率最大），并且抑制那些分數低的視窗。

NMS在計算機視覺領域有着非常重要的應用，如視訊目标跟蹤、資料挖掘、3D重建、目辨別别以及紋理分析等。

一、NMS

在檢測圖像中的目标時，不可避免地會檢出很多bboxes + cls scores，這些bbox之間有很多是備援的，一個目标可能會被多個bboxes檢出，如果所有bboxes都輸出，就很影響體驗和美觀了（同一個目标輸出100個bboxes，想想都後怕~~~），一種方案就是提升cls scores的門檻值，減少bbox數量的輸出；另一種方案就是使用NMS，将同一目标内的bboxes按照cls score + IoU門檻值做篩選，剔除備援地、低置信度的bbox；

可能又會問了：為什麼目标檢測時，會有這麼多無效、備援檢測框呢？這個。。。我的了解，是因為圖像中沒有目标尺度、位置的先驗知識，為保證對目标的高召回，就必須使用滑窗、anchor / default bbox密集采樣的方式，盡管檢測模型能對每個anchor / default bbox做出 cls + reg，可以一定程度上剔除誤檢，但沒有結合檢出bbox的cls score + IoU門檻值做篩選，而NMS就可以做到這一點；

目标檢測中應用NMS算法的主要目的是消除多餘（交叉重複）的視窗，找到最佳物體檢測位置。

如上圖所示，人臉檢測中，雖然每個視窗均檢測到人臉，但僅需給出一個最有可能表征人臉的視窗

1.原理

對于Bounding Box的清單B及其對應的置信度S，采用下面的計算方式。

選擇具有最大score的檢測框M，将其從B集合中移除并加入到最終的檢測結果D中。

通常将B中剩餘檢測框中與M的IoU大于門檻值Nt的框從B中移除。

重複這個過程，直到B為空。

重疊率(重疊區域面積比例IOU)門檻值

IOU表示了bounding box 與 ground truth 的重疊度，如下圖所示：

常用的門檻值是 0.3 ~ 0.5。

其中用到排序，可以按照右下角的坐标排序或者面積排序，也可以是通過SVM等分類器得到的得分或機率，R-CNN中就是按得分進行的排序。

就像上面的圖檔一樣，定位一個車輛，最後算法就找出了一堆的方框，我們需要判别哪些矩形框是沒用的。

非極大值抑制的方法是：先假設有6個矩形框，根據分類器的類别分類機率做排序，假設從小到大屬于車輛的機率 分别為A、B、C、D、E、F。

1. 從最大機率矩形框F開始，分别判斷A~E與F的重疊度IOU是否大于某個設定的門檻值;
2. 假設B、D與F的重疊度超過門檻值，那麼就扔掉B、D；并标記第一個矩形框F，是我們保留下來的。
3. 從剩下的矩形框A、C、E中，選擇機率最大的E，然後判斷E與A、C的重疊度，重疊度大于一定的門檻值，那麼就扔掉；并标記E是我們保留下來的第二個矩形框。
4. 就這樣一直重複，找到所有被保留下來的矩形框。

另一種解釋：

step-1：将所有檢出的output_bbox按cls score劃分（如pascal voc分20個類，也即将output_bbox按照其對應的cls score劃分為21個集合，1個bg類，隻不過bg類就沒必要做NMS而已）；

step-2：在每個集合内根據各個bbox的cls score做降序排列，得到一個降序的list_k；

step-3：從list_k中top1 cls score開始，計算該bbox_x與list中其他bbox_y的IoU，若IoU大于門檻值T，則剔除該bbox_y，最終保留bbox_x，從list_k中取出；

step-4：選擇list_k中top2 cls score(步驟3取出top 1 bbox_x後，原list_k中的top 2就相當于現list_k中的top 1了，但如果step-3中剔除的bbox_y剛好是原list_k中的top 2，就依次找top 3即可，了解這麼個意思就行)，重複step-3中的疊代操作，直至list_k中所有bbox都完成篩選；

step-5：對每個集合的list_k，重複step-3、4中的疊代操作，直至所有list_k都完成篩選；

舉例說明：（1）（2），這裡設定交并比>=0.6就删除對比框圖，留下最高分的框圖；對于低于門檻值的框圖留下，然後在剩下的框圖中排序，選出置信度值高的框圖，然後重複交并比比較這個過程。

（1）選出Dog這個框圖

（2）選出Bike這個框圖

NMS方法如何運作呢？首先因為經過了排序，是以第一個框是機率最大的框（下圖橘色）。然後繼續掃描下一個框跟第一個框，看是否IOU大于0.5：

的确IOU大于0.5，那麼第二個框是多餘的，将它剔除：

繼續掃描到第三個框，它與最大機率框的IOU小于0.5，需要保留：

繼續掃描到第四個框，同理需要保留：

繼續掃描後面的框，直到所有框都與第一個框比較完畢。此時保留了不少框。

接下來，以次大機率的框（因為一開始排序過，它在順序上也一定是保留框中最靠近上一輪的基礎框的）為基礎，将它後面的其它框于之比較。

如比較第4個框與之的IOU：

IOU大于0.5，是以可以剔除第4個框：

總之在經曆了所有的掃描之後，對Dog類别隻留下了兩個框：

這時候，或許會有疑問：明顯留下來的藍色框，并非Dog，為什麼要留下？

因為對計算機來說，圖檔可能出現兩隻Dog，保留機率不為0的框是安全的。

不過的确後續設定了一定的門檻值（比如0.3）來删除掉機率太低的框，這裡的藍色框在最後并沒有保留，因為它在20種類别裡要麼因為IOU不夠而被删除，要麼因為最後門檻值不夠而被剔除。

2.代碼示例

在R-CNN中使用了NMS來确定最終的bbox，其對每個候選框送入分類器，根據分類器的類别分類機率做排序(論文中稱為greedy-NMS)。但其實也可以在分類之前運用簡單版本的NMS來去除一些框。

python實作的單類别NMS:py_cpu_nms.py

def py_cpu_nms(dets, thresh):
    """Pure Python NMS baseline."""
    #x1、y1、x2、y2、以及score指派
    x1 = dets[:, 0]
    y1 = dets[:, 1]
    x2 = dets[:, 2]
    y2 = dets[:, 3]
    scores = dets[:, 4]

    #每一個檢測框的面積
    areas = (x2 - x1 + 1) * (y2 - y1 + 1)
    #按照score置信度降序排序
    order = scores.argsort()[::-1]

    keep = [] #保留的結果框集合
    while order.size > 0:
        i = order[0]
        keep.append(i) #保留該類剩餘box中得分最高的一個
        #得到相交區域,左上及右下
        xx1 = np.maximum(x1[i], x1[order[1:]])
        yy1 = np.maximum(y1[i], y1[order[1:]])
        xx2 = np.minimum(x2[i], x2[order[1:]])
        yy2 = np.minimum(y2[i], y2[order[1:]])

        #計算相交的面積,不重疊時面積為0
        w = np.maximum(0.0, xx2 - xx1 + 1)
        h = np.maximum(0.0, yy2 - yy1 + 1)
        inter = w * h
        #計算IoU：重疊面積 /（面積1+面積2-重疊面積）
        ovr = inter / (areas[i] + areas[order[1:]] - inter)
        #保留IoU小于門檻值的box
        inds = np.where(ovr <= thresh)[0]
        order = order[inds + 1] #因為ovr數組的長度比order數組少一個,是以這裡要将所有下标後移一位
       
    return keep
           

aster R-CNN的MATLAB實作與python版實作一緻,代碼在這裡:nms.m.另外,nms_multiclass.m是多類别nms,加了一層for循環對每類進行nms而已.

二、NMS loss

值的注意的是對多類别檢測任務，如果對每類分别進行NMS，那麼當檢測結果中包含兩個被分到不同類别的目标且其IoU較大時，會得到不可接受的結果。

如下圖所示：

一種改進方式便是在損失函數中加入一部分NMS損失。NMS損失可以定義為與分類損失相同：

L n m s = L c l s ( p , u ) = − l o g p u L_{nms}=L_{cls}(p,u)=−logp_u Lnms​=Lcls​(p,u)=−logpu​

,即真實類别u對應的log損失，p是C個類别的預測機率。實際相當于增加分類誤差。

參考論文《Rotated Region Based CNN for Ship Detection》（IEEE2017會議論文）的Multi-task for NMS部分。

三、Soft-NMS

NMS算法的一個主要問題是當兩個ground truth的目标的确重疊度很高時,NMS會将具有較低置信度的框去掉(置信度改成0),參見下圖所示：

紅色框和綠色框是目前的檢測結果，二者的得分分别是0.95和0.80。如果按照傳統的NMS進行處理，首先選中得分最高的紅色框，然後綠色框就會因為與之重疊面積過大而被删掉。

思路：不要粗魯地删除所有IOU大于門檻值的框，而是降低其置信度。

論文:《Improving Object Detection With One Line of Code》

改進之處:

改進方法在于将置信度改為IoU的函數:f(IoU)，具有較低的值而不至于從排序清單中删去.

1.線性函數

函數值不連續,在某一點的值發生跳躍。

原來的NMS可以描述如下：将IOU大于門檻值的視窗的得分全部置為0。

2.高斯函數

時間複雜度同傳統的greedy-NMS,為O(N2)。

分析上面的兩種改進形式，思想都是：

M為目前得分最高框， 為待處理框， 和M的IOU越大， 的得分 就下降的越厲害。

soft-NMS python代碼實作:

ua = float((tx2 - tx1 + 1) * (ty2 - ty1 + 1) + area - iw * ih)
ov = iw * ih / ua #iou between max box and detection box

if method == 1: # linear
    if ov > Nt: 
        weight = 1 - ov
    else:
        weight = 1
elif method == 2: # gaussian
    weight = np.exp(-(ov * ov)/sigma)
else: # original NMS
    if ov > Nt: 
        weight = 0
    else:
        weight = 1
# re-scoring 修改置信度
boxes[pos, 4] = weight*boxes[pos, 4]
           

參考：

https://www.cnblogs.com/makefile/p/nms.html

https://blog.csdn.net/zouxiaolv/article/details/107400193