薰風(fēng)說

Non-Maximum Suppression的翻譯是非“極大值”抑制，而不是非“最大值”抑制。這就說明了這個算法的用處：找到局部極大值，并篩除（抑制）鄰域內(nèi)其余的值。

這是一個很基礎(chǔ)的，簡單高效且適用于一維到多維的常見算法。因為特別適合目標(biāo)檢測問題，所以一直沿用至今，隨著目標(biāo)檢測研究的深入和要求的提高（eg：原來只想框方框，現(xiàn)在想框多邊形框），NMS也延伸出了不少變體。

與此同時，因為其比較基礎(chǔ)，簡單高效，因此我們更應(yīng)該掌握它的實現(xiàn)。

一、為何/何時/如何NMS? Why&When&How NMS？

非極大值抑制[1]（Non-Maximum Suppression，NMS），顧名思義就是抑制不是極大值的元素，可以理解為局部最大搜索。

這個局部代表的是一個鄰域，鄰域的“維度”和“大小”都是可變的參數(shù)。

NMS在計算機(jī)視覺領(lǐng)域有著非常重要的應(yīng)用，如視頻目標(biāo)跟蹤、3D重建、目標(biāo)識別以及紋理分析等。

1. 為何要用NMS Why NMS？

首先，目標(biāo)檢測與圖像分類不同，圖像分類往往只有一個輸出，但目標(biāo)檢測的輸出個數(shù)卻是未知的。除了Ground-Truth（標(biāo)注數(shù)據(jù)）訓(xùn)練，模型永遠(yuǎn)無法百分百確信自己要在一張圖上預(yù)測多少物體。

所以目標(biāo)檢測問題的老大難問題之一就是如何提高召回率。召回率（Recall）是模型找到所有某類目標(biāo)的能力（所有標(biāo)注的真實邊界框有多少被預(yù)測出來了）。檢測時按照是否檢出邊界框與邊界框是否存在，可以分為下表四種情況：

是所有某類物體中被檢測出的概率，并由下式給出：

為了提高這個值，很直觀的想法是“寧肯錯殺一千，絕不放過一個”。因此在目標(biāo)檢測中，模型往往會提出遠(yuǎn)高于實際數(shù)量的區(qū)域提議（Region Proposal，SSD等one-stage的Anchor也可以看作一種區(qū)域提議）。

這就導(dǎo)致最后輸出的邊界框數(shù)量往往遠(yuǎn)大于實際數(shù)量，而這些模型的輸出邊界框往往是堆疊在一起的。因此，我們需要NMS從堆疊的邊框中挑出最好的那個。

目標(biāo)檢測中的NMS

2. 何時使用NMS？When NMS?

回顧我在R-CNN中提到的流程：

提議區(qū)域

提取特征

目標(biāo)分類

回歸邊框

NMS使用在4. 回歸邊框之后，即所有的框已經(jīng)被分類且精修了位置。且所有區(qū)域提議的預(yù)測結(jié)果已經(jīng)由置信度與閾值初步篩選之后。

3. 如何非極大值抑制 How NMS？

一維簡單例子

由于重點是二維（目標(biāo)檢測）的實現(xiàn)，因此一維只放出偽代碼便于理解。

判斷一維數(shù)組I[W]的元素I[i](2<=i<=W-1)是否為局部極大值，即大于其左鄰元素I[i-1]和右鄰元素I[i+1]

算法流程如下圖所示：

算法流程3-5行判斷當(dāng)前元素是否大于其左鄰與右鄰元素，如符合條件，該元素即為極大值點。對于極大值點I[i]，已知I[i]>I[i+1]，故無需對i+1位置元素做進(jìn)一步處理，直接跳至i+2位置，對應(yīng)算法流程第12行。

若元素I[i]不滿足算法流程第3行判斷條件，將其右鄰I[i+1]作為極大值候選，對應(yīng)算法流程第7行。采用單調(diào)遞增的方式向右查找，直至找到滿足I[i]>I[i+1]的元素，若i<=W-1，該點即為極大值點，對應(yīng)算法流程第10-11行。

推廣至目標(biāo)檢測

首先，根據(jù)之前分析確認(rèn)NMS的前提，輸入與輸出。

使用前提

目標(biāo)檢測模型已經(jīng)完成了整個前向計算，并給出所有可能的邊界框（位置已精修）。

算法輸入

算法對一幅圖產(chǎn)生的所有的候選框，每個框有坐標(biāo)與對應(yīng)的打分（置信度）。

如一組5維數(shù)組：

• 每個組表明一個邊框，組數(shù)是待處理邊框數(shù)

• 4個數(shù)表示框的坐標(biāo)：X_max，X_min，Y_max，Y_min

• 1個數(shù)表示對應(yīng)分類下的置信度

注意：每次輸入的不是一張圖所有的邊框，而是一張圖中屬于某個類的所有邊框（因此極端情況下，若所有框的都被判斷為背景類，則NMS不執(zhí)行；反之若存在物體類邊框，那么有多少類物體則分別執(zhí)行多少次NMS）。

除此之外還有一個自行設(shè)置的參數(shù)：閾值 TH。

算法輸出

輸入的一個子集，同樣是一組5維數(shù)組，表示篩選后的邊界框。

算法流程

將所有的框按類別劃分，并剔除背景類，因為無需NMS。

對每個物體類中的邊界框(B_BOX)，按照分類置信度降序排列。

在某一類中，選擇置信度最高的邊界框B_BOX1，將B_BOX1從輸入列表中去除，并加入輸出列表。

逐個計算B_BOX1與其余B_BOX2的交并比IoU，若IoU(B_BOX1,B_BOX2) > 閾值TH，則在輸入去除B_BOX2。

重復(fù)步驟3~4，直到輸入列表為空，完成一個物體類的遍歷。

重復(fù)2~5，直到所有物體類的NMS處理完成。

輸出列表，算法結(jié)束

二、算法實現(xiàn)

1. 交并比

交并比（Interp over Union）是目標(biāo)檢測NMS的依據(jù)，因此首先要搞懂交并比及其實現(xiàn)。

衡量邊界框位置，常用交并比指標(biāo)，交并比（Injection Over Union，IOU）發(fā)展于集合論的雅卡爾指數(shù)（Jaccard Index）[3]，被用于計算真實邊界框Bgt（數(shù)據(jù)集的標(biāo)注）以及預(yù)測邊界框Bp（模型預(yù)測結(jié)果）的重疊程度。

具體來說，它是兩邊界框相交部分面積與相并部分面積之比，如下所示：

Python（numpy）代碼實現(xiàn)

import numpy as np def compute_iou(box1, box2, wh=False):"""compute the iou of two boxes.Args:box1, box2: [xmin, ymin, xmax, ymax] (wh=False) or [xcenter, ycenter, w, h] (wh=True)wh: the format of coordinate.Return:iou: iou of box1 and box2."""if wh == False:xmin1, ymin1, xmax1, ymax1 = box1xmin2, ymin2, xmax2, ymax2 = box2else:xmin1, ymin1 = int(box1[0]-box1[2]/2.0), int(box1[1]-box1[3]/2.0)xmax1, ymax1 = int(box1[0]+box1[2]/2.0), int(box1[1]+box1[3]/2.0)xmin2, ymin2 = int(box2[0]-box2[2]/2.0), int(box2[1]-box2[3]/2.0)xmax2, ymax2 = int(box2[0]+box2[2]/2.0), int(box2[1]+box2[3]/2.0)## 獲取矩形框交集對應(yīng)的左上角和右下角的坐標(biāo)（interp）xx1 = np.max([xmin1, xmin2])yy1 = np.max([ymin1, ymin2])xx2 = np.min([xmax1, xmax2])yy2 = np.min([ymax1, ymax2])## 計算兩個矩形框面積area1 = (xmax1-xmin1) * (ymax1-ymin1) area2 = (xmax2-xmin2) * (ymax2-ymin2)inter_area = (np.max([0, xx2-xx1])) * (np.max([0, yy2-yy1]))#計算交集面積iou = inter_area / (area1+area2-inter_area+1e-6)＃計算交并比 return iou

2. NMS的Python實現(xiàn)

從R-CNN開始，到fast R-CNN，faster R-CNN……都不難看到NMS的身影，且因為實現(xiàn)功能類似，基本的程序都是定型的，這里就分析Faster RCNN的NMS實現(xiàn)：

Python（numpy）代碼實現(xiàn)

注意，這里的NMS是單類別的！多類別則只需要在外加一個for循環(huán)遍歷每個種類即可

def py_cpu_nms(dets, thresh): """Pure Python NMS baseline.""" #dets某個類的框，x1、y1、x2、y2、以及置信度score#eg:dets為[[x1,y1,x2,y2,score],[x1,y1,y2,score]……]]# thresh是IoU的閾值 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 = [] #保留的結(jié)果框集合 while order.size > 0: i = order[0] keep.append(i) #保留該類剩余box中得分最高的一個 #得到相交區(qū)域,左上及右下 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數(shù)組的長度比order數(shù)組少一個,所以這里要將所有下標(biāo)后移一位 return keep

Faster R-CNN的MATLAB實現(xiàn)與python版實現(xiàn)一致,代碼在這里:nms.m.另外,nms_multiclass.m是多類別nms,加了一層for循環(huán)對每類進(jìn)行nms而已.

3. NMS的Pytorch實現(xiàn)

在Pytorch中，數(shù)據(jù)類型從numpy的數(shù)組變成了pytorch的tensor，因此具體的實現(xiàn)需要改變寫法，但核心思路是不變的。

這里的實現(xiàn)參照了知乎大佬TeddyZhang的專欄

IoU計算的Pytorch源碼為：（注意矩陣維度的變化）

# IOU計算# 假設(shè)box1維度為[N,4] box2維度為[M,4]def iou(self, box1, box2):N = box1.size(0)M = box2.size(0)lt = torch.max( # 左上角的點box1[:, :2].unsqueeze(1).expand(N, M, 2), # [N,2]->[N,1,2]->[N,M,2]box2[:, :2].unsqueeze(0).expand(N, M, 2), # [M,2]->[1,M,2]->[N,M,2])rb = torch.min(box1[:, 2:].unsqueeze(1).expand(N, M, 2),box2[:, 2:].unsqueeze(0).expand(N, M, 2),)wh = rb - lt # [N,M,2]wh[wh < 0] = 0 # 兩個box沒有重疊區(qū)域inter = wh[:,:,0] * wh[:,:,1] # [N,M]area1 = (box1[:,2]-box1[:,0]) * (box1[:,3]-box1[:,1]) # (N,)area2 = (box2[:,2]-box2[:,0]) * (box2[:,3]-box2[:,1]) # (M,)area1 = area1.unsqueeze(1).expand(N,M) # (N,M)area2 = area2.unsqueeze(0).expand(N,M) # (N,M)iou = inter / (area1+area2-inter)return iou

其中：

• torch.unsqueeze(1) 表示增加一個維度，增加位置為維度1

• torch.squeeze(1) 表示減少一個維度

# NMS算法# bboxes維度為[N,4]，scores維度為[N,], 均為tensordef nms(self, bboxes, scores, threshold=0.5):x1 = bboxes[:,0]y1 = bboxes[:,1]x2 = bboxes[:,2]y2 = bboxes[:,3]areas = (x2-x1)*(y2-y1) # [N,] 每個bbox的面積_, order = scores.sort(0, descending=True) # 降序排列keep = []while order.numel() > 0: # torch.numel()返回張量元素個數(shù)if order.numel() == 1: # 保留框只剩一個i = order.item()keep.append(i)breakelse:i = order[0].item() # 保留scores最大的那個框box[i]keep.append(i)# 計算box[i]與其余各框的IOU(思路很好)xx1 = x1[order[1:]].clamp(min=x1[i]) # [N-1,]yy1 = y1[order[1:]].clamp(min=y1[i])xx2 = x2[order[1:]].clamp(max=x2[i])yy2 = y2[order[1:]].clamp(max=y2[i])inter = (xx2-xx1).clamp(min=0) * (yy2-yy1).clamp(min=0) # [N-1,]iou = inter / (areas[i]+areas[order[1:]]-inter) # [N-1,]idx = (iou <= threshold).nonzero().squeeze() # 注意此時idx為[N-1,] 而order為[N,]if idx.numel() == 0:breakorder = order[idx+1] # 修補(bǔ)索引之間的差值return torch.LongTensor(keep) # Pytorch的索引值為LongTensor

其中：

• torch.numel() 表示一個張量總元素的個數(shù)

• torch.clamp(min, max) 設(shè)置上下限

• tensor.item() 把tensor元素取出作為numpy數(shù)字

4. C++實現(xiàn)NMS

C++代碼來自這個博客，真希望我也能有大佬們的碼力233……畢竟搞工程早晚會掣肘于Python的

NMS和soft-nms算法 - outthinker - 博客園www.cnblogs.com

程序整體思路：

先將box中的數(shù)據(jù)分別存入x1，y1，x2，y2，s中，分別為坐標(biāo)和置信度，算出每個框的面積，存入area，基于置信度s，從小到達(dá)進(jìn)行排序，做一個while循環(huán)，取出置信度最高的，即排序后的最后一個，然后將該框進(jìn)行保留，存入pick中，然后和其他所有的框進(jìn)行比對，大于規(guī)定閾值就將別的框去掉，并將該置信度最高的框和所有比對過程，大于閾值的框存入suppress，for循環(huán)后，將I中滿足suppress條件的置為空。直到I為空退出while。

static void sort(int n, const float* x, int* indices) { // 排序函數(shù)(降序排序)，排序后進(jìn)行交換的是indices中的數(shù)據(jù) // n：排序總數(shù)// x：帶排序數(shù)// indices：初始為0~n-1數(shù)目 int i, j; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) { if (x[indices[j]] > x[indices[i]]) { //float x_tmp = x[i]; int index_tmp = indices[i]; //x[i] = x[j]; indices[i] = indices[j]; //x[j] = x_tmp; indices[j] = index_tmp; } } }int nonMaximumSuppression(int numBoxes, const CvPoint *points, const CvPoint *oppositePoints, const float *score, float overlapThreshold, int *numBoxesOut, CvPoint **pointsOut, CvPoint **oppositePointsOut, float **scoreOut) { // numBoxes：窗口數(shù)目// points：窗口左上角坐標(biāo)點// oppositePoints：窗口右下角坐標(biāo)點 // score：窗口得分// overlapThreshold：重疊閾值控制// numBoxesOut：輸出窗口數(shù)目 // pointsOut：輸出窗口左上角坐標(biāo)點// oppositePoints：輸出窗口右下角坐標(biāo)點 // scoreOut：輸出窗口得分 int i, j, index; float* box_area = (float*)malloc(numBoxes * sizeof(float)); // 定義窗口面積變量并分配空間 int* indices = (int*)malloc(numBoxes * sizeof(int)); // 定義窗口索引并分配空間 int* is_suppressed = (int*)malloc(numBoxes * sizeof(int)); // 定義是否抑制表標(biāo)志并分配空間 // 初始化indices、is_supperssed、box_area信息 for (i = 0; i < numBoxes; i++) { indices[i] = i; is_suppressed[i] = 0; box_area[i] = (float)( (oppositePoints[i].x - points[i].x + 1) * (oppositePoints[i].y - points[i].y + 1)); } // 對輸入窗口按照分?jǐn)?shù)比值進(jìn)行排序，排序后的編號放在indices中 sort(numBoxes, score, indices); for (i = 0; i < numBoxes; i++) // 循環(huán)所有窗口 { if (!is_suppressed[indices[i]]) // 判斷窗口是否被抑制 { for (j = i + 1; j < numBoxes; j++) // 循環(huán)當(dāng)前窗口之后的窗口 { if (!is_suppressed[indices[j]]) // 判斷窗口是否被抑制 { int x1max = max(points[indices[i]].x, points[indices[j]].x); // 求兩個窗口左上角x坐標(biāo)最大值 int x2min = min(oppositePoints[indices[i]].x, oppositePoints[indices[j]].x); // 求兩個窗口右下角x坐標(biāo)最小值 int y1max = max(points[indices[i]].y, points[indices[j]].y); // 求兩個窗口左上角y坐標(biāo)最大值 int y2min = min(oppositePoints[indices[i]].y, oppositePoints[indices[j]].y); // 求兩個窗口右下角y坐標(biāo)最小值 int overlapWidth = x2min - x1max + 1; // 計算兩矩形重疊的寬度 int overlapHeight = y2min - y1max + 1; // 計算兩矩形重疊的高度 if (overlapWidth > 0 && overlapHeight > 0) { float overlapPart = (overlapWidth * overlapHeight) / box_area[indices[j]]; // 計算重疊的比率 if (overlapPart > overlapThreshold) // 判斷重疊比率是否超過重疊閾值 { is_suppressed[indices[j]] = 1; // 將窗口j標(biāo)記為抑制 } } } } } } *numBoxesOut = 0; // 初始化輸出窗口數(shù)目0 for (i = 0; i < numBoxes; i++) { if (!is_suppressed[i]) (*numBoxesOut)++; // 統(tǒng)計輸出窗口數(shù)目 } *pointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配輸出窗口左上角坐標(biāo)空間 *oppositePointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配輸出窗口右下角坐標(biāo)空間 *scoreOut = (float *)malloc((*numBoxesOut) * sizeof(float)); // 分配輸出窗口得分空間 index = 0; for (i = 0; i < numBoxes; i++) // 遍歷所有輸入窗口 { if (!is_suppressed[indices[i]]) // 將未發(fā)生抑制的窗口信息保存到輸出信息中 { (*pointsOut)[index].x = points[indices[i]].x; (*pointsOut)[index].y = points[indices[i]].y; (*oppositePointsOut)[index].x = oppositePoints[indices[i]].x; (*oppositePointsOut)[index].y = oppositePoints[indices[i]].y; (*scoreOut)[index] = score[indices[i]]; index++; } } free(indices); // 釋放indices空間 free(box_area); // 釋放box_area空間 free(is_suppressed); // 釋放is_suppressed空間 return LATENT_SVM_OK; }

碎碎念&絮叨一下

作為一個半路出家的初學(xué)者（本科電子信息工程，跨保CS），對coding一直處于某種“焦慮”的狀態(tài)。

比如我可以花時間看懂別人的實現(xiàn)，也能在這個基礎(chǔ)上小修小補(bǔ)，但從頭搭建一個程序總會讓我有一種莫名的抵觸情緒。

而我也認(rèn)識到，如果我想在個行業(yè)做出點成果，那不僅僅是需要git clone，調(diào)包調(diào)參那么簡單，我必須從頭開始一點點實現(xiàn)。甚至深入到一些框架的底層另起爐灶才能實現(xiàn)自己大膽的想法。

我離能夠隨心所欲地實現(xiàn)自己想法還有多遠(yuǎn)呢……希望越早越好吧，如果有幸你能看到這里，又有些經(jīng)驗可以分享的話。能說給我聽聽嗎？

參考文獻(xiàn)

[1]Neubeck A , Gool L J V . Efficient Non-Maximum Suppression[C]// 18th International Conference on Pattern Recognition (ICPR 2006), 20-24 August 2006, Hong Kong, China. IEEE Computer Society, 2006.

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊深度學(xué)習(xí)筆記專輯《統(tǒng)計學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯 獲取本站知識星球優(yōu)惠券，復(fù)制鏈接直接打開： https://t.zsxq.com/qFiUFMV 本站qq群704220115。加入微信群請掃碼：

總結(jié)

以上是生活随笔為你收集整理的【深度学习】非极大值抑制Non-Maximum Suppression（NMS）一文搞定理论+多平台实现...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。