object detection中的非极大值抑制(NMS)算法
前言 什么是NMS算法呢？即非极大值抑制，它在目标检测、目标追踪、三维重建等方面应用十分广泛，特别是在目标检测方面，它是目标检测的最后一道关口，不管是RCNN、还是fast-RCNN、YOLO等算法，都使用了这一项算法。 非极大值抑制（Non-Maximum Suppression，NMS），顾名思义就是抑制不是极大值的元素，可以理解为局部最大搜索。这个局部代表的是一个邻域，邻域有两个参数可变，一是邻域的维数，二是邻域的大小。这里不讨论通用的NMS算法(参考论文《Efficient Non-Maximum Suppression》对1维和2维数据的NMS实现)，而是用于目标检测中提取分数最高的窗口的。例如在行人检测中，滑动窗口经提取特征，经分类器分类识别后，每个窗口都会得到一个分数。但是滑动窗口会导致很多窗口与其他窗口存在包含或者大部分交叉的情况。这时就需要用到NMS来选取那些邻域里分数最高（是行人的概率最大），并且抑制那些分数低的窗口。 NMS在计算机视觉领域有着非常重要的应用，如视频目标跟踪、数据挖掘、3D重建、目标识别以及纹理分析等。本文主要以目标检测中的应用加以说明。
二、NMS 在目标检测中的应用
人脸检测框重叠例子
面对上图中左侧图片中这么多的被选矿，我们的目的就是要去除冗余的检测框,保留最好的一个.
有多种方式可以解决这个问题,Triggs et al. 建议使用
Mean-Shift
算法,利用bbox的坐标和当前图片尺度的对数来检测bbox的多种模式.但效果可能并不如使用强分类器结合NMS的效果好.下图中展现了目标检测的基本过程。
第一步：产生RP（region proposal）
第二步：使用分类网络给每一个候选框一个置信度（即可能的概率大小）
第三步：使用回归网络精修每个候选框的位置
第四步：最终应用NMS算法，剔除掉候选框，留下需要的。
三、NMS 原理
首先引入几个概念：
- 候选框列表B
- B所对应的置信度列表S
- B中置信度最大的那个框为M
- 最终的检测结果为D
- IOU值（此处不再展开）
- 人为设定的阈值Nt
对于Bounding Box的列表B及其对应的置信度S,采用下面的计算方式.选择具有最大score的检测框M,将其从B集合中移除并加入到最终的检测结果D中.通常将B中剩余检测框中与M的IoU大于阈值Nt的框从B中移除.重复这个过程,直到B为空.
重叠率(重叠区域面积比例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是我们保留下来的第二个矩形框。
就这样一直重复，找到所有被保留下来的矩形框。
代码示例
在R-CNN中使用了NMS来确定最终的bbox,其对每个候选框送入分类器,根据分类器的类别分类概率做排序(论文中称为greedy-NMS).但其实也可以在分类之前运用简单版本的NMS来去除一些框.
四、使用python来简单模拟一个NMS过程
# python3
import numpy as np
def py_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)
#order是按照score降序排序的
order = scores.argsort()[::-1]
keep = []
while order.size > 0:
i = order[0]
keep.append(i)
#计算当前概率最大矩形框与其他矩形框的相交框的坐标，会用到numpy的broadcast机制，得到的是向量
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或h算出来会是负数，用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)
#找到重叠度不高于阈值的矩形框索引
inds = np.where(ovr <= thresh)[0]
#将order序列更新，由于前面得到的矩形框索引要比矩形框在原order序列中的索引小1，所以要把这个1加回来
order = order[inds + 1]
return keep
# test
if __name__ == "__main__":
dets = np.array([[30, 20, 230, 200, 1],
[50, 50, 260, 220, 0.9],
[210, 30, 420, 5, 0.8],