4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Are you talking about this article, where edge detection, "snake list" - which is going by contour, is used? $\endgroup$ – Evil Mar 25 '16 at 0:09
  • $\begingroup$ Do you know Smith flood fill? There was article about making full boundary, creating something like Active Edges Table, but I discarded it, number of test was ultra low, but runtime... Not so good. $\endgroup$ – Evil Mar 25 '16 at 0:17
  • $\begingroup$ @EvilJS: I have added an answer. Thanks. $\endgroup$ – Yves Daoust Mar 25 '16 at 7:59
  • $\begingroup$ @EvilJS: No, I was'nt thinking of edge detection but of a flood filling process that first performs outline following then run filling (if that is possible). Thanks for your input. I have added an answer. $\endgroup$ – Yves Daoust Mar 25 '16 at 8:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @EvilJS: this is true only for shapes guaranteed to have no hole. Otherwise, you must scan the entire surface. $\endgroup$ – Yves Daoust Mar 25 '16 at 18:27
  • $\begingroup$ @EvilJS: I don't belive it. Unless you scan the whole surface, you can't tell where the holes are. $\endgroup$ – Yves Daoust Mar 25 '16 at 19:20

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.