基于MATLAB的骨架提取算法的研究实现(8)

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多面体的集合。