一种结合边缘点和特征点的点云精简方法及其效果评价

杨森,花向红,李丞,水浩奇,高金彬,张涧栗

(1.武汉大学测绘学院,湖北 武汉 430079; 2.武汉大学灾害监测与防治研究中心,湖北 武汉 430079)

0 引 言

相比传统测量技术,三维激光技术在数据获取方面具有快速、精确等特点[1],被广泛应用于变形监测[2,3]、地形测绘[4]、文物保护[5]等领域。随着三维激光扫描技术的快速发展,设备采集的数据精度和速度都有了很大提升,数据量十分巨大,为后续点云处理带来了很大的困扰[6]。如何合理进行点云精简,减少无效特征点云,保证点云特征不受破坏成为点云数据预处理中一个重要研究内容。

国内外学者针对点云精简做了大量研究,根据精简思路主要分为三种:包围盒法、随机采样法和曲率采样法[7]。文献[8]通过构建点云法向量特征和点云曲率特征约束,结合体素包围盒算法,能够在不损失点云特征的情况下,实现点云的快速精简。文献[9]提出基于快速点特征直方图(FPFH)特征提取的点云精简算法,算法首先提取出点云边缘点,计算非边缘点的FPFH值得到点云特征点,利用特征值将点云分为特征区域和非特征区域,利用最远点采样算法对非特征区域进行采样,结果表明算法既能保留精简模型的完整性也能较好地保留点云的大部分特征信息。文献[10]先对点云进行k均值聚类,类内法方向差值大于阈值时拆分为两类,迭代得到分类结果,在平坦区域保留聚类中心,在非平坦区域保留法向量差值最大的点,得到的精简点云误差更小。文献[11]利用主成分分析(principal component analysis,PCA)方法估计点云法向量及其夹角,然后利用最近邻点获取法向量夹角的信息熵,根据熵的大小实现点云精简。文献[12]提出保留点云属性的点云精简方法,对点云X,Y轴方向进行分割运算,提取X-Y边界,对提取边界后的散乱点云数据构建K邻域,通过邻域计算模糊熵和曲率,剔除曲率小于阈值的点实现点云的精简。为此,本文针对获得的点云原始数据十分庞大和原始点云数据中存在大量冗余的问题,提出一种结合边缘点和特征点提取的点云精简方法。通过实验,采用精简率、豪斯多夫距离和几何失真指数三个评价指标,将本文方法与随机采样、均匀采样和法向空间采样三种方法精简结果进行了对比分析,得出了有益结论。

1 基本原理

针对获得的点云原始数据十分庞大和原始点云数据中存在大量冗余的问题,本文提出了一种结合边缘特征点和内部特征点提取,在非特征区域进行最远点采样的点云精简方法。该方法的基本思想如下:首先建立点云的K领域关系,根据PCA算法求得点云的边缘点;然后通过点云的K领域关系,计算点云的ISS特征点,对点云构造尺度空间求得点云的SIFT3D特征点,从而提取点云特征点;之后将边缘点和特征点的重心作为最远点采样的起始点,对空洞区域进行点云增补;最后将边缘点、特征点和最远点采样得到的三类点云合并,设置阈值去除重复点,实现点云精简。其方法流程如图1所示。

图1 本文方法流程图

1.1 基于PCA法矢估计的点云边界提取

对点云来说,边界轮廓是一种重要的特征,对点云边缘的提取可以最大限度地保留点云的边界特征,因此在精简点云数据前需要先将点云的边界提取出来。

法向量估计是提取物体边界特征的一个关键过程,估计点云表面法线可以转化为求点切面的问题,假设给定点p(xi,yi,zi),i=1,2,…,n,拟合的平面方程为zi=axi+byi+c,估计值和实际值之间的总误差方程式如下:

(1)

(2)

要拟合出这个平面可以转化为求出平面上某一点和此平面的法向量,这一点就是目标点p和它的k个邻近点的平均点c,首先对整个点云构建k-d树,然后根据k-d树搜索目标点p的k个邻近点,通过最小化目标函数(1)来求法向量,其中n为待求法向量,根据PCA算法就可以求出该点对应的法向量。

(3)

(4)

在以最小二乘法拟合出切平面后,将采样点p和k个近邻点投影到切平面上,以采样点p的投影点为起点,近邻点的投影点为终点定义k个向量,选定任一向量作为起始向量,按照(顺时针或逆时针)顺序计算相邻两向量之间的角度,得到夹角的集合A={α1,α2,…,αk},计算这些角度中的最大值αi,若最大值αi大于阈值θ,则该点被判定为边界点,保留该点为边缘点,否则删除该点(如图2所示)。逐点对点云数据进行计算,从而完成边界特征点提取。

图2 边缘点和非边缘点示意图

1.2 特征点提取

常见的三维点云特征点提取算法主要有Harris3D、NARF、ISS3D、SIFT3D等,其中,Harris3D算法利用点云的法向量提取出点云的角点和边缘点;NARF算法在深度图像中进行关键点提取,降低了关键点提取的计算量,但是需要花费较长时间将点云转换为深度图像,转换过程中存在精度损失,NARF算法和Harris3D提取出的关键点主要是边缘点;根据文献[13]知,ISS3D算法和SIFT3D算法在点云存在旋转、平移和缩放的情况下仍具有良好的稳健性,ISS3D算法和SIFT3D算法可以很好地提取点云的内部特征点。因此,本文采用ISS3D和SIFT3D两种方法提取点云内部的特征点。

(1)ISS3D算法

(2)SIFT3D特征点

SIFT3D是对2D图像SIFT[15]的扩充,被应用于点云的处理中,对点云视角变化、平移变换具有很好的稳定性。SIFT3D关键点提取主要分为三部分:在点云尺度空间中检测极值点、确定关键点方向、关键点描述子的表示。首先对点云进行滤波,构造点云金字塔,对金字塔中每个点云构建高斯尺度空间,然后使用尺度空间构建高斯差分空间(DoG),通过比较点pi与邻域点的大小来判断pi点是否为极值点,邻域点包括同一层相邻的8个点以及上下两层各9个点;之后对极值点进行筛选得到稳定的极值点即特征点,根据特征点的局部特性来确定方向,每个特征点可以使用(x,y,z,σ,θ,Φ)来表示,其中(x,y,z)为空间坐标,σ为尺度信息;在确定特征点的方向后,建立包含尺度、位置和方向信息的描述符来对特征点进行描述。

1.3 点云增补与删除

在提取出点云边缘点和点云内部的特征点后,在点云平坦区域可能会存在空洞,需要对平坦区域进行适当的点云增补。本文采用改进的最远点采样算法对空洞进行修补,最远点采样算法[16](Fast point sampling,FPS)是3D点云深度学习框架PointNet++中的采样算法,算法主要步骤如下:

(1)设原始点云有n个点,需要采样出k个点,使用集合A代表采样点,集合B代表剩余点。初始情况下,集合A为空,集合B包括所有点。

(2)从原始数据中随机选取一个点P0作为起始点,将P0移入集合A,计算P0与剩余(n-1)个点的距离,选择距离最大的点移入集合A,此时集合A中有2个点,集合B有(n-2)个点。

(3)假设PB是集合B中的一个点,分别计算出PB到集合A中两个点的距离值,选择最小的距离值作为PB到集合A的距离;对于集合B中的所有点计算出到集合A的距离值,选择最大的距离对应的点作为第3个点,移动到集合A中。

(4)重复第(3)步,直到选出k个点为止。

传统的最远点采样中如果随机选择初始点,则每次采样结果都不同,本文中先将边缘点和特征点合并,计算其重心点,在去除边缘点和特征点后的点云中选择距离重心点最远的一点作为初始点进行最远点采样。

将边缘点、特征点和改进的最远点采样得到的三类点云合并,但是边缘点和特征点可能会存在重复,此时利用原始点云的平均距离作为阈值来删除合并结果中距离过近的点,即得到最终的精简点云。

1.4 评价指标

本文采用精简率、豪斯多夫距离和几何失真指数三个指标来评价本文的精简算法,具体定义如下:

(1)精简率

点云精简率的定义如下式:

(5)

(2)豪斯多夫距离

豪斯多夫距离(Hausdorff Distance,HD)是衡量两个点集之间距离的公式,给定欧氏空间两个点集A={p1,p2,…,pn}和B={q1,q2,…,qn},点集A,B的HD距离定义如下:

HD(A,B)=max(h(A,B),h(B,A))

(6)

(7)

(8)

当点集A是点集B的子集时,h(A,B)=0,HD(A,B)=h(B,A),HD越小,说明精简后点云分布越均匀,理论上反映出精简后点云与原始点云更相似[17]。

(3)几何失真指数

在二维图像压缩中,峰值信噪比(Peaksignal-to-noise ratio,PSNR)反映了压缩后图片质量,其定义如下:

(9)

(10)

式中,I,K为大小为H×W的单色图像,其中I是未压缩的原始图像,K是压缩后的图像,如果PSNR越大,说明压缩后图像的失真程度越小,如果是无损压缩,PSNR的值应该是无穷大。

同理,将类似定义引入到评价三维点云精简,定义几何失真指数(Geometric distortion index,GDI)作为点云精简评价指标,公式如下:

(11)

其中,p为信号峰值,代表误差的最大值。根据点云的数据类型设置为 1 023,在三维点云精简中,若GDI的值越大,代表失真越少,说明精简算法对原点云的描述能力越强。

2 实验与分析

为了验证本文点云精简方法的有效性,本文采取两组数据进行实验,第一组数据为测试数据,为斯坦福的兔子bunny数据集,第二组数据为实采数据,使用FARO的扫描仪获得武汉大学南门的石狮子点云数据。分别采用随机采样法、均匀采样法、法线空间采样法和本文方法对点云数据进行精简,进行结果效果分析。

2.1 测试数据实验分析

考虑到在边缘点提取过程中,阈值θ的选择对边缘点的数目和提取效果影响很大,因此本文为了确定最适合兔子点云的阈值,将阈值θ设置为0.1π～π之间,步距设为0.01π,提取出的边缘点数与阈值θ的关系如图3所示,图4是不同阈值提取出的边缘点结果。

图3 阈值θ与提取到的边缘点数目关系

图4 设置不同阈值边缘点提取效果

由图3和图4可以看出,随着阈值θ的增大,边缘点的数目在逐渐减小,但是在Π/2后随着阈值的增大,边缘点提取会出现比较多的缺失,边缘点数目减少的速度也明显减慢,因此在提取兔子点云边缘时,将阈值θ设置为Π/2。

在提取出点云的边缘点后,进行点云特征点提取,图5给出了ISS3D、SIFT3D,Harris3D、NARF四种特征点提取的结果,其中红色点为ISS3D,蓝色点为SIFT3D,绿色点为Harris3D,白色点为NARF。

图5 四种方法提取特征点结果

由图5可以看出:ISS3D提取到的特征点数目最多且分布均匀,兔子的嘴巴、腹部和尾巴处都存在特征点;NARF需要先将点云转换为深度图像,要求关键点的位置稳定且在不同的视角可以被重复探测,对点云的要求较高且提取速度最慢,其提取出的特征点主要集中在兔子的脖子区域,分布不均匀且数量少;Harris3D算法是从二维的角点提取算法扩展到三维点云,其利用点云的表面法向量信息检测特征点,领域半径r控制特征点的数目,r越小,对噪声越敏感,提取的角点越尖锐,r越大,会导致在平缓区域也检测出角点,本文采用点云的平均距离来控制r,减少人为设定r对检测结果的影响;SIFT3D方法在点云存在旋转、平移、缩放的情况下具有良好的稳健性,提取出的特征点分布在点云的内部特征区域和点云边缘。四种方法提取出的特征点的重复度均低于10%,其中SIFT3D和NARF方法重复点最多,仅为24个点,仅占NARF特征点的7%。为了提高特征点提取的速度和均匀性,本文采用ISS3D和SIFT3D提取特征点。

经过上面实验分析后,采用Π/2作为边缘点提取的阈值,采用SIFT3D和ISS3D提取特征点,并通过点云增补和删除后,所得到的点云结果(本文方法)和另外3种方法的精简结果,采用三种精简指标,进行比较分析,其结果如表1所示,精简后的效果如图6所示。

表1 兔子点云不同方法精简结果的评价指标统计

图6 兔子点云精简后的效果图

由图6可以看出:均匀采样得到的点云比较规则,在特征区域和平坦区域的采样点数相同,保留图5四种方法提取特征点结果细节特征的能力不如本文方法;随机采样法不考虑点云的特征值和曲率,细节特征损失较大,可能剔除点云的关键数据;法线空间采样法虽然能保留点云内部的特征,但点云边界特征损失较大,在点云平坦区域可能存在空洞;而本文方法可以很好地保存边缘点云和内部特征点,在平坦区域的点云也比较均匀,能够在相同的精简率下最大化地保留点云的特征和细节,与其他3种方法相比,本文方法精简结果的HD和GDI也是最优的,说明本文方法可以很好地描述原始点云。

2.2 实采数据实验分析

对使用FARO的扫描仪获得武汉大学南门的石狮子点云,使用本文方法和其他3种方法对点云进行精简,采集到的原始点云包括 294 726个数据点,由于只采用了单站扫描数据,狮子头部存在扫描盲区导致出现空洞,后续可以采用三角网格化方法或径向基函数法或GA-BP神经网络方法进行空洞修补。其精简结果如图7所示,采用三种精简指标,进行比较分析,其结果如表2所示。

表2 狮子点云不同方法精简结果的评价指标统计

图7 狮子点云精简后效果图

由图7可以看出:随机采样法和法线空间采样法的精简结果整体比较杂乱,在狮子墩部位存在点云空洞;均匀采样法的精简结果边界区域比较杂乱,特征区域和平坦区域的采样数一致,不能反映出点云的细节特征;本文方法的精简结果点云边界清晰,点云平坦区域没有空洞,还保留了点云的细节特征。由表2可知,本文方法得到的精简点云的HD和GDI均为最优,说明本文方法对大规模点云精简后的结果仍能很好地表达点云的整体特征。

3 结 论

本文针对获得的点云原始数据庞大和大量冗余的问题,提出了一种结合边缘点提取和特征点提取的点云精简方法,通过精简率、豪斯多夫距离和几何失真指数三个指标来评价本文的精简方法。实验结果表明,本文方法得到的精简结果失真程度更小,既保留了点云的细节特征,又减少了点云平坦区域的空洞,对大规模点云也有很好的适用性。