4
Zhang, Deriche, Faugeras, Luong
review the epip olar geometry, and then describ e in detail the three steps of the proposed
approach. A preliminary version of this pap er app eared in the pro ceedings of the third
European Conference on Computer Vision [12].
A similar idea has b een indep endently exploited by Xu et al. [57, 40], who also searched
for image corresp ondences through the recovery of the epip olar geometry. There are however
two main dierences:
The weak p ersp ective camera mo del is used in their work, and a full persp ective model is
used in ours. The choice of the most appropriate criterion for the recovery of the epipolar
geometry is not addressed in their work.
The search for the epipolar geometry is carried out with an exhaustive strategy in their
work. The complexity is prohibitively high even for a weak p ersp ective mo del (
O
(
m
4
n
4
),
where
m
and
n
are the numberofpoints in the rst and second image, respectively). The
complexity is reduced bychecking only a few closest points. In our work, some classical
techniques are applied to nd an initial set of correspondences.
We could apply the same strategy as that of Xu et al. [57, 40]. In fact, it has been applied to
solve the corresp ondence problem between two sets of 3D line segments [59]. When applying
it to the problem addressed in this paper, we need 8 p oint corresp ondences in order to
estimate the epipolar geometry. The complexity is then
O
(
m
8
n
8
). Supp ose b oth
m
and
n
are 100, the complexity is in the order of 10
32
! Xu et al. [57, 40] deal with also the motion
segmentation problem using epip olar constraint, which is not addressed in this pap er.
Recently, computer vision researchers havepaidmuch attention to the robustness of vi-
sion algorithms because the data are unavoidably error prone [17, 60]. Many the so-called
ro-
bust regression
methods have been proposed that are not so easily aected by outliers [25,48].
The reader is referred to [48, Chap. 1] for a review of dierent robust metho ds. The two most
popular robust metho ds are the
M-estimators
and the
least-median-of-squares
(LMedS) me-
thod (see Sect. 6.3). Kumar and Hanson [26] compared dierent robust metho ds for p ose
renement from 3D-2D line correspondences, while Meer et al. [38], for image smo othing.
Haralick et al. [18] applied M-estimators to solve the pose problem from p oint corresp on-
dences. Thompson et al. [51] applied the LMedS estimator to detect moving ob jects using
point corresp ondences b etween orthographic views. Other recentworks on the application
of robust techniques to motion segmentation include [52, 42, 3].
Regarding the robust recovery of the epipolar geometry, our work is closely related to
that of Olsen [43] and that of Shapiro and Brady [49]. Olsen uses a linear method to estimate
the epip olar geometry, which has already been shown in one of our previous work [32]to
be insuciently accurate. He further assumes that knowledge of the epipolar geometry,as
in many practical cases, is available. In particular, he assumes the epipolar lines are almost
aligned horizontally. This knowledge is then used to nd matches between the stereo image
pair, and a robust metho d (the M-estimator, see Sect. 6.3) is used to detect false matches
and to obtain a b etter estimate of the epip olar geometry. Shapiro and Brady also use a
linear metho d. The camera model is however a simplied one, namely an ane camera.
Correspondences are established by tracking corner features over time. False matches are
INRIA