Basic Algorithm

In this section, image analogy is completed in one level, without coherence, and without ANN acceleration. The result is shown in Figure 1.

Figure 1a A Figure 1b Ap

Figure 1c B Figure 1d Bp

Figure 1e Matching Result

Figure 1e presents the matching image. For each pixel in ‘Bp’, we match a pixel from ‘Ap’ to it. The red channel is the ‘x’ position of the corresponding pixel from ‘Ap’, and the green channel is the ‘y’ position. Because of the structure of ‘.bmp’ file, the pixel with the position of (0, 0) is at the bottom left of the image.

The neighborhood size in the example is 5 by 5. The running time (resolution: 320*240pixels) is 2200 seconds.

Coherence Search

In this section, coherence search is added, and kappa is used to define the preference between coherence search and closest-distance search.

Figure 2a presents the result after taking coherence into consideration (with kappa = 5.0), and Figure 2b is the matching image.

Figure 2a Coherence Result (kappa = 5.0) Figure 2b Matching Result

The size of regions in Figure 2b is apparently larger than that in Figure 1e, which is direct result of coherence. Figure 2a presents a different style of blur compared to Figure 1d, which is something like oil painting.

Taking coherence into consideration causes a bit more running time. In the example above, the running time is 2230s, also with the neighborhood of 5 by 5.

Figure 3 present the result with kappa = 1.0, note that the size of regions in the matching image is not as large as that in Figure 2b, giving a better result of blur.

Figure 3a Coherence Result (kappa = 1.0) Figure 3b Matching Result

For the example of texture synthesis (Figure 4), the choice of kappa influences greatly on the result.

synth1.Ap.bmp

Figure 5a Exemplar Figure 5b kappa = 0.0 Figure 5c kappa = 6.0

Multi-resolution Synthesis

To implement multi-resolution synthesis, we should generate gaussian pyramids for image ‘A’, image ‘Ap’, image ’B’, and do synthesis on each level, as shown in Figure 5.

Figure 5 Multi-resolution Synthesis

The running time increases not only because we have to generate 4 levels instead of 1, but also because we have to calculate with a longer feature vector at each pixel (since the neighboring pixels at coarser level is also included). The running time of the above example is 28021 seconds.

Although multi-resolution does not show great advantage over single-level synthesis in blurring, it outperforms single-level synthesis great in texture synthesis. Figure 6a shows the result of synthesis on flower in single-level, and Figure 6b shows the result in multi-level (4 levels). With the same parameters (kappa = 6.0, neighborhood size = 9 by 9), it is obvious that multi-level is helpful to preserve the unity of flowers in this case: from the result of single level implementation (Figure 6a), we can detect a lot of petal, but can hardly tell a complete flower.

Figure 6a Single-level Figure 6b Multi-level

ANN search acceleration

The result of ANN search acceleration is shown in Figure 7.

466_bp2 466_bp3 466_bp4

Figure 7 Synthesis with ANN

We achieve the same result with running time only 21 seconds (the error tolerance in ANN search is set as 0.0).

Constrained Texture Synthesis

We can no longer use L-shape to define the feature in ‘Bp’, since it is not a scanning order, and the neighborhood of a pixel which has been completed is totally random. Because the size of feature is not fixed, ANN cannot work in constrained texture synthesis, and we have to use brute force to find the corresponding pixel.

There is also another question that which pixel should be firstly synthesis? There are two possible methods. First one is bread-first-searching, that is to expand the completed pixels, and add the uncompleted pixels which are near to the completed pixels into an FIFO queue. In this sense, the pixel which is closer to the existing pixels are synthesized first, and pixels that are farther from the existing pixels synthesized later.

Another choice is to maintain a priority queue of pixels, and the value of a pixel is the number of pixels in its neighborhood that have been completed. The ‘neighborhood’ here is the one used in calculating the feature for each pixel.

Figure 8 presents the result of these two different methods. Two other sets of results will be shown in ‘Application: Image Inpainting’.