ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
2.3.2 Surface Connectedness Surface connectedness is 
defined as a random variable indicating the confidence in 
the hypothesis that two surfaces are connected. This re- 
tains continuous and non-continuous types, according to 
the changes of the surface normals near their adjacent bound- 
aries. The non-continuous types are further classified into 
convex and concave types. Connectedness with a type is 
computed from every pair of the 3D adjacent surfaces iden- 
tified from the surface adjacency graph. 
2.3.3 Surface Continuity Continuity indicates how 
smoothly two surfaces can be connected. Although two 
surfaces are not connected, they can be continuously con- 
nected through an imaginary intermediate surface between 
the surfaces. Then, the continuity between the surfaces 
is high while the connectedness is very low. This is the 
main difference from connectedness. In addition, contin- 
uously connected surfaces show high continuity but non- 
continuously connected surfaces show low continuity. 
2.3.4 Surface Parallelism Parallelism is defined as a 
random variable indicating the confidence in the hypothe- 
sis that two surfaces are parallel. It is associated with the 
similarity of the surface normals, the closeness of surfaces 
in the normal direction, and the area of the overlap of the 
surfaces. 
2.3.5 Surface Elevatedness  Elevatedness is an attribute 
of a surface that indicates how much elevated a surface is 
than adjacent surfaces along the surface boundaries. Ele- 
vatedness is a good indicator to identify ground surfaces 
from a set of surfaces since a ground surface is usually less 
elevated comparing to its adjacent surfaces. For example, 
the average elevation of a ground surface can be higher 
than a roof of building. However, if we compare eleva- 
tions only along adjacent boundaries, the ground surface is 
much lower. Hence, elevatedness is a promising attribute 
for the identification of ground surfaces. 
2.3.6 Perceptual Cue Graphs Based on connectedness, 
continuity, and parallelism computed from a set of sur- 
faces, we establish surface connectedness, continuity, and 
parallelism graphs. 
2.3.7 Intersections An intersection can be hypothesized 
by every pair of two surfaces connected non-continuously. 
This hypothesis is then confirmed if the straight line inter- 
sected by two surfaces is close to the adjacent boundaries 
of the surfaces. The ending points of the confirmed inter- 
section are deliberately determined along the straight line. 
2.3.8 Corners A corner can be derived by every set 
of three surfaces connected non-continuously. To identify 
such sets, we derive so-called tri-arcs from the connected- 
ness graph, where a tri-arc is assigned to three nodes con- 
nected to each other. A tri-arc invokes a corner hypothesis. 
This hypothesis is confirmed if the corner is close to the 
adjacent boundary edges of the three surfaces. 
2.3.9 Grouping Surfaces Surfaces are grouped into sur- 
face clusters so that all the surfaces originating from the 
same object (ex. at least the ground) is organized into the 
same cluster. The grouping criteria is designed to cluster 
two surfaces that retain high connectedness and low elevat- 
edness between them. This design is based on two obser- 
vations, that is, 1) highly connected surfaces must belong 
to the same object; 2) vertical discontinuities hardly exist 
between the surfaces originating from the ground. Every 
arc from the connectedness graph provides a surface pair to 
be examined for grouping with the grouping criteria. The 
grouping algorithm is summarized as follows: 
1. Establish a union-find structure where every surface is 
assigned to a separate cluster. This structure supports 
efficient operations of union of two clusters and find 
the cluster of a surface. 
2. Push all the arcs of the connectedness graph into a 
heap, where the heap stores the arc of the highest con- 
nectedness at the head. 
3. Pop the arc of the highest connectedness from the 
heap and identify the two surfaces linked by the arc. 
4. If the type of the connectedness between the surfaces 
is concave, go to step 9. 
5. If the connectedness is less than a threshold, go to 
step 10. 
6. Find two surface clusters including each surface. If 
they are the same, go to step 9. 
7. Compute elevatedness between the clusters. If its ab- 
solute value is is greater than a threshold, go to step 9. 
oo 
. Union of the two clusters. 
. Repeat steps 3 to 8 until no more arcs remain at the 
heap. 
10. Identify the cluster assigned to every surface using the 
union-find structure. 
2.3.10 Ground Surface Clusters We compute the ele- 
vatedness and the area for every surface cluster and iden- 
tify the cluster of the lowest elevatedness and the largest 
area as ground surface clusters. 
2.3.11 Above-ground polyhedral structures Above- 
ground polyhedral structures such as buildings may retain 
concave connectedness and significant elevatedness in a 
structure. Hence, after excluding the clusters identified as 
the ground, we further group the surface clusters with re- 
laxed criteria comparing to those in section 2.3.9. Then, 
each cluster is identified as an above-ground polyhedral 
structure. 
3. IMPLEMENTATION AND EXPERIMENTS 
3.1 Implementation 
We implemented the proposed approach as an autonomous 
system that generates a three-level perceptual organization 
A- 196