基于区域分割的点云骨架提取算法
晁莹;耿国华;张雨禾;张靖
【摘 要】In order to solve the problem that the L1 median skeleton extraction method involves many iterations and the skeleton easily cross the region of the tight adjacent region,an algorithm for extracting skeleton after gmentation is propod.According to the connectivity of the region of point cloud and the local correlation characteristics,the point cloud can be gmented into different regions using the Markov Random Field(MRF) model.Different initial contraction neighborhood scales are adaptively calculated in terms of region size and number of points in the same labeled region.The skeleton branches of each region are extracted by L1 median iteration.The skeleton connection is determined by Principal Component Analysis(PCA) and connection angle.Then the skeleton branch is connected to a complete point cloud skeleton according to the connection mode.Experimental results show that the algorithm can adaptively extract the skeleton of the points cloud and reduce the number of iterations to contract points cloud.It not only can
polyethylene
英语角的英文keep the original topological structure of the model,but also has a good effect on the model with uneven region tightness.%针对L1中值骨架提取方法存在迭代次数较多、相邻区域较紧密时骨架易跨越区域等问题,提出一种分区提取骨架的算法.结合点云区域的连通性及局部相关性,采用马尔科夫随机场模型,将给定点云分割成不同区域.在相同标号的区域根据区域大小和点集数自适应地计算不同的初始收缩邻域尺度,用L1中值不断收缩迭代提取各区域的骨架分支,通过主成分分析及连接角判定骨架连接方式,并根据该连接方式将骨架分支连接成完整的点云骨架.实验结果表明,该算法能够自适应地提取点云骨架,减少点云收缩的迭代次数,保持模型原有的拓扑结构,对于含有区域紧密度不均匀的模型有较好的效果.
【期刊名称】《计算机工程》
【年(卷),期】2017(043)010
【总页数】7页(P222-227,233)
【关键词】poduoyejieyi点云模型;马尔科夫随机场;区域分割;属性信息;骨架提取
【作 者】晁莹;耿国华;张雨禾;张靖
【作者单位】西北大学信息科学与技术学院,西安710127;西北大学信息科学与技术学院,西安710127;西北大学信息科学与技术学院,西安710127;西北大学信息科学与技术学院,西安710127
【正文语种】中 文
【中图分类】TP391.4
骨架模型(中轴)[1]是三维模型的概括表示形式,也是表示三维模型拓扑结构的主要方法,既能直观反映原始模型的拓扑连接性,同时又能很好表示出物体的形状特征。因此,点云模型的自动骨架提取也越来越引起人们的重视。
当前已有大量针对点云骨架提取的工作,主要分以下4类:1)对称轴分析法,文献[2]提出以视觉特征为基础来分析模型的对称轴从而提取骨架,该方法主要通过得到模型形状的对称轴来提取骨架。但在实际应用中,该方法较难实现。2)基于拓扑与几何分析的方法,包括Reeb图法和Voronoi图法。Reeb图法是通过定义一个连续函数u来计算每个顶点的函数值从而进行分类,然后再聚合顶点形成骨架图[3]。此外,针对特殊的应用需求,文献[4-5]应用测地函数和调
和函数将多变量实值函数引入到Reeb图的方法中。文献[6]基于Voronoi图提出一种直接近似模型中轴的骨架提取方法,此方法对离散模型不太适用,针对边界噪声比较敏感,因此,使用范围较小。3)距离场法[7],该方法先生成原始模型的距离场,然后提取并连接距离场中的局部极值点,最后作适当的细化调整得到骨架。文献[8]引入鞍点(Saddle Points)的概念来解决基于距离变换骨架算法难以保证其连通性的问题,最终得到了连通的线骨架。4)细化法,该方法是在原始模型形状不变的情况下,从外围开始向里迭代缩减特征点,直到不能再缩减的时候,骨架也就形成了。文献[9]基于空间中轴和图收缩提出利用八叉树模型进行有向收缩最终连通形成骨架,但是针对较大的模型比较耗时,并且稳定性较差。
目前基于点云模型的分割方法有很多,例如基于区域生长的分割[10],该方法利用高斯曲率和平均曲率组合将模型分割为不同的曲面元再进行区域生长而分类,但是分割效率较低。还有比较经典的K均值聚类分割方法,但此方法只能在类为近似球形时得到较好的聚类结果,若成矢量大小不一的正态分布时,则聚类易有误差。马尔科夫随机场(Markov Random Filed,MRF)近几年被成功应用到三维模型的分割中并取得了很好的效果[11-12]。
deha针对点云模型的L1中值骨架提取算法[13],通过不断扩大邻域半径迭代收缩下采样点同时加
入适当的斥力,使得采样点收缩成线性骨架。但此方法中对全局采用同一初始邻域进行收缩迭代提取骨架,对于区域大小及点集数差别较大的模型,迭代效率不高,同时对于区域相对紧密的模型骨架分支不易区分,提取骨架易出现误差。本文针对上述问题,提出一种基于分割的点云骨架提取算法,通过生成连接点及骨架分支后相互连接形成完整的骨架。
1.1 算法介绍
结合点云模型中各区域的连通性及局部相关性,本文提出一种基于区域分割的骨架提取方法。首先通过MRF对点云模型进行分割预处理,避免相对密集区域骨架易跨越区域的问题;然后,在相同标号的区域根据区域的大小和点集数自适应地计算不同的初始收缩邻域尺度h0,接着用L1中值不断收缩迭代进行骨架提取得到各区域的骨架分支;最后在区域相邻部分,进一步收敛得到连接点,通过主成分分析(Principal Components Analysis,PCA)及连接角大小,判定骨架支端点与连接点的连接方式,相互连接得到完整的点云骨架。本文算法把区域较小的部分也会单独进行骨架提取,保证模型的细节特征不被忽略,同时减少迭代次数,避免区域交接处骨架断裂,得到符合原始点云模型的拓扑结构,给定散乱点云模型P={pi}∈R3,i=1,2,…,N,该模型不含有任何拓扑连接性信息,本文提取其骨架,算法流程和算法步骤示意图如图1、图2所示,算法步骤如下:
美味的食物英文
1)基于马尔科夫随机场分割点云模型;
2)各区域骨架分支提取;
3)通过连接点将相邻区域骨架分支进行连接。
1.2 基于马尔科夫随机场的点云分割
免费英语
MRF是一个概率图模型,结合基点邻域之间相互关系和基点自身属性信息对点云模型进行有效建模分割,可以达到很好的效果。首先通过层次吉布斯模型得到状态概率分布和联合概率密度分布,然后建立能量函数,最后使目标能量函数最小化来求得点云模型最优标号,得到符合人类视觉的分割。
1.2.1 点云初始化
对于一个给定三维散乱点云模型P={p1,p2,…,pN},pi是点云中的点数据,L={1,2,…,K}为标号集合,K表示将点云分割后的区域数,标号问题的状态空间为:
exciteF=L×L×…×L=LN
则状态空间F中的每一个状态f可以生成一个对应的点云标号状态,即点云分割结果,对于每个基点i应属于哪个标号值(属性信息)由点的观测信息来定义,设为D={d1,d2,…,dN},其中:
吸血鬼日记第四季14
di=
是指第i个点的曲率估计,λ1,λ2,λ3为给定点pi的球邻域邻居点协方差矩阵的特征值且满足λ1≤λ2≤λ3。
1.2.2 层次吉布斯随机场模型苏州服装学院
层次吉布斯随机场模型[14]是MRF的一种,分为上层吉布斯分布和下层吉布斯分布。其中,上层吉布斯分布,即随机场的状态分布可用来描述随机场中基点(随机变量)之间的相互依赖关系;下层吉布斯分布则用来描述随机场中各个基点的属性信息分布。
上层吉布斯分布是由Hammersley-Clifford定理得到的MRF的状态概率分布为:
P(f) =×exp(-β×U(f))
其中:
necessity其中,Z为归一化常量;β为交互系数;U(f)为能量函数,是概率图模型中所有子团势能函数Vc(f)的和,用来决定先验信息在MRF中的比重;θi是点i的球邻域。
在下层吉布斯分布中,用高斯混合模型来描述各观测随机变量分布。通过采用K个高斯分布来拟合散乱点云属性信息值D=(d1,d2,…,dN}的直方图的方式,把标号集合L=(1,2,…,K}中K个标号对应K个高斯分布,对这些属性信息的值进行聚类分析。通过定义似然函数p(D|μ,σ)采用期望最大似然估计(EM算法)来估计各个高斯分布的权重、均值和标准差。由此可以得出在MRF点云模型标号给定的情况下,观测变量D=(d1,d2,…,dN}的联合概率密度函数为:
