Stephan Heuel
was emphasized in the context of object recognition. On the other hand, crisp and qualitative geometry in reconstructing
polyhedral scenes was the starting point for scene reconstruction (Clowes, 1971).
There are two basic problems to be tackled:
1. There appears to be no commonly accepted concept for topological relations in computer vision which can be used for
reasoning. The setup in (Rothwell et al., 1996), though broard in scope, does not support the topological reasoning based
on open sets.
2. The uncertainty of geometric entitites is a handicap for nearly all grouping systems, but needs to be conceptually
embedded into the grouping processes. The difficulty is the aquisition and use of appropriate uncertainty measures as e. g.
propagated by (Kanatani, 1995).
This paper adresses both problems: Its goal is to describe the topological and geometric concepts used in our system.
As topological reasoning is computationally far superior to geometric reasoning, we try to always exploit topological
knowledge before applying geometric checks. In order to minimize the number of control parameters for grouping the
uncertainty of the geometric features is tracked through the system in a consistent manner using classical error propagation
from 2D features to 3D structures. The feasability of this setup is demonstrated on real data, showing the usefulness of
using topology and the advantage of exploiting the statistics of the geometric entities.
2 TOPOLOGY OF POLYHEDRA, THEIR IMAGES AND IMAGE FEATURES
2.1 Polyhedral Surfaces and their Images
Due to occlusions and the incompleteness of any feature extraction polyhedral objects can only be recovered partially from
images. Without specific domain knowledge, e.g. restricting only the form of polyhedra, image analysis can reconstruct
sets of polyhedral surfaces. Polyhedral surfaces are connected subregions of the surface of a polyhedron.
The structure of such surfaces is given by a set of well known
constraints, inherited from polyhedra, especially concerning
the neighbourhood relations between points P, edges E and
regions R. These atomic elements are treated as open con-
nected sets of dimension 0, 1 and 2 being the basis for topo-
logical neighborhood relations (Dold, 1972). The formal model
is shown in fig. la.
If we first assume the faces of the polyhedron to have constant
albedo and the illumination to be homogeneous, an ideal pro-
jection with infinite resolution leads to a Mondrian-type im-
age, with points P', edges EF" and region R’ showing relations
with the same generic restrictions concerning the neighbor-
hood relations. Occlusions yield missing features and missing
and incorrect relations.
Figure 1: a) shows the neighborhood relations between-
points (P), edges (E) and regions (R) of a polyhedral
surface. The multiplicity of the relations is constrained,
given as range (e. g. 1..n). The same generic constraints
hold for the features P', E' and R' of the ideal image. b)
shows the possible relations between the observed image
2.2 Observable Image Features features P', E' and R' (0..n means optional).
We assume this ideal image is tried to be recovered with some feature extraction method. We use the method described
in (Fórstner, 1994, Fuchs, 1998) in general yielding points P', edges E', and regions R’ which are assumed to have no
overlap in the image plane. We also obtain neighborhood relations N ( F7, Fy), directly by analysing the Voronoi diagram
of all features F' (cf. fig. 6). There is no guarantee that all features or relations of the ideal projection can be detected.
Much more, neighborhood relations may occur between features of the same type. This situation is depicted in fig. 1b,
where no constraints on the number of neighborhoods can be found.
2.3 Relations between 3D Aggregates and their Generating Image Features
Starting from atomic features we may derive feature aggregates A
in order to reach a higher level of aggregration. The rules for this . .
aggregation process generally result from the image analysis task. N |
The aggregation process can take advantage of the neighborhood Wes . ej.
relations. As we want to reconstruct polyhedral surfaces we are in- À \ P
terested in basic 3D aggregates, namely point induced corners C, 5
edge induced wings W and region induced meshes M as shown in
fig. 2. These aggregates (A) may refer to the polyhedral surface rep-
resenting local surface structures, to its ideal image ( A’) triggering
the grouping process or to the observed image (A^) yielding a higher
level of symbolic image description.
Figure 2: shows basic aggregates, corners, wings
and meshes. Corners are most likely to show the
same topology in the image (cf. (Clowes, 1971)).
398 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
