Description
The PatchMatch Algorithm (100 Marks)
The technique is described in full detail in the following paper (available here):
C. Barnes, E. Shechtman, A. Finkelstein and D. B. Goldman, “PatchMatch: A Randomized Algorithm for Structural Image Editing,” Proc. SIGGRAPH 2009.
You should read Section 1 of the paper right away to get a general idea of the principles behind
the method. The problem it tries to address should be familiar to you given that the algorithm you
worked with in A2 relied on a “nearest-neighbor search” procedure for identifying similar patches
for inpainting. In fact, Criminisi et al’s inpainting algorithm is cited in Section 2 of the paper as a
motivation for PatchMatch. You should read Section 2 as well, mainly for context and background.
The algorithm you are asked to implement is described in full in Section 3. The algorithm’s initialization, described in Section 3.1, has already been implemented. Your task is to implement the
algorithm’s basic iteration as described in Section 3.2 up to, but not including, paragraph Halting
criteria. The starter code uses the terminology of Eq. (1) to make it easier for you to follow along.
For those of you who are more theoretically minded and/or have an interest in computer science
theory, it is worth reading Section 3.3. This section is not required for implementation but it does
help explain why the algorithm works as well as it does.
Sections 4 and 5 of the paper describe more advanced editing tools that use PatchMatch as a key
component. They are not required for your implementation, and Section 4 in particular requires a
fair amount of background that you currently don’t have. Read these sections if you are interested
in finding out all the cool things that you can do with PatchMatch.
Part 1. Programming Component (90 Marks)
You need to complete to implement the two functions detailed below. A skeleton of both is included
in file 320/A3/code/algorithm.py. This file is where your entire implementation will reside.
In addition to these functions, you will need to copy a few lines of code from your A1 implementation
for image reading and writing that are not provided in the starter code. Like in Assignment 2,
this requires no effort other than verbatim line-by-line copy from your Assignment 1 code. See
320/A3/code/README 1st.txt for details.
2
Part 1.1. The propagation and random search() function (65 Marks)
This function takes as input a source image, a target image, and a nearest-neighbor field f that
assigns to each patch in the source the best-matching patch in the target. This field is initially
quite poor, i.e., the target patch it assigns to each source patch is definitely not the most similar
patch in the target. The goal of the function is to return a new nearest-neighbor field that improves
these patch-to-patch correspondences. The function accepts a number of additional parameters that
control the algorithm’s behavior. Details about them can be found in the starter code and in the
paper itself.
As explained in the paper, the algorithm involves two interleaved procedures, one called random
search (50 marks) and the other called propagation (15 marks). You must implement both, within
the same function. You are welcome to use helper functions in your implementation but this is not
necessary (the reference implementation does not).
The starter code provides two flags that allow you to disable propagation or random search in this
function. As you develop your implementation, you can use these flags for debugging purposes, to
isolate problems related to one or the other procedure.
Part 1.2. The reconstruct source from target() function (15 Marks)
This function re-creates the source image by copying pixels from the target image, as prescribed
by the supplied nearest-neighbor field. If this field is of high quality, then the copied pixels will be
almost identical to those of the source; if not, the reconstructed source image will contain artifacts.
Thus, comparing the reconstructed source to the original source gives you an idea of how good a
nearest-neighbor field is.
Details of the function’s input and output parameters are in the starter code.
Part 1.3. Efficiency considerations (10 Marks)
You should pay attention to the efficiency of the code you write. Explicit loops cannot be completely
avoided in propagation and random search() but their use should be kept to an absolute minimum.
This is necessary to keep the running time of your code to a reasonable level: the input images you
are supplied are quite large and it will take a very long time to process them if you use too many
loops. No explicit loops are needed in reconstruct source from target().
Solutions that are no more than 50% slower than the reference implementation will receive full marks
for efficiency. Less efficient implementations will have some of those points deducted depending on
how much they deviate from this baseline.
Part 2. Report and Experimental evaluation (10 Marks)
Your task here is to put the PatchMatch to the test by conducting your own experiments. Try it
on a variety of pairs of photos; on two adjacent frames of video; on “stereo” image pairs taken by
capturing a photo of a static scene and then adjusting your viewpoint slightly (e.g., a few centimeters)
to capture a second photo from a different point of view. Basically, run it on enough image pairs to
understand when it works well and when it doesn’t.
At the very least, you must show the results of running the algorithm on the supplied source/target
image pairs, using command-line arguments like those specified in the file test images/jaguar2/README.txt.
3
Your report should highlight your implementation’s results (nearest neighbor field, reconstructed
source, etc) and discuss how well your algorithm performs, and the conditions in which it doesn’t
work well. The more solid evidence (i.e., results) you can include in your report PDF to back up
your arguments and explanations, the better.
Place your report in file 320/A3/report/report.pdf. You may use any word processing tool to create
it (Word, LaTeX, Powerpoint, html, etc.) but the report you turn in must be in PDF format.
What to turn in: Use the following sequence of commands on CDF to pack everything and submit:
> cd ~/CS320/
> tar cvfz assign3.tar.gz A3/CHECKLIST.txt A3/code A3/report A3/results A3/extras
> submit -c csc320h -a assign3 assign3.tar.gz
WARNING: Re: Academic Honesty
PatchMatch is a popular algorithm. C++ and OpenCV implementations are just a mouse click (or
google search) away. You must resist the temptation to download and/or adapt someone else’s code
and submit it without appropriate attribution. This is a serious academic offence that can land you
in a lot of trouble with the University.
Be aware that if an existing implementation is easy for you to find, it is just as easy for us to find as
well—in fact, you can be sure that we already have found and downloaded it.
4
