一、NMS in Object Detection

首先可以看下cousera上吴恩达关于NMS的讲解视频.

非极大值抑制，就是局部最大搜索。例如在人脸检测中，滑动窗口经过特征提取，分类器分类识别后，每个窗口都会得到一个分数，但是会有很多重叠交叉的边界框，因此需要NMS来选取这些邻域内分数最大的，并抑制那些分数低的窗口。我们的目的就是去除冗余的检测框，保留最好的那个。如上图所示。

1.单类别

对于Bounding Box的列表B及其对应的置信度S,采用下面的计算方式.选择具有最大score的检测框M,将其从B集合中移除并加入到最终的检测结果D中.通常将B中剩余检测框中与M的IoU大于阈值Nt的框从B中移除.重复这个过程,直到B为空.

假设有6个矩形框，根据分类器的类别分类概率做排序，假设从小到大属于车辆的概率分别为A、B、C、D、E、F。

从最大概率的框F开始，分别判断A,B,C,D,E与F的重叠率IOU是否大于阈值
假设B,D与F的IOU大于阈值，则去除B,D;并标记F是我们在第一轮中保留下来的
从剩下的A,C,E中，找到概率最大的E,判断A,C与E的IOU是否大于阈值。大于则扔掉，否则保留。并标记E是我们第二轮留下来的矩形框。
重复进行直到找到所有保留的框框。

代码：

def py_cpu_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) 
    #按照score置信度降序排序 
    order = scores.argsort()[::-1] keep = [] 
    #保留的结果框集合 
    while order.size > 0: 
        i = order[0] keep.append(i) 
        #保留该类剩余box中得分最高的一个 
        #得到相交区域,左上及右下 
        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:]]) 
        #计算相交的面积,不重叠时面积为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) 
        #保留IoU小于阈值的box 
        inds = np.where(ovr <= thresh)[0] 
        #因为ovr数组的长度比order数组少一个,所以这里要将所有下标后移一位
        order = order[inds + 1] 
         
    return keep

2.多类别

多类别的就是在单类别上多加一层for循环，对每类进行NMS而已。

keras-retinanet中的特定类别NMS

代码：

if class_specific_filter:
        all_indices = []
        # perform per class filtering
        #对每个类比进行NMS
        for c in range(int(classification.shape[1])):
            scores = classification[:, c]
            labels = c * keras.backend.ones((keras.backend.shape(scores)[0],), dtype='int64')
            all_indices.append(_filter_detections(scores, labels))

        # concatenate indices to single tensor
        indices = keras.backend.concatenate(all_indices, axis=0)
    else:
        scores  = keras.backend.max(classification, axis    = 1)
        labels  = keras.backend.argmax(classification, axis = 1)
        indices = _filter_detections(scores, labels)

#NMS
def _filter_detections(scores, labels):
        # threshold based on score
        indices = backend.where(keras.backend.greater(scores, score_threshold))

        if nms:
            filtered_boxes  = backend.gather_nd(boxes, indices)
            filtered_scores = keras.backend.gather(scores, indices)[:, 0]

            # perform NMS
            nms_indices = backend.non_max_suppression(filtered_boxes, filtered_scores, max_output_size=max_detections, iou_threshold=nms_threshold)

            # filter indices based on NMS
            indices = keras.backend.gather(indices, nms_indices)

        # add indices to list of all indices
        labels = backend.gather_nd(labels, indices)
        indices = keras.backend.stack([indices[:, 0], labels], axis=1)

        return indices

3.NMS损失

如果对每个类别进行NMS，会出现一种情况：当检测结果中包含两个被分配到不同类别的bbox且他们的IOU较大时，结果将不可接受。

《Rotated Region Based CNN for Ship Detection》中，引入了NMS损失，添加在训练的多任务损失中。

NMS损失和分类损失的定义相同。
$$
Lnms=Lcls(p,u)=-logp_u
$$
即为真实类别u对应的log损失，p是C个类别的预测概率。NMS损失实际是增加分类损失。

4.Soft-NMS

论文：Improving Object Detection With One Line of Code .

project：soft-nms-caffe

1.Hard NMS

也就是传统的NMS,有一个问题，就是当两个gt的确存在目标，且重叠度很高时（大于NMS的阈值），NMS会将置信度较低的框去掉（score置为0），导致这个object丢失，最后ap下降。如下图所示：

选取NMS的阈值也有两个问题：

设$Ot$表示我们在检测评估时，设的将一个proposal划分为正样本的阈值（与gt的重叠率阈值）：

threshold $Nt$很低时，周围的box都会被抑制掉，导致错误率上升

$Nt$很高时，导致$Ot$比较小的一些框框被保留下来，导致准确率的下降，false positive上升，true positive下降。

2. Soft NMS

思想：如果一个Bbox与M（置信度最高的框）的重叠率很大，应该赋予它一个很低的分数，而不是直接将score置为0；如果重叠度很低，那么就保留他原来的分数。见下图：

这里文章中提出了两种关于$s_if(iou(M,bi))$的式子：

linear function:

$$
s_i=\begin{cases}s_i,\quad iou(M,bi)<N_t \s_i(1-iou(M,bi)),\quad iou(M,bi)\ge N_t\end{cases}
$$

该线性函数不是连续的。我们希望：惩罚函数最好是连续的。当没有重叠时，既没有惩罚；当有很高的IOU时，惩罚因子也高。当IOU很低时，惩罚应该逐渐提高。因此，提出下面的函数：

Gaussian Function:

$$
s_i=s_i e^{-\frac{iou(M,b_i)^2}{\sigma}},\quad \forall b_i\notin D
$$

时间复杂度分析：

对于每个detection box,需要计算的是$O(N)$,

对于$N$个detection box，需要计算$O(N^2)$.

因此时间复杂度和原本的相比没什么区别。

结果

在基于proposal方法的模型结果上应用比较好,检测效果提升:

在R-FCN以及Faster-RCNN基于proposal的模型中的测试阶段运用Soft-NMS,在MS-COCO数据集上mAP@[0.5:0.95]能够获得大约1%的提升。因为他们的recall更高，在$Ot$更高的情况下有更高的提升空间。如果图片中出现羊群，鸟群，斑马群这样的易重叠的图片，map能提高的更多：3-6%。
但是对于SSD,YOLO这样不是基于proposal的检测器来说，几乎没有提升。

代码

参见caffe-c++代码：soft-nms

def cpu_soft_nms(np.ndarray[float, ndim=2] boxes, float sigma=0.5, float Nt=0.3, float threshold=0.001, unsigned int method=0):
    ……

    for i in range(N):
        ……

            area = (x2 - x1 + 1) * (y2 - y1 + 1)
            iw = (min(tx2, x2) - max(tx1, x1) + 1)
            if iw > 0:
                ih = (min(ty2, y2) - max(ty1, y1) + 1)
                if ih > 0:
                    ua = float((tx2 - tx1 + 1) * (ty2 - ty1 + 1) + area - iw * ih)
                    ov = iw * ih / ua #iou between max box and detection box
#两个nms的函数:
                    if method == 1: # linear
                        if ov > Nt: 
                            weight = 1 - ov
                        else:
                            weight = 1
                    elif method == 2: # gaussian
                        weight = np.exp(-(ov * ov)/sigma)
                    else: # original NMS
                        if ov > Nt: 
                            weight = 0
                        else:
                            weight = 1

                    boxes[pos, 4] = weight*boxes[pos, 4]
		    
		    # if box score falls below threshold, discard the box by swapping with last box
		    # update N
                    if boxes[pos, 4] < threshold:
                        boxes[pos,0] = boxes[N-1, 0]
                        boxes[pos,1] = boxes[N-1, 1]
                        boxes[pos,2] = boxes[N-1, 2]
                        boxes[pos,3] = boxes[N-1, 3]
                        boxes[pos,4] = boxes[N-1, 4]
                        N = N - 1
                        pos = pos - 1

            pos = pos + 1

    keep = [i for i in range(N)]
    return keep