alation
n
| of objects
| World
ometry
| Material
ge
'omputer Vision.
A
New York, USA.
extraction of ob-
ational Archives
, pp- 547-554.
cartographic fea-
al. (eds), Digital
88. Cooperative
puter Vision and
ss, pp. 662-672.
mmert, F., 1990.
n understanding.
hine Intelligence
für Photogram-
nowledge based
uences. Interna-
Sensing 28(3/2),
etworks - Explo-
rgan Kaufmann
and Radig, B.,
, in Gruen et al.
ects from Aerial
id, pp. 275-284.
puter vision al-
raction of Man-
rkhäuser, Basel,
BUNDLE ADJUSTMENT WITH GEOMETRIC CONSTRAINTS FOR HYPOTHESIS EVALUATION
Chris McGlone
Digital Mapping Laboratory
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213-3891 USA
email: jem@cs.cmu.edu
Commission Ill, Working Group 2
KEY WORDS: geometric model, reliability, bundle adjustment, statistics, image understanding
ABSTRACT
This paper describes the use of a bundle adjustment with geometric constraints to evaluate feature matches and geometric
assumptions, based on the use of reliability statistics. Our evaluation procedure starts with the smallest possible redundant
geometric subsets of the object, (e.g., one right-angle corner of a rectangular building), finds consistent feature matches
among them, and then combines the consistent matches into larger geometric entities and continues the evaluation. We derive
statistics to verify the geometric assumptions used in the solution and demonstrate their use to detect erroneous geometric
constraints.
1 MOTIVATION
Our goal is the automated and semi-automated construction
of accurate three-dimensional site models from multiple im-
ages. Several of our site modeling systems, such as SiteCity
[Hsieh, 1996; Hsieh, 1995], MultiView [Roux and McKeown,
1994a; Roux et al., 1995], and PIVOT [Shufelt, 1996a], use a
hypothesize-and-test paradigm, in which a large set of object
hypotheses is generated, then evaluated to extract the best
descriptions of cartographic features in the scene. Evaluation
methods have typically been based on image intensity, edge
geometry, or shadow identification [Shufelt and McKeown,
1993] or on image geometry [McGlone and Shufelt, 1993].
Methods using image and scene geometry are especially pow-
erful, since the geometry is independent of image intensity
properties and can be established from information sources
outside the image. We have been developing techniques to
utilize the geometric information more fully, built around a
bundle adjustment with object-space geometric constraints
and which calculates a complete set of evaluation statistics.
While the use of geometric constraints in a bundle adjust-
ment is not a new technology, most previous applications
have been concerned with the determination of sensor orien-
tations [Mikhail, 1970; McGlone and Mikhail, 1982]. We in-
tend to use the geometrically-constrained bundle adjustment
to provide a rigorous evaluation procedure, both for feature
matches and for object-space geometric assumptions.
The distinction between feature match verification and geo-
metric hypothesis verification is an important one. Verifica-
tion of a match means that the features identified on each
image all correspond to the same physical point in object
space. On the other hand, verification of a geometric hy-
pothesis means that the features involved, whether they are
lines, points, or planes, or other shapes, actually have the
specified object-space configurations. For instance, four ob-
ject space points may be correctly identified on all images,
but may be incorrectly specified to be coplanar.
The verification of point matches is equivalent to the test-
ing of point measurements for blunders, using standard data
snooping techniques [Forstner, 1985]; the addition of geo-
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
metric constraints makes such testing much more effective
[McGlone, 1995]. However, the evaluation of geometric hy-
potheses, as expressed by geometric constraints in the bun-
dle adjustment, requires the extension of standard statistical
techniques. The derivation of such statistics is discussed in
the next section. The following sections then discuss the ap-
plication of reliability statistics and geometric constraints to
evaluating feature matches and to evaluating the reliability
of the geometric information itself.
2 CONSTRAINT RELIABILITY
A large body of work in recent years has been concerned with
the derivation and interpretation of reliability statistics for
point measurements in traditional photogrammetric applica-
tions [Fórstner, 1985]. These techniques can be applied in
a straightforward manner to the matching of point features,
where corresponding images of an object must be identified
across multiple images.
However, our work involves extracting and modeling com-
plex objects, using their geometry to help us in the process.
We want to use this geometric information to assist in the
rigorous evaluation of our building hypotheses. As described
below, the unified approach to least squares adjustment gives
us this capability.
2.1 Mathematical basis
The detection of blunders is based upon the examination of
residuals; therefore, we want to quantify the effect of a blun-
der on the residuals from an adjustment. For the classical
case of least squares adjustment, the partial derivative of the
residuals with respect to the input observations is [Fôrstner,
1987]:
Av = —R Ay = -Q,,W Ay (1)
The R matrix in equation 1 is called the redundancy matrix,
since the trace of the matrix is equal to the redundancy of the
adjustment. The diagonal elements of the matrix, r;;, whose
values are between 0 and 1 since the matrix is idempotent,
indicate the portion of an error in an observation visible in
