在二维数组中填充边界框

Question

我有一个二维NumPy数组，看起来像这样

array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]]) `

我想要创建类似于上面显示的1的边界框掩模。例如，它应该像这样：

array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.], 
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.]])

我怎样才能轻松地做到这一点? 如果其他数字如2、3等存在，但我想忽略它们，并且大多数组是2，我该怎么做呢？

- a_parida

---

搜索“连通区域标记”以学习如何在“背景”值的场景中识别单独的对象。然后找到每个唯一标签的最小和最大行/列。 - Aaron

Answer 1

我们有skimage.measure来使组件标记变得更容易。我们可以使用skimage.measure.label来对数组中的不同组件进行标记，以及使用skimage.measure.regionprops来获取相应的切片，在这种情况下我们可以使用它们将值设置为1：

def fill_bounding_boxes(x):
    l = label(x)
    for s in regionprops(l):
        x[s.slice] = 1
    return x

如果我们尝试使用提议的例子：

from skimage.measure import label, regionprops

a = np.array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]])

我们得到：

fill_bounding_boxes(x)

array([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.]])

- yatu

Answer 2

虽然之前的回答已经很好了，但是下面是使用 scipy.ndimage 实现的方法：

import numpy as np
from scipy import ndimage

def fill_bboxes(x):
    x_components, _ = ndimage.measurements.label(x, np.ones((3, 3)))
    bboxes = ndimage.measurements.find_objects(x_components)

    for bbox in bboxes:
        x[bbox] = 1

    return x

ndimage.measurements.label 使用3x3的"ones"矩阵定义邻域进行连通组件标记。然后，find_objects 确定每个组件的边界框，您可以使用它来将其中的所有内容设置为1。

- mrks

---

你觉得你能扩展它以支持非正交边界框吗？ - a_parida

你可以为每个对象确定最小包围矩形（即对于每个bbox in bboxes），然后填充该矩形下方的区域，而不是bbox下方的区域。据我所知，scipy没有预制的函数来实现这一点。因此，你要么自己编写代码，要么使用类似OpenCV的cv.minAreaRect，但无论哪种情况，都必须决定如何离散化填充。 - mrks

Answer 3

有一个解决方案，但是有点巧妙，我不会为您编程。

OpenCV - 图像处理库，具有用于查找矩形轮廓（直线或旋转）的算法。您可能想要做的是将数组转换为2D灰度图像，查找轮廓并在轮廓内部写入1s。

请查看此图像 - 它来自Opencv DOC - 7.a- https://docs.opencv.org/3.4/dd/d49/tutorial_py_contour_features.html

您将对所有位于绿色线条内部的内容感兴趣。

---

老实说，我认为这比编写一些用于边界框的算法要容易得多。

注意

当然，您不必真正执行图像处理，但我认为仅使用opencv的边界框（countours）算法就足够了。

- Martin

Answer 4

这是一个有趣的问题。2D卷积是一种自然的方法。然而，如果输入矩阵是稀疏的（就像您的示例中），这可能会很昂贵。对于稀疏矩阵，另一种方法是使用聚类算法。这从输入框a（您的例子中的数组）中提取仅非零像素，并运行分层聚类。聚类基于特殊的距离矩阵（元组）进行。如果框在任何方向上相隔不超过1个像素，则合并。您还可以在初始化步骤中为任何所需数字应用过滤器（例如仅对a [row，col] == 1执行并跳过任何其他数字，或者任何您希望的）。"最初的回答"

from collections import namedtuple 

Point = namedtuple("Point",["x","y"]) # a pixel on the matrix
Box = namedtuple("Box",["tl","br"]) # a box defined by top-lef/bottom-right

def initialize(a):
    """ create a separate bounding box at each non-zero pixel. """
    boxes = []
    rows, cols = a.shape
    for row in range(rows):
        for col in range(cols):
            if a[row, col] != 0:
                boxes.append(Box(Point(row, col),Point(row, col)))
    return boxes

def dist(box1, box2):
    """ dist between boxes is from top-left to bottom-right, or reverse. """
    x = min(abs(box1.br.x - box2.tl.x), abs(box1.tl.x - box2.br.x))
    y = min(abs(box1.br.y - box2.tl.y), abs(box1.tl.y - box2.br.y))
    return x, y

def merge(boxes, i, j):
    """ pop the boxes at the indices, merge and put back at the end. """
    if i == j:
        return

    if i >= len(boxes) or j >= len(boxes):
        return

    ii = min(i, j)
    jj = max(i, j)
    box_i = boxes[ii]
    box_j = boxes[jj]
    x, y = dist(box_i, box_j)

    if x < 2 or y < 2:
        tl = Point(min(box_i.tl.x, box_j.tl.x),min(box_i.tl.y, box_j.tl.y))
        br = Point(max(box_i.br.x, box_j.br.x),max(box_i.br.y, box_j.br.y))
        del boxes[ii]
        del boxes[jj-1]
        boxes.append(Box(tl, br))


def cluster(a, max_iter=100):
    """ 
        initialize the cluster. then loop through the length and merge 
        boxes. break if `max_iter` reached or no change in length.
    """
    boxes = initialize(a)
    n = len(boxes)
    k = 0

    while k < max_iter:
        for i in range(n):
            for j in range(n):
                merge(boxes, i, j)
        if n == len(boxes):
            break
        n = len(boxes)
        k = k+1

    return boxes

cluster(a)
# output: [Box(tl=Point(x=2, y=2), br=Point(x=5, y=4)),Box(tl=Point(x=11, y=9), br=Point(x=14, y=11))]

# performance 275 µs ± 887 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# compares to 637 µs ± 9.36 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) for 
#the method based on 2D convolution

这将返回由角点（左上角和右下角）定义的盒子列表。这里的x是行号，y是列号。初始化循环遍历整个矩阵。但之后我们只处理非常小的一部分点。通过改变距离函数，您可以自定义盒子定义（重叠、非重叠等）。性能可以进一步优化（例如，在for循环中，如果i或j大于盒子长度，则可以打破循环，然后从合并函数返回并继续）。"最初的回答"

- Prodipta Ghosh