深度学习（⽬标检测）---⾮极⼤值抑制
（nonMaximumSuppression）
理论基础
说实话，讲理论基础实在不是我的强项，但是还是得硬着头⽪来讲，希望我的讲解不⾄于晦涩难懂。
⾮极⼤值抑制，简称为NMS算法。是⼀种获取局部最⼤值的有效⽅法。在3领域中，假设⼀个⾏向量的长度为w，从左向右，由第⼀个到第w个和其3领域中的数值进⾏⽐对。
如果某个i⼤于i+1并且⼩于i-1，则其为⼀个绝不最⼤值，同时也就意味着i+1不是⼀个局部最⼤值，所以将i移动2个步长，从i+2开始继续向后进⾏⽐较判断。如果某个i不满⾜上述条件，则将i+1，继续对i+1进⾏⽐对。当⽐对到最后⼀个w时，直接将w设置为局部最⼤值。算法流程如下图所⽰。
名字设计
应⽤范围
猫咪壁纸
⾮极⼤值抑制NMS在⽬标检测，定位等领域是⼀种被⼴泛使⽤的⽅法。对于⽬标具体位置定位过程，不管是使⽤sw(sliding Window)还是ss(lective ar ch)⽅法，都会产⽣好多的候选区域。实际看到的情形就是好多区域的交叉重叠，难以满⾜实际的应⽤。如下图所⽰。
针对该问题有3种传统的解决思路。
第⼀种，选取好多矩形框的交集，即公共区域作为最后的⽬标区域。
第⼆种，选取好多矩形框的并集，即所有矩形框的最⼩外截矩作为⽬标区域。当然这⾥也不是只要相交就直接取并集，需要相交的框满⾜交集占最⼩框的⾯积达到⼀定⽐例(也就是阈值)才合并。
第三种，也就是本⽂的NMS，简单的说，对于有相交的就选取其中置信度最⾼的⼀个作为最后结果，对于没相交的就直接保留下来，作为最后结果。
总体来说，3种处理思路都各有千秋，不能⼀概评论哪种好坏。各种顶会论⽂也会选择不同的处理⽅法。
程序实现
三叔是谁本⽂提供了nonMaximumSuppression的c语⾔，c++，M语⾔，三个版本。
其中，c语⾔版本为opencv的源码这⾥摘出并进⾏相关的注释。sort为排序函数，这⾥是最基本的选择排序算法的实现。nonMaximum Suppression为具体⾮极⼤值抑制的实现。
[cpp]
1. static void sort(int n, const float* x, int* indices)
2. {
3. // 排序函数，排序后进⾏交换的是indices中的数据
4. // n：排序总数// x：带排序数// indices：初始为0~n-1数⽬
5.
6. int i, j;
7. for (i = 0; i < n; i++)开学第一天作文
8. for (j = i + 1; j < n; j++)
9. {
10. if (x[indices[j]] > x[indices[i]])
11. {
12. //float x_tmp = x[i];
13. int index_tmp = indices[i];
14. //x[i] = x[j];
15. indices[i] = indices[j];
16. //x[j] = x_tmp;
17. indices[j] = index_tmp;
18. }
19. }
20. }
[cpp]
1. int nonMaximumSuppression(int numBoxes, const CvPoint *points,
2. const CvPoint *oppositePoints, const float *score,
3. float overlapThreshold,
4. int *numBoxesOut, CvPoint **pointsOut,
5. CvPoint **oppositePointsOut, float **scoreOut)
6. {
7.
8. // numBoxes：窗⼝数⽬// points：窗⼝左上⾓坐标点// oppositePoints：窗⼝右下⾓坐标点
9. // score：窗⼝得分// overlapThreshold：重叠阈值控制// numBoxesOut：输出窗⼝数⽬
10. // pointsOut：输出窗⼝左上⾓坐标点// oppositePoints：输出窗⼝右下⾓坐标点
11. // scoreOut：输出窗⼝得分
12. int i, j, index;
13. float* box_area = (float*)malloc(numBoxes * sizeof(float)); // 定义窗⼝⾯积变量并分配空间
14. int* indices = (int*)malloc(numBoxes * sizeof(int)); // 定义窗⼝索引并分配空间
15. int* is_suppresd = (int*)malloc(numBoxes * sizeof(int)); // 定义是否抑制表标志并分配空间
16. // 初始化indices、is_suppersd、box_area信息
17. for (i = 0; i < numBoxes; i++)
18. {
19. indices[i] = i;
20. is_suppresd[i] = 0;
21. box_area[i] = (float)( (oppositePoints[i].x - points[i].x + 1) *
孩子高烧22. (oppositePoints[i].y - points[i].y + 1));
23. }
24. // 对输⼊窗⼝按照分数⽐值进⾏排序，排序后的编号放在indices中
25. sort(numBoxes, score, indices);
26. for (i = 0; i < numBoxes; i++) // 循环所有窗⼝
27. {
28. if (!is_suppresd[indices[i]]) // 判断窗⼝是否被抑制
29. {
30. for (j = i + 1; j < numBoxes; j++) // 循环当前窗⼝之后的窗⼝
31. {
32. if (!is_suppresd[indices[j]]) // 判断窗⼝是否被抑制
33. {
34. int x1max = max(points[indices[i]].x, points[indices[j]].x); // 求两个窗⼝左上⾓x坐标最⼤值
35. int x2min = min(oppositePoints[indices[i]].x, oppositePoints[indices[j]].x); // 求两个窗⼝右下⾓x坐
标最⼩值
36. int y1max = max(points[indices[i]].y, points[indices[j]].y); // 求两个窗⼝左上⾓y坐标最⼤值
37. int y2min = min(oppositePoints[indices[i]].y, oppositePoints[indices[j]].y); // 求两个窗⼝右下⾓y坐
标最⼩值
38. int overlapWidth = x2min - x1max + 1; // 计算两矩形重叠的宽度
39. int overlapHeight = y2min - y1max + 1; // 计算两矩形重叠的⾼度
40. if (overlapWidth > 0 && overlapHeight > 0)
41. {
42. float overlapPart = (overlapWidth * overlapHeight) / box_area[indices[j]]; // 计算重叠的⽐率
43. if (overlapPart > overlapThreshold) // 判断重叠⽐率是否超过重叠阈值
44. {
45. is_suppresd[indices[j]] = 1; // 将窗⼝j标记为抑制
46. }
47. }
48. }
49. }
50. }
51. }
52.
53. *numBoxesOut = 0; // 初始化输出窗⼝数⽬0
54. for (i = 0; i < numBoxes; i++)
55. {
56. if (!is_suppresd[i]) (*numBoxesOut)++; // 统计输出窗⼝数⽬
57. }
钟的简笔画58.
59. *pointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配输出窗⼝左上⾓坐标空间
60. *oppositePointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配输出窗⼝右下⾓坐标空间
61. *scoreOut = (float *)malloc((*numBoxesOut) * sizeof(float)); // 分配输出窗⼝得分空间
62. index = 0;
63. for (i = 0; i < numBoxes; i++) // 遍历所有输⼊窗⼝
64. {
65. if (!is_suppresd[indices[i]]) // 将未发⽣抑制的窗⼝信息保存到输出信息中
66. {
67. (*pointsOut)[index].x = points[indices[i]].x;
68. (*pointsOut)[index].y = points[indices[i]].y;
69. (*oppositePointsOut)[index].x = oppositePoints[indices[i]].x;
70. (*oppositePointsOut)[index].y = oppositePoints[indices[i]].y;
71. (*scoreOut)[index] = score[indices[i]];
72. index++;
73. }新古典经济学
74.
74.
75. }
76.
77. free(indices); // 释放indices空间
78. free(box_area); // 释放box_area空间
79. free(is_suppresd); // 释放is_suppresd空间
80.
81. return LATENT_SVM_OK;
82. }
c++版本程序如下所⽰，根据opencv源码改编，vs2010实测运⾏完美。由于c和c++版本基本⼀个思路，因此将这两个的思路⼀起讲解。
整体程序分为两部分，sort函数主要实现候选框的置信度从⾼到低的排序，是基于基本的选择排序实现。nonMaximumSuppression主要实现⾮极⼤值抑制算法。算法思路为，先根据候选框的points 和oppositePoints 求出每个候选框的⾯积box_area，并将标签is_suppres d全部置为0。通过⼀个⼆重for循环将所有的候选框进⾏⽐对，这⾥的循环是从置信度最⾼的窗⼝进⾏⽐对，每层外循环中置信度最⾼的保留，其余的只要⼤于规定阈值overlapThreshold就舍弃，不⼤于阈值的保留下来。最终输出NMS处理后的结果。
[cpp]
1. static void sort(int n, const vector<float> x, vector<int> indices)
2. {
3. // 排序函数，排序后进⾏交换的是indices中的数据
4. // n：排序总数// x：带排序数// indices：初始为0~n-1数⽬
5.
6. int i, j;
7. for (i = 0; i < n; i++)
8. for (j = i + 1; j < n; j++)
9. {
10. if (x[indices[j]] > x[indices[i]])
11. {
12. //float x_tmp = x[i];
13. int index_tmp = indices[i];
14. //x[i] = x[j];
15. indices[i] = indices[j];
16. //x[j] = x_tmp;觳觫怎么读
17. indices[j] = index_tmp;
18. }
19. }
20. }
[cpp]
1. int nonMaximumSuppression(int numBoxes, const vector<CvPoint> points,const vector<CvPoint> oppositeP
oints,
2. const vector<float> score, float overlapThreshold,int& numBoxesOut, vector<CvPoint>& pointsOut,
3. vector<CvPoint>& oppositePointsOut, vector<float> scoreOut)
4. {
5. // 实现检测出的矩形窗⼝的⾮极⼤值抑制nms
6. // numBoxes：窗⼝数⽬// points：窗⼝左上⾓坐标点// oppositePoints：窗⼝右下⾓坐标点// score：窗⼝得分
7. // overlapThreshold：重叠阈值控制// numBoxesOut：输出窗⼝数⽬// pointsOut：输出窗⼝左上⾓坐标点
8. // oppositePoints：输出窗⼝右下⾓坐标点// scoreOut：输出窗⼝得分
8. // oppositePoints：输出窗⼝右下⾓坐标点// scoreOut：输出窗⼝得分
9. int i, j, index;
10. vector<float> box_area(numBoxes); // 定义窗⼝⾯积变量并分配空间
11. vector<int> indices(numBoxes); // 定义窗⼝索引并分配空间
12. vector<int> is_suppresd(numBoxes); // 定义是否抑制表标志并分配空间
13. // 初始化indices、is_suppersd、box_area信息
14. for (i = 0; i < numBoxes; i++)
15. {
16. indices[i] = i;
17. is_suppresd[i] = 0;
18. box_area[i] = (float)( (oppositePoints[i].x - points[i].x + 1) *(oppositePoints[i].y - points[i].y + 1));
19. }
20. // 对输⼊窗⼝按照分数⽐值进⾏排序，排序后的编号放在indices中
21. sort(numBoxes, score, indices);
22. for (i = 0; i < numBoxes; i++) // 循环所有窗⼝
23. {
24. if (!is_suppresd[indices[i]]) // 判断窗⼝是否被抑制
25. {
26. for (j = i + 1; j < numBoxes; j++) // 循环当前窗⼝之后的窗⼝
27. {
28. if (!is_suppresd[indices[j]]) // 判断窗⼝是否被抑制
29. {
30. int x1max = max(points[indices[i]].x, points[indices[j]].x); // 求两个窗⼝左上⾓x坐标最⼤值
31. int x2min = min(oppositePoints[indices[i]].x, oppositePoints[indices[j]].x); // 求两个窗⼝右下⾓x坐
标最⼩值
32. int y1max = max(points[indices[i]].y, points[indices[j]].y); // 求两个窗⼝左上⾓y坐标最⼤值
33. int y2min = min(oppositePoints[indices[i]].y, oppositePoints[indices[j]].y); // 求两个窗⼝右下⾓y坐
标最⼩值
34. int overlapWidth = x2min - x1max + 1; // 计算两矩形重叠的宽度
35. int overlapHeight = y2min - y1max + 1; // 计算两矩形重叠的⾼度
36. if (overlapWidth > 0 && overlapHeight > 0)
37. {
38. float overlapPart = (overlapWidth * overlapHeight) / box_area[indices[j]]; // 计算重叠的⽐率
39. if (overlapPart > overlapThreshold) // 判断重叠⽐率是否超过重叠阈值
40. {
41. is_suppresd[indices[j]] = 1; // 将窗⼝j标记为抑制
42. }
43. }
44. }
45. }
46. }
47. }
48.
49. numBoxesOut = 0; // 初始化输出窗⼝数⽬0
50. for (i = 0; i < numBoxes; i++)
51. {
52. if (!is_suppresd[i]) numBoxesOut++; // 统计输出窗⼝数⽬
53. }
54. index = 0;
55. for (i = 0; i < numBoxes; i++) // 遍历所有输⼊窗⼝
56. {
