Joaquín De Ferrari

Notes / Computer Vision

Homogeneous coordinates

Points and lines in the plane, summarized for review, with interactive figures.

ℓ = m1 × m2

The line through two points.

m = ℓ1 × ℓ2

The point where two lines meet.

Throughout this page, points are drawn in red ink and lines in blue ink.

1The homogeneous point

A point of the plane with Cartesian coordinates (x, y) is written in homogeneous coordinates by appending a third component equal to 1:

m = xy1

The payoff is that points and lines both become three-component vectors, and the geometric operations of the plane reduce to dot and cross products.

Scale does not matter

Any multiple λm with λ ≠ 0 represents the same point. All three of these vectors are the point (2, 3):

231 ∼ 462 ∼ −1−1.5−0.5

The reason is how we return to Cartesian coordinates: we divide by the third component. If m = [p q r]T, the point is

(x, y) = (pr, qr)

and the division cancels the factor λ: λp / λr = p / r. That is why the result of an operation does not need to end in 1; you only have to divide by r before reading it.

2The line as a vector

The line ax + by + c = 0 is fully described by its three coefficients, so it can also be written as a vector:

ℓ = abc ⟷ ax + by + c = 0

As with points, λℓ is the same line: multiplying the whole equation by λ does not change which points satisfy it.

When a point lies on a line

If you substitute m = [x y 1]T into the equation of the line, what you get is exactly a dot product:

ℓTm = ax + by + c = 0

For example, the lab's line [1 −1 10]T is x − y + 10 = 0. The point (10, 20) lies on it because 1·10 + (−1)·20 + 10·1 = 0.

Evaluating the line at a given x

Solving the equation for y:

y = −(ax + c) / b

This holds when b ≠ 0; if b = 0, the line is vertical. The lab uses it at x = 14 with the line above: y = −(14 + 10) / (−1) = 24.

3The line through two points

ℓ = m1 × m2

Why does this work? The cross product returns a vector perpendicular to both factors, and perpendicular means a zero dot product. So ℓTm1 = 0 and ℓTm2 = 0, which is exactly the condition for both points to lie on ℓ.

For points of the form [x y 1]T, the cross product becomes:

ℓ = y1 − y2x2 − x1x1y2 − x2y1

Drag m1 and m2. With a keyboard, select a point with Tab and move it with the arrow keys.

4The intersection of two lines

m = ℓ1 × ℓ2

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.

The result [p q r]T almost never comes with r = 1, so dividing by r is a required step before reading the coordinates.

Drag the endpoint circles to move each line. The lines are simplified before the cross product; any multiple would give the same point. Try making them parallel and watch r.

5The lab example, step by step

The points and lines lab chains everything above into a single example.

  1. The points. m1 = [10 20 1]T,  m2 = [20 30 1]T
  2. The line through them. ℓ = m1 × m2 = 20 − 3020 − 1010·30 − 20·20 = −1010−100
  3. Simplify. Dividing by −10 gives the same line, [1 −1 10]T, that is x − y + 10 = 0. This is the form the lab stores as ell_1.
  4. Evaluate at x = 14. y = −(1·14 + 10) / (−1) = 24
  5. Intersect with a second line. The lab uses ℓ2 = [1 1 −40]T, that is x + y = 40. m = ℓ1 × ℓ2 = (−1)(−40) − 10·110·1 − 1·(−40)1·1 − (−1)·1 = 30502
  6. Back to Cartesian. Here r = 2, so we divide: (302, 502) = (15, 25) Check: 15 − 25 + 10 = 0 and 15 + 25 − 40 = 0.

6Summary

The key ideas next to their NumPy equivalents, using the same variable names as the lab.

Point in homogeneous form
m = [x y 1]T
m = np.array([x, y, 1])
Back to Cartesian
(p/r, q/r)
x, y = m[0]/m[2], m[1]/m[2]
Scale does not matter
λm ∼ m, λℓ ∼ ℓ (λ ≠ 0)
No code: it is a property, not an operation.
Point on a line
ℓTm = 0
np.isclose(np.dot(ell, m), 0)
Line through two points
ℓ = m1 × m2
ell = np.cross(m1, m2)
Intersection of two lines
m = ℓ1 × ℓ2, then divide by r
mi = np.cross(ell_1, ell_2)
y for a given x
y = −(ax + c) / b
y = -(a*x + c)/b