ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision“, Graz, 2002 
test. The null hypothesis is "the point is on the surface" 
while the alternative hypothesis is "the point is not on the 
surface". The last task updates the current estimates of the 
plane parameters by incorporating the new point into the 
current model using a sequential least squares estimator. 
After growing each patch, we verify it in terms of its size, 
roughness, and geometry. If one of these criteria is vio- 
lated, the patch is discarded and its points are reset to un- 
segmented status so that they can be segmented to other 
patches. 
2.2 Primitive Level Process 
At the primitive level, we generate surfaces by merging 
some segmented patches. The primitive level process in- 
volves constructing patch adjacency graphs, computing merg- 
ing confidence of adjacent patches, merging adjacent patches 
of high merging confidence into surfaces, and deriving sur- 
face boundaries. Each surface is identified with the interior 
points, the surface parameters, and the surface boundaries. 
The input and output of the process are summarized in Ta- 
ble 2. 
Input e A set of patches. 
Output | e A set of surfaces. 
e A set of surface boundaries. 
e A patch/surface adjacency graph. 
  
  
  
  
  
  
Table 2: Input and output of the primitive level process. 
2.2.1 Patch Adjacency Graph A patch adjacency graph 
includes segmented patches as nodes and adjacency be- 
tween the patches as arcs. Adjacency between two patches 
are assigned if at least a point of a patch is adjacent to a 
point of the other patch. Based on the types of the point 
adjacency, the patch adjacency retains three different types 
such as '2D', '3D', and ’2D only’. The 2D only adjacency 
is assigned to two patches that are adjacent to each other 
only in 2D. For example, the 2D only adjacency can be es- 
tablished between a roof patch of a building and its neigh- 
boring ground patch. The 2D only adjacency is particularly 
important since it often suggests the existence of a missing 
vertical patch between 2D only adjacent patches. 
2.2.2 Merging Confidence Adjacent patches are to be 
merged if there exists a significant evidence that they share 
the same surface parameters and roughness. The merging 
confidence represents the degree of confidence in merging 
two patches. The merging confidence between two patches 
P; and 5 is defined as: 
6 nerge (Pi, P3) = Omerge (P1 e P3) : Omerge (Pa em P1) 
where Omerge(P1, P2) is the confidence in merging ^, and 
P»; Omerge(P, — P2) is the confidence in merging P, 
into P1; Omerge(P2 — P1) is the confidence in merging 
P, into P5. Omerge(P1 — P2) is defined as the p-value de- 
termined by a test statistic of a statistical test. This test ex- 
amines whether the points of 7» are consistent with those 
of 7 in terms of the parameters of the surface fitted to the 
points and the associated fitting errors. The surface model 
can be primitively a plane model but easily extended to 
more complex surfaces such as quadratic surfaces. 
2.2.3 Merging Patches Two adjacent patches with high 
merging confidence are merged into one surface. The merg- 
ing process is summarized as follows: 
1. Construct or update the patch adjacency graph. 
2. Compute the merging confidence between every pair 
of adjacent patches. 
3. Select the pair of the highest merging confidence. 
4. If the confidence of the selected pair is greater than a 
threshold, merge the patches and go to step 1. 
5. Otherwise, quit the merging process. 
The patch adjacency graph finally updated after the merg- 
ing process is considered as the surface adjacency graph. 
2.2.4 Surface Boundaries Surface boundaries represents 
a general shape for a cluster of points included by each 
merged surface, being computed from interior points based 
on the a-shapes (Edelsbrunner et al., 1983) algorithm. Here, 
the a-shapes are generalizations of the convex hull of a 
point set. They are constructed as subgraphs of the De- 
launay triangulation. Parameter o controls the level of the 
shape details. 
2.3 Structural Level Process 
At the structural level, we organize the merged surfaces 
into perceptually meaningful surface clusters. The pro- 
cess involves identifying surface adjacent boundary edges, 
computing various perceptual cues such as connectedness, 
continuity, parallelism and elevatedness, constructing the 
graph associated with each cue, hypothesizing intersec- 
tions and corners, grouping surfaces into meaningful sur- 
face clusters, and identifying ground surface clusters and 
above-ground polyhedral structures. Table 3 summarizes 
the input and output of the process. 
  
Input e A set of surfaces. 
e A set of surface boundaries. 
e A surface adjacency graph. 
Output | e À set of surface clusters. 
e À set of intersections. 
e À set of corners. 
e À surface adjacent boundary edge set. 
e À surface connectedness graph. 
e À surface continuity graph. 
e À surface parallelism graph. 
e À set of ground surface clusters. 
e À set of above-ground structures. 
  
  
  
  
  
Table 3: Input and output of the structural level process. 
2.3.1 Adjacent boundary edges If boundary edges are 
adjacent to boundaries of other surfaces they become adja- 
cent boundary edges. Their identification is very useful at 
the structural level because some important attributes such 
as connectedness and elevatedness are based on them. 
A - 195