Morphologie mathématique

Amincissement homotopique

Amincissement homotopique : algorithme pour amincir un objet discret sans changer sa topologie ⇒ on ne peut que supprimer les points simples.

On l'utilisera pour calculer les squelettes

Remarque : on ne peut pas supprimer tous les points simples en même temps (en parallèle).

Il faut supprimer les pixels itérativement

Amincissement homotopique séquentiel

1. Parcourir les pixels dans le scan order et supprimer les points simples.
2. Répéter jusqu'à la stabilité

Propriétés :

• Le squelette a la même topologie
• Squelette non centré
• Détails géométriques perdus. Le squelette ne représente que la topologie de l'objet.

On pourrait parcourir les pixels dans un ordre aléatoire

Propriétés :

• Topologie conservée
• Légèrement plus centré

Il faut guider l'amincissement afin d'obtenir un squelette centré

Amincissement homotopique par contours

1. Sélectionner les pixels du contour de l'objet (4-adjacents du complémentaire)
2. Supprimer itérativement tous les pixels dans ce sous-ensemble. Faire plusieurs passes jusqu'à la stabilité
3. Passer au contours suivant

Propriétés :

• Squelette centré
• Plusieurs passes avant stabilité

Pourquoi ne pas utiliser la transformée en distance ?

Amincissement homotopique par transformée en distance

1. Mettre dans une file de priorité les pixels de l'objet avec leur transformée en distance
2. Prendre le premier pixel. S'il est simple, le supprimer et ajouter ses 8-voisins dans la file (s'ils ne sont pas déjà là)
3. Répéter jusqu'à vider la file.

Propriétés :

• Squelette centré
• Une seule passe avant stabilité

Peut-on faire pareil avec du calcul parallèle ?

Amincissement homotopique par sous-grille

1. Partition en 4 sous-grilles :
   • \( (0,0) + (2 \mathbb{Z})^2 \)
   • \( (1,0) + (2 \mathbb{Z})^2 \)
   • \( (0,1) + (2 \mathbb{Z})^2 \)
   • \( (1,1) + (2 \mathbb{Z})^2 \)
2. Supprimer (en parallèle) les points simples dans la première sous-grille
3. Passer à la sous-grille suivante

Propriétés :

• On peut supprimer les pixels en parallèle car ils sont assez éloignés entre eux
• Squelette centré
• Plusieurs passes avant stabilité

Amincissement homotopique par cliques critiques

• k-clique ensemble de pixels maximal dont l'intersection est un k-cube
• Une k-clique est critique si sa suppression change la topologie de l'objet
• Théorème : si \( Y \) contient au moins un pixel de chaque k-clique critique de \( X \) alors ils ont la même topologie

Algorithme d'amincissement homotopique :

1. Marquer les pixels des 2-cliques critiques (en parallèle)
2. Marquer un pixel pour chaque 1-clique critique qui n'est pas couverte (en parallèle)
3. Marquer un pixel pour chaque 0-clique critique qui n'est pas couverte (en parallèle)
4. Supprimer les pixels non marqués

Bref

• Amincissement homotopique : supprimer les points simples
• Squelette topologique, géométrie ignorée
• Plusieurs méthodes pour diriger la suppression

Il faudrait maintenant conserver la géométrie de l'objet

Squelette géométrique

Il ne faut pas supprimer les branches du squelette (même si elles ont des points simples).

Première idée : on ne supprime pas les pixels dans l'axe médian

Propriétés :

• L'amincissement homotopique fait conserver la topologie
• En fixant les pixels de l'axe médian, on conserve la géométrie
• Mais on a les mêmes défauts : squelette pas fin, pas robuste

Il existe d'autres solutions : filtrer l'axe médian, méthodes topologiques

Filtrer l'axe médian

Sur chaque pixel de l'axe médian on définit :

• \( DT(x) \) : distance vers le complémentaire
• \( \Pi(x) \) : points de contact de la boule maximale avec le contour
• \( \theta(x) \) : plus grand angle entre les points de contact
• \( \delta(x) \) : plus grande distance entre les points de contact

On peut filtrer l'axe médian suivant ces fonctions

Filtrage par rayon

1. Calculer la transformée en distance sur l'axe médian
2. Supprimer les pixels avec \( DT(x) \) en dessous d'un seuil

Filtrage par angle

1. Calculer \( \Pi(x) \) = plus proches points du complémentaire : extension du calcul de la transformée en distance
2. \( \Pi^e(x) = \cup \Pi(y) \) pour tout \( y \) 4-voisin de \( x \) tel que \( DT(y) \leq DT(x) \)
3. Calculer \( \theta(x) \) : essayer toutes les paires de points dans \( \Pi^e(x) \)
4. Supprimer les pixels avec \( \theta(x) \) en dessous d'un seuil

Filtrage par distance

1. Calculer \( \Pi^e(x) \)
2. Calculer \( \delta(x) \) : essayer toutes les paires de points dans \( \Pi^e(x) \)
3. Supprimer les pixels avec \( \delta(x) \) en dessous d'un seuil

Conserver les extrémités

• Oublions l'axe médian. On supprime les points simples sauf s'ils sont une extrémité
• On utilise les mêmes masques que l'algorithme d'élagage
• On fixe les extrémités avant chaque passe d'amincissement homotopique

Conserver les isthmes

• Isthme pixel dont son voisinage a plusieurs composantes connexes ⇒ pixel à l'intérieur du squelette
• Caractérisation : \( x \in X\) est un isthme ssi \( x \) n'est pas simple et \( x \notin A \odot B \)
  

Comme pour l'axe médian, ces méthodes se comportent mal quand l'objet est bruité

Filtrage des isthmes par persistance

Algorithme pour calculer des isthmes avec une fonction \( \pi \) pour le seuillage

1. \( b(x) \gets \infty \) pour tout pixel ; \( g \gets 0 \)
2. Pour tout isthme, \( b(x) = \min(b(x), g) \)
3. Faire une passe d'amincissement homotopique. Pour chaque pixel supprimé, \( \pi(x) = g - b(x) \)
4. Passer à la génération suivante : \( g \gets g+1\)

\( \pi(x) \) = persistance d'un isthme : grand pour les pixels qui sont des isthmes longtemps avant d'être supprimés

Bref

• Axe médian : mauvaise topologie, bruité
• Axe médian + amincissement homotopique : topologie corrigée, toujours bruité
• Il faut des méthodes pour simplifier l'axe médian