1、电脑绣花走针自动生成的算法设计和实现摘 要绣花问题是连续型的填充，在不同区域的缝制过程中，缝针不能提针，因此不能用一般的离散型区域填充方法处理。本文解决了绣花缝针轨迹的两个问题：缝制区域节点的划分和点的遍历问题。本文运用几何计算和图论理论提出了一个绣花缝针轨迹自动生成算法先对轮廓走向进行定义通过轮廓铅垂方向的局部极值点的分割线将图案从上向下进行分割采用交点的特征值比较彻底的解决了分割时的重点问题将图案准确的划分成缝针能一次完成的若干个节点根据每个节点与其上或下分割线的一一对应关系收集到所有节点的轮廓信息在区域划分的基础上根据节点的邻接关系建立节点的邻接图一个无向连通图根据绣花问题的需要在无向连
2、通图中寻找指定起点和终点之间的最长路径这是一个 NP 问题在实际应用中往往以近似最长路来代替最长路现存的算法都针对图中任意两点之间的近似最长路本文利用一条最长路中是不可以被再被插入的这个事实通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路这样的一条路往往非常接近指定的起点与终点之间的最长路。关键词：绣花，无向连通图，最长路，深度优先生成树AbstractIn the process of embroidering, needle cannot hang up for changing to a differen
3、t area. Therefore, Embroider problem could be abstract as a continuous area-filling work. Considering disperse area-filling methods cannot process this problem well, based on geometry computing and graphics theory, we proposed an algorithm of finding path of embroidering needle in this paper.First,
4、we defined the outline orientations, and used part extremum point of outline gravitational orientation to build some divide lines so as to divide the picture. And we solve the overlap point problem by nodical eigenvalue method more perfectly. Therefore, the picture is divided into some nodes which c
5、an be finished by one drawing. Then, based on connections of these nodes, adjacency graph of nodes were built, it is a undirected connected graph. Based on the request of the embroider problem, we need to find a longest path in this undirected connected graph. It is a NP-hard problem that to find th
6、e longest path in undirected connected graph, so people intend to find some approximation algorithms in practice, but all the algorithms existed is for a approximate longest path between two random vertexes in the graph. Based on that a longest path cannot be inserted into a new vertex, we can inser
7、t all the nodes possible into the path between the certain two vertexes in the DFSTraverseTree of the graph to get a path that cant be inserted into again in a polynomial-time, usually this path will be a very good approximate longest path between two certain vertexes.Keywords Embroider, Undirected
8、connected graph, the longest path, DFSTraverseTree概述绣花1,2是一门非常古老的行业,也是我国璀璨的民族手工艺中一朵不衰的奇葩，多头机，顾名思义就是一台机有许多个机头,每个机器头独立进行刺绣操作,目前最多的达 28 头 1 而每个头又有很多支针( 俗称几种颜色)，最多达 12 针 1 电脑多头绣花的生产全部采用自动化作业,实现自动换针(换不同颜色的绣线) 、自动切线、自动移图等作业,基本摆脱了手工操作,它的动作完全由电子系统操作而绣花机绣什么图案。11 电脑绣花系统简介早在西周晚期即已出现的我国刺绣工艺，延绵历时数千年，绣艺精妙针法繁多，它与织
9、锦并驾齐驱地获得“ 锦绣文彩” 的称号。如今，中国刺绣遍及全国各地每一地区产品，又各具地方特色，成为出口大宗，颇受国外用户欢迎。历来刺绣是由手工一针一线绣出，但近来机绣技艺改进提高很快，制作一般日用绣品又快又好，这对繁荣刺绣工艺，满足人民生活需要，作出了一定贡献。电脑绣花起源于德国。又叫电子绣花。二战后，德国的 ZANGS 公司和 PFAFF公司相继将电子控制技术与缝纫技术和绣花技术相结合，在单台缝纫机可以绣花的基础上，将若干台缝纫机连接起来，运用电子技术集中控制，使绣花制品这种传统的手工艺术可以自动生产、批量生产。日本在六十年代也开始研制电子绣花机，在技术上很多抄袭德国制品，便很快发展起来。
10、特别是进入七十年代后，随着单片机的问世，终于跃进电脑绣花时代。电脑刺绣系统主要由两大模块组成:一部分是刺绣的工艺实现部分，即电脑绣花机及其控制系统:另一部分就是电脑绣花花版编辑CAD 系统。本文主要论述电脑绣花 CAD 系统相关的问题，作为电脑绣花机的辅助系统，它负责提供电脑绣花机控制系统所需要的花版信息。随着刺绣机的普及和人们对刺绣产品要求的提高，电脑绣花花版 CAD 系统的地位也口益突出。毕竟电脑绣花机只能完成一些机械动作，它不具备创造性功能，所有创造性的工作都是在花版编辑 CAD 系统中完成的。刺绣产品最终能否为广大用户所喜欢和接受在很大程度上取决于设计人员设计出来的花样是否具有独创性、
11、新颖性和时效性。一个好的打版软件能够让设计人员的意图顺利完整的体现出来，而一个不好的打版软件会限制设计人员的发挥，因此一个能如实、快速、准确地反映出设计者的构思，并给设计者提空一个良好的修改操作环境，一个对设计者非常友好的绣花软件对输出信息有很大的作用，进一步也会提高刺绣产品的最终质量。目前在国内外时常上有许多厂家都在进行这方面的研究工作，比较著名的有香港京华公司、天虹公司、意大利 PROWIN 公司、南京大学的天木、日本的田岛等，它们的产品一般都具有较好的兼容性，能与世界上许多著名的多头绣花机厂商的花版格式相匹配。12 电脑刺绣系统的发展趋势本文只论述电脑绣花花版 CAD 系统，因此只对其发
12、展趋势做简要介绍：1-、实现图像智能化自动编针、针法更加多样化目前的花版 CAD 系统普遍采用的方法是先用投影仪将花稿放大到合适尺寸，然后用数字化仪人工输入。这种方法效率很低，而且精度难以保证。因此通过扫描仪输入数字图像，通过图像处理识别各个图像区域，自动选择针法对每个区域编针是花稿输入的发展趋势。2、实现汉字和英文字的自动编针在一般的刺绣 CAD 系统中，汉字的编针都是作为普通的花稿处理，而汉字作为普通花纹输入效率很低。通过 WINDOWS 系统中自带的矢量字库来输入，其中包含字体的特征点，取得特征点后选用针法，自动编针汉字。3、刺绣花稿的模拟输出在以前的系统中，设计花稿的效果如何往往要通过
13、刺绣机绣出样品后才可以加以判断，这种方法费时费料。而如果能在显示器上或者通过打印机动态模拟刺绣物的实际效果，这样可以使设计和生产完全独立的分开操作，设计者可以根据模拟效果修改设计，大大提高了效率。4、图库管理和通信功能的扩展由于系统中可能会存放大量的花稿，系统应该提供方便的花稿管理方式，便于方便的查找所要的花稿。同时随着计算机网络的发展，要求绣花 CAD 系统应该具有能在网络上传送数据的功能，这样一方面可以避免许多重复劳动:另一方面也使得产品的设计周期大大缩短;甚至可以进行异地协同设计。这也是 CAD 系统发展的新趋势。13 绣花轮廓简介在绣花花稿中包含两种轮廓线，形轮廓和面形轮廓。线形轮廓就
14、是所有的刺绣操作都在一条线上完成，这条线可以是直线，也可以是曲线，如图 1-1 所示。图 1-1这是一条曲线轮廓，刺绣的所有的针点都会落在这条曲线上，这种轮廓我们称之为线形轮廓。面形轮廓就是刺绣操作在一个区域内完成，而面形轮廓又分成两种，一种叫对边轮廓，另一种叫复合轮廓。对边轮廓就是整个轮廓由两条曲线或者直线来确定，然后将两条曲线的起点和终点分别连接起来，构成一个闭合的区域，这样的一个轮廓叫做对边轮廓，如图 1-2 所示，整个轮廓由上下两条白线所确定，在左右两端分别将两条对边的起点和终点连接起来，构成一个闭合区域，然后选择适当的针法对闭合区域内进行绣花，如绿线所示。面形轮廓的另外一种叫做复合轮
15、廓，复合轮廓是由一个大的多边形和其内部的一个或多个多边形构成的轮廓，复合轮廓的刺绣区域是外部大多边形所包含的区域减去内部多边形的区域。图 1-2绣花缝针轨迹自动生成算法的设计设己提供一个图案(图 2-1)，是单色或彩色的，是简单的标签( 如西装上的标记) 或是复杂的图案(如一幅刺绣) ，希望提供缝针的走向轨迹.其基本要求是：图 2-1 图案的例子(1)图案上同一色彩的( 不同)区域缝制时必须一次完成，即在同一色彩的缝制过程中，缝针只能下一次针，上一次针，中间不能提针。（2）在跨越不同区域时缝针的过渡线不能穿越己缝制的图案区。很明显，这不能用区域填充力一法处理1，区域填充是离散型的填充，绣花问题
16、是连续型的填充，在不同区域的缝制过程中，缝针不能提针。例如图 2-1 中，头像的背景力一格和皮肤区域均须一次完成.也不是图的着色问题。南京大学计算机科学与技术系对智能刺绣 CAD 系统进行了长时间的研究，能对图像识别获得适合编针的轮廓图形因，文献中采用识别轮廓上的拐点，将轮廓按从上到下，自左至右的原则分为若十个区域，再对区域依次采用包梗自动编针，并指出分割区域是算法的核心，实现起来相当繁琐，因而文中未给出算法。本文运用几何计算和图论理论解决图案的区域分割问题并自动提供缝针的走向轨迹。2 1 问题抽象绣花问题可抽象成如下的数学问题：设给定一个由多边形构成的多连通域，即给定 N 个边界，其中一个外边界，一个或多个内边界，每个边界均由任意形状、封闭不交叉的折线构造.为叙述方便，采用了如图 2-2(a)的粗线所示带有 6 个内孔的简单图案。2-2(a)用轮廓表示图形的边界为了填充整治个区域，要设法将填充区分成若十个区域。划分的力一法是:通过边界铅垂力一向的局部极点（ Ymax,和 Ymin 点) 作水平线，得到与边界的交点，由此将图案区域从上向下划分成若干单连通区( 图 2-2(a)被划分成 19 个单连通区，以下简称“节点(node)”) 。
