FFT Based Procedure for Texture Synthesis
Texture synthesis has been a widely studied area in compute vision and computer graphics. It has been applied to broad fields such as image modeling, graphics and hole filling. The primary approach for texture synthesis has been to develop a statistical model which emulates the generative process of the texture they are trying to mimic. For example, Zhu et al  use a Markov random field (MRF) to model texture with some success. Heeger and Bergen  resample a random noise image to coerce it into a texture sample with similar histograms. It works well for highly stochastic textures, but fails for more structures textures.
Most recently, Efros and Leung  propose a very simple algorithm based on MRF without estimate of specific distribution. Their paper presents many impressive 2D textures and demonstrates that simple method do work well. However, as they mentioned in their paper, the algorithm is quite slow.
In this paper, we propose an efficient algorithm based on their algorithm. We will use fast Fourier transform technique (FFT) to search matching points. We provide a theoretical analysis by comparing the computation needed in both algorithms. Our results show that using FFT based algorithm will perform much faster than their algorithm, especially when the matching window has a large size, which is needed for most texture synthesis.
Given a sample texture image, a new image is synthesized one pixel at a time. This is one of two main reasons that make this algorithm to be slow. The other reason is that: to synthesize one pixel, we have to calculate all possible SSDs between pixels around the new pixel (within a matching window) and corresponding pixels around each pixel (local window with same window size as matching window) in sample image. Assuming that the sample image A has size of M ´ N and the matching window B has size of m ´ n. To synthesis a texture image, we will need about M ´ N ´ (M ´ N ´ 4 ´ m ´ n + m ´ n) computations. For example, for a 100 x 100 sample image and 20 ´ 20 matching window, we need about 1.6´1011 computations. This is a very large number.
To speed up, we have to reduce the computation time. In section 3, we will describe a new strategy to compute SSD efficiently so as to reduce the number of operations.
3. FFT based algorithm
The way to compute SSDs can be viewed as convolutions. Thus, instead of computing SSD pixel by pixel in sample image, we first zero pad image A and matching window B to the same size of (M + m –1) ´ (N + n –1). Then we perform FFT of the zero paded A and B and the inverse FFT of multiplication of their Fourier transform . To synthesis a texture image, we will need total M ´ N ´ (2 ´ 3 ´ (M + m –1) ´ (N + n –1) ´ (log2(M + m –1) + log2(N + n –1) ) + m ´ n) computations, which, as we will show, is much smaller than the number needed in Efros and Leung’s algorithm for larger window size.
To see the computation reduction, we plot the number of computations vs. window size m (here for simplicity, we assume m = n, M = N = 100). As seen from figure 1, as the window size increases, the number of computations needed for Efros’ algorithm increases dramatically compared with my algorithm. To see this clear, I also plot the log10(number of computation) vs. m. It is clear that for m between 10 and 30, my algorithm is about 10 times faster than Efros’, and for m large than 50, my algorithm will run about 100 times faster than Efros’ algorithm. Therefore, we cam reduce the computation time dramatically. Only for m equal to 3 and 4, Efros’ algorithm performs faster than my algorithm. However, as I will demonstrate, it is impractical to use so small window, which may not find the undergoing stochastic property (This is also discussed in Efros’s paper).
To have an idea about how large the matching window should be, we test our algorithm for synthesizing brick texture. Figure 3(a) is the sample texture, and 3(b) – (d) are synthesized textures with matching window size of 5 ´ 5, 15 ´ 15, and 31 ´ 51, respectively. Obviously, in this case, as window size is larger and larger, the results are better and better.
(a) (b) (c) (d)
figure 3 (a) sample texture, (b), (c), and (d) synthesized textures with 5 x 5, 15 x 15, and 31 x 51 window sizes, respectively.
4. SELECTED Results and Discussion
(a) (b) (c)
(a) (b) (c)
(a) (b) (c)
figure 7 (a) texture with hole (b) filled hole
figure 8 (a) texture with hole (b) filled hole
figure 9 (a) texture with hole (b) filled hole
5. FUTURE WORK AND IMPROVEMENTS
In this paper, we only reduce the computation time for searching matching pixels. To further reduce the computation time, we can try to synthesis a patch instead of one pixel each time.
Another issue is the window size. It is very important to select a proper window size. An automatic selection of window size will be desired. We may consider a moving average (MA) model together with MRF to model the intensity of each pixel. The size of MA window is the same as the matching window. When we increase the window size, the error (difference between real intensity and intensity estimated from MA model) will decrease. When the difference is small enough, the corresponding window size may be used as matching window size.
 S. C. Zhu, Y. Wu, and D. Mumford, "Filters, random fields and maximum entropy" International Journal of Computer Vision, vol. 27(2), pp.1-20, 1998.
 D. J. Heeger and J. R. Bergen, “Pyramid based texture analysis/synthesis” in Computer Graphics, pp. 229-238, ACM SIGGRAPH, 1995.
 A. A. Efros and T. K. Leung, “Texture synthesis by non-parametric sampling” IEEE International Conference on Computer Vision (ICCV’99), 1999
 A. K. Jain, Fundamentals of digital image processing, Prentice-Hall, Inc., 1989.