Bassin versant (traitement d’images)

En géologie, un bassin versant est une ligne de partage des eaux qui sépare les bassins hydrographiques adjacents.

Bassin versant par inondation

L’idée a été introduite en 1979 par S. Beucher et C. Lantuéjoul. L’idée de base consistait à placer une source d’eau dans chaque minimum régional du relief, à inonder tout le relief des sources et à construire des barrières lorsque différentes sources d’eau se rencontrent. L’ensemble de barrières qui en résulte constitue un bassin versant par inondation. Un certain nombre d’améliorations, collectivement appelées Priorité-Inondation, ont depuis été apportées à cet algorithme.

Bassin versant par distance topographiquedit

Intuitivement, une goutte d’eau tombant sur un relief topographique s’écoule vers le minimum  » le plus proche « . Le minimum « le plus proche » est celui qui se trouve à la fin du chemin de descente le plus raide. En termes de topographie, cela se produit si le point se situe dans le bassin versant de ce minimum. La définition précédente ne vérifie pas cette condition.

Bassin versant selon le principe de la goutte d’eaudit

Intuitivement, le bassin versant est une séparation des minima régionaux à partir desquels une goutte d’eau peut s’écouler vers des minima distincts. Une formalisation de cette idée intuitive a été fournie pour définir un bassin versant d’un graphique pondéré par les arêtes.

Bassin hydrographique inter-pixels

S. Beucher et F. Meyer ont introduit une implémentation algorithmique inter-pixels de la méthode du bassin hydrographique, suivant la procédure suivante:

1. Étiquetez chaque minimum avec une étiquette distincte. Initialisez un ensemble S avec les nœuds étiquetés.
2. Extrait de S un noeud x d’altitude minimale F, c’est-à-dire F(x) = min {F(y)|y ∈ S}. Attribuez l’étiquette de x à chaque nœud non étiqueté y adjacent à x et insérez y dans S.
3. Répétez l’étape 2 jusqu’à ce que S soit vide.

Bassin hydrographique topologiquemodifier

Les notions précédentes portent sur les bassins versants, mais pas sur la ligne de séparation produite. Le bassin versant topologique a été introduit par M. Couprie et G. Bertrand en 1997, et bénéficie de la propriété fondamentale suivante.Une fonction W est un bassin versant d’une fonction F si et seulement si W ≤ F et W conserve le contraste entre les minima régionaux de F ; où le contraste entre deux minima régionaux M1 et M2 est défini comme l’altitude minimale à laquelle il faut monter pour passer de M1 à M2. Un algorithme efficace est détaillé dans l’article.

Algorithme du bassin versant

Différentes approches peuvent être utilisées pour utiliser le principe du bassin versant pour la segmentation d’images.

• Des minima locaux du gradient de l’image peuvent être choisis comme marqueurs, dans ce cas une sur-segmentation est produite et une deuxième étape consiste à fusionner des régions.
• La transformation des bassins hydrographiques basée sur des marqueurs utilise des positions de marqueurs spécifiques qui ont été définies explicitement par l’utilisateur ou déterminées automatiquement avec des opérateurs morphologiques ou d’autres moyens.

Algorithme d’inondation de Meyer

L’un des algorithmes de bassin versant les plus courants a été introduit par F. Meyer au début des années 1990, bien qu’un certain nombre d’améliorations, collectivement appelées Priorité-Inondation, aient depuis été apportées à cet algorithme, y compris des variantes adaptées à des ensembles de données composés de milliards de pixels.

L’algorithme fonctionne sur une image en échelle de gris. Lors des inondations successives du relief de la valeur grise, des bassins versants avec des bassins versants adjacents sont construits. Ce processus d’inondation est effectué sur l’image en dégradé, c’est-à-dire que les bassins doivent émerger le long des bords. Normalement, cela conduira à une sur-segmentation de l’image, en particulier pour les matériaux d’image bruyants, par ex. données de tomodensitométrie médicale. Soit l’image doit être prétraitée, soit les régions doivent être fusionnées sur la base d’un critère de similarité par la suite.

1. Un ensemble de marqueurs, les pixels où l’inondation doit commencer, sont choisis. Chacun reçoit une étiquette différente.
2. Les pixels voisins de chaque zone marquée sont insérés dans une file d’attente de priorité avec un niveau de priorité correspondant à l’amplitude du gradient du pixel.
3. Le pixel avec le niveau de priorité le plus élevé est extrait de la file d’attente de priorité. Si les voisins du pixel extrait qui ont déjà été étiquetés ont tous la même étiquette, le pixel est étiqueté avec leur étiquette. Tous les voisins non marqués qui ne sont pas encore dans la file d’attente prioritaire sont placés dans la file d’attente prioritaire.
4. Refaire l’étape 3 jusqu’à ce que la file d’attente prioritaire soit vide.

Les pixels non marqués sont les lignes de partage des eaux.

Exemple d’une transformation de bassin hydrographique soutenue par des marqueurs pour une population de granulés pharmaceutiques. Les lignes de partage des eaux sont superposées en noir sur la pile d’images CT.

Algorithmes optimaux de forêt couvrant (coupes de bassins versants) Modifier

Les bassins versants en tant que forêt couvrant optimale ont été introduits par Jean Cousty et al. Ils établissent la cohérence de ces bassins versants : ils peuvent être définis de manière équivalente par leurs  » bassins versants  » (par une propriété de descente la plus raide) ou par les  » lignes de séparation  » séparant ces bassins versants (par le principe de la goutte d’eau). Ensuite, ils prouvent, par un théorème d’équivalence, leur optimalité en termes de forêts couvrant au minimum. Ensuite, ils introduisent un algorithme en temps linéaire pour les calculer. Il est intéressant de noter que des propriétés similaires ne sont pas vérifiées dans d’autres frameworks et que l’algorithme proposé est l’algorithme existant le plus efficace, à la fois en théorie et en pratique.

• Une image avec deux marqueurs (verts), et une Forêt couvrant Minimale calculée sur le gradient de l’image.

• Résultat de la segmentation par Forêt couvrant au minimum