L'étiquetage de composantes connexes (ECC), également connu sous le nom d'analyse de composantes connexes, d'extraction de blobs, d'étiquetage de régions ou de découverte de blobs, est une application algorithmique de la théorie des graphes dans laquelle des sous-ensembles de composantes connexes sont étiquetés de manière unique en fonction d'une heuristique donnée. Il est utilisé en vision par ordinateur pour détecter des régions connexes dans des images numériques binaires, bien que les images en couleur et les données de dimension supérieure puissent également être traitées. L'ECC est distinct de la segmentation d'image, et l'extraction de blobs est liée mais différente de la détection de blobs.
En pratique, l'ECC opère sur un graphe construit à partir des données d'entrée, où les sommets représentent des pixels ou des éléments et les arêtes indiquent la connectivité entre voisins. Un algorithme parcourt le graphe, attribuant des étiquettes aux sommets en fonction de la connectivité et des valeurs relatives. Après l'étiquetage, le graphe peut être partitionné en sous-ensembles, permettant de récupérer et de traiter l'information originale pour des tâches telles que le comptage, le filtrage et le suivi de blobs.
Définition et terminologie
Le terme étiquetage de composantes connexes est utilisé de manière cohérente dans la littérature académique, tandis que l'analyse de composantes connexes (ACC) varie tant en terminologie qu'en définition du problème. Rosenfeld et al. définissent l'ECC comme la création d'une image étiquetée dans laquelle les positions associées à la même composante connexe de l'image binaire d'entrée ont une étiquette unique. Shapiro et al. décrivent l'ECC comme un opérateur dont l'entrée est une image binaire et la sortie une image symbolique où l'étiquette de chaque pixel est un entier identifiant de manière unique sa composante connexe.
Il n'y a pas de consensus sur la définition de l'ACC ; elle est souvent utilisée de manière interchangeable avec l'ECC. Une définition plus étendue de Shapiro et al. stipule que l'ACC consiste en l'étiquetage de composantes connexes des pixels noirs, suivi de la mesure des propriétés des régions de composantes et de la prise de décision. Cet article adopte une interprétation plus large qui intègre ces perspectives.
Construction du graphe et connectivité
Un graphe est construit à partir des données d'entrée pertinentes, avec des sommets contenant les informations nécessaires à l'heuristique de comparaison et des arêtes indiquant les voisins connectés. L'algorithme parcourt le graphe, étiquetant les sommets en fonction de la connectivité et des valeurs relatives. La connectivité est déterminée par le support ; pour les graphes d'images, les voisinages courants incluent la connectivité 4 (nord, sud, est, ouest) et la connectivité 8 (incluant les diagonales).
Après l'étiquetage, le graphe peut être partitionné en sous-ensembles, après quoi l'information originale peut être récupérée et traitée. Cette approche se généralise à des dimensions arbitraires, bien que la complexité temporelle et spatiale augmente en conséquence.
Algorithme une composante à la fois
L'algorithme une-composante-à-la-fois est rapide, simple à implémenter et basé sur des méthodes de parcours de graphe. Il fait partie de l'algorithme de segmentation par ligne de partage des eaux de Vincent et Soille, avec d'autres implémentations existantes. La méthode utilise une liste chaînée pour conserver les index des pixels connectés, le choix entre la recherche en profondeur ou en largeur n'ayant aucune différence pratique pour cette application.
L'algorithme suppose une image binaire avec des pixels de premier plan et d'arrière-plan, visant à étiqueter les composantes connexes du premier plan. Étapes :
- Commencer au premier pixel, définir l'étiquette courante à 1.
- Si le pixel est au premier plan et non étiqueté, attribuer l'étiquette courante et l'ajouter à une file d'attente ; sinon, passer au pixel suivant.
- Retirer un élément de la file d'attente, examiner ses voisins (selon le type de connectivité). Si un voisin est au premier plan et non étiqueté, attribuer l'étiquette courante et l'ajouter à la file d'attente. Répéter jusqu'à ce que la file soit vide.
- Passer au pixel suivant et incrémenter l'étiquette courante.
Les pixels sont étiquetés avant d'être mis en file, et les voisins de chaque pixel de premier plan ne sont vérifiés qu'une seule fois ; les voisins des pixels d'arrière-plan ne sont pas vérifiés. Le pseudo-code utilise deux files pour gérer le traitement des pixels, assurant un parcours efficace.
Applications en vision par ordinateur
L'ECC est largement utilisé en vision par ordinateur pour détecter des régions connexes dans des images binaires, souvent après une étape de seuillage. L'extraction de blobs peut également être appliquée aux images en niveaux de gris et en couleur. Les blobs peuvent être comptés, filtrés et suivis, rendant l'ECC précieux dans les systèmes de reconnaissance d'images et les interfaces homme-machine.
Par exemple, dans les pipelines de Machine learning, l'ECC peut prétraiter les images pour des tâches de détection d'objets ou de segmentation, complétant des techniques comme les architectures U-Net. Il est également utilisé dans les systèmes d'Artificial intelligence pour analyser des images médicales, l'inspection industrielle et la conduite autonome, où l'identification de régions connexes est cruciale.
Concepts connexes et extensions
L'ECC est lié mais distinct de la détection de blobs, qui se concentre sur l'identification de régions d'intérêt basées sur des variations d'intensité. En revanche, l'ECC étiquette toutes les composantes connexes en fonction de la connectivité. L'algorithme peut être étendu à des données de dimension supérieure, comme les volumes 3D en imagerie médicale, avec un coût computationnel accru.
Les avancées récentes dans les modèles de Deep learning et de Neural network ont conduit à des approches apprises pour la segmentation, mais l'ECC reste un outil fondamental pour le post-traitement et l'analyse. Sa simplicité et son efficacité en font un élément essentiel des bibliothèques et frameworks de vision par ordinateur, souvent utilisé en conjonction avec Data Augmentation et Loss Functions dans les pipelines d'entraînement.
Voir aussi
- Vision par ordinateur
- Segmentation d'image
- Détection de blobs
- Théorie des graphes