Computational Photography, Spring 2016

Project #3: Image Quilting for Texture Synthesis and Transfer

Click here for source codes!

Date Submitted: 22 Mar 2016

445167 (Carol (Xu) Han)
446216 (Ying Wang)

Project Description

In this project students will implement 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. Texture synthesis is the process of creating an image of arbitrary size from a small sample (grass sample above). Texture Transfer means re-redering an image in the style of another one (Abraham Lincoln above).Students are required to implement the texture synthesis and texture transfer method explained in the paper.
-- Courtesy of Course Website

In this assignment we use matlab to implement the required algorithm: Image Quilting for Texture Synthesis and Transfer.

Texture Synthesis

Concept

The general idea of the presented texture synthesis method is to sample patches from the input texture and compose them in an overlapping way. The simplest solution would be to just randomly select a patch from the input texture each time. And actually this is what the stencil code does. With this solution the overlapping regions are not likely to match and this will result in noticeable edges in the result. A better approach, which you will need to implement, is to find a patch in the input texture that has some agreement with the pixels in the overlapping region (e.g. small SSD error). This will already produce pretty good results but still has some unwanted edge artifacts. To get rid of those, your final implementation will try to find a minimum error cut for the overlapping region.
Figure 2 of the paper illustrates those 3 different methods:

Inplementation

The procedures we did to implement the algorithm is described as follows:

  • First, we generate a large target texure image. In steps of a patch size, we iterate through it in raster scan order.
  • Second, we randomly sample a patch from the source texture image for every place in the target image.(perform exhaustive search to determine similar blocks) The texture overlaps with the previously selected patches within some error tolerance. Note that for each candidate patch from the source image, we calculate the SSD error with previously selected patches on the overlap area, and then randomly pick the patch with the minimum error for a best SSD image.
  • Then to reduce the seams, we need to find a minimum cut on the overlap region by dynamic programming. To do this we first need to find the optimal patch through minimum SSD. Then, calculate the error surface between the previous patches and the optimal patch on the overlap region. Finally, the minimum error path on the error surface found by seam carving algorithm is chosen as the new patch boundary. We use backtrace to find the cut.

Results

Here are the images we used as shown below, we have the source image, the random image, the best SSD image and the best SSD + minimum cut image. In the table, you may compare those images and their algorithms. The random one is a naive method, where the randomly selected patches are placed side by side. The image on the Best SSD image corresponds to the method by choosing the patch with minimum SSD on the overlap region. The rightmost image illustrates the result of lowest SSD with minimum cut.

Source Random Best SSD Best SSD + Minimum Cut
Analysis

The images displayed above detail the tree types of quilting algorithms implemented in this project. The first algorithm is the worst, which randomly sampled the patches from the given texture image, and placed them in the final result. Apparently, the patches are pretty evident and have distinct boundaries. This is a major issue with this texture synthesis method.

The second algorithm was a simple quilting algorithm that tried to find the patches in the source which closely matched an overlapping region of a new patch with pre-existing values from already placed old patches. This made for a much better result and as shown above, the patches are hard to distinguish unless one zooms in close to the image.

However, the final method was certainly the best since it modified the previous technique ever so slightly by incorporating a seam finding algorithm. In short, it found the best way to blend the overlapping patches to ensure that edges were nearly if not completely invisible.

Texture Transfer

Concept

We can augment the texture synthesis approach above to get a texture transfer algorithm. That is re-rendering an image with the texture samples of a different image. Each sample patch that we add to our synthesized image must now respect two different constraints: (a) it should have some agreement with the already synthesized parts (this is the constraint we used in texture synthesis), and (b) it should have some correspondance with the image we want re-render. We will use a parameter α to determine the tradeoff between these two constraints. To come up with a term for part (b) we need some measurement of how much a patch agrees with the underlying image. We can do this by calculating the SSD of a patch and the image on some corresponding quantity. One such quantity could be image intensity or the blurred image intensity.
The paper suggest to run multiple iterations of this while decreasing the tile size and adjusting α each time to get the best results. If we run multiple iterations we will need to incorporate the agreement of a patch with the already synthesized image and not just with the overlap region. So the error term will end up being something like this

error = (α) * (overlap_error + previous_synthezised_error) + (1 - α) * correspondence_error
Note that previous_synthezised_error will be 0 for the first iteration.

Inplementation

In this part, we implement texture transfer that is based on the idea of texture synthesis algorithm. Different from the texture synthesis algorithm, the optimal patch we sampled from the source texture image should respect the two following constraints at the same time:

  • the sampled patch has small SSD match error with previously selected patches on the overlap region.
  • the sampled patch has small correspondence error with the target image at the desired position.
In order to accommodate this error term, the total error in the texture synthesis algorithm can be modified as a weighted sum between the overlap error and the correspondence error:
total_error = α * overlap_error + (1 - α) * correspondence_error
('overlap_error' is the SSD distance between the optimal patch and previous synthesized patch on the overlap region, and the 'correspondence_error' is the SSD distance between the optimal patch and the patch from the target image at the desired position.) The α balances the texture synthesis and the fidelity to the target image correspondence map.

Successful results

Here are some results that we are quite satisfied. On the left is the texture image to be transfered, in the middle is the target image, and on the right is our result image.

Texture Image Target Image Synthesized Image

Failed results

Here is a result that not that good. It's a texture image with no repeating features and large variation. When we apply the texture to the target image, it creates a weired image with obvious seam and confusing texture.

Texture Image Target Image Synthesized Image

Analysis

From the results we can see that the algorithm works well for most of the examples, especially for those texture with low variations. The method requires that both the source texture image and the target image have a good distribution of intensity. Thus, we can sample patch with any level intensity from the source texture image, otherwise there is not enough variation and a lot of textures will be repeated in the resulting image.

Conclusions

Overall, we were quite pleased with the final results. For the texture synthesis part, we can see that for the non-repeative source image, the algorthms works well on reducing the seam, but still cannot make the result "natural" since the texture itself have a strong feature which is unnatural to be repeated. e.g. the leaf texture. And when the texture is highly repeating itself, the algorithm works well that you can hardly see the flaw.
The texture transfer is a little more tricky to get right which you can see from the images above, in cases like the bricks and the bread, where there is little colour variance, it is hard to map that onto another image that has much more color content. Also for the initial texture quilting, it helps to have some repeating features to the image, this makes sense and would be the case for textures. But if you put a picture of large variance to be quilted, for example the picture of the rose and a gun, which we've shown above, you might not get very good results.

Bell & Whistles(Extra Points)

1. Using filtering operations to speed things up

At first, we use the simplest method to calculte the ssd ( ssd = imgA.^2 + imgB. ^2 + (imgA.*imgB)*(-2)), which turns out to be very slow and takes lots of time to compute the best ssd results.

Then we use filtering operations to speed up the process. In the formula mentioned above, we can see that imgA is a fixed image, and imgB is changing each time. The (imgA.*imgB)*(-2) term takes most time to calculate. So we can use convolution to solve that. That is to use 'filter2' method (it is the same to use 'conv2') in the imgA.^2 and (imgA.*imgB)*(-2) terms. After using the filtering operations, we can finally compute images in a short time.

2. Varying the tile size can potentially help to get better results

It is interesting to compare the results with different patch size and overlap size and to see how the different sizes affect the performance. To do this, we first set the patch size to be 30 with overlap size 2 in the first row, 5 in the second row and 10 in the third row, respectively. The results are shown in the following images. When the patch size is the same, the larger overlap size corresponds to the better results, which is obvious in the first row agianst the third row of minimum cut method. However, the smaller patch size and large overlap size will take more time to generate the result.

Patch Size 30_Overlap 3 Patch Size 30_Overlap 5 Patch Size 30_Overlap 10
Patch Size 60_Overlap 5 Patch Size 60_Overlap 10 Patch Size 60_Overlap 20
Patch Size 90_Overlap 7 Patch Size 90_Overlap 75 Patch Size 90_Overlap 30

Patch Size 30_Overlap 3 Patch Size 30_Overlap 5 Patch Size 30_Overlap 10
Patch Size 60_Overlap 5 Patch Size 60_Overlap 10 Patch Size 60_Overlap 20
Patch Size 90_Overlap 7 Patch Size 90_Overlap 15 Patch Size 90_Overlap 30
Patch Size 30_Overlap 3 Patch Size 30_Overlap 5 Patch Size 30_Overlap 10
Patch Size 60_Overlap 5 Patch Size 60_Overlap 10 Patch Size 60_Overlap 20
Patch Size 90_Overlap 7 Patch Size 90_Overlap 15 Patch Size 90_Overlap 30
Patch Size 30_Overlap 3 Patch Size 30_Overlap 5 Patch Size 30_Overlap 10
Patch Size 60_Overlap 5 Patch Size 60_Overlap 10 Patch Size 60_Overlap 20
Patch Size 90_Overlap 7 Patch Size 90_Overlap 15 Patch Size 90_Overlap 30
Patch Size 180_Overlap 15 Patch Size 180_Overlap 30 Patch Size 180_Overlap 60

Analysis

As seen above, this technique works for a variety of images, but there are cases not shown above which can cause it trouble. Also, the values used to create the patch (i.e. overlap size, patch size, tolerance for SSD relative to minimum, etc.) factor into the quality of the synthesized texture. Having too small a patch size doesn't recreate the texture as desired and tends to make a new texture. Having too big a patch size with not a large enough overlap can cause the texture to have glaring edges. Also, too big a patch size compared to the orignal source size can make the output look reptitive. In all, different texture image should choose different parameter according to their unique patterns. And how to choose these parameters automatically is the next step to take. Because choosing suitable parameters can cost so much time.

3. Iterative Texture Transfer

Here we tested the iterative texture transfer scheme mentioned in the paper, in order to produce a natural and pleasing results. We iterate over the generated image several times, decreasing the patch size with each iteration. During each iteration, the optimal patch not only has the best SSD error with the neighbour patches on the overlap region, but also has the lowest SSD error with whatever was synthesized at the current patch from last iteration. Therefore, the total error becomes:

total_error = α * (overlap_error + previous_synthesized_error) + (1 - α) * correspondence_error
where the 'previous_synthesized_error' is the SSD error between current patch and the patch from last iteration at same position. In order to achieve a better performance, we should iterate 3 to 5 times and ajust the α according to the formula: α = 0.8 * (current_iteration - 1) / (total_iteration_number - 1) + 0.1

Here are the results:

Results

Source target Iteration 1 Iteration 3 Iteration 5

Analysis

The first row images we use patch size 90 x 90 and overlap size 15 x 15, then seperately iterate 1, 3, 5 times to get the results above.

The second row images we use patch size 50 x 50 and overlap size 8 x 8, then seperately iterate 1, 3, 5 times to get the results above.

The first column images above look great, but we can clearly notice those artifacts and it's not good enough. This is why we implement an iterative technique. This technique changes the alpha and uses the previous iterations image in the SSD_overlap error. Instead of just account for error of the overlap, it also tries to find an image that is similar to the image from the previous iteration. It is crucial that the details in the source image are small enough that it can be replicated in the target image. If the target image is not large enough compared to the size of the detail in the source image, either the target image won't appear in the final result or the texture will not look similar to that of the source image.

You can see how the image becomes clearer through iterations and the texture becomes more natural. This is a result of the alpha changing with iteration and decreasing linearly with each iteration from .9 to .1.

Thoughts

Difficuities: The dynamic programing is the most chanllenging one. After we finished the main code, we noticed the following could be done to improve:

  • Optimize the code and shorten the running time.
  • Figuring out the regular pattern for picking a better patch size and overlap size based on pictures with certain features.
We don't have enough time to make all of these results perfect, but we had several good thoughts to be implemented in future.

Reference

  • [1] Alexei A. Efros and William T. Freeman, Image Quilting for Texture Synthesis and Transfer, SIGGRAPH 2001.