Overview
For some applications in image processing, it is desirable to have a certain texture fill an arbitrary amount of space. Given a photo of the desired texture, we can accomplish this naïvely by tiling the image (or portions of the image) such that they fill the whole space; this, has the major drawback that the seams between edges of the texture sample will be easily visible, and hence not true to the original pattern. However, if we can select portions of the original image to tile according to how well they match surrounding tiles in the algorithm's output, we'll get a lot closer to a seamless image, and if we can tailor the overlap between these intelligently selected tiles such that it cuts through the path of least difference between a given tile and it's neighbors, our output will look even better. If we add the further restraint that each tile of an output texture image must bear some similarity to a similarly positioned tile of a second non-texture input image, we can reproduce the texture with some overlying structure defined by the second input image.
Algorithm
Texture Synthesis
n*n rectangular patches (or tiles) to be filled by near-seamless texture. For each desired tile:
- Iterate through all possible tiles for this position -- every
(n+b)*(n+b)square which could be taken from the original pattern image, and overlaps by some pre-set amountbwith the (already generated) tiles to the left and above of this tile. (The algorithm can be sped up, though the results degraded, by only selecting from a limited number of randomly chosen segments of the pattern image.) - Among these, choose the patch with the least sum of squared differences (SSD) between pixel values of the pixels from the candidate patch and the existing pattern pixels at the overlap.
- We can either stop here and accept some slight, rectangular borders around each segment, or we can find (as in this project) the minimum cost seam through the remaining differences in the border area and use this as the boundary between the left and above patches and the one in question. This can yield somewhat smoother results.
Texture Transfer
This is similar to the algorithm above, but we incorporate a slightly altered cost weighting for each candidate patch. Instead of just choosing the best overlap with previously chosen tiles, also added into the comparison is the degree of similarity (image distance by SSD) between a candidate tile and a corresponding segment of a second input image. By choosing tiles that match at least somewhat to the colors present in, for example, an image of Abraham Lincoln, we can procure a relatively seamless image of toast (or whatever other texture) that also bears the impression of Lincoln's face.
As suggested in the paper, this process can also be applied in iteration, with smaller and smaller patch sizes. During this process, in addition to the error of correspondence between a candidate patch and the source image, the error of previously calculated pattern sections (upon which this next iteration will overlay) must also be incorporated; given a weighting α, the formula
error = α * (overlap_error + previous_error) + (1 - α) * correspondence_errorResults
Following are the results of my program as applied to the test images, as well as some additional images of my choosing.
Texture Synthesis
Note that the SSD only and minimum error boundary image start with a different tile in the top left: for the first tile (which can essentially be anything), I select a random part of the source texture, to encourage variation in results. Also note that, alas, the images are not perfect; often there exists no perfect patch to line up precisely with the last, and finding the minimum error boundary can only do so much to split the difference. This could be easily remedied by doing something similar to Poisson blending between the patches, or even by subtly blurring the rift between them, but unfortunately I don't have enough time this week to implement this extension. In another interesting error case, note the repetition in the toast and map tilings; in these cases, there must be one patch which matches very will with itself and many other tiles, so it ends up dominating the output image.
Texture Transfer
These images faithfully represent the lower frequency signal in the source images, though some of the lower frequency signals in the textures are removed (for example, the billowing of the flame, and the larger-scale clumping of the rice). Perhaps in some cases I was overambitious, trying to get too much definition in my result images by running the algorithm with too many iterations. In my opinion, the toast images look the best; toast is a texture which is easily represented in a small sample, but varied on a large enough scale to provide the variation needed for different colors in an output image.
