974 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part Bl. Beijing 2008 
1.2 Heuristic search for corresponding planes 
The intersection of planar surfaces using Eq. 3 and Eq. 4 
requires that a correspondence between the planes in every pair 
of successive scans is established. The correspondence is 
formulated as a combinatorial problem, and solutions to this 
problem are sought through a heuristic search. Suppose that the 
segmentation algorithm extracts n planes in the first scan and 
n’ planes in the second scan of a pair of successive scans. The 
number of possible ways to choose r corresponding planes 
from the two sets of planes can be expressed as: 
building of the Aerospace Engineering Faculty of TU Delft. 
The test was carried out in an area of approximately 2x5x3 
n = c: • Pf 
n\ ri\ 
r\(n-r)\ (n'—r)\ 
(5) 
where C and P denote combination (unordered selection) and 
permutation (ordered selection) functions respectively. As 
mentioned before, the selection of r = 3 planes is sufficient for 
the intersection and position determination. However, to be 
able to find possible incorrect intersections, it is preferable to 
choose r = 4, and perform a least squares estimation of the 
intersection point. To reduce the number of combinations, 
extracted planes are sorted according to their size, and only the 
top 10 largest planes are used in the search. With these settings, 
the search space for finding 4 corresponding planes in two sets 
of 10 planes will contain 1058400 combinations. 
A brute force approach to the intersection of all the possible 
combinations will impose a great computational cost. To avoid 
this, it is desirable to perform a heuristic search for correct 
combinations by exploiting intrinsic constraints of the problem. 
Such constraints have been successfully used in the past to 
reduce the computational cost of combinatorial problems 
(Khoshelham and Li, 2004; Brenner and Dold, 2007). In this 
paper, we use the relative orientation of the corresponding 
planes as a heuristic to guide the search. The heuristic is based 
on the fact that the scanner rotation from one scan to another 
results in a same change in the orientation of the normal 
vectors in a set of corresponding planes. The comparison of the 
orientation of the normal vectors can be performed very 
efficiently in a reasonably small amount of time. By ruling out 
the combinations that exhibit an inconsistent change in the 
direction of the normal vectors, the search space can be greatly 
reduced to only a few correspondences (often 10-20). 
The intersection procedure is performed for all the remaining 
correspondences. The mean residual of the observations in the 
least-squares estimation of the intersection point is used as a 
constraint to reject the false intersections. After false 
intersections are rejected, the median of the remaining points is 
taken as the final intersection. The use of median is 
advantageous because of the possibility of yet having a few 
outliers in the results. The outliers might be the result of errors 
in the parameters of the extracted planes, or the existence of 
nearly parallel planes (especially the floor and the ceiling) in 
the sets of corresponding planes. Using the median ensures that 
the final intersection point is not biased by the possible outliers. 
EXPERIMENTAL RESULTS 
The proposed indoor navigation method was tested on a set of 
range data collected in the corridor of the OLRS section at the 
Fig. 5: Data and extracted features of the test scans. Left 
column: intensity images; middle column: range images; right 
column; segmented range images.