基于进化计算的地毯图案生成方法

赵海英， 彭 宏， 张小利

(1. 北京邮电大学世纪学院移动媒体与文化计算北京市重点实验室，北京 102613；2. 新疆师范大学网络教育学院，新疆 乌鲁木齐 830054)

基于进化计算的地毯图案生成方法

赵海英1， 彭 宏2， 张小利1

(1. 北京邮电大学世纪学院移动媒体与文化计算北京市重点实验室，北京 102613；2. 新疆师范大学网络教育学院，新疆 乌鲁木齐 830054)

新疆民族地毯图案具有独特的地域性、民族性和风格，如何保留和传承其风格特征是图案创新设计的难点。提出一种基于进化计算的创新设计方法。可通过分解地毯图案，分析其组成元素，抽取具有表征风格的特征予以进化计算，再生新型纹样，设计中还可以调整图案内容及结构来丰富花型变化，并通过不同顺序关系中元素组合增强图案的表现力，仿真实验表明该方法实现了生成具有风格化的创新图案，借助于主客观评价模型得到很高地认可。

进化计算；图案生成；图案基因；创新设计

图案创新设计是计算机应用领域中一个崭新而又活跃的重要分支[1-6]，它的应用面极广，且对国民经济建设有着重大作用。如何利用计算机自动生成新疆民族地毯图案是一个富有挑战的研究课题。新疆民族织物图案的组成比较复杂，时空跨度大、花型多、风格各异，包含了许多蜿蜒的、不规则的几何图形和植物纹。使得图案难以用传统的曲线或曲面描述，给图案特征提取与创新设计带来很大困难。该课题的研究难点在于：图案花型种类较少；设计的图案不能传承一定风格，缺少文化内涵的揭示；而各种新工具、新技术的出现仍然需要新的设计方法。进化设计是基于图案原来规则和设计经验，创新设计是一种风格的传承、变异和组合模式，通过创新将设计出更多具有新风格的地毯图案。因此，该文引入进化计算来传承具有一定民族风格的新疆地毯图案。

1 相关工作

艺术设计工作中很大一部分工作是艺术图案设计[7]，如轻纺行业的花布和地毯的花纹图案与色彩设计；服装行业的服装款式设计、排料和放样及衣料裁切设计等。如何搭建花纹图案自动生成系统，有助于设计师灵活、方便而迅速地设计出花布和毛毯图案，并通过用户的挑选进一步修改，获得用户满意的设计图案。在实际工作中常常需要将绘图和计算相结合，即所谓形数结合。实践证明，任何一个图形都可以用数学方程表示及讨论；反之，数学问题也可以用图形来描绘。这就为形与数结合的可行性提供了依据。

作者的数字文化研究团队在前期已经提出并完成了一些传承新疆民族风格的设计方法。其一，提出了对称性和随机性相结合的图案生成方法。通过对导入的初始图案进行双线性插值运算，生成一个正三角形作为第一个等边纹样基元；然后通过正反 120°旋转，扩展成两个等边基元；再利用对称和旋转变换把随机选择的不同等边纹样基元嵌入到六边形构型中，最后平铺六边形构型生成一幅新图案。其二，随机选择基元、堆砌对称构型和无缝平铺纹样。方法简单易用，且可传承新疆民族织物图案的对称性和稠密性。其三，提出了基于图像变形的图案生成算法[8]。先定义两类基因生成方法，然后对图元基因或再生基因进行组合变形即可获得创新图案。其四，提出了基于图像扰动的图案生成算法[9]。需引入交互分割模型提取图案中具有代表性的意义相对独立的图案基元，设计图案基元的相似变换规则，产生分形基元矩阵；然后引入准Arnold变换规则，对基元分形矩阵进行扰动以生成新图案。为了拓宽图案生成方法的适用范围，本论文引入进化计算进行图案设计。

进化设计[10]是一种将进化计算用于计算机辅助设计的技术，是一种基于实例的设计方法。针对以往的设计实例需要变化、修改和完善的设计过程，进化设计方法在一定程度上增加了设计重用性，提高了设计速度。图案进化设计作为进化计算与设计理论结合的一个新领域，成为人工智能原理应用到数字艺术的核心课题之一，也成为进化计算在应用方面的一个重大突破[11-13]——图案进化生成是最成功的商业形式之一。进化作品作为进化设计系统的产物，在各个应用领域中扮演着重要的角色。大部分的“进化设计”系统基本上都是基于 1999年 Bentley[14-15]设计系统发展而来的。系统随机构建初始群体中的个体，然后在用户审美选择中完成变异、交配的优胜劣汰。具有上百年甚至上千年的新疆民族织物图案在历史的演变过程中也遵循着遗传、变异、选择等优胜劣汰的自然选择规则和竞争机制。论文基于此研究思路把进化设计、组合变形应用到图案创新上。实验结果表明，该方法可以有效传承新疆民族风格，丰富地毯图案花型。

2 进化计算图案设计方法

在分析主体纹样特点的基础上，提出了一种基于进化纹样设计方法。在进化过程中，以“层”为单位编码和进化，并针对进化过程中的局部最优问题，提出了一种开放式的进化策略，即由用户灵活控制进化图层，并经过对进化个体的适应值引入用户打分机制来完成。这种开放式的进化策略有效地保证了进化的流畅性和完整性。图案由角隅、主体、边框三类纹样基因构成，如图1所示。搭建基于进化设计的图案生成系统(evolution carpet pattern design system, ECPDS)，如图2所示。

图1 图案由角隅、主体、边框三类纹样组成

图2 ECPDS框架

2.1 ECPDS框架

ECPDS的主要功能是应用进化计算和风格评估，实现基于进化算法的图案设计。该系统主要由两个模块构成：一是图案基因生成模块，该模块获取地毯图案的三类不同纹样(主体纹样、角隅纹样、边框纹样)，但数据的表示方式不同。二是图案进化设计模块，该模块完成进化设计流程，优化种群获取适应度分值高的地毯图案。由于ECPDS系统具有用户打分优先，能够满足用户设计需求。

2.2 交互式进化设计步骤

步骤1.在初始化中：

(1) 确定种群规模M和每个个体基因数(主体纹样、角隅纹样、边框纹样)N=3；

(2) 确定交叉概率Pm和变异概率Pc；

(3) 随机生成符合条件的初始种群。

步骤2.每个个体生成一幅图案，给每个图案打分，找到最优的个体。

步骤3.交叉变异：采用随机概率选优法。

步骤 4.保留最优个体的前提下进行轮盘赌选择。

其中打分100的图案自动保存到当前路径。

2.3 主观评分定量化处理

将主观评价转化为定量结果的算法如下：

首先将主观评分因素 F分解为若干子因素，即F= {f1, f2,…, fn}，其中，n为子因素数量。为每个子因素设计权重，权重集合为W = {w1, w2, …, wn}，满足若子因素fk由若干二阶子因素构成，则需要将 fk进一步划分为fk= {fk1, fk2, …, fkm}，且需要设计相应的权重Wk= {wk1, wk2, …, wkn}。在本文中，只将主观评分因素划分到一阶子因素集。

针对任意一幅自动生成的图案，假设某一主体给出的评分集为S = {s1, s2, …, sn}，其中，Si为在子因素 Fi方面，自动生成图案的评分，则该主体对该幅图案的最终评分记为：

为了进一步降低主观因素，本文提出多人同时对自动生成的图案进行评分。而将评分主体按照领域知识水平划分为两个等级，专家级和普通级。假设参与评分的人数为N，iα为主体i的权重，若主体i为专家级，则iα= 1；否则iα= 0。则该幅图像的总体得分设计为：

2.4 色调协调度

一幅地毯图案均由主体纹样基因、角隅纹样基因、边框纹样基因三部分组成。三种基因搭配在一起是否和谐，其中重要的一个标准则是各个基因的色调协调度。本文使用基于颜色直方图的互信息来表征色调的协调度。互信息是信息论领域的重要概念，用于衡量两个变量间的相似程度。设A、B、C分别代表主体纹样基因、角隅纹样基因、边框纹样基因，CHA, CHB, CHC分别为三个基因的颜色直方图。则三者之间的协调度定义为：

其中，MI(X,Y)为X与Y两者的互信息，其计算公式可表示为：

其中， H( X)和 H( Y)分别为变量X和Y的信息熵， H( X, Y)为X和Y的联合信息熵。

式(3)中，三种基因的色调协调度越高，则表明该图案越优秀。

3 实验结果与讨论

3.1 参数设置

根据算法，设计实验方案。目标是基于主体纹样基因、角隅纹样基因、边框纹样基因组成一幅新图案，并通过进化计算进行寻优。

(1) 初始化：图案生成器为交互式进化计算提供生成基因，并确定如下参数为种群规模M为5；每个个体基因数N为3；交叉概率Pm为0.6，变异概率Pc为0.1。

(2) 用户交互式打分确定适应度：主观评分因素 F包括风格、色调搭配、结构。三者的权重均为 1/3。共有7人参与评分，其中专家级4人，普通级3人。

(3) 交叉变异：①交叉：每个个体以0.6的概率与最优个体进行交叉，假设 u0为旧个体，ub为当前最优个体，un为新个体，则：un= u0+ a× (ub- u0)，其中：a为–1到1的随机整数。每产生一个新个体，都显示其对应的图像并打分。②变异：每个个体以0.1的概率变异，变异方法为：un= u0+ b，其中：b为–5到5的随机整数。每产生一个新个体，都显示其对应的图像并打分。

(4) 保留最优个体的前提下进行轮盘赌选择：先找最优个体并保存起来，然后对剩余个体用轮盘赌的方法选出19个个体，剩下的淘汰。用先前选出的最优个体作为第20个个体，最后返回继续。

3.2 实验结果

ECPDS的开发环境为Matlab 7.6.0。考虑到需要进行人机交互，即需要专家为自动生成的图案打分，所以使用Matlab提供的GUI机制。该系统的主界面如图3所示。

图3 基于进化设计的图案生成系统

为了便于专家打分，系统可以同时显示6幅生成的图案。而且输入的分数为多位专家共同打分的结果(统计方法为式(2))。当专家认为已经获得足够优秀的图案后，迭代结束。最后一次迭代后获得最高分的图案即为最终结果。图4显示了4幅本系统生成的具有新疆民族特色的地毯图案。

3.3 主题风格保持分析

带有地域特色图案的生成，需要某种风格的描述和表达。如何做到风格的保持是一个有趣的问题。本算法能够有效地保持所生成的图案风格，原因在于该算法以人机交互形式运行。在专家评分过程中，将风格作为一个要素进行考虑。若侧重于衡量风格是否得到保持，可将该因素的权重加大。

这里，主观评分因素F分为三种，包括风格、色调搭配、结构。其中，风格的权重设置为0.5，色调搭配和结构分别设置为 0.25。图案评分与迭代次数的关系如图5所示。

图4 基于进化设计的一组生成图案展示

图5 图案评分与迭代次数的关系(w1 =0.5， w2 =0.25，w3 =0.25)

从图5中可以发现，随着迭代次数的增加，最高得分也呈现几乎单调增加的状态，因为风格因素所占的比重远高于其他两种因素的比重。所以，最高得分的增加即意味着风格的统一性逐渐提高。

3.4 图案进化设计分析

与文献[16]、[17]算法相比，该系统突出特点：

(1) 采用编码方式能够显示基因与图案特征之间的关联，可以构建更多创新图案。

(2) 通过交互式评分机制有效地延展了设计空间，更好地协助了图案的风格化设计，解决新疆地毯图案风格化传承方法发展缓慢等问题。

(3) 该系统可以对其他生成图案进行优选，通过交互式进化设计迭代生成用户喜爱的图案，并通过设计与图案存储方式对应的交叉变异操作来有效地增大搜索空间，丰富图案多样性。

4 小 结

纹样是组成图案重要要素，它一般决定了图案的主要风格和特点。如何利用已有纹样进行创新设计，生成更具风格特色的织物纹样是论文的研究目标。本文采用了基于图案的组合、变形和扰动方法设计出大量创新图案，但缺少风格特征的约束，故将进化计算的一个重要分支——进化艺术的思想应用到图案创新设计上，提出了辅助设计生成新纹样的方法。相比基于图像组合、变形与扰动的生成方法优点表现在：

(1) 基于进化的图案设计方法是一种按照适应度值不断寻优的过程，算法是可约束的，而前者组合变换是无约束的。

(2) 基于进化的图案设计方法可以通过编码优化和适应度函数进一步改进生成效果，逼近设计者所需目标；而组合变换虽然具有变换力度更小，变换参数可调等优点，但运算规则过于简单。

(3) 实际应用中可以结合多种生成方法：通过组合变换扩大生成图案数量，而最终目标图案由进化选择获取。

然而，下一步的研究重心放在图案编码和适应度函数的确定，完善进化设计的图案生成方法。

(本文中的图案来源自张亨德设计师收集的地毯图案，苏州大学出版的《新疆地毯》，特此表示感谢！)

[1]刘 弘, 刘希玉, 唐明晰, 等. 支持外观造型创新设计的计算机辅助设计环境[J]. 计算机辅助设计与图形学学报, 2003, 15(10): 1258-1262.

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

[3]冯培恩, 陈 泳, 张 帅, 等. 基于产品基因的概念设计[J]. 机械工程学报, 2002, 38(10): 1-6.

[4]田笑一. 面向创新的印花图案CAD/CAM系统及若干关键技术研究[D]. 杭州: 浙江大学, 2002.

[5]倪 宁, 卜佳俊. 面向创新的图案CAD/CAM系统的研究[J]. 现代纺织技术, 2002, 10(3): 33-36.

[6]马凌洲. 计算机辅助织物创新设计与制作系统的研究与实现[D]. 杭州: 浙江大学, 2005.

[7]Schnier T, Yao Xin, Beale R, et al. Nature inspired creative design-bringing together ideas from nature, computer science, engineering, art, design [C]// Proceedings the Seventh International Conference on Adaptive Computing in Design and Manufacture (ACDM2006), Bristol, UK, 2006: 237-240.

[8]赵海英, 杨一帆, 徐光美. 新疆民族民间艺术图案生成方法[J]. 计算机系统应用, 2011, 20(7): 94-99.

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

[10]刘 弘, 刘希玉, 马丽娜. 支持进化的计算机辅助设计环境[J]. 计算机辅助设计与图形学学报, 2003, 15(2): 167-173.

[11]刘 涛. 基于进化计算技术的剪纸图案创新设计研究与实现[D]. 济南: 山东师范大学, 2009.

[12]郑自然. 基于智能计算的计算机辅助建模方法研究[D]. 济南: 山东师范大学, 2010.

[13]李 杰. 基于遗传算法的分形艺术图案生成方法的研究[D]. 济南: 山东师范大学, 2009.

[14]Bentley P. An introduction to evolutionary design by computers [M]. San Francisco, CA: Morgan Kaufmann Publishers, 1999: 1-73.

[15]Frazer J H. An evolutionary architecture [M]. London: Architectural Association Publications, 1995: 30-37.

[16]赵海英, 徐正光, 张彩明. 一类新疆民族风格的织物图案生成方法[J]. 图学学报, 2012, 33(2): 1-8.

[17]赵海英, 徐正光. 基于构型风格的新疆民族织物图案自动生成[J]. 图学学报, 2013, 34(1): 17-21.

A Generation Method of Carpet Pattern Based on Evolutionary Computation

Zhao Haiying1, Peng Hong2, Zhang Xiaoli1
(1. Mobile Media and Cultural Calculation Key Laboratory of Beijing Century College, Beijing University of Posts and Telecommunicatims, Beijing 102613, China; 2. College of Network Education, Xinjiang Normal University, Urumqi Xinjiang 830054, China)

There is unique regional, national character and style in Xinjiang ethnic carpet patterns. It is difficult to keep and inherit the style of design innovation design. An innovative design method is put forward based on evolutionary computation. The features are extracted which represent style and put into use the evolutionary computation, by decomposing carpet design and analyzing its components. So it can recreate new patterns. There are many ways to strengthen the design expressive force, including adjusting the design content and pattern structure to enrich the pattern changes, and also combining the different elements among the sequence relationship. The simulation experiments show that the method can realize the innovation design of style pattern, which get a high approval with the aid of the subjective and objective evaluation.

evolutionary computation; pattern generation; picture gene; innovative design

TP 391

A

2095-302X(2015)01-0041-06

2014-06-05；定稿日期：2014-08-05

国家自然科学基金资助项目(61163044)；国家社科基金重点资助项目(12AZD120，12AZD118)

赵海英(1972–)，女，山东烟台人，副教授，博士。主要研究方向为图形图像处理、虚拟现实与文化遗产。E-mail：zhy.yh@163.com

彭 宏(1972–)，男，四川人寿人，高级工程师，硕士。主要研究方向为计算机应用、图像处理。E-mail：hong_pengxj@126.com