TNI+VO · Exercice de Programmation

EP02_04 — 📐 Transformée de distance sur image binaire

2.12.4 EP02_04 📐 Transformée de distance sur image binaire

Étant donné une image binaire où les pixels de valeur 1 représentent l’objet et les pixels 0 représentent le fond, la distance d’un pixel de fond reçoit la distance minimale au pixel d’objet le plus proche. Les pixels d’objet reçoivent une distance 0. Pour simplifier, considérez que l’image ne contient qu’un seul objet avec un seul pixel de valeur 1.

Problème : Lire une image binaire \(L \times C\) et une métrique, puis calculer cette distance simplifiée en appliquant l’une des trois formules :

\[d_{\text{Euclidienne}} = \sqrt{(\Delta r)^2 + (\Delta c)^2}\]

\[d_{\text{City-block}} = |\Delta r| + |\Delta c|\]

\[d_{\text{Échiquier}} = \max(|\Delta r|,\; |\Delta c|)\]

où \(\Delta r\) est la différence de lignes et \(\Delta c\) la différence de colonnes entre deux pixels.

2.12.4.1 🖼️ Pourquoi cela importe-t-il ? - Applications de la TD

La Transformée de distance (TD) apparaît dans des dizaines de pipelines de vision par ordinateur :

Métrique Complexité Application typique
Euclidienne 🔴 \(O(n^2)\) naïve Squelettisation, correspondance de formes
City-block 🟡 \(O(n)\) avec 2 passes Morphologie, dilatation/érosion
Échiquier 🟢 \(O(n)\) avec 2 passes Morphologie, dilatation/érosion

2.12.4.2 📌 Exigences techniques

  • Entrée : * Première ligne : \(L\) et \(C\) (entiers).
    • Deuxième ligne : nom de la métrique (euclidean, cityblock ou chessboard).
    • Ensuite, la matrice binaire \(L \times C\) (valeurs 0 ou 1).
  • Pixels d’objet (1) : distance \(= 0\) (ou \(0.00\) pour euclidienne).
  • Pixels de fond (0) : distance au seul pixel d’objet de l’image.
  • Arrondi (euclidienne) : imprimer avec 2 décimales (format :.2f). City-block et Échiquier produisent des entiers — imprimer sans décimales.
  • Sortie : valeurs séparées par des espaces, une ligne par ligne de la matrice.
  • Voir dans Figure 2.15 une simulation de cet EP.

2.12.4.3 📌 Exemples

Entrée Sortie Observation
4
4
chessboard
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0		 2 2 2 2
2 1 1 1
2 1 0 1
2 1 1 1		 La distance Échiquier est \(\max(\|dx\|, \|dy\|)\). Le seul pixel objet est \((2,2)=0\) ; les autres stockent leur distance minimale jusqu’à lui.

2.12.4.4 📌 Observations finales

  • Comme l’image ne contient qu’un seul objet d’un pixel, la distance de chaque pixel de fond est simplement la distance de ce pixel au seul point objet.
  • L’implémentation peut utiliser la force brute (parcourir tous les pixels de l’image et calculer la distance directement), car \(L\) et \(C\) sont petits dans les cas de test.
  • Ce problème est un échauffement pour la Transformée de distance générale, qui sera travaillée dans des chapitres ultérieurs avec plusieurs objets et des algorithmes optimisés.
📐 Simulateur EP02_04 : Transformée de distance interactive Métriques : L₁, L₂ et L_∞

Cliquez sur les cellules de l'image binaire pour alterner les pixels de l'objet (1) et observez la carte de distance minimale calculée dans la matrice résultante.

Métrique :
Image binaire (cliquer pour modifier)
Transformée de distance
Grille 5×5 · 1 pixel(s) d'objet · Métrique : Échiquier (entier)
Figure 2.15: Simulateur EP02_04 : Transformée de distance en image binaire (Chessboard, City-block et Euclidienne) 
%%writefile EP02_04.py
# Code Python
Overwriting EP02_04.py
TestSuite("EP02_04.py").run()
✔️ EP02_04.cases existe déjà dans casos/
📋 5 cas chargé(s) depuis casos/EP02_04.cases

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