4

I have a large image distributed over multiple machines for which I need to implement the flood fill algorithm used in MS Paint. I am able to do it with a single machine but what approach must be followed for multiple machines.

6
  • Can you describe how the image is "distributed" over multiple machines? – Daenyth Jun 7 '16 at 13:34
  • The image is distributed in patches where each patch is stored on a different machine. We can also change this distribution if it will help. – Nikant Jun 7 '16 at 13:36
  • Split into tiles? – Daenyth Jun 7 '16 at 13:45
  • Ok if we split into tiles how do we implement the algorithm? – Nikant Jun 7 '16 at 13:58
  • I was asking if that's how it was split, sorry if that wasn't clear. Do your machines know about the relationship between areas? If each tile knows its left/right/up/down neighbors then it should be straightforward enough – Daenyth Jun 7 '16 at 14:06
3

Speaking very abstractly, connected component labeling is an example of closure of equivalence relations.

  • In the beginning, we only know the equivalence relations for some pairs of pixels. Specifically, we only know the equivalence relation for pixels that are next to each other (adjacent).
  • Each pixel has a color, which is a binary value (either 0 or 1). The equivalence relation for adjacent pixels (A, B) are defined as Color(A) == 1 AND Color(B) == 1
  • Furthermore, the pixels are already partitioned up and stored on different machines. If pixels (A, B) are adjacent but they are partitioned into different machines M(A) and M(B), then these two machines must exchange information in order to find out whether the two pixels are in the equivalence relation.
  • Because the task is an example of closure of equivalence relations, you can always use a divide-and-conquer approach:
    • Perform the closure of equivalence relations within each partition of pixels (depending on how they are stored across the machines). Basically, handle the case for all pairs of pixels A and B that are adjacent and where M(A) and M(B) are the same, for each M.
    • Perform the closure of equivalence relations across pairs of pixels located on different machines. Basically, handle the case where M(A) and M(B) are different.
    • Perform a final round of updating the labels on each pixel, to give the result.

There are several possible implementation strategies. The choice will greatly impact performance, and performance may also be impacted by the input data. (In other words, the performance between best-case input and worst-case input can be significant.)


User contributions licensed under cc by-sa 3.0 with attribution required (content policy)

enter image description here enter image description here enter image description here enter image description here enter image description here

1

I would use a breadth-first approach. Split the large image into tiles and have each worker own one tile, and also know what its neighbors are. Fill the first tile as normal. If any locations touch the edge of the tile and there is a neighbor in that direction, send a message to the neighbor with the location and color information so it can decide whether or not to fill. You then have each neighbor repeat this process until no tile edges with neighbors are reached.

Disclaimer: I've never implemented anything like this before, and I don't know what kind of flaws it might have. It's about 5 minutes worth of thought on the issue and may need changing.

2
  • 1
    To speed up the inter-node coordination, each node should prioritize scanning the perimeter of its tile, and flood-fill the middle later. – comingstorm Jun 7 '16 at 18:22
  • I would use horizontal strips and not tiles, simply because that is probably the way the memory is laid out for the image. – Frank Hileman Jun 9 '16 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.