大工至善|大学至真分享 http://blog.sciencenet.cn/u/lcj2212916

博文

[转载]【计算机科学】【2018.08】三维点云处理的拓扑方法

已有 495 次阅读 2020-10-9 22:21 |系统分类:科研笔记|文章来源:转载

本文为美国明尼苏达州立大学(作者:William Joseph Beksi)的博士论文,共126页。

 

由于低成本传感器的可用性,三维点云数据集变得越来越普遍。激光探测和测距(LIDAR)、立体光、结构光和飞行时间(ToF)都是捕捉环境三维表示的传感器例子。这些传感器越来越多地出现在智能手机、平板电脑、机器人和自动驾驶汽车等移动设备和机器中。随着硬件技术的发展,需要算法和数据结构来以创新和有意义的方式处理这些传感器生成的数据。

 

本文发展并应用代数拓扑方法处理三维点云数据集。近年来,拓扑数据分析(TDA)领域已经成熟,使得研究人员能够使用考虑数据“形状”的技术来分析点云数据集。这包括拓扑特征,例如连接的组件、孔、空洞和高维的类似物体。这些思想已经成功地应用于自然嵌入到度量空间(如欧几里德空间)中的数据集,在度量空间中,点之间的距离可以用来形成一个参数化的空间序列。通过研究这个序列不断变化的拓扑结构,我们获得了有关底层数据的信息。

 

在论文的第一部分,我们提出了一个快速的方法来建立一个三维VietorisRips复合体,使我们能够近似一个点云的拓扑结构。该复合体的构造分为三个并行阶段:最近邻搜索、边列表生成和三角形列表生成。边和三角形列表可以用于持久同调计算。

 

在论文的第二部分,我们提出了利用持久同调理论的思想来分割三维点云数据的方法。提出的算法首先生成点云数据集的简单复表示,然后计算对应于连通分量个数的复表示的第零同调群。最后,我们提取数据集中每个连接分量的簇。我们的研究表明,这些方法在存在噪声和采样条件差的情况下能够稳定地分割点云数据,从而比现有的分割方法具有优势。

 

在论文的第三部分,我们通过引入一个近似线性时间算法来解决计算拓扑中的一个开放问题,该算法用于增量计算拓扑持久1-cycle。此外,我们发展了第二个演算法,利用第一个演算法的输出来产生一个生成树,在这个生成树上可以计算出非有界的最小1-cycle。然后使用这些非有界最小1-cycle来定位和填充数据集中的孔。实验结果表明,我们的算法可以有效地重建由噪声传感器数据产生的三维点云表面

 

在论文的第四部分,我们开发了一个全局特征描述符,称为拓扑持久点签名(STPP,它对三维点云数据的拓扑不变量(第零个和第一个同调群)进行编码。与现有技术相比,STPP是一种具有竞争力的三维点云描述符,并且对噪声传感器数据具有弹性。我们的实验证明,STPP可以作为一个独特的特征,从而允许三维点云处理任务,如目标检测和分类。

 

本论文的研究主要是在两个方向上实现有效、高效、可扩展的三维点云拓扑处理方法。我们提出了这些算法,并分析了它们的理论性能和正确性证明。我们还通过使用公开数据集的实验来证明结果的可行性和适用性。

 

3D point cloud datasets are becoming morecommon due to the availability of low-cost sensors. Light detection and ranging(LIDAR), stereo, structured light, and time-of-flight (ToF) are examples ofsensors that capture a 3D representation of the environment. These sensors areincreasingly found in mobile devices and machines such as smartphones, tablets,robots, and autonomous vehicles. As hardware technology advances, algorithmsand data structures are needed to process the data generated by these sensorsin innovative and meaningful ways.

This dissertation develops and appliesalgebraic topological methods for processing 3D point cloud datasets. The areaof topological data analysis (TDA) has matured in recent years allowingresearchers to analyze point cloud datasets using techniques that take intoaccount the ‘shape’ of the data. This includes topological features such asconnected components, holes, voids, and higher dimensional analogs. These ideashave been successfully applied to datasets which are naturally embedded in ametric space (such as Euclidean space) where distances between points can beused to form a parameterized sequence of spaces. By studying the changingtopology of this sequence we gain information about the underlying data.

In the first part of the thesis, we presenta fast approach to build a 3D Vietoris-Rips complex which allows us to approximatethe topology of a point cloud. The construction of the complex is done in threeparallelized phases: nearest neighbors search, edge list generation, andtriangle list generation. The edge and triangle lists can then be used forpersistent homology computations.

In the second part of the thesis, wepresent approaches to segment 3D point cloud data using ideas from persistenthomology theory. The proposed algorithms first generate a simplicial complexrepresentation of the point cloud dataset. Then, the zeroth homology group ofthe complex which corresponds to the number of connected components iscomputed. Finally, we extract the clusters of each connected component in the dataset.We show that these methods provide a stable segmentation of point cloud data underthe presence of noise and poor sampling conditions, thus providing advantages overcontemporary segmentation procedures.

In the third part of the thesis, we addressan open problem in computational topology by introducing a nearly linear time algorithmfor incrementally computing topologically persistent 1-cycles. Further, wedevelop a second algorithm that utilizes the output of the first to generate aspanning tree upon which non-bounding minimal 1-cycles can be computed. Thesenon-bounding minimal 1-cycles are then used to locate and fill holes in adataset. Experimental results show the efficacy of our algorithms forreconstructing the surface of 3D point clouds produced by noisy sensor data.

In the fourth part of the thesis, wedevelop a global feature descriptor termed Signature of TopologicallyPersistent Points (STPP) that encodes topological invariants (zeroth and firsthomology groups) of 3D point cloud data. STPP is a competitive 3D point clouddescriptor when compared to the state of art and is resilient to noisy sensordata. We demonstrate experimentally that STPP can be used as a distinctive signature,thus allowing for 3D point cloud processing tasks such as object detection andclassification.

This dissertation makes progress towardseffective, efficient, and scalable topological methods for 3D point cloudprocessing along two directions. We present algorithms with an analysis oftheir theoretical performance and proof of correctness. We also demonstrate thefeasibility and applicability of our results with experiments using publicly availabledatasets.

 

1. 引言

2. 数学背景

3. R3 Vietoris-Rips复形式的快速重建

4. 点云分割

5. 点云空洞边界检测

6. 点云签名

7. 结论与讨论


更多精彩文章请关注公众号:205328s611i1aqxbbgxv19.jpg




http://blog.sciencenet.cn/blog-69686-1253768.html

上一篇:[转载]【无人机】【2011】直升机无人机的最优控制
下一篇:[转载]【信息技术】【2009】音频数字信号处理技术及应用

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-4-16 15:44

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部