深入理解NMS算法：原理、优化及代码实现 – wiki大全

作者： /

深入理解NMS算法：原理、优化及代码实现

1. 引言：NMS在目标检测中的核心作用

在计算机视觉领域，目标检测是一项基石任务，旨在识别图像中目标物体的位置（通过边界框）及其类别。现代目标检测算法，无论是基于区域提议（如Faster R-CNN）还是单阶段检测器（如YOLO、SSD），通常会生成大量的候选边界框（Bounding Box）。这些候选框往往会高度重叠，并且可能检测到同一个目标物体多次，但置信度略有不同。如果不加以处理，这将导致检测结果冗余且混乱。

非极大值抑制（Non-Maximum Suppression, NMS）算法正是为了解决这一问题而生。它的核心思想是：在一个局部区域内，抑制（或移除）那些置信度较低的重叠边界框，只保留置信度最高的边界框。NMS是几乎所有目标检测管道中不可或缺的后处理步骤，它能够显著提升检测结果的清晰度和准确性。

2. NMS算法的原理详解

NMS算法的原理相对直观，但其背后的逻辑对于理解目标检测至关重要。

2.1 核心概念：交并比（Intersection over Union, IoU）

在深入NMS之前，必须理解交并比（IoU）。IoU是衡量两个边界框重叠程度的指标。给定两个边界框 $B_1$ 和 $B_2$：

$$IoU(B_1, B_2) = \frac{Area(B_1 \cap B_2)}{Area(B_1 \cup B_2)}$$

其中，$Area(B_1 \cap B_2)$ 表示 $B_1$ 和 $B_2$ 的交集面积，$Area(B_1 \cup B_2)$ 表示 $B_1$ 和 $B_2$ 的并集面积。IoU的值域为 $[0, 1]$，值越大表示两个边界框重叠程度越高。

在NMS中，IoU用于判断两个边界框是否“过于重叠”，从而决定是否进行抑制。

2.2 传统NMS算法步骤

传统NMS算法（Greedy NMS）的步骤如下：

  1. 输入：

    • 一个待处理的边界框列表 $B = {b_1, b_2, …, b_n}$，其中每个 $b_i$ 包含其坐标信息（如 $(x_1, y_1, x_2, y_2)$ 或 $(center_x, center_y, width, height)$）和一个置信度得分 $s_i$。
    • 一个IoU阈值 $T_{iou}$。

  2. 输出：

    • 一个经过NMS处理后的、筛选出的边界框列表 $D$。

  3. 算法流程：

    a. 初始化一个空列表 $D$，用于存放最终的检测结果。
    b. 将所有待处理的边界框 $B$ 按照它们的置信度得分 $s_i$ 进行降序排序。
    c. 循环处理： 当 $B$ 不为空时，重复以下操作：
    * 从 $B$ 中选择置信度得分最高的边界框 $b_{max}$。
    * 将 $b_{max}$ 从 $B$ 中移除，并添加到结果列表 $D$ 中。
    * 对于 $B$ 中剩余的每一个边界框 $b_j$：
    * 计算 $b_{max}$ 和 $b_j$ 之间的IoU值：$IoU(b_{max}, b_j)$。
    * 如果 $IoU(b_{max}, b_j) > T_{iou}$，则说明 $b_j$ 与 $b_{max}$ 严重重叠。由于 $b_{max}$ 是当前置信度最高的框，我们将 $b_j$ 视为冗余检测，将其从 $B$ 中移除（抑制）。
    d. 当 $B$ 变为空时，循环结束。返回列表 $D$。

简而言之： NMS就是不断地找到当前最自信的检测框，并移除所有与它重叠度过高的其他检测框，直到所有框都被处理或移除。

3. 传统NMS算法实现（Python示例）

以下是一个使用Python和NumPy实现传统NMS算法的简化示例。为了清晰起见，我们将分步解释。

“`python
import numpy as np

def compute_iou(box1, box2):
“””
计算两个边界框的IoU。
box1: [x1, y1, x2, y2]
box2: [x1, y1, x2, y2]
“””
# 获取交集区域的坐标
x1_inter = max(box1[0], box2[0])
y1_inter = max(box1[1], box2[1])
x2_inter = min(box1[2], box2[2])
y2_inter = min(box1[3], box2[3])

# 计算交集区域的宽度和高度
width_inter = max(0, x2_inter - x1_inter + 1)
height_inter = max(0, y2_inter - y1_inter + 1)

# 计算交集面积
area_inter = width_inter * height_inter

# 计算box1和box2的面积
area_box1 = (box1[2] - box1[0] + 1) * (box1[3] - box1[1] + 1)
area_box2 = (box2[2] - box2[0] + 1) * (box2[3] - box2[1] + 1)

# 计算并集面积
area_union = area_box1 + area_box2 - area_inter

# 避免除以零
if area_union == 0:
    return 0.0

return area_inter / area_union

def nms(boxes, scores, iou_threshold):
“””
执行非极大值抑制。
boxes: shape (N, 4) 的数组，每个元素是 [x1, y1, x2, y2]
scores: shape (N,) 的数组，每个元素是对应边界框的置信度得分
iou_threshold: IoU阈值
“””
# 确保输入是numpy数组
boxes = np.array(boxes)
scores = np.array(scores)

# 如果没有边界框，直接返回空列表
if len(boxes) == 0:
    return []

# 获取边界框的面积 (用于计算IoU，虽然这里不需要单独计算面积，但在某些IoU实现中可能会用)
# x1 = boxes[:, 0]
# y1 = boxes[:, 1]
# x2 = boxes[:, 2]
# y2 = boxes[:, 3]
# areas = (x2 - x1 + 1) * (y2 - y1 + 1)

# 按照置信度得分降序排序
order = scores.argsort()[::-1]

keep_boxes = [] # 用于保存最终选定的边界框的索引

while order.size > 0:
    # 取出当前置信度最高的边界框的索引
    idx = order[0]
    keep_boxes.append(idx)

    # 移除已选择的边界框
    order = order[1:]

    # 如果没有剩余边界框，则跳出循环
    if order.size == 0:
        break

    # 计算当前最高置信度框与所有剩余框的IoU
    # 批量计算IoU可以提升效率，这里为了简化，仍然逐个计算

    # 选取剩余的边界框
    remaining_boxes = boxes[order]

    ious = [compute_iou(boxes[idx], b) for b in remaining_boxes]
    ious = np.array(ious)

    # 找到IoU小于阈值的边界框，保留它们的索引
    # 这里的np.where返回的是一个元组，我们只需要第一个元素
    inds = np.where(ious <= iou_threshold)[0]

    # 更新order，只保留那些IoU小于阈值的边界框
    order = order[inds]

return boxes[keep_boxes], scores[keep_boxes]

示例用法

if name == “main“:
# 假设有一些边界框和它们的置信度得分
# 格式：[x1, y1, x2, y2]
sample_boxes = np.array([
[10, 10, 50, 50], # 高置信度，作为基准框
[15, 15, 55, 55], # 与第一个框重叠
[8, 8, 48, 48], # 与第一个框重叠
[60, 60, 100, 100], # 不重叠
[65, 65, 105, 105], # 与第四个框重叠
[120, 120, 150, 150] # 不重叠
])
sample_scores = np.array([0.9, 0.85, 0.7, 0.95, 0.8, 0.6]) # 注意，第四个框置信度最高

print("原始边界框和置信度：")
for i, (box, score) in enumerate(zip(sample_boxes, sample_scores)):
    print(f"Box {i}: {box}, Score: {score:.2f}")

iou_threshold = 0.5
selected_boxes, selected_scores = nms(sample_boxes, sample_scores, iou_threshold)

print(f"\nNMS处理后 (IoU阈值={iou_threshold})：")
for i, (box, score) in enumerate(zip(selected_boxes, selected_scores)):
    print(f"Selected Box {i}: {box}, Score: {score:.2f}")

“`

代码解释：

  1. compute_iou(box1, box2)： 负责计算两个边界框的IoU。它通过计算交集和并集面积来得到结果。+1 是为了确保当 x1=x2 或 y1=y2 时，宽度或高度至少为1，避免零面积问题。
  2. nms(boxes, scores, iou_threshold)：
    • 首先将输入转换为NumPy数组，并处理空输入情况。
    • scores.argsort()[::-1]：这是关键一步，它返回根据置信度得分降序排列的索引。NMS总是从置信度最高的框开始处理。
    • keep_boxes：存储最终被保留下来的边界框的原始索引。
    • while order.size > 0：循环直到所有框都被处理完毕。
    • idx = order[0]：获取当前置信度最高的框的索引。
    • keep_boxes.append(idx)：将其添加到保留列表中。
    • order = order[1:]：将当前最高置信度框从待处理列表中移除。
    • remaining_boxes = boxes[order]：获取所有剩余的待处理边界框。
    • ious = [compute_iou(boxes[idx], b) for b in remaining_boxes]：计算当前最高置信度框与所有剩余框的IoU。
    • inds = np.where(ious <= iou_threshold)[0]：找到那些IoU小于等于阈值的框的索引。这些框不会被抑制。
    • order = order[inds]：更新 order 列表，只包含那些未被抑制的框，继续下一轮循环。

4. 传统NMS的局限性

尽管传统NMS算法效果显著，但在某些场景下它存在明显的局限性：

  1. 硬阈值问题： NMS使用一个固定的IoU阈值。
    • 如果阈值设置过高，可能会导致许多实际是不同目标的边界框被错误地保留，造成冗余检测。
    • 如果阈值设置过低，可能会导致真正属于同一目标但IoU稍低的检测框被错误地抑制，尤其是当目标密集排列时。
  2. 对密集目标失效： 当多个目标靠得非常近时（例如，一群人），它们之间的IoU可能很高。传统NMS会倾向于只保留其中置信度最高的一个，而抑制掉其他目标，导致“漏检”。
  3. 忽略置信度差异： 只要IoU超过阈值，无论被抑制框的置信度是0.6还是0.9，它都会被一视同仁地完全移除。这丢失了有用的信息，因为高置信度的重叠框可能包含一些有价值的信息。
  4. 计算复杂度： 原始NMS的时间复杂度在最坏情况下为 $O(N^2)$，其中 $N$ 是边界框的数量。当 $N$ 非常大时，NMS可能成为整个检测管道的瓶颈。

5. NMS的优化与变体

为了解决传统NMS的局限性，研究者们提出了多种优化算法和变体。

5.1 Soft-NMS

Soft-NMS（软NMS）是解决传统NMS“硬抑制”问题的一个重要改进。它的核心思想是：不直接移除重叠度高的边界框，而是降低其置信度得分。

原理：

当一个边界框 $b_j$ 与选定的最高置信度框 $b_{max}$ 的IoU超过阈值时，传统NMS会将其置信度 $s_j$ 设为0（即移除）。Soft-NMS则通过一个函数来衰减 $s_j$，使其分数降低但非完全归零。

常用的衰减函数有两种：

  1. 线性衰减：
    $$s_j = \begin{cases} s_j & \text{if } IoU(b_{max}, b_j) < T_{iou} \ s_j \cdot (1 – IoU(b_{max}, b_j)) & \text{if } IoU(b_{max}, b_j) \ge T_{iou} \end{cases}$$
  2. 高斯衰减：
    $$s_j = s_j \cdot e^{-\frac{IoU(b_{max}, b_j)^2}{\sigma}}$$
    其中 $\sigma$ 是一个超参数，控制衰减的速度。高斯衰减更平滑，通常效果更好。

优点：

  • 保留密集目标： 对于密集排列的目标，即使它们重叠度高，如果被抑制框的置信度原本就很高，Soft-NMS会降低其分数，而不是直接移除。这使得在后续的循环中，该框仍有机会被选中（如果它成为局部最高分），从而减少了漏检。
  • 更灵活： 避免了传统NMS中硬阈值带来的问题。

实现要点：
Soft-NMS的代码实现与传统NMS类似，主要区别在于：当IoU超过阈值时，不是从列表中移除框，而是更新其置信度得分。然后，在每一次循环中，重新根据当前的（可能已经衰减的）置信度得分进行排序，选择最高的框。

5.2 IoU-aware NMS：DIoU-NMS, CIoU-NMS

传统的NMS和Soft-NMS都只考虑了IoU值来判断重叠。然而，IoU有一个缺点：当两个框大小相同且完全包含时，或者当两个框中心点距离很远但IoU相同的情况下，IoU无法区分这些情况。为了更好地衡量边界框的相似性，研究者们提出了DIoU（Distance-IoU）和CIoU（Complete-IoU）。

DIoU和CIoU首先作为改进的损失函数被引入，但它们也可以用于改进NMS。

  • DIoU（Distance-IoU）： 在IoU的基础上考虑了两个边界框中心点的距离。距离越远，DIoU值越小。这有助于NMS更好地处理包含关系，并优先选择中心点更匹配的框。
    $$DIoU = IoU – \frac{\rho^2(b^{ctr}, b_g^{ctr})}{c^2}$$
    其中 $\rho^2(b^{ctr}, b_g^{ctr})$ 是预测框和真实框中心点的欧氏距离平方，$c$ 是覆盖两个框的最小外接矩形的对角线长度。

  • CIoU（Complete-IoU）： 在DIoU的基础上，进一步考虑了边界框的纵横比（aspect ratio）一致性。这使得CIoU在评估边界框相似度时更加全面。
    $$CIoU = DIoU – \alpha v$$
    其中 $\alpha$ 是一个权重参数，$v$ 用于衡量纵横比的一致性。

DIoU-NMS/CIoU-NMS 的思路：

将NMS中的 IoU 替换为 DIoU 或 CIoU 作为判断重叠的标准。即，当 $DIoU(b_{max}, b_j) > T_{diou}$ 时进行抑制（或衰减）。这样做的好处是：

  • 更准确的重叠判断： 不仅考虑重叠面积，还考虑中心点距离和纵横比，使得NMS能更智能地选择最佳边界框。
  • 提升小目标检测效果： 对于小目标，中心点距离和纵横比的微小差异可能导致IoU变化不明显，但DIoU/CIoU能更敏感地反映这些差异。

5.3 其他NMS变体

  • Fast NMS： 旨在提高NMS的计算效率，尤其是在GPU上。它通过并行化一些计算步骤来加速。
  • Cluster NMS / NMS by Components： 针对极端密集目标场景。它不是简单地删除重叠框，而是尝试将重叠框聚类，并从每个聚类中选择一个代表性框。
  • 学习型NMS (Learning NMS)： 尝试使用神经网络来学习NMS的策略，而不是依赖固定的规则和阈值。例如，有的方法会预测一个NMS分数，或者直接预测应该保留哪些框。

6. 结论

NMS算法作为目标检测后处理的关键环节，其重要性不言而喻。它有效地解决了检测器生成大量重叠候选框的问题，显著提升了目标检测的实用性。

从最初的贪婪NMS，到能处理密集目标的Soft-NMS，再到结合几何信息（如中心点距离和纵横比）的DIoU-NMS和CIoU-NMS，NMS算法的演进反映了目标检测领域不断追求更高精度和鲁棒性的努力。理解NMS的原理、局限性及其各种优化变体，对于深入学习和开发高性能的目标检测系统是至关重要的。在实际应用中，根据具体任务的需求和数据特点，选择或调整NMS策略，是提升模型整体性能的关键一步。

这篇文章详细介绍了NMS算法的原理、一个基本的Python代码实现、传统NMS的局限性以及其主要的优化和变体。希望这能帮助您深入理解NMS算法。

滚动至顶部