蜡染冰纹生成算法研究

喻扬涛， 徐 丹

(1. 云南大学信息学院，云南 昆明 650031；2. 云南民族大学人民武装学院，云南 昆明 650118)

蜡染冰纹生成算法研究

喻扬涛1,2， 徐 丹1

(1. 云南大学信息学院，云南 昆明 650031；2. 云南民族大学人民武装学院，云南 昆明 650118)

提出基于漫水思想的距离变换算法，取得较好实时性；采用概率算法确定种子点，改善冰纹分布；提出冰纹形态调整方法，改善单条冰纹形态；对交点加粗效果使用基于双曲线的交点复合距离控制，更加接近真实冰纹效果。实验表明，漫水的距离变换算法具有对数时间复杂度，实时性好；冰纹分布较以前算法更为均衡；冰纹折线及轮廓较粗问题得以解决；基于双曲线的交点复合距离控制能更好体现交点加粗效果。对已有仿真蜡染冰纹算法进行了改进，更好地实现了蜡染冰纹视觉特征。

非真实感绘制；蜡染冰纹；距离变换；染色

蜡染是一种以蜡为防染材料进行防染的传统手工印染技艺。蜡染的起源地主要有埃及、印度、中国、爪哇等。我国西南少数民族地区广泛流行的传统蜡染工艺及图案，独具特色，成为少数民族妇女生活中不可缺少的一种艺术。蜡染主要方法是用蜡刀蘸蜡液，在白布上描绘图案，然后浸入靛缸染色，用水煮脱蜡即现花纹。浸染中，蜡层破裂，染液便随着裂缝浸透在布上，留下天然花纹，称为冰纹。由于衣物经长时间染色，其间冰纹特征各不相同，展现出清新自然的美感。然而，手工印染技术生产效率低、污染大，因此各种蜡染仿真方法应运而生。

本文旨在研究具有一定实时性的、基于图像的二维冰纹生成算法，生成仿真蜡染图案，图 1为本文算法合成的图形“碗”。算法流程如下：①对盖蜡区进行距离变换，变换结果用于冰纹种子点的产生及生长方向的确定。②使用随机方法产生种子点，从种子点开始沿距离下降最快方向生成初始冰纹，此时的冰纹为单像素冰纹轮廓。③对形态不能满足要求的初始冰纹进行形态修正，得到形态较好的冰纹。④对单像素冰纹轮廓进行基于乘法模型的染色(如图2)。

图1 本文算法合成的“碗”形蜡染图

图2 冰纹仿真算法

1 蜡染冰纹视觉特征

“冰纹”是蜡染图案的灵魂，它是由于蜡画坯布在不断地翻卷浸染中，作为防染剂的蜡层自然开裂，染料随着裂缝浸染到坯布上，留下人工难以描绘的天然纹理。蜡染冰纹的形成与其制作过程中的工艺条件密切相关。

蜡染冰纹的视觉特征，主要有粗细特征、曲度特征、交叉特征、分布特征、形态特征等。粗细特征而言，质地偏硬的蜡或纹理较粗的面料，可以得到粗犷效果的冰纹；而质地偏软的蜡或使用丝绸等纹理细腻的面料，产生的冰纹较为细窄。另外一方面，同一作品中，由于裂缝产生的时间不同，各条冰纹粗细也不尽相同。曲度方面，冰纹线条主要呈流线形，弯曲时呈弧线状，较少出现折线形态。交叉特征方面，冰纹生成时，遇到其他冰纹即停止，多为“T”型交点，且通常交点处冰纹互相垂直。另外，裂缝交叉处开裂程度相对较大，染色时渗透染液较多，故染色后交叉处有不同程度的加粗现象。分布方面，若无人为影响，冰纹较易经过空旷处且常终止于旧冰纹凹入区域，呈随机分布。若有人为影响，常为平行状、网格分布等形态特征。图3为贵州苗族手工蜡染图。

图3 手工蜡染冰纹特征

2 相关工作

裂纹生成是蜡染仿真中最核心的部分。对于裂纹的生成算法，主要有物理建模方法和非真实感绘制(non-photorealistic rendering，NPR)方法两种。

基于物理建模，Terzopoulos等[1-2]引入graphics community方法模拟弹性和非弹性物体的形变及裂纹；Norton等[3]使用mass-spring模型进行固体裂纹仿真；Pauly等[4]将对象物体表示为由离散节点构成的模型，有限元方法广泛用于仿真脆性裂纹、韧性裂纹、三维表面裂纹及形变，mass-spring系统用于生成微单分子膜表面裂纹、树表裂纹及表面裂纹；Gobron和 Chilba[5]使用分子机器人生成裂纹并仿真表面的剥落，油画裂纹及剥落也使用2D网格模型进行模拟；Federl和Prusinkiewicz[6]使用楔形有限元建模仿真泥土裂纹及树皮。基于物理建模的方法仿真效果好，但方法复杂、计算量大，实时性差。

基于 NPR方法，Martinet等[7]先定义裂纹模式，然后在物体表面生成裂纹，可将此模式应用于不同物体；Wyvill和Novins[8]采用生长的方法生成裂纹；Mould[9]根据已有图像，生成与输入图像相似的裂纹；Tang等[10]提出基于 Voronoi图的冰纹生成算法。这些方法，算法相对简单，计算量小，但在冰纹视觉特征表现上，尚存在一些问题。

本文的蜡染仿真参考了文献[11]和文献[10]的算法，属于NPR方法，改善了生成裂纹的形态、分布及视觉效果并减少了算法执行时间，具有一定的实时性。

3 冰纹生成算法

冰纹视觉特征的模拟，关键是生成冰纹轮廓。生成过程中，应考虑分布、交叉、曲度、形态因素。本文的冰纹生成算法中，首先由用户根据纹样产生盖蜡区，用二值图像表示，冰纹在盖蜡区中生成。图4中，白色区域即为盖蜡区。得到盖蜡区后，对盖蜡区进行距离变换。随后，在距离变换基础上，由随机方法选取距离局部最大点，并由该点开始，沿距离下降最快方向生长冰纹。冰纹生成后，进行形态修正，在其方向上加入扰动，得到冰纹轮廓。其间应记录冰纹年龄、交点复合距离等参数，与冰纹密度、宽度、随机度、分布一起，才能较好体现冰纹的视觉特征。

图4 盖蜡区

3.1 距离变换

设Ω为图像域，W为盖蜡区，V为W的边缘及裂纹集合，盖蜡区的边界为最早的裂纹。裂纹生成时考虑其分布、形态特征，应具有如下特点：①裂纹从一条旧裂纹开始，到另一条旧裂纹结束；②新裂纹主要经过远离旧裂纹的空旷区域。这是因为裂纹通常通过张力较大处，并且具有减小张力的作用，靠近旧裂纹的像素张力趋于零。由特点②可求 W中任一点至距其最近裂纹的距离D(p)，对W中元素p的距离变换值D(p)定义如下：

若p∈V, D(p)初始化为0，否则为∞，由于仿真冰纹宽度特征需要，距离变换时应记录冰纹年龄λ。

Wyvill和Novins[8]使用标记变换算法(identity transform，IT)进行距离变换。

算法1. IT算法

(1) 按自左上到右下的顺序，进行第一次扫描。若当前扫描点p∈W，考察其邻域N(p)中左上部分的点n到最近裂纹的距离D(n)及n到p的距离，则|为新裂纹产生后p到最近裂纹的最新距离。若，修改D(p)值，记录裂纹年龄λ(p)。

(2) 按自右下到左上的顺序，进行第二次扫描。若当前扫描点p∈W，考察其邻域N(p)中右下部分的点n，若，修改D(p)值，记录裂纹年龄λ(p)。

(3) 算法终止。每条裂纹生成后，距离传递都要扫描所有点，IT算法单条裂纹复杂度为O(|Ω|)。对m条裂纹，复杂度为O(m|Ω|)。当盖蜡区较大、生成冰纹数量较多时，比较耗时。实验中，使用一幅像素为4280×3424的图像，生成裂纹数m=1 000，该算法耗时约5Min，实时性较差。

本文采用漫水策略，用漫水标记变换算法(flood identity transform，FIT)进行距离变换。该算法每次生成一条冰纹后，对该冰纹周围的点 p用漫水策略由裂纹开始，逐层向外修改其 D(p)值。若新D(p)值较原D(p)值小，说明新冰纹对p点有影响，应修改，并考虑修改其周围点 D(p)值；反之，新冰纹对p点没有影响，不修改D(p)值。若没有任何像素D(p)值被修改，说明已达漫水边界，算法终止。

算法2. FIT算法

(1) 初始化先进先出队列 queue，取得最新生成裂纹编号Num,其上所有点c入队，λ(c)=Num。

(3) 若queue非空，转步骤(2)；若queue空，算法结束。

算法中，逐层向外的漫水策略使用先进先出队列queue完成。queue初始化时存储裂纹轮廓，之后逐一处理其中元素，同时将下一层待考察元素入队。若 queue为空，则到达漫水边界，算法终止。

FIT算法只对最新冰纹的影响范围进行访问。越靠后生成的冰纹，影响范围越小，扫描像素范围越小，其时间复杂度较 IT算法时间复杂度O(m|Ω|)要小。实验表明，FIT算法时间复杂度可用对数函数进行较好拟合，而IT算法时间复杂度可使用线性函数较好拟合，FIT算法时间复杂度较IT算法小得多。

3.2 裂纹生成

单条裂纹生成时，首先使用随机算法找一个种子点，然后从该点进行生长，到达旧裂纹时停止。当裂纹数量达到要求时，算法终止。

假设裂纹生成后，会减小周边张力，则会生成最短长度的裂纹。生长时，有两个条件：①通过 D(p)局部最大点，最大程度降低张力，保证裂纹通过空旷处；②尽快到达旧裂纹。后者保证裂纹终止于旧裂纹曲率最大处，与裂纹的物理特性吻合。

为使裂纹沿 D(p)降落最快方向生长，应计算D(p)梯度。梯度计算后，使用随机算法在盖蜡区中确定一点q，从该-→点找到-→D(p)局部最大点q′，由q′ 沿D(p)梯度方向d及 -d进行生长。下一位置确定，本文采用了文献[8]提出的方法，如图5(a)所示。其中s为始点，t为下一点，生长点坐标为小数，且每点至少有一个坐标为整数。

使用该方法生成的冰纹，仅为冰纹轮廓。形态方面有 2个缺点：①冰纹轮廓较粗；②单个冰纹整体过于平直(如图5(b))。

产生以上问题，是因为梯度方向在像素间变化剧烈，导致微观上轮廓重叠，变粗；而在整体上的变化却显得单一，导致宏观上过于平直。针对 2个缺点，必需进行形态修正。修正缺点①的方法是对冰纹轮廓点进行半随机采样，在采样点之间进行插值。实验发现，采用线性插值即可达到要求。修正缺点②的方法是对裂纹方向加入扰动，本文使用高斯噪声进行扰动。通过以上处理，得到了较为理想的冰纹轮廓，如图6所示。

为模拟交点附近冰纹较宽的特征，单条冰纹生成后还应记录交点坐标。当全部冰纹轮廓生成后，对交点进行距离变换，记录所有像素到交点距离Dcross(p)。

图5 计算下一种子点及初始冰纹

图6 形态修正、加入扰动的冰纹轮廓

3.3 视觉特征控制

为控制冰纹仿真的视觉特征，在冰纹生成过程中可考虑如下参数：①冰纹参考宽度d(p)；②冰纹密度ρ(p)；③冰纹随机度w(p)。上述参数均由用户指定。

d(p)指不考虑年龄时冰纹的宽度，该值越大，冰纹整体越宽。ρ(p)指单位面积分布的冰纹数量，该值越大，冰纹越密。w(p)指冰纹的摆动幅度，即加入干扰程度，该值越大，冰纹摆动越大。图7是不同的参数值得到的不同结果。图7(a)中，左图为 50条冰纹，右图为 200条冰纹；图 7(b)中，左图参考宽度为 8，右图参考宽度为 20；图 7(c)中，左图随机度方差为 5，右图随机度方差为50。

图7 冰纹视觉参数

冰纹交点附近有加粗现象。该加粗与到交点距离Dcross(p)及到冰纹距离D(p)有关。文献[11]仅考虑与交点距离，文献[10]用双曲线近似，对双曲线内像素点着色。本文使用交点复合距离 DC(p)表示， DC(p )=D(p )a× Dcross(p)b。该参数从变换距离及欧氏距离两方面约束冰纹交点附近宽度。其中 a ×b=1。通过改变a，b的值，可以调整交点加粗效果。由于 a ×b=1，可使用点线比plr表示a、b的值。图8为不同plr值时的不同加粗效果。由图8可看出，点线比越大，交点加粗效果越明显。

图8 不同的plr值对交点加粗效果的影响

冰纹的另一个视觉特点，是其分布。当新冰纹生成后，这些地方张力减小，在新冰纹附近不应再产生种子点并生成冰纹。但文献[11]提出的冰纹生成算法初始种子点随机生成，各点概率相同，会在一些冰纹已经很密集的区域继续生成冰纹，不能很好体现上述特点，如图11所示。本文根据各区域已有冰纹密度调整种子点生成概率 R(p)，使得冰纹密度较大区域具有较小的 R(p)值，而密度较小的区域具有较大的 R(p)值，再按此概率生成种子点，取得较好的效果。图12(b)可以看出，使用本文的算法改进后，各区域生成冰纹相对均衡，分布得到改进。

4 染色模拟

染色模拟中，采用了文献[11]提出的乘性颜色模型。若使用点光源si对布料进行照射，设布料p点反射系数为ri(p)，第j层染料对布料的染色系数为ti;j(p)，则p点颜色为：

式(2)中，文献[11]基于光线经过入射和反射两个过程，ti;j(p)使用了平方。在本文算法中，ti;j(p)使用平方会造成所染颜色变化，不利于规定颜色的染制，故没有使用平方。i为RGB三个颜色通道。对于ti;j(p)的计算，引入染料浓度系数cj(p)，即：

cj(p)可通过距冰纹距离D(p)、年龄λ、交点复合距离DC(p)进行计算。

若仅考虑 D(p)，则染料浓度系数 cj(p)分布为指数分布。简单起见，用线性分布近似计算，即：

该函数为一上截断函数，其取值范围为[0,1]。若考虑年龄及交点复合距离，则：

DC0为参考交点复合距离。

采用上述算法，本文基于open cv环境进了仿真实验。图9为冰纹数量分别为50、100、150条 的结果。具体参数见表1。

图9 中国传统图案“鸡”靛蓝仿真结果

表1 冰纹生成的主要参数

5 实验结果及讨论

本文在文献[10]和文献[11]的算法基础上进行改进。提出实时性较高的距离变换算法；采用概率算法确定种子点，改善了冰纹的分布；提出冰纹形态调整方法，改善了冰纹的形态；对交点加粗效果使用复合交点距离控制，改善了加粗效果。

距离变换中，文献[11]生成每条裂纹都要扫描整个盖蜡区，当生成冰纹数量较多时，非常耗时，实时性较差。本文对其进行改进，采用漫水策略，仅对最新生成冰纹影响区域进行扫描，大大减少耗时。本文分别采用IT算法和FIT算法，对一幅像素1280×1024的图像进行1～1 000条裂纹生成，分析耗时与裂纹数量的关系，其中耗时采用20次运行耗时的均值。实验表明，IT算法中，耗时与裂纹数量成线性关系，在本文算法中，耗时与裂纹数量呈对数关系(如图10)。对于1 000条裂纹的生成，本文的算法耗时一秒多，IT算法耗时近5Min。显然，本文算法具有较少的时间复杂度，实时性较高。

图10 算法执行时间的比较

种子点的确定，文献[11]在整个盖蜡区随机生成，文献[10]先对盖蜡区进行三角剖分，在交点处产生种子点，也属随机生成。这样种子点产生概率与区域大小无关，有时会在较小区域多次生成冰纹，而较大的区域始终不生成冰纹，从而影响了视觉效果(如图11)。本文使用概率算法，在较大区域以较大概率形成种子点，使冰纹随机分布的同时主要在较大区域形成，最终冰纹的分布就比较均匀(如图8～9)。得到了较好的效果。

对于冰纹形态，原算法生成后未进行形态调整，很多地方有折线情况，并且冰纹轮廓较粗，如图5(b)所示。本文提出了形态修正算法，解决了轮廓较粗的问题，折线问题也得到了很好地控制。

交点加粗效果，文献[11]仅考虑与交点的距离，加粗效果不明显。文献[10]用双曲线近似，对双曲线内像素点着色，着色区域显得过于平整。本文引入交点复合距离DC(p)，从变换距离及欧氏距离两方面约束冰纹交点附近宽度，取得了较好的效果，如图12(b)所示。图13是我国传统图案“鸡”的仿真合成图，该图使用多种颜色，经多次染色得到。

图11 裂纹分布不均

图12 两种交点加粗效果对比

图13 传统图案“鸡”仿真图

6 展 望

本文算法仍然存在一些局限性，没有仿真实际蜡染的一些视觉特征。主要表现有：①冰纹常经过盖蜡区中较窄区域；②半随机冰纹，即冰纹按一定规律变化，但变化中具有随机性。另外，本文中实现的视觉特征，如交点处加粗，仿真加粗效果已有，但效果仍有缺憾。以上所述，均是以后继续研究的方向。

[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

国家自然科学基金资助项目(61163019，61271361)

喻扬涛(1973–)，男，云南宣威人，讲师，博士。主要研究方向为数字图像处理、非真实感图形绘制。E-mail：ynyuyyt@163.com

徐 丹(1968–)，女，云南昆明人，教授，博士。主要研究方向为基于图像的建模和绘制、非真实感绘制、图像处理与理解、虚拟现实、多媒体等。E-mail：735851271@qq.com