Talk:Iterated function system: Difference between revisions

Revision as of 22:40, 15 July 2008

Latest revision as of 17:06, 15 February 2024

(44 intermediate revisions by 21 users not shown)

Line 1:

{{talkheader}}

{{Sys rating|class=B|importance=high|field=Chaos theory}}

{{WikiProject banner shell|class=B|

{{WikiProject Systems|importance=high|field=Chaos theory}}

{{WikiProject Mathematics|class=C|importance=mid}}

}}

{{archive box|auto=yes}}

==Equivalent constructions==

== Ferns ==

There might be something unclear in the construction paragraph:

Does anyone know where the values in the fern IFS come from? For example, the map to draw the stalk is rather counterintuitive, because it seems to draw along the y-axis, whereas the actual stalk itself is made up of several segments increasing in their x-values. How would you go about deriving the values in the IFS (0.16 etc) if you didn't already know them, and what relations exist between them (e.g. if you changed one, how would you need to change the others to keep the fern "together")? I know Barnsley's Collage Theorem may be involved, but I'm not sure to what extent. [[User:Kidburla2002|Kidburla2002]] 00:04, 11 May 2007 (UTC)

''The most common algorithm to compute IFS fractals is called the chaos game. It consists of picking a random point in the plane, then iteratively applying one of the functions chosen at random from the function system and drawing the point. An alternative algorithm is to generate each possible sequence of functions up to a given maximum length, and then to plot the results of applying each of these sequences of functions to an initial point or shape.''

I agreee, that's why i propose replacing it with the much simpler spiral at the bottom of this page. This IFS has simpler equations and fewer transforms, and the illustration includes several steps. The fern example is good for showing how complex natural shapes can be reduced to IFS, not for understanding IFS. [[User:Spot|Spot]] 19:24, 18 August 2007 (UTC)

== Edit War ==

Is this a correct rendition of the two methods? Method 1 as described here takes an initial point, applies a randomly chosen transformation, plots the resulting point and applies a randomly chosen transformation on that point again. Method 2 as described here do effectively the same sequence of transformations but only plots the last point. Method 2 is then just Method 1 throwing away most of the plot.

We seem to have an edit war with Hristos, who repeatedly inserts a link to this external web page [http://illusions.hu/ IFS Illusions]. TheRingess, Gandalf61 and I keep removing it. To me the link appears to be a BSP to a non-free derivative work that does not credit its sources. Hristos, can you please explain here why you think this link belongs on this page? thanks, [[User:Spot|Spot]] 19:47, 10 March 2007 (UTC)

I might be showcasing my ignorance here, but in the chaos game (method 1), we have, intuitively, a point that is jumping around and never settles. Perhaps, we're trying to say that method 2 relies on function sequences such as f1(f2(f1(f3(f2(...('''X''')....))) where f1,f2,f3 are contractive mappings and that each such sequence have any point '''X''' converging on a specific fixed point. This sounds like it would rely on the [[Banach fixed point theorem]] but the chaos game seems to show that even though contractive mappings converge to a point, iterative application of different contractive mappings does not necessarily do the same.

:Hi! I'm the author of IFS Illusions. Can you tell me why you and TheRingess keep saying that this software is non-free? Have you tried to download it? Thanks. Simzer. 2007.05.25

So in short, I'm not sure what method 2 is supposed to be :-) [[User:EverGreg|EverGreg]] ([[User talk:EverGreg|talk]]) 13:54, 23 October 2009 (UTC)

:May I answer instead of Hristos? There were two reasons why we thought that the link belongs to this page.

:1. There were a branch of IFS generator among the external links. Interesting detail, that when TheRingess removed the link of IFS Illusions with apostrophising it to non-free software incorrectly there were real non-free softwares in the list constantly unremoved.

:2. We thought that the readers maybe interest to our software and our gallery. Now I see, that this is not the potent which forms this article.

:Simzer 2007.05.28

:The paper "fractals, graphs and fields" by Franklin Mendivil [http://mathdl.maa.org/mathDL/22/?pa=content&sa=viewDocument&nodeId=3128] explained the two methods and their equivalence very well. Recommended if there's others out there getting confused. :-) The construction paragraph seems correct, though it leaves out a lot of detail. [[User:EverGreg|EverGreg]] ([[User talk:EverGreg|talk]]) 19:40, 26 December 2009 (UTC)

IFS Illusions does not come with source code and its use is restricted to noncommercial, so it is not free.

The reason I removed the link and left Xenodream (the other commercial link) because it was there as long as i can remember and at least offers something unique whereas IFS Illusions appears derivative of Apophysis/FLAM3. The Xenodream link is now gone too. [[User:Spot|Spot]] 23:22, 29 May 2007 (UTC)

to EverGreg:

:A software is open source if there is a community, which develope it. It is not condition of free. Anyway why would be IFS Illusions open source? I developed it myself and nobody have offered his help to improve it and asked the source yet. Restriction of usage to noncommercial isn’t condition of free too. Just for your guidance: IFS Illusions is [http://en.wikipedia.org/wiki/Freeware freeware], and freeware doesn't meant non-free.

"Method 2 as described here do effectively the same sequence of transformations but only plots the last point."

There's a subtlety in method 2. Note that it doesn't say "generate a sequence of transformations". It says "generate EACH POSSIBLE sequence of transformations" (implication: from a known starting point in space.)

:That you think IFS Illusions is a derivate of Apophysis proofs that you don’t adept on IFSs. Yes, my software render iterated function systems too. There are just some little difference. For example: different function types and coloring model used, and a branch of attribute of rendering developed, etc. The user interface is also not like Apophysis as i haven’t seen it before I had made the software. And yes, there was ideas get from Flames like conform functions, but that is not the main functionality of the software.

If you have 3 transformations and you want sequences of length 10, you have 3^10 possible sequences of transformations. Given a common (arbitrary) starting point, this will yield 3^10 end points. Those 3^10 end points are plotted and make your fractal. [[Special:Contributions/46.64.181.38|46.64.181.38]] ([[User talk:46.64.181.38|talk]]) 14:11, 19 April 2014 (UTC)

:So your last reason for removing a link of a free software instead of a commercial one and mark it non-free is that the commercial one was there as long as you can remember. In sight of these negligence and dilettantence i don't understand why are you editing this article. Thank you in advance. Simzer 2007.06.02

::Right. Another way of looking at it is that the chaos-game algorithm is a random depth-first "search" that never backtracks, while Method 2 is an exhaustive search up to a given depth. But yes, this paragraph is super unclear. I just improved it slightly, but a '''lot''' more work is needed. [[User:Kragen|Kragen Javier Sitaker]] ([[User talk:Kragen|talk]]) 05:49, 19 July 2014 (UTC)

== Definitions ==

The iterated function system or IFS should be defined as a dynamical system. Then the fractal sets may be defined as the invariant sets of IFSs.

==DimensionExample==

Just not an encyclopedic, throught with ferns and triangles [http://vimeo.com/13074728 IFS animation 1] and [http://vimeo.com/12943444 IFS animation 2] <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Edo 555|Edo 555]] ([[User talk:Edo 555|talk]] • [[Special:Contributions/Edo 555|contribs]]) 14:05, 8 July 2010 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

Aren't fractals represented as 2 or 3 (or X) dimensional, but in actuality of fractional dimension? If so, this should be clarified in the article. [[User:Hyacinth|Hyacinth]] 00:43, 8 Feb 2005 (UTC)

== ChaosMajor Gamemissing topics ==

the article says "An IFS provides a global construction of a fractal by examining the backward orbits of points."

i don't understand that, can you clarify?

Although a few are mentioned as links, this page currently doesn't talk about any of these IFS topics, which I think are interesting and important:

then it says

"Where a high degree of detail in a small area of the fractal is required, local methods based on calculating forward orbits and the fate of individual points may be more efficient." what methods are these? please provide a reference.

* fractal image compression using IFSs;

:I added these sentences to the article, in an attempt to clarify a comment inserted by another contributor, which basically said "you cannot zoom into an IFS". Let me try to explain in more detail with an example. Suppose you want to plot the [[Julia set]] of the dynamical system <math>f(z)=z^2+c</math> i.e. the Julia set that lies "behind" the point c in the Mandelbrot set plane. There are two different ways of doing this.

* escape-time rendering of IFSs by inverting the functions;

* ray-traced rendering of 3-D IFSs;

* the relationship between IFSs and L-Systems, at any rate the commonly-studied L-Systems (it's easy to come up with a pathological L-System that doesn't obviously correspond to any IFS);

* Barnsley's deterministic iteration algorithm, which I guess is "Method 2"?

* the various other rendering methods presented by Hepting et al. 1991;

* the "collage theorem";

* Bell's "tesseral synecdoche algorithm";

* the "grayscale photo-copy algorithm" and its connection to the invariant measure of the IFS;

* the problem of computing the IFS's bounding box;

* the need to balance transform probabilities for stochastic ("chaos game") rendering (and the difficulty of doing so);

* computing sound upper and lower conservative bounds on the IFS's attractor;

* the phase transitions observed during continuous parameter variation.

Some random set of slides I ran across mentioned that you can get good ray-tracing results by approximating your surface normal as a weighted sum of the surface normals of the bounding spheres of the different subunits, which was part of what I was trying to figure out. I was disappointed to find that we haven't written a better article on this topic yet.

:One method is to use an IFS approach. Start with a random point ''z''; iterate the inverse functions <math>g(z)=\sqrt{z-c}</math>, taking one of the two values of the square root at random; throw away the first 10 or so iterates then plot the rest. The iterates lie in the backward orbit set of the initial point and they converge to the Julia set, because the Julia set is the limit set of the backward orbit set of any point.

Thoughts on which of these are most important to cover? How to organize them?

:The second method is to iterate <math>f(z)=z^2+c</math> for each point in a lattice. If the iterates diverge to infinity, that point is not in the Julia set; if they stay bounded then it is, because the Julia set is invariant under iterations of ''f''(''z''). In practice, you pick a threshold magnitude and plot a point ''z'' if <math>|f^n(z)|</math> is still less than this magnitude after, say, 10 iterations. This method examines the forward orbit of ''z''.

[[User:Kragen|Kragen Javier Sitaker]] ([[User talk:Kragen|talk]]) 06:19, 19 July 2014 (UTC)

:If your viewing window covers the whole Julia set, then the IFS method is more efficient - it will give you an outline of the Julia set very quickly, although it takes time to fill in detail. If your viewing window is just a small area of the Julia set then the forward orbit method is more efficient, because most iterates of the IFS method will fall outside of the viewing window, and so are thrown away. I don't have a reference for this to hand, but I would guess Barnsley's ''Fractals Everywhere'' most probably covers this.

== Zooming ==

:Does this explanation make things any clearer ? [[User:Gandalf61|Gandalf61]] 10:13, 20 June 2006 (UTC)

The article says that zooming in on an IFS fractal using the deterministic and random iteration algorithms is impractical.

This may not be the case, depending on how broadly you conceive each algorithm. I've been investigating producing high depth zooms, using a modification of the (depth first) deterministic iteration algorithm and reached a zoom of 5 × 10¹⁵⁰, using native 64 bit floating point arithmetic, without any noticeable deterioration in image quality, at little cost in extra computation time. At this point I hit an arithmetic overflow in the calculation of how deep the iterations should be, but this code can be refactored to avoid this. The modified code is ticking away and has reached a zoom 7 × 10¹⁹⁰. It may be possible to get to over 10⁶⁰⁰.

yes but it only works for a few special cases, not IFS in general.

The modification is to combine a shallow depth first deterministic algorithm with a pruned breadth first deterministic algorithm (i.e. selecting only those branches in the deeper parts of the tree which lie within the zoom).

:Yes, which is why the article says that local methods based on forward orbits ''may'' be more efficient. It does not claim that local methods exist for every IFS. [[User:Gandalf61|Gandalf61]] 12:57, 26 June 2006 (UTC)

I haven't tried it yet, but combining a random iteration algorithm with the same pruned breadth first deterministic algorithm, should also work. [[User:Lavateraguy|Lavateraguy]] ([[User talk:Lavateraguy|talk]]) 16:48, 3 November 2016 (UTC)

yes, but "may" is one tiny word at the end of a heavy paragraph. i'm not aware of any IFS implementations that do that, are you? i would say that's an interesting research idea, but not relevant to the point of the paragraph: how IFS are drawn, how that differs from the stereotypical 2D fractal algorithm, and the implication of this (zooming is hard).

:''Some'' IFSs produce the Julia sets of dynamical systems (<math>f(z)=z^2+c</math> is one example) and the same image can then be produced by tracing forward orbits - that's fact, not a research idea. However, if you want to rewrite or remove the whole paragraph, that is fine with me. I did not add this paragraph in the first place - I just tried to clarify a couple of sentences added by another contributor - so I don't feel strongly about it at all. [[User:Gandalf61|Gandalf61]] 11:26, 27 June 2006 (UTC)

Hi Gandalf, why do you keep reverting my work on the Iterated Function System page? The text you defend is misleading and nearly opaque. My version is correct and clear. I know this because I teach people about IFS all the time. You said "if you want to rewrite or remove the whole paragraph, that is fine with me. I did not add this paragraph in the first place - I just tried to clarify a couple of sentences added by another contributor - so I don't feel strongly about it at all. " but you persist in using your text. i do feel strongly about this and i know what i'm talking about. my text is shorter, uses less jargon, addreses the issues that concern and confuse readers, and is correct. what was inaccurate? please explain. -spot

:I reverted your version of the paragraph about the shortcomings of the IFS method of constructing fractals because:

:#Your version uses the term "IFS fractal". There is no such thing. An IFS is a ''method'' of constructing a fractal, not an attribute of the fractal itself.

:#Your version does not explain what the alternative construction methods are.

:#Your version uses the second person - "''you'' cannot easily zoom into ...". [[WP:STYLE]] says that use of the second person is discouraged because it sets an unencyclopedic tone.

:[[User:Gandalf61|Gandalf61]] 10:57, 2 August 2006 (UTC)

== video feedback as IFS ==

i would prefer to mention another implementation of IFS: video feedback.

{{unsigned|69.109.182.150|07:07, 27 June 2006--[[User:LutzL|LutzL]]}}

:Yes, that's a nice passtime to confuse shopkeepers. It's chaotic, but could you please explain in which sense this slightly perturbed affine linear map constitutes an IFS? Or any link detailing this?--[[User:LutzL|LutzL]] 10:04, 27 June 2006 (UTC)

see here: http://www.physics.gla.ac.uk/Optics/projects/fractalVideoFeedback/

and it's mention here: http://en.wikipedia.org/wiki/Optical_feedback

[[User:Spot|Spot]] 02:00, 10 March 2007 (UTC)

:Yes, nice descriptions of the effect. But neither page describes a relation to IFS. The other problem is that color is involved, or at least different shades of gray. An IFS is only capable to generate black-white images as representations of the fix-point set. As in the fractal flames example, optical feedback needs a generalization of IFS to something like self-similar functions [http://citeseer.ist.psu.edu/165405.html (Cabrelli/Molter (1996): Generalized Self-Similarity)].--[[User:LutzL|LutzL]] 08:16, 29 May 2007 (UTC)

== Construction ==

[[Image:Ifs-construction.png|thumb|right|400px|[[Ifs Construction]] IFS being made with two functions.]]

I propose adding the image on the right, with some text, possibly replacing the fern as the example. [[User:Spot|Spot]] 01:52, 30 May 2007 (UTC)

== Properties ==

Several things wrong here I fear.

* "In general, if there are p functions, then one may visualize the composition as a p-adic tree.". Link to [[p-adic]] takes you to p-adic numbers, not the same thing (see below), this is a ''full [[K-ary tree]]'' with K=p, ie each node has p immediate descendents.

* Confusion about the monoid (which consists of finite strings) and the tree (which has all infinite paths in it). The monoid can't consist of infinite strings, at least, not indexed by natural numbers: how could you compose the all L word with the all R word?

* Link to [[dyadic monoid]] redirects to [[modular group]], presumably intended to R to section Dyadic monoid. See [[Talk:Modular group]] for what I think is wrong there.

* "the elements of the monoid can be seen to be isomorphic with the p-adic numbers; that is, each digit of the p-adic number indicates which function is to be composed with." Not so. (1) The p-adic numbers form a ring, not a monoid. (2) the p-adic numbers have an infinite sequence of base p digits, the elements of the monoid are finite strings (3) the p-adic numbers are usually only defined for prime values of p (4) composition of finite p-ary strings is not isomorphic to either of p-adic addition or multiplication (5) the monoid is countable, the p-adic numbers are uncountable ...

* "The automorphism group of the dyadic monoid is the modular group". No, the automorphism group of the dyadic monoid is just the cyclic group of order 2. Proof. The monoid is generated by two elements L and R. The image of each under an automorphism must be a word of length 1 (otherwise the alleged automorphism would not be invertible) and so the automorphism is either L,R goes to L,R or R,L.

Would someone completely rewrite -- or delete -- this section please? [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 22:40, 15 July 2008 (UTC)