非极大值抑制(Non-Maximum Suppression)

文章作者:Tyan

博客:noahsnail.com  |  CSDN  |  简书 |   云+社区

1. 什么是非极大值抑制

非极大值抑制,简称为NMS算法,英文为Non-Maximum Suppression。其思想是搜素局部最大值,抑制极大值。NMS算法在不同应用中的具体实现不太一样,但思想是一样的。非极大值抑制,在计算机视觉任务中得到了广泛的应用,例如边缘检测、人脸检测、目标检测(DPM,YOLO,SSD,Faster R-CNN)等。

2. 为什么要用非极大值抑制

以目标检测为例:目标检测的过程中在同一目标的位置上会产生大量的候选框,这些候选框相互之间可能会有重叠,此时我们需要利用非极大值抑制找到最佳的目标边界框,消除冗余的边界框。Demo如下图:

左图是人脸检测的候选框结果,每个边界框有一个置信度得分(confidence score),如果不使用非极大值抑制,就会有多个候选框出现。右图是使用非极大值抑制之后的结果,符合我们人脸检测的预期结果。

3. 如何使用非极大值抑制

前提:目标边界框列表及其对应的置信度得分列表,设定阈值,阈值用来删除重叠较大的边界框。

IoU:intersection-over-union,即两个边界框的交集部分除以它们的并集。

非极大值抑制的流程如下:

  • 根据置信度得分进行排序
  • 选择置信度最高的比边界框添加到最终输出列表中,将其从边界框列表中删除
  • 计算所有边界框的面积
  • 计算置信度最高的边界框与其它候选框的IoU。
  • 删除IoU大于阈值的边界框
  • 重复上述过程,直至边界框列表为空。

Python代码如下:

#!/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)

源码下载地址:https://github.com/SnailTyan/deep-learning-tools/blob/master/nms.py

记得给个Star。Demo原图在README.md里。

实验结果:

  • 阈值为0.6
  • 阈值为0.5
  1. http://cs.brown.edu/~pff/papers/lsvm-pami.pdf
  2. http://blog.csdn.net/shuzfan/article/details/52711706
  3. http://www.cnblogs.com/liekkas0626/p/5219244.html
  4. http://www.tk4479.net/yzhang6_10/article/details/50886747
  5. http://blog.csdn.net/qq_14845119/article/details/52064928

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习原理

深度学习——CNN(2)池化层怎么反向传播?为什么采用小批量梯度下降?学习率设置

3903
来自专栏ATYUN订阅号

新手,你需要了解的关于神经网络的所有知识

这篇文章将带你了解什么是人工智能,机器学习和深度学习。 ? 神经元(Node)  – 它是神经网络的基本单位。它获得一定数量的输入和一个偏置值。当信号(值)到...

3397
来自专栏小鹏的专栏

反向传播与它的直观理解

为了感谢大神,我是跪在电脑前fork的。 问题描述与动机: 大家都知道的,其实我们就是在给定的图像像素向量x和对应的函数f(x),然后我们希望能够计算f在...

1799
来自专栏杨熹的专栏

用验证曲线 validation curve 选择超参数

本文结构: 验证曲线的作用? 验证曲线是什么? 怎么解读? 怎么画? ---- 验证曲线的作用? 我们知道误差由偏差(bias)、方差(variance)和噪声...

2805
来自专栏小詹同学

深度学习入门笔记系列 ( 四 )

本系列将分为 8 篇 。今天是第四篇 。总是理论有些枯燥 ,今天来动手基于 TF 框架实现两个简单的案例 ,以小搏大熟悉一下整个过程 。整体来说 ,训练神经网络...

532
来自专栏Bingo的深度学习杂货店

使用Tensorflow实现一个简单的神经网络

输入层、隐藏层、输出层的数目分别为2、3、1; 隐藏层和输出层的激活函数使用的是 ReLU; 训练的样本总数为 512,每次迭代读取的批量为 10; 交叉熵为损...

2444
来自专栏fangyangcoder

Andrew Ng机器学习课程笔记(二)之逻辑回归

http://www.cnblogs.com/fydeblog/p/7364636.html

833
来自专栏数值分析与有限元编程

逆迭代法求矩阵特征值

前面提到,幂迭代法用于求矩阵的主特征值以及对应的特征向量。如果把幂迭代用于这个矩阵的逆矩阵,那么就能求得最小的特征值。来看下面的定理: 设n阶矩阵A的特征值用λ...

3486
来自专栏Python中文社区

机器学习算法实践-标准与局部加权线性回归

專 欄 ❈PytLab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

2696
来自专栏决胜机器学习

机器学习(八) ——过拟合与正则化

机器学习(八)——过拟合与正则化 (原创内容,转载请注明来源,谢谢) 一、过拟合和欠拟合 1、概念 当针对样本集和特征值,进行预测的时候,推导θ、梯度下降等...

3325

扫码关注云+社区