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.