数字曲线多边形逼近方法及应用研究

摘要

人们常常通过物体的轮廓或区域边界的特征对其进行识别，这些轮廓或区域边界大多以数字曲线的形式表示。原始的轮廓或区域边界曲线通常含有较多的顶点，不便于进一步处理。用多边形来逼近这些曲线，可以在减少顶点数、压缩数据的同时，保留原始曲线的主要特征信息，因此成为目前常用的一种有效解决方法。
　　多年来，国内外许多专家学者对数字曲线多边形逼近问题进行了大量的研究，并提出了多种数字曲线多边形逼近算法。这些算法包含局部优化算法、全局优化算法以及新近发展的智能优化算法，并在许多数字曲线多边形逼近的具体应用中取得了较好的效果，但也还存在以下问题：(1)逼近多边形必须保留原曲线的特征，因此会涉及到多个约束控制条件，当各约束控制条件的数值不在同一数量级上时，就会出现相互掩盖，使得一些约束控制条件起不到相应的约束控制作用，以致相应的特征得不到保持。(2)已有算法还无法满足一些特殊的应用需求。如人工构造模型中规则形状轮廓的特征保持问题、皮料排样过程中多边形面料或样片的向里向外简化等。
　　围绕上述问题，本文主要展开了以下三个方面的研究工作：
　　首先，针对现有算法不能很好解决多个约束控制条件同时起作用的问题，提出一种基于多目标优化的数字曲线多边形逼近算法。该算法采用多目标优化的思想，将多边形逼近中的各约束控制条件分别作为优化目标，并将多边形逼近中间结果多边形各顶点位置转换为二进制矢量序列表示，采用通信编码中常用到的汉明距离和多边形顶点位置均值来实现粒子更新所需要的中间全局最优值和局部最优值的更合理选取。新算法使得多个约束控制条件能同时起到相应的约束控制作用，在真正意义上实现了多目标优化的数字曲线多边形逼近，使得简化前后的多边形形状特征得到了更好的保持。
　　其次，针对人工构造模型中常见的规则形状数字曲线多边形的特征保持问题，提出了一种基于几何矩的规则形状数字曲线多边形逼近算法。并结合数字曲线多边形逼近中常用的约束控制条件，对具有不同特征的规则形状数字曲线的多边形逼近问题展开研究，归纳总结了规则形状数字曲线多边形简化过程中约束控制条件的选用规律。
　　最后，针对排样、下料应用中的数字曲线多边形逼近问题，实现了一种基于原始边界偏移曲线的逼近算法。由于偏移曲线具有原边界轮廓的基本特性，本文在对面料或样片进行排样之前，先求出其原始边界曲线的偏移曲线，在距离和与偏移距离的共同约束下，对偏移曲线进行多边形逼近，来实现面料或样片的向里或向外简化，较好地满足了排样算法中对边界曲线的简化要求。

目录

封面

声明

中文摘要

英文摘要

目录

引言

1 绪论

1.1 课题的研究背景及意义

1.2 数字曲线多边形逼近概述

1.3 国内外研究现状

1.4 课题研究架构及本文组织结构

2 相关算法及理论基础

2.1 PSO算法

2.2 多目标优化算法

2.3 本章小结

3 面向数字曲线多边形逼近的多目标PSO算法

3.1 算法思想来源

3.2 面向数字曲线多边形逼近的多目标PSO算法

3.3 实验验证及分析

3.4 本章小结

4 规则形状数字曲线多边形逼近

4.1 规则形状数字曲线概念

4.2 基于几何矩的规则形状数字曲线多边形逼近

4.3 约束控制条件的选用规律

4.4 本章小结

5 排样问题中的数字曲线多边形逼近

5.1 排样问题中对多边形的简化要求

5.2 偏移曲线

5.3 基于偏移曲线的数字曲线多边形逼近

5.4 实验对比及分析

5.5本章小结

6 全文总结与研究展望

6.1 论文工作总结

6.2 研究展望

参考文献

致谢

附录：攻读硕士学位期间发表的部分学术论著