DBSCAN聚类和改进的双边滤波算法在点云去噪中的应用

2019-12-03曲金博

测绘通报 2019年11期

曲金博，王岩，赵琪

(沈阳建筑大学交通工程学院，辽宁沈阳 110168)

随着测绘技术的发展，三维模型在各方面都有着广阔的应用前景。三维激光点云数据获取时，由于仪器本身的精度，以及人为、环境因素等的影响，采集到的三维激光点云数据总存在噪声。近些年，国内外学者提出了一些点云去噪的方法，如文献[1]基于特征选择的双边滤波去噪，首先判断邻域点属于特征点还是非特征点，然后根据不同的点云范围进行滤波因子去噪，该算法在光顺上有所改进，但时间较长。文献[2]根据自适应密度聚类的结果进行双边滤波去噪，有效地去除了模型中的噪声点，但耗时太长。文献[3]引入双边滤子进行双边滤波自适应运算，选取自适应灰度方差S1，从而实现双边滤波算法的自适应，该算法自适应选取存在偏差，噪声去除有待加强。文献[4]针对噪声点尺度的问题，提出噪声尺度分类的双边滤波点云去噪算法，该算法将噪声分为大尺度和小尺度噪声进行去除，使用统计滤波和曲率估计对点云双边滤波进行改进，最后运用改进的双边滤波对小尺度噪声进行处理，该算法对不同尺度的噪声均有较好的去除效果，但是算法效率较低。文献[5]提出了一种改进的基于三维几何双边滤波的网格去噪方法，该方法保存了物体的特征，同时降低了噪声，达到不错的效果。

为了更好地识别噪声类型，对噪声点进行去除，保留点云特征，笔者提出将基于密度的DBSCAN聚类算法和改进的双边滤波方法相结合进行点云去噪。针对点云数据的特征，采用基于密度的DBSCAN聚类算法，通过设定密度参数来排除噪声点，对于其他点云采用改进的双边滤波方法进行光顺去噪，以提高去除噪声点的效率；并以沈阳民国时期代表性的建筑——沈阳金融博物馆为试验模型，对建筑实体进行去噪和光顺处理。

1 三维点云去噪算法

1.1 DBSCAN聚类算法原理

DBSCAN是一种经典的基于密度的聚类算法，不仅可以发现数据集中任意形状的类，且可以发现噪声点[6-8]。

DBSCAN算法有几个基本概念，引入记号表示概念，其中设数据集合D={x1,x2,…,xn}。

领域(Eps)：设x∈D，称DX={y∈D：d(y,x)≤Eps}为x的邻域，显然x∈Dx。

密度(density)：设x∈D，称ρ(x)=|Nx|为x的密度。本文的密度是一个整数值，且依赖于半径。

边界点(border point)：若x∈Dnc，且∃y∈D，满足y∈D，满足y∈Nx∩Dc，即x的领域中存在核心点，则称X为D的边界点，记由D中所有边界点构成的集合为Dbd。此外，边界点也可以这么定义，若x∈Dnc，且x落在某个核心点的领域内，则称x为D的一个边界点。一个边界点可能同时落入一个或多个核心点的领域。

核心点就是区域内部较稠密的点，边界点就是稠密区域边缘的点，而噪声点就是没有被区域覆盖的点。

直接密度可达(directly density-reachable)：设x，y∈D，若满足x∈Dc，y∈N(x)，则称y是从x直接密度可达的。

密度可达(density-reachable)：设p1，p2，…，pm∈D，其中m≥2。若满足pi+1是从pi直接密度可达的，i=1，2，…，m-1，则称pm是从p1密度可达的。

密度相连(density-connected)：设x，y，z∈D，若y和z均是从x密度可达的，则称y和z是密度相连的，显然密度相连具有对称性。

类(cluster)：称非空集合C⊂D是D的一个类，如果它满足对于x，y∈D，则：

(1) 最大化原则(maximality)，若x∈C，且y是从x密度可达的，则y∈C。

(2) 连通性原则(connectivity)，若x∈C，y∈C，则x、y是密度相连的。

1.2 双边滤波算法原理

1.2.1 双边滤波方法

双边滤波是一种滤波器，它是能够保持边界特征、去除噪声点和光顺的一种方法。双边滤波最重要的是权重，通过计算权重，使数据点向法向方向聚集，达到光顺去噪。

在双边滤波中，定义如下

p=pi+αn

(1)

式中，p为滤波后的点云数据；pi为原始点云数据；α为双边滤波权因子；n为数据点pi的法向量[7]。点云数据中α的定义为

(2)

式中，N(pi)为数据点pi的邻域点。

1.2.2 双边滤波方法改进

本文对双边滤波因子进行改进，提高其稳健性与保特征性，改进后的双边滤波因子定义为

(3)

光顺滤波权函数是标准高斯滤波,定义为

(4)

特征保持权函数与光顺滤波权函数类似，也是标准高斯滤波，定义为

(5)

式中，参数σc和σs均为高斯滤波参数，参数σc为数据点Pi到邻域点的距离对Pi点的影响因子，参数σs为数据点Pi到邻近点的距离在其法向量上的投影对Pi点的影响因子。其中，参数σc越大，三维点云数据模型的光滑性就越好；参数σs越大，三维点云数据模型的特征保持性就越好[9-12]。

2 本文方法

本文利用密度DBSCAN聚类算法对三维点云数据进行聚类，在聚类结果中选择建模所需的主体点云，去除噪声点云。

在DBSCAN聚类算法中初始半径和最小邻域都是自定义参数，要得到最优的结果必须反复设置两个参数。笔者针对反复设置参数的问题，提出自动计算初始半径和最小邻域的方法，用来降低算法的复杂度，提高计算速度[8]。

DBSCAN聚类算法在实际应用中比较耗时，为了得到良好的效果就需要设定好参数，初始半径和最小邻域属于自定义参数，要得到最优的结果必须反复设置两个参数。本文针对上述问题采用自动计算初始半径和最小邻域的方法，代替人工调整参数，该方法能有效提高计算速度。计算步骤如下：

(1) 计算间隔距离。根据式(6)—式(9)分别计算出i、j两点的欧氏距离、最大值、最小值和距离间距。

(6)

maxdist=Max{dist(i,j|0≤i≤n,0≤j≤D)}

(7)

mindist=Min{dist(i,j)|0≤i≤n,0≤j≤D}

(8)

distance=maxdist-mindist

(9)

式中，(xi，yi，zi)、(xj，yj，zj)分别为点i和点j的坐标；dist(i，j)为点i和点j之间的欧氏距离；maxdist为i、j两点间距离最大值；mindist为i、j两个点间距离最小值。

(2) 计算初始半径。把任意两点间的距离均匀分割成m段，并检测每段中dist(i，j)的频数pk，初始半径就是最大频数(rang)所在分段的中值，最大频数的计算公式为

rang=Max{pk|0≤k≤m}

(10)

(3) 计算最小邻域点数量。在确定初始半径后，增加最小邻域数，计算出邻域超过最小邻域数量的点的数量pN，对于任意点pi的邻域点数量pN1的计算公式如下

pN=count{dist(i,j)

(11)

pN1=count{pN1≥minpts|0≤i≤D}

(12)

竖轴是点云数量，横轴是最小邻域点数。从图2可以看出，在计算最小邻域点数中，随着最小邻域数量的增大，其中pN先大幅下降，然后趋于稳定。当minpts的值为9时，曲线基本稳定，因此最小邻域数目的取值为9。针对选取部分点云数据，pN的变化过程如图2所示。

DBSCAN聚类的步骤如图3所示。

利用DBSCAN聚类算法去除噪声点后，继续对点云数据进行滤波。本文用改进后的双边滤波方法对点云数据进行光顺[13-15]。

双边滤波去噪具体流程如下：

(1) 对每个点云数据Pi，求出它的k个最近邻点。

(3) 根据式(4)与式(5)计算出光顺滤波权函数Ws(x)和特征保持权函数Ws(y)。

(4) 将Ws(x)和Ws(y)代入，求出改进双边滤波因子α′的值。

(5) 将采样点Pi移动到滤波后的新数据点p的位置，建立新的点位信息。

(6) 更新点云数据，输出数据。

3 试验结果及分析

为验证本文算法的有效性，以沈阳民国时期代表性的建筑——沈阳金融博物馆为试验模型，运用DBSCAN聚类算法和改进后的双边滤波方法对其进行处理试验，结果如表1、图4—图6所示。

表1 点云数据量

从表1可以看出，本文方法处理所得的点云数据量要远远少于未经DBSCAN聚类算法处理直接滤波的点云数据量，说明笔者对于两种算法的结合是有效的，能够大幅去除数据点和噪声点。

图4中可以清晰看到存在大量的噪声点，图5为采用双边滤波方法处理后的数据，可以看出已经去除了部分噪声点，去噪效果一般，但保持了建筑物实体的特征。图6为文本方法处理之后的数据，可以清晰地看出图中噪声点几乎全部清除干净，去噪效果也比较明显，相对于图5不仅去除了大量点云噪声点，同时也保持了建筑物实体的特征，进一步验证了本文算法的有效性。