【论文阅读】PAIRWISELINKAGEFORPOINTCLOUDSEGMENTATIONISPRSluxiaohu

PAIRWISE LINKAGE FOR POINT CLOUD SEGMENTATION

Xiaohu Lu, Jian Yao∗, Jinge Tu, Kai Li, Li Li, Yahui Liu
School ofRemote Sensing and Information Engineering, Wuhan University, Wuhan, Hubei, P.R. China (xiaohu.lu,jian.yao,kaili,li.li,liuyahui)&＃64;whu.edu.cn http://cvrs.whu.edu.cn/

Commission III, WG III/2

1. INTRODUCTION

cluster

两大类&＃xff1a;partitioning和hierarchical

partitioning

The partitioning clustering algorithms usually classify each data point to different clusters via a certain similarity measurement

1、k-means&＃xff1a;参数来指定聚类的数目

2、CLARANS

3、mean-shift&＃xff1a; k-means的改进&＃xff0c;不需要参数

hierarchical

The hierarchical methods usually create a hierarchical decomposition of a dataset by iteratively splitting the dataset into smaller subsets until each subset consists of only one object

1、single-linkage

2、its variants

segment

three main categories: edge/border based, region growing based and hybrid

edge/border based

region growing

hybrid approaches

Objectives and Motivation

1、P-Linkage Clustering&＃xff1a;

develop a simple, efficient point cloud segmentation algorithm

2、Point Cloud Segmentation&＃xff1a;

employing the clustering algorithm on point cloud segmentation.

2. PAIRWISE LINKAGE

CutoffDistance:截止距离的选取

只有距离小于这个d才会被认为是neighbor

其中&＃xff0c;For each data point pi, the distance between pi and its closest neighbor is recorded in Dcn。

where scale is a customized parameter which means the cutoff distance dc is scale times the value of the median value of the set Dcn.

Density&＃xff1a;密度的计算

Pairwise Linkage:建立linkage关系&＃xff0c;保存聚类中心点

Hierarchical Clustering:分层聚类

ClusterMerging:

判据&＃xff1a;average densities of the adjacent points

如果两个cluster中的average densities of the adjacent points满足&＃xff1a;

则合并两个cluster

总的算法流程&＃xff1a;

对每一个点&＃xff0c;在其邻域内寻找比它本身特征&＃xff08;这里是密度&＃xff09;大的点&＃xff0c;如果有&＃xff0c;那么讲这个点记为CNP&＃xff0c;并将CNP-p之间的linkage保存到Table中&＃xff1b;如果在其邻域内没有比他自身特征好的点&＃xff0c;那么这个点就记为聚类中心。最后在聚类中心的集合中&＃xff0c;根据Table找每一个聚类中心对应的点集合

3. P-LINKAGE FOR POINT CLOUD SEGMENTATION

将cluster算法应用到点云分割上面&＃xff0c;和2维数据有三点不同&＃xff1a;

1、使用KNN找k个最近的邻域点&＃xff0c;而不是固定的距离的近邻点

2、使用点的平面度作为特征值

3、两个点之间的距离为他们法线方向的偏差

Normal Estimation

选取K个最近邻点&＃xff0c;使用前K/2个进行PCA估计法向量&＃xff1b;

使用Maximum Consistency with Minimum Distance (MCMD) algorithm (Nurunnabi et al., 2015)算法寻找inliers&＃xff0c;其方法是&＃xff1a;对这个p计算其邻域的K个点到估计的平面的距离N_OD&＃xff0c;然后计算这些数据的MAD&＃xff0c;进而计算出Rz_SCORE:

最后对每一给点p&＃xff0c;得到法线&＃xff0c;平面度&＃xff0c;一致性集合CS§

Linkage Building

对每一个p在其CS中选取比他平坦并且距离p最近的点作为CNP(pi)&＃xff0c;如果这个CNP(pi)存在那么创建一个linkage&＃xff0c;并且保存在一个table T&＃xff1b;如果这个点不存在并且当前点p的平坦度小于这个阈值&＃xff1a;

那么p就是cluster center&＃xff0c;并插入到list中。

Slice Creating

通过对cluster center中的点在Table中查找&＃xff0c;形成初始的clusters&＃xff0c;然后对每一个cluster&＃xff0c;通过一个类似于RANSAC的平面拟合的方式&＃xff08;MCS method proposed by (Nurunnabi et al., 2015)&＃xff09;&＃xff0c;迭代求得每一个cluster的最优的plane&＃xff0c;然后通过MCMD outlier removal得到内点&＃xff08;也就是Consistent Set (CS)&＃xff09;&＃xff0c;这样对于每一个slice S_p&＃xff0c;我们就获得了normal n(Sp)&＃xff0c;flatness λ(Sp)&＃xff0c;Consistent Set CS(Sp)。

Slice Merging

1、search for the adjacent slices for each one

满足下式&＃xff0c;则为adjacent slice

2、如果相邻的slice满足下面的公式&＃xff1a;

那么合并。

4. EXPERIMENTAL RESULTS

高斯分布的二维数据

5. CONCLUSION

提出层次聚类方法P-linkage&＃xff1b;将该算法应用到点云分割&＃xff0c;可以处理通过不同场景捕获的大量数据点。