基于三角剖分的带状图像细化算法的研究-计算机软件与理论专业论文.docxVIP

原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中己经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名-．扭兰翌 日期：弛!至：[：j二 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 (必威体育官网网址论文在解密后应遵守此规定) 论文作者签名：婢导师签名： 峥期：一 山东大学硕士学位论文基于三角剖分的带状图像细化算法的研究 山东大学硕士学位论文 基于三角剖分的带状图像细化算法的研究 硕士研究生：杨义军 指导教师：孟祥旭教授 摘要 在自动文字识别、指纹识别、工程图识别和自动线路板检测等识别系统中， 采用细化方法计算图像的骨架是一个十分重要的预处理步骤。已存在细化算法大 致可归纳为迭代和非迭代算法两种类型。迭代算法主要是根据骨架的一些特性来 制定限制条件，通过迭代由外到里逐步去除边缘点来计算图像骨架。但其存在速 度慢、对图像分辨率敏感等缺点。在非迭代算法中，骨架一般被看作图像内最大 圆盘的圆心集合。获取骨架的最常用技术是先利用图像距离的变化来求得可能组 成骨架的像素，然后根据骨架的特性来选择其中的子集。以往的非迭代方法多把 多边形分解成一些三角形和四边形，或者引入一些距离的变化，概念复杂，时间 复杂度高，实现起来困难。1998年，Melhi把三角剖分的思想引入到了细化方法 中，算法概念单一，处理简单。本文在Melhi细化方法的基础上，提出了两种新 的非迭代细化算法——基于Delaunay三角剖分的细化方法和基于快速三角剖分 的细化方法。 两种算法都是首先对带状图像进行边界检测获取带状图像的近似多边形边 界；对获得的多边形边界进行平滑和逆向编号；对求得的多边形边界根据带状图 像的宽度进行分割。对分割后的多边形边界我们分别进行如下处理： (1)基于Delaunay三角剖分的细化方法。算法首先对多边形边界顶点集进行 Delaunay三角剖分生成Delaunay三角形，按三角形和多边形边界的位置关系把 三角形分成三种类型——外部三角形，相交三角形和内部三角形。然后把相交三 角形分割成外部三角形和内部三角形；接着根据三角形面积的正负——外部三角 形面积为负，内部三角形面积为正，去掉所有外部三角形：根据每个三角形的类 型分别进行细化；连接生成整幅图像的骨架。通过实验结果与理论分析，可以看 出算法在时间复杂性和骨架质量上都要优于Melhi方法。由于算法中进行 山东大学硬士学位论文Delaunay三角剖分时产生了相交三角形，需进行全局处理。为了把相交三角形调 山东大学硬士学位论文 Delaunay三角剖分时产生了相交三角形，需进行全局处理。为了把相交三角形调 整局部化，进一步加快算法速度，我们提出了一种基于快速三角剖分的细化方法。 (2)基于快速三角剖分的细化方法。算法首先对求得的多边形边界求包围盒； 然后根据当前点和前一个点所在的三角形是否相邻判断是否在当前点和前一个 点之间加点——如果加入了点，则置最靠近前一个点的新加点为当前点，并根据 当前点是位于边上还是内部。分别将所在三角形分割成两个三角形或三个三角 形；接着根据最小角最大原则对新生成的三角形和相邻三角形进行相应的调整； 最后去掉外部三角形，并对内部三角形进行细化连接生成整幅图像的骨架。算法 通过把相交三角形的调整局部化加快了算法速度，同时对具有内圈的情况不用特 殊处理。所以本算法较前一种算法在算法时间复杂性和性能上有较大改进。 以上算法在文字识别，指纹识别、工程图识别以及工业图案设计中的带状图 像处理等方面有很大的意义。 关键词：细化、骨架、三角剖分、Delaunay三角剖分 山东大学硕士学位论文A 山东大学硕士学位论文 A Study Of Band‘‘Image Thinning Methods Based on Tr ianguIation Graduate Student：Yang,Yinjun Advisor：Prof．Meng Xiangxu ABSTRACT Thinning has played an important preprocess in a broad—range of recognition systems such as automatic tex