前言

Non-Maximum Suppression（NMS）非極大值抑制。從字面意思理解，抑制那些非極大值的元素，保留極大值元素。其主要用于目標(biāo)檢測，目標(biāo)跟蹤，3D重建，數(shù)據(jù)挖掘等。

目前NMS常用的有標(biāo)準(zhǔn)NMS, Soft NMS, DIOU NMS等。后續(xù)出現(xiàn)了新的Softer NMS，Weighted NMS等改進(jìn)版。

原始NMS

以目標(biāo)檢測為例，目標(biāo)檢測推理過程中會產(chǎn)生很多檢測框（A,B,C,D,E,F等），其中很多檢測框都是檢測同一個目標(biāo)，但最終每個目標(biāo)只需要一個檢測框，NMS選擇那個得分最高的檢測框（假設(shè)是C），再將C與剩余框計(jì)算相應(yīng)的IOU值，當(dāng)IOU值超過所設(shè)定的閾值（普遍設(shè)置為0.5，目標(biāo)檢測中常設(shè)置為0.7，僅供參考），即對超過閾值的框進(jìn)行抑制，抑制的做法是將檢測框的得分設(shè)置為0，如此一輪過后，在剩下檢測框中繼續(xù)尋找得分最高的，再抑制與之IOU超過閾值的框，直到最后會保留幾乎沒有重疊的框。這樣基本可以做到每個目標(biāo)只剩下一個檢測框。

原始NMS（左圖1維，右圖2維）算法偽代碼如下：

實(shí)現(xiàn)代碼：（以pytorch為例）

def NMS(boxes,scores, thresholds):    
    x1 = boxes[:,0]    
    y1 = boxes[:,1]    
    x2 = boxes[:,2]    
    y2 = boxes[:,3]    
    areas = (x2-x1)*(y2-y1)    
    
    _,order = scores.sort(0,descending=True)    
    keep = []    
    while order.numel() > 0:        
        i = order[0]        
        keep.Append(i)        
        if order.numel() == 1:            
            break        
        xx1 = x1[order[1:]].clamp(min=x1[i])        
        yy1 = y1[order[1:]].clamp(min=y1[i])        
        xx2 = x2[order[1:]].clamp(max=x2[i])        
        yy2 = y2[order[1:]].clamp(max=y2[i])  
        
        w = (xx2-xx1).clamp(min=0)        
        h = (yy2-yy1).clamp(min=0)        
        inter = w*h        
        
        ovr = inter/(areas[i] + areas[order[1:]] - inter)        
        ids = (ovr<=thresholds).nonzero().squeeze()     
        
        if ids.numel() == 0:            
            break        
        order = order[ids+1]    
    return torch.LongTensor(keep)

除了自己實(shí)現(xiàn)以外，也可以直接使用torchvision.ops.nms來實(shí)現(xiàn)。

torchvision.ops.nms(boxes, scores, iou_threshold)

上面這種做法是把所有boxes放在一起做NMS，沒有考慮類別。即某一類的boxes不應(yīng)該因?yàn)樗c另一類最大得分boxes的iou值超過閾值而被篩掉。

對于多類別NMS來說，它的思想比較簡單：每個類別內(nèi)部做NMS就可以了。實(shí)現(xiàn)方法：把每個box的坐標(biāo)添加一個偏移量，偏移量由類別索引來決定。

下面是
torchvision.ops.batched_nms的實(shí)現(xiàn)源碼以及使用方法

#實(shí)現(xiàn)源碼
max_coordinate = boxes.max()
offsets = idxs.to(boxes) * (max_coordinate + torch.tensor(1).to(boxes))
boxes_for_nms = boxes + offsets[:, None]
keep = nms(boxes_for_nms, scores, iou_threshold)
return keep

#使用方法
torchvision.ops.boxes.batched_nms(boxes, scores, classes, nms_thresh)

這里偏移量用boxes中最大的那個作為偏移基準(zhǔn)，然后每個類別索引乘以這個基準(zhǔn)即得到每個類的box對應(yīng)的偏移量。這樣就把所有的boxes按類別分開了。

在YOLO_v5中，它自己寫了個實(shí)現(xiàn)的代碼。

c = x[:, 5:6] * (0 if agnostic else max_wh)  # classes
boxes, scores = x[:, :4] + c, x[:, 4]  # boxes (offset by class), score
si = torchvision.ops.nms(boxes, scores, iou_thres)

這里的max_wh相當(dāng)于前面的boxes.max()，YOLO_v5中取的定值4096。這里的agnostic用來控制是否用于多類別NMS還是普通NMS。

NMS的缺點(diǎn)

需要手動設(shè)置閾值，閾值的設(shè)置會直接影響重疊目標(biāo)的檢測，太大造成誤檢，太小達(dá)不到理想情況。
低于閾值的直接設(shè)置score為0，做法太hard。
只能在CPU上運(yùn)行，成為影響速度的重要因素。
通過IoU來評估，IoU的做法對目標(biāo)框尺度和距離的影響不同。

NMS的改進(jìn)思路

根據(jù)手動設(shè)置閾值的缺陷，通過自適應(yīng)的方法在目標(biāo)系數(shù)時使用小閾值，目標(biāo)稠密時使用大閾值。例如Adaptive NMS。
將低于閾值的直接置為0的做法太hard，通過將其根據(jù)IoU大小來進(jìn)行懲罰衰減，則變得更加soft。例如Soft NMS，Softer NMS。
只能在CPU上運(yùn)行，速度太慢的改進(jìn)思路有三個，一個是設(shè)計(jì)在GPU上的NMS，如CUDA NMS，一個是設(shè)計(jì)更快的NMS，如Fast NMS，最后一個是掀桌子，設(shè)計(jì)一個神經(jīng)網(wǎng)絡(luò)來實(shí)現(xiàn)NMS，如ConvNMS。
IoU的做法存在一定缺陷，改進(jìn)思路是將目標(biāo)尺度、距離引進(jìn)IoU的考慮中。如DIoU。

下面稍微介紹一下這些方法中常用的一部分，另一部分僅提供鏈接。

Soft NMS

根據(jù)前面對目標(biāo)檢測中NMS的算法描述，易得出標(biāo)準(zhǔn)NMS容易出現(xiàn)的幾個問題：當(dāng)閾值過小時，如下圖所示，綠色框容易被抑制；當(dāng)過大時，容易造成誤檢，即抑制效果不明顯。因此，出現(xiàn)升級版soft NMS。

Soft NMS算法偽代碼如下：

標(biāo)準(zhǔn)的NMS的抑制函數(shù)如下：

IOU超過閾值的檢測框的得分直接設(shè)置為0，而soft NMS主張將其得分進(jìn)行懲罰衰減，有兩種衰減方式，第一種懲罰函數(shù)如下：

這種方式使用1-Iou與得分的乘積作為衰減后的值，但這種方式在略低于閾值和略高于閾值的部分，經(jīng)過懲罰衰減函數(shù)后，很容易導(dǎo)致得分排序的順序打亂，合理的懲罰函數(shù)應(yīng)該是具有高iou的有高的懲罰，低iou的有低的懲罰，它們中間應(yīng)該是逐漸過渡的。因此提出第二種高斯懲罰函數(shù)，具體如下：