非最大值抑制(NMS)（一）

非最大值抑制是一种主要用于目标检测的技术，其目的是从一组重叠框中选择出最佳的边界框。

首先，目标检测与图像分类不同，图像分类往往只有一个输出，但目标检测的输出个数却是未知的。除了Ground-Truth（标注数据）训练，模型永远无法百分百确信自己要在一张图上预测多少物体。

所以目标检测问题的老大难问题之一就是如何提高召回率。召回率（Recall）是模型找到所有某类目标的能力（所有标注的真实边界框有多少被预测出来了）。检测时按照是否检出边界框与边界框是否存在，可以分为下表四种情况：

召回率是所有某类物体中被检测出的概率，并由下式给出：

为了提高这个值，很直观的想法是“宁肯错杀一千，绝不放过一个”。因此在目标检测中，模型往往会提出远高于实际数量的区域提议（Region Proposal，SSD等one-stage的Anchor也可以看作一种区域提议）。

这就导致最后输出的边界框数量往往远大于实际数量，而这些模型的输出边界框往往是堆叠在一起的。因此，我们需要NMS从堆叠的边框中挑出最好的那个。

在下图中，非最大值抑制的目的是移除黄色和蓝色框，这样我们就只剩下绿色框了。

• 我们将使用的每个边界框的格式如下:bbox = [x1, y1, x2, y2, class, confidence].
• 假设对于这个图像我们有一个3个边界框列表;i.e bbox_list = [blue_box, yellow_box, green_box].
  • green_box = [x1, y1, x2, y2, ”Cat”, 0.9]
  • blue_box = [x3, y3, x4, y4, ”Cat”, 0.85]
  • yellow_box = [x5, y5, x6, y6, ”Cat”, 0.75]

• 作为NMS的第一步，我们按照置信度对框进行降序排序。这给了我们:bbox_list = [green_box, blue_box, yellow_box]
• 然后定义置信阈值。任何置信值低于此阈值的框都将被删除。对于本例，让我们假设置信阈值为0.8。使用这个阈值，我们将删除黄色框，因为它的置信度< 0.8。这就给我们留下了:bbox_list = [green_box, blue_box]
  

• 由于方框按照置信度降序排列，我们知道列表中的第一个方框具有最高的置信度。我们从列表中删除第一个框，并将其添加到一个新列表中。在本例中，我们将删除绿色框，并将其放入一个新列表中，例如bbox_list_new。
• 在这个阶段，我们为 IOU 定义了一个额外的阈值。此阈值用于删除具有高重叠的框。其推理如下：如果两个框有大量重叠，并且它们也属于同一类，则两个框很可能覆盖同一对象。由于目标是每个对象有一个框，我们尝试删除置信度较低的框。
• 对于我们的示例，假设我们的 IOU 阈值为 0.5
• 我们现在开始计算 绿色框与bbox_list 中也具有相同类的每个剩余框的 IOU。在我们的例子中，我们将只计算蓝色框与绿色框的 IOU。
• 如果绿框和蓝框的 IOU 大于我们定义的阈值 0.5，我们将移除蓝框，因为它具有较低的置信度，并且也有显着的重叠。
• 对图像中的每个框重复此过程，以仅得到具有高置信度的唯一框。
  

• 1.为confence_threshold和IOU_Threshold定义一个值。
• 2.按置信度的降序对边界框进行排序。
• 3.删除置信度 < Confidence_Threshold 的框
• 4.循环所有剩余的框，首先从具有最高置信度的框开始。
• 5.计算当前框与属于同一类的所有剩余框的 IOU。
• 6.如果 2 个框的 IOU > IOU_Threshold，则从我们的框列表中删除置信度较低的框。
• 7.重复此操作，直到我们遍历完列表中的所有框。

下面的代码是执行NMS的基本功能。可以优化以下计算 NMS 的代码以提高性能。

def nms(boxes, conf_threshold=0.7, iou_threshold=0.4):
	"""
	该函数对框列表执行 nms：
	boxes: [box1, box2, box3...]
	box1: [x1, y1, x2, y2, Class, Confidence]
	"""
	bbox_list_thresholded = []	# 按置信度过滤后包含框的列表
	bbox_list_new = []			# 包含 nms 之后的最终框的列表
	# 第 1 阶段：（对框进行排序，并过滤掉置信度低的框）
	boxes_sorted = sorted(boxes, reverse=True, key = lambda x : x[5])	# 根据置信度对框进行排序
	for box in boxes_sorted:
		if box[5] > conf_threshold:		# 检查方框的置信度是否大于阈值
			bbox_list_thresholded.append(box)	# 将框附加到bbox_list_thresholded列表
		else:
			pass
	#第 2 阶段：（循环遍历所有框，并删除 IOU 高的框）
	while len(bbox_list_thresholded) > 0:
		current_box = bbox_list_thresholded.pop(0)		# 移除最高置信度的包围框
		bbox_list_new.append(current_box)				# 将其附加到最终框bbox_list_new列表中
		for box in bbox_list_thresholded:
			if current_box[4] == box[4]:				# 检查两个框是否属于同一类
				iou = IOU(current_box[:4], box[:4])		# 计算两个包围框的IOU
				if iou > iou_threshold:					# 检查iou是否大于定义的阈值
					bbox_list_thresholded.remove(box)	# 如果有显著重叠，则删除框
	return bbox_list_new

• 1.该函数将特定图像的框列表、置信阈值和 iou 阈值作为输入。 （我已将它们的默认值分别设置为 0.7 和 0.4）
• 2.我们创建了 2 个名为 bbox_list_thresholded 和 bbox_list_new 的列表。 bbox_list_thresholded：包含过滤低置信度框后的新框列表 bbox_list_new：包含执行NMS后的最终box列表
• 3.我们通过按置信度降序对框列表进行排序来开始阶段 1，并将新列表存储在变量 box_sorted 中。名为 sorted 的Python 内置函数遍历我们的框列表，并根据我们指定的关键字对其进行排序。在我们的例子中，我们指定关键字 reverse=True 以降序对列表进行排序。第二个关键字 key 指定我们要用于排序的约束。我们使用的 lambda 函数提供了一个映射，该映射返回每个边界框的第 5 个元素（置信度）。 sorted 函数在遍历每个框时，会查看 lambda 函数，该函数将返回框的第 5 个元素（置信度），并以相反的顺序对其进行排序。
• 4.我们迭代所有已排序的框，并删除置信度低于我们设置的阈值的框（conf_threshold=0.7）
• 5.在第 2 阶段，我们将阈值框列表（bbox_list_thresholded）中的所有框一一循环，直到列表被清空。 我们首先从这个列表（current_box）中删除（弹出）第一个框，因为它具有最高的置信度，并将其附加到我们的最终列表（bbox_list_new）。
• 6.然后我们遍历列表 bbox_list_thresholded 中所有剩余的框，并检查它们是否与当前框属于同一类。 （box[4] 对应类）
• 7.如果两个框属于同一类，我们计算这些框之间的 IOU（我们将 box[:4] 传递给 IOU 函数，因为它对应于 (x1, y1, x2, y2) 的值，因为我们的 IOU函数不需要类别和置信度）。
• 8.如果 IOU > iou_threshold，我们从列表 bbox_list_thresholded 中删除该框，因为该框是IOU较大的框。
• 9.在NMS之后，我们返回更新的框列表。

import cv2
import numpy as np

def draw_boxes(frame, bbox_list, color=(255,0,0)):
	"""绘制框列表中的所有框，并显示置信度
		bbox_list = [box1,box2,box3....etc]
		box1 = [x1, y1, x2, y2, Class, confidence]
		要绘制框，我们只需要坐标，
		box1[:4] = [x1, y1, x2, y2]
		box1[5] = confidence"""
	for box in bbox_list:
		x1, y1, x2, y2 = box[:4]	# 我们只需要 (x1, y1) 和 (x2, y2) 坐标
		conf = box[5]
		cv2.rectangle(frame, pt1=(x1, y1), pt2=(x2, y2), color=color, thickness=2)
		frame = cv2.putText(frame, str(conf), (x1, y1-5), cv2.FONT_HERSHEY_SIMPLEX , 0.5, 
						(255, 255, 255), 1, cv2.LINE_AA) 	# 在图像上绘制IOU
	return frame

def IOU(boxA, boxB):
	""" 我们假设框遵循以下格式：
		box1 = [x1,y1,x2,y2], and box2 = [x3,y3,x4,y4],
		其中 (x1,y1) 和 (x3,y3) 表示左上角坐标
		(x2,y2) 和 (x4,y4) 代表右下角坐标 """
	# 确定相交矩形的 (x, y) 坐标
	xA = max(boxA[0], boxB[0])
	yA = max(boxA[1], boxB[1])
	xB = min(boxA[2], boxB[2])
	yB = min(boxA[3], boxB[3])
	# 计算相交矩形的面积
	interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)
	# 计算预测和真实矩形的面积
	boxAArea = (boxA[2] - boxA[0] + 1) * (boxA[3] - boxA[1] + 1)
	boxBArea = (boxB[2] - boxB[0] + 1) * (boxB[3] - boxB[1] + 1)
	# 通过取交集区域并将其除以预测 + 真实区域 - 交集区域的总和来计算并集交集
	iou = interArea / float(boxAArea + boxBArea - interArea)
	return iou

def nms(boxes, conf_threshold=0.7, iou_threshold=0.4):
	"""
	该函数对框列表执行 nms：
	boxes: [box1, box2, box3...]
	box1: [x1, y1, x2, y2, Class, Confidence]
	"""
	bbox_list_thresholded = []	# 按置信度过滤后包含框的列表
	bbox_list_new = []			# 包含 nms 之后的最终框的列表
	# 第 1 阶段：（对框进行排序，并过滤掉置信度低的框）
	boxes_sorted = sorted(boxes, reverse=True, key = lambda x : x[5])	# 根据置信度对框进行排序
	for box in boxes_sorted:
		if box[5] > conf_threshold:		# 检查方框的置信度是否大于阈值
			bbox_list_thresholded.append(box)	# 将框附加到bbox_list_thresholded列表
		else:
			pass
	#第 2 阶段：（循环遍历所有框，并删除 IOU 高的框）
	while len(bbox_list_thresholded) > 0:
		current_box = bbox_list_thresholded.pop(0)		# 移除最高置信度的包围框
		bbox_list_new.append(current_box)				# 将其附加到最终框bbox_list_new列表中
		for box in bbox_list_thresholded:
			if current_box[4] == box[4]:				# 检查两个框是否属于同一类
				iou = IOU(current_box[:4], box[:4])		# 计算两个包围框的IOU
				if iou > iou_threshold:					# 检查iou是否大于定义的阈值
					bbox_list_thresholded.remove(box)	# 如果有显著重叠，则删除框
	return bbox_list_new

def main():
	img = cv2.imread("Images/img.jpg")	# 读取图像
	img = cv2.resize(img, (416, 416))	# 调整要在屏幕上显示的图像的大小
	img_nms = img.copy()				# 创建图像的副本以在其上绘图

	bbox_dog1 = [90, 261, 228, 378, "Dog", 0.9]		# 定义不同的边界框
	bbox_dog2 = [121, 290, 216, 374, "Dog", 0.6]	
	bbox_dog3 = [49, 265, 243, 388, "Dog", 0.85]	
	bbox_person1 = [234, 91, 359, 370, "Person", 0.95]	
	bbox_person2 = [239, 116, 359, 374, "Person", 0.45]	
	bbox_person3 = [234, 71, 359, 370, "Person", 0.92]	
	bbox_list = [bbox_dog1, bbox_dog2, bbox_dog3, bbox_person1, bbox_person2, bbox_person3]	# 创建框的列表
	
	bbox_list_new = nms(bbox_list, conf_threshold=0.7, iou_threshold=0.4)	# 调用该函数执行NMS

	img = draw_boxes(img, bbox_list)				# 绘制nms之前的所有框
	img_nms = draw_boxes(img_nms, bbox_list_new)	# 绘制nms后的所有框
	img = cv2.putText(img, str("Before NMS"), (30, 30), cv2.FONT_HERSHEY_SIMPLEX , 1, 			# 写在nms之前的图像上
						(0, 0, 0), 2, cv2.LINE_AA) 		
	img_nms = cv2.putText(img_nms, str("After NMS"), (30, 30), cv2.FONT_HERSHEY_SIMPLEX , 1, 	# 写在nms之后图像上
						(0, 0, 0), 2, cv2.LINE_AA) 	
	cv2.imwrite("img.jpg", np.hstack((img, img_nms)))	# 保存图像
	cv2.imshow("IMG", np.hstack((img, img_nms)))	# 水平堆叠图像并显示
	cv2.waitKey()	# 等待按任意键退出

if __name__ == "__main__":
	main()

原图：

NMS前后图：

https://medium.com/analytics-vidhya/non-max-suppression-nms-6623e6572536