Standard
choice.
This paper focus on invariant measures arising from Iterated Function System with Probabilities (IFSP). We show the equivalence between an IFSP and a linear dynamical system driven by a white noise. Then, we use a multifractal analysis to obtain scaling properties of the resulting invariant measures, working in the framework of dynamical systems. Finally, as an application to fractal image generation, we show how this analysis can be used to obtain the most efficient choice for the probabilities to render the attractor of an IFS by applying the probabilistic algorithm known as ``chaos game".
An IFSP can be seen as a random dynamical system. We first introduce a discrete stochastic process formed by a sequence of i.i.d. random variables, z(n), n=1,2,3,..., which can take values in the set {1, ..., N} with probability distribution P(z(n) = j) = pj, n=1,2,3,..., where pi are the probabilities of the IFSP. The probability measure, P, associated with this white process can be determined by defining the joint probabilities P(z(1), z(2), ...). These joint probabilities factorize as:
Once the process has been defined we can proceed to formulate the stochastic equations of motion. The random dynamical system equivalent to the IFSP is governed by the stochastic equation:
where w(n) are the contractive applications of the IFSP and z(n) is the stochastic process defined above. Some equivalences between the IFSP and the random process are evident. For instance, the stochastic orbit {x(n), n=0, 1, ...} is equivalent to the sequence obtained from the IFSP applying the "chaos game" algorithm to x(0).
Given a set {p1, ..., pN}, there exists an unique Borel regular measure m, called the invariant measure of the IFSP, such that
for any Borel subset of X, S.
The term multifractal is applied when many fractal subsets with different scaling properties coexist simultaneously. In this sense, the invariant measure, m, generated by an IFSP has a multifractal character. Using the framework of dynamical systems above introduced, this paper shows that the singularities of this invariant measure are of the form:
where a(x1, ..., xn) is the singularity containing the points of the attractor that have an address containing symbol i with relative frequency xi. The Hausdorff dimension of a singularity a(x1, ..., xn) can be obtained as
This characterizes the multifractal properties of the IFS.
Regarding the problem of the choice of probabilities for generating the fractal attractor of an IFS applying the "chaos game", the standard criterion for this choice is the proportionality with respect to the contractive factor (see, for example, M. F. Barnsley (1990) "Fractals Everywhere", Academic Press, pag. 85). The efficiency of this algorithm to render the attractor of an IFS using a set of probabilities {p1,...,pN} can be related to the spectrum of singularities of the multifractal measure associated with the corresponding IFSP. Thus, we use the multifractal analysis introduced in this paper to obtain the most efficient choice of the probabilities.
For example, the fern IFS given by the applications
w1(x,y)=(0.81x+0.07y+0.12,-0.04x+0.84y+0.195),
w2(x,y)=(0.18x-0.25y+0.12,0.27x+0.23y+0.02),
w3(x,y)=(0.19x+0.275y+0.16,0.238x-0.14y+0.12),
w4(x,y)=0.0235x+0.087y+0.11,0.045x+0.1666y).
The figures below show the fractal images generated by the "chaos game" algorithm using the standard probabilities (p1=0.753, p2=0.123, p3=0.104, p4=0.020)
Standard
choice.
and the probabilities obtained based on the multifractal structure of the resulting IFSP (p1=0.701, p2=0.150, p3=0.129, p4=0.020).
Our
proposal.
In both cases the same number of iterations is performed.
The difference can be established visually.