[SOLVED] nearest neighbour downsize w/ averaged ties

[NicolasRobidoux]

If you look at the first and last figures shown at http://www.imagemagick.org/Usage/resize/#point, you'll notice that when downsizing, with -filter Point (nearest neighbour), an even sized image (10x10, in this example) by an even factor of 10 (5x5 and note that 10/5 is even), you break the alignment of the image: The uniformly black result suggests that "ties" (every sampled location in the resulting 5x5 corresponds to the midpoint of a 2x2 B/W checkerboard) was resolved the same way throughout.

Of course, it your goal in using Point is to not increase the number of colours of the image, this the desirable behavior. (Well, maybe you'd want the tie to be randomly resolved? Probably not.) So, I am not advocating a change in what IM does. I'm just trying to get what I need.

If you want to preserve the (local) alignment of the smaller image w.r.t. the larger one (as much as possible), this is not the desirable behavior. You'd rather have ties resolved by averaging. Of course, this will add new colours. (In the case of the above example, it will add grey to black and white.)

Here is, I believe, a fix. P.S. NOT!

Instead of

Code: Select all

convert INPUT.WHATEVER -filter Point -resize WIDTHxHEIGHT OUTPUT.WHATEVER

use

Code: Select all

convert INPUT.WHATEVER -filter Box -define filter:blur=0 -resize WIDTHxHEIGHT OUTPUT.WHATEVER

If I understand correctly how things work, IM will automagically enlarge the support of the Box so that at least one pixel is inside it, no matter the position within the output image (plus a nudge). So, in case there are ties, large enough to catch one will actually catch all.

Consequently, when you have ties, they will be resolved by averaging. (Provided you don't have bad luck with the nudge, but if you downsample to a factor of the original width and height, you should not have bad luck.)

(If someone has a better solution, I'd love to read it.)

[NicolasRobidoux]

An alternative might be to use -interpolate average when downsampling an even sized image by an even factor: http://imagemagick.org/script/command-l ... nterpolate

[NicolasRobidoux]

Uhmmm! Not sure the above proposed fix works flawlessly. P.S. Indeed, it does not.

[NicolasRobidoux]

Hopefully, the following works, if the resize preserves aspect ratio:

Code: Select all

convert INPUT.WHATEVER -filter Box -define filter:blur=1.5*OUT_WIDTH/IN_WIDTH -resize OUT_WIDTHxOUT_HEIGHT OUTPUT.WHATEVER

P.S.
When OUT_WIDTH/IN_WIDTH is the reciprocal of an integer, this appears to work perfectly.
When the ratio of the input size to the output size (in both directions) is not an integer, push 1.5 down toward 1 (e.g. use 1.00000001 instead of 1.5). Otherwise, you may end up averaging when there is no actual tie.

[anthony]

Checking....

In IMv6 this...

Code: Select all

  convert checks_10.gif -filter Point -resize 9x9 -scale 1000% show:

Produces a result I would have expected from box, rather than from point. That is I get images like this (magnified)

That is the center row becomes a gray merger! This is just wrong!

On the other hand IMv7! Does produce the correct results, such as this (magnified)


Hmmm could -resize point be doing interpolation, like -distort does? If so that would be acceptable! -- Nope interpolation setting has no effect! Bug then I would have seen a more global effect from interpolation if it did

[NicolasRobidoux]

...This is just wrong!

It is wrong if your primary motivation for using Point is not to add new colours. Since I believe this is the most common reason for using Point, IM7 appears to have the correct default behavior.

However, the "wrong" behavior (which adds grey) is exactly what I want. When you reduce 10x10 down to 9x9, the middle row and column have pixel centers that are located exactly at positions halfway between black and white pixels of the input image. Choosing one colour over the other instead of averaging has the potential of "shifting" the entire image toward one of the corners by a sub-pixel distance. This is unacceptable for my current use.

For my use, the middle row and column should be gray. So, in a way, this thread is about finding a clean way to get the wrong behavior with IM7, namely: Resolve "nearest" ties by averaging (instead of what appears to be top-left).

[magick]

Unfortunately we can not reproduce the results. We get the same results for IMv6 (6.7.6-4) and IMv7 (7.0.0-0) and there is no averaging. The point filter must not introduce new colors. Perhaps the issue is the floating-point implementation. In the past, we sometimes needed to add MagickEpsilon (1.0e-10) to certain math operations in ImageMagick to consistently produce correct results.

[anthony]

For my use, the middle row and column should be gray. So, in a way, this thread is about finding a clean way to get the wrong behavior with IM7, namely: Resolve "nearest" ties by averaging (instead of what appears to be top-left).

Have you tried interpolating colors? Interpolation has the choice of nearest, or integer for resolving this issue.
It also has average (always mix), and I have in my notes to add (at some point) a mixed interpolation of (nearest or average) depending closeness to real pixel or center. I also want to add catrom and hermite as interpolators.

[NicolasRobidoux]

Have you tried interpolating colors? Interpolation has the choice of nearest, or integer for resolving this issue.
It also has average (always mix), and I have in my notes to add (at some point) a mixed interpolation of (nearest or average) depending closeness to real pixel or center. I also want to add catrom and hermite as interpolators.

I gave it a quick try, but could not make sure that I was getting what I wanted. (Note that I don't want to always mix. I only want to mix when there is a tie.) Since I found an alternate solution, I let it go.

RE: Adding Catrom and Hermite: You know that, because the basis functions are (proportional to, with the same constant throughout) the members of a partition of unity, filtering (like resize does) is the same as interpolating (provided you don't stretch or shrink the support)?

Partition of unity means that if you sum all the values of the applicable basis functions at any point, you get 1.

[anthony]

I was not thinking of catrom and hermite interpolation filters for 'resize' but for general interpolation situations.

NOTE: -interpolate-resize (resize using the current interpolation setting) has been added to IMv7. In IMv6 -adaptive-resize is eroniously doing the same thing. It should actually be restricting itself to "mesh" interpolation, but for some reason keeps getting generalized

[NicolasRobidoux]

I figured that since IM is supposed to enlarge the support of the filter enough to make sure that there is at least one pixel in the region, this may work (to, once again, downsample with nearest neighbour, except that when there is a tie in the identity of nearest input pixels, the method averages the equally close pixel values):

Code: Select all

magick INPUT.IMG -filter Point -distort Resize WIDTHxHEIGHT OUTPUT.IMG

Bingo! (I've only checked exact integer downsampling ratios with square images, but this is my use case.)
P.S. This solution is kind of a hack, so I would not bet on it working "forever", but it works now.

[anthony]

The point filter fault was fixed by Magikc and was cause by a '<' vs '<=' floating point test in resize.
this is why it only appeared in very specific cases.

This has been fixed. -- Thanks Crisy

[NicolasRobidoux]

Assuming my svn contains the fixes (I should look at the log; svn'd minutes ago), here is. With an INPUT.IMG which is an 840x840 16-bit TIFF (note that 840=4*210)

Code: Select all

magick INPUT.tif -filter Point -resize 210x210 resizePoint.tif

gives something very different from

Code: Select all

magick INPUT.tif -filter Point -distort Resize 210x210 distortPoint.tif

which gives an answer just slightly different from

Code: Select all

magick INPUT.tif -filter Box -define filter:blur=.375 -resize 210x210 nearestWithAveragingTies.tif

which is what I want (but which is not, I believe, what you want in IM because, really, Point should be for never adding new colours). The small difference (max = 1, min = 0, in 16-bit, so it's "nothing") is likely due to slightly different rounding/clamping/casting.

My suggested conclusion: If you want Point to never adding colours, it would appear that this is not working for -distort yet. (I may not be particularly happy if this gets fixed, but I'm getting used to the idea that resolving ties by averaging when using nearest neighbour is something pretty unusual, even though it's "obviously" the right thing to do when one is dealing with a natural image which has not been "artificially" processed. Of course, with a paletted one, it's a disaster.)

[NicolasRobidoux]

My personal conclusion: Don't try so hard to keep the alignment, and let IM's nearest do whatever it wants.

Unless I change my mind, I'm not pursuing clean code "nearest neighbour that averages values when there is a tie" code anymore. I'm happy with what's above, but I worry a bit about relying on hacks based on possibly unstable implementation details. So Bye!

(Yes, I could restore symmetry by taking the average of the results obtained by moving the image corner into each one of the four possible positions with rotations or reflexions (cloning), resizing, unrotating/unreflecting, and averaging the four results. This is a clean, but long, way of doing the computation, which does not rely on implementation details. It's also unbelievably wasteful when there are no ties.)

For the purpose of my student Adam Turcotte's quantitative upsampler comparative test suite, it may be argued that "fixing" nearest neighbour in a way that makes it give the same result as Box when downsampling by exactly 2 in both directions is not so informative, since we of course use Box downsampling too.

So: KISS.

Part of why I made this decision is that when I reenlarge the results with Point and compute the standard deviation w.r.t. to the original (which, I must admit, is reasonably low noise) it is only about 12% less with the "resolve ties by averaging" method than with unadulterated nearest neighbour. That is, allowing IM to resolve ties whatever way it chooses does not have a huge impact on the standard deviation of the re-enlargement (for reasonable input images).

[NicolasRobidoux]

Here is a really compact solution:

Code: Select all

magick INPUT.IMG -filter Box -define filter:blur=0 -distort Resize WIDTHxHEIGHT OUTPUT.IMG

It will only do what I want when WIDTH divides the width of the input image exactly, and likewise with the HEIGHT, but this is the situation that I care about.
Of course it relies on ImageMagick enlarging the blur just enough to make sure that there is at least one point in the "Box" (which here is a disk).