logo

SCIENTIA SINICA Informationis, Volume 47, Issue 7: 832(2017) https://doi.org/10.1360/N112016-00034

A robust 3D point cloud skeleton extraction method

More info
  • ReceivedJun 10, 2016
  • AcceptedAug 25, 2016
  • PublishedFeb 27, 2017

Abstract

A robust method for three-dimensional point cloud skeleton extraction is proposed in this paper. First, a Laplace operator is used for contracting three-dimensional point cloud locally, and PCA (principal component analysis) is performed on the contracted point cloud to extract skeleton branches. Then, the local points that have been extracted as skeleton branches are fixed while the rest undergo further contraction. Point cloud contraction and local skeleton extraction are repeated until a complete skeleton curve that satisfies the termination conditions is obtained. Finally, by processing the cross points of skeleton and fitting cubic B-spline curves onto them, we can obtain the final skeleton curves. Experimental results show that, compared to existing methods, point cloud skeleton extraction with the proposed method is more robust and resistant to noise.


Funded by

国家自然科学基金重点项目(61332015)

国家自然科学基金(61572288,61202148,61373078)


Acknowledgment

感谢文献[28-30]的作者所提供的代码及程序.

  • Table 1   Comparisons of the time complexity
    Model Ref. [28] (s) Ref. [29] (s) Ref. [30] (s) Our method (s)
    Octopus 26.50 16.45 78.92 76.02
    Horse 15.27 32.83 73.58 59.01
    FE 18.43 54.28 34.62 114.63
    Man 20.33 43.73 27.68 86.55
    Couple 11.13 56.70 88.98 104.92
    Cow 10.50 44.51 75.70 76.46
  •   

    Algorithm 1 Laplace 局部收缩算法

    Require:

    步骤1: 若iterateTime等于1, 则计算 $W_{H}^{0}$, $S^{0}$, $W_{L}^{0}$和$L$, 利用式(1)和(3), 求出收缩后点云的坐标, 然后进行骨架提取; 步骤2: 若iterateTime大于1, 则针对没有达到稳定状态的点云重新计算$W_{H}^{i}$, $S^{i}$, $W_{L}^{i}$和$L$, 再次利用式(1)和(3)求出收缩后点云的坐标, 调用骨架提取算法, 进行骨架的提取; 步骤3: 判断没有达到稳定的数据点的个数. 若是还存在不稳定点, 则重复执行步骤2; 若所有点云都已经达到稳定状态, 则算法结束.

  •   

    Algorithm 2 骨架提取算法

    Require: 步骤1: 遍历每个不稳定点, 用PCA方法计算以当前点为中心的特征值与特征向量; 步骤2: 利用KD-tree找到当前点的邻近点, 如果邻近点的个数大于5, 则求出$\sigma_{i}$, 选出候选点; 步骤3: 找出$\sigma_{i}$最大值的候选点, 求出该点与邻近候选点之间的夹角, 若夹角小于给定阈值的候选点大于等于5 个, 则标记该点为骨架点; 步骤4: 连接骨架点得到骨架分支, 未提取骨架分支的不稳定点根据特征向量更新PCA半径$h_{i}$; 步骤5: 遍历所有数据点, 并重复步骤1$\sim$4, 得到所有可提取的骨架分支.

  •   

    Algorithm 3 点云骨架提取算法

    Require: 步骤1: 首先将$P$标记为不稳定点, 并计算初始PCA半径; 步骤2: 调用算法2进行骨架分支提取, 能够提取骨架分支的点云标记为稳定点; 步骤3: 将新的骨架分支与已提取的分支相连, 剩余的不稳定点调用算法1进行局部 Laplace 收缩; 步骤4: 重复执行步骤2、步骤3, 直至所有点标记为稳定点; 步骤5: 输出骨架$S$.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号