融合改进场力和判定准则的点云特征规则化

刘庆; 章光; 陈西江

doi:doi:10.3788/CJL201946.0404009

中国激光, 2019, 46 (4): 0404009, 网络出版: 2019-05-09

融合改进场力和判定准则的点云特征规则化下载： 697次

Point Cloud Feature Regularization Based on Fusion of Improved Field Force and Judging Criterion

论文大纲

刘庆 ^*章光陈西江

作者单位

武汉理工大学资源与环境工程学院, 湖北武汉 430079

激光光学激光扫描特征提取改进的三次B样条拟合边界线 laser optics laser scanning feature extraction improved cubic B-spline fitting boundary lines

AI 词云图 AI一句话精读 AI短摘要

注：本部分内容由 AI 自动生成，请您知悉。

摘要

为了快速有效地获取散乱点云中的边界特征点和边界线,提出了一种融合改进场力和判定准则的点云特征规则化算法。利用改进的k-d(k-dimensional)树搜索k邻域,以采样点及其k邻域为参考点集拟合微切平面并向该平面投影,在微切平面上建立局部坐标系以将三维坐标转化成二维坐标,利用场力和判定准则识别边界特征点;依据矢量偏转角度和距离对边界特征点进行排序连接;通过改进的三次B样条拟合算法对边界线进行平滑拟合。实验结果表明,该算法能够快速有效地提取边界特征点,且拟合后的边界线偏差量级为10 ^-5 m,具有较高的精度。

Abstract

In order to obtain the boundary feature points and boundary lines quickly and efficiently in the scattered point cloud, a point cloud feature regularization algorithm is proposed by means of the fusion of improved field force and judging criterion. An improved k-d (k-dimensional) tree method is first used to search the k neighbors of a sampling point. Then this sampling point and its k neighbors are used as the reference points to fit a micro-cut plane and project to this plane. The local coordinate system is established on the micro-cut plane and the three-dimensional coordinate is transformed into the two-dimensional coordinate. The boundary feature points are identified by use of field force and judging criterion. These boundary feature points are sorted and connected according to the vector deflection angle and distance. The boundary lines are smoothed by the improved cubic B-spline fitting algorithm. The experimental results show that the proposed algorithm can used to extract the boundary feature points quickly and efficiently, and the deviations of the fitted boundary lines are in the level of 10 -5 m, indicating a relatively high precision.

1 引言

近年来,随着物联网和社会物理信息系统(CPSS)的发展,激光扫描技术得到了广泛地应用^[1],如逆向工程、形状分析、物体识别、变形监测^[2-3]等。由于扫描得到的原始点云数据包含大量杂乱、无组织和不规则的点,需要对点云进行边界特征提取以提高数据的利用率。点云边界是曲面模型的重要组成部分,如何从散乱的点云数据中快速有效地提取边界线将直接影响曲面重构的效率和精度^[4]。目前,国内外许多学者对散乱点云的特征点提取展开了研究,Bazazian等^[5]通过分析由每个点的k(邻近点的数目)邻域所定义的协方差矩阵的特征值来检测尖锐边缘特征点;Hackel等^[6]使用二元分类器在点的邻域提取特征,给出每个点的轮廓分数,并进一步使用二元分类器选择最佳轮廓以达到边界特征提取的效果;Xi等^[7]依据共面条件将点云数据划分为不同的块,然后根据每个块的深度维度将其转换为二维图像,通过改进的拉普拉斯图像边缘检测方法提取每个平面的边界点;张雨禾等^[8]对点的反k近邻进行定义,并提出一种新的特征检测算子,将反k近邻的尺度作为点密度,引入特征的全局约束性信息,最后对基于密度空间聚类方法中的相关概念进行重新定义并建立新的特征识别准则,提取特征点;董伟^[9]利用k近邻搜索算法搜索k邻域,并根据邻近点确定法向量及基准面,利用基准面上探测点和邻近点的法向量夹角特性,确定建筑物边界,然后利用整体最小二乘和加权主元分析法对随机抽样一致算法进行改进,并基于该改进算法,确定折边两侧点云平面,利用两侧点云边界特性探测建筑物折边;陈朋等^[10]以点到其每3个相邻邻域点所构成平面的距离的平均值进行特征点的提取,提取的特征线更加完整,断裂线较少,受噪声影响小,但距离阈值d_min的设定受噪声和表面粗糙度的影响较大,且对曲面提取效果不好。陈义仁等^[11]在k近邻夹角算法^[12]的基础上,依据边界点和内部点的几何分布特性并通过场力和判定准则检测边界特征点。但特征点排序所采用的双向最近点搜索算法适用性差,拆分过程比较复杂,且生成的边界线不够光滑,存在多处尖角,不利于后续建模。

针对以上问题,本文对场力和算法做出改进。在将数据点向其微切平面投影时,把点的三维坐标转化成投影平面内的二维坐标,简化了每个点场力的计算;引入权重的概念将矢量偏转角度和距离同时作为排序的判定条件对边界点进行排序连接;最后将改进的三次B样条曲线拟合算法应用于边界线的拟合,得到连续光滑的边界线,实现点云特征规则化。

2 改进场力和算法提取边界特征点

2.1 改进的k-d树搜索k邻域

初始的点云数据是散乱的,只能提供物体表面的三维坐标信息,为此需要建立点云的k邻域。建立点云之间的拓扑关系能够有效地提高点云数据的处理速度和效率^[13]。传统的k-d树(在k维欧几里德空间组织点的数据结构)在处理大规模点云数据时,庞大的建树分支导致k-d树的删减代价比较大,且查询每个点的k邻域时都要遍历整个k-d树,降低了搜索效率。因此,在k-d树的基础上做出改进,利用空间动态网格^[14]划分点云并建立局部k-d树。

首先将原始点云中的每个数据点分别根据它们的x、y、z坐标值,按照升序的原则进行排序,假设任意一点P的三维排序坐标为(m,s,t)。分别在x、y、z方向上以P点为中心沿着正反两个方向依次搜索l个点,这样就得到了P点在x、y、z方向最近的2l个点。沿着三个方向搜索到的点集的交集部分形成空间网格Q,如图1所示。

图 1. 空间动态网格Q示意图

Fig. 1. Schematic of spatial dynamic grid Q

下载图片查看所有图片

对于分布不规则的点云,若只采用规则的空间网格划分,会使空间网格内的点云信息有较大差异,导致k邻域搜索出现错误^[15]。假设Q内的点数为K,若αk≤K≤βk,则在空间点集Q中直接建立局部k-d树;若K<αk,则增大l的取值;若K>βk,则减小l的取值。其中,α和β为控制系数,均大于1,当点云分布均匀时,α和β的值取小;否则取大^[14]。这样就相当于得到了一个动态网格,该动态网格对于各种密度的点云模型都有较强的适用性,有利于快速获取测量点的k邻域。

2.2 拟合微切平面

以采样点P_i和应用改进的k-d树算法搜索到的k个邻近点N_j(j=0, 1, …, k-1)作为局部平面参考点集,用最小二乘法拟合该点集的微切平面。由于在三维空间内,任意平面均可用三元一次方程表示,同时为了方便利用最小二乘法求取平面方程系数,因此设平面方程为F(x,y,z)=a₁x+a₂y+a₃z+a₄=0(a₁~a₄为平面方程的系数),其矩阵方程为

\begin{matrix} Aa = 0, (1) \end{matrix}

式中:A= $\begin{matrix} [\begin{matrix} \begin{matrix} x_{0} & y_{0} \\ x_{1} & y_{1} \end{matrix} & \begin{matrix} z_{0} & 1 \\ z_{1} & 1 \end{matrix} \\ \begin{matrix} ︙ & ︙ \\ x_{k} & y_{k} \end{matrix} & \begin{matrix} ︙ & ︙ \\ z_{k} & 1 \end{matrix} \end{matrix}] \end{matrix}$ 为由P_i及其k个邻近点的三维坐标构成的矩阵;a=[a₁a₂a₃a₄]^T。对矩阵A^TA进行奇异值分解,即

\begin{matrix} A = U (\begin{matrix} Σ_{r} & 0 \\ 0 & 0 \end{matrix}) V^{T}, (2) \end{matrix}

式中:U和V均为正交矩阵;对角矩阵Σ_r=diag(σ₁,σ₂,…,σ_r),σ_i= $\begin{matrix} \sqrt[]{λ_{i}} \end{matrix}$ (i=1,2,…,r),λ₁≥λ₂≥…≥λ_r>0为A^TA的全体非零特征值。A^TA的最小特征值所对应的特征向量即为方程Aa=0的最小二乘解。该微切平面的法向量为n=(a₁,a₂,a₃)。

2.3 边界特征点提取

设平面方程为F(x,y,z)=a₁x+a₂y+a₃z+a₄=0,将采样点P_i(x_i,y_i,z_i)及其k个邻近点N_j(x_j,y_j,z_j)向该微切平面投影,如图2所示。投影后采样点的坐标为P'_i(x'_i,y'_i,z'_i),同理可求得k个邻近点投影后的坐标点集为N'_j{(x'_j,y'_j,z'_j)|j=0,1,…,k-1}。

图 2. Pi及k个邻近点向其微切平面投影的示意图

Fig. 2. Schematic of projection of Pi and k neighbor points onto their micro-cut plane

下载图片查看所有图片

以P'_i为原点,其与最远点N'_j构成的向量方向为x轴方向,垂直方向为y轴方向,在微切平面内建立二维坐标系,可得坐标点集N'_ij{(x'_ij,y'_ij)|i=1,2,…,r;j=0,1,…,k-1},如图3所示。在微切平面内,如果k邻域投影点在P_i周围均匀分布,则

图 3. 微切平面内建立的局部二维坐标系

Fig. 3. Local two-dimensional coordinate system established in micro-cut plane

下载图片查看所有图片

认为P_i为内部点;如果k邻域投影点偏向P_i的一侧,则认为P_i为边界特征点。以P'_i为起始点、点集N'_ij{(x'_ij,y'_ij)|i=1,2,…,r;j=0,1,…,k-1}为终点定义向量 $\begin{matrix} V_{P'_{i} N'_{ij}} \end{matrix}$ =(x'_ij,y'_ij)(i=1,2,…,r;j=0,1,…,k-1),并对投影向量进行单位化:

\begin{matrix} V_{P″_{i} N″_{ij}} = \frac{V_{P'_{i} N'_{ij}}}{|V_{P'_{i} N'_{ij}}|} = \frac{(x'_{ij}, y'_{ij})}{\sqrt[]{x'^{2}_{ij} + y'^{2}_{ij}}} = (x″_{ij}, y″_{ij}) 。 (3) \end{matrix}

单位化后的 $\begin{matrix} V_{P″_{i} N″_{ij}} \end{matrix}$ 将分布在以P'_i为圆心的单位圆上,将其赋予成对圆心的拉力F_ij,大小为1,方向与 $\begin{matrix} V_{P″_{i} N″_{ij}} \end{matrix}$ 同向,并求合力。当所有向量都在同一个方向时,其合力达到最大值k,可以根据合力的大小 $\begin{matrix} |F_{ij}| \end{matrix}$ 与k的比值是否超过阈值ε(在0~1之间)来确定该点是否为边界特征点^[11]。

如果 $\begin{matrix} |\overset{k - 1}{\sum_{j = 0}} F_{ij}| \end{matrix}$ /k≥ε,则认为该采样点为边界特征点,如图4(a)所示;反之,则认为该采样点为内部点,如图4(b)所示。

图 4. 单位化后的投影向量。(a)邻域点偏向一侧(边界特征点);(b)邻域点均匀分布(内部点)

Fig. 4. Unitized projection vector. (a) Neighborhood points tilted to one side (boundary feature point); (b) neighborhood points distributed evenly (internal point)

下载图片查看所有图片

研究表明,k的取值受点云密度的影响。当点云较密集时,取较小的k值;而当点云较稀疏时,取较大的k值。ε的取值与点云模型的弯曲程度有关,当边界弯曲程度较大时,取较小的阈值;而当边界较平坦时,取较大的阈值。实验数据表明,k的取值在15~30之间,ε的取值在0.40~0.60之间,即可得到较理想的结果,提取出较高精度的边界特征点。

3 点云特征规则化

3.1 边界特征点排序连接

特征提取得到的点是无序的,为了得到连续的边界线,需要对其进行排序。在排序时如果仅以距离最小作为判定标准可能会出现误判,如图5所示。边界线Ⅰ中的P₂有可能错误地与边界线Ⅱ中的S连接,由于边界线具有连续性和局部性,即小范围内的连接走向不会特别大,因此引入矢量偏转角度的概念^[16]。连接边界特征点P₁与P₂,形成初始矢量V_P₁_P₂,接下来只需判定矢量V_P₂_P₃和V_P₂_S相对于V_P₁_P₂的偏转角度θ的大小,很明显V_P₂_P₃相对于V_P₁_P₂的偏转角度更小,故选择P₃作为P₂的下一个连接点。矢量偏转角度θ的计算公式为

\begin{matrix} θ = \arccos \frac{x_{1} x_{2} + y_{1} y_{2} + z_{1} z_{2}}{\sqrt[]{(x_{1}^{2} + y_{1}^{2} + z_{1}^{2}) (x_{2}^{2} + y_{2}^{2} + z_{2}^{2})}}, (4) \end{matrix}

式中:(x₁,y₁,z₁)=(x_P₂-x_P₁,y_P₂-y_P₁,z_P₂-z_P₁);(x₂,y₂,z₂)=(x_P₃-x_P₂,y_P₃-y_P₂,z_P₃-z_P₂)。

图 5. 利用矢量偏转角度选择下一个连接点

Fig. 5. Using vector deflection angle to select next connection point

下载图片查看所有图片

图 6. 使用矢量偏转角度排序出现的问题。(a)问题1;(b)问题2

Fig. 6. Problems during vector deflection angle sorting. (a) Question 1; (b) question 2

下载图片查看所有图片

实验证明,矢量偏转角度仅仅保证了特征点排序时的走向,在处理实际问题时选择θ最小值对应的点作为连接点往往会出现问题。图6(a)中初始矢量V_a₁_a₂和矢量V_a₂_a₃、V_a₂_a₄、V_a₂_a₅的偏转角度θ_i都为0,无法选择下一个连接点;图6(b)中初始矢量V_b₁_b₂和V_b₂_b₄的偏转角度θ₂最小,但明显b₂的下一个连接点应该是距离最近的b₃而不是b₄。因此引入R_i将矢量偏转角度和距离同时作为排序的判定条件,计算公式为

\begin{matrix} R_{i} = μ_{1} \frac{d_{i}}{d} + μ_{2} \frac{θ_{i}}{θ}, (5) \end{matrix}

式中:μ₁、μ₂为各项判据的权重;d_i为连接点与邻域点的距离;d为d_i的平均值;θ_i为矢量偏转角度;θ为θ_i的平均值。

使用上述算法对特征点进行排序,其步骤如下:

1) 从提取的边界特征点集U中任取一点作为初始起点P₁,令n=1,将P₁作为第一个元素归入新的V_n(n为边界线的数目),从点集U中搜寻与P₁距离最近的点作为其连接点P₂,将P₁和P₂从U中删除;

2) 在特征集合U∪V_n中搜寻P₂的邻域点集W_i;

3) 使用(4)式计算出矢量V_P₂_Wi与矢量V_P₁_P₂的偏转角度θ_i(在0°~180°之间);

4) 使用(5)式计算并选定R_i最小值所对应的邻域点W_i,将其作为P₂的连接点,如果W_i∈V_n,转到步骤6);

5) 更新P₁=P₂,P₂=W_i,将P₁作为新的元素按顺序归入点集V_n中,转到步骤2);

6) 如果U非空,令n=n+1,转到步骤1),否则结束排序。

V_n即为排序后的特征点集合。研究表明,一般情况下μ₁、μ₂取相同的权重就能达到较好的排序效果,当d_i、θ_i某一特征比较突出时只需提高对应的权重即可。将V_n中的点按顺序连接即得到初始边界线。

3.2 改进的三次B样条拟合

由于初始边界线是由排序后的边界特征点进行的简单直线连接,若边界线为曲线将会导致边界线不够光滑且存在多处尖角,不利于后续处理。为了提高边界精度,需要对其进行平滑处理,保证边界线具有一定程度的光滑性。在反求工程中,常采用B样条曲线对边界曲线进行拟合,传统的单段三次B样条曲线由4个型值点控制,拟合后的曲线具有局部性、凸包性、连续性等优点^[17],但拟合后的曲线不过型值点(原始边界特征点),造成一定程度的精度误差,如图7所示^[18]。因此在传统三次B样条曲线拟合的基础上,采用一种改进的三次B样条曲线拟合算法连接边界特征点^[19]。该算法的具体思路如图8所示。

图 7. 传统三次B样条算法原理图

Fig. 7. Schematic of traditional cubic B-spline algorithm

下载图片查看所有图片

在P₂两侧增加辅助型值点A_2,0,A_2,1,使P₂为A_2,0A_2,1的中点,且A_2,0A_2,1平行于底边P₁P₃,即 $\begin{matrix} |A_{2,0} P_{2}| \end{matrix}$ = $\begin{matrix} |P_{2} A_{2,1}| \end{matrix}$ =h $\begin{matrix} |P_{1} P_{3}| \end{matrix}$ (h为常数);同理在点P₃两侧增加辅助型值点A_3,0,A_3,1,满足 $\begin{matrix} |A_{3,0} P_{3}| \end{matrix}$ = $\begin{matrix} |P_{3} A_{3,1}| \end{matrix}$ =h $\begin{matrix} |P_{2} P_{4}| \end{matrix}$ (h为常数)。

图 8. 改进的三次B样条算法原理图

Fig. 8. Schematic of improved cubic B-spline algorithm

下载图片查看所有图片

然后以A_2,0、P₂、A_2,1、A_3,0、P₃、A_3,1为控制顶点,按照传统三次B样条原理即可得到三段B样条曲线,分别为r₁、r₂、r₃。为了使拟合后的曲线通过首末两点,只需令A_1,0=A_1,1=P₁,A_n_,0=A_n_,1=P_n,其中n=1,2,3。辅助型值点(不包括首末两点)的计算公式为

\begin{matrix} \{\begin{matrix} A_{i, 0} = P_{i} + P_{i} A_{i, 0} = P_{i} - h (P_{i + 1} - P_{i - 1}) \\ A_{i, 1} = P_{i} + P_{i} A_{i, 1} = P_{i} + h (P_{i + 1} - P_{i - 1}) \end{matrix} 。 (6) \end{matrix}

因为传统三次B样条曲线基函数的系数为1/6,为方便计算故取h=1/6。将辅助型值点均用原始型值点表示,则改进后的三次B样条的三段曲线拟合方程分别为

\begin{matrix} \begin{matrix} r_{1} (t) = \frac{1}{6} [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} \frac{1}{3} & - \frac{5}{6} & \frac{2}{3} & - \frac{1}{6} \\ 0 & 0 & 0 & 0 \\ - 1 & 0 & 1 & 0 \\ 0 & 6 & 0 & 0 \end{matrix}] [\begin{matrix} P_{1} \\ P_{2} \\ P_{3} \\ P_{4} \end{matrix}] = T B_{1} P, (7) \\ r_{2} (t) = \frac{1}{6} [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} - \frac{1}{2} & \frac{3}{2} & - \frac{3}{2} & \frac{1}{2} \\ 1 & - \frac{5}{2} & 2 & - \frac{1}{2} \\ 0 & - \frac{5}{2} & 3 & - \frac{1}{2} \\ - \frac{2}{3} & \frac{31}{6} & \frac{5}{3} & - \frac{1}{6} \end{matrix}] [\begin{matrix} P_{1} \\ P_{2} \\ P_{3} \\ P_{4} \end{matrix}] = T B_{2} P, (8) \\ r_{3} (t) = \frac{1}{6} [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} \frac{1}{6} & - \frac{2}{3} & \frac{5}{6} & - \frac{1}{3} \\ - \frac{1}{2} & 2 & - \frac{5}{2} & 1 \\ \frac{1}{2} & - 3 & \frac{5}{2} & 0 \\ - \frac{1}{6} & \frac{5}{3} & \frac{31}{6} & - \frac{2}{3} \end{matrix}] [\begin{matrix} P_{1} \\ P_{2} \\ P_{3} \\ P_{4} \end{matrix}] = T B_{3} P 。 (9) \end{matrix} \end{matrix}

依据上述方程逐段拟合,最终可以得到改进后的三次B样条曲线。将该方法应用到圆和正弦曲线的连接,如图9所示,可以看出改进后的三次B样条曲线相对于传统的三次B样条曲线在保证了局部性、凸包性、连续性等优点的同时,提高了精确性。

图 9. 三种方法拟合连接对比图。(a)圆;(b)正弦曲线

Fig. 9. Fitting connection comparison by three methods. (a) Circle; (b) sinusoid

下载图片查看所有图片

4 算法应用及分析

为了验证上述算法的可行性,以Matlab和CloudCompare软件为实验平台,在硬件配置为Intel® Core^TM i7-5500U CPU @2.40 GHz 4.00 GB内存、操作系统为Windows 10的计算机上针对两组不同的三维点云数据进行实验。

4.1 点云模型实验对比分析

为了更好地突出所提算法的实用性,选取边界线为曲线的三维曲面模型点云进行模拟,以便观测边界曲线的排序拟合效果。不同参数下的提取状况和比较有代表性的部分提取结果分别见表1和图10。该曲面原始点云如图11(a)、(f)、(k)所示,包含37148个数据点。由于该曲面点云模型密度较大,弯曲程度一般,故k值取26~30,阈值ε取0.48~0.52。

由表1可得,提取时间随着k值的增大而增大;提取的特征点数目随着阈值ε的增大而减少;由图10的部分效果图可以看出,当k=30,ε=0.50时提取到的特征点断裂线少,无噪声点,效果最好。为了验证所提算法的优越性,引入文献[ 11]、[12]中的算法作为对比实验,提取结果如图11所示。

表 1. 不同参数下的特征点提取状况和运行时间

Table 1. Extraction status of feature points and running time under different parameters

ε	k=26		k=28		k=30
ε	Feature pointnumber	Runningtime /ms	Feature pointnumber	Runningtime /ms	Feature pointnumber	Runningtime /ms
0.48	378	3041	357	3141	400	3216
0.50	321	2987	304	3125	340	3244
0.52	271	2972	254	3123	285	3198

查看所有表

图 10. 不同参数下的部分提取效果图。(a) k=30,ε=0.48;(b) k=30,ε=0.52;(c) k=28,ε=0.50;(d) k=30,ε=0.50

Fig. 10. Partial extraction effect diagrams under different parameters. (a) k=30, ε=0.48; (b) k=30, ε=0.52; (c) k=28, ε=0.50; (d) k=30, ε=0.50

下载图片查看所有图片

图 11. 点云模型的特征提取对比与拟合。(a)(f)(k)原始点云;(b)(g)(l)文献[ 11]算法;(c)(h)(m)文献[ 12]算法;(d)(i)(n)所提算法;(e)(j)(o)特征规则化

Fig. 11. Feature extraction comparison and fitting of point cloud model. (a)(f)(k) Original point clouds; (b)(g)(l) algorithmin Ref. [11]; (c)(h)(m) algorithm in Ref. [12]; (d)(i)(n) proposed algorithm; (e)(j)(o) feature regularization

下载图片查看所有图片

图 12. 长江二七大桥的特征提取对比与拟合。(a)侧视图;(e)主视图;(i)俯视图;(b)(f)(j)文献[ 12]算法;(c)(g)(k)所提算法;(d)(h)(l)特征规则化

Fig. 12. Feature extraction and fitting of Yangtze River Erqi Bridge. (a) Side view; (e) main view; (i) top view; (b)(f)(j) algorithm in Ref. [12]; (c)(g)(k) proposed algorithm; (d)(h)(l) feature regularization

下载图片查看所有图片

由图11(b)、(g)、(l)可以看出,文献[ 11]中算法提取的特征点不完整,有较多的断裂线;由图11(c)、(h)、(m)可以看出,文献[ 12]中算法的提取结果比较粗糙,存在非特征点的误判,有较多的断裂线和冗余点;相比于前两种算法的不足,所提算法提取的特征点更加完整,断裂线少,冗余点少,保证了提取的精确性,如图11(d)、(i)、(n)所示。对提取到的边界特征点进行特征规则化,得到该三维曲面模型的边界线,如图11(e)、(j)、(o)所示,可以看出特征规则化算法对提取后的边界特征点能够达到较好的排序拟合效果,得到光滑连续的边界线,更好地保留边界特征。

4.2 实例分析

由第4.1节可知,所提算法对于点云模型的特征提取和边界拟合效果较好。长江二七大桥有多种不同的边界特征,包含尖锐棱线、弱曲率线等,特征提取较难且边界线数目多、分布广,因此将所提算法应用到长江二七大桥进行实例分析。表2为文献[ 12]中算法和所提算法的特征点提取状况和运行时间对比,两种算法的提取结果见图12。

表 2. 两种算法的特征点提取状况和运行时间

Table 2. Extraction status of feature points and running time by two algorithms

Sculpture point cloud model	Original point number	Feature point number	Extraction rate /%	Running time /s
Algorithm of Ref. [12]	72902	7697	10.6	18.34
Proposed algorithm	72902	12095	16.6	12.57

查看所有表

由表2和图12可以得出以下结论:文献[ 12]中算法的特征点提取率为10.6%,有较多的断裂线和冗余点,存在部分边界特性缺失和部分提取效果不明显的问题,提取时间为18.34 s;所提算法的特征提取率为16.6%,完整清晰地保留了边界特性,断裂线少,冗余点少,且提取时间为12.57 s,运行效率高。应用特征规则化算法对特征点进行处理,得到连续光滑的边界线;然后采用随机抽样法从原始点云中抽取40个边界点(主体部分20个,钩索部分前后各10个),对拟合后的边界线进行偏差分析,40个点与拟合后的边界线的偏差量见表3。

由表3的数据可以得到40个点的平均偏差和标准差(均方差):

\begin{matrix} \begin{matrix} \bar{μ} = (\overset{40}{\sum_{i = 1}} μ_{i}) / 40 = 0.0698 mm, (10) \\ σ = \sqrt[]{\frac{1}{40} \times \overset{40}{\sum_{i = 1}} (μ_{i} {- \bar{μ})}^{2}} = 0.0337 mm 。 (11) \end{matrix} \end{matrix}

由(10)、(11)式可知,拟合得到的边界线平均偏差为0.0698 mm,标准差为0.0337 mm,偏差量级为

表 3. 随机抽取的40个点与边界线的偏差量

Table 3. Deviations between randomly selected 40 points and boundary lines

Position	μ /mm
Bridge body	0.0472	0.0063	0.0389	0.0412	0.0682	0.0561	0.1068	0.0231	0.0561	0.0968
	0.0210	0.0178	0.0492	0.0639	0.1078	0.1134	0.0892	0.0634	0.0548	0.1249
Hook	0.0437	0.0894	0.0947	0.1069	0.1127	0.0357	0.0368	0.0479	0.1018	0.0294
	0.0417	0.0396	0.1034	0.0147	0.1058	0.0369	0.0647	0.1249	0.1078	0.1095

查看所有表

10^-5 m,由此可以说明该边界线具有较高的精度,能够更好地保留边界特性。

5 结论

通过改进场力和判定准则实现点云的特征规则化。首先在一种基于点云密度的动态网格内建立局部k-d树搜索k邻域,接着以采样点及其k邻域点建立最小二乘微切平面并向该平面投影,将点的三维坐标转化为投影平面内的二维坐标,根据场力和判定准则提取边界特征点;然后以矢量偏转角度为基础提出一种新的排序算法对提取出来的特征点进行排序并生成初始边界线;最后利用一种改进的三次B样条拟合算法对边界线进行平滑拟合。该算法利用改进的k-d树搜索k邻域,并将三维坐标转化为二维坐标,不仅可以准确地提取边界特征点,而且加快了提取效率;考虑到了点云的特征规则化,采用改进的排序算法和改进的三次B样条拟合算法得到了连续光滑的边界线,避免了直接连接的边界线存在多处尖角、不够光滑的缺点。同时,该算法易于实现,应用面广,对均匀和非均匀点云的提取效果都有较好的稳定性。

参考文献

[1] Wang Y H, Wang L J, Hao W, et al. A novel slicing-based regularization method for raw point clouds in visible IoT[J]. IEEE Access, 2018, 6: 18299-18309.

[2] 张立朔, 程效军. 基于激光点云的隧道形变分析方法[J]. 中国激光, 2018, 45(4): 0404004.

Zhang L S, Cheng X J. Tunnel deformation analysis based on lidar points[J]. Chinese Journal of Lasers, 2018, 45(4): 0404004.

[3] 章涛, 陈西江. 利用三维激光扫描技术监测桥梁振幅[J]. 激光与光电子学进展, 2018, 55(5): 051409.

Zhang T, Chen X J. Bridge amplitude monitoring with three-dimensional laser scanning technology[J]. Laser & Optoelectronics Progress, 2018, 55(5): 051409.

[4] Varady T, Martin R R, Cox J. Reverse engineering of geometric models: an introduction[J]. Computer-Aided Design, 1997, 29(4): 255-268.

[5] BazazianD, Casas JR, Ruiz-HidalgoJ. Fast and robust edge extraction in unorganized point clouds[C]∥2015 International Conference on Digital Image Computing: Techniques and Applications (DICTA), 2015: 1- 8.

[6] HackelT, Wegner JD, SchindlerK. Contour detection in unstructured 3D point clouds[C]∥IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016: 1610- 1618.

[7] Xi XH, Wan YP, WangC. Building boundaries extraction from points cloud using an imageedge detection method[C]∥IEEE International Geoscience and Remote Sensing Symposium (IGARSS), 2016: 1270- 1273.

[8] 张雨禾, 耿国华, 魏潇然, 等. 采用密度空间聚类的散乱点云特征提取方法[J]. 西安电子科技大学学报(自然科学版), 2017, 44(2): 114-120.

Zhang Y H, Geng G H, Wei X R, et al. Feature extraction of point clouds using the DBSCAN clustering[J]. Journal of Xidian University (Natural Science), 2017, 44(2): 114-120.

[9] 董伟. 利用邻近点几何特征实现建筑物点云特征提取[J]. 激光与光电子学进展, 2018, 55(7): 071006.

Dong W. Feature extraction of the building point cloud by using geometrical characteristics of adjacent points[J]. Laser & Optoelectronics Progress, 2018, 55(7): 071006.

[10] 陈朋, 谭晔汶, 李亮. 地面三维激光扫描建筑物点云特征线提取[J]. 激光杂志, 2016, 37(3): 9-11.

Chen P, Tan Y W, Li L. Extraction of building's feature lines based on 3-D terrestrial laser scanning[J]. Laser Journal, 2016, 37(3): 9-11.

[11] 陈义仁, 王一宾, 彭张节, 等. 一种改进的散乱点云边界特征点提取算法[J]. 计算机工程与应用, 2012, 48(23): 177-180, 190.

Chen Y R, Wang Y B, Peng Z J, et al. Improved algorithm for extraction of boundary characteristic point from scattered point cloud[J]. Computer Engineering and Applications, 2012, 48(23): 177-180, 190.

[12] 孙殿柱, 范志先, 李延瑞. 散乱数据点云边界特征自动提取算法[J]. 华中科技大学学报(自然科学版), 2008, 36(8): 82-84.

Sun D Z, Fan Z X, Li Y R. Automatic extraction of boundary characteristic from scatter data[J]. Journal of Huazhong University of Science and Technology (Nature Science), 2008, 36(8): 82-84.

[13] 孙金虎. 点云模型分割与融合关键技术研究[D]. 南京: 南京航空航天大学, 2013: 9- 24.

Sun JH. Research on key technologies of point cloud segmentation and fusion[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2013: 9- 24.

[14] 马骊溟, 徐毅, 李泽湘. 基于动态网格划分的散乱点k邻近快速搜索算法[J]. 计算机工程, 2008, 34(8): 10-11, 21.

Ma L M, Xu Y, Li Z X. Fast k-nearest neighbors searching algorithm for scattered points based on dynamic grid decomposition[J]. Computer Engineering, 2008, 34(8): 10-11, 21.

[15] 张蓉. 一种改进的立体栅格K邻域搜索算法[J]. 科技创新与应用, 2017( 29): 5- 6.

ZhangR. An improved spatial grid K-neighborhood search algorithm[J]. Technology Innovation and Application, 2017( 29): 5- 6.

[16] 顾园园, 姜晓峰, 张量. 曲面重构中带孔洞点云数据的边界提取算法[J]. 苏州大学学报(工科版), 2008, 28(2): 56-61.

Gu Y Y, Jiang X F, Zhang L. The boundary extraction of point cloud with hole in surface reconstruction[J]. Journal of Suzhou University (Engineering Science Edition), 2008, 28(2): 56-61.

[17] 施法中. 计算机辅助几何设计与非均匀有理B样条[M]. 2版. 北京: 高等教育出版社, 2013: 133- 149.

Shi FZ. Computer aided geometric design and non-uniform rational B-spline[M]. 2nd ed. Beijing: Higher Education Press, 2013: 133- 149.

[18] 曾卓. 阿达依·谢尔亚孜旦, 申传鹏. 三次B样条小波的曲线拟合研究[J]. 机械科学与技术, 2018, 37(6): 891-895.

Zeng Z, Xieeryazidan A, Shen C P. A research on curve fitting of cubic B-spline wavelets[J]. Mechanical Science and Technology for Aerospace Engineering, 2018, 37(6): 891-895.

[19] 段振云, 王宁, 杨旭, 等. 一种改进B样条曲线拟合算法研究[J]. 机械设计与制造, 2016( 5): 17- 19, 23.

Duan ZY, WangN, YangX, et al. An algorithm of improved B-spline curve fitting[J]. Machinery Design & Manufacture, 2016( 5): 17- 19, 23.

刘庆, 章光, 陈西江. 融合改进场力和判定准则的点云特征规则化[J]. 中国激光, 2019, 46(4): 0404009. Qing Liu, Guang Zhang, Xijiang Chen. Point Cloud Feature Regularization Based on Fusion of Improved Field Force and Judging Criterion[J]. Chinese Journal of Lasers, 2019, 46(4): 0404009.

融合改进场力和判定准则的点云特征规则化 下载： 697次

1 引言

2 改进场力和算法提取边界特征点

2.1 改进的k-d树搜索k邻域

图 1. 空间动态网格Q示意图

Fig. 1. Schematic of spatial dynamic grid Q

2.2 拟合微切平面

2.3 边界特征点提取

图 2. Pi及k个邻近点向其微切平面投影的示意图

Fig. 2. Schematic of projection of Pi and k neighbor points onto their micro-cut plane

图 3. 微切平面内建立的局部二维坐标系

Fig. 3. Local two-dimensional coordinate system established in micro-cut plane

图 4. 单位化后的投影向量。(a)邻域点偏向一侧(边界特征点);(b)邻域点均匀分布(内部点)

Fig. 4. Unitized projection vector. (a) Neighborhood points tilted to one side (boundary feature point); (b) neighborhood points distributed evenly (internal point)

3 点云特征规则化

3.1 边界特征点排序连接

图 5. 利用矢量偏转角度选择下一个连接点

Fig. 5. Using vector deflection angle to select next connection point

图 6. 使用矢量偏转角度排序出现的问题。(a)问题1;(b)问题2

Fig. 6. Problems during vector deflection angle sorting. (a) Question 1; (b) question 2

3.2 改进的三次B样条拟合

图 7. 传统三次B样条算法原理图

Fig. 7. Schematic of traditional cubic B-spline algorithm

图 8. 改进的三次B样条算法原理图

Fig. 8. Schematic of improved cubic B-spline algorithm

图 9. 三种方法拟合连接对比图。(a)圆;(b)正弦曲线

Fig. 9. Fitting connection comparison by three methods. (a) Circle; (b) sinusoid

4 算法应用及分析

4.1 点云模型实验对比分析

表 1. 不同参数下的特征点提取状况和运行时间

Table 1. Extraction status of feature points and running time under different parameters

图 10. 不同参数下的部分提取效果图。(a) k=30,ε=0.48;(b) k=30,ε=0.52;(c) k=28,ε=0.50;(d) k=30,ε=0.50

Fig. 10. Partial extraction effect diagrams under different parameters. (a) k=30, ε=0.48; (b) k=30, ε=0.52; (c) k=28, ε=0.50; (d) k=30, ε=0.50

图 11. 点云模型的特征提取对比与拟合。(a)(f)(k)原始点云;(b)(g)(l)文献[ 11]算法;(c)(h)(m)文献[ 12]算法;(d)(i)(n)所提算法;(e)(j)(o)特征规则化

Fig. 11. Feature extraction comparison and fitting of point cloud model. (a)(f)(k) Original point clouds; (b)(g)(l) algorithmin Ref. [11]; (c)(h)(m) algorithm in Ref. [12]; (d)(i)(n) proposed algorithm; (e)(j)(o) feature regularization

图 12. 长江二七大桥的特征提取对比与拟合。(a)侧视图;(e)主视图;(i)俯视图;(b)(f)(j)文献[ 12]算法;(c)(g)(k)所提算法;(d)(h)(l)特征规则化

Fig. 12. Feature extraction and fitting of Yangtze River Erqi Bridge. (a) Side view; (e) main view; (i) top view; (b)(f)(j) algorithm in Ref. [12]; (c)(g)(k) proposed algorithm; (d)(h)(l) feature regularization

4.2 实例分析

表 2. 两种算法的特征点提取状况和运行时间

Table 2. Extraction status of feature points and running time by two algorithms

表 3. 随机抽取的40个点与边界线的偏差量

Table 3. Deviations between randomly selected 40 points and boundary lines

5 结论

Article Outline

相关论文

相关资讯

关于本站 Cookie 的使用提示

全站搜索

融合改进场力和判定准则的点云特征规则化下载： 697次