Project 1: Image Quilting

CS 6501 - Computational Photography

Due: Tues, Sept 30 (11:59 PM)

This project involves implementing a simple texture synthesis method, Image Quilting. Additionally, graduate students should implement the second part, PatchMatch, which can be used for texture synthesis, but for simplicity we will just use it for finding correspondences between image pairs. The second part is optional for undergraduates (implementing both parts correctly will result in extra credit for undergraduates).

Part 1: Image Quilting

Image quilting is a simple technique for creating a larger textured image from a smaller input. The idea of the algorithm is to sample square regions or patches from the input in such a way that they align well, like a jigsaw puzzle.

The simplest algorithm (a) chooses source patches randomly, and arranges them in non-overlapping manner on the target image, which does not give a good "puzzle solution." A more complicated algorithm (b) overlaps the patches slightly, and chooses source patches so that each piece agrees with its neighbors. Finally, the full algorithm (c) allows puzzle pieces to have ragged edges in the overlap region, and solves for the best "seam" or "cut" using dynamic programming. The algorithms are shown in Figure 2 of the paper:

Your assignment is to implement the algorithm (c) in a language of your choice (suggested: MATLAB, Python). We recommend doing this by first implementing (a), then building on that for (b), and then (c). Read the paper and it should be fairly self-explanatory. However, we give some hints:

Part 2: PatchMatch (Mandatory for graduate students, optional for undergraduates)

PatchMatch is a method for quickly finding dense correspondences between "patches" or small square regions in a pair of images. I researched this for my Ph.D. thesis, and it was also tech transferred into some features of Photoshop such as Content Aware Fill. It was significantly (10-100x) faster than previous techniques so it allowed some high quality image editing applications to run interactively for the first time.

Your assignment is to implement the core matching algorithm for PatchMatch from Section 3-3.2 of the paper. Unlike Image Quilting, PatchMatch finds correspondences between densely overlapping patches, meaning a patch is defined around every pixel. Patches have a small fixed size such as 7x7. The algorithm attempts to find for each patch in the "from" image A, what is the most similar patch in the "to" image B, under all possible (integer) translations:

The algorithm is a fast approximation algorithm, which may not find the best matching patch, but finds an approximate solution quickly. It does this by optimizing an array containing the correspondence mapping from image A to image B, in three phases:

Your assignment is to implement the first two phases by referencing the paper. The third stage of random search is optional extra credit, although recommended because it gives better results.

Then, test your algorithm on the pair of images bike_a.png and bike_b.png. Find the match from the A image to the B image. Visualize the x and y coordinates of the correspondence field (plot them as images using imagesc in MATLAB or imshow in Python) and make sure these look reasonable. Also visualize the patch distance, which is also a 2D image. These should look roughly like x, y, D, although use your preferred color scheme. For extra credit, you can also reconstruct the A image using the matched patches of image B, as done in Figure 3, which gives this result.

Implementation notes:


Feel free to collaborate on solving the problem but write your code individually.


Submit your assignment in a zip file named In the root directory place a README.txt file that is your writeup, which should include: For Part 1, place a subdirectory part1 in your zip file containing:
For Part 2, place a subdirectory part2 in your zip containing:
Finally submit your zip to UVA Collab.