Project 1: Texture

CS 6501 - Computational Photography

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

This project has two parts. First, you will implement a simple texture synthesis method, Image Quilting. In the second part, you will implement a more complex algorithm, PatchMatch, which can be used for texture synthesis, but for simplicity we will just use it for finding correspondences between image pairs.

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

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:

Policies

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

Submission

Submit your assignment in a zip file named yourname_project1.zip. 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.