Talk:Iterated function system: Difference between revisions

Revision as of 17:10, 19 July 2008

Latest revision as of 17:06, 15 February 2024

(27 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)

:Yes, I think you are right. Any mention of ''p''-adic numbers in this section is mostly misleading (or at least would require a lot of explanation to clarify the point being made), so that should be left out. And the whole "dyadic monoid" bit is confusing. I have cut down the section by removing most of these confusing references. There is still an outstanding point around the subtle distinction between the monoid which contains only finite strings and the limit object which contains countably infinite strings or sequences of functions - I may try to add some further explanation when I have more time. [[User:Gandalf61|Gandalf61]] ([[User talk:Gandalf61|talk]]) 10:48, 16 July 2008 (UTC)

::I think the point is that the monoid (finite strings) ''[[Group action#Generalizations|acts]]'' on the tree (infinite paths). [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 20:08, 16 July 2008 (UTC)

== Further points ==

# The article needs [[WP:RS|references]]. I believe that the 1981 paper of Hutchinson is {{cite journal | last=Hutchinson | first=John E. | title=Fractals and self similarity | journal=Indiana Univ. Math. J. | volume=30 | year=1981 | pages=713-747 }}. See [http://www.zentralblatt-math.org/zmath/en/search/?q=an:0598.28011&format=complete ZMATH].

# The link to [[John Hutchinson]] points to a disambiguation page and I don't think any of the articles referred to there can be the right one.

# The redlink [[Hutchinson set]] needs to be turned blue, or supplemented by a brief explanation or of course both.

# "S is the fixed point of a Hutchinson operator, which is the union of the functions fi" might read better as "S is a set fixed under the action of any of the functions fi." supplemented by adding the following

# "One way of constructing such a fixed set is to start with an initial point or set S_0 and iterating the actions of the f_i, as S_{n+1} = \bigcup_i f_i[S_n], then taking S to be the union \bigcup_n S_n. Random elements of S may be obtained by the "chaos game", see below. Hutchinson showed that the system {fi} has a unique closed bounded fixed set, which is the closure of the sets obtained by these iterations.

# There's an issue with closure here. If the fi are closed and continuous then taking the closure of a fixed set is again a fixed set.

# Hutchinson's paper requires the mappings fi to be [[contraction map]]s, not alluded to here.

# "Iterated function systems are a generalisation of the Cantor set, first described in 1884, and of de Rham curves, a type of self-similar curve described by Georges de Rham in 1957." This needs some justification. I see that the Cantor set can be obtained as a fixed set of the functions f1(x) = x/3 and f2(x) = (x+2)/3 starting with the set {0} provided that we then take the closure. I'm not sufficiently familiar with the de Rham curves to expand on those. But anyway folks, we need [[WP:RS|references]] here!

Enough for now ... [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 20:52, 16 July 2008 (UTC)

: ad (3) Done but it's the merest of stubs so far. [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 17:09, 19 July 2008 (UTC)

==Contraction mappings==

The sentence "Although the theory of IFS requires each function to be contractive, in practice software that implements IFS only require that the whole system be contractive on average." does not appear to be supported by an appropriate [[WP:RS|reference]]. [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 18:36, 18 July 2008 (UTC)

:page 3 of Draves and Reckase, the first reference listed.[[User:Spot|Spot]] ([[User talk:Spot|talk]]) 20:15, 18 July 2008 (UTC)

::I have to point out that's by you yourself (a point you might have made) -- I think the onus is on you to show that it is appropriate in the light of [[WP:V#SELF]] or, preferably, find another, third-party, reference. [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 21:09, 18 July 2008 (UTC)

:::The same material has been published in regular scientific channels, eg Applications of Evolutionary Computing, 2005, LNCS 3449 http://www.springer.com/computer/foundations/book/978-3-540-25396-9 and ACM Non-Photorealistic Animation and Rendering; The Electric Sheep and their Dreams in High Fidelity; Scott Draves (invited keynote) June 2006 http://www.siggraph.org/events/symposia/npar2006 But the Flame paper linked here is more accessible and complete. And if you google for "contractive on average" you will see others using this phrase for IFS. The reference was already in the bibliography I am just letting you know what page specifically... [[User:Spot|Spot]] ([[User talk:Spot|talk]]) 22:22, 18 July 2008 (UTC)

::::References published in regular scientific channels would be the appropriate ones to add. If you have one which defines "contractive on average" then by all means add that too. Bear in mind that [[WP:V#Burden of evidence]] puts the onus on you to do that when you add material. [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 22:38, 18 July 2008 (UTC)

:::::I didn't add the reference, it has been there for years, I'm just telling you on what page you can find the statement in the references already used that backs up the edit in question. Do the references really have to define it or just use the phrase? This is a statement about the computer graphics technique of IFS, not the mathematical objects, maybe it should just go into the section on constructions, which also includes implementation info such as the effect of zooming. I think that would be an best what do you think? [[User:Spot|Spot]] ([[User talk:Spot|talk]]) 22:54, 18 July 2008 (UTC)

:::::Looks like this paper defines it: http://ace.acadiau.ca/math/mendivil/Papers/infifs.ps [[User:Spot|Spot]] ([[User talk:Spot|talk]]) 00:15, 19 July 2008 (UTC)

::::::Contraction on average requires a notion of probability on the infinite k-ary tree and so really has to be defined after the description of the "chaos game". References that seem good to me are {{cite journal | title=Iterated Random Functions | author= Persi Diaconis | coauthors=David Freedman | journal= SIAM Review | volume=41 | issue=1 | pages=45-76 | date=Mar 1999 | url=http://oz.berkeley.edu/tech-reports/511.pdf | format=PDF }} and {{cite journal | author=Thomas Jordan | coauthors=Mark Pollicott | title=The Haussdorff dimension of measures for iterated function systems which contract on average | journal=Discrete and Continuous Dynamical Systems | volume=22 | year=2008 | pages=235-246 | url=http://www.warwick.ac.uk/~masdbl/pesin.pdf | format=PDF }} [[User:Richard Pinch|Richard Pinch]] ([[User talk:Richard Pinch|talk]]) 09:05, 19 July 2008 (UTC)