Print

发布时间: 2020-09-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.190660
2020 | Volume 25 | Number 9




    计算机图形学    




  <<上一篇 




  下一篇>> 




分形曲线生成的频域方法
expand article info 陈伟1,2, 乔洁雯1, 周晨1
1. 江南大学人工智能与计算机学院, 无锡 214122;
2. 江苏省媒体设计与软件技术重点实验室, 无锡 214122
收稿日期: 2019-12-24; 修回日期: 2020-03-27; 预印本日期: 2020-04-03
基金项目: 国家自然科学基金项目（61602213，61772013）；江苏省绿色船舶技术重点实验室开放课题项目（2019Z03）
第一作者简介: 陈伟, 1986年生, 男, 副教授, 主要研究方向为计算机辅助几何设计、计算机图形学。E-mail:wchen_jdsm@163.com;
乔洁雯, 女, 硕士研究生, 主要研究方向为计算机图形学。E-mail:qiaojwe@163.com;
周晨, 男, 硕士研究生, 主要研究方向为计算机图形学。E-mail:6181611034@stu.jiangnan.edu.cn.
中图法分类号: TP391
文献标识码: A
文章编号: 1006-8961(2020)09-1904-11

摘要

目的 分形几何学的理论研究与应用实践方兴未艾，在分形的计算机生成领域，传统方法是在空间域中，通过对生成元的迭代操作而形成。为了扩展分形的生成方法，本文将频谱分析引入到分形几何中。方法 正交函数系是频谱分析的核心问题之一。考虑到分形曲线是一类连续而不光滑的折线型信号，通常的三角函数（Fourier变换）、连续小波变换仅适用于光滑的对象，否则会出现所谓“Gibbs现象”；另一方面，以V-系统为代表的正交分段多项式函数系适用于表达包含间断性的对象，否则会出现信息冗余。因此，通常的正交函数系均不适合分形的频谱表达与分析。针对分形曲线的特点，本文将其视为一次样条函数，通过引入一类正交样条函数系-Franklin函数系，实现了对分形曲线的有限项精确正交表达，得到Franklin频谱，从而完成分形的时频变换。然后，对Franklin频谱系数在不同尺度上进行修改。最后，通过正交重构得到新的分形。结果 对比实验验证了Franklin函数系在分形曲线频域表达方面的优越之处，它既能通过最小项数实现分形的正交表达，而且不会出现Gibbs现象。本文以von Koch曲线、Sierpinski square曲线和Hilbert曲线这3个经典分形为例，通过对Franklin谱在不同尺度上的自由调节，能够方便地生成大量形态各异的新的分形曲线。结论 Franklin谱不仅能够实现对分形曲线的有限精确重构，而且还能在不同尺度上刻画分形的形态特征。基于Franklin频谱调节实现的分形生成方法，只要修改频谱就可以得到大量的新型分形曲线，而且这些分形的样式千变万化，几乎不可预测，这种分形生成方式为分形设计带来了巨大的自由空间，为分形的生成提供了新的思路与方案。

关键词

分形曲线; 正交函数系; Franklin函数; 频谱分析; 多分辨率

Fractal curve generation method based on the frequency domain
expand article info Chen Wei1,2, Qiao Jiewen1, Zhou Chen1
1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China;
2. Jiangsu Key Laboratory of Media Design and Software Technology, Wuxi 214122, China
Supported by: National Natural Science Foundation of China (61602213, 61772013)

Abstract

Objective The theoretical research and application of fractal geometry is continuously making progress. Traditional methods are formed in the spatial domain through iterative operations on generators. To extend the fractal generation method, we introduce the spectrum analysis method into fractal geometry. In signal processing tasks, such as filtering, data compression, model editing, and object retrieval, the spectrum analysis method has been widely and successfully applied, especially in the field of computer-generated fractals. However, spectrum analysis based on orthogonal transform is rarely studied in fractal generation and analysis. One reason is the lack of a suitable orthogonal function system. We should choose to express the fractal accurately with a few orthogonal basis functions. Polygonal fractal curves should be chosen as orthogonal expressions of the same type of orthogonal function systems. From the point of view of the spline function, the polyline is a linear spline function. Therefore, we make a fractal curve on the basis of a class of one-time orthogonal spline function system (Franklin function) to obtain the Franklin spectrum. Compared with other orthogonal function systems, the Franklin spectrum has inherent advantages in the expression and generation of fractal curves. Method We first show the orthogonal decomposition and reconstruction algorithm of fractal curves under the Franklin function system. Then, with the classic von Koch snowflake curve taken as an example, the Fourier series, the V system, and the Franklin orthogonal system are compared to express the fractal curve. Lastly, the Franklin spectrum is modified, and then orthogonal reconstruction is performed to generate rich and diverse fractal curves. The advantages and characteristics of this method are compared and demonstrated. The traditional generator iteration is a process-based fractal expression method, but we express the fractal from the perspective of spectrum, which is the essential difference. One of the fundamental core issues of spectrum analysis is the choice of orthogonal function systems. Considering that the fractal curve is a continuous and unsmooth polyline type, the traditional orthogonal function system has the following two problems. On the one hand, the usual trigonometric functions (Fourier transform) and wavelet transform are only suitable for smooth objects. On the other hand, the orthogonal piecewise polynomial function system represented by the V system is suitable for continuous and discontinuous objects. Neither method is suitable for fractal spectrum analysis. Therefore, this study introduces a type of continuous orthogonal function system, i.e., the Franklin function system. Through the orthogonal decomposition of fractal curves, the corresponding Franklin spectrum is obtained. Result We take a typical typing curve, i.e., the von Koch curve, as an example and use the Fourier and Franklin methods to perform orthogonal decomposition and reconstruction. The characteristics of the fractal curve expression algorithm based on the Franklin function are verified. Moreover, compared with other orthogonal function systems, it emphasizes the advantage of the Franklin function system in the frequency domain representation of fractal curves. Based on the von Koch curve, Sierpinski square curve, and Hilbert curve, we use different resolutions and parameters to conduct comparative experiments. The experiments verify the superiority of the Franklin function system in the frequency domain expression of fractal curves. By freely adjusting the Franklin spectrum, many new fractal curves with different shapes can be easily generated. According to the properties of the Franklin function system (orthogonality and multiresolution), the Franklin spectrum describes the fractal curve from the frequency domain perspective and achieves the optimum multilevel hierarchical approximation of the entire fractal curve. Low-frequency components focus on the contour information of the fractal curve, whereas high-frequency components describe its detailed information. When the Franklin spectral coefficient reaches 2n+1 terms, an accurate reconstruction of the fractal curve can be achieved; ordinary orthogonal function systems cannot achieve such accuracy. Conclusion We take the fractal curves of the study as an example. Classical fractal objects, such as von Koch snowflake, Siepinski carpet, and Hilbert curve, have an infinitely small-scale hierarchical structure. However, when they are stored in a computer and drawn, they can only present approximation results within a certain scale. Therefore, they are continuous but unsmooth polylines. Afterward, choosing Franklin orthogonal function systems can make proper orthogonal expressions for such objects. The Franklin function can be accurately expressed with limited orthogonal basis functions. On the one hand, Franklin functions are not smooth functions and thus can express fractal graphs well with polyline segments. On the other hand, Franklin functions are not discontinuous orthogonal function systems, and continuous functions can be expressed with a few term basis functions. This expression does not have fragility; in other words, the fractal orthogonal expression using the Franklin function does not distort the fractal curve. In general, the Franklin spectrum can not only achieve limited and accurate reconstruction of fractal curves but also describe the morphological characteristics of fractals on different scales. The fractal generation method based on Franklin spectrum adjustment provides new ideas and solutions for fractal generation.

Key words

fractal curve; orthogonal system; Franklin functions; spectrum analysis; multi-resolutions

0 引言

分形(fractal)是描述不规则几何形态的有力工具，从微观世界复杂物质的结构，到宏观世界浩瀚天体的演变，分形都无所不在。分形被喻为大自然的几何学(Mandelbrot，1983)。虽然分形一词由Mandelbrot于1975年才首次提出，但分形的某些概念和思想，早在100多年前的传统数学中就已经是广为人知的事实。从传统微积分的角度来看，人们将诸如von Koch雪花、Siepinski地毯、Cantor函数、Wierstrass函数及Peano曲线等这些处处连续又处处不可微的函数，都作为数学中的反例。作为分形几何的创始人，Mandelbrot的最大贡献在于将历史上公认的反例摆正了位置，使它们成为分形几何的主角。

自分形几何学提出以来，其理论研究和应用实践方兴未艾(Barseley，1988；Peitgen等，2012；丁玮和齐东旭，1998；李文娟等，2017；刘鸿雁等，2008)。在计算机图形学领域，分形几何的研究重点是分形图形的计算机生成方法，包括Lindenmayer方法(简称L系统)(Smith，1984)、迭代函数系统(iterative functional system，IFS)(Demko等，1985)等方法。在计算机辅助几何设计(computer aided geometric design，CAGD)领域，细分方法成为一类重要而高效的曲线曲面造型技术(Dyn等，1987；Gregory和Qu，1996；Conti和Hormann，2011；Mustafa，2017)。分形曲线的生成遵循相同的原理, 通过对少量离散控制点的不断迭代细化操作，可以得到极限意义下的分形曲线。不同的是前者追求曲线的光滑性，而后者却相反，从而可以在迭代过程中对不同的参数进行自由选择(Siddiqi等，2014；Hu等，2019；Kaur和Sivia，2019)。

从信号处理的角度来看，通过对分形进行正交分解，生成对应的频谱，可以获得分形特征的量化数字结果。相比于传统的分数维这种单一数字特征(Mandelbrot，1985；Falconer，1985)，频谱信息更加关注分形的整体几何特征，从而推动对分形更加深入的认识及应用。

齐东旭(1994)在关于分形生成的专著中，将Haar函数、Walsh函数及U-系统等正交函数系放在一起讨论，意在强调相互之间的联系。受此启发，宋瑞霞等人(2016)首次将分形曲线在一类正交分段多项式函数系(V-系统)上进行正交表达，得到相应的频谱。

本文提出的分形曲线生成的频谱方法指的是将分形曲线表达成另外一种正交展开的形式。众所周知，在信号处理领域，如滤波、数据压缩、模型编辑和对象检索等诸多问题中，频谱分析方法得到了非常广泛和成功的应用(Meyer，1993；Dremin，2005；柳重堪，1982；齐东旭等，2011；熊刚强和齐东旭，2010)，其代表性的数学工具为Fourier、Walsh和Wavelets等各种正交变换。然而，尽管将频谱分析方法引入分形几何具有重要的研究与应用价值，但基于正交变换的频谱分析在分形的生成及分析方面的研究却非常少见。究其原因，主要是缺少合适的正交函数系。以本文研究的分形曲线为例，von Koch雪花、Siepinski地毯和Peano曲线等这些经典的分形对象是数学上的几何抽象，具有无穷小尺度的层次结构。然而，将它们在计算机中进行存储及绘制时，只能是在一定尺度范围内逼近的结果，它们是连续的不光滑的折线。因此，为了对分形进行恰当的正交表达，正交函数系的选择是关键问题。一方面，追求光滑性的三角函数系及小波函数显然是不合适的，因为有限个光滑函数的线性组合必然仍为光滑函数；另一方面，以U-系统与V-系统为代表的间断型正交函数系尽管可以用较多项的间断基函数来合成连续函数，但是这种表达具有脆弱性。如果缺少一项基函数，重构的结果就会出现间断，从而使分形曲线失真。

本文的基本思想是：折线型的分形曲线应该选用同类型的正交函数系进行正交表达。从样条函数的观点来看，折线即为一次样条函数。因此，本文基于一类一次正交样条函数系(Franklin函数)对分形曲线作正交表达，从而得到Franklin频谱。与其他的正交函数系相比，Franklin频谱在分形曲线的表达与生成上具有内在的优势。

1 Franklin函数系

1.1 Franklin函数的构造

Franklin函数是由Philip Franklin给出的一类定义在$L^2$[0, 1]上的连续正交函数系(Franklin，1928)，它是对一组线性无关的截断幂基，经正交化过程得到。首先，考虑线性无关组$\{α_{n}(x), 0≤x≤1\}$，具体为

$ \begin{matrix} {{\alpha }_{0}}(x)=1,{{\alpha }_{1}}(x)=x \\ {{\alpha }_{i}}(x)={{(x-{{a}_{i}})}_{+}},i=2,3,\cdots \\ \end{matrix} $ (1)

式中，$(x-a_{i})_{+}$为截断单项式，$a_{i}=(2i-1-2^{m})/2^{m}$，$m$为不超过$2i-1$的2的最高方幂指数，即区间[0, 1]的节点依次为$\frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}, \frac{1}{{16}}, \frac{3}{{16}}, \ldots $。

将上述线性无关组$\{α_{n}(x), 0≤x≤1\}$经过Gram-Schmidt正交化过程，结果即为Franklin函数系，记为$\{φ_{n}(x)\}$。限于篇幅，本文只给出Franklin函数系的前5项基函数的表达式，即

$ {{\varphi }_{0}}(x)=1,0\le x\le 1 $

$ {{\varphi }_{1}}(x)=\sqrt{3}(2x-1),0\le x\le 1 $

$ {{\varphi }_{2}}(x)=\left\{ \begin{array}{*{35}{l}} \sqrt{3}(1-4x) & 0\le x<1/2 \\ \sqrt{3}(4x-3) & 1/2\le x\le 1 \\ \end{array} \right. $

$ {{\varphi }_{3}}(x)=\left\{ \begin{array}{*{35}{l}} \sqrt{33}(5-38x)/11 & 0\le x<1/4 \\ \sqrt{33}(26x-11)/11 & 1/4\le x<1/2 \\ \sqrt{33}(5-6x)/11 & 1/2\le x\le 1 \\ \end{array} \right. $

$ {{\varphi }_{4}}(x)=\left\{ \begin{array}{*{35}{l}} \sqrt{231}(1-12x)/77 & 0\le x<1/4 \\ \sqrt{231}(36x-11)/77 & 1/4\le x<1/2 \\ \sqrt{231}(45-76x)/77 & 1/2\le x<3/4 \\ \sqrt{231}(100x-87)/77 & 3/4\le x\le 1 \\ \end{array} \right. $

线性无关组前9项的函数图像以及对应的前9项Franklin基函数的图像如图 1所示。



图 1 线性无关组前9项与对应的Franklin函数
Fig. 1 First 9 terms of linearly independent groups and corresponding Franklin functions ((a) linearly independent group; (b) Franklin functions)

1.2 Franklin函数的主要性质

1) 标准正交性。Franklin函数系是定义在区间[0, 1]上的标准正交函数系，即

$ \int_{0}^{1}{{{\varphi }_{i}}}(x){{\varphi }_{j}}(x)\text{d}x={{\delta }_{ij}},i,j=0,1,2,\cdots $ (2)

2) 多分辨率。从Franklin函数系的定义可以看出，它的节点分布具有逐层加密的特点，从而具有多分辨率性。

3) 一致收敛性。设$F(x)$为区间[0, 1]上的连续函数，它的Fourier-Franklin级数为$F \sim \sum\limits_{i = 0}^\infty {{c_i}{\varphi _i}\left(x \right), {c_i} = \left\langle {F, {\varphi _i}} \right\rangle = \int_0^1 {F\left(x \right){\varphi _i}\left(x \right){\rm{d}}x} } $，则

$ \begin{array}{*{20}{l}} {{c_i} = \langle F,{\varphi _i}\rangle = \int_0^1 {F(x)} {\varphi _i}(x){\rm{d}}x,{\rm{则}}}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \mathop {{\rm{lim}}}\limits_{n \to \infty } {{\left\| {F - {S_n}F} \right\|}_\infty } = 0} \end{array} $ (3)

式中，$S_{n}F$表示Fourier-Franklin级数的部分和，即

$ {S_n}F = \sum\limits_{i = 0}^{n - 1} {{c_i}} {\varphi _i}(x) $ (4)

4) 折线再生性。设$F(x)$为区间[0, 1]上的一次样条函数，节点位置为$x = \frac{q}{{{2^r}}}$($q$，$r$是整数)。那么，$F(x)$可以用有限项Franklin函数精确重构。

Meyer(1993)对Franklin函数系给予了很高的评价，Franklin函数系兼具Haar函数系与Schauder函数系的优点，对平稳信号或非平稳信号均能够较好地处理。但Franklin函数系的表达式复杂，不像Haar函数系或Schauder函数系具有简单的数学表达式，也不能通过对某个特定函数的积分变换和压缩平移等操作得到。因此，在很长的一段时间内，Franklin函数系并没有引起人们足够的重视。

随着现代计算机硬件及软件技术的发展，可以借助计算机自动完成正交化工作，得到足够多的Franklin基函数，以满足实际应用的需要。蔡占川等人(2009)将Franklin函数系推广到高次，得到一类$k$ ($k≥2$)次正交样条函数系，并应用到样条曲线曲面的几何造型正交分解(蔡占川等，2009)、散乱数据拟合(蔡占川和陈伟，2013)、数字曲线逼近(陈伟和齐东旭，2013)、图像重构(陈伟等，2015)等领域。

2 分形曲线正交表达方法

2.1 分形曲线的Franklin函数表达

分形曲线在某个尺度下可看做折线形态。假设折线段数为$2^{n}$, $n \in {\mathbb{Z}^ + }$，在数学上可表达为分段连续线性函数，具体为

$ P(t) = \left\{ {{p_j}(t),\frac{{j - 1}}{{{2^n}}} < t \le \frac{j}{{{2^n}}}|j = 1,2, \cdots ,{2^n}} \right\} $ (5)

式中，$p_{j}(t)$为第$j$段上的线性函数。

从样条函数的角度来看，$P(t)$为定义在区间[0, 1]上的均匀1次样条曲线。因此，$P(t)$可表达为

$ P(t) = \sum\limits_{i = 0}^{{2^n}} {{P_i}} \cdot {\varOmega _1}({2^n}t - i),t \in [0,1] $ (6)

式中，$\mathit{Ω}_{1}(t)$为1次B样条基本函数，即

$ {\varOmega _1}(t) = \left\{ {\begin{array}{*{20}{l}} {1 - |t|}&{|t| \le 1}\\ 0&{|t| > 1} \end{array}} \right. $ (7)

$\{P_{i}=(x_{i}, y_{i})|i=0, 1, …, 2^{n}\}$为控制点，也是分形曲线折点处的坐标。可以看出，$P(t)$的自由度为$2^{n}+ 1$。因此，$P(t)$可以由Franklin正交系的前$2^{n}+ 1$个基函数精确重构，重构公式为

$ P(t) = \sum\limits_{i = 0}^{{2^n}} {{\lambda _i}} \cdot {\varphi _i}(t),t \in [0,1] $ (8)

式中，$\{φ_{i}(t)\}$为第$i$个Franklin基函数。$λ_{i}=(λ_{i}^{x}, λ^{y}_{i})$为重构系数，也称为Franklin-谱系数，计算公式为

$ {\lambda _i} = \int_0^1 P (t) \cdot {\varphi _i}(t){\rm{d}}t $ (9)

Franklin-谱$\{λ_{i}, i=0, 1, …\}$是从频域角度对分形曲线进行刻画，它实现了对分形曲线的整体的多层次的最佳平方逼近。低频分量集中刻画了分形曲线的轮廓信息，高频分量刻画了细节信息。特别地，当Franklin-谱系数达到$2^{n}+1$项时，可以实现对分形曲线的精确重构，这是通常的正交函数系不能实现的。

2.2 Franklin函数重构示例

对典型的分形曲线——von Koch雪花曲线进行正交分解与重构，验证基于Franklin函数的分形曲线表达算法，强调相比于其他的正交函数系，Franklin函数系在分形曲线频域表达上的优势。图 2是von Koch曲线及其Franklin频谱。图 2(a)为第3级下的von Koch雪花曲线，是一条由64段组成的折线，因而其自由度为65。图 2(b)和图 2(c)为该曲线在Franklin正交系前65项基函数下正交分解的频谱$\{(λ^{x}_{i}, λ^{y}_{i})|i=0, 1, …, 64\}$。可以看出，分形曲线在Franklin正交系下表达后，能量集中于低频部分，且频谱分布的层次更加分明。根据Franklin频谱在不同分辨率下对原分形曲线进行正交重构，结果如图 3所示。



图 2 von Koch曲线及其Franklin频谱
Fig. 2 von Koch curve and its Franklin spectrum
((a) von Koch curve; (b) Franklin spectrum ($x$ component); (c) Franklin spectrum ($y$ component))



图 3 von Koch曲线的Franklin函数重构
Fig. 3 Reconstruction results for von Koch curve based on Franklin functions
((a) 17 refactorings (16 segments); (b) 33 refactorings (32 segments); (c) 65 refactorings (64 segments, accurate reconstruction))

根据Franklin正交系的性质及本例结果，可以得出如下结论：1)当利用前$n + 1$项Franklin函数重构时，所得结果为一条包含$n$段的折线，且不会出现间断情形；2)当重构项目按2的方幂增加时，重构结果即为在不同分辨率下对原曲线的最佳平方逼近；3)相比于其他的正交函数系，利用Franklin函数系可以实现在最少重构项数的条件下，对分形曲线的精确表达。

作为对比，von Koch雪花曲线在不同Fourier级数重构项数下的结果如图 4所示。可以看出，由于Fourier级数基函数(三角函数)的光滑性，在有限项逼近时始终存在因逼近函数的波动引起的误差，且这种误差不会因逼近项数的增加而消失。因此，Fourier级数在逼近分形曲线中存在本质的困难。



图 4 von Koch曲线的Fourier级数重构
Fig. 4 Reconstruction results for von Koch curve based on Fourier series
((a) 50 refactorings; (b) 200 refactorings; (c) 500 refactorings)

图 5为von Koch雪花曲线在1次V-系统下的重构结果。由于V-系统是正交分段多项式函数系，对包含$n$段的折线，需要$2n$项基函数才能精确重构。而且，当项数少于该数目时，重构的结果中就会出现间断，这是V-系统与Franklin正交系的最重要区别之一。图 5(a)为V-系统前64项重构，结果是一条包含32段的彼此间断的折线。图 5(b)为仅缺少一项(本例为第81项基函数)时，重构曲线出现2处间断。



图 5 von Koch曲线的1次V-系统重构
Fig. 5 Primary reconstruction results for von Koch curve based on V-system((a) 64 refactorings (32 segments); (b) 127 refactorings (63 segments); (c) 128 refactorings (64 segments, accurate reconstruction))

综上所述，理论与实验均表明，相比于通常的正交函数系，Franklin函数系在分形曲线的正交表达方面具有较好的表现和优势。

3 基于Franklin频谱分形曲线生成

传统的生成元迭代是一种基于过程的分形表达方法，而本文是从频谱角度对分形进行表达。对于已有的分形曲线，可以计算出相应的Franklin-谱。本节要解决如何生成新的分形曲线的问题。

首先，将Franklin基函数$\{φ_{n}(x), n=0, 1, 2, …\}$按层次关系重新给出排列次序。记$F_{n}^{j}(x)$为Franklin正交系的第$n$层中的第$j$个基函数。当$n=1$时，$F_{1}^{1}(x)$、$F_{1}^{2}(x)$为前2项Legendre多项式。当$n≥2$时，$j=1, 2, …, 2^{n-2}$，表示第$n$层包含$2^{n-2}$个基函数。第$n$层基函数的节点比上层($n-1$层)基函数的节点加密1倍，即分辨率提高1倍。

假设一个分形曲线$P(t)$在Franklin函数系下的正交表达为

$ P(t) = \sum\limits_{n = 1}^N {\sum\limits_j {\lambda _n^j} } \cdot F_n^j(t) $ (10)

若将第$n$层全部基函数记作向量形式，则

$ {\mathit{\boldsymbol{F}}_n}(t) = (F_n^1,F_n^2, \cdots ,F_n^{2n - 2}) $ (11)

相应的频谱向量为

$ {\mathit{\boldsymbol{\lambda }}_n}(t) = (\lambda _n^1,\lambda _n^2, \cdots ,\lambda _n^{2n - 2}) $ (12)

于是，式(10)可写为

$ P(t) = \sum\limits_{n = 1}^N {{\mathit{\boldsymbol{\lambda }}_n}} \cdot {\mathit{\boldsymbol{F}}_n}(t) $ (13)

为了对频谱进行修改，对每层的频谱向量引入一个参数$α_{n}，n=1, 2, …, N$，得

$ Q(t) = \sum\limits_{n = 1}^N {{\alpha _n}} {\mathit{\boldsymbol{\lambda }}_n} \cdot {\mathit{\boldsymbol{F}}_n}(t) $ (14)

$Q(t)$即为对原频谱修改而新生成的分形曲线。可以看出，通过设置不同的参数向量$\mathit{\boldsymbol{\alpha }}=(α_{1}, α_{1}, …, α_{N})$，可以得到不同的分形曲线。

根据Franklin函数系的多分辨率特性以及频谱按层整体修改的方案，参数向量$\mathit{\boldsymbol{\alpha }}$低位分量对应频谱的低频部分，它们主要影响分形曲线的总体结构；反之，参数向量$\mathit{\boldsymbol{\alpha }}$高位分量对应频谱的高频部分，它们主要影响分形曲线的细节特征。这些基本原则对本文提出的分形曲线生成的频域方法具有重要的指导意义。综上，通过对Franklin-谱的修改，再经过正交重构即可生成丰富多样的分形曲线。

4 实验

4.1 分形曲线在不同分辨率下的逼近

对参数向量做特殊设置，即

$ {\mathit{\boldsymbol{\alpha }}_k} = \sum\limits_{i = 1}^{k - 1} {{\mathit{\boldsymbol{e}}_i}} ,k = 2,3, \cdots ,N $ (15)

式中，$\boldsymbol{e}_{i}$表示第$i$个分量为1的基本行向量。当参数向量取$\mathit{\boldsymbol{\alpha }}_{k}$时，根据式(14)所得的结果为原分形曲线在第$k$级分辨率下的逼近。

图 6(a)为第6级von Koch曲线，是由4 096段组成的折线，该分形曲线可以在$N=12$层Franklin函数系下精确表达，即频谱向量为$\mathit{\boldsymbol{\lambda }}_{n}$，$n=1, 2, …, 12$。那么，根据式(8)，可以取不同的参数向量$\mathit{\boldsymbol{\alpha }}_{k}$得到相应分辨率下的逼近曲线，如图 6(b)—(i)所示。



图 6 von Koch曲线在不同分辨率下的逼近
Fig. 6 Approximation of von Koch curves at different resolutions((a) von Koch curve (level 6, segment 4 096); (b) $\mathit{\boldsymbol{\alpha }}_{11}=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0)$; (c) $\mathit{\boldsymbol{\alpha }}_{10}=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0)$; (d) $\mathit{\boldsymbol{\alpha }}_{9}=(1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0)$; (e) $\mathit{\boldsymbol{\alpha }}_{8}=(1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0)$; (f) $\mathit{\boldsymbol{\alpha }}_{7}=(1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0)$; (g) $\mathit{\boldsymbol{\alpha }}_{6}=(1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0)$; (h) $\mathit{\boldsymbol{\alpha }}_{5}=(1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0)$; (i) $\mathit{\boldsymbol{\alpha }}_{4}=(1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0$))

图 7(a)为第6级Sierpinski square曲线，也是由4 096段组成的折线。图 7(b)—(j)显示了不同的参数向量$\mathit{\boldsymbol{\alpha }}_{k}$下得到的逼近曲线。



图 7 Sierpinski square曲线在不同分辨率下的逼近
Fig. 7 Approximation of Sierpinski square curves at different resolutions
((a)Sierpinski square curve; (b) $\mathit{\boldsymbol{\alpha }}_{11}$; (c) $\mathit{\boldsymbol{\alpha }}_{10}$; (d) $\mathit{\boldsymbol{\alpha }}_{9}$; (e) $\mathit{\boldsymbol{\alpha }}_{8}$; (f) $\mathit{\boldsymbol{\alpha }}_{7}$; (g) $\mathit{\boldsymbol{\alpha }}_{6}$; (h) $\mathit{\boldsymbol{\alpha }}_{5}$; (i) $\mathit{\boldsymbol{\alpha }}_{4}$; (j) $\mathit{\boldsymbol{\alpha }}_{3}$)

可以看出，随着参数向量$\mathit{\boldsymbol{\alpha }}_{k}$中对应的高频分量逐步置零，重构曲线在不同尺度上仍然保留了原始分形曲线的形态特征。这一结果再次说明Franklin频谱能够有效刻画分形曲线的特征。

4.2 基于经典分形曲线生成新的分形曲线

对参数向量不再局限于简单的置零操作，而是进行更为自由地修改，继而对修改后的Franklin频谱进行正交重构得到新的分形曲线。显然，通过这种方法可以生成无限多个不同的分形曲线，图 8—图 10仅列出基于von Koch分形曲线、Sierpinski分形曲线和Hilbert分形曲线生成的若干代表性的结果，每个新分形曲线下方标有对应的参数向量。可以看出，只要改变参数向量的极少数的分量，就会产生形态迥异而丰富多姿的分形曲线。这种对分形在频域上的处理手段，为分形的生成提供了新的思路与方案。



图 8 基于von Koch曲线的分形曲线生成
Fig. 8 Fractal curve generation based on von Koch curve



图 9 基于Sierpinski square曲线的分形曲线生成
Fig. 9 Fractal curve generation based on Sierpinski square curve



图 10 基于Hilbert曲线的分形曲线生成
Fig. 10 Fractal curve generation based on Hilbert curve

5 结论

提出了一种分形曲线生成的新方法，称为Franklin频域方法。从信号处理的角度来看，有限分辨率下的分形曲线是一类分段线性函数, 是具有连续性但不具有光滑性的信号。将这类信号重新表达在由Franklin函数组成的正交函数空间中，从而得到分形的频谱。Franklin频谱准确地刻画了分形曲线的多尺度特征。在此理论基础上，构造了一类频谱调节因子，从而实现了对Franklin频谱定性与定量相结合的修改。

不同频段的Franklin频谱反映了分形曲线不同尺度上的特征，频谱调节因子实现了对分形曲线的滤波。只要修改频谱调节因子便可以得到相对应的分形曲线，从而实现了分形曲线的生成。

传统的分形生成方法主要通过对生成元在不同尺度上进行迭代复制而得到最终的分形，所有的操作都在空间域中进行。当选定生成元图形后, 最终的分形结果就基本确定，改变余地十分有限。运用本文方法，只要修改频谱就可以得到大量的新型分形曲线，而且这些分形的样式是千变万化的，几乎不可预测，这种分形生成方式为分形设计带来了巨大的自由空间。

作为一项探索性研究工作, 本文方法无论在理论上还是在实践应用中都仍有许多问题需要解决。包括频谱与分形维数之间的内在联系、分形频谱的机理性解释、分形图案的频谱编辑方法等一系列问题，尚需进行更深入的理论及应用研究。

参考文献

  • Barseley M F. 1988. Fractal Everywhere. New York: Academic Press
  • Cai Z C, Chen W. 2013. Least square approximation and analysis for scattered data based on orthogonal GF system. Acta Scientiarum Naturalium Universitatis Sunyatseni, 52(5): 73-77 (蔡占川, 陈伟. 2013. 基于正交GF系统的散乱数据拟合及分析. 中山大学学报(自然科学版), 52(5): 73-77)
  • Cai Z C, Chen W, Qi D X, Tang Z S. 2009. A class of general Franklin functions and its application. Chinese Journal of Computers, 32(10): 2004-2013 (蔡占川, 陈伟, 齐东旭, 唐泽圣. 2009. 一类新的正交样条函数——Franklin函数的推广及其应用. 计算机学报, 32(10): 2004-2013)
  • Chen W, Cai Z C, Qi D X. 2015. Orthogonal Franklin moments and its application for image representation. Chinese Journal of Computers, 38(6): 1140-1147 (陈伟, 蔡占川, 齐东旭. 2015. 一类新的正交矩-Franklin矩及其图像表达. 计算机学报, 38(6): 1140-1147) [DOI:10.11897/SP.J.1016.2015.01140]
  • Chen W, Qi D X. 2013. Polygonal approximation of digital curves based on Franklin function. Journal of Computer-Aided Design and Computer Graphics, 25(7): 980-987 (陈伟, 齐东旭. 2013. 基于Franklin函数的数字曲线多边形逼近. 计算机辅助设计与图形学学报, 25(7): 980-987) [DOI:10.3969/j.issn.1003-9775.2013.07.007]
  • Conti C, Hormann K. 2011. Polynomial reproduction for univariate subdivision schemes of any arity. Journal of Approximation Theory, 163(4): 413-437 [DOI:10.1016/j.jat.2010.11.002]
  • Demko S, Hodges L and Naylor B. 1985. Construction of fractal objects with iterated function systems//Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques. Boston: ACM: 271-278[DOI:10.1145/325165.325245]
  • Ding W, Qi D X. 1998. Recursive refinement algorithm of fractal generation and it's application. Journal of Image and Graphics, 3(2): 123-128 (丁玮, 齐东旭. 1998. 分形生成的递归细化算法及应用. 中国图象图形学报, 3(2): 123-128) [DOI:10.11834/jig.19980229]
  • Dremin I M. 2005. Wavelets:mathematics and applications. Physics of Atomic Nuclei, 68(3): 508-520 [DOI:10.1134/1.1891202]
  • Dyn N, Levin D, Gregory J A. 1987. A 4-point interpolatory subdivision scheme for curve design. Computer Aided Geometric Design, 4(4): 257-268 [DOI:10.1016/0167-8396(87)90001-X]
  • Falconer K J. 1985. The Geometry of Fractal Sets. Cambridge: Cambridge University Press [DOI:10.1017/CBO9780511623738]
  • Franklin P. 1928. A set of continuous orthogonal functions. Mathematische Annalen, 100(1): 522-529 [DOI:10.1007/BF01448860]
  • Gregory J A, Qu R B. 1996. Nonuniform corner cutting. Computer Aided Geometric Design, 13(8): 763-772 [DOI:10.1016/0167-8396(96)00008-8]
  • Hu Y, Zheng H C, Geng J. 2019. Calculation of dimensions of curves generated by subdivision schemes. International Journal of Computer Mathematics, 96(6): 1278-1291 [DOI:10.1080/00207160.2018.1438601]
  • Kaur M, Sivia J S. 2019. Minkowski, Giuseppe Peano and Koch curves based design of compact hybrid fractal antenna for biomedical applications using ANN and PSO. AEU-international Journal of Electronics and Communications, 99: 14-24 [DOI:10.1016/j.aeue.2018.11.005]
  • Li W J, Zhao H P, Shang S N. 2017. Onboard ship saliency detection algorithm based on multi-scale fractal dimension. Journal of Image and Graphics, 22(10): 1447-1454 (李文娟, 赵和平, 尚叔楠. 2017. 多尺度分形维的星载舰船显著性检测. 中国图象图形学报, 22(10): 1447-1454) [DOI:10.11834/jig.160529]
  • Liu C K. 1982. Orthogonal Functions and Its Applications. Beijing: National Defence Industry Press (柳重堪. 1982. 正交函数及其应用. 北京: 国防工业出版社)
  • Liu H Y, Sui T, Xu Z, Zhu W Y. 2008. Research on periodicity of general M-J chaos-fractal images generated by Fibonacci sequence. Journal of Image and Graphics, 13(3): 536-540 (刘鸿雁, 隋涛, 徐喆, 朱伟勇. 2008. Fibonacci序列构造广义M-J混沌分形图谱周期性的研究. 中国图象图形学报, 13(3): 536-540) [DOI:10.11834/jig.20080327]
  • Mandelbrot B B. 1983. The Fractal Geometry of Nature. New York: Freeman
  • Mandelbrot B B. 1985. Self-affine fractals and fractal dimension. Physica Scripta, 32(4): 257-260 [DOI:10.1088/0031-8949/32/4/001]
  • Meyer Y. 1993. Wavelets:Algorithm and Applications. Philadelphia: SIMA Press
  • Mustafa G. 2017. Statistical and geometrical way of model selection for a family of subdivision schemes. Chinese Annals of Mathematics, Series B, 38(5): 1077-1092 [DOI:10.1007/s11401-017-1024-6]
  • Peitgen H O, Jürgens H, Saupe D. 2012. Chaos and Fractals:New Frontiers of Science. New York: Springer Press [DOI:10.1007/978-1-4757-4740-9]
  • Qi D X. 1994. Fractal and Its Computer Generation. Beijing: Science Press (齐东旭. 1994. 分形及其计算机生成. 北京: 科学出版社)
  • Qi D X, Song R X, Li J. 2011. Non-Continuous Orthogonal Functions. Beijing: Science Press (齐东旭, 宋瑞霞, 李坚. 2011. 非连续正交函数-U-系统、V-系统、多小波及其应用. 北京: 科学出版社)
  • Siddiqi S S, Idrees U, Rehan K. 2014. Generation of fractal curves and surfaces using ternary 4-point interpolatory subdivision scheme. Applied Mathematics and Computation, 246: 210-220 [DOI:10.1016/j.amc.2014.07.078]
  • Smith A R. 1984. Plants, fractals, and formal languages//Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM: 1-10[DOI:10.1145/964965.808571]
  • Song R X, Zhu J W, Wang X C. 2016. Spectrum analysis of fractals based on orthogonal decomposition. Journal of Computer-Aided Design and Computer Graphics, 28(3): 488-497 (宋瑞霞, 朱建旺, 王小春. 2016. 分形的正交频谱分析. 计算机辅助设计与图形学学报, 28(3): 488-497) [DOI:10.3969/j.issn.1003-9775.2016.03.015]
  • Xiong G Q, Qi D X. 2010. Algorithm of image encoding based on U-orthogonal transform. Journal of Image and Graphics, 15(11): 1569-1577 (熊刚强, 齐东旭. 2010. 基于U-正交变换的图像编码算法. 中国图象图形学报, 15(11): 1569-1577) [DOI:10.11834/jig.20101113]