CS129 / Project 4 / Texture synthesis and transfer with Image Quilting
Toasty Lincoln
In this project we do two things: texture synthesis and texture transfer, both via image quilting. Texture synthesis involves taking a texture of some size and using that texture, we synthesize a bigger version of the texture which maintains the original texture's look. To do this, we superimpose patches from the original texture onto a bigger canvas, so to speak, until we've filled the whole thing in. Using this same idea, texture transfer takes patches from an original texture but instead of just trying to paste in seamless patches, we are also trying to match up to a source image, so that some of the detail of the source image will be evident from looking at the new image. The theoretical basis and basic implementation details of these algorithms can be found in this paper by Efros and Freeman, but I will also explain details of my implementation below.
Algorithm: Synthesis
For the synthesis portion of the algorithm, we use three different methods: Random patches, Best SSD, and Best SSD with min seam. In the random patches approach, we go through each patch in the target image and grab a random one from the source texture to place there, regardless of what was already there in the target. This doesn't work very well. For the Best SSD approach, we superimpose patches onto the target image so that their left and top edges will overlap previously placed patches by a small amount. We take 1000 random patches from the source texture and look at the SSD between each potential patch and what already exists in the image. We pick the patch with the smallest SSD value by this metric. If there is no overlap we essentially choose a random patch, but this is only the case for the first patch we place in the target image. This works reasonably well, although the patches don't line up perfectly which introduces some visible edges. To try and combat this, we introduce a third algorithm, which is Best SSD with min seam. We take the same approach as Best SSD to find the best patch, but instead of just putting that patch in the image, we find the best minimum error seam on both the left and top sides between the target image and patch we're trying to put in the image. Once we have those seams, we put the patch in the image but cut it along those seams to attempt to make the image seamless. For finding the best seam, we use the same code and algorithm as last project, which was seam carving, but we only find one seam and don't carve it out this time.
Results: Synthesis
| Original | Random | Best SSD | Best SSD with min seam |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Discussion
It's pretty clear that the Best SSD and min cut algorithm is the winner here. It worked better than the alternatives on all of the images. I probably could have gotten better results if I had done an exhaustive search over all possible patches for each patch insertion, but that was a very slow process when I tried it, so I decided that random was fine. I also could have avoided the repetition in the toast image by taking a random patch that was past a certain threshold of error instead of taking the "best" patch every time. Overall I'd say this worked reasonably well. Interestingly the larget features, such as the big holes in the cheese are ignored with the patch size I took since a patch inside the hole would only match up to other patches inside the hole, which could explain the lack of detail on the Best SSD min cut cheese image
Algorithm: Transfer
For the transfer part of the algorithm, I used the same algorithm as in the paper. In this algorithm, you run through each patch in the image like in synthesis, but you also include some correspondence term between the patch you're selecting and a patch from some source image you're trying to transfer the texture onto. You do this iteratively with smaller and smaller patches and greater and greater emphasis on the overlap for a few iterations, which generally gives nice results. Basically I used the same SSD and min seam algorithm as in synthesis, but I also included a correspondence term between the patch I was taking and the equivilent patch from the source image. I also factored in the patch's error both between what it overlapped on the sides and what it overlapped in general, since the transfer process is iterative so after the first iteration you want to maintain the general intensity of the patch you are replacing.
Results: Transfer
| Original Texture | Original Image | Transfered Image |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Discussion
This algorithm seems to be working reasonably well, especially for the toast images. In the case of the medieval painting, the sharp lines and large color differences make the algorithm work very well, while Jerry Rice gets a little lost. It is worth noting that the toast image has a lot more variation in color than the rice image, which may also have contributed to the sharper image of the medieval painting. Yoda to grass worked alright, but it seems like the toast is uniquely oriented to looking good. This could also be because we know that toast can take on any level of brownness, as long as it's continuous with its immediate surroundings, while rice and grass are less well defined in that way.