Page 328 -

Section 10.2 Fitting Lines and Planes 296

10.2.3 Fitting Multiple Lines
Now assume we have a set of tokens (say, points), and we want to fit several lines to
this set of tokens. This problem can be difficult because it can involve searching over
a large combinatorial space. One approach is to notice that we seldom encounter
isolated points; instead, in many problems, we are fitting lines to edge points. We
can use the orientation of an edge point as a hint to the position of the next point
on the line. If we are stuck with isolated points, then k-means can be applied.
Incremental line fitting algorithms take connected curves of edge points
and fit lines to runs of points along the curve. Connected curves of edge points
are fairly easily obtained from an edge detector whose output gives orientation (see
exercises). An incremental fitter then starts at one end of a curve of edge points and
walks along the curve, cutting off runs of pixels that fit a line well (the structure of
the algorithm is shown in Algorithm 10.1). Incremental line fitting can work well,
despite the lack of an underlying statistical model. One feature is that it reports
groups of lines that form closed curves. This is attractive when the lines of interest
can reasonably be expected to form a closed curve (e.g., in some object recognition
applications) because it means that the algorithm reports natural groups without
further fuss. When one uses this strategy, occlusion of an edge can lead to more
than one line segment being fitted to the boundary. This difficulty can be addressed
by postprocessing the lines to find pairs that (roughly) coincide, but the process is
somewhat unattractive because it is hard to give a sensible criterion by which to
decide when two lines do coincide.

Put all points on curve list, in order along the curve
Empty the line point list
Empty the line list
Until there are too few points on the curve
Transfer first few points on the curve to the line point list
Fit line to line point list
While fitted line is good enough
Transfer the next point on the curve
to the line point list and refit the line
end
Transfer last point(s) back to curve
Refit line
Attach line to line list
end

Algorithm 10.1: Incremental Line Fitting.

Now assume that points carry no hints about which line they lie on (i.e., there
is no color information or anything like it to help, and, crucially, the points are not
linked). Furthermore, assume that we know how many lines there are. We can
attempt to determine which point lies on which line using a modified version of
k-means. In this case, the model is that there are k lines, each of which generates