## Description

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