南昌航空大学科技学院学士学位论文
图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值重建出物体，而且它实现起来相对简单，能够抽取出不规则物体的骨架，使用面较广。另外基于距离变换的方法在骨架点的准确度上有明显的优势，且由此类方法求出的骨架具有完全重建原始图形的能力，并具备平移、旋转、比例变化的不变性。但是，用这种方法抽取出 的点集并不能保证得到一个连通的骨架。同时这类方法很难保证骨架的连通性，这将影响骨架拓扑特性的表达。此类方法也不保证骨架结果的单像素特性，这点与骨架定于是不符合的。 1.2.4 广义势场方法 广义势场方法假定物体的边缘上聚集了均匀分布的同种电荷，这些电荷在物体内部产生了一个稳定的电场。该方法首先选择物体边界上的凸点作为起始点，然后依照电场的方向移动到场强为0的地方。起始点的移动轨迹构成骨架的一个分支，最后连接所有分支得到骨架。广义势场方法利用了不同于距离变换的矢量场，取得了很好的结果。Ma等人提出过基于可见互斥力的骨架抽取算法，它应用了物理学上的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。Cornea等人对广义势场方法进行了改进，该方法将场强为0的点作为关键点，根据其文献所提出的力跟踪方法连接个个关键点，得到物体的核骨架，然后选择曲率较大的边界点继续生成骨架得到物体的层次骨架。
6
南昌航空大学科技学院学士学位论文
1.2.5各种骨架化算法的比较
在二维情况下，这些方法都能够保证所生成的骨架能很好地反映原模型的几何，拓扑特征。但对于三维模型，基于Voronoi图的方法很难保证骨架是一维的，且计算效率低，其他三类方法一般都能得到一维的线性骨架，对模型的每一个内部离散点，拓扑细化法需要迭代访问多次，所以相比于距离场方法，它效率较差。
拓扑细化类方法最大的优点是能保证优良的连通性能，即骨架结果保持与原始 图形相同的拓扑特征。拓扑特征是识别物体的关键特征，因此保留拓扑特征非常重要。但是细化算法大都需要进行迭代运算， 因此计算量相 当庞大。并且细化法得到的骨架结果位置不精确 。 基于距离变换的方法能够很好的解决细化法骨架位置不准确的问题，同时对运算量的要求也大大降低 ，并且可以通过设计各种参数降低对噪声的敏感度。此类方法的缺点在于不能保证骨架 的连通性和单像素性，其原因也是离散处理造成的 ，离散域内圆的定义和圆的包 含关系很难把握，并且有可能真实的骨架位置位于两离散点正中，于是两点皆被选为骨架点或丢失，破坏了单像素性和连通性。 广义势场方法不仅考虑骨架最近边界点的影响，还考虑了很多其他的边界点，使得该方法对边界噪声不敏感，而且得到的线性骨架具有很好的连通性。但是计算广义势场的计算复杂度较高。 值得注意的是物体通常不能从非常细的线性骨架准确地再生。因此在物体的骨架线性提取时一定要重视，理想的骨架算法应具有如下的性质： 1) 骨架结果保留原始图形的拓扑特征，即骨架的点集必须是连通的，最好 保持单像素宽度，只有这样，才能降低后续处理的复杂性; 2) 骨架带有一定的形状信息，例如骨架点处的距离变换值； 3）骨架应当位于相对物体边界的中心； 4）骨架结果对边界噪声的敏感度低，边界的轻微扰动不会产生骨架的明显 变化； 5）要保存初始物体的结构特征（拓扑结构）与结合性，并且一般要具备物 体的再形成能力。即由骨架可以重建出原始的物体，这就需要骨架化 程是可逆的。
7