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:

- When sampling patches from the source image, the source patch can have any pixel position whereas the target patch can only have positions that are multiples of its size.
- In (b), when finding a patch that agrees with its already-placed neighbor you can either exhaustively sample all possible source patches or else randomly sample a subset of them.
- In (b) if you always take the best patch according to the overlap error then this may produce repetitions. Instead, you can randomly sample one of the top
*k*patches for more variation. Alternatively, you can select all patches with less than some error tolerance and randomly sample from those.

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

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

Implementation notes:

- Every patch needs to be denoted with a coordinate. Two reasonable choices are to say a patch's coordinate is its upper left corner pixel, or its center pixel. If you choose upper left corner notation then there will be a gutter on the bottom and right sides of the image where pixels do not have a patch because the patch is partially outside the image. Make sure to skip patches that are outside the image by labelling them with high or "infinite" distance in all stages of the algorithm, to avoid invalid correspondences.
- The patch distance
*D*can be an arbitrary function but one reasonable choice is to sum up the squared differences between corresponding pixels in the patch. - See the efficiency notes at the end of Section 3.2. In particular, I recommend to store the correspondence field or "nearest neighbor field"
*f*as a 3-channel array, containing in its first channel the*x*coordinate of the best patch found so far, in the second channel the*y*coordinate, and in the third channel, the patch distance*D*. - For this application, just 2-5 iterations of the algorithm should suffice.
- I recommend to implement a method
`improve_nnf`

which takes the nearest neighbor field*f*, a patch coordinate (*ax*,*ay*) and a proposed target patch coordinate (*bx*,*by*). This function exits early if the target patch coordinate is out of bounds. Then it modifies the NNF if the target patch coordinate has less patch distance (SSD) than the one currently stored in the NNF. With this method is it then straightforward to implement propagation. - The paper stores in the nearest neighbor field
*f*the relative offset vector*f*(*ax,ay*) = (*bx-ax, by-ay*). You can alteratively use absolute coordinates, with the notation,*f*(*ax,ay*) = (*bx, by*). Bounds checking is easier with absolute coordinates. However, propagation with relative coordinates just involves trying the same offset vector as your adjacent patches, which for absolute coordinates requires an additional shift by__+__1 pixel (best to draw on paper if you are confused).

`yourname_project1.zip`

. In the root directory place a `README.txt`

file that is your writeup, which should include:
- Your name
- UVA computing ID
- Operating system
- Note any unfinished parts of the assignment, and any extra credit you did

`part1`

in your zip file containing:- Source for a program that allows the full algorithm (c) to be run.
- Add to your README writeup a brief text documentation of how to run the program.
- Choose a new and fairly repetitive texture image from your own photos or Flickr. Save the input and output to images starting with
`input`

and`output`

in the`part1`

subdirectory (we will collect any neat outputs for a gallery of results). The output should be at least twice the width and height of the input to test the algorithm.

`part2`

in your zip containing:- Source for your PatchMatch implementation.
- Add to your README writeup a brief description of how to run the program.
- Include your visualizations of the
*x*and*y*correspondence values found by the algorithm, as well as the patch distance*D*, after the algorthm has converged. Submit these in the files,`vis_x.png`

,`vis_y.png`

,`vis_d.png`

. If you did the extra credit of showing the reconstruction of A from B patches, then also submit`vis_reconstruction.png`

.