cs129 / Texture synthesis and transfer with Image Quilting

In this project, we use an algorithm called image quilting that stitches together small parts of a texture to produce either a larger image made up of the texture (image synthesis), or to render a different object with that texture (image transfer). On the right is an example of image transfer. The unknown pokemon is rendered with a toast texture.

Image Synthesis

The goal of image synthesis is to produce a large image by putting together parts of a smaller image. In the example below, there are three different ways that I accomplish that using a grass texture. On the left is the naive method. The program simply puts together blocks that it samples randomly from the original texture. One can clearly tell in the naive method that this image is made up of a composite of smaller parts.

In the center image, I implemented a sum-squared differences method to find a patch that best "fits" given its neighbors. The algorithm first places a random patch from the grass in the top left. Next, we choose another patch and overlap it slightly with the original patch (the original patch's right edge with our new patch's left edge). I score how "different" the overlapping parts are by using SSD and repeat this process for a number of randomly selected patches. I then use the lowest scoring patch (the least "different") and place that on the image. For the other rows, it also overlaps the patch with the upper neighbor. Note that although the middle grass image looks more realistic, we can still easily see edges between blocks.

In the right image, I implemented the SSD method along with min-cut. When I find the best overlapping neighbor, I perform seamcarve to find the seam that has the lowest energy (in the left and top edges). Notice now in the right most grass picture, you cannot see the block edges as you could with just SSD.

Naive random placement of grass patches.

Placement of grass patches with SSD (no min-cut).

Placement of grass patches with SSD and min-cut.

One problem that arose was getting a lot of repeats as the "best" neighbor. Although with SSD these patches were deemed the best fit, it made the picture look artifical. Below, on the left, is an example of such an occurence. The toast no longer looks realistic because of the clear repeats. In order to resolve this, I stored all of the samples in a matrix along with their SSD scores. After iterating through all of the samples, I sorted the matrix and picked a random patch from a group containing a certain number of the minimum scoring patches. On the right is a result of that implementation.

Toast without optimization.

Toast with optimization.

Image Transfer

The goal of image transfer is to render an image with a texture form a different image. This is accomplished using an adjusted version of the image quilting algorithm for image synthesis. Whereas before I only compared each new patch with the neighboring patches, I must now compare the patch to the source image as well. The algorithm is implemented using a coarse to fine technique. First the larger patches are calculated purely from comparison with the source image. In the next iteration, the patches are smaller and are now compared against their neighbors, what was found in the first iteration, and the source image. Below are some of the results I got applying the algorithm to render various images with various textures.