Stephan Heuel 
  
Selecting Hypotheses using Topology: We consider all pos- 
sible pairs (G, D) of grouped sets G from 4.3 and directions ——b»- 
D. With the same argument as in 4.3, we can compare the » C C 
neighbored 2D-regions A^ of G with the neighbored 2D- Ss 
regions &5 of the direction D. If the intersection of these 5 C? ; Déc: 
2D-region sets is not empty, we accept this pair for the sub- C; : C 
sequent geometrical test. 
Testing Hypothesis using Geometry: From the grouped set 
of corners G we can compute an averaged plane £(A)c with Figure 4: The 2-cori nes Ct and C3 are coplanar, but 
an averaged covariance matrix 3:44. From the direction D nal with C One direction D € C3 is coplanar to 
we can compute a line L with X77. If the geometrical test C1 and C5. Black arrows indicate directions within a 
does not reject L € £c, we include D to the grouped set of group. 
corners G. 
4.5 Grouping Directions to 3D Edges 
At this stage of grouping we know, which corners and directions belong to the same surface. Now the task is to connect 
the corners C? and directions D :— C' so that the connections are (estimated) 3D edges of the polyhedral surface. 
Selecting Hypotheses using Topology: Each direction D € C? of a corner C? resp. a direction D from 4.3 refers to a 
set £'(D) of 2D image edges. Again, using the analysis of relations of 2D and 3D features and aggregates in 2.3, a pair 
of directions ( D1, D3) belongs to the same 3D edge if they share at least one 2D edge, i.e. £'(D1) (1 £'(D3) z 0. Note 
that we do not test all directions in the scene, but only those belonging to the same grouped set G of corners. 
Testing Hypotheses using Geometry: It is still possible that the topology selection above results in pairs (Dj, D3) of 
3D-direction, which are not collinear to each other, e.g. when having an accidental view. Therefore we test the two lines 
Ly, Ly with 9; ;, induced by the directions: L4 — L». If a pair of direction also succeeds this test, we assume to have a 
polyhedral edge between them. 
4.6 Generating 2-Corners from 3D Edges 
The step described in 4.5 may already result in a complete boundary description of a polyhedral surface. This boundary 
description can be interpreted as an undirected graph. Then the boundary is called complete if the graph consists of one 
cycle. However, if there is no cycle in the graph, we might be able to add a vertex and replace two graph-edges in order 
to get a cycle. An addition of a vertex is the same as estimating a new 2-corner on the surface; replacing two edges is the 
same as grouping the two directions of the new 2-corner to two new 3D-edges of the surface. We can do this by computing 
the intersection of direction pairs ( D1, D5), where the directions D; refer to vertices of arity 1. We only consider those 
intersections which lie on the directions; its projection in the images must be within the image bounds. If there is more 
than one possible intersection for one direction, we take the one closest to vertex of arity 1. 
4.7 Generating 3D Edges from 2D Edges 
Now we still might have an incomplete boundary of the surface, e.g. a U-shaped boundary, where two directions are 
parallel to each other. We do not have 3D information to fill the gap at this stage of the analysis, we'd have to go back to 
the images and project appropriate 2D edges (selected by an anlaysis of the ‘ FAG’) to the planar surface. The we have to 
find the intersections of the projedted 2D edge with the parallel direction. This has currently not been implemented yet. 
As a first guess we just close a U-shape boundary by connecting the vertices of arity 1. 
S RESULTS 
We have tested our grouping approach described in sec. 4 on one synthetic scene with two polyhedra (cf. fig 5) and 
with 11 aerial scenes containing one building each (cf. figs. 6 and 7) without changing any parameters. Alltogether 110 
n-corners have been generated, containing 232 directions. 
: : m" a+03 : : 
We excluded those directions where the averaged standard deviation o—; :— V ME of the direction angles o and / 
exceeded 10°, thus rejecting bad observations. The algorithm found 62 polyhedral surfaces. Table 3 documents the effect 
of topological selection prior the geometrical test, the reduction rate in the three grouping stages in sec. 4.3—4.5 is less than 
40%. It can also be seen that the topological test on shared 2D lines sec. 4.5 is more reliable than the ones of intersecting 
2D regions in 4.3 resp. 4.4, cf. third column. 
  
402 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.