"Close gap" in Fill tool

Develop Feature Requests
, ,
63

I’m very interested in this topic, both from the artist and programming perspective. I’m trying to rack my brain thinking of how this could even be done, and the only thing I can think of that doesn’t take forever is some way of converting raster linework into a vector representation before the fill tool is even used. Having that information would make both ‘fill to center of line’ and ‘close gap’ trivial with vector math.

Of course then it would need its own ‘lineart fill’ tool with its own ‘pre-processing’ step. And now we’re just back to the colorize mask.

64

@Ralek If you’ve ever used the Image trace feature in Illustrator, you’ll know that the conversion is way too messy to be considered useable, even on very high resolution images. It’s too far off from the pixel source.

Is there any open-source tool out there that has a fill-gap tool? Maybe that could serve as inspiration for the algorithm.

65

trace bitmap to vector? inkscape do have that feature.

66

Hi

@Deif_Lou you can be interested by this topic here

The github link is broken but it should be possible to take a look in mypaint code (maybe filtering jplloyd commits could help)

Grum999

67

I’ve used image trace probably thousands of times in AI by this point, joys of working in a sign store for several years. :stuck_out_tongue:

Yeah the output is terrible for anything other than 2-color rasters, but the use case of a ‘gap fill’ just so happens to be on lineart layers, which are usually 2-color rasters.

68

If we are looking for similar implementation in free software. GIMP has gap detection in its fill tool now - 3.4. Bucket Fill. You can take a look at the implementation detail from the dev blog here - https://girinstud.io/news/2019/02/smart-colorization-in-gimp/

Here is a small quick demo I did using GIMP on my system

70

I already have that bookmarked, hehe.
The code is kind of convoluted. A strange mix of c++ and python. It is similar to the cps one in that I think the gaps are detected as the filling is performed.

I also have that bookmarked, it is based on a paper by David Tschumperlé, creator of GMIC. This uses another approach. In summary, some feature points are detected in the image, like stroke ends, corners etc. then they are use to make some virtual lines/limits used to stop the filling (It is more complex actually, but just to understand it). You can see how it works in the gmic colorize filters:

Screenshot_20220819_141141
Screenshot_20220819_141141901×553 75.3 KB

The issues I see with this method are that it can lead to over-segmentation, which means that only a portion of the desired region is filled, as can be seen on the video. Also, as in the case of vectorizing, it requires to pre-process the image to make sure that you have a good line drawing to extract the features from. It is also a global method, it needs to pre-process all the layer beforehand, even if the resulting selected region is tiny.

73

Yes I agree it is a bit time consuming. The flood fill should fill all the area in one go.

74

Perhaps some simple secondary logic could be added w.r.t to the regions when the user fills one, like filling all bordering regions with an area of 1/5th or less than the region being filled (recursively), etc. Maybe some variation of that behavior would help, not sure all the side effects

75

The side-effects I can come up with from the top of my head are:

  • to know the area of a sub-region you have to perform potentially eppensive operations. That is added to the preprocessing of the image + feature extraction + dividing lines computation.
  • choosing an arbitrary number like 1/5 may result in the sub-regions that are gaps being filled and maybe even the regions beyond. Gaps are measure in px across, not area. You can set an 8px maximum gap and have a gap region that joins two 20x20px regions while being 1000x4px (which has bigger area).
76

I’m going to open again by highlighting that I’ve never even looked at Krita’s source code; but I have some thoughts. Most unapproachable-looking image processing algorithms take advantage of vector operations on the processor, which started with MMX back in the 90s. (You might remember the confusing ad with the engineers in neon-colored suits, working to “Play that Funky Music”?) What it allows for is performing loops that run multiple samples at the same time, as long as there aren’t any conditions that depend on previous iterations of the loop. (The vector operations usually result in a lot of vadds and pmovs in the generated assembly, if you want to check your work to be sure you didn’t interrupt it with something like an exit-loop-if-condition statement.) This can increase the speed by sixteen fold or more; never mind its close cousin, pushing the operation to graphics hardware.

Additionally, from my time screwing around with GIMP, I recall images were already somewhat pre-segmented into image tiles; perhaps I’m wrong, but if Krita uses a tiling technique, we may not need to worry about the entire image if only so many tiles are masked. It’s beautifully efficient when you’re dealing with extreme image sizes, and it really wouldn’t surprise me if Krita does the same thing.

The last thing to come to mind, which you may well be perfectly aware of (I’m not sure of your experience in DSP/Image Processing yet, I hope I’m not offending), is the use of the jump flood algorithm (not to be confused with the flood fill algorithm, which is more brute-force in my opinion). Its performance is pretty much constant-time, which makes it great for things like Voronoi diagrams and other processing-and-memory-intensive wizardry. It falls right in line with the vector operations stuff I was talking about, too, so it runs blazing fast.

I’m not sure if grow-selection and shrink-selection specifically use dilation and erosion, but you’re right, they certainly appear to. If the selection is feathered, it probably just uses grayscale dilation and erosion.

I’ll admit I’m not entirely sure what I’m looking at with your illustration, but could we solve the problem of unnecessary erosion with a selective OR mask of some kind, from the original image? Otherwise I feel like it would still save us artists a lot of time if we just had to enclose an area with our stylus a few more times, but didn’t need to worry about fill leaking.

77

  • Yeah I know vector instructions can accelerate the computations, but it’s not as straightforward. They are used to speed up different areas of krita, although I’ve never used them.

  • Krita’s internal images (paint devices) are tiled.

  • I encountered that jump flood algorithm a couple of times, but in the subject of distance transforms, if I remember correctly. I’ve never look at it in depth. If you know some floodfill like implementation that uses that algorithm please tell me. Krita uses the classic scanline fill, which is faster than the naive floodfill.

  • My experience in DSP/Image Processing is what I just taught myself by searching the internet. My background is not in computer science but in fine arts.

  • Grow and shrink selection use some dilation/erosion algorithms.

  • In my illustration you can see a mask (white), maybe the result of a floodfill, and its opening by a kernel that produces 2 disconnected regions (red). It shows that just by opening the result of the floodfill to disconnect the big regions by the gap size is not enough, since opening also removes features like corners that should be part of the final “sub-mask”.

  • I don’t know what you mean with “unnecesary erosion”.

  • Overall I have not found any paper or the like that just shows how to solve this problem of gap closing for a floodfill like tool in a straightforward way. I’ve found some that try to solve it by first analyzing the image to find features like stroke ends or corners and then connecting them to divide the region in smaller regions hopefully where the gaps are. They look promising and so on, but at the end they are computationally expensive, not generic enough, or have some other issues. Others try to use a morphological approach, like using opening, but there is no standard, accepted (at least public) method to solve our problem, apparently.

  • If you have interest on solving this, I encourage you to make a small app to test your ideas without having to deal with krita code. You then can try to make it work with krita’s floodfill, unless you can also implement a faster one.

78

If you have interest on solving this, I encourage you to make a small app to test your ideas without having to deal with krita code. You then can try to make it work with krita’s floodfill, unless you can also implement a faster one.

I think I’m going to be doing just that, as learning the structure of Krita—while something I should definitely get around to eventually—is kind of a new task in itself.

I don’t know what you mean with “unnecesary erosion”.

By “unnecessary erosion”, I meant the concern about removing minor textures in the image by using a topological close. “Eroding” away the “texture”, basically.

I did have a thought a moment ago. One of the primary things I’ve learned about sketching is that the first task is usually to break down an image into what I would call “primitives”, and many others might call basic shapes—circles, squares, spheres, cubes, and so forth, which make up the general flow of the image. I’m currently reading up on the SIFT (Scale Invariant Feature Transform) algorithm for image recognition, and it occurs to me that we could do the same thing in reverse…

Just take the final sketch, regardless of how it was implemented, and SIFT-match it against a selection of basic primitives, coloring in each one, until the region enclosed is manifested by the filled basic shapes.

We then wouldn’t have to worry about closing the sketch to fill it, as we would be filling rough components (our basic shapes) that fit the SIFT keypoint profile. If a head looks roughly like an ellipse, drop the ellipse in and fill it; then worry about every other match for so many iterations.

I have no idea how well it would work and am still implementing my own SIFT (or QSIFT) algorithm, but I think I may be onto something, as a machine-driven art style is kind of what we’re talking about here, and basic shapes are generally also closed shapes. Additionally, the patent ran out in March of 2020, so anyone can use it now.

I am perfectly aware of how nuts this sounds, using modern image-recognition algorithms to fill in a stroke; but hey, doesn’t everything at some point? I think it’s more fitting a a brush configuration option, in the end. There might be a few ways to solve this.

79

As a side note, optimizers will usually take care of that for you and automatically compile your code loops to vector operations, if you follow three simple rules:

  1. No “loop dependencies”—that is, each result should be calculatable without worrying about the result of any other part of the loop.
  2. Avoid branching into another function conditionally (in fact, avoid conditionals in general and use select-mask instead, if you can). This kind of jump is extremely difficult to vectorize, and sometimes you get a massive speed boost from calculating the result for everything, and then factoring it in based on a mask value.
  3. Watch for memory access that’s indirect, which is kind of an extension of part one. If you access a pointer dependent on an indexed value of an array or collection, you’re asking for trouble turning it into a vector op.

Basically write it like a GPU is going to do the heavy lifting, instead of a CPU. I’ve seen speed increases of around two thousand times, though that kind of comparison is very obviously hardware dependent! One hundred times faster is more typical.

AMD is now implementing AVX-512 instructions on their Ryzen 9s (after some debate with Intel about whether it is encroaching on GPU territory); which should make vectorized assembly even faster than before. We graphics programmers are being utterly spoiled.

80

This would be a very useful feature for flatting. The “close gap” setting also needs to have the option to choose a threshold, since the size of the gaps will vary, according to each artist’s art style.

81

krita fill test

I was also looking for a solution while colorizing some line art and created a small test app. Initially, I also thought of the GIMP/colorize mask approach that uses edge detection/watershed to segment the image after I found the link (https://girinstud.io/news/2019/02/smart-colorization-in-gimp/) that @raghukamath posted above.

But then I thought of another solution: 2D Raytracing. It uses Bresenham’s line algorithm for line art detection and the gap is detected by comparing and limiting the ray length of adjacent rays.

I wrote a small app in the same Framwork as Krita (Qt) and C++.

It can even fill multiple gaps but still needs a few optimizations for e.g. non-trivial-shapes.
image

82

Interesting approach.
My main questions at the moment are:

  • What happens if the gaps are not seen from the point you clicked on?
  • Would this approach work well with fuzzy lines, less flat graphics?
  • Is it scalable? How that performs when filling large areas?
83

Nice i think most of us be happy with this already :heart_eyes:

84

Looks promising!

Is it also possible to configure the gap size for the tool (e.g. to fill small gaps, but to leave larger ones open or to fill both smaller and larger gaps)?