Research internship: holes detection in point clouds using computational topology (job offer closed)

Nmellado/ octobre 12, 2022/ Open Positions

6 months – Master 2 Research Internship.
STORM research group, CNRS, IRIT, Toulouse.
Contact: nicolas.mellado AT irit.fr

Context

Point clouds are a type of unstructured data that is widely present in the field of computer graphics. They are notably produced by techniques of surface acquisition such as photogrammetry or LiDAR. These techniques enable the sampling of complex surfaces – sometimes a whole building – at millimeter-resolution, thus generating hundreds of millions of points. An example of point cloud is shown in Figure 1.

Such a surface acquisition has numerous applications: visualization, integration in virtual/augmented reality environments, pattern recognition, CAD, etc. These applications touch a large panel of fields, such as computer animation, video games development, robotics, medicine, archaeology, and more.

However, point cloud data must be processed before they can be used in the applications. An analysis must be performed to gather information on the data (for instance geometric information), followed by eventual operations of surface reconstruction, or classification.

Figure 1. Point cloud generated by the 3D acquisition of a church. Points are represented by spheres.

Topological Data Analysis (TDA) is a quite recent (≈ 25 years) scientific field that aims at characterizing data based on the generic and robust extraction of the structural information present in the data. These information relate to the topological shapes of the data, properties that are invariant under continuous geometric deformations. A typical example is the number of “holes” present in a shape. Such characteristics can then be used to represent the original data, in order to perform visualization or classification tasks.

In the recent years, numerous data analysis and visualization methods have been developed around these concepts. The applications spawn various fields, such as astrophysics, biology and medical imaging, molecular chemistry, fluid mechanics…

Figure 2. Three shapes with different topological characteristics. The cube (on the left) contains a hole of dimension 3 (a cavity). The loop (at the center) has a hole of dimension 2 (a cycle). The torus (on the right) shows at the same time a hole of dimension 2 (a handle), and a hole of dimension 3 (a cavity).

Project description

In this internship, we propose to apply concepts taken from Topological Data Analysis to the extraction of topological information in 3D point clouds: the number and type of “holes” that are present in the sampled surface. Intuitively, depending on their dimension, these holes are the cycles, the handles, and the cavities located in the data (Figure 2). In order to perform this extraction, we propose to use two classical tools of TDA: the Rips Complex and the notion of Topological Persistence.

The Rips complex of a point cloud is designed in the following way (illustrated in Figure 3): Given an initial point cloud, we consider spheres centered in each point, with a radius that grows progressively. As soon as the intersection of several spheres becomes non-empty, a simplex (an edge, a triangle or a tetrahedron) linking the corresponding points is inserted in the complex.

The topology of the complex (number of connected components, number of holes) effectively changes along the construction. The analysis of this evolution enables to extract information on the topological structures present at different scales in the data, and to characterize their relative importance with the notion of topological persistence. In the example from Figure 3, this analysis highlights the presence of two 2D holes in the data, or two cycles.

Figure 3. Construction of the Rips complex (edges and triangles in blue) of a small 2D point cloud (in red).

Roadmap

  • Study of a short bibliography on topological data analysis, in particular the notions of Rips complex and Topological Persistence.
  • Implementation (Python or C++) of a prototype for the computation of the Rips complex of a 2D point cloud, and evaluation of the method.
  • Implementation of the topological analysis (hole extraction) of the Rips complex, and evaluation of the method.
  • To push a little further, we may take a look at one or several of the following leads:
    • Development of techniques to improve the quality or performance of the analysis.
    • Tackling 3D point clouds.
    • Integration in an existing C++ library for point cloud analysis.

Skills

  • Linear algebra
  • Knowledge in Computer Graphics and/or Computer Vision
  • Good programming skills (modern C++)
  • Bonus: Experience in 3d point cloud analysis/processing

Related work

  • An introduction to computational topology [4]. Introduction to topological persistance at page 178. Formal introduction to rips complex at page 74.
  • Examples of application of the topological persistance in astrophysics [8,9], biology and medical imaging [1,3], chemistry [2,5,7], and fluid mechanics [6]:
  1. Keri Anderson, Jeffrey Anderson, Sourabh Palande, and Bei Wang. Topological data analysis of functional MRI connectivity in time and space domains. In MICCAI Workshop on Connectomics in NeuroImaging, 2018.
  2. H. Bhatia, S. Jadhav, P. Bremer, G. Chen, J. A. Levine, L. G. Nonato, and V. Pascucci. Flow visualization with quantified spatial and temporal errors using edge maps. IEEE Transactions on Visualization and Computer Graphics, 2012.
  3. Alexander Bock, Harish Doraiswamy, Adam Summers, and Cláudio T. Silva. TopoAngler : Interactive Topology-Based Extraction of Fishes. IEEE Transactions on Visualization and Computer Graphics (Proc. of IEEE VIS), 2018.
  4. H. Edelsbrunner and J. Harer. Computational Topology : An Introduction. American Mathematical Society, 2009.
  5. D. Guenther, R. Alvarez-Boto, J. Contreras-Garcia, J.-P. Piquemal, and J. Tierny. Characterizing molecular interactions in chemical systems. IEEE Transactions on Visualization and Computer Graphics (Proc. of IEEE VIS), 2014.
  6. J. Kasten, J. Reininghaus, I. Hotz, and H.C. Hege. Two-dimensional time-dependent vortex regions based on the acceleration magnitude. IEEE Transactions on Visualization and Computer Graphics, 2011.
  7. Malgorzata Olejniczak, André Severo Pereira Gomes, and Julien Tierny. A Topological Data Analysis Perspective on Non-Covalent Interactions in Relativistic Calculations. International Journal of Quantum Chemistry, 2019.
  8. Nithin Shivashankar, Pratyush Pranav, Vijay Natarajan, Rien van de Weygaert, EG Patrick Bos, and Steven Rieder. Felix : A topology based framework for visual exploration of cosmic filaments. IEEE Transactions on Visualization and Computer Graphics, 2016. http://vgl.serc.iisc.ernet.in/felix/index.html
  9. T. Sousbie. The persistent cosmic web and its filamentary structure : Theory and implementations. Royal Astronomical Society, 2011. http://www2.iap.fr/users/sousbie/web/html/indexd41d.html
Share this Post