ul 2004
ease of
roved to
ANSAC
xtensive
1997).
| Second
'ation of
tis
yi Zi
Zi
/
| for the
es show
liers are
this be-
2
Ye.
where p
mum at
ns using
ates the
nization
not have
ze set of
ponding
as qual-
with the
a model.
iteration
set ofn |
r failure
“outliers
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
In the case of the LMedS estimator o = 0.5, but other values may
be used according to a priori knowledge on the outlier proportion.
The table 1 gives the number of iterations for different values of
the probability of failure. The complexity of the LMedS is rela-
tively high: O(Nlog(N)), since the residuals of all the features
should be sorted.
Preitenct4^ 10-3. 1,107 2 T dz Loco 10
Tate 18 35 52 70 87
Table 1: Minimum number of iterations for an expected proba-
bility of failure.
p
Figure 4: Two views of the 3D reconstruction of 2 regions using
the LMedS approach.
The RANSAC algorithm: the Random Sample Consensus has
been proposed for the robust estimation of shape parameters (Fis-
chler and Bolles, 1981). It is very similar to the LMedS. As prin-
cipal difference, the RANSAC requires the operator to give a tol-
erance threshold to reject a point as outlier for a given model. The
outline of the algorithm is the following:
e select n features randomly, and estimate the corresponding
model,
e count the number of features which are out a given tolerance
€ to the model,
e repeate previous steps £ times and select the model with the
minimum number of outliers.
The RANSAC paradigm can be considered as the dual approach
to the LMedS estimation: the RANSAC algorithm optimizes the
proportion of features which are within a given error to the model,
while the LMedS optimizes the error for a given proportion of
features. Both have the same probability of failure. The figures 4
and 5 indicate a similar robustness against outliers for the estima-
tion of planar surfaces. The advantage of the RANSAC over the
LMedS is its complexity, which is linear with the total number of
features.
Figure 5: Two views of the 3D reconstruction of 2 regions using
the RANSAC approach.
1045
Choice of the estimator: among the three approaches presented
above, we retained the RANSAC algorithm, since it has the ad-
vantage to be robust to the presence ouf outliers in the data and
to have a complexity which is linear with the number of observa-
tions.
The presence of outliers in the data requires some explanation.
In the context of 3D plane estimation, the outliers in the image
regions have three principal origins:
e some laser points correspond to small structures which are
discarded in the segmentation because of the minimum size
of the regions: chimneys on the roofs, cars on the streets,
ste,
e the segmentation is far to be perfect and presents over and
under-segmentation problems, which are clearly visible on
the figure 1,
e a bad localization of the laser point cloud compared to the
aerial image generates mis-matchings between the laser points
and the segmented regions.
The two first sources of outliers correspond to local artifacts in
the laser data or in the image segmentation. They are supposed
to have negligible effects compared to the third origin of outliers.
3 REGISTRATION AND 3D RECONSTRUCTION
3.1 Evaluation Function
The quality of the 3D reconstruction being used to determine the
relative position of the laser points and the optical image, an eval-
uation function for the 3D reconstruction is needed, whose opti-
mum corresponds to the true relative position. Obviously, the
evaluation function should be directly related to the technique in-
volved in the 3D reconstruction. Since we made the choice of the
RANSAC approach, the global proportion of outliers calculated
with all reconstructed surfaces will serve for the evaluation.
Let R] = {rs,i = 1...M} be the partition of the aerial image
provided by the segmentation algorithm, £ the set of 3D laser
points and f the deformation to be evaluated. We will abusively
use the notation I(p) for the projection of a 3D point p in the
image plane / using the collinearity equations. Then the set of
laser points whose projection in the image after the deformation
f falls in a region r; of the segmentation is noted:
£p, — ipe £/I(fp)erij
The plane estimated with the RANSAC procedure using the 3D
points in L¢ ,, is called Ps ,,.
The criterion for the evaluation of the deformation f can then be
written as:
> card {p € Lj, /dist(f(p), Ps,r;) > €)
ri€R;
(f) =
€ s eard (£y,
ri€Rr;
where dist(p, P) is the Euclidian distance between the point p
and the plane P, and e is the tolerance error used in the RANSAC
procedure for the estimation of the planes.
