非极大值抑制(Non-Maximum Suppression)

发表于 | 分类于

非极大值抑制

非极大值抑制，简称为NMS算法，英文为Non-Maximum Suppression。其思想是搜素局部最大值，抑制极大值。NMS算法在不同应用中的具体实现不太一样，但思想是一样的。非极大值抑制，在计算机视觉任务中得到了广泛的应用，例如边缘检测、人脸检测、目标检测（DPM，YOLO，SSD，Faster R-CNN）等。

算法用途

以目标检测为例：目标检测的过程中在同一目标的位置上会产生大量的候选框，这些候选框相互之间可能会有重叠，此时我们需要利用非极大值抑制找到最佳的目标边界框，消除冗余的边界框。

左图是人脸检测的候选框结果，每个边界框有一个置信度得分(confidence score)，如果不使用非极大值抑制，就会有多个候选框出现。右图是使用非极大值抑制之后的结果，符合我们人脸检测的预期结果。

nms算法过程

  • 根据置信度得分进行排序
  • 选择置信度最高的比边界框添加到最终输出列表中，将其从边界框列表中删除
  • 计算所有边界框的面积
  • 计算置信度最高的边界框与其它候选框的IoU。
  • 删除IoU大于阈值的边界框
  • 重复上述过程，直至边界框列表为空。

具体代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import numpy as np

def py_cpu_nms(dets, thresh):
    """Pure Python NMS baseline."""
    x1 = dets[:, 0]  #xmin
    y1 = dets[:, 1]  #ymin
    x2 = dets[:, 2]  #xmax
    y2 = dets[:, 3]  #ymax
    scores = dets[:, 4]  #confidence

    areas = (x2 - x1 + 1) * (y2 - y1 + 1)  #the size of bbox
    order = scores.argsort()[::-1]  #sort bounding boxes by decreasing order, returning array([3, 1, 2, 0])

    keep = []        # store the final bounding boxes
    while order.size > 0:
        i = order[0]   #the index of the bbox with highest confidence
        keep.append(i)    #save it to keep
        xx1 = np.maximum(x1[i], x1[order[1:]]) #array([ 257.,  280.,  255.])
        yy1 = np.maximum(y1[i], y1[order[1:]]) #array([ 118.,  135.,  118.])
        xx2 = np.minimum(x2[i], x2[order[1:]]) #array([ 360.,  360.,  358.])
        yy2 = np.minimum(y2[i], y2[order[1:]]) #array([ 235.,  235.,  235.])

        w = np.maximum(0.0, xx2 - xx1 + 1)   #array([ 104.,   81.,  104.])
        h = np.maximum(0.0, yy2 - yy1 + 1)   #array([ 118.,  101.,  118.])
        inter = w * h   #array([ 12272.,   8181.,  12272.])

        # Cross Area / (bbox + particular area - Cross Area)
        ovr = inter / (areas[i] + areas[order[1:]] - inter)
        #reserve all the boundingbox whose ovr less than thresh
        inds = np.where(ovr <= thresh)[0]
        order = order[inds + 1]

    return keep

dets = np.array([
                [204, 102, 358, 250, 0.5],
                [257, 118, 380, 250, 0.7],
                [280, 135, 400, 250, 0.6],
                [255, 118, 360, 235, 0.7]])
thresh = 0.3
keep=py_cpu_nms(dets, thresh) 
print keep #  out:[3]