多边形域的Delaunay三角化及其应用研究

摘要

Delaunay三角化是计算几何的重要研究内容之一，由其生成的Delaunay三角网格，具有空外接圆、最小角最大等众多特性，是计算几何的重要几何结构之一。此外，Delaunay三角化拥有较完善的理论体系，如今已经在图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等领域得到广泛应用，也是解决骨架计算、可见性计算等计算几何其它问题的有效工具。近年来，也被成功地应用于模式识别过程中的模式匹配，比如指纹细节点匹配，受到人们的密切关注。本论文对多边形域的Delaunay三角化进行了较为深入的研究，并以此为基础研究解决在图形图像、虚拟现实等研究工作中的骨架计算问题，以及在线手写体识别中的特征提取问题。这些问题来源于教研室的“集成化计算机辅助图案设计制版系统”的研发工作以及在微软亚洲研究院实习期间关于“基于离散隐Markov模型的在线手写体识别系统”的研究实现中，有着非常重要的理论意义和实际应用价值。 本论文的贡献主要有： 1、针对任意平面多边形域，采用增量思想和均匀网格，在局部范围内快速生成约束Delaunay三角形。算法不会生成区域外的三角形；对存在折线、离散点以及含“洞”的情况不需要特殊处理。实验结果表明，对于随机生成的简单多边形域三角化速度快，平均计算时间呈近似线性，明显快于其它三角化算法。 2、针对文字、工业图案等带状图像的带状边界多边形，充分利用其近似等宽性优化约束Delaunay三角化(CDT)算法，并以此为基础设计实现了一种有效的带状图像骨架化算法。该CDT算法数据结构简单，易于理解和实现，负载开销小；实验表明，算法明显快于其它三角化算法。基于此的骨架化算法，相比其它骨架化算法，易于实现，且速度也有明显提高。 3、针对在线手写英文字符，充分利用其时序化特性和图形几何拓扑信息，给出了一种沿约束边的CDT算法，并提出一种新型的图形上下文描述器——Delaunay三角形特征描述器，以有效地提取特征。Delaunay三角形特征描述器涵盖了一定程度上的全局特性，实验表明，相比其它传统特征组合，明显改善了识别准确率，并增强了系统的稳定性及鲁棒性。 4、针对在线英文手写体，基于离散隐Markov模型(DHMM)理论构建了一个识别系统。对于每类字符样本，通过迭代的Baum-Welch重估计算法训练生成多个HMM。采用级联HMM(CCHMM)的方法识别单词，同时还提出了基于模型训练层次和识别层次的多种剪枝方法用于单词识别，不仅在识别率上比穷举搜索方法略有提高，而且大大减少了搜索空间，提高了识别速度。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第一章 引言

第二章 平面多边形域的快速约束Delaunay三角化

第三章 带状多边形Delaunay三角化及其骨架化

第四章 基于Delaunay三角化的在线手写字符特征提取

第五章 基于隐Markov模型的在线手写体识别系统

第六章 总结与展望

参考文献

致谢

攻读硕士学位期间撰写的学术论文及获得的科研成果