ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
data driven strategy) and thus less application-dependent 
although it slightly favors urban applications. 
We now summarize the overall process. From a given 
set of irregularly distributed 3D surface points we com- 
pute perceptual organization at the signal, primitive and 
structural levels. At the signal level, we organize the raw 
points into spatially coherent surface patches. Then, at the 
primitive level, we merge the patches into co-parametric 
surfaces and identify surface boundaries. Finally, at the 
structural level, we group the surfaces into perceptually 
meaningful surface clusters and derive intersections, cor- 
ners, and the ground surface from them. 
2.1 Signal Level Process 
At the signal level, we organize raw 3D points into spa- 
tially coherent patches. The signal level process involves 
establishing and refining adjacency among points, select- 
ing seed patches, and growing patches from the seeds. Each 
patch is identified with the interior points and the parame- 
ters of a plane approximated to the points. The input and 
output of the process are summarized in Table 1. 
  
Input € A set of points. 
Output | e A set of patches. 
e À point adjacency graph. 
  
  
  
  
  
Table 1: Input and output of the signal level process. 
2.1.1 Point Adjacency Adjacency is based on the dis- 
tance between points. Five types of adjacency are intro- 
duced. First, 2D’ adjacency is assigned to any pair of 
points if the horizontal distance between the points is less 
than a given threshold. For a 2D adjacent pair, '3D' ad- 
jacency is assigned if the 3D distance is also less than the 
threshold and "2D only’ adjacency is assigned otherwise. 
3D adjacent pairs are further classified into *3D refined’ if 
they pass a refining process and 3D unnecessary’ other- 
wise. 
The refining process is to identify some unnecessary ones 
from 3D adjacent pairs. For example, a point on the top of 
a car is undesirably identified to be adjacent to other point 
on the ground once the distance between them is not so 
large. Such unnecessary adjacent pairs can be identified if 
other pairs within the same area are statistically consistent 
except them. The refining process is summarized as: 
1. Select a point as a center and collect all 3D adjacent 
points. 
2. Fit a plane to the collected points using a robust esti- 
mator such as Least Median Squares Estimator (Koster 
and Spann, 2000). 
3. Classify the points into inliers and outliers with re- 
spect to the robustly fitted plane. 
4. If the center is an outlier, eliminate the adjacency be- 
tween the center and every other point. Otherwise, 
eliminate the adjacency between the center and every 
outlier. 
5. Repeat step 1 to 4 for every point. 
Based on the adjacency assignment, we establish a point 
adjacency graph, where a node incorporates a point; an arc 
links a pair of adjacent points, retaining the type of the 
adjacency. 
2.1.2 Seed Patches Seed patches serve as initial patches 
from which planes start to grow. Hence, seed patches should 
be as complete and homogeneous as possible. Here, com- 
pleteness implies that all the actual planes should grow 
from seed patches; homogeneity indicates that seed patches 
should satisfy planar surface models. To accomplish com- 
pleteness and homogeneity, we propose the following se- 
lection procedure: 
1. For every point in a data set, generate a small patch 
by clustering a fixed number of neighboring points. 
2. Fita plane to each patch and compute the fitting error. 
3. Establish an ordered-list (heap) of the seed patches so 
that the patch with the minimum fitting error will be 
fetched first. 
2.1.3 Patch Growing Patches are growing from seed 
patches, followed by verification. The growing process 
comprises four main tasks: 
1. Fetch a non-corrupted seed patch. 
2. Find the nearest point to the current patch. 
3. Perform a hypothesis test to examine whether the point 
is statistically consistent with the current patch. 
4. After passing the acceptance test, the current patch is 
updated accordingly. 
The first task keeps fetching a seed patch from the seed 
heap until a non-corrupted one is found, where a corrupted 
seed is one that contains one or more points that have al- 
ready been assigned to another patch during the previous 
growing processes. Also, an arc heap is initially created 
with the arcs of 3D refined types in the point adjacency 
graph, which link at least a point of a seed patch. This heap 
is constructed so that the arc of the minimum length will be 
fetched first, where the length is defined as the distance be- 
tween two points linked by the arc. The second task finds 
the nearest point to the current patch among the external 
points adjacent to at least an internal points based on the 
3D refined adjacency. An arc in the arc heap connects two 
internal points, or one internal point and one external point. 
Hence, one should repeatedly pop the shortest arc from the 
heap until an arc connected to an external point is found. 
Then, the external point is the nearest point to the patch. If 
the heap becomes empty, or the length of the shortest arc 
exceeds a threshold, the growing process terminates. The 
third task statistically determines whether the nearest point 
is consistent with the current patch based on a hypothesis 
A- 194