(7)
BN^'W;
CNW.
mm NN.
for the total set
atistical testing
s that we do on
onstraint obser-
straint equation
/alues to ensure
t too optimistic.
rix to determine
ticular observa-
ised to quantify
ts on the image
lication, we can
t values on the
stance between
n parameter ap-
with a too-small
amining the off-
actions between
ch of an error in
of a constraint
' residuals apply
ability to isolate
ipon the redun-
ustment. While
ndancy and the
iat bad observa-
examination of
ically introduce
the determining
trong enough, a
strained points.
and redundant
ifferences in the
ions, depending
| were expressed.
eled as a scaled
narity and right
ctangular prism
rs in the corner
combination of
n that this is a
when the solu-
s very high con-
he two solutions
ndard deviations
ally realistic, the
ent behaviors.
1 of using redun-
dant constraints
s are dependent.
| rectangle to be
rth angle can be
e. In the unified
approach, however, the constraint equations are actually ob-
servation equations; adding redundant observation equations
actually improves the solution.
3 EVALUATION OF FEATURE MATCHING USING
GEOMETRIC INFORMATION
One of the most common problems in computer vision is the
matching of point features between multiple images. Cor-
ner detectors or interest operators generate a large num-
ber of features, often similar in appearance; this forces a
choice between accepting only the most obvious matches,
and thereby discarding the majority of the features, or deal-
ing with matches containing a large number of errors.
A simple strategy for evaluating feature matches would be to
perform a bundle adjustment for each plausible combination
of potential feature matches, with assumed object space ge-
ometry modeled by geometric constraints. By examining the
statistics for each adjustment, we could then decide which
feature matches are blunders and which are valid.
The obvious problem with this strategy is combinatorics. For
the evaluation to be effective we need redundant solutions,
i.e., at least three image rays for each object point, at least
four points to determine a general plane, etc. However, to
obtain sufficient redundancy we must process the many pos-
sible feature matching combinations. For instance, if a given
object point has three possible matches on three images, 27
solutions would have to be run. If we add another image with
another three possible matches to obtain better redundancy,
81 solutions would be required. Adding geometric constraints
between features only makes the combinatorics worse, since
we must test all possible matches of all features involved.
Our solution to this dilemma is to work with the smallest
possible redundant subsets—the smallest geometric configu-
ration which can be redundantly specified with the available
features. In this example, the redundant geometric subsets
are the right angles at each building corner. The 3D coordi-
nates of each point defining the right angle are determined by
the intersection of the image rays; constraining the 3D points
lie at a right angle within a horizontal plane means that their
positions are redundantly determined. This redundancy, or
extra information, allows us to evaluate the point matches.
Each subset is solved for every combination of feature
matches, and feature matches which do not form any consis-
tent subsets are eliminated. Feature matches which are part
of consistent subsets are used to form larger subsets. The
process is repeated until the final solution is obtained, and,
ideally, only one consistent set of match hypotheses is left.
The computational savings due to this decomposition de-
pends upon the number of possible feature matches com-
pared to the number of subsets used. For example, if each
point has 4 possible matches on each image, each subset so-
lution will require 4? solutions. Since there are four subsets
of the total solution, a total of 4* subset solutions will be re-
quired. Doing the complete geometric solution would require
4* separate solutions. The subset solutions are smaller (fewer
parameters and points) and therefore less expensive than the
complete solution, but we must still do some number of com-
plete solutions after editing points using the subset solutions.
We would still prefer to do the subset solutions over doing
the complete solution, simply for the reason that the subsets
are simpler to edit and understand since fewer features are
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Figure 1: Image fhn715 showing building corners to be
matched.
involved. Also, we do not necessarily have to do every pos-
sible geometric subset, as long as all features are included in
some subset.
This section describes the application of this technique to
point matching, although it can be applied to matching edges
or even combinations of edges. In the following examples
we use three images, two vertical (fhn715, fhn717) and one
oblique (fhov1627), taken over Ft. Hood, Texas, as part of
the RADIUS program [Gee and Newman, 1993]. We start
with four building corners in fhn715, shown in Figure 1. Fig-
ures 2 and 3 show the initial set of corners extracted by the
BUILD [Shufelt and McKeown, 1993] corner finder for im-
ages fhn717 and fhov1627, along with the epipolar lines cor-
responding to the points of interest on fhn715.
We first filter the corners using criteria such as epipolar
search bounds (propagated from the image orientation co-
variance), point elevation ranges, corner direction, [Roux and
McKeown, 1994b; Roux and McKeown, 1994a], or corner
type determined by vanishing point analysis [Shufelt, 1996b;
McGlone and Shufelt, 1993]. Next, potentially matching im-
age points are intersected and their standardized residuals are
examined to eliminate bad matches. The results of the these
two steps are shown in Figures 4 and 5. The smaller dots
are the points remaining after preliminary filtering using the
epipolar bounds, an expected elevation range, and the corner
direction, while the larger dots represent points which have
apparently valid matches. Note that no valid corners survived
the filtering for point 3 on image fhov1627.
At this point, we introduce the object space geometry into
the evaluation. Since we are looking for the horizontal roof
of a rectangular building, we can apply constraints forcing
the four hypothesized roof corners to lie in a horizontal plane
and to form right angles. However, applying the constrained
solution to each possible combination of potentially matching
points would require an impractical number of solutions.
Taking the potential matches for three out of the four corner
points at a time, we perform solutions constraining the three
points to form a right angle in a horizontal plane. Points in
consistent subsets are flagged for incorporation in the overall
solution, which includes all combinations of potential match-
ing points for all four corners of the building. Figures 6 and
7 show the points remaining after the right-angle constraints
solution as small dots, and the final points as larger dots.
Note that point 2 on image fhov1627 has two possibilities,
