喻揚濤， 徐 丹

(1. 云南大學(xué)信息學(xué)院，云南 昆明 650031；2. 云南民族大學(xué)人民武裝學(xué)院，云南 昆明 650118)

蠟染冰紋生成算法研究

喻揚濤1,2， 徐 丹1

(1. 云南大學(xué)信息學(xué)院，云南 昆明 650031；2. 云南民族大學(xué)人民武裝學(xué)院，云南 昆明 650118)

提出基于漫水思想的距離變換算法，取得較好實時性；采用概率算法確定種子點，改善冰紋分布；提出冰紋形態(tài)調(diào)整方法，改善單條冰紋形態(tài)；對交點加粗效果使用基于雙曲線的交點復(fù)合距離控制，更加接近真實冰紋效果。實驗表明，漫水的距離變換算法具有對數(shù)時間復(fù)雜度，實時性好；冰紋分布較以前算法更為均衡；冰紋折線及輪廓較粗問題得以解決；基于雙曲線的交點復(fù)合距離控制能更好體現(xiàn)交點加粗效果。對已有仿真蠟染冰紋算法進(jìn)行了改進(jìn)，更好地實現(xiàn)了蠟染冰紋視覺特征。

非真實感繪制；蠟染冰紋；距離變換；染色

蠟染是一種以蠟為防染材料進(jìn)行防染的傳統(tǒng)手工印染技藝。蠟染的起源地主要有埃及、印度、中國、爪哇等。我國西南少數(shù)民族地區(qū)廣泛流行的傳統(tǒng)蠟染工藝及圖案，獨具特色，成為少數(shù)民族婦女生活中不可缺少的一種藝術(shù)。蠟染主要方法是用蠟刀蘸蠟液，在白布上描繪圖案，然后浸入靛缸染色，用水煮脫蠟即現(xiàn)花紋。浸染中，蠟層破裂，染液便隨著裂縫浸透在布上，留下天然花紋，稱為冰紋。由于衣物經(jīng)長時間染色，其間冰紋特征各不相同，展現(xiàn)出清新自然的美感。然而，手工印染技術(shù)生產(chǎn)效率低、污染大，因此各種蠟染仿真方法應(yīng)運而生。

本文旨在研究具有一定實時性的、基于圖像的二維冰紋生成算法，生成仿真蠟染圖案，圖 1為本文算法合成的圖形“碗”。算法流程如下：①對蓋蠟區(qū)進(jìn)行距離變換，變換結(jié)果用于冰紋種子點的產(chǎn)生及生長方向的確定。②使用隨機方法產(chǎn)生種子點，從種子點開始沿距離下降最快方向生成初始冰紋，此時的冰紋為單像素冰紋輪廓。③對形態(tài)不能滿足要求的初始冰紋進(jìn)行形態(tài)修正，得到形態(tài)較好的冰紋。④對單像素冰紋輪廓進(jìn)行基于乘法模型的染色(如圖2)。

圖1 本文算法合成的“碗”形蠟染圖

圖2 冰紋仿真算法

1 蠟染冰紋視覺特征

“冰紋”是蠟染圖案的靈魂，它是由于蠟畫坯布在不斷地翻卷浸染中，作為防染劑的蠟層自然開裂，染料隨著裂縫浸染到坯布上，留下人工難以描繪的天然紋理。蠟染冰紋的形成與其制作過程中的工藝條件密切相關(guān)。

蠟染冰紋的視覺特征，主要有粗細(xì)特征、曲度特征、交叉特征、分布特征、形態(tài)特征等。粗細(xì)特征而言，質(zhì)地偏硬的蠟或紋理較粗的面料，可以得到粗獷效果的冰紋；而質(zhì)地偏軟的蠟或使用絲綢等紋理細(xì)膩的面料，產(chǎn)生的冰紋較為細(xì)窄。另外一方面，同一作品中，由于裂縫產(chǎn)生的時間不同，各條冰紋粗細(xì)也不盡相同。曲度方面，冰紋線條主要呈流線形，彎曲時呈弧線狀，較少出現(xiàn)折線形態(tài)。交叉特征方面，冰紋生成時，遇到其他冰紋即停止，多為“T”型交點，且通常交點處冰紋互相垂直。另外，裂縫交叉處開裂程度相對較大，染色時滲透染液較多，故染色后交叉處有不同程度的加粗現(xiàn)象。分布方面，若無人為影響，冰紋較易經(jīng)過空曠處且常終止于舊冰紋凹入?yún)^(qū)域，呈隨機分布。若有人為影響，常為平行狀、網(wǎng)格分布等形態(tài)特征。圖3為貴州苗族手工蠟染圖。

圖3 手工蠟染冰紋特征

2 相關(guān)工作

裂紋生成是蠟染仿真中最核心的部分。對于裂紋的生成算法，主要有物理建模方法和非真實感繪制(non-photorealistic rendering，NPR)方法兩種。

基于物理建模，Terzopoulos等[1-2]引入graphics community方法模擬彈性和非彈性物體的形變及裂紋；Norton等[3]使用mass-spring模型進(jìn)行固體裂紋仿真；Pauly等[4]將對象物體表示為由離散節(jié)點構(gòu)成的模型，有限元方法廣泛用于仿真脆性裂紋、韌性裂紋、三維表面裂紋及形變，mass-spring系統(tǒng)用于生成微單分子膜表面裂紋、樹表裂紋及表面裂紋；Gobron和 Chilba[5]使用分子機器人生成裂紋并仿真表面的剝落，油畫裂紋及剝落也使用2D網(wǎng)格模型進(jìn)行模擬；Federl和Prusinkiewicz[6]使用楔形有限元建模仿真泥土裂紋及樹皮?；谖锢斫５姆椒ǚ抡嫘Ч茫椒◤?fù)雜、計算量大，實時性差。

基于 NPR方法，Martinet等[7]先定義裂紋模式，然后在物體表面生成裂紋，可將此模式應(yīng)用于不同物體；Wyvill和Novins[8]采用生長的方法生成裂紋；Mould[9]根據(jù)已有圖像，生成與輸入圖像相似的裂紋；Tang等[10]提出基于 Voronoi圖的冰紋生成算法。這些方法，算法相對簡單，計算量小，但在冰紋視覺特征表現(xiàn)上，尚存在一些問題。

本文的蠟染仿真參考了文獻(xiàn)[11]和文獻(xiàn)[10]的算法，屬于NPR方法，改善了生成裂紋的形態(tài)、分布及視覺效果并減少了算法執(zhí)行時間，具有一定的實時性。

3 冰紋生成算法

冰紋視覺特征的模擬，關(guān)鍵是生成冰紋輪廓。生成過程中，應(yīng)考慮分布、交叉、曲度、形態(tài)因素。本文的冰紋生成算法中，首先由用戶根據(jù)紋樣產(chǎn)生蓋蠟區(qū)，用二值圖像表示，冰紋在蓋蠟區(qū)中生成。圖4中，白色區(qū)域即為蓋蠟區(qū)。得到蓋蠟區(qū)后，對蓋蠟區(qū)進(jìn)行距離變換。隨后，在距離變換基礎(chǔ)上，由隨機方法選取距離局部最大點，并由該點開始，沿距離下降最快方向生長冰紋。冰紋生成后，進(jìn)行形態(tài)修正，在其方向上加入擾動，得到冰紋輪廓。其間應(yīng)記錄冰紋年齡、交點復(fù)合距離等參數(shù)，與冰紋密度、寬度、隨機度、分布一起，才能較好體現(xiàn)冰紋的視覺特征。

圖4 蓋蠟區(qū)

3.1 距離變換

設(shè)?為圖像域，W為蓋蠟區(qū)，V為W的邊緣及裂紋集合，蓋蠟區(qū)的邊界為最早的裂紋。裂紋生成時考慮其分布、形態(tài)特征，應(yīng)具有如下特點：①裂紋從一條舊裂紋開始，到另一條舊裂紋結(jié)束；②新裂紋主要經(jīng)過遠(yuǎn)離舊裂紋的空曠區(qū)域。這是因為裂紋通常通過張力較大處，并且具有減小張力的作用，靠近舊裂紋的像素張力趨于零。由特點②可求 W中任一點至距其最近裂紋的距離D(p)，對W中元素p的距離變換值D(p)定義如下：

若p∈V, D(p)初始化為0，否則為∞，由于仿真冰紋寬度特征需要，距離變換時應(yīng)記錄冰紋年齡λ。

Wyvill和Novins[8]使用標(biāo)記變換算法(identity transform，IT)進(jìn)行距離變換。

算法1. IT算法

(1) 按自左上到右下的順序，進(jìn)行第一次掃描。若當(dāng)前掃描點p∈W，考察其鄰域N(p)中左上部分的點n到最近裂紋的距離D(n)及n到p的距離，則|為新裂紋產(chǎn)生后p到最近裂紋的最新距離。若，修改D(p)值，記錄裂紋年齡λ(p)。

(2) 按自右下到左上的順序，進(jìn)行第二次掃描。若當(dāng)前掃描點p∈W，考察其鄰域N(p)中右下部分的點n，若，修改D(p)值，記錄裂紋年齡λ(p)。

(3) 算法終止。每條裂紋生成后，距離傳遞都要掃描所有點，IT算法單條裂紋復(fù)雜度為O(|?|)。對m條裂紋，復(fù)雜度為O(m|?|)。當(dāng)蓋蠟區(qū)較大、生成冰紋數(shù)量較多時，比較耗時。實驗中，使用一幅像素為4280×3424的圖像，生成裂紋數(shù)m=1 000，該算法耗時約5Min，實時性較差。

本文采用漫水策略，用漫水標(biāo)記變換算法(flood identity transform，F(xiàn)IT)進(jìn)行距離變換。該算法每次生成一條冰紋后，對該冰紋周圍的點 p用漫水策略由裂紋開始，逐層向外修改其 D(p)值。若新D(p)值較原D(p)值小，說明新冰紋對p點有影響，應(yīng)修改，并考慮修改其周圍點 D(p)值；反之，新冰紋對p點沒有影響，不修改D(p)值。若沒有任何像素D(p)值被修改，說明已達(dá)漫水邊界，算法終止。

算法2. FIT算法

(1) 初始化先進(jìn)先出隊列 queue，取得最新生成裂紋編號Num,其上所有點c入隊，λ(c)=Num。

(3) 若queue非空，轉(zhuǎn)步驟(2)；若queue空，算法結(jié)束。

算法中，逐層向外的漫水策略使用先進(jìn)先出隊列queue完成。queue初始化時存儲裂紋輪廓，之后逐一處理其中元素，同時將下一層待考察元素入隊。若 queue為空，則到達(dá)漫水邊界，算法終止。

FIT算法只對最新冰紋的影響范圍進(jìn)行訪問。越靠后生成的冰紋，影響范圍越小，掃描像素范圍越小，其時間復(fù)雜度較 IT算法時間復(fù)雜度O(m|?|)要小。實驗表明，F(xiàn)IT算法時間復(fù)雜度可用對數(shù)函數(shù)進(jìn)行較好擬合，而IT算法時間復(fù)雜度可使用線性函數(shù)較好擬合，F(xiàn)IT算法時間復(fù)雜度較IT算法小得多。

3.2 裂紋生成

單條裂紋生成時，首先使用隨機算法找一個種子點，然后從該點進(jìn)行生長，到達(dá)舊裂紋時停止。當(dāng)裂紋數(shù)量達(dá)到要求時，算法終止。

假設(shè)裂紋生成后，會減小周邊張力，則會生成最短長度的裂紋。生長時，有兩個條件：①通過 D(p)局部最大點，最大程度降低張力，保證裂紋通過空曠處；②盡快到達(dá)舊裂紋。后者保證裂紋終止于舊裂紋曲率最大處，與裂紋的物理特性吻合。

為使裂紋沿 D(p)降落最快方向生長，應(yīng)計算D(p)梯度。梯度計算后，使用隨機算法在蓋蠟區(qū)中確定一點q，從該-→點找到-→D(p)局部最大點q′，由q′ 沿D(p)梯度方向d及 -d進(jìn)行生長。下一位置確定，本文采用了文獻(xiàn)[8]提出的方法，如圖5(a)所示。其中s為始點，t為下一點，生長點坐標(biāo)為小數(shù)，且每點至少有一個坐標(biāo)為整數(shù)。

使用該方法生成的冰紋，僅為冰紋輪廓。形態(tài)方面有 2個缺點：①冰紋輪廓較粗；②單個冰紋整體過于平直(如圖5(b))。

產(chǎn)生以上問題，是因為梯度方向在像素間變化劇烈，導(dǎo)致微觀上輪廓重疊，變粗；而在整體上的變化卻顯得單一，導(dǎo)致宏觀上過于平直。針對 2個缺點，必需進(jìn)行形態(tài)修正。修正缺點①的方法是對冰紋輪廓點進(jìn)行半隨機采樣，在采樣點之間進(jìn)行插值。實驗發(fā)現(xiàn)，采用線性插值即可達(dá)到要求。修正缺點②的方法是對裂紋方向加入擾動，本文使用高斯噪聲進(jìn)行擾動。通過以上處理，得到了較為理想的冰紋輪廓，如圖6所示。

為模擬交點附近冰紋較寬的特征，單條冰紋生成后還應(yīng)記錄交點坐標(biāo)。當(dāng)全部冰紋輪廓生成后，對交點進(jìn)行距離變換，記錄所有像素到交點距離Dcross(p)。

圖5 計算下一種子點及初始冰紋

圖6 形態(tài)修正、加入擾動的冰紋輪廓

3.3 視覺特征控制

為控制冰紋仿真的視覺特征，在冰紋生成過程中可考慮如下參數(shù)：①冰紋參考寬度d(p)；②冰紋密度ρ(p)；③冰紋隨機度w(p)。上述參數(shù)均由用戶指定。

d(p)指不考慮年齡時冰紋的寬度，該值越大，冰紋整體越寬。ρ(p)指單位面積分布的冰紋數(shù)量，該值越大，冰紋越密。w(p)指冰紋的擺動幅度，即加入干擾程度，該值越大，冰紋擺動越大。圖7是不同的參數(shù)值得到的不同結(jié)果。圖7(a)中，左圖為 50條冰紋，右圖為 200條冰紋；圖 7(b)中，左圖參考寬度為 8，右圖參考寬度為 20；圖 7(c)中，左圖隨機度方差為 5，右圖隨機度方差為50。

圖7 冰紋視覺參數(shù)

冰紋交點附近有加粗現(xiàn)象。該加粗與到交點距離Dcross(p)及到冰紋距離D(p)有關(guān)。文獻(xiàn)[11]僅考慮與交點距離，文獻(xiàn)[10]用雙曲線近似，對雙曲線內(nèi)像素點著色。本文使用交點復(fù)合距離 DC(p)表示， DC(p )=D(p )a× Dcross(p)b。該參數(shù)從變換距離及歐氏距離兩方面約束冰紋交點附近寬度。其中 a ×b=1。通過改變a，b的值，可以調(diào)整交點加粗效果。由于 a ×b=1，可使用點線比plr表示a、b的值。圖8為不同plr值時的不同加粗效果。由圖8可看出，點線比越大，交點加粗效果越明顯。

圖8 不同的plr值對交點加粗效果的影響

冰紋的另一個視覺特點，是其分布。當(dāng)新冰紋生成后，這些地方張力減小，在新冰紋附近不應(yīng)再產(chǎn)生種子點并生成冰紋。但文獻(xiàn)[11]提出的冰紋生成算法初始種子點隨機生成，各點概率相同，會在一些冰紋已經(jīng)很密集的區(qū)域繼續(xù)生成冰紋，不能很好體現(xiàn)上述特點，如圖11所示。本文根據(jù)各區(qū)域已有冰紋密度調(diào)整種子點生成概率 R(p)，使得冰紋密度較大區(qū)域具有較小的 R(p)值，而密度較小的區(qū)域具有較大的 R(p)值，再按此概率生成種子點，取得較好的效果。圖12(b)可以看出，使用本文的算法改進(jìn)后，各區(qū)域生成冰紋相對均衡，分布得到改進(jìn)。

4 染色模擬

染色模擬中，采用了文獻(xiàn)[11]提出的乘性顏色模型。若使用點光源si對布料進(jìn)行照射，設(shè)布料p點反射系數(shù)為ri(p)，第j層染料對布料的染色系數(shù)為ti;j(p)，則p點顏色為：

式(2)中，文獻(xiàn)[11]基于光線經(jīng)過入射和反射兩個過程，ti;j(p)使用了平方。在本文算法中，ti;j(p)使用平方會造成所染顏色變化，不利于規(guī)定顏色的染制，故沒有使用平方。i為RGB三個顏色通道。對于ti;j(p)的計算，引入染料濃度系數(shù)cj(p)，即：

cj(p)可通過距冰紋距離D(p)、年齡λ、交點復(fù)合距離DC(p)進(jìn)行計算。

若僅考慮 D(p)，則染料濃度系數(shù) cj(p)分布為指數(shù)分布。簡單起見，用線性分布近似計算，即：

該函數(shù)為一上截斷函數(shù)，其取值范圍為[0,1]。若考慮年齡及交點復(fù)合距離，則：

DC0為參考交點復(fù)合距離。

采用上述算法，本文基于open cv環(huán)境進(jìn)了仿真實驗。圖9為冰紋數(shù)量分別為50、100、150條 的結(jié)果。具體參數(shù)見表1。

圖9 中國傳統(tǒng)圖案“雞”靛藍(lán)仿真結(jié)果

表1 冰紋生成的主要參數(shù)

5 實驗結(jié)果及討論

本文在文獻(xiàn)[10]和文獻(xiàn)[11]的算法基礎(chǔ)上進(jìn)行改進(jìn)。提出實時性較高的距離變換算法；采用概率算法確定種子點，改善了冰紋的分布；提出冰紋形態(tài)調(diào)整方法，改善了冰紋的形態(tài)；對交點加粗效果使用復(fù)合交點距離控制，改善了加粗效果。

距離變換中，文獻(xiàn)[11]生成每條裂紋都要掃描整個蓋蠟區(qū)，當(dāng)生成冰紋數(shù)量較多時，非常耗時，實時性較差。本文對其進(jìn)行改進(jìn)，采用漫水策略，僅對最新生成冰紋影響區(qū)域進(jìn)行掃描，大大減少耗時。本文分別采用IT算法和FIT算法，對一幅像素1280×1024的圖像進(jìn)行1～1 000條裂紋生成，分析耗時與裂紋數(shù)量的關(guān)系，其中耗時采用20次運行耗時的均值。實驗表明，IT算法中，耗時與裂紋數(shù)量成線性關(guān)系，在本文算法中，耗時與裂紋數(shù)量呈對數(shù)關(guān)系(如圖10)。對于1 000條裂紋的生成，本文的算法耗時一秒多，IT算法耗時近5Min。顯然，本文算法具有較少的時間復(fù)雜度，實時性較高。

圖10 算法執(zhí)行時間的比較

種子點的確定，文獻(xiàn)[11]在整個蓋蠟區(qū)隨機生成，文獻(xiàn)[10]先對蓋蠟區(qū)進(jìn)行三角剖分，在交點處產(chǎn)生種子點，也屬隨機生成。這樣種子點產(chǎn)生概率與區(qū)域大小無關(guān)，有時會在較小區(qū)域多次生成冰紋，而較大的區(qū)域始終不生成冰紋，從而影響了視覺效果(如圖11)。本文使用概率算法，在較大區(qū)域以較大概率形成種子點，使冰紋隨機分布的同時主要在較大區(qū)域形成，最終冰紋的分布就比較均勻(如圖8～9)。得到了較好的效果。

對于冰紋形態(tài)，原算法生成后未進(jìn)行形態(tài)調(diào)整，很多地方有折線情況，并且冰紋輪廓較粗，如圖5(b)所示。本文提出了形態(tài)修正算法，解決了輪廓較粗的問題，折線問題也得到了很好地控制。

交點加粗效果，文獻(xiàn)[11]僅考慮與交點的距離，加粗效果不明顯。文獻(xiàn)[10]用雙曲線近似，對雙曲線內(nèi)像素點著色，著色區(qū)域顯得過于平整。本文引入交點復(fù)合距離DC(p)，從變換距離及歐氏距離兩方面約束冰紋交點附近寬度，取得了較好的效果，如圖12(b)所示。圖13是我國傳統(tǒng)圖案“雞”的仿真合成圖，該圖使用多種顏色，經(jīng)多次染色得到。

圖11 裂紋分布不均

圖12 兩種交點加粗效果對比

圖13 傳統(tǒng)圖案“雞”仿真圖

6 展 望

本文算法仍然存在一些局限性，沒有仿真實際蠟染的一些視覺特征。主要表現(xiàn)有：①冰紋常經(jīng)過蓋蠟區(qū)中較窄區(qū)域；②半隨機冰紋，即冰紋按一定規(guī)律變化，但變化中具有隨機性。另外，本文中實現(xiàn)的視覺特征，如交點處加粗，仿真加粗效果已有，但效果仍有缺憾。以上所述，均是以后繼續(xù)研究的方向。

[1] Terzopoulos D, Platt J, Barr A, et al. Elastically deformable models [J]. Computer Graphics (SIGGRAPH'87 Proceedings), 1987, 21(4)： 205-214.

[2] Terzopoulos D, Pleischer K.Modeling inelastic deformation： viscoelasticity, plasticity, fracture [J]. Computer Graphics, 1988, 22(4)： 269-278.

[3] Norton A, Turk G, Bacon B, et al. Animation of fracture by physicalModeling [J]. The Visual Computer, 1991, (7)：210-219.

[4] PaulyM, Keiser R, Adams B, et al.Meshless animation of fracturingSolids [J]. ACM Transactions on Graphics, 2005, 24(3)： 957-964.

[5] GobronS, Chiba N.Simulation of peeling using 3d-surface cellular automata [C]//Proceedings of the 9th Pacific Conference on Computer Graphics and Applications. Tokyo, Japan, 2001： 338-347.

[6] Federl P, Prusinkiewicz P. Finite elementModel of fracture formation on growing surfaces [C]// ComputationalScience-ICCS 2004. Krakow, Poland, 2004： 138-145.

[7]Martinet A, Galin E, Desbenoit B, et al. ProceduralModeling of cracks and fractures [C]//International Conference onShapeModeling and Applications 2004. Genova, Italy, 2004： 346-349.

[8] Wyvill G, Novins K. Filtered noise and the fourth dimension [C]//ACMSIGGRAPH 99 Conference Abstracts and Applications. New York, USA, 1999： 242.

[9]Mould D. Image-guided fracture [C]//Proceedings of Graphics Interface. Ontario, Canada, 2005： 219-226.

[10] Tang Ying, Fang Kuanjun, FuShaohai, et al. An improved algorithm forSimulating wax-printing patterns [J]. Textile Research Journal, 2011, 81(14)：1510-1520.

[11] Wyvill B, Overveld K, CarpendaleS. Rendering cracks in batik [C]//Proceedings of the 3rd InternationalSymposium on Non-photorealistic Animation and Rendering. New York, USA, 2004： 61-149.

Research on Batik Crack Rendering Algorithm

Yu Yangtao1,2, Xu Dan1
(1.School of InformationScience and Engineering, Yunnan University, Kunming Yunnan 650031, China; 2. College of People′s Armed Forces Education, Yunnan University of Nationalities, Kunming Yunnan 650118, China)

The existing algorithm of rendering batik crack is improved in this paper. A distance transform algorithm based floodMethod is proposed to get good real-time performance, a probability algorithm is used to findSeed point for getting good distribution, aMethod of adjusting crackShape is proposed to improveSingle crack′sShape, and T-junction thickening is controlled by hyperbola forMore like batik crack. ExperimentsShow that theseMethods canSimulate visual features of batik crack better and have good real-time performance.

non-photorealistic rendering; batik crack; distance transformation; dye

TP 391

A

2095-302X(2015)02-0159-07

2014-08-11；定稿日期：2014-08-20

國家自然科學(xué)基金資助項目(61163019，61271361)

喻揚濤(1973–)，男，云南宣威人，講師，博士。主要研究方向為數(shù)字圖像處理、非真實感圖形繪制。E-mail：ynyuyyt@163.com

徐 丹(1968–)，女，云南昆明人，教授，博士。主要研究方向為基于圖像的建模和繪制、非真實感繪制、圖像處理與理解、虛擬現(xiàn)實、多媒體等。E-mail：735851271@qq.com