Fast plane rotation algorithm?

Question

I am working on an application that detects the most prominent rectangle in an image, then seeks to rotate it so that the bottom left of the rectangle rests at the origin, similar to how IUPR's OSCAR system works. However, once the most prominent rectangle is detected, I am unsure how to take into account the depth component or z-axis, as the rectangle won't always be "head-on". Any examples to further my understanding would be greatly appreciated. Seen below is an example from IUPR's OSCAR system.

alt text http://quito.informatik.uni-kl.de/oscar/oscar.php?serverimage=img_0324.jpg&montage=use

Answer 1

You don't actually need to deal with the 3D information in this case, it's just a mappping function, from one set of coordinates to another.

Look at affine transformations, they're capable of correcting simple skew and perspective effects. You should be able to find code somewhere that will calculate a transform from the 4 points at the corners of your rectangle.

Almost forgot - if "fast" is really important, you could simplify the system to only use simple shear transformations in combination, though that'll have a bad impact on image quality for highly-tilted subjects.

Answer 2

Actually, I think you can get away with something much simpler than Mark's approach.

1. Once you have the 2D coordinates on the skewed image, re-purpose those coordinates as texture coordinates.

2. In a renderer, draw a simple rectangle where each corner's vertices are texture mapped to the vertices found on the skewed 2D image (normalized and otherwise transformed to your rendering system's texture coordinate plane).

Now you can rely on hardware (using OpenGL or similar) to do the correction for you, or you can write your own texture mapper:

The aspect ratio will need to be guessed at since we are disposing of the actual 3D info. However, you can get away with just taking the max width and max height of your skewed rectangle.

Perspective Texture Mapping by Chris Hecker