Click here to Skip to main content
15,868,016 members
Articles / Desktop Programming / MFC
Article

Anti Aliased Image Transformation (Aaform)

Rate me:
Please Sign up or sign in to vote.
4.79/5 (15 votes)
24 Feb 2006CPOL5 min read 86.3K   2.3K   52   17
Optimal Image Transformation

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.

Sample Transformation

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:

C++
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.

Aaform Demo

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
S Keller30-Oct-12 8:37
S Keller30-Oct-12 8:37 
GeneralJust what I needed Pin
Kangerm00se9-Feb-11 9:27
Kangerm00se9-Feb-11 9:27 
GeneralRe: Just what I needed Pin
blackeye200420-Jul-11 18:46
blackeye200420-Jul-11 18:46 
Generalcould you help me?thanks Pin
panpan12321-Mar-10 18:11
panpan12321-Mar-10 18:11 
QuestionTransparency Pin
Member 76080223-Oct-09 6:08
Member 76080223-Oct-09 6:08 
Generalit is very nice Pin
Kiaee6-Aug-06 0:37
Kiaee6-Aug-06 0:37 
GeneralRe: it is very nice Pin
msg5556-Aug-06 4:17
msg5556-Aug-06 4:17 
Generalit is very nice Pin
Kiaee6-Aug-06 0:36
Kiaee6-Aug-06 0:36 
JokeFinally Pin
Marc Selman6-Mar-06 4:45
Marc Selman6-Mar-06 4:45 
GeneralRe: Finally Pin
msg5556-Mar-06 10:15
msg5556-Mar-06 10:15 
GeneralVery Nice! Pin
WREY26-Feb-06 7:52
WREY26-Feb-06 7:52 
GeneralI cann't find the codes Pin
kellyonlyone25-Feb-06 14:56
sponsorkellyonlyone25-Feb-06 14:56 
GeneralRe: I cann't find the codes Pin
msg55525-Feb-06 16:55
msg55525-Feb-06 16:55 
GeneralMore Detailed Pin
NormDroid25-Feb-06 7:14
professionalNormDroid25-Feb-06 7:14 
This could be a good article, it's just lacking facts and details.

Blogless
GeneralRe: More Detailed Pin
msg55525-Feb-06 10:33
msg55525-Feb-06 10:33 
GeneralCheck out the AGG library Pin
Jim Crafton25-Feb-06 4:14
Jim Crafton25-Feb-06 4:14 
GeneralNice set of math :) Pin
Kochise25-Feb-06 3:54
Kochise25-Feb-06 3:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.