COS 429 - Computer Vision

Spring 2004

Course home Outline and lecture notes Assignments


Assignment 2

Due Thursday, Mar. 11


Texture Synthesis using Image Quilting

The goal of this assignment is to implement texture synthesis using the Image Quilting algorithm of Efros and Freeman. The paper and some sample results are available from http://www.cs.berkeley.edu/~efros/research/quilting.html.


Basic algorithm: Your code should do the following:


Min-cut: Once you have the basic version (just copying tiles) working, implement the algorithm for finding a minimum-error cut between overlapping tiles, following the approach described in Section 2.1 of the Efros and Freeman paper. Briefly, the idea is the following:

Assume we have horizontally-adjacent blocks B1 and B2, overlapping in some region. Compute an error image e, equal in size to the overlap region, where eij is the squared difference between pixels ij in B1 and B2. We now want to compute a min-cost path through e, from top to bottom. In order for the path to be smooth, we must ensure that, where the cut path crosses row i, it is either in the same column as in row i-1 or one column to the left or right.

To help us compute the cut path, we construct a second array E, where the value stored in Eij is the minimum cost of all partial cut paths starting at the top of the image and passing through pixel ij. A naive algorithm for filling in the entries of E would require recursive evaluation of many paths, but we can take a shortcut by observing that any path passing through (i,j) must also pass through either (i-1,j-1), (i-1,j), or (i-1,j+1). So, if we fill in entries of E from top to bottom, we can find Eij as just eij plus whichever of the above three entries is the smallest. We can therefore fill in E without any recursive calls. Then, starting with the minimum entry in the bottom row and walking back up to the top, we can extract the minimum cut path.

Be aware that you will have to do the min-cut twice per tile, once along the left edge and once along the top.


Evaluating the results: Run the texture synthesis algorithm on the weave.jpg and text.jpg images, as well as 2-3 images of your choice, generating images approximately twice the size of the original. Describe the effects of changing parameters, especially the tile size. Show any particularly entertaining failure cases you encounter.


Extensions: Though not required, you may implement the following for extra credit:


Submitting

This assignment is due Thursday, March 11, 2004 at 11:59 PM. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.

Please submit: