Click here to Skip to main content
15,511,078 members
Articles / Programming Languages / Visual Basic
Article
Posted 26 Oct 2013

Tagged as

Stats

37.4K views
1.7K downloads
10 bookmarked

Perspective Projection of a Rectangle (Homography)

Rate me:
Please Sign up or sign in to vote.
4.93/5 (10 votes)
26 Oct 2013CPOL3 min read
Short study of the perspective projection of a rectangle in space; homography opposed to bilinear transform

Image 1

Introduction

A rectangle in general position in space is seen by a camera as a quadrilateral. Any point inside the rectangle projects to a point inside the quadrilateral. This article is about how the mapping of any point can be found, given the projections of the four corners.

We will establish the necessary equations, to compare to the well-known bilinear interpolation method and highlight the inaccuracy of the latter for this purpose.

The Bilinear Transform

Let us discuss the bilinear transform first. A very simple way to map the original rectangle to the quadrilateral is by linear interpolation along the sides.

First we perform a linear interpolation along two opposite sides, using an interpolation parameter Image 2. Then we interpolate between these two interpolated points, using a second interpolation parameter, Image 3. Given the four projected corners Image 4, clockwise, we have:

Image 5

Image 6

and:

Image 7

or simply:

Image 8

You can check for yourself a nice property of this scheme: if you start interpolating on the other pair of sides (03, 12) instead of (01, 32), you will get exactly the same result.

Note that by this definition, any grid line with Image 9 or Image 10 constant is transformed into a straight line. (But arbitrary lines are transformed into a curve - a conic curve.)

The Homographic Transform

Establishing the true projection equations will require some more effort. First, we will establish the general form of the equations, then the way to compute any unknown parameter they comprise.

From spatial geometry, we know that a rigid object is moved in space by applying to it a rotation and a translation. A rotation is described by a 3x3 matrix which is applied to the original coordinates, and the translation by a 3-vector which is added. In our case, the rectangle lies in a plane so that one of the input coordinates is identically 0.

Hence the transformation equations:

Image 11

Image 12

Image 13

Then the projection itself is achieved by reducing the Image 14 coordinates in the inverse proportion of the distance:

Image 15

Image 16

with Image 17 being a constant called the focal length of the camera, that we can absorb in the constants Image 18 above.

We obtain a so-called homography:

Image 19

Image 20

The nine coefficients can be multiplied by a common arbitrary factor, and without loss of generality, we can assume Image 21, to get:

Image 22

Image 23

To determine the 8 unknown coefficients, we use the coordinates of the projections of the four corners, let Image 24, corresponding to Image 25 and Image 26, in clockwise order and replace them in the general expression:

Image 27

Image 28

Image 29

Image 30

Image 31

Image 32

Image 33

Image 34

The bad news: this gives us a nonlinear system of 8 equations in 8 unknowns (Image 35 to Image 36), something usually painful to solve.

The good news: the system can be linearized and simplified to such an extent that the solution becomes straightforward.

First, we translate all Image 37 by Image 38 so that Image 39 becomes the origin; we denote the new vertices Image 40. This makes the coefficients Image 41 and Image 42 vanish because:

Image 43

Image 44

Two unknowns are gone!

Next, we linearize by moving the denominator to the left-hand side and rearranging the terms:

Image 45

Image 46

When we substitute Image 47 by their values at Image 48, Image 49 and Image 50, we get these six equations:

Image 51

Image 52

Image 53

Image 54

Image 55

Image 56

By introducing Image 57, and Image 58, we get a further simplification (this is a little rabbit out of a hat – but it is optional):

Image 59

Image 60

Image 61

Image 62

Image 63

Image 64

<to id="_x0000_i1044" src="/KB/recipes/674433/image062.png" height="16" width="12" border="0">and Image 65 we subtract equations 1 and 5 from 3, and 2 and 6 from 4, yielding (note the new indexes):

Image 66

Image 67

Solving this 2x2 system in Image 68 and Image 69 by Cramer's rule is trivial, and Image 70, Image 71, Image 72, Image 73, Image 74, Image 75 immediately follow.

Image 76

Image 77

Image 78

Image 79

Image 80

Image 81

Image 82

Image 83

The accompanying demo application will show you the discrepancies between the bilinear and perspective transforms, which is particularly noticeable for skewed quadrilaterals. On the opposite, for parallelograms both transforms become affine and coincide exactly.

When the quadrilateral is not convex, the perspective transform shows "erratic" behavior. This is because such cases are not physically achievable.

Background

General understanding of analytic geometry and perspective transforms is assumed.

Using the Code

The code directly reflects the equations established in the article and is just meant to illustrate these. The chosen language is irrelevant.

Drag the quadrilateral corners with the mouse.

Points of Interest

While working on the homographic equations, I was amazed to see how easily they can be solved in the case of a rectangle.

History

This is the first version.

License

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


Written By
CEO VISION fOr VISION
Belgium Belgium
I fell into applied algorithmics at the age of 16 or so. This eventually brought me to develop machine vision software as a professional. This is Dreamland for algorithm lovers.

Comments and Discussions

 
Questionexcellent! Pin
Southmountain26-Sep-20 14:57
Southmountain26-Sep-20 14:57 
QuestionRectangle aspect ratio Pin
Ali Kashani1-Sep-15 10:05
Ali Kashani1-Sep-15 10:05 
AnswerRe: Rectangle aspect ratio Pin
YvesDaoust1-Sep-15 10:51
YvesDaoust1-Sep-15 10:51 
GeneralRe: Rectangle aspect ratio Pin
Ali Kashani1-Sep-15 13:50
Ali Kashani1-Sep-15 13:50 
Questiondoubt Pin
Member 1101899017-Aug-14 23:49
Member 1101899017-Aug-14 23:49 
QuestionGood Pin
scosta_FST30-Oct-13 5:02
scosta_FST30-Oct-13 5:02 
5! A little too concise, but 5!
Maybe some examples of area of application could improve the article.
For example I've already used this kind of algorithms to correct the perspective distortion in some industrial machinery.
QuestionAlpha equals transparency Pin
RedDk29-Oct-13 6:40
RedDk29-Oct-13 6:40 
QuestionAddition suggestion Pin
martin_bisson28-Oct-13 21:26
martin_bisson28-Oct-13 21:26 

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.