Waterloo Fractal Coding and Analysis Page. -------

Waterloo Fractal Coding and Analysis Group

(formerly known as the "Waterloo Fractal Compression Project")

-------

Under construction as of 12 July 2007

Introduction

The Waterloo Fractal Coding and Analysis Group (which originated from the "Waterloo Fractal Compression Project" that used to be located at this website) is comprised of five researchers who have been interested in various aspects of fractal analysis including: iterated function systems, fractal image coding, generalized fractal transforms and the inverse problem of approximation using fixed points of contraction mappings. The "fractalators" of this group are

The first four "fractalators" listed above are pictured below. This photo was taken during an "IFS brainstorming session" at Waterloo in 2006:

Ed Vrscay, Herb Kunze, Davide La Torre, Franklin Mendivil, Ed Vrscay, Herb Kunze .... (Photo and graphical effects courtesy of Franklin Mendivil)

For a brief history of the Waterloo Fractal Compression Project and its evolution to our present group, please click here

What are Iterated Function Systems? What is fractal image coding?

Iterated Function Systems (IFS)

IFS is the term originally devised by Michael Barnsley and Steven Demko [1] for a collection of contraction mappings over a complete metric space, typically compact subsets of R^n. Systems of contraction mappings had been considered previously by a number authors for various purposes. But the landmark papers of John Hutchinson [2] and, independently, Barnsley and Demko [1] showed how such systems of mappings with associated probabilities could be used to construct fractal sets and measures: the former from a geometric measure theory setting and the latter from a probabilistic setting. For those who are not familiar with IFS, we'll provide a simple discussion and example a little later in this section.

Just as important, however, was the fact that the Barnsley/Demko paper was the first to suggest that IFS could be used to approximate natural objects. This was the seed of the inverse problem of fractal approximation: Given a "target" set, S, for example, a leaf, can we find an IFS with attractor A (see below) that approximates S to a reasonable degree.

In a subsequent paper, Barnsley and students [3] showed how the inverse problem of fractal approximation was could be reformulated by means of the infamous "Collage Theorem": instead of trying to find an IFS whose attractor A would match the target S (a very tedious and difficult problem), one can look for an IFS that maps A as close as possible to itself. More on this later.

Fractal image coding

After [3], the next natural question was: "Can we use IFS to approximate images?" The seminal paper [4] by A. Jacquin, then a Ph.D. student of Barnsley at Georgia Tech, provided the basis of block-based fractal image coding which is still used today. Jacquin's paper launched an intensive activity in fractal image compression [5-7]. Indeed, in the meantime, Barnsley left Georgia Tech to found the company Iterated Systems which was dedicated to the commercialization of fractal image compression.

In fractal image coding, one tries again to approximate a "target" image y with the fixed point x' of a contractive fractal transform T. In general, however, this direct inverse problem is difficult because of the complex nature of the fractal transform, which maps modified subimages onto other regions. A great simplification is afforded by the Collage Theorem of Ref. [3] above. In collage coding, one looks for a transform T that minimizes the so-called collage distance d(y,Ty). Most, if not all, fractal image coding methods rely on collage coding.

Very briefly, block-based fractal image coding is a "local IFS" procedure. Given an image I, one typically seeks to approximate its subimages on n x n range subblocks R_i with contracted (i.e., decimated) and greyscale-modified subimages on 2n x 2n domain subblocks D_j. For each range block, one searches for the best domain block D_i from a domain pool. The larger the domain pool, the better opportunity for a good approximation, but at the expense of higher search times.

Below is an example of fractal image coding as applied to the infamous Lena image:

Fractal compression methods were actually quite competitive until the appearance of powerful wavelet-based methods and, subsequently, context-based coders. Nevertheless, it has always been the philosophy of the Waterloo research programme that fractal-based methods are interesting mathematically and that they may also be able to provide useful information about images. We are indeed finding that there is much "life after compression".

A simple introduction to IFS

Suppose that w : X -> X is a contraction mapping of a complete metric space (X,d) to itself. Then, by the celebrated Banach Fixed Point Theorem, there is a unique point x' in X such that w(x') = x', the fixed point of w. Moreover, for any starting point x_0 in X, the sequence of points {x_n} defined by the iteration procedure x_{n+1}=w(x_n) converges to x' as n -> infinity. In other words, x' is an attractive fixed point .

Now suppose that we have more than one contraction mapping on X, i.e. w_i : X -> X, i=1,...N. Each of these maps w_i will have its own fixed point x'_i. And, of course, if we apply only one of these maps repeatedly, say w_P, then the iteration sequence {x_n} will converge to its fixed point x'_P. But what happens if you pick the maps at random? Clearly, each map will be fighting to bring the sequence to its own fixed point!

Assuming that you pick each map w_i with a nonzero probability p_i (sum of p_i = 1), the sequence will eventually approach a unique set, the "attractor" A of the "iterated function system" W = {w_1, ... , w_N}, performing a random walk over it (or at least getting nearer and nearer to it). The probabilities will play a role in determining how often various regions of the attractor are visited.

    Examples on [0,1]:

  1. w_1(x) = x/3, w_2(x) = x/3 + 2/3. Note that w_1(0)=0 and w_2(1)=1. Then the attractor of this IFS is the classical Cantor set on [0,1].

  2. w_1(x) = x/2, w_2(x) = x/2 + 1/2. Note again that w_1(0)=0 and w_2(1)=1. Then the attractor of this IFS is the interval [0,1]. If p_1 = p_2 = 1/2, then the distribution of the random-walking iterates {x_n} over the interval [0,1] is uniform. If p_1 > p_2, then there is more probability of finding the iterates in the interval [0,1/2] than in [1/2,1]. But this means that there will be more probability of finding them in [0,1/4] vs. [1/4,1/2] and more in [1/2,3/4] than [3/4,1], and so on. The result is that the visitation frequencies over small sets demonstrate a complicated fractal-like pattern.

    An example in [0,1] X [0,1]:

  3. w_1(x,y)=(x/2,y/2), w_2(x,y)=(x/2+1/2,y/2), w_3(x,y)=(x/2,y/2+1/2). The fixed points of these maps are, respectively, (0,0), (1,0) and (0,1). The attractor of this IFS is a "rectangular" Sierpinski gasket with corners at these fixed points.

    Note: Let us go back to Franklin Mendvil's beautiful montage of photos presented above. Starting at the upper left photo (which could be considered as the "seed" set), if you scan left-to-right and then move down and scan left-to-right again, you have the first six "sets" that are approaching this "rectangular" Sierpinski gasket.

For a little more discussion on this subject, along with a quite readable introduction to fractal image coding, you may wish to look at E.R. Vrscay's Hitchhiker's Guide to Fractal Image Compression. It was written for a general audience with some undergraduate mathematical knowledge. Ref. [8] below is also a very nice and readable discussion of fractal image coding.

References

  1. M.F. Barnsley and S. Demko, Iterated function systems and the global construction of fractals, Proc. Roy. Soc. London A399, 243-275 (1985).
  2. J. Hutchinson, Fractals and self-similarity, Indiana Univ. J. Math. 30, 713-747 (1981).
  3. M.F. Barnsley, V. Ervin, D. Hardin and J. Lancaster, Solution of an inverse problem for fractals and other sets, Proc. Nat. Acad. Sci. USA 83, 1975-1977 (1985).
  4. A. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans. Image Proc. 1, 18-30 (1992).
  5. M.F. Barnsley and L.P. Hurd, Fractal Image Compression, A.K. Peters, Wellesley, Mass. (1993).
  6. Y. Fisher, Fractal Image Compression, Theory and Application, Springer-Verlag, New York (1995).
  7. N. Lu, Fractal Imaging, Academic Press, New York (1997).
  8. Y. Fisher, A discussion of fractal image compression, in Chaos and Fractals, New Frontiers of Science, H.-O. Peitgen, H. Jurgens and D. Saupe, Springer-Verlag, Heidelberg (1994).

Summary of research: past and recent

As stated earlier, it has been the philosophy of the Waterloo research programme that fractal-based methods are interesting mathematically and that they may also be able to provide useful information about images.

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: