[Numpy-discussion] nd_image.affine_transform edge effects

[Zachary Pincus]

Hello all,

Mystery solved, I think.

I downloaded Stéfan's Lena images and tried rotating them myself. As  
far as I can tell, the artifacts are caused by numerical overflow, as  
Lena is an unsigned 8-bit image.

If Lena is converted to floating-point before the rotation is  
applied, and then the intensity range is clipped to [0,255] and  
converted back to uint8 before saving, everything looks fine.

So, the "problem" was indeed the ringing that spline interpolation  
introduces. Despite the fact that this ringing was on the order of a  
few percent (as shown earlier), that few percent made a big  
difference when the it caused intensity values to ring over the top  
or under the bottom of the numerical type's range. Thus the bizarre  
wrap-around artifacts only in certain edge regions.

When using floating-point images throughout, the spline interpolation  
looks great even on the step-function images, up to order 4 and 5  
where the ringing gets (slightly) noticeable.

So, is this a bug? Well, I still think so. Given that small ringing  
is going to happen on all but the very smoothest images, and given  
that ndimage is going to be used on non-floating-point types, it  
would be good if there were some explicit internal clipping to the  
data type's range. Otherwise, the ndimage resampling tools are unfit  
for use on non-floating-point data that resides near the edges of the  
range of the data type.

Though I'm not quite sure how one would structure the calculations so  
that it would be possible to tell when over/underflow happened... it  
might not be possible. In which case, either the tools should use  
floating-point math at some of the steps internally (as few as  
possible) before clipping and converting to the required data type,  
or explicit warnings should be added to the documentation.

Zach




On Mar 24, 2007, at 1:58 PM, Stefan van der Walt wrote:

> On Sat, Mar 24, 2007 at 01:41:21AM -0400, James Turner wrote:
>> That's hard to say. Just because it's mainly a continuous-tone image
>> doesn't necessarily mean it is well sampled everywhere. This depends
>> both on the subject and the camera optics. Unlike the data I usually
>> work with, I think everyday digital photographs (probably a photo
>> scan in the case of Lena) do not generally have the detector sampling
>> frequency matched to the optical resolution of the image. If that's
>> true, the presence of aliasing in interpolated images depends on the
>> structure of the subject and whether the scene has edges or high-
>> frequency patterns in it.
>
> Agreed, but the aliasing effects isn't not the problem here, as it
> should be visible in the input image as well.  I'd expect a
> third-order spline interpolation to be more smooth than a first-order
> interpolant, but in the resulting images this isn't the case.
>
> See
>
> http://mentat.za.net/results/lena_small.png
> http://mentat.za.net/results/img_rot_30_1.png (1st order spline)
> http://mentat.za.net/results/img_rot_30_3.png (3rd order spline)
>
>> Lena has been decimated (reduced in size) prior to the rotation. That
>> is definitely a good way to get artefacts, unless an anti-aliasing
>> filter is applied before shrinking the image. My impression is that
>> this image is probably somewhat undersampled (to understand exactly
>> what that means, read up on the Sampling Theorem).
>
> The artefacts arn't visible in the source image (url above).  The
> image definately is a scaled down version of the original Lena -- very
> interesting, btw, see
>
> http://www.cs.cmu.edu/~chuck/lennapg/lenna.shtml
>
>> investigating it further. One experiment might be to blur the  
>> original
>> Lena with a Gaussian whose sigma is 1 pixel of the shrunken image
>> before actually shrinking her, then do the rotation.
>
> A rotation should take place without significant shifts in colour.
> This almost looks like a value overflow problem.
>
>> So I do wonder if the algorithm in nd_image is making this worse
>> than it needs to be.
>
> That is my suspicion, too.
>
>> compare the results? I just tried doing a similar rotation in  
>> PyRAF on
>> a monochrome image with a bicubic spline, and see considerably  
>> smaller
>> artefacts (just a compact overshoot of probably a few % at the
>> edge).
>
> Could you apply the PyRAF rotation on the Lena given above and post
> the result?
>
> I always thought we could simply revert to using bilinear and bicubic
> polygon interpolation (instead of spline interpolation), but now I
> read on wikipedia:
>
> """
> In the mathematical subfield of numerical analysis, spline
> interpolation is a form of interpolation where the interpolant is a
> special type of piecewise polynomial called a spline. Spline
> interpolation is preferred over polynomial interpolation because the
> interpolation error can be made small even when using low degree
> polynomials for the spline. Thus, spline interpolation avoids the
> problem of Runge's phenomenon which occurs when using high degree
> polynomials.
> """
>
> http://en.wikipedia.org/wiki/Spline_interpolation
>
> also take a look at
>
> http://en.wikipedia.org/wiki/Runge%27s_phenomenon
>
> So much for side-stepping Runge's phenomenon :)
>
> Cheers
> Stéfan
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at scipy.org
> http://projects.scipy.org/mailman/listinfo/numpy-discussion