The algorithm uses about half a byte per pixel and saves the path it follows. That kind of implies that the stack is still there and present, it’s just bounded to the number of pixels, and could actually be modified to just use a bounded area of the heap. But conceptually it’s easier to follow the way the paper was written. Neat.
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. :)
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.
I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.
How does this deal with one pixel gaps? The algorithm can enter it just fine but there's no space to go back out again, and there doesn't seem to be a system for backtracking, unless I've misunderstood the algorithm
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 (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 repeat with any remaining directions.
Another option if you find yourself with this problem (flood fill, no recursion) is union find/connected components. Like the algorithm proposed in the article, you still need to store O(N) things, and runtime is still O(N).
What's the utility of this? It's arguably still using a stack, just encoded in the original data structure itself. If your original data structure somehow uses colors but is also fine with the algorithm overwriting with its own colors, I guess it works? But those are very unusual preconditions. For any real world scenario I can imagine, I feel like there's a better solution.
If the colors in your original data are important, then you can't really just overwrite them and/or assume that the algorithm can use its own colors. You're going to have to add a stack.
If your original data doesn't have colors, adding a stack is better than integrating metadata into the original data structure.
If for some reason your original data has colors but they aren't considered important, then just remove the colors and add a stack.
If your concern is about dynamic memory, preallocate static memory equal to the size of the original data structure.
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. Depending on the resolution of the image, you can basically get away with 5 more variables, 20 more bytes if they're all 4-byte values, using this approach than 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.
But that's only assuming that your original data structure already has space for the algorithm to store metadata. If there's space that can be manipulated freely to store metadata, can't you just remove that space to save memory, and then use the extra space for a stack?
17 comments
[ 1.3 ms ] story [ 2.2 ms ] threadI'll be converting my code to the stackless version toot sweet.
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. :)
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.
If the colors in your original data are important, then you can't really just overwrite them and/or assume that the algorithm can use its own colors. You're going to have to add a stack.
If your original data doesn't have colors, adding a stack is better than integrating metadata into the original data structure.
If for some reason your original data has colors but they aren't considered important, then just remove the colors and add a stack.
If your concern is about dynamic memory, preallocate static memory equal to the size of the original data structure.
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. Depending on the resolution of the image, you can basically get away with 5 more variables, 20 more bytes if they're all 4-byte values, using this approach than 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.