詳解非極大值抑制算法之Python實現

Posted on by

一、概述

這裡不討論通用的NMS算法(參考論文《Efficient Non-Maximum Suppression》對1維和2維數據的NMS實現)，而是用於目標檢測中提取分數最高的窗口的。例如在行人檢測中，滑動窗口經提取特征，經分類器分類識別後，每個窗口都會得到一個分數。但是滑動窗口會導致很多窗口與其他窗口存在包含或者大部分交叉的情況。這時就需要用到NMS來選取那些鄰域裡分數最高（是行人的概率最大），並且抑制那些分數低的窗口。

NMS在計算機視覺領域有著非常重要的應用，如視頻目標跟蹤、數據挖掘、3D重建、目標識別以及紋理分析等。

二、NMS 在目標檢測中的應用

2.1、人臉檢測框重疊例子

我們的目的就是要去除冗餘的檢測框,保留最好的一個.

有多種方式可以解決這個問題,Triggs et al. 建議使用Mean-Shift 算法,利用bbox的坐標和當前圖片尺度的對數來檢測bbox的多種模式.但效果可能並不如使用強分類器結合NMS的效果好.

2.2、目標檢測 pipline

產生proposal後使用分類網絡給出每個框的每類置信度,使用回歸網絡修正位置,最終應用NMS.

三、NMS 原理

對於Bounding Box的列表B及其對應的置信度S,采用下面的計算方式.選擇具有最大score的檢測框M,將其從B集合中移除並加入到最終的檢測結果D中.通常將B中剩餘檢測框中與M的IoU大於閾值Nt的框從B中移除.重復這個過程,直到B為空.

3.1、重疊率(重疊區域面積比例IOU)閾值

常用的閾值是 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是我們保留下來的第二個矩形框。

就這樣一直重復，找到所有被保留下來的矩形框。

3.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

Faster R-CNN的MATLAB實現與python版實現一致,代碼在這裡:nms.m.另外,nms_multiclass.m是多類別nms,加瞭一層for循環對每類進行nms而已.

四、NMS loss

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

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

即真實列別u對應的log損失，p是C個類別的預測概率。實際相當於增加分類誤差。
參考論文《Rotated Region Based CNN for Ship Detection》（IEEE2017會議論文）的Multi-task for NMS部分。

五、Soft-NMS

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

論文:《Improving Object Detection With One Line of Code》
改進之處:

改進方法在於將置信度改為IoU的函數:f(IoU),具有較低的值而不至於從排序列表中刪去.

1.線性函數

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

2.高斯函數

時間復雜度同傳統的greedy-NMS,為

5.1、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]

5.2、Caffe C++ 版實現

makefile/frcnn

效果

在基於proposal方法的模型結果上應用比較好,檢測效果提升:

在R-FCN以及Faster-RCNN模型中的測試階段運用Soft-NMS,在MS-COCO數據集上mAP@[0.5:0.95]能夠獲得大約1%的提升(詳見這裡). 如果應用到訓練階段的proposal選取過程理論上也能獲得提升. 在自己的實驗中發現確實對易重疊的目標類型有提高(目標不一定真的有像素上的重疊,切斜的目標的矩形邊框會有較大的重疊).
而在SSD,YOLO等非proposal方法中沒有提升.

六、其它應用

邊緣檢測:Canny算子中的非極大值抑制是沿著梯度方向進行的，即是否為梯度方向上的極值點；

特征點檢測:在角點檢測等場景下說的非極大值抑制，則是檢測中心點處的值是否是某一個鄰域內的最大值.

以上就是詳解非極大值抑制算法之Python實現的詳細內容，更多關於非極大值抑制 Python實現的資料請關註WalkonNet其它相關文章！

推薦閱讀：