迭代函数系统和自相似分形
5.00/5 (14投票s)
构建广泛分形家族的简单方法
引言
在本文中，我将展示如何使用一组少数的收缩仿射变换来生成可以近似现实世界对象的 the fractals。迭代函数系统（IFS）是由 **M.F. Barnsley** 于 1985 年开发的一种方法，并且是某些图像压缩方法的基础。
我开发了一个简单的桌面应用程序来演示使用此方法构建分形的两个基本算法。IFSDrawer 解决方案使用 Visual Studio 2015 以 C# 编写。
背景
平面上的点仿射变换是一种形式为
当然，这可以扩展到多于二维的空间，但我们将处理二维点。
通过 **e** 和 **f** 系数，我们可以沿水平和垂直方向移动点。
当 **b** 和 **c** 系数的值为零时，**x** 和 **y** 坐标乘以系数 **a** 和 **d**。这可以用来放大或缩小图形，并且可以通过为这些系数赋予负值来创建水平和/或垂直对称性。
另一方面，如果您将 **a** 和 **d** 的值设为零，则可以使用 **b** 和 **c** 系数来交换 **x** 和 **y** 坐标。
通过将系数设为 **a=cosϕ**, **b=-sinϕ**, **c=sinϕ** 和 **d=cosϕ**，您可以将图形的点旋转一个角度 **ϕ**。
您可以通过计算其矩阵的乘积来组合各种变换。
IFS 只是 n 个仿射变换的集合，您将它们迭代应用于给定的点或点集，创建一个收敛于分形集的序列，该分形集是系统的吸引子。变换必须是收缩的，这意味着系数必须在 0 和 1 之间。
有两种基本算法。使用确定性算法，您开始将 n 个变换应用于任意点集，获得 n 个变换后的集合。您一遍又一遍地将 n 个变换迭代应用于前一步获得的所有集合。在第 k 步，您有 n^k 个变换后的集合。当您绘制这些集合时，您可以看到所有集合的并集如何收敛到系统的吸引子——一个自相似分形。通常您不需要超过 10 次迭代。
在随机算法中，您只将系统的一个函数应用于单个点。所有函数都有一个分配的概率，所有函数的总和为 1。在每次迭代中，您取一个介于 0 和 1 之间的随机数，然后依次累加每个函数的概率，直到结果大于此随机数，则选择相应的函数并将其应用于该点，依此类推，通常进行大量次数，约 10000 次或更多。
使用应用程序
一旦启动 **IFSDrawer** 应用程序，您可以使用工具栏中的第二个按钮打开应用程序 **Samples** 文件夹中的一个示例文件。打开 **Sierpinski.ifs** 文件以查看确定性算法的示例。
在开始处理之前，您必须使用工具栏中的最后一个按钮来检查网格中每行系数定义的各种变换的值。最后一列 **P** 用于在算法的随机版本中定义概率。将其留空以使用算法的确定性版本。
在右侧，有一个列表框，您可以在其中选择一个形状来应用确定性算法。然后，您可以使用工具栏中间带有绿色箭头的按钮，逐步迭代系统。
该网格允许在单元格中定义公式，因此您不必使用计算器。有关公式语法的更多信息，请参阅本文（此处为西班牙语）。在此项目中，我添加了常量 **_pi**、**_e**（分别代表 pi 和 e），**_rand**（生成 0 到 1 之间的随机数），以及 **_width** 和 **_height**（分别为当前绘图的宽度和高度）。
您可以使用工具栏右侧的另外两个按钮添加新变换或删除选定的行。工具栏左侧的按钮分别用于清除所有内容、打开文件、将变换保存到文件、将图像保存到文件以及将图像复制到剪贴板。
随机算法的控件略有不同。例如，打开 **Leaf.ifs** 文件并单击检查按钮。
现在，在工具栏中间，有两个文本框，您可以在其中设置算法的迭代次数以及最终绘图的缩放因子。而不是逐步进行，因为迭代次数很多，当您按下带有两个绿色箭头的按钮时，将完成所有迭代。
使用代码
应用程序的代码分为四个项目。**BNFUP** 项目是表达式编译器。您可以在本文（此处为西班牙语）中了解更多关于它的信息。**GridFormulas** 项目是网格数学公式的实现，而 **FormulaDataGridView** 是 DataGridView 控件的实现。
应用程序本身在 **IFSDrawer** 项目中。这是用于存储每个仿射变换的 **Transformation** 类。
[Serializable]
public class Transformation
{
public Transformation()
{
}
public object A { get; set; }
public object B { get; set; }
public object C { get; set; }
public object D { get; set; }
public object E { get; set; }
public object F { get; set; }
public object P { get; set; }
public double AValue
{
get
{
if (A == null)
{
return double.NaN;
}
if (A is FormulaBase)
{
return (A as FormulaBase).Value;
}
return (double)A;
}
}
public double BValue
{
get
{
if (B == null)
{
return double.NaN;
}
if (B is FormulaBase)
{
return (B as FormulaBase).Value;
}
return (double)B;
}
}
public double CValue
{
get
{
if (C == null)
{
return double.NaN;
}
if (C is FormulaBase)
{
return (C as FormulaBase).Value;
}
return (double)C;
}
}
public double DValue
{
get
{
if (D == null)
{
return double.NaN;
}
if (D is FormulaBase)
{
return (D as FormulaBase).Value;
}
return (double)D;
}
}
public double EValue
{
get
{
if (E == null)
{
return double.NaN;
}
if (E is FormulaBase)
{
return (E as FormulaBase).Value;
}
return (double)E;
}
}
public double FValue
{
get
{
if (F == null)
{
return double.NaN;
}
if (F is FormulaBase)
{
return (F as FormulaBase).Value;
}
return (double)F;
}
}
public double PValue
{
get
{
if (P == null)
{
return double.NaN;
}
if (P is FormulaBase)
{
return (P as FormulaBase).Value;
}
return (double)P;
}
}
}
**A**、**B** 等属性是 object 类型，因为它们可以包含 double 值或 FormulaBase 对象。您可以通过 **AValue**、**BValue** 等属性获取它们转换为 double 的值。此类仅用于存储数据，不具备功能。
所有形状类都继承自抽象基类 **ShapeBase**。
public abstract class ShapeBase
{
protected GraphicsPath _path;
protected bool _fill = false;
public ShapeBase()
{
}
public ShapeBase(ShapeBase clon, Transformation tr)
{
_path = clon._path.Clone() as GraphicsPath;
Transform(tr);
}
public abstract void SetInitialSize(SizeF sz);
public virtual ShapeBase Draw(Graphics gr, Transformation tr)
{
if (tr != null)
{
ShapeBase snw = GetType().GetConstructor(new Type[] { typeof(ShapeBase), tr.GetType() }).Invoke(new object[] { this, tr }) as ShapeBase;
snw.Draw(gr);
return snw;
}
else
{
Draw(gr);
return this;
}
}
protected virtual void Transform(Transformation tr)
{
Matrix m = new Matrix((float)tr.AValue, (float)tr.BValue, (float)tr.CValue, (float)tr.DValue, (float)tr.EValue, (float)tr.FValue);
_path.Transform(m);
}
protected virtual void Draw(Graphics gr)
{
if (_path != null)
{
if (_fill)
{
gr.FillPath(Brushes.Black, _path);
}
else
{
gr.DrawPath(Pens.Black, _path);
}
}
}
}
带参数的构造函数用于创建给定形状的副本并对其应用给定的变换。
图形存储在 **GraphicsPath** 对象中，变量为 **_path**，并在 **SetInitialSize** 方法中创建，该方法所有形状都必须重写并实现。
公共 **Draw** 方法将变换应用于形状，并将其绘制在给定的 **Graphics** 对象中。它返回一个变换后的自身副本。
例如，这是三角形形状的实现。
public class EquilateralTriangle : ShapeBase
{
public EquilateralTriangle() : base()
{
}
public EquilateralTriangle(ShapeBase clon, Transformation tr) : base(clon, tr)
{
}
public override void SetInitialSize(SizeF sz)
{
float szm = Math.Min(sz.Width, sz.Height);
PointF p1 = new PointF(0f, 0f);
PointF p2 = new PointF(-szm * (float)Math.Cos(2 * Math.PI / 3), szm * (float)Math.Sin(2 * Math.PI / 3));
PointF p3 = new PointF(szm, 0f);
_path = new GraphicsPath();
_path.AddLine(p1, p2);
_path.AddLine(p2, p3);
_path.AddLine(p3, p1);
}
public override string ToString()
{
return "Equilateral Triangle";
}
}
public class FilledEquilateralTriangle : EquilateralTriangle
{
public FilledEquilateralTriangle() : base()
{
_fill = true;
}
public FilledEquilateralTriangle(ShapeBase clon, Transformation tr) : base(clon, tr)
{
_fill = true;
}
public override string ToString()
{
return "Filled " + base.ToString();
}
}
您必须实现的唯一方法是 **SetInitialSize**（用于创建图形）和重写 **ToString**（用于在形状列表框中显示其名称）。
确定性算法实现在 **bStep** 按钮的点击事件处理程序中。
private void bStep_Click(object sender, EventArgs e)
{
try
{
// New generation of shapes
List<ShapeBase> lnw = new List<ShapeBase>();
// Create the bitmap
int hv = Math.Min(pbDraw.Size.Width, pbDraw.Size.Height);
Bitmap bmp = new Bitmap(hv + 1, hv + 1);
Graphics gr = Graphics.FromImage(bmp);
gr.FillRectangle(Brushes.White, new Rectangle(0, 0, hv + 1, hv + 1));
// Process all shapes
foreach (ShapeBase sh in _lShapes)
{
// Apply every function to each shape
foreach (Transformation t in _ifs)
{
// Add new generated shape
lnw.Add(sh.Draw(gr, t));
}
}
_lShapes = lnw;
Bitmap oldimg = pbDraw.Image as Bitmap;
bmp.RotateFlip(RotateFlipType.RotateNoneFlipY);
pbDraw.Image = bmp;
if (oldimg != null)
{
oldimg.Dispose();
}
_step++;
lStep.Text = "Step " + _step.ToString();
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
lStep.Text = "";
bStep.Enabled = false;
}
}
正如您所见，这非常简单。处理形状列表，并将所有变换应用于每个形状，并将它们绘制在位图上。在每一步，都会创建一个新的形状生成，并替换前一个。
随机算法实现在 **bRandom** 按钮的点击事件处理程序中。
private void bRandom_Click(object sender, EventArgs e)
{
try
{
// Get parameter values
int iterations = 5000;
if (!int.TryParse(txtIterations.Text, out iterations))
{
MessageBox.Show("Integer no valid");
txtIterations.SelectAll();
txtIterations.Focus();
}
if (iterations < 100)
{
iterations = 100;
}
else if (iterations > 50000)
{
iterations = 50000;
}
txtIterations.Text = iterations.ToString();
float scale = 0f;
if (!float.TryParse(txtZoom.Text, out scale))
{
MessageBox.Show("Number not valid");
txtZoom.SelectAll();
txtZoom.Focus();
}
if (scale <= 0f)
{
scale = 1f;
}
txtZoom.Text = scale.ToString();
// Create the Bitmap
int hv = Math.Min(pbDraw.Size.Width, pbDraw.Size.Height);
Bitmap bmp = new Bitmap(hv + 1, hv + 1);
Graphics gr = Graphics.FromImage(bmp);
gr.FillRectangle(Brushes.White, new Rectangle(0, 0, hv + 1, hv + 1));
pbDraw.Image = bmp;
Random rnd = new Random();
// Point to iterate
PointF pt = new PointF(0f, 0f);
// Center of the image
Point pc = new Point(bmp.Width / 2, bmp.Height);
for (int ix = 0; ix < iterations; ix++)
{
double vr = rnd.NextDouble();
// Select a function according with the probabilities
Transformation t = _ifs[_ifs.Count - 1];
double p = _ifs[0].PValue;
for (int it = 0; it < _ifs.Count - 1; it++)
{
if (vr <= p)
{
t = _ifs[it];
break;
}
p += _ifs[it + 1].PValue;
}
// Transform the current point
float x = (float)(pt.X * t.AValue + pt.Y * t.BValue + t.EValue);
float y = (float)(pt.X * t.CValue + pt.Y * t.DValue + t.FValue);
pt = new PointF(x, y);
// Scale result
Point pp = new Point((int)(pt.X * scale), (int)(pt.Y * scale));
// Discard the first 10 iterations and points beyond the image
if ((ix > 10) && (pp.X + pc.X >= 0f) && (pc.Y - pp.Y >= 0f) && (pp.X + pc.X < bmp.Width) && (pc.Y - pp.Y < bmp.Height))
{
bmp.SetPixel(pp.X + pc.X, pc.Y - pp.Y, Color.Black);
}
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
bRandom.Enabled = false;
}
}
在这种情况下，每次使用相同的点，并且只选择一个函数来将变换应用于该点。概率用于选择应用。前 10 个点被丢弃，因为它们很有可能离吸引子太远。
这就是全部，感谢阅读！！！