2D Array neighboring algorithm

Question

I have a 2D array like this:

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

If we extract the coordinates of all the 1's we get:

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

So now I want to find the areas which are created by neighboring 1's (not diagonally). In order to do this, I need to find a way to check the neighbours of neighbors.I've been thinking about using two arrays and swapping the neighbours of one neighbor to one then to another but it isn't a very efiicient way especially when it comes to processing a big array.Is there a better solution to this problem ?

Thanks

Answer 1

There are many such methods, they are referred as connected-component labeling. Here are some of them that are not so old (in no particular order):

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

The second method is mentioned as "Wu's algorithm" in the literature (they actually refer to an older paper, but the algorithm presented there is the same), and is regarded as one of the fastest for this task. Using flood fill is certainly one of the last methods that you would want to use, as it is very slow compared to any of these. This Wu algorithm is a two-pass labeling based on the union-find data structure with path compression, and is relatively easy to implement. Since the paper deals with 8-connectivity, I'm including sample code for handling the 4-connectivity (which your question is about).

The code for the union-find structure is taken as is from the paper, but you will find similar code in about every text you read about this data structure.

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

For simplicity I assume the array is padded with zeroes at the top and left sides.

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

So initially you have an array a which you pass to this function scan. This is the first labeling pass. To resolve the labels, you simply call flatten_label(p). Then the second labeling pass is a trivial one:

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

Now your 4-connected components have been labeled, and max(p) gives how many of those you have. If you read the paper along this code you should have no trouble understanding it. The syntax is from Python, if you have any doubt about its meaning, feel free to ask.

Answer 2

if my understanding of your question is right, you can use floodfill to solve the problem.