La transformée en distance (distance transform) d'une image binaire, parfois appelée fonction distance, permet de connaître la distance entre un pixel donné et le pixel le plus proche de l'image. De nombreuses méthodes exploitent cette transformée pour accéler des calculs. Par exemple dans la localisation de motifs dans un image par Chamfer Matching ¹ ou pour l'obtention d'une distance de Hausdorff entre deux images ², les calculs peuvent être considérablement accélérés. En effet le calcul de la transformée peut-être réalisé très rapidement, avec une très bonne approximation, en propageant un petit masque sur deux parcours de l'image. La carte de dissimilarité, que nous employons pour comparer des images, peut également se formuler avec des transformées en distances (voir le billet Reconnaissance de symboles binaires par mesure de dissimilarités locales, par exemple).

L'inconvénient est que la transformée en distance est définie pour des images binaires. Obtenir une définition pour des images en niveaux de gris peut permettre une extension de nombre de méthodes aux images en niveaux de gris également. Ce billet est un petit état de l'art des méthodes qui existent pour obtenir une transformée en distance pour des images en niveau de gris.

Définition pour des images binaires

La transformée en distance (TeD) est définie par :

Étant donnée une image, sa transformée en distance est une image où la valeur de chaque pixel correspond à la distance du pixel du fond le plus proche.

On peut définir une variante où le mot "fond" (background) est remplacé par "forme" (foreground). Pour être plus précis, il conviendrait donc de parler soit de transformée en distance par rapport au fond, soit de transformée en distance par rapport à la forme. Certaines confusions que l'on trouve parfois dans les articles seraient ainsi évitées.

Dans une image binaire, la distance entre deux pixels est donnée par la distance euclidienne entre les deux points. La distinction fond/forme est complète, le fond étant par exemple représenté par les pixels de valeur 0, la forme par les valeurs 1.

Pour étendre la définition à des images en niveaux de gris, deux approches sont possibles :

• adapter la notion de distance entre deux pixels, ou
• adapter la notion de "fond".

Généralisation de la distance

Une étude de Céline Fouard ³ résume la situation : la définition reste la même, change la définition de la distance. Si l'on considère deux pixels, il est nécessaire de prendre en compte les niveaux de gris des pixels du chemin qui relie ces deux pixels. Si ce chemin est noté $\pi(t)$, deux possibilités sont retenues :

• prendre la somme des pixels le long de ce chemin :

  $D = \int_{0}^{1}\| \pi(t) \| \mathrm{d}t ,$

• ou prendre la longeur du chemin le long de la "surface" définie par l'image:

  $D = \int_{0}^{1}\| \frac{\mathrm{d}\pi(t)}{\mathrm{d}t}(t) \| \mathrm{d}t .$

Gray Weighted Distance Transform (GWDT)

La distance choisie est définie par la somme pondérée des niveaux de gris le long du chemin discret reliant deux points. Cette distance revient à estimer la surface située sous la courbe représentant les niveaux de gris en fonction du chemin parcouru. La distance est donc l'intégrale des niveaux de gris entre les deux pixels. In fine, le coût de déplacement entre deux pixels adjacents est donc le suivant :

\[ w_{GWDi} = \frac{1}{2} (I(t_i) + I(t_{i+1})) \times | t_i - t_{i+1} | \]

où $| | t_i - t_{i+1} | |$ est la distance spatiale entre deux pixels et $I(t_i)$ est le niveau de gris de l'image pour le pixel $t_i$.

La méthode revient parcourir un chemin contenant les plus faibles niveaux de gris possibles.

Weighted Distance Transform on Curved Space (WDTOCS)

Dans ce cas, le chemin entre deux points est défini comme un chemin en 3 dimensions, contraint de rester sur la surface définie par les niveaux de gris de l'image. La distance est définie comme la longueur du plus petit chemin géodésique entre ces deux points. Le coût de déplacement entre deux pixels adjacents est alors :

$w_{WDOCSi} = \sqrt{(I(t_i) + I(t_{i+1}))^2 + | t_i - t_{i+1} |^2}.$

La méthode revient à parcourir un chemin présentant le moins de variation de niveaux de gris possible.

Critique des deux méthodes

Le principal inconvénient l'approche WDTOCS est l'inhomogénéité de l'équation. Si les niveaux de gris ne représentent pas physiquement une distance, par exemple une intensité lumineuse comme c'est le plus souvent le cas, alors la formule impose de réaliser la somme d'intensité et de "vraies" distance. Pour pallier ce problème, les niveaux de gris sont coeffficientés, camouflant ainsi cette inconsistance. Le coefficient permet également de résoudre un problème de dynamique entre les axes x, y et les intensités.

L'approche GWDT présente quelques lacunes quant à son utilisation en tant que distance : c'est une distance par rapport à la forme, mais pas par rapport au fond. De plus certaines informations situées à l'interface fond/forme ne sont pas correctement prises en compte (voir Évaluation de la qualité d’images compressées avec des dissimilarités locales et globales).

Ces deux approches présentent l'intérêt d'avoir une interprétation claire. Par contre elles ne sont applicable, que lorsque l'image possède une forme exprimée sur un fond. Typiquement une image représentant un objet sur un fond uniforme. Ainsi leur utilisation est rarement possible sur une image naturelle (une forêt), où la distinction fond/forme n'existe généralement pas.

Généralisation de la notion de fond : Continuous Distance Transform (CDT)

Dans cette approche par Joaquim Alrandis ⁴, la distance représentée reste la distance euclidienne calculée entre les coordonnées x, y des deux pixes considérés. Par contre l'approche est une tentative de généraliser les notions de "pixel blanc" et "trouver le pixel blanc le plus proche".

• La notion "pixel blanc" devient "la plus grande valeur brillante" (maximum bright value).
• La notion "trouver le pixel blanc le plus proche" est transformée en "accumuler les valeurs brillantes dans le voisinage, jusqu'a un maximum" (accumulate a maximum bright value on the neighborhood).

Grosso-modo, la méthode revient à faire croître une fenêtre, plus exactement une bordure, autour du pixel considéré. Une somme pondérée des valeurs située sur cette bordure est effectuée et accumulée. Le rayon de la bordure croît ainsi jusqu'à  ce que la valeur accumulée est supérieur ou égale au niveau de gris maximum de l'image. Le rayon de la bordure est alors retenu comme distance.

L'approche est interressante dans cette généralisation des notions. Cependant, cette définition semble être une réponse un peu trop ad-hoc au problème. Ainsi l'interprétation des distances renvoyée est plus délicate que dans les deux autres méthodes.

Ce qu'il faudrait (en guise de conclusion)

La transformée en distance idéale présenterait les qualités suivantes :

• une distance bien définie et interprétable facilement. Cette distance n'est pas nécessairement la distance euclidienne, elle peut être la distance généralisée calculée sur un chemin,
• applicable sur des images ne présentant pas nécessairement de fond/forme,
• tendre vers la TeD binaire lorsque l'image tends vers une image binaire.

FMN.

ps: ajout de dernière minute. En contrôlant le référencement de cette page, je suis tombé sur une autre approche : "Distance transforms for real-valued functions" par Ilya Molchanov et al. (http://dx.doi.org/10.1016/S0022-247X(02)00719-9). Dès que j'ai lu l'article en détail, j'en donne mon analyse.

Références

1.

• [1988,article] bibtex
  G. Borgefors, "Hierarchical Chamfer Matching: A Parametric Edge Matching Algorithm," IEEE Trans. Pattern Anal. Mach. Intell., vol. 10, iss. 6, pp. 849-865, 1988.
  @article{Borgefors1988,
  author = {Gunilla Borgefors},
  title = {Hierarchical Chamfer Matching: A Parametric Edge Matching Algorithm},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  volume = {10},
  number = {6},
  year = {1988},
  pages = {849-865},
  ee = {http://computer.org/tpami/tp1988/i0849abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de} }

2.

• [2009,book] bibtex
  R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, 2009.
  @book{Brunelli2009,
  author = "Brunelli, R.", TITLE = "Template Matching Techniques in Computer Vision: Theory and Practice", PUBLISHER = "Wiley", YEAR = "2009", MONTH = "May", BIBSOURCE = "http://www.visionbib.com/bibliography/match-pl489.html#TT41877"}

3.

• [2006,inproceedings] bibtex
  C. Fouard and M. Gedda, "An Objective Comparison between Gray Weighted Distance Transforms and Weighted Distance Transforms On Curved Spaces," in Proc. of DGCI'06, 2006.
  @InProceedings{Fouard2006,
  author = {Fouard, C\'eline and Gedda, Magnus},
  title = {An Objective Comparison between Gray Weighted Distance Transforms and Weighted Distance Transforms On Curved Spaces },
  booktitle = {Proc. of DGCI'06},
  year = {2006},
  }

4.

• [2000,inproceedings] bibtex
  J. Arlandis, J. C. Pérez-Cortes, and R. Llobet, "Handwritten Character Recognition using the Continuous Distance Transformation," in ICPR, 2000, pp. 1940-1943.
  @inproceedings{Arlandis2000,
  author = {Joaquim Arlandis and Juan Carlos P{\'e}rez-Cortes and Rafael Llobet},
  title = {Handwritten Character Recognition using the Continuous Distance Transformation},
  booktitle = {ICPR},
  year = {2000},
  pages = {1940-1943},
  ee = {http://csdl.computer.org/comp/proceedings/icpr/2000/0750/01/07501940abs.htm},
  bibsource = {DBLP, http://dblp.uni-trier.de} }