EP08_05 — 🟡 Étiquetage des Composantes Connexes : Segmentation d’Instances

8.14.5 EP08_05 🟡 Étiquetage des Composantes Connexes : Segmentation d’Instances

L’exemple de segmentation classique de ce chapitre a séparé les « instances » de pièces simplement par leur déconnexion spatiale dans le masque binaire résultant du seuillage d’Otsu. Cette étape finale — étiqueter chaque composante connexe avec un identifiant d’instance — est exactement ce que vous êtes chargé d’implémenter ici, à partir de zéro, sur un masque binaire déjà prêt (0 = fond, 1 = objet), comme s’il s’agissait d’une réimplémentation manuelle de cv2.connectedComponents.

Cet exercice met également en évidence, de manière très concrète, la limitation discutée dans le chapitre : le résultat dépend entièrement de la façon dont on définit la « voisinage » entre pixels — et, comme vous le verrez dans le deuxième exemple, deux pixels en diagonale peuvent être considérés comme la même instance ou comme des instances différentes, en fonction exclusivement de la connectivité choisie, et non d’une quelconque notion sémantique d’objet.

8.14.5.1 📋 Directives d’Implémentation

Entrée : Lire les dimensions \(H \times W\) du masque binaire et ses \(H \times W\) valeurs (\(0\) ou \(1\)).
Connectivité : Lire l’entier \(c \in \{4, 8\}\). En connectivité \(4\), les voisins de \((i,j)\) sont \((i{-}1,j)\), \((i{+}1,j)\), \((i,j{-}1)\) et \((i,j{+}1)\). En connectivité \(8\), on ajoute les quatre diagonales : \((i{-}1,j{-}1)\), \((i{-}1,j{+}1)\), \((i{+}1,j{-}1)\) et \((i{+}1,j{+}1)\).
Découverte des composantes : En parcourant le masque ligne par ligne, de gauche à droite et de haut en bas, chaque fois qu’un pixel de valeur \(1\) encore non étiqueté est trouvé, il initie une nouvelle composante : attribuez-lui le prochain étiquette disponible (la première composante découverte reçoit l’étiquette \(1\), la deuxième l’étiquette \(2\), et ainsi de suite) et propagez cette même étiquette à tous les pixels de valeur \(1\) atteignables à partir de lui par une chaîne de voisins (selon la connectivité choisie) — par recherche en largeur, en profondeur, ou par union-find, à votre choix.
Pixels de fond : restent avec l’étiquette \(0\) et n’appartiennent à aucune instance.
Sortie : D’abord, imprimer la carte complète des étiquettes — \(H\) lignes avec \(W\) entiers chacune. Ensuite, pour chaque étiquette \(\ell\) de \(1\) à \(K\) (dans l’ordre de découverte), imprimer Instance l: A pixels, où \(A\) est la quantité de pixels avec cette étiquette. Enfin, imprimer Total d'instances: K.

8.14.5.2 📌 Contraintes Computationnelles

Ordre de découverte = ordre de parcours : les étiquettes sont numérotées dans l’ordre où chaque nouvelle composante est trouvée par le parcours ligne par ligne, et non par taille ou position.
Connectivité explicite : deux pixels de valeur \(1\) n’appartiennent à la même instance que s’il existe une chaîne de voisins selon \(c\) les reliant l’un à l’autre — ne pas utiliser par erreur la connectivité opposée.
Masque binaire pur : toutes les valeurs d’entrée sont exactement \(0\) ou \(1\).

8.14.5.3 🧠 Fondement Théorique

Élément	Rôle dans la segmentation classique d’instances
Seuillage (Otsu, Chap. 4)	Étape précédente qui produit le masque binaire à partir de l’image d’intensité
Composante connexe	Chaque instance est définie uniquement par la connectivité spatiale des pixels d’objet, sans aucune notion de forme, de classe ou d’apparence
Connectivité 4 vs. 8	Paramètre qui modifie le résultat : en connectivité 8, deux blobs unis uniquement en diagonale deviennent une seule instance
Limitation centrale	La technique fusionne des instances qui se touchent ou se chevauchent (même si ce sont des objets clairement distincts), car il n’y a pas de notion d’« objet » — seulement de « région connectée »

8.14.5.4 📦 Spécification d’Entrée et de Sortie (VPL)

Entrée :

Ligne 1 : Entiers \(H\) et \(W\).
Les \(H\) lignes suivantes : \(W\) entiers (\(0\) ou \(1\)) chacune.
Dernière ligne : Entier \(c\) (\(4\) ou \(8\)).

Sortie :

\(H\) lignes avec \(W\) entiers chacune (la carte des étiquettes).
Une ligne par instance, dans l’ordre de découverte : Instance l: A pixels.
Dernière ligne : Total d'instances: K.

8.14.5.5 📌 Exemples

Entrée	Sortie	Observation
6 6 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 8	0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 2 2 Instance 1: 4 pixels Instance 2: 4 pixels Total d’instances: 2	Deux blocs \(2\times2\) clairement séparés : le résultat est le même en connectivité 4 ou 8.
2 2 1 0 0 1 8	1 0 0 1 Instance 1: 2 pixels Total d’instances: 1	En connectivité 8, les deux pixels en diagonale appartiennent à la même instance. Répétez cet exemple avec \(c=4\) : le résultat devient 2 instances de 1 pixel chacune — uniquement par le changement de connectivité, sans aucune différence dans le masque.

🎮 Simulateur EP08_05 : Composants connectés (Connectivité 4 vs. 8) Même masque → Étiquettes différentes

Le même masque (deux pixels en diagonale) — basculez la connectivité et observez le nombre d'instances et les couleurs des étiquettes changer.

–

Figure 8.19: Simulateur EP08_05 : Étiquetage des composants connexes — Connectivité 4 vs. 8

%%writefile EP08_05.py
# Code Python

Overwriting EP08_05.py

TestSuite("EP08_05.py").run()

✔️ EP08_05.cases existe déjà dans casos/
📋 6 cas chargé(s) depuis casos/EP08_05.cases

🔍 Test de Python : EP08_05.py
⚠️ EP08_05.py : fichier vide (moins de 3 lignes). Tests ignorés.