基于進化計算的地毯圖案生成方法

趙海英， 彭 宏， 張小利

(1. 北京郵電大學世紀學院移動媒體與文化計算北京市重點實驗室，北京 102613；2. 新疆師范大學網(wǎng)絡教育學院，新疆 烏魯木齊 830054)

基于進化計算的地毯圖案生成方法

趙海英1， 彭 宏2， 張小利1

(1. 北京郵電大學世紀學院移動媒體與文化計算北京市重點實驗室，北京 102613；2. 新疆師范大學網(wǎng)絡教育學院，新疆 烏魯木齊 830054)

新疆民族地毯圖案具有獨特的地域性、民族性和風格，如何保留和傳承其風格特征是圖案創(chuàng)新設計的難點。提出一種基于進化計算的創(chuàng)新設計方法?？赏ㄟ^分解地毯圖案，分析其組成元素，抽取具有表征風格的特征予以進化計算，再生新型紋樣，設計中還可以調整圖案內容及結構來豐富花型變化，并通過不同順序關系中元素組合增強圖案的表現(xiàn)力，仿真實驗表明該方法實現(xiàn)了生成具有風格化的創(chuàng)新圖案，借助于主客觀評價模型得到很高地認可。

進化計算；圖案生成；圖案基因；創(chuàng)新設計

圖案創(chuàng)新設計是計算機應用領域中一個嶄新而又活躍的重要分支[1-6]，它的應用面極廣，且對國民經(jīng)濟建設有著重大作用。如何利用計算機自動生成新疆民族地毯圖案是一個富有挑戰(zhàn)的研究課題。新疆民族織物圖案的組成比較復雜，時空跨度大、花型多、風格各異，包含了許多蜿蜒的、不規(guī)則的幾何圖形和植物紋。使得圖案難以用傳統(tǒng)的曲線或曲面描述，給圖案特征提取與創(chuàng)新設計帶來很大困難。該課題的研究難點在于：圖案花型種類較少；設計的圖案不能傳承一定風格，缺少文化內涵的揭示；而各種新工具、新技術的出現(xiàn)仍然需要新的設計方法。進化設計是基于圖案原來規(guī)則和設計經(jīng)驗，創(chuàng)新設計是一種風格的傳承、變異和組合模式，通過創(chuàng)新將設計出更多具有新風格的地毯圖案。因此，該文引入進化計算來傳承具有一定民族風格的新疆地毯圖案。

1 相關工作

藝術設計工作中很大一部分工作是藝術圖案設計[7]，如輕紡行業(yè)的花布和地毯的花紋圖案與色彩設計；服裝行業(yè)的服裝款式設計、排料和放樣及衣料裁切設計等。如何搭建花紋圖案自動生成系統(tǒng)，有助于設計師靈活、方便而迅速地設計出花布和毛毯圖案，并通過用戶的挑選進一步修改，獲得用戶滿意的設計圖案。在實際工作中常常需要將繪圖和計算相結合，即所謂形數(shù)結合。實踐證明，任何一個圖形都可以用數(shù)學方程表示及討論；反之，數(shù)學問題也可以用圖形來描繪。這就為形與數(shù)結合的可行性提供了依據(jù)。

作者的數(shù)字文化研究團隊在前期已經(jīng)提出并完成了一些傳承新疆民族風格的設計方法。其一，提出了對稱性和隨機性相結合的圖案生成方法。通過對導入的初始圖案進行雙線性插值運算，生成一個正三角形作為第一個等邊紋樣基元；然后通過正反 120°旋轉，擴展成兩個等邊基元；再利用對稱和旋轉變換把隨機選擇的不同等邊紋樣基元嵌入到六邊形構型中，最后平鋪六邊形構型生成一幅新圖案。其二，隨機選擇基元、堆砌對稱構型和無縫平鋪紋樣。方法簡單易用，且可傳承新疆民族織物圖案的對稱性和稠密性。其三，提出了基于圖像變形的圖案生成算法[8]。先定義兩類基因生成方法，然后對圖元基因或再生基因進行組合變形即可獲得創(chuàng)新圖案。其四，提出了基于圖像擾動的圖案生成算法[9]。需引入交互分割模型提取圖案中具有代表性的意義相對獨立的圖案基元，設計圖案基元的相似變換規(guī)則，產生分形基元矩陣；然后引入準Arnold變換規(guī)則，對基元分形矩陣進行擾動以生成新圖案。為了拓寬圖案生成方法的適用范圍，本論文引入進化計算進行圖案設計。

進化設計[10]是一種將進化計算用于計算機輔助設計的技術，是一種基于實例的設計方法。針對以往的設計實例需要變化、修改和完善的設計過程，進化設計方法在一定程度上增加了設計重用性，提高了設計速度。圖案進化設計作為進化計算與設計理論結合的一個新領域，成為人工智能原理應用到數(shù)字藝術的核心課題之一，也成為進化計算在應用方面的一個重大突破[11-13]——圖案進化生成是最成功的商業(yè)形式之一。進化作品作為進化設計系統(tǒng)的產物，在各個應用領域中扮演著重要的角色。大部分的“進化設計”系統(tǒng)基本上都是基于 1999年 Bentley[14-15]設計系統(tǒng)發(fā)展而來的。系統(tǒng)隨機構建初始群體中的個體，然后在用戶審美選擇中完成變異、交配的優(yōu)勝劣汰。具有上百年甚至上千年的新疆民族織物圖案在歷史的演變過程中也遵循著遺傳、變異、選擇等優(yōu)勝劣汰的自然選擇規(guī)則和競爭機制。論文基于此研究思路把進化設計、組合變形應用到圖案創(chuàng)新上。實驗結果表明，該方法可以有效傳承新疆民族風格，豐富地毯圖案花型。

2 進化計算圖案設計方法

在分析主體紋樣特點的基礎上，提出了一種基于進化紋樣設計方法。在進化過程中，以“層”為單位編碼和進化，并針對進化過程中的局部最優(yōu)問題，提出了一種開放式的進化策略，即由用戶靈活控制進化圖層，并經(jīng)過對進化個體的適應值引入用戶打分機制來完成。這種開放式的進化策略有效地保證了進化的流暢性和完整性。圖案由角隅、主體、邊框三類紋樣基因構成，如圖1所示。搭建基于進化設計的圖案生成系統(tǒng)(evolution carpet pattern design system, ECPDS)，如圖2所示。

圖1 圖案由角隅、主體、邊框三類紋樣組成

圖2 ECPDS框架

2.1 ECPDS框架

ECPDS的主要功能是應用進化計算和風格評估，實現(xiàn)基于進化算法的圖案設計。該系統(tǒng)主要由兩個模塊構成：一是圖案基因生成模塊，該模塊獲取地毯圖案的三類不同紋樣(主體紋樣、角隅紋樣、邊框紋樣)，但數(shù)據(jù)的表示方式不同。二是圖案進化設計模塊，該模塊完成進化設計流程，優(yōu)化種群獲取適應度分值高的地毯圖案。由于ECPDS系統(tǒng)具有用戶打分優(yōu)先，能夠滿足用戶設計需求。

2.2 交互式進化設計步驟

步驟1.在初始化中：

(1) 確定種群規(guī)模M和每個個體基因數(shù)(主體紋樣、角隅紋樣、邊框紋樣)N=3；

(2) 確定交叉概率Pm和變異概率Pc；

(3) 隨機生成符合條件的初始種群。

步驟2.每個個體生成一幅圖案，給每個圖案打分，找到最優(yōu)的個體。

步驟3.交叉變異：采用隨機概率選優(yōu)法。

步驟 4.保留最優(yōu)個體的前提下進行輪盤賭選擇。

其中打分100的圖案自動保存到當前路徑。

2.3 主觀評分定量化處理

將主觀評價轉化為定量結果的算法如下：

首先將主觀評分因素 F分解為若干子因素，即F= {f1, f2,…, fn}，其中，n為子因素數(shù)量。為每個子因素設計權重，權重集合為W = {w1, w2, …, wn}，滿足若子因素fk由若干二階子因素構成，則需要將 fk進一步劃分為fk= {fk1, fk2, …, fkm}，且需要設計相應的權重Wk= {wk1, wk2, …, wkn}。在本文中，只將主觀評分因素劃分到一階子因素集。

針對任意一幅自動生成的圖案，假設某一主體給出的評分集為S = {s1, s2, …, sn}，其中，Si為在子因素 Fi方面，自動生成圖案的評分，則該主體對該幅圖案的最終評分記為：

為了進一步降低主觀因素，本文提出多人同時對自動生成的圖案進行評分。而將評分主體按照領域知識水平劃分為兩個等級，專家級和普通級。假設參與評分的人數(shù)為N，iα為主體i的權重，若主體i為專家級，則iα= 1；否則iα= 0。則該幅圖像的總體得分設計為：

2.4 色調協(xié)調度

一幅地毯圖案均由主體紋樣基因、角隅紋樣基因、邊框紋樣基因三部分組成。三種基因搭配在一起是否和諧，其中重要的一個標準則是各個基因的色調協(xié)調度。本文使用基于顏色直方圖的互信息來表征色調的協(xié)調度?；バ畔⑹切畔⒄擃I域的重要概念，用于衡量兩個變量間的相似程度。設A、B、C分別代表主體紋樣基因、角隅紋樣基因、邊框紋樣基因，CHA, CHB, CHC分別為三個基因的顏色直方圖。則三者之間的協(xié)調度定義為：

其中，MI(X,Y)為X與Y兩者的互信息，其計算公式可表示為：

其中， H( X)和 H( Y)分別為變量X和Y的信息熵， H( X, Y)為X和Y的聯(lián)合信息熵。

式(3)中，三種基因的色調協(xié)調度越高，則表明該圖案越優(yōu)秀。

3 實驗結果與討論

3.1 參數(shù)設置

根據(jù)算法，設計實驗方案。目標是基于主體紋樣基因、角隅紋樣基因、邊框紋樣基因組成一幅新圖案，并通過進化計算進行尋優(yōu)。

(1) 初始化：圖案生成器為交互式進化計算提供生成基因，并確定如下參數(shù)為種群規(guī)模M為5；每個個體基因數(shù)N為3；交叉概率Pm為0.6，變異概率Pc為0.1。

(2) 用戶交互式打分確定適應度：主觀評分因素 F包括風格、色調搭配、結構。三者的權重均為 1/3。共有7人參與評分，其中專家級4人，普通級3人。

(3) 交叉變異：①交叉：每個個體以0.6的概率與最優(yōu)個體進行交叉，假設 u0為舊個體，ub為當前最優(yōu)個體，un為新個體，則：un= u0+ a× (ub- u0)，其中：a為–1到1的隨機整數(shù)。每產生一個新個體，都顯示其對應的圖像并打分。②變異：每個個體以0.1的概率變異，變異方法為：un= u0+ b，其中：b為–5到5的隨機整數(shù)。每產生一個新個體，都顯示其對應的圖像并打分。

(4) 保留最優(yōu)個體的前提下進行輪盤賭選擇：先找最優(yōu)個體并保存起來，然后對剩余個體用輪盤賭的方法選出19個個體，剩下的淘汰。用先前選出的最優(yōu)個體作為第20個個體，最后返回繼續(xù)。

3.2 實驗結果

ECPDS的開發(fā)環(huán)境為Matlab 7.6.0?？紤]到需要進行人機交互，即需要專家為自動生成的圖案打分，所以使用Matlab提供的GUI機制。該系統(tǒng)的主界面如圖3所示。

圖3 基于進化設計的圖案生成系統(tǒng)

為了便于專家打分，系統(tǒng)可以同時顯示6幅生成的圖案。而且輸入的分數(shù)為多位專家共同打分的結果(統(tǒng)計方法為式(2))。當專家認為已經(jīng)獲得足夠優(yōu)秀的圖案后，迭代結束。最后一次迭代后獲得最高分的圖案即為最終結果。圖4顯示了4幅本系統(tǒng)生成的具有新疆民族特色的地毯圖案。

3.3 主題風格保持分析

帶有地域特色圖案的生成，需要某種風格的描述和表達。如何做到風格的保持是一個有趣的問題。本算法能夠有效地保持所生成的圖案風格，原因在于該算法以人機交互形式運行。在專家評分過程中，將風格作為一個要素進行考慮。若側重于衡量風格是否得到保持，可將該因素的權重加大。

這里，主觀評分因素F分為三種，包括風格、色調搭配、結構。其中，風格的權重設置為0.5，色調搭配和結構分別設置為 0.25。圖案評分與迭代次數(shù)的關系如圖5所示。

圖4 基于進化設計的一組生成圖案展示

圖5 圖案評分與迭代次數(shù)的關系(w1 =0.5， w2 =0.25，w3 =0.25)

從圖5中可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加，最高得分也呈現(xiàn)幾乎單調增加的狀態(tài)，因為風格因素所占的比重遠高于其他兩種因素的比重。所以，最高得分的增加即意味著風格的統(tǒng)一性逐漸提高。

3.4 圖案進化設計分析

與文獻[16]、[17]算法相比，該系統(tǒng)突出特點：

(1) 采用編碼方式能夠顯示基因與圖案特征之間的關聯(lián)，可以構建更多創(chuàng)新圖案。

(2) 通過交互式評分機制有效地延展了設計空間，更好地協(xié)助了圖案的風格化設計，解決新疆地毯圖案風格化傳承方法發(fā)展緩慢等問題。

(3) 該系統(tǒng)可以對其他生成圖案進行優(yōu)選，通過交互式進化設計迭代生成用戶喜愛的圖案，并通過設計與圖案存儲方式對應的交叉變異操作來有效地增大搜索空間，豐富圖案多樣性。

4 小 結

紋樣是組成圖案重要要素，它一般決定了圖案的主要風格和特點。如何利用已有紋樣進行創(chuàng)新設計，生成更具風格特色的織物紋樣是論文的研究目標。本文采用了基于圖案的組合、變形和擾動方法設計出大量創(chuàng)新圖案，但缺少風格特征的約束，故將進化計算的一個重要分支——進化藝術的思想應用到圖案創(chuàng)新設計上，提出了輔助設計生成新紋樣的方法。相比基于圖像組合、變形與擾動的生成方法優(yōu)點表現(xiàn)在：

(1) 基于進化的圖案設計方法是一種按照適應度值不斷尋優(yōu)的過程，算法是可約束的，而前者組合變換是無約束的。

(2) 基于進化的圖案設計方法可以通過編碼優(yōu)化和適應度函數(shù)進一步改進生成效果，逼近設計者所需目標；而組合變換雖然具有變換力度更小，變換參數(shù)可調等優(yōu)點，但運算規(guī)則過于簡單。

(3) 實際應用中可以結合多種生成方法：通過組合變換擴大生成圖案數(shù)量，而最終目標圖案由進化選擇獲取。

然而，下一步的研究重心放在圖案編碼和適應度函數(shù)的確定，完善進化設計的圖案生成方法。

(本文中的圖案來源自張亨德設計師收集的地毯圖案，蘇州大學出版的《新疆地毯》，特此表示感謝！)

[1]劉 弘, 劉希玉, 唐明晰, 等. 支持外觀造型創(chuàng)新設計的計算機輔助設計環(huán)境[J]. 計算機輔助設計與圖形學學報, 2003, 15(10): 1258-1262.

[2]黃 琦, 孫守遷, 張立珊. 面向產品創(chuàng)新的3維草圖設計技術研究[J]. 計算機集成制造系統(tǒng), 2007, 13(2): 224-227.

[3]馮培恩, 陳 泳, 張 帥, 等. 基于產品基因的概念設計[J]. 機械工程學報, 2002, 38(10): 1-6.

[4]田笑一. 面向創(chuàng)新的印花圖案CAD/CAM系統(tǒng)及若干關鍵技術研究[D]. 杭州: 浙江大學, 2002.

[5]倪 寧, 卜佳俊. 面向創(chuàng)新的圖案CAD/CAM系統(tǒng)的研究[J]. 現(xiàn)代紡織技術, 2002, 10(3): 33-36.

[6]馬凌洲. 計算機輔助織物創(chuàng)新設計與制作系統(tǒng)的研究與實現(xiàn)[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]. 計算機系統(tǒng)應用, 2011, 20(7): 94-99.

[9]趙海英, 惠 雯, 徐光美. 一種新的圖案紋樣生成方法[J]. 計算機系統(tǒng)應用, 2011, 20(3): 85-89.

[10]劉 弘, 劉希玉, 馬麗娜. 支持進化的計算機輔助設計環(huán)境[J]. 計算機輔助設計與圖形學學報, 2003, 15(2): 167-173.

[11]劉 濤. 基于進化計算技術的剪紙圖案創(chuàng)新設計研究與實現(xiàn)[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–)，女，山東煙臺人，副教授，博士。主要研究方向為圖形圖像處理、虛擬現(xiàn)實與文化遺產。E-mail：zhy.yh@163.com

彭 宏(1972–)，男，四川人壽人，高級工程師，碩士。主要研究方向為計算機應用、圖像處理。E-mail：hong_pengxj@126.com