Overview of Non-Maximum Suppression (NMS) Algorithm
Non-Maximum Suppression (NMS) is an algorithm used for computer vision tasks such as object detection, primarily to select the most reliable one from multiple overlapping bounding boxes or detection windows It will be An overview of NMS is given below.
1. Principle of operation of NMS: NMS works by the following steps:
1. Obtain the reliability score and bounding box information of the detected object: Obtain the bounding box of the object detected by the detector (e.g., object detection model) and its corresponding reliability score (the confidence that the detected object really exists).
2. Find the bounding box with the largest confidence score: Sort the bounding boxes in descending order by confidence score, take the bounding box at the top of the sorted list (with the largest confidence score), and add it to the adoption list. This bounding box is the basis for comparison with the remaining bounding boxes. 3.
3. Calculate the overlap with other bounding boxes and remove those that are larger than the threshold: For the remaining bounding boxes, calculate the overlap with the bounding box with the largest reliability score (Intersection over Union, IoU), and if the IoU is larger than the threshold value (usually 0.5 ), and bounding boxes with an IoU greater than the threshold (usually 0.5) are considered as overlapping. Among the overlapping bounding boxes, all bounding boxes other than the one with the largest reliability score are removed. For more information on IoU, see “Overview of IoU (Intersection over Union) and related algorithms and implementation examples“.
4. Adding bounding boxes to the employment list: Non-overlapping bounding boxes are added to the employment list, and the bounding box with the largest reliability score among overlapping bounding boxes is also added to the employment list.
5. Iteration: The above procedure is repeated until there are no bounding boxes remaining.
2. Advantages of NMS:
Reduction of overlapping bounding boxes: NMS reduces overlapping multiple candidate detections, leaving the most reliable detection results.
Selection of the detection with the highest reliability score: Based on the bounding box with the largest reliability score, NMS compares it with other detection candidates and selects the appropriate one.
NMS is one of the algorithms that play an important role in computer vision tasks such as object detection and semantic segmentation, which, with appropriately set thresholds and efficient implementation, can produce accurate and efficient detection results.
Algorithms related to the NMS algorithm
Although NMS itself is a stand-alone algorithm, there are related algorithms and methods. The following describes those algorithms related to NMS.
1. Sorting and Filtering: NMS is based on the concepts of sorting and filtering. The method sorts the list of detected objects by their confidence scores and filters out overlapping objects in order to select the most reliable ones.
Sorting: The detected objects are sorted in descending order by reliability score, which places the most reliable ones at the top.
Filtering: Process the sorted list in order, removing overlapping bounding boxes. The bounding box with the highest reliability score is adopted and any overlapping bounding boxes are removed.
2. Intersection over Union (IoU): IoU is an indicator of the degree of overlap between two bounding boxes, based on the threshold used in NMS. It is defined by the following formula
\[ IoU = \frac{{\text{Area of Intersection}}}{{\text{Area of Union}}} \]
If the IoU is greater than the threshold, the two bounding boxes are considered to overlap.
3. Soft-NMS: Soft-NMS is an improved version of NMS and introduces soft weighting to update object scores. While normal NMS removes overlapping bounding boxes, Soft-NMS gives weights to overlapping bounding boxes to ease the removal process. This method preserves some overlapping bounding boxes, resulting in improved object detection accuracy.
4. Greedy NMS: Greedy NMS is a general NMS algorithm. It processes a list of detected objects sorted in descending order by reliability score and removes overlapping bounding boxes, and of those that overlap, those with lower reliability scores are removed.
5. Soft-IoU: Soft-IoU will be a method of normalizing the IoU by using a soft-max function in the calculation of the IoU. This produces a soft IoU score.
Application examples of the NMS algorithm
NMS is widely used mainly in object detection tasks. Examples of their applications are described below.
1. Object Detection: In object detection, multiple bounding boxes (detection windows) are obtained when multiple objects exist in an image. In this case, NMS is applied as follows.
- Sort the detected bounding boxes by reliability score.
- Select the most reliable bounding box and calculate its overlap with the other bounding boxes.
- Bounding boxes whose overlap exceeds a certain threshold are removed to obtain the final object detection result.
2. semantic segmentation: Semantic segmentation predicts for each pixel in an image which class it belongs to. In this case, there are multiple candidates for each pixel, and NMS is applied to remove overlap to obtain the final segmentation result.
3 Character Recognition: In character recognition, NMS can be used to eliminate overlapping characters to obtain accurate character detection results.
4. Object Tracking: In object tracking in video data, objects may overlap in consecutive frames; NMS can be used to remove the overlap from the object detection results of each frame to obtain consecutive tracking results.
5. face detection: In face detection, multiple faces may be detected; NMS can be applied to eliminate overlaps and obtain accurate face detection results.
6. vehicle detection in parking lots and traffic scenes: NMS is also used for vehicle detection in parking lots and traffic scenes. Multiple vehicles may overlap, and NMS can be applied to obtain accurate vehicle detection results.
Example Implementation of the Non-Maximum Suppression (NMS) Algorithm
An example of a basic NMS implementation is shown below. In the following example, a simple NMS algorithm is implemented using Python and NumPy. Here, we take as input a list of Bounding Boxes and their reliability scores.
import numpy as np
def non_maximum_suppression(boxes, scores, threshold):
"""
Implementation of non-maximum suppression (NMS) algorithm
Args:
- boxes: A list of bounding boxes. Each bounding box is represented in the format [x1, y1, x2, y2
- scores: List of bounding box reliability scores.
- threshold: IoU (degree of overlap) threshold. Overlapping boxes with an IoU greater than this value are excluded.
Returns:
- selected_indices: List of indices for the selected bounding box.
"""
# Bounding box coordinates
x1 = boxes[:, 0]
y1 = boxes[:, 1]
x2 = boxes[:, 2]
y2 = boxes[:, 3]
# Bounding box area
areas = (x2 - x1 + 1) * (y2 - y1 + 1)
# Sort index in order of highest score
indices = np.argsort(scores)[::-1]
selected_indices = []
while len(indices) > 0:
# Get the index of the bounding box with the highest score
i = indices[0]
selected_indices.append(i)
# Calculate IoU with remaining bounding boxes
xx1 = np.maximum(x1[i], x1[indices[1:]])
yy1 = np.maximum(y1[i], y1[indices[1:]])
xx2 = np.minimum(x2[i], x2[indices[1:]])
yy2 = np.minimum(y2[i], y2[indices[1:]])
w = np.maximum(0.0, xx2 - xx1 + 1)
h = np.maximum(0.0, yy2 - yy1 + 1)
inter_area = w * h
iou = inter_area / (areas[i] + areas[indices[1:]] - inter_area)
# Delete bounding boxes whose degree of overlap is below a threshold
indices = indices[1:][iou <= threshold]
return selected_indices
In this example, boxes is a two-dimensional NumPy array with bounding box coordinates ([x1, y1, x2, y2] format) per row, and scores is a list of reliability scores for each bounding box. Also, threshold will be the threshold of the IoU.
The function applies NMS to the given bounding boxes and reliability scores, removes bounding boxes with large overlap, and returns the index of the selected bounding box.
Challenges of the NMS Algorithm and Measures to Address Them
Although NMS is a useful method, it also has several challenges. These challenges and corresponding countermeasures are described below.
Challenges:
1. selection of IoU threshold: In NMS, the IoU threshold for removing overlapping bounding boxes needs to be set appropriately. If the threshold is too high, objects that should be detected will not be detected properly.
2. setting the optimal threshold for each class: The optimal IoU thresholds for different classes of objects differ, and setting the optimal threshold for each class can improve accuracy, but is difficult to set manually.
3. impact of low-reliability detection results: Low-reliability detection results (bounding boxes with low reliability scores) may leave overlapping bounding boxes in the NMS process, which increases false positives and reduces accuracy.
4. computational efficiency problem: NMS performs overlap calculations on a large number of bounding boxes, which increases the computational cost, especially for large data sets and high-resolution images.
Solution:
1. dynamic adjustment of IoU: Instead of a fixed threshold value, some methods dynamically adjust the IoU threshold based on the distance between bounding boxes, reliability scores, etc. This allows searching for the optimal threshold value under various conditions and improving accuracy.
2. class-specific optimization: To set optimal IoU thresholds for each class, there are methods that allow the detection model to learn during training, and by learning class-specific thresholds, appropriate thresholds can be set for different classes of objects.
3. soft NMS: Soft NMS also gives weights to overlapping bounding boxes and mitigates deletion, which allows unreliable detection results to be more appropriately handled in the NMS process, reducing the impact of false positives.
4. use of acceleration methods: There are methods available to accelerate NMS calculations, such as parallel processing using graphics cards (GPUs), implementation in fast languages such as Cython and C++, and approximate calculations using features. These methods can be used to improve computational efficiency.
Reference Information and Reference Books
For details on image information processing, see “Image Information Processing Techniques.
Reference book is “
“
“
“
コメント