CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation
multimodal distribution. There, laser points at ground level
appear as the lowest distinct peak. Such positions are then used
as seed points for the region growing procedure, which collects
all points falling below a certain slope. The necessary search
operations are accomplished by means of the k-d tree data
structure. In general, this method may misclassify some points
(e.g. inner courtyards), but this is negligible for our application.
An overview of advanced methods for bare-earth extraction can
be found in (Sithole & Vosselman, 2004).
The main step of the model creation is the extraction of planar
features from the remaining 3D points. Remarkably, the applied
segmentation method is almost identical to the algorithm used
for detection of straight line segments in the scan line data,
except for the terms line/plane and the different data structure.
Similarly, geometric features of the extracted shapes have to be
computed in both the model and the on-line results. These
topics are described in sections 3.2 and 3.4, respectively.
Figure 4 gives an impression of the derived model data. The
underlying point cloud is composed of four partial scans of the
terrain (different aspects).
Figure 4. Partial view of the database (model) with ground level
(blue) and identified planar patches (red).
3.2 Scan line analysis of airborne LiDAR data
perpendicular feet of the two outermost inliers. Figure 6 shows
detected straight lines for an exemplary scan line, depicted with
a suitable color-coding according to the normal direction.
(1) Choose an unprocessed position / at random among the
available scan line data in the array A.
(2) Check a sufficiently large interval around this position i for
available data, resulting in a set S of 2D points.
(3) Set the counter k to zero.
(4) If S contains more than a specific number of points, go to
(5). Otherwise mark this position / as discarded and go to
step (14).
(5) Increase the counter k by one.
(6) Perform a RANSAC-based straight line fitting with the 2D
points in the specified set S.
(7) If the number of inliers is low, mark the current position i
as discarded and go to step (14).
(8) Obtain the Hessian normal form L: (x-p)-no = 0 and push
the current position i on a stack (LIFO).
Region growing
(9) Pop the first element j off the stack.
(10) Check each position in an interval around j, which has
not already been looked at, whether the respective
point lies sufficiently near to the straight line L. If so,
push its position on the stack and include the 2D point
in a new set S'.
(11) While the stack is not empty, go to (9). Otherwise
continue with step (12).
(12) If the counter k has reached its predefined maximum (e.g.
two cycles), mark all positions of points in S' as processed
and determine the regression line to SStore the
perpendicular feet of the two outermost points to define
the straight line segment and go to step (14). Otherwise
continue with (13).
(13) Go to step (4) with the new set of points S:=S‘.
(14) Repeat from (1) until all points are classified.
Figure 5. Procedure for RANSAC-based shape extraction
(example: detection of lines in a set of 2D points).
During on-line processing, the analysis of geometric features is
performed directly on the scan line data. Most parts of typical
buildings will appear as local straight line segments in the 2D
Cartesian representation, even if the airborne laser scanner is
used in oblique configuration (Figure 1). The RANSAC
technique is used to locally fit straight line segments to the scan
line data. As mentioned in section 3.1, the algorithm described
below can be modified to accomplish segmentation of planar
surfaces in a 3D point cloud. This is simply done by replacing
the scan line index with the k-d tree data structure, and by
turning attention to 3D planes instead of 2D lines.
An overview of the proposed method is shown in Figure 5.
Within each iteration step, we randomly select a position in the
array A of scan line data points and try to fit a straight line
segment to the neighboring data. The RANSAC technique
provides a robust estimation of the line segment’s parameters. If
the fitted straight line is of poor quality, the data associated with
the current position is assessed as clutter. Otherwise, we try to
optimize the line fitting by looking for all data points that
support the previously obtained line, which is done in steps (9),
(10), and (11). These steps actually represent a “line growing”
algorithm. The local fitting of a straight line segment is repeated
with the supporting points to get a more accurate result. The
end points of each line segment can be found as the
-700 -
E -720 -
^ -740 —
ro
£ -760 •
-780 -
w
-100
AaVV-..^
50 100
Scan x [m]
150
200
250
Figure 6. Detected straight line segments in a typical scan line.
3.3 Grouping of line segments
The end points of each line segment are georeferenced to result
in correct positioned straight 3D lines. In this section, we
describe a procedure to connect coplanar line segments of
consecutive scan lines. Let P„ P h and P k be three of the four
end points of two line segments in different scan lines. The
distance of the fourth end point P m to the plane defined by the
three others is a measure of coplanarity. We define a distance d p
as the sum of all four possible combinations:
d __y\{P-Pn,) T (P;-P^{P;-P k )\ (3.1)
||U-p,-)*(/>,-a )||
The algorithm to find corresponding line segments in a
sequence of scan lines can be summarized as follows:
