Talk
Abstracts:
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
|
