基于图像的二维剪纸自动生成方法

陈佳舟，王宇航，Amal Ahmed Hasan Mohammed，黄可妤，卢周扬，彭群生

（1.浙江工业大学计算机学院,浙江杭州310012；2.浙江大学CAD&CG国家重点实验室,浙江杭州310058）

剪纸是我国宝贵的非物质文化遗产,具有“圆如秋月、尖如麦芒、方如青砖、缺如锯齿、线如胡须”等鲜明特点,是一种广泛流传的民间艺术。剪纸在房屋装饰、民俗礼葬、艺术收藏等方面具有举足轻重的地位,使它跻身于中国国务院和联合国教科文组织批准的《人类非物质文化遗产代表名录》。

剪纸的设计极具挑战性,不仅要求画面简洁、直观,还需要表达特定的文化内涵,并且整个剪纸必须整体连通。这些设计要求对于业余剪纸爱好者来说无疑是巨大的挑战,也给剪纸的艺术传承和民间传播带来了很大困难。因此,我国的民间剪纸被列为中国民间十大文化遗产抢救工程之一。

本文旨在研究计算机辅助剪纸设计,从而降低人工剪纸设计的难度,满足剪纸的连通性和艺术特点要求。现有的计算机辅助剪纸设计方法主要分为基于纹样的交互设计和计算机自动生成两种。基于纹样的交互设计方法依赖大量的用户交互,对用户的要求比较高,难以推广。而现有的计算机自动生成方法不是局限于特点题材(比如肖像),就是缺乏对连通性的保证和对剪纸效果的保证。

本文提出了一种基于图像的二维剪纸生成方法,能够将任意数码照片自动转化为剪纸图形。首先利用图像分割方法建立区域连接图;其次,基于该连接图对颜色、边界对比度和区域连通性进行数学建模,并获得优化目标函数;最后,通过模拟退火算法求解目标方程,自动生成保持图像内容的剪纸图形。此外,还开发了连通性后处理和区域指定等用户交互工具,允许用户干预剪纸图形的自动生成。本文方法生成的剪纸图形画面简洁、整体连通,在降低剪纸设计难度的同时还可满足个性化的设计需求。

1 相关工作

1.1 基于纹样的交互式剪纸设计

受纸张的空间和颜色限制,剪纸往往需要运用最为简洁的线条符号来刻画复杂的形象,久而久之便形成了一套确定的符号化纹样,比如，动物五官结构,一般都采用特定的纹样。剪纸纹样是艺术家抒发情感、表达寓意的重要途径,也是剪纸艺术区别于其他民间艺术形式的主要特征。剪纸纹样可以分为形体结构纹样、特征纹样以及装饰纹样等。目前的研究工作主要集中在剪纸纹样的识别和基于纹样的交互式剪纸图形设计两方面。

由于纹样是民间剪纸艺术在代代相传中保留下来的表达特定寓意的符号化语言,从现有的剪纸作品中自动识别纹样能够帮助我们建立剪纸纹样库,从而辅助剪纸的设计。纹样特征是识别剪纸纹样的关键,通过深入研究目前现有的图像特征提取方法[1],有助于自动识别剪纸纹样。张显全等[2]提出了一种基于纹样库的计算机剪纸系统设计。该纹样库包含许多不同特征的纹样,并且通过参数变换可以适应不同的要求,即纹样可按照用户的需要进行长短、粗细、角度以及弯曲程度的变化[3],由于纹样是手动设计的,因此其连通性需要用户自己来保证。李岳等[4]对装饰纹样进行了深入研究,提出了一些复合纹样的生成方法，如扩大对称的纹样设计,渐变的路径装饰等。张显全等[5]利用小波分析理论对剪纸图像中的纹理进行识别,小波变换具有多尺度分解特点,更符合人类的视觉机制,与计算机视觉过程相似,能够在不同尺度上描述图像的变化特征。

虽然纹样的构造较为固定,但在不同的剪纸艺术家手上却往往各有特点。为了形成各种纹样,仅有一些基本的纹样是不够的,需要在已有纹样的基础上,通过计算机辅助设计思想生成大量纹样。刘涛等[6]对剪纸图案风格进行了研究,提出利用遗传算法对剪纸图案进行设计的理念。涂传朋等[7]研究了计算机生成剪纸风格流水动画形式,提出一种生成剪纸风格流水动画的方法：首先对手工剪纸纹样进行分类处理,如平稳流水波纹、浪花纹等,并且构造出静态结构,然后，根据不同类型的水纹构建不一样的动态控制机制。

1.2 计算机自动剪纸生成方法

文献[8]提出了一种基于阈值的自动生成方法,其大致思路为：首先，寻找一个合适的阈值,将整幅图像二值化,然后，采用不连通区域的连接算法。使用Dijkstra算法连接不连通的邻近区域，将不连通区域连接起来。文献[9]提出了艺术阈值处理的相关技术，结合图像信息来处理图像阈值,对图像分块,对每个块设定阈值并进行二值化操作，使用艺术阈值算法对图像进行优化,并通过调整参数得到不同风格的艺术形象。

文献[10]提出了一种人物肖像剪纸生成方法。优秀的肖像类剪纸作品需要捕获特殊的人物特征。基于此,MENG等[10]提出以自底向上和自顶向下为线索进行取值。在自底向上阶段,从输入图像中提取包含脸部器官的图像区域,用动态阈值的方法将这些图像区域二值化。在自顶向下阶段,则使用艺术家预先描绘的模板对相关图像区域进行匹配。最后对各个区域进行And-Or图连接,从而得到最终的剪纸效果。基于模块的方法能够达到满意的效果,但只适用于人物肖像,并且基于模板方法，需要预先建库,工作量较大。

2 本文方法

为了缓解交互式剪纸图形设计的交互困难,也为了克服基于模板的人物肖像剪纸自动生成方法的局限性[8],提出了一种新的基于图像的二维剪纸生成方法,能够将一幅彩色图像自动转换为一幅整体连通的剪纸图形。首先利用图像分割方法建立区域连接图(2.1小节);接着,基于该连接图，对颜色、边界对比度和区域连通性等进行建模,并建立优化目标函数(2.2小节);然后,通过求解该目标函数获得每个区域的镂空属性(2.3小节);最后,自动生成剪纸图形,并允许用户进行局部特征修改和纹样添加等后处理和交互操作(2.4小节)。该方法能够自动生成相互连通的剪纸图形,图形线条光顺度可控,并能保持原图中大部分物体的形状特征。

2.1 建立区域连接图

现有基于阈值的方法能够将输入图像划分为镂空和保留两部分,从而获得一个粗糙的剪纸图形。然而,剪纸设计需要综合考虑物体的明暗、边缘的强弱和画面整体的连通等因素,基于阈值的方法，仅根据像素的明暗来确定像素的镂空属性，并不符合剪纸的艺术特色。另一方面,由于本文方法不限定所处理的输入图像内容,因此无法与基于模板的方法[10]一样，从输入图像中直接检测需要转化为剪纸形状的物体。为此,首先将图像空间分割为颜色相近的许多子区域,再将这些子区域按照空间位置关系建立区域连接图,为寻找同时解决区域明暗、边界强弱和整体连通等多种艺术要求的方案提供条件。

2.1.1 图像分割

能够将彩色图像分割为多个子区域的方法不胜枚举,除了已经提到的阈值方法外,常用的还有分水岭分割方法、金字塔分割方法、图切割（graph cut）方法、K-means分割方法、Mean-shift分割方法等。分水岭分割算法可以通过阈值的方法自动选择种子点,但所产生的分割结果过于粗糙,无法满足本文建立区域连接图的要求,如图1(b)所示。金字塔分割是一种形态学分割方法,笔者用OpenCV中的cvPyrSeg-mentation函数进行尝试,分割结果中含有很多面积很小的区域,且区域边界锯齿严重,如图1(c)所示。K-means分割是一种基于聚类分析的方法,其结果和金字塔分割方法类似,如图1(d)所示。需要指出的是,图1(c)和(d)的结果,都是预先将输入图像进行一定的高斯模糊后完成的,锯齿边界和小面积区域依然难以去除。

图1 不同图像分割方法的比较Fig.1 Comparison of different image segmentation methods

基于计算机视觉的Mean-shift分割方法,通过迭代偏移局部均值,达到任意维空间数据的聚类效果,计算量较小,收敛速度快,不需要用户通过交互指定,在图像分割、平滑和视频目标跟踪等领域具有广泛应用。笔者对该分割方法进行了尝试，结果如图1(e)所示，可以看出,产生的区域大小合适,边界锯齿不严重。

本文采用Mean-shift分割方法对图像做聚类分析,利用位置-颜色空间向量v=(αx,αy,R,G,B)完成初始样本的构建,该5维向量表示p=(x,y)位置上的像素颜色R,G,B。由此,Mean-shift分割方法可定义为一个搜索中心点位置的迭代过程：

式（1）的作用就是在每次迭代过程中对所有符合‖v i-uk‖≤δ这一局部邻域条件的初始样本求平均值,k代表目前的迭代次数,uk代表迭代次数为k时的均值位置,nk代表在该局部邻域范围内初始样本的个数。因此,局部邻域中心点位置随初始样本的变化不断移动,直到该中心位置几乎不再改变，迭代过程结束。另外,Mean-shift分割方法以每个初始样本vi为起点（即u0=vi）,分别进行迭代，迭代过程结束后,将距离中心位置较近的邻域划分为同一个子区域,计算每个子区域的平均颜色,并将该子区域的所有像素都设置成平均颜色，进而得到分割后的图像,实现过程参见文献[11]。

Mean-Shift分割方法依赖于参数调节。其中,参数δ主要控制分割子区域的大小,分割区域的面积随δ的增大而增加,而分割区域的数量随δ的增大而减少,δ是本文方法的调节参数之一。为避免分割后产生面积过小的区域,将该算法的最小区域面积参数设为 wh,其中，w表示图像区域的长,h表示图像区域的宽。参数α主要控制位置空间和颜色空间之间的尺度比。本文将该参数值设定为自适应值255/ wh。

虽然Mean-shift分割能得到封闭的区域,但其边界往往带有锯齿,与剪纸艺术追求的简洁画面不符,见图1(e)。为此,提出一种基于局部统计的滤波方法,以消除锯齿效应。对于像素p(其所属区域编号为λp),统计该像素局部邻域内全体像素的所属区域编号{λq|‖p-q‖≤s},并用出现次数最多的区域编号λp代替当前像素p的区域编号。其中,参数s是代表滤波范围的整数,用于控制边界的光滑程度,s越大,边界线条越光滑。如图1(f)所示,该统计滤波方法不仅可有效解决边界锯齿问题,而且不会破坏图像的整体分割结果。

需要指出的是,去除边界锯齿的传统解决方法是：首先，矢量化边界线条（一般表示为多边形）,接着，对线条进行分段光顺处理,最后，用原有的编号填充每个区域。这类方法不仅无法并行计算，效率低,而且稳定性较差,分割产生的锯齿边界容易矢量化，导致失败。而本文基于统计的滤波方法,可以并行处理区域编号滤波,能够有效去除复杂的锯齿,只需要一个简单的4-邻域判断即可获得边界像素,从而避免进行复杂的边界像素矢量化和区域填充。

2.1.2 生成连接图

有了上述图像分割,基于图像的剪纸生成任务就不需要逐个像素地判定应镂空还是保留,而只要计算每个分割区域的镂空属性,即是否进行整体的镂空处理。计算时不仅需要考虑每个区域的颜色、面积等属性,而且需要考虑区域之间的取值关系。如相邻区域的镂空属性不同,之间的边界会得到保留;如果相邻区域的镂空属性相同,之间的边界会消失。因为分割区域之间的镂空属性存在相互影响,为此，用一个连接关系图对其建模,将其视作一个整体,建立优化目标函数,全局求解每个区域的镂空属性分类。

本文将分割区域视作顶点V={vi},相邻区域之间的边界视作它们的边E={eij},由此构建一个连接关系图G=(V;E)。计算每个顶点的区域面积、平均颜色、平均位置等属性。其中,区域面积Ai是指该区域所包含的像素点个数,平均颜色ci是指像素颜色的平均值,平均位置pi是指像素点位置的平均值。对于每条边界,也可以计算长度和强度等属性。其中,长度li,j是指该边界所经过的像素点个数,强度si,j是指这些像素点梯度的平均值,用以计算该边界的视觉显著性。本文用Sobel算子计算梯度大小。

2.2 建立优化目标函数

一幅剪纸只有2种颜色,而输入图像包含成千上万种颜色。即使用每个分割区域的平均颜色来代替该区域的所有颜色,图像的颜色也远多于2种。而要将一幅图像转化为一幅剪纸,实际上是确定每个分割区域是取前景色还是背景色。其中,前景色为红色,是保留下来的纸张颜色,而背景色是白色,是镂空后的颜色。基于上述区域连接图G=(V;E),本文引入一个优化目标函数,该函数由3个约束条件加权组成,分别对顶点约束、边界约束和连通性约束进行数学建模。

2.2.1 顶点约束方程

剪纸是一种镂空的艺术,镂空的区域由于透光更为明亮。为了使生成的剪纸图形尽可能地反映输入图像的内容,剪纸中的镂空区域应该尽量与输入图像中的明亮区域对应,非镂空区域则与输入图像中的灰暗区域对应。本文将镂空区域的颜色视作白色,非镂空区域的颜色视作黑色,由此定义它们与输入图像中相应分割区域的颜色差：

于是,目标剪纸图形与输入图像之间的顶点约束函数可以用所有区域的颜色差来定义：

其中,Ai为分割区域的面积,W和H分别为输入图像的长和宽。

2.2.2 边界约束方程

块之间的边界包含了图像的轮廓和边缘。为了保留这些边缘的可见性,颜色差别较大的两个相邻区域应取相反的二进制值,即一个镂空、一个保留，颜色差别较小的两个相邻区域则可以取相同的二进制值,即同时镂空或保留。本文以此为原则,对取相同二进制值和取不同二进制值的相邻区域分别计算惩罚函数,即Calike和Copp。对于任意一对相邻区域(i,j),如果它们的二进制取值相同(bi=bj),则(i,j)∈Ealike, 反之则属于Eopp。Calike和 Copp的定义如下：

其中,对二进制取值相同的相邻区域Ealike用平均颜色差的加权平均来计算Calike,而对二进制取值不同的相邻区域Eopp,则用1减去平均颜色差的加权平均来计算Copp。需要指出的是,该公式与文献[12]的主要差别在于边界强度si,j的使用。注意到有一些边界虽然很长,但边界两侧的区域在边界附近颜色过渡很光滑,即si,j值较小，这些边界即使两侧区域的整体平均颜色有一定差异,但在视觉上边界两侧的颜色差异较小。因此,该边界对应的惩罚因子应适当减小,本文通过引入si,j的权重因子来实现。

2.2.3 连通性约束方程

我国早期的民间剪纸主要用于窗花装饰,出于张贴的便利,要求剪纸联通为一个整体。经过上百年的传承,形成了中国剪纸有别于其他任何民间艺术的构型特色。传统的二值化方法虽然能够将输入图像转化为局部区域镂空或保留的剪刻效果,但难以保证剪纸的连通性。虽然可以用后处理方法将不连通的区域强行连接起来,如文献[8]采用的Dijkstra算法,但连接部分计算机处理痕迹明显,且难以保证连接的牢固。而民间剪纸艺术家在设计剪纸时通常已考虑了剪纸的整体连通性,仅需在剪刻过程中做简单的局部调整即可。本文将连通性约束加入目标函数,试图一次性生成具有良好连通性的剪纸图形。

为了达到约束剪纸连通性的目的,将生成剪纸中的不连通的前景（保留）区域数量Nc用于连通性约束的计算：

其中,N为整幅图像分割得到的区域总数量。由于不连通前景区域数量一般远少于区域总量,因此将N取平方根做分母。

2.3 求解目标函数

目标函数为所有约束项的加权和,即

为此,需要寻找 N个二进制值,即{b1,b2,…,bN},bi∈{0,1},使该目标函数 Ctotal最小化。最为简单的方法是穷举所有的可能二进制值组合,计算在这些组合下的目标函数值,经比较得到最小值。然而,这样的组合有2N种,穷举所有的组合显然不合适，计算开销太大,处理复杂图像时可能需要数小时。

为解决目标函数求解问题,本文用近似求解方法取代穷举法。能用于这一类目标函数的近似求解方法很多,考虑本文的顶点约束项和边界约束项等都是建立在连接关系图上的,故选择基于图的近似求解方法，主要有图切割法[13](graph cuts)、置信度传播算法[14](belief propagation)和模拟退火法[15]。

图切割法的能量函数主要由数据项和光滑项组成,如用本文中的顶点约束项和边界约束项来代替，然而，文献[16]发现，将图像分割问题转换为图的最大流/最小流问题所产生的区域分割往往过于粗糙,无法保留大部分边界轮廓特征；如目标函数采用置信度传播算法的无向有环版本,即带圈置信度传播算法（loopy belief propagation）（一种机器学习方法）求解，计算效率又较低,且稳定性和收敛性难以保证。故本文选择随机算法——模拟退火法,虽然也不能保证找到全局的最优解,但可以较快地找到问题的近似最优解,且具有良好的稳定性和收敛性，在参数设置得当的情况下,模拟退火法的搜索效率较穷举法高很多。

模拟退火法首先用随机值{b1,b2,…,bN}作为初始化状态值,并计算在当前状态下的目标函数值；接着,随机选择一个区域bi,更改状态值,并计算新的目标函数值，如果新目标函数值较原目标函数值小,就接受该状态值的改变，如果新目标函数值增加,就以一定的概率pk接受该状态值的改变。其中,pk=p0βn,p0为接受概率的初始值（本文取0.5）,β为接受概率的下降速度（本文取0.9）,而n是在目标函数值增加的情况下状态值改变被接受的次数。不断迭代上述过程,直至迭代达到一定次数（本文取1 000次）,或者连续多次迭代都无法接受状态值的改变（本文取30次）,或者p k的值小于一个很小的阈值（本文取0.001）。

在模拟退火过程中,以一定的概率接受局部非最优解的目的是防止陷入局部极小值点,从而得到全局最优解。由于接受概率每使用一次都会以α的比例下降,所以模拟退火法的收敛性是能够保证的，但每次迭代都需要计算目标函数值。为了降低计算量,本文仅计算状态值改变产生的目标函数值的变化量,即ΔCtotal,如果ΔCtotal＜0,说明应该接受状态值改变;如果ΔCtotal≥0,则以概率p k接受这一改变。由于ΔCtotal的计算仅涉及当前区域、相邻区域和与其连通的区域,因此，计算量较重新计算ΔCtotal小很多。

2.4 后处理和用户交互

上述目标函数求解结束后,即可获得保留了大部分轮廓特征的剪纸效果,如图2和图3所示。然而,这些剪纸效果与民间艺术家创作的纸质剪纸相比,在整体连通性和装饰纹样方面仍有差距。为此,本文开发了连通性后处理和针对纹样的用户交互工具,使用户能够轻松地生成符合剪纸艺术特点的剪纸图形。

图2 部分纹样库示意Fig.2 Some patterns in our library

2.4.1 连通性后处理

由于目标函数将整体连通性视作软约束而非硬约束,生成的剪纸虽然不连通区域数量较少,但无法保证仅有一个不连通区域。通过增大式(6)中的连通性约束系数wconnect，可减少不连通区域数量,但增大过多会导致顶点约束和边界约束失效,使剪纸效果失真。

为保证剪纸的整体连通性，首先,根据区域边界的强度si,j，将边界线条划分为物体轮廓线和非物体轮廓线，如图3(e)所示,颜色越红的边界强度越大,越有可能被划分为物体轮廓线。检查每条物体轮廓线能否连接不连通区域，如能,用宽度为5的红色线条绘制该物体轮廓线,将不连通区域连接起来,如图3(f)所示。需要指出的是,当强度si,j难以有效计算物体轮廓线时（如当物体内部的纹理边界强度很大时）,需要手动进行前景分割[13]，以获取更准确的物体轮廓线,如图5(e)所示。

图3 天鹅图像的自动剪纸生成结果Fig.3 Paper-cut results of the swan image

物体轮廓线并不能连接所有不连通的区域,如图3(f)中中央的一块前景区域。为此,还采用了Dijkstra算法[17],以最短路径连通算法连接相邻不连通区域。首先对图像进行八连通扫描线种子填充标记[18],对同一区域像素点取相同标签；标记完像素点后,以图像像素点为结点,以图像像素点的像素值为每个结点的初始距离,相邻结点间的距离为2个结点像素值之和,为改变连通效果设定阈值,当距离大于阈值时，规定该像素点距离为无穷大。基于上述假设,求出图像上一点到某点的距离。从某个像素点z出发,将图像像素点分成两类,a类为已求得的到该像素点的距离,b类为未求得的,从b类中寻找距离最小的点作为更新点p,从p出发，更新距离,并且将p归为a类,重复上述操作,直到b类为空集为止,这样可以求出z到其余像素点的距离。将2个图像块之间像素点间距离最短的作为这2个块间的距离,利用主元分析,得到此路径的主方向,并对路径进行填充,以改善效果。

2.4.2 用户交互

本文剪纸自动生成方法的目的是辅助业余剪纸爱好者进行设计,而非取代传统的手工剪纸艺术。当用户对自动生成的剪纸图样不满意或有一些特殊要求时,允许用户进行手动修改。自动生成和用户交互工具相结合,可大大提高业余甚至专业剪纸爱好者使用本系统进行剪纸设计的效率。为此,还开发了区域属性指定和纹样添加2种用户交互工具。

目标函数为一组约束方程,当对某一局部进行调整(将某一区域指定为镂空、保留或与另一个区域相同)时，需进行预处理和后处理。预处理，指在目标函数求解前已指定的,会影响其他区域的属性;后处理，指在目标函数求解后指定的,仅改变指定区域的属性,不会影响其他区域。后处理非常简单,而预处理则需要适当改进模拟退火求解算法，步骤如下：

初始化阶段：将区域初始化为用户需要的属性,即镂空或保留，对区域属性相同的,取相同的随机二进制值;

算法迭代阶段：当随机选择到指定的区域时,算法不会改变其镂空或保留属性,或者在改变当前区域的同时也改变同值的其他区域。

需要指出的是,用图切割方法求解目标函数,难以通过算法的调整来支持用户交互指定的预处理。

纹样是中国民间剪纸的重要特色,主要由剪纸设计者凭其所要表达的寓意而定,有时与图像内容并不相关，因此,根据图像内容自动生成剪纸纹样缺乏合理性,现有的基于纹样的剪纸方法大多以手动交互为主。本文开发了相应的纹样设计交互工具,以弥补自动生成方法难以生成纹样的不足。首先,建立一个剪纸纹样库,包括诸如月牙纹、柳叶纹、花瓣纹、铜钱纹和锯齿纹等最为常见的纹样,如图2所示。

此外,还为每个纹样设计了不同的变化模板,用户可以轻易编辑，如添加花瓣纹的花瓣数量、增加锯齿纹的锯齿数量等。当用户将纹样添加到自动生成的剪纸中时,本文方法会根据背景的镂空属性自动判断该纹样是镂空还是保留状态,当难以简单判定时,也会对出现的不连通区域进行提示。

3 实验结果与比较

图3展示了从输入图像到最终剪纸结果的主要流程，其中,(b)为Mean-shift图像分割后再使用边界光顺的结果,可以看到其边界较为光滑;(c)为分割后每个区域的平均颜色;(d)为采用模拟退火法求解目标函数式(6)的结果,其中不连通区域有3块；(e)展示了边界线条的强度,越红表示强度越大,是物体轮廓线,越蓝表示强度越小,不是物体轮廓线;(f)为用物体轮廓线将不连通区域进行连接的结果,可以看到，剪纸图形的不连通区域降至2块；(g)为采用Dijkstra连接算法,将剩下的2块不连通区域连接为一个整体,使最终结果不仅整体连通,且保持了输入图像的主要轮廓特征。

图4为本文方法对长颈鹿图像的处理结果，(b)为分割区域的平均颜色图，(c)为求解目标函数后得到的剪纸效果，(d)为用户通过本文提供的纹样交互工具为长颈鹿添加了锯齿纹样后的效果。

图4 长颈鹿图像的剪纸生成效果Fig.4 Paper-cut results of the giraffe image

图5 展示了本文方法对建筑环境图像的处理结果，(b)为分割边界；(c)为分割区域的平均颜色图；(d)为通过全自动目标函数模拟退火法求解得到的剪纸效果,该结果尚有少量不连通的区域(绿色圆圈处)；(e)为经连通性后处理,即Dijkstra算法处理后的图,保证了剪纸的整体连通；(f)为利用纹样库中的纹样模板,手动添加云朵纹样和流水纹样后的效果。

图6 展示了本文对斑马图像的处理结果。其中,(b)和(c)分别为Mean-shift产生的分割边界和分割区域平均颜色；(d)为求解没有使用连通性约束项的目标函数的结果,且没有添加物体轮廓线,该结果存在25块不连通区域；(e)为添加物体轮廓线、去除面积很小的不连通区域后的结果,虽然其目标函数依然没有使用连通性约束,但其连通性比(d)好很多,尤其在物体轮廓附近;(f)为既有轮廓线又有连通性约束的结果，内部不连通区域较（e）少。

为展示连通性约束项的影响,将有连通性约束和没有连通性约束的结果相减，即图(f)减去图(e)，得到图(g)。图(g)中的红色区域表明，连通性约束虽然产生了与顶点约束相违背的镂空属性赋值，但缓解了区域连通性的问题。图6(h)为经Dijkstra算法后处理(蓝色圆圈内)和用户区域指定交互(斑马的鼻子处)的最终剪纸结果,该结果已经完全实现了整体连通,且基本保留了斑马的外观特征。

利用GPU进行加速,分割区域的光顺、区域边界的提取、Sobel边界强度的计算均基于GLSL脚本实现,采用NVIDIA GeForce 9800 GT显卡仅需0.03～0.08 s。在CPU上,时间主要花在Mean-shift分割和模拟退火法计算上，其中,Mean-shift分割的时间依赖于图像的大小,一般需0.1～3.2 s，模拟退火法的快慢主要由区域连接图的规模决定,一般需0.3～2.0 s，上述时间均为 Intel® CoreTM2 DuoE 6550@2.33GHz台式电脑上的统计数据。

4 结 论

提出了一种基于图像的二维剪纸生成方法,能够将任意数码照片自动转化为剪纸图形。该方法首先利用图像分割方法建立区域连接图;接着,基于该连接图，对颜色、边界对比度和区域连通性进行数学建模,并获得优化目标函数;最后,通过模拟退火算法求解目标函数,自动生成保持图像内容的剪纸图形。同时,还提供了诸如连通性后处理和区域指定等用户交互工具,用户可便捷地在自动生成的剪纸图形中加入个性化内容。实验表明,本文方法生成的剪纸，画面简洁、整体连通,既提高了剪纸的设计效率,又满足了个性化的设计需求,有利于推动和促进我国民间剪纸艺术的传承与传播。

本文方法依赖于初始的图像分割结果,对分割失败的图像往往剪纸效果较差。因此,将来的工作之一是研究如何将剪纸的各种约束加入到图像分割环节,或许不需要分割就能得到剪纸结果。此外,不同地区不同爱好者的剪纸风格千差万别,如果能收集不同风格的剪纸,将来或许可以研究数据驱动的剪纸自动生成方法,使生成的剪纸带有鲜明的风格特征。

图6 斑马图像的剪纸效果对比Fig.6 Comparison of the Zebra paper cutting effect