This algorithm implements an image-based method for texture synthesis and transfer. In texture synthesis, samples from a texture swatch are quilted together to form a similar texture with different dimensions. In texture transfer, samples from a texture swatch are mapped onto a black-and-white image (intensity image) and quilted together to form a textured version of the black-and-white image.
Algorithm
In both algorithms, square patches are densely sampled from the texture swatch and assembled in scanline order to form the final image. Each patch overlaps previous patches by a predefined margin, which allows for blending along the patch seams later. To select the next texture patch to quilt into the image, each candidate patch is scored on the SSD between the candidate patch overlap region and the overlap regions to the left and above the patch in the quilted image. The texture transfer algorithm imposes additional constraints, which will be discussed below. The outline of the texture synthesis algorithm is given now:
- Texture Synthesis
- Compute the SSD between each candidate patch overlap and the corresponding overlap regions in the assembled image.
- Select the n best scoring texture patches and further remove any candidates that are not within a certain threshold of the minimum score, to avoid including poor matches.
- From these final candidates, randomly select a patch to use. This random selection helps to avoid repeated texture patches in the final image.
- Finally, find the minimum pixel difference seams along the overlapping borders of the texture patch and the existing image. Copy the texture patch contents into the quilted image from these seams outward, to minimize the visibility of the seams where the new patch was added.
- Repeat until the image is constructed to the desired dimensions.
In the texture transfer algorithm, candidate patches were judged not only by how well they matched the existing image pixels, but also by how well they matched the given intensity image. Therefore, additional constraints were imposed in selecting the texture patch candidates. Also, since after the first iteration, the algorithm operates on a full quilted image, pixel differences are calculated not only in the overlap regions, but over the entire texture patch area. The relative weighting of pixel differences and intensity differences was given by a value alpha. At first, the alpha value strongly favored the intensity differences, creating a base layer of tones. With each iteration, the texture patch size decreased and the alpha value shifted more in favor of pixel differences, emphasizing patches that quilted together seamlessly. The outline of the texture transfer algorithm:
- Texture Transfer
- Compute the SSD between each candidate patch and the corresponding region in the assembled image.
- Blur the intensity image and the texture image, then compute the SSD between each candidate patch and the corresponding region in the intensity image.
- Combine alpha times the pixel-difference SSD and one minus alpha times the intensity-difference SSD to calculate the final patch scores.
- Select the n best scoring texture patches and further remove any candidates that are not within a certain threshold of the minimum score, to avoid including poor matches.
- From these final candidates, randomly select a patch to use.
- Finally, find the minimum pixel difference seams along the overlapping borders of the texture patch and the existing image. Copy the texture patch contents into the quilted image from these seams outward, to minimize the visibility of the seams where the new patch was added.
- Repeat until the image is constructed to the desired dimensions and then repeat the entire process until the desired number of iterations are completed.
Extra Credit
To enable a dense search of texture patches, it was necessary to optimize the SSD calculations. This was achieved by implementing the calculations as a combination of filtering operations. Observing that A2 - B2 = A2 - 2AB + B2, it is possible to calculate each individual term of the right side of the equation as a filtering operation, and moreover, it is possible to calculate the sum of each term in the patch area as part of the same filtering step. The calculation of each term only takes into account the pixels that are to be compared, by using a mask that highlights the pixels under consideration.
Results
Texture Synthesis Results
The results of the texture synthesis algorithm are displayed below. The original texture swatch is shown to the left. To the right, a texture synthesized from random patches is shown first, followed by the results of the pixel-difference SSD scoring calculation, and finally the fully synthesized texture with seam carving. The results of the texture transfer algorithm are presented after.
Limitations: Due to the enforcement of random candidate selection, sometimes the selected patch is misaligned with the rest of the texture, and its misalignment cascades to the subsequent patch alignments. Additionally, the algorithm seems to be disrupted by coarse textures, so the patch size and the texture coarseness must complement each other.
Texture Transfer Results
The results of the texture transfer algorithm are shown below. In the top left is the intensity image, and below that is the same image mapped with toast texture. The toast texture is shown for each intensity image, as it performed the most consistently for all images. In the top right is a separate texture swatch, and below that, the intensity image mapped with the different texture.
Limitations: The algorithm requires that the input texture has a good grayscale distribution, otherwise the results will be poor, and many textures will be repeated in the final image. These effects are especially prominent in areas of consistent intensity. To combat these problems, I tried to normalize the intensity values of the intensity images and the texture images.
