1.8RC7 Win7 Resample Nearest Neighbor artifacts?

[mschuster]

I am seeing what appear to be interpolation artifacts when I use the Resample process Nearest Neighbor interpolation.

Open outflow1.tif. This is a small crop.
Zoom the image window to 4:1 (400% zoom).

Clone the image window, and use the Resample process with Nearest Neighbor interpolation and a 400% zoom.

Compare the two images, look especially along the ionization front, you should be able to see differences, the Resample result looks aliased and lower quality. Open outflow3.tif. This is the Resample result from my laptop.

Open outflow2.tif. This is nearest neighbor resampling from a different software tool. It looks better than PI's Resample results, and more similar to PI's image zoom.

Thanks,
Mike

https://dl.dropboxusercontent.com/u/109232477/PixInsight/outflow.zip

[Juan Conejero]

This is just how nearest neighbor works. See:

http://pixinsight.com/doc/docs/InterpolationAlgorithms/InterpolationAlgorithms.html

Our implementation of nearest neighbor rounds source coordinates to the nearest integer:

Since resampling works by inverse mapping (the coordinates on the result image are mapped to coordinates on the source image), resampling up can generate these effects as a result of rounding, depending on the dimensions of the image and the scaling factors applied.

Pixel replication is a completely different geometrical operation, and it has nothing to do with interpolation. Your outflow2 image is the result of a 1:4 replication. If this is what you want to get, then use the IntegerResample tool.

[mschuster]

Thanks Juan. IntegerResample does give me what I want.

I understand rounding sensitivity depending on mapping, but in this case of simple 4x sampling I wonder how aliasing is possible.

Subpixel positioning will be a 2D translation of of the sequence 0.0, 0.25, 0.5, 0.75, say 0.1, 0.35, 0.6, 0.85 or 0.2, 0.45, 0.7, 0.95, etc. In these cases two samples round down and two samples round up, and so a simple pixel replication seems always to result.

Thanks,
Mike

[Juan Conejero]

This is a rounding issue. For example, enter the following in PI's console:

j Math.round( 0.5 )

Contrarily to what one might expect, the result is zero. Of course, the result of:

j Math.round( 0.5000000000000001 )

is exactly one. However,

j Math.round( 1.5 )

gives 2.0, not 1.0.

Current versions of PixInsight use the Banker's rule for rounding floating point numbers to the nearest integers. The Banker's rule says that a perfect half must always be rounded to the nearest even digit. That's why round(0.5) = 0 (zero is an even number), round(1.5) = 2, round(2.5) = 2, round(3.5) = 4, and so on. Banker's rounding (also known as Gaussian rounding) is statistically more accurate than the usual arithmetic rounding, but can be problematic for some very specific operations that depend critically on rounding, such as nearest neighbor upsampling.

By the way, rounding to the nearest integer is a performance-critical routine that I have implemented using an IEEE trick (if you are interested in the nitty-gritty, open pcl/Math.h and look for "RoundI"). Basically, the rounding operation can be reduced to a simple addition, taking advantage of some peculiarities of the IEEE binary representation. This improves performance of many critical routines dramatically. If you feel like a real hacker after reading this, I strongly recommend the book Hacker's Delight by Henry S. Warren. It's a real delight

[mschuster]

Thanks for the explanation Juan.

I actually am familiar with unbiased rounding and I agree it explains my observation.

However (not surprisingly!) it has been my experience not use unbiased rounding in computer graphics rasterization implementations on purpose avoid the annoying aliasing.

Thanks,
Mike

[mschuster]

Hi Juan,

I think this is important so I give another example.

Suppose I am integrating subs where all rotations equal exactly 0, all scales exactly 1 and varying dx and dy values.

If dx and/or dx equals exactly 0.5 then using unbiased rounding in nearest neighbor produces horrible aliasing.

IMO much better to use biased rounding in interpolation. In fact I believe this is true for all interpolation schemes in addition to nearest neighbor.

IMO unbiased rounding should be used always, except when it produces aliased results.

Thanks, Mike

[Juan Conejero]

Hi Mike,

The only pixel interpolation algorithm that depends on integer rounding of coordinates is nearest neighbor; the rest of algorithms work by truncating coordinates (floor operation), precisely to prevent aliasing caused by periodic rounding artifacts (which are unavoidable, even with biased rounding schemes).

So with the exception of nearest neighbor, coordinates are *always* handled as real numbers for interpolation purposes in PixInsight, and if they have to be converted to integers, they are truncated.

So the repercussion of this issue is really minimal: only NN can be affected. Nevertheless, I'll try to release ASAP new versions of interpolating tools that depend on NN that round using arithmetic rules.

[Juan Conejero]

Mike,

This bug has been fixed in the new versions of the Geometry and ImageRegistration modules, which I have released today. Thank you for detecting this problem.

However, there's something that may seem weird at first sight, so I prefer to comment it in advance.

The PI/PCL implementation of nearest neighbor uses now arithmetic rounding of coordinates:

Round( 0.5 ) = 1
Round( 1.5 ) = 2
Round( 2.5 ) = 3

and so on. When nearest neighbor is used to upsample an image, inverse mapping inevitably causes an odd effect on the borders of the resulting image. Consider the first row of your 128x128 image, being upsampled 4:1 to 512x512:

Result pixel coordinate   : 0    1    2    3    4    5    6    ... 505    506    507    508    509    510   511
Source pixel coordinate   : 0.00 0.25 0.50 0.75 1.00 1.25 1.75 ... 126.25 126.50 126.75 127.00 127.25 127.5 127.75
Rounded source coordinate : 0    0    1    1    1    1    2    ... 126    127    127    127    127    127   127

Due to the biased interpolation, the first two columns are atypical. After columns 0 and 1, we have sequences of four duplicates of the same original pixel. However, since we cannot interpolate outside the source image, the last two rows must necessarily be duplicates of the last pixel in the source row, at column index 127. The rounded coordinate would be 128, which doesn't exist. The same happens vertically.

The obvious way to avoid these atypical border rows and columns is to truncate coordinates (e.g. by the floor operation) instead of rounding. If we truncate, the first four columns map to zero, and the last four ones map to 127, which is equivalent to pixel replication. However, truncating coordinates is incorrect in my opinion. These border effects are IMO statistically irrelevant; they are just the result of a strictly correct implementation.