arrays - 二维数组邻域算法

Question

我有一个像这样的二维数组:

0,1,0,0,1
1,0,1,0,1
0,1,1,0,1
0,1,0,1,1
1,1,0,0,1

如果我们提取所有 1 的坐标，我们会得到:

(height,width)
1,2
1,5
2,1
... 

所以现在我想找到由相邻的 1(不是对角线)创建的区域。为了做到这一点，我需要找到一种方法来检查邻居的邻居。我一直在考虑使用两个数组并将一个邻居的邻居交换到一个然后再交换到另一个，但这不是一种非常有效的方法，尤其是当涉及到处理大数组时。有没有更好的解决方案来解决这个问题？

谢谢

Answer 1

有很多这样的方法，它们被称为连通分量标记。以下是其中一些不太老的(排名不分先后):

1. Light Speed Labeling For RISC Architectures , 2009
2. Optimizing Two-pass Connected-Component Labeling Algorithms , 2009
3. A Linear-time Component-Labeling Algorithm Using Contour Tracing Technique , 2004 年

第二种方法在文献中被称为“Wu's algorithm”(他们实际上指的是一篇较旧的论文，但那里提出的算法是相同的)，被认为是完成这项任务最快的方法之一。使用洪水填充肯定是您最不想使用的方法之一，因为与其中任何一种相比它都非常慢。该Wu算法是一种基于路径压缩的联合查找数据结构的二次标注，实现起来相对容易。由于本文涉及 8 连通性，因此我包含了用于处理 4 连通性(您的问题与此有关)的示例代码。

union-find 结构的代码是从论文中获取的，但是你会在你阅读的关于这个数据结构的每一篇文章中找到类似的代码。

def set_root(e, index, root):
    # Set all nodes to point to a new root.
    while e[index] < index:
        e[index], index = root, e[index]
    e[index] = root

def find_root(e, index):
    # Find the root of the tree from node index.
    root = index
    while e[root] < root:
        root = e[root]
    return root

def union(e, i, j):
    # Combine two trees containing node i and j.
    # Return the root of the union.
    root = find_root(e, i)
    if i != j:
        root_j = find_root(e, j)
        if root > root_j:
            root = root_j
        set_root(e, j, root)
    set_root(e, i, root)
    return root

def flatten_label(e):
    # Flatten the Union-Find tree and relabel the components.
    label = 1
    for i in xrange(1, len(e)):
        if e[i] < i:
            e[i] = e[e[i]]
        else:
            e[i] = label
            label += 1

为简单起见，我假设数组的顶部和左侧用零填充。

def scan(a, width, height): # 4-connected
    l = [[0 for _ in xrange(width)] for _ in xrange(height)]

    p = [0] # Parent array.
    label = 1
    # Assumption: 'a' has been padded with zeroes (bottom and right parts
    # does not require padding).
    for y in xrange(1, height):
        for x in xrange(1, width):
            if a[y][x] == 0:
                continue

            # Decision tree for 4-connectivity.
            if a[y - 1][x]: # b
                if a[y][x - 1]: # d
                    l[y][x] = union(p, l[y - 1][x], l[y][x - 1])
                else:
                    l[y][x] = l[y - 1][x]
            elif a[y][x - 1]: # d
                l[y][x] = l[y][x - 1]
            else:
                # new label
                l[y][x] = label
                p.append(label)
                label += 1

    return l, p

所以最初你有一个数组a，你将它传递给这个函数scan。这是第一个标记 channel 。要解析标签，您只需调用 flatten_label(p)。然后第二个标记过程是微不足道的:

for y in xrange(height):
    for x in xrange(width):
        l[y][x] = p[l[y][x]]

现在你的 4-connected 组件已经被标记，max(p) 给出了你有多少个。如果您沿着这段代码阅读这篇论文，您应该可以毫不费力地理解它。语法来自 Python，如果您对其含义有任何疑问，请随时询问。