分形火焰算法

The Fractal Flame Algorithm 

Scott Draves

Spotworks, NYC, USA

Erik Reckase

Berthoud, CO, USA

September 2003, Last revised November 2008

源文件:📎The Fractal Flame Algorithm★★★.pdf

 Abstract

The Fractal Flame algorithm is a member of the Iterated Function System (IFS) class of fractal algorithms. A two-dimensional IFS creates images by plotting the output of a chaotic attractor directly on the image

plane. The fractal flame algorithm is distinguished by three innovations over text-book IFS: non-linear functions, log-density display, and structural coloring. In combination with standard techniques of antialiasing and motion blur the result is striking image variety and quality.The guiding principle of the design of the algorithm is to expose and preserve as much of the information content of the attractor as possible. We found that preserving information maximizes aesthetics.


摘要

分形火焰算法是迭代函数系统(IFS)分形算法的一个成员。二维IFS通过直接在图像平面上绘制混沌吸引子的输出来生成图像。分形火焰算法与教科书IFS相比有三个创新点:非线性函数对数密度显示结构着色结合抗锯齿运动模糊的标准技术,结果是惊人的图像变化和质量。该算法设计的指导原则是尽可能多地显示和保存吸引子的信息内容。我们发现这些保存下来的信息充分呈现出美学特征。


Overview

Some examples appear in Figure 1. The paper begins by defining classic, linear iterated function systems and hence grounding our notation and terminology.

The classic formulation is then extended with non-linear variations in Section 3 and then further extended with post transforms and final transforms in Section 3.1. Section 4 describes how log-density display works and its importance, and Section 5 covers the coloring algorithm. These three sections cover the core innovations. Sections 6 and 8 explain other important properties of the implementation, and Section 7 shows how to create symmetric flames. The appendix is a catalog of the variations including formulas and examples.


1 概述

一些例子如图1所示。本文首先定义了经典的线性迭代函数系统,从而为我们的符号和术语奠定了基础。然后在第3节中用非线性变化扩展经典公式,然后在第3.1节中用变换最终变换进一步扩展。第4节介绍了日志密度显示的工作原理及其重要性,第5节介绍了着色算法。这三个部分涵盖了核心创新。第6节和第8节则解释其他重要属性的实现,第7节讲解如何创建对称的flame。附录是变体(variations)的总目录,包括了公式和例子。


Classic Iterated Function Systems

A two-dimensional Iterated Function System (IFS) is a finite collection of nfunctions Fi from R2 to R2. The solution of the system is the set S in R2 (and hence an image) that is the fixed point of Hutchinson’s recursive set equation [3]:


2 经典迭代函数系统

二维迭代函数系统(IFS)是从R2R2的关于n函数Fi的有限集合。系统的解是R2中的集合S(因此是图像),它是Hutchinson递推集合方程的不动点[3]:


MolyChin:在一个二维平面通过一个(通常是非线性的)函数映射来建立点到点的函数迭代。不同于Mandelbore集的作图方法(求吸引点【发散或收敛】的程度),分形火焰算法是迭代一定次数就画一个点,并且起步是一些(粒子密度)随机点。利用点的随机性来覆盖一个定义域和值域。而M集算法是通过设定的步长在一定定义域内计算每个点(的收敛性)。

 

 

Figure 1: Example fractal flame images. The names of these flames are: a) 206, b) 191, c) 4000, and d) 29140. These images were selected for their aesthetic properties.

图1:分形火焰图像的示例。这些火焰的名字是:A)206,B),191,C)4000,D)29140。这些图像之所以被选定是因为他们具有美学的特性

 

image.png 

Figure 2: Sierpinski’s Gasket, a simple IFS. X and y increase towards the lower right. The recursive【递归的】 structure is visible as the whole image is made up of three copies of itself, one for each function.

图2:谢尔宾斯基垫片,一个简单的IFS。 X和Y的增加朝向右下方。递归结构是可见的,整个图像是由三个对自身的拷贝构成,每个拷贝同使用同一个函数。

 

As implemented and popularized by Barnsley [1] the functions Fi are linear (technically they are affine as each is a two by three matrix capable of expressing scale, rotation, translation, and shear):

正如Barnsley[1]所实现和推广的那样,函数Fi是线性的(从技术上讲,它们是仿射的,因为每个函数都是一个二乘三矩阵,能够表示比例、旋转、平移和剪切):



For example, if the functions are

例如,如果函数是


then the fixed-point S is Sierpinski’s Gasket, as seen in Figure 2.

然后固定点S是Sierpinski的垫圈,如图2所示。


In order to facilitate the proofs and guarantee convergence of the algorithms, the functions are normally constrained to be contractive, that is, to bring points closer together. In fact, the normal algorithm works under the much weaker condition that the whole system is contractive on average. Useful guarantees of this become difficult to provide when the functions are non-linear. Instead we recommend using a numerically robust implementation, and simply accept that some parameter sets result in better images than others, and some result in degenerate images.


为了便于证明和保证算法的收敛性,通常将函数约束为可压缩的,即使点更接近。事实上,正规算法是在整个系统平均收缩的弱条件下工作的当函数为非线性时,很难提供这方面的有用保证。相反,我们建议使用一个数值稳健的实现,并且简单地接受一些参数集会产生比其他参数更好的图像,而一些参数集会导致退化图像。


The normal algorithm for solving for S is called the chaos game. In pseudocode it is:

求解S的一般算法称为混沌博弈。在伪码中,它是:

(x, y)= a random point in the bi-unit square
iterate {
i = a random integer from 0 to n − 1 inclusive
(x, y) = Fi(x, y)
plot(x, y) except during the first 20 iterations
}


20次迭代画一个点。


The bi-unit square are those points where x and y are both in [-1,1]. The chaos game works because if (x, y) ∈ S then Fi(x, y) ∈ S too. Though we start out with a random point, because the functions are on average contractive the distance between the solution set and the point decreases exponentially. After 20 iterations with a typical contraction factor of 0.5 the point will be within 10−6 of the solution, much less than a pixel’s width. Every point of the solution set will be generated eventually because an infinite string of random symbols (the choices for i) contains every finite substring of symbols. This is explained in more formally in Section 4.8 of [1]. No sufficient number of iterations is given by the algorithm. Because the chaos game operates by stochastic sampling, the more iterations one makes the closer the result will be to the exact solution. The judgement of how close is close enough remains for the user. In fractal flames, the number of samples is specified with the more abstract parameter quality, or samples per output pixel. That way the image quality (in the sense of lack of noise) remains constant in face of changes to the image resolution and the camera. It is useful to be able to weight the functions so they are not chosen with equal frequency in line 3 of the chaos game. We assign a weight, or relative probability wi to each function Fi. This allows interpolation between function systems with different numbers of functions: the additional functions can be phased in by starting their weights at zero. Differently weighted functions are also necessary to draw symmetric flames as shown in Section 7. Some implementations of the chaos game make each function’s weight proportional to its contraction factor. When drawing one-bit per pixel images this has the advantage of converging faster than equal weighting because it avoids redrawing pixels. But in our context with mutiple bits per pixel and non-linear functions (where the contraction factor is not constant) this device is best avoided.


混沌博弈之所以有效,是因为如果(x,y)∈S,那么Fi(x,y)∈S也是。虽然我们从一个随机点开始,但由于函数是平均压缩的,所以解集和点之间的距离呈指数递减。经过20次迭代,典型的收缩因子为0.5,该点将在解的10-6范围内,远小于像素的宽度。解集的每个点最终都会被生成,因为无限长的随机符号串(i的选择)包含符号的每个有限子串。这在[1]第4.8节中有更正式的解释。算法没有给出足够的迭代次数。由于混沌博弈是随机抽样的,迭代次数越多,结果越接近精确解。用户仍然可以判断离得有多近。在分形火焰中,采样数由更抽象的参数质量(即每个输出像素的采样数)指定。这样,在图像分辨率和相机发生变化时,图像质量(在没有噪声的情况下)保持不变。在混沌博弈的第3行中,能够对函数进行加权是很有用的,这样它们就不会以相同的频率被选择。我们给每个函数Fi分配一个权重或相对概率wi。这允许在具有不同数量功能的功能系统之间进行插值:附加功能可以通过将其权重从零开始逐步引入。如第7节所示,绘制对称火焰也需要不同的加权函数。混沌博弈的一些实现使得每个函数的权重与其压缩因子成正比。当绘制每像素一位的图像时,它的优点是收敛速度快于等权重,因为它避免了重绘像素。但在我们的背景下,每像素多比特和非线性函数(其中压缩因子不是恒定的)这个设备是最好的避免。



3 Variations

We now generalize this algorithm. The first step is to use a larger class offunctions than just affine functions. Start by composing a non-linear functionVj from R2to R2 with the affine functions:


3 变体

我们现在推广这个算法。第一步是使用比仿射函数更大的函数类。首先用仿射函数组成一个从R2到R2的非线性函数vj:


We call each such function Vj a variation, and each one changes the shape and character of the solution in a recognizable way. The initial variations were simple remappings of the plane. They were followed by dependent variations, where the coefficients of the affine transform define the behaviour of the variation. More recently, parametric variations have been introduced, which are variations controlled by additional parameters independent of the affine transform. Appendix A documents 49 variations. Variation 0 is the identity function. It and six more examples are:


我们称每一个这样的函数Vj为变量,每一个函数都以可识别的方式改变解的形状和特征。最初的变化是平面的简单翻版。随后是相关变化,其中仿射变换的系数定义了变化的行为。最近,参数变化被引入,它是由独立于仿射变换的附加参数控制的变化。附录A记录了49项变体。变量0是标识函数。它和另外六个例子是:

image.png


where

An example of a dependent variation is Popcorn, V17, which is dependent on the c and f coefficients of the affine transform. The PDJ variation, V24, is an example of a parametric variation. PDJ relies on four external parameters (p1, p2, p3, p4) to fully characterize its behaviour. Variations can be further generalized by replacing the integer parameter j with a blending vector vij with one coefficient per variation. Then


依赖变异的一个例子是爆米花V17,它依赖于仿射变换的c和f系数。PDJ变量V24是参数变量的一个例子。PDJ依赖于四个外部参数(p1、p2、p3、p4)来完全描述其行为。通过将整数参数j替换为混合向量vij(每个变量一个系数),可以进一步推广变量。那么


With this generalization, if are n functions, then there are 87n parameters that specify it. The parameters consist of 49n variational coefficients vij, 31n parametric coefficients, 6n matrix coefficients ai through fi, and n weights wi. Significantly fewer parameters are required, however, if unused parameters are assumed to be 0.  


有了这个泛化,如果是n个函数,那么就有87n个参数指定它。参数包括49n个变分系数vij、31n个参数系数、6n个矩阵系数ai-through-fi和n个权重wi。但是,如果假定未使用的参数为0,则需要的参数要少得多。


3.1 Post Transforms  

To this point, applying a transform to a set of coordinates involves first applying an affine transformation to the coordinates, and then applying a non-linear variation function to the result of the affine transformation. We further generalize this with the addition of a secondary affine transformation, a post transform, to be applied after the non-linear function. This provides the ability to change the coordinate systems of the variations. If the post transform is

then we redefine the Fi as follows:


3.1转换后

在这一点上,对一组坐标应用变换首先需要对坐标应用仿射变换,然后对仿射变换的结果应用非线性变化函数。我们进一步推广这一点,在非线性函数之后加上一个二次仿射变换,一个后变换。这提供了更改变量坐标系的能力。如果后转换是

然后我们将Fi重新定义如下:

3.2 Final Transforms

We can now introduce the concept of a final transform, which is an additional function Ff inal(x, y) that is always applied regardless of the value of i in the iteration loop. The final transform is like a non-linear camera. The result of the application of the final transform function is not ‘in the loop’, and there can be only one final transform per flame. The final transform can have a post transform associated with it. In pseudocode, we now have:


3.2最终转换

现在,我们可以引入最终变换的概念,它是一个附加函数,无论迭代循环中i的值是多少,它总是被应用。最后的变换就像一个非线性相机。应用最终变换函数的结果不是“在循环中”,每个火焰只能有一个最终变换。最后的转换可以有一个与之关联的后转换。在伪代码中,我们现在有:


(x, y)= a random point in the bi-unit square
iterate {
i = a random integer from 0 to n − 1 inclusive
(x, y) = Fi(x, y)
(xf, yf) = Ff inal(x, y)
plot (xf, yf) except during the first 20 iterations
}


Adding the post transforms to the earlier parameter count, we now have 93nparameters necessary to fully specify n functions. If a final transform is desired,then the total number of parameters necessary is 93(n + 1).


将post转换添加到前面的参数计数中,现在有93n个参数需要完全指定n个函数。如果需要最终转换,则所需的参数总数为93(n+1)。


4 Log-Density Display

The chaos game produces a series of (x, y) points which are plotted on the image plane. The collection of these points approximates the solution S to the iterated function system. S is a subset of the plane, and hence membership is a binary function, and the image is therefore black and white, lacking even shades of gray. See Figure 3a for an example. Information is lost every time we plot a point that has already been plotted. A more interesting image can be produced if we render a histogram of the chaotic process, that is, increment a counter at each pixel instead of merely plotting. These counters can be visualized by mapping them to shades of gray or by using a color-map that represents different densities (larger count values are more dense) with different colors. A linear mapping of counters to gray values results in Figure 3b. The result is unsatisfying because of the large dynamic range of densities. Like many natural systems, the densities are often distributed according to a power law (frequency is proportional to an exponent of the value). Figure 4 has two histograms demonstrating this. The densest points are much denser than the average density, hence with a linear map most of the image is very dark, and information is lost. The flame algorithm addresses the problem by using a logarithmic map from density to brightness. See Figure 3c for the result. The logarithm allows one to visually distinguish between, for example, densities of 3,000 and 5,000 in one part of the image and 30 and 50 in another part.


4 对数密度显示

混沌游戏产生一系列(x,y)点,这些点被绘制在图像平面上。这些点的集合近似于迭代函数系统的解S。S是平面的子集,因此隶属度是一个二元函数,因此图像是黑白的,缺少均匀的灰度。示例见图3a。每次我们绘制已经绘制的点时,都会丢失信息。如果我们呈现一个混沌过程的直方图,即在每个像素处增加一个计数器,而不是仅仅绘制,则可以生成更有趣的图像。这些计数器可以通过将它们映射到灰度或使用表示不同密度(较大的计数值更密集)的不同颜色的颜色映射来可视化。计数器与灰度值的线性映射如图3b所示。由于密度的动态范围较大,结果不令人满意。与许多自然系统一样,密度通常根据幂律分布(频率与值的指数成正比)。图4有两个柱状图说明了这一点。最密集的点比平均密度要密集得多,因此使用线性地图时,大部分图像都很暗,信息丢失。火焰算法通过使用从密度到亮度的对数映射来解决这个问题。结果见图3c。对数允许人们视觉上区分,例如,图像的一部分密度为3000和5000,另一部分密度为30和50。


image.png

Figure 3: Successive refinements of the rendering technique starting with a) binary membership, then b) linear, c) logarithmic, d) with color, e) with gamma factor, and finally f) with vibrant colors. The parameters to create this image are given in Appendix B.

图3:从a)二进制成员关系,然后b)线性,c)对数,d)用颜色,e)用伽玛系数,最后f)用鲜艳的颜色开始,对渲染技术进行了连续改进。 附录B中提供了用于创建此映像的参数。


image.png

Figure 4: Plots showing that the distribution of densities in an IFS follows the power law. The density (on the horizontal axis) is the number of hits by the system in a pixel, the frequency (on the vertical axis) is the number of pixels with that density (or up to the next power of two). The line is from the image in Figure 3, the other is the composite of 19 old, favorite systems including Figure 3. In each case, after a plateau the graph is nearly a straight line in log-log space. This is the definitive characteristic of a power law distribution. Each image was computed with 9.2e6 samples on a 900x900 grid.

图4:显示IFS中密度分布遵循幂律的曲线图。密度(在水平轴上)是系统在一个像素中的命中次数频率(在垂直轴上)是具有该密度的像素的数目(或者达到两个下一个功率)。这条线来自图3中的图像,另一条是19个旧的、最喜欢的系统的组合,包括图3。在每种情况下,在一个平台之后,图在对数空间中几乎是一条直线。这是幂律分布的决定性特征。每张图像在900x900网格上用9.2e6个样本计算。


The display of high dynamic range images like these by tone mapping is studied in computer graphics [4]. The logarithm used here (combined with the gamma factor, described below) is just an ad-hoc tone-map. This log-density mapping is the source of a 3D illusion. On sight people often guess that fractal flames are rendered in 3D, but as just described the algorithm works strictly with a 2D buffer. However, where one branch of the fractal crosses another, one may appear to occlude the other if their densities are different enough because the lesser density is inconsequential in sum. For example branches of densities 1000 and 100 might have brightnesses of 30 and 20. Where they cross the density is 1100, whose brightness is 30.4, which is hardly distinguishable from 30.  


在计算机图形学中研究了通过色调映射显示此类高动态范围图像的方法[4]。这里使用的对数(结合下面描述的伽马因子)只是一个特别的音调图。这种对数密度映射是三维幻觉的来源。人们经常猜测分形火焰是在3D中渲染的,但正如刚才所描述的那样,该算法严格使用2D缓冲区。然而,当分形的一个分支交叉于另一个分支时,如果它们的密度相差足够大,则其中一个分支可能看起来会遮挡另一个分支,因为较小的密度在总和上是无关紧要的。例如,密度为1000和100的分支的亮度可以是30和20。它们穿过的密度是1100,亮度是30.4,很难与30区分开来。


5 Coloring  

There is more information to be wrung from the attractor. In particular, which parts of the attractor come from which functions? The flame algorithm uses color to convey this. The result is a substantial aesthetic improvement. Color could be assigned according to the density map and although the result is increased visibility of the densities relative to grayscale, the internal structure of the fractal remains opaque. Furthermore, for animation the eye prefers that the color of each part of the attractor remain unchanged over time, otherwise the illusion of an object in motion is compromised. The fractal flame algorithm uses an original means to accomplish this: adding a third coordinate to the iteration. Naturally we want to use a palette or color-map which we define as a function from [0,1] to (r,g,b) where r, g, and b are in [0,1]. A palette is classically specified with an array of 256 triples of bytes. To achieve this we assign a color ci to each function Fi (and a corresponding cf inal if a final transform is present) and add an independent coordinate to the chaos game:


5 着色

吸引子里还有更多的信息。特别是吸引子的哪些部分来自哪些函数?flame算法使用颜色来传达这一点。结果是美感有了实质性的提高。可以根据密度图指定颜色,尽管结果是密度相对于灰度的可见性增加,但分形的内部结构仍然不透明。此外,对于动画,眼睛希望吸引子的每个部分的颜色随时间保持不变,否则运动对象的幻觉会受到损害。分形火焰算法使用一种原始的方法来实现这一点:在迭代中添加第三个坐标。当然,我们希望使用调色板或彩色地图,我们将其定义为从[0,1]到(r,g,b)的函数,其中r,g,b在[0,1]中。调色板是由256个三倍字节的数组经典地指定的。为了实现这一点,我们为每个函数Fi分配一个颜色ci(如果存在最终变换,则为相应的最终变换),并为混沌游戏添加一个独立的坐标:


(x, y)= a random point in the bi-unit square
c = a random point in [0,1]
iterate {
i = a random integer from 0 to n − 1 inclusive
(x, y) = Fi(x, y)
c = (c + ci)/2
(xf , yf) = Ffinal(x, y)
cf = (c + cfinal)/2
plot (xf , yf , cf) except during the first 20 iterations
}


This has the important property that the most recently applied function akes the largest difference in the color index and also in spatial location.
Indices make less difference as they recede in time. Hence colors are continuous in the final image.

Color plotting is naturally implemented by keeping three counters per pixel instead of one, and adding the current color to the three of them instead of incrementing a single density counter. That is not enough information for proper logdensity display, however. Taking the logarithm of each channel independently grossly alters the colors. Instead one must add a fourth channel of so-called alpha (α), or transparency values. So then to plot a point the color is added to the three color channels, and 1 is added to the alpha channel. After all the samples have been accumulated each channel is scaled by log α/α. See Figure 3d for the result. The resulting alpha values can be output with the image if the file format supports them, or they can be used for compositing the fractal with a background immediately, or they can be discarded.


这具有一个重要的特性,即最近应用的函数在颜色索引和空间位置上的差异最大。数随着时间的推移变化不大。因此,颜色在最终图像中是连续的。

自然地,彩色绘图是通过每像素保留三个计数器而不是一个,并将当前颜色添加到三个计数器而不是增加一个密度计数器来实现的。但是,这还不足以显示正确的日志密度。独立地取每个通道的对数会严重地改变颜色。相反,必须添加第四个通道,即所谓的alpha(α)或透明度值。因此,要绘制点,颜色将添加到三个颜色通道,1将添加到alpha通道。所有样本累积后,每个通道按logα/α缩放。结果见图3d。如果文件格式支持,生成的alpha值可以与图像一起输出,也可以用于立即将分形与背景合成,或者可以将其丢弃。


6 The Gamma Factor

Accurate display of any digital image on a Cathode Ray Tube (CRT) requires gamma correction to account for the non-linear response of screen phosphors to voltage. Without correction the darker parts of an image appear too dark. If the brightness b of a pixel is a value between 0 and 1, the corrected brightness is simply: bcorrected = b1/γ where γ normally about 2.2. But depending on the specific image, gamma values as large as 4 improve visibility of fine structure in the attractor. Large gamma values also substantially increase the visible noise, and so require longer rendering times to compensate. The parameter is therefor left to the user to set according to taste and circumstance. See Figure 3e for the result of applying gamma 4 to our running example. Because the red, green, and blue phosphors respond independently, gamma correction is normally applied to each color channel independently. However if the gamma value is unnaturally large this has the effect of washing out the colors of the image (it becomes pastel or ghostly off-white). This is because saturated colors occur due to large difference between channel values. But gamma correction boosts any small values towards one, leaving less difference, and hence less saturation. While one may desire this effect, to preserve bright colors the gamma correction may be applied the same way the logarithm is: by calculating a scale factor on the alpha channel, and then applying it to the three color channels. The name of the parameter that selects this is called vibrancy, and it can take any value from 0, meaning to apply gamma to channels independently, to 1, meaning to apply gamma from the alpha channel to each channel.

6 伽马系数

在阴极射线管(CRT)上精确显示任何数字图像需要伽马校正,以解释荧光屏对电压的非线性响应。如果不进行校正,图像较暗的部分会显得太暗。如果像素的亮度b是介于0和1之间的值,则校正后的亮度仅为:b校正=b1/γ,其中γ通常约为2.2。但根据具体的图像,伽玛值高达4可提高吸引子中精细结构的可见性。较大的gamma值也会显著增加可见噪波,因此需要更长的渲染时间来进行补偿。因此,参数由用户根据口味和环境进行设置。将gamma 4应用于我们的运行示例的结果,请参见图3e。由于红色、绿色和蓝色荧光粉独立响应,伽马校正通常独立应用于每个颜色通道。但是,如果gamma值不自然地大,则会产生清除图像颜色的效果(它变为柔和或幽灵般的灰白色)。这是因为饱和颜色是由于通道值之间的巨大差异而产生的。但是gamma校正会将任何小的值向一个方向推进,留下更少的差异,从而减少饱和度。虽然人们可能希望这种效果,但为了保持明亮的颜色,伽马校正可以采用与对数相同的方式应用:通过计算α通道上的比例因子,然后将其应用于三个颜色通道。选择此参数的参数名称为振动,它可以取0(表示将gamma独立应用于地震道)到1(表示将gamma从alpha cha应用于地震道)之间的任意值。


7 Symmetry

The human mind responds to symmetric designs at a fundamental level. When the matrix coefficients are chosen at random, the chances of a symmetric design appearing are vanishingly small. We can easily inject such functions intentionally, however. The result appears in Figure 5. There are two kinds of symmetries: rotational and dihedral. First we cover rotations. Adding a function to the system that rotates by 180 degrees makes a 2-way rotational symmetry appear. The weight of this function should be equal to the sum of the weights of all other functions in the system. That way half of the jumps in the chaos game are between the two halves, and hence the two halves will have equal density. If the rotation function is given the same weight as the other functions, then one of the two halves will only be a shadow of the other.


7 对称性

人类的思维在基本层面上对对称设计作出反应。当矩阵系数随机选取时,对称设计出现的几率很小。然而,我们可以很容易地有意地注入这些(形成对称的)函数。结果如图5所示。有两种对称:旋转对称和二面体对称。首先我们讨论旋转。将旋转180度的函数添加到系统中会出现双向旋转对称。此函数的权重应等于系统中所有其他函数的权重之和。这样,在混沌游戏中,一半的跳跃在两个半部分之间,因此两个半部分的密度相等。如果旋转函数与其他函数具有相同的权重,则两个半体中的一个将仅是另一个半体的阴影。

image.png

Figure 5: Examples of symmetry. Image d shows how the colors wash out without special treatment of the color coordinate for symmetry transforms.

图5:对称的例子。图d显示了在没有对对称变换的颜色坐标进行特殊处理的情况下,颜色是如何被洗掉的。


Adding a rotation by 120 degrees does make a 3-way symmetry appear. The three branches do not have equal density however, and no weighting would balance them. That%E2%80%99s because in order to get into the 240-degree branch in the chaos game, one has to pick the rotational function twice in a row, which is only 25% probable, but the 120-degree branch is 50% probable. Instead one must introduce two transforms, one by 120 degrees and one by 240, and give them both weight equal to the sum of the others. Then all three branches will have the same probability. In general, to produce n-way symmetry, n-1 additional transforms are necessary to balance the densities. A dihedral symmetry is created by adding a function that inverts the x coordinate only (producing bilateral symmetry). Again it is given weight equal to the sum of all the other weights combined. Combining this function with rotation functions gives all the dihedral symmetries. Dihedral symmetries are named with negative integers, so the simple bilateral symmetry is -1, and snowflake symmetry is -6. This just follows the isomorphism between multiplication on integers and composition of symmetries. It is also possible to introduce symmetries by modifying the chaos game to support them directly instead of adding symmetric functions. For example, one can just add an integer symmetry parameter, and then after picking a function at random, pick a rotation at random. But then how to interpolate between symmetries without discontinuities is problematic. Getting good colors with the symmetry functions requires special treatment. The problem is the symmetry functions can bring a point back onto itself after two or more applications. If the color is modified by these functions and then plotted at its original location, different colors get averaged, and the image loses color diversity. The solution is to not change the color coordinate when applying symmetry functions. This also makes the colors symmetric as well as the shape.


增加120度的旋转确实会出现三向对称。然而,这三个分支的密度并不相等,没有权重可以平衡它们。这是因为在混沌游戏中,为了进入240度分支,一个人必须连续两次选择旋转函数,只有25%的概率,但是120度分支有50%的概率。相反,必须引入两个变换,一个变换120度,一个变换240度,并赋予它们与其他变换之和相等的权重。那么这三个分支都有相同的概率。一般来说,要产生n向对称性,需要n-1附加变换来平衡密度。(形成图形成分均衡的对称)通过添加一个仅反转x坐标的函数(产生双边对称)来创建二面体对称。同样,它被赋予的权重等于所有其他权重的总和。将此函数与旋转函数相结合可得到所有的二面体对称性。二面体对称用负整数命名,因此简单的双边对称为-1,雪花对称为-6。这就遵循了整数乘法和对称合成之间的同构。也可以通过修改混沌博弈来引入对称性,从而直接支持它们,而不是添加对称函数。例如,可以只添加一个整数对称参数,然后在随机选取一个函数后,随机选取一个旋转。但是如何在对称性之间插值而不间断是个问题。用对称函数获得好的颜色需要特殊处理。问题是对称函数可以在两个或更多的应用之后使一个点回到自身。如果用这些函数修改颜色,然后将其绘制在原始位置,不同的颜色将得到平均值,图像将失去颜色多样性。解决方法是在应用对称函数时不更改颜色坐标。这也使得颜色和形状对称。


8 Filtering

Aliasing in spatial and temporal directions is visually disturbing and also indicates information loss because one cannot tell if an artifact in the image is an original or an alias. With anti-aliasing, there is no ambiguity.

The chaos game lends itself to anti-aliasing. Consider spatial aliasing first, that is the elimination of the jaggie edges. The normal technique is to draw  the desired image at high resolution, and then filter it down to display resolution. This is known as upersampling, and its cost is linear in time and memory (though the sampling is normally applied in two dimensions, so 3 by 3 supersampling means 9x). With the chaos game however we can achieve this effect by just increasing the number of buckets used in the histogram without increasing the number of iterations. There is a small, sublinear cost in time though because the time spent filtering is significant, and the increased memory usage also means increased cache misses during iteration. The effect on visual quality,however, is dramatic. Gamma correction should be done at this filtering step,when the maximum number of bits of precision is still available.


8 过滤

在空间和时间方向上的混叠在视觉上是令人不安的,并且还表示信息丢失,因为人们无法判断图像中的伪影是原始的还是别名。有了反走样,就没有歧义了。

混沌游戏有助于消除混叠。首先考虑空间混叠,即消除锯齿边缘。通常的方法是在高分辨率下绘制所需的图像,然后将其过滤到显示分辨率。这被称为超采样,其成本在时间和内存上是线性的(尽管采样通常应用于二维,所以3×3的超采样意味着9x)。然而,在混沌游戏中,我们可以通过增加直方图中使用的桶数而不增加迭代次数来达到这种效果。不过,时间上有一个很小的次线性开销,因为过滤所花的时间很长,而且内存使用量的增加也意味着迭代期间缓存未命中的增加。然而,对视觉质量的影响是戏剧性的。在该滤波步骤中,当仍然存在精度的最大位数时,应进行伽马校正。


Despite this filtering, the logarithm and gamma factor may cause low-density parts of an image to appear dotted or noisy. A wider filter would solve this, but at the expense of making the well-sampled parts of the image blurry. This can be addressed with a form of Density Estimation [5]. We have implemented a dynamic filter where a blur kernel of width inversely proportional to the density of points in the histogram is applied to the samples [6]. The blur kernel is scaled based on the supersampling level, and is applied after the log density scaling.his variable width filter allows higher density areas to remain in focus, while lower density areas are significantly smoothed. Figure 6 illustrates the effect of density estimation.


尽管有这种过滤,对数和伽马因子可能导致图像的低密度部分出现虚线或噪声。一个更宽的滤波器可以解决这个问题,但代价是使图像中采样良好的部分变得模糊。这可以用密度估计的形式来解决[5]。我们已经实现了一个动态滤波器,其中一个宽度与直方图中点的密度成反比的模糊核被应用于样本[6]。模糊核根据超采样级别进行缩放,并在对数密度缩放后应用。他的可变宽度滤波器允许高密度区域保持聚焦,而低密度区域则显著平滑。图6说明了密度估计的效果。

image.png

Figure 6: Demonstration of density estimation: (a) a low-resolution, low-quality,zoomed image rendered without density estimation, and (b) with density estimation, and (c) a high quality render at high resolution with density estimation.

图6:密度估计演示:(a)未经密度估计而渲染的低分辨率、低质量、缩放图像;(b)经密度估计而渲染的图像;(c)经密度估计而在高分辨率下渲染的高质量图像。


9 Motion Blur

Motion blur, or temporal anti-aliasing, is not so easy to do correctly. Supersampling can be achieved by varying the parameters over time while running the chaos game. That is, if 5M samples are used to draw the frame at time t,o instead use 1M samples at time t-0.5, 1M samples at t-0.25, 1M at t, 1M at t+0.25 and 1M at t+0.5, all the while accumulating into the same buffer. That would be 5x supersampling for free! With linear density display, this would ork exactly.

The non-linearity of the logarithm complicates things. Consider a pixel with density 8. Assume for simplicity the logarithm is base 2, so its assigned brightness is 3. Now put the fractal in motion so it blurs across two pixels, each should get brightness 1.5. But if the motion takes place before the logarithm then the 8 samples would be divided into two pixels of density 4 each, whose logarithm is 2, not 1.5. Objects in motion would appear unnaturally bright.

A proper solution requires the use of an extra buffer: the first buffer is linear and accumulates the histogram. After each temporal sample, take the logarithm of this buffer and accumulate it into the second one, applying the ensity estimation filter in the process. After all samples are completed, the second buffer is filtered down into the final image.

The drawback of this approach, however, is the computational effort required to apply the density estimation filter repeatedly to the linear buffer; multiple applications of the filter can easily double the rendering time.

After experiments with a single buffer yielded acceptable results, we decided to default to single buffer renders, while retaining the option of using the extra buffer.


9 运动模糊

运动模糊,或者暂时的消除混叠,不是那么容易做正确的。在运行混沌游戏时,可以通过随时间改变参数来实现超采样。也就是说,如果在时间t时使用5M样本绘制帧,则在时间t-0.5时使用1M样本,在时间t-0.25时使用1M样本,在时间t时使用1M样本,在时间t+0.25时使用1M样本,在时间t+0.5时使用1M样本,所有这些样本同时累积到同一缓冲区中。这将是5倍的免费超级采样!使用线性密度显示,这将非常有效。

对数的非线性使事情复杂化。考虑密度为8的像素。为简单起见,假设对数是以2为底,因此其指定亮度为3。现在让分形运动起来,使它在两个像素之间模糊,每个像素的亮度应该是1.5。但是如果运动发生在对数之前,那么8个样本将被分成两个密度为4的像素,每个像素的对数是2,而不是1.5。运动中的物体会显得异常明亮。

正确的解决方案需要使用一个额外的缓冲区:第一个缓冲区是线性的,并累积直方图。在每个时间样本之后,取该缓冲区的对数并将其累加到第二个缓冲区中,在此过程中应用密度估计滤波器。完成所有采样后,第二个缓冲区被过滤到最终图像中。

然而,这种方法的缺点是,需要在线性缓冲区中重复应用密度估计滤波器;多次应用该滤波器可以很容易地使渲染时间加倍。对单个缓冲区的实验产生了可接受的结果之后,我们决定默认使用单个缓冲区呈现,同时保留使用额外缓冲区的选项。


Directional Motion Blur

Uniformly distributing the samples among time steps works well for an animated series of frames, but the illusion of motion of an individual frame animation may be improved by providing a sense of direction. Early attempts at directional motion varied the number of samples used at each time step, but since the density estimation filter was more aggressive during less dense time steps, the result appeared unnatural.

Figure 7: (a) motion blur and (b) directional motion blur.

Instead, the color of points accumulated during earlier time steps are scaled in intensity, with the scaling constant approaching 1.0 as the time steps progress.

A rendering parameter can be supplied to the renderer to change how aggressively the blending varies throughout the time steps. See the effects of directional motion blur in Figure 7.


方向运动模糊

对于动画的一系列帧,在时间步之间均匀地分布采样效果很好,但是通过提供方向感,可以改善单个帧动画的运动错觉。早期的定向运动尝试改变了每个时间步使用的样本数,但由于密度估计滤波器在较低密度的时间步中更具攻击性,结果显得不自然。

image.png

图7:(a)运动模糊和(b)方向运动模糊。

相反,在早期时间步中累积的点的颜色按强度缩放,随着时间步的推进,缩放常数接近1.0。

可以向渲染器提供一个渲染参数,以更改在整个时间步骤中混合变化的剧烈程度。请参见图7中的定向运动模糊效果。


10 History and Acknowledgements

In 1987 at Brown University Bill Poirier showed Scott Draves what he called ‘Recursive Pictures’ a kind of two-dimensional IFS. Poirier used a formulation that included perspective transforms, but lacked a software implementation. In response Draves created the first of many IFS algorithms. It was written in Postscript and ran on the Laserwriter, producing high resolution line drawings.

Draves reimplemented this idea in a variety of ways over the three years he spent in the Computer Graphics Research Group at while still at Brown.

The first implementation to include all three definitive characteristics of fractal flames (non-linear variations, log-density display, and structural coloring) was created in the summer of 1991 while Draves was an intern at the NTT-Data Corporation in Tokyo, Japan and was generously allowed to pursue his own projects.

That version was released on the then-nascent world wide web in 1992 under the General Public License (GPL), making it the first open-source art. It has since been incorporated into and ported to many environments, including the imp, Photoshop (as Kai’s Power Tools FraxFlame), After Effects, Digital Fusion, Ultra Fractal 3, screensavers for Macintosh, Windows, and Linux, as well as stand-alone programs (Apophysis, Oxidizer, and Qosmic).


10 历史和致谢

1987年,在布朗大学,比尔·波里尔向斯科特·德雷夫斯展示了他称之为“递归图片”的二维IFS。porier使用了包含透视变换的公式,但是缺少软件实现。作为回应,Draves创建了许多IFS算法中的第一个。它是用Postscript写的,在Laserwriter上运行,生成高分辨率的线条图。

德拉维斯在他还在布朗大学时,在计算机图形学研究小组工作了三年,他以各种方式重新实现了这个想法。

1991年夏天,Draves在日本东京的NTT数据公司实习时,第一次实现了包含分形火焰全部三个明确特征(非线性变化、对数密度显示和结构着色)并被慷慨地允许从事自己的项目。

该版本于1992年以通用公共许可证(GPL)的形式在当时刚刚兴起的万维网上发布,成为第一个开源艺术。此后,它被纳入并移植到许多环境中,包括IMP、PS图象处理软件(作为KAI的动力工具FrasFi焰)、效果后、数字融合、超分形3、Macintosh、Windows和Linux的屏幕保护程序以及独立程序(Apple Survives、Ongisher和Qosmic)。


The combined-channel gamma feature and the vibrancy parameter that controls it were introduced in 2001. The symmetries were introduced in 2003. Variations 7 to 12 were developed by Ronald Hordijk for his screen-saver version of the flame algorithm, then ported to the Ultra Fractal version by Erik Reckase, and adopted into the original version (with some modifications) by Draves in 2003.

In 2004, Mark Townsend released Apophysis, a translation of Draves’ C code into Delphi Pascal, with the addition of a GUI for interactive design. Erik Reckase became more involved with the flame algorithm after the release of pophysis, and became an official developer and maintainer in 2005. Reckase’s contributions have focused on improved image quality, code optimization, and keeping up with the wealth of variations being developed in the Apophysis community.

In 2006 Peter Sdobnov added final transforms to Apophysis and they were soon after adopted by our implementation to maintain compatibility.

Thanks to Hector Yee for suggesting tone mapping as the general solution to the dynamic range problem, and David Hart for suggesting density estimation as an improved filter technique.

The fractal flame algorithm is also the seed that spawned the Electric Sheep distributed screen-saver [2], a follow-on art project by Draves. In this system,thousands of idle computers from all over the world are harnessed into rendering (and evolving) fractal flames. The work of all participating clients is shared alike.


2001年引入了组合沟道伽马特征和控制它的振动参数。对称性是在2003年引入的。Ronald Hordijk为他的flame算法的屏幕保护程序版本开发了7到12个变体,然后由Erik Reckase移植到超分形版本,并在2003年被Draves采用到原始版本(经过一些修改)。

2004年,MarkTownsend发布了Apophysis,一个将Draves的C代码翻译成DelphiPascal的版本,并添加了一个用于交互设计的图形用户界面。Erik Reckase在apophysis发布后开始更多地参与flame算法,并于2005年成为官方的开发和维护人员。Reckase的贡献集中在提高图像质量、代码优化和跟上在APO社区中开发的丰富变化上。

2006年,Peter Sdobnov为apopthysis添加了最终的转换,并很快被我们的实现所采用,以保持兼容性。

感谢Hector Yee建议将色调映射作为动态范围问题的一般解决方案,以及David Hart建议将密度估计作为改进的滤波技术。

分形火焰算法也是“电子羊”分布式屏幕保护程序(Draves的后续艺术项目)的种子。在这个系统中,来自世界各地的数千台闲置计算机被用来绘制(和进化)分形火焰。所有参与客户的工作都是相同的。


References

[1] Michael Barnsley: Fractals Everywhere. Academic Press, San Diego, 1988.

[2] Scott Draves. The Electric Sheep Screen-Saver: A Case Study in Aesthetic Evolution. Applications of Evolutionary Computing, LNCS 3449, 2005.

[3] Hutchinson, J. Fractals and Self-Similarity. Indiana University Journal of Mathematics. 30, 713-747, 1981.

[4] Jack Tumblin, Holly Rushmeier. Tone Reproduction for Realistic Images.

IEEE Computer Graphics and Applications. November/December 1993

(Vol. 13, No. 6) pp. 42-48.

[5] B. W. Silverman, Density Estimation for Statistics and Data Analysis, Chapman and Hall, London, 1986.

[6] F. Suykens and Y. D. Willems. Adaptive filtering for progressive Monte Carlo image rendering. In Eighth International Conference in Central Europe on Computer Graphics, Visualization and Interactive Digital Media

(WSCG 2000), Plzen, Czech Republic, February 2000.


Appendix: Catalog of Variations

附录:变体目录


For each variation we give its formula and its name, and provide a list of parameters for parametric variations. Variables used in these formulas are:



(a, b, c, d, e, f) are considered to be the affine transform coefficients for a variation, and are used in dependent variations. Ω is a random variable that is either 0 or π. Λ is a random variable that is either -1 or 1. Ψ is a random variable

uniformally distributed on the interval [0, 1]. The ’trunc’ function returns the integer part of a floating-point value.

A visualization of the distorted coordinate grid and a representative flame using this variation are also supplied. As in Figure 2, x and y increase towards the lower right, to match the coordinate system of the output image. Note that these sample flames are selected based on their characteristic shape and not for any aesthetic qualities. The representative images attempt to use a single variation, but in general, variations can be mixed when creating flames. For random-based variations, a scatterplot is substituted for the coordinate grid.


对于每个变量,我们给出其公式和名称,并提供参数变量的参数列表。这些公式中使用的变量有:


(a,b,c,d,e,f)被认为是变化的仿射变换系数,并用于仿射变化。Ω是一个0或π的随机变量。是-1或1的随机变量。Ψ是在区间[0,1]上均匀分布的随机变量。“trunc”函数返回浮点值的整数部分。

还提供了扭曲坐标网格的可视化和使用这种变化的典型火焰。如图2所示,x和y向右下方增加,以匹配输出图像的坐标系。请注意,这些样本火焰是根据其特征形状选择的,而不是为了任何审美品质。有代表性的图像试图使用单一的变化,但通常情况下,在产生火焰时可以混合变化。对于随机变化,用散射图代替坐标网格。


Linear (Variation 0)


 

Sinusoidal (Variation 1)

 

 

Spherical (Variation 2)

 

 

Swirl (Variation 3)

 

 

Horseshoe (Variation 4)

 

 

Polar (Variation 5)

 

 

Handkerchief (Variation 6)

 

 

Heart (Variation 7)

 

 

Disc (Variation 8)

 

 

Spiral (Variation 9)

 

 

Hyperbolic (Variation 10)

 

 

Diamond (Variation 11)

 

 

Ex (Variation 12)


 

Julia (Variation 13)

 

 

Bent (Variation 14)

 

 

Waves (Variation 15) - dependent

 

 

Fisheye (Variation 16)

Note the reversed order of x and y in the formula.

注意公式中x和y的倒序。

 

 

Popcorn (Variation 17) - dependent

 

 

Exponential (Variation 18)

 

 

Power (Variation 19)

 

 

 

Cosine (Variation 20)

 

 

 

Rings (Variation 21) - dependent

 

 

 

Fan (Variation 22) - dependent

 

 

 

Blob (Variation 23) - parametric

 

 

 

PDJ (Variation 24) - parametric

 

 

 

Fan2 (Variation 25) - parametric

 

 

 

Rings2 (Variation 26) - parametric

 

 

 

Eyefish (Variation 27)

 

 

 

Bubble (Variation 28)

 

 

 

Cylinder (Variation 29)

 

 

 

Perspective (Variation 30) - parametric

 

 

 

Noise (Variation 31)

 

 

 

JuliaN (Variation 32) - parametric

 

 

 

JuliaScope (Variation 33) - parametric

 

 

 

Blur (Variation 34)

 

 

 

Gaussian (Variation 35)

 

 

 

RadialBlur (Variation 36) - parametric

 

 

 

Pie (Variation 37) - parametric

 

 

 

Ngon (Variation 38) - parametric

 

 

 

Curl (Variation 39) - parametric

 

 

 

Rectangles (Variation 40) - parametric

 

 

 

Arch (Variation 41)

 

 

 

Tangent (Variation 42)

 

 

 

Square (Variation 43)

 

 

 

Rays (Variation 44)

 

 

 

Blade (Variation 45)

 

 

 

Secant (Variation 46)

 

 

 

Twintrian (Variation 47)

 

 

 

Cross (Variation 48)