Texture synthesis and Texture Transfer with Image Quilting

CS129 Computational Photography Project 4

Image Quilting

Background

Texture synthesis is the process of constructing arbitrary large image from a small image sample by taking advantage of its structural content. Texture Transfer means re-redering an image in the style of another one. The example of both process is shown below.

Goal

The goal of this project is to implement Texture Synthesis and Texture Transfer. The algorithm used in this project follows the paper Image Quilting for Texture Synthesis and Transfer by Alexei A. Efros and William T. Freeman. The basic idea of this algoritm is to synthesize new texture by patches of the existing texture from smaller sample and stitching them together seamlessly.

Texture Synthesis and Texture Transfer

Texture Synthesis

Texture Synthesis is the process by which an arbitrary large image is constructed using the texture from source image. Thus by repeating this texture in an intelligent manner creates a larger image with same texture and minimum artifacts.

Texture Synthesis Algorithm

The high-level view of algorithm is described below :

To synthesize a larger image we traverse through it in raster scan order in steps of a block size (patch size).
The next step in this process is to find a patches in the sample image which overlaps with the previously selected block within some error tolerance. This is done by finding the SSD (Sum of Squared Difference) between overlap region of the blocks. The error tolerance varies from image to image. From all patches satisfying this constraint one patch is randomly selected.
To add the selected patch seamlessely we find a minimum cut between these overlapped blocked. This is done using dynamic programming. First the error matrix is generated taking the squared difference of the overlapped region. Then we compute the cummulitave error matrix from top to bottom. The bottom row with the lowest value is selected and the vertical error path from that value is the minumum cut required. This process is repeated in horizontal direction.
Finally, we construct the image by adding these blocks through minimum cut. The process is repeated for each block of the larger image going through it in raster scan order.

Some Texture Synthesis Example

Texture Transfer

Texture transfer is the process by which the texture of a source image is transferred to a target image. The resulting image looks like the target image but it is made out of the texture of the source image. The texture transfer example is shown below.

Texture Transfer Algorithm

As Image Quilting algorithm selects an output patch based on the local image information it can be used for texture transfer. Thus synthesizing a new block now depends on soruce image as well as the target image.

Whenever a block in the result image has to be synthesized the algorithm needs to find a suitable block in the source texture that satisfies the following conditions:
The block should have some agreement with the already synthesize part as well as the overlapped part. The algorithm tackles this part by taking SSD of the block and the already synthesized part.
The block should corresponds to the part of the image we want to re-render. This condition is checked by taking the SSD of the blurred image intensities of the block and the part of the target image.
The algorithm accounts how much the patch should match the conditions discussed above by following formula:


                % The Error term:
                
                error = (alpha) * (overlap_error + previous_synthezised_error) + (1 - alpha) * correspondence_error