非极大值抑制的作用

在进行目标检测过程中，我们的分类器会对每一个滑动窗口的内容进行分类，而滑动窗口是按照设定的步长在图像金字塔的每个图层中从上到下、从左向右移动，这样一个目标就会出现在多个滑动窗口中，最后我们就会获得多个相交、重叠的矩形框。如下图在目标检测过程中目标上会产生多个矩形框，我们希望从这些矩形框中挑选出一个最合适的矩形框且剔除多余的矩形框，使得每个目标只被一个矩形框标记。

非极大值抑制（Non Maximum Suppression）以下简称 NMS，的主要作用是去除目标检测过程中产生的冗余矩形框。要实现 NMS 首先需要计算矩形框之间的交并比（Intersection over Union），以下简称 IoU。下图以直观的例子展示计算 IoU 的方法，左图中的目标（人）同时被两个矩形框标记，为了剔除多余的矩形框需要计算两个矩形框的 IoU。IoU 的计算的方法如下图中间的公式所示，即两个框的交集（红色区域）与两个框的并集（绿色区域）的比值。如果计算后的 IoU 大于事先设定的阈值，则剔除较小的矩形框（下图中最右边图片所示），通过这个过程我们就达到了剔除冗余的矩形框的目的。接下来我们将通过代码来实现一个 NMS 函数。

代码实现

然后我们定义一个名为 NMS 的函数（见下面代码）。该函数有两个参数，第一个参数 boxes 表示目标检测过程中获得的所有矩形框。第二个参数 threshold 表示事先定义的一个阈值，当两个矩形框重叠的面积超过这个阈值时我们将剔除其中一个矩形框

def NMS(boxes, threshold):
    if len(boxes) == 0:
        return []
    
    boxes = np.array(boxes).astype("float")

    x1 = boxes[:,0]
    y1 = boxes[:,1]
    w1 = boxes[:,2]
    h1 = boxes[:,3]
    x2 = x1 + w1
    y2 = y1 + h1
    
    area = (w1 + 1) * (h1 + 1)
    temp = []
    
    idxs = np.argsort(h1)
    
    while len(idxs) > 0:
        last = len(idxs) - 1
        i = idxs[last]
        temp.append(i)   
        
        x1_m = np.maximum(x1[i], x1[idxs[:last]])
        y1_m = np.maximum(y1[i], y1[idxs[:last]])
        
        x2_m = np.minimum(x2[i], x2[idxs[:last]])
        y2_m = np.minimum(y2[i], y2[idxs[:last]])
        
        w = np.maximum(0, x2_m - x1_m + 1)
        h = np.maximum(0, y2_m - y1_m + 1)
        
        over = (w * h) / area[idxs[:last]]
        
        idxs = np.delete(idxs, np.concatenate(([last],  
            np.where(over > threshold)[0])))  

    return boxes[temp].astype("int")

在目标检测过程中我们的算法有可能没有检测到任何目标，那么这就表示在图片中没有用于标记目标的矩形框。所以下面的代码第 2 行我们将用一个 if 语句来判断输入的 boxes 的数量是否为 0，如果矩形框的数量为 0 则函数返回一个空列表。然后我们还需要将 boxes 转换为 NumPy 数组并且将其中每个元素转换为 float 浮点类型（见代码第 5 行），因为后面我们需要用这些元素进行算术运算。

代码第 7 到 10 行，我们使用切片方法获取每一个 boxes 内的元素并将其分别保存在 x1、y1、w1、h1 这四个数组中。这四个数组中分别保存了每一个 boxes 中的第一至四元素。x1 表示矩形框左上角顶点的横坐标，y1 表示矩形框左上角顶点的纵坐标，w1 是矩形框的宽，h1 是矩形框的高。 代码第 11、12 行我们使用这四个数组计算得出每个矩形框的右下角顶点横坐标的集合 x2 和 纵坐标的集合 y2。

代码第 14 行表示我们需要计算每个矩形框的面积。这里分别将 w1 和 h1 加 1 是为了避免使用 area 计算 IoU 时分母为零的情况发生。我们还初始化了代码 15 行中的 temp 列表用于临时存储值。

代码 17 行我们使用 NumPy 的 argsort 方法将 h1 中的元素从小到大排序并返回每个元素在 h1 中的下标，需要注意的是 idxs 中的元素是 h1 中元素的下标，这些下标排列的顺序是按照其对应 h1 中元素的大小排列的。

接下来我们使用 while 循环遍历 idxs，当 idxs 中没有元素时终止循环。代码 20 到 22 行我们获取 idxs 中最后一个元素并将其添加到 temp 中。

代码 24 行我们使用 np.maximum 方法将 x1[i] 与 boxes 中其他矩形框的左上角横坐标两两比较， 将较大的值保存在数组 x1_m 中。同样代码 25 行将 y1[i] 与 boxes 中其他矩形框的左上角纵坐标两两比较，将较大的值保存在数组 y1_m 中。两个矩形框重叠的部分是矩形，所以这一步的目的是为了找到这个重叠矩形的左上角顶点。同理，27、28 两行代码的目的是为了找出这个重叠矩形的右下角顶点。我们使用 np.minimum 将 x2[i] 与 boxes 中其他矩形框的右下角横坐标两两比较， 将较小的值保存在数组 x2_m 中。同样的再将 y2[i] 与 boxes 中其他矩形框的右下角纵坐标两两比较，将较小的值保存在数组 y2_m 中。

有了重叠矩形的两个顶点坐标，我们就可以计算矩形的宽和高，进而可以计算矩形的面积。第 30，31 行代码是分别计算矩形的宽和高，我们使用 np.maximum 方法来剔除掉没有相交的矩形。如果两个矩形框相交，则 x2_m - x1_m + 1 和 y2_m - y1_m + 1 大于零，如果两个矩形框不相交则这两个值小于零。

33 行代码表示计算重叠矩形面积和 area 中的面积的比值 over，这一步和计算 IoU 是等效的。35 行代码的目的是为了剔除重叠的矩形框。我们使用 np.where 判断 over 中的元素是否大于设定的阈值 threshold，如果大于这个阈值则返回这个元素的下标。接着使用 np.concatenate 方法将 idxs 中最后的元素和返回的下标拼接在一起。最后通过 np.delete 方法从 idxs 中删除这些下标对应的元素。

通过上一步我们删除了与 idxs 中 last 对应的矩形框相互重叠且面积大于阈值的矩形框（同时也从 idxs 中删除最后一个元素），然后进入下一个循环直到 idxs 中的元素个数为 0，最后我们通过下面一行代码返回挑选后的矩形框，同时我们需要使用 astype 方法将 boxes 中的浮点类型转换为整数类型。