Skewing an image using Perspective Transforms

I'm trying to perform a skew on an image, like one shown here

_{(source: microsoft.com)}
.

I have an array of pixels representing my image and am unsure of what to do with them.

A much better way to do this is by inverse mapping.

Essentially, you want to "warp" the image, right? Which means every pixel in the source image goes to a predefined point - the predefinition is a transformation matrix which tells you how to rotate, scale, translate, shear, etc. the image which is essentially taking some coordinate (x,y) on your image and saying that, "Ok, the new position for this pixel is (f(x),g(y)).

That's essentially what "warping" does.

Now, think about scaling an image ... say, to ten times the size. So that means, the pixel at (1,1) becomes the pixel at (10,10) - and then the next pixel, (1,2) becomes the pixel (10,20) in the new image. But if you keep doing this, you will have no values for a pixel, (13,13) because, (1.3,1.3) is not defined in your original image and you will have a bunch of holes in your new image - you'll have to interpolate for that value using the four pixels around it in the new image, i.e. (10,10) , (10,20), (20,10), (200,2) - this is called bilinear interpolation.

But here's another problem, suppose your transformation wasn't simple scaling and was affine (like the sample image you've posted)- then (1,1) would become something like (2.34,4.21) and then you'd have to round them in the output image to (2,4) and then you'd have to do bilinear interpolation on the new image to fill in the holes or more complicated interpolation - messy right?

Now, there's no way to get out of interpolation, but we can get away with doing bilinear interpolation, just once. How? Simple, inverse mapping.

Instead of looking at it as the source image going to the new image, think of where the data for the new image will come from in the source image! So, (1,1) in the new image will come from some reverse mapping in the source image, say, (3.4, 2.1) and then do bilinear interpolation on the source image to figure out the corresponding value!

Transformation matrix

Ok, so how do you define a transformation matrix for an affine transformation? This website tells you how to do it by compositing different transformation matrices for rotation, shearing, etc.

Transformations:

_{(source: mathieu at people.gnome.org)}

Compositing:

_{(source: mathieu at people.gnome.org)}

The final matrix can be achieved by compositing each matrix in the order and you invert it to get the the inverse mapping - use this compute the positions of the pixels in the source image and interpolate.