In: Stilla U, Rottensteiner F, Paparoditis N (Eds) CMRT09. IAPRS, Vol. XXXVIII, Part 3/W4 — Paris, France, 3-4 September, 2009 
191 
(1) Select the next line segment a in the current scan line. 
(2) Set the label of a to a new and increasing labeling 
number. 
(3) Successively compare line segment a to each line 
segment b of several previous scan lines. If Euclidean 
distances, disparity of normal direction, and the measure 
of coplanarity d p are found to be smaller than predefined 
thresholds, go to step (4). Otherwise go to step (5). 
(4) Set the label of a to that of b. 
(5) Continue with (1) until all line segments a are processed. 
The above steps summarize the main ideas of our method. In 
fact, we apply an extended two-pass approach to improve 
detection of connected components. More details on this topic 
can be found in (Hebei & Stilla, 2008). Figure 7 illustrates the 
procedure. First, each line segment is initialized with a unique 
label. Coplanar line segments that are found to lie near to each 
other are linked together by labeling them with a common 
labeling number. This process is repeated until all new line 
segments are labeled. Surfaces are represented by the emerging 
clusters of line segments with the same label (Figure 8). 
Figure 8. Result of scan line grouping for measured ALS data. 
3.4 Feature extraction 
Each cluster of connected straight line segments can be 
characterized by a set of features which are described in this 
section. For a given cluster of connected line segments, let C 
denote the set of associated 3D data points. The centroid of C 
can be computed as the sum of all points divided by their 
number, and C can be translated towards the origin: 
The eigenvectors of the covariance matrix C 0 'C 0 are the 
principal components of C. The normal direction n 0 is given as 
the normalized eigenvector that corresponds to the smallest 
eigenvalue. The value of the smallest eigenvalue of the 
covariance matrix, divided by the number of points, is 
influenced by the curvature and the scatter of C. If it is near 
zero, this indicates a planar surface. The features used to 
identify matching surfaces in the model data and the results of 
scan line analysis are: centroid, normal direction, and the 
normalized eigenvalues of the covariance matrix. These features 
can even be used to classify and remove irregularly shaped 
surfaces, e.g. the ground level in Figure 8. 
3.5 Registration of ALS and model data 
Even without considering terrain-based navigation, we assume 
that the sensor position is known approximately with standard 
GPS accuracy. In case of GPS dropouts, the IMU drift will not 
distort the positioning exactness dramatically. The relative 
accuracy provided by the INS measurements still ensures 
consistent ALS measurements over limited periods of time, 
depending on the quality of the INS system. In some situations, 
the absolute navigational accuracy needs to be improved. 
Examples are low-altitude flights of helicopters at night or 
preparation of landing approaches during rescue missions at 
urban areas. 
If the helicopter is equipped with a LiDAR sensor, ALS data 
can be collected for several seconds in order to scan the urban 
area in front of the helicopter (Figure 8). Surfaces that are 
instantaneously detected in these data can be compared and 
matched to the existing database of the terrain (Figure 4). The 
features that are used to establish links have been described in 
section 3.4. First, the displacement of the centroids has to fall 
below a maximum distance. Second, the angle between the 
normal directions should be small (e.g. <5°). Third, the 
normalized eigenvalues of the covariance matrix C</C 0 should 
be similar. Large planes are likely to be subdivided into 
dissimilar parts, but we are not interested in finding 
counterparts to all planes. It is sufficient to have some (e.g. 20) 
correct assignments. Figure 9 illustrates an exemplary pair of 
associated surfaces. The offset in position and orientation 
indicates the inaccuracy of the navigational data. 
Figure 9. A pair of corresponding planes in model M and 
currently acquired ALS data D. 
In this section, we determine a rigid transformation (R,t) to 
correct these discrepancies. Let £ M denote the planar surface of 
the model A/that is associated with the plane E D in the currently 
collected ALS data D. The respective Hessian normal form of 
these planes is given by the centroids and the normal directions 
n M , n o (Figure 9). Since both planes should be identical after 
registration, the centroid of E D should have zero distance to E M . 
Moreover, the two normal vectors should be equivalent if they 
are normalized to the same half space. In addition to these 
conditions, we can assume that errors of orientation will not 
exceed the range of ±5°. That enables us to linearize the 
equations: