面试必考 N M S NMS NMS汇总
1. N M S NMS NMS代码与实现
N o n Non Non- M a x i m u m Maximum Maximum- S u p p r e s s i o n Suppression Suppression(非极大值抑制): 当两个 b o x box box空间位置非常接近，就以 s c o r e score score更高的那个作为基准，看 I O U IOU IOU即重合度如何，如果与其重合度超过阈值，就抑制 s c o r e score score更小的 b o x box box，只保留 s c o r e score score大的就 B o x Box Box，其它的 B o x Box Box就都应该过滤掉。对于 N M S NMS NMS而言，适合于水平框，针对各种不同形状的框，会有不同的 N M S NMS NMS来进行处理。
具体的步骤如下：
- 如图所示，我们有 6 6 6个带置信率的 r e g i o n region region p r o p o s a l s proposals proposals，我们先预设一个 I O U IOU IOU的阈值如 0.7 0.7 0.7。
- 按置信率大小对 6 6 6个框排序，举例为 0.94 , 0.91 , 0.90 , 0.83 , 0.79 , 0.77 0.94, 0.91, 0.90, 0.83, 0.79, 0.77 0.94,0.91,0.90,0.83,0.79,0.77。
- 设定置信率为 0.94 0.94 0.94的 r e g i o n region region p r o p o s a l s proposals proposals为一个物体框；
- 在剩下 5 5 5个 r e g i o n region region p r o p o s a l s proposals proposals中进行循环遍历，去掉与 0.94 0.94 0.94物体框 I O U IOU IOU大于 0.7 0.7 0.7的。
- 重复 2 2 2～ 4 4 4的步骤，直到没有 e g i o n egion egion p r o p o s a l s proposals proposals为止。
- 每次获取到的最大置信率的 r e g i o n region region p r o p o s a l s proposals proposals就是我们筛选出来的目标。
参考代码如下：
import numpy as np
def NMS(dets, thresh):
"""Pure Python NMS baseline."""
# tl_x,tl_y,br_x,br_y及score
x1 = dets[:, 0]
y1 = dets[:, 1]
x2 = dets[:, 2]
y2 = dets[:, 3]
scores = dets[:, 4]
#计算每个检测框的面积，并对目标检测得分进行降序排序
areas = (x2 - x1 + 1) * (y2 - y1 + 1)
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]
order = order[inds + 1] #注意这里索引加了1,因为ovr数组的长度比order数组的长度少一个
return keep
运行后，则删除了多余的框，结果如图所示：
2. S o f t Soft Soft N M S NMS NMS的代码与实现
说到 S o f t Soft Soft N M S NMS NMS，首先需要了解传统 N M S NMS NMS有哪些缺点。其主要缺点包括如下：
- 物体重叠：如下面第一张图，会有一个最高分数的框，如果使用 N M S NMS NMS的话就会把其他置信度稍低，但是表示另一个物体的预测框删掉（由于和最高置信度的框 o v e r l a p overlap overlap过大）
- 所有的 b b o x bbox bbox都预测不准：不是所有的框都那么精准，有时甚至会出现某个物体周围的所有框都标出来了，但是都不准的情况，如下图所示。
- 传统的 N M S NMS NMS方法是基于分类分数的，只有最高分数的预测框能留下来，但是大多数情况下 I o U IoU IoU和分类分数不是强相关，很多分类标签置信度高的框都位置都不是很准。
S o f t Soft Soft N M S NMS NMS主要是针对 N M S NMS NMS过度删除框的问题。 S o f t − N M S Soft-NMS Soft−NMS吸取了 N M S NMS NMS的教训，在算法执行过程中不是简单的对 I o U IoU IoU大于阈值的检测框删除，而是降低得分。算法流程同 N M S NMS NMS相同，但是对原置信度得分使用函数运算，目标是降低置信度得分。其算法步骤如下：
红色的部分表示原始 N M S NMS NMS算法，绿色部分表示 S o f t Soft Soft- N M S NMS NMS算法，区别在于，绿色的框只是把 s i s_{i} si降低了，而不是把 b i b_{i} bi直接去掉，极端情况下，如果 f f f只返回 0 0 0，那么等同于普通的 N M S NMS NMS。
b i b_{i} bi为待处理 B B o x BBox BBox框， B B B为待处理 B B o x BBox BBox框集合， s i s_{i} si是 b i b_{i} bi框更新得分， N t N_{t} Nt是 N M S NMS NMS的阈值， D D D集合用来放最终的 B B o x BBox BBox， f f f是置信度得分的重置函数。 b i b_{i} bi和 M M M的 I O U IOU IOU越大， b i b_{i} bi的得分 s i s_{i} si就下降的越厉害。
f f f函数是为了降低目标框的置信度，满足条件，如果 b i b_{i} bi和 M M M的 I o U IoU IoU越大， f ( i o u ( M , b i ) ) f(iou(M, bi)) f(iou(M,bi))就应该越小， S o f t Soft Soft- N M S NMS NMS提出了两种 f f f函数：
经典的 N M S NMS NMS算法将 I O U IOU IOU大于阈值的窗口的得分全部置为 0 0 0，可表述如下：
论文置信度重置函数有两种形式改进，一种是线性加权的：
一种是高斯加权形式：
s i = s i e − i o u ( M , b i ) 2 σ , ∀ b i ∉ D s_{i}=s_{i} e^{-\frac{\mathrm{iou}\left(\mathcal{M}, b_{i}\right)^{2}}{\sigma}}, \forall b_{i} \notin \mathcal{D} si=sie−σiou(M,bi)2,∀bi∈/D
$Soft $ N M S NMS NMS算法的优点如下：
- 该方案可以很方便地引入到object detection算法中，不需要重新训练原有的模型;
- soft-NMS在训练中采用传统的NMS方法，可以仅在推断代码中实现soft-NMS。
- N M S NMS NMS是 S o f t Soft Soft- N M S NMS NMS特殊形式，当得分重置函数采用二值化函数时， S o f t Soft Soft- N M S NMS NMS和 N M S NMS NMS是相同的。 s o f t soft soft- N M S NMS NMS算法是一种更加通用的非最大抑制算法。
而，在一些场景的实验中，可以看到 S o f t Soft Soft N M S NMS NMS的效果也是优于 N M S NMS NMS的。
这里提供一个 g i t h u b github github 中的 C y t h o n Cython Cython代码展示:
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):
# 在i之后找到confidence最高的框，标记为max_pos
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
# 找到max的框
while pos < N:
if maxscore < boxes[pos, 4]:
maxscore = boxes[pos, 4]
maxpos = pos
pos = pos + 1
# 交换max_pos位置和i位置的数据
# 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
while pos < N:
# 先记录内层循环的数据bi
x1 = boxes[pos, 0]
y1 = boxes[pos, 1]
x2 = boxes[pos, 2]
y2 = boxes[pos, 3]
s = boxes[pos, 4]
# 计算iou
area = (x2 - x1 + 1) * (y2 - y1 + 1)
iw = (min(tx2, x2) - max(tx1, x1) + 1) # 计算两个框交叉矩形的宽度，如果宽度小于等于0，即没有相交，因此不需要判断
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) #计算union面积
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
S o f t e r Softer Softer N M S NMS NMS的代码与实现
针对剩余的两个问题， S o f t e r Softer Softer N M S NMS NMS做出了自己的努力。
- 针对分类置信度和框的 I o U IoU IoU不是强相关的问题，构建一种 I o U IoU IoU的置信度，来建模有多大把握认为当前框和 G T GT GT是重合的。
- 针对所有的框单独拿出来都不准的问题，文章中提出一种方法，根据 I o U IoU IoU置信度加权合并多个框优化最终生成框。
S o f t e r Softer Softer- N M S NMS NMS文章对预测框建模，以下公式中 x x x表示偏移前的预测框， x e x_{e} xe表示偏移后的预测框，输出的 x g x_{g} xg表示 G T GT GT框，使用高斯函数对预测框建模:
P Θ ( x ) = 1 2 π σ 2 e − ( x − x e ) 2 2 σ 2 P_{\Theta}(x)=\frac{1}{2 \pi \sigma^{2}}e^{-\frac{(x-x_{e})^2}{2 \sigma^{2}}} PΘ(x)=2πσ21e−2σ2(x−xe)2
对于 G T GT GT框建模：使用 d e l t a delta delta分布(即标准方差为 0 0 0的高斯分布极限)。
P D ( x ) = δ ( x − x g ) P_{D}(x)=\delta\left(x-x_{g}\right) PD(x)=δ(x−xg)
对于 d e l t a delta delta分布，当 σ \sigma σ越小，其函数图像就会越瘦高，同时，当 σ \sigma σ越小，表示网络越确定，可以使用 1 − σ 1-\sigma 1−σ就可以作为网络的置信度。
同时，论文使用 K L KL KL散度来最小化 B o u n d i n g Bounding Bounding b o x box box r e g r e s s i o n regression regression l o s s loss loss。既 B o u n d i n g Bounding Bounding b o x box box的高斯分布和 g r o u n d ground ground t r u t h truth truth的狄拉克 d e l t a delta delta分布的 K L KL KL散度。直观上解释， K L KL KL L o s s Loss Loss使得 B o u n d i n g Bounding Bounding b o x box box预测呈高斯分布，且与 g r o u n d ground ground t r u t h truth truth相近。而将包围框预测的标准差看作置信度。
如 f a s t e r faster faster r c n n rcnn rcnn中添加了 s o f t e r softer softer n m s nms nms之后的示意图如图所示：
多加了一个 σ \sigma σ预测，也就是 b o x box box s t d std std，而 B o x Box Box的预测其实就是上面公式中的 x e x_{e} xe。
因此，整个计算过程如下：
- 计算 x e x_{e} xe与 x x x的2范数距离和 σ \sigma σ计算出 P θ ( x ) P_{\theta}(x) Pθ(x).
- 通过 x g x_{g} xg与 x x x的2范数距离算出 P D P_{D} PD.
- 使用 P D P_{D} PD与 P θ P_{\theta} Pθ计算 K L s KLs KLs散度作为 l o s s loss loss，最小化 K L L o s s KLLoss KLLoss。
关于坐标回归的损失函数：
L r e g = D K L ( P D ( x ) ∥ P Θ ( x ) ) = ∫ P D ( x ) log P D ( x ) P Θ ( x ) d x = − ∫ P D ( x ) log P Θ ( x ) d x + ∫ P D ( x ) log P D ( x ) d x = − ∫ P D ( x ) log P Θ ( x ) d x + H ( P D ( x ) ) = − log P Θ ( x g ) + H ( P D ( x ) ) = ( x g − x e ) 2 2 σ 2 + 1 2 log ( σ 2 ) + 1 2 log ( 2 π ) + H ( P D ( x ) ) \begin{array}{l} L_{r e g}=D_{K L}\left(P_{D}(x) \| P_{\Theta}(x)\right) \\ =\int P_{D}(x) \log \frac{P_{D}(x)}{P_{\Theta}(x)} d x \\ =-\int P_{D}(x) \log P_{\Theta}(x) d x+\int P_{D}(x) \log P_{D}(x) d x \\ =-\int P_{D}(x) \log P_{\Theta}(x) d x+H\left(P_{D}(x)\right) \\ =-\log P_{\Theta}\left(x_{g}\right)+H\left(P_{D}(x)\right) \\ =\frac{\left(x_{g}-x_{e}\right)^{2}}{2 \sigma^{2}}+\frac{1}{2} \log \left(\sigma^{2}\right)+\frac{1}{2} \log (2 \pi)+H\left(P_{D}(x)\right) \end{array} Lreg=DKL(PD(x)∥PΘ(x))=∫PD(x)logPΘ(x)PD(x)dx=−∫PD(x)logPΘ(x)dx+∫PD(x)logPD(x)dx=−∫PD(x)logPΘ(x)dx+H(PD(x))=−logPΘ(xg)+H(PD(x))=2σ2(xg−xe)2+21log(σ2)+21log(2π)+H(PD(x))
而后面两项是与 x e x_{e} xe无关，可以去掉～
L reg = α ( ∣ x g − x e ∣ − 1 2 ) − 1 2 log ( α + ϵ ) L_{\text {reg }}=\alpha\left(\left|x_{g}-x_{e}\right|-\frac{1}{2}\right)-\frac{1}{2} \log (\alpha+\epsilon) Lreg =α(∣xg−xe∣−21)−21log(α+ϵ)
因此，计算过程如下图所示：
网络预测出来的结果是 x 1 i , y 1 i , x 2 i , y 2 i , σ x 1 i , σ x 2 i , σ x 3 i , σ x 4 i x1_{i}, y1_{i}, x2_{i}, y2_{i}, \sigma{x1_{i}}, \sigma{x2_{i}}, \sigma{x3_{i}}, \sigma{x4_{i}} x1i,y1i,x2i,y2i,σx1i,σx2i,σx3i,σx4i。前面四个为坐标，而后面四个是坐标的 σ \sigma σ。
上表中的蓝色的是 s o f t soft soft- n m s nms nms，只是降低了 S S S的权值。重点看绿色的，绿字第一行表示拿出所有与 B B B的 I o U IoU IoU大于 N t N_{t} Nt的框（用 i d x idx idx表示），然后将所有这些框做一个加权， B [ i d x ] / C [ i d x ] B[idx]/C[idx] B[idx]/C[idx]其实是 B [ i d x ] ∗ 1 / C [ i d x ] B[idx] * 1/C[idx] B[idx]∗1/C[idx]，后者是置信度 1 σ 2 \frac{1}{\sigma^{2}} σ21，并使用 s u m sum sum做了归一化。需要注意的是， S o f t e r Softer Softer- N M S NMS NMS算法中， B B B是不变的， s o f t e r softer softer- n m s nms nms只调整每个框的位置，而不筛选框。
贴一张效果图：