Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 4 down vote accepted

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)
share|improve this answer
Thanks! But are there any efficient implementation of this? This is a brute force approach and it's O(n^2), right? – Dzung Nguyen Feb 18 '13 at 17:26
@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) – Andrey Rubshtein Feb 18 '13 at 17:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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