e given 
. non- 
om the 
  
  
  
  
  
  
  
  
  
es 
nverse 
Stephan Heuel 
  
4 RECONSTRUCTING POLYHEDRAL SURFACES 
41 Generating 3D Corners 
The corner reconstruction, cf. (Lang and Fôrstner, 1996), starts with selected image aggregates having the stuctural prop- 
erties of 3D corners and thus probably being corners ' C' in the i-th image. These image corners ! C" are selected by point 
induced feature aggregation using the extracted features ' F'and their mutual neighborhood relations ! N^ - N( F/,* F;) 
collected in the graph FAG’, cf. (Fuchs, 1998). Multi image correspondence analysis establishes an image corner corre- 
spondence evaluating the structural similarity of the image corners with respect to epipolar geometry. This correspondence 
set forms the basis for the transition to initially derived 3D corners C being corner hypotheses. These hypotheses have to 
be verified by multi image parameter estimation using all image features F which support the hypotheses simultaneously. 
For verification the residuals of parameter estimation are used. Each n-corner C™ requires 3 + 2 - n geometric parameters 
g being the three coordinates of the point vector of the corner point Py and two parameters for each of the n edges Fj 
of the n-corner, being the direction angles o; and the azimth 3. 
Besides the optimal estimates g of parameters the parameter estimation also gives their covariance matrix 355. which 
is used to propagate the uncertainty of the corner reconstruction during 3D grouping. In order to have a link to the 
above mentioned geometric reasoning (sec. 3), we actually store the n + 1 3D-points being the corner point P, and 
virtual points P,(X + Rj) along the corner edge direction which are given by the normalized direction vectors Rj = 
(cos o, cos B, , sin o cos B, sin B; ), determined from the angle parameters a, and 9, of the corner edge Fj. Starting 
with the covariance matrix 3:55, one can easily derive the covariance matrix X, of the n -- 1 points by error propagation. 
Thus triplets of points are used for deriving corner planes ¢,, (Am) (sec. 4.3) spanning the regions R,, including the 
corresponding covariance matrix X 4,, A,, . 
4.0 3D-Grouping 
Now we want describe our approach to derive a description of polyhedral surfaces from the computed corners C" derived 
in 4.1. The goal of the first two steps of the proposed grouping approach is to find those 3D entities, namely 2-corners and 
1-corners (furtheron called directions), which belong to the same polyhedral surface. Starting from the set of n-corners 
C" = (P,E,..., Ep, Ry,... By) with m = (3), we generate a set of m 2-corners C? — (P, F1, Ra, R()) for each 
n-corner C". Note that every 2-corner is neighbored to at least one region R which lie on a unique plane c. 
4.3 Grouping 2-corners of Surfaces 
For grouping coplanar 2-corners we have to test (5) pairs of corners (C3, C;, ), where & is the total number of 2-corners. 
If we would only apply a geometrical test on coplanarity, we might group corners, which actually refer to different 
polyhedral surfaces but are accidentally planar (see example 5). Furthermore, solely testing coplanarity can be quite time 
consuming, depending on À and the time-behaviour of the geometrical test. Therefore we first exploit the topology of the 
underlying images 7, namely the relations of the FAG', cf. 2.3, before applying a geometrical test. Using topology is most 
likely not as time-consuming as using geometry, since it is only a look-up on the known data. 
Selecting Hypotheses using Topology: Here we apply the analysis of relations of 2D and 3D features and aggregates 
as described in 2.3. A pair of corners (C7, C2) belongs to the same mesh (i.e. a 3D polyhedral surface including its 
boundary, cf. 2.1) if they are both neighbored to the same 3D-region, i. e. they are related in the A AG. This relation in 3D 
also can possibly be found in the relations of the FAG' of the images. We can use this fact to select those pairs of corners 
satisfying the following condition: suppose £1 resp. £5 to be the set of image edges inducing the corners Cf resp. 2. 
These image edges again are neighbored to a set of image regions R resp. RS of all images. If the intersection R, N RS 
is not empty, we can infer the hypothesis that the 3D-edges of the corners C7, C7 share at least one 3D-region. 
Testing Hypothesis using Geometry: We now take the selected pairs of corners from 4.3 and group them with respect 
to coplanarity. Since the two corners are statistically uncertain, we apply the method described in sec. 3: we compute the 
plane e, resp. £2 of the 2-corners C? resp. C2 and their covariance matrices X4, 4, resp. 3X 4,4, and test the condition 
€, = €». If this is true, we assume that the two 2-corners belong to the same polyhedral surface. Testing this for all 
selected cornerpairs, we obtain a number of grouped sets G = {Gy} = {U C2} of 2-corners, which are identified to 
belong to the same surface. 
4.4 Grouping Directions of Surfaces 
A direction is a 1-corner D :— C! — (P, E), generated from an n-corner, similar to 4.3. In this step we want to include 
those directions, which belong to the surface, but have not been covered by the above grouping process. This is possible 
as one can see in fig. 4. To find those directions D, we again first apply a selection based on topology before geometrically 
testing planarity. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 401