COS 429 - Computer Vision

Spring 2004

Assignment 2

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:

• Read in a source image
• Take as input the following parameters:
  • The tile size
  • The amount of overlap between tiles (by default 1/6 of the tile size)
  • An error tolerance (by default 0.1)
  • The destination image size
  (To simplify things, you can assume that an integral number of tiles will fit. That is, for some positive integer n,

  destination size = n * tilesize - (n-1) * overlap

• Seed the output image by copying a random tile from the source image to the top-left corner of the destination.
• Proceeding in raster order (left-to-right, top-to-bottom), fill in new tiles:
  • For each possible tile position in the source image, find the sum of squared differences (SSD) between that tile and the existing destination image, in the overlap region. For RGB images, find the total SSD over all three color channels.
  • Find all tile positions that have SSD errors less than (1 + tolerance) times the best SSD error.
  • Pick a random tile from the above, and copy it to the destination image.

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 B₁ and B₂, overlapping in some region. Compute an error image e, equal in size to the overlap region, where e_ij is the squared difference between pixels ij in B₁ and B₂. 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 E_ij 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 E_ij as just e_ij 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:

• Constrained texture synthesis (see the Efros and Leung page)
• Texture transfer
• Multiresolution blending between tiles based on the techniques of Burt and Adelson (instead of min-cut)

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:

• Your texture synthesis code (as one or more .m files).
• Synthesized textures for the two images listed above, as well as 2-3 images of your choosing (using an appropriate tile size).
• A README or README.html file containing comments on your experiments with different parameters, and any relevant implementation notes.