Texture synthesize

Part I) Randomly sampled texture, no overlap

This assignment asked us to synthesize a new texture form an input image. To do this, we can simply select random patches (blocks) from the input image and then copy and paste them to synthesize a texture. Although this way is profoundly easy, the resultant image has bad quality.

Part II) Simple Quliting Image

The second approach, which I implemented it, is more sophisticated (called simple quilting algorithm). Instead of copying and pasting random patches to generate a texture, it selects one patch that is similar to the neighbor patches (left neighbor patch and up neighbor patch). As we expect, this approach synthesizes better results than the random approach, though yet we can see some artifacts in the output of this algorithm. Although the algorithm tries to choose a patch that is similar to the its spatial neighbor patches, it can not prevent some artifacts like edges appear in the resultant image.

In all the experiments, I set the width of the overlaping region set to 1/6* size(patch). To choose a right patch from the input image so that the output image seems both random, and smooth, we are suggested to add a tolerance to the minimum score. Imagin this, if the minimum score became zero or a small value, then the algorithm select exactly the previous patch or its spatial neighbors in the input image. Therefore, the resultant image is very similar to the input image since its patch come from a specific region of the input image. Therefore, we avoid this happning by replacing zero or very small ssd with a very big number like 1000 . In that situation, we are sure that selecting patch is not the previous patch nor its neighbor.

Part III) Seam Finding

To remove these artifacts and synthesize more smooth texture, which means a texture without abruptly changes, Efros and Freeman suggested a novel approach (called image quilting algorithm) in the paper. They introduced the idea of Minimum Error Boundary cut. Instead of changing the overlap region by the new patch, find a path through the overlap region that divide the overlap into two parts. The left parts filled by the left patch's pixels, and the right part filled by the new patch's pixels. Finding the minimum path is done by dijikstra algorithm in that way. We compute the squared error for the overlap region by subtarcting the overlap region of the new patch and the overlap region of its left neighbor patch( called ssd_overlap), and then consider this ssd_overlap as a graph which has (patchsize*overlapsize) nodes where its nodes are the pixels of the region, its edges connect each pixel (node) to its spatial neighbors. Finally, Dijikstra algorithm is applied for finding the low cost (minimum) path. It is worth to mention that for template matching I implemented SSD not using Matlab's function xcorr2.

textur borrowed from here

Texture Transfer

We can use the previous approach to painting a image( called target) with a texture( called source). For this goal, an additional constraint should be added to the previous constraint. In other words, to selecting a patch from the source, not only this patch should be similar to its left and up neighbors in the output image, but also it's intensity (illumination) should be similar to intensity of the patch from the target image. Therefore, I used this following formula where alfa = 0.2:
alfa*(Bi - Bi+1)2+(1-alfa)*(Bi+1-Ti+1)2
Source ImageTarget ImagePainted Image, patch size = 20
Source Image from hereTarget ImagePainted Image, patch size =10

Extra Credit

I implemented the iterative version of the texture transfer algorithm, as the paper explained. In order to enhance the quality of the resultant image, the texture transfer algorithm should be repeated three times(N=3) where in each iteration the size of patch is reduced by 1/2, and the parameter alfa changed by the formula: alfai = 0.8*(i-1)/(N-1)+0.1 In this version, not only a patch should be similar to spatial neighbors, but also it should be similar to the patch of the previous iteration. In this situation, the quality of image extermly increased. Unfortunatly, I could not show my result here, since my algorithm run verey slowly, since for tempelate matching I implemented ssd by myself instead of using Matlab functions like Xcorr2, filter2.