# Project: Textures and Seams

## Logistics

• Files: Github Classroom.
• Extra disk space: /course/cs1290_students
• Part 1: No questions this week; the project has more code to write, and you can catch up with the labs.
• Work on your lab submissions.
• Part 2: Code
• Required files: code/, writeup/writeup.pdf —use the 'createSubmissionZip.py' script.
• Due: Weds 11th Nov. 2020, 9pm.

## Background

We will implement Image Quilting for Texture Synthesis and Transfer, a SIGGRAPH 2001 paper by Alexei A. Efros and William T. Freeman. The paper presents a simple image-based method to perform texture synthesis and texture transfer. Texture synthesis is the process of creating an image of arbitrary size from a small sample (grass sample above). Texture Transfer means re-redering an image in the style of another one (Abraham Lincoln above).

## Requirements / Rubric

• +30 pts: Texture Synthesis: Best SSD match
• +30 pts: Texture Synthesis: Best SSD match + minimum error path
• +20 pts: Texture Transfer
• +10 pts: Use your algorithm on three of your own images.
• +10 pts: Write up your project (writeup/writeup.pdf). Describe your process and algorithm, show your results as images and output values, describe any extra credit and show its effect, tell us any other information you feel is relevant, and cite your sources. We provide you with a LaTeX template in writeup/writeup.tex. Please compile it into a PDF and submit it along with your code. In class, we will present the project results for interesting cases.
• +10 pts: Extra credit (up to ten points)
• -5*n pts: Lose 5 points for every time (after the first) you do not follow the instructions for the hand in format

## Extra Credit

The baseline will work reasonably well for many images, but for certain types of images there are very noticable failures. In particular, humans are very sensitive to distortions in faces and distortions in straight lines. Images with large areas of high-frequency texture also tend to behave oddly with simple energy functions.

Here are some ideas, but we will give credit for other clever ideas:

• up to 3 pts: Use Poisson blending to make things more seamless.
• up to 3 pts: If you want to speed things up, you can calculate the SSD between a region and the entire input image (texture) efficiently by using filtering operations.
• up to 5 pts: Experiment with different correspondance quantities for texture transfer and report your findings.
• up to 5 pts: For some textures it can make sense to take samples at different scales and orientations. Also, varying the tile size can potentially help to get better results.
• up to 5 pts: The tile size and the overlap size can have a big influence on the result. Run experiments with varying values for those parameters an report your results.
• up to 10 pts: There are other strategies to find a good cut in the overlapping regions, e.g., graphcut. Take a look at Project 3 of CSCI 1290 previous offering for some explanation.
• up to 10 pts: Implement a patch-based "image analogies" technique as per Hertzmann et al.

For all extra credit, be sure to demonstrate on in your report where your extra credit has improved image quality or created an interesting effect.

## Hand in

You will lose points if you do not follow instructions. Every time after the first that you do not follow instructions, you will lose 5 points. The folder you hand in must contain the following:

• code/ - directory containing all your code for this assignment
• writeup/writeup.pdf - your report as a PDF file generated with Latex.

To create the ZIP file to submit run:

 >> createSubmissionZIP.py

from the command line. Make sure you are in the root project directory, and that you keep the name writeup.pdf for your report. Upload the generated ZIP file to Gradescope.

## Details

### Texture Synthesis

The general idea of the presented texture synthesis method is to 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. This is what the stencil code does. With this solution the overlapping regions are not likely to match and this will result in noticeable edges in the result. 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). This will already produce pretty good results but still has some unwanted edge artifacts. To get rid of those, your final implementation will try to find a minimum error cut for the overlapping region.

Figure 2 of the paper illustrates those 3 different methods:

The stencil code produces images as shown in (a). Your job will be to fill out the parts of student.py that will produce results like in (b) and (c) in the above figure. Run python main.py --help to see how to run the code.

### Texture Transfer

We can augment the texture synthesis approach above to get a texture transfer algorithm. That is re-rendering an image with the texture samples of a different image. 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), and (b) it should have some correspondance with the image we want re-render. We will use a parameter $$\alpha$$ 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.

The paper suggest to run multiple iterations of this while decreasing the tile size and adjusting $$\alpha$$ each time to get the best results. The stencil does that for you. If we run multiple iterations we will need to incorporate the agreement of a patch with the already synthesized image and not just with the overlap region. So the error term will end up being something like this:

error = ($$\alpha$$) * (overlap_error + previous_synthezised_error) + ($$1 - \alpha$$) * correspondence_error

Note that previous_synthezised_error will be 0 for the first iteration. Your code for this will go into the get_patch_to_insert_transfer function.

### Implementation Tips

• Read the paper if you get stuck. It is pretty easy to understand and reveals a lot of the details.
• 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 (make sure you special case if minimum_error = 0, especially if you do exhaustive search):
[y, x] = find(errors_of_all_patches <= minimum_error * (tolerance))
Another approach would be to sort all the patches according to their error and then randomly sample from the best $$N$$ patches.
• There are different ways you can sample the input texture for a patch. You can do an exhaustive search over every possible patch or you could search over a fixed number of randomly drawn samples.
• Minimum error cut sounds a lot like seam carving? Yes, it is. You will have to calculate two cuts for most patches (for the left and the above overlap region). To calculate a cut path in the overlapping region of a new block using dynamic programming:
1. Compute the energy matrix $$E$$ for your image (e.g., the gradient magnitude, or the absolute sum of gradient energy across the three color channels).
2. Initialize a scoring matrix $$M$$ of size of your image and with the energy matrix $$E$$ values.
3. Set the values of every entry in the matrix except for the first row by adding to it the minimal value in any of the cells above it within one column distance: $$M(x,y) = E(x,y) + min( M(x-1,y-1), M(x,y-1), M(x+1,y-1) ).$$ You'll have to do this in an order such that $$M(...,y-1)$$ is defined at the time it's evaluated—row by row works. Also be aware of boundary conditions.
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.

## Acknowledgements

Project derived from Image Quilting for Texture Synthesis and Transfer. Description and setup inspired by CS498 at University of Illinois at Urbana-Champaign. Some code taken from other projects of Brown CSCI 1290 or Brown CSCI 1430.