Line Art Bucket Fill

The “Fill by line art detection” option in the Bucket Fill tool is adapted from an algorithm named “A Fast and Efficient Semi-guided Algorithm for Flat Coloring Line-arts” by Sébastian Fourey, David Tschumperlé and David Revoy.

I (Jehan) implemented it as a new option in the “Bucket fill tool”, as a job for the CNRS research center, under direction of David Tschumperlé and Sébastian Fourey.

Aryeom was the principal artist advisor for all the changes and improvements we made to the algorithm, but also to improve user experience and graphical interface.

This page is not going to re-explain the algorithm in details, but instead will try to simplify the algorithm flow, break it into clear steps and explain changes we did for our implementation.

Algorithm intent

This is not a generic bucket fill algorithm, in that it won’t work with any random image. It is really dedicated to “line art” drawing, or any image which can be usefully pre-processed into a line art looking image. Hence the name of the feature.

In particular, chances are that running it on a photography won’t give you very useful results.

The advantages of this algorithm for such line art images are in particular:

• Unlike other bucket fill algorithms which usually rely on color proximity, by detecting what “lines” are, we detect the borders of fill zones, and that makes it easier to “flood” the fill color or a pattern under the lines. This prevents the very common issue of thin ugly unfilled pixels near line borders (because of antialiased pixels for instance) which makes other bucket fill algorithms unusable in practice for many simple-looking cases.
• Line art zones are not always perfectly closed. In some occasions, it is just some imperfect lines due to the nature of drawing. In other cases, it is even on purpose, as a line art style, where you don’t want to close your strokes even though they might represent closed areas. The algorithm is meant to try and detect when such unclosed areas should have been.

3-steps algorithm

There are basically 3 steps performed during a line art bucket fill:

1. Detect what is line art.
2. “Guess” where lines are supposed to be closed and try to create closures.
3. Fill the enclosed area and flood under the line art.

Step 1: line art detection

The first step is a very basic conversion of the image into a single channel, using a threshold to decide whether a pixel is part of a line or not.

This channel can either be based on luminosity (light means background), i.e. grayscaling the image, or just using the alpha channel (if “Detect opacity rather than grayscale” is checked and there is an alpha channel).

In the end, we get a binarized version of the images with some pixels belonging to strokes, and others not. This step is fast and easy.

Step 2: line art closure

The second step is the most important part of the algorithm, and the best is to look at the research paper linked earlier. Basically from the binarized image, we are trying to characterize key points, which are supposed to be “extremities” of strokes. This is done by computing local normals and curvatures at each stroke point.

Once we have keypoints, the algorithm proposes closures based on keypoints proximity. The closure can take the form of splines (curved closure) or segments (straight lines). The original algorithm has 2 variables to determine whether we consider a closure of any type (spline_max_length and segment_max_length). This is implemented in GIMP core code, but not shown in the GUI as the Bucket Fill tool options only displays a single “Maximum gap length” which is used for both variables. This was chosen for simplification of usage.

Improvement over the research paper

A first improvement in our implementation, unlike the research paper, is that the original algorithm (as published) was not working fine on fat strokes because it was using a global median stroke thickness. It even ended up opening holes in line art in some cases. To work whatever the stroke size, we needed to compute a local radius estimate for every stroke border point. It is more accurate and less processing intensive.

The commit implementing this change has more details on the change, information on what alternatives were evoked and the actual implementation.

Usage warning

Note that this algorithm will work better with smooth strokes. When drawing lines using a brush with obvious “texture”, such as the “Acrylic” collection of brushes in default GIMP brush set, the rough characteristic of the lines end up creating more keypoints than it should (i.e. not only in extremities, yet also in middle of strokes). It may make this step slower and create too many closed zones. No absolute solution for this issue has been found.

Step 3: filling closed area and flooding (line art) borders

The actual bucket fill step is different in the research paper and our implementation.

The original authors envisioned a “all area at once” workflow where an artist give all colors for the whole image, using color spots, and let the algorithm choose the zones to fill. Instead we stay on a workflow assuming you want to work on a specific zone only with a single color. Originally we were using the "gegl:watershed-transform" GEGL operation.

Eventually we moved to a simpler and much faster algorithm based on a distance map and a local thickness map, in order to flood at most half of the stroke (depending on local radius at each point). This made the border flooding very efficient.

This is another major difference from the originally proposed algorithm in the research paper.

GUI enhancements

Line art pre-computation

The line art computation can take some time, in particular for big and complex images. This is not really the first step, but especially the second step (characterizing key points and closing) which can be the most expensive.

As a consequence, we made these 2 steps work in a thread. As soon as the tool is selected or as soon as the source image is modified, computation starts (not when you click on canvas with the tool). Since a few microseconds may pass between several clicks, it allows a sensation of instantness as all the harder processing happened in this in-between time.

Holding the pointer while filling

A second GUI enhancement is that as long as you don’t release your pointer, the line art and closure are not recomputed and simply reused, allowing you to “refine” your fill. It makes it faster, and also allows you to cancel a fill by right-clicking (third button) when releasing.

Line art source

We also added a concept of line art “source”. Typically the source for the line art can be the selected layer itself, but also the whole image (“Sample merged” equivalent) or the layer above or below, depending on whether you want to fill using the source transparency (common use case for fully digitally-drawn pictures) or often with “Multiply” mode too (common use case for colorizing cleaned-up scans).

This is not only useful to cater to various workflows but also because any source where the filled image is not a part of (i.e. when the source is “Layer above the selected one” or “Layer below the selected one”) will be lightning fast as the line art and closure will never have to be recomputed.

Disabling second step

Another UX improvement was the ability to disable the second step of the algorithm (line art closure) by unchecking the “Automatic closure” option.

The base idea is that:

1. In some conditions, as explained above, too many key points are created and closures become an annoyance more than anything else.
2. For many drawing styles, unclosed line arts are not expected (or should be fixed).

Therefore it made sense to allow disabling the closure creation algorithm as this is the costlier (in processing time). Note that setting “Maximum gap length” to 0 is equivalent, but having a checkbox was a lot simpler and better experience (you don’t lose your ideal gap length setting, in case you need to regularly switch from one fill style to another).

Using target merged to source (manual closure)

Also there exist methods to create closures manually, which are used by advanced artists, such as Aryeom, who often teach it to university students.

The base idea is that other fill or selection algorithm per color proximity are “leaking” through line art holes. Yet sometimes you just don’t want to close the hole because it’s on purpose, as an unfinished stroke style. How do you close without closing?

In this case, what you can do is to close the hole… with your fill color and style (on the fill layer, not the line art layer). Then color distance computed in sample merged mode will close the line art. Of course, there is still the problem of the thin unfilled zone near stroke borders. This is why colorists would use the “Fuzzy Select” tool instead, then grow the selection and finally fill it.

Here is what Aryeom would do (note that she had scripts to do it in much fewer steps, but this is what the low-level steps are actually doing):

1. Line art is top (or bottom) layer, and color is bottom (resp. top) layer. A closed area is represented but the line style doesn’t actually close the area. Let’s say the line color is black while fill color is blue.
2. Select the color layer, and close the unclosed area with the fill color (blue) and a paint tool.
3. Switch to the “Fuzzy select” tool, in “Sample merged” and “Select by Composite”. Click inside the area (which is now closed since we are in sample merged mode so both the line and color layers are taken into account).
4. Grow the selection by a few pixel (Select > Grow in menus) as needed, depending on the approximate line size. This will simulate our flooding step.
5. Switch to “Bucket fill” tool in “Fill whole selection” and fill with fill color (blue).

This whole procedure can be reproduced now with the Bucket fill tool in “Fill by line art detection”, unchecking “Automatic closure” and checking “Manual closure in fill layer” instead.

It will then merge a binarized version of the fill layer to the line layer, the same way as it’s done in the first step. The only difference is that no closure are computed from the fill layer, so it stays fast even though this part has to be re-computed after each change.