Non-maximum Suppression
directory
1. What is non-maximum suppression
2. Why use non-maximum suppression
3. How to use non-maximum suppression
4. Reference materials
1. What is non-maximum suppression
Non-maximum Suppression is the NMS algorithm for short. The idea is to search for local maximum value and suppress maximum value. The specific implementation of the NMS algorithm varies from application to application, but the idea is the same. Non-maximum suppression has been widely used in computer vision tasks, such as edge detection, face detection, target detection (DPM, YOLO, SSD, Faster R-CNN), etc.
2. Why use non-maximum suppression
Take target detection as an example: in the process of target detection, a large number of candidate boxes will be generated at the same target position, and these candidate boxes may overlap with each other. In this case, we need to use non-maximum suppression to find the best target boundary boxes and eliminate redundant boundary boxes. The Demo is shown below:
Object Detection
The left figure shows the result of candidate boxes for face detection. Each bounding box has a confidence score. If non-maximum suppression is not used, multiple candidate boxes will appear. The picture on the right shows the result after using non-maximum suppression, which is in line with our expected result of face detection.
3. How to use non-maximum suppression
Prerequisite: the target bounding box list and its corresponding confidence score list, set the threshold value, the threshold value is used to delete the overlapping bounding box. IoU: intersection-over-union. The part of the intersection of two boundary boxes is divided by their union.
The flow of non-maximum suppression is as follows:
- Sort by confidence score
- Select the ratio bounding box with the highest confidence to add to the final output list and remove it from the bounding box list
- Calculates the area of all bounding boxes
- Calculate the IoU of the bounding box with the highest confidence and other candidate boxes.
- Delete the border box whose IoU is greater than the threshold
- Repeat the process until the bounding box list is empty.
The Python code is as follows:
#! /usr/bin/env python
# _*_ coding: utf-8 _*_
import cv2
import numpy as np
""" Non-max Suppression Algorithm @param list Object candidate bounding boxes @param list Confidence score of bounding boxes @param float IoU threshold @return Rest boxes after nms operation """
def nms(bounding_boxes, confidence_score, threshold) :
# If no bounding boxes, return empty list
if len(bounding_boxes) == 0:
return [], []
# Bounding boxes
boxes = np.array(bounding_boxes)
# coordinates of bounding boxes
start_x = boxes[:, 0]
start_y = boxes[:, 1]
end_x = boxes[:, 2]
end_y = boxes[:, 3]
# Confidence scores of bounding boxes
score = np.array(confidence_score)
# Picked bounding boxes
picked_boxes = []
picked_score = []
# Compute areas of bounding boxes
areas = (end_x - start_x + 1) * (end_y - start_y + 1)
# Sort by confidence score of bounding boxes
order = np.argsort(score)
# Iterate bounding boxes
while order.size > 0:
# The index of largest confidence score
index = order[-1]
# Pick the bounding box with largest confidence score
picked_boxes.append(bounding_boxes[index])
picked_score.append(confidence_score[index])
# Compute ordinates of intersection-over-union(IOU)
x1 = np.maximum(start_x[index], start_x[order[:-1]])
x2 = np.minimum(end_x[index], end_x[order[:-1]])
y1 = np.maximum(start_y[index], start_y[order[:-1]])
y2 = np.minimum(end_y[index], end_y[order[:-1]])
# Compute areas of intersection-over-union
w = np.maximum(0.0, x2 - x1 + 1)
h = np.maximum(0.0, y2 - y1 + 1)
intersection = w * h
# Compute the ratio between intersection and union
ratio = intersection / (areas[index] + areas[order[:-1]] - intersection)
left = np.where(ratio < threshold)
order = order[left]
return picked_boxes, picked_score
# Image name
image_name = 'nms.jpg'
# Bounding boxes
bounding_boxes = [(187.82.337.317), (150.67.305.282), (246.121.368.304)]
confidence_score = [0.9.0.75.0.8]
# Read image
image = cv2.imread(image_name)
# Copy image as original
org = image.copy()
# Draw parameters
font = cv2.FONT_HERSHEY_SIMPLEX
font_scale = 1
thickness = 2
# IoU threshold
threshold = 0.4
# Draw bounding boxes and confidence score
for (start_x, start_y, end_x, end_y), confidence in zip(bounding_boxes, confidence_score):
(w, h), baseline = cv2.getTextSize(str(confidence), font, font_scale, thickness)
cv2.rectangle(org, (start_x, start_y - (2 * baseline + 5)), (start_x + w, start_y), (0.255.255), -1)
cv2.rectangle(org, (start_x, start_y), (end_x, end_y), (0.255.255), 2)
cv2.putText(org, str(confidence), (start_x, start_y), font, font_scale, (0.0.0), thickness)
# Run non-max suppression algorithm
picked_boxes, picked_score = nms(bounding_boxes, confidence_score, threshold)
# Draw bounding boxes and confidence score after non-maximum supression
for (start_x, start_y, end_x, end_y), confidence in zip(picked_boxes, picked_score):
(w, h), baseline = cv2.getTextSize(str(confidence), font, font_scale, thickness)
cv2.rectangle(image, (start_x, start_y - (2 * baseline + 5)), (start_x + w, start_y), (0.255.255), -1)
cv2.rectangle(image, (start_x, start_y), (end_x, end_y), (0.255.255), 2)
cv2.putText(image, str(confidence), (start_x, start_y), font, font_scale, (0.0.0), thickness)
# Show image
cv2.imshow('Original', org)
cv2.imshow('NMS', image)
cv2.waitKey(0)
Copy the codeDownload source address: github.com/SnailTyan/d… Make sure you give me a Star. The original Demo is in readme.md.
Experimental results:
- Threshold value of 0.6
Threshold = 0.6
- Threshold value of 0.5
Threshold = 0.5
- Threshold value of 0.4
Threshold = 0.4
4. Reference materials
- www.pyimagesearch.com/2014/11/17/…
- Cs.brown.edu/~pff/papers…
- Blog.csdn.net/shuzfan/art…
- www.cnblogs.com/liekkas0626…
- www.tk4479.net/yzhang6_10/…
- Blog.csdn.net/qq_14845119…