网站地图
下载:
-
近年来, 3维激光扫描技术在快速高精度获取3维空间信息中发挥着重要作用[1-2]，基于点云的目标识别和3维重建一直都是研究热点，边界提取是目标识别[3]、3维重建[4-5]过程中的重要步骤。精确的边界不仅影响着曲面几何特征的表达，还对重建后曲面模型的质量和精度有着重要的作用[6]。
目前边界点云的提取算法较多，主要有栅格划分法、微切平面法、三角网法和凸包类算法等。KE等人[7]对点云进行空间栅格划分，建立空间拓扑关系，依据栅格内是否有点检索边界，这种算法速度快，但是受点云密度和栅格大小影响较大，且提取精度不高。基于微切平面的方法是将待判定点及其邻域点投影到微切平面上，再依据一定的准则判别该点是否属于边界点。SUN等人[8]提出计算微切平面内投影点所构成的最大夹角作为判定依据。CHEN等人[9]通过模拟点与点间的拉力的合力判断待定点是否是边界点。SU等人[10]先计算各点法向量，然后将法向量投影至高斯球中，通过高斯映射法线聚类，依据聚类结果提取边界点，基于微切平面的方法效率太低，对每个点都需要投影，然后根据判断条件精确判定，耗时较长。基于三角网的方法，CHEN等人[11]提出通过遍历所有三角形的边长，依据边长阈值确定边界边，这种方法需要事先构建三角网，耗时较多。LIN等人[12]也提出了一种过滤三角网的方法提取点云边界，该方法也在点云数据量较少的情况下能取得较好的效果，在海量数据中提取效率较低。基于凸包类算法较为典型的是alpha shapes[13-14]，这种方法在2维点集中能取得较好的结果，但是在3维点集中提取结果不佳。LI等人[15]提出了凸壳内缩法提取离散点边界，但是无法提取内部空洞边界。JIANG等人[16]为了提高边界提取的效率，先采用HAN[17]提出的模拟点间拉力的方法先粗提取边界点，再依据SUN提出的最大夹角准则精提取边界点，该方法能够一定程度提高边界点提取效率，但是粗提取的判断准则计算量依然较大。
针对上述算法中边界点提取耗时较长的问题，本文中提出一种层次化提取边界点的方法。通常边界点只占总点云数据的少部分，对每个点都进行精确判定效率不高，可以采取简单的判定方法: 先对整体点云进行初步筛选，提取出边界点潜在点集，再对边界点潜在点集进行精提取，从而能够实现边界点的高效提取。
-
本文中的算法是首先对输入的点云数据构建k维(k-dimensional，k-D)树用于空间索引[18]，再采用R邻域内重心差异准则粗提取边界点，对粗提取的边界点在局部投影面上精确提取边界点。本文中算法的具体流程如图 1所示。
Figure 1. Algorithm flow chart
-
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为边界点粗提取结果图。图中的点云数据包括点云内部边界点和点云外部边界点，粗提取的边界点集中包含边界点、少量毛刺噪声点、边界边缘内部点。粗提取方法可以有效地剔除大部分非边界点，可以为后续精提取边界点提高效率。
Figure 3. Crude extraction of boundary points
-
粗提取的边界点中包含了边界点、部分边界边缘内部点和少量毛刺噪声点，精提取的目的就是将边界点从粗提取的点集中分离处理来。目前精确提取边界点的方法有很多，参考文献中提出的基于邻近点最大夹角的方法能够有效的提取边界点。将采样点及其邻域内点集投影至最小二乘拟合的微切平面上，寻找采样点与邻域内点连线构成的最大夹角ε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所示。
Figure 4. The included angle on the projection plane of neighborhood point
若β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为精提取结果图。可以看出，基于邻近点最大夹角的方法剔除了少量毛刺噪声点和边界边缘内部点，能够精确提取边界点。对粗提取过程中筛选出的点集进行精确提取，避免对每一个原始点进行微切平面拟合及精确判定，故能够极大地提高边界点的提取效率。
Figure 5. Essence extraction of boundary points
-
选取扫描的桌子点云数据验证本文中算法的可行性，再采用瑞格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]中的能更为完整地提取边界点云，验证了本文中算法的可行性。
Figure 6. Table boundary points extract results
表 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所示。
Figure 7. Extraction results of white tower boundary points
表 2中对3种边界提取方法进行了比较分析。参考文献[8]中提出的方法能够有效精确地提取边界点，且本文中和参考文献[16]中精提取方法都与参考文献[8]中边界提取方法一致，故可以假设参考文献[8]中提取的边界点是精确且完整的，通过将本文中和参考文献[16]中的提取结果与参考文献[8]中的提取结果进行比较，分析本文中算法的提取精度。对于本文中和参考文献[16]中提取的结果，通过与参考文献[8]中的提取结果进行同名点检索，若本文中或参考文献[16]中提取的点能在参考文献[8]中提取的点集中能检索到同名点，则该点被标记为正确提取点，否则为错误提取点。分析表 2中正确率和运行时间可知，本文中算法相对与参考文献[16]不仅耗时较少，而且精度更高，这是由于在粗提取过程中本文中采用了更简单、更有效的边界点判定规则。
表 2 Comparison of extraction precision between different boundary extraction methods
-
本文中提出了一种快速精确提取边界点的方法，针对传统的基于邻近点最大夹角提取边界点方法进行改进，首先依据R邻域点集重心坐标与采样点的距离粗提取边界点，将大量的非边界点剔除，提高提取效率，再依据邻近点最大夹角精确提取边界点。实验表明本文中提出的方法能够快速精确的提取边界点，层次化快速边界提取方法中尽管缩短了提取时间，但是降低了提取精度，通过白塔数据实验表明，相对于传统的依据邻近点最大夹角提取边界点方法，本文中的方法在损失5.23%的精度下能缩短22.11%的运行时间，相较于其它层次化提取方法，本文中的提取精度在提高7.17%的同时能缩短10.99%的运行时间。但本文中的方法易受到点云密度的影响，相关阈值的选取都与点云密度有关，对密度分布不均匀的数据提取的效果不佳，下一步研究方向为提高算法的自适应程度。
层次化点云边界快速精确提取方法研究
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
-
Figure 2. Location map of barycenter points in the neighborhood of non-boundary points and boundary points R
Figure 4. The included angle on the projection plane of neighborhood point
a—schematic diagram of projection point direction vector distribution b—the angle between projection points
-
[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. -
点击查看大图
图(7) / 表(2)
计量
- 文章访问数: 4201
- HTML全文浏览量: 3071
- PDF下载量: 29
- 被引次数: 0
