A Stackless Floodfill Automaton

In a sense it uses half a byte per pixel, but Nils M Holm's suggested implementation is to reserve 16 colors for the flood-fill algorithm, because you don't need to remember the color of the pixels you're flood-filling, so you can overwrite them with the flood-fill algorithm's state. The path is saved in those same 16 colors. This reduces your available color space, assuming 8-bit color, from 256 colors to 240 colors, which means you get 7.91-bit color instead of 8-bit color. So it actually only uses 0.09 bits per pixel, which at 1024×768 is 9154 bytes.

If you were to instead use a bounded area of the heap with 4 bits per pixel, as you are suggesting, your bound would be 393216 bytes.

However, it's not totally clear that that's the right way to account for it, because if you have a 256-color image that you have to reduce to 240 colors to have space for this algorithm, there isn't an obvious way to get back the lost colors by storing 9154 bytes somewhere else. You might be able to do something like pick the least popular 16 colors from the image (which occupy a maximum of 49152 pixels and usually less), store a bitmap telling where they were (98304 bytes), store the colors of the marked pixels into a 24576-byte array, replace them with some neutral color, run the flood fill, and then restore the colors. But, while that uses significantly less than 393216 bytes, it still uses a lot more than 9154 bytes, and it's probably pretty slow on the kind of computer where you'd be trying to do something like this.

At the other extreme, if your 256-color image actually only used the 216 "web-safe" colors (#000, #003, #006, ... #030, #033, etc.), you'd already have 16 leftover colors available. And freeing up 16 colors on a 16-bit or 24-bit TrueColor display would damage the image quality only imperceptibly.

The pixels are effectively being turned into a linked list using the special values as ‘pointers’. This list is used as a stack, and the current position is the stack pointer.

I don’t think they explain the backtracking part very well, and they should have used an example that fills a non-rectangular area so it actually demonstrates the whole algorithm.

It’s a neat trick if you have spare values to use as markers, though. :)

Why were you needing floodfill?

It backtracks using the origin direction. As it traces back to the original starting pixel, before filling the current pixel it attempts to scan the remaining directions for each pixel (which may be none). If those lead to further pixels needing to be filled it'll start going forward again, and eventually hit a dead end and trace back to the branch point and continue to scan around it, eventually discovering is itself a dead end and go to its own predecessor.

Basically, a pixel will go through states like:

  (U,R) ;; came from up, went right
  (U,D) ;; came from up, went down
  (U,L) ;; came from up, went left
  (U,U) ;; came from up, went up

Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.

> What's the utility of this?

Constant memory usage. It uses a small amount of additional memory (tracking the current pixel, pixel value, and a couple temp variables used for calculations) over the image itself making it a very low overhead algorithm. You can basically get away with 5 more variables, 20 more bytes if they're all 4-byte values, using this approach compared to the much greater memory needs of a stack-based approach (either a stack data structure or recursive). And actually just 4 variables since the D and P variables don't overlap in lifetime.

EDIT: Light editing of the above for grammar and clarity.

Runtime of union find is slightly worse than O(N). https://www2.eecs.berkeley.edu/Pubs/TechRpts/1974/28764.html

This document is from 2023, so maybe.