3.1 High Level Motivation
The high level intuition behind our algorithm is shown in Figure 3.1. We have two manifolds A
and B with descriptors computed at lattice points, visualized as colored circles. We wish to find for
each descriptor in A, the most similar descriptor in B. We do this by taking advantage of spatial
locality properties observed in the previous chapter: when we have a good match, we can propagate
it to adjacent points on the lattice, and if we have a reasonable match, we can try to improve it by
randomly searching for better matches around the target position. The first stage — propagation
— takes advantage of the property that many matches are coherent, or have the same relative
matching coordinates, as discussed in the previous chapter (Figure 2.1 and Figure 2.2). The second
stage — random search — looks for better correspondences relative to the current correspondence’s
target position, according to a peaked search distribution, similar to the measured distributions in
Figure 2.4.
In this chapter, we develop our algorithm for 2D images, which have a regular lattice of the
positions of all pixels. However, our algorithm has also been applied to 1D contours and 3D geometric
data, so we can imagine generalizing these propagation and random search operations to any space
that locally is Euclidean or nearly so.
3.2 Introduction
Many methods recently have been developed for manipulating images at a high level, such as
retargeting algorithms that change image aspect ratios, or image completion algorithms that remove
unwanted objects from photographs. Many of the most powerful of these methods are patch based:
they divide the image into many small, overlapping rectangles of fixed size, called patches.
To understand our matching algorithm, we must consider the common
components of patch based algorithms: The core element of nonparametric patch
sampling methods is a repeated search of all patches in one image region for the
most similar patch in another image region. In other words, given images or
regions A and B, find for every patch in A the nearest neighbor in B under a
patch distance metric such as L
p
. We call this mapping the Nearest-Neighbor Field
(NNF), illustrated schematically in the inset figure. Approaching this problem with
a na¨ıve brute force search is expensive – O(mM
2
) for image regions and patches
of size M and m pixels, respectively. Even using acceleration methods such as approximate nearest
12
