克隆算子在民族图案生成中的应用研究

刘战东，李 勇，张海军，赵彩霞

（1.新疆师范大学 计算机科学技术学院，新疆 乌鲁木齐 830054；2.乌鲁木齐市第八一中学 新疆 乌鲁木齐 830002）

新疆作为多民族的聚居区，蕴藏着丰富的民族传统艺术资源。新疆民间图案艺术是中华民族图案艺术的组成部分，它具有中华民族文化的特征，其展现出的灿烂的民族图案风格，反应了新疆各族人民的审美观和生活情趣。

当今，由于工业的突飞猛进，机织绣品代替了传统的手工刺绣，中华民族传统非物质文化遗产的保护问题，已引起社会各界人士的广泛关注。在民族风、怀旧风盛行的今天，新疆民族图案在纺织、印刷、雕刻、陶瓷、建筑、娱乐、动画等诸多行业中逐渐被推广应用。因此如何满足人们日益增长的精神文化的需要，既充满民族情调而又不失现代精神的创新形式走到了现代设计的前沿，已成为艺术设计师急需解决的问题，同时也成了学术界研究的焦点。

采用民族图案设计原理和方法，利用计算机图案数据处理技术，可以对民族图案进行设计；此外也可以选用以算法为基础的设计方法来对民族图案进行设计[1]。采用侧重于生成规则描述的非线性理论来生成创新性图案是非常合适，但是这种方法生成的图案并不能保证民族图案原始纹饰图案的特点和图案的民族情调。如果通过合适的算法来生成图案就可以保留图案原有的民族情调，其研究意思将更具有应用价值。文中的侧重点是分析新疆民族艺术图案的差异与相似性，提取出能表征民族情调的特征（纹饰图案基元符号）；采用免疫算法中的克隆算子来对纹饰图案基元符号进行操作，操作后在不破坏整体图案的情况下，保证整体图案的民族风格得以传承和发扬。

1 相关研究

目前，国内外关于不同民族传统图形的研究成果较少[2-3]，在已发表文献中只有伊斯兰星形图案、印度Kolam图案、植物纹装饰图案以及中国的剪纸图案等方面的研究。

1.1 计算机辅助图案生成

在剪纸图案研究方面[4-5]，浙江大学的潘云鹤教授和孙守迁教授在该领域的研究取得了突破性成果，并提出了计算机辅助生成剪纸图像的方法[6]，该方法在图案的构图、色彩描绘、草图设计及知识表达方面被广泛地应用。一种支持外观造型创新设计的进化计算方法[7]，由山东师范大学的刘弘教授和刘希玉教授提出。此外，在面向产品的概念设计方面，产品基因的概念被提出，该概念被广泛地应用于产品信息分类、仿生设计、功能模块划分和结构生长型创新设计等方面。

1.2 基于智能算法的图案生成

最近几年，在国内外，遗传算法被计算机设计人员应用到计算机辅助创新设计中，并且取得了很多令人满意的成果[7]。在文献[1]中，新疆师范大学的赵海英博士首次提出借用生物学基因词汇来定义图案元素，阐述了图案生成的方法，该方法在多图案整合和控制组合规则再生图案方面存在一定的局限性；为克服该局限性，赵海英博士计划引入人工智能和其它智能算法对图案基因变换，进而控制图案生成过程[8]。

1.3 基于分形理论的图案生成

在国外，很多学者利用数学理论提出了生成图案的模型和算法[9]。Barnsley讨论了迭代函数系统的生成方法：主要有确定性算法与随机性算法，通过调整IFS的参数来生成大量图案，该方法成功应用于纺织艺术图案设计方面，为纹饰图案的设计提供了新的设计思路。1968年，丹麦植物学家A Lindenmayer提出了一个植物形态学模型，简称为L系统。20世纪80年代由A R Smith和P Prusuikieuicz等人将L系统引入计算机图形学，为自然景物的计算机模拟提供了有效方法。将IFS与L系统相结合，可以实现植物类纹饰图案的生成，利用该方法可以较好地解决民间纹饰图案中植物形状的花型。但是根据实物植物叶子的形状和大小，如何自动地控制IFS的参数、L系统的角度和长度的参数随机扰动是一个有待进一步研究的问题。

2 克隆免疫算法模型

2.1 基本概念

定义1民族图案基元：是指在一个民族图案中多次重复的、封闭的、不可再分的图案基本单位。在文中民族图案基元是指亲和度解空间中的点。

定义2民族图案元：经过抽象、合成、纯化等艺术手法处理而成 “有意味的形式”的、且具有民族风格及地域特点的图案信息单元。

定义3民族图案再生元：由民族图案基元按照一定的变换规则和排列规则生成的图案信息单元。

定义4抗体[10]：在人工免疫系统中，抗体一般指问题的侯选解。在本文中，抗体是指民族图案元。

定义5抗原[10]：在人工免疫系统中，抗原一般是指问题目标函数的函数。

定义6抗体-抗原亲合度[10]：在人工免疫系统中，抗体-抗原亲合度具体反映了抗体与抗原之间结合能力。

定义7抗体-抗体亲合度[10]：抗体-抗体亲合度指不同抗体间的距离，它具体反映了抗体与抗体之间结合能力。

2.2 克隆算子

根据抗原与抗体间亲合度函数f（*），把解空间中任意一个点 ai（k）∈A（k）复制成 qi个相同的点 a′i（k）∈A′（k），然后利用免疫基因操作、克隆选择变换操作来获得新的抗体群。克隆算子包括4种操作：克隆、免疫基因、克隆选择和克隆死亡[10]，如图 1所示。

图1 克隆算子的操作过程Fig.1 Process of clone operator operation

免疫学家普遍认为，抗体间亲合度成熟和抗体多样性的产生主要是通过抗体的高频变异来实现的。

①变异：为了保留抗体原始种群的信息，克隆算法的变异只作用到克隆的抗体上：

②交叉：为了保留抗体原始种群的信息，克隆算法的交叉只作用到克隆的抗体上：

2.3 民族图案生成算法

通过分析民族图案的特点，抽取能表征民族内涵的民族图案元，利用克隆算子生成新的图案。算法步骤如下所示：

Step 1输入民族图案；

Step 2生成民族图案基元；

Step 3克隆算子对民族图案基元进行操作；

Step 4生成民族图案元和再生图案元。

3 图案生成举例

图2为从栽绒地毯图像中提取的4种纹饰图案基元；图3是由4种纹饰图案基元通过克隆算子的4种操作后生成的图案元。图4是由12种图案元通过组合生成的再生图案元。

图2 4种图案基元Fig.2 Four pattem primitives

图3 12种图案元Fig.3 Twelve pattern elements

图4 6种再生图案元Fig.4 Six patem elements

4 结束语

论文提出了民族图案基元、民族图案元和民族图案再生基元的概念。民族图案基元通过克隆、免疫基因、克隆选择和克隆死亡4种操作后生成新的图案基元，使其在继承并传统民族图案内涵的情况下，生成了新的民族图案元和再生图案元。

将克隆算子应用于民族图案生成方法的研究中，通过控制克隆算子4种操作中的一种或几种操作就可以快速生成多种图案元。利用该方法生成的民族图案，可以有效保证图案民族内涵基本不变的情况下得到传承和发扬；同时也为民族非物质文化遗产的保护提供了新的思路。为了生成复杂的、不规则的民族图案，下一步的工作重点是将克隆算子和分形学理论相结合，对民族图案的生成过程进行控制。

[1]赵海英，杨一帆，徐光美.新疆民族民间艺术图案生成方法[J].计算机系统应用，2011，20（7）：94-99.

ZHAO Hai-ying，YANG Yi-fan，XU Guang-mei.Design method for Xinjiang folk art pattern[J].Computer Systems&Applications，2011，20（7）：94-99.

[2]张显全，于金辉，蒋凌琳，等.基于纹样的计算机剪纸系统[J].计算机工程，2006，32（11）:248-250.

ZHANG Xian-quan，YU Jin-hui，JIANG Ling-lin，et al.Computer paper cut-out system based on decorative pattern[J].Computer Engineering，2006，32（11）:248-250.

[3]李岩.面向特征的传统艺术图案建模技术研究 [D].杭州:浙江大学，2007.

[4]张显全，于金辉，蒋凌琳，等.计算机辅助生成剪纸形象[J].计算机辅助设计与图形学学报，2005，17（6）:1378-1382.

ZHANG Xian-quan，YU Jin-hui，JIANG Ling-lin，et al.Computer assisted generation of paper cut-out images[J].Journal of Computer-Aided Design&Computer Graphics，2005，17（6）:1378-1382.

[5]彭冬梅.面向剪纸艺术的非物质文化遗产数字化保护技术研究[D].杭州:浙江大学，2008.

[6]黄琦，孙守迁，张立珊.面向产品创新的3维草图设计技术研究[J].计算机集成制造系统，2007，13（2）:224-227.

HUANG Qi，SUN Shou-qian，ZHANG Li-shan.Threedimension sketch design oriented to product innovation[J].Computer Integrated Manufacturing Systems，2007，13 （2）:224-227.

[7]刘涛，刘弘.基于遗传算法的剪纸图案创新设计[J].计算机工程与应用，2008，44（12）:75-77.

LIU Tao，LIU Hong.Creative design of paper cut-out based ongeneticalgorithm[J].ComputerEngineeringandApplications，2008，44（12）:75-77.

[8]赵海英，惠雯，徐光美.一种新的图案纹样生成方法[J].计算机系统应用，2011，20（3）:85-89.

ZHAO Hai-ying，HUI Wen，XU Guang-mei.A new method for pattern generation[J].Computer Systems&Applications，2011，20（3）:85-89.

[9]郑自然，刘希玉.基于遗传算法的适合纹样花卉图案设计方法[J].山东师范大学学报：自然科学版，2006，21（3）:36-38.

ZHENG Zi-ran，LIU Xi-yu.A method of flower pattern design based on genetic algorithm[J].Journal of Shandong Normal University:Natural Science，2006，21（3）:36-38.

[10]刘战东，付涛，戴玉刚，等.基于区间套理论的克隆选择算法的收敛性研究[J].计算机工程与科学，2010，32（5）:57-59.

LIU Zhan-dong，FU Tao，DAI Yu-gang，et al.A study on the convergence of the clonal selection algorithm based on the interval sheath theorem[J].Computer Engineering&Science，2010，32（5）:57-59.