CS129 / Project 4 / Image Quilting for Image Synthesis and Transfer

Introduction

In this project, texture synthesis and transfer are implemented based on image quilting. Patch-based image analogies is also implemented as an extra credit.

Image quilting is the process of generating new images by stitching together patches from existing images. Texture synthesis is the process of generating a new texture based on a given texture, where the new texture could have larger size than the given texture. Texture transfer is the process of taking two input images - the texture and the source image - and output a target image which resembles the source image but is formed solely by pixels from the input texture.

Texture Synthesis

Three different patch-based methods are implemented for texture synthesis: 1) random patch selection, 2) best SSD matching, and 3) best SSD matching + minimum error path.

Random patch selection is the simplest case. In this case, the program simply iterates through the output texture (initialized to have zero values everywhere) patch by patch, and for each patch to be filled in, it selects a patch from the input texture at random and copies it over.

The SSD matching method takes into consideration the patches that have been placed when placing each patch. The first patch is selected from the input texture at random. After that, each patch to be filled in overlaps with the previously placed patches, both vertically and horizontally. When selecting the patch to be copied over, the algorithm iterates through all the possible patches from the input texture, and calculate the sum of squared difference between the overlap region in the output patch and the corresponding region in the input patch. To avoid excessive repetition, the algorithm selects one patch at random from all the patches that has a SSD within 1.1 times of the minimum SSD error across all the possible patches.

In the third method, after choosing the patch to be copied over to the output texture, two minimum error paths (left and top) are calculated and only pixels to the right and bottom of the two paths are copied to the output texture. To compute the two minimum error paths, an error matrix is first constructed by calculating the squared difference between every pair of pixels from the overlap regions of the input texture patch and output texture patch respectively. Then, the find_min_path code from project 3 is applied on the error matrix to get the two minimum error paths.

Result 1: Texture Synthesis

Here are the texture synthesis result obtained using 1) random patch selection, 2) best SSD matching, and 3) best SSD matching + minimum error path. All the results are obtained with tile size = 60 pixels and overlap size = 10 pixels.

OriginalRandomSSDMin cut

Overall, the result of the SSD + min cut algorithm is always better than using SSD alone. Also, SSD alone is always significantly better than random selection.

Texture Transfer

The texture transfer algorithm also produces the output image by coping patches from an input texture, but it takes into consideration of both how well a patch matches the previously placed patches and how well it matches the corresponding patch in the input image. In this implementation, the squared difference in image intensity is used to measure how well a patch matches the corresponding patch in the input image. For all the examples below, the tile size used is 42, overlap size 7, and number of iterations is 3. To speed things up, the algorithm does not iterate through all the possible patches in the input texture, but instead only iterate through 1/20 of all the possible patches, chosen at random with replacement.

Result 2: Texture Transfer

TextureOriginal imageOutput image

Patch-based Image Analogies

Given a set of images A, A' and B, an image analogies algorithm aims to produce an image B' where the mapping between B and B' is, ideally, the same as the mapping between A and A'. Or the mapping should be as close as possible. Usually we assume that A' is produced by applying a filter on A.

The patch-based image analogies algorithm produces B' by selecting a patch in A that matches a particular patch in B, and then copies the corresponding patch in A' to the appropriate pixels in B'. In this particular implementation, the algorithm combines SSD and minimum error path, similar to the texture transfer algorithm described above. The only difference is that while in the texture transfer algorithm, the algorithm matches patches from the texture with patches from the image and copies patches from the texture, here the algorithm matches patches from two images A and B and copies patches from another image A'. The tile size used in the implementation is 20, and the overlap size is 5.

Result 3: Patch-based Image Analogies

For images on row 1, lomo effect is applied on the source image. For images on row 2, a Gaussian blur filter has been applied on the source image.

Source Source - filtered Target Target - filtered

The patch-based image analogies has two inherent limitations. First, as we can only draw pixels from the input filtered image to form the output "filtered" image, the expressiveness of the algorithm is limited. If the input images A and B are very dissimilar, then the result might look pretty bad simply because it is difficult to find good match. Also, as the algorithm is patch-based, it is likely to have noticeable artifacts on the boundaries between different patches. This might be improved by applying Poisson blending and/or by using smaller patch size, though.

Effect of tile size and overlap size

To qualititively evaluate the effect of different tile sizes and overlap sizes, I have run experiments on five textures with tile sizes 10, 30, 60 and 120. For each of the tile sizes (except tile size 10), two overlap sizes - 1/6 of the tile size and 1/3 of the tile size - were tested. Experiments were run with both SSD and SSD + min error path, but as there was no significant difference between these two in terms of tile/overlap sizes, here we only show results based on SSD + min error path.

Result 4: Effect of tile size and overlap size

Effect of tile size (tile size from top to bottom: 10, 30, 60, 120):

Effect of overlap size (first row: tile size = 30, overlap size = 5; second row: tile size = 30, overlap size = 10):

In general, it looks like using smaller tile size increases the variety within the output texture, but also often fails to preserve structures of relatively large scale. On the other hand, using larger tile size often preserves large scale structure, but may produce texture that looks repetitive. For example, the output of the toast texture looks better with tile sizes of 10 and 30 and looks unnatural with larger tile sizes, presumably because toasts consist of finer structures. Meanwhile, the apple and autumn leaves textures both look better with larger tile sizes, and start to lose the basic structures (single apple and single leaf) with smaller tile sizes. Overall, I think different types of textures require different tile sizes to get the best outputs.

The tests for different overlap sizes might be inadequate. But roughly speaking, smaller overlap size tends to err on the side of having more observable seams, while larger overlap size on the side of having more repetitions.