南昌航空大学科技学院学士学位论文
Study on skeleton extraction algorithm realization based on
MATLAB
Student name : Yu Haoran Class: 0982042
Supervisor : Ou Qiaofeng
Abstract：Prevailing in the world of Computer-Aided Design, digital museum, medical
imaging, scientific visualization, virtual reality, computer graphics and gaming environment, Three-dimensional (3D) data become more and more a common feature of nowadays multimedia. The line-like representation is a one-dimensional (ID) abstraction of a three-dimensional (3D) object, consisting of a set of curves embedded in 3D space. This line-like representation of a 3D object is also known as the centerline or the curve-skeleton. As a reduced representation, the curve-skeleton capture the essential shape (topology and geometry) of the underlying 3D object in an easy to understand and very compact form, also increase the efficiency of memory usefulness and compress ratio. In this paper firstly discussed the research status of all kinds of definitions and skeleton extraction
algorithm framework, through analysis and comparison of different categories of skeleton algorithm, advantages and disadvantages of the different categories of skeleton algorithm. The next generation of 3D voxel model, compares the advantage and disadvantage of existing voxelization method, focusing on the use of the minimum bounding box of Euclidean distance measure grid model voxelization algorithm based on improved, the acceleration algorithm and integrated into the 3D model visualization platform skeleton extraction on the Matlab platform, the experiment proved efficiency of the algorithm, to meet the need of task. Finally, systematic analysis of the model skeleton algorithm we need to develop, mainly discusses and implements several representative skeleton extraction algorithm, the respective characteristics of comparative experimental results are given, analysis and improvement suggestions.
Keywords: medial axis curve-skeleton Skeleton algorithm
Signature of Supervisor :
南昌航空大学科技学院学士学位论文
目 录
1 绪论 .................................................. 1
1.1研究背景与意义 .................................................. 1
1.2国内外研究现状 .................................................. 2
1.2.1基于拓扑与几何分析的方法 ................................. 2 1.2.2拓扑细化的方法 ............................................. 4 1.2.3基于距离变换的方法 ........................................ 5 1.2.4 广义势场方法 ............................................. 6 1.2.5各种骨架化算法的比较 ....................................... 7 1.3 论文主要工作与内容安排 ......................................... 8
2 物体骨架提取方法研究 .................................. 9
2.1 骨架提取的基本概念 .............................................. 9
2.1.1物体骨架与物体边界/轮廓的关系 .............................. 9 2.1.2提取物体骨架的基本要求 .................................... 10 2.2 经典的物体骨架提取算法 ......................................... 10
2.2.1细化骨架提取算法 .......................................... 10 2.2.2距离变换骨架提取算法 ...................................... 11 2.2.3 Voronoi图骨架化算法 ...................................... 12 2.2.4偏微分方程骨架化算法 ...................................... 12 2.2.5形态学骨架提取算法 ........................................ 13 2.3当前骨架提取算法面临的重点和难点 ............................... 13 2.4构建物体视觉主骨架 ............................................. 14
2.4.1视觉主部分概念 ............................................ 15 2.4.2 提取视觉主骨架 ........................................... 15 2.5 结论 ........................................................... 17
3 骨架树描述及有关识别算法研究 ......................... 18
3.1骨架树的基本概念 ............................................... 18 3.2骨架树模型的建立 ............................................... 18 3.3 骨架树形状描述及有关识别算法 ................................... 19
3.3.1形状特征描述 .............................................. 19 3.3.2 基于拓扑和形状相似度结合的识别算法 ....................... 20 3.4 结论 ........................................................... 20
4 基于MATLAB的实现步骤及分析 .......................... 21
4.1 MATLAB图像分析方法简介 ........................................ 21 4.2算法实现步骤流程图 ............................................. 21 4.3 算法实现骨架提取 ............................................... 23
4.3.1 形态学骨架化算法实现骨架提取 ............................. 23 4.3.2 二值图像细化算法实现骨架提取 ............................. 24
南昌航空大学科技学院学士学位论文
4.4 图像对比分析 ................................................... 25
5 结论与展望 ........................................... 26 参考文献 ............................................... 27 致 谢 ................................................. 29 附录 ................................................... 30
南昌航空大学科技学院学士学位论文
1 绪论
1.1研究背景与意义
随着扫描技术和计算机图形学的发展以及计算机性能的提高，模型己成为继声音、图像和视频之后的第四种多媒体数据类型。对模型的使用与研究在娱乐、医学、机械工程、计算机仿真和虚拟现实，工业应用等领域得到了认间，日益发达的互联网技术为人们对三维模型的共享和处理提供 了条件，这些都导致对维模型应用需求的增长。但是三维模型的信息量很大，同时三维模型的描述方法多样，如点集合表示法、多边形网格表示法和体素表示法等，这也使得三维模型在许多应用中发生占用存储空间过大、运行计算负载过重 、达不到时计算的情形。所以需要一种\紧凑的 \ 表示方式来尽可能完整，全面地表示描述三维模型的结构特征信息等。其中最常用一种简 化的表示方式就是使用一维曲线 ，一般称为中心线或者线性骨架。利用物体的骨架来捕述对象是一种既能强调物体的结构特征，也能提高内存使用率与数据压缩率的好方法。骨架作为计算机图形学、计算几何学、点集拓扑学和图论等跨学科专业的研究内容，有丰富的理论支撑和很多成熟的数学工具可以利用。自从Blum[1]的开创性研究以来 ，数十年来研究者们从不同的角度研究了骨架的各个侧面，并且将它应用到越来越广泛的领域之中。这些领悟几乎涉及到计算机视觉和图像理解领域的方方面面。 骨架是原始图形的一种压缩表示 ，与原始图形保持了相同 的拓扑结构， 并且存在于图形的对称轴上，能够同时反映图形的拓 扑与形状信息，减少原始 图形的冗余信息，是在二维或三维空间里描述物体基本拓扑的有力抽象化手段。三维模型的骨架是该物体的直观图或中心线的表示。应用中它可以代替原三维模型参与许多运算，从而大大减少计算开销，可广泛用于医学可视 化、模式识别、计算机动画等领域。近年来，随着体可视化技术的发展以及体图形学的出现，使得三维骨架提取成为了一个研究热点。 在过去的二十年里，科研工作者在三维骨架提取领域已经开发了很多的算法，并且新的算法也正在不断出现。2006年美国Rutgers大学的Cornea等人详尽综述了三维线性骨架提取的应用与研究，并在网站上公开了部分算法的源代码供大家使用。可以说这极大方便了研究者，但Cornea提供的源代码读取数据格式不统一，同时缺乏可视化显示，非常不便于重复使用。为避免重复使用，非常有必要充分利用各种已有算法，开发二维、三维骨架提取平台。
1
南昌航空大学科技学院学士学位论文
1.2国内外研究现状
骨架是表示物体的一种很自然的形式，三维模型的骨架可以看成是由物体中所有的最大内接球中心所在位置点构成。三维模型的骨架在计算机视觉、医学图像可视化、特征提取与表示、模型匹配跟踪等诸多领域有着广泛的应用。
骨架算法的研究工作已经开展了三十多年，其中二维图形的骨架算法研究比三维情况下要成熟许多。最初三维物体骨架提取算法使用人 工指定的方法。人工指定算法要求用户一张张地在切片上直接指定中心点，然后再将点连成线。这种方法耗时费力，己很少采用。当前的研究主要可以分为以下四类。第一类是基于拓扑与几何分析的方法，通过构造模型的Voronoi图或Reeb图来得到骨架；第二类是拓扑细化法(Topology Thinning) ，又称为模拟烧草模型算法，此类算法从边界开始，反复迭代地逐层剥离离散后的模型， 直 至剩下一维的骨架；第三类方法是基于距离场的方法 ，它们先生成关于模型的距离场，再提取距离场中的局部极值点，然后连接这些点，并作一些细化调整得到骨架；第四类是广义势场方法，假设模型的边界上聚集了均匀分部的同种电荷电源，采用牛顿静电力学模型建立立场，让种子点逐步移动到达力学平衡点，然后依据种子点的相邻关系连接这些平衡点得到骨架。下面分别详细介绍各类算法的研究情况。 1.2.1基于拓扑与几何分析的方法 基于拓扑与几何分析的方法又主要包括两方面 :Voronoi图和Reed图。 Voronoi图是计算几何领域里的一项重要工具。Voronoi 图的概念是俄国数学家G Voronoi 在 1908年提出 的，是计算几何学上非常著名的工具，被广泛的应用于各个行业。在二维平面M上给定一个包含 n个点的集合S?{Pi?M,1?i?n}，与S关联的Voronoi图为覆盖整个平面 M 的一个凸多边形的集合VD?{(Pi)|Pi?S}， 其中： v(Pi)?{p|d(p,Pi)?d(p,Pj),i?j,1?i?n,1?j?n} （1-1）， v(pi)包含了 M 中所有到点pi的距离小子点集 S内任何其他点距离的空间区域。式（1-1）给出点pi的Voronoi多边形，点集S的Voronoi多边形集合就构成了S的Voronoi图。图1-1给出了平面内的一组点及由这组点集 生成的 Voronoi 图。这个概念也可以扩展到三维空间上，这样的Voronoi图就是Voronoi多面体的集合。
2