Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Méthode du Fast marching
Bonjour,
Je suis débutante en traitement d'image, je cherche a comprendre le déroulement de la méthode du fast marching pour la construction du plus court chemin dans une image en niveau de gris. J'ai trouvé beaucoup de documentation mais c'est expliqué de manière très mathématique, et je n'arrive pas a comprendre le principe en gros. Merci de m'expliquer le principe de manière intuitive, je vous rappel que je suis débutante et je n'ai pas bcp de notions.
Cordialement
Anna
L'objectif c'est d'avoir une surface de départ qui se propage dans un domaine 2D. On pourrait voir ca comme une étendue d'eau qui se répand dans un paysage montagneux.Envoyé par anna0510
Le principe de la méthode fast marching (FMM), c'est d'effectuer cette propagation pixel par pixel en fonction du temps. Un peu comme on ferait avancer une vidéo image par image.
Pour cela, on prend la surface de départ et on modélise la courbe fermée qui représente la frontière = le bord de la surface.
Pour chaque pixel du bord, on calcule le temps qu'il faut pour que le bord atteigne le prochain pixel du domaine. Ce temps dépend deux facteurs:
- la direction de propagation = la normale a la courbe a cet endroit.
- la vitesse de propagation = une valeur qui dépend du domaine 2D a cet endroit.
Une fois qu'on a les temps de propagation "Ti" pour chaque pixel du bord, on prend le temps le plus petit "Tmin". On calcule alors la position qui sera occupée par chaque pixel du bord a ce temps Tmin. L'un des pixels aura donc atteint un nouveau pixel, et tous les autres seront a mi-chemin d'un nouveau pixel.
On peut a nouveau modéliser la courbe fermée qui représente la frontière, et on recommence l'opération.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Merci de votre réponse
Est ce que la vitesse de propagation peut être simplement la distance d'un pixel du front au pixel du front précédant ?
heu... oui. Mais ca voudrait dire qu'il n'y a aucune contrainte liée à la valeur d'intensité des pixels, ce qui est plutôt étrange.
Si on fait de la segmentation, la vitesse doit favoriser la propagation vers un pixel d'intensité similaire, et pénaliser la propagation vers un pixel d'intensité différente.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
oui biensure, mais moi je veut juste calculer le chemin le plus court entre 2 points dans une image.
Je veux construire une carte de distance entre mes 2 points avec la méthode du "fast marching", et après retrouver le chemin le plus court. Mais j'ai du mal a modéliser la vitesse et le sens de propagation.
Autant prendre l'algorithme de Dijkstra ou A-star.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Dijkstra serait plus simple j'avouemais l'exercice consiste à construire une géodésique entre 2 points d'une image avec la méthode du Fast marching. donc obligée de faire avec
Je veux construire une carte de distance entre mes 2 points avec la méthode du "fast marching", et après retrouver le chemin le plus court. Mais j'ai du mal a modéliser la vitesse et le sens de propagation.
Si j'ai bien compris, je pars d'un pixel qui est le point de départ, je parcours tout ses voisins à tour de rôle et je leur attribut une valeur qui est la distance au point départ (va leur du pixel voisin + valeur du pixel de départ + distance) mais je ne sais pas comment introduire le sens et la vitesse.
Merci de votre aide
J'attend toujours votre réponse. Merci
Il s'agit de créer une carte des distances (distance map). C'est à dire un tableau de la taille de l'image où chaque case contient la distance parcourue depuis le point de départ.
Le point de départ "P(0)" est à une distance de 0.
On calcule alors les distances des points P(1,i) qui sont sur le front, c'est à dire les 8 points autour de "P(0)":
- Les points au nord/sud/est/ouest de "P(0)" sont à une distance de 1.
- Les points au nord-ouest/ne/so/se de "P(0)" sont à une distance de 1.41
On recommence à calculer les distances des points P(2,j) qui sont sur le nouveau front. Pour cela, on rapplique la même technique:
- Un point au nord/sud/est/ouest de "P(1,i)" est à une distance de P(1,i)+1
- Un point au nord-ouest/ne/so/se de "P(1,i)" est à une distance de P(1,i)+1.41
Si on tombe sur une case déjà remplie, on conserve la distance la plus petite.
etc.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Je vous remercie
Merci beaucoup
Mai ce que je n'arrive pas a comprendre, c'est le sens de propagation? là on va parcourir à chaque itération tout le voisinage et garder la plus petite valeur, c'est à dire qu'on a un retour vers les pixels déjà définit, donc on a pas un sens unique de propagation ??
Deuxième chose c'est la vitesse, a quoi celle ci correspond dans l'algorithme que vous m'avez indiqué?
En vous remerciant infiniment, je suis bloquée depuis plusieurs jours et votre aide m'est absolument bénéfique.
Anna
Effectivement, dans le fast-marching la direction de propagation est la normale à la courbe du front. Pour chaque point P(1,i), on devrait donc estimer cette direction et calculer précisément où se situent les points P(2,j).
Mais comme j'ai supposé une vitesse de propagation constante, je peux calculer le temps de passage de tous les points qui sont dans un voisinage 3x3. Ce qui revient a calculer une carte des distances par dilatation.
Si c'est pour calculer le chemin le plus court entre deux points, sans contraintes de vitesse, c'est tout aussi efficace.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
ok, c'est a dire en gros pas besoin du fast marching pour le calcule de géodésique entre 2 points. Je veux dire la puissance du fast marching ne peut être totalement exploitée dans ce cas.
De mon point de vue, si les vitesses de propagation sont constantes cette méthode perd grandement de son intérêt. Et s'il n'y a aucune contrainte sur la forme de la ligne du front (élasticité/rigidité), ca perd même totalement son intérêt.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Merci infiniment
Je vous remercie beaucoup, vous m'avez énormément aidé
Au plaisir
Anna
Répondre avec citation
Partager