Past Progress (1990-2000)

Generalized fractal transforms and associated inverse problems, fractal image coding, Solving other inverse problems in mathematics using "collage coding"

The most popular "fractal-based" 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 grey-level 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 IFS-type 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 value-distorted copies of itself.)
• The above procedure led to a unification of the various IFS-type methods over function spaces: IFS -> IFZS -> IFSM.
• The IFS-type 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 fractal-wavelet transform where subtrees of wavelet coefficient trees are scaled and copied to lower subtrees. In general, fractal-wavelet transforms are equivalent to recurrent local IFSM with condensation functions.
• Posing formal inverse problems of approximation of functions, measures, etc. using IFS-type 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 one-to-one, 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 N-map 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 N-map 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 N-map 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 fractal-wavelet 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:

  • E.R. Vrscay, From Fractal Image Compression to Fractal-Based Methods in Mathematics, in Fractals in Multimedia, edited by M.F. Barnsley, D. Saupe and E.R. Vrscay (Springer-Verlag, New York, 2002).
  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), IFS-Type Operators on Integral Transforms, in Fractals: Theory and Applications in Engineering, edited by M. Dekking, J. Levy-Vehel, E. Lutton and C. Tricot (Springer Verlag, London), pp. 125-138 (1999).
  • B. Forte and E.R. Vrscay, Solving the inverse problem for measures using iterated function systems: A new approach, Adv. Appl. Prob., 27, 800-820 (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, 177-231 (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, 79-100 (1992).

• We reverse the procedure involving wavelets and define an IFSW operator W (IFS on wavelets) or fractal-wavelet 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:
  • F. Mendivil and E.R. Vrscay, Correspondence Between Fractal-Wavelet Transforms and Iterated Function Systems With Grey-Level Maps, in Fractals in Engineering: From Theory to Industrial Applications,, edited by J. Levy Vehel, E. Lutton and C. Tricot (Springer Verlag, London, 1997).
  We have used such 1D fractal-wavelet transforms for audio compression:
  • R.A. Wannamaker and E.R. Vrscay, Fractal Wavelet Compression of Audio Signals, J. Audio Engineering Society, Vol. 45, Nos. 7-8, pp. 540-553 (1997).
  We have also shown hown 2D fractal-wavelet transforms can be used in image coding and compression:
  • E.R. Vrscay, A Generalized Class of Fractal-Wavelet Transforms for Image Representation and Compression, Canadian Journal of Electrical and Computer Engineering, Vol. 23, Nos. 1-2, pp. 69-83 (1998).

• 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:
  • E.R. Vrscay and D. Saupe Can One Break the "Collage Barrier" in Fractal Image Coding?" in Fractals: Theory and Applications in Engineering, edited by M. Dekking, J. Levy-Vehel, E. Lutton and C. Tricot, (Springer Verlag, London) pp. 307-323 (1999).

• 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.
  • H.E. Kunze and E.R. Vrscay, Solving Inverse Problems for ODEs Using the Picard Contraction Mapping , Inverse Problems 15, 745-770 (1999).
  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:
  • H. Kunze, J. Hicken and E.R. Vrscay, Inverse problems for ODEs using contraction maps: Suboptimality of the `Collage Method', Inverse Problems 20, 977-991 (2004).

• 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, xx-xx (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.)