| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Jacques Blanc-Talon
ETCA/CREA/SP, 16 bis, av. Prieur de la Côte d'Or
94114 Arcueil, France
Email: blanc@etca.fr
Encoding fractal sets as quad-trees is considered. Every node of the tree is compared to a dictionary which is recursively built. Comparison is performed by looking for self-similarity within images. Geometrical operations (rotation and rescaling) are used to match statistical moments of the images to compare. Numerical results are used to determine the probabilities of assigning to the rules of a context-free grammar inferred from the set of trees.
Syntactic techniques provide a pleasant and almost natural way for generating fractal sets. One of the reasons for their popularity is that the objects actually being processed are symbols related to geometrical primitives (frequently vectors) rather than obscure numerical coefficients. These symbols are gathered into words, and sequences of words are iteratively built, giving better and better approximations of the fractal set. It is confounding but promising to see how the same principle is able to generate rather simple curves (Cantor's triadic set or von Koch's curve, for example, [7]) as well as much more complicated sets such as natural plants and forests [11, 12]. Thus, study of fractal sets, regardless of the dimension of the initial space (1, 2 or 3), is transposed into the study of infinite words. In the case of the simplest generating system, namely the D0L-system, it is merely the study of the topological adherence of its language, while the study of the system itself is a problem that can be expressed in terms of formal language theory. In this paper, DT0L-systems and Context-Free grammars are considered.
Little attention has been given to the thorny inverse problem. In a few words, it consists in computing the grammar that can generate a given fractal set. Obviously, the interest of considering fractal words instead of the sets themselves would fade if it were not possible to find a good inference algorithm. At this point, results gained in syntactic pattern recognition help, in particular to give answers to what follows. Before designing any inference method for fractal sets, one must consider the following points thoroughly:
Though queries (3) and (4) are relevant to pure grammatical inference, (1) and (2) address the present problem.
Concerning (1), an encoding (or a word) must be an ordered set of letters and the mapping of any sequence of words increasing in length is considered to be convergent to the initial data set. The order of the letters within the words (the way the words are written) is determined by the encoding algorithm. Thus, the set (or alphabet) of geometrical primitives (or letters) must be exhaustive; that is, the curve must be wholly described by the alphabet. This alphabet can be either fixed (for example, vectors) or dynamically determined according to the nature of the data set (sparse data, Jordan curve or thick set).
Concerning (2), structure of the fractal set must be translated into combinatorial properties of words so as to be used by the syntactic model. As we said above, this structural information consists in some relationship between different parts of the curve.
Figure 1: A syntactic fractal pattern recognition system.
This paper focuses on the encoding of sets for grammatical inference. Its implementation is the first block of a system aiming at analysing, recognising and synthesising 2D and 3D fractal sets from geological data (since the computations are quite intensive, the method has never been tested on 3D data!) Other blocks performing grammatical inference and parsing have been described in [4] and [5]. The basics needed to understand grammatical inference are exposed in Section 2. Sections 3 describes the segmentation method. Numerical results are used to compute the probabilities of a context-free grammar; since this grammar is inferred in the next block, detail of this previously unpublished work has been put in appendix A.
Figure 1 shows the different blocks of the system - those being detailed in this paper are shown in bold style.
The problem of grammatical inference can be roughly expressed as:
Given a language
, find the system which generates it.
The main assumption of grammatical pattern recognition is that every distinctive feature of the initial set has been captured
in the encodings of the inference set.
In the case of fractal patterns, this structural information is considered to be self-similarity.
However, if encodings must naturally reflect this self-similarity, the syntactic model must use it.
As we shall see, recursive models provide a nice scheme for making such structures within words.
Of course, mathematical structures are too perfect and some deviation will be allowed,
in particular in using the
-transform of a language.
Given a finite alphabet T, D0L-systems generate self-similar words by iterating a morphism
on an initial word s.
More generally,
can be drawn (randomly or not) at every iteration among a set of several morphisms when a DT0L-system is used.
A context-free grammar
in Chomsky normal form can then be easily derived from a DT0L-system
by replacing for every a in T the value
by a rewriting rule
(assuming f is a one-to-one map
and N a set of non-terminal symbols).
generates more realistic encodings than the initial D0L-system;
moreover their distribution can be enhanced by fitting the rules with probabilities.
This work, excepting the computation of the stochastic grammar (detailed in 4),
has been previously exposed in [4, 5, 3]
and we recall below the main results which are useful for the understanding.
Since DT0L-systems rewrite words from the left to the right, the existence of an infinite word
can be studied by considering the sequence of its prefixes
(left-factor set) in the following metric space.
The similarity distance
is defined as
for any words u, v in
,
the space of possibly infinite words.
The topology induced by
is the same as the left-factor topology one gets when considering prefixes of words.
More precisely, the word u is a left-factor of x if there exists v such that x = u v.
This notion leads to the notion of the adherence
of a language
and to the center
of a language:
Language adherence is a natural notion which does not lead to a convenient description of all the sets close to the initial one in the origin space. Extension of this notion to bilateral centres can be found in [6]; today, changing the definition of the convergence of a sequence seems more promising. A conclusion of this mathematical background is that every iterated morphism yielding an infinite word has an adherence set made of this word only. This unicity ensures that an approximate representation of the curve can be computed whatever the accuracy needed.
The previous ultrametric is not very convenient for comparing noisy encodings. The Levenstein distance between words u and v is defined as:
where 
stands for the ball centered on u of radius n, n being the number of
deletions, insertions and substitution of letters needed to transform u into v.
According to 
, let us define the
-transformation of order p of a language
as:
which allows us to consider finite noise over languages. We have proposed in [4] the following definition which leads to proposition 2.1:
Thus, a context-free grammar could be a convenient recursive system for generating fractals.
Its inference has been described in [5] as
the product of several generalisations of the inference of a D0L-system.
One first computes a D0L-system
which interpolates the structural information common to all encodings.
Inference of this system involves techniques such as the computation of the eigenvalues of a growth matrix.
A grammar is then derived from
which preserves the basic structure of
the curve.
One assumes the curve to encode is self-similar; that is, it is a patchwork of rotated, rescaled and translated copies of itself
(the Collage theorem, [1]).
Therefore, comparison of two images
can be performed by using a correlation-like formula after setting them
in the same axis system.
After that, the images have the same size
, their barycentre is at a middle point
and the slopes of their regression line are equal.
The algorithm performs successively a rotation of
, a rescaling, a translation plus a cropping (see paragraph 3.2).
Comparison of a couple of images
will be written from now on
for brevity.
The angle is determined as follows.
Let be a couple of binary images (the method is the same in the case of gray-level images)
of size
and
being the binary value of pixel (x, y) in image
.
The moment E[X] of the variable X is defined as usual as
where 
is the measure E[1] of the image being considered.
Given image 
, the well-known regression equation system is :
with solution
We consider a centered rotation
of image
so as to equal the new value
to the value
of image 
(we assume
exists):
in which 
denotes E[a]E[b] - E[ab] for the sake of clarity.
Assuming that
:
which can be rewritten
if:
Let 
, then
the global solution exists if
and is equal to:
Four comparisons are thus needed to determine the actual correlation value; the greatest result is chosen. One must notice that the accuracy of the method depends on the image being rotated and rescaled.
Quad-trees are used to tile the initial fractal curve with potential copies of itself. Such a tiling is easy to implement and the reader can convince himself/herself of the ability of quad-trees to generate 3D fractals in [2].
At every step, the current tiling is compared with primitives stored in a dictionary, this dictionary being dynamically determined (see next paragraph). Comparison is performed by using the correlation algorithm described above. If some correlation between the current tiling and any entry in the dictionary is found, the branching process stops; the node gets the label of the correct entry. Otherwise, the tiling is split up into 4 other tilings whose homogeneity with the root tiling (the whole set) is checked (equivalence of the fractal dimensions). A significant difference of the fractal dimensions implies either a copy of a different fractal curve is present within the initial fractal set or the tiling being considered is probably too small. The exploration stops when a minimal size of the tilings is reached.
Given two images
and
, an
important improvement consists in cropping the size of the biggest of the two
images so as to remove possible noise due to the tiling process. Bounds of the
new image are determined by using a standard optimisation algorithm - which is
greedy for computation time!
As previously said, the dictionary is composed of tilings and is dynamically built.
On the one hand, a given tiling is considered as a new entry every time the recursive exploration stops (that is, either when the minimum size for a tiling is reached or when inhomogeneity with the root tiling is found). On the other hand, elements in the dictionary are in constant competition with the tilings of bigger size to which they are compared: if the correlation is good enough, a smaller entry is replaced by a bigger one so as to refine the information stored in the dictionary.
Despite interesting results, this work is far from completion and raises challenging problems as research in fractals often does.
Among the set of possible questions, one may wonder how the information of boundaries adjustment used during the correlation process
(so-called cropping) can be added to the grammar. More generally, is it necessary to keep this information stored
or is the structural information the only thing needed to reconstruct the fractal set?
A definitive result concerning this research would be to find a canonical mapping from the space of words to the geometrical space so as to be able to draw any set, providing the correct grammar has been loaded. Such a goal could be weakened to the research of a minimal class, every mapping of which would fit the same task given a class of grammars. But according to A. Le Méhauté (see [10]), any parsing tree must convey a differential form which drives the generating process. Maybe this approach is too general in our restrictive study. As we pointed out in [4], a dual approach would be to study the importance of the function which maps the words to the geometrical space.
This method has been applied to atmospheric clouds and gave interesting results (NATO project).
Given an image
and the related inferred context-free grammar
we want to determine the probability to assign to every rule in P.
The result will be the stochastic context-free grammar (SCFG) which generates the class of fractal sets
.
For an introduction to stochastic languages, see [9].
Form of a rule in P is either
whose probability is known,
or 
whose probability is not.
Constraints are:
from
.
of any image
as close as possible
to the correlation value
.
The method is a straightforward application of the consistency conditions for stochastic context-free grammars.
Let 
be a SCFG.
is the set of stochastic rules
.
Let 
and
respectively denote
and the number of productions with premise A.
A SCFG is consistent if:
is the eigenvalue of the first moment matrix E of the generating process corresponding to
which has the greatest magnitude. Let us consider the set of rules C(A) with the premise A (see [8]).
For every A in N, the
argument-generating function
is:
where 
denotes the number of times the non-terminal
appears in the string
of the production
.
The matrix E is defined as:
and 
denotes its characteristic polynomial.
The problem of finding the
's can be considered as a maximisation problem (so as to ensure a uniform use of the rules)
and solved by using Lagrange's multipliers.
At the present date, we have no global formula and it must be done after every inference.
We just sketch the method so as not to introduce useless notations.
Let 
denote the encoding of image
and
the vector of probabilities.
Given a finite sequence of m images
, consistency and parsing conditions can be rewritten as:
Lagrange's method makes use of
multipliers related to the constraints f and g;
minimising 
implies:
How to Fill the Gap between Fractals and Stochastic Context-Free Grammars?
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html blanc.tex.
The translation was initiated by Pam Milliken on Tue Nov 5 09:06:18 EST 1996Tue Nov 5 09:06:18 EST 1996
