retour

Équation iconale, plus courts chemins

Ce script effectue un calcul approché de plus courts chemins dans le plan (ou une partie du plan), où chaque point est éventuellement muni d'une «vitesse» différente (d'autant plus importante que le point de l'image correspondante est sombre).
Diverses applications sont montrées:

• Calcul de trajectoires de rayons lumineux (2 indices, gradient, trou)
• Calcul de plus courts chemins dans un environnement (obstacles, labyrinthe)
• Détection de vaisseaux dans des images médicales (vaisseaux, cortex)

Le script

• Sélectionnez l'image dans lequel vous souhaitez calculer des plus courts chemins.
• Effectuez un click gauche sur un point de l'image. La carte des distances au point est alors calculée par un algorithme de «propagation d'onde» appelé «fast marching method» (la vitesse de l'animation est réglable). Une représentation de cette carte des distances par lignes de niveaux et une carte 3d (dont on peut changer le point de vue) apparaissent.
• Effectuez un click droit sur un point de l'image pour calculer et tracer le plus court chemin jusqu'au point choisi précédemment (on peut également effectuer un click gauche sur la carte des distances).

Vitesse: 50 100 500 max Image: Uniforme 2 indices 2 indices (très différents) Gradient Fort gradient Trou Obstacles Labyrinthe Vaisseau Cortex

Comment ça marche?

En quelques mots:

• Il faut voir l'image de départ comme une carte géographique, où l'intensité de l'image indique la vitesse à laquelle on peut se déplacer (on se déplace d'autant plus vite que la zone est sombre).
• Premier click: la carte des «temps d'arrivée» D(x,y) (en partant du point de départ cliqué a) est obtenue par résolution approchée de l'équation aux dérivées partielles suivante: ∥ ∇ D(x,y)∥=I(x,y) avec condition initiale D(a)=0, où ∇D est le vecteur gradient de D, et I(x,y) est l'intensité de l'image. L'idée est que plus l'image est sombre dans une zone, plus l'intensité est faible, et plus la variation de temps d'arrivée (mesurée par la norme du gradient) sera faible.
• Second click: on effectue une «descente» sur la carte des temps d'arrivée depuis le point cliqué b, jusqu'à a - autrement dit, on suit la ligne de plus grande pente sur la figure en 3D de gauche.
• On peut montrer que l'on obtient ainsi une approximation du «plus court chemin» (en un sens à préciser) entre a et b.

Le problème et la méthode de résolution sont respectivement détaillés ici (pages 22 à 31) et là (pages 42 à 60).
La résolution de ce problème est accessible à de bons étudiants d'informatique en L1 ou L2. Il est bon de se familiariser préalablement avec l'algorithme de Dijkstra, et d'avoir quelques notions de géométrie euclidienne.