面試必考 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隻調整每個框的位置，而不篩選框。
貼一張效果圖：