patternMinor
Efficient flood filling (seed filling)
Viewed 0 times
fillingseedefficientflood
Problem
I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) connexity rules.
There are well-known solutions to this problem, such as recursion on the immediate neighbors, or the scanline approach. The former takes 4/8 tests of the neighbor color per pixel, and the latter takes a little less as when a straight run of pixels is processed, one backward test is saved per pixel. I have heard of an article possibly published in 2006, which is based on outline following, but have no reference for it.
(Whether the actual implementation uses the recursion stack or an allocated array is not relevant for this question. Nor is the "fixed-memory" requirement for which solutions have been proposed.)
My intuition tells me that better could be achieved by avoiding the repetition of some neighbor tests. In an extreme case, you can fill a square starting from the middle and spiraling until you reach the boundary with just one test per pixel, as you know that all pixels inside the spiral have been filled.
So my question: do you know of any theoretical study on the required number of neighbor tests per pixel for flood filling ? (The question can be rephrased in terms of graph theory as a connected component labeling problem.)
There are well-known solutions to this problem, such as recursion on the immediate neighbors, or the scanline approach. The former takes 4/8 tests of the neighbor color per pixel, and the latter takes a little less as when a straight run of pixels is processed, one backward test is saved per pixel. I have heard of an article possibly published in 2006, which is based on outline following, but have no reference for it.
(Whether the actual implementation uses the recursion stack or an allocated array is not relevant for this question. Nor is the "fixed-memory" requirement for which solutions have been proposed.)
My intuition tells me that better could be achieved by avoiding the repetition of some neighbor tests. In an extreme case, you can fill a square starting from the middle and spiraling until you reach the boundary with just one test per pixel, as you know that all pixels inside the spiral have been filled.
So my question: do you know of any theoretical study on the required number of neighbor tests per pixel for flood filling ? (The question can be rephrased in terms of graph theory as a connected component labeling problem.)
Solution
Following comments by @EvilJS which restarted a bibliographic search, here is relevant material that improves upon the initial algorithm by Alvy Ray Smith, which I called "scanline" in the OP.
It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin & Barsky is the most theory-oriented resource.
-
Computer Graphics And Geometric Modelling : Implementation & Algorithms
Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. See 2.4 Fill Algorithms.
-
Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
-
Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
-
Fishkin, Ken, “Filling a Region in a Frame Buffer,” in [Glas90], 278–284.
-
Heckbert, Paul S., “A Seed Fill Algorithm,” in [Glas90], 275–277.
-
[Glas90] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.
It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin & Barsky is the most theory-oriented resource.
-
Computer Graphics And Geometric Modelling : Implementation & Algorithms
Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. See 2.4 Fill Algorithms.
-
Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
-
Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
-
Fishkin, Ken, “Filling a Region in a Frame Buffer,” in [Glas90], 278–284.
-
Heckbert, Paul S., “A Seed Fill Algorithm,” in [Glas90], 275–277.
-
[Glas90] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.
Context
StackExchange Computer Science Q#33140, answer score: 3
Revisions (0)
No revisions yet.