figure 5. Phases of the randomized nearest neighbor algorithm:
(a) patches initially have random assignments; (b) the blue
patch checks above/green and left/red neighbors to see if they
will improve the blue mapping, propagating good matches;
(c) the patch searches randomly for improvements in concentric
neighborhoods.
A
A
A
B
B
B
(a) Initialization
(b) Propagation
(c) Search
mapping at (x, y). Let z = (x, y). The new candidates for f (z)
are f(z − Dp) + Dp, where Dp takes on the values of ( 1, 0) and
(0, 1). Propagation takes a downhill step if either candidate
provides a smaller patch distance D.
The effect is that if (x, y) has a correct mapping and
is in a coherent region R, then all of R below and to the
right of (x, y) will be filled with the correct mapping.
Moreover, on even iterations we propagate information
up and left by examining patches in reverse scan order,
and using candidates below and to the right. If used in
isolation, propagation converges very quickly, but ends
up in a local minimum. So a second set of trials employs
random search.
random search. A sequence of candidates is sampled
from an exponential distribution, and the current nearest
neighbor is improved if any of the candidates has smaller
distance D. Let v0 be the current nearest neighbor f(z).
We attempt to improve f(z) by testing a sequence of candidate mappings at an exponentially decreasing distance
from v0:
pixels, followed by random search in the neighborhood of
the best nearest neighbor found so far. Sections 3. 2 and 3. 3
describe these steps in more detail.
ui = v0 + wa i ri
( 1)
3. 2. initialization
The NNF can be initialized either by assigning random values to the field, or by using prior information. When initializing with random values, we use independent uniform
samples across the full range of image B. The image editing
applications described in Section 4 repeat the search process in a coarse-to-fine pyramid, interleaving search and
reconstruction at each scale. So we have the option to use
the previous solution—possibly upscaled from a coarser
level of the pyramid—as an initial guess. However, if we
use only this initial guess, the algorithm can sometimes get
trapped in suboptimal local minima. To retain the quality
of this prior but still preserve some ability to escape from
such minima, we perform a few early iterations of the algorithm using a random initialization, then merge with the
initial guess only at patches where D is smaller, and then
perform the remaining iterations. This gives a good trad-eoff of retaining local minima found on previous iterations
without getting stuck there.
3. 3. iteration
After initialization, we iteratively improve the NNF. Each
iteration of the algorithm proceeds as follows: nearest
neighbors are examined in scan order (from left to right,
top to bottom), and each undergoes propagation followed by
random search. These operations are interleaved at the patch
level: if Pj and Sj denote, respectively, propagation and random search at patch j, then we proceed in the order: P1, S1,
P2, S2,…, Pn, Sn.
Propagation. We attempt to improve f(x,y) using the
known nearest neighbors of f (x − 1, y) and f (x, y − 1), assum-
ing that the patch coordinates are likely to be offset by the
same relative translation one pixel to the right or down. For
example, if there is a good mapping at (x − 1, y), we try to use
the translation of that mapping one pixel to the right for our
where ri is a uniform random in [− 1, 1] × [− 1, 1], w is a large
maximum search “radius,” and a is a fixed ratio between
search window sizes. We examine patches for i = 0, 1, 2,…
until the current search radius wa i is below 1 pixel. In our
applications w is the maximum image dimension, and
a = 1/2, except where noted. Note the search window must
be clamped to the bounds of B.
halting criteria. Although different criteria for halt-
ing may be used depending on the application, in practice
we have found it works well to iterate a fixed number of
times. All the results shown here were computed with 4–5
iterations total, after which the NNF has almost always con-
verged. Convergence is illustrated in Figure 6.
3. 4. Discussion
Our algorithm converges quickly to a good approximate
solution in a small number of iterations. We compared
our convergence with competing methods such as kd-trees
with PCA, vp-trees with PCA, and theoretically analyzed
the convergence properties of our algorithm.
6 We found
that for equal matching error, and low numbers of iterations, our algorithm is 20–100 x faster than the best competing algorithm, kd-tree with PCA, and uses substantially
less memory.