基于区域聚类分割的点云特征线提取

王晓辉; 吴禄慎; 陈华伟; 胡赟; 石雅莹

doi:doi:10.3788/AOS201838.1110001

光学学报, 2018, 38 (11): 1110001, 网络出版: 2019-05-09

基于区域聚类分割的点云特征线提取下载： 1424次

Feature Line Extraction from a Point Cloud Based on Region Clustering Segmentation

论文大纲

王晓辉 ^1,2,*吴禄慎 ^1,*陈华伟 ¹胡赟 ¹石雅莹 ¹

作者单位

¹ 南昌大学机电工程学院, 江西南昌 330031

² 赤峰学院建筑与机械工程学院, 内蒙古赤峰 024000

AI 词云图 AI语音精读 AI语音超短摘要

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

摘要

提出一种非结构化点云特征线提取方法,其过程主要分为区域分割和特征检测两个阶段。在区域分割阶段,引入社会粒子群优化模糊C-均值聚类算法对点云数据进行区域聚类,得到边界清晰的各个分区,便于后续边界特征的提取;在特征检测阶段,对各个分区进行局部径向基函数曲面重构,以获取各个分区内采样点的曲率信息。提出基于平均曲率计算的局部特征权值,并通过局部特征权值和曲率极值法对特征点进行双重检测。并通过建立特征点的最小生成树构建特征曲线。对不同点云模型进行特征线提取实验,结果表明,本文方法既能够提取点云模型中的显著特征和尖锐特征,也能够很好地提取特征强度变化的曲线特征。

Abstract

This study presents a novel methodology to extract feature lines from unorganized point clouds. In this study, the extraction of feature lines from point clouds is divided into two stages: region segmentation and feature detection. In the region segmentation stage, the social particle swarm optimization fuzzy C-means clustering algorithm is introduced to cluster the point cloud data; further, each partition is obtained with a clear boundary, which is beneficial to extract the boundary features. In the feature detection stage, local surface reconstruction that is based on the radial basis function is conducted for each partition. Additionally, the curvature values of the sampling points are calculated according to the established local implicit surface; further, local feature weights that are based on the mean curvature are proposed. The feature points can be identified based on the local feature weights using the curvature extremum method. Finally, the feature lines can be generated by establishing the minimum spanning tree of the feature points. Different point cloud models are selected to perform the feature line extraction experiments. The experimental results exhibit that the proposed method can extract significant and sharp features from the point cloud models along with the curve features with intensity variations.

1 引言

点云数据的特征提取是计算机可视化、数字几何处理及逆向工程等领域中的一项重要研究内容,已广泛用于曲面重建、数据分割、曲线匹配和拼接等几何处理中。目前,对点云特征提取的研究主要集中在对特征线的提取及运算上。在三维点云数据中,特征线是特征点的有序连接,可用于反映三维模型的表面结构特征及其几何形状。通过对三维点云数据进行分析,可准确识别能代表点云模型特征的数据点,从而获得特征曲线。

点云数据的特征提取是指从点云模型中识别出几何模型的轮廓、尖锐处、凸凹处和过渡光滑处的结构特征及形状特征的过程。特征提取主要有基于点和基于三角网格2种方式。学者们从分析点云数据的邻域信息及几何特性方面入手,对特征线提取问题展开了研究。Gumhold等^[1]通过计算邻域图建立局部点云之间的连接信息,并用主成分分析法确定特征点,但对曲面凹凸性差别小的谷脊特征提取效果较差;Pauly等^[2]在前述方法的基础上引入多尺度分析,通过分析局部邻域内的点成为特征点的可能性,以此来识别特征点,这种方法更为稳健抗噪。Demarsin等^[3]提出了一种基于图论的点云特征线提取算法。采用一级分割法提取候选特征点,并对其进行图形化处理重新获得尖锐特征线,构造最小生成树重新连接特征线,但该算法仅能应用于均匀分布的点云数据。Kim等^[4]使用近似移动最小二乘法,通过逼近曲面来估计曲率及其导数,然后,利用Delaunay三角剖分来计算邻域信息,从而提取谷脊点。但该方法不能用于包含少量邻域点的尖锐点处。Ni等^[5]提出了一种邻域几何属性分析方法(AGPN),用于检测点云的三维边缘和跟踪特征线。在边缘检测步骤中,通过分析每个查询点邻域的几何性质,结合随机采样一致性(RANSAC)和角间隙度量来检测边缘。在特征线跟踪步骤中,采用基于区域生长和模型拟合的混合方法跟踪特征线。该方法可靠性好,且AGPN对输入数据的点密度不敏感。Altantsetseg等^[6]使用截取的傅里叶级数检测点云中的特征点,并使用曲率加权拉普拉斯算子平滑方法稀疏潜在特征点,再通过增加提取点来构造特征线,并投影到原始点云上。聂建辉等^[7]将符号曲面变化度与特征区域分割相结合,为点云数据提供了一种有效的特征线提取方法。但是该方法在强噪声的情况下,易导致提取的特征线出现断裂和缺损的情况。

在点云数据获取过程中,噪声和数据的不完整会直接影响点云特征的提取效果。为此,学者们通过引入数学方法来对特征提取算法进行改进。Park等^[8]提出了一种基于张量投票理论的新方法,可从包含随机噪声、孤立点和伪影的非结构化点云中提取尖锐特征,且对噪声起到了很好的抵制作用。Liu等^[9]使用多尺度算子,即法线的差来检测潜在特征线附近的特征点。Zhang等^[10]将基于泊松分布的统计模型作为一种工具用于从点云中提取特征点。该方法不需要预先进行曲面重构,并且不受噪声点、邻域尺度或点云采样质量的影响。李明磊等^[11]提出了一种基于体素生长的点云结构直线段提取方法,以体素为单位进行邻域判断,并采用基于体素的区域生长对结构直线段的分布区域进行分割,根据分布区域的范围及其所在平面的数学方程实现对特征的提取和优化。该方法可以准确高效地得到较为理想的特征提取结果。

对于结构复杂的点云模型,为了能使曲面的参数线在局部区域保持与几何特征的对应关系,可以先对点模型进行分区。张爱武等^[12]提出了一种机载LiDAR点云分类的自适应特征选择方法,其依据地形起伏情况对整体点云数据进行区域划分,自适应选择适宜该区域LiDAR点云分类的特征集合。该方法可以有效地降低特征维数,缩短运算时间,且分类精度较高。Weber等^[13]提出了一种使用高斯映射聚类进行特征检测的技术,利用高斯映射聚类对局部邻域上当前点组成的三角形的法向进行聚类,依据聚类个数判别特征点。该方法对尖锐特征信息敏感,但是对强度渐变的特征信息无法提取。Xu等^[14]研究了一种分割曲面和从不规则断裂碎片的三角网格中提取边缘特征线的新方法,通过使用基于顶点法向量的聚类算法来完成粗糙表面分割。为了区分原始面和断裂面,又引入了一种新的积分不变量来计算表面粗糙度。通过基于面法向量和粗糙度合并面来实现精确的表面分割,再基于表面分割提取边缘特征线。Bazazian等^[15]提出一种基于分割的多尺度边缘提取技术。根据测地距离通过全局分析对点云进行分割,再根据局部邻域定义多尺度算子。通过在点云的多个尺度上应用该算子,以确定特征的持续性。该方法提高了边缘的检测精度,且具有较好的稳健性。

由上述分析可知,点云特征提取结果主要受噪声干扰、数据的离散性和不完整性,以及点云模型自身的复杂性和多样性等因素的影响较大。现有的方法对点云模型的轮廓线、棱线等提取效果较好,但对过渡特征的提取仍存在一定的缺陷。过渡特征线是开曲线,过度强调其闭合特性并不能求取所有特征线。为此,本文提出了基于区域聚类分割的无组织点云特征线提取新方法。其应用社会粒子群优化模糊C-均值(SPSO-FCM)聚类算法对点云模型进行分区,将其划分为具有几何特征相似性的多个区域,且使曲面的参数线在局部区域保持与几何特征的对应关系,得到区域边界清晰的各个分区。然后对每一分区进行局部径向基函数(RBF)曲面重构,计算出局部区域点云的曲率信息,采用局部特征权值和曲率极值法识别特征点。构建特征点的最小生成树生成特征曲线。基于平均曲率的局部特征权值能表达采样点曲面变化形状,反映尖锐点的特性;分区求解曲率信息及特征信息,能减少计算量,提高时间效率。

2 本文算法

2.1 算法概述

输入点云数据采用聚类优化算法对点云进行区域分割,将点云划分为包含原始对象特征信息的各个聚类区域;再对每个分区的点云分别进行RBF曲面重构,并计算每一分区的曲率信息,通过设置局部特征权值和筛选曲率极值点来识别区域特征点;构建特征点的最小生成树,并进行分割、细化,提取出特征线。算法简易流程如图1所示。

图 1. 算法过程图。(a)原始点云;(b)聚类分割结果;(c)特征点识别结果;(d)生成特征线

Fig. 1. Overall procedure of the proposed method. (a) Original point cloud; (b) region clustering segmentation result; (c) feature point recognition result; (d) generation of the feature lines

下载图片查看所有图片

2.2 算法实施步骤

2.2.1 点云区域聚类

基于聚类的区域分割方法是将具有较高相似特征性的数据点进行统计分类的过程,分割得到的各个区域之间的交线为特征线。采用社会粒子群优化算法(SPSO)与模糊C-均值(FCM)聚类算法的混合方法来实现点云数据的区域划分。SPSO-FCM聚类方法为:1)用SPSO算法对种群进行初始化,并为每个粒子设置不同的跟随阈值;2)设置种群中每个粒子当前最优位置和初始种群的最优位置,更新自由粒子的位置和跟随粒子的速度和位置;3)采用模糊C-均值聚类算法求解隶属度矩阵,确定适应值函数,更新所有粒子的最优位置,并判断粒子和种群的位置优越性,得到准确的聚类中心,实现对点云数据的区域划分。SPSO算法具有较强的全局搜索能力,可避免FCM聚类算法容易陷入局部收敛的缺陷。SPSO-FCM聚类算法精度高,而且还有较好的抗噪性,可实现区域的准确分割,得到较清晰的区域边界,有利于边界特征点的提取。SPSO-FCM聚类算法的具体步骤详见文献[ 16]。

2.2.2 RBF隐式曲面的建立

径向基函数隐式曲面的建立是用来获取点云模型曲率信息。常用的点云曲率估算方法有主成分分析法、移动最小二乘法等,其中,主成分分析法对微分属性的估算粗糙且不精确,而移动最小二乘法计算复杂度较高。因此,选择基于RBF的曲率估算方法,主要是通过建立采样点的局部隐式曲面,并根据微分几何理论计算曲率等微分属性。基于RBF的重构曲面光滑性、连续性较好,方法自动化程度高,但重建速度慢。为改善重建速度慢、耗时的问题,对聚类分割后的每一个分区点云进行局部RBF曲面重构,此过程所涉及的采样点数较少,系数矩阵比较简单,可实现参数的快速求解。

定义点云中任一采样点p_i的k邻域为N_k(p_i),采用KD树方法对k邻域进行快速搜索,构建无组织点云之间的拓扑关系,对其k邻域内的点进行局部RBF曲面重构。根据经验值,k的取值范围为k∈[9,30]。选取不同的k值进行实验:当k值较小时,局部曲面拟合精度较低,影响曲面重构效果;当k值较大时,曲面拟合需要的时间较长,算法效率降低,而且搜索时间也受k值影响。因此,选择k=16。若三维空间中某一聚类区域的n个采样点为{p₁,p₂,…,p_i,…,p_n},且分别对应约束值{h₁,h₂,…,h_i,…,h_n}。如果能构造函数f(r)使得每个点均满足等式f(p_i)=h_i,那么方程f(p_i)=0就可以表示一个隐式曲面,则建立隐式曲面方程为

\begin{matrix} f (r) = \overset{n}{\sum_{j = 1}} ω_{j} ϕ (r - p_{j}) + P (r) = 0, (1) \end{matrix}

式中:r为插值约束点,即构建曲面时通过的任意散乱点;p_j为建立曲面所需的采样点;ω_j为对应每个采样点的径向基的权值;P(r)为一阶多项式,对任一点(x,y,z),P(r)=a₀+a₁x+a₂y+a₃z;ϕ(r-p_j)为径向基函数,常采用的形式为ϕ(x)= $\begin{matrix} {|x|}^{3} \end{matrix}$ 。

由给定的n个散乱点确定的约束条件为

\begin{matrix} \begin{matrix} f (p_{i}) = & \overset{n}{\sum_{j = 1}} ω_{j} ϕ (p_{i} - p_{j}) + P (p_{i}) = h_{i}, i = 1,2, \dots, n 。 (2) \end{matrix} \end{matrix}

使能量方程取得最小值需要满足下式的正交条件为

\begin{matrix} \overset{n}{\sum_{j = 1}} ω_{j} = \overset{n}{\sum_{j = 1}} ω_{j} p_{j}^{x} = \overset{n}{\sum_{j = 1}} ω_{j} p_{j}^{y} = \overset{n}{\sum_{j = 1}} ω_{j} p_{j}^{z} = 0 。 (3) \end{matrix}

由(2)、(3)式可以建立线性方程组为

\begin{matrix} [\begin{matrix} ϕ_{11} & ϕ_{12} & \dots & ϕ_{1 n} & 1 & p_{1}^{x} & p_{1}^{y} & p_{1}^{z} \\ ϕ_{21} & ϕ_{22} & \dots & ϕ_{2 n} & 1 & p_{2}^{x} & p_{2}^{y} & p_{2}^{z} \\ ︙ & ︙ & ︙ & ︙ & ︙ & ︙ & ︙ \\ ϕ_{n 1} & ϕ_{n 2} & \dots & ϕ_{nn} & 1 & p_{n}^{x} & p_{n}^{y} & p_{n}^{z} \\ 1 & 1 & \dots & 1 & 0 & 0 & \dots & 0 \\ p_{1}^{x} & p_{2}^{x} & \dots & p_{n}^{x} & 0 & 0 & \dots & 0 \\ p_{1}^{y} & p_{2}^{y} & \dots & p_{n}^{y} & 0 & 0 & \dots & 0 \\ p_{1}^{z} & p_{2}^{z} & \dots & p_{n}^{z} & 0 & 0 & \dots & 0 \end{matrix}] [\begin{matrix} ω_{1} \\ ω_{2} \\ ︙ \\ ω_{n} \\ a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{matrix}] = [\begin{matrix} h_{1} \\ h_{2} \\ ︙ \\ h_{n} \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}] 。 (4) \end{matrix}

解线性方程组(4),得唯一的一组解(ω₁,ω₂,…,ω_n,a₀,a₁,a₂,a₃)。将所得解代入(1)式,得到该隐式曲面方程为

\begin{matrix} \begin{matrix} f (x, y, z) = \overset{n}{\sum_{j = 1}} ω_{j} {[\sqrt[]{(x - p_{j}^{x})^{2} + (y - p_{j}^{y})^{2} + (z - p_{j}^{z})^{2}}]}^{3} + \\ a_{0} + a_{1} x + a_{2} y + a_{3} z 。 (5) \end{matrix} \end{matrix}

2.2.3 曲率信息估算

为聚类分割后的每一分区建立隐式曲面f(x,y,z),根据参数曲面的曲率性质计算其主曲率和主方向,并将其近似为采样点的曲率值。根据微分几何理论可知,局部曲面内采样点的高斯曲率K是主曲率的乘积,平均曲率H是主曲率之和的平均值。K与H符号设置的不同,可以代表不同的局部曲面类型。若采样点的最大主曲率为k₁,最小主曲率为k₂,相对应的最大主曲率方向为M₁,最小主曲率方向为M₂。那么高斯曲率和平均曲率可表示为

\begin{matrix} K = k_{1} k_{2}, H = \frac{k_{1} + k_{2}}{2} 。 (6) \end{matrix}

根据平均曲率符号得到采样点的凹凸信息,并基于平均曲率的方法提取特征点。

2.2.4 特征点识别

为点云中的每一个采样点设置一个特征权值,使之与采样点隶属于特征点的可能性成正比关系。本文提出利用点云平均曲率来计算点的局部特征权值,将局部特征权值与设置的阈值相比,从而检测出局部区域内潜在的特征点。局部特征权值反映了采样点平均曲率的离散程度,而方差能够反映数据偏离平均数的分布情况,因此,可以利用方差定义点云的局部特征权值。对于点云中任一点p_i∈P,其k邻域点集为q_i∈Q(i=1,2,…,k),已知k邻域点集内点q_i处的平均曲率为 $\begin{matrix} H_{q_{i}} \end{matrix}$ ,则定义采样点在k邻域下的局部特征权值为

\begin{matrix} ω (q_{i}, k) = \sqrt[]{\frac{1}{k} \overset{k}{\sum_{i}} {(|H_{q_{i}}| - \bar{V})}^{2}}, (7) \end{matrix}

式中 $\begin{matrix} \bar{V} \end{matrix}$ 是k邻域内点的平均曲率的平均值,即 $\begin{matrix} \bar{V} = \frac{1}{k} \overset{k}{\sum_{i}} H_{q_{i}} 。 \end{matrix}$

对于∀p_i∈P,若该点k邻域处的局部特征权值满足ω(q_i,k)>ω_max,则认为该点为k邻域下的特征点,其中ω_max为阈值,可由用户设定或通过系统自动计算得到。在局部特征权值大的区域,点的平均曲率的离散性较大,说明该区域内包含的特征信息量较大,则该点成为特征点的可能性就越大。因是对k邻域内众多采样点求解局部特征权值,所以,局部特征权值对单点噪声不敏感。因此,采用该方法检测特征点,可满足算法对高信息量、稳健性和较强抗噪性的要求。

将根据局部特征权值检测出的点作为候选特征点,沿着候选特征点的最大主曲率方向和最小主曲率方向搜索其曲率极值点,实际特征点即为候选特征点内的曲率极值点。在候选特征点中任选一点q,沿最大主曲率方向M₁找到其左右两个相邻点q_1l和q_1r,如果k₁(q)≥k₁(q_1l)且k₁(q)≥k₁(q_1r),则q为曲率极值点,即为检测出的实际特征点,其中k₁(q_1l)、k₁(q_1r)分别为点q_1l、q_1r沿最大主曲率方向M₁上的曲率值。否则,再沿最小主曲率方向M₂找到q点的左右两个相邻点q_2l和q_2r,若k₂(q)≤k₂(q_2l)且k₂(q)≤k₂(q_2r),则q为最小主曲率方向上的极值点,也可以作为实际特征点。由此,遍历候选特征点集中的每一个点,提取出当前集合中曲率极值点作为实际特征点,则在候选特征点集中删除非曲率极值点。特征点识别流程图如图2所示。

图 2. 特征点识别流程图

Fig. 2. Flow chart of the feature point recognition stage

下载图片查看所有图片

2.2.5 特征线生成

得到的实际特征点是杂乱无序、不包含任何拓扑信息,因此还需要通过构建特征曲线的方法对特征点进行连接。特征线生成步骤如下:1)根据采样点的局部特征权值大小,筛选出特征权值最大的点作为种子点,建立最小生成树,构建连通区域;2)将特征点连接成线;3)分割、细化细小分支,得到特征线。

3 实验结果与分析

3.1 不同点云模型的特征提取结果分析

在VS2013和OpenGL开发平台下实现本文特征提取方法,并在具有CPU Intel Core i5 2.6 GHz处理器和8 G内存的标准PC上对点云模型进行测试,实验结果如图3~6所示。

图 3. 模型1的特征线提取。(a)模型1原始点云;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 3. Feature line extraction from Model 1. (a) Original point cloud of Model 1; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

下载图片查看所有图片

图 4. 模型2的特征线提取。(a)模型2三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 4. Feature line extraction from Model 2. (a) Triangulated lighting model of Model 2; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

下载图片查看所有图片

图3为模型1特征线提取过程,其由5个规则平面和顶部一个不规则曲面构成,将点云数据聚类后,为凸显聚类结果,用不同颜色表示模型分区后的效果,如图3(b)所示。规则平面为S₃~S₇,顶部不规则曲面依据形状特征信息又划分为3个区域,分别为S₁、S₂和S₈。图3(c)、(d)中的红色点分别为检测出的候选特征点和识别出的真实特征点。模型1中的显著特征主要为直线特征,在其顶部包含了3条特征强度逐渐减弱的曲线特征。由图3(e)可看出,模型1的显著特征均得到正确提取,且尽可能多地提取了曲线特征。图4为模型2的特征线提取过程,其为八面体点云模型,特征线为八面体的棱线。图4(a)为模型2经三角化后的光照模型,能够更清晰地显示模型2的特征;图4(b)为SPSO-FCM区域分割结果,每一区域的边界划分清晰。图4(c)、(d)为特征点识别结果;图4(e)所示模型2的棱线均得到准确提取。图5所示为模型3特征线提取过程。图3~5所示点云模型结构比较规则,均包含显著特征信息,且以直线特征信息为主,模型中的尖锐特征信息也能得到较好识别。

模型4为Fandisk点云模型,其中既包含尖锐特征,也包含曲线特征,且曲线特征的强度是渐变的,其特征线提取过程如图6所示。将本文方法与

图 5. 模型3的特征线提取。(a)模型3三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 5. Feature line extraction from Model 3. (a) Triangulated lighting model of Model 3; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

下载图片查看所有图片

图 6. 模型4的特征线提取。(a)模型4三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 6. Feature line extraction from Model 4. (a) Triangulated lighting model of Model 4; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

下载图片查看所有图片

文献[ 13]提出的基于高斯法向聚类的特征提取方法进行比较,得到如图7所示的实验对比结果。结果显示,文献[ 13]方法可以提取Fandisk模型上的直线特征和曲线特征,但对于扇形区域的特征信息,没有很好的保留,未识别出部分特征强度逐渐减弱的曲线特征。图7(b)中,本文方法提取结果明显优于文献[ 13]方法。模型5为Vase点云模型,其特征信息以特征强度变化的曲线特征为主。为进一步验证本文方法对较弱特征的提取效果,应用两种方法对模型5进行特征线提取,对比结果如图8所示。本文方法不仅能够提取到大部分主要特征,同时还能提取到更多的强度较弱的特征。表1、2总结了特征提取流程不同阶段的性能数据。

图 7. 模型4特征提取方法比较。(a)文献[ 13]方法;(b)本文方法

Fig. 7. Comparison of the feature extraction methods used in Model 4. (a) Ref. [13] method; (b) proposed method

下载图片查看所有图片

图 8. 模型5特征提取方法比较。(a)模型5三角化光照模型;(b)文献[ 13]方法;(c)本文方法

Fig. 8. Comparison of the feature extraction methods used in Model 5. (a) Triangulated lighting model of Model 5; (b) Ref. [13] method; (c) proposed method

下载图片查看所有图片

综合上述实验分析可知,本文方法可以有效提取点云模型的主要特征信息,并且保证其精度;特征点识别及特征线生成时间较快,提高了特征线提取效率。

表 1. 不同阶段的点云数目

Table 1. Complexity in different stages

Model	Number of original point clouds	Number of candidate feature points	Number of feature points
Model 1	6177	1729	803
Model 2	13294	2924	1728
Model 3	40000	8799	5199
Model 4	54465	13071	7080
Model 5	25901	5957	3626

查看所有表

表 2. 特征提取流程中的时间参数

Table 2. Duration of the feature extraction pipeline in seconds

Model	Candidate feature point extraction time /s	Feature point extraction time /s	Feature line generation time /s
Model 1	0.040	0.039	0.241
Model 2	0.090	0.099	0.379
Model 3	0.346	0.286	1.763
Model 4	0.501	0.412	1.837
Model 5	0.190	0.164	0.796

查看所有表

3.2 k邻域尺度变化的敏感性

选择k个最邻近点来表示点的邻域,在特征点提取过程中,通过对不同邻域尺度(选取不同的k值)下提取的特征点的分析,证明除k值取过大或过小外,本文方法对邻域尺度的变化不敏感。由于采样不均匀,导致不同区域的k邻域尺度不同,但特征点却是相同的。凭经验k的取值范围可归纳为k∈[9,30],设定k=16作为所有最终结果的默认设置。图9所示为模型3和模型4在不同邻域尺度下的特征提取结果,两者均表现出不同程度的非均匀采集密度。邻域尺度在以下情况下对点云模型具有相当大的影响: 1)给定的点云非常不均匀;2)受到严重的噪声干扰。

图 9. 本文方法在不同邻域尺度下的特征线提取效果。(a1)模型3的原始点云及其局部放大细节;(a2) k=10,(a3) k=16,(a4) k=25的提取效果;(a5)模型3特征线;(b1)模型4的原始点云及其局部放大细节;(b2) k=10,(b3) k=16,(b4) k=25的特征线提取效果;(b5)模型4特征线

Fig. 9. Feature line extracted by the proposed method using different neighborhood scales. (a1) Original point cloud and its partial enlarged detail in Model 3; extraction effects with (a2) k=10, (a3)k=16, (a4)k=25; (a5) feature line of Model 3; (b1) original point cloud and its partial enlarged detail in Model 4; extraction effects with (b2) k=10, (b3) k=16, (b4) k=25; (b5) feature line of Model 4

下载图片查看所有图片

3.3 对噪声的稳健性

为验证本文方法对噪声的稳健性,通过Matlab软件给点云模型2和模型4添加适当的噪声进行实验。模型2中添加的信噪比分别为15 dB,20 dB和30 dB的高斯白噪声;模型4中添加的信噪比分别为45 dB,50 dB和60 dB的高斯白噪声。图10所示为噪声模型的特征提取结果,由于特征点是通过计算阈值和分析区域信息定义的,证明强度适中的噪声对点云模型的特征提取结果影响不大。随着噪声强度的增加,会使某些特征点缺失。模型4中,在具有尖锐特征的区域中出现大面积的梯度,随着噪声强度的增加,导致特征较弱点和边缘点丢失。因此,特征线重建时无法连接所有特征线,会出现特征线断裂的情况。

图 10. 本文方法在不同强度噪声下的特征提取结果。(a)~(c)模型2中分别添加15 dB、20 dB和30 dB的噪声; (d)~(f)模型4中分别添加45 dB、50 dB和60 dB的噪声

Fig. 10. Results of the proposed method for noisy datasets. (a)-(c) Add noise of 15 dB, 20 dB and 30 dB in Model 2, respectively; (d)-(f) add noise of 45 dB, 50 dB and 60 dB in Model 4, respectively

下载图片查看所有图片

4 结论

提出了一种基于区域聚类分割的散乱点云特征线提取方法,应用聚类算法对点云数据进行区域分割,得到区域边界清晰的子区域,再在此基础上分区进行点云特征信息的提取。这样有助于更准确地提取到点云模型的边界特征信息。同时,聚类算法所具有的良好的抗噪性可以降低对噪声点云特征信息的干扰。在特征点识别过程中,采用方差定义局部邻域内采样点的特征权值,并通过局部邻域内的采样点的平均曲率来计算特征权值。采用局部特征权值的方法能更好地提取尖锐特征点和弱特征信息。而在点云的曲率计算和特征提取过程中,采用局部分析的策略,可以减少计算量和复杂度,提高方法运行的效率,尤其适用于复杂的、特征类型多变的点云模型。

经实验验证,本文方法在提取到点云模型中显著特征、尖锐特征的同时,能够尽可能多地提取到强度变化的特征信息。但对于形状复杂、曲线特征信息较多的点云模型,所提取的特征线仍存在局部断裂或者不完整的情况。下一步研究工作将针对这个问题展开。此外,特征线的优化也是一个值得研究的方向。

参考文献

[1] GumholdS, Wang XL, MacleodR. Feature extraction from point clouds[C]∥International Meshing Roundtable, 2001: 293- 305.

[2] Pauly M, Keiser R, Gross M. Multi-scale feature extraction on point-sampled surfaces[J]. Computer Graphics Forum, 2003, 22(3): 281-289.

[3] Demarsin K, Vanderstraeten D, Volodine T, et al. Detection of closed sharp edges in point clouds using normal estimation and graph theory[J]. Computer-Aided Design, 2007, 39(4): 276-283.

[4] Kim S K. Extraction of ridge and valley lines from unorganized points[J]. Multimedia Tools and Applications, 2013, 63(1): 265-279.

[5] Ni H, Lin X G, Ning X G, et al. Edge detection and feature line tracing in 3D-point clouds by analyzing geometric properties of neighborhoods[J]. Remote Sensing, 2016, 8(9): 710.

[6] 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/7/8): 617-626.

[7] 聂建辉, 刘烨, 高浩, 等. 基于符号曲面变化度与特征分区的点云特征线提取算法[J]. 计算机辅助设计与图形学学报, 2015, 27(12): 2332-2339.

Nie J H, Liu Y, Gao H, et al. Feature line detection from point cloud based on signed surface variation and region segmentation[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(12): 2332-2339.

[8] Park M K, Lee S J, Lee K H. Multi-scale tensor voting for feature extraction from unstructured point clouds[J]. Graphical Models, 2012, 74(4): 197-208.

[9] Liu X S, Jin C N. Feature line extraction from unorganized noisy point clouds[J]. Journal of Computational Information Systems, 2014, 10(8): 3503-3510.

[10] Zhang Y H, Geng G H, Wei X R, et al. A statistical approach for extraction of feature lines from point clouds[J]. Computers & Graphics, 2016, 56: 31-45.

[11] 李明磊, 宗文鹏, 李广云, 等. 基于体素生长的点云结构直线段提取[J]. 光学学报, 2018, 38(1): 0112001.

Li M L, Zong W P, Li G Y, et al. Extraction of structure line segments from point clouds using voxel-based region growing[J]. Acta Optica Sinica, 2018, 38(1): 0112001.

[12] 张爱武, 肖涛, 段乙好. 一种机载LiDAR点云分类的自适应特征选择方法[J]. 激光与光电子学进展, 2016, 53(8): 082802.

Zhang A W, Xiao T, Duan Y H. A method of adaptive feature selection for airborne LiDAR point cloud classification[J]. Laser & Optoelectronics Progress, 2016, 53(8): 082802.

[13] WeberC, HahmannS, HagenH. Sharp feature detection in point clouds[C]∥IEEE International Conference on Shape Modeling and Applications, 2010: 175- 186.

[14] Xu J Y, Zhou M Q, Wu Z K, et al. Robust surface segmentation and edge feature lines extraction from fractured fragments of relics[J]. Journal of Computational Design and Engineering, 2015, 2(2): 79-87.

[15] BazazianD, Casas JR, Ruiz-HidalgoJ. Segmentation-based multi-scale edge extraction to measure the persistence of features in unorganized point clouds[C]∥International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, 2017: 317- 325.

[16] 王晓辉, 吴禄慎, 陈华伟, 等. 应用改进的粒子群优化模糊聚类实现点云数据的区域分割[J]. 光学精密工程, 2017, 25(4): 1095-1105.

Wang X H, Wu L S, Chen H W, et al. Particle swarm optimization fuzzy clustering[J]. Optics and Precision Engineering, 2017, 25(4): 1095-1105.

王晓辉, 吴禄慎, 陈华伟, 胡赟, 石雅莹. 基于区域聚类分割的点云特征线提取[J]. 光学学报, 2018, 38(11): 1110001. Xiaohui Wang, Lushen Wu, Huawei Chen, Yun Hu, Yaying Shi. Feature Line Extraction from a Point Cloud Based on Region Clustering Segmentation[J]. Acta Optica Sinica, 2018, 38(11): 1110001.

基于区域聚类分割的点云特征线提取下载： 1424次

1 引言

2 本文算法

2.1 算法概述

图 1. 算法过程图。(a)原始点云;(b)聚类分割结果;(c)特征点识别结果;(d)生成特征线

Fig. 1. Overall procedure of the proposed method. (a) Original point cloud; (b) region clustering segmentation result; (c) feature point recognition result; (d) generation of the feature lines

2.2 算法实施步骤

图 2. 特征点识别流程图

Fig. 2. Flow chart of the feature point recognition stage

3 实验结果与分析

3.1 不同点云模型的特征提取结果分析

图 3. 模型1的特征线提取。(a)模型1原始点云;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 3. Feature line extraction from Model 1. (a) Original point cloud of Model 1; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 4. 模型2的特征线提取。(a)模型2三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 4. Feature line extraction from Model 2. (a) Triangulated lighting model of Model 2; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 5. 模型3的特征线提取。(a)模型3三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 5. Feature line extraction from Model 3. (a) Triangulated lighting model of Model 3; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 6. 模型4的特征线提取。(a)模型4三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 6. Feature line extraction from Model 4. (a) Triangulated lighting model of Model 4; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 7. 模型4特征提取方法比较。(a)文献[ 13]方法;(b)本文方法

Fig. 7. Comparison of the feature extraction methods used in Model 4. (a) Ref. [13] method; (b) proposed method

图 8. 模型5特征提取方法比较。(a)模型5三角化光照模型;(b)文献[ 13]方法;(c)本文方法

Fig. 8. Comparison of the feature extraction methods used in Model 5. (a) Triangulated lighting model of Model 5; (b) Ref. [13] method; (c) proposed method

表 1. 不同阶段的点云数目

Table 1. Complexity in different stages

表 2. 特征提取流程中的时间参数

Table 2. Duration of the feature extraction pipeline in seconds

3.2 k邻域尺度变化的敏感性

3.3 对噪声的稳健性

图 10. 本文方法在不同强度噪声下的特征提取结果。(a)~(c)模型2中分别添加15 dB、20 dB和30 dB的噪声; (d)~(f)模型4中分别添加45 dB、50 dB和60 dB的噪声

Fig. 10. Results of the proposed method for noisy datasets. (a)-(c) Add noise of 15 dB, 20 dB and 30 dB in Model 2, respectively; (d)-(f) add noise of 45 dB, 50 dB and 60 dB in Model 4, respectively

4 结论

Article Outline

关于本站 Cookie 的使用提示

全站搜索

基于区域聚类分割的点云特征线提取 下载： 1424次

1 引言

2 本文算法

2.1 算法概述

图 1. 算法过程图。(a)原始点云;(b)聚类分割结果;(c)特征点识别结果;(d)生成特征线

Fig. 1. Overall procedure of the proposed method. (a) Original point cloud; (b) region clustering segmentation result; (c) feature point recognition result; (d) generation of the feature lines

2.2 算法实施步骤

图 2. 特征点识别流程图

Fig. 2. Flow chart of the feature point recognition stage

3 实验结果与分析

3.1 不同点云模型的特征提取结果分析

图 3. 模型1的特征线提取。(a)模型1原始点云;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 3. Feature line extraction from Model 1. (a) Original point cloud of Model 1; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 4. 模型2的特征线提取。(a)模型2三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 4. Feature line extraction from Model 2. (a) Triangulated lighting model of Model 2; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 5. 模型3的特征线提取。(a)模型3三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 5. Feature line extraction from Model 3. (a) Triangulated lighting model of Model 3; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 6. 模型4的特征线提取。(a)模型4三角化光照模型;(b)聚类分割结果;(c)候选特征点集;(d)特征点集;(e)特征线提取结果

Fig. 6. Feature line extraction from Model 4. (a) Triangulated lighting model of Model 4; (b) region clustering segmentation; (c) set of candidate feature points; (d) set of feature points; (e) feature line extraction results

图 7. 模型4特征提取方法比较。(a)文献[ 13]方法;(b)本文方法

Fig. 7. Comparison of the feature extraction methods used in Model 4. (a) Ref. [13] method; (b) proposed method

图 8. 模型5特征提取方法比较。(a)模型5三角化光照模型;(b)文献[ 13]方法;(c)本文方法

Fig. 8. Comparison of the feature extraction methods used in Model 5. (a) Triangulated lighting model of Model 5; (b) Ref. [13] method; (c) proposed method

表 1. 不同阶段的点云数目

Table 1. Complexity in different stages

表 2. 特征提取流程中的时间参数

Table 2. Duration of the feature extraction pipeline in seconds

3.2 k邻域尺度变化的敏感性

3.3 对噪声的稳健性

图 10. 本文方法在不同强度噪声下的特征提取结果。(a)~(c)模型2中分别添加15 dB、20 dB和30 dB的噪声; (d)~(f)模型4中分别添加45 dB、50 dB和60 dB的噪声

Fig. 10. Results of the proposed method for noisy datasets. (a)-(c) Add noise of 15 dB, 20 dB and 30 dB in Model 2, respectively; (d)-(f) add noise of 45 dB, 50 dB and 60 dB in Model 4, respectively

4 结论

Article Outline

相关论文

相关资讯

关于本站 Cookie 的使用提示

全站搜索

基于区域聚类分割的点云特征线提取下载： 1424次