Explanation of nearest neighbor interpolation algorithm for image rotation

Question

I am trying to understand the implementation of nearest neighbor algorithm for image rotation. The conventional nearest neighbor algorithms I know, calculate some explicit euclidean distances between different points and take the point with the lowest euclidean distance as the best point. But in image interpolation, I do not find any explicit euclidean distance in the implementation. I am referring to this answer to another similar question. The given solution perfectly rotates an input image by the given angle. But I have many questions about the code (I do not understand what they are doing).

1.) Why does the author multiply by sqrt(2) for the new indices (lines 4 and 5) ?

2.) What is the author doing in the following lines of code (to be precise, I understand he is multiplying the indices by rotation matrix. But why does he have the extra terms like m/2, n/2, t-mm/2 and s-nn/2 ? What is he doing with if i>0 && j>0 && i<=m && j<=n ?) ? :

for t=1:mm
   for s=1:nn
      i = uint16((t-mm/2)*cos(thet)+(s-nn/2)*sin(thet)+m/2);
      j = uint16(-(t-mm/2)*sin(thet)+(s-nn/2)*cos(thet)+n/2);
      if i>0 && j>0 && i<=m && j<=n           
         im2(t,s,:)=im1(i,j,:);
      end
   end
end

Any help will be much appreciated !

The author explains the sqrt(2) factor in the answer, "the rotated image is always bigger with maximum being 45 degree rotation. Hence, the sqrt(2) factor". As for the if condition, all that's doing is making sure that the points are within the range of the original image im1. — beaker
@beaker Yes I realize that. But why only sqrt(2) for the multiplication ? What is the significance of sqrt(2) ? In the if condition, I see that he is literally copying data from the source image instead of doing any nearest neighbor interpolation (estimating the value of pixels for missing indices when we truncate floating point values of cos(theta) and sin(theta)). There is no b-spline function or any other nearest neighbor interpolation being used... What is he doing here ? — Arun Kumar
"There is no b-spline function or any other nearest neighbor interpolation being used" Nearest neighbor interpolation is literally finding the nearest pixel to your sub-pixel location and taking its value. B-spline interpolation is something totally different. Rounding the floating-point location is nearest neighbor interpolation. The code should be doing round(...), instead it truncates. It's not the same, but just leads to a half-pixel shift in both directions, which you would likely not notice. — Cris Luengo

Cris Luengo Cris Luengo · Accepted Answer · 2019-06-25T21:43:45

The code implements a rotation around the center of the image. Since coordinates within the image (indices) start at 1 in MATLAB, the natural origin of rotation is around a pixel just outside the top-left corner of the image. As per my answer to your previous question, such a rotation involves shifting coordinates, applying the rotation matrix, then shifting them back.

The code uses as origin of rotation the center of the image, x=n/2, y=m/2, with m and n the sizes of the input image. It then shifts the rotated coordinates back a bit further, so the center of the new image is at (mm/2,nn/2), with mm = m*sqrt(2) and nn = n*sqrt(2) the size of the output image. (Note that if we rotate by 45 degrees we need the output image to be sqrt(2) times the input size to not lose any data, for smaller rotations we could do with a smaller output size).

If you put all of these values into the matrices I showed in the previous answer, you should (hopefully) get to the equations shown in the code.

Finally, the code has a conditional statement to avoid reading outside the input image domain (indexing out of bounds produces an error). When rotating the image, and producing a larger output image, some output pixels will map to regions outside the input image. These are left at 0 in the code.

Note that the code linked to is not at all efficient. It doesn't preallocate the output matrix, and consequently it repeatedly resizes the output array as it writes to it, which is very expensive. It also could precompute some of the computations done within the loop, things like cos(thet) don't change between loop iterations.

Explanation of nearest neighbor interpolation algorithm for image rotation

1 Answers