Homologie persistante
SMACUD1L - Master IMD
Stabilité
Soient \( f, g: K \longrightarrow \mathbb{R} \). Leur distance est \[ \|f-g\|_{\infty} = \max_{\sigma \in K} |f(\sigma) - g(\sigma)| \]
Question : si \( f \) et \( g \) sont similaires, que se passe-t-il avec leurs diagrammes de persistance ? Comment les comparer ?
Distance de Hausdorff
Soient \( X, Y \) deux multi-ensembles de points de \( \mathbb{R}^2 \), \[ \begin{align*} d_H(X,Y) = \max \{ &\max_{x \in X} \min_{y \in Y} \|x-y\|_{\infty},\\ &\max_{y \in Y} \min_{x \in X} \|x-y\|_{\infty} \} \end{align*} \]
- Prends un \( x \in X \), regarde sa distance vers \( Y \)
- Fais la même chose pour chaque \( x \in X \) et prends la plus grande distance
- Échange \( X \) et \( Y \), prends encore la plus grande
Exercice 4
Distance de Hausdorff ?
Premier théorème de stabilité Cohen-Steiner et al, 2007
\[ d_H(D_q(f), D_q(g)) \leq \|f-g\|_{\infty} \]
En français : si on change un peu la fonction d'une filtration, son diagramme de persistance aura ses points à coté
Exemple 7
Fonction \( f \) continue définie sur \( K \) un intervalle
Une idée de pourquoi :
- Soit \( \delta = \|f-g\|_{\infty} \)
- \( f^{-1}(-\infty, x] \subset g^{-1}(-\infty, x + \delta] \)
- \( g^{-1}(-\infty, x] \subset f^{-1}(-\infty, x + \delta] \)
- On se sert de ces inclusions pour démontrer le théorème...
Distance bottleneck
\[ d_B(X,Y) = \min_{\gamma} \max_{x \in X} \|x - \gamma(x)\|_{\infty}, \] où \( \gamma:X \rightarrow Y \) bijective
- Fais un couplage entre les points de \( X \) et \( Y \), prends la plus grande distance entre les couples
- Parmi tous les couplages, prends la valeur la plus petite
Exercice 5
Distance bottleneck ?
Deuxième théorème de stabilité Cohen-Steiner et al, 2007
\[ d_B(D_q(f), D_q(g)) \leq \|f-g\|_{\infty} \]
En français : si on change un peu la fonction d'une filtration, chaque point va bouger d'un peu
Comme \( d_H(X,Y) \leq d_B(X,Y) \), ce deuxième théorème est plus fort
Morale
Les théorèmes de stabilité nous disent que :
- Si la fonction contient des erreurs (estimation), les diagrammes restent pareils
- Les points près de la diagonale ( = trous avec une courte durée) ne sont pas importants (car indistinguables d'une erreur)
- Deux diagrammes différents ⇒ deux fonctions différentes, mais pas le contraire
Exercice 6
Deux fonctions très différentes avec des diagrammes identiques ?
Calcul (homologie standard)
- Complexe simplicial \( K \) ≃ liste de tuples
-
liste de tuples ≃ matrices de bord,
\( \partial_{q+1}(\langle v_1, \cdots, v_q \rangle) = \sum_{i=1}^q (-1)^{i+1} \cdot \langle v_1, \cdots, \hat{v}_i, \cdots, v_q \rangle \) - \( H_q(K) = \ker(\partial_q) / \text{im}(\partial_{q+1}) = (\mathbb{Z}/2 \mathbb{Z})^{\beta_q} \)
- \( \beta_q = \dim(\ker(\partial_q)) - \dim(\text{im}(\partial_{q+1})) \)
- \( \dim(\ker(\partial_q)) \), \( \dim(\text{im}(\partial_{q+1})) \) ? ⟶ Diagonalisation
Exemple 8
\( \beta_0 = 4-3, \beta_1 = 2-1, \beta_2 = 0-0 \)
Pour calculer les groupes d'homologie avec coefficients dans une anneau ( \( \mathbb{Z} \) ), il faut calculer la forme normale de Smith des matrices de bord
\( H_q = \mathbb{Z}^{4-3} \oplus \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/6\mathbb{Z} \)
Calcul (homologie persistante)
Pour calculer les paires de persistance, pas besoin de calculer tous les nombres de Betti persistants \( \beta_q^{i,j} \)
Il suffit une élimination gaussienne en \( \mathcal{O}(n^3) \)
Notation :
- \(\sigma_1, \ldots, \sigma_n \) simplexes triés selon la filtration
-
\(D\) matrice de bord, toutes dimension confondues
\( D = (d_{ij}) \) telle que \( \partial(\sigma_j) = \Sigma_i \left( d_{ij} \cdot \sigma_i \right) \)
for j = 1...n
if Cj ≠ 0
i ← max(k; dkj = 1)
// élimination gaussienne avec le pivot dij
for k = 1...n
Rk ← Rk + dkj Ri
for k = 1...n
Ck ← Ck + dik Cj- \( M = \{ (\sigma_i, \sigma_j) \vert d_{ij} = 1 \} \)
- \( U = K - M \)
- \( D_q(f) = \{ (f(\sigma_i), f(\sigma_j)) \vert \dim(\sigma_i) = q \} \cup \{ (f(\sigma_k), \infty) \vert \sigma_k \in U, \dim(\sigma_k) = q \} \)
Exercice 7
Calculer les paires de persistance \( (i, j) \)
Morale
- Algorithme aussi basé sur la Forme Normale de Smith
- C'est toujours le plus jeune trou qui meurt
Applications
Quelques applications :
- Traitement d'images : reconstruction de contours
- Robotique : comment attraper un objet
- Visualisation scientifique : distinguer les parties importantes
- Analyse de formes : mesurer les trous
1. Traitement d'images
Comment reconnaître les contours ?
-
Entrée : ensemble fini de points \( P \subset \mathbb{R}^2 \)
Il devrait ressembler à un échantillon sur un graphe planaire - Sortie : un graphe planaire \( G \)
Si l'ensemble de points représente assez bien la forme, on devrait la retrouver
Algorithme :
- Construis une filtration avec des boules croissantes centrées sur les points (α-complexe)
- Calcule le diagramme de persistance de dimension 1 (composantes connexes ⇒ très rapide)
- Ignore les paires les plus proches de la diagonale à partir d'un seuil (widest gap) ⟵ clé de l'algorithme
- Le graphe \( G \) est formée par les cycles d'homologie des paires qui restent
Alpha complexe : filtration sur un ensemble de points \( P \subset R^2 \)
- Complexe : triangulation de Delaunay d'un ensemble de points
-
Fonction de filtration \( f \) :
- sur les 2-simplexes : rayon du cercle circonscrit du triangle
- sur les 1-simplexes : rayon du cercle circonscrit de l'arête (s'il ne contient pas d'autre point), minimum des valeurs des cofaces sinon
- sur les 0-simplexes : 0
- Propriété : \( f^{-1}(-\infty, a] \cong \) union des boules de rayon \( a \) centrées sur les points de \( P \)
Exemple 9
Exercice 8
Quelle est la sortie de l'algorithme pour ces données ?
2. Robotique
Question : comment attraper un objet à l'aide d'une main robotique et de la gravité ?
Observation : il y a plusieurs façons de l'attraper ; certaines sont meilleurs qu'autres
Filtration : espace de translations invalides + un rideau qui descend
\( (x,y) \in D_1 \) ⇒ il y a une façon d'attraper l'objet et la quantité d’énergie nécessaire pour s'échapper est \( y - x \)
En pratique :
- Translations et rotations ⇒ espace de configurations sans collision \( F \subset \mathbb{R}^2 \times \mathbb{S}^1 \)
- Complexe : échantillon sur les configurations invalides et triangulation de Delaunay
- Filtration définie sur les arêtes : \( -\infty \) si longueur sous un seuil, \( \min(-y) \) sinon. On regarde \( D_2 \)
Exemple 10
3. Visualisation scientifique
Problème : visualiser la formation de doigts dans un écoulement d'eau salée
Données :
- Pour chaque pas de temps \( k \), un ensemble fini \( P_k \subset \mathbb{R}^4 \)
- Un élément \( (x, y, z, c) \) correspond à un point avec coordonnées spatiales \( (x, y, z) \) avec concentration de sel \( c \)
Étapes :
- Interpoler la concentration sur l'espace
- Séparer l'eau salée de l'eau non-salée (seuillage)
- Détecter les différents doigts (segmentation)
- Relier les différents doigts entre les pas de temps
Détails de l'étape 3 (segmentation) :
- Fonction de filtration : distance géodésique (négative) vers la base
- Seuillage du diagramme de persistance de dimension 0 proportionnel à l'image de la fonction (10%)
- Chaque sommet est associé avec le maximum le plus proche
Exemple 11
4. Analyse de formes
Question : comment distinguer les trous d'un objet ?
Érosions + dilatations = filtration
- \( D_q \cap Q^{0,0} \) = \( \beta_q \) paires \( (- a_i, b_i) \) avec \( a_i, b_i \geq 0 \)
- Une paire \( (a_i, b_i) \) pour chaque trou
-
\( a_i \) : de combien il faut éroder l'objet pour casser ce trou
= épaisseur -
\( b_i \) : de combien il faut dilater l'objet pour remplir ce trou
= largeur
De plus, le couplage de l'algorithme de l'homologie persistante permet de définir les deux centres de chaque trou
Stabilité : la distance entre les paires de deux objets \( X \) et \( Y \) est bornée par \[ d_H(X, Y) + d_H(X^c, Y^c) \]
En français : si on perturbe la frontière de l'objet, l'épaisseur et la largeur de chaque trou reste à peu près la même
Morale
- La stabilité des diagrammes permet de dégager le bruit
- En même temps, on peut distinguer les features les plus importantes (potentiellement)
- On utilise souvent l'homologie persistante en dimension 0 (calcul beaucoup plus rapide)
Conclusion
- Homologie persistante = extension de l'homologie à une suite de complexes
- Stabilité ⇒ correction, classement, comparaison
- Complexité worst-case cubique, mais presque linéaire en pratique
- Très à la mode car elle permet de faire de petites erreurs
Quelques ressources :
