Description
In this assignment you will extend your PatchMatch implementation from A3 in two ways: (1)
computing k nearest-neighbour fields per image pair, corresponding to the k best-matching patches
between source and target, and (2) using these fields to denoise a noisy input image. The techniques
behind these tasks are described in papers by Barnes et al. and Buades et al., respectively. To
complete this assignment you need to look at an extremely small piece of each paper—just two
paragraphs from the first and three from the second.
Your specific task is to complete the technique’s implementation in the starter code. The starter
code is essentially identical to the starter code for A3, and your implementation requires just a few
changes/extensions to your A3 implementation. As in A3, it is based on OpenCV and is supposed
to be executed from the command line, not via a Kivy GUI.
Goals: The goals of the assignment are to (1) get you familiar with the use of more advanced
data structures for image processing, namely heaps; (2) see how the relatively simple algorithm you
implemented in A3 can open the door to very powerful image processing tools; and (3) become even
more aware of the efficiency of the code you write.
Bonus components: I am not including any explicit bonus components. You are welcome to read
one or both of the papers associated with these techniques in full and implement some the many
ideas they contain. If you intend to do this you need to talk to Kyros ASAP to discuss feasibility
and possible bonus points. Bonus components can be submitted after the A4 submission deadline
after prior consultation with Kyros. Bonus points will be awarded according to the complexity of
the implementation, etc.
Important: As in the previous assignments, you are advised to start immediately by reading the
relevant parts of the papers (see below). The next step is to compare the starter code to the one you
used for A3. As in A3, the assignment involves a combination of understanding what it is that you
have to implement and then actually doing the coding. Your task, however, is conceptually much
simpler than A3 because you are extending an algorithm and an implementation you should already
know quite well. If you were not able to get your A3 implementation working, please contact Kyros
ASAP. You will be given permission to copy and extend someone else’s A3 code so that you are not
hampered by your A3-specific issues.
Testing your implementation on CDF: As in A3, it is possible to develop and run your code
remotely from CDF.
Starter code & the reference solution
Use the following sequence of commands on CDF to unpack the starter code and to display its input
arguments:
1
> cd ~
> tar xvfz patchmatch_k.tar.gz
> rm patchmatch_k.tar.gz
> cd CS320/A4/code
> python viscomp.py –help
Consult the file 320/A4/code/README 1st.txt for details on how the code differs from A3. Its
structure should be thoroughly familiar to you by now. In addition to the starter code, I will provide
pre-complied binaries for OS X and CDF/Linux (probably on March 29th).
As I have explained in previous assignments, you should not expect your implementation to produce
exactly the same output as the reference solution; tiny differences in implementation might lead to
slightly different results. This is not a concern, however, and the TAs will be looking at your code
as well as its output to make sure what you are doing is reasonable.
320/A4/CHECKLIST.txt: Please read this form carefully. It includes information on the course’s
Academic Honesty Policy and contains details on the distribution of marks in the assignment. You
will need to complete this form prior to submission, and this will be the first file the TAs will look
at when marking your assignment.
Part 1. The Generalized PatchMatch Algorithm (70 Marks)
The technique is described in full detail in the following paper (available here):
C. Barnes, E. Shechtman, D. B. Goldman, and A. Finkelstein, “The Generalized PatchMatch Correspondence Algorithm,” Proc. ECCV 2010.
The only part of the paper you really need to read is the first paragraph of Section 3.2 and the
paragraph entitled Heap algorithm in the same section. Rather than keeping track of the “best”
displacement for each pixel as you did in A3, your implementation must now maintain a MAX heap
for every pixel. The pixel’s heap should contain the k displacements and the patch distance of each
displacement.
The MAX heap is a data structure that implements a priority list. Its most important feature is that
it allows very efficient identification of the maximum element in it. This data structure is (almost)
provided by Python: Python’s heapq package provides a MIN heap, which allows efficient removal
of the smallest element in the heap, along with operations such as pushing and popping elements
from it. You will need to think about what you need to do to make heapq behave like a MAX heap
for your task.
Beyond this data structure, the random search and propagation are done exactly as in the original
algorithm—except that now you have k displacement candidates associated with every pixel rather
than just one. I am also providing the skeleton of a couple of helper functions that you should
implement in order to streamline your implementation of this function.
More guidelines on how to structure your implementation are provided in the starter code. As in
A3, your entire implementation should reside in the file 320/A4/code/algorithm.py.
You will need to copy some code verbatim from your A3 implementation: the code for image reading
and writing and for the reconstruct source from target() function. See the file
320/A4/code/README 1st.txt for details.
2
Part 1.1 The propagation and random search k() function (55 Marks)
This function generalizes propagation and random search() from A3. In fact, the reference implementation differs only by about 15 lines of from the reference code in A3. The only difference
is that it now needs to maintain a heap for each pixel. In addition to the heap, the function must
also maintain a dictionary for each pixel. This per-pixel dictionary makes it easy and efficient to
check whether or not a particular candidate displacement is already in a pixel’s heap so that it is
not added again. The propagation and random search k() function should not insert duplicate
entries into a heap, as per the algorithm in the paper. See the file 320/A4/code/algorithm.py for
more information.
As in A3, the starter code provides two flags that allow you to disable propagation or random search
in this function. In A3 these flags had the opposite effect of what they were supposed to do: when
disable propagation was False, propagation was actually enabled and vice versa. This has now
been fixed, so be sure to update your code account for this fix.
Part 1.2. The heap helper functions (15 Marks)
The purpose of these functions is to make it easy for you to convert an array of k nearest-neighbour
fields to/from a heap. These functions serve to structure your thinking on how to extend your A3
implementation of propagation and random search() without making too many changes to it. It
is strongly recommended that you tackle these functions first—and make sure they work correctly—
before modifying your propagation and random search() function from A3.
Note: The starter code will not run before these functions are implemented since some of the code
in file patchMatch.py depends on them.
Part 2. The Non-Local Means Denoising Algorithm (20 Marks)
The technique is described in full detail in Section 3 of the following paper (available here):
A. Buades, B. Coll, and J.-M. Morel, “A non-local algorithm for image denoising,” Proc. CVPR 2005.
Do not get intimidated by the other sections of this paper! They are not relevant at all for your
implementation; ignore them and you will be just fine.
The non-local means algorithm (NLM for short) takes as input one noisy input image and returns
a “denoised” version of it, i.e., an image where noise is reduced compared to the original. The
algorithm is extremely simple and is summarized in in Figure 1 and in the first equation of Section 3.
According to that equation, the intensity of pixel i of the denoised output image is a weighted average
of the intensities of a small set of pixels j in the noisy input image. The NLM algorithm specifies
exactly (1) how to choose the “right” set of pixels j for each pixel i and (2) what weight w(i, j) to
assign to each pixel j when computing this average.
This is where the Generalized PatchMatch algorithm comes to the rescue: before running NLM, we
run Generalized PatchMatch using the same noisy image as both the source and the target. This
computes, for every pixel i in the noisy image, the k pixels whose patches are most similar to the
patch centered at i. To compute the denoised intensity at pixel i, NLM simply computes a weighted
average of the intensity of these pixels.
According to NLM, the weights w(i, j) in this average should depend on the similarity of the patches
3
centered at pixels i and j. The exact expressions to use are given by the third and fourth equation
in Section 3 (you can ignore the second equation). They are computed from the sum-of-squareddifferences between the patches.
Part 3. Efficiency considerations (0 Marks)
You should pay attention to the efficiency of the code you write. Explicit loops (probably) cannot
be completely avoided for most of the functions you have to write, 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:
expect your code to take longer time to process an image compared to A3, and much longer if you
use too many loops. That being said, you will not lose marks by writing inefficient code for this
assignment.
Part 4. Report and Experimental evaluation (10 Marks)
Your task here is to put the NLM algorithm to the test. Try it on a variety of noisy photos (e.g., taken
with your cellphone in poor lighting conditions), and comment on how the following parameters of the
Generalized PatchMatch algorithm affect the results of NLM: (a) the maximum search radius w; (b)
the number of nearest neighbours k; and (c) the patch size. Include these results in your report, along
with the results of applying NLM to the noisy image in the starter code. The more solid evidence
(i.e., results) you can include in your report PDF to back up your arguments and explanations, the
better.
Finally, your report should also include the results of running Generalized PatchMatch on the
jaguar2 image pair for k = 3 and all the other parameters set to their default values.
Place your report in file 320/A4/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. Please
do not include any actual image files in the tarfile you submit.
What to turn in: Use the following sequence of commands on CDF to pack everything and submit:
> cd ~/CS320/
> tar cvfz assign4.tar.gz A4/CHECKLIST.txt A4/code A4/report A4/extras
> submit -c csc320h -a assign4 assign4.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
