“迭代函数系统”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
 
第1行： 第1行：
−
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
+
此词条暂由彩云小译翻译，翻译字数共213，未经人工整理和审校，带来阅读不便，请见谅。
  
 
[[File:Sierpinski1.png|thumb|right|250px|[[Sierpinski triangle]] created using IFS (colored to illustrate self-similar structure)]]
 
[[File:Sierpinski1.png|thumb|right|250px|[[Sierpinski triangle]] created using IFS (colored to illustrate self-similar structure)]]
第5行： 第5行：
 
[[Sierpinski triangle created using IFS (colored to illustrate self-similar structure)]]
 
[[Sierpinski triangle created using IFS (colored to illustrate self-similar structure)]]
  
−
[[使用 IFS (着色以说明自相似结构)创建的谢尔宾斯基三角形]]
+
[[使用 IFS 创建的谢尔宾斯基三角形(着色以说明自相似结构)]
  
 
[[File:Chris Ursitti fractal 0000.png|thumb|right|200px|Colored IFS designed using [[Apophysis (software)|Apophysis]] software and rendered by the [[Electric Sheep]].]]
 
[[File:Chris Ursitti fractal 0000.png|thumb|right|200px|Colored IFS designed using [[Apophysis (software)|Apophysis]] software and rendered by the [[Electric Sheep]].]]
第15行： 第15行：
 
In [[mathematics]], '''iterated function systems''' ('''IFSs''') are a method of constructing [[fractal]]s; the resulting fractals are often [[self-similar]]. IFS fractals are more related to [[set theory]] than fractal geometry.<ref name="picg">{{cite book |title=Progress in Computer Graphics: Volume 1 |last=Zobrist |first= George Winston |author2=Chaman Sabharwal |year=1992 |publisher=Intellect Books |isbn=9780893916510 |page=135 |url=https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC |accessdate=7 May 2017}}</ref> They were introduced in 1981.
 
In [[mathematics]], '''iterated function systems''' ('''IFSs''') are a method of constructing [[fractal]]s; the resulting fractals are often [[self-similar]]. IFS fractals are more related to [[set theory]] than fractal geometry.<ref name="picg">{{cite book |title=Progress in Computer Graphics: Volume 1 |last=Zobrist |first= George Winston |author2=Chaman Sabharwal |year=1992 |publisher=Intellect Books |isbn=9780893916510 |page=135 |url=https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC |accessdate=7 May 2017}}</ref> They were introduced in 1981.
  
−
In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. They were introduced in 1981.
+
In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS factals.
  
−
在数学中，迭代函数系统是构造分形的一种方法; 由此产生的分形通常是自相似的。与分形几何相比，IFS 分形与集合论的关系更大。它们是在1981年推出的。
+
在数学中，迭代函数系统是构造分形的一种方法; 由此产生的分形通常是自相似的。与分形几何相比，IFS 分形与集合论的关系更大。给出惊人的好图像压缩，即使对于那些似乎没有简单的 IFS 面形所显示的自相似结构的照片也是如此。
  
  
第23行： 第23行：
 
'''IFS''' fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the [[Sierpiński triangle]]. The functions are normally [[contraction mapping|contractive]], which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, [[ad infinitum]]. This is the source of its self-similar fractal nature.
 
'''IFS''' fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the [[Sierpiński triangle]]. The functions are normally [[contraction mapping|contractive]], which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, [[ad infinitum]]. This is the source of its self-similar fractal nature.
  
−
IFS fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the Sierpiński triangle. The functions are normally contractive, which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, ad infinitum. This is the source of its self-similar fractal nature.
+
As of 1995, all fractal compression software is based on Jacquin's approach.
  
−
Ifs 分形，正如它们通常被称为的那样，可以是任意数量的维数，但是通常是在2D 中计算和绘制的。分形是由几个自身副本的结合组成的，每个副本由一个函数(因此称为“函数系统”)进行转换。典型的例子是 sierpi 滑雪三角形。这些函数通常是收缩的，这意味着它们使点靠得更近，使形状变小。因此，迭代函数系统分形的形状是由几个可能重叠的自身的小副本组成的，每个副本也是由自身的副本组成的，而且是无限的。这就是其自相似分形特性的来源。
+
截至1995年，所有的分形压缩软件都是基于 Jacquin 的方法。
  
  
第33行： 第33行：
 
Formally, an [[iterated function]] system is a finite set of [[contraction mapping]]s on a [[complete metric space]].<ref>Michael Barnsley (1988). ''Fractals Everywhere'', p.82. Academic Press, Inc. {{ISBN|9780120790623}}.</ref> Symbolically,
 
Formally, an [[iterated function]] system is a finite set of [[contraction mapping]]s on a [[complete metric space]].<ref>Michael Barnsley (1988). ''Fractals Everywhere'', p.82. Academic Press, Inc. {{ISBN|9780120790623}}.</ref> Symbolically,
  
−
Formally, an iterated function system is a finite set of contraction mappings on a complete metric space. Symbolically,
+
The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the Hutchinson operator. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal.
  
−
在形式上，迭代函数系统是完备空间上的有限压缩映射集。象征性地,
+
该图展示了由两个仿射函数构造 IFS 的过程。函数通过它们对双单元正方形的影响来表示(函数将轮廓的正方形转换为阴影的正方形)。这两个函数的组合形成了哈钦森算子。算子的三次迭代被显示出来，然后最终的图像是不动点的，最终的分形。
  
 
:<math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math>
 
:<math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math>
−
 
−
<math>\{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N}</math>
 
−
 
−
math i: x 到 mid i 1,2，dots，n，n 在 mathbb n / math 中
 
  
 
is an iterated function system if each <math>f_i</math> is a contraction on the complete metric space <math>X</math>.
 
is an iterated function system if each <math>f_i</math> is a contraction on the complete metric space <math>X</math>.
  
−
is an iterated function system if each <math>f_i</math> is a contraction on the complete metric space <math>X</math>.
+
Early examples of fractals which may be generated by an IFS include the Cantor set, first described in 1884; and de Rham curves, a type of self-similar curve described by Georges de Rham in 1957.
  
−
如果每个数学成绩 / 数学成绩都是迭代函数系统 / 完备空间数学 x / 数学的缩写，那么这个成绩就是100分。
+
由 IFS 产生的分形的早期例子包括 Cantor 集，第一次描述是在1884年; 和 de Rham 曲线，一种自相似曲线，由 Georges de Rham 在1957年描述。
  
  
第55行： 第51行：
 
[[File:Chaosgame.gif|thumb|right|250px|Construction of an IFS by the [[chaos game]] (animated)]]
 
[[File:Chaosgame.gif|thumb|right|250px|Construction of an IFS by the [[chaos game]] (animated)]]
  
−
Construction of an IFS by the [[chaos game (animated)]]
+
IFSs were conceived in their present form by John E. Hutchinson in 1981 and popularized by Michael Barnsley's book Fractals Everywhere. <!-- In 1992 Scott Draves developed the Fractal flame algorithm.-->
  
−
通过[[混沌游戏(动画)]]构建一个 IFS
+
1981年，约翰 · e · 哈钦森以现在的形式构思了 IFSs，并由迈克尔 · 巴恩斯利的著作《分形无处不在》而流行开来。1992年，斯科特 · 德拉维斯发明了分形火焰算法
  
 
[[File:Ifs-construction.png|thumb|IFS being made with two functions.]]
 
[[File:Ifs-construction.png|thumb|IFS being made with two functions.]]
−
 
−
IFS being made with two functions.
 
−
 
−
Ifs 具有两个功能。
 
  
 
Hutchinson (1981) showed that, for the metric space <math>\mathbb{R}^n</math>, or more generally, for a complete metric space <math>X</math>, such a system of functions has a unique nonempty [[Compact space|compact]] (closed and bounded) fixed set ''S''. One way of constructing a fixed set is to start with an initial nonempty closed and bounded set ''S''<sub>0</sub> and iterate the actions of the ''f''<sub>''i''</sub>, taking ''S''<sub>''n''+1</sub> to be the union of the images of ''S''<sub>''n''</sub> under the ''f''<sub>''i''</sub>; then taking ''S'' to be the [[Closure (topology)|closure]] of the union of the ''S''<sub>''n''</sub>. Symbolically, the unique fixed (nonempty compact) set <math>S\subseteq X</math> has the property
 
Hutchinson (1981) showed that, for the metric space <math>\mathbb{R}^n</math>, or more generally, for a complete metric space <math>X</math>, such a system of functions has a unique nonempty [[Compact space|compact]] (closed and bounded) fixed set ''S''. One way of constructing a fixed set is to start with an initial nonempty closed and bounded set ''S''<sub>0</sub> and iterate the actions of the ''f''<sub>''i''</sub>, taking ''S''<sub>''n''+1</sub> to be the union of the images of ''S''<sub>''n''</sub> under the ''f''<sub>''i''</sub>; then taking ''S'' to be the [[Closure (topology)|closure]] of the union of the ''S''<sub>''n''</sub>. Symbolically, the unique fixed (nonempty compact) set <math>S\subseteq X</math> has the property
−
 
−
Hutchinson (1981) showed that, for the metric space <math>\mathbb{R}^n</math>, or more generally, for a complete metric space <math>X</math>, such a system of functions has a unique nonempty compact (closed and bounded) fixed set S. One way of constructing a fixed set is to start with an initial nonempty closed and bounded set S<sub>0</sub> and iterate the actions of the f<sub>i</sub>, taking S<sub>n+1</sub> to be the union of the images of S<sub>n</sub> under the f<sub>i</sub>; then taking S to be the closure of the union of the S<sub>n</sub>. Symbolically, the unique fixed (nonempty compact) set <math>S\subseteq X</math> has the property
 
−
 
−
Hutchinson (1981)证明了，对于度量空间数学[ r ] ^ n / math，或者更广泛地说，对于完备空间数学 x / math，这样一个函数系统有唯一的非空紧(闭和有界)固定集 s。 构造固定集的一种方法是从初始非空闭有界集 s 子0 / 子开始，迭代 f 子 i / 子的动作，将 s 子 n + 1 / 子取为 f 子 i / 子下 s 子 n / 子映象的并，然后将 s 取为 s 子 n / 子的并的闭包。从符号上看，唯一的固定(非空紧凑)集 math s  subseteq x / math 具有该属性
 
  
 
:<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
 
:<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
−
 
−
<math>S = \overline{\bigcup_{i=1}^N f_i(S)}.</math>
 
−
 
−
数学 s 加行{ i 1} ^ n f i (s)} . / 数学
 
  
 
The set ''S'' is thus the fixed set of the [[Hutchinson operator]] <math>F: 2^X\to 2^X</math> defined for <math>A\subseteq X</math> via
 
The set ''S'' is thus the fixed set of the [[Hutchinson operator]] <math>F: 2^X\to 2^X</math> defined for <math>A\subseteq X</math> via
−
 
−
The set S is thus the fixed set of the Hutchinson operator <math>F: 2^X\to 2^X</math> defined for <math>A\subseteq X</math> via
 
−
 
−
因此，集合 s 是为数学 a  subseteq x / math 定义的 Hutchinson 算子数学 f: 2 ^ x  to 2 ^ x / math 的固定集合
 
  
 
:<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>
 
:<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>
−
 
−
<math>F(A)=\overline{\bigcup_{i=1}^N f_i(A)}.</math>
 
−
 
−
数学 f (a) overline { bigcup { i 1} ^ n f i (a)} . / math
 
  
  
  
 
The existence and uniqueness of ''S'' is a consequence of the [[contraction mapping principle]], as is the fact that
 
The existence and uniqueness of ''S'' is a consequence of the [[contraction mapping principle]], as is the fact that
−
 
−
The existence and uniqueness of S is a consequence of the contraction mapping principle, as is the fact that
 
−
 
−
的存在性和唯一性是压缩映射原理的结果，事实上也是如此
 
  
 
:<math>\lim_{n\to\infty}F^{\circ n}(A)=S</math>
 
:<math>\lim_{n\to\infty}F^{\circ n}(A)=S</math>
−
 
−
<math>\lim_{n\to\infty}F^{\circ n}(A)=S</math>
 
−
 
−
(a) s / math
 
  
 
for any nonempty compact set <math>A</math> in <math>X</math>. (For contractive IFS this convergence takes place even for any nonempty closed bounded set <math>A</math>). Random elements arbitrarily close to ''S'' may be obtained by the "chaos game," described below.
 
for any nonempty compact set <math>A</math> in <math>X</math>. (For contractive IFS this convergence takes place even for any nonempty closed bounded set <math>A</math>). Random elements arbitrarily close to ''S'' may be obtained by the "chaos game," described below.
−
 
−
for any nonempty compact set <math>A</math> in <math>X</math>. (For contractive IFS this convergence takes place even for any nonempty closed bounded set <math>A</math>). Random elements arbitrarily close to S may be obtained by the "chaos game," described below.
 
−
 
−
在数学 x / math 中的任意非空紧集数学 a / math。(对于收缩型迭代函数系统(IFS) ，这种收敛甚至发生在任何非空的闭有界集数学 a / math 上)。任意接近 s 的随机元素可以通过下面描述的“混沌游戏”获得。
 
  
  
  
 
Recently it was shown that the IFSs of noncontractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in ''X'') can yield attractors.
 
Recently it was shown that the IFSs of noncontractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in ''X'') can yield attractors.
−
 
−
Recently it was shown that the IFSs of noncontractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in X) can yield attractors.
 
−
 
−
近年来研究表明，非收缩型 IFSs (即非收缩型 IFSs)与非收缩型 IFSs (即非收缩型 IFSs)之间存在一定的相关性。组成的映射，不收缩方面的任何拓扑等价度量在 x)可以产生吸引子。
 
  
 
These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>
 
These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.<ref>M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System</ref>
−
 
−
These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.
 
−
 
−
这些在射影空间中自然产生，尽管圆上的经典无理角也可以调整。
 
  
  
  
 
The collection of functions <math>f_i</math> [[Generating set|generates]] a [[monoid]] under [[Function composition|composition]]. If there are only two such functions, the monoid can be visualized as a [[binary tree]], where, at each node of the tree, one may compose with the one or the other function (''i.e.'' take the left or the right branch). In general, if there are ''k'' functions, then one may visualize the monoid as a full [[k-ary tree|''k''-ary tree]], also known as a [[Cayley tree]].
 
The collection of functions <math>f_i</math> [[Generating set|generates]] a [[monoid]] under [[Function composition|composition]]. If there are only two such functions, the monoid can be visualized as a [[binary tree]], where, at each node of the tree, one may compose with the one or the other function (''i.e.'' take the left or the right branch). In general, if there are ''k'' functions, then one may visualize the monoid as a full [[k-ary tree|''k''-ary tree]], also known as a [[Cayley tree]].
−
 
−
The collection of functions <math>f_i</math> generates a monoid under composition. If there are only two such functions, the monoid can be visualized as a binary tree, where, at each node of the tree, one may compose with the one or the other function (i.e. take the left or the right branch). In general, if there are k functions, then one may visualize the monoid as a full k-ary tree, also known as a Cayley tree.
 
−
 
−
函数 math f / math 的集合在复合下生成一个幺半群。如果只有两个这样的函数，monoid 可以可视化为一棵二叉树，其中，在树的每个节点上，一个可以与一个或另一个函数(即。采取左侧或右侧分支)。一般来说，如果有 k 个函数，那么我们可以把 monoid 想象成一个完整的 k 元树，也称为 Cayley 树。
 
  
  
第136行： 第88行：
  
 
[[File:Fractal fern explained.png|thumb|upright|[[Barnsley's fern]], an early IFS]]
 
[[File:Fractal fern explained.png|thumb|upright|[[Barnsley's fern]], an early IFS]]
−
 
−
[[Barnsley's fern, an early IFS]]
 
−
 
−
[[Barnsley's fern, an early IFS]]
 
  
 
[[File:Menger sponge (IFS).jpg|thumb|200px|[[Menger sponge]], a 3-Dimensional IFS.]]
 
[[File:Menger sponge (IFS).jpg|thumb|200px|[[Menger sponge]], a 3-Dimensional IFS.]]
−
 
−
[[Menger sponge, a 3-Dimensional IFS.]]
 
−
 
−
[[Menger sponge, a 3-Dimensional IFS.]]
 
  
 
[[File:Coupe d'arbre.png|thumb|IFS "tree" constructed with non-linear function Julia]]
 
[[File:Coupe d'arbre.png|thumb|IFS "tree" constructed with non-linear function Julia]]
−
 
−
IFS "tree" constructed with non-linear function Julia
 
−
 
−
用非线性函数 Julia 构造 IFS“树”
 
  
 
[[File:Golden Square fractal with T-branching 8.svg|thumb|[[Golden ratio|Golden squares]] with [[T-square (fractal)|T-branching]]]]
 
[[File:Golden Square fractal with T-branching 8.svg|thumb|[[Golden ratio|Golden squares]] with [[T-square (fractal)|T-branching]]]]
−
 
−
Golden squares with T-branching]]
 
−
 
−
带有 t 型分支的金色方块]]
 
  
 
{{multiple image
 
{{multiple image
−
 
−
{{multiple image
 
−
 
−
{多重图像
 
  
 
  | align =  
 
  | align =  
−
 
−
| align =
 
−
 
−
校准
 
−
 
−
| direction = horizontal
 
  
 
  | direction = horizontal
 
  | direction = horizontal
−
 
−
| 方向水平
 
−
 
−
| width = 150
 
  
 
  | width = 150
 
  | width = 150
−
 
−
150
 
−
 
−
| header =
 
  
 
  | header =  
 
  | header =  
−
 
−
标题
 
  
 
  | image1 = Golden Square fractal 6.svg
 
  | image1 = Golden Square fractal 6.svg
−
 
−
| image1 = Golden Square fractal 6.svg
 
−
 
−
1 Golden Square fractal 6. svg
 
−
 
−
| caption1 = [[Golden ratio|Golden square]] fractal
 
−
 
−
| caption1 = Golden square fractal
 
−
 
−
1 Golden square fractal
 
−
 
−
| image2 = Half square fractal 5.svg
 
−
 
−
| image2 = Half square fractal 5.svg
 
−
 
−
2 Half square fractal 5. svg
 
−
 
−
| caption2 = Half fractal
 
−
 
−
| caption2 = Half fractal
 
−
 
−
2 Half fractal
 
−
 
−
| footer =
 
−
 
−
| footer =
 
−
 
−
我不知道你在说什么
 
−
 
−
}}
 
−
 
−
}}
 
−
 
−
}}
 
−
 
−
 
−
 
−
Sometimes each function <math>f_i</math> is required to be a [[Linear transformation|linear]], or more generally an [[affine transformation|affine]], transformation, and hence represented by a [[matrix (mathematics)|matrix]]. However, IFSs may also be built from non-linear functions, including [[projective transformation]]s and [[Möbius transformation]]s. The [[Fractal flame]] is an example of an IFS with nonlinear functions.
 
−
 
−
Sometimes each function <math>f_i</math> is required to be a linear, or more generally an affine, transformation, and hence represented by a matrix. However, IFSs may also be built from non-linear functions, including projective transformations and Möbius transformations. The Fractal flame is an example of an IFS with nonlinear functions.
 
−
 
−
有时候每个函数数学 i / math 必须是线性的，或者更一般地说是仿射变换，因此要用矩阵来表示。然而，IFSs 也可以由非线性函数构造，包括射影变换和 m bius 变换。分形火焰是具有非线性函数的迭代函数系统的一个例子。
 
−
 
−
 
−
 
−
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 to transform the point to get a next 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.
 
−
 
−
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 to transform the point to get a next 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.
 
−
 
−
计算 IFS 分形最常用的算法叫做“混沌博弈”。它包括在平面上选择一个随机点，然后迭代应用从函数系统中随机选择的函数之一，对该点进行变换得到下一个点。一种替代算法是生成给定最大长度内的每个可能的函数序列，然后绘制将这些函数序列中的每个应用于初始点或形状的结果。
 
−
 
−
 
−
 
−
Each of these algorithms provides a global construction which generates points distributed across the whole fractal. If a small area of the fractal is being drawn, many of these points will fall outside of the screen boundaries. This makes zooming into an IFS construction drawn in this manner impractical.
 
−
 
−
Each of these algorithms provides a global construction which generates points distributed across the whole fractal. If a small area of the fractal is being drawn, many of these points will fall outside of the screen boundaries. This makes zooming into an IFS construction drawn in this manner impractical.
 
−
 
−
这些算法中的每一个都提供了一个全局构造，生成分布在整个分形上的点。如果画出一小块分形区域，其中许多点将落在屏幕边界之外。这使得缩小到以这种方式绘制的 IFS 结构是不切实际的。
 
−
 
−
 
−
 
−
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.<ref>{{cite web |last=Draves |first=Scott |authorlink=Scott Draves |author2=Erik Reckase |date=July 2007 |url=http://flam3.com/flame.pdf |title=The Fractal Flame Algorithm |format=pdf |accessdate=2008-07-17 |archive-url=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf |archive-date=2008-05-09 |url-status=dead }}</ref>
 
−
 
−
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.
 
−
 
−
虽然迭代函数系统理论要求每个函数都是收缩的，但在实际应用中，实现迭代函数系统的软件只要求整个系统平均是收缩的。
 
−
 
−
 
−
 
−
==Partitioned iterated function systems==
 
−
 
−
 
−
 
−
PIFS (partitioned iterated function systems), also called local iterated function systems,<ref name="lacroix"/> give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS factals.<ref name="SIGGRAPH'92">{{cite conference
 
−
 
−
PIFS (partitioned iterated function systems), also called local iterated function systems, give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS factals.<ref name="SIGGRAPH'92">{{cite conference
 
−
 
−
Pifs (分区的迭代函数系统) ，也被称为局部迭代函数系统，提供了令人惊讶的好图像压缩，即使是对于那些看起来没有简单的 IFS 面形所显示的自相似结构的照片。 92"{ cite conference
 
−
 
−
|url= https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf
 
−
 
−
|url= https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf
 
−
 
−
Https://karczmarczuk.users.greyc.fr/matrs/dess/radi/refs/fractal_paper.pdf
 
−
 
−
|last= Fischer
 
−
 
−
|last= Fischer
 
−
 
−
最后一个费舍尔
 
−
 
−
|first= Yuval
 
−
 
−
|first= Yuval
 
−
 
−
首先是 Yuval
 
−
 
−
|title= SIGGRAPH'92 course notes - Fractal Image Compression
 
−
 
−
|title= SIGGRAPH'92 course notes - Fractal Image Compression
 
−
 
−
| SIGGRAPH’92课程笔记-分形图像压缩
 
−
 
−
|conference= SIGGRAPH
 
−
 
−
|conference= SIGGRAPH
 
−
 
−
会议 SIGGRAPH
 
−
 
−
|conferenceurl= http://www.siggraph.org/
 
−
 
−
|conferenceurl= http://www.siggraph.org/
 
−
 
−
会议 /  http://www.siggraph.org/
 
−
 
−
|editor= Przemyslaw Prusinkiewicz
 
−
 
−
|editor= Przemyslaw Prusinkiewicz
 
−
 
−
|editor= Przemyslaw Prusinkiewicz
 
−
 
−
|publisher= [[ACM SIGGRAPH]]
 
−
 
−
|publisher= ACM SIGGRAPH
 
−
 
−
美国计算机学会 SIGGRAPH 分会
 
−
 
−
|volume= Fractals - From Folk Art to Hyperreality
 
−
 
−
|volume= Fractals - From Folk Art to Hyperreality
 
−
 
−
| 卷分形-从民间艺术到超现实
 
−
 
−
|date= 1992-08-12
 
−
 
−
|date= 1992-08-12
 
−
 
−
日期1992-08-12
 
−
 
−
}}</ref>
 
−
 
−
}}</ref>
 
−
 
−
{} / ref
 
−
 
−
 
−
 
−
==The inverse problem==
 
−
 
−
{{Main|Fractal compression}}
 
−
 
−
 
−
 
−
Very fast algorithms exist to generate an image from a set of IFS or PIFS parameters. It is faster and requires much less storage space to store a description of how it was created, transmit that description to a destination device, and regenerate that image anew on the destination device, than to store and transmit the color of each pixel in the image.<ref name="lacroix">Bruno Lacroix. [http://www.collectionscanada.gc.ca/obj/s4/f2/dsk2/ftp01/MQ36939.pdf "Fractal Image Compression"]. 1998.</ref>
 
−
 
−
Very fast algorithms exist to generate an image from a set of IFS or PIFS parameters. It is faster and requires much less storage space to store a description of how it was created, transmit that description to a destination device, and regenerate that image anew on the destination device, than to store and transmit the color of each pixel in the image.
 
−
 
−
现有的非常快速的算法可以从一组 IFS 或 PIFS 参数生成图像。与存储和传输图像中每个像素的颜色相比，它更快，并且需要更少的存储空间来存储它是如何创建的描述，将该描述传输到目标设备，并在目标设备上重新生成该图像。
 
−
 
−
 
−
 
−
The [[inverse problem]] is more difficult: given some original arbitrary digital image such as a digital photograph, try to find a set of IFS parameters which, when evaluated by iteration, produces another image visually similar to the original.
 
−
 
−
The inverse problem is more difficult: given some original arbitrary digital image such as a digital photograph, try to find a set of IFS parameters which, when evaluated by iteration, produces another image visually similar to the original.
 
−
 
−
反问题更加困难: 给定一些原始的任意数字图像，比如一张数码照片，试图找到一组 IFS 参数，通过迭代计算，可以得到另一张与原始图像视觉上相似的图像。
 
−
 
−
In 1989, Arnaud Jacquin presented a solution to a restricted form of the inverse problem using only PIFS; the general form of the inverse problem remains unsolved.<ref>
 
−
 
−
In 1989, Arnaud Jacquin presented a solution to a restricted form of the inverse problem using only PIFS; the general form of the inverse problem remains unsolved.<ref>
 
−
 
−
在1989年，Arnaud Jacquin 提出了一个只使用 PIFS 的限制形式的反问题的解，反问题的一般形式仍未解决。 裁判
 
−
 
−
Dietmar Saupe, Raouf Hamzaoui.
 
−
 
−
Dietmar Saupe, Raouf Hamzaoui.
 
−
 
−
迪特玛 · 索佩，拉乌夫 · 哈姆扎维。
 
−
 
−
[https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/SaHa94.pdf "A Review of the Fractal Image Compression Literature"].
 
−
 
−
[https://www.uni-konstanz.de/mmsp/pubsys/publishedFiles/SaHa94.pdf "A Review of the Fractal Image Compression Literature"].
 
−
 
−
Https://www.uni-konstanz.de/mmsp/pubsys/publishedfiles/saha94.pdf  : 《分形图像压缩文献评论》。
 
−
 
−
</ref><ref name="kominek">
 
−
 
−
</ref><ref name="kominek">
 
−
 
−
(参考文献名称“ kominek”)
 
−
 
−
John Kominek.
 
−
 
−
John Kominek.
 
−
 
−
约翰 · 科米内克。
 
−
 
−
[https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf "Algorithm for Fast Fractal Image Compression"].
 
−
 
−
[https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf "Algorithm for Fast Fractal Image Compression"].
 
−
 
−
Https://pdfs.semanticscholar.org/d77b/ffac2560c92771d3756c0e29863a44919d6f.pdf 的“快速分形图像压缩算法”。
 
−
 
−
{{doi|10.1117/12.206368}}.
 
−
 
−
.
 
−
 
−
.
 
−
 
−
</ref><ref name="lacroix"/>
 
−
 
−
</ref>
 
−
 
−
/ 参考
 
−
 
−
 
−
 
−
As of 1995, all [[fractal compression]] software is based on Jacquin's approach.<ref name="kominek"/>
 
−
 
−
As of 1995, all fractal compression software is based on Jacquin's approach.
 
−
 
−
截至1995年，所有的分形压缩软件都是基于 Jacquin 的方法。
 
−
 
−
 
−
 
−
==Examples==
 
−
 
−
The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the [[Hutchinson operator]]. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal.
 
−
 
−
The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the Hutchinson operator. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal.
 
−
 
−
该图展示了由两个仿射函数构造 IFS 的过程。函数通过它们对双单元正方形的影响来表示(函数将轮廓的正方形转换为阴影的正方形)。这两个函数的组合形成了哈钦森算子。算子的三次迭代被显示出来，然后最终的图像是不动点的，最终的分形。
 
−
 
−
 
−
 
−
Early examples of fractals which may be generated by an IFS include the [[Cantor set]], first described in 1884; and [[de Rham curve]]s, a type of self-similar curve described by [[Georges de Rham]] in 1957.
 
−
 
−
Early examples of fractals which may be generated by an IFS include the Cantor set, first described in 1884; and de Rham curves, a type of self-similar curve described by Georges de Rham in 1957.
 
−
 
−
由 IFS 产生的分形的早期例子包括 Cantor 集，第一次描述是在1884年; 和 de Rham 曲线，一种自相似曲线，由 Georges de Rham 在1957年描述。
 
−
 
−
 
−
 
−
==History==
 
−
 
−
IFSs were conceived in their present form by [[John E. Hutchinson]] in 1981<ref>{{cite journal |last=Hutchinson |first=John E. |title=Fractals and self similarity |journal=Indiana Univ. Math. J. |volume=30 |year=1981 |pages=713–747 |doi=10.1512/iumj.1981.30.30055 |url=http://wwwmaths.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf |issue=5}}</ref> and popularized by [[Michael Barnsley]]'s book ''Fractals Everywhere''. <!-- In 1992 [[Scott Draves]] developed the [[Fractal flame]] algorithm.-->
 
−
 
−
IFSs were conceived in their present form by John E. Hutchinson in 1981 and popularized by Michael Barnsley's book Fractals Everywhere. <!-- In 1992 Scott Draves developed the Fractal flame algorithm.-->
 
−
 
−
1981年，约翰 · e · 哈钦森以现在的形式构思了 IFSs，并由迈克尔 · 巴恩斯利的著作《分形无处不在》而流行开来。! ——1992年斯科特 · 德拉维斯发明了分形火焰算法
 
−
 
−
 
−
 
−
{{Quote|IFSs provide models for certain plants, leaves, and ferns, by virtue of the self-similarity which often occurs in branching structures in nature.|Michael Barnsley ''et al.''<ref name=V-variable>[[Michael Barnsley]], ''et al.'',{{cite web |url= http://www.maths.anu.edu.au/~barnsley/pdfs/V-var_super_fractals.pdf |title=V-variable fractals and superfractals}}&nbsp;{{small|(2.22&nbsp;MB)}}</ref>}}
 
−
 
−
 
−
 
−
==See also==
 
−
 
−
{{Portal|Mathematics}}
 
−
 
−
*[[Complex-base system#Base .E2.88.921.C2.B1i|Complex-base system]]
 
−
 
−
*[[Collage theorem]]
 
−
 
−
*[[Infinite compositions of analytic functions]]
 
−
 
−
*[[L-system]]
 
−
 
−
*[[Fractal compression]]
 
−
 
−
 
−
 
−
==Notes==
 
−
 
−
{{Reflist|30em}}
 
−
 
−
 
−
 
−
==References==
 
−
 
−
*{{cite web |last=Draves |first=Scott |authorlink=Scott Draves |author2=Erik Reckase |date=July 2007 |url=http://flam3.com/flame.pdf |title=The Fractal Flame Algorithm |format=pdf |accessdate=2008-07-17 |archive-url=https://web.archive.org/web/20080509073421/http://flam3.com/flame.pdf |archive-date=2008-05-09 |url-status=dead }}
 
−
 
−
*{{cite book |last=Falconer |first=Kenneth |authorlink=Kenneth Falconer (mathematician) |title=Fractal geometry: Mathematical foundations and applications |url=https://archive.org/details/fractalgeometrym0000falc/page/113 |url-access=registration |publisher=John Wiley and Sons |year=1990 |isbn=0-471-92287-0 |pages=[https://archive.org/details/fractalgeometrym0000falc/page/113 113–117, 136] }}
 
−
 
−
*{{cite journal |last=Barnsley |first=Michael |authorlink=Michael Barnsley |author2=Andrew Vince |arxiv=1005.0322 |title=The Chaos Game on a General Iterated Function System |journal=Ergodic Theory Dynam. Systems |volume=31 |year=2011 |issue=4 |pages=1073–1079|bibcode=2010arXiv1005.0322B }}
 
−
 
−
*'''For an historical overview, and the generalization :''' {{cite journal |first=Claire|last=David  |  |title=fractal properties of Weierstrass-type functions |journal=Proceedings of the International Geometry Center |volume=12 |year=2019 |issue=2 |pages=43-61|url=https://journals.onaft.edu.ua/index.php/geometry/article/view/1485 }}
 
−
 
−
 
−
 
−
{{Fractal software}}
 
−
 
−
{{Fractals}}
 
−
 
−
 
−
 
−
{{DEFAULTSORT:Iterated Function System}}
 
−
 
−
[[Category:Iterated function system fractals| ]]
 
−
 
−
[[Category:1981 introductions]]
 
  
 
Category:1981 introductions
 
Category:1981 introductions

2020年10月25日 (日) 20:55的版本

此词条暂由彩云小译翻译，翻译字数共213，未经人工整理和审校，带来阅读不便，请见谅。

文件:Sierpinski1.png
Sierpinski triangle created using IFS (colored to illustrate self-similar structure)

Sierpinski triangle created using IFS (colored to illustrate self-similar structure)

[[使用 IFS 创建的谢尔宾斯基三角形(着色以说明自相似结构)]

Colored IFS designed using Apophysis software and rendered by the Electric Sheep.

Apophysis software and rendered by the Electric Sheep.]]

[软件，并由电子羊渲染]

In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry.[1] They were introduced in 1981.

In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry. give surprisingly good image compression, even for photographs that don't seem to have the kinds of self-similar structure shown by simple IFS factals.

在数学中，迭代函数系统是构造分形的一种方法; 由此产生的分形通常是自相似的。与分形几何相比，IFS 分形与集合论的关系更大。给出惊人的好图像压缩，即使对于那些似乎没有简单的 IFS 面形所显示的自相似结构的照片也是如此。


IFS fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the Sierpiński triangle. The functions are normally contractive, which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, ad infinitum. This is the source of its self-similar fractal nature.

As of 1995, all fractal compression software is based on Jacquin's approach.

截至1995年，所有的分形压缩软件都是基于 Jacquin 的方法。


Definition

Formally, an iterated function system is a finite set of contraction mappings on a complete metric space.[2] Symbolically,

The diagram shows the construction on an IFS from two affine functions. The functions are represented by their effect on the bi-unit square (the function transforms the outlined square into the shaded square). The combination of the two functions forms the Hutchinson operator. Three iterations of the operator are shown, and then the final image is of the fixed point, the final fractal.

该图展示了由两个仿射函数构造 IFS 的过程。函数通过它们对双单元正方形的影响来表示(函数将轮廓的正方形转换为阴影的正方形)。这两个函数的组合形成了哈钦森算子。算子的三次迭代被显示出来，然后最终的图像是不动点的，最终的分形。

[math]\displaystyle{ \{f_i:X\to X\mid i=1,2,\dots,N\},\ N\in\mathbb{N} }[/math]

is an iterated function system if each [math]\displaystyle{ f_i }[/math] is a contraction on the complete metric space [math]\displaystyle{ X }[/math].

Early examples of fractals which may be generated by an IFS include the Cantor set, first described in 1884; and de Rham curves, a type of self-similar curve described by Georges de Rham in 1957.

由 IFS 产生的分形的早期例子包括 Cantor 集，第一次描述是在1884年; 和 de Rham 曲线，一种自相似曲线，由 Georges de Rham 在1957年描述。


Properties

Construction of an IFS by the chaos game (animated)

IFSs were conceived in their present form by John E. Hutchinson in 1981 and popularized by Michael Barnsley's book Fractals Everywhere.

1981年，约翰 · e · 哈钦森以现在的形式构思了 IFSs，并由迈克尔 · 巴恩斯利的著作《分形无处不在》而流行开来。1992年，斯科特 · 德拉维斯发明了分形火焰算法

IFS being made with two functions.

Hutchinson (1981) showed that, for the metric space [math]\displaystyle{ \mathbb{R}^n }[/math], or more generally, for a complete metric space [math]\displaystyle{ X }[/math], such a system of functions has a unique nonempty compact (closed and bounded) fixed set S. One way of constructing a fixed set is to start with an initial nonempty closed and bounded set S0 and iterate the actions of the fi, taking Sn+1 to be the union of the images of Sn under the fi; then taking S to be the closure of the union of the Sn. Symbolically, the unique fixed (nonempty compact) set [math]\displaystyle{ S\subseteq X }[/math] has the property

[math]\displaystyle{ S = \overline{\bigcup_{i=1}^N f_i(S)}. }[/math]

The set S is thus the fixed set of the Hutchinson operator [math]\displaystyle{ F: 2^X\to 2^X }[/math] defined for [math]\displaystyle{ A\subseteq X }[/math] via

[math]\displaystyle{ F(A)=\overline{\bigcup_{i=1}^N f_i(A)}. }[/math]


The existence and uniqueness of S is a consequence of the contraction mapping principle, as is the fact that

[math]\displaystyle{ \lim_{n\to\infty}F^{\circ n}(A)=S }[/math]

for any nonempty compact set [math]\displaystyle{ A }[/math] in [math]\displaystyle{ X }[/math]. (For contractive IFS this convergence takes place even for any nonempty closed bounded set [math]\displaystyle{ A }[/math]). Random elements arbitrarily close to S may be obtained by the "chaos game," described below.


Recently it was shown that the IFSs of noncontractive type (i.e. composed of maps that are not contractions with respect to any topologically equivalent metric in X) can yield attractors.

These arise naturally in projective spaces, though classical irrational rotation on the circle can be adapted too.[3]


The collection of functions [math]\displaystyle{ f_i }[/math] generates a monoid under composition. If there are only two such functions, the monoid can be visualized as a binary tree, where, at each node of the tree, one may compose with the one or the other function (i.e. take the left or the right branch). In general, if there are k functions, then one may visualize the monoid as a full k-ary tree, also known as a Cayley tree.


Constructions

Barnsley's fern, an early IFS
Menger sponge, a 3-Dimensional IFS.
IFS "tree" constructed with non-linear function Julia
文件:Golden Square fractal with T-branching 8.svg
Golden squares with T-branching

{{multiple image 

| align = 

| direction = horizontal

| width = 150

| header = 

| image1 = Golden Square fractal 6.svg

Category:1981 introductions

类别: 1981年引言


This page was moved from wikipedia:en:Iterated function system. Its edit history can be viewed at 迭代函数系统/edithistory

  1. ↑ Zobrist, George Winston; Chaman Sabharwal (1992). Progress in Computer Graphics: Volume 1. Intellect Books. p. 135. ISBN 9780893916510. https://play.google.com/store/books/details?id=Ai6Qo0qoE9EC. Retrieved 7 May 2017. 
  2. ↑ Michael Barnsley (1988). Fractals Everywhere, p.82. Academic Press, Inc.
    .
  3. ↑ M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System
取自“https://wiki.swarma.org/index.php?title=迭代函数系统&oldid=16932”