基于最小角度三角化填充的枝干点云根部空洞修补.pdf

西北林学院学报2 0 2 3,3 8(4):2 1 4-2 2 3J o u r n a l o f N o r t h w e s t F o r e s t r y U n i v e r s i t y d o i:1 0.3 9 6 9/j.i s s n.1 0 0 1-7 4 6 1.2 0 2 3.0 4.2 7基于最小角度三角化填充的枝干点云根部空洞修补 收稿日期:2 0 2 2-0 4-2 5 修回日期:2 0 2 2-0 6-0 2 基金项目:广东省 林业科技创新项 目(2 0 2 1 K J C X 0 0 1);国家重 点研发计划(2 0 1 6 Y F C 0 5 0 2 7 0 4);江苏 高 校 优 势 学 科 建 设 工 程 项 目(P A P D)。第一作者:杨 杰。研究方向:遥感与G I S应用技术。E-m a i l:n j_y a n g_j i e q q.c o m*通信作者:温小荣,博士,副教授,硕士生导师。研究方向:森林资源监测与G I S应用。E-m a i l:n j w 9 8 7 21 6 3.c o m杨 杰1,2,温小荣1,2*,汪求来3,叶金盛3(1.南京林业大学 南方现代林业协同创新中心,江苏 南京 2 1 0 0 3 7;2.南京林业大学 林学院,江苏 南京 2 1 0 0 3 7;3.广东省林业调查规划院,广东 广州 5 1 0 5 2 0)摘 要:激光雷达扫描仪获得的树木点云仅表达了树木的表面,缺少根部截面的点云,因而往往是不封闭的,这一特性对树木建模的2种主要方法(骨架和D e l a u n a y三角网)都会产生影响,增加了额外处理工作并且降低了模型精度,而现有研究中点云的空洞修补方法并不能直接应用于枝干点云根部。针对这一现状,结合对现有空洞修补方法进行改进,并适用于枝干点云的根部,分为由预处理、根部空洞边界的获取、基于最小角度法的空洞三角化填充与后处理4个阶段,并以C+编程实现,以根部空洞修复和未修复的骨架对比了效果。结果表明,rb e、k、4个参数设置合理时填充枝干点云能够在正确监测点云空洞边界的基础上较好且快速地修复根部的空洞,使用处理后的点云建立的骨架相较于未处理的中心偏移明显改善,因而有助于提高枝干建模的精度。该方法拓宽了点云空洞修补的适用场合。关键词:空洞修补;D e l a u n a y三角网;树木建模中图分类号:S 7 5 8 文献标志码:A 文章编号:1 0 0 1-7 4 6 1(2 0 2 3)0 4-0 2 1 4-1 0F i l l i n g T r e e R o o t H o l e i n B r a n c h P o i n t C l o u d W i t h T r i a n g u l a t i o n s B a s e d o n M i n i m u m A n g l e sY A N G J i e1,2,WE N X i a o-r o n g1,2*,WA N G Q i u-l a i3,Y E J i n-s h e n g3(1.C o-I n n o v a t i o n C e n t e r f o r S u s t a i n a b l e F o r e s t r y i n S o u t h e r n C h i n a,N a n j i n g F o r e s t r y U n i v e r s i t y,N a n j i n g 2 1 0 0 3 7,J i a n g s u,C h i n a;2.F a c u l t y o f F o r e s t r y,N a n j i n g F o r e s t r y U n i v e r s i t y,N a n j i n g 2 1 0 0 3 7,J i a n g s u,C h i n a;3.G u a n g d o n g F o r e s t r y S u r v e y a n d P l a n n i n g I n s t i t u t e,G u a n g z h o u 5 1 0 5 2 0,G u a n g d o n g,C h i n a)A b s t r a c t:O n l y t h e s u r f a c e o f a t r e e c a n b e e x p r e s s e d i n t h e p o i n t c l o u d p r o v i d e d b y a L i D A R s c a n n e r.T r e e p o i n t c l o u d s a r e a l w a y s u n c l o s e d f o r l a c k o f t h e s e c t i o n o f t h e r o o t.T h e f e a t u r e h a s a b a d i n f l u e n c e o n t w o m a j o r m e t h o d s o f t r e e m o d e l i n g,i n c l u d i n g s k e l e t o n a n d D e l a u n a y t r i a n g u l a t i o n,w h i c h i n c r e a s e e x t r a p r o-c e s s i n g w o r k a n d d e c r e a s e t h e a c c u r a c y o f m o d e l s.H o w e v e r,t h e e x i s t i n g m e t h o d s o f p o i n t c l o u d h o l e-f i l l i n g c a n n o t d i r e c t l y a p p l y t o t h e r o o t s e c t i o n i n t r e e b r a n c h p o i n t c l o u d.A i m e d a t t h i s i s s u e,t h e m e t h o d p r o-p o s e d i n t h e r e s e a r c h i m p r o v e d t h e e x i s t i n g h o l e-f i l l i n g m e t h o d s t o s a t i s f y t h e a p p l i c a b i l i t y o f h a n d l i n g t h e r o o t s e c t i o n i n t r e e b r a n c h p o i n t c l o u d.I t w a s d i v i d e d i n t o f o u r s t a g e s:p r e p r o c e s s i n g,o b t a i n i n g t h e r o o t c a v i t y b o u n d a r y,c a v i t y t r i a n g u l a t i o n f i l l i n g b a s e d o n t h e m i n i m u m a n g l e m e t h o d a n d p o s t-p r o c e s s i n g.I t w a s i m p l e m e n t e d b y C+p r o g r a mm i n g f o r s h o w i n g t h e d i f f e r e n c e b e t w e e n t h e s k e l e t o n p r o d u c e d a f t e r h o l e-f i l l i n g a n d w i t h o u t h o l e-f i l l i n g.T h e r e s u l t s s h o w e d t h a t w h e n f o u r p a r a m e t e r s w e r e s e t r a t i o n a l l y rb e,k,f i l l i n g t h e r o o t h o l e o f t h e b r a n c h p o i n t c l o u d s w a s b e t t e r a n d q u i c k.C o m p a r e d w i t h t h e b r a n c h p o i n t c l o u d b e f o r e r o o t h o l e-f i l l i n g,t h e p r o d u c e d s k e l e t o n w i t h t h a t a f t e r r o o t h o l e-f i l l i n g h a d s m a l l e r c e n t e r d e v i-a t i o n.T h e r e f o r e t h e r e s e a r c h i s h e l p f u l t o i m p r o v e t h e a c c u r a c y o f t r e e b r a n c h m o d e l i n g.A d d i t i o n a l l y t h e m e t h o d c a n b r o a d e n a p p l i c a b l e o c c a s i o n o f p o i n t c l o u d h o l e-f i l l i n g.K e y w o r d s:h o l e-f i l l i n g;D e l a u n a y t r i a n g u l a t i o n;t r e e m o d e l i n g 树木枝干在林业调查研究中十分重要,近年来,利用树木枝干点云作为数据源进行枝干建模提取林业参数成为一项研究热点1-2。但由于激光雷达获取的是物体表面的信息,对于树木根部截面只有边缘点,这一现象会对枝干建模造成影响。(树木)枝干点云建模一般使用D e l a u n a y三角网方法或骨架方法3,若采用D e l a u n a y三角网方法,则模型在根部截面处会出现很多“狭长”三角形,影响了三角网的构建质量4;若采用骨架方法,按照X u等5给出的骨架建立过程,需要选择一个根节点,计算枝干点云中其他点与根节点的最短路径距离,依据距离划分成若干层(b i n s),并把每层聚类分割成若干部分(b i n),最后由每一个部分计算中心确定骨架点。当根节点位于根部截面的边缘时,靠近根部的骨架点会朝树干表面偏移,影响了骨架的精度。对枝干点云根部的空洞修补能够有效解决问题。目前,点云空洞修补是一项关键的研究,但这些研究并没有针对枝干点云并且也不能直接运用到枝干点云上。表1对比了现有的若干研究并分析了各自的局限性,这些局限性正是这些算法不能直接处理枝干点云空洞的原因。针对于树木枝干点云根部的空洞修补,本研究基于C+编程实现,结合P C L点云库以及该库所自带的第三方库给出了一种修补流程,由预处理、根部空洞边界的获取、基于最小角度法的空洞三角化填充与后处理4个阶段构成。表1 点云空洞修补研究及其局限性T a b l e 1 R e s e a r c h e s o f p o i n t c l o u d h o l e-f i l l i n g a n d t h e i r l i m i t a t i o n s文献来源原理局限性蒋刚6将已有空间点向3个相互正交的空间平面投影,并在各投影面上分别利用支持向量机做回归,再通过内插值获得缺失点在3个平面上的坐标后合成缺失的空间点只适用于已有点和缺失点近似在同一条连续光滑的曲线上的情况蔡香玉等7采用径向基函数神经网络填补空洞适用于平面点云或变化缓慢的近似于光滑曲面的点云,且在这个面上已知点较多王俊豪8通过选取特征点的方法进行空洞修补要能够找到与空洞区域具有特征相同的其他位置的点王丽英等9利用外边界轮廓点拟合最小二乘平面,在该平面内利用边界点与中心距离的方差和曲率在等距扩大或者缩小的范围内插值算法主体是检测空洞范围,没有给出具体的插值方式孙晓东1 0利用边界结合NUR B曲线反求漏洞点并规避噪声点更偏向于解决边界不闭合时的情况陈相等1 1采用最小角度法三角化填充空洞松弛参数是定值,在不同点云上效果不一;原算法只适用于凸多边形的空洞1 材料与方法1.1 试验数据来源使用型号为R I E G L V Z-4 0 0 i的地基激光雷达扫描仪,设置扫描模式为P a n o r a m a 4 0。对位于江苏省宿迁市泗洪县陈圩林场马浪湖分场(3 3 1 5 N,1 1 8 1 8 E)中美洲黑杨(P o p u l u s d e l t o i d e s)的一个小班中选择的样地,进行多站扫描得到样地的地基激光点云数据1 2-1 3,扫描模式的详细参数见表2。对该点云数据经去噪、去除地面点、归一化后进行单木分割,从中选取1棵样木的点云,进行枝叶分离得到试验所用的枝干点云(图1)。在试验阶段先以枝干点云对比不同参数对某些步骤产生的影响,而在算法性能分析部分选用同一样地内的其他美洲黑杨的枝干点云展示在各自相对最佳参数下的效果。1.2 空洞修补原理本研究提出的空洞修补主要分为4个阶段:预处理、根部空洞边界的获取、基于最小角度法的空洞三角化填充与后处理。预处理部分用于找到输入枝干点云的根部边界点云,在根部空洞边界获取阶段,由于直接确定真正的空洞边界较为困难,因而转化为确定一个等价的空洞边界,然后再基于最小角度图1 试验用的枝干点云F i g.1 B r a n c h p o i n t c l o u d i n t h e r e s e a r c h512第4期杨 杰 等:基于最小角度三角化填充的枝干点云根部空洞修补表2 R I E G L V Z-4 0 0 i扫描模式P a n o r a m a 4 0T a b l e 2 R I E G L V Z-4 0 0 i s c a n n i n g m o d e P a n o r a m a 4 0扫描分辨率扫描时间/s测量分辨率2 0 m分辨率5 0 m扫描站数4 0 m d e g4 52 2.5 M i o1 4 mm3 4 mm4 0 0法的空洞三角化填充阶段填充这个等价的空洞,把填充好的等价空洞还原到枝干根部空洞所在位置,并对可能存在的缝隙和重复点进行处理后得到修补后的树木枝干点云。空洞修补流程见图2。1.2.1 预处理 对于输入的枝干点云,为了获取它的边界,需要对每一个点进行法线估计(n o r m a l e s-t i m a t i o n),以作为对局部表面的法向量的近似推断,法线估计可采用k d t r e e的K搜索或半径搜索(搜索半径记为rn e)。在获取了法线估计值后,与原点云一同作为输入,设置搜索半径(s e a r c h r a d i u s)rb e和夹角阈值(a n g l e t h r e s h o l d)m(默认取/4)后获得枝干边界点云。此时获得的枝干边界点云中的点集中分布在枝干点云的根部及树梢位置,但并没有区分出哪些点是根部边界的点,可以通过聚类将所有点分割成不同的部分,欧氏聚类提取(e u c l i d c l u s t e r e x t r a c t i o n,E C E)是点云聚类中的一种简单有效的方法1 4,除了输入的点云外,还需要2个必要的参数,一是聚类容忍度(c l u s t e r t o l e r a n c e)或搜索半径(用E p s),二是每一个聚类分割所允许的最小点数(m i n c l u s t e r s i z e,用M i n P t s表示)1 5。由于能够构成面至少需要3个点,因而M i n P t s取3。在聚类完成后,很容易找到根部边界点云。1.2.2 根部空洞边界的获取 首先,拟合平面与计算平面法向。记根部边界点pi=xi yi zi T,i=1,2,n,n3,piB,所有根部边界点的平均坐标(质心)为x y z T,待拟合的平面方程为a x+b y+c z+d=0,为了便于后续研究,a、b、c需要满足a2+b2+c2=1,记矩阵A=x1-x y1-y z1-zxn-x yn-y zn-z Z w i c k1 6指出,正交距离回归(O D R)可以用于拟合平面,而在三维空间中找到最优O D R平面最常用的方法是利用矩阵的奇异值分解(S V D):对A进行S V D分解,即存在n维酉矩阵U、3维酉矩阵V和矩阵=100020003000000 n3式中:奇异值i,i=1,2,3满足123,使得A=UVH,则最优O D R平面经过质心,且垂直于A的最小奇异值3对应的矩阵V的列,即拟合后得到的a=V1 3,b=V2 3,c=V3 3,d=-ax-by-cz,拟合平面的法向量为n=a b c T,是单位向量。本研 究 中 在 对 矩 阵A进 行S V D分 解 时 使 用E i g e n:J a c o b i S V DE i g e n:M a t r i x X d 类。图2 空洞修补流程F i g.2 H o l e-f i l l i n g p r o c e s s612西北林学院学报3 8卷 其次,旋转根部边界点云后投影至水平面并计算高度均值。由于倾斜且不在同一个平面内的离散点近似在一个多面体盒子中,难以确定的空洞边界,在得到平面法向量后,对点云进行旋转,并投影到水平面上,以便于研究。令向量ez=0 0 1 T,旋转角度=a r c c o snez|n|ez|,旋转轴=nez,归一化的旋转轴0=xyz T,由罗德里格旋转公式可知旋转矩阵:R=c o s+2x(1-c o s)-zs i n+xy(1-c o s)ys i n+xz(1-c o s)zs i n+xy(1-c o s)c o s+2y(1-c o s)-xs i n+yz(1-c o s)-ys i n+xz(1-c o s)xs i n+yz(1-c o s)c o s+2z(1-c o s),并记每一个旋转后的边界点为p i=R pi,p iB,将p i投影至水平面得到p i=p i1p i2 TB,并令h=1nni=1p i3,该高度将作为所有修补的空洞点的高度。再次,计算凸包、凹包以获得空洞边界。当有了平面点集后,待填充的空洞位于一个可将这些点包围住的多边形的内部,需要找到空洞的边界。最小凸包是指一个能够包括平面点集中全部点的最小凸多边形1 7,利用p c l:C o n v e x H u l lp c l:P o i n t X Y Z类求取平面点集B 的最小凸包,得到多边形C凸,该多边形以有向边组成,即C凸的边为v0v1,v1v2,vm-2vm-1,vm-1v0,viB。若直接在最小凸包内填充点,边界处的点则会增多,这一方面会造成外密内疏的现象,另一方面影响到原本真实的边界点云的分布状况,因而需要在最小凸包中去掉原本点分布的区域。凹包是一个能够尽可能包括平面点集中点的凹多边形,不同于凸包,没有最小凹包一说,此外,获得的凹包的形状受制于形状参数,越小,凹包的形状倾向于在某一处凹陷以更加贴合点集的外形,这就会造成某些点因为影响到为满足其他更多点贴合的多边形的建立而被排除在得到的凹包内的情况,当+?时得到的凹包将无限接近于凸包1 8。本研究中以参数利用p c l:C o n c a v e H u l lp c l:P o i n t X Y Z 求取平面点集B 的凹包,得到多边形C凹。从最小凸包中去掉与凹包相同的部分,事实上剩余的图形可能是由多个多边形所构成,也就是说,多边形的减法运算得到的是多边形的集合,而定义最优化问题。m a xA r e a(C)s.t.CSC=C凸-C凹的最优解C=C*为空洞边界的多边形,本研究中利用b o o s t库求取空洞多边形边界。最后,需要确定边界的封闭方向,也就是确定指向多边形内部的方向。由格林公式可知封闭区域D边界曲线正向L+满足DQx-Py dxdy=L+Pdx+Qdy由式(1)可知,沿多边形的边求曲线积分,若积分值为正,则为沿着边界曲线正方向(逆时针),反之为顺时针,记C是由点ui=xiyi T,i=0,1,L,r-1依次构成,则边界的路径积分为 C-ydx=-r-1i=0(x(i+1)m o dr-xi)y(i+1)m o dr+yi2=D-(-y)y dxdy=Ddxdy因而只需计算-r-1i=0(x(i+1)m o dr-xi)y(i+1)m o dr+yi2(1)的值,若为正,则多边形随着点的序号增加逆时针封闭;若为负,则为顺时针封闭。式(1)取绝对值后即为求二维平面离散点依次所围成的多边形面积的鞋带公式(s h o e l a c e f o r m u l a)1 9。1.2.3 基于最小角度法的空洞三角化填充 算法1给出了根部点云空洞的填补方法。本研究对以前的方法做了如下完善。1)引入多边形封闭方向可适应凹多边形的处理,并且便于编程,而且计算复杂度低;2)将松弛参数k由定值1.2修改为变量,试验结果部分将比较不同k对填充效果的影响;3)引入最小角度的限制,该最小角度用1 8 0 -(为一个较小的正数参数)作限制,一方面可以避免编程时由于浮点数产生的问题;另一方面也可以影响到允许的三角形的形状,进而影响到修补点的分布。算法1 基于最小角度的空洞三角化填充A l g o r i t h m.1 T r i a n g u l a r h o l e-f i l l i n g b a s e d o n a m i n i m u m a n g l e输入:C,空洞多边形边界封闭方向,k,输出:Q 计算初始的空洞多边形边长的平均值l初始化当前空洞边界多边形C:=C初始化新增加点的集合Q:=w h i l e空洞未修补完整d o初始化存放每一个边界点的内角角度的序列,中元素个数与C的顶点数相等f o r e a c h空洞多边形C的边界点ui d o:=1 8 0712第4期杨 杰 等:基于最小角度三角化填充的枝干点云根部空洞修补根据封闭方向决定i还是i3 6 0-e n d f o ri f 中最小角度值m a x1 8 0 -t h e n b r e a ke n d i f找到中最小角度值对应的边界点uti f|u(t-1)m o dru(t+1)m o dr|kl t h e n去掉C中的边界点ut和与之相连的边,并连接u(t-1)m o dru(t+1)m o dre l s eu t定义为点u(t-1)m o dr和u(t+1)m o dr的中点Q Q u t将C中的边界点ut和与之相连的边分别用u t和u(t-1)m o dru t、u tu(t+1)m o dr取代e n d i fe n d w h i l e其中,条件“空洞未修补完整”可以由研究者的需要所确定,例如判断当前的空洞多边形面积是否大于某一值等,而若未作约束以t r u e替代即可,因为依靠最小角度是否满足程序继续的要求仍可以作为判断循环终止的依据,本试验采用后者,不采用约束。不论是自行确定的“空洞未修补完整”还是对最小角度的约束,事实上是防止中心过密与计算机浮点数所带来的无限循环问题。对于每一轮找到最小角度值对应的边界点的处理见图3。此外,算法中,根据方向决定i还是i3 6 0-,是指多边形某一个顶点ui所在的内角的角度i应当由该顶点到与之相连的2条边的2个顶点u(i-1)m o dr,u(i+1)m o dr的2个向量uiu(i-1)m o dr,uiu(i+1)m o dr的夹角根据多边形封闭方向确定(表3),其中u,1,u,2分别表示顶点u的横坐标与纵坐标。图3 三角化填充过程F i g.3 P r o c e s s o f t r i a n g u l a r f i l l i n g表3 顶点内角角度的确定方法T a b l e 3 D e t e r m i n a t i o n m e t h o d o f i n t e r n a l a n g l e s f r o m v e r t i c e s条件1条件2封闭方向条件3iu(i-1)m o dr,1=ui1u(i-1)m o dr,2u(i+1)m o dr,1顺时针ui1ui2逆时针ui1u(i+1)m o dr,1u(i-1)m o dr,1ui1令u(i+1)m o dr,2=ui2-u(i-1)m o dr,2ui1-u(i-1)m o dr,1(u(i+1)m o dr,1-u(i-1)m o dr,1)+u(i-1)m o dr,2u(i-1)m o dr,1u(i+1)m o dr,2顺时针u(i+1)m o dr,2ui1逆时针u(i+1)m o dr,2u(i+1)m o dr,21.2.4 后处理 在填充后,令q i=q i1 q i2 hTQ,其中,q iQ,修补的空洞点云Q由每一个点qi=R-1q i构成。按照前述方法得到的修复的空洞点所形成的面与根部点云间可能会存在一定的间隙。判断间隙是否存在的依据可以表述为:存在Q中某一边界点qj,若它在一定范围r内的近邻点中没有任何属于原枝干点云的点,则存在空隙。r可以取原枝干点云在不存在重复点的情况下的分辨率(或称点云密度,定义为点云中每一个点与其最近点的距离的均值)。若存在空隙,只需将拟合平面上半部分内的根部边界点云投影至该平面上所形成的点云加入到空812西北林学院学报3 8卷 洞修补的点云。最后,为防止重复点对后续编程实现时造成影响,将空洞点云加入原枝干点云后,需要去除重复点,或者利用k d t r e e以较小的半径最邻近搜索,将存在于非常小范围邻域内的邻居点从点云中移除。若想使空洞修补的点云尽可能地与原枝干点云的点分布密度相接近,则半径的选取可以点云分辨率为准。1.3 试验环境试验环境见表4。表4 试验环境T a b l e 4 E x p e r i m e n t a l e n v i r o n m e n t项目配置/版本号操作系统W i n d o w s 1 1专业版版本2 1 H 2处理器1 1 t h G e n I n t e l(R)C o r e(TM)i 7-1 1 6 5 G 7 2.8 0 GH z内存1 6.0 G BV i s u a l S t u d i o C o mm u n i t y 2 0 1 91 6.1 1.1 1P C L1.1 1.1B o o s t1.7 4(P C L 1.1 1.1第三方库自带)E i g e n3(P C L 1.1 1.1第三方库自带)2 结果与分析2.1 不同的搜索半径对边界点云检测的影响该枝干点云的点数为2 4 6 6 2 5,点云分辨率=0.0 0 6 6 3 2,用参数K=1 0搜索进行法线估计,设置参数rb e=2 0、m=4、E p s=1 0、M i n P t s=3获取根部边界点云,一般来说,rb e=1 0 即可,由于本试验的点云密度高,而在根部某一侧上点云略微稀疏,若仍这样取会使获得的根部边界点云过多地包括稀疏一侧的点云,效果差,因而后续试验均在取rb e=2 0 的条件下进行。图4为试验数据在某一角度观察下的根部点云以及rb e=1 0 与rb e=2 0 时获得的根部边界点云。2.2 不同的对空洞边界形状的影响由原理部分可知,在阶段2中会对最终结果影响的参数为,而的选取应当尽可能贴合点集。为了便于直观展示,以向z轴正方向作为观察方向观察根部点云,不同的得到的空洞边界形状见图5。图4 根部边界获取结果的比较F i g.4 C o m p a r i s o n b e t w e e n a c q u i s i t i o n r e s u l t s o f r o o t b o u n d a r y 由图5可知,当显著大于6时,凹包的形状不断接近凸包的形状,因而无法找到空洞;而略小于6时,凹包未能够涵盖全部的点,并且在显著小于6时,凹包不能涵盖到绝大部分点,此时的空洞边界与凸包非常接近,也不正确;当=6时得到的空洞边界是相对最正确的,以此继续后续试验。2.3 不同的k,对修补结果的影响由原理部分可知,参数k影响新增点的数量和分布,而参数决定是否停止修补。对比不同k,对修补结果的影响见图6。用*表示填充的点云的分辨率,表示填充的点云中离空洞边界多边形质心最近的点与质心的直线距离,比较图6中1 6种情况。*与越靠近,即=|*-|越接近0,填充的点云分辨率越接近原枝干点云的分辨率;若较大,说明根部中心并没有得到填充,填充的点云并不能完整地覆盖整个根部截面。因此理想的修复效果应为*与枝干点云分辨率接近,且须尽可能小。n*表示填充的点云点数。结合图6和表5可知,在一定范围内对修补结果毫无影响,而超过了这个范围后,重建结果十分912第4期杨 杰 等:基于最小角度三角化填充的枝干点云根部空洞修补糟糕,而由原理部分可知,也不能取值过小,不然会造成无限循环,而取值大并不总是没有影响,因而取0.0 5 能够保证在其他枝干点云上的可用性。当k=2.4时,中心偏右的一块较大的区域中未有新增点,在现有的研究中,k取1.2与1.8相比,非常接近,而k=1.8时的更小,这说明根部中心的点云空洞更小一些,结合图像可知,此时点的密度与边界点云更为接近,并不像k=1.2时集中直观上与多条线段相类似,分布相对分散,符合理想的修补效果。后续以参数k=1.8,=0.0 5 继续试验。2.4 算法性能分析在前述参数设定的条件下分别测量所提出算法的用时与最大内存使用,其中最大内存使用是指该阶段中内存峰值与运行本研究算法前内存的差值,结果 为:总 运 行 时 间 为2 7.7 6 6 s,阶 段1用 时2 5.0 7 8 s;最大内存使用为3 6 MB(出现在阶段1),输出时相较于执行算法前额外增加了3 MB。阶段1用时 较 多 且 内 存 用 量 大 是 由 点 云 的 法 线 估 计造成。以枝干骨架为例,对比未作空洞修补与作过空洞修补的枝干点云建立出的效果(图7),以枝干点云的根部质心作为根部骨架点改进前后定量分析的基准,由于计算根部骨架点的点云与根部点云质心是不同的,因而偏移距离总是0,而偏移距离越小,则与根部中心越契合。试验表明,未作空洞修补的根部骨架点偏移距离为0.1 6 2 0 4 6 0,而作过空洞修补的根部骨架点偏移距离为0.0 1 6 3 2 3 0,仅为前者的约1/1 0。图5 对空洞边界形状的影响F i g.5 I n f l u e n c e s o n t h e h o l e s h a p e w i t h d i f f e r e n t 022西北林学院学报3 8卷 表5 不同k,时的*,n*T a b l e 5*,n*o f d i f f e r e n t k,/()k=0.6k=1.2k=1.8k=2.40.0 5*=0.0 0 2 4 4 1*=0.0 0 4 3 9 5*=0.0 0 8 9 0 0*=0.0 1 6 6 8 9=0.0 0 4 1 9 1=0.0 0 2 2 3 7=0.0 0 2 2 6 8=0.0 1 0 0 5 7=0.0 0 7 0 8 2=0.0 1 9 2 4 3=0.0 1 3 6 8 8=0.0 0 5 1 6 4n*=1 9 8 2n*=7 4 6n*=2 5 5n*=9 35*=0.0 0 2 4 4 1*=0.0 0 4 3 9 5*=0.0 0 8 9 0 0*=0.1 6 6 8 9=0.0 0 4 1 9 1=0.0 0 2 2 3 7=0.0 0 2 2 6 8=0.0 1 0 0 5 7=0.0 0 7 0 8 2=0.0 1 9 2 4 3=0.0 1 3 6 8 8=0.0 0 5 1 6 4n*=1 9 8 2n*=7 4 6n*=2 5 5n*=9 31 5*=0.0 0 8 2 1 2*=0.0 0 8 2 9 7*=0.0 0 8 9 0 0*=0.1 6 6 8 9=0.0 0 1 5 8=0.0 0 1 6 6 5=0.0 0 2 2 6 8=0.0 1 0 0 5 7=0.1 4 5 1 9 8=0.1 4 1 4 3 7=0.0 1 3 6 8 8=0.0 0 5 1 6 4n*=9 3n*=8 0n*=2 5 5n*=9 32 5*=0.0 2 2 3 7 5*=0.0 3 8 5 3 0*=0.0 4 1 7 5 8*=0.0 8 0 5 5 6=0.0 1 5 7 4 3=0.0 3 1 8 9 8=0.0 3 5 1 2 6=0.0 7 3 9 2 4=0.1 4 5 3 2 3=0.1 4 3 6 4 3=0.1 4 2 4 1 1=0.1 4 3 3 8 7n*=2 3n*=1 6n*=1 5n*=7图6 k,对修补结果的影响F i g.6 I n f l u e n c e s o n f i l l i n g e f f e c t s w i t h d i f f e r e n t k,进一步选取同一样地其他美洲黑杨的枝干点云在各自相对最佳参数下进行空洞修复,它们的参数、枝干点云形态与修复前后的骨架见图8。由图8可知,设置适当参数进行空洞修补后,骨架的根部偏移均有所改善。因此,本方法能够明显改善树木枝干骨架根部中心偏移问题,证实了本研究的有效性和实用性。3 结论与讨论针对现有点云修补算法不能直接适用于枝干根122第4期杨 杰 等:基于最小角度三角化填充的枝干点云根部空洞修补图7 效果对比F i g.7 E f f e c t c o m p a r i s o n部点云的空洞修补,提出的基于最小角度三角化填充的枝干点云根部空洞修补,通过试验验证其能够较为快速且较好地修复根部的空洞,但仍有改进的空间。1)P C L提供的点云法线估计用时和内存使用较高,更快的法线估计算法能够进一步降低二者的需求。2)该算法需要设定的参数较多,并且某些参数根据经验所设定时并不能很好地得到预期的效果,而设置不合理的参数会严重影响到修补结果,因而需要研究者多次尝试方可确定。可以直接决定参数图8 验证F i g.8 V a l i d a t i o n或给出合理的参数选取范围以帮助研究者决定的启发式算法。由图4可知,搜索半径应为边界点云近乎在一个平面或近似为扁筒壁状,若难以找到合适的搜索半径,则选取1个畸变较小的边界点云时的搜索半径,并对边界点云中的点过滤使其满足形状上的要求。此外,本研究也有助于其他不规则物体的点云中某一或某些平面缺损时的修补,相较于以往只对平面点云或近似 平面的地面 点 云 拓 宽 了 适 用 的场景。参考文献:1 曹伟,陈动,史玉峰,等.激光雷达点云树木建模研究进展与展望J.武汉大学学报:信息科学版,2 0 2 1,4 6(2):2 0 3-2 2 0.C A O W,C H E N D,S H I Y F.P r o g r e s s a n d p r o s p e c t o f L i D A R p o i n t c l o u d s t o 3 D t r e e m o d e l sJ.G e o m a t i c s a n d I n f o r m a