二维布尔型数组的子区域

Question

我有一个二维的布尔类型数组。我想要得到一个包含 True 值的最小子区域，并且边界也全部为 False 的切片列表（或类似的数据结构）。

我可以循环遍历每一行和每一列，当满足这个条件时，存储其索引，但是我想知道是否有其他更高效的方式或者库来实现这个功能。你可以假定原始布尔数组的边界总是为 False/0。

例子1: 例子2: 编辑！添加了新的例子并提供了正确的解决方案。对于混淆问题，我感到很抱歉。

- JustANoob

---

不确定你的例子是否符合逻辑。为什么在下面的框中的第一个框不应该包含在更大的框中，因为它们共享一列？ - yatu

我犯了一些错误，我添加了相同的数组。它们代表两个不同的示例，红色标记的区域是我想要获取切片的子区域。 - JustANoob

在第一个例子中，不应该有三个区域吗？编辑：我想这取决于您是想要最大尺寸的区域还是最小尺寸的区域。 - user10400458

定义是有效的，并且具有唯一解。我今天不知道自己在想什么，甚至不能给出正确的示例解决方案...马上更新。 - JustANoob

这回答解决了你的问题吗？在像素数组中查找连通组件 那不就是查找连通组件吗？ - HansHirse

Answer 1

这是连通组件分析，之前已经有人提出并回答了。根据那里的被接受的答案来适应您的需求，可能的解决方案非常简短：

import numpy as np
from scipy.ndimage.measurements import label


def analysis(array):
    labeled, _ = label(array, np.ones((3, 3), dtype=np.int))
    for i in np.arange(1, np.max(labeled)+1):
        pixels = np.array(np.where(labeled == i))
        x1 = np.min(pixels[1, :])
        x2 = np.max(pixels[1, :])
        y1 = np.min(pixels[0, :])
        y2 = np.max(pixels[0, :])
        print(str(i) + ' | slice: array[' + str(y1) + ':' + str(y2) + ', ' + str(x1) + ':' + str(x2) + ']')


example1 = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 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, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 1, 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, 0, 0]
]).astype(bool)

example2 = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]).astype(bool)

for a in [example1, example2]:
    print(a, '\n')
    analysis(a)
    print('\n')

这是输出的结果（不包含示例）：

[[...]] 

1 | slice: array[1:2, 3:5]
2 | slice: array[4:6, 6:8]
3 | slice: array[8:8, 2:2]

[[...]] 

1 | slice: array[1:3, 5:8]
2 | slice: array[2:2, 3:3]
3 | slice: array[4:5, 1:1]
4 | slice: array[5:8, 3:6]
5 | slice: array[6:6, 8:8]
6 | slice: array[8:8, 8:8]

希望能帮到您！

------------------
System information
------------------
Python:  3.8.1
SciPy:   1.4.1
------------------

- HansHirse

Answer 2

你可以从图的角度来解决这个问题，将1的坐标作为图元素，8向连接，然后只需找到图中的连通分量。如果数据稀疏，则应该比循环可能的正方形尺寸要快得多。以下是它的工作原理示例：

from itertools import combinations

def find_squares(a):
    # Find ones
    ones = [(i, j) for i, row in enumerate(a) for j, val in enumerate(row) if val]
    # Make graph of connected ones
    graph = {a: [] for a in ones}
    for a, b in combinations(ones, 2):
        if abs(a[0] - b[0]) <= 1 and abs(a[1] - b[1]) <= 1:
            graph[a].append(b)
            graph[b].append(a)
    # Find connected components in graph
    components = []
    for a, a_neigh in graph.items():
        if any(a in c for c in components):
            continue
        component = {a, *a_neigh}
        pending = [*a_neigh]
        visited = {a}
        while pending:
            b = pending.pop()
            if b in visited:
                continue
            visited.add(b)
            component.add(b)
            b_neigh = graph[b]
            component.update(b_neigh)
            pending.extend(c for c in b_neigh if c not in visited)
        components.append(component)
    # Find bounds for each component
    bounds = [((min(a[0] for a in c), min(a[1] for a in c)),
               (max(a[0] for a in c), max(a[1] for a in c)))
              for c in components]
    return bounds

a = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
     [0, 0, 0, 1, 0, 0, 1, 0, 1, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
     [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
square_bounds = find_squares(a)
print(*square_bounds, sep='\n')
# ((1, 5), (3, 8))
# ((2, 3), (2, 3))
# ((4, 1), (5, 1))
# ((5, 3), (8, 6))
# ((6, 8), (6, 8))
# ((8, 8), (8, 8))

- jdehesa