Description of Algorithms

Single Resolution Synthesis Algorithm (Wei, Levoy)

This algorithm performs a linear search through the input image for each pixel of the output image. It locates the input image pixel with a neighborhood that is "closest" (in L2 norm) with the neighborhood of the current output pixel, and uses its color value for the current output pixel.

The neighborhood for a pixel is "causal", which means that it covers only pixels that have already been synthesized, not the random noise pixels below the current pixel. If the neighborhood extends behind the right or bottom edge of the image, a pixel (x, y) on the neighborhood uses the color value (x % image.width, y % image.height). This has the effect of making the resulting image tileable without noticing the borders. If the neighborhood extends before the left or top edge, a random noise value is used for this pixel.

Multi Resolution Synthesis Algorithm (Wei, Levoy)

This algorithm is similar to the single resolution algorithm, but instead of using one image, it generates Gaussian image pyramids for both the input and output images. Both pyramids should have the same number of levels. The algorithm then synthesizes the levels of the output image, from smallest to largest. The neighborhood in this case also includes the pixels around the parent pixel in the previous level.

K-D Tree Acceleration for the Single/Multi algorithms

Since both these algorithms make extensive use of nearest-neighbor searches, a K-D tree data structure may be used to speed up the search process. The neighborhoods of all the input image pixels are first added to the K-D tree. Then, everytime we have to search for a best matching neighborhood to an output pixel neighborhood, we just have to search the tree, which is a very fast operation. A key problem with using K-D trees to speed up these synthesis algorithms is how to represent a neighborhood, which is a list of pixels, as a K-dimensional point. Given a neighborhood ( (R1, G1, B1) ... (Rn, Gn, Bn) ), there are several possibilites that I tried. One such method was to have a 3n-dimensional point ( R1, G1, B1, R2, G2, B2, ... , Rn, Gn, Bn ). None of my attempts produced satisfactory results, however.

Image Quilting Algorithm (Efros, Freeman)

This algorithm is fundamentally different from Wei and Levoy, since it does not operate at the pixel level, but considers square blocks of pixels. My implementation allows the size of the block to be user-defined. Here are the major steps:

1) Go through the output image in steps of one block, minus an overlap amount.

2) For every location, search the input image for a list (of a given length) of blocks. Each of these potential blocks, when placed down on the output image such that it overlaps with the block above or to the left, has an overlap area within some error tolerance. One of these blocks is then picked at random.

3) We will now place this block on the output image with some overlap to the left (vertical overlap) and above (horizontal overlap). In the overlap regions, we compute a path of minimum error along which to attach the new block.