Algorithme couplé

En considérant que le minimum global du gradient topologique est certainement un point de contour, on l'utilise généralement comme point de référence. On peut alors construire la distance entre et n'importe quel point du domaine. À partir de là, un simple algorithme de descente sur la fonction distance en partant d'un point donnera le chemin minimal entre et , c'est-à-dire le chemin le plus court et le moins coûteux entre ces deux points. Si et sont deux points sur le même contour, comme la fonction potentiel est choisie de telle sorte qu'il soit peu coûteux de rester sur le contour (grâce au gradient topologique), le chemin minimal sera une très bonne approximation du contour entre et . L'avantage est que cette fois-ci, le contour identifié entre ces deux points sera fermé.

Une amélioration très peu coûteuse consiste à utiliser plusieurs points d'initialisation, et de construire la fonction distance à l'ensemble de ces points. Le diagramme de Voronoï correspondant peut être vu comme le graphe dual de celui de la fonction distance, et le point de distance minimale sur chaque arête du diagramme donne le point équidistant le plus proche des deux points-clés correspondant à l'arête.

L'algorithme est finalement le suivant:

Construire le gradient topologique pour la détection de contours, comme vu dans les sections précédentes.

Choisir points-clés. Le principal point-clé est le minimum global du gradient topologique, et les autres sont par exemple d'autres points ayant pour gradient topologique des valeurs proches du minimum global.

Construire la fonction distance à cet ensemble de points-clés.

En déduire le diagramme de Voronoï correspondant.

Pour chaque arête, trouver le point de distance minimale.

Pour chacun de ces points-selles, classés par distance croissante, vérifier qu'il ne servira pas à relier des points-clés déjà connectés à plusieurs autres points-clés.

Si ce n'est pas le cas, utiliser ce point de distance minimale pour initialiser un algorithme de descente vers chacun des deux points clés voisins, afin de récupérer le chemin minimal correspondant entre les deux points-clés.

Cet algorithme converge et assure que chaque point-clé est connecté à au plus deux autres points-clés. Cela fournit donc un contour fermé, reliant les points-clés, et qui est une approximation d'un contour de l'image puisqu'il passe dans un fond de vallée du gradient topologique.

Comme nous l'avons constaté dans [3], cela permet d'améliorer sensiblement notre algorithme d'inpainting. Cela permet également de segmenter l'image plus efficacement. Pour les autres applications, nous n'avons pas constaté de gain réellement significatif en utilisant cette méthode.