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)?


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$ – Dzung Nguyen Feb 18 '13 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$ – Andrey Rubshtein Feb 18 '13 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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