# Affine transformation on a pixel grid

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)
-
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 Feb 18 '13 at 17:33