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