The goal of this assignment is to implement the image quilting algorithm for texture synthesis and transfer. Texture synthesis is the process of algorithmically constructing a large digital image from a small digital sample image by taking advantage of its structural content. Texture transfer means re-rendering an image in the style of another one (see the face on toast image above). The main idea of texture synthesise is to sample patches and lay them down in overlapping patterns, such that the overlapping regions are similar. The overlapping regions may not match exactly, which will result in noticeable edges. Texture transfer is achieved by encouraging sampled patches to have similar appearance to a given target image, as well as matching overlapping regions of already sampled patches. In this project I Implemented Image Quilting for Texture Synthesis and Transfer, a SIGGRAPH 2001 paper by Alexei A. Efros and William T. Freeman. The paper presents a simple image-based method to do texture synthesis and texture transfer. We can see first three parts of this assignment as below:
To synthesize a new texture image, as a first step one can simply take random blocks (patches) of a user defined size from the source image, and tile them until the output image is full. For this section I created a function quilt_random(sample, outsize, patchsize) that randomly samples square patches of size patchsize from sample in order to create an output image of size outsize. I started from upper-left corner to bottom-right corner. Samples randomly placement without overlap.
The results of this part are shown below:
This section consists of taking into account the overlapping region of each patch. That is, for every new patch to be added into the output image, one needs to compare (depending on the patch orientation) if there exist a vertical boundary, horizontal boundary or both with the last patch included in the output image. In this section we need to implement an algorithm that will sample similar square patches to create the texture. The added patches will overlap those already present in the output image. Instead of put image blocks side-by-side, new image blocks are put in such a way that they have overlapping regions with putted blocks. And instead of randomly selecting a block, and the most suited blocks from source images that overlapping regions have minimal distance (so-called error) from the overlapping regions of putted blocks are selected. Suitable blocks a selected randomly. This reduces the mismatch at edges of adjacent image blocks. I created a quilt_simple function (sample, outsize, patchsize, overlap, tol). Where outsize is the size of the output image, patchsize is the size of the patches to be sampled, overlap is the size of the overlap region (in pixels), and tol is acceptable tolerance level for patch to be sampled. First, I sampled a random patch and put it in the top left corner, then for next location I determined which pixels will be overlap with new patch. I calculated sum of squared differences (SSD) between the pixels in overlap and all possible positions in the sample. Low SSD means a high similarity. These patches overlaped horizontally as well as vertically. Then, I selected a random patch in positions having a relatively low score to add it to the texture image. For this purpose, we find the minimum score (minc) by function and then sample a patch among it. For the first patches minc will be 0. For solve this problem we set minc to a large but stil small value. We select maximum between minc and small cost value. I used odd value of patch size.
The results of this part are shown below:
This step takes into consideration the minimum cut path, that is, we want to make a cut between two overlapping blocks on the pixels where the two textures match the best (where the overlap error is low). In this section we need to implement the seam finding to remove edge artifacts from the overlapping patches. I implemented the algorithm in MATLAB to do this purpose. I Created a function cut(bndcost) that finds the min-cost contiguous path from the left to right side of the patch according to the cost indicated by bndcost. We use a dynamic programming to find the min_cost path because the cost of a path through each pixel is the square differences of the output image. After find this path, I define a binary mask by using this path. For top left overlap we need compute two seems, and the mask of these two seams is intersection of masks for each seam.