非極大值抑制（Non-Maximum Suppression窘哈，NMS[1]）可以正面地表述為局部最大搜索（Local Maximum Search）, 其中局部最大值大于其所有鄰居 (不包括其自身)。本質(zhì)上是搜索局部極大值雌澄，抑制非極大值元素倚喂。
NMS 在計(jì)算機(jī)視覺領(lǐng)域有著非常重要的應(yīng)用每篷，如視頻目標(biāo)跟蹤、數(shù)據(jù)挖掘端圈、3D重建焦读、目標(biāo)識別以及紋理分析等。[2]
2.1 1D NMS
Straightforward Implementation
NMS 的簡單實(shí)現(xiàn)由兩個(gè)嵌套循環(huán)組成, 其中外部循環(huán)遍歷所有像素, 內(nèi)部循環(huán)針對外部循環(huán)的所有鄰居測試其候選項(xiàng)舱权。一旦鄰居強(qiáng)度超過當(dāng)前候選, 內(nèi)部循環(huán)就會中止矗晃。顯然, 該算法需要對每個(gè)像素做 2n 次比較, 而不需要提前中止。在最壞的情況下, 中止不能降低復(fù)雜性宴倍。這可以通過將算法應(yīng)用于強(qiáng)度趨勢來看出张症。由于一側(cè)的像素總是小于候選像素, 因此內(nèi)部循環(huán)會在第 (n + 1) 迭代處中止, 從而使每個(gè)像素有 n + 1 次比較。因此, 比較像素的最壞情況數(shù)是 鸵贬。關(guān)于時(shí)間復(fù)雜度分析的具體內(nèi)容可查看原論文[1]俗他。下面我以一張圖片來說明 NMS：
import numpy as np
from matplotlib import pyplot as plt
np.set_printoptions(2) # 修改了 NumPy 的打印精度
# 指定默認(rèn)字體, 為在 Matplotlib 中顯示中文，設(shè)置特殊字體
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False # 解決保存圖像是負(fù)號 '-' 顯示為方塊的問題
%matplotlib inline
img_name = '../images/catdog.jpg'
img = plt.imread(img_name)
載入圖片之后恭理，我們先討論 3-Neighborhood拯辙。
3-近鄰
我們先將原圖片拉直為一個(gè)向量郭变，下面我們定義 NMS：
I = img.flatten()[:30]
w = len(I)
maximumat = []
i = 1
while i + 1 < w:
if I[i] > I[i+1] and I[i] >= I[i-1]: # I[i] 是極大值
maximumat.append(i)
else:
i += 1
while i + 1 < w and I[i] <= I[i+1]:
i += 1
if i + 1 < w:
maximumat.append(i)
i += 2
plt.plot(I, 'y--')
plt.scatter(maximumat, I[maximumat])
plt.axis('off')
for _x, _y in enumerate(I):
plt.text(_x, _y, str(_x))
為了更加形象颜价，下面我們將展示 NMS 處理前后的圖像：
I = img.flatten()
w = len(I)
maximumat = []
i = 1
while i + 1 < w:
if I[i] > I[i+1] and I[i] >= I[i-1]:
maximumat.append(i)
else:
i += 1
while i + 1 < w and I[i] <= I[i+1]:
i += 1
if i + 1 < w:
maximumat.append(i)
i += 2
K = img[:].flatten()
K[maximumat] = 0
img1 = K.reshape(img.shape) # 去除極大值點(diǎn)后組成的圖像
img2 = img - img1 # 極大值點(diǎn)組成的圖像
plt.figure(figsize=(10, 10))
plt.subplot(131)
plt.imshow(img)
plt.title('原圖')
plt.axis('off')
plt.subplot(132)
plt.imshow(img1)
plt.title('去除極大值點(diǎn)圖')
plt.axis('off')
plt.subplot(133)
plt.imshow(img2)
plt.title('極大值點(diǎn)圖')
plt.axis('off')
plt.show()
2.2 動(dòng)態(tài)塊算法：(2n+1)-近鄰
def nms(y, n):
'''
參數(shù)
===========
y:: 一維數(shù)組
n:: 近鄰數(shù)
返回
==========
N-近鄰 的 NMS
'''
i = 0
maximumat = []
w = len(y)
while 2 * n + i < w:
if I[i+n] > max(I[i+n+1:i+2*n]) and I[i+n] >= max(I[i:i+n]):
maximumat.append(i+n)
else:
i += 1
while 2 * n + i < w and I[i+n] < max(I[i+n+1:i+2*n]):
i += 1
if 2 * n + i < w:
maximumat.append(i+n)
i += n
return maximumat
為了方便我將可視化的代碼放入函數(shù)：
def plot(img, img1, img2):
plt.figure(figsize=(10, 10))
plt.subplot(131)
plt.imshow(img)
plt.title('原圖')
plt.axis('off')
plt.subplot(132)
plt.imshow(img1)
plt.title('去除極大值點(diǎn)圖')
plt.axis('off')
plt.subplot(133)
plt.imshow(img2)
plt.title('極大值點(diǎn)圖')
plt.axis('off')
plt.show()
import numpy as np
from matplotlib import pyplot as plt
np.set_printoptions(2) # 修改了 NumPy 的打印精度
# 指定默認(rèn)字體, 為在 Matplotlib 中顯示中文，設(shè)置特殊字體
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False # 解決保存圖像是負(fù)號 '-' 顯示為方塊的問題
%matplotlib inline
img_name = '../images/catdog.jpg'
img = plt.imread(img_name)
I = img.flatten()
n = 3
maximumat = nms(I, n)
K = img[:].flatten()
K[maximumat] = 0
img1 = K.reshape(img.shape) # 去除極大值點(diǎn)后組成的圖像
img2 = img - img1 # 極大值點(diǎn)組成的圖像
plot(img, img1, img2)
I = img.flatten()
n = 100
maximumat = nms(I, n)
K = img[:].flatten()
K[maximumat] = 0
img1 = K.reshape(img.shape) # 去除極大值點(diǎn)后組成的圖像
img2 = img - img1 # 極大值點(diǎn)組成的圖像
plot(img, img1, img2)
-
Neubeck A, Van Gool L. Efficient Non-Maximum Suppression[C]. international conference on pattern recognition, 2006: 850-855. ? ?
-
非極大值抑制（Non-Maximum Suppression诉濒，NMS）周伦，顧名思義就是抑制不是極大值的元素，可以理解為局部最大搜索未荒。這個(gè)局部代表的是一個(gè)鄰域专挪，鄰域有兩個(gè)參數(shù)可變，一是鄰域的維數(shù)，二是鄰域的大小寨腔。這里不討論通用的 NMS 算法(參考論文《Efficient Non-Maximum Suppression》 對 1 維和 2 維數(shù)據(jù)的 NMS 實(shí)現(xiàn))速侈，而是用于目標(biāo)檢測中提取分?jǐn)?shù)最高的窗口的。例如在行人檢測中迫卢，滑動(dòng)窗口經(jīng)提取特征倚搬，經(jīng)分類器分類識別后，每個(gè)窗口都會得到一個(gè)分?jǐn)?shù)乾蛤。但是滑動(dòng)窗口會導(dǎo)致很多窗口與其他窗口存在包含或者大部分交叉的情況每界。這時(shí)就需要用到 NMS 來選取那些鄰域里分?jǐn)?shù)最高（是行人的概率最大），并且抑制那些分?jǐn)?shù)低的窗口家卖。@http://www.cnblogs.com/makefile/p/nms.html ? 康行天下 ?
