留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用Delaunay细分进行噪声点云曲面重建

李国俊 李宗春 孙元超 李伟 黄志勇

李国俊, 李宗春, 孙元超, 李伟, 黄志勇. 利用Delaunay细分进行噪声点云曲面重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
引用本文: 李国俊, 李宗春, 孙元超, 李伟, 黄志勇. 利用Delaunay细分进行噪声点云曲面重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
Citation: LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513

利用Delaunay细分进行噪声点云曲面重建

doi: 10.13203/j.whugis20140513
详细信息
    作者简介:

    李国俊, 硕士, 主要从事点云曲面重建和时频计量研究。1010551750@qq.com

  • 中图分类号: P237.3;TP751

Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds

More Information
    Author Bio:

    LI Guojun, master, specializes in surface reconstruction and time-frequency measurement. E-mail:1010551750@qq.com

  • 摘要: 针对噪声点云曲面重建,提出了一种基于Delaunay细分的曲面重建算法。首先以点云法向为约束,采用抗差估计的方法拟合球面近似局部曲面;然后利用沿坐标轴的包围盒树结构(axis aligned bounding boxes tree,AABB-tree)快速搜索与线段相交的曲面包围球,以各包围球球心为初值、半径为可信区间,并行化迭代计算出线段与球面的首个交点,该交点可近似为线段与曲面交点;最后不断地插入交点进行Delaunay细分,从而网格化曲面。实验结果表明,当点云噪声较大时,该方法可以快速、稳健地重建出高质量曲面,且曲面重建精度较高。
  • 图  1  本文算法流程图

    Figure  1.  Flowchart of the Proposed Algorithm

    图  2  线段与曲面交点

    Figure  2.  Segment-Surface Intersection

    图  3  AABB-tree球面索引

    Figure  3.  Sphere Searching with AABB-tree

    图  4  Delaunay细分

    Figure  4.  Delaunay Refinement

    图  5  噪声点云曲面重建

    Figure  5.  Noisy Point Clouds Surface Reconstruction

    图  6  噪声与理想兔子点云

    Figure  6.  Noisy and Free Bunny Point Cloud

    图  7  重建曲面偏差图

    Figure  7.  Surface Reconstruction Errors

    图  8  三角面质量分布

    Figure  8.  Triangle Quality Proportion

    图  9  某雕像曲面重建

    Figure  9.  Status Surface Reconstruction

    图  10  雕像偏差图

    Figure  10.  Status Errors

    表  1  本文算法参数

    Table  1.   Algorithm Parameters

    0 0.4% 0.7% 1.0% 雕像
    k 15 15 15 15 15
    λ 1.10 1.70 2.00 2.50 1.25
    αα 10 10 10 10 10
    αr 2.32 2.01 1.74 1.56 1.50
    αd 2.32 2.01 1.74 1.56 1.50
    Vb 362 272 362 272 362 272 362 272 930 730
    Ve 40 377 40 598 41 258 41 311 265 429
    F 80 453 80 949 82 285 82 444 526 425
    下载: 导出CSV

    表  2  曲面重建耗时/s

    Table  2.   Surface Reconstruction Time/s

    0 0.4% 0.7% 1.0% 雕像
    APSS 190.3 290.8 416.3 626.1 -
    泊松算法 31.8 33.1 33.7 33.4 109.5
    本文算法 136.6 226.5 407.1 747.7 535.8
    下载: 导出CSV
  • [1] 朱德海.点云库PCL学习教程[M].北京:北京航空航天大学出版社, 2012, 359-360

    Zhu Dehai. Point Cloud Library PCL Learning Tutorial[M]. Beijing:Beihang University Press, 2012, 359-360
    [2] Amenta N, Choi S, Kolluri R K. The Power Crust, Unions of Balls, and the Medial Axis Transform[J]. Computational Geometry, 2001, 19(2):127-153
    [3] Dey T K, Goswami S. Provable Surface Reconstruction from Noisy Samples[C]. The Twentieth Annual Symposium on Computational Geometry, Brooklyn, NY, 2004
    [4] Kuo C, Yau H. A Delaunay-Based Region-Growing Approach to Surface Reconstruction from Unorganized Points[J]. Computer-Aided Design, 2005, 37(8):825-835 doi:  10.1016/j.cad.2004.09.011
    [5] 张剑清, 李彩林, 郭宝云.基于切平面投影的散乱数据点快速曲面重建算法[J].武汉大学学报·信息科学版, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml

    Zhang Jianqing, Li Cailin, Guo Baoyun. A Fast Surface Reconstruction Algorithm for Unorganized Points Based on Tangent Plane Projection[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml
    [6] Yau H, Yang T, Jian H. A Region-Growing Algorithm Using Parallel Computing for Surface Reconstruction from Unorganized Points[J]. Advances in Engineering Software, 2013, 59:29-37 doi:  10.1016/j.advengsoft.2013.03.002
    [7] Alexa M, Behr J, Cohen-Or D, et al. Point Set Surfaces[C]. The Conference on Visualization, San Diego, California, USA, 2001
    [8] Guennebaud G, Gross M. Algebraic Point Set Surfaces[C]. ACM Transactions on Graphics, San Diego, 2007
    [9] Campos R, Garcia R, Alliez P, et al. Splat-Based Surface Reconstruction from Defect-Laden Point Sets[J]. Graphical Models, 2013, 75(6):346-361 doi:  10.1016/j.gmod.2013.08.001
    [10] Kazhdan M, Bolitho M, Hoppe H. Poisson Surface Reconstruction[C]. The Fourth Eurographics Symposium on Geometry Processing, Cagliari, 2006
    [11] Alliez P, Cohen-Steiner D, Tong Y, et al. Voronoi-Based Variational Reconstruction of Unoriented Point Sets[C]. Symposium on Geometry Processing, Barcelona, Spain, 2007
    [12] Mullen P, de Goes F, Desbrun M, et al. Signing the Unsigned:Robust Surface Reconstruction from Raw Pointsets[C]. Computer Graphics Forum, Lyon, France, 2010
    [13] Giraudot S, Cohen-Steiner D, Alliez P. Noise-Adaptive Shape Reconstruction from Raw Point Sets[C]. Computer Graphics Forum, Genova, Italy, 2013
    [14] Gander W, Golub G H, Strebel R. Least-Squares Fitting of Circles and Ellipses[J]. BIT Numerical Mathematics, 1994, 34(4):558-578 doi:  10.1007/BF01934268
    [15] Pratt V. Direct Least-Squares Fitting of Algebraic Surfaces[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4):145-152 doi:  10.1145/37402
    [16] Yuanxi Y. Robust Estimation for Dependent Observations[J]. Manuscripta Geodaetica, 1994, 19(1):10-17
    [17] Adamson A, Alexa M. Approximating and Intersecting Surfaces from Points[C]. The 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Aachen, 2003
    [18] Boissonnat J, Oudot S. Provably Good Sampling And Meshing of Surfaces[J]. Graphical Models, 2005, 67(5):405-451 doi:  10.1016/j.gmod.2005.01.004
    [19] Lorensen W E, Cline H E. Marching Cubes:A High Resolution 3D Surface Construction Algorithm[C]. The 14th Annual Conference on Computer Graphics and Interactive Techniques, Anaheim, 1987
    [20] CGAL. Computational Geometry Algorithm Library[EB/OL]. http://www.cgal.org, 2015
    [21] Béchet E, Cuilliere J, Trochu F. Generation of a Finite Element MESH from Stereolithography (STL) Files[J]. Computer-Aided Design, 2002, 34(1):1-17 doi:  10.1016/S0010-4485(00)00146-9
  • [1] 黄攀, 唐劲松, 钟何平.  干涉合成孔径声呐复图像配准分段曲面拟合法 . 武汉大学学报 ● 信息科学版, 2021, 46(8): 1259-1264. doi: 10.13203/j.whugis20190306
    [2] 付永健, 李宗春, 何华.  点云内在属性因子驱动的自适应滚球算法 . 武汉大学学报 ● 信息科学版, 2020, 45(3): 353-361. doi: 10.13203/j.whugis20180390
    [3] 黄攀, 唐劲松, 钟何平, 徐魁.  基于有理函数曲面拟合的InSAS复图像配准新方法 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 601-607. doi: 10.13203/j.whugis20170167
    [4] 钟德云, 王李管, 毕林.  复杂矿体模型多域自适应网格剖分方法 . 武汉大学学报 ● 信息科学版, 2019, 44(10): 1538-1544. doi: 10.13203/j.whugis20170304
    [5] 李鹏程, 徐青, 邢帅, 刘志青, 张军军.  利用波形信息的加权曲面拟合LiDAR点云滤波 . 武汉大学学报 ● 信息科学版, 2018, 43(3): 420-427. doi: 10.13203/j.whugis20150377
    [6] 张继贤, 段敏燕, 林祥国, 臧艺.  激光雷达点云电力线三维重建模型的对比与分析 . 武汉大学学报 ● 信息科学版, 2017, 42(11): 1565-1572. doi: 10.13203/j.whugis20150385
    [7] 杨军, 林岩龙, 张瑞峰, 王小鹏.  一种大规模点云k邻域快速搜索算法 . 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
    [8] 詹银虎, 郑勇, 张超, 张中凯, 李铸洋, 马高峰.  球面圆拟合算法及其在测月定向中的应用 . 武汉大学学报 ● 信息科学版, 2015, 40(11): 1514-1519. doi: 10.13203/j.whugis20130562
    [9] 何海清, 黄声享, 陈婷.  一种顾及粗差的径向神经网络高程曲面拟合法 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 547-551. doi: 10.13203/j.whugis20130041
    [10] 吴军, 李伟, 彭智勇, 刘荣, 唐敏.  融合形态学灰度重建与三角网分层加密的LiDAR点云滤波 . 武汉大学学报 ● 信息科学版, 2014, 39(11): 1298-1303.
    [11] 曾齐红, 毛建华, 李先华, 刘学锋.  机载LiDAR点云数据的建筑物重建研究 . 武汉大学学报 ● 信息科学版, 2011, 36(3): 321-324.
    [12] 李佳田, 李佳, 段平, 余莉.  球面Delaunay三角网的透视投影算法 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1116-1119.
    [13] 张剑清, 李彩林, 郭宝云.  基于切平面投影的散乱数据点快速曲面重建算法 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 757-762.
    [14] 刘亚文, 宋守东.  利用航空影像、点云数据和矢量图进行简单房屋三维重建方法研究 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 894-897.
    [15] 谷川, 潘国荣, 施贵刚, 陈兴权.  基于遗传算法的曲面拟合参数辨识 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 983-986.
    [16] 田峰敏, 徐定杰, 李宁.  Delaunay三角化中特征约束细分嵌入算法 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 358-361.
    [17] 赵煦, 周克勤, 闫利, 邓非.  基于激光点云的大型文物景观三维重建方法 . 武汉大学学报 ● 信息科学版, 2008, 33(7): 684-687.
    [18] 曾齐红, 毛建华, 李先华, 刘学锋.  激光雷达点云平面拟合过滤算法 . 武汉大学学报 ● 信息科学版, 2008, 33(1): 25-28.
    [19] 王解先.  工业测量中一种二次曲面的拟合方法 . 武汉大学学报 ● 信息科学版, 2007, 32(1): 47-50.
    [20] 张孟君, 舒红, 刘艳, 王涛.  基于空间曲面拟合的自适应阈值选取方法 . 武汉大学学报 ● 信息科学版, 2006, 31(5): 395-398.
  • 加载中
图(10) / 表(2)
计量
  • 文章访问数:  1563
  • HTML全文浏览量:  103
  • PDF下载量:  325
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-08-04
  • 刊出日期:  2017-01-05

利用Delaunay细分进行噪声点云曲面重建

doi: 10.13203/j.whugis20140513
    作者简介:

    李国俊, 硕士, 主要从事点云曲面重建和时频计量研究。1010551750@qq.com

  • 中图分类号: P237.3;TP751

摘要: 针对噪声点云曲面重建,提出了一种基于Delaunay细分的曲面重建算法。首先以点云法向为约束,采用抗差估计的方法拟合球面近似局部曲面;然后利用沿坐标轴的包围盒树结构(axis aligned bounding boxes tree,AABB-tree)快速搜索与线段相交的曲面包围球,以各包围球球心为初值、半径为可信区间,并行化迭代计算出线段与球面的首个交点,该交点可近似为线段与曲面交点;最后不断地插入交点进行Delaunay细分,从而网格化曲面。实验结果表明,当点云噪声较大时,该方法可以快速、稳健地重建出高质量曲面,且曲面重建精度较高。

English Abstract

李国俊, 李宗春, 孙元超, 李伟, 黄志勇. 利用Delaunay细分进行噪声点云曲面重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
引用本文: 李国俊, 李宗春, 孙元超, 李伟, 黄志勇. 利用Delaunay细分进行噪声点云曲面重建[J]. 武汉大学学报 ● 信息科学版, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
Citation: LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
  • 随着三维激光扫描技术的发展,获取物体海量点云已更加便捷、快速。但是,由于各种因素的影响,原始点云并非理想点云数据。虽然点云预处理技术能够在一定程度上提高点云质量,但仍可能存在部分缺陷,例如点云噪声、拼接误差、点云欠采样等。因此,研究噪声点云的曲面重建仍然十分必要。

    根据重建曲面和数据点之间的关系,可将曲面重建方法分为插值法和逼近法两大类[1]

    插值法重建曲面完全通过原始数据点,主要包括两种方法:(1)基于Delaunay三角化方法[2-3]。该方法首先对点云进行Delaunay三角剖分,然后根据一定的拓扑准则抽取出与原始曲面同胚的受限Delaunay三角形(restricted Delaunay triangle,RDT)。(2)基于区域生长方法[4-6]。该方法按照特定准则,不断选择新点加入当前区域边界,生成新三角形并更新边界,直到遍历所有点得到初始剖分,最后优化初始剖分。由于插值法完全通过数据点,当原始点云噪声较大时,则很难保证曲面重建精度。

    逼近法重建曲面不一定通过原始数据点,主要分为三种:(1)局部拟合法[7-9]。首先利用邻域点进行局部几何体拟合,然后通过反复迭代投影逼近原始曲面,最后提取隐函数的等值面即为待重建曲面。该方法具有一定的抗噪性,但点云噪声较大时,容易出现过度拟合导致错误曲面特征。(2)全局函数法[10-11]。利用法向或协方差矩阵等与曲面微分的关系建立全局能量模型,并求解出采样点函数值使得目标函数最大化。该方法可以抵抗少量离群点的影响,但是容易出现局部过度平滑现象。(3)距离函数法[12-13]。利用点到点的距离建立稳健的无符号距离场,并根据距离函数属性判断其符号。该方法可以抵抗离群点影响,但是重建精度较低,且对点云密度要求较高。

    根据上述分析,本文提出了一种基于Delaunay细分(Delaunay refinement,DR)的曲面重建算法。该算法通过局部球面拟合克服点云噪声影响,利用沿坐标轴的包围盒树结构(axis aligned bounding boxes tree,AABB-tree)和并行化技术快速计算线段与曲面交点,最后采用Delaunay细分方法可以生成不同分辨率曲面。

    • 利用Delaunay细分进行曲面重建方法的关键在于如何准确、快速计算出线段与曲面的交点。为了确保精度,采用以法向为约束的拟合球面近似局部曲面,在选取权函数时,采用抗差选权迭代法,克服了不同质量点云权重的不确定性。为了提高速度,对曲面包围球进行AABB-tree分割,快速查找与线段相交的包围球,针对各包围球,并行化迭代计算出线段与曲面的近似交点。本文算法流程如图 1所示。

      图  1  本文算法流程图

      Figure 1.  Flowchart of the Proposed Algorithm

    • 球面拟合方法主要分为两类:(1)几何法[14]。其准则是所有点到拟合球面的距离平方和最小。一般采用线性化迭代最小二乘求解,若初值给定不准确,容易出现迭代发散或陷入局部最优的情况。当拟合曲面接近平面时,目标函数不一定收敛于最小值。(2)代数法[15]。根据采样点建立隐函数,其零等值面即为拟合球面。该方法计算简单、速度快且适合平面模型。

      一般球面代数方程可表示为:

      $$ f\left( \mathit{\boldsymbol{x}} \right) = \left[{\begin{array}{*{20}{c}} \mathit{\boldsymbol{1}}&{{\mathit{\boldsymbol{x}}^{\rm{T}}}}&{{\mathit{\boldsymbol{x}}^{\rm{T}}}\mathit{\boldsymbol{x}}} \end{array}} \right]u\left( \mathit{\boldsymbol{x}} \right) = 0 $$ (1)

      式中,u(x)=[u0 u1 u2]T表示代数球面系数; f(x)表示点x到拟合球面的距离场函数,其梯度方向与点法向相等。

      $$ \begin{array}{l} n\left( \mathit{\boldsymbol{x}} \right) = \nabla f\left( \mathit{\boldsymbol{x}} \right) = \left[{\begin{array}{*{20}{c}} \mathit{\boldsymbol{1}}&{{\mathit{\boldsymbol{x}}^{\rm{T}}}}&{{\mathit{\boldsymbol{x}}^{\rm{T}}}\mathit{\boldsymbol{x}}} \end{array}} \right]\nabla u\left( \mathit{\boldsymbol{x}} \right) + \\ \left[{\begin{array}{*{20}{c}} \mathit{\boldsymbol{0}}&{{\mathit{\boldsymbol{I}}_3}}&{\mathit{\boldsymbol{2}}{\mathit{\boldsymbol{I}}_3}\mathit{\boldsymbol{x}}} \end{array}} \right]u\left( \mathit{\boldsymbol{x}} \right) \end{array} $$ (2)

      式中,∇表示一阶导数; I3表示3阶单位阵。实际上,式(2)可近似表示为:

      $$ n\left( \mathit{\boldsymbol{x}} \right) \approx \left[{\begin{array}{*{20}{c}} \mathit{\boldsymbol{0}}&{{\mathit{\boldsymbol{I}}_3}}&{\mathit{\boldsymbol{2}}{\mathit{\boldsymbol{I}}_3}\mathit{\boldsymbol{x}}} \end{array}} \right]u\left( \mathit{\boldsymbol{x}} \right) $$ (3)

      由式(3)可知,以法向为约束进行球面拟合,其主要优点是拟合方程为线性方程,通过简单的点坐标与法向运算便可得到球面方程系数。以法向偏差最小化为目标函数,球面拟合法方程可表示为:

      $$ \begin{array}{l} \left[{\begin{array}{*{20}{c}} {\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right){\mathit{\boldsymbol{I}}_3}} }&{2\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right){\mathit{\boldsymbol{p}}_i}} }\\ {{{\left( {2\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right){\mathit{\boldsymbol{p}}_i}} } \right)}^2}}&{4\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right)\mathit{\boldsymbol{p}}_i^{\rm{T}}{\mathit{\boldsymbol{p}}_i}} } \end{array}} \right]\left[{\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{u}}_1}}\\ {{\mathit{\boldsymbol{u}}_2}} \end{array}} \right] = \\ \left[{\begin{array}{*{20}{c}} {\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right){\mathit{\boldsymbol{n}}_i}} }\\ {2\sum {{w_i}\left( \mathit{\boldsymbol{x}} \right)\mathit{\boldsymbol{p}}_i^{\rm{T}}{\mathit{\boldsymbol{n}}_i}} } \end{array}} \right] \end{array} $$ (4)

      式中,piniwi(x)分别表示参与拟合点坐标、法向和权重。进一步解算可得:

      $$ \begin{array}{l} {\mathit{\boldsymbol{u}}_2} = \beta \frac{{\sum {w_i}\mathit{\boldsymbol{p}}_i^{\rm{T}}{\mathit{\boldsymbol{n}}_i}-\sum {{\tilde w}_i}\mathit{\boldsymbol{p}}_i^{\rm{T}}\sum {w_i}{\mathit{\boldsymbol{n}}_i}}}{{2(\sum {w_i}\mathit{\boldsymbol{p}}_i^{\rm{T}}{\mathit{\boldsymbol{p}}_i}-\sum {{\tilde w}_i}\mathit{\boldsymbol{p}}_i^{\rm{T}}\sum {w_i}{\mathit{\boldsymbol{p}}_i})}}\\ {\mathit{\boldsymbol{u}}_1} = \sum {{\tilde w}_i}{\mathit{\boldsymbol{n}}_i}-2{\mathit{\boldsymbol{u}}_2}\sum {{\tilde w}_i}{\mathit{\boldsymbol{p}}_i}\\ {\mathit{\boldsymbol{u}}_0} = - \mathit{\boldsymbol{u}}_1^{\rm{T}}\sum {{\tilde w}_i}{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{u}}_2}\sum {{\tilde w}_i}\mathit{\boldsymbol{p}}_i^{\rm{T}}{\mathit{\boldsymbol{p}}_i} \end{array} $$ (5)

      式中,${{\tilde w}_i} = {w_i}/\sum {{w_j}} $; β表示场函数尺度系数,通过调整β可以平衡拟合点与拟合法向的权重。为保证‖∇f(x)‖与点法向长度一致,本文限定‖∇f(x)‖=1,即

      $$ \mathit{\boldsymbol{u}}_1^{\rm{T}}{\mathit{\boldsymbol{u}}_1}-4{\mathit{\boldsymbol{u}}_0}{\mathit{\boldsymbol{u}}_2} = 1 $$ (6)

      拟合球面与原始曲面的近似程度主要受两个因素影响:

      1)邻域点。邻域点过多或过少容易导致过度平滑或产生错误细节特征。常用的邻域点有球邻域点、k-邻域点、基于密度邻域点和基于曲率邻域点。为了兼顾效率与最优化邻域点,本文根据点云密度确定邻域点:

      $$ {\mathit{\boldsymbol{h}}_\mathit{\boldsymbol{p}}} = \{ \mathit{\boldsymbol{q}}|\left\| {\mathit{\boldsymbol{p}} - \mathit{\boldsymbol{q}}} \right\| \le \lambda {\left\| {\mathit{\boldsymbol{q}} - {N_k}\left( \mathit{\boldsymbol{q}} \right)} \right\|_{max}}\} $$ (7)

      式中,hp为点p的邻域点; Nk(q)表示qk-邻域点集合; λ表示球域影响因子,随着λ不断增大,hp不断增加。通过调整kλ可适应不同密度点云,可以有效减弱点云噪声影响。

      2)权函数。在点云法向求解中,可能存在部分点法向不准确或方向不一致,选择合理的权函数可以弥补点云法向缺陷。目前,常用的权函数有高斯权函数和近似高斯权函数,此类权函数在一定程度上能够优化拟合结果,但对粗差数据较为敏感。本文采用抗差估计的IGG3[16]方案不断地对点云法向重新定权。

      $$ {w_i} = \left\{ \begin{array}{l} {w_i}, \left| {\overline {{v_i}} } \right| \le {k_0}\\ {w_i}\frac{{{k_0}({k_1}-\left| {\overline {{v_i}} } \right|)}}{{\left| {\overline {{v_i}} } \right|({k_1}-{k_0})}}, {k_0} \le \left| {\overline {{v_i}} } \right| \le {k_1}\\ 0, \left| {\overline {{v_i}} } \right| \ge {k_1} \end{array} \right. $$ (8)

      式中,|vi|=|vi|/σ0为标准化残差分量;σ0为中误差;k0k1为模型参数,取值在1.0~1.5和2.5~8.0之间。本文取k0=1.0,k1=2.5,w0=1.0,一般经过2~3次迭代便可有效剔除粗差数据。

    • 计算线段l与曲面S的交点r即求解线段l与局部拟合球面s的交点。类似于移动最小二乘法(moving least square,MLS)[7]迭代投影的过程,本文采用迭代计算线段与球面交点的方法逼近真实交点。理论上,随着迭代次数增加,|f(ri)|不断减小,交点ri越来越逼近直线l与曲面S的真实交点[17],如图 2所示。

      图  2  线段与曲面交点

      Figure 2.  Segment-Surface Intersection

      算法具体流程如下:

      1)给定点r的初始值r0,利用点r的邻域点拟合球面s

      2)计算直线l与拟合球面s的交点r1,若存在两个交点,则取其中点。

      3)令r=r1,重复(1)、(2),直到‖ri-ri-1‖≤ε, ‖ri-r0‖≤di>t

      其中,ε=1×10-7t=4。步骤(3)要求‖ri-r0‖≤d,主要是为了清除偏离点r0过大的明显错误交点。

      为了快速获取点r0,采用以点pi为球心、ρi为半径的球面Bi包围曲面Sρi表示可能包含点r的球形半径,一般取值为点pi至第5~8邻近点的距离。显然,当ρi足够大时,若直线l与曲面S相交,则必定与∑Bi相交,如图 3所示。

      图  3  AABB-tree球面索引

      Figure 3.  Sphere Searching with AABB-tree

      将所有的球面以空间包围盒形式进行AABB-tree分割,可快速获取与直线l相交的球面。一般存在多个与线段相交的球面,且各球面相互独立,因此可进行并行化运算。与多项式局部曲面拟合相比,采用球面拟合更适合计算线段与曲面的交点,无需迭代运算、速度更快,且拟合精度与二次多项式情形相当。

    • 当点云密度足够时,Delaunay细分方法可得到受限Delaunay三角面,该三角面与原始曲面同胚[18]。每个受限Delaunay三角形都有一个曲面Delaunay球,该球以对偶的Voronoi边与曲面交点为球心,外接受限Delaunay三角形,曲面Delaunay球内不包含其他任何采样点,如图 4所示。

      图  4  Delaunay细分

      Figure 4.  Delaunay Refinement

      Delaunay细分方法首先从原始点云中随机选取部分点进行Delaunay剖分,然后不断插入新的Voronoi边与曲面交点,直到所有三角形的曲面Delaunay球满足以下3个条件:

      1)角度条件。球内的受限Delaunay三角形角度都大于 αα

      2)半径条件。球半径小于 αr

      3)距离条件。球心到受限Delaunay三角形距离小于 αd

      其中,αα一般取值10°~30°,αrαd取为若干倍${d_{{\rm{den}}}} = \frac{1}{n}\sum\limits_{i = 1}^n {\left( {\frac{1}{k}\sum\limits_{j = 1}^{j = k} {\left\| {{\mathit{\boldsymbol{p}}_i}-\mathit{\boldsymbol{q}}_i^j} \right\|} } \right)} $;qij为点pik-邻域点,k取值6~12。当αrαd时,生成的三角面具有较高的质量。

      与移动立方体(marching cubes,MC)算法[19]相比,Delaunay细分方法只需计算线段与曲面交点,且具有严格的理论证明,生成的三角面质量较高,但是该方法不适合处理曲面尖锐特征处,主要是尖锐特征处点云密度难以保证。

    • 为验证本文算法的有效性,利用CGAL库[20]在Win 7系统、Intel Core2 T6670 CPU @2.2 GHz的计算机上实现了本文算法。实验点云数据为兔子(362 272个点),并在此基础上增加三组标准差为0.4%点云包围盒半径(bounding box radius,BBR)、0.7% BBR、1.0% BBR的模拟高斯噪声点云数据。几种不同算法曲面重建效果如图 5所示。

      图  5  噪声点云曲面重建

      Figure 5.  Noisy Point Clouds Surface Reconstruction

      图 5可以看出,当标准差大于0.4%BBR时,Power Crust算法和Robust Cocone算法无法准确地重建出完整曲面,APSS、泊松算法和本文算法的重建曲面为2-流形面且具有较高的重建质量。

      进一步对比APSS算法、泊松算法和本文算法的曲面重建精度。由于362 272个点的兔子点云含有一定噪声,若采用该点云作为参考点云,原始点云自身的噪声可能影响分析结果。因此,采用无噪声的35 947个点的兔子点云作为参考点云更为合理,如图 6所示。

      图  6  噪声与理想兔子点云

      Figure 6.  Noisy and Free Bunny Point Cloud

      当标准差为1.0%BBR时,三种算法曲面重建偏差图如图 7所示。

      图  7  重建曲面偏差图

      Figure 7.  Surface Reconstruction Errors

      图 7可以看出,在高曲率区域,如兔子的脖子、尾巴和耳朵等处,APSS算法和本文算法的偏差明显小于泊松算法,这主要是在高曲率区域,采用拟合球面可以更准确地逼近原始曲面。在平滑区域,点云法向估计较为准确,3种算法的曲面重建精度相当。

      与MC算法提取等值面不同,本文采用Delaunay细分方法生成的三角面质量更高。文献[21]给出了一种常用的三角面质量评价方案。

      $$ Q = \frac{{\sqrt {12} }}{{{d_{{\rm{max}}}}}}\sqrt {\frac{{\mathop \prod \limits_{i = 1}^3 (\bar d-{d_i})}}{{\bar d}}}, 0 < Q < 1 $$ (9)

      式中,di表示三角形第i条边长;dmax表示最长的边长;$\bar d = \sum {{d_i}/2} $。Q越大表示三角面越接近等边三角形,即三角面质量越高。

      APSS和本文算法重建三角面质量分布如图 8所示。

      图  8  三角面质量分布

      Figure 8.  Triangle Quality Proportion

      图 8中可以看出,本文算法生成的三角面质量明显优于APSS,且不存在尖锐三角面。

      最后,利用Riegl VZ400扫描仪实测某雕像,并利用本文算法进行曲面重建,如图 9所示。

      图  9  某雕像曲面重建

      Figure 9.  Status Surface Reconstruction

      图 9(c)中可以看出,重建曲面的三角面质量较高,且点云密度均匀。图 9(b)中部分区域点云密度过高,导致球面拟合的邻域很小,该区域的曲面细节特征更为明显。因此,当点云密度与曲面曲率成正比时,本文算法的曲面重建效果更为理想。

      进一步验证本文算法较泊松算法在曲面重建精度方面的优越性,结果如图 10所示。

      图  10  雕像偏差图

      Figure 10.  Status Errors

      图 10中可以看出,本文算法曲面重建精度明显优于泊松算法曲面重建,但是在多站点云拼接处,如雕像中线、左侧胸口处等,明显存在精度差异。因此,在点云数据采集及预处理阶段,应尽量保证点云密度一致、精度相当、拼接准确。

      本文算法曲面重建效果与部分参数设置密切相关,具体情况如表 1所示。表 1中,VbVe表示重建前后点个数,F表示重建三角面个数。随着点云噪声不断增大,需要逐步增大λ以确保拟合球面的邻域足够大。此时,在迭代计算线段与曲面交点时,近似交点将被更多的曲面包围球包含,大量球面搜索将会极大增加算法耗时。因此,当重建三角面个数相当时,随着点云噪声不断增大,本文算法耗时将不断增大,如表 2所示。

      表 1  本文算法参数

      Table 1.  Algorithm Parameters

      0 0.4% 0.7% 1.0% 雕像
      k 15 15 15 15 15
      λ 1.10 1.70 2.00 2.50 1.25
      αα 10 10 10 10 10
      αr 2.32 2.01 1.74 1.56 1.50
      αd 2.32 2.01 1.74 1.56 1.50
      Vb 362 272 362 272 362 272 362 272 930 730
      Ve 40 377 40 598 41 258 41 311 265 429
      F 80 453 80 949 82 285 82 444 526 425

      表 2  曲面重建耗时/s

      Table 2.  Surface Reconstruction Time/s

      0 0.4% 0.7% 1.0% 雕像
      APSS 190.3 290.8 416.3 626.1 -
      泊松算法 31.8 33.1 33.7 33.4 109.5
      本文算法 136.6 226.5 407.1 747.7 535.8

      表 2中可以看出,当点云噪声较小时,本文算法的曲面重建耗时略低于APSS。随着点云噪声不断增大,本文算法的曲面重建耗时迅速增加,高于APSS。泊松算法的耗时不受点云噪声影响,明显低于APSS和本文算法。一般情况下,本文算法的耗时随着αr的减小呈平方倍数增加,所生成的三角面数量也呈平方倍数增加。

    • 本文针对噪声点云提出了一种基于Delaunay细分的曲面重建算法,利用不同噪声水平的模拟数据,从曲面重建精度和质量角度,对比了Power Crust算法、Robust Cocone算法、APSS算法、泊松算法和本文算法的曲面重建效果。结果表明,当点云噪声较大时,Power Crust算法和Robust Cocone算法重建曲面失败, 本文算法较泊松算法和APSS算法分别在曲面重建精度和质量上具有一定的优势。

参考文献 (21)

目录

    /

    返回文章
    返回