-
本文中的算法是首先对输入的点云数据构建k维(k-dimensional,k-D)树用于空间索引[18],再采用R邻域内重心差异准则粗提取边界点,对粗提取的边界点在局部投影面上精确提取边界点。本文中算法的具体流程如图 1所示。
-
3维激光扫描获取的点云数据是离散且无序的,需建立空间索引结构提高数据检索效率。k-D树是点云常用的数据组织结构,可以快速检索采样点的邻域点。对于非边界点,其R邻域内点集分布较为均匀,邻域内点集的重心坐标与采样点的距离较小;对于边界点,其R邻域内点集集中分布在采样点的一侧,邻域内点集的重心坐标与采样点的距离较大,如图 2所示。因此, 本文中从采样点R邻域内点集重心坐标与采样点位置的距离D出发,利用边界点与非边界点中D的差异性粗提取边界点集。
Figure 2. Location map of barycenter points in the neighborhood of non-boundary points and boundary points R
粗提取的具体流程如下所述。
(1) 构建k-D树。采用快速分类的分割方法建立k-D树,把指定维度的值放在根上,在这个维度上较小数值放在左子树、较大的放在右子树,然后分别在左右子树上重复该过程,直至最后一个树仅有一个点。
(2) 计算R邻域内点集重心。通过k-D树检索采样点R邻域内点,利用下式计算该邻域内点集重心坐标:
$ C(\bar X, \bar Y, \bar Z) = \left( {\frac{{\sum\limits_{i = 1}^n {{x_i}} }}{n}, \frac{{\sum\limits_{i = 1}^n {{y_i}} }}{n}, \frac{{\sum\limits_{i = 1}^n {{z_i}} }}{n}} \right) $
(1) 式中,$ C(\bar{X}, \bar{Y}, \bar{Z})$为重心点坐标,n为邻域内点个数,(xi, yi, zi)为邻域内第i个点的坐标。
(3) 计算重心点与采样点距离值D。设定距离阈值δ,若D≥δ,则采样点被标记为边界点,同时保存该点的索引。
(4) 遍历所有点。重复步骤(2)和步骤(3),对所有点进行判定,完成边界点的粗提取,得到粗提取边界点集的索引。
图 3为边界点粗提取结果图。图中的点云数据包括点云内部边界点和点云外部边界点,粗提取的边界点集中包含边界点、少量毛刺噪声点、边界边缘内部点。粗提取方法可以有效地剔除大部分非边界点,可以为后续精提取边界点提高效率。
-
粗提取的边界点中包含了边界点、部分边界边缘内部点和少量毛刺噪声点,精提取的目的就是将边界点从粗提取的点集中分离处理来。目前精确提取边界点的方法有很多,参考文献中提出的基于邻近点最大夹角的方法能够有效的提取边界点。将采样点及其邻域内点集投影至最小二乘拟合的微切平面上,寻找采样点与邻域内点连线构成的最大夹角εmax,若εmax大于设定的角度阈值,则该点为边界点。
依据粗提取点集在原始点云中的索引,利用粗提取过程中构建的k-D树,检索粗提取点p邻域内点集$\boldsymbol{X}=\left\{\left(x_{i}, y_{i}, z_{i}\right) \mid 0 \ll i \ll m\right\} $,用最小二乘法求解该点集的微切平面参量。将一般平面方程ax+by+cz+d=0, (c≠0)改写成z=a0x+a1y+a2z,其中$a_{0}=-\frac{a}{c} $$a_{1}=-\frac{b}{c}, a_{2}=-\frac{d}{c} $。依据最小二乘拟合这m+1个点的平面方程,使其满足$ S = \sum\limits_{i = 0}^m {{{\left( {{a_0}{x_i} + {a_1}{y_i} + {a_2}{z_i}} \right)}^2}} $最小,即$\frac{\partial S}{\partial a_{k}}=0, k=0, 1, 2 $。可通过解方程组(2)式得到a0,a1,a2,再通过(3)式求解X内点在微切平面的坐标$q^{\prime}\left(x_{i}^{\prime}, y_{i}^{\prime}, z_{i}^{\prime}\right) $:
$ \left[ {\begin{array}{*{20}{c}} {\sum\limits_{i = 0}^m {x_i^2} }&{\sum\limits_{i = 0}^m {{x_i}} {y_i}}&{\sum\limits_{i = 0}^m {{x_i}} }\\ {\sum\limits_{i = 0}^m {{x_i}} {y_i}}&{\sum\limits_{i = 0}^m {y_i^2} }&{\sum\limits_{i = 0}^m {{y_i}} }\\ {\sum\limits_{i = 0}^m {{x_i}} }&{\sum\limits_{i = 0}^m {{y_i}} }&{m + 1} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{a_0}}\\ {{a_1}}\\ {{a_2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\sum\limits_{i = 0}^m {{x_i}} {z_i}}\\ {\sum\limits_{i = 0}^m {{y_i}} {z_i}}\\ {\sum\limits_{i = 0}^m {{z_i}} } \end{array}} \right] $
(2) $ \left\{\begin{array}{l} x_{i}{ }^{\prime}=\frac{\left(b^{2}+c^{2}\right) x_{i}-a b y_{i}-a c z_{i}-a d}{a^{2}+b^{2}+c^{2}} \\ y_{i}{ }^{\prime}=\frac{-a b x_{i}+\left(a^{2}+c^{2}\right) y_{i}-b c z_{i}-b d}{a^{2}+b^{2}+c^{2}} \\ z_{i}{ }^{\prime}=\frac{-a c x_{i}-b c y_{i}+\left(a^{2}+b^{2}\right) z_{i}-c d}{a^{2}+b^{2}+c^{2}} \end{array}\right. $
(3) 在微切平面内,通过(4)式得到邻域投影点q′与采样点p(x, y, z)的单位方向向量。这样就将点p邻域内点分布在以点p为圆心的单位圆上,如图 4a所示。选择单位圆内任意方向向量$\boldsymbol{p q}_{i}{ }^{\prime} $为起始方向,计算$\boldsymbol{p q}_{i}{ }^{\prime} $与微切平面法向量n的叉积v,分别计算其它方向向量与$\boldsymbol{p q}_{i}{ }^{\prime} $和v的夹角αi,βi,如图 4b所示。
若βi≥90°,则αi=360°-αi。将αi从小到大排序,通过(5)式计算相邻向量间的夹角,最大夹角阈值一般设置为90°:
$ \begin{gathered} p \boldsymbol{q}_{i}^{\prime \prime}=\frac{\boldsymbol{p} \boldsymbol{q}_{i}{ }^{\prime}}{\left|\boldsymbol{p} \boldsymbol{q}_{i}{ }^{\prime}\right|}= \\ \frac{\left\{x-x_{i}{ }^{\prime}, y-y_{i}{ }^{\prime}, z-z_{i}{ }^{\prime}\right\}}{\sqrt{\left(x-x_{i}{ }^{\prime}\right)^{2}+\left(y-y_{i}{ }^{\prime}\right)^{2}+\left(z-z_{i}{ }^{\prime}\right)^{2}}} \end{gathered} $
(4) $ \delta_{i}=\left\{\begin{array}{l} \alpha_{i+1}-\alpha_{i}, (i=1, 2, \cdots, m-1) \\ 360^{\circ}+\alpha_{1}-\alpha_{i}, (i=m) \end{array}\right. $
(5) 图 5为精提取结果图。可以看出,基于邻近点最大夹角的方法剔除了少量毛刺噪声点和边界边缘内部点,能够精确提取边界点。对粗提取过程中筛选出的点集进行精确提取,避免对每一个原始点进行微切平面拟合及精确判定,故能够极大地提高边界点的提取效率。
-
选取扫描的桌子点云数据验证本文中算法的可行性,再采用瑞格VZ-1000扫描的白塔数据对本文中算法的提取精度进行分析。实验在配置为i5-6200U CPU 2.30GHz、内存8GB、Windows 10 64位操作系统的PC机运行,在MATLAB R2016a软件中编写脚本实现本文中的算法、参考文献[8]中的算法和参考文献[16]中的算法。
-
原始点云平均间距为0.001m,共454943个点,首先对原始点云精简,采用网格法下采样[19-20],网格间距为0.01m,精简后点云个数为20988个,如图 6a所示。参考文献[8]中提取的边界结果如图 6b所示。本文中算法粗提取中R取3倍网格间距,即R=0.3m,距离D取网格间距,即点云平均间距0.01m,粗提结果如图 6c所示,粗提取过程中最大夹角阈值设置为90°,最终提取的边界点结果如图 6d所示。参考文献[16]中同样采用先粗提取后精提取的思路,其粗提取的结果如图 6e所示,精提取结果如图 6f所示。由实验结果可以看出,本文中算法相较于参考文献[16]中的能更为完整地提取边界点云,验证了本文中算法的可行性。
表 1中对3种不同边界提取方法的提取结果进行了比较。参考文献[8]中可视为不进行粗提取,直接对原始数据进行精提取,总耗时最长,但能得到精确的边界点集。参考文献[16]中粗提取的点云个数比本文中的方法多,但是精提取后点云个数比本文中方法少,说明本文中粗提取的点集包含更多的边界点,本文中粗提取的精度更高,因此后续精提取的时间能缩短35.54%。本文中提出的粗提取方法运行时间相较于参考文献[16]中的缩短了21.21%,总耗时相较于参考文献[8]中的缩短了28.21%,较参考文献[16]中的缩短了22.89%。
Table 1. Comparison of operation efficiency of different boundary extraction methods
-
对白塔点云数据先进行网格法下采样,网格大小为0.01m,共55049个点,如图 7a所示。同样粗提取中R取0.03m,距离D取0.01m,最大夹角阈值取90°,本文中边界点的提取结果如图 7b所示,参考文献[8]中提取的白塔边界点结果如图 7c所示,参考文献[16] 中提取的边界点结果如图 7d所示。
表 2中对3种边界提取方法进行了比较分析。参考文献[8]中提出的方法能够有效精确地提取边界点,且本文中和参考文献[16]中精提取方法都与参考文献[8]中边界提取方法一致,故可以假设参考文献[8]中提取的边界点是精确且完整的,通过将本文中和参考文献[16]中的提取结果与参考文献[8]中的提取结果进行比较,分析本文中算法的提取精度。对于本文中和参考文献[16]中提取的结果,通过与参考文献[8]中的提取结果进行同名点检索,若本文中或参考文献[16]中提取的点能在参考文献[8]中提取的点集中能检索到同名点,则该点被标记为正确提取点,否则为错误提取点。分析表 2中正确率和运行时间可知,本文中算法相对与参考文献[16]不仅耗时较少,而且精度更高,这是由于在粗提取过程中本文中采用了更简单、更有效的边界点判定规则。
表 2 Comparison of extraction precision between different boundary extraction methods
层次化点云边界快速精确提取方法研究
Research on the method of rapid and accurate extraction of boundary points by hierarchy
-
摘要: 为了提高依据邻近点最大夹角提取边界点方法的提取效率,提出了一种层次化快速精确提取边界点的方法。先对任意采样点检索其R邻域内点集,依据R邻域内点集重心点坐标与采样点的距离粗提取边界点,然后将粗提取的边界点及其邻域点投影至微切平面,通过各邻近点与采样点的方向向量求取相邻向量间的最大夹角,再依据最大夹角精提取边界点。通过理论分析和点云数据实验验证了该算法的可行性。结果表明,该算法相较于传统的方法,能缩短22.11%的运行时间,但精度降低5.23%;相较于其它层次化提取方法,在缩短10.99%的运行时间的同时精度提高7.17%。该研究为点云3维重建中边界提取提供了参考。Abstract: In order to improve the extraction efficiency of the boundary point extraction method based on the maximum Angle of adjacent points, a hierarchical fast and accurate boundary point extraction method was proposed. R in the neighborhood at any sampling point set was firstly retrieved, followed by the crude extraction of boundary point according to the distance from the center of gravity point coordinates to the sampling point in the R neighborhood point set. The crude extract of boundary points and their neighborhood points were then projected to the tangent plane, and the maximum angle between adjacent vectors was calculated through the adjacent points and sampling points in the direction of the vector, the final accurate boundary point was then extracted based on the maximum angle. Through theoretical analysis and point cloud data experiment, the feasibility of the algorithm was verified. The results show that this algorithm can respectively shorten the running time by 22.11% and the accuracy by 5.23% compared with the traditional method, and can respectively shorten the running time by 10.99% and improve the accuracy by 7.17% compared with other hierarchical extraction methods. This study provides a reference for boundary extraction in point cloud 3-D reconstruction.
-
Key words:
- laser technique /
- boundary extraction /
- R neighborhood /
- the tangent plane
-
Table 1. Comparison of operation efficiency of different boundary extraction methods
表 2 Comparison of extraction precision between different boundary extraction methods
-
[1] WU H, LIU H Y, DING G F, et al. Automatic extraction of power lines from laser point clouds in complex environments[J]. Laser Technology, 2020, 44(4): 509-514(in Chinese). [2] XU L G, GUO T, WU Sh H. et al. Fast extraction and reconstruction of power line based on point cloud data features[J]. Laser Technology, 2020, 44(2): 244-249(in Chinese). [3] WANG Sh Y, TAO Sh X, YANG F, et al. Laser range gated imaging target recognition based on convolutional neural network[J]. Laser & Optoelectronics Progress, 2019, 56(2): 21001 (in Chinese). [4] FENG M, YANG M L, XIA Y H, et al. 3-D modeling of high-steep cliffs combining with 3-D laser scanning and oblique photogrammetry[J]. Science of Surveying and Mapping, 2020, 45(1): 99-107 (in Chinese). [5] WU K, AO J F, FANG Q. Extraction of building's feature lines based on 3-D laser scanning technology[J]. Laser Technology, 2012, 36(4): 553-556(in Chinese). [6] LIU Y, SUN Sh Y. Laser point cloud denoising based on principal component analysis and surface fitting[J]. Laser Technology, 2020, 44(4): 497-502(in Chinese). [7] KE Y L, FAN Sh Q. Research on direct extraction of boundary from point clouds[J]. Chinese Journal of Mechanical Engineering, 2004, 40(9): 116-120(in Chinese). doi: 10.3901/JME.2004.09.116 [8] SUN D Zh, FAN Zh X, LI Y R. Automatic extraction of boundary characteristic from scattered data[J]. Huazhong University of Science & Technology(Natural Science Edition), 2008, 36(8): 82-84(in Chinese). [9] CHEN Y R, WANG Y B, PENG Zh J, et al. Improved algorithm for extraction of boundary characteristic point from scattered point cloud[J]. Computer Engineering and Applications, 2012, 48(23): 77-180 (in Chinese). [10] SU Y L, PING X L. Point cloud edge extraction algorithm based on Gauss map clustering[J]. Laser & Optoelectronics Progress, 2019, 56(11): 111506(in Chinese). [11] CHEN X, TONG X H. Research on points cloud hole filling algorithm and accuracy in triangle mesh[J]. Bulletin of Surveying and Mapping, 2013, 59(4): 1-3(in Chinese). [12] LIN S, TIAN L Y, BI J X, et al. Accurate calculation of single-tree crown volume based on 3-D laser scanning data[J]. Science of Surveying and Mapping, 2020, 45(8): 115-122(in Chinese). [13] WANG Z Y, MA H Ch, XU H G, et al. Novel algorithm for fast extracting edges from massive point clouds[J]. Computer Engineering and Applications, 2010, 46(36): 213-215(in Chinese). [14] HE H, LI Z C, LI G J, et al. Surface reconstruction for scattered point clouds with adaptive α-shape[J]. Journal of Computer Applications, 2016, 36(12): 3394-3397 (in Chinese). [15] LI W J, LI Sh N, QIU J, et al. Boundary detection of multi-density point cluster using convex hull retracted method[J]. Science of Surveying and Mapping 2014, 39(9): 126-129(in Chinese). [16] JIANG Ch Ch, LIU K, SHU M. Algorithm for fast and accurate boundary points extraction[J]. Journal of Optoelectronics · Laser, 2020, 31(5): 531-538(in Chinese). [17] HAN Y Ch, HOU H, BAI Y R, et al. A closed point cloud edge extraction algorithm using edge coefficient[J]. Laser & Optoelectronics Progress, 2018, 55(11): 111003 (in Chinese). [18] BENTLEY J L. Multidimensional binary search trees used for associative searching [J]. Journal of Communications of the ACM, 1975, 18(9): 509-517. doi: 10.1145/361002.361007 [19] WANG H T, ZHANG L Y, DU J, et al. Simplification and error analysis based on implicit surface for measuring point-sets[J]. Journal of Image & Graphics, 2007, 12(11): 2114-2118. [20] MARTIN R R, STROUD I A, MARSHALL A D. Data reduction for reverse engineering[J]. Reccad, Deliverable Document Copernicus Project, 1997, 10(1): 85-100.