Image Analogies

Jingwan Lu

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 searchPatch 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. 38slevel4. 63slevel3level2level1
With all other parameters the same, but kappa = 2
single level. 40slevel4. 63slevel3level2level1


4. Approximate nearest neighbor search acceleration

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

4 levels, 5x5, kappa = 3
inputWithout ANN. 70swith 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.

3 levels, 9x9, kappa = 3
inputresult. 11s
inputresult. 603s
inputresult. 803s


6. Applications and Results

1) Image Filter

source pairwatercolor painting
input5 levels, kappa=1, 5x5. 419s
input4 levels, kappa=3, 5x5. 273s

2) Texture Synthesis

In order to obtain some randomness, before synthesis, the coarsest level is initialized with pixels randomly picked from Ap.

input4 levels, kappa=4, 5x5. 32s
input5 levels, kappa=4, 9x9. 8210s
input4 levels, kappa=4, 5x5. 46s

3) Texture By Number

5 levels, kappa=2, 9x9. 1816s
4 levels, kappa=3, 9x9. 5476s

4) Image Inpainting

See above for the three examples.