Almost all of the real-world textures can be modeled as linear, non-Gaussian, stationary random fields. It turns out that most of these textures are in fact generated by passing a non-Gaussian noise through a non-causal linear filter. This motivates us towards using a 2-dimensional, non-causal, linear system to synthese the textures. For simplicity, we will use only AR models in our texture synthesis.

Texture synthesis using causal AR model

If the filter is causal, the synthesis can be done by directly filtering a non-Gaussian noise through the IIR filter. It is as easy as finding the textures samples using a recursive equation with some initial or boundary conditions. In fact in this case the image is the solution to a linear system of equations whose coefficients matrix is triangular.

Texture synthesis using non-causal AR model

If the filter is non-causal, then there is no recursive equation. In this case, we have to either calculate the truncated impulse response of the system and use the basic convolution equation for the linear system to find the texture, or solve the input-output system of linear equations. For the first method, we need to use a very long approximation of the true impulse response of the IIR filter to get an acceptable image. This makes the method very difficult to implement, and thus we will use the second method.

For the second method, the difference with the causal case is in the fact that the coefficients matrix is no longer a triangular one. Solving a system of linear equations still does not seem to be a difficult problem, but the challenge is that for an image of size M x M, we have a system of M² linear equations. For example, for a texture of size 128 x 128, the size of the system of linear equations is 16384, and the coefficient matrix has 268,435,456 elements. Direct solution to this system of linear equations is too complex and takes a lot of time. So we look for some low complexity methods for solving this system.

To find a low complexity method, we notice that the coefficients matrix of this system is a block circulant matrix. In [2] a low complexity method of solving linear systems of equations with block Toeplitz matrices is proposed, in which, using the FFT and an appropriate permutation, the block circulant matrix is converted to a block diagonal matrix. This way, the original system of M² linear equations is reduced to M independent systems of M linear equations, which is much easier to solve.

In order to be able to use this method, we approximate the original block Toeplitz matrix with a block circulant one, by just substituting the blocks from the lower triangle of the matrix with appropriate blocks from the upper triangle.

Using the method of [2], this system of linear equations reduces to the following block diagonal system:

This system of linear equations can now easily be solved in Matlab.

In this project, the above mentioned methods were applied for texture synthesis. As an example, the left hand side texture of the following figure was produced using a causal AR model, while the texture on the right was synthesized using a non-causal AR model.