采用模糊聚类与随机游走的计算机辅助乱针绣制作方法

摘要

本发明公开了采用模糊聚类与随机游走的计算机辅助乱针绣制作方法，包括以下步骤：步骤1，定义了适合乱针绣针迹特点的参数化交叉针模型，并且通过枚举实验的方法确定了交叉针参数与图像特征的映射关系；步骤2，以输入的彩色图像作为参考图片，针对给定图像生成交叉针集合，对交叉针集合包含的交叉针采用基于模糊聚类与随机游走算法进行聚类，并且根据步骤1得到的映射关系调整交叉针参数得到针迹序列；步骤3，将针迹坐标转换为电脑刺绣机所需坐标，并将其输入电脑刺绣机，得到相应乱针绣绣品。本发明对乱针绣的机械化标准化生产具有重要意义。

说明书

技术领域

本发明涉及一种计算机辅助乱针绣制作方法，属于计算机图像处理和计算机图形学技术领域。 

背景技术

乱针绣是由常州艺人杨守玉教授于二十世纪三十年代创立的一种新的刺绣艺术，其以针线代笔，以丝线带色，并利用线条的交叉重叠创造出优美的艺术化作品。乱针绣常以花卉、人物等摄影图片为绣稿，绣品具有针法活泼、线条流畅、色彩丰富、层次感强、风格独特等特点，不仅迥别于中国的其它种类绣品，而且在世界范围内也是极其珍贵的艺术作品，多次作为国礼赠送给外国政府或领导人收藏，已被列入江苏首批非物质文化遗产之中。然而，乱针绣目前主要依靠手工创作完成，生产周期漫长导致乱针绣作品昂贵，无法为普通民众所拥有和认可；且乱针绣对绣者的技艺素质要求非常高，不仅要掌握“画理”和熟练的绘画技巧，而且能掌握“绣理”和熟练的刺绣技巧，绣者的成才之路艰辛而漫长，导致乱针绣人才日趋匮乏，对这一传世绝技的保护和传承构成了极大威胁。 

因此，采用计算机手段直接从油画、摄影和素描等稿本的数字图像中获取作品内容进而生成相应的乱针绣针迹序列，不仅有利于加深普通民众对于乱针绣的理解而且对乱针绣绣者的培养也具有重要的意义，同时生成的针迹序列也可以作为绣机的输入而自动生成乱针绣绣品，对于乱针绣这一绣艺品种的保护和传承具有重要意义。已有诸如文献1李俊,张华,王崇骏：智能化刺绣CAD系统中的工作流技术研究.计算机科学,2005,32(3):97-100.所述的日本的Tajima、德国的ZSK、美国的Wilcom等刺绣打版系统，往往需要人工交互编辑针法序列，且生成的针迹线条规整，只能处理简单的图案，不满足乱针绣工艺的要求。由于乱针绣工艺十分复杂，国内外很少有计算机辅助乱针绣制作的研究，主要的研究包括中国专利《一种计算机辅助乱针绣制作方法》，公开号：CN101859335A，该专利以彩色图像作为输入，采用乱针绣绣线颜色选择和针迹生成技术生成乱针绣绣品的针迹序列，并将其输入刺绣机得到乱针绣绣品。然而，其在乱针绣的实际制作过程中影响其绣制结果的因素不仅仅有绣线的颜色，还有绣线排布的长度、密度等多种因素；在针迹生成上，其采用试探法仅仅根据图像局部区域 的颜色差异、梯度方向确定绣线针迹而没有考虑到其他图像特征例如区域矢量场，图像的显著性特征对于针迹生成的影响。另外的研究还包括中国专利《一种采用遗传算法的计算机辅助乱针绣制作方法》，公开号：101310211288.2，该专利采用遗传算法优化乱针绣针法排布中的参数，虽然该方法考虑了图像特征对针法排布当中的密度、长度等的影响，但是由于其对于一个区域设定统一的参数使得结果过于呆板，缺乏灵活性，且方法所需时间较长，效率较低。 

从乱针绣的制作过程上看，其关键是根据输入的彩色图像生成乱针绣制作所需要的针迹序列，我们可以将生成乱针绣针迹序列的过程看成一个基于图像的艺术化绘制过程。相关研究主要包括了文献1Oliver D,Stefan H,Cornelius v O,et al.Floating Points:A Method for Computing Stipple Drawings.Computer Graphics Forum,2000,19(3):41-50所述采用点为单位填充区域，其对于单个点的定义主要包括了对其位置和半径大小的定义，在确定点笔触参数时通过在关键点按照一定的灰度区域放置不同大小的黑色点，然后由预先定义的模板采用误差扩散法计算出放置这一点后对模板中其他像素整体的色调的影响，并计算模板中其他像素经过误差扩散后的新的色调值，根据色调值计算是否放置新的点笔触以及确定点笔触的大小。在线画法中，相关研究主要包括了影线画法和色彩画法。影线画法如文献2Stefan H,Heino H,Oliver D.Beyond stippling—methods for distributing objects on the plane.Computer Graphics Forum,2003,22(3):515-522中所述采用长短、粗细不一的线段作为基本笔触填充单位，因此其采用的笔触模型为包括位置、长短、粗细、朝向在内的单根参数化线段模型。在参数的确定方面，其采用泰森多边形算法(Voronoi)将图像划分成不同的小区域，在每个小区域中放置笔触，笔触的长短、粗细、朝向等则可以根据划分出的小区域的大小、所覆盖位置的亮度、图像梯度或者小区域朝向来确定。在色彩画法中，如文献3Michio S,Yasushi Y.An Algorithm For Automatic Painterly Rendering Based On Local Source Image Approximation.Proceedings of the1st international symposium on Non-photorealistic animation and rendering.ACM,2000.53-58中所述笔触模型的定义则多采用B样条曲线来定义笔触，生成的笔触线条多为曲线线条，通过曲线线条的弯曲、转折来模拟艺术家的创作过程。但是，在乱针绣实际制作过程中是以相互交叉的平直绣线作为基本的绣制单位，需要定义包括了交叉针位置、长度、朝向、夹角等参数与已有的笔触参数 定义存在很大的不同。另外在参数的设置过程中，对于点画法和影线画法，其笔触参数是根据图像亮度来进行设定，其艺术本身多是以表现阴影特征为主，因此所生成的笔触往往没有覆盖亮度较高的区域，而乱针绣本身则要求绣线均匀覆盖满整个区域。而对于色彩画法，现有的笔触设定方法多是采用图像矢量场或是图像梯度场生成笔触的控制点，也不适用于乱针绣这种以平直绣线为基本填充单位的绣制方法。 

在笔触相互之间依赖关系的建立方面，相关研究主要包括文献4Mingtian Z,Song-Chun Z.Customizing Painterly Rendering Styles Using Stroke Processes.Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation and Rendering.ACM,2011.137-146提出的基于反应扩散方法建立笔触参数之间的关系，其首先建立笔触之间的空间拓扑关系，而后采用反应扩散的方法得到笔触参数之间的关系。其只是单纯的对笔触参数进行平滑或者锐化操作，且需要用户自己指定相关的平滑参数。在乱针绣的实际制作过程中，艺术家在放置单独每一根绣线看似是杂乱无章的，但是在一定的范围内绣线在整体上是有一定的规律的，即所谓的“小乱大不乱”。因此我们需要设计适合乱针绣的笔触依赖关系确定方法。 

综上所述，本发明提出了采用模糊聚类与随机游走的计算机辅助乱针绣制作方法。该方法首先对乱针绣针法基元—交叉针进行了参数化定义，并且采用枚举实验的方法给出了交叉针参数与图像显著性、颜色分布以及矢量场混乱度等图像特征之间的关系。而后本文采用模糊聚类与随机游走聚类方法对笔触点按照他们所对应的特征进行聚类，并且将聚类的结果用于指导交叉针参数的设定，得到了最终的交叉针针迹序列，从而得到了可用于机器绣制的乱针绣针迹方案。 

发明内容

发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供了采用模糊聚类与随机游走的计算机辅助乱针绣制作方法，该方法支持用户以彩色图像作为输入直接获取相应的乱针绣绣品。 

技术方案：采用模糊聚类与随机游走的计算机辅助乱针绣制作方法，其特征在于，包括以下步骤： 

步骤一，确定交叉针参数与图像特征映射关系：包括定义交叉针参数，以及确定交叉针参数与图像特征之间的映射关系； 

步骤二，交叉针聚类及针迹序列生成：针对给定图像生成交叉针集合，对交叉针集合包含的交叉针采用基于模糊聚类与随机游走算法进行聚类，依据步骤一得到的映射关系设定每一个类别的交叉针参数，得到乱针绣绣品的针迹序列； 

步骤三，将步骤二中得到的乱针绣绣品针迹序列转换为电脑刺绣机使用的以毫米为单位的坐标格式，将其输入电脑刺绣机，从而得到给定图像对应的乱针绣绣品。 

本发明步骤一中所述确定交叉针参数与图像特征映射关系包括以下步骤：步骤11，定义交叉针参数，将两根相交的绣线定义为一个交叉针，每个交叉针包含参数p_i、θ_i、β_i、ξ_i以及γ_i：p_i表示两条绣线的交叉点，p_i控制交叉针的位置，下标i表示第i个交叉针；θ_i为交叉针针迹方向即相交绣线的角平分线方向，θ_i控制交叉针的朝向，θ_i的取值范围在0°～180°之间；β_i为交叉针夹角即两条绣线与角平分线的夹角，β_i控制两根绣线之间的交叉角度，取值范围在0°～45°之间；ξ_i表示交叉针长度，ξ_i控制相互交叉的两根等长度绣线的长度，取值范围在10～40个像素之间；γ_i为交叉针混乱度，用来控制交叉针随机变动的混乱程度；每根绣线的朝向在[-45.0,45.0]*γ_i的范围内随机变动，γ_i的取值范围在0～1之间。 

步骤12，采用枚举实验方法确定映射关系：确定交叉针参数与图像特征之间的映射关系；从训练图像库中随机选取一组图像，对于每幅图像选择位于图像左上角100×100大小的区域作为实验所用图像区域，采用枚举实验方法确定映射关系具体为：步骤121：确定交叉针长度ξ_i与图像显著性特征映射关系；步骤122：确定交叉针夹角β_i与图像颜色分布特征映射关系；步骤123：确定交叉针混乱度γ_i与图像矢量场混乱度映射关系。 

步骤121中，确定交叉针长度ξ_i与图像显著性特征映射关系具体为：步骤121a：任意选择一个图像区域，提取其中每个像素点所对应的图像显著性特征，并求取图像区域中所有像素点的图像显著性特征的平均值；步骤121b：另令计数参数length=0；步骤121c：如果计数参数length=0，采用Sobel算子计算图像区域在水平轴x和垂直轴 y方向上的图像梯度，否则转步骤121m；步骤121d：计算每个图像区域的交叉针针迹总体方向θ^a；步骤121e：计算每个图像区域的交叉针整体夹角β^a；步骤121f：在图像区域范围内生成方向为θ^a+β^a和θ^a-β^a相互交叉的两组平行线段，两组平行线段内相互平行的平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，其中ρ为平行线段之间的疏密程度的控制参数；步骤121g：计算图像区域的周长，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段；步骤121h：将得到的线段两两之间存在交叉的组合成为一个交叉针，得到交叉针集合Λ^a，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ^a+β^a与θ^a-β^a，即交叉针 的朝向θ_i=θ^a，交叉针的夹角β_i=β^a，每根交叉针的绣线颜色设定为其中心点所对应的原图中的颜色；步骤121i：将每个交叉针的参数调整为ξ_i=30*length/100+10，β_i=10，γ_i=0.1；步骤121j：将交叉针集合Λ^a绘制在白色画布上，得到交叉针集合Λ^a所对应的绘制结果图像，并计算原实验区域和绘制结果图像所对应的图像细节特征图像；步骤121k：计算图像区域和绘制结果图像所对应的图像细节特征图像之间的差异值步骤121l：对计数参数进行累加赋值length=length+1，转步骤121c；步骤121m：求取所有差异值中最小的差异值所对应的交叉针长度ξ_i，转步骤121a直到所有实验所用图像区域都被处理完；步骤121n：得到每个实验所用图像区域所对应的最优交叉针长度ξ_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果。 

步骤122中，确定交叉针夹角β_i与图像颜色分布特征映射关系具体为：步骤122a：任意选择一个图像区域，采用Sobel算子计算图像区域在水平轴x和垂直轴y方向上的图像梯度，根据图像梯度计算图像区域内所有像素的图像颜色分布特征，并对所有像素的图像颜色分布特征求平均值得到图像区域的颜色分布特征；步骤122b：另计数参数beta=0；步骤122c：如果计数参数beta≤100，计算每个图像区域的交叉针针迹总 体方向θ^b，否则转步骤122l；步骤122d：计算每个图像区域的交叉针整体夹角β^b；步骤122e：在图像区域范围内生成方向为θ^b+β^b和θ^b-β^b相互交叉的两组平行线段，两组平行线段内相互平行的平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)；步骤122f：计算图像区域的周长，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段；步骤122g：将得到的线段两两之间存在交叉的组合成为一个交叉针 得到交叉针集合Λ^b，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ^b+β^b与θ^b-β^b，即交叉针的朝向θ_i=θ^b，交叉针夹角β_i=β^b，每根交叉针的绣线颜色设定为其中心点所对应的原图中的颜色；步骤122h：将每个交叉针的参数调整为ξ_i=20，β_i=45*beta/100，γ_i=0.1；步骤122i：将交叉针集合Λ^b绘制在白色画布上，得到交叉针集合Λ^b所对应的绘制结果图像，并分别计算图像区域和绘制结果图像所对应的图像颜色直方图；步骤122j：计算实验区域和绘制结果图像所对应的图像颜色直方图之间的卡方差步骤122k：对计数参数进行累加赋值beta=beta+1，转步骤122c；步骤122l：求取所有卡方差中最小的差异值所对应的交叉针长度β_i，转步骤122a直到所有实验所用图像区域都被处理完；步骤122m：得到每个实验所用图像区域所对应的最优交叉针夹角β_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果。 

步骤123中，确定交叉针混乱度γ_i与图像矢量场混乱度映射关系具体为：步骤123a：任意选择一个图像区域，提取图像区域的矢量场，对图像区域内所有像素的矢量场混乱度求平均值得到图像区域的矢量场混乱度；步骤123b：另计数参数gama=0；步骤123c：如果计数参数gama≤100，采用Sobel算子计算图像区域在水平轴x和垂直轴y方向上的图像梯度，否则转步骤123m；步骤123d：计算每个区域的交叉针针迹总体方向θ^c；步骤123e：计算每个区域的交叉针整体夹角β^c；步骤123f：在图像区域范围内生成方向为θ^c+β^c和θ^c-β^c相互交叉的两组平行线段，两组平行线段内相互平行的 平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)；步骤123g：计算图像区域的周长，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段；步骤123h：将得到的线段两两之间存在交叉的组合成为一个交叉针得到交叉针集合Λ^c，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ^c+β^c与θ^c-β^c，即交叉针的朝向θ_i=θ^c，交叉针夹角β_i=β^c，每根交叉针的绣线颜色设定为其中心点所对应的原图中的颜色；步骤123i：将每个交叉针的参数调整为ξ_i=20，β_i=20，γ_i=gama/100；步骤123j：将交叉针集合Λ^c绘制在白色画布上，得到交叉针集合Λ^c所对应的绘制结果图像；步骤123k：计算图像区域与绘制结果图像之间的色差步骤123l：对计数参数进行累加赋值gama=gama+1，转步骤123c；步骤123m：求取所有色差中最小的差异值所对应的交叉针长度γ_i，转步骤123a直到所有实验所用图像区域都被处理完；步骤123n：得到每个实验所用图像区域所对应的最优交叉针长度γ_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果。 

本发明步骤二中所述交叉针聚类及针迹序列生成具体包括以下步骤：步骤21：将给定图像分割成为不同的对象区域，每个对象区域为一组像素点集合，，集合中任意像素点至少与该集合中另一像素点相邻；步骤22：提取每个对象区域的矢量场和显著性特征图像；步骤23：对于每一个对象区域，采用Sobel算子计算对象区域在水平轴x和垂直轴y方向上的图像梯度；步骤24：计算每个对象区域的交叉针针迹总体方向θ；步骤25：计算每个对象区域的交叉针夹角β；步骤26：在对象区域范围内生成方向为θ+β和θ-β相互交叉的两组平行线段，平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，其中ρ为平行线段之间的疏密程度的控制参数；步骤27：计算对象区域的周长，以周长的十分之一为长度将两组平行线段内的每条平行线段各自分为一组线段；步骤28：将得到的线段两两之间存在交叉的组合成为一个交叉针Λ_i，得到交叉针集合Λ，其中 交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ+β与θ-β，即交叉针Λ_i的朝向θ_i=θ，交叉针夹角；步骤29：建立交叉针集合Λ的空间拓扑关系，得到交叉针集合Λ的邻接矩阵A；步骤210：对交叉针集合中每一个交叉针Λ_i，分别提取其中心点所对应的图像特征，包括图像显著性特征、图像颜色分布特征以及图像矢量场混乱度，得到每个交叉针所对应的特征向量x_i,i=1,2,...,N，N为交叉针集合Λ中总的交叉针数目，每个特征向量x_i的维度h=3分别为x_i={x_i1,x_i2,x_i3}，其中x_i1表示交叉针Λ_i中心点所对应的图像显著性特征，x_i2表示交叉针Λ_i中心点所对应的图像颜色分布特征，x_i3表示交叉针Λ_i中心点所对应的矢量场混乱度；步骤211：采用基于模糊聚类与随机游走算法对交叉针进行聚类，得到每个交叉针Λ_i对应的类别L_i，L_i∈1～K，其中K为聚类数目；步骤212：根据每个交叉针对应的类别，按照步骤一得到的映射关系重新调整每个交叉针的针法参数，得到调整后的交叉针集合Λ'；步骤213：根据交叉针集合Λ'得到每根绣线的起始点和终止点，创建未排序的针迹序列，从而获取对象区域的未排序的针迹序列stitches；步骤214：对未排序针迹序列stitches按照其绣线覆盖面积的图像显著性大小进行排序，得到重新排列的针迹序列。 

其中，步骤29中建立交叉针集合Λ的空间拓扑关系具体包括：步骤29a：对于交叉针集合中的每一个交叉针Λ_i，计算其中心点与交叉针集合中所有其他交叉针中心点之间的欧式距离其中p_i.x,p_i.y,p_j.x,p_j.y分别表示交叉针中心点p_i与p_j的坐标，i=1,...,N，j=1,2,...,i-1,i+1,...,N；步骤29b：对得到的距离按照由小到大的顺序进行升序排列，得到与交叉针Λ_i距离最近的前4个交叉针Λ_a,Λ_b,Λ_c,Λ_d；步骤29c：将与交叉针相邻的交叉针序号分别设定为步骤29b中所得到的4个交叉针的下标a,b,c,d。 

其中步骤211中采用基于模糊聚类与随机游走算法对交叉针进行聚类具体包括：步骤211a：初始化聚类中心：如果聚类数K为指定值，则随机生成K个h维向量作为 K个聚类中心c_j，j=1,...,K；否则，采用均值漂移算法，自动计算聚类数K，并产生K个聚类中心c_j，j=1,...,K；步骤211b：计算交叉针Λ_i的特征向量x_i与聚类中心c_j的距离d_ij，i=1,...N，j=1,...,K；步骤211c：计算交叉针Λ_i从属于聚类j的隶属度u_ij，即交叉针Λ_i从属于聚类j的概率；步骤211d：建立邻接图G，邻接图的顶点集V=V_x∪V_c，由网格面片顶点集V_x={v_i|i=1,...,N}与聚类顶点集组成，网格面片顶点集中的每个顶点v_i对应交叉针集合中的一个交叉针，聚类顶点集中的每个顶点表示一个聚类；如果交叉针Λ_i和交叉针Λ_i'满足i'∈{A_i1,A_i2,A_i3,A_i4}或者i∈{A_i'1,A_i'2,A_i'3,A_i'4}，则称它们相邻，将其对应的顶点v_i和v_i'在邻接图G中连接边，计算边的网格面片顶点权重w_ii'；步骤211e：将每个交叉针所对应的顶点与所有聚类所对应的顶点在邻接图G中连接边，计算边的权重步骤211f：将聚类顶点集中的顶点作为种子点，网格面片顶点集中的顶点作为非种子点，通过随机游走算法，计算一个随机游走者从非种子点i出发，在到达其他种子点之前到达种子点的概率枚举当前要计算的种子点seed，计算表示一个随机游走者从每个非种子点出发，在到达其他种子点之前到达种子点seed概率的N维向量p^seed，将N维向量p^seed中的概率值作为隶属度u_ij，从而对隶属度进行更新；步骤211g：聚类中心计算：根据步骤211f中更新后的隶属度，以及交叉针特征向量x_i，计算新的聚类中心c_j′；步骤211h：判断是否收敛：计算新的聚类中心c_j′和原聚类中心c_j的距离d^c，若距离d^c小于阈值ε，则说明已收敛，转步骤211i；否则，用新的聚类中心c_j′替换原聚类中心c_j，并转步骤211b，所述阈值ε为10^-6；步骤211i：根据最终的隶属度u_ij，将交叉针划分到所属的聚类中，每个交叉针所属的聚类类别L_i，L_i∈1～K为该交叉针对应隶属度最大的聚类，从而获得K个聚类，每个聚类都由属于该聚类的交叉针组成。 

其中步骤212中，根据每个交叉针对应的类别，重新调整每个交叉针的针法参数 具体包括：步骤212a：对任意交叉针聚类类别L_i，遍历交叉针集合Λ中的所有交叉针，找出所有聚类类别L_i=k的交叉针，记为其中表示每个属于类别k的交叉针，Q为类别k交叉针总数目；步骤212b：根据步骤121n、步骤122m以及步骤123n的拟合结果，计算聚类中心c_j,j=k所对应的交叉针长度、交叉针夹角以及交叉针混乱度；步骤212c：将交叉针集合Λ^k中所有交叉针的交叉针长度、交叉针夹角和交叉针混乱度调整为步骤212b所计算出来的交叉针参数；步骤212d：将交叉针集合Λ^k中的所有交叉针朝向调整为其中心点所在图像区域的矢量场方向；步骤212e：对所有交叉针类别分别进行步骤212a～步骤212d，得到经过调整后的交叉针集合Λ'；步骤212f：每根交叉针的绣线颜色设定为其中心点所对应的原图中的颜色。 

其中步骤214中，对未排序针迹序列进行排序具体包括：步骤214a：计算未排序针迹序列stitches中每根绣线所覆盖的I_salience图像面积的图像显著性stitchsalience_k；步骤214b：根据计算得到的图像显著性stitchsalience_k，按照stitchsalience_k的大小对针迹序列stitches进行升序排列，得到排序后的针迹序列newstitches，排在前面的即为要先进行绣制的绣线。 

本发明前两个步骤生成了一个针迹序列，针迹的起始点和终止点的坐标都是以像素为单位，而电脑刺绣机所使用的坐标一般是以毫米作为单位。步骤四将以像素为单位的针迹坐标数据乘以绣线宽度即可得到以毫米作为单位的电脑刺绣机坐标，再将其输入电脑刺绣机即可得到乱针绣绣品。 

最后再将得到的电脑刺绣机格式的乱针绣绣品针迹序列输入电脑刺绣机，从而得到给定图像对应的乱针绣绣品。 

有益效果：本发明具有以下优点：1、允许用户以任意的彩色图像作为输入，得到其相应的乱针绣制作结果，大大减少了传统的手工作业量，提高了乱针绣制作效率；2、定义了交叉针参数与图像特征之间的映射关系，首次以函数方程的形式给出了乱针绣针法与图像特征的定量关系；3、本发明采用自动聚类的方法确定交叉针参数之间的依赖关系，效率高、精度大，能够有效的再现乱针绣在实际制作过程中的针法排布特点。 综上所述，本发明依据输入的彩色图像采用计算机辅助手段自动完成乱针绣的制作过程，并对乱针绣的制作生成做了有意义的尝试，有助于乱针绣这门技艺的传承和发展。 

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。 

图1为本发明的流程图。 

图2为本发明的交叉针参数定义。 

图3为本发明最终乱针绣绣制效果图。 

具体实施方式：

本发明公开了一种采用模糊聚类与随机游走算法的计算机辅助乱针绣制作方法，如图1所示，下面分别介绍各实施例部分的主要流程： 

1、确定交叉针参数与图像特征映射关系 

本发明要确定交叉针参数与图像特征之间的映射关系，如步骤一所述，具体包括了交叉针的参数化定义、交叉针初始排布生成以及映射关系确定，下面分步一一进行介绍。 

1.1定义交叉针参数 

乱针绣的运针要求绣线线条针针交叉，绣线交叉是乱针绣的特点，因此我们需要定义单个交叉针的参数。在实际绣制中，交叉针主要有以下特点：（1）乱针绣中绣线交叉的形式大致可以分为两大类：大乱针和小乱针，前种针法运用时，线条交叉朝向具有一定的方向性，如直斜、横斜或倾向角度的交叉；后种针法的线条交叉的朝向则一般是向四面散开的，没有方向性。可见，线条交叉方向的控制是定义交叉线条的重要因素。（2）交叉针根据其所在对象区域的纹理的不同，其交叉角度的大小也不同，纹理分布较为规律的区域交叉角度较小，纹理分布杂乱的区域在绣制时的交叉角度也较大，因此线条交叉角度也是定义交叉线条的重要因素。（3）在乱针绣的实际绣制中，乱针绣艺人会根据所要绣制对象在图中的重要程度分别施以不同长度的针迹，对于图中重要程度比较高的区域往往采用比较细的绣线来表达其细节特征，反之则采用比较长的绣线进行绣制。综上，本发明将两根相交的绣线定义为一个交叉针，如图2所示。每个交叉针参数定义如下： 

（1）交叉针位置p_i：L₁和L₂为相交的绣线，p_i为L₁和L₂交点，p_i控制了交叉针所放置的位置； 

（2）交叉针朝向θ_i：AB为L₁和L₂角平分线，θ_i为AB与x轴夹角，控制了交叉针的整体朝向，取值范围在0°～180°之间； 

（3）交叉针夹角β_i：参数β_i为L₁与L₂的夹角，β_i越小，L₁和L₂的方向越接近，控制了两根绣线之间的交叉角度，取值范围在0°～45°之间； 

（4）交叉针长度ξ_i：绣线L₁与L₂的交叉针长度，控制了相互交叉的两根等长度绣线的长度，取值范围在10～40个像素之间； 

（5）交叉针混乱度γ_i：为了保证交叉针在局部有一定的混乱度，在生成交叉针后本文允许每根绣线的朝向在[-45.0,45.0]*γ_i的范围内随机变动以保证交叉针排布的多样性，γ_i则是用来控制交叉针随机变动程度，取值范围在0～1之间。 

1.2映射关系确定 

为了确定针法参数与图像特征之间的关系，本文采用枚举实验方法通过不断变换交叉针参数并从中选择填充图像区域的最优参数确定某一交叉针参数与对应图像特征之间的映射关系，如步骤12所述。本发明选择的用于实验的图像库为BSDS500(http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.ht ml)图像库，我们从中随机选择了126幅图像，对于每幅图像我们选择位于图像左上角100×100大小的图像区域作为实验所用图像区域，记为其中对于交叉针Λ_i的朝向θ_i本发明则直接根据图像矢量场对其进行设定。 

（1）确定交叉针长度ξ_i与图像显著性特征映射关系： 

输入：实验区域R^text； 

输出：交叉针长度ξ_i与图像显著性特征Salience映射关系f₁，ξ_i=f₁(Salience)； 

步骤121a：任意选择一个图像区域采用文献5Ming-Ming C,Guo-Xin Z,Mitra N J,et al.Global contrast based salient region detection[A].Computer Vision and Pattern  Recognition(CVPR),2011IEEE Conference on[C].IEEE,2011.409-416所述方法提取图像区域每个像素点所对应的图像显著性特征，并求取其图像区域中所有像素图像显著性特征的平均值Salience； 

步骤121b：另计数参数length=0； 

步骤121c：如果计数参数length≤100，采用文献6R.Gonzalez and R.Woods,Digital Image Processing.New York:Addison-Wesley,1992所述Sobel算子计算图像区域在水平轴x和垂直轴y方向上的图像梯度G_x(s)，G_y(s)，s表示区域中的像素点，否则转步骤121m； 

步骤121d：采用公式(1)计算每个图像区域的交叉针针迹总体方向θ^a： 

$>{\theta }^a=\frac{1}{2}\arctan \left(\frac{V_x}{V_y}\right)---\left(1\right)$>

其中$>V_x=\underset{s\in R_t^{\mathrm{text}}}{\Sigma }2G_x\left(s\right)G_y\left(s\right),V_y=\underset{s\in R_t^{\mathrm{text}}}{\Sigma }\left(G_x{\left(s\right)}^2{-G}_y{\left(s\right)}^2\right);$>

步骤121e：采用公式(2)计算每个图像区域的交叉针整体夹角β^a： 

$>{\beta }^a=\arctan \left(\sqrt{\frac{\underset{s\in R_t^{\mathrm{text}}}{\Sigma }{G}_x{\left(s\right)}^2}{\underset{s\in R_t^{\mathrm{text}}}{\Sigma }{G}_y{\left(s\right)}^2}}\right)---\left(2\right)$>

步骤121f：在图像区域范围内生成方向为θ^a+β^a和θ^a-β^a相互交叉的两组平行线段，两组平行线段内相互平行的平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，其中ρ为平行线段之间的疏密程度的控制参数，ρ取值范围在0～1之间，为了保证生成的绣线能覆盖整个区域，本发明取ρ=0.8； 

步骤121g：计算图像区域的周长perimeter，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段； 

步骤121h：将得到的线段两两之间存在交叉的组合成为一个交叉针得到交叉针集合Λ^a，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣 线方向分别为θ^a+β^a与θ^a-β^a，即交叉针的朝向θ_i=θ^a，交叉针的夹角β_i=β^a，每根交叉针的绣线颜色设定为其中心点所对应的图像区域中的颜色； 

步骤121i：为了考察交叉针长度与图像显著性特征的映射关系，我们固定每个交叉针的交叉针夹角和交叉针混乱度，只改变交叉针长度，即将每个交叉针的参数调整为ξ_i=30*length/100+10，β_i=10，γ_i=0.1； 

步骤121j：将交叉针集合Λ^a绘制在白色画布上，得到交叉针集合Λ^a所对应的绘制结果图像并采用文献7Kang H,Lee S,Chui C.K.Coherent line drawing.In:Proceedings of the5th international symposium on Non-photorealistic animation and rendering(NPAR'2007).San Diego:ACM Press,2012.43-50所述方法分别计算图像区域R^text和绘制结果图像I_Simulation所对应的图像细节特征图像，记为CLD_text，

步骤121k：按照公式(3)计算CLD_text与之间的差异值

$>{\Delta }_{\mathrm{length}}^t=\underset{\mathrm{pixel}\in R_t^{\mathrm{text}}}{\Sigma }\left|\right|{\mathrm{CLD}}_{\mathrm{text}}\left(\mathrm{pixel}\right),{\mathrm{CLD}}_{\mathrm{Simulation}}^a\left(\mathrm{pixel}\right)\left|\right|/10000---\left(3\right)$>

步骤121l：对计数参数进行累加赋值length=length+1，转步骤121c； 

步骤121m：求取所有差异值中最小的差异值所对应的交叉针长度ξ_i，转步骤121a直到所有实验所用图像区域都被处理完； 

步骤121n：得到每个实验所用图像区域所对应的最优交叉针长度ξ_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果如公式(4)： 

ξ_i=f₁(Salience)=40.64*e^{-5.372*Salience}+12.77*e^{0.1905*Salience}    (4) 

（2）确定交叉针夹角β_i与图像颜色分布特征映射关系： 

输入：实验区域R^text； 

输出：交叉针长度ξ_i与图像颜色分布特征ColorDistribution映射关系f₂，ξ_i=f₂(ColorDistribution)； 

步骤122a：任意选择一个图像区域采用Sobel算子计算其在水平轴x和垂直 轴y方向上的图像梯度采用公式(5)求取其包含像素点的图像颜色分布特征ColorDistribution_s： 

$>\mathrm{ColorDistribut}{\mathrm{ion}}_s=\left(\begin{array}{cc}\sqrt{\frac{\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_x^t{\left(s^{\prime }\right)}^2}{\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_y^t{\left(s^{\prime }\right)}^2}}& \mathrm{if}\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_x^t{\left(s^{\prime }\right)}^2<\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_y^t{\left(s^{\prime }\right)}^2\\ \sqrt{\frac{\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_y^t{\left(s^{\prime }\right)}^2}{\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_x^t{\left(s^{\prime }\right)}^2}}& \mathrm{if}\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_x^t{\left(s^{\prime }\right)}^2\ge \underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }{G}_y^t{\left(s^{\prime }\right)}^2\end{array}\right)---\left(5\right)$>

其中σ(s)表示像素点s的8邻域像素点集合，对图像区域内所含像素的图像颜色分布特征求平均值得到该区域的颜色分布特征ColorDistribution； 

步骤122b：另计数参数beta=0； 

步骤122c：如果计数参数beta≤100，采用公式(1)计算每个图像区域的交叉针针迹总体方向θ^b，否则转步骤122l： 

步骤122d：采用公式(2)计算每个图像区域的交叉针整体夹角β^b： 

步骤122e：在图像区域范围内生成方向为θ^b+β^b和θ^b-β^b相互交叉的两组平行线段，两组平行线段内相互平行的平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，本发明取ρ=0.8； 

步骤122f：计算图像区域的周长perimeter，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段； 

步骤122g：将得到的线段两两之间存在交叉的组合成为一个交叉针得到交叉针集合Λ^b，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ^b+β^b与θ^b-β^b，即交叉针的朝向θ_i=θ^b，交叉针的夹角β_i=β^b，每根交叉针的绣线颜色设定为其中心点所对应的图像区域中的颜色； 

步骤122h：为了考察交叉针夹角与图像颜色分布特征的映射关系，我们固定每个 交叉针的交叉针长度和交叉针混乱度，只改变交叉针夹角，即将每个交叉针的参数调整为ξ_i=20，β_i=45*beta/100，γ_i=0.1； 

步骤122i：将交叉针集合Λ^b绘制在白色画布上，得到交叉针集合Λ^b所对应的绘制结果图像并分别计算图像区域R^text和绘制结果图像所对应的图像颜色直方图，记为H_text，

步骤122j：按照文献8Pablo A,Michael M,Charless F,Jitendra M.Contour Detection and Hierarchical Image Segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(5):898～916所述方法计算H_text与之间的卡方差

步骤122k：对计数参数进行累加赋值beta=beta+1，转步骤122c； 

步骤122l：求取所有卡方差中最小的差异值所对应的交叉针长度β_i，转步骤122a直到所有实验所用图像区域都被处理完； 

步骤122m：得到每个实验所用图像区域所对应的最优交叉针夹角β_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果如公式(6)： 

β_i=f₂(ColorDistribution)=78.42*e^{1.432*ColorDistribution}-78.52*e^{1.427*ColorDistribution}      (6) 

（3）确定交叉针混乱度γ_i与图像矢量场混乱度映射关系： 

输入：实验区域R^text； 

输出：交叉针长度ξ_i与图像矢量场混乱度VectorChaos映射关系f₃，ξ_i=f₃(VectorChaos)； 

步骤123a：任意选择一个图像区域采用文献7所述方法提取图像区域的矢量场Θ并按照公式(7)计算区域所包含每个像素点s对应的矢量场混乱度VectorChaos_s： 

$>{\mathrm{Vector}}_s=\frac{\underset{s^{\prime }\in \sigma \left(s\right)}{\Sigma }(1-\cos (2\Theta \left(s^{\prime }\right)-2\bar{\Theta }))/2}{8}---\left(7\right)$>

其中表示图像区域的平均矢量场方向，σ(s)表示像素点s的8邻域像素点集合，对图像区域内所含像素的矢量场混乱度求平均值得到该区域的矢量场混乱度VectorChaos； 

步骤123b：另计数参数gama=0； 

步骤123c：如果计数参数gama≤100，采用文献6所述Sobel算子计算图像区域在水平轴x和垂直轴y方向上的图像梯度G_x(s)，G_y(s)，s表示区域中的像素点，否则转步骤123m； 

步骤123d：采用公式(1)计算每个图像区域的交叉针针迹总体方向θ^c： 

步骤123e：采用公式(2)计算每个图像区域的交叉针整体夹角β^c： 

步骤123f：在图像区域范围内生成方向为θ^c+β^c和θ^c-β^c相互交叉的两组平行线段，两组平行线段内相互平行的平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，本发明取ρ=0.8； 

步骤123g：计算图像区域的周长perimeter，以周长的十分之一为单位长度将两组平行线段内的每条平行线段各自分为一组线段； 

步骤123h：将得到的线段两两之间存在交叉的组合成为一个交叉针得到交叉针集合Λ^c，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ^c+β^c与θ^c-β^c，即交叉针的朝向θ_i=θ^c，交叉针Λ_i的夹角β_i=β^c，每根交叉针的绣线颜色设定为其中心点所对应的图像区域中的颜色； 

步骤123i：为了考察交叉针混乱度与矢量场混乱度的映射关系，我们固定每个交叉针的交叉针长度和交叉针夹角，只改变交叉针混乱度，即将每个交叉针的参数调整为ξ_i=20，β_i=20，γ_i=gama/100； 

步骤123j：将交叉针集合Λ^c绘制在白色画布上，得到交叉针集合Λ^c所对应的绘制结果图像

步骤123k：按照公式(8)计算图像区域R^text与绘制结果图像之间的色差 

$>{\Delta }_{\mathrm{gama}}^t=\sqrt{{(R\left(R^{\mathrm{text}}\right)-R\left(I_{\mathrm{Simulation}}^c\right))}^2+{(G\left(R^{\mathrm{text}}\right)-G\left(I_{\mathrm{Simulation}}^c\right))}^2+{(B\left(R^{\mathrm{text}}\right)-B\left(I_{\mathrm{Simulation}}^c\right))}^2}---\left(8\right)$>

其中R(R^text)，G(R^text)，B(R^text)，分别表示R^text与 在RGB三个通道上的像素值； 

步骤123l：对计数参数进行累加赋值gama=gama+1，转步骤123c； 

步骤123m：求取所有色差中最小的差异值所对应的交叉针长度γ_i，转步骤123a直到所有实验所用图像区域都被处理完； 

步骤123n：得到每个实验所用图像区域所对应的最优交叉针长度γ_i，采用指数函数模型对结果进行函数拟合，得到函数拟合结果如公式(9)： 

γ_i=f₃(VectorChaos)=0.1134*e^{-4.276*VectorChaos}+0.02144*e^{7.035*VectorChaos}      (9) 

2、交叉针聚类及针迹序列生成 

输入：输入的彩色图像I_src； 

输出：乱针绣绣品每个区域的针迹序列stitches={stitch_k:k=1～4N}，其中stitch_k={startx_k,starty_k,endx_k,endy_k,color_k}； 

步骤21：本发明首先采用文献8所述图像分割方法，将图像分割成为Z个不同的对象区域{R₁,R₂,...,R_Z}，每个对象区域R_z为一组像素点集合，集合中任意像素点至少与该集合中另一像素点相邻，z为区域序号； 

步骤22：采用文献7所述方法提取每个对象区域R_z的矢量场Θ，并采用文献5所述方法提取显著性特征图像I_salience； 

步骤23：对于每一个对象区域R_z，采用文献6所述Sobel算子计算对象区域R_z在水平轴x和垂直轴y方向上的图像梯度G_x(s)，G_y(s)，s表示区域R_z中的像素点； 

步骤24：采用公式(1)计算每个对象区域的交叉针针迹总体方向θ： 

步骤25：采用公式(2)计算每个对象区域的交叉针整体夹角β； 

步骤26：在图像区域范围内生成方向为θ+β和θ-β相互交叉的两组平行线段，两组平行线段之间的间隔为d=12*(1-ρ)/(1+ρ)，本发明取ρ=0.8； 

步骤27：计算对象区域的周长perimeter，以周长的十分之一为长度将两组平行线段内的每条平行线段各自分为一组线段； 

步骤28：将得到的线段两两之间存在交叉的组合成为一个交叉针Λ_i，得到交叉针集合Λ，其中交叉针的中心点p_i设为两条线段的交叉点，组成交叉针的两条绣线方向分别为θ+β与θ-β，即交叉针Λ_i的朝向θ_i=θ，交叉针Λ_i的夹角β_i=β； 

步骤29：建立交叉针集合Λ的空间拓扑关系，得到交叉针集合Λ的邻接矩阵A； 

步骤210：对交叉针集合中所包含的每一个交叉针Λ_i，采用文献5所述方法提取其中心点所对应的图像显著性特征，采用步骤122a中公式(5)计算其中心点所对应的颜色分布特征，并采用步骤123a中公式(7)计算其中心点对应的矢量场混乱度，得到每个交叉针所对应的特征向量x_i,i=1,2,...,N，N为交叉针集合Λ中总的交叉针数目，每个特征向量的维度h=3，其中x_i1表示交叉针Λ_i中心点所对应的图像显著性特征，x_i2表示交叉针Λ_i中心点所对应的图像颜色分布特征，x_i3表示交叉针Λ_i中心点所对应的矢量场混乱度； 

步骤211：采用基于模糊聚类与随机游走算法对交叉针进行聚类，得到每个交叉针Λ_i对应的类别L_i，L_i∈1～K，其中K为聚类数目； 

步骤212：根据每个交叉针对应的类别，重新调整每个交叉针的针法参数，得到调整后的交叉针集合Λ'； 

步骤213：根据交叉针集合Λ'根据公式(10)得到每根绣线的起始点和终止点，创建未排序的针迹序列，从而获取对象区域的未排序的针迹序列stitches： 

$>\left(\begin{array}{c}{\mathrm{startx}}_k=m_k+\frac{{\xi }_k}{2}*\cos \left({\phi }_k\right),\mathrm{start}{y}_k=m_k+\frac{{\xi }_k}{2}*\sin \left({\phi }_k\right)\\ {\mathrm{endx}}_k=m_k-\frac{{\xi }_k}{2}*\cos \left({\phi }_k\right),{\mathrm{endy}}_k=m_k-\frac{{\xi }_k}{2}*\sin \left({\phi }_k\right)\end{array}\right)---\left(10\right)$>

其中startx_k，starty_k，endx_k，endy_k分别表示绣线的起始点的横纵坐标和终止点的横纵坐标； 

步骤214：对未排序针迹序列stitches按照其绣线覆盖面积的图像显著性大小进行排序，得到重新排列的针迹序列。 

2.1交叉针空间拓扑关系计算 

在对交叉针进行聚类之前，首先要建立交叉针之间的空间拓扑关系，得到交叉针集合所对应的邻接矩阵A，如步骤29所述，具体为： 

输入：交叉针集合Λ； 

输出：邻接矩阵A={A_im|i=1,...,N;m=1,2,3,4}； 

步骤29a：对于交叉针集合中的每一个交叉针Λ_i，计算其中心点与交叉针集合中所有其他交叉针中心点之间的欧式距离，公式为： 

$>{\mathrm{Dis}}_{\mathrm{ij}}=\sqrt{{(p_i.x-p_j.x)}^2+{(p_i.y-p_j.y)}^2}---\left(11\right)$>

其中p_i.x,p_i.y,p_j.x,p_j.y分别表示交叉针中心点p_i与p_j的坐标，i=1,...,N，j=1,2,...,i-1,i+1,...,N； 

步骤29b：对得到的距离按照由小到大的顺序进行升序排列，得到与交叉针Λ_i距离最近的前4个交叉针Λ_a,Λ_b,Λ_c,Λ_d； 

步骤29c：另A_i1=a,A_i2=b,A_i3=c,A_i4=d。 

2.2基于模糊聚类与随机游走算法交叉针聚类 

根据所有交叉针的特征向量和其所对应的空间拓扑关系，采用基于模糊聚类与随机游走算法对交叉针进行聚类，得到每个交叉针Λ_i对应的类别L_i，L_i∈1～K，如步骤211所述，具体为： 

输入：交叉针集合Λ，交叉针所对应的特征向量x_i,i=1,2,...,N，邻接矩阵 A={A_im|i=1,...,N;m=1,2,3,4}； 

输出：每个交叉针Λ_i对应的类别L_i，L_i∈1～K； 

步骤211a：初始化聚类中心：如果聚类数K为指定值，则随机生成K个h维向量（h=3）作为K个聚类中心c_j，j=1,...,K；否则，采用均值漂移（mean-shift）算法，如文献9Comaniciu D.,MEER P.Mean shift:a robust approach towards feature space analysis.IEEE Transactions On Pattern Analysis and Machine Intelligence,2002,24(5):603-619.所述，自动计算聚类数K，并产生K个聚类中心c_j，j=1,...,K； 

步骤211b：采用公式(12)计算交叉针Λi的特征向量x_i与聚类中心c_j的距离d_ij，i=1,...N，j=1,...,K： 

$>d_{\mathrm{ij}}=\sqrt{\underset{t=1}{\overset{h}{\Sigma }}{(x_{\mathrm{it}}-c_{\mathrm{jt}})}^2}---\left(12\right)$>

其中，t表示特征向量的每个维度； 

步骤211c：计算交叉针Λ_i从属于聚类j的隶属度u_ij，即交叉针Λ_i从属于聚类j的概率，公式如下： 

$>u_{\mathrm{ij}}=\frac{1}{\underset{l=1}{\overset{K}{\Sigma }}{\left(\frac{d_{\mathrm{ij}}}{d_{\mathrm{il}}}\right)}^{2/(m-1)}}---\left(13\right)$>

其中，m∈(1,+∞)是控制算法柔性的加权指数参数，m取值越大，算法聚类的模糊程度越高，通常取值为2，d_ij是特征向量x_i与聚类中心c_l的距离，l表示聚类。 

步骤211d：建立邻接图G，邻接图的顶点集V=V_x∪V_c，由网格面片顶点集V_x={v_i|i=1,...,N}与聚类顶点集组成，网格面片顶点集中的每个顶点v_i对应交叉针集合中的一个交叉针，聚类顶点集中的每个顶点表示一个聚类；如果交叉针Λ_i和交叉针Λ_i'满足i'∈{A_i1,A_i2,A_i3,A_i4}或者i∈{A_i'1,A_i'2,A_i'3,A_i'4}，则称它们相邻，将其对应的顶点v_i和v_i'在邻接图G中连接边，边的网格面片顶点权重w_ii'为： 

$>w_{{\mathrm{ii}}^{\prime }}=e^{-{d_{{\mathrm{ii}}^{\prime }}}^2}---\left(14\right)$>

其中表示交叉针Λ_i和交叉针Λ_i'对应特征向量之间的距离； 

步骤211e：将每个交叉针所对应的顶点与所有聚类所对应的顶点在邻接图G中连接边，边的权重为： 

$>w_{\mathrm{ij}}^C=\gamma u_{\mathrm{ij}}{d}_i---\left(15\right)$>

其中，u_ij为交叉针Λ_i从属于聚类j的隶属度，d_j是交叉针Λ_i与其所有相邻交叉针顶点权重之和。γ是调节交叉针顶点权重w_ii'与聚类顶点权重的参数，取值范围为(0,1]，γ取值越小，聚类顶点对隶属度更新过程影响越小，相邻交叉针的影响越大，一般可设置为0.1； 

步骤211f：将聚类顶点集中的顶点作为种子点，网格面片顶点集中的顶点作为非种子点，通过随机游走算法，计算一个随机游走者从非种子点i出发，在到达其他种子点之前到达种子点的概率枚举当前要计算的种子点seed，可通过以下方程(16)计算表示一个随机游走者从每个非种子点出发，在到达其他种子点之前到达种子点seed概率的N维向量p^seed： 

(L+γD)p^seed=-B^Tm^seed      (16) 

其中，L为一个N×N的矩阵，其元素L_ii′为： 

d_i是交叉针Λ_i与其所有相邻网格面片的边的面片顶点权重之和，D是一个N×N的对角矩阵：D_ii=d_i，B是一个K×n的矩阵：B_ji=-γu_ijd_i，B^T表示矩阵B的转置矩阵m^seed为一个K维指示向量： 

p^seed是一个n维向量：表示一个随机游走者从非种子点i出发，在到达其他种子点之前到达种子点seed的概率。采用任何稀疏线性方程求解算法都可求解此方程，本专利具体实施过程中采用TAUCS稀疏线性方程求解库求解公式(5)所对应的稀疏线性方程得到概率值p^seed，参考文献10：Toledo,S.,Chen,D.,Rotkin,V.,2003.TAUCS:A library of sparse linear solvers,ver.2.2.http://www.tau.ac.il/～stoledo/taucs/。 

将概率值作为隶属度u_ij，从而对隶属度进行更新； 

步骤211g：聚类中心计算：根据步骤211f中更新后的隶属度，以及交叉针特征向量x_i，采用公式(19)计算新的聚类中心c_j′： 

$>{c_j}^{\prime }=\frac{\underset{i=1}{\overset{N}{\Sigma }}{u}_{\mathrm{ij}}^m{x}_i}{\underset{i=1}{\overset{N}{\Sigma }}{u}_{\mathrm{ij}}^m}---\left(19\right)$>

其中，u_ij是网格面片i从属于聚类j的隶属度，x_i是网格面片i的h=3维特征向量，m是控制算法柔性的加权指数参数； 

步骤211h：判断是否收敛：采用公式(19)计算新的聚类中心c_j′和原聚类中心c_j的距离d^c： 

$>d^c=\sqrt{\underset{j=1}{\overset{K}{\Sigma }}{(c_j-{c_j}^{\prime })}^2}---\left(20\right)$>

若距离d^c小于阈值ε，则说明已收敛，转步骤24i；否则，用新的聚类中心c_j′替换原聚类中心c_j，并转步骤26b，所述阈值ε为一个控制计算精度的阈值，一般可设置为10^-6; 

步骤211i：根据最终的隶属度u_ij，将交叉针划分到所属的聚类中，每个交叉针所属的聚类类别L_i，L_i∈1～K为该交叉针对应隶属度最大的聚类，即： 

$>u_{{\mathrm{iL}}_i}=\underset{j=1}{\overset{K}{\max }}{u}_{\mathrm{ij}}---\left(21\right)$>

从而获得K个聚类，每个聚类都由属于该聚类的交叉针组成。 

2.3交叉针参数调整 

在得到每个交叉针所对应的聚类类别后，需要对交叉针参数按照其聚类类别进行调 整，如步骤212所述，具体为： 

输入：交叉针集合Λ，每个交叉针Λ_i对应的类别L_i，L_i∈1～K，K个聚类中心c_j，j=1,...,K，区域的图像矢量场Θ； 

输出：经过调整过后的交叉针集合Λ'； 

步骤212a：对任意交叉针聚类类别L_i，遍历交叉针集合Λ中的所有交叉针，找出所有聚类类别L_i=k的交叉针，记为其中表示每个属于类别k的交叉针，Q为类别k交叉针总数目； 

步骤212b：根据公式(4)(6)(9)分别计算聚类中心c_j,j=k所对应的交叉针长度、交叉针夹角以及交叉针混乱度； 

步骤212c：将交叉针集合Λ^k中所有交叉针的交叉针长度、交叉针夹角和交叉针混乱度调整为步骤212b所计算出来的交叉针参数； 

步骤212d：将交叉针集合Λ^k中的所有交叉针朝向调整为其中心点所在图像区域的矢量场方向； 

步骤212e：对所有交叉针类别分别进行步骤212a～步骤212d，得到经过调整后的交叉针集合Λ'； 

步骤212f：每根交叉针的绣线颜色设定为其中心点所对应的原图中的颜色。 

2.4针迹序列排序 

为了达到更好的绣制效果，我们需要对得到的针迹序列进行排序，使得关键绣线的绣制顺序靠后，这样可以使得其不被后续的绣线所覆盖。如步骤214所述，对针迹序列按照其绣线覆盖面积的图像显著性大小进行排序，得到重新排列的针迹序列，具体为： 

输入：未排序的针迹序列stitches，图像显著性特征I_salience； 

输出：经过排序的针迹序列newstitches； 

步骤214a：计算未排序针迹序列stitches中每根绣线所覆盖的I_salience图像面积的图像 显著性stitchsalience_k，如公式(22)所示： 

$>\mathrm{stitchsalienc}{e}_k=\underset{\mathrm{pos}\in {\mathrm{stitch}}_k}{\Sigma }{I}_{\mathrm{salience}}\left(\mathrm{pos}\right)---\left(22\right)$>

其中，pos表示所有在绣线stitch_k上的像素点； 

步骤214b：根据计算得到的图像显著性stitchsalience_k，按照stitchsalience_k的大小对针迹序列stitches进行升序排列，得到排序后的针迹序列newstitches，排在前面的即为要先进行绣制的绣线。 

最后的绣制效果如图3所示。 

本发明实现了一种采用遗传算法的计算机辅助乱针绣制作方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。