21.2 Patch match🔗⧉

A hole-filler erasing a tourist from a vacation photo, a texture synthesizer growing more brick wall, a content-aware resizer widening a panorama without stretching the faces: under the hood these tools all spend almost all their time asking one small question, over and over: for this little patch of the output, where in the source is the patch that looks most like it? Answer it once and you have copied a believable scrap of content into place; answer it for every output pixel and you have a dense map of where each piece of the result came from. The trouble is the cost. Asked naively (compare each patch against every candidate), that search is so slow that for years exemplar methods were batch jobs, not interactive tools. PatchMatch later enabled the interactive completion feature introduced in Photoshop CS5; earlier exemplar methods already worked, but dense matching was a major computational cost.

This chapter is about making that question fast, and the object it produces is the nearest-neighbor field: for each output patch, the offset to its best source match. There are two roads. The first is a randomized heuristic, PatchMatch Barnes, Shechtman, Finkelstein and Goldman, 2009, which exploits two facts about real images to get a near-perfect field in a few passes over the image. The second is a global energy minimization, Shift-Map editing Pritch, Kav-Venaki and Peleg, 2009, which poses the same "where does each output pixel come from" question as a graph-cut labeling and approximately minimizes it with graph-cut moves. The two approaches organize the same offset-field representation around different objectives and computational tradeoffs.

21.2.1 The nearest-neighbor field, and why exhaustive search is the bottleneck🔗⧉

Start by naming the shared sub-problem precisely, because once you see it you see it everywhere. Exemplar inpainting (Criminisi's method, and the older Efros–Leung texture synthesis, Efros & Leung 1999), patch-based texture synthesis, content-aware retargeting, even non-local-means denoising and Image Analogies, each one repeatedly needs, for a given output patch, the most similar patch in some source region. Collect those answers for every pixel and you have a nearest-neighbor field (NNF): an offset field

where $P_{\text{out}}(p)$ is the small patch (say $7\times 7$) centered at output pixel $p$, $P_{\text{in}}(p+\Delta)$ is the source patch reached by adding the offset $\Delta = f(p)$, and $D$ is the sum-of-squared-differences patch distance. Read it back: for each output pixel, $f$ stores the displacement to the source patch that matches it best, and $D$ is how good that match is. The field $f$ is the whole object of this chapter; everything downstream is "now copy along $f$" (Figure 21.2.1⛶ fullscreen).

Now the cost wall. Computed exhaustively, finding $f(p)$ for one pixel means comparing its patch against every candidate patch in the source, and you do that for every output pixel. That is quadratic in the number of pixels, and on a multi-megapixel image it is hopeless for anything interactive. Acceleration structures like kd-trees over patch descriptors help, but they still fall far short of real time on full-resolution photos, and they cost memory. This quadratic search (not the copying, not the blending) is the reason exemplar texture synthesis and Criminisi inpainting were slow, and the reason a one-click "remove this object" tool had to wait for a faster way to get the field.

The key reframing is to stop insisting on the exact nearest-neighbor field. We almost never need it. We need a field good enough that the patches it points to are visually right, and that we can settle for approximately, but fast. Two ways to do that: a randomized heuristic (PatchMatch, next) and a global energy minimization (Shift-Map, at the end). The rest of the chapter is those two.

21.2.2 PatchMatch: randomized correspondence Barnes et al. 2009🔗⧉

PatchMatch is one of those algorithms that sounds unlikely at first, but converges quickly in practice. It rests on two facts about natural images, and the whole design is a way to cash them in.

The first is coherence. Real images are made of coherent regions (a stretch of wall, a patch of sky) and within them, adjacent output patches usually map to adjacent source patches. If the patch at $p$ matched well to the source patch at $p+\Delta$, then the patch just to the right of $p$ very likely matches well to the source patch just to the right of $p+\Delta$, the same offset $\Delta$, give or take. So one good offset is good for its neighbors, and a single correct match wants to spread.

The second is a many-trials probability argument. Suppose you assign every output pixel a completely random offset. Most will be terrible. But there are a great many pixels, and the source has only so many places a given patch could go, so purely by chance, some patches will land on a good or near-good match. You do not need most guesses to be good; you need a few lucky hits anywhere in the image, because coherence will let you spread them. Random guessing seeds; coherence harvests.

The algorithm uses both facts in three moves, iterated a handful of times (Figure 21.2.3⛶ fullscreen):

1. Random initialization. Give every pixel a random offset into the valid source region. The resulting field is mostly garbage, but across many trials it will contain a few good matches by chance.
2. Propagation. Scan the image in raster order (top-left to bottom-right), and alternate the scan direction each iteration (bottom-right to top-left on the next pass, so information flows both ways). At pixel $p$, do not just keep its current offset: also try the offsets its already-scanned neighbors used, the pixel to its left and the one above, without changing the offset: neighboring target positions plus the same displacement give neighboring source positions. If the field stored absolute source coordinates instead, those coordinates would need the one-pixel adjustment. Keep whichever of the candidates gives the smallest patch distance $D$. The effect is a flood fill: a single good offset, once found, infects its whole coherent region in one sweep, because each pixel copies the good offset from the neighbor that already has it.
3. Random search. Propagation can only spread offsets that already exist somewhere; it cannot discover a better one or fine-tune. So after propagating at $p$, refine its current best by testing a sequence of random offsets in an exponentially shrinking window around it: candidates of the form $f(p) + w\,\alpha^{i}\,R_i$ for $i = 0, 1, 2, \dots$, where $w$ is the image size, $\alpha < 1$ (say $\tfrac12$), and $R_i$ is a fresh two-dimensional random vector uniformly sampled from $[-1,1]^2$. Reject candidates whose source patch is invalid, and stop when the window radius drops below one pixel. The first, large jumps can escape a bad local optimum entirely; the later, tiny jumps polish the match to the exact pixel. Keep the best seen.

The whole algorithm is short: initialize, then sweep, propagating and searching at each pixel:

initialize f[p] ← random offset, for every pixel p
repeat a few passes (alternate scan direction each pass):
    for each pixel p in scan order:
        propagate: f[p] ← best valid offset in {f[p], f[p_prev], f[p_other]}
            # evaluate each candidate using the patch distance at p
        random search: center ← f[p]; radius ← w
        while radius >= 1:
            candidate ← center + round(radius * uniform_vector([-1,1]²))
            if candidate is valid and improves D at p: f[p] ← candidate
            radius ← α * radius
return f

where p_prev and p_other are left/up neighbors on a forward pass and right/down neighbors on a backward pass; omit nonexistent neighbors. Choose w to span the source and 0 < α < 1, often one half. A few passes commonly produce a useful approximate field, but runtime and accuracy depend on image size, patch size, content, and implementation. The field requires one offset and its distance per output pixel.

Why does it converge so fast, when the per-pixel search it replaces is quadratic? Because the work is shared in exactly the way the two facts allow. Propagation turns one lucky match into an entire region's worth of good matches for free: the expensive discovery happens once per coherent region, and coherence broadcasts it. Random search gives pixels opportunities to escape bad offsets that propagation cannot improve; a finite number of passes gives no guarantee that every pixel succeeds, and its exponential window means it covers "anywhere in the image" and "right next door" with a logarithmic number of tries. The slogan is worth keeping: randomness plus coherence beats brute force. You are not avoiding the search; you are letting the structure of images do almost all of it for you.

You can watch this happen on your own photographs, one pixel at a time (Figure 21.2.2⛶ fullscreen). With B a shifted copy of A, the part of the field the first sweep has passed is already a single color, the true offset; after one iteration the mean patch distance has fallen most of the way to where it ends, at about eight patch comparisons per pixel per iteration, where exhaustive search at the figure's image size needs about twelve thousand.

One extension matters for later chapters. Generalized PatchMatch Barnes, Shechtman, Goldman and Finkelstein, 2010 lifts the field from a single nearest neighbor per pixel to the $k$ nearest neighbors, and from pure translations to offsets that also include rotations and scales. That is what you need when the content you want to match is transformed: a texture at a different orientation, a stylized example, the rotated-patch matching inside denoising and style transfer (cross-ref Chapter 25.1, Style transfer). Same core loop (init, propagate, search) over a larger space of offsets.

21.2.3 Applications: hole filling, retargeting, reshuffle🔗⧉

Once approximate NNF computation is fast enough, a family of edits that used to be impractical becomes interactive, and they are mostly the same engine pointed at different constraints (Figure 21.2.6⛶ fullscreen).

Interactive hole filling: the engine inside Content-Aware Fill. To fill a hole, repeatedly run PatchMatch between the hole's patches and the rest of the image, copy in the best-matching source patches, average overlapping copies, and iterate coarse-to-fine down an image pyramid so that the fill is globally consistent and not just locally plausible. This search accelerated exemplar completion enough for interactive editing. One objective used in this family is bidirectional similarity Simakov, Caspi, Shechtman and Irani, 2008: a good result is both coherent (every output patch has a good match in the source, so nothing looks fabricated) and complete (every important source patch appears somewhere in the output, so nothing important is dropped). PatchMatch is the fast search that makes minimizing that two-sided similarity interactive.

Image retargeting: content-aware resize. Change a photo's aspect ratio (make it wider for a banner, narrower for a phone) while preserving the important content rather than uniformly squashing it (which turns faces into ovals and buildings into parallelograms). The patch-based version re-synthesizes the image at the new size so that every output patch still has a good source match, letting unimportant, repetitive regions (sky, grass) absorb the change. This is the smooth cousin of seam carving (Avidan & Shamir 2007), which retargets by greedily removing one minimum-energy connected seam of pixels at a time; we will see in the Shift-Map section that seam carving is the greedy special case of a global offset-labeling.

Reshuffle. Drag an object to a new spot in the image and let the algorithm re-synthesize the rest so the scene stays coherent: the moved object lands cleanly and the gap it left behind, and the place it now covers, are filled from surrounding content. Same NNF machinery, now with a user constraint pinning some content to a new location.

And beyond. The same engine drives video completion Wexler, Shechtman and Irani, 2007 (fill a hole consistently across time, not just space), Image Melding Darabi, Shechtman, Barnes, Goldman and Sen, 2012 (PatchMatch with rotation/scale plus a gradient-domain blend, so the copied patches are also integrated, not just placed), the self-similarity search inside denoising, and the patch search inside Image Analogies (cross-ref Chapter 25.1, Style transfer).

All of these can be run on your own photographs (Figure 21.2.8⛶ fullscreen). Each view is one application, computed in the browser with the same randomized search: hole filling and reshuffling by coarse-to-fine completion, retargeting by bidirectional similarity beside plain scaling and seam carving, texture synthesis from an exemplar, non-local-means denoising over the $k$ nearest patches that generalized PatchMatch finds anywhere in the image, dense correspondence between two frames, color transfer by patch voting, and the detection of a region copied within a photo. The last three change only what is matched and what is done with the field; the search is the one described above.

One caveat, because it sets up the rest of the part. Every method here still copies real content, rearranging patches that genuinely exist in the image, so it is reconstruction-leaning within the image: bounded by its source material, although a copied patch can still depict the wrong hidden content. It cannot invent a face that was never there, only borrow one. The generative successors (diffusion inpainting and outpainting) synthesize new content instead of copying it: far more capable (they can hallucinate a plausible building behind the removed sign), and correspondingly less faithful (they can hallucinate the wrong one). That is the L7.8show / L7.7show hand-off to Chapter 7.4, Generative AI and diffusion: copying exposes where borrowed content came from, while generation can create new content; neither establishes what was hidden in the original scene.

21.2.4 Shift-Map image editing Pritch et al. 2009: editing as graph-cut labeling🔗⧉

PatchMatch finds a good offset field by a clever search. Shift-Map editing defines an explicit energy over the offset field and reduces it through graph-cut moves. The reframing is the chapter's big lesson made literal: decide, per output pixel, a single shift $M(p)$ into the input, and then read the output off by copying

So the output is a rearrangement of input pixels under a smooth offset (shift) field, exactly the same kind of object as the NNF, only now chosen by global optimization instead of randomized search (Figure 21.2.9⛶ fullscreen).

What makes one shift field better than another? An energy in two parts (the L10.5show template):

• The data term $E_{\text{data}}$ encodes the task, and this is where retargeting, removal, and reshuffle differ only in one line. For retargeting, the output grid has the requested dimensions, while constraints on mapped positions and boundaries encourage retaining the desired source extent rather than simply taking a crop. For object removal, it assigns infinite cost to any shift that would copy from the forbidden region: the removed object literally cannot be a source. For reshuffle, it pins chosen content to its new place. Same solver, different data term.
• The smoothness / seam term $E_{\text{smooth}}$ penalizes inconsistent neighboring shifts: if two adjacent output pixels pull from different parts of the input, there is a seam between them, and the penalty is the color and gradient discontinuity across that seam. A seam is inexpensive where competing source assignments join compatibly; a real edge is not automatically cheap, and a misplaced cut can remain visible, the same principle as the minimum-error boundary cut in image quilting.

Reducing $E(M)$ seeks a coherent rearrangement under the chosen costs; it does not establish the globally best labeling. The solver is graph cuts / $\alpha$-expansion (Boykov et al. 2001): the labels are the candidate shifts, the data term sets each pixel's cost for taking a label, the smoothness term sets the cost of a seam between neighboring labels, and each alpha-expansion step offers every pixel a binary choice between its current label and the proposed label. When that move energy is submodular, min-cut solves the move exactly; iterating such moves generally yields a local optimum of the multi-label problem, with approximation guarantees only under additional conditions on the costs. The label set (all possible shifts) is large, so Shift-Map runs coarse-to-fine: solve on a downsampled image with a small set of shifts, then refine the offsets on finer levels. The result is an offset map with clean, explicit seams placed exactly where the eye will not catch them.

PatchMatch and Shift-Map are dual views of the same object. Hold the two side by side and the chapter closes on itself. Both produce an offset field that rearranges the input into the output. PatchMatch finds it by a randomized heuristic: fast, approximate, and ideal when you want a dense field for synthesis (hole filling, reshuffle), where every output pixel needs a plausible source and a clean global seam matters less than speed. Shift-Map finds it by minimizing a global graph-cut energy: more explicitly coupled through neighboring labels, producing seams chosen by its energy, ideal for retargeting and removal, where you want control over seam placement and task constraints. This is the L10.1show → L10.5show progression in one picture: an affinity (patch similarity, or seam cost) is consumed either by a fast local rule (propagation) or by a global cut ($\alpha$-expansion). The affinity is the design; the solver is a choice.

A few cross-references close the loop. Seam carving (Avidan & Shamir 2007) is the greedy special case Shift-Map generalizes: it removes one optimal seam at a time, where Shift-Map optimizes the whole rearrangement at once. The seamless blend after a cut or patch composite (to erase whatever residual mismatch the seam leaves) is the gradient-domain Poisson solve of Chapter 10.8, Poisson image editing (the L10.4show half of "cut here, blend there"). And the learned successor to all of it (generate the fill rather than copy it, predict dense correspondence with deep features rather than search for it) lives in Chapter 7.4, Generative AI and diffusion L7.7show and Chapter 7.3, Deep learning.