From: hfvb@sunvax.sun.ac.za (Hendrik Boshoff)
Newsgroups: sci.math,alt.fractals
Subject: Re: Fractal Interpolation
Date: 8 Apr 92 18:57:33 +0200
Distribution: sci
Organization: E&E Eng, University Stellenbosch

In article <BURTLE.92Mar30225446@penda.cs.odu.edu>, 
    burtle@penda.cs.odu.edu (William J Burtle) writes:
> I tried a similar post on alt.fractals, and got no response, so
> I'll try it here:
> 
> I am looking for some help with fractal interpolation.  We would
> like to use the Hidden-Variable method in Chapter 6 of Barnsley's 
> _Fractals Everywhere_.  We are having problems understanding what
> these hidden variables are, i.e., where do they come from?  We
> would like to have the same IFS produced reliably from the same
> set of data points each time.  Any help with fractal interpolation
> methods will be greatly appreciated.
> 
> Thanks,
> 	Bill Burtle
> 
> --
> 
>    |-------------------------------------------------------------|
>    |  William Burtle                "Ohne Hast, aber ohne Rast." |
>    |  Old Dominion University        (Without haste, but without |
>    |  burtle@cs.odu.edu                  rest).  - Goethe        |
>    |-------------------------------------------------------------|
 
I assume you are at ease with ordinary fractal interpolation, in which you
have the vertical scaling factors (d_i) as free parameters. All the others
(a,b,c,e,f) are fixed by the data and the assumption that you want an
attractor which will be a continuous function. So even here, the d's do
not come from somewhere, and any value would be consistent with the data
to be interpolated.

The aim of coding could be efficiency, then one would like to drop lots of
data points and send only enough across to allow you to reconstruct
the initial data faithfully by interpolation. Coding then becomes an 
optimization in which d's must be found to best interpolate between
sparsely chosen points, in a way that will approximate the left out data.

The problem is then not only to find d's, but to choose the best points
to be interpolated.

In the case of hidden variable interpolation, the attractor is made
three-dimensional, in such a way that its projection onto two planes
will be continuous functions.

What is gained by this, is more degrees of freedom. Only self-affine
functions can be accurately given by IFS attractors. The _projection_
of these need not be self-affine though.

The price is a higher data rate, and a much more complicated
simultaneous optimization of 4*N parameters instead of N.

What you need to do now, is to choose the best interpolation points,
along with four "hidden variables" for each point, in such a way that
the interpolation yields something like your original function in between.

An error function has to be defined, and an optimization algorithm. If
you keep these fixed, and stick to the same error limits, the same IFS
will be reliably produced.

Depending on your skill, this reliable IFS may be a good or a bad
approximation to the data.

It is not at all clear how the hidden variables should be determined.
In the ordinary interpolation case, the Collage Theorem supplies clues
to values of d. What you need for the hidden case, is an inverse
pojection, which goes from your 2D data to a 3D data set that is
self-similar.

You could of course implement an exhaustive search through some
discretization of the parameter space, and wait the age of the universe
for an optimal result.

A better approach may be to get the best ordinary interpolation fit, and
then allow the hidden variables as a perturbation. This could trap you
in a local minimum, but I expect it to converge at least. It must be
determined if the improvement gained in this way justifies the added data.

David S Mazel finished his PhD at Georgia Tech in June 1991, with the title
"Fractal Modeling of Time-Series Data." In it he describes the application
of inter alia hidden variable interpolation. In his scheme, he fixes the
three dimensional attractor by putting his data in both allowed projections.
To my mind this approach sacrifices the added degrees of freedom, virtually
guarantees that the 3D attractor will not be self-similar, and still needs
4 parameters for each data point. His exposition is lucid however, and he
presents lots of examples, so I recommend your getting a copy.

A more accessible (and compact) report is his presentation at ICASSP '91,
in the Proceedings, Vol 5 pp 3393-3396, titled "Hidden-Variable Fractal
Interpolation of Discrete Sequences."

Hope this helps.

Hendrik

#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#
+                         Hendrik F.V. Boshoff                              +
#    Dept E&E Ingenieurswese             Dept E&E Engineering               #
+    Universiteit van Stellenbosch       University of Stellenbosch         +
#    SUID-AFRIKA                         SOUTH AFRICA                       #
+                      email boshoff@firga.sun.ac.za                        +
#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#+#

Xref: sparky sci.math:5987 alt.irc:1357