halo minimization by local min/max smooth clamping

[NicolasRobidoux]

Sharpening (using most methods, including USM) and resampling with filters that have negative lobes produces halos.

I am wondering if the following would work well to minimize halos when using such operations.

I'll use image enlargement as an example.

Take your original image.

From this image, compute two versions of the original: One has, at every pixel, the min (over each channel) of the nearest nine pixels.

The other is similar except that we take the max.

Now, resize the original with whatever filter you want, negative lobes and all, and also resize the the "min" and "max" pseudo-images with an INTERPOLATORY MONOTONE method (Hermite or bilinear (triangle), say; I wish I had programmed Locally Bounded Bicubic for IM, but I haven't).

One colour channel at a time, clamp the pixel value of the enlarged image by the min/max values at the same location (possibly with some "fudge factor").

-----

Have you ever heard of such an approach? Comments/ideas? (I'm guessing this is trivial to program in IM.)

[magick]

Can you provide a name for the algorithm you're discussing? We could code it for you for testing. What would be the option name? Perhaps -bounded-resize?

[NicolasRobidoux]

How about -clamp-locally?

It is quite descriptive, and if it ends up working when sharpening without resampling, the same name will work.

(My new motto: -think-globally, -clamp-locally.)

Warning: If downsampling, taking min/max over 3x3 patches will not work. Things will have to be done more carefully.

[NicolasRobidoux]

Note that I hope that (with min/max taken over suitable areas) this will work well with downsampling as well.

It would appear to me that the halos force the JPEG quantization step to waste some of its bits on negative lobe overshoot/undershoot values.

In addition, JPEG itself creates ringing-like artifacts.

So, I'm hoping that -clamp-locally will lead to better JPEG compressed thumbnails.

The tricky balance: Make sure that the clamping "surfaces" are smooth enough, and permissive enough (through the use of "wide" min/max ellipses/rectangles; above, I suggested 3x3 when upsampling), not to introduce aliasing (staircasing and ridging, in particular; they should not affect moire much). On the other hand, they should be restrictive enough to have an impact on ringing.

What I'm trying to reproduce for natural images is the well-known fact that haloing won't hurt you as much if you have a black and white (not greyscale: binary) image, because over/undershoots are clamped to white/black anyway.

[NicolasRobidoux]

I forgot the most important thing: Thank you for having a look.

[NicolasRobidoux]

When I have a bit more time, I'll try to figure out a good general way of computing the min/max to clamp with at each output pixel. In a nutshell, this is the key issue.

[NicolasRobidoux]

When upsampling, I'm not sure anymore that this will be so hot without using a sophisticated nonlinear scheme to create the clamping "surfaces" from the min/max values. (Using triangle or Hermite to interpolate the pointwise min/max will probably give artifacts.)

When downsampling, it's probably going to be OK provided the min/max are taken over rectangles corresponding to the use of a filter with window > 1 when using resize/ellipses corresponding to the use of a filter with window > sqrt(2) when using distort. (Using 2 in both cases is probably fine.)

I suspect that this is not going to do too well when dealing with noisy images.

[magick]

Is -clamp-locally restricted to image resizing? Or will it apply the sharpening, blurring, etc.?

For each algorithm it supports, we'll need a short description on how the option should behave. Let's assume resizing. We create three images. First a MIN image and then a MAX. Next we resize the original image followed by resizing the MIN and MAX images with say integer interpolation. We can now clamp the resized image as bounded by MIN and MAX. Is that correct?

If -clamp-locally applies to other options (e.g. -sharpen), we'll need a description of how to properly clamp.

[NicolasRobidoux]

Is -clamp-locally restricted to image resizing? Or will it apply the sharpening, blurring, etc.?

Let's leave sharpening out of it, at least for now. I'm not sure I can make it do something really useful.

-clamp-locally should work with any resampling operation. However, it will only be useful with non-monotone resampling methods (filters with negative lobes, for example). If a monotone method has a window wider than 1 (quadratic, cubic, Gaussian blur), -clamp-locally, as described below, will "tighten" the blur in a way which I guess will not be that useful.

For each algorithm it supports, we'll need a short description on how the option should behave. Let's assume resizing. We create three images. First a MIN image and then a MAX. Next we resize the original image followed by resizing the MIN and MAX images with say integer interpolation. We can now clamp the resized image as bounded by MIN and MAX. Is that correct?

If -clamp-locally applies to other options (e.g. -sharpen), we'll need a description of how to properly clamp.

Let me start with the simplest case: Enlarging an image. (I'll get back to other orthogonal transformations, and distort, when I have thought things through more carefully.)

Your description is then dead on.

Step 1) Take min/max over small areas (3x3 squares makes a lot of sense) in the original image to get an additional two images of the same size as the original: a "min" one, and a "max" one.

Step 2) Use a monotone interpolatory filter to enlarge the result to the same size as the final result. In IM, there are basically three monotone interpolatory filters: nearest (will be awful), triangle (will be OK, but the clamping will sometime introduce weak bilinear artifacts) and hermite; let's say triangle for a start. Now, we have three images of the final size: the enlarged original, the enlarged "min" image, and the enlarged "max" image.

Step 3) Clamp each color channel of the enlarged image using the enlarged min and max images, pixel by pixel.

Let me give an example of what it will do with an image with one light gray column in the middle of a dark gray image, enlarged a lot with resize lanczos.

Unclamped, the result will be the lanczos 3 kernel. So, there will be a dark ring between x=-2 and -1, and x=1 and 2 (distances measured in the original image), and a light halo between -3 and -2, and 2 and 3.

Clamped-locally, the result will be the lanczos 3 kernel within a distance of 1 of the center of the light column, the lanczos 3 kernel tailed off quickly as if with a triangle window between a distance of 2 and 3, and will be flat dark gray outside of (-2,2). That is, the first (dark) halo will be minimized, and the second (light) halo will be completely suppressed. (If you would like to leave the first halo alone but minimize the second, bounce back, halo, use a 5x5 instead of a 3x3. This, of course, is kind of pointless with, say, Lanczos2 or Catmull-Rom/Keys; but it could be useful with the default Lanczos, namely Lanczos 3.)

Now, clamped-locally is a nonlinear method. Generally, all lobes of the lanczos 3 kernel will contribute. But not, at least not as much, when they lead to (major) overshoot and undershoot.

-----------------

If you are reducing, or distorting, things are more complicated. Step 3 is the same, but the computation of the min/max image aligned with the reduced/distorted image will be more costly/complicated. I actually have not fully figured it out. What we want is something more or less like this (when reducing): At each output pixel location (of the final image), take the min/max over the interior of a rectangle of width 3/r, where r is the downsampling ratio in the horizontal direction (hence <=1) and height 3/s, where s is the downsampling ratio in the vertical direction. The number "3" is not magical: At this point, anything between 2 and 4 should work reasonably well.

(You may want to wait until the dust in my head has settled to work on this.)

[fmw42]

If I understand correctly, this will do it. But I see no change from simply resizing. Correct me if there is something wrong in my approach.

# first line: read image
# second line: resize original with bilinear
# third line: take 3x3 local min at each pixel and then resize 200% using bilinear
# fourth line: take 3x3 local max at each pixel and then resize 200% using bilinear
# fifth line: keep the brighter of the resized original and min images
# sixth line: keep the darker of the previous result and the max images
# seventh line delete temps and create output

filt="triangle"
convert lena.png \
\( -clone 0 -filter $filt -resize 200% \) \
\( -clone 0 -statistic minimum 3x3 -filter $filt -resize 200% \) \
\( -clone 0 -statistic maximum 3x3 -filter $filt -resize 200% \) \
\( -clone 1 -clone 2 -compose lighten -composite \
-clone 3 -compose darken -composite \) \
-delete 0-3 lena_${filt}_200_clamplocal.png

# simple resize
convert lena.png -filter $filt -resize 200% lena_${filt}_200.png

# compare results
compare -metric rmse lena_${filt}_200.png lena_${filt}_200_clamplocal.png null:
0 (0)

Same result when using filt="hermite"

[NicolasRobidoux]

Not quite:

# first line: read image
# second line: resize original with whatever scheme you want (lanczos, say; if you want a drastic change, use lagrange with a large degree) by X% (X>100)
# third line: take 3x3 local min at each pixel of the original image and then resize X% using bilinear (or maybe hermite)
# fourth line: take 3x3 local max at each pixel of the original image and then resize X% using bilinear (or maybe hermite)
# fifth line: keep the brighter of the resized original and min images
# sixth line: keep the darker of the previous result and the max images
# seventh line delete temps and create output
...

What you do is you enlarge with your favorite "negative lobe" filter, and then you limit the ringing damage with the min and max images (which are created with an interpolatory monotone scheme, not your favorite).

If you want a milder effect, use a 5x5 instead of a 3x3, or a disk (5x5 minus the four corners, for example). If you want a stronger effect, use a small cross (3x3 minus the four corners); this probably will be a disaster.

I'm guessing that 3x3 or 5x5 minus the four corners is as good as it gets.

As mentioned above, -clamped-locally will also have an effect on, say, quadratic, cubic or gaussian, even though they don't have a negative lobe.

(Gotta get back to grading/teaching prep. I'll read, but won't respond.)

[fmw42]

OK. Corrected:




filt="triangle"
convert lena.png \
\( -clone 0 -filter lanczos -resize 200% \) \
\( -clone 0 -statistic minimum 3x3 -filter $filt -resize 200% \) \
\( -clone 0 -statistic maximum 3x3 -filter $filt -resize 200% \) \
\( -clone 1 -clone 2 -compose lighten -composite \
-clone 3 -compose darken -composite \) \
-delete 0-3 lena_${filt}_200_clamplocal.png



convert lena.png -filter lanczos -resize 200% lena_lanczos_200.png



compare -metric rmse lena_${filt}_200.png lena_${filt}_200_clamplocal.png null:
105.592 (0.00161123)




filt="hermite"
convert lena.png \
\( -clone 0 -filter lanczos -resize 200% \) \
\( -clone 0 -statistic minimum 3x3 -filter $filt -resize 200% \) \
\( -clone 0 -statistic maximum 3x3 -filter $filt -resize 200% \) \
\( -clone 1 -clone 2 -compose lighten -composite \
-clone 3 -compose darken -composite \) \
-delete 0-3 lena_${filt}_200_clamplocal.png



convert lena.png -filter lanczos -resize 200% lena_lanczos_200.png



compare -metric rmse lena_${filt}_200.png lena_${filt}_200_clamplocal.png null:
107.502 (0.00164038)

I cannot see any significant visual difference when flickering the pairs.

[NicolasRobidoux]

Thank you Fred.

...I cannot see any significant visual difference when flickering the pairs.

It could be because lena is a somewhat soft focus image which is not particularly high contrast. Lanczos ringing certainly does not jump at you here: there is not much to suppress.

In a sense, it is reassuring, B/C when Lanczos works well, clamp-locally does not break anything.

(It could also be because my idea is not so good.)

[fmw42]

...I cannot see any significant visual difference when flickering the pairs.

It could be because lena is a soft focus image. Lanczos ringing certainly does not jump at you here: there is not much to suppress.

(It could also be because my idea is not so good.)

Can you suggest a different image? I can test with that. Would zelda be better? Or some cartoon-like image?

[NicolasRobidoux]

Can you suggest a different image? I can test with that. Would zelda be better? Or some cartoon-like image?

Suggestion: Crop http://www.pbase.com/konascott/image/69543104/original so you overlap the chimney, the roof and the sky. Maybe take another crop where you get the horizontal wooden slats and the window.

(Cartoon is not so good if the background is white. You don't see overshoots. If you can find a cartoon on a grey background, then fine.)

Another suggestion: The IM rose. It gives pretty dreadful haloing when enlarged enough.