Material from IMA Talks

Michael F. Barnsley (Department of Mathematics & Statistics, University of Melbourne)  Mbarnsley@aol.com

Lossless Fractal Compression using IFS

It is shown how the invariant measure of a stationary stochastic process, when it contains no atoms and is fully supported, can sometimes be associated with an IFS with probabilities and with a certain dynamical system. This provides a geometrical approach to the discovery of lossless data compression algorithms such as those that employ the Burrows Wheeler Transform. Fascinating geometrical invariants associated with IFS with probabilities, even when there is no unique invariant measure, are presented and applications to multimedia are proposed.

Jonathan Blackledge (Department of Mathematical Sciences, De Montfort University)   jmb@dmu.ac.uk

On the Statistics of Dimension: Multi-fractals and Fractal Modulation   pdf   postscript

Below is a TeX version

We consider a new approach to modelling a non-stationary or multi-fractal stochastic field $u(x,t)$ using a fractional partial differential equation of (time dependent) order $q(t)$ given by

$$\left [{\partial^{2}\over\partial x^{2}}-\tau^{q(t)}{\partial ^{q(t)} \over \partial t^{q(t)}}\right ]u(x,t)=-F(x,t), \h -\infty < q(t) < \infty ,\h \forall t$$

where $\tau$ is a constant and $F$ and $q$ are stochastic functions. The theoretical background and ideas upon which this equation is based are presented. This includes a brief overview of random fractal walks, L\'evy flights, fractional calculus and fractional dynamics. A general solution to this equation is then considered using a Green's function method from which an asymptotic solution is derived for $x\rightarrow 0$. Numerical algorithms for computing this solution are introduced and results presented to illustrate its characteristics which depend on the random behaviour of $q(t)$. One important and interesting aspect of this approach is concerned with the effect of changing the statistics [i.e. the Probability Density Function (PDF) of $q(t)$] used to \lq drive' the solution. Since $q$ is a dimension (the \lq Fourier dimension' which is related to the fractal dimension), the introduction of a PDF associated with $q(t)$ leads directly to the notion of the \lq statistics of dimension'. \v In the context of $q(t)$ being a random variable, the asymptotic solution for $u(x,t)$ when $x\rightarrow 0$ yields special behaviour when $q=2$. This is characterised by events that are analogous to L\'evy-type flights which we call \lq Brownian transients'. We also address the inverse problem in which a discrete solution is found for $q(t)$ from a known stochastic field $u(x,t)$ when $x\rightarrow 0$. A single application is considered - Fractal Modulation - where $q(t)$ is assigned just two states for all $t$. This approach is analogous to Frequency Modulation but where a bit stream is forced to \lq look like' background fractal noise for applications in (covert) digital (multimedia or otherwise) communication systems.

Jean-luc Dugelay (Multimedia Communications Department, Institut EURECOM)

Fractals in Multimedia Imaging: From Compression to Image Indexing and Watermarking

Fractal compression is a particular form of block-based vector quantization and consists in expressing an image in terms of local self-similarities. But despite a series of optimizations, the elaboration of hybrid schemes, the possible extension to colour and moving pictures, etc., fractal based image compression has never reached the initial expected success. However some notions and properties included in the fractal theory can present a fair potential in some other domains of image processing such as zoom, indexing or also watermarking.

Indeed, the compression inspired by the fractal theory possesses some invariance properties by affine (geometric and photometric) transformations, such as change of scale factor, that can be useful to some applications.

Typically, this representation space is useful when one looks for images, that are globally similar or close to a given image sample, inside an image database, or also when one hides a message inside an image and would like to be able to recover it later in a reliable manner, even if the image has undergone one or several non destructive attacks.

Michael Frame (Department of Mathematics, Union College)

A Web-Based Fractal Geometry Course for Non-science Students

Over a decade of experience at teaching fractal geometry to non-science students, together with an underestimation of the work involved in webpage design, led me to develop a web-based version of this course for the fall 2000 semester. Especially when coupled with a wide range of applications, fractal geometry is an ideal topic for this style of instruction. Yet unanticipated consequences of this modality arose almost immediately. I shall illustrate some of the advantages of a web-based fractal geometry course, demonstrate a few of the surprises, and discuss general aspects of the suitability of fractal geometry as a general education science course.

Raouf Hamzaoui (Department of Informatik, University of Leipzig)

Fast Local Search for Fractal Image Compression

In fractal image compression, the code for a digital image is a representation of a contractive affine mapping whose fixed point is an approximation to the image. The decoding consists of iterating the contractive mapping until convergence to the fixed point. Fractal image compression was introduced by Barnsley and Jacquin in the late eighties. Since then, many researchers have improved the original approach in various ways. Unfortunately, the rate-distortion results of the best fractal coders are still inferior to those of the state-of-the-art in image compression. However, the potential of fractal image compression has not been fully exploited because current fractal schemes do not find optimal codes. Optimal fractal image compression is an NP-hard combinatorial minimization problem where the set of feasible solutions is a large finite set of contractive affine mappings, and the cost function is the error between the original image and the fixed point of one such mapping. Current fractal image schemes are based on a greedy suboptimal algorithm known as collage coding. In this talk, I will present a local search technique that can significantly improve an initial solution found by collage coding. The complexity of local search, which requires successive computations of the fixed point of an affine mapping of a high-dimensional space, is drastically reduced by combining a graph algorithm and a Gauss-Seidel like iterative method.

Material from Talk

Douglas Hardin (Department of Mathematics, Vanderbilt University)

From Fractal Interpolation Functions to Wavelets: The HD Problem for Refinable Functions

Fractal interpolation functions (Barnsley, 1986) are a class of functions with self-affine graphs. Fractal interpolation functions also naturally arise in the study of refinable functions. In fact, refinable functions are piecewise fractal interpolation functions.

In this talk we consider the so-called H-D problem for refinable functions: Given a fractal interpolation function F supported on [0,1], find all refinable functions that can be pieced together from the shifts of F. This is joint work with Tom Hogan.

Lyman P. Hurd (MediaBin, Iterated Systems, Inc.)

A Lagrangian Cost Model for a Fractal Transform Compressor

Classical fractal image compression is at heart a multivariate optimization problem requiring at the least a consideration of rate (filesize) and collage error (distortion). In this paper I will examine the improvements gained by a Lagrangian cost model for the determination of the optimal map for each block, and apply a series of techniques introduced in a previous paper on video compression for the establishment of an optimal partial quadtree of subblocks.

Ning Lu (Advanced Digital Imaging Laboratories, Inc.)

Fractal Techniques in Image Segmentation

The task of image segmentation, similar to the tasks of image compression and image enhancement, is used to be achieved by understanding the characteristics and geometry of images. The more knowledge - in either their frequency distributions or focused subject matters - we can apply, the better results can be achieved.

Extended works in fractal image compression and fractal image enhancement have proven that fractal technique is a unique powerful technique in digital image processing that can achieve very good results without explicitly enumerating knowledge from image science as most nonlinear algorithms found in engineering literature. Nevertheless, nonlinear algorithms are expensive for hardware implementation.

Here we present some further study in fractal image segmentation.

Ken Musgrave (FractalWorlds.com)

Windows on a Parallel Universe: Exploring Fractal Planets

The time has at last arrived when existing, readily accessible technology can provide a window on a parallel universe. This window will initially look out onto a single, highly realistic, random fractal planet. We have the ability to explore this planet in real time, and to image it in non-real time with pixel-sized detail, at unlimited resolution. The dilation symmetry inherent in random fractal models of natural phenomena such as mountains and clouds allows us to implement arbitrary level of detail when imaging a planet built from them. Arbitrary level of detail frees the viewer to roam, to move as close or as far from the planet as desired, without significant aliasing or loss of detail. In early 2001 we will deliver such exploration tools over the Internet in the form of a free "transporter" program and an ~$200 "generator" program for authoring new planets, both of which will run on a fast home computer. The high-dimensional vector of parameter values that completely specifies a given scene constitutes "transporter coordinates" that effectively "beam" the viewer to a given place on a given planet, that "place" being simply a point in the hyperspace of possible parameter values. The realism of these random planets provides a real sense of being there. Each image represents a theorem proved in a formal system; what one is exploring is inherent in the logic that the program embodies. These planets are not built by hand; they exist in the timeless truth of mathematical logic. The planets are not an end in themselves, but rather a context for content, from shopping malls to artificial ecosystems. When the technology matures to the point that the full non-real time realism is available in an immersive, interactive environment we will have cyberspace, the future of the Internet.

Dietmar Saupe (Institut fuer Informatik, Universitaet Leipzig)   saupe@acm.org  saupe@informatik.uni-leipzig.de  http://www.informatik.uni-leipzig.de/cgip/

The State of the Art in Pure Fractal Compression

In "pure" fractal image compression - devised by Barnsley and Jacquin in 1989 - an image is partitioned into blocks each of which being similar to another typically larger block elsewhere in the image. Similarity is taken modulo intensity shift and scaling. The decoder recovers an image approximation from this self-referential description by iteration. A lot of effort has gone into getting the best performance out of this approach, and we will review the main streams of this work. Of particular interest are the optimization of the partition, reduction of the encoding complexity, and attractor coding. Some of our currently ongoing work addresses optimization of error protection for transmission of fractal codes in noisy channels and progressive fractal image coding.

Edward R. Vrscay (Department of Applied Mathematics, University of Waterloo)   ervrscay@links.uwaterloo.ca   http://links.uwaterloo.ca

From Fractal Image Compression to Fractal-based Methods in Mathematics

I shall briefly review some mathematical approaches involving "fractal transforms" and the inverse problem (work with B. Forte) that were inspired by earlier work in fractal image coding. These include (i) the construction of IFS-type operators over various spaces, (ii) the formulation of appropriate inverse problems using contraction maps and (iii) the solution of such inverse problems. (A very recent development in (i) is "IFS over vector-valued measures" which, among other things, can be used to compute line integrals of smooth vector fields over fractal curve attractors of IFS. This is work with Franklin Mendivil, who will describe the method in more detail in a later talk.)

"Fractal-wavelet transforms," an IFS-type operation on wavelet coefficient trees, have the potential to draw from the best of both worlds: 1) the multiresolution framework of wavelets and 2) the scaling property of fractals. There is still hope that the duality of FW transforms can be used to develop both theory and practical coding from the two directions: (i) that IFS theory/methods can be enhanced using the enormous amount of results in wavelet analysis and (ii) that practical wavelet coding methods can be enhanced using fractal-type methods. Some encouraging results have been found and will be reviewed here. There is still a great deal of work to be done.

Finally, IFS-type inverse problems are centered around the idea of approximating a "target" by the fixed point of a contraction mapping. The inverse problem is usually reformulated in terms of the "collage theorem" - finding an operator that sends the target as close to itself as possible. This naturally leads to the question: "Where else in (applied) mathematics can we possibly formulate and use such inverse problems involving contraction mappings?" An obvious place to start was the initial value problem in ODEs, using the Picard integral operator: Given a trajectory or set of trajectories, find the best vector field (work with Herb Kunze, who will describe the method in more detail in a later talk). Indeed, such "parameter identification problems" have been of great interest in a number of areas, e.g. kinetics and population dynamics, and the collage method rigorously justifies the various heuristic solutions/algorithms that have been devised over the years. This indeed serves as an inspiration to look at other fields of mathematics and science, either fractal or nonfractal in nature.

Material from IMA Talks

Minisymposium: Fractals in Multimedia

2000-2001 Program: Mathematics in Multimedia