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

南昌航空大学科技学院学士学位论文

图1-1平面内的点集和其Voronoi图 骨架及Voronoi图都基于最短距离约束，Voronoi图的生成是一个由点到区域的扩张过程，骨架的提取是 一个区域到线的细化过程 ，可以以火的蔓延为例进行分析。假如在某一区域M中存在一点集，在t= O时点燃点集中的点，着火点以同样的速度向四周扩散，燃烧前沿相交时熄灭，燃烧区域对 M的分割就是 Voronoi分割。边界点具有特殊性，其燃烧前沿不能够完全相交，因此 Voronoi图边界的多边形是无限向外扩展的。同理假如对某一区域边界线上的所有点，在t= 0时点燃，火的前沿以相同的速度向内部扩散，燃烧前沿相遇时熄灭，熄灭火焰点的集合便是区域的骨架。 骨架实际上是物体内部相对于物体边界的最大内切圆的中心的集合，而内切圆的圆心至少与物体边界上的两个点具有相等的距离。同时，与物体边界点所关联的Voronoi图所生成的靠近物体中心的Voronoi边与 至少两个边界点具有相同的距离。因此，图形边界点集的 Voronoi图能够给出部分的骨架。不完备之处在于Voronoi图计算的是空间内到给定点集距离最小的区域，因而不区分图形内外部分，在遇到有凹点的图形时与精确骨架有差别，可以说物体的骨架点集是Voronoi图的子集。

Voronoi图方法只适合计算简单多面体的骨架，不适用于离散模型，同 时处理内部有空洞的物体也有困难。对于复杂的物体实体，理论上可以先用表面网格模型

3

南昌航空大学科技学院学士学位论文

表达，然后计算 Voronoi图，但是若原始物体表面太光滑，则表面多边形太小，Voronoi图的计算量将十分庞大，因此Voronoi图方法的适用范围目前还比较狭窄。此类方法也便于生成多尺度骨架描述，但是 需要剪枝 的过程，而且规则很复杂。对于边界噪声的影响，此类方法也表现得特别敏感，这一点对于识别系统是非常不利的。 另外一些方法基于Reeb图思想。该类算法首先在模型上定义一个连续函数 ，计算每个模型顶点的函数值，将具有同样函数值的顶点聚合成一个顶点，得到模型的骨架。 一般采用Reeb图进行骨架抽取的思路，都将计算对象放在模型的顶点上，而后根据顶点的函数值计算其所在面片落入的各个函数值区间，进行骨架创建。而黄坤武提出一种针对模型面片进行直接骨架抽取的算法框架，首先定义模型面片之间的距离计算方法，创建模型的对偶图，然后在该对偶图上应用Reeb图的计算思想，在对偶顶点上定义一个连续函数并计算每个顶点的函数值，最终根据计算得到的函数值以及顶点对应的面片之间的邻接关系创建模型的骨架。

1.2.2拓扑细化的方法

拓扑细化方法是一种受到广泛关注的算，这类方法模拟烧草模型的物理过程，由图像的边界开始向内演化，逐步搜索到中轴骨架的位置。基本思想是逐层均匀的剥掉图形的边界点，剩下最里层的不能在剥掉（否则会影响连通性）的部分就得到了图形的骨架。

这类算法的研究首先 开始于二维图像 ，后来又逐渐扩展到三维领域。这一类算 法的关键就是简单点 (Simple point)和端节点 (End point) 的判断。所谓简单点，就是那些被删除后不会改变图像拓扑结构的点。端节点也是一类简单点，但是对它的删除 可能会丢失一些物体末端信息，会造成过皮细化。为了保留物体形状有用的信息， 那些作为端节点的简单点就必须保留不变。这一类方法的过程实际上就是简单点的 判断与删除的过程。这个过程一直重复，直到没有点能够被删除，这样就产生了骨架，但是端节点在三维情况下的定义却不容易确定。根据对简单点的判断的不同方法，又可以分为基于模板的算法和基于边界的算法。 拓扑细化方法的优点就是能够保证所抽取的骨架的连通性，同时，容易平行实现，对于光滑的、规则的物体，是一种不错的细化选择。但是，它也存在着很多的缺点，比如会产生一些小突起，以及无关的枝桠。而且对于三维物体而言，

4

南昌航空大学科技学院学士学位论文

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

依据距离的参照据，提取骨架的距离场可分为两类：到源点的距离场，记为DFS（Distance Field from Source）,一般在模型表面上选取一个源点，然后计算模型表面上或内部的所有点到该源点的距离，得到的距离场即为DFS；到模型边界的距离场，记为DFB（Distance Field from Boundary），对于模型内部的某一点，计算该点到模型边界的最短距离，得到的距离场即为DFB。基于这两种距离场的骨架提取方法 分别称为DFS方法和DFB方法。距离场方法，一般需要先将模型离散为规则数据场的体素表达，再进行骨架提取的工作。

在这些方法中，它们大多使用 Dijkstra算法来构造距离场或者进行骨架节点的搜索。Dijkstra算法事先构造某特定权值来度量图中路径的长度，然后从图的某指

5

南昌航空大学科技学院学士学位论文

定源点出发，依据路径长度的递增次序，来产生到所有其它顶点的全局最短路径。于是，若把模型表面多边形的所有边和顶点看作一个连通图，多边形的边的欧式长度作为路径权值，那么运用 Dijkstra算法就可以在模型表面上建立DFS，若把DFB值看作是高度值，则模型的DFB就是一个高度位图，那么骨架分支就是该位图的“山脊线”。若构造某路径权值，使之随DFB值（高度值）单调递减，那么运用 Dijkstra算法得到的某两点间的最短路径，就是这两点间的“山脊线”，这样就得到了一条骨架分支。提取所有这样的分支，就可得到模型的完整骨架。 Gagvani提出一种基于距离变换的带参数控制的三维骨架提取方法。该方法比较每个点与其邻域点的距离变换值，满足一定局部最大条件的点被选为骨架点，再利用一个细化参数控 制骨架点的密度，并且可以由这些骨架点半自动地抽取出三维物体的中心线。 这种方法的优点是，能够由骨架点及其DT值重建出物体，而且它实现起来相对简单，能够抽取出不规则物体的骨架，使用面较广。另外基于距离变换的方法在骨架点的准确度上有明显的优势，且由此类方法求出的骨架具有完全重建原始图形的能力 …… 此处隐藏：1950字，全部文档内容请下载后查看。喜欢就下载吧 ……