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 !

Answer 1

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.