2

次のような 2D 配列があります。

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によって作成された領域を見つけたいと思っています。これを行うには、隣人の隣人をチェックする方法を見つける必要があります。大きな配列の処理に関しては、この問題に対するより良い解決策はありますか?

ありがとう

4

2 に答える 2

4

このような方法は多数あり、それらは連結成分ラベリングと呼ばれます。それほど古くないものの一部を次に示します (順不同)。

  1. RISCアーキテクチャのための光速ラベリング、2009年
  2. 2パス連結成分ラベリングアルゴリズムの最適化、2009年
  3. 等高線追跡技術を使用した線形時間コンポーネント ラベル付けアルゴリズム、2004

2 番目の方法は、文献で「Wu のアルゴリズム」として言及されており (実際には古い論文を参照していますが、そこで提示されているアルゴリズムは同じです)、このタスクで最も高速な方法の 1 つと見なされています。フラッド フィルの使用は、これらの方法に比べて非常に遅いため、絶対に使用したくない方法の 1 つです。この Wu アルゴリズムは、パス圧縮を使用したユニオン検索データ構造に基づく 2 パス ラベル付けであり、比較的簡単に実装できます。この論文は 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。これは最初のラベリング パスです。ラベルを解決するには、単に を呼び出しますflatten_label(p)。次に、2 番目のラベル付けパスは簡単なものです。

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

これで、4 連結コンポーネントにラベルが付けられ、max(p)それらの数がわかります。このコードに沿って論文を読めば、問題なく理解できるはずです。構文は Python からのものです。その意味について疑問がある場合は、お気軽にお問い合わせください。

于 2013-01-16T02:56:50.573 に答える
0

あなたの質問に対する私の理解が正しければ、 floodfillを使用して問題を解決できます。

于 2013-01-16T01:17:38.220 に答える