基于聚类中心点连接的点云分割
基于聚类中心点连接的点云分割
原文题目：PAIRWISE LINKAGE FOR POINT CLOUD SEGMENTATION
摘要：在本文中，我们首先提出了一种新颖的分层聚类算法，称为（P-Linkage），该算法可用于对任意维的数据进行聚类，然后将其有效地应用于无序3D点云分割。P-Linkage聚类算法首先计算每个数据点的特征值，例如2D数据点的密度和3D点云的平坦度。然后，对于每个数据点，依据特征值大小创建查询点和k近邻点之间成对链接。通过以这种搜索链接的方式，可以进一步发现其他聚类。最后，合并所有的聚类完成分割。
Introduction
分割是点云处理中重要的预处理步骤之一,是将数据点分类和标记为多个单独的组或区域的过程，每个组或区域对应于对象表面的特定形状。
1.1
Point cloud segmentation
3D点云分割并不容易，因为三维点数据通常不完整，稀疏分布且没有拓扑结构，而且对点的统计分布也没有先验知识。针对点云分割，目前的方法可以大致分为三大类：基于边界，基于区域增长和混合方法。
基于边界的方法尝试检测形成闭合边界的不连续性，然后将点分组到已标识的边界和连接的边缘内。这些方法通常适用于深度图，将局部表面超过给定阈值的点定义为边界。最常用的局部表面特性是表面法线，梯度，主曲率或高阶导数（Sappa和Devy，2001；Wani和Arabnia，2003）。但是，由于激光扫描仪本身引起的噪声或3D空间中空间上不均匀的点分布，此类方法通常会检测到不连续的边缘，导致封闭边界区域的识别工作效果不佳（Castillo等，2013）。
基于区域增长的方法通过检测连续表面的几何特性来完成分割。在无序3D点云的分割中，这些方法首先选择种子点，如果种子点和邻近点在表面点属性（例如方向和曲率）具有相似性，则将其与种子点聚类（Rabbani et al。，2006，Jagannathan and Miller，2007）。还有一些算法将子窗口（Xiao等，2013）或线段（Harati等，2007）作为种子点。（Woo et al。，2002）提出了一种基于八叉树的3D网格方法来处理大尺度无序点云。能够平滑连接区域是基于区域增长方法的关键。广泛使用表面法线和曲率约束条件来找到平滑连接的区域（Klasing等，2009；Belton和Lichti，2006）。一般情况下，由于使用了全局信息，基于区域增长的方法比基于边缘的方法对噪声更加鲁棒（Liu和Xiong，2008）。但是，这些方法对初始种子区域的位置很敏感，区域边界附近点的法线和曲率的不正确估计会导致分割结果不准确，并且离群点还会导致过分割或欠分割。
混合方法同时使用基于边缘/边界的方法和基于区域增长的方法，以克服各前两个方法的局限性（Vieira和Shimada，2005；Lavouée等，2005）。Benk˝o和V´arady，2004年）提出了一种用于工程对象分割的混合方法，该方法首先使用基于边缘的方法检测锐利边缘，然后在滤除锐利边缘后找到平滑区域并混合。但是，这些混合方法的好坏取决于采用的单个方法的效果。
1.2
Clustering
聚类分析旨在基于元素的相似性将其分类，已应用于许多领域，例如数据挖掘，天文学和模式识别。通常，这些算法可以分为两类：分区方法和分层方法。分区聚类算法通常通过某种相似性度量将每个数据点分类为不同的聚类。传统的算法K-Means（MacQueen等，1967）和CLARANS（Ng和Han，1994）属于这一类。分层方法通常通过将数据集迭代拆分为较小的子集，直到每个子集仅包含一个对象，从而创建数据集的分层分解，例如，单链接（SLink）方法及其变体（Sibson，1973）。
1.3
Clustering in Point Cloud Segmentation
基于元素的相似度，将元素分类的聚类算法也可以应用于3D点云的分割。广泛使用的K-Means算法（MacQueen等，1967）将数据点划分为K个（给出簇数的预定义参数），K-Means聚类算法的缺点是它需要事先知道聚类簇的数量，但在许多情况下无法预先定义。为了克服这一缺点，在点云分割中采用了均值漂移算法（Comaniciu和Meer，2002），该算法是一种通用的非参数技术，用于对分散的数据进行聚类（Yamauchi等，2005b；Yamauchi等，2005a，Zhang等，2008）。在（Yamauchi等，2005b，Yamauchi等，2005a）的工作中，均值漂移算法分别用于积分网格法线和高斯曲率的整合。在（Liu and Xiong，2008）的工作中，将法线方向转换为高斯球体，并提出了一种新颖的单元均值漂移算法，以无参数的方式识别平面，抛物线形，双曲线形或椭圆形表面。但是，大多数基于聚类的点云分割方法只能发现少量分割，这种分割可以在某些行业应用中使用，但在包含数大量数据的室内和室外激光扫描仪点云上可能会失败。
1.4
Objectives and Motivation
在本文中，我们提出了一种简单，有效的点云分割算法，该算法通过在点云分割上应用聚类算法，可以应用与无序点云。引入两个概念：
P-Linkage Clustering:基于以下假设：数据点应与其最接近的相邻点（CNP）处于同一群集中，而最接近的相邻点（CNP）更有可能成为群集中心，我们提出了一种新颖的分层成对方法，称为成对链接（P-Linkage），它以简单有效的方式发现集群。首先，应用成对链接程序将每个数据点在数据点级别链接到其CNP。然后可以通过从具有最大局部密度的点开始沿成对链接搜索来发现初始聚类，提出的聚类方法不是迭代的，一般情况下只需要一步，针对特定情况也提出了一种聚类方法。
Point Cloud Segmentation:基于提出的P-Linkage聚类，我们开发了一种简单高效的点云分割算法，该算法仅需一个参数，即可应用于大量非结构化的车载，空中和固定式激光扫描仪点云。点云分割中的P链接聚类将3D点的估计曲面的平坦度作为其特征值，并通过沿链接的点集合收集来形成初始聚类。对于每个初始集合，我们创建一个切片。所有切片均以简单或有效的方式进行合并以获得最终的分割结果。所提出的点云分割算法只需要一个参数就可以平衡平面和曲面结构的分割结果。
2 PAIRWISE LINKAGE
P-Linkage聚类方法的关键概念是：数据点pi应该与最接近的邻居pj位于同一个群集中，而最邻近的邻居pj更有可能成为群集中心，并且pi和pj之间的这种关系称为成对链接。此概念源自非最大抑制（NMS）的概念（Canny，1986；Neubeck和Van Gool，2006），其中仅需要用一个数据点与其邻居进行比较，如果密度不是最大，则抑制。图1显示了NMS的原理，从中我们可以看到p1被p2抑制，并且与p3相比，p2受到相同的抑制，这导致链接p1→p2→p3。通过这种方式，曲线上的所有数据点最终都可以通过与相邻点的比较而链接到聚类中心c，它是局部最大值。实际上，P-Linkage聚类弥补了数据点的局部信息与全局信息之间的差距，这使其比基于局部的聚类方法更鲁棒，并且比基于全局的聚类方法更高效。
图1 2维高斯曲线上的成对链接的插图。从NMS派生而来，PLinkage将每个数据点与其相邻点进行比较，并形成从p1→p2→p3 ...→c的链接。
基于2D数据点聚类的成对链接算法以数据点的密度为其特征值来建立链接。主要概念如下:
Cutoff Distance：如图2所示，截止距离dc是一个全局参数，用于将数据点pi的邻域集与其他数据点区分开。在（Rodriguez和Laio，2014）的最新工作中，将dc的值设置为任意两个数据点之间的所有距离（表示为集合D）的所有距离的前1％-2％值的升序排列。但是，以这种方式设置截止距离dc是不合适的，因为dc是相邻点分布的指标，应该从局部邻域而不是D中得出。因此，我们提出了一种简单的方法来确定dc的值，如下所述。对于每个数据点pi，将pi与它的最近邻居之间的距离记录在Dcn中，然后将dc计算为：
其中scale是自定义参数，这意味着截止距离dc是scale乘以设置Dcn的中值的值。这样，dc表示的邻域分布信息要比将其设置为D的1％-2％多得多。只有将到pi的距离小于dc的数据点视为pi的邻域集，记为Ii，绿色圆圈如图2所示。
图2分层聚类过程的说明。数据点p1和p34是聚类中心，符号→表示成对链接，绿色的大圆圈表示具有截止距离dc的数据点的邻域集
Density：（Rodriguez和Laio，2014年）将数据点pi的密度定义为其邻居数据点的数量，该值是离散值，因此不适合我们需要连续值密度的应用。在我们提出的方法中，数据点pi的密度ρi是通过在所有数据点上应用高斯核来计算的，如下所示：
其中N表示所有数据点的数量，dij是两个点pi和pj之间的距离。
Pairwise Linkage: 利用所有数据点的密度，可以以非迭代的方式恢复成对的链接，方法如下。对于邻域为Ii的数据点pi，我们遍历Ii中的每个点，并找到密度大于pi的最近数据点pj，然后我们认为数据点pi应该与pj在同一簇中，并且记录数据点pi和pj之间的链接。如果pi的密度是局部最大值，这意味着Ii中不存在密度大于pi的数据点，则我们将pi视为聚类中心。成对链接过程的结果由记录链接关系的查找表T和记录所有聚类中心的集合Ccenter组成。
Herarchical Cluctering: 分层聚类是自上而下的过程，类似于分裂聚类算法的过程。对于Ccenter中的每个群集中心ci，我们开始以深度优先或广度优先的方式从ci搜索查找表T，以收集与ci直接或间接连接的所有数据点，从而生成一个以ci为中心的群集。整个层次聚类找到最终的聚类C。图2显示了层次聚类过程的图示。从图2中，我们可以看到p1是其局部最大密度而成为聚类中心，并且在（p1，p13），（p13，p4），（p4，p27）和（p27，p8）之间存在四个成对链接。因此，按照p1→p13→p4→p27→p8进行层次聚类。通过这种方式，聚类信息从密集的数据点传播到稀疏的数据点，这类似于热传播。
Cluster Meraging: 如图1所示，当数据点呈高斯分布时，通过成对链接的层次聚类可以找到全局聚类中心并很好地恢复聚类，但是当存在一个或多个局部最大值时，聚类结果可能会失败。为了应对数据点分配的所有条件，提出了一种定制的集群合并策略，该策略包括以下三个步骤。首先，对于每个群集C p，计算Cp中所有数据点的平均密度µp和标准偏差σp。其次，通过搜索相邻簇之间的边界数据点来收集每个簇Cp的相邻簇。对于Cp中的每个数据点pi，其邻域集表示为Ii。如果Ii中的数据点pj属于另一个簇Cq，则将这两个簇视为一对相邻簇，将pi和pj分别记录为Cp和Cq之间的相邻点。
第三，对于每个相邻的簇对Cp和Cq，Cp和Cq的相邻点的平均密度分别表示为ρp和ρq。如果满足以下条件，将合并这两个相邻的群集：
群集合并以迭代方式进行，这意味着将直接或间接与起始群集相邻的所有群集合并。
Outliers: 在（Ester等人，1996）提出的以前的工作中，离群点是那些密度小于某个阈值的点。通过这种方式，低密度数据点可以被分类为离群值。在（Rodriguez and Laio，2014）的工作中，离群点被认为是密度小于群集边界区域中最高密度的那些异常点，这意味着将丢弃群集边界区域中的所有数据点作为离群值。在我们的工作中，我们考虑群集级别的异常值。如果密度为局部最大但小于所有数据点的中值密度中位数（ρ）的数据点pi，则将具有pi的同一群集中的所有数据点视为异常值。
图2展示了所提出的P-Linkage方法的一些基本思想，从中我们可以观察到分别有蓝色和红色两个簇。对于每个数据点，通过搜索密度大于其自身密度的最近邻点来形成成对链接。例如，首先将p8链接到p27，然后将p27链接到p4，再将p4链接到p13，最后将p13链接到p1，并且在其附近密度最大。通过这种方式，可以找到完整的链接，即p8→p27→p4→p13→p1，因此所有这五个数据点都被归类为同一聚类，其聚类中心为p1。对于所有蓝色的数据点（作为单独的群集），将执行相同的过程。类似地，红色簇可以通过这种方式形成。至于两个聚类之间边界上的数据点，仍然可以应用成对链接。以数据点p33为例，p19，p7，p6和p28是其邻近点，p6是其最邻近点（CNP），因此p33被分类为蓝色簇，这是非常合理的。黑色的四个数据点p26，p18，p17和p16被归类为离群值，因为它们的邻域中不存在CNP，并且它们的聚类中心的密度也不足够高。
综上所述，所提出的聚类方法在通常情况下仅需一步即可发现聚类和聚类中心，而无需合并过程。对于每个具有密度ρi的数据点pi，我们找到其密度大于pi的最接近的相邻点CNP（pi），并将该点pi分类为与CNP（pi）相同的群集。如果数据点pi的密度ρi是局部最大值并且大于平均密度ρ，则我们将pi视为聚类中心。算法1详细描述了建立P链接聚类方法的完整过程。
3 P-LINKAGE FOR POINT CLOUD SEGMENTATION
点云的分割也可以表述为聚类问题，因为小表面上的数据点通常共享相似的法线值。因此，我们可以在点云的分割上采用建议的P-Linkage聚类方法，该方法在两个方面与2D数据点的分割有所不同：（1）邻域基于K最近邻（KNN）而不是固定距离（2）特征值是估计表面的平整度而不是邻域的密度；（3）将两个数据点法线方向的偏差作为度量而不是其欧几里得距离。在以下小节中，我们将详细说明基于P链接的点云分割算法。
Normal Estimation:在本文中，我们采用KNN方法查找每个数据点的邻域，并通过主成分分析（PCA）估算邻域表面的法线。该过程包含以下三个步骤。首先，我们通过应用ANN库构建k-d树（Mount and Arya，2010）。对于每个数据点pi，找到其K个最近邻居（KNN）并将其记录为Ii，并根据它们到pi的距离按升序排序。其次，对于每个数据点pi，协方差矩阵由其KNN集Ii中的前K / 2个数据点形成，如下所示：
其中Σ表示3×3协方差矩阵，p表示Ii中前K / 2个数据点的平均矢量。然后是标准特征值方程：
对于每个数据点，我们首先找到它的K个最近邻居，然后通过PCA通过第一个K/2个邻居计算其特征向量，然后将特征向量v0作为法线，将特征值λ0作为估计平面的平坦度。之后，采用最大距离最小一致性算法（MCMD）（Nurunnabi et al，2015）查找内部值和异常值，中值绝对偏差（MAD）的计算如下：
Rz权重为：
小于恒定阈值2.5（Nurunnabi et al，2015）。因此，对于每个数据点pi，我们获得其法线n（pi），平坦度λ（pi）和一致集CS（pi）。
Linkage Building: 利用所有数据点的法线，平坦度和CS，可以以非迭代的方式恢复成对链接，方法如下。对于每个数据点pi，我们在其CS中进行搜索以找出平坦度小于pi的邻居，并从中选择法线与pi具有最小偏差的邻近点作为CNP（pi）。如果存在CNP（pi），则会在CNP（pi）和pi之间建立成对链接并将其记录在查找表T中。如果pi的平坦度λ（pi）在其附近最小，并且λ（pi）超过以下阈值：
则将pi作为聚类中心，并将其插入群集中心Ccenter的列表中。
Slice Creating: 为了创建表面切片，首先通过从Ccenter中的每个聚类中心沿着查找表T搜索以形成聚类C，以收集与其直接或间接连接的数据点。数据点数小于10的群集将作为异常值被删除。然后，对于每个聚类C p，通过（Nurunnabi et al，2015）提出的MCS方法通过平面拟合创建一个切片，这是一个迭代过程，迭代次数计算为：
迭代后，按升序对S（λ0）进行排序，然后选择与最小平坦度对应的平面作为Cp的最佳拟合平面。
然后，应用MCMD离群值消除方法找出与Cp最佳拟合的平面的离群值，也称为一致性集（CS）。因此，对于每个切片Sp，我们以与每个数据点相同的方式获得其法线n（Sp），平坦度λ（Sp）和一致集CS（Sp）。
Slice Merging：为了获得在室内和工业应用中非常普遍的完整平面和曲面，提出了一种有效的切片合并方法，该方法类似于PLinkage群集中引入的群集合并过程，并包含以下步骤。首先，我们搜索每个切片的相邻切片，如果满足以下条件，则将两个切片Sp和Sq视为相邻切片：
然后，对于切片Sp及其相邻切片Sq之一，如果满足以下条件，它们将被合并：
4 EXPERIMENTAL RESULTS
P-Linkage唯一需要的自定义参数是用于确定dc值的比例。为了评估在高斯分布数据上提出的方法，我们在“形状集”1中选择了两个测试数据，分别包含15个和31个聚类。图3显示了它们的聚类结果，其中黑点代表离群值，其他不同颜色的点属于不同的聚类。
我们可以看到，在两个数据集中，所有聚类均被正确发现，并且所提出的方法提取的离群值都是合理的。
图5该方法在3D（XYZ）模拟测试数据上的聚类结果：原始数据点和聚类结果从左到右投影到XY平面，YZ平面和XZ平面上
所提出的P-Linkage聚类可以直接用于存在大量的数据点场景点云的分割等应用，为了测试所提出的点云分割方法的鲁棒性，我们将其应用于车载，空中和固定式激光扫描仪点云。
5 CONCLUSION
在本文中，我们提出了一种新的名为P-Linkage的分层聚类方法，通过在数据点上的成对链接，以一种简单有效的方式发现聚类。提出的P-Linkage聚类可以直接用于具有大量聚类和复杂场景的点云。我们提出了一种高效的点云分割算法，该算法可以处理从不同场景捕获的大量数据点。从2D到4D的不同数据的实验结果充分证明了所提出的P-Linkage聚类算法的效率和鲁棒性，并且在车载，空中和固定式激光扫描仪点云上的大量实验结果充分说明了鲁棒性和可靠性。
资源
关于我们
目前微信交流群不断壮大，由于人数太多，目前有两个群，为了鼓励大家分享，我们希望大家能在学习的同时积极分享，将您的问题或者小总结投稿发到群主邮箱主邮箱dianyunpcl@163.com。