Image Quilting for Texture Synthesis and Transfer
by Xiaofeng Tao (taox)
Introduction
The objective of this image quilting algorithm is to select patches from an input texture and then mosaic the texture patches in an overlapping fashion. The resulting texture synthesis can be used to fill holes in an image or expand an image. Furthermore, this same method may be extended to texture transfer by rerendering a target image with a given texture. The technique described below is an implementation of the algorithm presented in (Efros and Freeman). In addition, poisson blending is also applied to remove seam artifacts from the image.
Texture Synthesis Algorithm Overview
The following steps describe texture synthesis, which will generate new image content based on an input texture's structure and intensity. The overlapping tiles are calculated one by one iteratively until the full texture mosaic is completed.- Select the texture patch for a single tile
First, random tile sized samples are taken from the input texture. The number of random samples taken is a fixed percentage (10%) of the total possible patch coordinates in the input texture. Each random sample is compared to the overlapping regions of any neighboring tiles in the existing texture mosaic (usually comparing the top and left boundaries). The comparison metric used is the sum of squared differences of the image intensity. The sum of squared differences are sorted for all random samples in order from best (lowest value) to worst (highest value). Finally, a sample is randomly selected from the top 10% of the sorted samples to be the texture patch for that tile. This stochastic selection is better than just picking the best sample since it reduces repetition and looks more natural.
- Find minimum seams along top and left tile boundaries
The following minimum seam calculation is performed on the top and left overlapping regions to find the ideal top and left tile boundaries for the new texture patch. The transpose of the top overlapping region is taken so that the same algorithm code can be used for both regions.
First, an energy map must be constructed by calculating the sum of squared differences at each pixel.
Next, an accumulated cost matrix must be constructed by starting at the top edge and iterating through the rows of the energy map. The value of a pixel in the accumuluated cost matrix is equal to its corresponding pixel value in the energy map added to the minimum of its three top neighbors (top-left, top-center, and top-right) from the accumulated cost matrix. The value of the very top row (which obviously has no rows above it) of the accumulated cost matrix is equal to the energy map. Boundary conditions in this step are also taken into consideration. If a neighboring pixel is not available due to the left or right edge, it is simply not used in the minimum of top neighbors calculation.
The minimum seam is then calculated by backtracing from the bottom to the top edge. First, the minimum value pixel in the bottom row of the accumulated cost matrix is located. This is the bottom pixel of the minimum seam. The seam is then traced back up to the top row of the accumulated cost matrix by following. The minimum seam coordinates are recorded.
- Set overlap regions and perform poisson blending around minimum seams
The minimum seam coordinates from Step 2 are then used to determine the boundary around which to assign values to the overlapping regions between tiles. Finally, poisson blending is performed around these minimum seam boundaries to reduce artifacts. This step is further described in the poisson blending section.
- Repeat Steps 1 - 3 until all texture patch tiles are computed
This process is repeated until all tiles in the texture mosaic have been calculated.
Poisson Blending
This enhancement is designed to smooth the boundary between texture patches and reduce artifacts. This is done by creating a small masked regions around the minimum seam boundaries to blend. The width of these masked regions is parameterized to be at most 5 pixels wide. The masked regions are always created so that the existing texture patches are used as the source images and the new texture patch with modified overlapping regions is used as the target image. The masked region is then filled by examining the source and target gradients with poisson blending. This technique is used for both texture synthesis and texture transfer.
The benefits of poisson blending can be seen below. The seams are much more noticable on the left without poisson blending than on the right.
No Poisson Blending (left) vs Poisson Blending (right)
|
Texture Synthesis Results
The following results for texture synthesis first show the input texture and a completely random sampling of the input texture. Next, the results show how using the sum of squared distances metric to select from random samples is better than a random sampling. Finally, the images with minimum seams and poisson blending show the best results.
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Input texture (left), and Random (right)
|
SSD only (left), and SSD with min seams + poisson blending (right)
|
Texture Transfer
The texture synthesis algorithm described earlier can be easily extended to also transfer a texture onto a target image. This is done by changing the error metric from minimum sum of square differences (SSD) to the following equation, where alpha is a constant between 0 and 1, SSD_overlap_error is the original SSD metric for overlapping regions, previous_iteration_error is the SSD between the new texture patch and the previous iteration's generated texture, and correspondence_error is the SSD between the new texture patch and the target image being rendered.
error = (alpha) * (SSD_overlap_error + previous_iteration_error) + (1 - alpha) * correspondence_error
This new metric is then used for both selecting the best texture patches and the minimum seams calculation. The second modification is that the algorithm is performed iteratively over several different tile scales (from large to small). This is done so that the larger features are rendered first and then the smaller details are gradually refined in the output texture transfer image.
Texture Transfer Results
Texture transfer results are shown below. I suspect that optimizing the tilesize for each particular case, using a larger input texture, or using a metric other than image intensity may be required to improve these results.
Input image (left), and Texture (right)
|
Result
|
Input image (left), and Texture (right)
|
Result
|
Input image (left), and Texture (right)
|
Result
|
Input image (left), and Texture (right)
|
Result
|
Texture Transfer Failure Case
This is clearly a failure case, because most of the ship's details besides part of the superstructure and the wake have been eliminated. I was hoping that the white ice texture would map onto the ship while the black ice texture would map onto the sea. The problem was that parts of the ship, such as the heliport and bow hull, are closer in intensity to the color of the water than the rest of the ship. The image actually got worse as more iterations were processed because the water areas took over the ship. Also, there are parts of the ship are too detailed for the tile sizes that were used in the texture transfer. In conclusion, a better metric than image intensity and a more optimal tile size is probably needed to get a better result.
Input image (left), and Texture (right)
|
Result
|