CS 129 Project 4 Writeup

Jeroen Chua (jchua)
October 24 2012

Outline

I briefly describe a method to do image quilting and texture transfer, as described in "Image Quilting for Texture Synthesis and Transfer, A. Efros and W. Freeman, SIGGRAPH 2001" [1]. Broadly, the image quilting generates a new texture image given an input image by generating patches one at a time (with overlap). When choosing a patch to put into the synthesized image, the agreement of the patch with its immediate neighbours is considered. I implemented two methods when considering neighbour agreement: SSD on the overlap between the patch and its neighbours, and SSD+min-cut on the overlap between the patch and its neighbours. Both methods are described in [1]. In the case of SSD+min-cut, and overlap regions both above and to the left of the patch, I find the vertical min-cut and then the horizontal min-cut, and then merge the proposed cuts. For texture transfer, I use image intensities for the correspondance map.

Extra credit work

The output results for texture synthesis are sensitive to both the patch size used, and amount of overlap between patches. I examine the choice of patch size and overlap on the algorithm's results.

Result images for image quilting

All synthesized images are [320 480], and were synthesized using a patch size of [60,60], and an overlap of 10 pixels. The images, from left to right, are:
  1. Source: Original texture image
  2. Synth-SSD: Synthesized image using SSD
  3. Synth-SSD+min-cut: Synthesized image using SSD+min-cut
The results are discussed after the displayed images.

Click an image to see it at its full size.
Source Synth-SSD Synth-SS+min-cut

First, the algorithm works quite well for textures that do not exhibit "rigged" patterns. The grass texture (row 3), radishes (row 4), and rice (row 7), for example, are visually pleasing, and at first glance, look like perfectly good textures. However, for textures that exhibit a great deal of pattern, the algorithm has noticeable artifacts. For example, the brick texture (row 2) should contain strong horizontal and vertical lines, which is not so in the synthesized image. The bricks "break" or suddenly discontinue, which makes it immediately obvious that this texture was generated, and was not found in real life. The same can be said for the pentagon pattern (row 5). The SSD approach, as can be seen in the results, produces numerous "block" artifacts, which makes it clear that the texture was artificially generated. In general, the SSD+min-cut approach produces more visually pleasing results than the SSD approach. This is to be expected since using min-cut allows a more flexible way of combining patches, which may produce fewer artifacts.

Result images for texture transfer

All images were synthesized using an initial patch size of [42,42], and an overlap of 7 pixels. The images, from left to right, are:
  1. Source: Original image
  2. Texture: Original texture
  3. : Transfer: Original image rendered using the given texture
The results are discussed after the displayed images.

Click an image to see it at its full size.
Source Texture Transfer

The texture-transfered image do indeed look like the original source images, albeit with a significant lack of detail (although, getting small details, like the shape of the nose, is not at all possible with the coarse size of patches used). Note that the results are sensitive to getting roughly "appropriate" patches on the first pass of the algorithm, due to the error term that measures how well a synthesized patch agrees with the already-generated pixels it is completely replacing.

Varying patch size and overlap (graduate-credit)

The texture synthesis results rely crucially on the patch size and the amount of overlap used. Larger patches may introduce artifacts in overlap regions since there are more pixels to match at once, but produce regions of no artifacts in non-overlapping regions, since the pixels in such regions come from the source image itself. Using more overlap between patches may reduce the artifacts between patches, but results in an quadratic increase in run-time. I show results below, starting with keeping the patch size at 60, but varying the overlap size, using values [5,10,15,20]. I only show SSD+min-cut results for brevity (SSD+min-cut performs better, too). The images, from left to right, are:
  1. Source: Original image
  2. Synth-overX: Synthesized image using SSD+min-cut, with patch size of [60,60], overlap size of X pixels.
Source Synth-over5 Synth-over10 Synth-over15 Synth-over20

For more structure textures (eg, apples in row 1, pentagons in row 5), using a smaller overlap size produces synthesized textures closer to the original. This is to be expected, since having less overlap between patches means more of each patch is copied as a whole into the synthesized texture. Since the input texture, by defintion, has the kinds of (textured) structure we seek, the synthesized texture contains more of the (textured) structure when smaller overlaps are used since a greater proprotion of an input is copied over at once.

For more stochastic textures (eg, radishes in row 4, rice in row 7, toast in row 9), overlap does not appear to be critical- the synthesized textures look equally appealing (to me, anyway).

Finally, I show results for varying patch size, keeping the overlap size at 10 pixels. I only show SSD+min-cut results for brevity (SSD+min-cut performs better, too). The images, from left to right, are:
  1. Source: Original image
  2. Synth-patchX: Synthesized image using SSD+min-cut, with patch size of [X,X], overlap size of 10 pixels.
Source Synth-patch30 Synth-patch40 Synth-patch50 Synth-patch60 Synth-patch70

The patch size only matters up to being able to capture the intrinsic "scale" of any patterns in the texture. For example, for the radish texture (row 4), all patch sizes tested yielded equally appealing synthesized textures since the primary "unit" of texture is a single radish, which fits within the smallest patch size tested ([30,30]). On the other hand, for the pentagon texture (row 5), larger patches yielded synthesized textures that were visually more appealing. This is perhaps because the smaller patches are not large enough to capture the primary "unit" of texture (a pentagon), while largers patches are big enough to enclose single pentagons. This effect is especialyl apprent in looking at the results for patch size [30,30] and [70,70] (column 2, column6) for the pentagons- the textured synthesized using [30,30] patches contains virtually no pentagons, while the textured synthesized using [70,70] does contain pentagon patterns.