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

12x

11x

10x

9x

8x

7x

6x

5x

4x

3x

2x

1x

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

proportion of outliers

Fig. 6. RANSAC speed-up factor expected from the rigidity constraint

where t is the processing time needed for one iteration throughout the full ho-
mography evaluation process from four correspondences. This finally leads to:

( total number of iterations )

s = . (14)

( number of rigid - body transf ormations )

Based on the previous experimental results, this speed-up factor is represented in
figure 6 with respect to the proportion of outliers. It shows that when the rigidity
constraint is used, RANSAC is already twice as fast with only 22% of outliers.
At 50% of outliers it is almost five times faster, and it still rises, becoming more
than ten times faster with 80% of outliers. This shows that in any situation, the
rigidity constraint not only prevents non rigid homographies, but also improves
the overall performances of RANSAC.

5Con lu on

In order to improve the results of the RANSAC algorithm in cases where the
proportion of outliers is very large, an analysis of the invalid homographies ob-
tained in such situations was performed in this paper. It led us to clarify the fact
that a homography cannot be reduced to a rigid-body transformation and that
the RANSAC algorithm is not always able to reject non rigid-body transforma-
tions. From these observations, a lightweight rigidity constraint has then been
proposed, which makes it possible to prevent non-rigid-body transformations at
a nearly negligible computing cost compared to the one needed for estimating a
homography and checking all the putative correspondences for consistency with
it. The evaluation tests have shown that a speed-up factor of more than ten
can be expected in the presence of a large proportion of outliers. While the