VDoi: 10.1145/2018396.2018421
The PatchMatch Randomized
Matching Algorithm for Image
Manipulation
abstract
This paper presents a new randomized algorithm for quickly
finding approximate nearest neighbor matches between
image patches. Our algorithm offers substantial performance improvements over the previous state of the art
( 20–100×), enabling its use in new interactive image editing
tools, computer vision, and video applications. Previously,
the cost of computing such matches for an entire image had
eluded efforts to provide interactive performance. The key
insight driving our algorithm is that the elements of our
search domain—patches of image pixels—are correlated,
and thus the search strategy takes advantage of these statistics. Our algorithm uses two principles: first, that good
patch matches can be found via random sampling, and
second, that natural coherence in the imagery allows us to
propagate such matches quickly to surrounding areas. Our
simple algorithm allows finding a single nearest neighbor
match across translations only, whereas our general algorithm additionally allows matching of k-nearest neighbors,
across all rotations and scales, and matching arbitrary
descriptors. This one simple algorithm forms the basis for a
variety of applications including image retargeting, completion, reshuffling, object detection, digital forgery detection,
and video summarization.
1. iNtRoDuctioN
As digital and computational photography have matured,
researchers have developed sophisticated methods for analyzing and editing digital photographs and video. Many of
the most powerful of these methods are patch-based: they
divide the image into many small, overlapping rectangles
of fixed size (e.g., 7 × 7 squares, one defined around every
pixel), called patches, and then manipulate or analyze the
image based on its patches. For example, patch-based
techniques can be used for image retargeting, in which an
image is resized to a new aspect ratio—the computer automatically produces a good likeness of the original image
but with new dimensions. These techniques can also be
used for image completion, in which a user simply erases an
unwanted portion of an image, and the computer automatically synthesizes replacement pixels that plausibly match
the rest of the image.
However, because these algorithms must search and
manipulate millions of patches, performance in many cases
had previously been far from interactive: operations such as
image completion could previously take minutes.
24
In this paper we describe an algorithm that accelerates
many patch-based methods by at least an order of magnitude. This makes it possible to apply many powerful techniques for image editing for the first time in an interactive
interface, as shown in Figure 1. We also offer intuitive
controls for our image editing interface. Further, our algorithm is not limited to image editing, and can be applied
to many techniques that use image patches. We report our
experiences using our algorithm in object detection, digital
forgery detection, and video summarization. Because our
algorithm is a fairly general mathematical tool, we believe
similar techniques could be used for other application
domains in vision, graphics, or other fields where dense
matchings are desired.
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,
To design an efficient search algorithm we look at
the statistics of natural images—photographs of real
objects—and design a good search strategy by taking
The original version of this paper is entitled “PatchMatch:
A Randomized Correspondence Algorithm for Structural
Image Editing” and was published in ACM Transactions
of Graphics (Proc. SIGGRAPH), August 2009.