Page 245 -

224 4 Feature detection and matching

and use this to select one of the six cube faces. Divide the remaining two coordinates by m
and use these as indices into the cube face. While this avoids the use of trigonometry, it does
require some decision logic.
One advantage of using the cube map, first pointed out by Tuytelaars, Van Gool, and
Proesmans (1997), is that all of the lines passing through a point correspond to line segments
on the cube faces, which is useful if the original (full voting) variant of the Hough transform
is being used. In their work, they represent the line equation as ax + b + y =0, which
does not treat the x and y axes symmetrically. Note that if we restrict d ≥ 0 by ignoring the
polarity of the edge orientation (gradient sign), we can use a half-cube instead, which can be
represented using only three cube faces, as shown in Figure 4.44b(Tuytelaars, Van Gool, and
Proesmans 1997).

RANSAC-based line detection. Another alternative to the Hough transform is the RAN-
dom SAmple Consensus (RANSAC) algorithm described in more detail in Section 6.1.4.In
brief, RANSAC randomly chooses pairs of edgels to form a line hypothesis and then tests
how many other edgels fall onto this line. (If the edge orientations are accurate enough, a
single edgel can produce this hypothesis.) Lines with sufficiently large numbers of inliers
(matching edgels) are then selected as the desired line segments.
An advantage of RANSAC is that no accumulator array is needed and so the algorithm can
be more space efficient and potentially less prone to the choice of bin size. The disadvantage
is that many more hypotheses may need to be generated and tested than those obtained by
finding peaks in the accumulator array.
In general, there is no clear consensus on which line estimation technique performs best.
It is therefore a good idea to think carefully about the problem at hand and to implement
several approaches (successive approximation, Hough, and RANSAC) to determine the one
that works best for your application.

4.3.3 Vanishing points
In many scenes, structurally important lines have the same vanishing point because they are
parallel in 3D. Examples of such lines are horizontal and vertical building edges, zebra cross-
ings, railway tracks, the edges of furniture such as tables and dressers, and of course, the
ubiquitous calibration pattern (Figure 4.45). Finding the vanishing points common to such
line sets can help refine their position in the image and, in certain cases, help determine the
intrinsic and extrinsic orientation of the camera (Section 6.3.2).
Over the years, a large number of techniques have been developed for finding vanishing
points, including (Quan and Mohr 1989; Collins and Weiss 1990; Brillaut-O’Mahoney 1991;
McLean and Kotturi 1995; Becker and Bove 1995; Shufelt 1999; Tuytelaars, Van Gool, and
Proesmans 1997; Schaffalitzky and Zisserman 2000; Antone and Teller 2002; Rother 2002;
Koˇ seck´ a and Zhang 2005; Pflugfelder 2008; Tardif 2009)—see some of the more recent pa-
pers for additional references. In this section, we present a simple Hough technique based
on having line pairs vote for potential vanishing point locations, followed by a robust least
squares fitting stage. For alternative approaches, please see some of the more recent papers
listed above.
The first stage in my vanishing point detection algorithm uses a Hough transform to accu-
mulate votes for likely vanishing point candidates. As with line fitting, one possible approach