## 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 transformed
`dst `

- `Bitmap `

to draw the transformed image onto
`xcorner `

- Array of the `x`

coordinates of the transformed image. `xcorner.size() `

must equal `4`

`ycorner `

- Array of the `y`

coordinates of the transformed image. `ycorner.size() `

must equal `4`

`callbackfunc `

- 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 ratios
`SkewHorizontal`

: 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