An Effective Rigidity Constraint for Improving RANSAC in Homography Estimation - Advanced Concepts for Intelligent Vision Systems - page 211

100%

4-correspondences sets leading to rigid-body transformations
4-correspondences sets leading to non rigid-body transformations

90%

80%

70%

60%

50%

40%

30%

20%

10%

0%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

proportion of outliers

Fig. 5. Proportion of four-correspondence sets evaluated by RANSAC leading to either
a rigid-body or a non-rigid-body transformation with respect to the proportion of
outliers

leading to a rigid-body transformation, so is any subset of four correspondences.
Hence, non rigid-body transformations only occur in homography estimation
from four correspondences, when outliers are introduced. In order to evaluate
the proportion of rigid-body and non-rigid-body transformations obtained when
estimating a homography from randomly chosen four-correspondences sets, a set
of 256 inliers regularly distributed over an image was defined. Then the propor-
tion of inliers and outliers was progressively modified by successively exchanging
the corresponding points of two inliers, which increases the number of outliers
by two and decreases the number of inliers by two, respectively. At each step,
10 7 randomly chosen four-correspondences sets were evaluated for rigidity and
the results are illustrated in figure 5. It shows that with only 22% of outliers,
half the homographies obtained from four correspondences are non-rigid-body
transformations. It means that when RANSAC has to deal with 22% outliers
or more, it spends more than half its processing time considering solutions that
have no chance of success.
The computing cost for processing the rigidity constraint is nearly negligible
compared to the one needed for estimating a homography and checking all the
putative correspondences for consistency with this homography. Thus, when us-
ing the rigidity constraint, the overall RANSAC processing time is only devoted
to rigid-body transformations. It is then possible to express the speed-up factor s
obtained thanks to the rigidity constraint in the following way:

) · s =

t · ( total number of iterations t · ( number of rigid - body transf ormations ,

(13)

)