Towards Morse Theory for Point Cloud Data - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Towards Morse Theory for Point Cloud Data

Résumé

Morse theory provides a powerful framework to study the topology of a manifold from a function defined on it, but discrete constructions have remained elusive due to the difficulty of translating smooth concepts to the discrete setting. Consider the problem of approximating the Morse-Smale (MS) complex of a Morse function from a point cloud and an associated nearest neighbor graph (NNG). While following the constructive proof of the Morse homology theorem, we present novel concepts for critical points of any index, and the associated Morse-Smale diagram. Our framework has three key advantages. First, it requires elementary data structures and operations, and is thus suitable for high-dimensional data processing. Second, it is gradient free, which makes it suitable to investigate functions whose gradient is unknown or expensive to compute. Third, in case of under-sampling and even if the exact (unknown) MS diagram is not found, the output conveys information in terms of ambiguous flow, and the Morse theoretical version of topological persistence, which consists in canceling critical points by flow reversal, applies. On the experimental side, we present a comprehensive analysis of a large panel of bi-variate and tri-variate Morse functions whose Morse-Smale diagrams are known perfectly, and show that these diagrams are recovered perfectly. In a broader perspective, we see our frame work as first step to study complex dynamical systems from mere samplings consisting of point clouds.
La théorie de Morse fournit un formalisme puissant p our étudier une variété à partie d'une fonction définie sur celle-ci, mais généraliser au cas discret les constructions connues en topologie différentielle est une problématique ouverte. Considérons le problème consistant à approximer le diagramme de Morse-Smale(MS) d'une fonction à partir d'une graphe de plus proches voisins (NNG) défini sur un nuage de point échantillonnant cette fonction. En suivant la construction du theoreme central de l'homologie de Morse, nous présentons des concepts nouveaux de points critiques, ainsi que le diagramme de Morse-Smale associé. Notre canevas présente trois avantages clefs. Tout d'abord, les primitives utilisées relèvent d'algorithmes et structures de données élémentaires, adaptées au traitement de données en grande dimension. Ensuite, la connaissance du gradient de la fonction étudiée n'est pas requis. Enfin, en cas desous-echantilonnage et même si le diagramme de MS exact n'est pas retrouvé, des informations sur desambiguités de flot sont mises en évidence. Du point de vue expérimental, nous présentons une analyse exhaustive de fonctions 2D et 3D dont les diagrammes de MS sont connus, et parfaitement retrouvés. Dans un registre plus général, nous pensons que notre canevas est un premier pas dans la perspective de l'étude de systèmes dynamiques à partir de nuages de points.
Fichier principal
Vignette du fichier
Cazals2013MuellerRobertRoth_Morse-for-point-clouds-v1.pdf (2.51 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02988939 , version 1 (04-11-2020)

Identifiants

  • HAL Id : hal-02988939 , version 1

Citer

Frédéric Cazals, Christian Mueller, Charles Robert, Andrea Roth. Towards Morse Theory for Point Cloud Data. [Research Report] RR-8331, RESEARCH CENTRE SOPHIA ANTIPOLIS – MÉDITERRANÉE. 2013. ⟨hal-02988939⟩
469 Consultations
592 Téléchargements

Partager

Gmail Facebook X LinkedIn More