Past Progress (19902000)
Generalized fractal transforms and associated inverse problems,
fractal image coding, Solving other
inverse problems in mathematics using "collage coding"
The most popular "fractalbased" algorithms for both the representation
representation as well as the compression of computer images have
involved some implementation of the method of Iterated Function Systems
(IFS) on complete metric spaces, e.g. IFS with probabilities (IFSP),
Iterated Fuzzy Set Systems (IFZS), Fractal Transforms (FT), the
Bath Fractal Transform (BFT) and IFS with greylevel maps (IFSM).
(FT and BFT are special cases of IFSM.) The "IFS component" of these
methods is a set of N contraction maps {w_1, w_2,...,w_N}, w_i : X > X,
over a complete metric space (X,d), the "base space" which represents
the computer screen.
The major developments of the research at Waterloo up to roughly 2000 were:
 The formulation of a consistent mathematical theory of Generalized
Fractal Transforms over a suitable complete metric space
(Y,d_Y) which could represent our space of images. This involves
the determination of a suitable fractal transform operator T
which will map images to images. A set of rules for constructing
such IFStype operators is formulated including the condition
that T be contractive with respect to the metric d_Y.
(In a "nonrigorous nutshell", a GFT seeks to express a mathematical
object  e.g., set, function, measure 
as a union of spatially contracted and range valuedistorted
copies of itself.)
 The above procedure led to a unification of the various IFStype
methods over function spaces: IFS > IFZS > IFSM.
 The IFStype methods over function spaces were linked with the
method of IFSP (over probability measures) by a formulation of fractal
transforms over D'(X), the space of distributions on X.
 The mathematical basis of the discrete fractalwavelet transform
where subtrees of wavelet coefficient trees are scaled and copied
to lower subtrees. In general, fractalwavelet transforms are
equivalent to recurrent local IFSM with condensation functions.
 Posing formal inverse problems of approximation of
functions, measures, etc. using IFStype methods. By "formal
inverse problem", we mean that the approximation of a "target"
function/measure/image may be produced to arbitary accuracy.
 Solutions to the various formal inverse problems as well as algorithms
to achieve approximations to arbitrary accuracy.
 Fractal transforms induced by IFSP/IFSM operators. Given a fractal
transform operator T : Y > Y and a faithful representation
Z = phi(Y), where phi is onetoone, then find the operator S : Z > Z
induced by T. Noteworthy examples include:
 Let Y be the space of probability measures on X. Let T : Y > Y be the
Markov operator on Y associated with an Nmap IFSP defined on X.
Now let Z be the infinite sequence space {g_n} of moments of measures
in Y. Associated with T is a mapping S on these moments.
 Let Y be the space L^1(X) and let T : Y > Y be the IFSM operator
on Y associated with an Nmap IFSM defined on X.
Let Z be the space of Fourier transforms of functions in Y. Associated
with T is a mapping S on Fourier transforms.
 Let Y be the space L^2(X) and let T: Y > Y be the IFSM operator
on Y associated with an Nmap IFSM defined on X.
Let Z be a space of orthogonal wavelets obtained by multiresolution
(e.g., dyadic refinement). Associated with T is a mapping S on
wavelet coefficient trees. In the special case the the IFSM maps
are dyadic and the wavelets are nonoverlapping Haar wavelets, then
S scales subtrees and copies them onto lower subtrees as well as placing a
"condensation" tree at the top  what is known as the
fractalwavelet transform.
We may then wish to solve inverse problems in these other representations.
For example, we have shown that a collage theorem for moments can
be used to solve inverse problems for approximation of probability measures.
Much of the above is summarized in the following paper:
More details of the various methods are provided in the following papers:

B. Forte and E.R. Vrscay,
Theory of Generalized Fractal Transforms,
in Fractal Image Encoding and Analysis, edited by Y.
Fisher (Springer Verlag, Heidelberg, 1998).

B. Forte and E.R. Vrscay,
Inverse Problem Methods for Generalized Fractal Transforms,
in Fractal Image Encoding and Analysis, ibid.

B. Forte, F. Mendivil and E.R. Vrscay (1999),
IFSType Operators on Integral Transforms, in
Fractals: Theory and Applications
in Engineering,
edited by M. Dekking, J. LevyVehel, E. Lutton and C. Tricot
(Springer Verlag, London),
pp. 125138 (1999).

B. Forte and E.R. Vrscay,
Solving the inverse problem for measures using iterated function systems:
A new approach, Adv. Appl. Prob., 27, 800820 (1995).

B. Forte and E.R. Vrscay,
Solving the inverse problem for function and image approximation
using iterated function systems
Dyn. Cont. Disc. Imp. Sys. 1, 177231 (1995).

C.A. Cabrelli, B. Forte, U.M. Molter and E.R. Vrscay,
Iterated Fuzzy Set Systems: A New Approach to the Inverse
Problem for Fractals and Other Sets,
J. Math. Anal. Appl. 171, 79100 (1992).

We reverse the procedure involving wavelets and define an IFSW
operator W (IFS on wavelets) or fractalwavelet transform
on wavelet coefficient trees that maps scaled
copies of subtrees onto lower subtrees. The mapping W induces a mapping T
in the spatial domain which is equivalent to a local IFSM operator with
condensation functions:
We have used such 1D fractalwavelet transforms
for audio compression:
We have also shown hown 2D fractalwavelet transforms can
be used in image coding and compression:

Investigating the suboptimality of "collage coding"
Collage coding is a "greedy algorithm," hence suboptimal. We
have investigated this suboptimality for some simple fractal coding
problems in:

Using "collage coding" to solve other inverse problems in applied mathematics:
We have been looking at other (not necessarily fractal) applications of
collage coding, i.e., inverse problems in applied mathematics that may
be formulated in terms of the approximation of a "target" by the fixed
point of a contractive map. We first successfully applied "collage coding"
to the inverse problem of ODEs: Given a "target" curve x(t) in R^n (or set
of curves) , possibly determined
by data points, find the "best" vector field f(x) (from a prescribed class
of functions, e.g., polynomials) for which the target is an approximate
solution to the initial value problem
dx/dt = f(x), x(0)=x_0. This is done by means of the
Picard integral operator T associated with the IVP. We look for a T
(which is defined by the vector field f) such that
the "collage distance" d(x,Tx) is made as small as possible.
This problem is very important in the context of parameter
identification in biological models, chemical kinetics, compartmental models.
As mentioned above,
collage coding is suboptimal. More recently, we have
investigated this suboptimality for the ODEs problem in:

A simple proof of the ergodicity of the IFSP "chaos game"
J. Elton originally proved that the "chaos game" for an IFS with probabilities
was ergodic. Here, we use the additional fact that the invariant measure is
unique to provide a simpler proof:

B. Forte and F. Mendivil,
A classical ergodic property for IFS: A simple proof,
Ergodic Theory and Dynamical Systems 18, xxxx (1998).
(Note: This is the original manuscript. The year "2000" appears
in it because the file was regenerated from the original source file that year.)