Computational Photography and Image Manipulation

In this assignment, we will implement the texture synthesis method we covered in class: Efros and Freeman , Image Quilting for Texture Synthesis and Transfer, SIGGRAPH 2001.

Due date: Tuesday, November 26, by midnight Assignment data: Data - zip file

Part 1: Texture synthesis (70 pts)

The general idea of the presented texture synthesis method is to sample patches from the input texture and compose them in an overlapping way. By given an input texture image, firstly sample patches from the input texture and compose them in an overlapping way.

The simplest solution would be to just randomly select a patch from the input texture each time. With this solution the overlapping regions are not likely to match and this will result in noticeable edges in the result. We will call this method ‘Method 1’.

A better approach, which you will need to implement, is to find a patch in the input texture that has some agreement with the pixels in the overlapping region (e.g., small SSD error). Specifically, Just taking the “best” patch according to SSD could result in repeating patterns in the result. To get a more stochastic result you can sample a patch within some tolerance of the minimum error:
[y, x] = find(errors_of_all_patches <= minimum_error * (tolerance))
Or, you can sort all the patches according to their error and then randomly sample from the best N patches. This is ‘Method 2’.

The method above will already produce pretty good results but still has some unwanted edge artifacts. To get rid of those, your will try to find a minimum error cut for the overlapping region in Method 3. Computing the minimum error cut path in the overlapping region of a new block, we can use dynamic programming in a similar way to seam carving for image retargeting as we covered in the lecture. The strategy can be summarized as follows:

1- Compute the energy matrix E for the overlapping region (e.g., the overlapping error, the difference between two patches).
2-Initialize a scoring matrix M of size of the overlapping region with the energy matrix E values.
3- Set the values of every entry in the scoring matrix row by row (except for the first row) by adding to it the minimal value in any of the cells above it within one column distance.
4- Find the minimal value in the bottom row of the scoring matrix. This is the bottom of the minimal error cut.
5- To produce the final cut, trace back up M by following the smallest value in any of the positions above it.

Figure 2 of the original paper provides a nice demonstration of these 3 methods.

For these methods, we will have the patch size parameter. The ideal patch size changes from texture to texture, and you should determine a good patch size for each of the textures you synthesize and report this value in your report. Method 2 and Method 3 also have the size of the overlapping region as a parameter, which you should determine with experimentation and report.

In the data provided for the assignment, you will find 10 texture examples that you will extend. The final size of the generated textures should be 5 times larger than the input image in both width and height. You should show the results for each texture using the 3 methods defined above. For ‘grass’, ‘random3’ and ‘text’, show additional results using Method 3 using a smaller and larger patch size than the one you determined and comment on the results.

Part 2: Texture transfer (30 pts)

Texture Transfer means re-rendering an image in the style of another one.

We can augment the texture synthesis approach above to get a texture transfer algorithm. Like texture synthesis, each sample patch that we add to our synthesized image must now respect two different constraints:
(a) it should have some agreement with the already synthesized parts (this is the constraint we used in texture synthesis)
(b) it should have some correspondence with the image we want re-render. We will use a parameter \(α\) to determine the tradeoff between these to constraints.

To come up with a term for part (b) we need some measurement of how much a patch agrees with the underlying image. We can do this by calculating the SSD of a patch and the image on some corresponding quantity. One such quantity could be image intensity or the blurred image intensity. So the error term will end up being something like this:

error = (α) * (overlap_error + previous_synthezised_error) + (1−α) * correspondence_error

You should transfer the rice and toast textures into the images of Lincoln and Monroe as provided in the assignment data, showing 4 examples in your report. You should experimentally determine and report the α values you end up using for each pair. For one example of your choosing, provide extra results with different α values and comment.