Page 241 -

220 4 Feature detection and matching

(a) (b) (c)

(d) (e) (f)
Figure 4.39 Image editing in the contour domain (Elder and Goldberg 2001) c 2001 IEEE: (a) and (d) original
images; (b) and (e) extracted edges (edges to be deleted are marked in white); (c) and (f) reconstructed edited
images.

4.3 Lines

While edges and general curves are suitable for describing the contours of natural objects,
the man-made world is full of straight lines. Detecting and matching these lines can be
useful in a variety of applications, including architectural modeling, pose estimation in urban
environments, and the analysis of printed document layouts.
In this section, we present some techniques for extracting piecewise linear descriptions
from the curves computed in the previous section. We begin with some algorithms for approx-
imating a curve as a piecewise-linear polyline. We then describe the Hough transform, which
can be used to group edgels into line segments even across gaps and occlusions. Finally, we
describe how 3D lines with common vanishing points can be grouped together. These van-
ishing points can be used to calibrate a camera and to determine its orientation relative to a
rectahedral scene, as described in Section 6.3.2.

4.3.1 Successive approximation

As we saw in Section 4.2.2, describing a curve as a series of 2D locations x i = x(s i ) provides
a general representation suitable for matching and further processing. In many applications,
however, it is preferable to approximate such a curve with a simpler representation, e.g., as a
piecewise-linear polyline or as a B-spline curve (Farin 1996), as shown in Figure 4.40.
Many techniques have been developed over the years to perform this approximation,
which is also known as line simplification. One of the oldest, and simplest, is the one proposed
by Ramer (1972) and Douglas and Peucker (1973), who recursively subdivide the curve at