排样图形匹配中的聚类算法应用的研究.pdfVIP

04’中国企业a动化和信息化建设论坛暨中南六省区a动化学会学术年会大会专辑 排样图形匹配中的聚类算法应用研究 ————————一 宋亚男1，万频1，李学聪1，邓飞其2。叶家玮3 1．广东工业大学自动化学院，广东510090 2N3．华南理工大学自动化科学与工程学院，广东510640 摘要：本文通过对排样问题的需要进行分析，选取了有效的聚类特征；通过对模糊c一均值算法和 减法聚类算法的比较，选取减法聚类实现对排样图形的聚类；给出了针对排样问题的参数选取，文末给 出了实例。 关键词：模糊C均值聚类；减法聚类；排样 这种想法是基于这样的假设：同类型的网形 1前言 将能够靠接更紧密。例如：面积相近的近似规则 排样优化问题普遍存在于钣金、钢结构、船 图形之间的凹凸将能拼合得更为紧密。 舶、服装、皮革和纸制品、玻璃等行业生产过程 2特征提取 中。其总目标是在给定的几何图形上不重叠地放 置更多的满足要求的几何图形(一维、二维)，使 本文采用基于位图的图形，为了讨论方便， 材料利用率最大；具体到不同的行业以及切割、 首先给出以下定义ItI： 排样环境，表现为不同的约束形式，但没有本质 定义1位图的外包矩形矩形的每条边与陔位 的差别。这是一类NP—hard问题，当计算复杂度飞图至少有一个交点，并且位图的任何一点都是该矩 速增加时，我们就不得不在节省时间和节省原材 形的内点或者边界点。 料上取一个平衡点作为最终的选择。 定义2位图的外包矩形集对位图分别用垂直 为了使得同类型图形放在一起进行排样，以 和水平扫描线夹逼的方法求取该位图的外包矩形， 提高排样速度和材料利用率。可先对图形进行聚 取两个方向夹逼距离较大的值作为长度‘，取两 类分析。 个方向夹逼距离较小的值作为宽度Ⅵ记为(，，州)； 专业论文 再将位图旋转度k。，使用上述的方法获得位图的 一步刻画，可以采用多边矩形(边数的矩形进行 外包矩形(f2帕)，重复上述的操作，依次获得位图 包络)或者其他规则图形进行包络，例如：六边 80。／k 6)， 形；近似长短轴反映了图形趋于正方形还是长条 的180／k个外包矩形(厶Ⅵ)(其中，‘2w-l，2—1 这些矩形构成位图的外包矩形集。 形。 E，。；{(t，Ⅵ)I‘2峨，i=l…2180。／k。} (1) (2)这三个特征是强特征目，聚类的结果满足 定义3位图的匹配外包矩形集若 紧致集的要求[31。具有较好的可分性。 V(‘，w)∈‰， ■一∈‰，并且有V(Ij，叫)∈K一， 3聚类算法在排样图形匹配中的应用 3(1，，Ⅵ)s(‘，Ⅵ1。V一即为位图的匹配外包矩形集。 其中，≤表示J，≤j，oFⅥ≤Ⅵ。 通常有两类对数据集进行聚类的方法，即迭 定义4最小外包矩形设外包矩形面积集合为： 代的动态聚类算法和非迭代的分级聚类算法。其 ＆。={‘×Ⅵl(‘，Ⅵ)∈％。}，f=1…2l％。l (2) 中动态聚类是一种普遍采用的方法。下面主要讨 则最小包络矩形面积： 论动态聚类中的模糊C一均值聚类、减法聚类及在