非极大值抑制 NMS（non maximum suppression）

[SihangWu]

非极大值抑制 NMS（non maximum suppression）

非极大值抑制顾名思义就是抑制不是极大值的元素，搜索局部的极大值。在很多计算机视觉任务中都有广泛应用，如：边缘检测、目标检测等。

• 在物体检测非极大值抑制应用十分广泛，主要目的是为了消除多余的框，找到最佳的物体检测的位置

　　如上图中：同一个人可能有好几个框(每一个框都带有一个分类器得分)，虽然几个框都检测到了人脸，但是不需要这么多的框，只要找到一个最能表达人脸的框。这时就需要用到NMS来选取那些邻域里分数最高，并且抑制那些分数低的窗口。

---

抑制的过程是一个迭代-遍历-消除的过程。

step 1:

将所有框的得分降序排列，选中最高分及其对应的框：

---

step2:

遍历其余的框，如果和当前最高分框的重叠面积(IOU)大于一定阈值，我们就将框删除。

注释：

在目标检测的评价体系中，有一个参数叫做 IOU ，简单来讲就是模型产生的目标窗口和原来标记窗口的交叠率。具体我们可以简单的理解为： 即检测结果(DetectionResult)与 Ground Truth 的交集比上它们的并集，即为检测的准确率 IOU :

如下图所示：
GT=GroundTruth;
DR=DetectionResult;
黄色边框框起来的是：GT⋂DR
绿色框框起来的是：GT⋃DR

---

step3:

从未处理的框中继续选一个得分最高的，重复上述过程。

---

下面给出MATLAB下的快速NMS代码，并带有详细的注释：

%% NMS:non maximum suppression
function pick = nms(boxes,threshold,type)
% boxes: m x 5,表示有m个框，5列分别是[x1 y1 x2 y2 score]
% threshold: IOU阈值
% type：IOU阈值的定义类型

    % 输入为空，则直接返回
    if isempty(boxes)
      pick = [];
      return;
    end

    % 依次取出左上角和右下角坐标以及分类器得分(置信度)
    x1 = boxes(:,1);
    y1 = boxes(:,2);
    x2 = boxes(:,3);
    y2 = boxes(:,4);
    s = boxes(:,5);

    % 计算每一个框的面积
    area = (x2-x1+1) .* (y2-y1+1);

    %将得分升序排列
    [vals, I] = sort(s);

    %初始化
    pick = s*0;
    counter = 1;

    % 循环直至所有框处理完成
    while ~isempty(I)
        last = length(I); %当前剩余框的数量
        i = I(last);%选中最后一个，即得分最高的框
        pick(counter) = i;
        counter = counter + 1;  

        %计算相交面积
        xx1 = max(x1(i), x1(I(1:last-1)));
        yy1 = max(y1(i), y1(I(1:last-1)));
        xx2 = min(x2(i), x2(I(1:last-1)));
        yy2 = min(y2(i), y2(I(1:last-1)));  
        w = max(0.0, xx2-xx1+1);
        h = max(0.0, yy2-yy1+1);
        inter = w.*h;

        %不同定义下的IOU
        if strcmp(type,'Min')
            %重叠面积与最小框面积的比值
            o = inter ./ min(area(i),area(I(1:last-1)));
        else
            %交集/并集
            o = inter ./ (area(i) + area(I(1:last-1)) - inter);
        end

        %保留所有重叠面积小于阈值的框，留作下次处理
        I = I(find(o<=threshold));
    end
    pick = pick(1:(counter-1));
end

---

一维，3邻域情况下的NMS即判断一维数组I[W]的元素Ii是否大于其左邻元素I[i-1]和右邻元素I[i+1]，算法流程如下图所示：

• a. 算法流程3-5行判断当前元素是否大于其左邻与右邻元素，如符合条件，该元素即为极大值点。对于极大值点I[i]，已知I[i]>I[i+1]，故无需对i+1位置元素做进一步处理，直接跳至i+2位置，对应算法流程第12行。

• b. 若元素I[i]不满足算法流程第3行判断条件，将其右邻I[i+1]作为极大值候选，对应算法流程第7行。采用单调递增的方式向右查找，直至找到满足I[i]>I[i+1]的元素，若i<=W-1，该点即为极大值点，对应算法流程第10-11行。

---

部分摘取
http://blog.csdn.net/shuzfan/article/details/52711706
http://blog.csdn.net/eddy_zheng/article/details/52126641