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?– DaenythJun 7, 2016 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.– NikantJun 7, 2016 at 13:36
-
Split into tiles?– DaenythJun 7, 2016 at 13:45
-
Ok if we split into tiles how do we implement the algorithm?– NikantJun 7, 2016 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– DaenythJun 7, 2016 at 14:06
|
Show 1 more comment
2 Answers
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 asColor(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 machinesM(A)andM(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
AandBthat are adjacent and whereM(A)andM(B)are the same, for eachM. - Perform the closure of equivalence relations across pairs of pixels located on different machines. Basically, handle the case where
M(A)andM(B)are different. - Perform a final round of updating the labels on each pixel, to give the result.
- 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
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)
- https://i.stack.imgur.com/3W3lC.png
- https://i.stack.imgur.com/WVn66.png
- https://i.stack.imgur.com/dVuF4.png
- https://i.stack.imgur.com/snPRM.png
- https://i.stack.imgur.com/yzWk1.png
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.
-
1To speed up the inter-node coordination, each node should prioritize scanning the perimeter of its tile, and flood-fill the middle later. Jun 7, 2016 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. Jun 9, 2016 at 16:31