EUROGRAPHICS 2005 / M. Alexa and J.

Marks Volume 24 (2005), Number 3

(Guest Editors)

Fractional Fourier Texture Masks:

Guiding Near-Regular Texture Synthesis

A. Nicoll and J. Meseth and G. Müller and R. Klein

Institut für Informatik II, Universität Bonn, Germany

Abstract
Recently, the special kind of near-regular texture has drawn significant attention from researchers in the field of
texture synthesis. Near-regular textures contain global regular structures that pose significant problems to the
popular sample-based approaches, and irregular stochastic structures that can not be reproduced by simple tiling.
Existing work tries to overcome this problem by user assisted modeling of the regular structures and then relies
on regular tiling. In this paper we use the concept of fractional Fourier analysis to perform a fully automatic
separation of the global regular structure from the irregular structure. The actual synthesis is performed by gen-
erating a fractional Fourier texture mask from the extracted global regular structure which is used to guide the
synthesis of irregular texture details. Our new method allows for automatic and efficient synthesis of a wide range
of near-regular textures preserving their regular structures and faithfully reproducing their stochastic elements.
Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional
Graphics and Realism – Color, shading, shadowing, and texture, I.4.7 [Image Processing and Computer Vison]:
Feature Measurement – Texture

1. Introduction to faithfully reproduce these textures due to restrictions of

neighborhood sizes and lack of adequate distance functions.
During the last years, the area of texture synthesis has
been devoted significant work from researchers in computer In this paper we introduce the concept of fractional
graphics and computer vision. The developed algorithms not Fourier texture masks (procedural textures for the regular
only achieve impressive synthesis results for various kinds of parts), which are derived by extracting the regular struc-
textures but also provide general methods applicable to other ture from a texture using fractional Fourier analysis and "en-
interesting fields like image restoration or geometry comple- larging" it to a desired size. These masks are used to guide
tion. Nevertheless, not all kinds of textures can currently be sample-based synthesis algorithms in faithful selection and
handled in a pleasing manner. Especially textures referred to placement of copied pixels or patches, effectively enforcing
as near-regular textures [LTL05] that contain global, regular global, regular structure and therefore leading to drastically
structures as well as stochastic deviations from regularity are improved synthesis quality for near-regular textures.
still very difficult if not impossible to synthesize faithfully.
Our new, robust method for synthesis of near-regular tex-
Examples of this type of texture are frequently found in the
tures is composed of three major steps:
real world: most textiles (e.g. used for clothing, furniture, or
car interiors) and construction elements (walls, floors, grid 1. separation of the dominant regular structure from irreg-
structures, corrugated sheet roofs) fall into this category, and ular texture detail using the fractional Fourier transform
even natural objects like water waves, feathers and fur. and an intensity filter,
2. synthesis of the regular structure based on the inverse
The specific difficulty of these textures originates from
fractional Fourier transform,
the strong mixture of regular patterns which govern global
3. addition of irregular texture detail by extended sample-
structure, and the subtle, yet characteristic deviation from
based texture synthesis algorithms.
this regularity. Since the regular patterns may be of arbi-
trary scale, existing sample-based synthesis algorithms fail In the following, we first review some related work in

c The Eurographics Association and Blackwell Publishing 2005. Published by Blackwell

Publishing, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main Street, Malden,
MA 02148, USA.
 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

Section 2. Afterwards, Section 3 provides background and and paste them in a regular manner such that the color
implementation details of our algorithms for separation and differences in the overlap region are minimized. A similar
synthesis of the regular texture structure. Section 4 then approach is followed by Liang et al. [LLX∗ 01] but they
shows how the resulting fractional Fourier texture masks can apply feathering to merge overlapping patches. Kwatra et
be used to guide existing sample-based texture algorithms to al. [KSE∗ 03] generalize and improve these approaches by
faithfully reproduce both local and global structure. After reducing the problem of combining the pixels to a minimal
presenting and discussing our results in Section 5 we con- cut problem and allowing for blocks of arbitrary sizes. Re-
clude and describe future directions of research in Section 6. gions of varying size are as well supported by the algorithm
of Nealen and Alexa [NA03]. Despite the fact that copying
large texture regions allows for preservation of large texture
2. Related work structures, the exact alignment of structures in the target tex-
The objective of texture synthesis is to generate images that ture often fails due to bad placement of patches.
reproduce a distribution of textural features which humans To overcome these problems, the concept of texture masks
perceive as a specific type of texture. was developed. These masks are either used to guide con-
For a limited class of textures this distribution can be sistent [LYS01] or user-controlled [Ash01] texture place-
modeled using for example Perlin Noise [Per85] or reaction- ment, or to enforce that the shape of prominent features
diffusion systems [Tur91]. These types of procedural texture e.g. from animal fur is not broken apart during texture syn-
synthesis offer the advantage of user control and extremely thesis [ZZV∗ 03]. We use a similar approach in the final syn-
compact representation. thesis step of our algorithm but we propose a unique and
automatic analysis for generating such texture masks from
To capture more general types of texture, statistical mod- near-regular textures.
eling has been adopted. Motivated by research on human
texture perception, statistics of filter response vectors have These near-regular textures have been devoted attention
been used most frequently. The actual synthesis is per- from the community because they contain regular (tileable)
formed by iteratively matching statistics of a sample tex- structures that are not captured by local distributions, and ir-
ture and the synthesized result. E.g., Heeger and Bergen regular elements that are not reproduced correctly by tiling.
[HB95] matched marginal histograms of filter response Therefore, textures dominated by regular structures still pose
vectors at different spatial scales. Follow up publications problems for sample-based texture synthesis and need spe-
[Bon97, PS00, BJEYLW01] improved upon this scheme by cial attention. A first step in this direction was made by the
enforcing more complex joint statistics of filter coefficients work of Dischler et al. [DMLC02] who tried to identify ele-
but still fail on highly structured textures. Few publications mentary patches in the texture and analyzed their spatial ar-
(e.g. [ZWM98]) propose parametric texture models based on rangement which is then reproduced in the synthesized tex-
the Markov Random Field model of texture. Texture synthe- ture. An approach bridging the gap between regular tiling
sis involves fitting the model to a sample texture and sam- and stochastic placement of texture elements was presented
pling from the resulting distribution which can be computa- by Cohen et al. [CSHD03]. They enforce boundary con-
tionally very expensive and still reproduces mainly stochas- ditions along tiles but the placement does not account for
tic textures only. global regular structures ranging across tiles.

These elaborate models are outperformed in speed, qual- A more general approach for handling regular and poten-
ity and applicability by simple non-parametric sampling as tially large structures during texture synthesis was developed
proposed in the seminal paper by Efros and Leung [EL99]. by Liu et al. [LCT04] and Liu and Tsin [LTL05]. They used
The method synthesizes a texture pixel by pixel by selec- the observation that an infinite variety of periodic patterns
tively copying pixels from a sample. Appropriate pixels are can be characterized by a finite number of symmetry groups
identified by comparing their neighborhoods whose size is to extract tileable parts of a texture that correspond to the
the only tuning parameter of the algorithm. It can be shown regular structure of the texture. Tiling these textures with
that this scheme produces consistent estimates of the dis- overlap and merging the tiles leads to very good results for
tribution of pixels given their neighborhood [Lev02]. This most regular textures. The approach was recently extended
simple but powerful idea has inspired many researchers and to handle near-regular textures [LLH04] by treating them
numerous improvements of the original algorithm have been as deformations of regular textures. One drawback of this
published over the years. Many of them focused on speed- method is that extraction of tiles requires significant user in-
ing up the search for similar neighborhoods using for exam- tervention whereas our process is fully automatic. Another
ple tree-structured vector quantization [WL00], k-coherance problem is that it requires at least two complete tiles to be in-
search [TZL∗ 02], or jump maps [ZG02]. For textures with cluded in the sample texture. Although this usually poses no
large structures compared to affordable neighborhood sizes, problem, such data may be unavailable if regular structures
copying of whole patches instead of single pixels was ad- of different scales are included in the texture (a complete tile
vocated: Efros and Freeman [EF01] select fixed size blocks would need to be as large as the least common multiple of the

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

a) Original b) DFT low-pass c) DFT intensity d) FrDFT intensity

original
2 frequencies
a) Original b) DFT low-p. 6 frequencies
original 20 frequencies

original original
c) DFT int. 2 frequencies d) FrDFT int. 2 frequencies
6 frequencies 6 frequencies

Figure 1: Results of applying filters to a Corduroy texture samplewith black dots added at random locations. Whereas the images
show the texture sample, the curves visualize the luminance values of the pixels of the first scanline only. While the lowpass
filter result (b) still contains irregular structures and about 20 basis functions are required for a reasonable approximation of
the 1D signal, the intensity filter (c) performs much better using just 6 frequencies. Nevertheless, the leakage error can only be
eliminated applying the FrDFT intensity filter (d).

different scales). Our approach is able to treat the different crete Fourier transformation (DFT) which represents the sig-
scales individually and therefore requires no such large tex- nal by a sum of sine and cosine functions. Given the resulting
tures. Finally, unlike our approach they neither separate reg- frequency spectrum, the question of which and how many
ular from stochastic texture elements, which improves the frequencies are relevant for the regular part of the image sig-
quality of synthesized results, nor do they compute an ex- nal arises. If too few frequencies are taken into account, most
plicit, compact model of the regular texture parts. of the structure is smoothed out. If too many frequencies are
selected, the signal itself is better reproduced but at the cost
of introducing irregular structure.
3. FrDFT-Analysis
One way to select the relevant frequencies is to apply a
In this section, we describe our approach for separating the low pass filter to the image signal. In previous approaches
regular structure, which dominates the appearance of many for texture synthesis this idea is incorporated by building
near-regular textures like knitware or woven textiles, from image pyramids and synthesizing the low-resolution levels
the irregular one. Our intuitive distinction between these two first. Unfortunately, in general these low frequencies do not
kinds of data is that structures are perceived as regular if they correspond to the regular structures directly, which is shown
occur (at least nearly) periodically while irregular structures in Figure 1b.
are distributed in a different, more complex way. Therefore,
A more appropriate selection criterion is based on two
we represent a texture by periodic basis functions to deter-
observations. First, since the regular structures in the im-
mine and extract regular structures.
age signal dominate the overall appearance of most near-
Such a representation can be derived by applying a dis- regular textures (see e.g. the Corduroy sample in Figure 1),

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

1 FT
f(k)=cos(2πbk
—)
m DFT
FrDFT
14 FrDFT cos(7.2·2πx)
0.5
b=2 12
0
m 10
5
-0.5 b=—
2
8

-1
6 0 5 10 15 20 25

Figure 2: Fractional frequency. Representing the perfectly 4

regular fractional frequency b = 52 by integer frequencies

2
requires a large amount of basis functions, since the corre-
sponding signal is not periodic w.r.t. the range [0, m]. 0
0 5 10 15 20 25 frequency

Figure 3: Comparison of absolute DFT and FrDFT coeffi-

they carry a much larger amount of energy than the irregu- cients for the curve in Figure 1 after subtraction of mean
lar patterns. Second, while the energy contained in strongly value. The dominant regular structure is caused by fre-
visible irregular structures is distributed among a large num- quency 7.2. The small plot shows the FrDFT of the function
ber of frequencies, the main part of the energy contained in cos(7.2 · 2πx).
the periodic structures is carried by a few frequencies al-
ready (compare Figure 1c). We therefore select the frequen-
cies carrying the most energy and call the selection based on
this criterion an intensity filter. Synthesizing the regular structure by continued evaluation
of periodic functions requires exact knowledge of the frac-
While application of the intensity filter to the DFT of the tional frequencies corresponding to the regular structures. A
signal yields good results already, the leakage effect of the method to analyse these frequencies is the fractional Fourier
DFT introduces artifacts along the borders of the image as transform (FrDFT, also called linear FrDFT [Wei]) [BS90].
illustrated in Figure 1c. This prohibits high quality synthesis While the DFT of a sequence a j , j = 0, . . . , m − 1 is a func-
of the extracted regular structure since the erroneous regions tion FT : Z → C with
would be contained repeatedly in the synthesized image. The
1 m−1 −2πi zmj
reason for the existance of leakage problems is shown in
Figure 2, where both functions represent perfectly periodic
FT (z) = ∑ a je
m j=0
, (1)
signals restricted to the interval [0, m]. With respect to the
given interval, only the function with b = 2 is periodic, the the fractional Fourier transform of a sequence a j , j =
one with b = 52 is not. Applying the intensity filter to the 0, . . . , m − 1 is a function FT : R → C with
DFT always yields a signal periodic w.r.t. the given inter- 1 m−1 −2πi kmj
val, which prohibits a faithful representation of the perfectly FT (k) = ∑ a je
m j=0
(2)
regular frequency b = 52 . For a texture the restriction of the
signal to such a window is usually defined implicitely when or for a two-dimensional texture
capturing the texture by a photograph. The window is typi- my −1 mx −1  
kx jx k y jy
1
∑ ∑
cally neither perfectly aligned with the regular structure nor −2πi mx + my
FT (kx , ky ) = a jx jy e . (3)
does it contain an integer amount of oscillations of the reg- mx my jy =0 jx =0
ular structure. A solution for this problem is the use of a
fractional discrete Fourier transform. The following property provides the key idea to extract the
exact fractional frequency of a signal: The absolute value
|FT (k)| of the FrDFT of a complex periodic sequence of
3.1. Fractional DFT bj
the form a j = Fb e2πi m , j = 0, . . . , m − 1, Fb ∈ C with fre-
Definition 3.1 (Fractional Frequency) For a function quency b ∈ R reaches its maximum for k = b [BS90] and
f (k) = cos(2π mb k) defined on [0, m], b ∈ [0, m2 ], we call b FT (b) = Fb is the Fourier coefficient that determines inten-
the frequency with respect to m. b is called a fractional fre- sity and phase (see Figure 3). To exploit this property (which
quency if b ∈ / Z. For a two-dimensional function analogously holds for frequency pairs) in the context of tex-
   ture synthesis, two problems have to be solved. First, tex-
bx kx by ky
f (kx , ky ) = cos 2πi + tures are real-valued. Second, the regular structure of most
mx my
relevant textures is contained in more than one frequency
the analogon holds for a frequency pair (bx , by ) with respect and therefore not only a single frequency has to be deter-
to mx and my . mined.

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

A widely accepted approximation to the first problem is Threshold 0.5 1 2 5

the computation of the analytic signal from the real-valued Frequency pairs found 175 76 35 14
input by computing the Hilbert transform [Bra99]. Runtime 97 s 48 s 27 s 11 s
Solving the second problem is more difficult. If the reg- Table 1: Runtime and result size of the FrDFT analysis for
ular structure is contained in several frequency pairs (as various thresholds and the texture from Figure 1 measured
usual), the FrDFT is the sum of the FrDFT of each of the on a 2.4 GHz PC.
pairs. As the small plot in Figure 3 shows, |FT (k)| contains
many local maxima even for a function determined by a sin-
gle dominant fractional frequency. The FrDFT of a real se-
quence as in the large plot of Figure 3 therefore contains var- complexity of the algorithm in two ways. First, the maxi-
ious local maxima of which some correspond to fractional mum search in the 2D-FrDFT can be reduced to the one-
frequencies contained in the regular structure and some do dimensional case, because for fixed kx or fixed ky Equa-
not. In the following we will therefore describe a method to tion (4) is a 1D-sinc2 function. To find a 2D-maximum, we
identify the correct maxima in FT (kx , ky ) corresponding to therefore first search a 1d-maximum with fixed ky and then
the fractional frequencies that carry the regular structure. use its position as fixed kx .

The method we developed is based on the fact that the Applying this first modification, the run-time complex-
m
magnitude mli of a local maximum at (kxi , kyi ) is much ity is reduced to O(mx my ( mdxx + dyy )n) but still remains high.
smaller than the magnitude mg of the global maximum at Therefore, our second optimization is to restrict the regions
(kxg , kyg ) (mli ≈ mg /|π2 (kxg − kxi )(kyg − kyi )| for kxi 6= kxg in which we search for the maxima. As visible in Figure 3,
and kyi 6= kyg ). This is due to the fact that the FrDFT of a 2D the position of a FrDFT global maximum can roughly be
function with frequencies bx and by can be approximated as determined using the DFT. We are only looking for the most
follows (for a proof see Appendix A): intense frequencies and thus only the highest maxima of FT .
The DFT gives us the values of FT for kx , ky ∈ Z and there-
|FTbx ,by (kx , ky )|2 ≈ fore we only need to search the [−1, 1]2 regions around DFT
|Fbx ,by |2 · sinc2 (kx − bx ) · sinc2 (ky − by ) (4) coefficients that are larger than a threshold. By choosing a
high threshold, a large amount of time can be saved (Ta-
where sinc(x) is defined as ble 1). Applying this second modification reduces the run-
(
sin(πx) time to O(mx my ( d2x + d2y )c), where c denotes the number of
πx x 6= 0
sinc(x) = . (5) DFT values above the threshold.
1 x=0
The extracted frequency pairs are near-optimal only since
Due to this strong difference between the magnitude of interference effects caused by the summation of multiple fre-
local and global maxima, the global maxima should be well quencies shift the location of maxima slightly. To compen-
preserved even when multiple fractional frequencies are con- sate for this effect, we optimize the frequency pairs such that
tained in the sequence. In special, the most intense maximum the least-squares color difference between the original image
should still remain the global maximum, which turned out to and the one reconstructed from the frequency pairs is mini-
be a valid assumption during our tests. mized.

The basic method for extraction of relevant frequencies

is therefore the following: we determine the frequency with 3.2. Fractional Fourier Texture Masks
largest absolute value of the corresponding fractional Fourier
The FrDFT analysis determines frequency pairs b1 , . . . , bn
coefficient, remove the contributions from this frequency
with respective Fourier coefficients F1 , . . . , Fn . These fre-
from the analyzed image, do a FrDFT transformation on the
quencies can be synthesized using the inverse DFT formula:
remaining image, and keep continuing extracting frequen-  
bh y jy
cies until the absolute value of the largest remaining Fourier n 2πi
bh x jx
+
∑ Fh e
mx my
coefficient is below some threshold. Determining largest val- a jx jy = . (6)
ues in each step is done by first sampling the coefficients h=1
with a fixed step size and then applying a standard maxi- If we choose jx , jy ∈ Z, the size of the synthesized texture
mization algorithm, starting at the sample with largest value. is unlimited and the frequencies of the regular structures
represent the parameters of a procedural texture containing
Unfortunately, extracting frequencies in this way is very
these structures. This process is known as Fourier synthe-
time consuming (the run-time of the algorithm is roughly
m sis [WW92] and we call the output fractional Fourier texture
O(mx my mdxx dyy n), where dx and dy denote the distance in x
masks (FFTMs). Examples of FFTMs are shown in the third
and y direction between values for which the FrDFT coef-
row of Figure 7.
ficient is computed and n denotes the number of extracted
frequencies). We therefore suggest to improve the run-time We can use the frequency information to calculate the size

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

of a texture with tilable regular structures. A regular struc- of the respective FFTM values. The contributions from
ture is tilable, if the frequencies describing the structure are both parts are summed into a single value after scaling the
not fractional w.r.t. the texture size. In simple cases, this is FFTM-similarities by a mask weight c. Please note that
the most intense frequency pair. In the general case, the low- incorporating dMM can be interpreted as the previously
est frequency of the regular structures has to be determined. missing way to improve the standard similarity measure
Let bl be this frequency pair. Then to consider structural information as well.
nx ny
m0x = mx · and m0y = my · (7) Cluster ID match. The pixels of Min are clustered based
blx bly
on similar neighborhoods N f ull using k-means clustering.
produces tilable sizes for all (nx , ny ) ∈ N × N and nx = Whenever a pixel xout is synthesized, the cluster ID of the
ny = 1 is a single tile of the pattern as described by Liu et corresponding pixel is determined. This cluster ID defines
al. [LLH04]. a candidate set of pixels in Min and thus corresponding
The FrDFT analysis and synthesis are performed for each pixels Tin from which the pixel to be copied is selected
color channel separately. Our tests determined that trans- using the measure dT T defined above.
forming the RGB color data to YCr Cb colorspace gives best
results since it reduced deviation of the per-channel frequen- Synthesized
cies. In addition, for many textures the analysis turned out (Tout and Mout)
to become faster, because usually the Y-channel contains the Nupper

Ny
most information.
Nlower

4. Synthesis Not yet synthesized

(Mout only)
In this section we describe how to incorporate FFTMs into Nx
xout
existing pixel- or patch-based synthesis algorithms. The out-
put texture will be denoted by Tout , by Mout we will refer to a
FFTM with size equal to the desired output size, and by Min Figure 4: The neighborhoods Nupper and Nlower with size
to the part corresponding to input texture Tin . In this way for Nx × Ny . Nupper is defined for all textures and masks, but
every pixel in Tin there is exactly one corresponding pixel in Nlower is undefined for Tout .
the FFTM Min .

4.1. Pixel-Based Synthesis

In the pixel-based synthesis approach an output texture is
generated from an input texture by selectively copying pix-
els. A pixel is chosen by comparing the neighborhood of
the current pixel in the output to a candidate list of neigh-
borhoods of pixels in the input texture. The comparison
of neighborhoods is typically carried out by computing
the L2 norm of the difference between neighborhood vec-
tors ~N(Tin , xin ) and ~N(Tout , xout ). A typical neighborhood is
shown in Figure 4.
Incorporating FFTMs into pixel-based synthesis algo-
rithms can be achieved in different ways, from which we
implemented the two following ones: Figure 5: Upper row: synthesis results with k-coherence and
Full neighborhood comparison. This approach is inspired cluster ID match. The results with full search and full neigh-
by the texture mask approach as proposed by Zhang borhood comparison are similar. Lower row: ANN search
et al. [ZZV∗ 03]. The neighborhood used to determine and full neighborhood comparison. Both examples used a
best matching pixels is extended from Nupper to N f ull = 3 × 3 neighborhood. The images on the right visualize x and
Nupper ∪ Nlower . Whereas the similarity of pixels in Nupper y components of source coordinates respectively. The origi-
is measured by the standard L2 norm nal texture is shown in Figure 7.

dT T = ~N(Tin , xin ) − ~N(Tout , xout ) . (8)

2 To accelerate the actual neighborhood selection stan-
For pixels in Nlower we evaluate the L2 norm dard strategies like the k-coherence search of Tong et
al. [TZL∗ 02] and approximate nearest neighbor (ANN)
dMM = ~N(Min , xin ) − ~N(Mout , xout ) (9) search [LLX∗ 01, ZG02] can be applied in both approaches.
2

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

We achieved the best results for the combination of full 5. Results

neighborhood comparison with ANN search. An examina-
We tested our algorithms with various texture samples. The
tion of the output source coordinates as illustrated in Fig-
pixel-based algorithm is very easy to use since the only
ure 5 shows the reason for the better quality of the ANN
manual parameters that need to be selected are the inten-
search results. The apparent noise in the output texture is
sity filter threshold, the neighborhood size, and the mask
caused by very little spatial coherence in the source co-
weight. For synthesizing textures with the help of FFTMs
ordinates. The noise is not caused by problems in the k-
we used a 3 × 3 neighborhood which is (much) smaller than
coherence or the ANN search algorithm, because it occurs
the largest structures in the textures. When omitting FFTMs
even with an exhaustive search that always finds the best
much larger neighborhoods were used (for the images in Fig-
matching neighborhood. If the ANN search with the full
ure 7, from left ro right 6 × 6, 5 × 5, 8 × 8, 10 × 10, and
neighborhood search is used, the source coordinates show
10 × 10) which increases synthesis times drastically.
that small spatially coherent regions are copied from the in-
put texture. This is due to the implementation of the ANN As the results in Figure 7 shows, FFTMs clearly
algorithm we use [AM], which favors neighborhood vectors help to preserve regular structures. While standard ANN-
close to the query vector if the tree was built with the vectors accelerated per-pixel synthesis of the textile textures fails
in scanline order. to preserve the appearance of the textures – especially re-
production of the rightmost texture fails completely – sim-
During our experiments, we found that for reproducing
ply employing the FFTMs as textures performs much bet-
simple structures with the ANN approach, a small 2 × 2
ter already, since they preserve the textures’ most significant
neighborhood and a weight c ≈ 1 produce good results. Re-
property: their regularity. Addition of irregular detail further
production of more complex structures like knitted wool re-
improves the quality of the texture whereas the degree of
quires a larger 6 × 6 neighborhood to obtain good results and
improvement depends on the visual dominance of the regu-
possibly a higher value for c. Usually, if c < 0.1 the mask has
lar structure. Especially textures with visually rich appear-
no effect, and if c > 5 the mask weight is too large. In case
ance like the knitted wool or the rightmost texture profit ex-
large neighborhoods are required, we apply Principal Com-
tremely. To our knowledge no other automatic texture syn-
ponent Analysis to reduce the dimension of the neighbor-
thesis algorithm is capable of producing results that resem-
hood vectors to about 16, which significantly increases syn-
ble the input textures that closely. Additional, very nice re-
thesis speed while just slightly decreasing synthesis quality.
sults that do not represent textiles are shown in Figure 8.

4.2. Patch synthesis

Incorporation of FFTMs into patch-based synthesis algo-
rithms basically follows the same idea as for pixel-based
methods. Whereas the quality of pixel-based algorithms was
improved by completing the full neighborhood with val-
ues from FFTMs, we applied the same principle to parts of
patches that do not overlap with already synthesized pixels.
Figure 6: Example for improved quality of patch-based
Additionally, to support iterative improvement of synthe-
synthesis. Although the mask has good quality, the ANN
sized textures using the Graphcut algorithm [KSE∗ 03] we
synthesis (middle) fails to reproduce the irregular struc-
extended the pixel representation from standard 3D RGB
tures. Applying extended patch-based synthesis incorporat-
vectors to 6D vectors that additionally contain the respective
ing FFTMs (right) the results become very pleasing.
mask values, scaled by the FFTM weight c. This way, we can
simply reuse the standard L2 norm to compute dMM +c·dT T ,
which helps to find well fitting patches that additionally pre-
Synthesizing textures using our patch-based approach
serve the regular structure.
leads to very good results which are superior to the results
of the ANN-accelerated pixel-based method in some cases.
Figure 6 shows an example in which the pixel-based algo-
4.3. Extensions
rithm fails to add the irregular details but which is handled
Our algorithm can easily be extended to create tilable tex- by the patch-based algorithm very well. Further results of
tures. With Equation (7) we calculate an appropriate output this method are shown in Figure 9. Synthesis was done us-
size for the regular structures. If we wrap around the neigh- ing the sub-patch matching strategy [KSE∗ 03], which was
borhoods at the border and add a second pass for the pixels previously not known to give good results for near-regular
where the opposite neighborhood was undefined during the texture, which confirms the usefulness of FFTMs. The used
first pass, the irregular structures produced by the pixel syn- patch size can be determined automatically by computing
thesis fit without visible edges. parts of the texture that are tileable (see Section 3.2), which

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

are usually much smaller than the full texture, leading to run- the Levenberg-Marquardt optimization method gets stuck
time advances compared to the entire patch matching strat- in, undesired interference patterns as visible in the mask in
egy [KSE∗ 03]. The determined patch size needs not be very Figure 10 occur. The errors are usually small enough to al-
accurate to achieve pleasing results (e.g. the bottom right low a reproduction of the sample, thus the FrDFT intensity
texture in Figure 9 contains features of size 75 × 60 pixels filter can always be used to avoid the DFT leakage effect.
and was synthesized using a patch size of 40 × 40). Please However, for textures with difficult structures, the larger the
note that synthesis of the textures in Figure 6 and in the top FrDFT synthesized area becomes, the more disturbed the re-
left of Figure 9 was previously not possible using fully auto- sult gets (see Figure 10).
matic algorithms (see [LHW∗ 04]).

1282 pixels 2392 pixels

6. Conclusions
Neighborhoodsize No PCA PCA No PCA PCA
2×2 0.16 0.07 0.42 0.10 In this paper a new method for synthesis of near-regular tex-
3×3 0.42 0.12 1.44 0.14 tures was proposed. The key observation behind this method
4×4 0.90 0.21 3.22 0.21
is that an DFT intensity filter can be applied to separate dom-
5×5 1.65 0.37 — 0.30
inant regular structures from irregular texture detail. Since
Table 2: Runtime per output pixel for the ANN synthesis in the DFT intensity filter works for already tileable textures
milliseconds for the first (1282 pixels) and fourth (2392 pix- only, we applied FrDFT instead of DFT. We introduced an
els) sample in figure 7. PCA was applied to the neighbor- algorithm for automatic extraction and synthesis of the reg-
hood vectors from Tin and Min to reduce their dimension to ular patterns, resulting in fractional Fourier texture masks.
16. Based on these masks we proposed sample-based texture
synthesis algorithms that add the missing irregular texture
Table 2 shows some runtime examples for the ANN syn- details and showed the high quality of results by several ex-
thesis, measured on a 2.4 GHz Pentium 4. The runtime in- amples.
creases with the neighborhood size, but can be reduced sig- Application of the FrDFT intensity filter should prove
nificantly using PCA. Other measurements show that the beneficial in combination with other methods as well. Liu
ANN search time depends on the sample appearance, be- et al.’s [LTL05] approach for computation of shape and size
cause the time varies for samples of the same size. In gen- of tileable texture elements, which is based on autocorre-
|N|
eral, we found an approximate runtime of O( ε log |Tin |) lations, should be improved by removing irregular texture
per output pixel. parts. Additionally, the extracted frequencies represent an
Synthesis times for the patch-based method are much explicit description of unique texture properties and might
longer, typically many minutes for the examples shown in thus contribute to accurate texture recognition. Finally, the
this paper. The exact time naturally depends on the size of intensity filter might be employed as the basis of a special-
the synthesized texture, the number of improvement steps ized compression technique.
necessary or allowed, and the size of copied patches. Never- Although our method turned out to be very robust for tex-
theless, synthesis times are not noticeably longer than with- tures with regular structures that carry a large amount of en-
out incorporation of FFTMs. ergy, handling of regular textures like pinstriped suits is diffi-
Comparing the pixel- and patch-based synthesis ap- cult. Improving our technique for textures where the regular
proaches is difficult. For most textures, ANN-accelerated patterns are very small and appear at very distant locations
synthesis already yields very good results at a fast speed. – leading to a much smaller amount of energy – remains for
Nevertheless, we found the patch-based algorithm to be future research.
more robust: it provides good results even in cases where
In addition, handling the problem of inexact extraction of
the pixel-based approach fails.
frequencies as described in Section 5 will also be investi-
The quality of the FFTM has great influence on the result. gated further.
If the mask contains the regular structures without errors,
the synthesized textures are of high quality. Otherwise, the Finally, in order to make our approach applicable to near-
synthesis algorithms produce errors as shown in Figure 10. regular textures with substantial geometric variation, we
plan to combine our method with regularization approaches
The errors are caused by slight deviations from the true like the one of Liu et al. [LLH04].
frequency in the FrDFT analysis process and occur espe-
cially, if the texture has sharp structures like the brick wall.
The Fourier transform of these structures consists of sev- Acknowledgements
eral frequencies at distinct, fixed ratios to each other. If
the FrDFT analysis fails to determine these frequencies ex- This work was partially funded by the European Union un-
actly due to numerical problems or due to local minima der project RealReflect (IST-2001-34744).

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

Figure 7: Examples for successful synthesis. Each column shows from top to bottom the input sample, standard ANN synthesis
without a mask, the mask created with the FrDFT synthesis, and the ANN synthesis result with mask. In many cases the FFTM
provides a very accurate approximation of the synthesized texture already.

Figure 8: Examples for successful synthesis of non-textile samples with the pixel-based approach.

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

Figure 9: Examples for successful synthesis with the patch-based approach.

Figure 10: Problematic synthesis. The FFTM (middle) contains errors if the frequencies are extracted inaccurately, which leads
to undesired interference. In such a case, texture synthesis (right) fails to reproduce the original appearance (left).

 
d
Appendix A: Proof of Approximation 4 The Taylor series of 1 − cos m
gives

Theorem A.1 Let d := 2π(k − b). Then for k, b ∈ [0, m[ d


d2
2 2
1 − cos ≈
|FTb (k)| ≈ sinc (k − b). (10) m 2m2
1 − cos(d) 2
Proof A.1 ⇒ ≈ 2 (1 − cos(d))
m2 (1 − cos( md )) d

If frequency b is described by Fourier coefficient Fb , then

2
sinc2 (k − b) = (1 − cos(d)) . |FTb (k)|2 ≈ (|Fb | · sinc(k − b))2 . For a two-dimensional frequency
d2 (bx , by ) with coefficient Fbx ,by
2
1 1 − eid 1 − cos(d) |FTbx ,by (kx , ky )|2 ≈ |Fbx ,by |2 · sinc2 (kx − bx ) · sinc2 (ky − by ) (11)
|FTb (k)|2 = = [BS90]
m2 1 − e idm m2 (1 − cos( md )) for bx , kx ∈ [0, mx [ and by , ky ∈ [0, my [.

c The Eurographics Association and Blackwell Publishing 2005.

 A. Nicoll & J. Meseth & G. Müller & R. Klein / Fractional Fourier Texture Masks

References [LLH04] L IU Y., L IN W.-C., H AYS J. H.: Near regular

texture analysis and manipulation. In Proc. of SIGGRAPH
[AM] A RYA S., M OUNT D.: ANN: Library
’04 (August 2004).
for Approximate Nearest Neighbor Searching.
www.cs.umd.edu/∼mount/ANN/. [LLX∗ 01] L IANG L., L IU C., X U Y.-Q., G UO B., S HUM
H.-Y.: Real-Time Texture Synthesis by Patch-Based
[Ash01] A SHIKHMIN M.: Synthesizing natural textures.
Sampling. ACM Trans. Graphics 20, 3 (2001), 127–150.
In Proc. of Symposium on Interactive 3D Graphics
(2001), pp. 217–226. [LTL05] L IU Y., T SIN Y., L IN W.-C.: The Promise and
Perils of Near-Regular Texture. International Journal of
[BJEYLW01] BAR -J OSEPH Z., E L -YANIV R., L ISCHIN -
Computer Vision 62, 1-2 (2005), 145–159.
SKI D., W ERMAN M.: Texture Mixing and Tex-
ture Movie Synthesis Using Statistical Learning. IEEE [LYS01] L IU X., Y U Y., S HUM H.-Y.: Synthesizing bidi-
Trans. Vis. and Comp. Graphics 7, 2 (2001), 120–135. rectional texture functions for real-world surfaces. In
Proc. of SIGGRAPH 2001 (2001), pp. 97–106.
[Bon97] B ONET J. S. D.: Multiresolution sampling pro-
cedure for analysis and synthesis of texture images. In [NA03] N EALEN A., A LEXA M.: Hybrid texture synthe-
Computer Graphics (1997), pp. 361–368. sis. In Proc. of 14th Eurographics Workshop on Rendering
(2003), pp. 97–105.
[Bra99] B RACEWELL R.: The Fourier Transform and Its
Applications, 3rd ed. McGraw-Hill, NY, 1999. [Per85] P ERLIN K.: An image synthesizer. In Proc. of
SIGGRAPH 1985 (1985), vol. 19(3), pp. 287–296.
[BS90] BAILEY D. H., S WARZTRAUBER P. N.: The Frac-
tional Fourier Transform and Applications. Tech. Rep. [PS00] P ORTILLA J., S IMONCELLI E. P.: A Paramet-
RNR-90-004, NASA Advanced Supercomputing, Mail ric Texture Model Based on Joint Statistics of Complex
Stop T27-A, Moffett Field,CA 94035, April 1990. Wavelet Coefficients. International Journal of Computer
Vision 40, 1 (2000), 49–70.
[CSHD03] C OHEN M. F., S HADE J., H ILLER S.,
D EUSSEN O.: Wang tiles for image and texture gener- [Tur91] T URK G.: Generating textures on arbitrary sur-
ation. ACM Trans. Graphics 22, 3 (2003), 287–294. faces using reaction-diffusion. In Proc. of SIGGRAPH
1991 (1991), pp. 289–298.
[DMLC02] D ISCHLER J.-M., M ARITAUD K., L ÉVY B.,
C HAZANFARPOUR D.: Texture Particles. In Proc. of Eu- [TZL∗ 02] T ONG X., Z HANG J., L IU L., WANG X., G UO
rographics 2002 (2002). B., S HUM H.-Y.: Synthesis of bidirectional texture func-
tions on arbitrary surfaces. In Proc. of the 29th annual
[EF01] E FROS A. A., F REEMAN W. T.: Image quilting conference on Computer graphics and interactive tech-
for texture synthesis and transfer. Proc. of SIGGRAPH niques (2002), pp. 665–672.
2001 (August 2001), 341–346.
[Wei] W EISSTEIN E. W. ET AL .: Fractional fourier
[EL99] E FROS A. A., L EUNG T. K.: Texture synthesis by transform. from mathworld–a wolfram web resource.
non-parametric sampling. In Proc. of IEEE Int. Conf. on mathworld.wolfram.com/FractionalFourierTransform.html.
Computer Vision – Volume 2 (1999), p. 1033.
[WL00] W EI L.-Y., L EVOY M.: Fast texture synthesis
[HB95] H EEGER D. J., B ERGEN J. R.: Pyramid-based using tree-structured vector quantization. In Proc. of SIG-
texture analysis/synthesis. In Proc. of SIGGRAPH 1995 GRAPH 2000 (2000), ACM Press/Addison-Wesley Pub-
(1995), pp. 229–238. lishing Co., pp. 479–488.
[KSE∗ 03] K WATRA V., S CHÖDL A., E SSA I., T URK G., [WW92] WATT A., WATT M.: Advanced Animation and
B OBICK A.: Graphcut Textures: Image and Video Syn- Rendering Techniques. ACM Press New York / Addison-
thesis Using Graph Cuts. ACM Trans. Graphics 22, 3 Wesley, 1992.
(July 2003), 277–286.
[ZG02] Z ELINKA S., G ARLAND M.: Towards real-time
[LCT04] L IU Y., C OLLINS R. T., T SIN Y.: A Compu- texture synthesis with the jump map. In Proc. of 13th
tational Model for Periodic Perception Based on Frieze Eurographics Workshop on Rendering (2002).
and Wallpaper Goups. IEEE Trans. Pattern Analysis and
[ZWM98] Z HU S. C., W U Y., M UMFORD D.: Filters,
Machine Intelligence 26, 3 (2004), 354–371.
random fields and maximum entropy (frame): Towards a
[Lev02] L EVINA E.: Statistical Issues in Texture Analysis. unified theory for texture modeling. International Journal
PhD thesis, University of California, Berkeley, 2002. of Computer Vision 27, 2 (1998), 107–126.
[LHW∗ 04] L IN W.-C., H AYS J. H., W U C., K WATRA V., [ZZV∗ 03] Z HANG J., Z HOU K., V ELHO L., G UO B.,
L IU Y.: A Comparison Study of Four Texture Synthesis S HUM H.-Y.: Synthesis of progressively-variant textures
Algorithms on Regular and Near-regular Textures. Tech. on arbitrary surfaces. ACM Trans. Graphics 22, 3 (2003),
Rep. CMU-RI-TR-04-01, Robotics Institute, Carnegie 295–302.
Mellon University, Pittsburgh, PA, 2004.

c The Eurographics Association and Blackwell Publishing 2005.