Check efficiently if two pixels of an image are connected

Question

Suppose you have an arbitrary black and white image, consider the following ones as an example:

...........     ........... 
...........     ........... 
...........     ........... 
.OOO...O...     ........... 
X...O.O.OOY     XOOO...OOOY 
.....O.....     ........... 
...........     ........... 
...........     ........... 
...........     ...........

Where "." represent black pixels, "O", "X", "Y" represent white pixels

The left picture's X and Y pixels are interconnected between themselves along the path of O's (in terms of Moore's neighbourhood). While on the right picture X and Y pixels are disconnected. By having an arbitrary black and white image, I need highly performant algorithm that will answer the question whether some group of pixels is connected to another group of pixels. I'm pretty sure that there has to be well-developed solution to this problem, since the problem looks common, but I can't seem to find one that would suite me. And by the way I'm aware of Flood Fill algorithm but currently I'm not considering it, since it does more job than it is required to answer the initial question.

I would appreciate reference to any info in subject direction,

P.S.

Just in case you have the answer the original question, maybe you might have answer to the following:

...........
...........
...........
.OOO...O...
X...O.O.OOY
.....O.....
..........Z
..........U
..........V

It would be also great (but not required) could answer the initial question in the following form:

Pixel X is connected to pixel Y,

Pixel X is not connected to pixel Z,

Pixel X is not connected to pixel U,

Pixel X is not connected to pixel V,

Thank you in advance!

possible duplicate of [Connected Component Labelling](http://stackoverflow.com/questions/14465297/connected-component-labelling) — beaker, Aug 03 '15 at 02:36
Either Depth-First or Breadth-First Search (as in the linked question) will efficiently answer any of these questions. — beaker, Aug 03 '15 at 02:38
The best algorithm depends on your use-cases. Are you going to have a single image, and then test lots of pairs of pixels on that image? Or is it a different image each time? — samgak, Aug 03 '15 at 04:18
Connected Component Labelling solves my problem in best possible ways, thank you — Lu4, Aug 03 '15 at 08:28

score 1 · Accepted Answer · answered Aug 03 '15 at 04:22

You are right, the problem is pretty common and have a well known performant algorithm which runs in time proportional to the size of the input: O(n) (because each vertex have maximum 8 edges). All you need is to pass through the image to create a graph, where each pixel is the vertex and the edge is when 2 vertices are neighbors.

Then having a graph you simply run a DFS/BFS on your graph, starting with your X vertex and stopping if either you reached Y, or there is nothing in your frontier.

Notice that here you can also take advantage of heuristics and even use A* algorithm (where your heuristics is the manhattan distance).

Check efficiently if two pixels of an image are connected

P.S.

1 Answers1