image quilting

Project 4: Image Quilting for Texture Synthesis and Transfer

Synthesizing images by stitching together small patches.

Due Date: 11:59pm on Wednesday, October 24th, 2012

Brief

MATLAB stencil code is available in /course/cs129/asgn/proj4/stencil/. You're free to do this project in whatever language you want, but the TAs are only offering support in MATLAB.

Background

In this project you 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 do 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

You are required to implement the texture synthesis and texture transfer method explained in the paper. You should run both algorithms on at least 3 of your own images in addition to the test cases we provide.

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. And actually 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 get_patch_to_insert_synthesis.m that will produce results like in (b) and (c) in the above figure. You can run proj4_synthesis.m.

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 α 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 α 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 = (α) * (overlap_error + previous_synthezised_error) + (1 - α) * correspondence_error

Note that previous_synthezised_error will be 0 for the first iteration. Your code for this will go into get_matching_patch_transfer.m. You can run proj4_transfer.m.

Implementation Tips

Write up

For this project, and all other projects, you must do a project report in HTML. In the report you will describe your algorithm and any decisions you made to write your algorithm a particular way. Then you will show and discuss the results of your algorithm. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant.

Include the given images and at least three images from an outside source for both algorithms.

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:

For all extra credit, be sure to demonstrate on your web page cases where your extra credit has improved image quality.

Graduate Credit

To get graduate credit on this project you must do one form of extra credit of sufficient difficulty. Any of the suggested extra credit satisfies this requirement.

Handing in

This is very important as 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 at the root:

Then run: cs129_handin proj4
If it is not in your path, you can run it directly: /course/cs129/bin/cs129_handin proj4

Rubric

Credits

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 CS129 or Brown CS143.