ISSN 1320-0682
|
|
|
|
ISSN 1320-0682 |
| Source: | http://www.complexity.org.au/ci/vol06/blanc-talon/blanc-talon.html | Received: | 01/07/1998 | ||
| Vol 6: | Copyright 1998 | Accepted for publication: | 15/10/1998 |
Jacques Blanc-Talon
CTA/GIP,
16 bis, av. Prieur de la Côte d'Or, 94114 Arcueil, France
Email: blanc@etca.fr
WWW: http://www.etca.fr/Users/Jacques.Blanc-Talon
Approximate identification of coupled map lattices is considered. The local dynamics is split into a local function, expanded in Hermite's polynomial series, and a coupling one which is the convolution product of the neighborhoods by a kernel. The local function fits the data set (an image) while the convolution kernel of the coupling function is adjusted to fit a set of some selected patterns, gathering the so-called ``structural information''. The structural information to be considered is shown to be the connected set of the zero-crossings of the Laplacian of the input image , which is computed by using Gauss kernels. A practical computation of a CML from stone patterns is shown.
Research on cellular automata (CA) is about a couple of decades old as it started, at least officially, approximately at the date of Wolfram's well-known papers [22]. Compared to the analytical study of global equations, cellular automata provide physicists with a mere bottom-up approach: global behaviors are generated from local rules and interactions over bounded domains. Generic CA have been proposed in various fields (see collective works [3, 8]) and the number of new related applications is still growing. The key point of this approach is that cellular automata can be efficiently implemented and tested: it is therefore an experimental approach in the best meaning of the word.
In brief, a cellular automaton is a discrete spatially-extended dynamical system: it is discrete in time, space and state space. However, this last feature could turn to be a stumbling block when matching with real experiments. Coupled map lattices (CMLs) were introduced by Kaneko [10] as a paradigm for the study of turbulence, convection and other similar problems occurring in physics. They may be considered as a generalization of CA since they are discrete in time and space but continuous in state space. Coupled map lattices are well-suited to the study of patterns growing under the action of repulsive and attractive forces [20], also called a reaction-diffusion process [16] and remain at the same time mathematically tractable. Despite the increase of their practical generality, only little attention has been paid to the inverse problem, namely the approximation of a data set; at the same time, the only works relevant to CA identification are probably [1, 8].
Actually, most of the work being available on CMLs is devoted to their analysis either by using statistical techniques [2] or by means of formal language theory [8, 9, 12]. One reason for this state of things is that both CMLs and CA are highly parameter sensitive which makes one wonder about the possibility of solving the inverse problem. Actually, any valid approximation scheme must answer a few fundamental questions, in the reverse order of importance:
The first question is relevant to the well-known parameter sensitivity of coupled systems. One common technique for coping with it is to control the CML Jacobian, which is discussed in section 3: the system behaves in a chaotic manner as long as it does not approach a fixed point. This chaotic behavior is an advantage in applications where tuning by hand of the parameters must be forbidden, as in data encryption applications. Langton's conjecture , which assumes there is a critical parameter turning on the chaotic behavior [23] has been criticized in many papers [6].
Some hints for answering the second question can be found in Roy and Amritkar's paper [18]. The authors show that noise does not play a detrimental role by destroying small patterns but, on the contrary, allows formation of new structures in a mode they call stochastic resonance.
As we shall see below, the initial purpose of this study is certainly not to explain any physical process but on the converse to force a system to reach a point somewhere in its evolution. Though no straightforward relationship can be exhibited, the method still performs CML identification since the system is computed according to structural information; moreover, it is not constrained to accept the image as a stable point which leaves it full ability to evolve in different directions.
The information being actually caught by the CML has been called ``structural information''. It consists of the edges of the initial image, which lie in the connected set of the zero-crossings of the Laplacian and are computed by using Gauss kernels. This point is discussed in section 4.
The practical problem being addressed in this paper is to compute a general (deterministic) coupled map lattice which can yield a particular array of values, whose integer truncation can be displayed as an image. Possible applications fall within image compression, texture analysis and cryptography. As for CA, interaction domains to be considered are restricted to small neighborhoods around cells because physically meaningful interactions are limited in range. In the present application, this choice is still valid since the luminance of a given pixel depends almost only on its neighborhood. Since no additional information is assumed to be available about the initial array, a Gaussian noise over the array may be a good and plausible start according to the particular definition of the structural information.
The evolution equation is the sum of a local (site) function and a coupling function. About the site function, instead of taking the logistic map which has been extensively studied either in chains [5] or in arrays (e.g. [11] for the analysis of spatial structures in population dynamics) or, again, any other polynomial function of degree in or [7], we shall try to remain as general as possible in keeping a power series within a convergence domain. Our approach which makes use of image processing techniques is rather innovative since the CML is computed straight from the image instead of being approximated by a CA like in [4]; moreover, there is only one CML for one or several images and its parameters do not evolve as in [14].
This paper is organized as follows. Section 2 introduces the theoretical work, a complete presentation of the method being given in section 3. In section 4, a new definition of CML structural information is given and discussed. Experiments from real images are shown in section 5, followed by the conclusion.
In the following, a CML is 5-tuple
where N is the dimension of the site array, S is
the set of sites indexed by
and L is the local transition function:
``attached'' to every site. r is the diameter of ball B (according to metric d in
- see remark below) whose interior can interact with the behavior of the site at its center; C is
the coupling function which governs that interaction, and thus the interaction of the whole ball on site x with
respect to some measure
is given by:
On discrete lattices, different tessellations and related metrics can be used which lead to different topological properties. In the following, we consider only linear coupling functions leading to the evolution equation at site j:
Notwithstanding such an apparent naive definition, this system is able to capture very rich and complex behaviors. When d is the ``city-block'' (or ``Manhattan'') distance, an interesting remark is that the finite sum in the right member of previous equation can be rewritten as:
with
for every
and
otherwise in the related box. This is the
well-known formula of the convolution product
of a
signal y by a kernel
which leads us to consider the
interaction of the neighborhood on the site as the one of a linear (or
not!) system with a given transfer function. For sake of simplicity,
we restrict now our attention to linear system with M = L = 2 r +
1. What can we do about the local function?
Provided L is
and of finite energy with respect to the scalar product:
that is
, it can be expanded in Hermite's polynomial
series:
The system is thus governed by the equation:
In the following, expansion is stopped at rank p. As we shall see, this particular choice of Hermite's expansion of the local function is motivated by the definition and the practical computation of the structural information.
Let us consider an image
of some process showing evidence
of spatial structures we would like to model. We assume we don't have
any additional information about this image, that we know neither the
image which initiated the process, nor whether the observed structures
are stable or unstable, nor if the grid of the image is the support of
the lattice. Reminding that the general inverse problem for CA is
NP-hard, the CML inverse problem without any hints seems hopeless and
it is not surprising that only a tiny effort has been devoted to it.
Instead of the rigorous mathematical problem of finding the right CML which generates image
(as a stable
point, if it has any), we can wonder:
Is there any CML which may generate a close image?
Of course, the proximity of the original image and the computed one must be expressed in terms of some structural distance, provided the favored structures gather the information we are interested in. Rewritten like this, the exact inverse problem becomes an approximation problem, which can be solved in several ways under the right assumptions. Our attempt, which hopes to remain as general as possible, is the following.
Square images are considered instead of rectangular ones for the sake of simplicity, without loss of
generality. Let
be the original
-valued image of size
. The estimated computed image
is given by the
general equation 2 which can be rewritten as:
( 
is the Kronecker delta), or, with a little linear algebra:
or again, in explicit form:
In equation 3,
and
are vectors with entries
and
; please notice that
may
be different from 0. The vector
is the input of the
equation.
is a Gaussian noise modelling the influence of the image outside of the rectangular box, its mean
and variance are
and
which are easily found by direct
computations over the set of neighborhoods. Thus,
is a Toeplitz matrix which shows interesting
theoretical properties.
If the local function (i.e. the
's) were known, the coupling function would be given by the inversion
of a large sparse matrix of size
or, equivalently, by the inverse of the mean
of all the
matrices of size
over the image. The first method is called deconvolution and generally
approached by the second one which yields a system like:
or, in a less aesthetic form:
with special indices
and
( 
is the floor integer value of the real x). The sums are restricted to a set
we
shall discuss in the next section. Our problem is thus equivalent to the coupled subproblems:
We haven't taken up the problem of finding the best p but the third subproblem is solved easily by minimizing the quadratic error:
Inverting the summation order yields a linear equation
with H being the sum over the
whole image
of the Hermite's polynomials.
Proposition 9.1
A standard Conjugate Gradient Method [21] has been used for minimizing this system; due to
polynomials properties, the Hessian matrix used in the algorithm has again a special form. The starting point of the
procedure is given as
and
as the Gaussian kernel from
equation 9 below.
Since the behavior of the CML is assumed to admit the input image
as a ``rather stable'' point, the
Jacobian of the system over a small part of the image:
has to be at most zero, at least minimum in magnitude. Its computation is a little tricky since it makes use of Hermite's polynomials recursion property and a discussion about it is out of the scope of this paper. On the other hand, the structural information of the image must remain invariant, i.e. under the action of the Gauss operator. This nuance on the meaning of a stable point should lead to a different analysis of stability.
Figure 1: (a) Apart of a
CML
Figure 1: (b) The structural information image computed with a Gaussian kernel
The finite sums in 7 are performed on a set
we haven't explicitly
defined yet: this is the set of connected structures within
. According to our initial hypothesis, it
collects the essential structural information needed to compute the CML. In [19], Roy and Amritkar define a
structure as a region of space such that the difference in the values of close sites within this region is less than a
given threshold. As such a simple definition could not be consistent with more advanced sophisticated structural models,
we define a structure to be the curve on which the Laplacian of the image is zero.
First, the notion of structure has to be defined clearly; second, an explicit numerical method has to be found. A
preliminary remark is that we consider the array of values of the CML
as an image, in the common understanding of it. In that case, a
structure can be defined according to the Mumford-Shah
model which seeks simultaneously for a
piecewise smoothed image
with a set
of abrupt
discontinuities called the edges. It can be shown
[15] that the best edge detector is the system minimizing the following functional with respect to F:
The first part means that the smoothed image is actually smooth outside of the edge set, the second that it is a good approximation of the initial image and the third that we look for a minimal set, discarding trivial solutions. In many ways, minimization of this functional is linked to solving the heat equation a favored operator of which is the Gauss function. As a conclusion to a theoretical analysis of these arguments, we define the structural information in a CML as:
Definition 9.1
Non-connected edges are not taken into account since they vanish after a few iterations.
Numerous methods (may be a thousand!) exist in image processing for performing edge segmentation and edge
connection. We have naturally been led to follow Marr and Hildreth's approach [13] which consists in
smoothing
by a Gaussian kernel, then in applying the Laplacian of the Gauss function, numerically computed by
the difference of two Gaussians (DOG operator). For instance, figure 4 is a subimage of 20,000 iterations
of
on an initial random image where T is the first approximation of a
Gaussian kernel, i.e.
As in the definition of the evolution equation 2, the Gauss function plays a crucial role: more precisely, the structural information of the CML is mainly captured by the coupling function.
Figure 2: natural rocks formations in Svalbard.
While honeymooning in Spitzberg in 1997, I arrived near New London (a smiling place which counted about 7 inhabitants at his best in the last century, when they were trying to extract marble from the stones under the ice) in a flat field covered with surprising formations, occurring in closed curves of medium size rocks put on a layer of smaller stones (see figure 2). Amazed, I took a picture of it and, back to the lab, tried to play with a simple CA simulation software so as to generate similar patterns. Of course I succeeded in doing something but was unable to know how valid my experiments were since I had no quality criterion.
Before applying the present identification process to the image, some preprocessing was made. First, the interesting part of the image showing the patterns was selected and mapped to a reference plane, after suppression of geometrical effects due to both perspective and camera optics (fig. 3.c); please note that this operation yields a triangular image. The structural information was then extracted from a rectangular part of the bottom of the image (the more accurate part); figure 3.d shows the structural information superimposed to the initial image.
Figure 3a:Mapped image: preprocessing of the initial image.
Figure 3b: Structural information: preprocessing of the initial image.
For the structural information being computed, the computed solution is
Figure 4 shows respectively 10, 100 and 1,000 iterations of the previous function (the contrast has been enhanced so as to show tiny details). While the background changes dramatically from (e) to (f), one can check show that the patterns capturing the structural information remain quite stable.
Figure 4a: Evolution of the computed CML: 10 iterations.
Figure 4b:Evolution of the computed CML: 100 iterations.
Figure 4c: Evolution of the computed CML: 1000 iterations.
Coupled map lattices were introduced about fifteen years ago as models of extended dynamical systems. One of their advantages is to show a very rich space-time dynamical behavior. However, most of the analytical studies in the literature have been restricted to low-order monic site functions since cubic or higher-degree polynomials are very hard to deal with analytically.
In the present case, we focused on the identification (or inverse) problem, considered in an approximation framework. This led us to define a notion of structural information coherent with information theory concepts and a new form of the evolution equation suitable for computational issues. A numerical identification algorithm has been proposed.
A lot of work remains to be undertaken in the direction of a reliable approximation tool, namely the study of the pseudo-stability of approximating CMLs and of their accuracy as well as the relationship between patterns and the computed kernel, which was one the primary goals. Also, global parameters should be estimated on practical experiments and compared to theoretical studies.
I would like to thank Ronan Thomas who performed the image registration.
 |
