基于体素生长的点云结构直线段提取

李明磊; 宗文鹏; 李广云; 王力

doi:doi:10.3788/AOS201838.0112001

光学学报, 2018, 38 (1): 0112001, 网络出版: 2018-08-31

基于体素生长的点云结构直线段提取下载： 1257次

Extraction of Structure Line Segments from Point Clouds Using Voxel-Based Region Growing

论文大纲

李明磊 ^*宗文鹏李广云王力

作者单位

信息工程大学导航与空天目标工程学院, 河南郑州 450001

测量点云平面八叉树体素线段 measurement point cloud plane octree voxel line segment

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

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

摘要

针对现有结构直线段提取方法存在的效率低下或准确程度不足等问题,提出了一种基于体素生长的点云结构直线段高效提取方法。首先,对点云进行体素化剖分与平面分割,并以体素为单位进行邻域判断,实现对结构直线段分布区域的筛选;然后,采用基于体素的区域生长对结构直线段的分布区域进行分割;最后,依据结构线段分布区域的范围以及其所在平面的数学方程实现其提取和优化,并进行精度评定。进行了实验测试,利用多组点云数据验证了本方法的有效性,利用对比实验验证了本方法的精度和高效性。实验结果显示:相比现有方法,该方法在效率上提高了10倍以上,在精度上提高了0.25倍左右,证明提出的方法可以准确高效地得到较为理想的点云结构直线段提取结果。

Abstract

Aim

ing at the problems remaining in existing extraction method of structure line segment such as low efficiency and reliability, an efficient extraction method for structure line segments from point clouds through voxel-based region growing is proposed. Firstly, point cloud is voxelized and segmented, and the distributing regions of structure line segments are recognized through voxel-based nearest neighbors searching. Then, the distributing regions of structure line segments are segmented through voxel-based region growing. Finally, corresponding line segments are extracted and optimized in these segmented regions according to the equations of their supporting planes, and the accuracy of the results are assessed. The test experiments are performed, and the feasibility, accuracy and efficiency of the proposed method are verified by obtaining the processing and comparison results of adopted point clouds. The experimental results indicate that the efficiency is increased more than 10 times and the accuracy is improved about 0.25 times, which verifies that the proposed method has high accuracy and efficiency as well as the ability of achieving relatively more ideal results.

1 引言

随着数字地球、智慧城市、虚拟现实等概念的提出与相关技术的不断推进,三维空间信息的快速获取与处理逐渐取代二维平面信息相关处理的地位,成为当前的研究热点。作为一种新型三维空间信息获取技术的代表,三维激光扫描测量技术发展迅猛并不断开拓新的应用领域,三维空间数据的采集速度越来越快、数据质量越来越好、信息量越来越丰富,相应的三维扫描测量结果——三维点云作为一种新型的数据形式也成为相关领域学者争相研究的热点。其中,线特征的语义描述是一个具有重要研究价值的领域,已有部分学者研究了平面交线(即结构直线段,下文简称结构线段)的提取并探索了其相关应用,总结起来主要有基于投影图像的方法和基于平面交线的方法两大类。

为了将较为成熟的图像处理算法应用到三维领域,一种较为简单的思路是将三维数据投影到二维,因此,部分学者考虑利用各种类型的图像化投影进行三维线段提取的相关研究,主要有深度图像、阴影图像及强度图像等类型。文献[ 1]首先将点云投影为深度图像^[2](按照一定采样间隔对点云进行投影),并通过邻域插值对图像的空像素点进行填充,之后采用Line-Segment-Detector (LSD)算法^[3-4]在深度图像中提取线段。类似的,文献[ 5]在文献[ 1]处理方式的基础上,根据正射影像生成时边界区域的深度变化设定阈值过滤边界点,然后同样采用LSD算法提取线段。由于点云一般分布不均匀,并且一定距离以外达不到较高的分辨率,而且点云投影获取深度图像时不同投影分辨率的选用对提取结果会产生较大影响,因此这种线段提取方式具有一定的局限性。文献[ 6]首先将三维点云结合Eye Dome Lighting算法^[7]转换为基于多投影视角(视点均匀分布在点云的包围球面上)的阴影图像,之后采用LSD算法在阴影图像中提取二维线段及其支持区,然后将二维线段支持区投影回三维空间得到三维线段支持区,并将此支持区沿其主方向投影到二维平面上进行“V”型形状结构拟合,通过合并和区域生长对此结构进行优化,最后对“V”型形状结构对应的两扇平面进行拟合,将平面的交线作为提取的目标线段,该方法较为依赖视点和投影分辨率的选取,不适用于室内场景。

现有的直接从三维数据中提取三维线特征的方法有一部分是针对特征曲线进行的,例如,文献[ 8]采用移动最小二乘法计算局部曲率提取脊线和谷线,文献[ 9]采用一维截断的傅里叶级数识别特点并计算近似曲率用于提取显著的特征曲线等。对于三维结构线段的提取,文献[ 10]和[11]利用区域生长^[12]提取平面交线,并分别将线段应用于视觉定位和测距传感器标定,文献[ 13]将利用随机抽样一致(RANSAC)算法^[14-15]提取的平面进行相交得到三维线段,并将线段用于多站点云之间的拼接,文献[ 16]采用了点云法矢在高斯球面聚类的方式进行平面提取进而提取平面的交线,最后通过交互产生多边形结构。现有的基于平面相交提取结构线段的方法思路基本上一致,即先从点云中分割平面,然后再判断平面是否相交,进而求取交线,最后依托平面内点在线段上的投影范围确定最终线段的端点,但这种方式一般具有一定的盲目性,每个平面都需要与其他平面进行非平行性、相邻性和相交性判别,并且最终线段的提取结果并非依托的是线段的邻域(支持区),容易产生端点误判,另外,在平面之间的相交性判断及交线端点的确定方面都存在效率低下或准确程度不足等问题。

针对现有结构线段提取算法存在的低效性和精度低等问题,本文研究了一种基于体素生长的结构线段快速定位与提取方法。该方法在点云体素化剖分和平面分割的基础之上首先依据体素之间的相似性分布筛选出结构线段的潜在分布区域,实现对结构线段的快速定位,然后基于体素生长对各个结构线段的潜在分布区域进行分割,之后在各分割结果中进行结构线段的提取与优化,最后对结构线段提取结果的精度进行定量评定。

2 结构线段的提取

基于平面相交提取结构线段时,平面分割结果的优劣是影响线段提取结果的重要因素,平面是否真实相交(相交部位是否真实存在点)以及线段端点的确定是线段提取的重点。所提出的利用体素生长的点云结构直线段提取方法的流程如图1所示,算法主要分为5个步骤:点云的体素化剖分、基于体素生长的平面分割、潜在结构线段支持区的识别、结构线段支持区的分割以及结构线段的提取与优化。本节将对算法的具体步骤进行详细描述。

2.1 点云的体素化剖分

八叉树结构是一种依托于点云空间分布的数据结构,数据的增减不改变整体结构,并且剖分层数的增减简便易行,具有较好的空间直观性,其基本剖分原理不做赘述。八叉树的剖分涉及到其初始体素尺寸和剖分终止条件等问题。文献[ 1]采用的点云八叉树体素剖分及基于体素生长的平面分割方法是目前较为先进的区域生长平面分割方法,其参照文献[ 17]的思路,根据点云的密度及体素信息的精度需求确定初始尺寸d_I,第二步继续依据人工设定的

图 1. 所提算法流程。(a)原始点云;(b)体素生成;(c)平面分割;(d)潜在线段支持区体素的识别;(e)提取结构线段支持区;(f)三维结构线段的提取与结果优化;(g)算法流程图

Fig. 1. Procedure of the proposed method. (a) Original point cloud; (b) voxelization; (c) plane segmentation; (d) recognition of potential support voxels; (e) segmentation of support regions; (f) extraction of three-dimensional structure line segments and refinement; (g) algorithm flow chart

下载图片查看所有图片

体素最小尺寸阈值d_min和局部平面拟合标准差的阈值σ_th对初始体素进行细分。这种方法需要额外的时间开销进行点云密度的预判,并且具有较多的经验参数输入值。

为避免点云密度判定与经验参数的输入,本研究在八叉树剖分时将d_I固定设定为一个初始较小值,并依据初始剖分后各体素内点个数的平均值动态调整八叉树的层数。初始剖分后可得到一系列立方体体素块,依据各体素内点可计算得到体素的重心点,为了使体素内点分布情况一致化,将距各体素重心距离为 $\begin{matrix} \sqrt[]{3} \end{matrix}$ d_v/2(d_v为体素尺寸)的外接球邻域内点作为体素的归化内点,用于下一步体素信息的计算。

在各体素中,参照点云平面拟合的协方差分析算法^[18],得到各体素内点分布的三个特征值λ₁≥λ₂≥λ₃>0及特征向量,进而得到体素的法矢n_v和拟合标准差σ_v,参照文献[ 19]计算三个分别反映点集呈线状、面状或体状(球状)分布概率的空间维度特征描述符:

\begin{matrix} α_{1 D} = \frac{\sqrt[]{λ_{1}} - \sqrt[]{λ_{2}}}{\sqrt[]{λ_{1}}}, α_{2 D} = \frac{\sqrt[]{λ_{2}} - \sqrt[]{λ_{3}}}{\sqrt[]{λ_{1}}}, α_{3 D} = \frac{\sqrt[]{λ_{3}}}{\sqrt[]{λ_{1}}} 。 (1) \end{matrix}

由于σ_v的大小受激光扫描测量精度以及被测物体的颜色、材质及粗糙程度等因素的影响,为了使阈值σ_th自动适应数据厚度(一般采用点云局部平面拟合标准差的平均值来计算,反映点云到局部拟合面的平均离散程度),本研究依据体素呈面状分布概率α_2D值对体素信息进行统计,以最近似面状分布的一批平面体素作为表面平整度最好并且能够反映激光测量精度的代表性体素,统计其σ_v信息得到σ_th。

为了保证α_2D值能准确反映体素呈平面分布的概率,依据(1)式可知,需保证 $\begin{matrix} \sqrt[]{λ_{1}} \end{matrix}$ 和 $\begin{matrix} \sqrt[]{λ_{2}} \end{matrix}$ 比 $\begin{matrix} \sqrt[]{λ_{3}} \end{matrix}$ 高出一个数量级,即 $\begin{matrix} \sqrt[]{λ_{2}} \end{matrix}$ ≥10 $\begin{matrix} \sqrt[]{λ_{3}} \end{matrix}$ ,需使体素内点分布的直径大于10倍的内点分布厚度,即2·( $\begin{matrix} \sqrt[]{3} \end{matrix}$ d_v/2)≥10(2σ_v),从而d_v与σ_v之间的最小比例限制R_th不应小于(20/ $\begin{matrix} \sqrt[]{3} \end{matrix}$ )∶1,否则将导致α_2D值不可靠。在体素剖分过程中,如果其尺寸d_v小于2R_thσ_v,剖分后的子体素尺寸必然小于R_thσ_v,因此将体素尺寸阈值d_min设为d_min=2R_thσ_th。

得到剖分终止条件d_min和σ_th后,对初始八叉树进行进一步细分。在本节剖分过程中主要有三层判断条件:如果当前层体素尺寸小于d_min时,终止整个剖分过程;否则,判断各体素的拟合标准差σ_v与σ_th的关系,如果σ_v≤σ_th,当前体素终止剖分;另外,如果当前体素剖分后所有子体素的σ_v相比当前体素并未减小,当前体素的所有子体素终止剖分。如果三层判断条件都未满足,则对当前体素进行剖分。图1(b)为该步骤得到的体素结构示例。

2.2 基于体素生长的平面分割

对于基于体素的区域生长,其主要问题是确定相邻共面体素间的法矢夹角阈值θ_th及体素重心到其邻域共面体素拟合面的距离因子阈值d_th。

对于θ_th的确定,体素内点拟合面的竖截面示意如图2所示,依据随机误差分布特性,点云在目标物体真值表面呈一定厚度分布,设d'_v= $\begin{matrix} \sqrt[]{3} \end{matrix}$ d_v/2为体素的外接球半径,体素法矢n_v与归属面(图2中粗虚线)法矢之间的最大偏差倾角为arctan(σ_v/d'_v),由于本研究中八叉树剖分特性可保证d'_v≥10σ_v,故可得θ≤2arctan(0.1),这里将θ_th设置为2arctan(0.1)≈11.42°。

图 2. 相邻共面体素的法矢夹角与体素尺寸和拟合标准差之间的关系示意图

Fig. 2. Sketch map for the relationship among intersection angle, voxel size and fitting standard deviation value of two neighbor coplanar voxels

下载图片查看所有图片

对于d_th的确定,首先依据α_2D≥α_1D且α_2D≥α_3D条件筛选可置信平面体素作为种子体素,并将其依据α_2D排序,采用类似上节八叉树剖分的体素统计策略将统计得到的各个峰值区间对应的种子体素分层,在各层中动态设定d_th为本层统计得到的σ_th。

在确定生长条件后,按照排序后的种子体素以体素为单位依次进行基于体素的分层区域生长,各层生长完毕后对被生长到的未被归为平面体素的边缘体素进行邻域平面的共面性判断,将其内点归类到其距离最近的平面中,以优化各层体素生长平面分割的结果。该步骤执行后的平面分割结果参考图1(c)。

2.3 线段支持区体素的预筛选

图3(a)所示的八叉树体素结构为图1(b)对应数据的顶视图(点云底色为回光强度假彩色),在基于体素生长平面分割的基础之上,以图3(b)中选用的示例平面体素(用红色标示)为例,所采用的线段支持区体素预筛选方法的思路为:在体素平面的中部区域,其元素体素相互邻接并且呈平面分布,如图3(b)中与示例平面体素(红色标示)的直接相邻的一阶邻域体素(蓝色标示)同样也为平面体素,依据此特点可分离出不在边缘并且不与边缘相邻的体素,从而筛选出包括边缘体素和与边缘体素相邻体素在内的潜在线段支持区体素。图3(a)所示数据经过边缘和非边缘体素分离之后的效果如图3(c)所示,其对应侧视图如图1(d)所示,图示效果表明本节方法可以有效定位出线段的潜在支持区体素,由于归属平面已知,其尺寸不均匀的情况并不影响线段的提取。

图 3. 潜在线段支持区的筛选。(a)八叉树体素全局结构;(b)非边缘且非边缘相邻体素(红色体素块)位置示意;(c)潜在线段支持区体素(红色体素块)

Fig. 3. Recognition of potential support voxels. (a) Global structure of octree voxels; (b) distribution of non-edge and non-edge adjacent voxels which are shown in red; (c) potential support voxels which are shown in red

下载图片查看所有图片

2.4 支持区点集的体素生长提取

通过将体素生长过程约束在潜在支持区之内,避免了在提取线段支持区之时体素生长的盲目性,并且任意一体素其一阶邻域之内必定存在两个以上平面,从而使生长过程对于种子体素的选用无特殊要求。基于体素生长提取线段支持区的具体过程为:

步骤1, 种子区域的选定。如图4(a)所示,任意选取一边缘体素v_seed,假定其归属面为Θ_left(顶视图所示平面),其邻接面为Θ_right(侧视图所示平面),搜寻其一阶邻域体素v_NNI,统计v_seed和v_NNI所归属平面的个数n_Θ。由于在三面相交的墙角区域不易进行共面性判断进而进行区域生长,并且体素生长提取的目标为两面交线区域,故当n_Θ>2时放弃当前种子体素v_seed并重新选用下一边缘体素作为种子体素执行本步骤。

体素生长提取线段支持区。(a)种子体素(红色体素)邻域(蓝色体素)平面分布的统计及初步生长(虚线为支持区边界);(b)种子体素的生长(红色体素为新种子体素,绿色体素为上次生长所用的种子体素,蓝色体素为待生长体素,红色箭头为生长方向);(c)最终提取的线段支持区点集(上图顶视图用红色标示位置,下图用不同颜色区分不同线段的支持区)

图 4. 体素生长提取线段支持区。(a)种子体素(红色体素)邻域(蓝色体素)平面分布的统计及初步生长(虚线为支持区边界);(b)种子体素的生长(红色体素为新种子体素,绿色体素为上次生长所用的种子体素,蓝色体素为待生长体素,红色箭头为生长方向);(c)最终提取的线段支持区点集(上图顶视图用红色标示位置,下图用不同颜色区分不同线段的支持区)

Fig. 4. Extraction of support regions using voxel-based region growing. (a) Statistics of plane distribution in the neighbor voxels (which are shown in blue) of the seed voxel (which is shown in red) and proceeding of initial region growing (in which the dash lines represent the border of the support region); (b) region growing from the seed voxels (in which the initial seed is in green, the new seeds are in red and the neighbor voxels of the new seeds are in blue, while the red arrows indicate the grow

下载图片查看所有图片

步骤2, 线段支持区的存储与新种子体素的选定。当n_Θ=2时,说明当前种子体素位于两平面相交处,结构直线的方程可用如下二元组表示:

\begin{matrix} υ (p) = (Θ_{left}, Θ_{rig h t}), (2) \end{matrix}

式中p∈Θ_left∩Θ_right,其对应的结构线段可通过端点求解后得到。定义任意点p'到υ(p)支持面的距离为

\begin{matrix} PtSR_dist [p', υ (p)] = |(p' - Θ \cdot \bar{P}) \cdot Θ \cdot n|, (3) \end{matrix}

式中,

\begin{matrix} Θ = \underset{Θ \in {Θ_{left}, Θ_{rig h t}}}{ar g_{} \max} (|(p' - Θ \cdot \bar{P}) \cdot Θ \cdot n|), (4) \end{matrix}

式中Θ· $\begin{matrix} \bar{P} \end{matrix}$ 与Θ·n分别为平面Θ的重心点和法矢。对于当前结构线段A,本步在其对应种子体素v_seed和被生长体素v_NNI中搜寻其支持区点集:对于潜在支持点p'∈v_seed∪v_NNI,当其到平面Θ_left和Θ_right的距离都小于阈值w(这里将其设置为v_seed的宽度,并将其作为当前线段A支持区的宽度W_A)时,即当p'满足如下条件式:

\begin{matrix} PtSR_dist [p', υ (p)] \leq w, (5) \end{matrix}

此时根据其平面分割时的归属面将其存储到线段的支持面SR_A·Θ_left或SR_A·Θ_right中。如果某v_NNI的内点有一部分被归属到SR_A中,则将此v_NNI作为下次生长的种子体素,如图4(b)所示(增加的红色体素为新种子点)。

步骤3, 种子体素的生长。利用步骤2新增的种子体素进行生长,首先判断新种子体素的邻域体素归属面是否是SR_A·Θ_left或SR_A·Θ_right,如果是,则将此邻域体素依据步骤2中的(3)式和(5)式存储到SR_A中,否则不处理。生长过程示意如图4(b)所示。

步骤4, 生长终止条件及新线段支持区的生长。按照步骤2~步骤3的顺序迭代进行体素生长,直至此过程未新增种子体素时,当前线段支持区停止生长。然后选定尚未被处理的边缘体素作为新的候选种子体素重新执行步骤1~步骤3识别新的线段支持区。当所有边缘体素被处理过后,终止整个生长过程。

基于体素生长的线段支持区点集提取过程执行完毕后的效果如图4(c)所示。

2.5 结构线段的提取与优化

基于体素生长提取到的各条线段的支持区点集分别呈“V”型分布,如图1(e)所示,这一点与文献[ 6]初步提取的线段支持区(此文献将其称为“V-Shape”)类似,但区别是本研究提取的V-Shape两侧支持面的方程已知,不需要再进行两侧支持面的分割与拟合。本节在线段端点的确定方面采用的思路与文献[ 10-11, 13]等基于平面相交的方法类似,区别是在提取交线之前进行线段支持面重心的归化,并且仅依托支持区点集在交线上的投影确定线段的端点。从V-Shape中提取线段的具体过程描述如下:

步骤1, 支持面的重心归化。将平面分割后各个拟合面与点云重叠显示,如图5所示,由于现实世界中的平面不能保证平整,并且仪器测量存在误差,拟合面与实际数据之间存在一定的偏差,尤其是在类似屋顶等具有一定承重变形的平面与承重墙连接的墙角区域,这种偏差更为明显,直接利用拟合面求解结构线段,结果可能与其支持区点集存在一定的偏差。本步为减弱上述问题的影响,将支持面向支持区的重心进行平移,即将(4)式中拟合面的重心 $\begin{matrix} \bar{P} \end{matrix}$ 替换为SR_A·Θ的重心。

图 5. 拟合面与原始点云重叠显示

Fig. 5. Overlap display of fitting plane and original

下载图片查看所有图片

步骤2, 计算线段的方向矢量。在三维空间中,一条直线的数学方程一般采用过此直线的任意两个非平行平面的方程表示,如(2)式所示,具体到本节描述的情形,如图6(a)所示,线段A为支持面Θ_left和Θ_right的交线,线段的方向矢量n_A用Θ_left·n和Θ_right·n的外积表示。

步骤3, 寻找两侧支持面各自投影值最大和最小的点。为了确定线段的端点,需要求解两侧支持区点集分别在线段上的投影范围。通过搜寻在线段方向上投影值最大和最小的支持区内点[如图6(b)

中的P_m和P_n两点]确定支持区投影范围:如图6(b)所示,首先在支持区中任意选定一点P₀,如果矢量 $\begin{matrix} \vec{P_{0} P_{i}} \end{matrix}$ 与线段方向矢量n_A的内积 $\begin{matrix} \vec{P_{0} P_{i}} \end{matrix}$ ·n_A小于零,则将P_i点作为线段的未投影起点候选点(记为:P_s候选点),如果大于零,则将其作为线段的未投影终点候选点(记为:P_e候选点);然后依次判断P_s和P_e两点与剩余点P_j之间连线矢量与n_A的内积之间的关系,如果 $\begin{matrix} \vec{P_{e} P_{j}} \end{matrix}$ 与n_A的内积大于零,将此点保存为P_e,如果 $\begin{matrix} \vec{P_{s} P_{j}} \end{matrix}$ 与n_A的内积小于零,将此点保存为P_s,否则不更新候选点。

步骤4, 求解线段端点。步骤3在两侧支持区分别得到了一套线段未投影端点候选点,这些候选点在支持面交线上的投影点即为线段的端点候选点。首先将两套候选点按照步骤3选定候选点时采用的内积判定法的思路确定线段的分布区域[图6(b)中的黄色标示区域,并将P和'_mP_n两点分别作为P_e和P_s],然后求取P_s和P_e在两支持面上的投影点作为线段的端点P_AS和P_AE。对于线段起点P_AS的计算,通过求解两支持面与过P_s法矢为n_A的平面之间的三面交点可得,P_AE的求解思路与P_AS相同。

步骤5, 结果的优化。尽管在步骤1~步骤4中将线段端点的计算约束在线段的支持区中一定程度上减弱了端点误判情形,但仍不可能完美地解决此问题,如图7(a)所示,三面相交的墙角位置处几条线段共用同一个端点,但实际提取的相交线段的端点之间存在一定的错位,需要进行进一步的端点合并等处理,以优化线段提取结果。由于结构线段是依据支持面的方程求解所得,因此线段需进行端点合并

图 6. 结构线段与其支持区。(a)结构线段相关变量定义;(b)支持区两侧点集的各自投影范围(黄色区域为最终选用支持区)

Fig. 6. Structure line and its support regions. (a) Definition of corresponding parameters of structure line; (b) projection regions of the support regions (yellow region is the final selected support region)

下载图片查看所有图片

图 7. 结构线段的优化。(a)优化前;(b)优化后

Fig. 7. Refinement of structure line segments. (a) Before refinement; (b) after refinement

下载图片查看所有图片

的情形比较单一,即在线段相交区域如果线段的端点距离小于两者的支持区宽时,合并这两个邻接端点。图7(a)所示问题经过优化后的效果如图7(b)所示。

2.6 精度的评定

为了对算法提取的结构线段进行量化的精度评定,定义标准差σ_υ来衡量支持区点集到结构线段A的平均距离。对于每个支持区内点P_i∈SR_A·Θ_left∪SR_A·Θ_right,其到结构线段A的距离定义为

\begin{matrix} Pt 2 VS h ape_dist (P_{i}, A) = |(P_{i} - Θ \cdot \bar{P}) \cdot Θ \cdot n|, (6) \end{matrix}

式中,

\begin{matrix} Θ = \underset{Θ \in {Θ_{left}, Θ_{rig h t}}}{ar g_{} \min} (|(P_{i} - Θ \cdot \bar{P}) \cdot Θ \cdot n|), (7) \end{matrix}

则结构线段的标准差σ_υ可用下式计算:

\begin{matrix} σ_{υ} = \sqrt[]{\frac{\overset{i = (k_{L} + k_{R})}{\sum_{i = 1}} Pt 2 VS h ape_dist (P_{i} {, A)}^{2}}{k_{L} + k_{R}}}, (8) \end{matrix}

式中k_L和k_R分别为SR_A·Θ_left和SR_A·Θ_right包含的点的个数。点云场景中所有结构线段提取结果的平均标准差 $\begin{matrix} {\bar{σ}}_{υ} \end{matrix}$ 为各条结构线段σ_υ的平均值。

此精度评定指标的绝对大小受点云的厚度决定,其相对大小可反映提取的结构线段与其支持区点云的靠近程度,从而可以反映其提取精度。

3 实验与分析

3.1 实验数据

为验证所提出的方法,利用实测和模拟点云数据进行算法的验证与对比。其中,数据Data1为文献[ 20]提供的在巴黎市某街道采集得到的建筑数据,主要用于本研究的平面分割实验;数据Data2和Data3分别为Robotic 3D Scan Repository^[21]和AIM@SHAPE repository^[22]开源提供的多站地面三维激光扫描测量获取的较为完整的教堂建筑点云,欧式教堂建筑一般为非规则结构,平面分布较为复杂;数据Data4为郑州信大先进技术研究院提供的单站单视角地面三维激光扫描测量获取的某规则建筑立面,其包含了较多的结构线段片段,部分结构线段由于视角问题并不能有效呈现;数据Data5为郑州信大先进技术研究院提供的从建筑模型上采样得到的点云,数据较为理想,平面和结构线段特征都得到较为完美的呈现。实验数据的相关信息如表1所示。

表 1. 实验数据相关信息

Table 1. Information of experimental data

Data information	Data1	Data2	Data3	Data4	Data5
Data volume /10⁶	13.8	13.1	32.8	4.7	100.0
Point interval /cm	3.79	1.74	0.78	2.37	1.24

查看所有表

3.2 平面分割对比实验

本研究中基于体素生长的平面分割方法是在文献[ 23]算法(下文简称OB算法)的基础之上改进得到,为了验证新算法的效果,将本算法的分割结果与OB算法的结果进行比对分析。由于OB算法需要输入较多的阈值参数(包括d_I, d_min, σ_th, θ_th及d_th等5种),实验中将OB算法所需参数依据本算法通过自动统计得到的参数来设定。

利用数据Data1进行实验验证,得到平面分割结果对比如图8和表2所示,其中精度和召回率信息为对图8所示局部区域的平面分割结果进行统计得到。由于进行了体素信息的统计以及采用分层生长的方式,本算法较OB算法效率略有降低,但从分割结果可以看出,本方法可以得到更为精细的平面分割结果,类似Data1中门窗框架等特征都可以得到有效分割。

3.3 结构线段提取实验结果与分析

对实验数据执行本研究所提的结构线段提取算法,线段提取结果的效果如图9所示,提取的线段数目和效率如表3所示。

图 8. 数据Data1平面分割结果(不同颜色区分不同平面)。(a)数据Data1及其局部;(b) OB算法分割结果;(c)本算法分割结果

Fig. 8. Segmentation result of Data1 (different planes are shown in different color). (a) Data1 and its local feature; (b) segmentation result of OB method; (c) segmentation result of the proposed method

下载图片查看所有图片

图 9. 结构线段提取结果。(a) Data2; (b) Data3; (c) Data4; (d) Data5; (e) Data2的提取结果; (f) Data3的提取结果; (g) Data4的提取结果; (h) Data5的提取结果

Fig. 9. Extraction results of structure line segments. (a) Data2; (b) Data3; (c) Data4; (d) Data5; (e) extraction result of Data2; (f) extraction result of Data3; (g) extraction result of Data4; (h) extraction result of Data5

下载图片查看所有图片

表 2. 平面分割实验结果对比

Table 2. Comparison of experimental results of planer segmentation

Item	Time cost /s	Plane number	Precision	Recall
OB	35.6	933	86.2	84.7
Proposed method	48.8	1029	98.9	98.2

查看所有表

从实验结果可知:

1) 得益于本算法对点云进行较为精细的平面分割,点云中的可视结构线段基本可以得到有效的提取;

2) 得益于从体素层面对结构线段进行快速定位与提取,算法整体效率较高;

表 3. 实验数据相关处理结果

Table 3. Processing results of experimental data

Data information	Data2	Data3	Data4	Data5
Plane number	5293	7168	5111	3383
Line segment number	6841	9522	3568	8707
Time cost for plane segmentation /s	50.9	51.9	27.9	208.6
Time cost for line segment extraction /s	9.4	7.4	4.0	28.3

查看所有表

3) 对比图9所示4组数据的不同完整度可知,数据的完整度越高,结构线段提取结果越完善。例如,图中数据Data4采用地面三维激光扫描仪进行单站扫描测量得到,相当于仅从一个视角观察目标区域,部分结构线不能得到完整的体现,而数据Data5相当于一个相反的极端,目标物体各个视角的点云基本都具备完整性,从而结构线段得到了最完美的体现;

4) 对比图9所示4组数据的不同建筑类别可知,本算法由于针对的是结构直线段特征的提取,从而更加适用于规则建筑点云的处理,而对于类似教堂等非规则建筑的点云,在较多部位提取的结构线段实际上并非直线段,而是对曲线的一种分段近似,不能得到较为理想的曲线提取结果。

3.4 结构线段提取对比实验

为了对比验证本研究所提的结构线段提取算法的提取效果,在本组实验中将本算法的实验结果与文献[ 13]采用的基于RANSAC平面相交的方法(下文用“RPB”表示)得到的结果作对比;为了对比验证本算法的效率,首先利用本研究所提的基于体素生长的平面分割算法对点云进行分割,然后利用文献[ 10-13]等采用的平面相交的方式提取结构线段(为表述简便,下文将此种方式用“VPB”表示),最后将VPB方法的结果及耗时与本算法进行对比。

各算法的结构线段提取效果对比如图10所示,执行效率和精度对比结果如表4所示,其中d_th和θ_th分别为平面分割时输入的点到平面的距离因子阈值及法矢夹角阈值,“点线距”为在利用(5)式确定线段端点时阈值w的设定值,即仅采用平面中满足“点线距”约束下的点进行线段端点的计算,实验中RPB算法的此值设置为10倍平面拟合标准差Θ·σ,VPB方法设置为10倍各平面的平均点间距d_avg,本算法设置为种子体素的宽度。

图 10. Data4结构线段提取结果对比。(a)原始测试数据;(b) RANSAC算法平面分割结果;(c)本算法平面分割结果;(d) RPB算法提取结果;(e) VPB算法提取结果;(f)本算法提取结果(为便于比对未显示线段支持区)

Fig. 10. Comparision of structure line segment extracting results of Data4. (a) Original test data; (b) plane segmentation result of RANSAC algorithm; (c) plane segmentation result of the proposed method; (d) extraction result of RPB algorithm; (e) extraction result of VPB algorithm; (f) extraction result of the proposed method (the support regions are hidden for comparision)

下载图片查看所有图片

表 4. 算法执行效率及精度对比

Table 4. Efficiency and accuracy comparison of the algorithms

Item	Threshold				Plane number	Time cost /s			$\begin{matrix} {\bar{σ}}_{υ}_{} \end{matrix}$ /cm
Item		$\begin{matrix} {d_{t h}}_{} \end{matrix}$ /m	$\begin{matrix} {θ_{t h}}_{} \end{matrix}$ /(°)	Point-line distance /m		Segmentation	Line extraction	Total	Before centralization	After centralization
RPB	0.01	25.0	10×Θ·σ		888	38.8	23.1	61.9	1.45	—
VPB	—	—	10×d_avg		5111	27.9	151.6	179.5	2.03	—
Proposed method	—	—	—		5111		4.0	31.9	1.87	1.43

查看所有表

从图10和表4展示的对比实验结果可以得出以下结论:

1) 对比分析图10(d)和(e)分别展示的RPB算法和VPB算法的结构线段提取结果可知,由于RANSAC算法倾向于将平行共面的非邻接平面分割成为一个平面,例如数据Data4中存在有众多阵列分布的窗体,窗体一般包含上下左右4个框架面,RANSAC算法倾向于将各个窗体相互平行的框架面分割为一个平面,这实际上是一种欠分割的表现,从而易导致图10(d)所示的结构线段纵横交错的错误结果,需要进行进一步的线段分割处理,而同样采用平面相交提取结构线段的VPB方法是基于平面特征的精细分割,基本不存在类似于RPB算法的错误。

2) 综合对比分析图10展示的三种算法的结构线段提取结果可知,基于本研究采用的平面分割方法的VPB算法与本算法的结果较为近似,由此可知基于平面相交结构线段提取的效果受制于平面分割的效果。

3) 从表4展示的算法执行效率对比中可知,由于基于平面相交的方法需要在平面分割结果的全局进行两两相交判断,在平面数目增加时处理效率会急剧降低;本研究基于体素生长的方式避免了盲目的平面间相交判断,处理效率高于基于平面相交的方式,线段提取效率相比平面相交方法提高了10倍以上。

4) 从表4展示的算法计算结果的精度对比中可知,本算法由于采用了支持面向支持区重心的归化,结构线段提取的平均标准差得到了一定程度的降低,精度提高了0.25倍左右;VPB算法与本算法采用重心归化前的精度近似;RPB算法由于事先将点到平面的距离约束到1 cm范围以内,仅提取平整度相对较高的平面,得到标准差的值较小。

4 结论

提出了一种基于八叉树体素生长的结构线段提取方法,其核心思路是利用体素层面的操作进行点云的平面分割以及结构线段的快速定位与提取。该方法首先对点云进行体素化剖分与平面分割,然后根据各体素与其邻域体素之间的共面关系筛选出结构线段的潜在分布区域,实现对点云中结构线段的定位,然后采用体素生长的方式在定位区域中进行结构线段支持区的分割,最后在分割结果中进行结构线段的提取与优化,并对其提取结果进行精度评定。实验中,对不同类型的测试数据处理的效果和效率以及与现有处理方式的对比结果证明了此方法可以相对高效地实现对结构线段的有效提取。

本算法的主要局限性在于:由于采用平面方程联立求解的方式提取平面的交线,因此只能提取平面“V”型相交的结构线段,而在类似图1所示墙面区域上下两平行平面相接的“-_”型相接区域,虽然原则上存在一个连接两个平行平面的连接面,但由于两平行面距离过近或存在遮挡等因素,连接面不能被有效分割,从而导致在 “-_” 类型区域不能有效提取线段[图1(c)平面分割结果和图1(f)线段提取结果的对比可以反映出此问题]。本算法主要贡献在于:在初始参数基础上八叉树体素剖分及生长阈值选用的自适应化,算法自动适应数据,实现了在整个平面分割与结构线段提取处理过程中无需人工输入额外参数,并且基于体素生长提取点云结构线段的方式依托于点云分布,可以快速有效地获取较为完整且精度较高的平面交线。

参考文献

[1] 梁玉斌. 面向建筑测绘的地面激光扫描模式识别方法研究[D]. 武汉: 武汉大学, 2013.

梁玉斌. 面向建筑测绘的地面激光扫描模式识别方法研究[D]. 武汉: 武汉大学, 2013.

Liang YB. Research on pattern recognition methods for terrestrial laser scanning towards building surveying and mapping[D]. Wuhan: Wuhan University, 2013.

[2] HernándezJ, Marcotegui B. Filtering of artifacts and pavement segmentation from mobile lidar data[C]. ISPRS Workshop Lasers Scanning, 2009, Part3/W8: 329- 333.

HernándezJ, Marcotegui B. Filtering of artifacts and pavement segmentation from mobile lidar data[C]. ISPRS Workshop Lasers Scanning, 2009, Part3/W8: 329- 333.

[3] Von Gioi R G, Jakubowicz J, Morel J M, et al. . LSD: a fast line segment detector with a false detection control[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2010, 32(4): 722-732.

Von Gioi R G, Jakubowicz J, Morel J M, et al. . LSD: a fast line segment detector with a false detection control[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2010, 32(4): 722-732.

[4] Von Gioi R G, Jakubowicz J, Morel J M, et al. . LSD: a line segment detector[J]. Image Process on Line, 2012, 2(4): 35-55.

Von Gioi R G, Jakubowicz J, Morel J M, et al. . LSD: a line segment detector[J]. Image Process on Line, 2012, 2(4): 35-55.

[5] 车尔卓, 詹庆明, 金志诚, 等. 基于激光点云的建筑平立剖面图半自动绘制[J]. 激光与红外, 2015, 45(1): 12-16.

车尔卓, 詹庆明, 金志诚, 等. 基于激光点云的建筑平立剖面图半自动绘制[J]. 激光与红外, 2015, 45(1): 12-16.

Che E Z, Zhan Q M, Jin Z C, et al. Semiautomatic drawing of plan-view, front-view and section-view of a building based on terrestrial laser scanning[J]. Laser & Infrared, 2015, 45(1): 12-16.

[6] Lin Y, Wang C, Cheng J, et al. Line segment extraction for large scale unorganized point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 102(1): 172-183.

Lin Y, Wang C, Cheng J, et al. Line segment extraction for large scale unorganized point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 102(1): 172-183.

[7] BouchenyC. Interactive scientific visualization of large datasets: towards a perceptive-based approach[D]. Grenoble: Joseph Fourier University, 2008.

BouchenyC. Interactive scientific visualization of large datasets: towards a perceptive-based approach[D]. Grenoble: Joseph Fourier University, 2008.

[8] Cimarusti D L, Saito K, Vaughn J E, et al. Extraction of ridge and valley lines from unorganized points[J]. Multimedia Tools & Applications, 2013, 63(1): 265-279.

Cimarusti D L, Saito K, Vaughn J E, et al. Extraction of ridge and valley lines from unorganized points[J]. Multimedia Tools & Applications, 2013, 63(1): 265-279.

[9] Altantsetseg E, Muraki Y, Matsuyama K, et al. Feature line extraction from unorganized noisy point clouds using truncated Fourier series[J]. Visual Computer, 2013, 29(6-8): 617-626.

Altantsetseg E, Muraki Y, Matsuyama K, et al. Feature line extraction from unorganized noisy point clouds using truncated Fourier series[J]. Visual Computer, 2013, 29(6-8): 617-626.

[10] BorgesP, ZlotR, BosseM, et al. Vision-based localization using an edge map extracted from 3D laser range data[C]. IEEE International Conference on Robotics and Automation, 2010, 58( 8): 4902- 4909.

BorgesP, ZlotR, BosseM, et al. Vision-based localization using an edge map extracted from 3D laser range data[C]. IEEE International Conference on Robotics and Automation, 2010, 58( 8): 4902- 4909.

[11] MoghadamP, BosseM, ZlotR. Line-based extrinsic calibration of range and image sensors[C]. IEEE International Conference on Robotics and Automation, 2013: 3685- 3691.

MoghadamP, BosseM, ZlotR. Line-based extrinsic calibration of range and image sensors[C]. IEEE International Conference on Robotics and Automation, 2013: 3685- 3691.

[12] RabbaniT, Heuvel F A V D, Vosselman G. Segmentation of point clouds using smoothness constraint[C]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006: 248- 253.

RabbaniT, Heuvel F A V D, Vosselman G. Segmentation of point clouds using smoothness constraint[C]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006: 248- 253.

[13] Poreba M, Goulette F. A robust linear feature-based procedure for automated registration of point clouds[J]. Sensors, 2015, 15(1): 1435-1457.

Poreba M, Goulette F. A robust linear feature-based procedure for automated registration of point clouds[J]. Sensors, 2015, 15(1): 1435-1457.

[14] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[15] Schnabel R, Wahl R, Klein R. Efficient RANSAC for point-cloud shape detection[J]. Computer Graphics Forum, 2007, 26(2): 214-226.

Schnabel R, Wahl R, Klein R. Efficient RANSAC for point-cloud shape detection[J]. Computer Graphics Forum, 2007, 26(2): 214-226.

[16] Chen J, Chen B. Architectural modeling from sparsely scanned range data[J]. International Journal of Computer Vision, 2008, 78(2): 223-236.

Chen J, Chen B. Architectural modeling from sparsely scanned range data[J]. International Journal of Computer Vision, 2008, 78(2): 223-236.

[17] Filin S, Pfeifer N. Neighborhoodsystems for airborne laser data[J]. Photogrammetric Engineering & Remote Sensing, 2005, 71(6): 743-755.

Filin S, Pfeifer N. Neighborhoodsystems for airborne laser data[J]. Photogrammetric Engineering & Remote Sensing, 2005, 71(6): 743-755.

[18] 官云兰, 程效军, 施贵刚. 一种稳健的点云数据平面拟合方法[J]. 同济大学学报(自然科学版), 2008, 36(7): 981-984.

官云兰, 程效军, 施贵刚. 一种稳健的点云数据平面拟合方法[J]. 同济大学学报(自然科学版), 2008, 36(7): 981-984.

Guan Y L, Cheng X J, Shi G G. A robust method for fitting a plane to point clouds[J]. Journal of Tongji University (Natural Science), 2008, 36(7): 981-984.

[19] DemantkéJ, MalletC, DavidN, et al. Dimensionality based scale selection in 3D LiDAR point clouds[C]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Laser Scanning, 2011, 38( 5): 97- 102.

DemantkéJ, MalletC, DavidN, et al. Dimensionality based scale selection in 3D LiDAR point clouds[C]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Laser Scanning, 2011, 38( 5): 97- 102.

[20] Vallet B, Brédif M, Serna A, et al. TerraMobilita/iQmulus urban point cloud analysis benchmark[J]. Computers & Graphics, 2015, 49: 126-133.

Vallet B, Brédif M, Serna A, et al. TerraMobilita/iQmulus urban point cloud analysis benchmark[J]. Computers & Graphics, 2015, 49: 126-133.

[21] BorrmannD, ElsebergJ. Robotic 3D scan repository-12[EB/OL]. http: ∥kos.informatik.uni-osnabrueck.de/3Dscans/.

BorrmannD, ElsebergJ. Robotic 3D scan repository-12[EB/OL]. http: ∥kos.informatik.uni-osnabrueck.de/3Dscans/.

[22] AIM@SHAPE repository[EB/OL]. http: ∥kos.informatik.uni-osnabrueck.de/3Dscans/.

AIM@SHAPE repository[EB/OL]. http: ∥kos.informatik.uni-osnabrueck.de/3Dscans/.

[23] Vo A V, Linh T H, Laefer D F, et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 104: 88-100.

Vo A V, Linh T H, Laefer D F, et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 104: 88-100.

李明磊, 宗文鹏, 李广云, 王力. 基于体素生长的点云结构直线段提取[J]. 光学学报, 2018, 38(1): 0112001. Minglei Li, Wenpeng Zong, Guangyun Li, Li Wang. Extraction of Structure Line Segments from Point Clouds Using Voxel-Based Region Growing[J]. Acta Optica Sinica, 2018, 38(1): 0112001.

基于体素生长的点云结构直线段提取 下载： 1257次

1 引言

2 结构线段的提取

2.1 点云的体素化剖分

图 1. 所提算法流程。(a)原始点云;(b)体素生成;(c)平面分割;(d)潜在线段支持区体素的识别;(e)提取结构线段支持区;(f)三维结构线段的提取与结果优化;(g)算法流程图

Fig. 1. Procedure of the proposed method. (a) Original point cloud; (b) voxelization; (c) plane segmentation; (d) recognition of potential support voxels; (e) segmentation of support regions; (f) extraction of three-dimensional structure line segments and refinement; (g) algorithm flow chart

2.2 基于体素生长的平面分割

图 2. 相邻共面体素的法矢夹角与体素尺寸和拟合标准差之间的关系示意图

Fig. 2. Sketch map for the relationship among intersection angle, voxel size and fitting standard deviation value of two neighbor coplanar voxels

2.3 线段支持区体素的预筛选

图 3. 潜在线段支持区的筛选。(a)八叉树体素全局结构;(b)非边缘且非边缘相邻体素(红色体素块)位置示意;(c)潜在线段支持区体素(红色体素块)

Fig. 3. Recognition of potential support voxels. (a) Global structure of octree voxels; (b) distribution of non-edge and non-edge adjacent voxels which are shown in red; (c) potential support voxels which are shown in red

2.4 支持区点集的体素生长提取

2.5 结构线段的提取与优化

图 5. 拟合面与原始点云重叠显示

Fig. 5. Overlap display of fitting plane and original

图 6. 结构线段与其支持区。(a)结构线段相关变量定义;(b)支持区两侧点集的各自投影范围(黄色区域为最终选用支持区)

Fig. 6. Structure line and its support regions. (a) Definition of corresponding parameters of structure line; (b) projection regions of the support regions (yellow region is the final selected support region)

图 7. 结构线段的优化。(a)优化前;(b)优化后

Fig. 7. Refinement of structure line segments. (a) Before refinement; (b) after refinement

2.6 精度的评定

3 实验与分析

3.1 实验数据

表 1. 实验数据相关信息

Table 1. Information of experimental data

3.2 平面分割对比实验

3.3 结构线段提取实验结果与分析

图 8. 数据Data1平面分割结果(不同颜色区分不同平面)。(a)数据Data1及其局部;(b) OB算法分割结果;(c)本算法分割结果

Fig. 8. Segmentation result of Data1 (different planes are shown in different color). (a) Data1 and its local feature; (b) segmentation result of OB method; (c) segmentation result of the proposed method

图 9. 结构线段提取结果。(a) Data2; (b) Data3; (c) Data4; (d) Data5; (e) Data2的提取结果; (f) Data3的提取结果; (g) Data4的提取结果; (h) Data5的提取结果

Fig. 9. Extraction results of structure line segments. (a) Data2; (b) Data3; (c) Data4; (d) Data5; (e) extraction result of Data2; (f) extraction result of Data3; (g) extraction result of Data4; (h) extraction result of Data5

表 2. 平面分割实验结果对比

Table 2. Comparison of experimental results of planer segmentation

表 3. 实验数据相关处理结果

Table 3. Processing results of experimental data

3.4 结构线段提取对比实验

图 10. Data4结构线段提取结果对比。(a)原始测试数据;(b) RANSAC算法平面分割结果;(c)本算法平面分割结果;(d) RPB算法提取结果;(e) VPB算法提取结果;(f)本算法提取结果(为便于比对未显示线段支持区)

表 4. 算法执行效率及精度对比

Table 4. Efficiency and accuracy comparison of the algorithms

4 结论

Article Outline

相关论文

相关资讯

关于本站 Cookie 的使用提示

全站搜索

基于体素生长的点云结构直线段提取下载： 1257次