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

图1-1平面内的点集和其Voronoi图

骨架及Voronoi图都基于最短距离约束，Voronoi图的生成是一个由点到区域的扩张过程，骨架的提取是 一个区域到线的细化过程 ，可以以火的蔓延为例进行分析。假如在某一区域M中存在一点集，在t= O时点燃点集中的点，着火点以同样的速度向四周扩散，燃烧前沿相交时熄灭，燃烧区域对 M的分割就是 Voronoi分割。边界点具有特殊性，其燃烧前沿不能够完全相交，因此 Voronoi图边界的多边形是无限向外扩展的。同理假如对某一区域边界线上的所有点，在t= 0时点燃，火的前沿以相同的速度向内部扩散，燃烧前沿相遇时熄灭，熄灭火焰点的集合便是区域的骨架。

骨架实际上是物体内部相对于物体边界的最大内切圆的中心的集合，而内切圆的圆心至少与物体边界上的两个点具有相等的距离。同时，与物体边界点所关联的Voronoi图所生成的靠近物体中心的Voronoi边与 至少两个边界点具有相同的距离。因此，图形边界点集的 Voronoi图能够给出部分的骨架。不完备之处在于Voronoi图计算的是空间内到给定点集距离最小的区域，因而不区分图形内外部分，在遇到有凹点的图形时与精确骨架有差别，可以说物体的骨架点集是Voronoi图的子集。

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