克隆算子在民族圖案生成中的應用研究

劉戰東，李 勇，張海軍，趙彩霞

（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.