cs129 / Texture synthesis and transfer with Image Quilting

CS129 / Project 4 / Texture synthesis and transfer with Image Quilting

1.Texture Synthesis

The goal of texture synthesis is to construct unlimited amount of image data from a sample of texture by taking its structural content. And the process of image quilting is to synthesize a larger image by attaching small patches of existing texture. In the first part, we implement quilting by Best SSD match algorithm which presents decent results. In the second part, we extend the SSD algorithm by adding minimum path finding procedure, which makes the results even better.

1.1 Best SSD Match

To achieve the optimal patch from source texture, which has the relatively small SSD error with the previous patches(left and above) on the overlap region, (1)we search the source texture exhaustively. And for every possible patch from source texture we calculate the SSD error with the previous patches on the overlap region and find the minimum error value. (2)To avoid repeating results, we sample a patch randomly within some tolerance of the minimum error. Here is one thing we should notice that there is always one patch that will make the SSD error equal to 0, so when we try to obtain the tolerance range(minimum_error*tolerance), the result will always be 0. To avoid such result, I set the SSD error of that situation to infinite.

1.2 Best SSD Match with Minimum error path

The results produced by Best SSD Match are pretty good, but still have several obvious edge artifacts on overlap region. To improve this, we add one more step after SSD match.

Here is the method:

Find the optimal patch through Best SSD Match algorithm
Calculate the error surface between the previous patches and the optimal patch at the overlap region: (overlap_optimal-overlap_previous).^2
Find the minimum error path by Seam Carving algorithm and that path with the minimum energy cost is the boundary of the overlap region of the optimal patch.

1.3 Result Images

Random	SSD Match	SSD with Minimum path

2.Texture Transfer

What does Texture transfer do is re-rendering an image with samples from a different texture. Based on the texture synthesis algorithm we just mentioned, now the optimal patches we pick up have to respect 2 constrains:(1)It should have small SSD errors with the patches we already synthesized at the overlap regions. (2)It should have some correspondence(eg.image intensity) with the source image at according regions. To obtain the optimal patch, we search every possible patch in the given texture exhaustively and pick up the minimum error which respects: error = alpha*(overlap_error+previous_error) + (1-alpha)*correspondence_error, where 'overlap_error' is the SSD match error between the patch and previous synthesized patch at the overlap region. And 'previous_error' is the SSD error between current patch and the patch from last iteration at same place, in the first iteration this value equals to 0. The 'correspondence_error' is the SSD error between the intensity of current patch and the patch from source image at according region. To make the result look better, we should iterate over the synthesized image 3-5 times and change the alpha value accordingly(alpha = 0.8*(current_iteration-1)/(whole_iteration_number-1) + 0.1).

2.1 Result Images

Raw Texture	Source Image	Re-rendering Image

3.Extra Credit

3.1 Graph Cut

In the session 1.2 we use dynamic programming to choose the minimum energy cost path from the overlap regions. In this part, we use different way Graphcut to find a good cut at the overlap region of current patch and previously synthesized patch. The core of the Graphcut algorithm is to generate a neighbor edge weights graph where every node represents the weight of edge between two adjacent pixels(4-way neighbors). The edge weight equals to M = SSD(first_image(current_pixel)-second_image(current_pixel)) + SSD(first_image(neighbor_pixel)-second_image(neighbor_pixel)). The edge weight shows the 'price' we break that edge.

Here is the method:

Generate the neighbor edge weights graph for every edges of two adjacent pixels (every pixel has 4 neighbors: up, down, left, right) and set source and sink edge weights to infinite
Using max-flow/min-cut algorithm to label the overlap region to show the current pixel should come from first or second image, in the other word, to find the optimal cut which cost lowest according to the graph.

3.2 Poisson Blending

After doing minimum path find we want to make the results more seamless by using poisson blending to the target and source images. In this case, target image is the overlap region of the previously synthesized patch and source image is the overlap region of the optimal patch we choose from the Best SSD match precedure, and the mask is generated basing on the minimum path finding result.

Result Images

SSD with Minimum path	SSD with Graphcut	SSD with Minimum path and poisson blending

3.3 Different tilesize and overlapsize

In the part, I experimented 3 different tilesizes with 3 different overlapsizes and it left a big effect on the results. The 3 tilesizes are 60 with the overlapsizes 5,10,20, 30 with the overlapsizes 2,5,10, and 90 with the overlapsizes 7,15,30. As we can see below, when the patches have the same tilesize, the bigger the overlapsizes are(non-extreme situation), the better the results are, especially for the SSD with min path version. On the other hand, the bigger the overlapsizes are, the more time will be cost when generating the new patch. When the ratios of the tilesize and the overlapsize are the same, the bigger of the tilesizes are, the more decent of the results are because the number of the overlap regions will be smaller and the time cost seems smaller but it may cause more repeatable results because of less possible patches from the raw texture.

3.3.1 Example Images

Random	SSD Match	SSD with Minimum path

tilesize 30, overlapsize 2

tilesize 30, overlapsize 5

tilesize 30, overlapsize 10

tilesize 60, overlapsize 5

tilesize 60, overlapsize 10

tilesize 60, overlapsize 20

tilesize 90, overlapsize 7

tilesize 90, overlapsize 15

tilesize 90, overlapsize 30

3.4 Different correspondence quantity

In the session 2, we used image intensity as the corresponding quantity to represent the brightness of the according patches. In this part, we change the the quantities to the SSD errors of the color and gradient. As the result image show, color quantity works well but the gradient quantity not work as good as the intensity one for the gradient cannot reflect the luminance of the image directly but the boundary condition.