tnorth ~ blog

Maintenant que l'année académique recommence, il est temps de publier un travail effectué dans le cadre des études : je ne vais pas m'étendre là dessus, et les intéressés pourrons consulter le poster associé ici.

Dans ce travail, le très connu algorithme de Dijkstra a été utilisé pour chercher un plus court chemin dans des images du fond de l'oeil.

Introduction

L'algorithme en question peut s'appliquer à énormément de choses différentes. Il est par exemple utilisé dans le protocole ''open shortest path first'' pour le routage IP, ou autres applications "graphes et réseaux". De même, il sert à assister des algorithmes d'intelligence artificielle pour déterminer le chemin le plus court pour déplacer, dans l'exemple d'un jeu, un personnage d'un endroit à un autre d'une manière efficace.

Revenons au cas d'une image: la création d'un graphe dans ce cas devient bien moins générale, et se réduit à des réseaux ou chaque sommet du graphe n'est relié qu'à ses voisins (géographiques) directs. Chaque lien est doté d'un coût, qui décrit s'il est aisé ou non de passer du pixel actuel au pixel visé. On pourra ainsi associer à chaque pixel de l'image un sommet, et à chaque lien entre ce pixel et ses voisins une arête.

Et de façon similaire, on pourrait créer une grille représentant un terrain virtuel. Le coût de déplacement pourrait être représentatif de l'altitude à grimper, ou du type d'obstacles à franchir.

Implémentation C

Il existe donc beaucoup d'implémentations de cet algorithme dans pas mal de langages de programmation différents. Néanmoins, je n'ai pas réellement trouvé d'algorithme écrit en C pur qui implémentent Dijkstra avec une complexité en dessous de O(N²). En voici donc une version, écrite pour appliquer l'algorithme sur des images, pour le moment restreint à deux dimensions. Il serait très facile de le modifier pour ajouter une 3ème dimension!

Astuces pour réduire le temps d'exécution

Exécuter Dijkstra prend du temps pour deux choses:

1. Il faut créer un graphe à partir des données (l'image par exemple), en temps O(N) où N est le nombre de sommets
2. Il faut calculer le chemin le plus court pour arriver du point de départ au point de destination, en temps O(|E+N| log(N)) où E est le nombre d'arêtes.

Dans le cas d'images, augmenter chaque cote d'un facteur deux revient à multiplier par 4 le nombre de sommets. Autant la création du réseau que l'algorithme vont nécessiter du temps de calcul !

La proposition est alors la suivante : redimensionner le graphe (= l'image) pour y calculer un plus court chemin. Ensuite, définir une zone de travail autour de ce chemin, et recalculer le chemin le plus court sur l'image pleine résolution. Attention: la garantie d'obtenir le plus court chemin est perdue. Par contre, cela permet d'obtenir rapidement un "suffisamment" bon chemin.

Indication du temps de calcul en fonction de la taille de l'image (cf légende). Utiliser la multi-résolution permet de gagner beaucoup de temps sur les grosses images, ainsi que de l'occupation mémoire.

Applications

Aperçu interactif de l'algorithme

Peut-être visualisé dans un navigateur à jour ici : Dijkstra pas à pas Chaque click fait avancer l'algorithme d'un pas.

Labyrinthes

Il est possible de résoudre des labyrinthes:

Il a fallu moins de 2 secondes pour charger les images et retrouver le chemin sur l'image complète (clickez l'image)

Suivi de vaisseaux sanguins

Récupérer le code

Tout est disponible sur bitbucket.

Code C pur

Il faut regarder le dossier tests/ et s'en inspirer pour utiliser Dijkstra. Pour le moment, aucune interface robuste ou programme user-friendly n'a été préparé pour l'utiliser.

Module C pour Python

Une fois compilé avec la méthode standard, le module ne comporte que 3-4 fonctions très simples à utiliser. On se référera au fichier de test disponible dans le dossier du module.