非極大值抑制（Non-Maximum Suppression, NMS）

1. What

非極大值抑制，簡稱為NMS算法，英文為Non-Maximum Suppression。其思想是搜素局部最大值，抑制極大值。NMS算法在不同應用中的具體實作不太一樣，但思想是一樣的。非極大值抑制，常用于邊緣檢測、目标檢測等計算機視覺任務。

2. Why

以目标檢測為例：目标檢測的過程中在同一目标的位置上會産生大量的候選框，這些候選框互相之間可能會有重疊，此時我們需要利用非極大值抑制找到最佳的目标邊界框，消除備援的邊界框。

2. How

1. 根據置信度得分進行排序；
2. 選擇置信度最高的比邊界框添加到最終輸出清單中，将其從邊界框清單中删除；
3. 計算所有邊界框的面積；
4. 計算置信度最高的邊界框與其它候選框的IoU；
5. 删除IoU大于門檻值的邊界框；
6. 重複上述過程，直至邊界框清單為空。

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