非极大抑制(NMS)及其变种

非极大抑制(Non-Maximum Suppression，NMS)

非极大抑制（Non-Maximum Suppression, NMS），顾名思义就是机制不是极大值的元素，可以理解为局部最大搜索。这个局部代表的是一个领域，领域有两个参数可变，一个是领域的维数，另一个是领域的大小。

NMS在计算机视觉领域有着非常重要的作用，如食品跟踪，数据挖掘，3D重建，目标识别以及纹理分析等。本文主要关注其在目标检测领域的应用。

NMS 在目标检测中的应用

以人脸检测为例

目标检测算法会在目标的周围产生一些冗余的框，我们的目的是从这些冗余的框中提取出匹配目标最好的框。有多重方式可以解决这个问题，Triggs et al. 建议使用Mean-Shift算法，利用bbox的坐标和当前图片尺度的对数来检测bbox的多种模式，但是效果可能并不如使用分类器结合NMS算法的效果好。

NMS原理

对于Bounding box的列表B和其对应的置信度S，采用下面的计算方式。

选出具有最大score的检测框M，将其从B集合中移除并加入到最终检测结果D中。
将B中剩余检测框中与M的IoU大于阈值T(一般取0.3~0.5)的框从B中移除。
重复上述过程，直到B为空终止。

在上述过程中用到了排序，即对B中的bbox按照置信度S进行排序。具体以一个例子说明。

1569676554493

1569676615451

如图中，目标检测算法在定位人脸的时候会找出一堆框，因此我们需要判断哪些检测框是没有用的。我们假设算法给出了六个框Bbox = {A,B,C,D,E,F}，其对应的置信度为Score = {0.4,0.8,0.5,0.4,0.9,0.6}

首先将目标检测框列表Bbox利用其对应的置信度Score进行排序。即Bbox={E,B,F,C,D,A}。
从列表Bbox中选出置信度最大的框E，将其放置在列表Detect中，并将E从列表Bbox中删除，即得到Bbox={B,F,C,D,A}和Detect={E}。
计算Bbox中剩余的框与E的重叠度IoU，并判断其是否大于某个设定的阈值，若大于则从Bbox中删除。假设C和D与E的IoU大于设定的阈值，则从Bbox中删除C和D。
接着取当前Bbox中置信度最大的框B，重复2,3步骤操作，直至列表Bbox为空终止。

代码示例

单类NMSPython cpu 版本代码

import cv2
import numpy as np
import matplotlib.pyplot as plt


def nms(bboxes,scores,thresh):
    """
    bboxes -> [x1,y1,x2,y2] Nx4 输入的是左上和右下的坐标
    scores -> Nx1
    """
    x1 = bboxes[:,0]
    y1 = bboxes[:,1]
    x2 = bboxes[:,2]
    y2 = bboxes[:,3]
    order = scores.argsort()[::-1] # 对得分排序
    areas = (x2 - x1 + 1) * ( y2 - y1 + 1) # 计算bbox的面积
    keep = []

    while order.size > 0:
        i = order[0]
        keep.append(i)
        # 计算当前概率最大矩形框与其他矩形框的相交框的坐标
        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:]])

        w = np.maximum(0.0, xx2-xx1+1)
        h = np.maximum(0.0, yy2-yy1+1)
        inter = w * h  # 计算交叠部分的面积

        overlaps = inter/(areas[i] + areas[order[1:]] - inter) # 计算IoU

        inds = np.where(overlaps<=thresh)[0]
        order = order[inds+1]

    return keep


if __name__ == "__main__":
    img = cv2.imread("./demo.jpg")
    bboxes = [[105, 165, 290, 350],
              [150, 190, 340, 400],
              [80, 140, 250, 320],
              [153,130, 333, 330],
              [70, 199, 243, 406]]
    scores = [0.99, 0.6, 0.56, 0.7, 0.45]
    img2 = np.copy(img)
    bboxes = np.asarray(bboxes)
    scores = np.asarray(scores)

    keep = nms(bboxes, scores, 0.3)
    new_bboxes = bboxes[keep]
    new_scores = scores[keep]

    for i, box in enumerate(bboxes):
        x1, y1, x2, y2 = box
        cv2.rectangle(img,(x1,y1),(x2,y2),(0,255,0),2)
        cv2.putText(img,'%.2f'%scores[i], (x1,y1), 2, 1, (255, 255, 0))

    for i, box in enumerate(new_bboxes):
        x1, y1, x2, y2 = box
        cv2.rectangle(img2,(x1,y1),(x2,y2),(0,255,0),2)
        cv2.putText(img2,'%.2f'%new_scores[i], (x1,y1), 2, 1, (255, 255, 0))
    plt.figure()
    plt.imshow(img)
    plt.figure()
    plt.imshow(img2)
    plt.show()

上述代码只是针对单类目标进行NMS操作，如若想实现多类的NMS，只需要在外面套一层for 循环，每次对单一类别进行NMS，共进行类别数次。

Soft-NMS

上述NMS算法的一个主要问题是当两个ground truth的目标的确重叠度很高时,NMS会将具有较低置信度的框去掉(置信度改成0)

nms-problem

而soft NMS则是将和最大置信度重叠高于设定阈值的box的置信度降低。根据其IoU值，对重叠度高的置信度做一个基于连续函数的降值映射（decays the detection scores of all other objects as a continuous function of their overlap with Max）。NMS直接对score置0，当前高IoU的bbox就直接丢弃，而soft NMS只会降低当前bbox的score，不会丢掉。

伪代码如下，

preview

Non-Maximum Suppression

非极大抑制(Non-Maximum Suppression，NMS)

NMS 在目标检测中的应用

NMS原理

代码示例

Soft-NMS

FEATURED TAGS

FRIENDS