# 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.

### Sample texture

(Photo by NICSOLUCION / CC BY)

(Photo by webstreats / CC BY)

(Photo by James 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 Nicholas Laughlin / CC BY NC SA)

Sample texture (Photo by James Cridland / CC BY)

(Photo by Pattys-photos / CC BY)

(by sandeep MM / CC BY NC)

# Texture Transfer

Texture transfer works the same way – except the cost function is $\alpha \sum (A_{1} - A_{2})^2 + (1-\alpha) \sum (B_{1} - B_{2})^2$ where $A_1, A_2$ are the overlapping regions from the previous section and $B_1, B_2$ are the correspondence maps. Correspondence maps are the intensities of the sample texture patch and the corresponding background image patch.

# Texture Transfer and Laplacian Pyramid Blending

(Original Jeremy Brooks / CC BY NC)

(Original Pattys-photos / CC BY)

(Original James 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 Nicholas Laughlin / CC BY NC SA)

### Another example

iterative:

non-iterative:

sample:

(Photo by PKub / CC BY NC SA)