Floodfill - seeking input on morphology and blur bounding box behaviour

Hello, I am in the process of refactoring and cleaning up some code that adds the following features to the fill tool:

Dilation/Erosion (Grow/Shrink) - uses Urbach-Wilkinson’s algorithm, linear’ish complexity (w.r.t structuring element radius) and handles alphas.

Feathering - applies fake gaussian blur to the fill using the old repeated box-blur trick

Gap closing - right now, it is just dilating the source tiles w.r.t the target color prior to filling, and dilating the fill an equal amount afterwards, but I’m working on an approach that detects rapid changes in minimal radius during the fill stage (hence my refactoring effort; some new preprocessing required).

I have also added some features that are not as interesting, such as filling to the layer below the active and ignoring the background layer when filling using “sample merged”.

My question is about the role of the bounding box for dilation and blur. Right now, I have elected to ignore it after the fill is done, creating new tiles as needed and dilating/blurring outside of the bbox. I think this is the desired behaviour in the general case, BUT perhaps not when a frame is active. Any thoughts on this?


@dothiko this would be your area since you were looking into improving the floodfill tool as well.

1 Like

@odysseywestra Thanks, I don’t know about Urbach-Wilkinson’s algorithm, but very interesting! :blush:
I think fast morphology would also be useful/helpful for ‘close-fill’.

Hello,@jpll, I think flood-fill itself is limited by a frame, so morphology/blurring should also be limited by it. :smiley:

I’m inclined to agree about that and assume that it’s not difficult to find out whether the frame is set or not. The change to the algorithm is trivial of course (might have some slight performance impact, but probably not noticeable for most cases).

The UW-algorithm uses dynamic programming (memoization) to efficiently reuse the result for individual chords in the structuring element. By rotating the lookup table storing these results, we ideally only have to perform a single update operation per tile row (by first sorting the tiles appropriately and reusing the lookup table across tiles).

Since we only get the performance benefit when operating on tile columns, the columns could be processed concurrently, but I don’t know if that is feasible from python (or worth the additional complexity).

1 Like