Notes / Computer Vision / Note 1 of 6
Leer en españolHomogeneous coordinates
Three numbers for every point and every line of the plane, so that joining two points and crossing two lines each take one cross product.
Two questions come up constantly when a computer works with geometry: which line passes through two given points, and where do two given lines cross?
-
The line through two points
-
The point where two lines cross
-
Two parallel lines: do they meet?
With the x and y we learn at school, these are two different calculations, and each has a case where it breaks: a line written with a slope cannot be vertical, and the crossing of two parallel lines comes out as a division by zero. Homogeneous coordinates describe every point and every line of the plane with three numbers instead of two. Then both questions have the same answer, one cross product, and even two parallel lines get a point where they meet. The camera geometry in the notes that follow is written in them.
Throughout this page, points are drawn in red ink and lines in blue ink.
1A third coordinate for every point
Write the point (x, y) with a third number, 1:
The third number adds nothing yet. What makes these coordinates useful is a rule about all three together: multiplying the vector by any number λ other than 0 gives the same point. These three vectors are all the point (2, 3):
To read the point back, divide the first two numbers by the third. If m = [p q r]T, the point is
The division cancels λ, since λp / λr = p / r. So a calculation may end with any third number: divide by it before reading the result. λ = 0 is left out because it turns every point into [0 0 0]T, and a vector whose third number is 0 has nothing to divide by; section 6 shows what such a vector means.
Each point is a line through the origin
The rule has a picture behind it. Read [p q r]T as a position in a space with axes p, q and r. The ordinary plane sits in that space at height r = 1, so m = [x y 1]T is a point on it. Every multiple λm lies on the line through the origin and m, and that line crosses the plane only once, at m. Dividing by r slides a vector along its line, back to the plane. A negative λ puts it on the other side of the origin, still on the same line.
If the origin were an eye and the plane r = 1 a window, each of these lines would be a line of sight: everything along it lands on the same spot of the window. That is how a camera sees, and the camera notes return to this picture. The red line in the figure is not a line of the plane: it holds every vector that stands for m.
Drag m across the plane and λm along its line, and drag the background to turn the view. With a keyboard, select the figure, λm or m with Tab and use the arrow keys.
2A line is three numbers too
A line of the plane has an equation ax + by + c = 0. Its three coefficients describe it completely, so the line can be written as a vector too:
For example, [1 −2 4]T is the line x − 2y + 4 = 0. As with points, scale does not matter: multiplying the whole equation by λ does not change which points satisfy it, so [2 −4 8]T and [−1 2 −4]T are the same line.
When a point lies on a line
Put m = [x y 1]T into the left side of the equation, and what you compute is a dot product:
The point lies on the line exactly when ℓTm = 0. The point (2, 3) lies on x − 2y + 4 = 0, since 1·2 + (−2)·3 + 4·1 = 0; the point (6, 3) does not, since 1·6 + (−2)·3 + 4·1 = 4. The test only asks whether the result is zero, so it gives the same answer for any multiple of ℓ or of m.
The line at a given x
To draw a line, or to find where it is at a given x, solve its equation for y:
This needs b ≠ 0; with b = 0 the line is vertical, x = −c/a. At x = 6, the line above has y = −(6 + 4) / (−2) = 5: the point (6, 5), right above (6, 3).
ℓ = ⟷
Change a, b and c to move the line, and drag m onto it. The ring marks the line's point at m's x. With a keyboard, select m or a coefficient with Tab and use the arrow keys.
3Every line is a plane through the origin
Go back to the space of section 1, with axes p, q and r. The vectors [p q r]T with ap + bq + cr = 0 form a plane through the origin, and ℓ = [a b c]T is perpendicular to it, since its dot product with every vector in the plane is zero. That plane meets r = 1 exactly in the line ax + by + c = 0.
So a point is a line through the origin, and a line is a plane through the origin. The point m lies on ℓ when the line of m lies inside the plane of ℓ, which is what ℓTm = 0 says. Scaling ℓ stretches or flips the perpendicular vector, but the plane stays the same, and so does the line. The zero vector is perpendicular to every vector and picks out no plane, which is why λ ≠ 0 here too.
The next two sections use this picture: joining two points and crossing two lines both come down to planes through the origin.
ℓ = ⟷
Drag λℓ along its line, change a, b and c to move the line, and drag the background to turn the view. Turn it until the blue plane shrinks to a line: λℓ then meets it at a right angle. With a keyboard, select the figure, λℓ or a coefficient with Tab and use the arrow keys.
4The line through two points
Why does this work? The cross product of two vectors is perpendicular to both, and perpendicular means a zero dot product. So ℓTm1 = 0 and ℓTm2 = 0, which is the test of section 2 for both points: ℓ passes through both. In the picture of section 3, the lines of m1 and m2 span one plane through the origin, the plane of the line through both points, and m1 × m2 is the vector perpendicular to it.
For points of the form [x y 1]T, the cross product works out to
The result is rarely in its simplest form. For the points (2, 1) and (8, 5) it is [−4 6 2]T, which divided by −2 is [2 −3 −1]T, the line 2x − 3y − 1 = 0. By section 2, both vectors are the same line.
Drag m1 and m2. With a keyboard, select a point with Tab and move it with the arrow keys.
5Where two lines cross
It is the same operation with the roles swapped. The vector m is perpendicular to both ℓ1 and ℓ2, so ℓ1Tm = 0 and ℓ2Tm = 0: the point lies on both lines. In the picture of section 3, the planes of the two lines meet in a line through the origin, and that line is the point m.
The result [p q r]T rarely ends in 1, so divide by r before reading it. The line 2x − 3y − 1 = 0 of section 4 and the line 2x + y − 13 = 0 give [40 24 8]T, and dividing by 8 gives the point (5, 3).
When the two lines are parallel, r comes out 0 and there is nothing to divide by. That is not a failure of the method: section 6 shows what the vector means.
Drag the circles to move the lines. Each line is the cross product of its two circles, divided down to its simplest form; any multiple would give the same point. Try making the lines parallel.
6Parallel lines meet at infinity
Two parallel lines can always be written with the same a and b, so they differ only in c: ℓ1 = [a b c]T and ℓ2 = [a b c′]T. Their cross product is
Its third number is 0, so it cannot be divided into a point of the plane. Its first two numbers point along both lines: moving by (b, −a) leaves ax + by unchanged, since ab − ba = 0.
The picture in space shows what happened. The planes of the two lines still meet in a line through the origin, but for parallel lines that line lies flat on the floor r = 0, parallel to the plane r = 1, so it never reaches it. As one line turns toward parallel, the crossing runs off and the line of m flattens; past parallel, the crossing comes back from the opposite side.
A vector [p q 0]T is called an ideal point, or a point at infinity: the point where all the lines with direction (p, q) meet. With ideal points, any two different lines meet at exactly one point, even parallel ones.
The line at infinity
Every ideal point satisfies 0·p + 0·q + 1·0 = 0, so all of them lie on one line, ℓ∞ = [0 0 1]T, the line at infinity. Its plane in space is the floor, r = 0.
Drag the blue circle to turn ℓ2 about the small dot, and drag the background to turn the view. Move the circle down one step at a time: the crossing runs off, the lines become parallel, and the crossing comes back from the other side. With a keyboard, select the figure or the circle with Tab and use the arrow keys.
7Summary
The key ideas next to their NumPy equivalents.
m = np.array([x, y, 1])x, y = m[0]/m[2], m[1]/m[2]ell = np.array([a, b, c])np.isclose(np.dot(ell, m), 0)y = -(a*x + c)/bell = np.cross(m1, m2)m = np.cross(ell_1, ell_2)np.isclose(m[2], 0)ell_inf = np.array([0, 0, 1])