A1-NikhilNaikalRicardoGarcia

From CS294-69 Image Manipulation and Computational Photography Fa11

For this assignment, we decided to implement two papers:

- PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. Connelly Barnes, Eli Shechtman, Adam Finkelstein and Dan B Goldman. SIGGRAPH 2009

- Region-Filling and Object Removal by Exemplar-Based Inpainting. Antonio Criminisi, Patrick Pérez, and Kentaro Toyama. CVPR 2004.

In the results below, we have included videos that show the algorithms in action.

Patch Match Implementation

Our implementation of patch match was done in C++ with a MEX interface to MATLAB. The basic patch match algorithm allows for best matches between a source and target image to be found quickly. The novelty in the algorithm is in its ability to greatly reduce the computational complexity of algorithms that require correspondence searches between a target and source image. In our implementation, we created a simple hole filling implementation where we used patch matching to find matches for patches that lied along the edge of the unfilled image region. Working inwards, the entire hole in the image was filled with consecutive layers until the hole was completed.

In tests, we found that the convergence of the algorithm to a final solution was highly dependent on the size of the hole. If we used two similar images for patch matching, such as an original image and a copy of that image with noise added, only 5-10 iterations of the propagation and random search steps were needed. This was similar for when we tested the method using a stereo pair as the source and target image.

In the examples presented below, the iteration number was set to 50. The higher iterations were likely due to the reduced number of patches that were searched for in each iteration. If we have an image where we are looking for patch matches for each pixel, there is a high likelihood that some of the initial randomly assigned correspondences are actually correct. Therefore, the propagation step allows correct pixels in a nearby region to be found quickly as well. When only filling in a small region of an image, the likelihood of initial matches being correct is lower, and therefore it takes longer for the algorithm to converge on the correct solution.

Click on image below to download video example:

Exemplar based inpainting (Criminisi et. al.)

We have implemented the exemplar based texture synthesis paper by Criminis et. al. In their paper, they present a novel and efficient algorithm for hole filling that replicates both texture and structure. They note that the success of structure propagation hinges on the order in which the filling proceeds. They have presented a best-first algorithm in which the confidence of the synthesized pixel values is propagated based on its linear connectivity. With this algorithm, broken lines tend to connect, thus realizing the “Connectivity Principle” of visual perception. The color values themselves are computed using an exemplar based synthesis. So the distance metric for choosing the right exemplar is based on the Sum of Squared Distance (SSD) on the image patches. The video demonstrates the algorithm on an example image.

Click on image below to download video example:

Extension: Exemplar based inpainting with augmented disparity based distance metric

In this final experiment, we wanted to see how well hole filling would work using 2 binocular views of the object. It can be argued that humans perform hole filling using experience, contextual information as well as depth cues. Of these, depth from disparity is perhaps at the lowest level of processing in the visual cortex. In order to see the performance on stereo images, we first obtained a depth map for the images. Such depth maps can be computed quite precisely using stereo image pairs, but for this assignment, we just loaded the ground truth depth maps associated with the images from the Middlebury stereo dataset. Using these depth maps, we proceed to define a new distance metric for choosing the right exemplar to copy texture from. The distance metric is a combination of the SSD on the color image patches, SSD on the disparity image patches, and a constraint that enforces patch sampling from behind the object that needs to filled in and not in front. The patch priority algorithm continues to be the same as that in Criminisi’s paper. The video demonstrates the algorithm on the same example image.

Click on image below to download video example:

Results

We have some more results in this section. The disparity maps associated with each image are shown in grayscale. The further the pixel, the darker it is in the disparity map. Below, we show some before and after examples using our patch match implementation, Criminisi, and Criminisi plus depth. In each example, we attempt to remove a single object from the scene. The images were taken from the Middlebury Vision data set.

Original Image	Depth Image	Patch Match	Criminisi	Criminisi w/ Depth