Image Quilting

The goal of this project is to implement the image quilting algorithm for texture synthesis and transfer using the approach described in the SIGGRAPH 2001 paper by Efros and Freeman.

The image quilting algorithm synthesizes texture by stitching together small patches of existing images in a consistent way. Given a sample of texture, it can be used to generate an unlimited amount of image data that resemble the input. The idea behind image quilting is that the unit of texture synthesis should be a patch rather than a pixel.

Comparison of random, overlapping, seam-finding methods

Left: Randomly sampled square patches. Simplest but least effective method. Middle: The patches were selected so that the distance between the overlapping regions is minimized. Neighboring patches look more natural compared to the random method, but the edge artifacts are still noticeable. Right: In addition to minimizing the difference in the overlapping region, the seam-finding algorithm finds the min-cost boundary that minimizes the difference along the edge.

Another example

Sample texture

(Photo by flickrNICSOLUCION / CC BY)

(Photo by flickrwebstreats / CC BY)

(Photo by flickrJames Cridland / CC BY)

How seam-finding works

Start by placing a randomly selected patch in the left-most block of the first row. The algorithm then finds the next patch and fills the next block as illustrated below:

Step 1

In a set of randomly sampled patches, compute the cost, the sum of squared differences (SSD), of the overlapping regions ( in the example above) for each and select the patch with the minimum cost – or randomly select from a set of low-cost patches depending on the error tolerance value.

Step 2

Compute the seam: the minimum cost path that divides the two patches at the overlap region – and make that the boundary of the new block. The cost here is the sum of the pixel value differences along the path. Finding the path can be done easily using dynamic programming.

Total cost: 8.9011

Step 3

Mask out the region outside the computed boundary, fill the block, and repeat. Starting at the second row, both horizontal and vertical overlaps need to be considered.

More results

(Photo by flickrNicholas Laughlin / CC BY NC SA)


Sample texture (Photo by flickrJames Cridland / CC BY)


(Photo by flickrPattys-photos / CC BY)


(by flickrsandeep MM / CC BY NC)

Texture Transfer

Texture transfer works the same way – except the cost function is where are the overlapping regions from the previous section and are the correspondence maps. Correspondence maps are the intensities of the sample texture patch and the corresponding background image patch.

Bells & Whistles

Texture Transfer and Laplacian Pyramid Blending

(Original flickrJeremy Brooks / CC BY NC)

(Original flickrPattys-photos / CC BY)

(Original flickrJames Cridland / CC BY)

Iterative Texture Transfer

Iterative texture transfer preserves the texture of the sample image by iteratively reducing the block size and overwriting to the previous output. The example below (iterative) starts with patch size 47x47 pixels then reduces the size by 1/2 each time.

iterative:

non-iterative:

sample:

(Photo by flickrNicholas Laughlin / CC BY NC SA)

Another example

iterative:

non-iterative:

sample:

(Photo by flickrPKub / CC BY NC SA)