一种散点云的自适应切片算法.docxVIP

一种散点云的自适应切片算法 目前，测量装置能够高效、高精度地收集模型的外观数据，但收集的数据没有明显的拓扑关系，并且很大。采用切片技术可在减少点云数据的同时拟合轮廓线,准确表达模型型面特征。 国内外学者对点云切片技术已进行了一定的研究,文献计算各层数据点到相应切片的平均距离,若该距离大于阈值,则在两层切片的中间位置增加一层切片,该方法实现简单,但没有充分考虑点云的特征分布状况,自适应性差。文献将切片邻域数据点向初始切片投影,对投影点进行精简并构造轮廓线,计算投影点到轮廓线的最大距离,依据该距离与阈值的大小关系确定切片位置,该方法需迭代估算切片位置,算法运行效率低。文献估算点云密度,依据密度值计算各层切片的位置,通过邻域数据点配对连线并与切片求交获取切片数据,最后采用Christofids算法对切片数据点进行排序。该方法随机取几个数据点估算点云密度,准确性差,直接影响点云的切片精度,且采用Christofids算法对切片数据点排序只能得到一个近似解,不能保证排序结果的最优性。 作者提出一种散乱点云自适应切片算法,该算法改进R*-tree建立点云动态空间索引结构,深度优先遍历该结构,查询与切片相交的叶结点集合,以该集合中各结点包含的数据点作为切片邻域数据。依据邻域数据与切片的位置关系将其分为正负两个区域,通过正负区域配对点连线与切片求交获取切片数据,并采用最小生成树算法对该数据排序,得到有序的切片数据点,实现散乱点云的自适应切片,实例证明该算法适用于各种复杂型面散乱点云,切片数据获取精度高,算法运行速度快。 1 动态域理论结构的构建 通过改进R*-tree建立散乱点云动态空间索引结构,实现散乱点云的动态存取及切片数据点的快速查询。 1.1 r#-to着力点失效 文献引入R*-tree建立点云空间索引结构,其结点插入算法基于结点MBR(Minimum Bounding Rectangle)增量,应用于散乱点云的空间聚类分簇时,若局部点云平行于坐标平面分布,结点MBR将由3维退化为2维,导致R*-tree结点插入失效,破坏了R*-tree结点的聚合性。为解决该问题,将数据点及叶结点MBR统一表示为4维点对象(x,y,z,r),其中x,y,z为MBR中心坐标,r为MBR的外接球半径值。如图1所示,象素点为散乱数据点,实线框为R*-tree的结点MBR,短线图形为MBR外接球,球心坐标为4维点的前3维坐标,外接球半径为第4维坐标值。 1.2 r#-to分团算法 采用k-means算法实现散乱点云的空间聚类分簇。在选取初始分簇中心时,为减少k-means迭代次数,将相距最远的一对结点的MBR中心作为初始分簇中心。 确定初始分簇中心后,将数据点添加到中心距其最近的分簇中。为使结点MBR均匀,根据R*-tree定义,当分裂所得结点的子结点数k小于R*-tree最小子结点数m时,则将另一簇中距离当前簇较近的(m-k)个结点插入到当前簇中,并调整分簇结果。 采用k-means算法对R*-tree叶结点进行聚类分簇时,需要迭代定位最终的分簇中心。对于同簇结点中的N个叶结点,其四维标准化坐标为pi(xi,yi,zi,ri),i=1,…,N,分簇中心坐标(x-,y-,z-,r-)可由公式(1)计算: 各叶结点至聚类分簇中心的距离,可由公式(2)计算: 该索引结构由3种结点组成,最上层为根结点,最底层为叶结点,其余为内部结点,内部结点可以由多层结点构成。除根结点外,每个结点的子结点数n满足m≤n≤M,其中m、M分别为结点的最小、最大子结点数,通常取8和20。基于4维点表示的散乱点云动态空间索引结构如图2所示。 2 邻域划分及配对 基于散乱点云动态空间索引结构,采用深度优先遍历方式获取与切片相交的叶结点,依据叶结点与切片的位置关系确定当前切片的邻域数据及下层切片的位置,对邻域数据进行区域划分并配对,将配对点所在直线与切片求交,获取切片数据。 2.1 叶片位置计算 设切片平行于XOY平面分布,法矢n指向Z轴正方向,点云在Z轴上的极值为zmin与zmax,采用公式(3)计算点云初始切片位置: 其余各层切片的位置可由公式(4)计算: 令与第i层切片相交的叶结点集合为L,εj为L中各叶结点的顶点距切片的距离,由式(5)计算,n为L中位于切片正侧(即εj0)的叶结点顶点数。 2.2 切片邻域数据 令叶结点的顶点为vi(1≤i≤8),q为切片上任意点,采用式(5)判断叶结点与切片的位置关系。 若εi0,表示叶结点位于切片负侧;εi0表示叶结点位于切片正侧。如图3(a)所示,若叶结点8个顶点的εi值均为正(或负),则表示叶结点与切片相离;如图3(b)所示,若εi的值不同时为正(或负),表示叶结点与切片相交。 基于以上判断法则,获取与切片相交的叶结点,将其包含的数据点作为