非极大值抑制算法 NMS

非极大值抑制NMS

对于目标检测等任务，由于在预测的时候生成了很多默认的候选框，再对这些候选框进行微调，因此导致对同一个物体可能有多个预测框。NMS正是为了解决这个问题而提出的算法。

算法原理

已知：对同一个类别的物体，有多个预测框，每个框都有一个置信度
目的：确定每个物体对应的框体，删除多余的框体
步骤：

• i)将多个框体按照置信度排序
• ii)选出置信度最大的框体，删除剩余框体与该框体IoU大于阈值的框体。（这一步确定了一个物体的框体，并删除了其他可能重复预测的框体）
• iii）重复步骤ii，直至处理完所有框体

例子

先假设有6个输出的矩形框(即proposal_clip_box)，根据分类器类别分类概率做排序，从小到大分别属于车辆的概率(scores)分别为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是我们保留下来的第二个矩形框。
就这样一直重复，找到所有被保留下来的矩形框。

算法实现

def nms(dets, thresh):
    """ 非极大值抑制算法 :param dets: ndarray， eg:[[x1,y1,x2,y2,score], [x1,y1,x2,y2,score], [x1,y1,x2,y2,score]...] :param thresh: int eg:0.7 :return: """
    # 计算每个框的面积
    x1 = dets[:, 0]
    y1 = dets[:, 1]
    x2 = dets[:, 2]
    y2 = dets[:, 3]

    area = (x2-x1+1) * (y2-y1+1)

    # 按置信度排名
    score = dets[:, 4]
    order = score.argsort()[::-1]   # 从大到小排序

    # 要保留的框体
    keep = []

    # 取出置信度最大的框，删除其他框
    while order.size > 0:
        chosed = order[0]
        keep.append(chosed)
        # 计算和其他框的IoU

        # 计算交叉部分坐标
        inter_x1 = np.maximum(x1[chosed], x1[order[1:]])
        inter_y1 = np.maximum(y1[chosed], y1[order[1:]])
        inter_x2 = np.minimum(x2[chosed], x2[order[1:]])
        inter_y2 = np.minimum(y2[chosed], y2[order[1:]])

        # 交叉面积
        inter_area = (inter_x2-inter_x1+1) * (inter_y2 - inter_y1 + 1)

        # IoU
        IoU = inter_area / (area[chosed] + area[order[1:]] - inter_area)

        # 筛选IoU小于阈值的框体
        left = np.where(IoU < thresh)[0]

        order = order[left + 1] # left 中编号比order中小了1

    return keep