Distance Transform

Abstract: A distance transform, also known as distance map or distance field, is a representation of a distance function to an object, as an image. Such maps are used in several applications, especially in document image analysis. Some optimizations can be obtained by less generic methods: for example, maps calculated by front propagation can determine shorter paths, assuming that the image is non-convex. This presentation discusses different distance transform algorithms and underlines their advantages and weaknesses. Finally we will explain our choices. Résumé: Une carte de distances est une représentation sous forme d’image d’une fonction distance à un objet. Ces cartes sont utilisées dans de nombreuses applications, en particulier en analyse d’images de documents qui nous serviront d’illustration. Certaines methodes de calcul de cartes moins generiques que d’autres peuvent s’averer plus rapides: par exemple, des cartes calculées par propagation de fronts permettent de determiner des plus courts chemins mais ne fonctionnent que lorsque le support est connu pour etre non-convexe. Cette présentation fait un tour d’horizon des différents algorithmes de calculs de cartes de distance, met en évidence leurs atouts et faiblesses et explique les choix retenus