# projective geometry: how do I turn a projection of a rectangle in 3D into a 2D view

So the problem is that I have a 3D projection of a rectangle that I want to turn into 2D. That is I have a photo of a sheet of paper laying on a table which I want to transform into a 2D view of that sheet.

Thus, what I need is to get an un-distorted 2D image by reverting all the 3D/projection transformations and getting a plain view of the sheet from the top. I happened to find some directions on the subject but they don't suggest an immediate instruction on how this can be achieved. It would be really helpful to get a step-by-step instruction of what needs to be done. Or, alternatively, a link on a resource that breaks it down to little details.

-
On What aspect do you need help? The vision part (detecting the edges of the paper)? The geometry part (determine 3d position and reverse the mapping)? The image processing part (resampling images)? Or the programming part (what libraries you can use on a given platform) ? – Kris Van Bael Nov 11 '12 at 8:23
Geometry part please. I need formulas that map 4 points of the 3D projection view to 4 points on a 2D plane. – bonomo Nov 11 '12 at 10:20
I've marked my answer for deletion, as I didn't understand what you wanted. As I understand it now, you have a digital photograph of a document, taken at an oblique angle, and you want to form an image of the document as though it was square-on to the camera. – John R. Strohm Nov 11 '12 at 18:50
You are looking for a Homography. This can be computed directly from the four corner points of the rectangle in your input image, plus your (fixed) target points. I'm sorry I don't have time to write up a full answer, but this is a standard part of any computer vision course (for example, these lecture notes are relevant). For a library solution, OpenCV has findHomography. – John Bartholomew Nov 11 '12 at 18:57
Of the linear equations listed in the lecture notes linked by @JohnBartholomew, the most commonly used one is on the second-to-last page (Set up a 2N x 8 matrix, put zero on the right hand side, and use SVD to find null space/subspace with minimal residue) – rwong Nov 12 '12 at 4:36

One factor that is really important to help understanding most any method of performing this operation is that you will be taking each pixel location of your END image and then calculating the position within the source image to calculate the pixel data from (using one of numerous interpolation methods.)

Understanding that the calculation goes "in reverse" is key to groking this type of transformation.

-
Thank you for your answer. I do understand that each pixel from that end projection needs to be translated into the target view that represents an approximation of the original image. Now all I need is a set of transformation matrices that would do this trick for me by applying them all to each pixel of the sheet projection. After that I need to interpolate the gaps in the target image using one of the techniques mentioned by @AbdiasSoftware – bonomo Nov 11 '12 at 18:44
There won't be any gaps. The value for each pixel location of the final image is calculated from the source image using the interpolation function. – Dave Nay Nov 11 '12 at 18:50
Re-reading your comment to my answer, I think you didn't get what I'm saying. Each pixel of the target view is translated to a floating point coordinate within the end projection. This is opposite of what you have stated. The essence of what I am saying is that you will be calculating the source of pixel and not the destination. – Dave Nay Nov 11 '12 at 18:59

What you need to convert this with is morphing/warping using for example an algorithm called Catmull-Rom cubic spline interpolation.

The "correction" is easier to achieve if you don't look at it as a 3D rectangle, but as a distorted perspective of an image.

Using morphing techniques can help you calculate the various interpolations along the two axis (how much you need to interpolate or not on a given x/y coordinate). The morph/warp is of course with a destination as a 'perfect' rectangle.

You didn't state what language you prefer, but here are some resources on the topic with source code (the first one shows a more complex mesh, but you would only need one "square" of that making it simpler):

Catmull-Rom cubic spline interpolation:
http://www.ibiblio.org/e-notes/Splines/Cardinal.htm

-
It's not just warping a quad onto a rectangle. It's gotta be perspective-correct. I believe that none of your links take that consideration into account. – Kris Van Bael Nov 11 '12 at 21:26
There is really no need to consider correct perspective as such. If you project an image that originally is square/rectangle it will "re-gain" (by the means of interpolation) that information when morphed into a equal rectangle. What you might encounter as a problem is lens distortion (bending lines). To solve this you will need more details on the "square" to compensate for the bending. – K3N Nov 11 '12 at 22:06
It's possible that the mappings that you used preserve straight lines and are hence perspective-correct. However, that is not a given. Bi-linear interpolation, for instance, can also map a rectangle on any quad. Yet the result is not perspective-correct. – Kris Van Bael Nov 11 '12 at 22:21