Image Analogies

Jingwan Lu jingwanl@princeton.edu

Click on the image to see the original size.

The synthesis results demonstrated in the writeup is saved in subfolders in /html/.

1. Basic Algorithm

This part is implemented exactly according to the paper. The window size used here is 5x5. The window shape is a L-shaped neighbourhood containing the already synthesized pixels in the single level. For each pixel, the program does a brute force search for the best approximate feature vector match. The feature used here is the luminance value of the pixel.

The input pair : bluring effect

The given image and the synthesized output. The computation time : 616s

The input pair : emboss effect

The given image and the synthesized output. The computation time : 557s

2. Coherence search

Coherence search is added to the basic algorithm. The effect is particularly apparent for texture synthesis especially when the sample texture contain some human familiar structure. Increasing the kappa parameter means more likely to take the coherence search result instead of the approximate search. The synthesis result preserve coherence in the local neighbourhood. In the flower example, as we increase kappa, flower structure starts to show up. But when the kappa parameter is too large, visible seams appear between patches. Visualization of patches (indices where each pixel originate from the source) along with the synthesis results are shown. As kappa increases, the patch size increases and the resulting texture more and more resembles the examplar.

Texture Synthesis : brute force, single level, 5x5. The following sythesis result all takes around 40s.

Input texture. No coherence search Patch visualization

kappa = 2 kappa = 4

kappa = 8 kappa = 20

3. Multiresolution synthesis

The program starts synthesis from the coarsest level. The finner level synthesis depends on its immediate lower level result. The feature vector contains both the local L-shapped neighbourhood in the current level and the corresponding full neighbourhood in the lower level. Using multi-level gives better synthesis result when using the same window size. The is because, when synthesizing the coarse levels, the window size is large enough to suggest image structure. Suppose the window size for the current level is w x w, then the window size in the lower level is (w+1)/2.

Texture Synthesis : brute force, 5x5.

The following compares the single level with multi-level(4) results. The intermediate results are shown here. No coherence.

single level. 38s level4. 63s level3 level2 level1

With all other parameters the same, but kappa = 2

single level. 40s level4. 63s level3 level2 level1

4. Approximate nearest neighbor search acceleration

With ANN, the performance improves dramatically while maintaining similar synthesis result

4 levels, 5x5, kappa = 3
input	Without ANN. 70s	with ANN. 31s

5. Constrained texture synthesis

Different from texture synthesis, the synthesis starts from the hole boundary inward or from the extrapolation boundary outward. The program uses a queue data structure to keep a list of boundary points to be synthesized. And the boundary points are synthesized in transversal order. New boundary pixels are inserted into the queue by breath first search. Instead of using fixed-size L-shapped neighbourhood, variable-size neighbourhood is used here. All the already synthesized pixels contribute to the neighbourhood. Therefore, ANN cannot be used here. The method works well with stochastic texture, but with more structured texture, seams are visible.