西夏文字骨架抽取方法研究毕业论文

《西夏文字骨架抽取方法研究毕业论文》由会员分享，可在线阅读，更多相关《西夏文字骨架抽取方法研究毕业论文（30页珍藏版）》请在金锄头文库上搜索。

1、 西夏文字骨架抽取方法研究毕业论文目 录1 绪论11.1研究背景与意义11.2国外研究现状21.2.1基于拓扑与几何分析的方法21.2.2拓扑细化的方法41.2.3基于距离变换的方法51.2.4各种骨架化算法的比较61.3 论文主要工作与容安排72 物体骨架提取方法研究82.1 骨架提取的基本概念82.1.1物体骨架与物体边界/轮廓的关系82.1.2提取物体骨架的基本要求92.2 经典的物体骨架提取算法92.2.1细化骨架提取算法92.2.2距离变换骨架提取算法102.2.3 Voronoi图骨架化算法112.2.4偏微分方程骨架化算法112.2.5形态学骨架提取算法122.3当前骨架提取算法

2、面临的重点和难点122.4构建物体视觉主骨架132.4.1视觉主部分概念132.4.2 提取视觉主骨架142.5 结论153 骨架树描述及有关识别算法研究163.1骨架树的基本概念163.2骨架树模型的建立173.3 骨架树形状描述及有关识别算法173.3.1形状特征描述183.3.2 基于拓扑和形状相似度结合的识别算法183.4 结论184 基于MATLAB的实现步骤及分析194.1 MATLAB图像分析方法简介194.2算法实现步骤流程图194.3 算法实现西夏文字骨架提取204.3.1 形态学骨架化算法实现骨架提取204.3.2 二值图像细化算法实现骨架提取214.4 图像对比分析225

3、 结论与展望22参考文献24致 谢25 .专业.专注. 1绪论 1.1 研究背景与意义 西夏文字自明代中叶以后,再无人使用,历经明、清两代五百余年间,世人不复知历史上曾有过这种精美奇特的文字.到19世纪初,才由中国学者发现和识别出西夏文字,揭示了它在历史上的存在.而对西夏文字的研究可以让我们更好的,更深入的研究西夏学.随着扫描技术和计算机图形学的发展以及计算机性能的提高,模型己成为继声音、图像和视频之后的第四种多媒体数据类型.对模型的使用与研究在娱乐、医学、机械工程、计算机仿真和虚拟现实,工业应用等领域得到了认间,日益发达的互联网技术为人们对三维模型的共享和处理提供 了条件,这些都导致对维模型

4、应用需求的增长.但是三维模型的信息量很大,同时三维模型的描述方法多样,如点集合表示法、多边形网格表示法和体素表示法等,这也使得三维模型在许多应用中发生占用存储空间过大、运行计算负载过重 、达不到时计算的情形.所以需要一种紧凑的 表示方式来尽可能完整,全面地表示描述三维模型的结构特征信息等.其中最常用一种简 化的表示方式就是使用一维曲线 ,一般称为中心线或者线性骨架.利用物体的骨架来捕述对象是一种既能强调物体的结构特征,也能提高存使用率与数据压缩率的好方法.骨架作为计算机图形学、计算几何学、点集拓扑学和图论等跨学科专业的研究容,有丰富的理论支撑和很多成熟的数学工具可以利用.自从Blum的开创性研

5、究以来 ,数十年来研究者们从不同的角度研究了骨架的各个侧面,并且将它应用到越来越广泛的领域之中.这些领悟几乎涉及到计算机视觉和图像理解领域的方方面面1.骨架是原始图形的一种压缩表示 ,与原始图形保持了相同 的拓扑结构, 并且存在于图形的对称轴上,能够同时反映图形的拓 扑与形状信息,减少原始 图形的冗余信息,是在二维或三维空间里描述物体基本拓扑的有力抽象化手段.三维模型的骨架是该物体的直观图或中心线的表示.应用中它可以代替原三维模型参与许多运算,从而大大减少计算开销,可广泛用于医学可视 化、模式识别、计算机动画等领域.近年来,随着体可视化技术的发展以及体图形学的出现,使得三维骨架提取成为了一个研

6、究热点.在过去的二十年里,科研工作者在三维骨架提取领域已经开发了很多的算法,并且新的算法也正在不断出现.2006年美国Rutgers大学的Cornea等人详尽综述了三维线性骨架提取的应用与研究,并在上公开了部分算法的源代码供大家使用.可以说这极大方便了研究者,但Cornea提供的源代码读取数据格式不统一,同时缺乏可视化显示,非常不便于重复使用.为避免重复使用,非常有必要充分利用各种已有算法,开发二维、三维骨架提取平台.1.2 国外研究现状 骨架是表示物体的一种很自然的形式,三维模型的骨架可以看成是由物体中所有的最大接球中心所在位置点构成.三维模型的骨架在计算机视觉、医学图像可视化、特征提取与表

7、示、模型匹配跟踪等诸多领域有着广泛的应用.骨架算法的研究工作已经开展了三十多年,其中二维图形的骨架算法研究比三维情况下要成熟许多.最初三维物体骨架提取算法使用人 工指定的方法.人工指定算法要求用户一地在切片上直接指定中心点,然后再将点连成线.这种方法耗时费力,己很少采用.当前的研究主要可以分为以下四类.第一类是基于拓扑与几何分析的方法,通过构造模型的Voronoi图或Reeb图来得到骨架；第二类是拓扑细化法(Topology Thinning) ,又称为模拟烧草模型算法,此类算法从边界开始,反复迭代地逐层剥离离散后的模型, 直 至剩下一维的骨架2；第三类方法是基于距离场的方法 ,它们先生成关于

8、模型的距离场,再提取距离场中的局部极值点,然后连接这些点,并作一些细化调整得到骨架；第四类是广义势场方法,假设模型的边界上聚集了均匀分部的同种电荷电源,采用牛顿静电力学模型建立立场,让种子点逐步移动到达力学平衡点,然后依据种子点的相邻关系连接这些平衡点得到骨架.下面分别详细介绍各类算法的研究情况. 1.2.1 基于拓扑与几何分析的方法基于拓扑与几何分析的方法又主要包括两方面 :Voronoi图和Reed图.Voronoi图是计算几何领域里的一项重要工具.Voronoi 图的概念是俄国数学家G Voronoi 在 1908年提出 的,是计算几何学上非常著名的工具,被广泛的应用于各个行业.在二维平

9、面M上给定一个包含 n个点的集合,与S关联的Voronoi图为覆盖整个平面+的一个凸多边形的集合, 其中： （1.1）包含了 M 中所有到点的距离小子点集 S任何其他点距离的空间区域.式（1.1）给出点的Voronoi多边形,点集S的Voronoi多边形集合就构成了S的Voronoi图.图1.1给出了平面的一组点及由这组点集 生成的 Voronoi图.这个概念也可以扩展到三维空间上,这样的Voronoi图就是Voronoi多面体的集合. 图1.1平面的点集和其Voronoi图 骨架及Voronoi图都基于最短距离约束,Voronoi图的生成是一个由点到区域的扩过程,骨架的提取是 一个区域到线的

10、细化过程 ,可以以火的蔓延为例进行分析.假如在某一区域M中存在一点集,在t= 0时点 燃点集中的点,着火点以同样的速度向四周扩散,燃烧前沿相交时熄灭,燃烧区域对 M的分割就是Voronoi分割.边界点具有特殊性,其燃烧前沿不能够完全相交,因此Voronoi图边界的多边形是无限向外扩展的.同理假如对某一区域边界线上的所有点,在t= 0时点燃,火的前沿以相同的速度向部扩散,燃烧前沿相遇时熄灭,熄灭火焰点的集合便是区域的骨架.骨架实际上是物体部相对于物体边界的最大切圆的中心的集合,而切圆的圆心至少与物体边界上的两个点具有相等的距离.同时,与物体边界点所关联的Voronoi图所生成的靠近物体中心的Vo

11、ronoi边与 至少两个边界点具有相同的距离.因此,图形边界点集的 Voronoi图能够给出部分的骨架.不完备之处在于Voronoi图计算的是空间到给定点集距离最小的区域,因而不区分图形外部分,在遇到有凹点的图形时与精确骨架有差别,可以说物体的骨架点集是Voronoi图的子集.Voronoi图方法只适合计算简单多面体的骨架,不适用于离散模型,同 时处理部有空洞的物体也有困难.对于复杂的物体实体,理论上可以先用表面网格模型表达,然后计算 Voronoi图,但是若原始物体表面太光滑,则表面多边形太小,Voronoi图的计算量将十分庞大,因此Voronoi图方法的适用围目前还比较狭窄.此类方法也便于

12、生成多尺度骨架描述,但是 需要剪枝 的过程,而且规则很复杂.对于边界噪声的影响,此类方法也表现得特别敏感,这一点对于识别系统是非常不利的.另外一些方法基于Reeb图思想.该类算法首先在模型上定义一个连续函数 ,计算每个模型顶点的函数值,将具有同样函数值的顶点聚合成一个顶点,得到模型的骨架.一般采用Reeb图进行骨架抽取的思路,都将计算对象放在模型的顶点上,而后根据顶点的函数值计算其所在面片落入的各个函数值区间,进行骨架创建.而黄坤武提出一种针对模型面片进行直接骨架抽取的算法框架,首先定义模型面片之间的距离计算方法,创建模型的对偶图,然后在该对偶图上应用Reeb图的计算思想,在对偶顶点上定义一个

13、连续函数并计算每个顶点的函数值,最终根据计算得到的函数值以及顶点对应的面片之间的邻接关系创建模型的骨架. 1.2.2 拓扑细化的方法拓扑细化方法是一种受到广泛关注的算,这类方法模拟烧草模型的物理过程,由图像的边界开始向演化,逐步搜索到中轴骨架的位置.基本思想是逐层均匀的剥掉图形的边界点,剩下最里层的不能在剥掉（否则会影响连通性）的部分就得到了图形的骨架.这类算法的研究首先 开始于二维图像 ,后来又逐渐扩展到三维领域.这一类算 法的关键就是简单点 (Simple point)和端节点 (End point) 的判断.所谓简单点,就是那些被删除后不会改变图像拓扑结构的点.端节点也是一类简单点,但是

14、对它的删除 可能会丢失一些物体末端信息,会造成过皮细化.为了保留物体形状有用的信息, 那些作为端节点的简单点就必须保留不变.这一类方法的过程实际上就是简单点的 判断与删除的过程.这个过程一直重复,直到没有点能够被删除,这样就产生了骨架,但是端节点在三维情况下的定义却不容易确定.根据对简单点的判断的不同方法,又可以分为基于模板的算法和基于边界的算法.拓扑细化方法的优点就是能够保证所抽取的骨架的连通性,同时,容易平行实现,对于光滑的、规则的物体,是一种不错的细化选择.但是,它也存在着很多的缺点,比如会产生一些小突起,以及无关的枝桠.而且对于三维物体而言,细化的过程比较复杂,从而需要给出大量的删除条

15、件或者特殊的规则,以避免在细化过程中造成不连通的现象.而且,细化法只是考虑局部连通关系,无法对图形特征进行全局的把握,使它对噪声特别敏感,含有大量噪声的边界常常会导致许多点被误认为端节点. 1.2.3 基于距离变换的方法基于距离变换的方法是利用物体的连通性,对局部领域进行距离变换赋值,从而抽取出物体的骨架点.物体的每一点的DT（Distance Transform）值被定义为这个点到边界点的最小距离.由于骨架点相对于物体的边界而言应当处于中心的位置,而从理论上讲 ,最接近于物体中心的点应该具有最大的 DT 值.因此,DT值就能为骨架点的确定提供有用的信息.距离度量（Distance Metric）是衡量图像中两点间距离的方法,目前,有很多种距离规则可以用于计算距离变换值.例如两点 间的欧式距离就可以提供足够的信息来判断该点是否位于中心.但是在实际计算中,两点间的欧式距离为：其中,和分别为两点的笛卡尔坐标,其计算代价是非常高的,如此精确的距离计算也是不必要的,在一些文献中,使用Manbattan距离或者Cbess.board距离来加快计算.根据体图形学的理论,在三维空间中,物体是以离散网格的形式采样的.因此可以用加权距离规则来近似欧式