基于子结构匹配方法的多规则L系统反演研究样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
基于子结构匹配方法的多规则L系统反演研究
Research on the inverse problem of mutil-rules Lindenmayer System  based on substructure matching
朱元伟
摘　要:由已知的L系统的结果字符串寻找出原来的初始公理和产生式规则集是L系统反演的主要工作。本文以L系统的自相似特点为基础, 经过子结构的分层匹配算法实现带有两个限定条件的L系统字符串的反演, 能够简便准确获取L系统初始公理和产生式规则集。算法主要包含4个步骤:分割最终字符串并建立子结构池;对子结构池中包含其它子结构的字符串进行进一步分割; 经过与各层次回溯得到的子结构匹配, 取得子结构与产生式前驱之间的对应关系; 经过回溯迭代过程得到其最简形式, 获得初始字符串; 试验中, 所有被测试的字符串都能够被反演到等价L系统规则集。
关键词: L系统;虚拟植物; L系统反演;子结构匹配

Abstract—Finding out the set of original rules is the main work of  the inversion of  Lindermayer system .The algorithm of this paper obtain a set of rules from a long Lindenmayer string with two conditions by matching sub-structures. The algorithm consists of five steps: divide the Lindenmayer string into substrings recursively and push them into the sub-structure buffer pool;further divide the sub-structure which contains others in the pool;replace the sub-structures in Lindenmayer by the identifier in the pool then do repeat as in the previous step.Using the newly obtained sub-structure match structures in buffer pool to get the map relationship between sub-structures and predecessors; replacing repeated string with a predecessor char that marking the same string in the pool, and continuing this process recursively until get the original axiom. In the tests carried out, all the Lindenmayer strings could be reverted to a set of Lindenmayer rules that identical to the original rules used to generate the string.
Key-words: L-system; virtualplant; Inverse problems; substructure matching Problems

引言:
L系统不但被用于植物的形态模拟 [1], 还被用于数据压缩[2]、 加密解密[3][4]、 音乐生成[5] [6]、 IP网络流量工程( Traffic engineering of IP networks) [7]等领域。这些问题都需要用到L系统的反演过程。自L系统1968年诞生以来[8],其有诸多学者研究了其反演过程。其中, 在文[9]提出GLP( Genetic L-System Programming) 思想之后, 文[10][11][12][13]经过GLP对特定植物结构形态的L系统反演进行了有益的探索。但GLP需要大量计算、 比较, 结果也具有不稳定性。文[14]则提出一种基于统计规律的方法。统计方法能够显著减少计算量, 但作者提出的算法只能应用于单符号的二维DOL系统。文[15]提出了基于裂解法获取L系统初始公理和产生式集合的方法。裂解法具有较好的精度, 但需要经过复杂的裂解过程, 只能处理容量不大的数据, 要将这些结果组织为能够识别的形式还需某些额外的开销。文[16]对单个产生式的DOL系统提出了一种经过回溯迭代过程获得初始公理和产生式组的方法。这种方法具有比较高的效率, 可是只能解决单个产生式规则的情况。本文受植物结构自相似特点的启发, 提出了一种子结构分层匹配的算法。该方法充分利用L系统整体结构与子结构的相似性, 能够在不考虑迭代次数的情况下, 寻找到具有等价效果的多规则L系统的产生式规则集。最后, 本文给出了一个算法的应用举例。

1.L系统基础。
L 系统是由一条初始公理和若干条产生式规则组成的并行重写系统,能够很好的描述具有自相似特征的植物的拓扑结构和生长规律。 L系统有多种类型, 主要有DOL系统、 随机L系统、 参数L系统、 微分L系统以及上下文相关 L 系统等。下面以DOL系统为例说明其基本原理, 一个DOL系统是一个三元式:
L=<V, ω, P>
V是一个字母表, V中的元素用来组成表示图形命令的字符串;
ω是初始公理, 用以确定L系统及其对应图形的起始状态, 而且ω∈V;
P是产生式的有限集合, 形式为a->x, 分别称字符a和字符串x为产生式的前驱和后继。如果没有明确的为a∈v指定重写产生式, 则a->a, 且产生式(a, a)∈P。
L系统从一个初始公理开始, 应用产生式规则进行有限次, 最终得到一个表示分形图的字符串。例如:
初始公式ω: F
产生式 P: F->F[-F][+F]F
表一 L系统的迭代过程示例
迭代步数
迭代结果
0
F
1
F[-F][+F]F
2
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F] F[-F][+F]F
3
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F][+F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F]F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F
为使获得的最终字符串能描绘出图形, 需要对其进行适当的几何解释, 即对字符串中的每个字符赋予一个特定的图形含义。最常见的方法称为”龟图解释”。
二维平面上的龟图解释一般会将字符定义为表二的动作:
表 二 龟图解释中字符对应的动作
字符
动作
说明
F
龟向前移动一步, 步长为d, 并从原先位置到当前位
置画一直线。
d 为预先定义的一个步长长度。
+
前进方向逆时针旋转δ°。
δ为预先定义的角度。
-
前进方向顺时针旋转δ°。
[
将当前状态压入堆栈。
当前状态一般包括位置和前进方向
]
从堆栈中弹出一个状态作为当前状态。
图1是在角度δ=30°, 迭代次数n=0,1,2时, 使用如下初始公式和产生式所生成的图形。
初始公理ω: F
产生式 P: F->F[-F][+F]F

n=0 , δ=30° n=1 , δ=30° n=2 , δ=30°
图一 , L系统产生的图形示例

2.L系统的图形子结构与字符串子结构
子结构是个相正确概念 ,也是个递归的概念, 植物主干上的一个侧枝便是植物的一个子结构。文献[17]中最早提出子结构思想。现在学者多将子结构算法作为一种提高计算机的仿真速度的途径。其算法是首先产生一个(对于确定性L系统)或若干个(对于随机L系统)具有相同属性的子结构, 当这些子结构出现在其它子结构中时, 不需要重复计算, 直接使用已有的子结构中的信息[18]。
子结构在图形表现为上植物的分支结构, 在图形对应的字符串上则表现为这个字符串的一个子串。例如:
图2( b) 是图2( a) 的子结构。对应的字符串为( 一个连续的下划线表示一个子结构) :
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F [-
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F][+
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F]
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F
图2( c) 是图2( b) 的子结构, 对应的字符串为( 一个连续的下划线表示一个子结构) :
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F

(a) (b) (c)
图 二 子结构的图形示意图
3.多规则L系统的反演方法
3.1定义
最小子结构: 当一个结构不再包含与自己相同形式的子结构时, 称为对这个形式的最小子结构。在本文中对应于一个L系统产生式的后继字符串。
次最小子结构: 与最小子结构对应的, 最小子结构经过按一定次序组合产生的子结构。
最小子结构的组合: 最小子结构对应的字符串经过一定的次序排列而产生的字符串序列。
等价L系统: 如果两个不同的L系统, 经过各自的迭代, 能够产生相同的结果字符串, 则称这两个L系统为等价L系统。

图三 最小子结构示意图( 椭圆区域为最小子结构)
L系统规则的反演是L系统迭代的逆过程。必须指出, 不同的L系统规则集合可能推出完全相同的字符串序列。而且 ,任意非空字符串S,都能够是某个规则集合的结果字符串。只需定义ω:A, A->S, 经过一步推导即可。虽然对任意非空串都能够定义逆过程,但它所推得的L系统不惟一, 我们的目标是获得一个经过够迭代产生S字符串的产生式规则集合。

3.2字符串的反演算法

限定条件说明:
1.产生式有且只有一层括号, 且以非终结符开始。
2.在2次迭代字符串中包含所有非终结符, 反演字符串是2次迭代以后的结果。

因为每个产生式的前驱都会出现在最终字符串中, 因此具有如下结论:
定理1: L系统迭代的最终字符串, 包含所有的最小子结构而且完全是由最小子结构字符串经过组合而成。
证明( 归纳法) : 设iter为迭代次数, S为迭代iter次的结果字符串。则
（1） 证明当iter=2时满足上述定理。由于iter=1时, S是某个产生式的后继, 而且根据限定条件2, 包含所有的非终结符。经过并行将所有的非终结符替换为后继, 因此iter=2的S包含所有产生式后继, 而且完全由产生式后继组合而成。
（2） 假设当iter=n时满足条件, 证明当iter=n+1时也满足条件。因iter=n时, S是由最小子结构组合而成, 又因为最小子结构是由产生式前驱构成, 而且包含所有非终结符。经过一次迭代产生的iter=n+1的字符串S, 则是由非终结符被对应的产生式后继替换而得到, 因此iter=n+1时, S是由产生式后继组合而成, 而且包含所有的产生式后继。
定理2: 经过对每层子结构递归使用至少具有两层的括号分割, 能够得到完整的最小子结构或者最小子结构的组合。
证明: 由限定条件可知, 所有的产生式括号层次最多为一层。因此至少具有两层的括号内的字符串至少经过了一次替换, 括号内所有的非终结符已被替换为完整的最小子结构。同样, 由于替换是并行进行的, 括号外的非终结符也全部被替换为完整的最小子结构。因此, 以至少为两层的括号为界分割的子结构, 是完整的最小子结构或者最小子结构的组合。

在匹配过程中需要一个子结构缓冲池保存各个阶段产生的子结构字符序列。子结构缓冲池结构如下:
子结构标识
字符串
非终结符个数
最小子结构序列

多产生式DOL系统字符串的反演算法:
1. 获取各级子结构中包含的最小子结构以及次小子结构。以高于当前括号层次两层的括号为分割符, 递归取分割字符串S; 将字符串保存到子结构缓冲池中, 同时将原串中对应的字符串用缓冲池中的标识Pi(i=1,2,3...)替换形成字符串SS。
2. 测试子结构池中的子结构之间的整体包含情况。对缓冲池中的所有字符串Pi( i=1,2,3...) 与其它字符串进行包含测试。其中, 不包含其它字符串的子结构暂时设定为为最小子结构。经过再次匹配获得其它子结构中的最小子结构组成序列, 替换字符串SS中的相应标识, 使SS只由临时最小子结构的标识符组成; 更改缓冲池中相应的数据。
3. 经过对由( 2) 获得SS字符串进一步分割, 确定非终结符与最小子结构的对应关系。将字符串SS赋给S, 并将分割符去掉。进行( 1) ( 2) 操作, 将得到的关于Pi的字符串放入缓冲池中; 根据各个子结构非终结符个数和对应的”[”,”]”,”+”,”-”字符位置匹配缓冲池中的子结构。如果匹配成功, 则能够经过位置对应确定可迭代字符与最小子结构的对应关系。如果不成功, 说明当前得到的子结构是比缓冲池中已有子结构更小的单元。转到( 2) 操作, 将原有子结构进一步分解为更小的结构。
4. 回溯迭代过程, 获得初始公理。由于已经获得了组成当前字符串S的各个临时产生式后继, 能够经过递归方法, 把当前字符串按( 1) 进行分割, 经过与子结构池中匹配, 替换为相应非终结符的方法进行回溯。当回溯结果只有一层括号而且不能在子结构池中匹配到相同结构时停止, 这个字符串就是初始公理。
5. 经过上述步骤完整的获得了初始公理和产生式组。

在算法步骤( 1) 中, 由定理二能够得到其S字符串的最小子结构或者最小子结构的组合。而步骤( 2) 对包含另一个子结构的子结构字符串进行分割。步骤( 3) ( 4) 则进一步分割包含在回溯过程中产生的新字符串的子结构字符串。由限制条件2以及定理1可知, 缓冲池中的字符串已经包含所有的产生式后继, 因此回溯过程中获得的子结构一定是缓冲池中的结构或者是缓冲池中结构的子结构。经过匹配、 分拆, 最终可得到一个可产生被反演字符串S的产生式规则集合。

4.应用实例
需要反演的字符串:
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F
[+F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]FF[-F][+F]F[+F[-F][+F]FF[+FX]F[-X]+FX]F[-F][+F]F[-F[+FX]F[-X]+FX]+F[-F][+F]FF[+FX]F[-X]+FX]
F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]F
[-F[-F][+F]F[+F[-F][+F]FF[+FX]F[-X]+FX]F[-F][+F]F[-F[+FX]F[-X]+FX]+F[-F][+F]FF[+FX]F[-X]+FX]
+F[-F][+F]F[-F[-F][+F]F][+F[-F][+F]F]F[-F][+F]FF[-F][+F]F[+F[-F][+F]FF[+FX]F[-X]+FX]F[-F][+F]F[-F[+FX]F[-X]+FX]+F[-F][+F]FF[+FX]F[-X]+FX
( 1) 将字符串S按照括号层次进行递归分割为子结构之后的结果。”, ”为分隔符。
F[-F][+F]F,
[-F[-F][+F]F],
[+F[-F][+F]F],
F[-F][+F]F
[+F[-F][+F]F,
[-F[-F][+F]F],
[+F[-F][+F]F],
F[-F][+F]FF[-F][+F]F,
[+F[-F][+F]FF[+FX]F[-X]+FX],
F[-F][+F]F,
[-F[+FX]F[-X]+FX],
+F[-F][+F]FF[+FX]F[-X]+FX],
F[-F][+F]F,
[-F[-F][+F]F],
[+F[-F][+F]F],
F[-F][+F]F
[-F[-F][+F]F,
[+F[-F][+F]FF[+FX]F[-X]+FX],
F[-F][+F]F,
[-F[+FX]F[-X]+FX],
+F[-F][+F]FF[+FX]F[-X]+FX],
+F[-F][+F]F,
[-F[-F][+F]F],
[+F[-F][+F]F],
F[-F][+F]FF[-F][+F]F,
[+F[-F][+F]FF[+FX]F[-X]+FX],
F[-F][+F]F,
[-F[+FX]F[-X]+FX],
+F[-F][+F]FF[+FX]F[-X]+FX

子结构标识
字符串
非终结符个数
最小子结构序列
P1
F[-F][+F]F
4
P1
P2
F[-F][+F]FF[-F][+F]F
8
P2
P3
F[-F][+F]F F[+FX]F[-X]+FX
11
P3
P4
F[+FX]F[-X]+FX
7
P4

用缓冲池中标识替换对应字符串后的结果:
P1, [-P1], [+P1], P1[+P1, [-P1], [+P1], P2, [+P3], P1, [-P4], +P3], P1, [-P1], [+P1], P1[-P1, [+P3], P1, [-P4], +P3], +P1, [-P1], [+P1], P2, [+P3], P1, [-P4], +P3。
( 2) 最小子结构判别之后的缓冲池状态。
子结构标识
字符串
非终结符个数
最小子结构序列
P1
F[-F][+F]F
4
P1
P2
F[-F][+F]F F[-F][+F]F
8
P1P1
P3
F[-F][+F]F F[+FX]F[-X]+FX
11
P1P4
P4
F[+FX]F[-X]+FX
7
P4
只由最小子结构组成的字符串SS:
P1[-P1][+P1]P1[+P1[-P1][+P1]P1P1[+P1P4]P1[-P4]+ P1P4]P1[-P1][+P1]P1[-P1[+P1P4]P1[-P4]+P1P4]+P1[-P1][+P1]P1 P1[+P1P4]P1[-P4]+ P1P4。
( 3) 获取SS中最小子结构而且经过判别之后的缓冲池状态。
子结构标识
字符串
非终结符个数
最小子结构序列
P1
F[-F][+F]F
4
P1
P2
F[-F][+F]F F[-F][+F]F
8
P1P1
P3
F[-F][+F]F F[+FX]F[-X]+FX
11
P1P4
P4
F[+FX]F[-X]+FX
7
P4
P5
P1[-P1][+P1]P1
4
P5
P6
P1[+P1P4]P1[-P4]+P1P4
7
P6
经过匹配可得P1[-P1][+P1]P1 对应于F[-F][+F]F, P1[+P1P4]P1[-P4]+P1P4对应于F[-F][+F]F F[+FX]F[-X]+FX。经过取对应位置的字符, 可知道 子结构P1的前驱为F, P4的前驱为X。因此获得的产生式组为: F->F[-F][+F]F,X-> F[+FX]F[-X]+FX。
( 4) 获得初始公理的回溯过程。
在( 3) 步骤中, 已经获得了第一次回溯结果, 将Pi替换为对应的字符得到:
F[-F][+F]F[+F[-F][+F]FF[+FX]F[-X]+ FX]F[-F][+F]F[-F[+FX]F[-X]+FX]+F[-F][+F]F F[+FX]F[-X]+ FX。
第二次回溯结果: F[+FX]F[-X]+FX
第三层回溯结果: X
第三次回溯只有一个字符, 因此初始公理为 X。
经过上述的步骤, 获得的示例的初始公理和产生式组为:
初始公理: X
产生式: F->F[-F][+F]F,X-> F[+FX]F[-X]+FX。

5.结论
本文提出的将不同层次的子结构进行匹配、 分拆成临时最小子结构, 并经过回溯得到最初公理。算法既利用了L系统树形结构的自相似特点识别最小子结构, 又利用了子结构匹配中的计算的简单快捷。对多规则L系统的反演具有非常。但需要注意的是经过本文算法得到的不一定是原L系统规则集, 而是其等价L系统。今后的工作包括: 更宽松限定条件的L系统字符串的反演; 三维L系统字符串的反演; 以及将反演算法应用于对现实中树形结构L系统产生式的自动获取过程。

参考文献:
[1] 胡包钢, 赵星, 严红平．植物生长建模与可视化--回顾与展望[J]．自动化学报, , 27(6): 819-821．
[2] Nevill-Manning, C.G., Witten, Ian H. Identifying Hierarchical Structure in Sequences: A linear-time algorithm. Journal of Artificial Intelligence Re-search 7, 67–82, 1997.
[3] A.Salomaa,S.Yu.: On a public-key cryptosystem based on iterated morphisms and substitutions. Theoretical Computer Science,1986,283-296.
[4] 谭敬潘, 基于L系统的公钥密码体制的密钥生成和存储技术研究[G],中山大学, .
[5] P. Prusinkiewicz, ”Score generation with L-systems,”Proceedings of the 1986 International Computer Music Conference, 1986. 455–457.
[6] B. F. Lourenco, J. C. L. Ralha, M. C. P. Brandao,L-Systems, Scores, and Evolutionary Techniques,Proceedings of 6th Sound and Music Computing Conference, Portugal, , 113-118.
[7] Salvador, P., Nogueira, A., Valadas, R.: Modeling multifractal IP traffic: Characterization of packet arrivals and packet sizes using stochastic L-Systems. In: 10th International Conference on Telecommunication Systems, Modeling and Analysis, 577–587 ( )
[8] Lindenmay A．Mathematical models for cellular interaction in development, Parts I and
II[J]．Journal ofTheoretical Biology,1968,18:280-315.
[9] Jacob, C. Genetic L-System Programming: Breeding and Evolving Artificial Flowers with Mathematica, IMS 95, Proc. First International Mathematica Symposium, Southampton, Great Britain,ComputationalMechanics Publications, Southampton, UK, pp. 215-222, 1995.
[10]Humera Farooq, M.Nordin Zakaria, Mohd. Fadzil Hassan, and Suziah Sulaiman,:An Approach to Derive Parametric L-System Using Genetic Algorithm.H. Badioze Zaman et al. (Eds.): IVIC , LNCS 5857, pp. 455–466, . ©Springer-Verlag Berlin Heidelberg
[11]D.wang, D.J.Kerbyson, G.J.King, G.R.Nudd.: Realistic image synthesis of plant structures for genetic analysis.Image and Vision Computing 19( ) 517-522.
[12] Runqiang Bian, Jim Hanan, Norishige Chiba,Statistical data directed evolution of L-system models for botanical trees,4th International Workshop on Functional-Structural Plant Models, 7-11 june –Montpellier, France Edited by C. Godin et al., pp. 253-256.
[13]Bian R, Chen P'Burrage K et al．Derivation of L-system models from measurements of biological branching structures using genetic algorithms[R]．Lecture Notes in Computer Science 2358, , 514-524．
[14] 叶庆卫.基于单符号统计的简单L系统反演约束研究[J].中国图象图形学报. ,7(7).
[15]Fan yongbing,Chen gang,Dong guangchang.:Solving and analyzing PD0L inverse process,Science in China,44F(3),234-240,
[16]Edmar Santos, Regina Célia Coelho .:Obtaining L-systems Rules from Strings. Computational Modeling (MCSUL), Third Southern Conference on Computational Modeling. .11  23(25): 143 – 149. 
[17] Przemyslaw Prusinkiewicz,Aristid Lindenmayer. The Algorithmic Beauty of Plants,Springer-Verlag New York,Inc.1991.
[17]Yan H.P.,Barczi J.-F, Reffye De.Fast algorithm of plant computation based on substructure instances[A].In: International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision [C].Plzen,Czech, , 10(3): 145-153．
[18]张维统, 基于改进L-系统的植物形态可视化研究[G],浙江工业大学, .4