I'm implementing affine transformations on images. Currently I'm doing rotation, but general transformation will be added later.

Basically each pixel is mapped by the rotation matrix R:

$\begin{bmatrix} cos(a) & -sin(a) \\ sin(a) & cos(a) \end{bmatrix} $

The problem is that mapping back does not always come back to a grid point, so I basically rounding it using a brute force approach. What is a better approach (similarly to Bresenham's line drawing algorithm)?


1 Answer 1


What you need is an interpolation method.

The method you described is called nearest-neighbor, because you pick the pixel that is nearest to the place you actually wanted.

Other methods include:

  • bi-linear interpolation (Select 4 nearest points, interpolate by x and y according to distance) (see here)
  • barycentric interpolation (Select 3 nearest points, interpolate in the system of coordinates of the triangle)
  • bi-cubic interpolation (see here)
  • $\begingroup$ Thanks! But are there any efficient implementation of this? This is a brute force approach and it's O(n^2), right? $\endgroup$ Feb 18, 2013 at 17:26
  • $\begingroup$ @DzungNguyen, I am not sure what is n in your notation, but assuming that it is number of pixels, then no, it is a linear algorithm O(n) $\endgroup$ Feb 18, 2013 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.