Introduction
Aaform (Anti Aliased Image Transformation) is a technique I have developed for transforming a rectangular bitmap into any quadrilateral (including convex/complex quadrilaterals). I believe that this is the optimal way to transform images that exist. Aaform uses a lot of geometry concepts that will be mentioned in this article. You can read about them here (code samples are in VB.NET, but any programmer should be able to follow them).
Below is an arbitrary sample transformation of this Website's logo.
How It Works - Intro
Aaform includes two main functions, Transform and CreateTransform. Transform is used to transform one image into another. This is useful when you want to transform one image into another image while keeping the edges looking nice. CreateTransform simply creates a blank image large enough to hold the transformed image, then puts in a call to Transform. Below is the C++ prototype of the transform function:
transform(HBITMAP src, HBITMAP dst, std::vector<double> xcorner,
std::vector<double> ycorner, aaf_callback callbackfunc)
src - Bitmap to be transformeddst - Bitmap to draw the transformed image ontoxcorner - Array of the x coordinates of the transformed image. xcorner.size() must equal 4ycorner - Array of the y coordinates of the transformed image. ycorner.size() must equal 4callbackfunc - The callback function serves two purposes. First, it allows the client code to be updated on the progress of transform, and secondly, it gives the client code an opportunity to cancel the transformation.
(xcorner[0], ycorner[0]) make up the top left corner of the transformed image, (xcorner[1], ycorner[1]) top right, (xcorner[2], ycorner[2]) bottom right, and (xcorner[3], ycorner[3]) bottom left.
How It Works - Make the Grid
The first thing transform does after checking some conditions and allocating memory is create a grid of the corners of every pixel in the transformed image. srcwidth is the width of the bitmap passed as src and srcheight is the height of the bitmap passed as src.
Looping from x = 0 to srcwidth, creategrid creates a line (in AX + BY = C form) from the point (x / srcwidth) percent down the line created by (xcorner[0], ycorner[0])-(xcorner[1],ycorner[1]) [the top edge] and then points the same percentage down the line created by (xcorner[3], ycorner[3])-(xcorner[2],ycorner[2]) [the bottom edge].
Next, a nested for loop is executed that goes from y = 0 to srcheight. It creates a line from the point(y / srcheight) percent down the line created by (xcorner[0], ycorner[0])-(xcorner[3],ycorner[3]) [the left edge] and then points the same percentage down the line created by (xcorner[1], ycorner[1])-(xcorner[2],ycorner[2]) [the right edge].
Finally, it finds where the two lines intersect and adds this point to our grid as the top right corner of the pixel located at (x, y). Since pixels share corners, there is no need to calculate all four corners for each pixel. For example, to get the top right corner of pixel (0, 0), you only need to find the top left corner of the pixel (1, 0).
How It Works - The Main Loop
Now that we have the coordinates of each corner of each transformed pixel, all we have to do is find the area of overlap over each destination pixel. Obviously we don't want to compare each transformed pixel with each destination pixel, so instead we will compare each transformed pixel with each destination pixel within the minimum floor of the transformed pixels x and y coordinates and the maximum ceil of the transformed pixels x and y coordinates. Then we will find the area of overlap of the transformed pixel's polygon over the destination pixel's square for each destination pixel within the scan area. Polygon overlap is fairly complicated, and if you are interested in knowing how it works, take a look here. (Polygon Overlap is covered in the Polygon section) Then the overlap of these two polygons can be used to determine how much representation the transformed pixel should receive in the destination pixel.
Each of the destination pixels are 1x1 squares that therefore have a maximum area of 1 square unit. So it follows that the maximum area of overlap is 1 in the case that the transformed pixel completely encloses the destination pixel. So therefore an overlap of 1.0 indicates that the transformed pixel has 100% representation in the destination pixel, thus they should be the same color. An overlap of 0.5 indicates 50% representation, and an overlap of 0.0 indicates no representation. And that's how Aaform works in a nutshell.
Extras
Aaform also includes a couple of functions that use CreateTransform to do more specific tasks:
Rotate: Rotates an image by the passed degrees Stretch: Stretches an image by the passed ratiosSkewHorizontal: Skews the image horizontally by the passed degrees (-90, 90)SkewVerticle: Skews the image vertically by the passed degrees (-90, 90)
Implementation
I have written Aaform in three languages (C++, VB6, and VB.NET). Because of this, I am not going to go over how to use the algorithm in each language. Please look at the sample project listed above for details on each function's uses.
Conclusion
I believe that Aaform produces the best quality image transformations possible in terms of data representation (it has the least data loss). I am not an expert in how the eye interprets light, so it is hard for me to say how well it represents the transformed image visually (but obviously, it does this pretty well).
History
- 24th February, 2006: Initial post
