改进的点云数据三维重建算法 下载: 2416次
1 引言
科技的快速发展推动着数字化数据采集设备的日益完善,点云重建问题已经变得至关重要。以图像为基础的三维重建不能直接提供待重建物体的空间信息,故而很难对待重建物体各个角度进行精准还原,而三维点云数据可以完美地呈现物体表面结构信息、空间信息以及物体的模型细节,能有效避免传统的基于图像的三维重建无法直接提供空间信息的问题。虽然日益完善的点云采集设备可以快速从物体表面扫描获得大量点云数据,但是大规模的点云数据使设备存储和计算处理效率低下,导致重建出的模型表面失真,整体效果模糊。目前点云的三维重建对多个领域有着重要的研究价值,因此重建的模型往往会包含形貌各异、内部拓扑结构不一样、曲面多值或有孔洞等特征,这些对重建算法的适应度、算法实现效率及消耗时间等作出了要求[1]。因此对采集到的海量点云进行一系列的降噪、滤除冗余数据、法向量重定向等操作为后续高效率的曲面重建是很有必要的。
目前点云的表面重建已经成为研究的一个活跃领域,常用的三维重建方法主要有贪婪投影三角化算法、移动立方体以及泊松曲面重建算法,但是它们各自存在一定的缺点。贪婪投影三角化在三角化时不能同时进行曲面平滑和孔洞修复;移动立方体重建后会包含大量的三角形面片数据且信息丢失严重;泊松曲面重建不能很好捕捉重建表面的局部细节。文献[ 2]基于体积的Delaunay三角测量的方法,对空间要求、计算时间以及点分布进行约束,最终重建结果与物体的实际形状一致。文献[ 3]中改进的基于Delaunay三角剖分算法,通过创建一个三角网格插入点完成重建,用于从无组织的扫描点数据集合中自动重建模型,算法具有简单、高效和均匀等优点。文献[ 4]利用基于点云单应性的迭代最近点配准算法进行重建,该算法稳健性强、收敛速度快、收敛精度高,有助于三维模型的快速重建。文献[ 5]使用全局拟合方法,将隐函数定义为以点为中心的径向基函数(RBF)的总和,但缺点是RBF(多谐波)是全局支持的,并且不衰减,数据量大的点云集重建时会涉及自适应RBF减少和快速多极方法。文献[ 6]引入基于Voronoi的方法处理噪声输入数据,虽然这些技术可以处理输入数据中的小孔和中等欠采样区域,但它们不太适用于在3D数据采集中经常出现的具有大孔的数据集。文献[ 7]提出将体积扩散应用于带符号的距离场表示中,该方法能有效处理拓扑复杂的孔的算法,文献[ 8]在这个算法的基础上使用偏微分方程来演化距离场,类似于图像的修复技术。文献[ 9]通过网格和隐式曲面之间的新误差度量,对三角形网格构造隐式曲面,新误差度量采用三角形内点和顶点的加权函数来拟合隐式曲面,隐式曲面可以控制三角形的曲面和顶点之间的近似误差,该方法生成的细分单元格少,且在处理具有较少顶点的三角形网格时更稳定。文献[ 10]提出一种用于放射治疗(RT)解剖结构三维表面重建的新方法,该方法通过结合图像体素分割处理和使用小波的隐式表面流方法得到人工横截面轮廓,并根据网格质量指标对结果进行定性和定量评估。
针对以上算法在三维重建时存在曲面平滑与孔洞修复较差、重建物体表面局部细节不能很好捕捉、重建后出现大量数据信息丢失等缺点,本文提出一种改进的三维点云重建算法。经过实验验证,本文算法能有效解决重建后物体边缘易产生未封闭曲面、表面粗糙、孔洞等一些问题,并成功重建,在一定程度上减少了重建消耗时间,提高了重建效率,最终得到的实验结果比较理想。
2 改进的点云重建算法
本文算法的主要思想是:首先通过统计滤波器对点云简化去噪,噪声数据的存在会导致重建得到的物体表面不平滑,呈锯齿状;然后建立点云间拓扑结构,对点云法向量进行法向重定向,以减少法向指向的二义性;最后将具有磁盘拓扑结构的点云映射到平面,将二维三角剖分方法应用于平面参数化,为二维点提供三角形连通性,并将其传输回三维点云,形成网格曲面。
本文算法具体步骤如下所示。
1)对输入的PCD(PCD代表点云的类型是.pcd类型)点云使用统计滤波器移除离群点。
2)在降噪后的数据中选择初始点区域增长构建初始网络,构建过程中通过定义相邻三角网格法向量的夹角来进行约束,若某点法线方向偏离设定角度,该点则不连接到样本点上,最终分离出相对较为平缓的区域。
3)对分割后的各部分点云数据进行平面拟合;将各个点云映射到拟合后的平面上,并对其进行二维Delaunay三角剖分。根据物体表面点的法向量得到此点与法向垂直的切平面,由于二维数据点的三角化已非常成熟,因此可以先将表面点及其附近点投影到该点的切平面上,进行二维三角化,进而得到点与点之间的连接关系,通过连接关系将剖分结果映射回三维空间中。
4)孔洞修补以及网格优化。首先计算模型孔洞边界边长的平均值和每个边界点两条相邻边夹角的大小;然后获得最小夹角的边界点,计算该点相邻边界点的距离,当该距离小于两倍的平均值时增加一个三角形,不符合时增加两个三角形;更新孔洞的信息直至孔洞修补完成;对于修补之后的孔洞用最小二乘网格进行网格优化,完成模型的三维重建。
2.1 点云简化去噪
在获取点云数据时,点采样通常是不均匀的,容易在法线位置和其他地方产生噪声,丢失一些表面区域的数据。测量中的误差也会产生稀疏的离群点,这些会使估计局部点云特征(例如采样点处法向量或曲率变化率)时产生错误的数值。点云数据集中每一个点代表特别的信息,区域内点越密集表示有用的信息越多;孤立的离群点信息量较小,则所表达的信息可直接忽略。滤波处理作为预处理的第一步,若没有对噪声点、离群点处理,最终重建的结果必然会产生一定的影响。
本文主要通过统计滤波器达到滤噪的目的,如
2.2 区域增长法
区域增长法主要通过比较点法线之间的角度,将满足平滑约束的相邻点合并在一起分离出较为平缓的区域,从而完成区域的增长。算法的主要工作原理是从有最小曲率值的点开始进行区域增长,因为曲率最小的点位于平坦区域,而从最平坦的区域增长可以减少区域的总数。其过程是:1)按照点的曲率值对点进行排序,并将排序结果添加到种子点集中并找到最小曲率值点;2)计算每个相邻点与当前种子点的法线与法线之间的角度,若角度小于设定的阈值,则将该相邻点添加到当前区域中;3)测试该相邻点的曲率值,若小于设定的阈值,则将其添加到种子点集中;4)将通过两次检验的点从种子点集中去掉。当种子点集变空时表示该区域的增长已结束。
如
2.3 三角网格化
在点云三维曲面重建中,Delaunay三角网格被公认为是最优的网格,Delaunay三角网格拼接结构较为稳定,形成的网格接近正三角形,因此Delaunay三角网格被公认为是最优的三角网格[11],但海量点云的Delaunay三角网格生成效率低下,且构建过程中容易出现失真的情况。在真实的三维情况下Delaunay三角化的复杂程度增加,处理大量点云数据时耗费时间较多,且在重建过程中易出现失真、空洞等问题。为了有效降低三角化时间,提高效率,本文首先对分组后的点云用最小二乘法分别进行曲面拟合;随后将该组每一个散乱点映射到拟合平面区域S上得到点集V,通过Delaunay三角剖分算法得到点与点之间的拓扑连接关系;最后将连接关系映射回三维空间,生成物体表面在点集V的局部三角网格。
3 实验结果及分析
为了验证本文算法的有效性和可行性,基于LINUX系统之一的Ubuntu 16.04系统进行实验平台的搭建,安装必要的环境工具PCL 1.8.1、VS 2013以及点云所需的CMAKE、QT、VTK、boost库等。采用已有的bunny、horse、dragon等模型进行验证,记录本文方法处理时间并与另外两种经典方法进行比较。
为了显示本文方法的优越性,首先与泊松重建算法和基于Delaunay算法进行比较,分析算法时间复杂度。泊松重建算法是一种以融合全局和局部为基础的隐式曲面重建方法,通过求解泊松方程来得到点云模型所描述的表面信息代表的隐性方程,然后利用该方程进行等值面提取,得到具有几何实体信息的表面模型。重建后的模型表面光滑细腻,具有良好的几何表面特性和细节特性,但是其容易在重建物体边缘时产生未封闭的曲面以及存在孔洞的缺点[12]。
表 2. 不同点云重建耗时对比
Table 2. Comparison of reconstruction time of different point cloudss
|
表 1. 不同点云去噪前后的点云数量对比
Table 1. Comparison of number of point clouds before and after denoising of different point clouds
|
图 6. 基于三种算法的dragon重建。(a)基于本文算法;(b)基于Delaunay算法;(c)基于泊松算法
Fig. 6. Dragon reconstruction based on three algorithms. (a) Based on proposed algorithm; (b) based on Delaunay algorithm; (c) based on Poisson algorithm
4 结论
利用统计滤波器对点云简化去噪,随后选择初始点进行区域增长,进行网格化完成重建。通过实验结果可知,本文算法相比于泊松算法时间和精度都大大提高,相比于Delaunay算法虽然时间稍多,但是大大减少了孔洞的存在,提高了模型重建的精度。本文方法能够有效地解决实际重建过程中出现的噪声、孔洞、粗糙等问题,能构建更加规则的三角形网格,实现去除伪封闭曲面达到高度修复的目的。
[1] 张珍铭. 基于Delaunay三角化的三维散乱点云曲面重塑算法研究[D]. 南京: 南京航空航天大学, 2006.
Zhang ZM. Research on Delaunay-based surface reconstruction algorithms from 3D unorganized point clouds[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2006.
[2] Lorensen W E, Cline H E. Marching cubes: a high resolution 3D surface construction algorithm[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 163-169.
[3] Bernardini F, Mittleman J, Rushmeier H, et al. The ball-pivoting algorithm for surface reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4): 349-359.
[4] 韦盛斌, 王少卿, 周常河, 等. 用于三维重建的点云单应性迭代最近点配准算法[J]. 光学学报, 2015, 35(5): 0515003.
[5] Carr JC, Beatson RK, Cherrie JB, et al. Reconstruction and representation of 3D objects with radial basis functions[C]∥Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2001, August 12-17, 2001, Los Angeles, California, USA. New York: ACM, 2001: 67- 76.
[6] Dey TK, GoswamiS. Tight cocone: a water-tight surface reconstructor[C]∥Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA. New York: ACM, 2003: 127- 134.
[7] DavisJ, Marschner SR, GarrM, et al. Filling holes in complex surfaces using volumetric diffusion[C]∥Proceedings. First International Symposium on 3D Data Processing Visualization and Transmission, June 19-21, 2002, Padova, Italy. New York: IEEE, 2002: 7396003.
[8] VerderaJ, CasellesV, BertalmioM, et al. Inpainting surface holes[C]∥Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429), September 14-17, 2003, Barcelona, Spain. New York: IEEE, 2003: 903- 906.
[10] MoriconiS, ScalcoE, BroggiS, et al. High quality surface reconstruction in radiotherapy: cross-sectional contours to 3D mesh using wavelets[C]∥2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), August 25-29, 2015, Milan, Italy. New York: IEEE, 2015: 4222- 4225.
[11] 李国俊, 李宗春, 孙元超, 等. 利用Delaunay细分进行噪声点云曲面重建[J]. 武汉大学学报(信息科学版), 2017, 42(1): 123-129.
Li G J, Li Z C, Sun Y C, et al. Using Delaunay refinement to reconstruct surface from noisy point clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129.
[12] 刘涛. 泊松隐式曲面重建算法及其并行化研究[D]. 太原: 中北大学, 2018.
LiuT. Research on parallelizing Poisson algorithm of implicit surface reconstruction[D]. Taiyuan: North University of China, 2018.
Article Outline
庞正雅, 周志峰, 王立端, 叶珏磊. 改进的点云数据三维重建算法[J]. 激光与光电子学进展, 2020, 57(2): 021102. Pang Zhengya, Zhou Zhifeng, Wang Liduan, Ye Juelei. Improved Three-Dimensional Reconstruction Algorithm for Point Cloud Data[J]. Laser & Optoelectronics Progress, 2020, 57(2): 021102.