cloud of 3-D points having no topological relationship. There-
fore the raw laser data should be interpolated into a regular
grid on the xy plane prior to segmentation. Owing to the
quasi random distribution of the laser points the interpola-
tion errors are usually large, especially near breaklines.
ALR data acquired by the Airborne Topographic Mapper con-
ical scanner [Krabill et al., 1995] at the Commission Ill test
site in Ocean City, MD ([Csathó et al., 1998]) are used to il-
lustrate some of the problems (Figure 3). Figure 3(b) shows
the distribution of the laser points in 2D. The contour map
is created by using a TIN model based interpolation. In ad-
dition to the distribution of the laser points let us consider
the location of the laser system relative to the building. The
aircraft passed the building on its left, so the laser was firing
from the left producing illuminated footprints on the ground,
on the roof on the building and on the walls. Small segments
of two scans are marked by gray squares and circles in Fig-
ure 3(b). A few laser points are located on the wall which is
close to the sensor (left side in (b) and front of building in
(a)), and there is some occlusion on the opposite side (right
side in (b)). The distribution of the laser points on the near
side is quite irregular, probably owing to the irregular outline
of the building and the balconies (Figure 3(a)).
The surface depicted in Figure 3(c) is interpolated by using
minimum curvature spline interpolation. This method min-
imizes the total curvature and the surface is not allowed to
bend sharply. This results overshooting at corners or along
edges (Note the peaks around the roof of the building). Fig-
ure 3(d) shows the surface interpolated by using a TIN model
based linear interpolation. The TIN model provides a better,
but visually not very pleasing solution. The resulting triangles
give a tent like appearance, moreover many points interpo-
lated along the side of the building have large elevation errors
[Schenk et al., 1999].
5.3 The procedure
After the preprocessing and interpolation the data are seg-
mented by a robust sequential estimator (RSE) procedure.
The major steps of the RSE approach are summarized in
Fig. 4.
The algorithms first selects appropriate seed points that repre-
sent possible surfaces. For each nonredundant seed it chooses
the best approximation from the selection of planar and bi-
quadratic models, using a modified Akaike Information Crite-
rion. With this best model, each surface is expanded from its
seed over the entire image; this step is repeated for all seeds.
The most significant and novel features of the algorithm, the
seed selection, model choice and expand operations are em-
bedded in a loop. The procedure starts with stringent criteria
for smoothness and minimum size of the seed regions and the
thresholds are decreased in every iteration. The seed selec-
tion stops when all data is assigned to at least one surface.
The remaining steps of pruning, removing and filling are sim-
ple postprocessing heuristics. The procedure ends with or-
ganizing the regions into a complete, non-ambiguous scene
description.
5.4 Seed selection
Ideally, seed regions are selected within every independent
surface. Redundant seeds increase the computational bur-
den and risk of over segmentation, while missing seeds could
leave surfaces unmodeled. Surface fitting for region growing
starts in every seed region. There are different approaches for
International Archives of Photogrammetry and Remote Sensing, Vol. 32, Part 3W14, La Jolla, CA, 9-11 Nov. 1999
(a)
(b)
(c)
(d)
Figure 3: Interpolation of laser points. (a) Photograph of the
building, (b) Contour map of the building from laser points using
TIN model based linear interpolation, square and circle mark laser
footprint belonging to the same scan line, spiral shows the perspec-
tive center of the photograph in (a), (c) interpolation of laser data
by minimum curvature method, (d) interpolation of laser data by
linear interpolation of TIN model.
Internatio
[5
[^
Compute initia
Compute ii
Re
Ren
Figure 4: Block di:
scheme
seed selection. For
regions from the F
tures), and erodes t
remain. By a seed |
dow. In the RSE =:
used to locate smc
the largest, contig
dant seeds are elim
a loop, starting wi
minimum size of s
creased in every ite
data have been co
isolated singletons
5.5 Choosing be
The next step is to
planar and biquadi
subsection first the
tial Estimator (RSE
lection is introduce
procedure used for
Robust M-Estima
(lower variance) th
normally distribute
are only slightly les
distribution. We |
as a robust estima
we assume for the
direct evaluation o
normal distributior
estimates are obta
squares (IRLS). Le
