Page 326 -

Section 10.2 Fitting Lines and Planes 294

tokens in 3D is also useful, and our methods for fitting lines in the plane apply with
little change.

10.2.1 Fitting a Single Line
We first assume that all the points that belong to a particular line are known, and
the parameters of the line must be found. We adopt the notation

u i
u =
k
to simplify the presentation.
There is a simple strategy for fitting lines, known as least squares. This
procedure has a long tradition (which is the only reason we describe it!), but has
a substantial bias. Most readers will have seen this idea, but many will not be
familiar with the problems that it leads to. For this approach, we represent a line
as y = ax + b. At each data point, we have (x i ,y i ); we decide to choose the line
that best predicts the measured y coordinate for each measured x coordinate. This
means we want to choose the line that minimizes

2
(y i − ax i − b) .
i
By differentiation, the line is given by the solution to the problem

y 2 x 2 x a
= .
y x 1 b
Although this is a standard linear solution to a classical problem, it’s not much help
in vision applications, because the model is an extremely poor one. The difficulty
is that the measurement error is dependent on coordinate frame—we are counting
vertical offsets from the line as errors, which means that near vertical lines lead
to quite large values of the error and quite funny fits (Figure 10.3). In fact, the
process is so dependent on coordinate frame that it doesn’t represent vertical lines
at all.
We could work with the actual distance between the point and the line (rather
than the vertical distance). This leads to a problem known as total least squares.
We can represent a line as the collection of points where ax + by + c =0. Every
line can be represented in this way, and we can think of a line as a triple of values
(a, b, c). Notice that for λ = 0, the line given by λ(a, b, c) is the same as the line
represented by (a, b, c). In the exercises, you are asked to prove the simple, but
extremely useful, result that the perpendicular distance from a point (u, v)toa
line (a, b, c)is given by

2
2
abs(au + bv + c)if a + b =1.
In our experience, this fact is useful enough to be worth memorizing. To minimize
the sum of perpendicular distances between points and lines, we need to minimize

2
(ax i + by i + c) ,
i