>
>
ard scheme,
nutually ex-
es.
1e ability to
, photomet-
d stereo, to
ribing com-
der control.
-D and 3-D
rework, and
nework and
rely on ex-
in matching
> one draw-
occluded or
ges, it may
is often, for
ss of meth-
te along the
pe extended
d geometri-
late based)
/e been ob-
tions [Grün
ation-based
e. We pro-
t matching
methods in
ge) and are
g an "edgi-
ess measure
. Geometric
ce the num-
1as a virtual
l.
ng the pho-
5.2 after a
photometric
s that per-
s should be
mputed 3-D
segments of the house in Fig. 6. The details of the algorithm
are described in [Bignone 1995].
A more classical approach in stereo matching is under de-
velopment. This approach simultaneously matches the edges
extracted from the four images. To cope with both broken
edges and edges with different length, epipolar stripes are de-
fined to first of all relax the epipolar constraint and secondly
to reduce the search space. Similar to the above approach,
geometric and photometric constraints are used to reduce the
number of false matches. The preliminary result of the new
stereo matching is shown in Fig. 8B.
=
%
A on E
(A) (B)
Figure 8: (A) the matched 3-D segments (notice the false
matches), using the edginess approach, and (B) the novel
simultaneous stereo matching among all four images. Notice
that the new results are more complete than the old ones.
6.2 Coplanar Grouping of 3-D Segments
To group 3-D segments into planes, we propose a simple
method that accounts for outliers in the data [Bignone 1995].
The proposed method explicitly uses the similarity relations
from section 5.3 to drive the algorithm. This has the advan-
tage that we only extract planes that are somehow related to
similar 2-D contours and hence we largely reduce the number
of mismatches in the extracted planes. The algorithm pro-
ceeds in two steps similar to the procedure in [Stricker and
Leonardis 1995]:
Explore: The exploration generates an initial set of hypothe-
ses. Given the similarity relationships of section 5.3 and
the 3-D geometry of the segments, planes are fitted to
pairs of related contours that are roughly coplanar. The
support of those planes are then extended by iteratively
including segments that are related to the hypothesis
and that are close enough to the plane. After each iter-
ation the plane parameters are re-approximated.
Merge: The exploration produces a set of plane hypotheses.
Because all the contours belonging to the same physical
plane may not be related in the sense of section 5.3, this
plane may give rise to several hypotheses that must be
merged. This is done by performing a statistical test on
pairs of parallel planar hypotheses to check whether or
not they describe the same plane.
For the house in Fig. 8A the exploration instantiated 13 planes
and after the merging step only 6 remained. The 2-D con-
tours of the extracted planes are shown in Fig. 9. A plane
consists of a number of 3-D segments, most of which are cor-
rectly matched and belong to a planar object part. In Fig. 9,
plane E is vertical and plane F consists of a correctly matched
contour and a false match (the 2-D contour on the ground).
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
a rt o i e
© o
Figure 9: The result of grouping the 3-D segments in Fig. 8A
to planes. Plane D consists of two 3-D segments.
As we are interested in the outer boundary of the roofs, we
regard those correctly matched 3-D segments that lie inside
the roof as disturbances. For example, the shadow contours
on plane A and the roof window in plane B, although cor-
rectly matched, do not represent 3-D segments of the roof
boundary. lt is not possible to exclude these disturbing 3-
D segments until we have inferred the object boundary of
each plane. Some of the planes in Fig. 9 are rejected in the
reconstruction of the house, see section 6.4.
6.3 Extract and Select 2-D Enclosures
In the preceding section we described an algorithm that
groups 3-D segments into planes. The results in Fig. 9
clearly demonstrate that, in most cases, only a subset of
all segments on each plane actually represents the outer
boundary of a roof. Furthermore, the planes are often in-
complete due to false matches or when the matching algo-
rithm does not find good correspondences for the 2-D con-
tours. The extracted planes themselves are therefore not
sufficient to describe the roofs. We therefore need an ad-
ditional procedure which is capable of inferring the outer
boundary of the extracted planes and then rank them accord-
ing to simple shape criteria [Henricsson and Stricker 1995,
Bignone et a/. 1996].
We propose a graph-based approach similar to [Kim and
Muller 1995, Fua and Hanson 1991]. Each similarity rela-
tion of section 5.3 defines a node in a relations graph, and
compatible nodes represent the graph arcs. A cycle in the
graph corresponds to a closed boundary in the image. The
strategy consists of grouping related 2-D contours to form
2.D enclosures, thereby using the 2-D contours belonging to
the extracted planes to initialize the enclosure finding algo-
rithm. Each 2-D enclosure hypothesizes the boundary for the
corresponding plane. The boundaries of the vertical planes
are often not entirely visible in single images, hence, we ex-
clude the vertical planes right from the beginning. The tight
coupling between the 2-D and 3-D processes plays an im-
portant role since we do not need to find all possible 2-D
enclosures, only those that overlap with non-vertical planes.
The major reason for grouping in 2-D instead of in 3-D is that
additional and more complete information is available in 2-D.
For example, in 2-D a// straight 2-D contours, their photo-
metric and chromatic attributes and the computed similarity
relations are available.
327
