非极大值抑制算法(nms)
1. 算法原理
非极大值抑制算法(Non-maximum suppression, NMS)的本质是搜索局部极大值,抑制非极大值元素。
2. 3邻域情况下NMS的实现
3邻域情况下的NMS即判断一维数组I[W]的元素I[i](2<=i<=W-1)是否大于其左邻元素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行。
3. NMS在物体检测中的应用
物体检测中应用NMS算法的主要目的是消除多余(交叉重复)的窗口,找到最佳物体检测位置。
如上图所示,人脸检测中,虽然每个窗口均检测到人脸,但仅需给出一个最有可能表征人脸的窗口
程序整体思路:
先将box中的数据分别存入x1,y1,x2,y2,s中,分别为坐标和置信度,算出每个框的面积,存入area,基于置信度s,从小到达进行排序,做一个while循环,取出置信度最高的,即排序后的最后一个,然后将该框进行保留,存入pick中,然后和其他所有的框进行比对,大于规定阈值就将别的框去掉,并将该置信度最高的框和所有比对过程,大于阈值的框存入suppress,for循环后,将I中满足suppress条件的置为空。直到I为空退出while。
代码(C++):
static void sort(int n, const float* x, int* indices)
{
// 排序函数(降序排序),排序后进行交换的是indices中的数据
// n:排序总数// x:带排序数// indices:初始为0~n-1数目 int i, j;
for (i = ; i < n; i++)
for (j = i + ; j < n; j++)
{
if (x[indices[j]] > x[indices[i]])
{
//float x_tmp = x[i];
int index_tmp = indices[i];
//x[i] = x[j];
indices[i] = indices[j];
//x[j] = x_tmp;
indices[j] = index_tmp;
}
}
}
int nonMaximumSuppression(int numBoxes, const CvPoint *points,
const CvPoint *oppositePoints, const float *score,
float overlapThreshold,
int *numBoxesOut, CvPoint **pointsOut,
CvPoint **oppositePointsOut, float **scoreOut)
{ // numBoxes:窗口数目// points:窗口左上角坐标点// oppositePoints:窗口右下角坐标点
// score:窗口得分// overlapThreshold:重叠阈值控制// numBoxesOut:输出窗口数目
// pointsOut:输出窗口左上角坐标点// oppositePoints:输出窗口右下角坐标点
// scoreOut:输出窗口得分
int i, j, index;
float* box_area = (float*)malloc(numBoxes * sizeof(float)); // 定义窗口面积变量并分配空间
int* indices = (int*)malloc(numBoxes * sizeof(int)); // 定义窗口索引并分配空间
int* is_suppressed = (int*)malloc(numBoxes * sizeof(int)); // 定义是否抑制表标志并分配空间
// 初始化indices、is_supperssed、box_area信息
for (i = ; i < numBoxes; i++)
{
indices[i] = i;
is_suppressed[i] = ;
box_area[i] = (float)( (oppositePoints[i].x - points[i].x + ) *
(oppositePoints[i].y - points[i].y + ));
}
// 对输入窗口按照分数比值进行排序,排序后的编号放在indices中
sort(numBoxes, score, indices);
for (i = ; i < numBoxes; i++) // 循环所有窗口
{
if (!is_suppressed[indices[i]]) // 判断窗口是否被抑制
{
for (j = i + ; j < numBoxes; j++) // 循环当前窗口之后的窗口
{
if (!is_suppressed[indices[j]]) // 判断窗口是否被抑制
{
int x1max = max(points[indices[i]].x, points[indices[j]].x); // 求两个窗口左上角x坐标最大值
int x2min = min(oppositePoints[indices[i]].x, oppositePoints[indices[j]].x); // 求两个窗口右下角x坐标最小值
int y1max = max(points[indices[i]].y, points[indices[j]].y); // 求两个窗口左上角y坐标最大值
int y2min = min(oppositePoints[indices[i]].y, oppositePoints[indices[j]].y); // 求两个窗口右下角y坐标最小值
int overlapWidth = x2min - x1max + ; // 计算两矩形重叠的宽度
int overlapHeight = y2min - y1max + ; // 计算两矩形重叠的高度
if (overlapWidth > && overlapHeight > )
{
float overlapPart = (overlapWidth * overlapHeight) / box_area[indices[j]]; // 计算重叠的比率
if (overlapPart > overlapThreshold) // 判断重叠比率是否超过重叠阈值
{
is_suppressed[indices[j]] = ; // 将窗口j标记为抑制
}
}
}
}
}
} *numBoxesOut = ; // 初始化输出窗口数目0
for (i = ; i < numBoxes; i++)
{
if (!is_suppressed[i]) (*numBoxesOut)++; // 统计输出窗口数目
} *pointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配输出窗口左上角坐标空间
*oppositePointsOut = (CvPoint *)malloc((*numBoxesOut) * sizeof(CvPoint)); // 分配输出窗口右下角坐标空间
*scoreOut = (float *)malloc((*numBoxesOut) * sizeof(float)); // 分配输出窗口得分空间
index = ;
for (i = ; i < numBoxes; i++) // 遍历所有输入窗口
{
if (!is_suppressed[indices[i]]) // 将未发生抑制的窗口信息保存到输出信息中
{
(*pointsOut)[index].x = points[indices[i]].x;
(*pointsOut)[index].y = points[indices[i]].y;
(*oppositePointsOut)[index].x = oppositePoints[indices[i]].x;
(*oppositePointsOut)[index].y = oppositePoints[indices[i]].y;
(*scoreOut)[index] = score[indices[i]];
index++;
} } free(indices); // 释放indices空间
free(box_area); // 释放box_area空间
free(is_suppressed); // 释放is_suppressed空间 return LATENT_SVM_OK;
}
软化非极大值抑制算法(softnms)
参考链接:http://blog.csdn.net/app_12062011/article/details/77963494
Motivation
绝大部分目标检测方法,最后都要用到 NMS-非极大值抑制进行后处理。 通常的做法是将检测框按得分排序,然后保留得分最高的框,同时删除与该框重叠面积大于一定比例的其它框。
这种贪心式方法存在如下图所示的问题: 红色框和绿色框是当前的检测结果,二者的得分分别是0.95和0.80。如果按照传统的NMS进行处理,首先选中得分最高的红色框,然后绿色框就会因为与之重叠面积过大而被删掉。
另一方面,NMS的阈值也不太容易确定,设小了会出现下图的情况(绿色框因为和红色框重叠面积较大而被删掉),设置过高又容易增大误检。
思路:不要粗鲁地删除所有IOU大于阈值的框,而是降低其置信度。
Method
先直接上伪代码,如下图:如文章题目而言,就是用一行代码来替换掉原来的NMS。按照下图整个处理一遍之后,指定一个置信度阈值,然后最后得分大于该阈值的检测框得以保留
原来的NMS可以描述如下:将IOU大于阈值的窗口的得分全部置为0。
文章的改进有两种形式,一种是线性加权的:
一种是高斯加权的:
分析上面的两种改进形式,思想都是:M为当前得分最高框, 为待处理框, 和M的IOU越大, 的得分 就下降的越厉害。
具体地,下面是作者给出的代码:(当然不止一行T_T)
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):
cdef unsigned int N = boxes.shape[0]
cdef float iw, ih, box_area
cdef float ua
cdef int pos = 0
cdef float maxscore = 0
cdef int maxpos = 0
cdef float x1,x2,y1,y2,tx1,tx2,ty1,ty2,ts,area,weight,ov for i in range(N):
maxscore = boxes[i, 4]
maxpos = i tx1 = boxes[i,0]
ty1 = boxes[i,1]
tx2 = boxes[i,2]
ty2 = boxes[i,3]
ts = boxes[i,4] pos = i + 1
# get max box
while pos < N:
if maxscore < boxes[pos, 4]:
maxscore = boxes[pos, 4]
maxpos = pos
pos = pos + 1 # add max box as a detection
boxes[i,0] = boxes[maxpos,0]
boxes[i,1] = boxes[maxpos,1]
boxes[i,2] = boxes[maxpos,2]
boxes[i,3] = boxes[maxpos,3]
boxes[i,4] = boxes[maxpos,4] # swap ith box with position of max box
boxes[maxpos,0] = tx1
boxes[maxpos,1] = ty1
boxes[maxpos,2] = tx2
boxes[maxpos,3] = ty2
boxes[maxpos,4] = ts tx1 = boxes[i,0]
ty1 = boxes[i,1]
tx2 = boxes[i,2]
ty2 = boxes[i,3]
ts = boxes[i,4] pos = i + 1
# NMS iterations, note that N changes if detection boxes fall below threshold
while pos < N:
x1 = boxes[pos, 0]
y1 = boxes[pos, 1]
x2 = boxes[pos, 2]
y2 = boxes[pos, 3]
s = boxes[pos, 4] 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 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
这么做的解释如下:
如上图:
假如还检测出了3号框,而我们的最终目标是检测出1号和2号框,并且剔除3号框,原始的nms只会检测出一个1号框并剔除2号框和3号框,而softnms算法可以对1、2、3号检测狂进行置信度排序,可以知道这三个框的置信度从大到小的顺序依次为:1-》2-》3(由于是使用了惩罚,所有可以获得这种大小关系),如果我们再选择了合适的置信度阈值,就可以保留1号和2号,同时剔除3号,实现我们的功能。
但是,这里也有一个问题就是置信度的阈值如何选择,作者在这里依然使用手工设置的值,依然存在很大的局限性,所以该算法依然存在改进的空间。
result:
NMS和soft-nms算法的更多相关文章
-
NMS(非极大值抑制算法)
目的:为了消除多余的框,找到最佳的物体检测的位置 思想: 选取那些领域里分数最高的窗口,同时抑制那些分数低的窗口 Soft-NMS
-
论文阅读笔记四十八:Bounding Box Regression with Uncertainty for Accurate Object Detection(CVPR2019)
论文原址:https://arxiv.org/pdf/1809.08545.pdf github:https://github.com/yihui-he/KL-Loss 摘要 大规模的目标检测数据集在 ...
-
IoU与非极大值抑制(NMS)的理解与实现
1. IoU(区域交并比) 计算IoU的公式如下图,可以看到IoU是一个比值,即交并比. 在分子中,我们计算预测框和ground-truth之间的重叠区域: 分母是并集区域,或者更简单地说,是预测框和 ...
-
NMS 和 Soft-NMS
转自https://zhuanlan.zhihu.com/p/42018282 一 NMS NMS算法的大致思想:对于有重叠的候选框:若大于规定阈值(某一提前设定的置信度)则删除,低于阈值的保留.对于 ...
-
非极大值抑制(Non-Maximum Suppression,NMS)
概述 非极大值抑制(Non-Maximum Suppression,NMS),顾名思义就是抑制不是极大值的元素,可以理解为局部最大搜索.这个局部代表的是一个邻域,邻域有两个参数可变,一是邻域的维数,二 ...
-
非极大值抑制(NMS)
转自:https://www.cnblogs.com/makefile/p/nms.html 概述 非极大值抑制(Non-Maximum Suppression,NMS),顾名思义就是抑制不是极大值的 ...
-
非极大值抑制Non-Maximum Suppression(NMS)
非极大值抑制(Non-Maximum Suppression,NMS) 概述 非极大值抑制(Non-Maximum Suppression,NMS),顾名思义就是抑制不是极大值的元素,可以理解为局 ...
-
非极大值抑制(NMS,Non-Maximum Suppression)的原理与代码详解
1.NMS的原理 NMS(Non-Maximum Suppression)算法本质是搜索局部极大值,抑制非极大值元素.NMS就是需要根据score矩阵和region的坐标信息,从中找到置信度比较高的b ...
-
一分钟速学 | NMS, IOU 与 SoftMax
非极大抑制 NMS的英文是Non-maximum suppression的缩写. 简单的说,就是模型给出了多个重叠在一起的候选框,我们只需要保留一个就可以了.其他的重叠的候选框就删掉了,效果可见下图: ...
-
NMS系列
NMS soft NMS softer NMS https://www.cnblogs.com/VincentLee/p/12579756.html
随机推荐
-
序列化,反序列化和transient关键字
一.序列化和反序列化的概念 序列化:指把java对象转换为字节序列的过程. 反序列化:指把字节序列恢复为java对象的过程. 对象的序列化主要有两种用途: 1) 把对象的字节序列保存到硬盘上,通常存放 ...
-
C++注意
断言assert是仅在Debug版本起作用的宏,它用于检查“不应该”发生的情况. 在函数的入口处,使用断言检查参数的有效性(合法性). 如果程序在assert处终止了,并不是说含有该assert的函数 ...
-
gulp配置文件备份
/** * Created by leyi on 2016/8/25 0025. */ /*********************package.json依赖模块****************** ...
-
Cheatsheet: 2014 10.01 ~ 10.30
.NET ASP.NET Web Api: Unwrapping HTTP Error Results and Model State Dictionaries Client-Side HTTP 20 ...
-
MongoDB 删除数据库
MongoDB 删除数据库 语法 MongoDB 删除数据库的语法格式如下: db.dropDatabase() 删除当前数据库,默认为 test,你可以使用 db 命令查看当前数据库名. 实例 以下 ...
-
onkeyup,onkeydown和onkeypress
如下一段代码: <html> <script> function checkForm(){ if(event.keyCode ==13){ event.keyCo ...
-
Linux System Programming note 8 ——File and Directory Management
1. The Stat Family #include <sys/types.h> #include <sys/stat.h> #include <unistd.h> ...
-
运算符重载 与 sort()
运算符重载与sort() 二话不说上代码: #include <iostream> #include <algorithm> using namespace std; stru ...
-
3 Eclipse 查看不了源码
Eclipse 查看源码时,报source not found问题,经查资料,需要配置环境变量才能查看到. 在用户变量或者系统变量下,配置CLASSPATH,值为JDK的lib路径:D:\Progra ...
-
内核知识第六讲,内核编写规范,以及获取GDT表
内核知识第六讲,内核编写规范,以及获取GDT表 一丶内核驱动编写规范 我们都知道,在ring3下,如果我们的程序出错了.那么就崩溃了.但是在ring0下,只要我们的程序崩溃了.那么直接就蓝屏了. 那么 ...