Discussion :

[cjacquel]

Bonjour,

Que choisir entre le distance de chamfrein et l'Edm (Euclidean distance map) ?

Merci
Christophe

[Kangourou]

Bonjour,

La carte des distances euclidiennes est normalement plus exacte que les distances de chanfrein. Si le temps de calcul n'est pas trop long, alors c'est ce qu'il vaut mieux utiliser.

Les distances de chanfrein sont des approximations de la distance euclidienne, et induisent donc des déformations (cartes de distance un peu "anguleuses"). Par contre elles peuvent être plus rapide à exécuter, et plus simples à implémenter.

[ToTo13]

induisent donc des déformations (cartes de distance un peu "anguleuses")

Les EDM aussi (que l'on appelle aussi distance de Montanari si ma mémoire est bonne). C'est le même masque utilisé, sauf que l'on utilise des poids réels au lieu d'entiers.

[Kangourou]

Les EDM aussi (que l'on appelle aussi distance de Montanari si ma mémoire est bonne). C'est le même masque utilisé, sauf que l'on utilise des poids réels au lieu d'entiers.

heu... non !
Par définition une EDM utilise une distance euclidienne, on ne doit donc pas observer d'artefact dû à la propagation d'une distance calculée dans un masque. Montanari utilise une distance calculée (en flottant) dans un voisinage local, mais autorise un voisinage plus grand que précédemment, ce qui réduit les erreurs mais ne les supprime pas.

Je me suis replongé dans la thèse de Thiel (1994) (https://tel.archives-ouvertes.fr/tel-00005113), et grosso-modo l'historique est le suivant :

• Rosenfeld et Pfalz (1966, 1968) introduisent les distances discrètes D4 et D8
• Montanari (1968) augmente la taille du voisinage pour tenir compte aussi des pixels qui ne sont pas des voisins directs (par ex les pixels en +/-1, +/-2)
• Danielsson (1980) introduit un algo de calcul des distances euclidiennes, qui nécessite de garder les coordonnées des pixels contributeurs (on a des algos 'vectoriels')
• Borgefors (1984, 1986) introduit les distances de chanfrein, qui consistent à remplacer identifier les poids "idéaux" pour des calculs sur des voisinages limités et à base d'entiers
• Dans les années 1990, plusieurs approches émergent pour le calcul des cartes de distance euclidiennes. On en trouve un comparatif dans la revue de Ricardo Fabbri : "2D Euclidean Distance Transform Algorithms: A Comparative Survey", qui a aussi mis ses codes à disposition : http://distance.sourceforge.net/

A+