Homologie persistante

SMACUD1L - Master IMD


Observations :

  • Le nombre de trous varie en fonction du paramètre
  • Certains trous restent dans les Ă©tapes suivantes
  • Si on bouge un peu les points, le comportement global est similaire

Rappel d'homologie

  • \(K\) : complexe simplicial fini
  • \(K_q\) : simplexes de \(K\) de dimension \(q\)
  • \( (C, \partial) \) : complexe de chaĂ®nes induit par \(K\) avec anneau de coefficients = \(\mathbb{Z}/2\mathbb{Z} \) (corps)
  • \(H_q = \ker(\partial_q) / \text{im}(\partial_{q+1}) \) : groupe d'homologie de dimension \(q\) de \(K\) (espace vectoriel)
  • \(\beta_q = \dim(H_q)\) = nombre de Betti de dimension \(q\)
Exemple 1

Cycles, classes d'Ă©quivalence, base d'homologie :

Soient \(K \subset K'\). L'application inclusion \(inc : K \longrightarrow K'\) induit une application linéaire \[\iota : H_q(K) \longrightarrow H_q(K')\] entre ses groupes d'homologie

Exemple 2

MĂŞme nombre de trous mais

  • \(\iota\) n'est pas injective ⇒ « un trou de K est bouchĂ© dans K' »
  • \(\iota\) n'est pas surjective ⇒ « K' a un trou qui n'Ă©tait pas dans K »

DĂ©finir la persistante

Filtration : suite de complexes imbriqués \[K^1 \subset K^2 \subset \cdots \subset K^n\]

Exemple 3

Soit \(f: K \rightarrow \mathbb{R}\) telle que :

  1. \(\sigma \subset \tau \Rightarrow f(\sigma) \leq f(\tau)\)
  2. \( f(K) = \{a_1 < a_2 < \cdots < a_n\} \)

Alors \( f^{-1}(-\infty, a_1] \subset f^{-1}(-\infty, a_2] \subset \cdots \) est une filtration (exercice facile)

Exercice 1

Compléter cette fonction pour qu'elle définisse une filtration

Exemple 4

Soit \(f: K_0 \rightarrow \mathbb{R}\) quelconque. On définit \( \bar{f}: K \rightarrow \mathbb{R} \)

  • \( \bar{f}(\sigma) = f(\sigma) \), si \( \sigma \in K_0 \)
  • \( \bar{f}(\sigma) = \max\{f(\tau) \vert \tau \subset \sigma, \tau \in K_0\} \), sinon

Alors \( \bar{f} \) définit une filtration (exercice facile)

Exercice 2

Éteindre cette fonction aux simplexes de dimension supérieure

Exemple 5

Soit \(K^1 \subset \cdots \subset K^n\) une filtration. On définit \( f: K^n \rightarrow \mathbb{R} \), \( f(\sigma) = i \Leftrightarrow \sigma \in K_{i} \setminus K_{i-1} \)

Alors \( f \) définit la filtration donnée (exercice facile)

Donc, on peut travailler avec une filtration (suite de complexes) ou avec une fonction monotone : \( \sigma \subset \tau \Rightarrow f(\sigma) \leq f(\tau) \)

Soit \( f \) monotone, \( f(K) = \{ a_1, \cdots, a_n\} \). Notation :

  • \( K^i = f^{-1}\left( -\infty, a_i \right] \)
  • \(\iota_q^{i,j}: H_q(K^i) \longrightarrow H_q(K^j)\) application linĂ©aire induite par l'inclusion (\( 1 \leq i \leq j \leq n \))
  • \( \beta_q^{i,j} = \dim( \text{im}(\iota_q^{i,j}) ) \) : nombres de Betti persistants
  • \( \mu_q^{i,j} = \beta_q^{i,j-1} - \beta_q^{i-1,j-1} - \beta_q^{i,j} + \beta_q^{i-1,j} \) (\( 1 \leq i < j \leq n+1,\quad \beta_q^{0,j} = \beta_q^{i,n+1} = 0 \))
Exercice 3
  • Quelle inĂ©galitĂ© entre \( \beta_q(K^i) \) et \( \beta_q^{i,j} \) ?
  • Quelle inĂ©galitĂ© entre \( \beta_q(K^j) \) et \( \beta_q^{i,j} \) ?
En français
  • \( \beta_q^{i,j-1} \) = nombre de trous de \( K^i \) qui sont encore dans \( K^{j-1} \)
  • \( \beta_q^{i,j-1} - \beta_q^{i-1,j-1} \) = nombre de trous qui apparaissent dans \( K^i \) et sont encore dans \( K^{j-1} \)
  • \( \beta_q^{i,j} - \beta_q^{i-1,j} \) = nombre de trous qui apparaissent dans \( K^i \) et sont encore dans \( K^{j} \)
  • \( \mu_q^{i,j} \) = nombre de trous qui apparaissent dans \( K^i \) et disparaissent dans \( K^{j} \)

Le diagramme de persistance de dimension q de \( f \) est le multi-ensemble \( D_q(f) \subset \overline{\mathbb{R}}^2 \) avec

  • les points \( (a_i, a_j) \) avec multiplicitĂ© \( \mu_q^{i,j} \) (\( a_{n+1} = \infty \))
  • les points \( (x, x) \) avec multiplicitĂ© \( \infty \), pour tout \( x \in \mathbb{R} \)

Les \( (a_i, a_j) \) sont les paires de persistance

Exemple 6

Homologie persistante de dimension 0

Morale
  • On peut suivre les trous d'un complexe Ă  autre dans une filtration (ils ne sont pas indĂ©pendants)
  • L'homologie persistante permet de dĂ©finir la date de naissance et de mort d'un trou, donc aussi sa durĂ©e.

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*} \]

  1. Pour chaque \( x \in X \), regarde la distance vers \( Y \)
  2. Fais la mĂŞme chose pour chaque \( x \in X \) et prends la plus grande distance
  3. É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 \) une intervalle

Cohen-Stenier et al, Stability of persistence diagrams (2005)

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

  1. Fais un couplage entre les points de \( X \) et \( Y \), prends la plus grande distance entre les couples
  2. 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 meilleur

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

Algorithme incrémental pour l'homologie

Algorithme pour calculer les nombres de Betti d'un complexe simplicial Delfinado + Edelsbrunner, 1992

Il faut trier les simplexes de façon Ă  avoir une filtration :

  • \(K = \{\sigma_1, \ldots, \sigma_n\}\)
  • Pour tout j, \(K^j = \{\sigma_1, \ldots, \sigma_j\}\) est un complexe simplicial
β0, β1, β2 ← 0
for j = 1...n
    q ← dim(σj)
    if σj appartient Ă  un cycle de Kj
        βq = βq + 1
    else
        βq+1 = βq+1 - 1
return (β0, β1, β2)

Idée de la preuve :

  • Ajouter un q-simplexe incrĂ©mente \(\beta_q\) ou dĂ©crĂ©mente \(\beta_{q+1}\) (ThĂ©orème d'Euler-PoincarĂ©)
  • Si \(\sigma^j\) appartient Ă  un cycle de \(K^j\) alors il y a un nouveau cycle par rapport Ă  \(K^{j-1}\), et ce n'est pas un bord.
Exercice 7

Calculer les nombres de Betti

1

Deux types de simplexes :

  1. Positif : il appartient Ă  un cycle dans \(K^j\)
    ⇒ « il ajoute un trou »
  2. NĂ©gatif : son bord est un cycle non trivial dans \(K^{j-1}\)
    ⇒ « il supprime un trou »

Algorithme

L'algorithme incrémental peut être adapté pour calculer les paires de persistance. Il faut :

  1. Bon choix des bases d'homologie
  2. Coupler les simplexes négatifs (un trou disparaît) avec des simplexes positifs (un trou apparaît)

Pour simplifier, on considère des filtrations avec un seul simplexe entrant à la fois.

Quand on arrive Ă  un simplexe positif \( \sigma^i \) :

  • nouveau cycle : \( g^i = \sigma^i + \sum_{l \in L} \sigma^l \)
  • notons que pour tout \( l \in L, l < i \)
  • base de \( H(K^i) \) = base de \( H(K^{i-1}) \cup \{ g^i \}\)
  • Correspondance Ă©lĂ©ment d'une base ↔ simplexe positif ↔ \( i \in [1, n] \)

Quand on arrive à un simplexe négatif \( \sigma^j \) :

  • \( \partial(\sigma^j) \) cycle non trivial dans \( K^{j-1} \) (exercice)
  • \( \partial(\sigma^j) = \sum_{i \in I} g^i \) dans \( H(K^{j-1}) \)
  • \( \sum_{i \in I} g^i= 0 \) dans \( H(K^{j}) \) ⇒ ils ne sont pas linĂ©airement indĂ©pendants
  • base de \( H(K^j) \) = base de \( H(K^{j-1}) \setminus \{ g^k \} \) (lequel ?)
  • Correspondance simplexe nĂ©gatif ↔ ensemble de simplexes positifs prĂ©cĂ©dents ↔ \( I \subset [ 1, j-1 ] \)

Pseudocode :

L0, L1, L2 ← ∅
B0, B1, B2 ← ∅
for j = 1...n
    q ← dim(σj)
    if σj est positif
        Bq ← Bq ∪ {j}
    else
        I ← ∂(σj)
        i ← max(I)  // c'est lui, le plus jeune !
        Bq-1 ← Bq-1 - {i}
        Lq-1 ← Lq-1 ∪ {(i,j)}
foreach σi non couplĂ©
    q ← dim(σi)
    Lq ← Lq ∪ {(i,n+1)}
return (L0, L1, L2)

\( D_q = \{ (a_i, a_j) \vert (i,j) \in L_q \} \)

Exercice 8

Calculer les paires de persistance \( (i, j) \)

1

k-Triangle Lemma

Soit \( Q^{i,j} = ]-\infty, i] \times ]j, \infty[ \), alors \[ \beta_q^{i,j} = \#(L_q \cap Q^{i,j}) \]

C'est la clé de la preuve de l'algorithme.

On fixe \( q \) et \( i \), et on le démontre par induction sur \( k = j-i \geq 0 \).

Cas de base : Si \( i = j \) alors \( \beta_q^{i,i} = \beta_q(K^i) \).

D'autre part, \( \#(L_q \cap Q^{i,i}) \) =

  • = nombre de paires \( (a,b) \in L_q, a \leq i < b\)
  • = nombre \( q \)-simplexes positifs moins nombre \( (q+1) \)-simplexes nĂ©gatifs Ă  l'Ă©tape i
  • = \( \beta_q(K^i) \) (voir l'algorithme incrĂ©mental)

Induction : Vrai pour \( \beta_q^{i,j} \). Deux possibilités pour \( \beta_q^{i,j+1} \) :
\( \beta_q^{i,j+1} = \beta_q^{i,j} \) ou \( \beta_q^{i,j+1} = \beta_q^{i,j} -1 \)

\( \beta_q^{i,j+1} = \beta_q^{i,j} -1 \) ssi :

  • \( \partial(\sigma^{j+1}) \sim x \in H_q(K^i) \), car \( \iota_q^{i,j}(\partial(\sigma^{j+1})) \neq 0 \) et \( \iota_q^{i,j+1}(\partial(\sigma^{j+1})) = 0 \)
  • ssi \( \sigma^{j+1} \) est un simplexe nĂ©gatif de dimension \( q+1\), \( \partial(\sigma^{j+1}) = \sum_{i \in I} g^i \) dans \( H_q(K^i) \)
  • ssi il y a une paire \( (a, j+1) \in L_q \) avec \( a = \max(I) < i \)
  • ssi \( \#(L_q \cap Q^{i,j+1}) = \#(L_q \cap Q^{i,j}) - 1 \) □

Ce qui reste :

  • DĂ©montrer que \( D_q = \{ (a_i, a_j) \vert (i,j) \in L_q \} \).
  • Filtration gĂ©nĂ©rale, avec plusieurs simplexes entrant en mĂŞme temps.
  • L'algorithme explicite pour savoir si un simplexe est positif, nĂ©gatif, et son bord dans la base de \( H_q^{j} \)

L'algorithme explicite est similaire à celui du calcul de l'homologie avec la Forme Normale de Smith et sa complexité en temps est \( \mathcal{O}(n^3) \)

Morale
  • Algorithme aussi basĂ© sur la Forme Normale de Smith.
  • Quand plusieurs trous se fusionnent, ils tuent le plus jeune.

Applications

Quelques applications :

  1. Robotique : comment attraper un objet
  2. Traitement d'images : reconstruction de contours
  3. Visualisation scientifique : distinguer les parties importantes
  4. Analyse de formes : mesurer les trous

1. 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 \)
  • On construit cet espace avec un Ă©chantillon sur les configurations invalides et un type de complexe simplicial (α-weighted complexes)
  • On trie les simplexes du complĂ©mentaire de haut en bas et on regarde \( D_2 \)

2. 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 :

  1. Construis une filtration avec des boules croissantes centrĂ©es sur les points (α-complexe)
  2. Calcule le diagramme de persistance de dimension 1 (composantes connexes ⇒ très rapide)
  3. Ignore les paires les plus proches de la diagonale Ă  partir d'un seuil (widest gap) ⟵ clĂ© de l'algorithme
  4. Le graphe \( G \) est formée par les cycles d'homologie des paires qui restent
Exercice 9

Quelle est la sortie de l'algorithme pour ces données ?

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 :

  1. Interpoler la concentration sur l'espace
  2. Séparer l'eau salée de l'eau non-salée (seuillage)
  3. Détecter les différents doigts (segmentation)
  4. 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

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 :

  • Applied Algebraic Topology Network [YouTube]
  • Cours de Topological data analysis avec exercices [cours]
  • Geometric and Topological Inference [livre]
  • Computational topology: an introduction [livre]
  • Topological Data Analysis for Scientific Visualization [livre]