Fill area with nearest colour from boundary

[jules43]

I have an area of an image which is empty (black or transparent). I would like to fill the area with the colour from the nearest point on the boundary. Effectively spreading the colours out from the border.

Is there a way to do this with image magic?


Thanks

[fmw42]

Please always provide your IM version and platform and an example image. You can post to some place such as dropbox.com and put the URL here.

[snibgo]

What version of IM, on what platform?

I would like to fill the area with the colour from the nearest point on the boundary.

Boundary of the image, or boundary of the area?

If boundary of the (transparent) area, my script shiftFill.bat does this, for IM v6. See my "Filling holes" page. If you don't use Windows BAT, you would need to translate it to your script language of choice.

[fmw42]

Can you provide an example input image? You can post to some place such as dropbox.com and put the URL here. Also please always provide your IM version and platform.

[jules43]

An example of an image I'd like to do the fill operation on can be found here: https://www.dropbox.com/s/9w1wbnvvqdk5g ... e.psd?dl=0

The result I want is that every black pixel in the image is replaced with a pixel taken from the closest point in the image that has a non-black colour. In reality I only need the ~30% nearest the border filled.

(It's worth noting that the image actually contains data)

I've taken a look at @snibgo's "filling holes" page, some of the results look really good, and it does seem that shiftFill.bat might do what I need, though as it works by shifting in four directions I fear it won't always choose the actual closed colour.

It's also possible the membrane fill could do what I need, I only have one hole, but the images on that page are no longer working.

However, I'm not sure if I'm up to setting up CYGWIN and building the C code, in order to use them.

I should be able to replace my black pixels with transparent ones by using -fill #00000000 -opaque #000.

[snibgo]

Ah, yes, sorry, shiftBlur finds the closest only in a vertical or horizontal direction. I think the general scheme could be adapted to find the closest in any direction.

That's what I get, reduced for the web. Sorry, the full-size version is 10 MB, which is too large for me to upload.

My process modules fillholes and fillholespri won't do what you want.

[snibgo]

Re-stating the problem:

- Fill all transparent pixels by setting each to the colour of its nearest opaque pixel.

- Assume we have no partial-transparency.

- Assume that where a transparent pixel has a number of nearest opaque pixels at the same distance, we don't care which one is used.

I've thought about this problem, and can't see a simple command-line solution. The simplest/quickest method seems to be brute-force:

For each transparent pixel, loop through all the opaque pixels to find the nearest. This will be slow. Improvement: when we know the nearest distance for one transparent pixel, the nearest distance for its neighbour won't be much greater.

Coding this as a process module, it would be reasonably fast, but not great. Does anyone have any better ideas?

[fmw42]

The closest I can come in a simple command is as follows:

line1: read the input
line2: create copy of original and make black transparent
line3: create copy of original and convert to binary white/black and get edge on the white side of transition
line4: composite the previous edge image with the original to convert the edges to color
line5: scale the color edge image to one column to get the average opaque colors (exclude tranparent),
the scale back up to full image size and compose the transparent image (from step 2) over it.

That fills the black area with the average color of the left and right side of the black area.

Code: Select all

convert FillHoleImage.psd[0] \
\( -clone 0 -transparent black \) \
\( -clone 0 -fill white +opaque black -morphology edgein diamond:1 \) \
\( -clone 0 -clone 2 -compose multiply -composite -transparent black \) \
\( -clone 3 -scale 1x! -alpha off -scale 3840x1920! -clone 1 -compose over -composite \) \
-delete 0-3 result1.png

[fmw42]

Here is an alternate that interpolates the two single column colors, but takes about 3-4 min to run due to the use of -fx.

Code: Select all

black_center_x=2500
wm1=`convert -ping FillHoleImage.psd[0] -format "%[fx:w-1]" info:`
center_x=`convert -ping FillHoleImage.psd[0] -format "%[fx:round(w/2)]" info:`
rollx=$((center_x-black_center_x))
time convert FillHoleImage.psd[0] \
\( -clone 0 -transparent black \) \
\( -clone 0 -fill white +opaque black -morphology edgein diamond:1 \) \
\( -clone 0 -clone 2 -compose multiply -composite -transparent black \) \
\( -clone 3 -roll $rollx -crop 50x100% -scale 1x! -alpha off \
-size 3840x1920 xc: -reverse -monitor -fx "xx=i/$wm1; u[1].p{0,j}*xx + u[2].p{0,j}*(1-xx)" +monitor \
-clone 1 -compose over -composite \) \
-delete 0-3 result2.png

I could be even better by interpolating over a width equal to the width of the black area and inserting that in the right place.

Or better, to write a proper IM MagickFilter to interpolate across lines between the two sides of the color edges.

[anthony]

An alternative method may be the use of sparse color as a fill operator.

http://www.imagemagick.org/Usage/canas/#sparse_fill

You would apply it using the 'Voronoi' technqiue.

basically you use edgein to get the edge pixels then convert that into a the points to use for -sparse color.
And overlay the original image on the result.

Code: Select all

convert FillHoleImage.psd[0] -transparent black -channel A -morphology EdgeIn Diamond hole_shape.png

convert hole_shape.png txt:- |
   sed '1d; / 0) /d; s/:.* /,/;' | \
     convert hole_shape.png -alpha off \
                -sparse-color Voronoi '@-'  hole_filled_voronoi.png

convert hole_filled_voronoi.png FillHoleImage.psd[0] -composite hole_filled.png

Yes it is slow but then it is doing a lot of calculations, But each transparent pixel will be filled with EXACTLY the closest color.
It may be able to speed up by using a write mask. so that only the required transparent pixels will be calculated.

[fmw42]

I think there may be a typo with a line continuation at the end of the first line missing.

This

Code: Select all

convert hole_shape.png txt:- |
   sed '1d; / 0) /d; s/:.* /,/;' | \
     convert hole_shape.png -alpha off \
                -sparse-color Voronoi '@-'  hole_filled_voronoi.png

perhaps should be

Code: Select all

convert hole_shape.png txt:- | \
   sed '1d; / 0) /d; s/:.* /,/;' | \
     convert hole_shape.png -alpha off \
                -sparse-color Voronoi '@-'  hole_filled_voronoi.png

The following is a faster alternative using sparse-color: in place of txt:

Code: Select all

convert FillHoleImage.psd[0] -transparent black +write hole_transparent.png -channel A -morphology EdgeIn Diamond hole_shape.png
convert hole_shape.png sparse-color:- |\
convert hole_shape.png \
-monitor -sparse-color Voronoi '@-' +monitor -alpha off  hole_filled_voronoi.png
convert hole_filled_voronoi.png hole_transparent.png -compose over -composite hole_result_voronoi.png

However, the result I get is very similar to snibgo's and not close to mine above.

[snibgo]

Brilliant, thanks. Anthony's code gives the expected result for a test case:

Output:

[snibgo]

A more compact implementation, that fills transparent pixels in %INFILE%. Windows BAT syntax:

Code: Select all

convert ^
  %INFILE% ^
  ( +clone ^
    -channel A -morphology EdgeIn Diamond +channel ^
    +write sparse-color:%TMP_DIR%\vf.txt ^
    -sparse-color Voronoi "@%TMP_DIR%\vf.txt" -alpha off ^
  ) ^
  -compose DstOver -composite ^
  %OUTFILE%

[anthony]

Nice example snibgo. The main problem with the technique is that is it Ultra Slow!

I would like to use a morphology operator that sets color in the color
channels while working out distance in a hidden background channel to replace the pixel color when a 'shorter' distance is found. This should be VERY fast.

Actually a Voronoi fill, is the starting point that is used in a Color Diffusion (blured, like a shepards fill, but without 'leaks' from disjoint edges). There is a paper all about painting vector images where this is at its heart Diffusion Curves http://artis.imag.fr/Publications/2008/OBWBTS08/

I have updated the IM examples area on Hole Filling with raw indexes of various techniques though give it time to appear.
http://www.imagemagick.org/Usage/masking/#hole_filling


ASIDE: Fred... The final slash on the first and second (which had one anyway) lines is NOT needed for bash, though it does not hurt.
The pipeline '|' tells bash that the command is not yet finished.
However I do need those extra end-of-line backslashes in IM Example, example code, as code executor uses it to know that it is a multi-line command. So IM examples code needs it, even though BASH does really care.
Basically my code was correct!

Actually I forgot that Cristy added the "sparse-color:-" output format for me when this technique first came out!

[snibgo]

That "diffusion_curves" paper is interesting. It is closely related to the work I've been doing with cartoons, and gives me ideas for extensions. Performance aside, it can be implemented in IM. For example, from that paper:

Using my blurFill.bat on that "diffusion curves" image:

(Both images reduced in size for the web.)

@jules43: Sorry, I'm drifting your thread. Have we solved your problem?