Given a 2D array , find regions in it

Question

Let us assume we have the following 2d array:

2 1 2 2 1 1 
2 2 1 2 1 1 
2 1 3 2 1 1 
2 2 2 1 3 3 
2 2 1 1 3 3 
2 2 1 1 3 3

Now, I want to find contiguous regions in the above. Two locations belong to a contiguous region if there is a path between them and their values are the same. Moreover, all nodes in the path should also have the same value. For example, We can divide the above into the following 5 regions:

A B A A D D 
A A B A D D 
A B C A D D 
A A A D E E
A A D D E E 
A A D D E E

You are allowed to go in all 8 directions. I am looking for an implementation in Java. Can someone please help me with this. The interface is something like

VectorFeature returnComp(int matrix[][])

where VectorFeature can be as follows

class VectorFeature{
  string region
  int numberForRegion
  int numOfElements

}

I Know the idea of how to implement this but i am looking for a fast/ bug free implementation in JAVA!

This should help http://stackoverflow.com/questions/1257117/does-anyone-have-a-working-non-recursive-floodfill-algorithm-written-in-c — innochenti, Feb 19 '12 at 16:56
@innochenti: Moreover, floodfill only allows going in 4 directions. For me its 8 — Programmer, Feb 19 '12 at 17:00
@Programmer: There is nothing to stop you implementing an 8-neighbour flood-fill. — Oliver Charlesworth, Feb 19 '12 at 17:07

score 0 · Accepted Answer · answered Feb 19 '12 at 16:57

0

You could do worse than starting at Wikipedia: Connected-component labeling.

answered Feb 19 '12 at 16:57

Oliver Charlesworth

267,707
33
569
680

score 0 · Answer 2 · answered Feb 19 '12 at 17:48

Here's what to do.

Firs turn your 2d array into a (mostly) 8 degree graph with the following rule:

e (i,j) if color_i = color_j for all i, for all j in 8neighbours.i

Represent these edges as an adjacency matrix A

Then take the following element-wise OR product

C = I OR A OR A^2 OR A^3 OR ... A^k

Where C is the or-product that has a 1 at i,j if there is a path from i to j in any of 0-k steps.

Now, finally take the element wise and-product

R = C AND C_transpose

Row i of R has a column at j iff i and j belong to the same component. Then you have your regions, since the only paths this will represent are the paths that you originally represented in your 2D array. And no edges will go between regions. But this matrix product takes a while to compute, so we want an alternative:

For reasons I won't go into relating to convergence of the sum of the above progression of As, we can choose a tuneable parameter alpha to make that series converge and we can find an approximation to R by

R' = inverse(I - alpha * A)

This will have the same pattern of non-zero elements as in R, but is much easier to compute. (Note that, while in R you will have 1s and 0s ,in R' you will have 0s and non-0s (floats), so you can read off the regions all the same)

You could do this in Java. But why not use matlab?

This answer was taken nearly verbatim (but not) from the great book:Graph Algorithms in the Language of Linear Algebra. By J Kepner and J Gilbert.

Given a 2D array , find regions in it

2 Answers2