Iterated Function Systems

[Crucifixio]

Hello everybody,
This this my first time I'm writing on this forum, I've got problem which I can't manage myself, namly I'm writing program about Iterated Function System in which user can set parameters for transformation (contraction) - create his own fractals, generate them and calculate Minkowski dimension. The problem I'm fighting with is how to check affine transformation for contraction (arbitrary) - I don't know which metric to use.
My contraction transformation looks like
|a   b|    |e|
|c   d| + |f |
plus one parameter for probability.

BTW. If there any solution to automatic set probablity to contraction function to work ??
Any help would be very helpfull.

[cKleinhuis]

hello there, you can use the determinant of the matrix to check if it is contractous or not, if i understood you right ... 

[David Makin]

If you mean "How do I calculate the probababilities from the scales ?" then the answer is given by:

log(p0)/log(s0)=log(p1)/log(s1)=log(p2)/log(s2)=....=log(pn)/log(sn)=constant
and
p0+p1+p2+p3+...+pn = 1

The above lead to:
P0+P0^(log(S1)/log(S0))+P0^(log(S2)/log(S0))+....+P0^(log(Sn)/log(S0))=1.0

where p1 to pn are the probabilities and s1 to sn are the scales. This only works provided that all scales are contractive and non-zero - and obviously all transforms are purely affine.
Also "constant" in the above gives the fractal dimension.

[Crucifixio]

Trifox - simple matrix determinant check will tell me that this transformation is contraction ?? If Det > 0 than it's contraction.

[Crucifixio]

David Makin,
In your formula scales s0...sn are which parameters of transformation matrix ??

[cKleinhuis]

the determinant gives you the scale change of the transformation

1= no change

0 = object is scaled to zero

-1 = object is mirrored around center

0.5 = object is scaled halve

remember that you only take the 2x2 part of the 2x3 matrix, the translation part has no affect on the scale
|a   b|    |e|
|c   d| + |f |

[David Makin]

The s0 to sn are the scales, normally the values of the 2*2 determinant for 2D fractals or the 3*3 determinant for 3D fractals.
As Trifox stated you get contraction when abs(determinant) is >0 and <1.

[David Makin]

I should add:

1. Use the absolute scales.

2. that you can solve:

P0+P0^(log(S1)/log(S0))+P0^(log(S2)/log(S0))+....+P0^(log(Sn)/log(S0))=1.0

using a binary search if you take s0 as the largest scale.

[Crucifixio]

Thanks very much guys, when I finish I will post my program on to this forum.

[cKleinhuis]

Thanks very much guys, when I finish I will post my program on to this forum.

i do hope so !

 

[Crucifixio]

One more question log function is log₁₀ or log_n

[David Makin]

Because the calculation involves log(a)/log(b) it doesn't matter what the log base is as long as you use the same base for log(a) as log(b)

[Ross Hilbert]

Here is what I use. Start from the bottom and work up.
Hope this helps.
Ross


'
' Define Affine object.
'
Object Affine { A : B : C : D : E : F }
'
' Normalize the count values in weights[].
' On return, the values will all be between 0 and 1
' and the sum of all values will equal 1.
'
void Math.NormalizeWeights(weights[], count) {
  sum = 0
 
  for (idx = 0, idx < count, idx += 1) {
    sum += weights[idx]
  }
  for (idx = 0, idx < count, idx += 1) {
    weights[idx] /= sum
  }
}
'
' Return the determinate of an affine transformation matrix.
'
Complex Affine.Determinate(Affine a) = a.A*a.D - a.B*a.C
'
' Affine.TransformPoint applies an affine transformation
' matrix to a point z and returns the resulting point.
'
' A B E     z.X     A*z.X + B*z.Y + E
' C D F  *  z.Y  =  C*z.X + D*z.Y + F
' 0 0 1     1       1
'
Complex Affine.TransformPoint(Affine a, z) {
  return Complex( \
    a.A*z.x + a.B*z.y + a.E, \
    a.C*z.x + a.D*z.y + a.F  \
  )
}
'
' Generate a random contraction map.
'
' To be a contraction map, the affine transformation
' coefficients must satisfy the following conditions:
'
'   a^2 + c^2 < 1
'   b^2 + d^2 < 1
'   a^2 + b^2 + c^2 + d^2 < 1 + (a*d - c*b)^2
'
Affine Affine.RandomContractionMap(center, radius) {
  while (True) {
    a = Random.NumberInRange(-1, 1)
    w = Sqrt(1 - a^2)
    c = Random.NumberInRange(-w, w)
   
    b = Random.NumberInRange(-1, 1)
    w = Sqrt(1 - b^2)
    d = Random.NumberInRange(-w, w)
 
    if (a^2 + b^2 + c^2 + d^2 < 1 + (a*d - c*b)^2) {
      break
    }
  }
  e = center.x + Random.NumberInRange(-radius, radius)
  f = center.y + Random.NumberInRange(-radius, radius)
 
  return Affine(a, b, c, d, e, f)
}
'
' Initialize weights w[] using the weighted average of
' the absolute value of the determinates of the affine
' transformations in s[].
'
' For a discussion of the following algorithm, see:
'   "Chaos and Fractals"
' by Peitgen, Jurgens, Saupe, Section 6.3 pages 327-329.
'
void Affine.InitializeWeights(Affine s[], w[], count) {
  for (idx = 0, idx < count, idx += 1) {
    w[idx] = Max(0.01, Abs(Affine.Determinate(s[idx])))
  }
  Math.NormalizeWeights(w[], count)
}
'
' N is the number of Affine transformations.
' s[N] are the Affine transformations.
' w[N] are the weights.
'
Complex w[N]
Affine s[N]

for (idx = 0, idx < N, idx += 1) {
  s[idx] = Affine.RandomContractionMap(0, 1)
}
Affine.InitializeWeights(s[], w[], N)

[David Makin]

Hi,

Just to say that using the "log(Pi)/log(Si)=constant" method provides more accurate results than the method from "Chaos and Fractals" (I verified this by using both methods for the probablilities on many fractals and found that when the scales are not uniform this method was noticeably better at filling the gaps evenly).

The proof of the method can be found in:
"A Multifractal Analysis of IFSP Invariant Measures With Application to Fractal Image Generation"
by J.M.Gutiérrez, A.Iglesias and M.A. Rodríguez.

The document was formerly available on the web as fractals96.pdf

[Ross Hilbert]

Thanks David,

I found the document you referenced and I'll give it a read.
Looks good, thanks again!

Ross