基于FPFH的权重局部最优投影点云精简算法_王曦.pdf

电 子 测 量 技 术E L E C T RON I CME A S U R EME N TT E CHNO L O G Y第4 5卷 第2 3期2 0 2 2年1 2月 D O I:1 0.1 9 6 5 1/j.c n k i.e m t.2 2 0 9 9 3 4基于F P F H的权重局部最优投影点云精简算法*王 曦1,2 王宗彦1,2 张宇廷1,2 吴 璞1,2 范浩东1,2(1.中北大学机械工程学院 太原 0 3 0 0 5 1;2.山西省起重机数字化工程技术研究中心 太原 0 3 0 0 5 1)摘 要:针对现有点云简化算法存在易丢失关键特征和复杂潜在曲面信息的问题,提出一种基于F P F H的权重局部最优投影(WL O P)点云精简算法。首先,采用快速点特征直方图(F P F H)查找并提取原始模型中的特征点;然后,通过WL O P算法精简原始稠密点云,生成去噪、无离群点且均匀分布的点云;最后,利用点云融合方法将特征点与简化模型融合并去除冗余点。将本文算法与最小包围盒法、最远点采样法、权重局部最优投影算法进行对比实验。实验结果表明本文算法在简化率为3 0%时,点云分布均匀性和特征保留方面均优于其他算法。此外,可视化分析结果表明,本文算法既能够保证精简模型的完整性,又能较好地保留原始点云关键特征。信息熵分析结果表明,精简后的点云包含信息丰富,特征表达准确。该算法可为点云重建提供重要应用价值。关键词:点云精简;F P F H;WL O P;点云融合;信息熵中图分类号:T P 3 9 1 文献标识码:A 国家标准学科分类代码:4 6 0.4 0 3 5W e i g h t e d l o c a l o p t i m a l p r o j e c t i o n p o i n t c l o u d s i m p l i f i c a t i o n a l g o r i t h m b a s e d o n F P F HW a n g X i1,2 W a n g Z o n g y a n1,2 Z h a n g Y u t i n g1,2 Wu P u1,2 F a n H a o d o n g1,2(1.S c h o o l o f M e c h a n i c a l E n g i n e e r i n g,N o r t h U n i v e r s i t y o f C h i n a,T a i y u a n 0 3 0 0 5 1,C h i n a;2.S h a n x i C r a n e D i g i t a l E n g i n e e r i n g T e c h n o l o g y R e s e a r c h C e n t e r,T a i y u a n 0 3 0 0 5 1,C h i n a)A b s t r a c t:I n o r d e r t o t a c k l e t h e p r o b l e m t h a t t h e o r i g i n a l p o i n t c l o u d s i m p l i f i c a t i o n w a s e a s y t o l o s e k e y f e a t u r e s a n d c o m p l e x l a t e n t s u r f a c e i n f o r m a t i o n,t h i s p a s s a g e p r o p o s e d a w e i g h t e d l o c a l o p t i m a l p r o j e c t i o n(WL O P)p o i n t c l o u d s i m p l i f i c a t i o n a l g o r i t h m b a s e d o n F P F H.F i r s t l y,t h i s p a s s a g e u s e d F a s t P o i n t F e a t u r e H i s t o g r a m(F P F H)t o f i n d a n d e x t r a c t f e a t u r e p o i n t s i n t h e o r i g i n a l m o d e l.T h e n,t h e o r i g i n a l d e n s e p o i n t c l o u d w a s r e d u c e d b y t h e WL O P a l g o r i t h m t o g e n e r a t e p o i n t c l o u d w h i c h h a d n o n o i s e,n o o u t l i e r s,a n d w a s e v e n l y d i s t r i b u t e d.F i n a l l y,a p o i n t c l o u d f u s i o n m e t h o d w a s u s e d t o c o m b i n e t h e f e a t u r e p o i n t s w i t h t h e s i m p l i f i e d m o d e l a n d r e m o v e r e d u n d a n t p o i n t s.T h i s p a s s a g e c a r r i e d o u t c o m p a r a t i v e e x p e r i m e n t s b e t w e e n a l g o r i t h m w i t h m i n i m u m r e c t a n g u l a r b o u n d i n g b o x a l g o r i t h m,f a r t h e s t p o i n t s a m p l i n g a l g o r i t h m a n d w e i g h t e d l o c a l o p t i m a l p r o j e c t i o n.T h e e x p e r i m e n t a l c o n c l u s i o n i n d i c a t e s t h a t t h e a l g o r i t h m i n t h i s p a p e r i s b e t t e r t h a n o t h e r a l g o r i t h m s i n t e r m s o f d i s t r i b u t i o n u n i f o r m i t y a n d f e a t u r e r e t e n t i o n w h e n t h e r e d u c t i o n r a t e i s 3 0%.I n a d d i t i o n,t h e v i s u a l a n a l y s i s r e s u l t s s h o w t h a t t h e a l g o r i t h m i n t h i s p a p e r n o t o n l y g u a r a n t e e t h e i n t e g r i t y o f t h e s i m p l i f i e d m o d e l,b u t a l s o b e t t e r p r e s e r v e t h e k e y f e a t u r e s o f t h e o r i g i n a l p o i n t c l o u d.T h e r e s u l t s o f i n f o r m a t i o n e n t r o p y a n a l y s i s s h o w t h a t t h e s i m p l i f i e d p o i n t c l o u d c o n t a i n s r i c h e r i n f o r m a t i o n a n d e x p r e s s e s m o r e a c c u r a t e f e a t u r e.T h e a l g o r i t h m c a n p r o v i d e i m p o r t a n t a p p l i c a t i o n v a l u e f o r p o i n t c l o u d r e c o n s t r u c t i o n.K e y w o r d s:p o i n t c l o u d s i m p l i f i c a t i o n;F P F H;WL O P;p o i n t c l o u d i n t e g r a t i o n;i n f o r m a t i o n e n t r o p y 收稿日期:2 0 2 2-0 6-1 3*基金项目:山西省重点国际科技合作项目(2 0 1 9 0 3 D 4 2 1 0 1 5)资助0 引 言 随着激光测量技术和计算机图形学的飞速发展,逆向工程和数字化的三维空间信息技术已成为计算机图形图像处理领域的研究热点1。与二维图像相比,对于外形复杂且特征信息丰富的物体,三维点云图像能够表达出更多的几何信息,被广泛的应用于自动驾驶、测绘、机器人定位抓取等领域2。现今三维激光扫描技术能够获取大量高精度的点云数据,但往往存在冗余点、噪声点、分布不均及数据量大等问题,严重影响数据存储、传输和模型重建等后续工911 第4 5卷电 子 测 量 技 术作。因此,在保证简化后模型的完整性和保留关键特征基础上,对原始点云数据的精简预处理是必不可少的3。国内外学者针对点云精简问题做了大量研究。传统的点云精简算法主要有:最小包围盒法、曲率采样法、最远点采样法和权重局部最优投影算法等。W a n g4,S u5等为了提高点云简化效率,分别提出基于曲率的点云精简策略,实现在高简化率的情况下,仍然保留大量特征点的 目 的。Y a r o n等6为了在法线方向不明确的情况下,处理干扰点方向的噪声数据,提出一种局部最优投影(L O P)点云精简算法。H u a n g等7通过改进L O P算法,在L O P基础上,引入权重密度算子,解决了L O P简化后点分布不均的问题。李海鹏8,贾薇9等针对点云数据集冗余点过多,影响数据处理效率的问题,采用快速点特征直方图(F P FH)的方法消除冗余点对精简模型的影响。李琪琪等1 0在精简策略中引入泊松分布区域生长算法,解决了传统简化算法丢失大量特征信息的问题。焦晨等1 1针对点云模型普遍存在噪声点的问题,综合多种滤波方法实现在精简点云的同时去除冗余数据。王琼等1 2针对车辆点云数据重构效率低和精简质量差的问题,采用k d-t r e e建立空间索引结构,提高了模型精简质量和曲面重构效率。传统点云精简算法大多侧重于保留模型完整性,提高处理效率,往往会忽略模型细节特征,丢失大量重要信息,无法保证精简后的质量1 3-1 4。针对上述问题,本文提出了一种基于F P FH的权重局部最优投影点云精简算法。本文主要工作:1)WL O P算法融合了F P FH特征提取的优点,在WL O P算法中加入F P FH特征提取算子,精简后的模型既能较好的表达点云细节特征,又能解决噪声点、离群点、分布不均等问题。2)通过信息熵评价方法对精简后的点云模型进行评价,该方法能够科学公正地衡量精简模型中包含信息量的大小。1 本文方法1.1 快速点特征直方图(F P F H)基本的点云模型特征表达方式有曲率和法线两种,但只能估计单点周围的几何特征,无法清晰地表述与附近邻域内其他点的几何关系,导致特征信息表达不准确1 5。相反,点特征直方图(P FH)是一种姿态恒定的局部特征表达方式,能够通过参数化方法描述某点与其球性区域内近邻点的空间差异,以多维直方图的形式表达某点所在局部区域的特征属性。直方图所在的高维超空间在不同采样密度和噪声环境下具有较强鲁棒性,并为特征表示提供了一个可度量的信息空间。要得到目标点Pq与其近邻点关系的特征直方图,首先搜索其在半径为r的球形区域内所有近邻元素,两两连接组成一个网络,构成目标点Pq的P FH影响区域,如图1所示。设球形区域内任意两点Ps和Pt的法向量为ns,nt,以图1 目标点Pq的P F H影响区域Ps的法向量为u轴,以右手定则确定坐标轴u v w,由此定义以Ps为原点的固定局部坐标系,如图2所示。图2 邻域点对局部坐标系局部坐标系u v w平移到点Pt处,则法向量ns,nt间偏差可由来表示,两点间欧式距离记为d,计算公式为:=vnt(1)=a r c t a n(wnt,unt)(2)=u(Pt-Ps)d(3)d=Pt-Ps(4)由上式组成k邻域内每一对点的四元组,将两点的坐标值和其对应的法向量分量以四元组的方式进行表达,降低了计算的复杂度。由于欧式距离d表达的信息对整体几何特征贡献较小,故将四元组中的角度参数划分为b个子区间,最终创建出含有b3个区间的直方图。通过统计子区间中点的数目,确定P F H描述子,通过对特征显著区间设定阈值提取目标点云的关键特征。由于P F H特征描述子的计算复杂度为O(n k2),为了降低计算复杂度,满足实时性需求,RU S U1 6等在P F H基础上提出了快速点特征直方(F P F H),将时间复杂度降低至O(n k)。F P F H影响区域如图3所示,1)计算数据集中每一点与其球形区域内所有近邻点间的一个元组,记为S P F H。2)重新确定每个点邻域范围,最终的直方图由邻近的S P F H值计算得到。F P FH(Pq)=S P FH(Pq)+1kki=11iS P FH(Pk)(5)1.2 权重局部最优投影算法(WL O P)局部最优投影算法(L O P)是一种无参数化点云精简算021 王 曦 等:基于F P FH的权重局部最优投影点云精简算法第2 3期图3 目标点P q的F P F H影响区域法1 7。由于该算法不是基于局部参数化的方法,对于复杂的点云模型具有良好的鲁棒性。如果点云模型中含有光滑曲面,则该算子提供二阶近似值,从而满足简化模型的合理性。L O P算法采用L 1中值优化的原理,从而得出高质量的点云数据输出,并且不依赖于点的局部参数化或其局部方向,对复杂点云仍具备普遍适用性。能够有效的去除点云集中噪声点、离群点且能够较好地解决元素分布不均的问题,更加忠实地遵循原始形状。权重局部最优投影算法(WL O P)是在L O P的基础上引入(r)=-r替代L O P算法中(r)=1/(3r3)作为投影排斥力因子,使得WL O P算法不会过早的收敛,精简结果保留更多关键信息。具体算法为:给定一个点集P=pjj JR3,WL O P通过固定点迭代的方式定义点集X=xiiIR3投影到P上,投影点集记为Q=qiiI,且Q要满足投影点到P的加权距离之和最小,迭代次数记为Xk(k=0,1,n),则下一次迭代所需能量最小化,如式(6)所示。iIjJxi-pj(ki j)/vj+i Ii(xi-xki)(ki i)ki(6)其中,ki j=xki-pj,ki i=xki-xki。(r)=e-r2/(h/4)2为平滑权重函数,h=4db b/m(db b为输入点云边界的对角线长度,m为点的数量),为排斥力因子。L O P算法优化标准与L1中值密切相关,如果输入点云分布高度不均,则L O P算法也会遵循这种不均匀的趋势,导致精简后的点云模型在特征区域出现大量冗余点。故WL O P算法在L O P的基础上定义局部密度权重,加强了稠密区域内点的斥力。vj和ki分别为点集P和X中每一点的局部密度权重:vj=1+j Jj(pj-pj)(7)ki=1+i Ii(ki i)(8)Xk+1迭代的结果为xk+1i=jJpjki j/vjj Jki j/vj+i Iiki i ki ki i j Jki ki i(9)式中:ki j=(ki j)ki j,ki i=(ki i)|(ki i)|ki i。2 算法流程 WL O P算法虽然能够去除点云中噪声点和离群点,使采样后的点均匀分布在空间中,但点云弯曲程度较大的潜在曲面特征易被抹平。本文在WL O P算法的基础上增加了F P F H特征提取算子,使得精简后的点云在减少了数据量的同时,显著的反映出模型的细节特征。算法的具体步骤如下;输入:点集P=(xi,yi,zi)以及相关参数输出:精简后的点云集P 步骤1)特征提取。根据式(5)计算点云数据每点的F P F H值。通过得到的F P F H直方图确定特征点所在的组合区间,确定该区间阈值(根据不同的点云模型特征区间调整),提取特征点并输出。图4所示为采用F P FH特征提取算子对B u n n y模型、P l a n e模型、A n g l e模型和H a n d模型特征提取结果。步骤2)点云精简。首先,通过WL O P算法计算输入点集与投影点集中每一点所占权重值,通过每点所占权重确定其在原始点云模型的细节特征表达的重要性,然后确定邻域半径r,通过式(9)迭代,最终得到一组去噪、无离群点且均匀分布的点云。步骤3)点云融合。将步骤1中提取的特征点与步骤2)中精简后的点云融合,并通过P C L_K D-t r e e去除冗余点,得到数据量小且特征信息丰富的点云。本文以S t a n f o r d大学和普林斯顿视觉与机器人实验室在早期所提供的开源点云数据集中B u n n y、A n g l e、H a n d和P l a n e模型为例,验证F P F H特征提取算子的鲁棒性和适应性。B u n n y模型的特征信息主要为头部、耳部和腿部;A n g l e模型的特征信息为人类头部轮廓、全身肌肉线条和翅膀;H a n d模型的特征信息为手掌的大鱼际区和指间区掌纹;P l a n e模型相比于其他3个模型,包含大量平滑特征,特征信息主要为头部螺旋桨、起落架和机翼。如图4可视化结果可以看出,F P F H特征提取算子对弯曲程度较大的潜在曲面特征提取完整,充分体现了三维图像在信息表达方面的优势。同时可以得出,点特征直方图通过搜索K-D T r e e寻找k近邻点,通过计算达到的F P F H值划分特征区间,可有效搜索并提取点云特征信息。3 点云精简算法验证 在 配 置 开 源C+编 程 库C G A L-4.1 3.2和P C L-1.9.0的V S 2 0 1 7环境下实现本文方法,并在C P U I n t e l C o r e i 5、2.6 GH z处理器和 8 G B 内存的标准 P C 上对图四所选样本进行精简实验。选取样本为斯坦福大学三维扫描库和m o d e l n e t 4 0中潜在曲面弯曲程度较大,细节特征丰富的数据集为测试样本。并将本文算法与最小包围盒法、最121 第4 5卷电 子 测 量 技 术 图4 不同模型特征提取结果远点采样法、WL O P点云精简算法进行对比分析,从可视化和信息熵两个方面对算法进行评价。3.1 可视化效果分析 为了测试本文算法对不同形状和数据量的点云模型适用性和鲁棒性,测试不同算法对B u n n y模型、P l a n e模型、A n g l e模型和H a n d模型在3 0%精简率(删减点云数/输入点云数)下的精简效果,并与本文算法进行对比,如图5所示。从图中可以看出,对于数据量大且细节特征丰富的点云模型,最小包围盒法、最远点采样法和W L O P算法三种算法均完整保留了原始模型的基础形状。相对而言,最小包围盒法和最远点采样法分布更加均匀,但是对于模型的细节特征损失严重;W L O P算法在一定程度上保留了部分特征信息,但分布离散化比较严重;而本文算法在保留关键特征信息的同时,相较于W L O P算法,点云分布均匀性得到了提高。图5 精简率3 0%下不同模型精简效果 对于B u n n y模型,最小包围盒法和最远点采样法只保留少量腿部特征,头部和耳部信息大量丢失;WL O P算法保留了部分头部特征,腿部和耳部特征丢失严重;而本文提出的算法既保证了精简后模型的完整性和均匀性,又极大程度的保留了b u n n y模型的特征信息,明显地表达出b u n n y的头部、耳部和腿部特征。对于A n g l e和H a n d模型,相比于其他三种点云简化算法,本文算法同样保留大量特征信息。针对P l a n e模型同时包含弯曲程度较大的潜221 王 曦 等:基于F P FH的权重局部最优投影点云精简算法第2 3期在曲面特征和大量平滑特征的问题,本文算法不仅完整地保留了特征信息还对平滑特征区域进行轮廓提取和下采样操作,使得精简后的点云模型较为明显的表 达 出 了P l a n e的特征信息。对于结构复杂,信息量巨大的点云模型,本文算法也具有较好的适用性,能够同时满足完整性和保留特征信息的要求。3.2 信息熵分析 信息熵是一个含义丰富的熵值概念1 8。信息熵可以用来评价精简后点云所包含特征信息量的大小。根据点云模型平均曲率的分布情况计算数据集中每点的熵值。某点的熵值越大,表明该点对模型的贡献越大。简化模型整体的熵值越大,说明该模型包含信息越丰富,表达的特征越准确。信息熵的计算公式为:Ei=-pil o g2pi-kj=1pjl o g2pj(1 0)pi=hihi+kj=1hj(1 1)pj=hjhi+kj=1hj(1 2)其中,Ei为i点的熵值,pi、pj为i点和j点的曲率概率分布,hi为i点的平均曲率值,j点是p点邻域范围内的点。模型整体熵值为:E=ni=1Ei(1 3)根据式(1 3)计算本文所采用的4种点云精简算法简化模型整体信息熵,如表1所示。从表中可以看出,在B u n n y、A n g l e和H a n d模型精简结果中,本文提出的算法信息熵值均为最高。但是在P l a n e模型上,本文算法略低于WL O P算法。结果表明,本文算法对于存在尖锐和平滑特征的点云模型,精简效果会有所下降。但是点云分布均匀性良好的最小包围盒法和最远点采样法信息熵低于WL O P算法和本文算法,所以同时兼顾模型关键特征保留和整体完整性的熵值更高,精简后的点云数据包含的特征信息也更加丰富。表1 4种算法熵值计算结果1 03算法模型最小包围盒法最远点采样法WL O P本文算法B u n n y2.3 0 5 71.3 9 4 33.6 1 5 43.8 0 2 2P l a n e0.9 4 7 11.3 6 6 91.4 6 4 91.4 5 2 5A n g l e1.7 4 7 11.7 5 0 21.0 8 3 22.6 8 7 2H a n d1.3 1 9 22.1 5 2 31.7 6 9 02.9 3 9 44 结 论 本文提出了基于F P FH的权重局部最优投影点云精简算法。该算法主要以开源P C L库和C GA L库为基础,以S t a n f o r d大学和普林斯顿视觉与机器人实验室公布的点云数据集为研究对象,利用F P F H计算点云数据集的点特征直方图,通过对特征点所在区间设定阈值的方式提取点云的特征信息并与WL O P算法简化后的点云相融合,达到强制保留特征信息的精简目的。与传统点云精简算法相比,该算法在保证点云分布均匀性的同时,充分地保留了点云模型的细节特征。解决了现有点云简化算法易丢失细节特征和曲面形状信息的问题。克服了三维点云数据信息量 过 大,存 储、传 输 时 间 过 长,处 理 效 率 过 低 等问题。参考文献1 李明磊,张蕊,李广云,等.激光扫描点云法矢精确计算与表面光顺方法J.计算机辅助设计与图形学学报,2 0 1 5,2 7(7):1 1 5 3-1 1 6 1.2 喻永前.基于点云数据的特征约束精简与三维重构技术研究D.上海:上海大学,2 0 2 1.3 张雨禾,耿国华,魏潇然,等.保留几何特征的散乱点云简化算法J.计算机辅助设计与图形学学报,2 0 1 6,2 8(9):1 4 2 0-1 4 2 7.4 WANG G L,WU L S,HU Y,e t a l.P o i n t c l o u d s i m p l i f i c a t i o n a l g o r i t h m b a s e d o n t h e f e a t u r e o f a d a p t i v e c u r v a t u r e e n t r o p yJ.M e a s u r e m e n t S c i e n c e a n d T e c h n o l o g y,2 0 2 1,3 2(6):6 5 0 0 4-6 5 0 1 6.5 S U Z X,L I Z Y,Z HAO Y D,e t a l.C u r v a t u r e-a w a r e s i m p l i f i c a t i o n f o r p o i n t-s a m p l e d g e o m e t r yJ.J o u r n a l o f Z h e j i a n g U n i v e r s i t y S C I E N C E C,2 0 1 1,1 2(3):1 8 4-1 9 4.6 Y A R O N L,D A N I E L C,D A V I D L,e t a l.P a r a m e t e r i z a t i o n-f r e e p r o j e c t i o n f o r g e o m e t r y r e c o n s t r u c t i o nJ.A CM T r a n s a c t i o n s o n G r a p h i c s(TOG),2 0 0 7,2 6(3):2 2-2 8.7 HUA N G H,L I D,Z HA N G H,e t a l.C o n s o l i d a t i o n o f u n o r g a n i z e d p o i n t c l o u d s f o r s u r f a c e r e c o n s t r u c t i o nJ.A CM T r a n s a c t i o n s o n G r a p h i c s(TOG),2 0 0 9,2 8(5):1-7.8 李海鹏,徐丹,付宇婷,等.基于F P F H特征提取的散乱点云精简算法J.图学学报,2 0 2 2,4 3(4):5 9 9.9 贾薇,舒勤,黄燕琴.基于F P F H的点云特征点提取算法 J.计 算 机 应 用 与 软 件,2 0 2 0,3 7(7):1 6 5-1 6 9,2 4 5.1 0 李琪琪,花向红,赵不钒,等.一种基于曲率泊松碟采样的散乱点云精简方法J.测绘通报,2 0 2 0(S 1):1 7 6-1 8 0.1 1 焦晨,王宝锋,易耀华.点云数据滤波算法研究J.国外电子测量技术,2 0 1 9,3 8(1 1):1 8-2 2.1 2 王琼,王海燕,孙保群,等.车辆曲面重构中点云精简算法 的 研 究 与 改 进 J.电 子 测 量 与 仪 器 学 报,2 0 1 7,3 1(1 1):1 6 9 3-1 7 0 1.321 第4 5卷电 子 测 量 技 术1 3 李仁忠,杨曼,刘阳阳,等.一种散乱点云的均匀精简算法J.光学学报,2 0 1 7,3 7(7):9 7-1 0 5.1 4 杨焕宇.面向虚拟现实的三维点云数据处理关键技术研究D.上海:东华大学,2 0 1 6.1 5 李茂月,马康盛,王飞,等.基于结构光在机测量的叶片点云预处理方法研究J.仪器仪表学报,2 0 2 0,4 1(8):5 5-6 6.1 6 RU S U R B,B L O D OW N,B E E T Z M.F a s t p o i n t f e a t u r e h i s t o g r a m s f o r 3 D r e g i s t r a t i o nC.P r o c e e d i n g s o f I E E E I n t e r n a t i o n a l C o n f e r e n c e o n R o b o t i c s a n d A u t o m a t i o n,2 0 0 9:1 8 4 8-1 8 5 3.1 7 王晓辉,吴禄慎,陈华伟.基于法向量距离分类的散乱点云数据去噪J.吉林大学学报(工学版),2 0 2 0,5 0(1):2 7 8-2 8 8.1 8 李佩佩,崔凤英.基于二分K-m e a n s聚类的曲率分级点云数 据 精 简 优 化 算 法 研 究 J.电 子 测 量 技 术,2 0 2 2,4 5(4):6 6-7 1.作者简介王曦,硕士研究生,主要研究方向为图像处 理 与 深 度学习。E-m a i l:9 8 7 6 0 4 4 3 7q q.c o m王宗彦(通信作者),教授,博士生导师,主要研究方向为智能制造与数字化。E-m a i l:i a w a n g z o n g y a n s i n a.c o m421