Graphics Reference
In-Depth Information
This is closely related to the sum-of-squared-differences distance
(SSD)
2
2
D
ssd
(
a
,
b
)
=
a
−
b
(4.36)
2
=
D
euc
(
a
,
b
)
In certain cases, a training set of ground-truth matches may be available that can
be used to estimate the
n
that statistically relates each pair
of descriptor values. In this case, we can define the
Mahalanobis distance
as
×
n
covariance matrix
1
/
2
)
−
1
D
mahal
(
a
,
b
)
=
(
a
−
b
(
a
−
b
)
(4.37)
Given a distance function
D
between two descriptors, matches are typically gen-
erated using the method of
nearest neighbors
. That is, the match to a descriptor
a
from a set of candidates
B
is computed as
b
∗
=
argmin
b
D
(
a
,
b
)
(4.38)
∈
B
a
,
b
∗
)
a
,
b
∗
)
is below a user-
specified threshold. After all, not every feature in one image is expected to appear
in another, and incorrect feature matches can severely affect the performance of
subsequent algorithms that depend on matches (e.g., matchmoving in Chapter
6
).
Lowe [
306
] proposed a rule for more precise descriptor matching based on both
Typically
(
is accepted as amatch only if the distance
D
(
a
,
b
∗
)
a
,
b
∗∗
)
, where
b
∗∗
D
(
and
D
(
is the descriptor with the second closest distance
a
,
b
∗
)
a
,
b
∗
)/
a
,
b
∗∗
)
to
a
. The rule is to accept
is below a user-
specified threshold (e.g., 0.8). This criterion is sometimes called the
nearest neighbor
distance ratio
. The goal is to prevent situations where
a
has several very similar
matches in
(
as a match if
D
(
D
(
, making it impossible to choose an unambiguously best match. For
example, the corner of a window on the wall of a building may make an excellent fea-
ture on its own, but the wall may have several nearly identical windows that prevent
the corner from being matched correctly in a second image.
Another less-often used matching criterion is the
normalized cross-correlation
given by
B
n
1
s
a
s
b
(
NCC
(
a
,
b
)
=
a
i
−
µ
)(
b
i
−
µ
b
)
(4.39)
a
i
=
1
where
a
and
s
a
are the mean and standard deviation of the elements of
a
. Two
vectors that match well should have a high NCC, near 1. The NCC is most often used
for matching raw blocks of intensities as opposed to derived descriptors. If the blocks
are already normalized for affine illumination changes as described in the previous
section, then the NCC is simply the dot product between the two descriptor vectors
(i.e., the cosine of the angle between the vectors). While the NCC is not a distance
function, the same concepts of best and second-best matches can apply to detecting
and filtering potential matches. The NCC can also be computed very efficiently using
the Fast Fourier Transform due to its similarity to convolution.
Finally, we note that a match to a given feature in one image cannot occur at
an arbitrary location in a second image; the match location is constrained by the
epipolar geometry
. That is, the match location in the second image must lie along
the
epipolar line
corresponding to the feature in the first image. We can iteratively
µ
