Algorithmes de suivi de chemin de trame

Question

J'ai une grille de valeurs qui ressemble à l'image ci-dessous (le blanc représente les valeurs élevées, le fond noir représente la valeur zéro).

J'essaie d'écrire une sorte de code de suivi de chemin pour commencer à l'extrémité d'une des lignes et tracer jusqu'à l'autre extrémité, en passant par les valeurs les plus élevées possibles (c'est-à-dire que plus les pixels choisis pour être dans la ligne sont blancs, mieux c'est) mais en arrivant quand même à l'autre extrémité.

Cela fait un moment que je me débats avec ce problème, et je n'arrive pas à faire fonctionner ce que j'essaie. Je me suis donc demandé si un algorithme générique avait déjà été développé pour ce type de problème. J'ai fait beaucoup de recherches, mais la plupart des algorithmes de parcours semblent être conçus pour fonctionner sur des vecteurs/réseaux, et non sur des grilles matricielles comme celle-ci.

Des idées ?

Answer 1

L'idée la plus simple est probablement d'utiliser la fonction Algorithme A* où chaque pixel est un nœud, et le coût du nœud est l'obscurité du pixel.

Mise à jour : J'ai trouvé une belle tutoriel .

Answer 2

Une façon d'y parvenir :

1. Filtrez l'image pour qu'elle soit plus proche du noir et blanc.
2. Tracez une ligne à travers les pixels blancs. Pour ce faire, commencez par un pixel blanc. Tracez une ligne à partir de ce pixel jusqu'à chaque autre pixel blanc situé à une distance de 2 (ou 3 environ), mais ignorez les pixels situés à proximité d'une ligne précédente. Continuez ainsi jusqu'à ce que vous ayez couvert tous les pixels qui ne sont pas proches (2 ou 3 pixels) d'une ligne. Vous devrez procéder à quelques ajustements mineurs pour que cela fonctionne correctement.
3. Reliez les extrémités des lignes que vous avez tracées. Si deux extrémités sont proches (1 ou 2 pixels ?) l'une de l'autre, reliez-les. Vous devriez obtenir quelques lignes composées d'un grand nombre de segments courts, avec éventuellement quelques boucles et fourches.
4. Éliminez toutes les petites boucles dans les lignes et séparez les lignes au niveau des fourches, de manière à obtenir quelques lignes composées d'un grand nombre de segments courts.
5. Réduire les points. Pour chaque ligne, vérifiez si elle est presque droite. Si c'est le cas, supprimez tous les points intérieurs. Si ce n'est pas le cas, vérifiez les deux moitiés de la ligne de manière récurrente jusqu'à ce que vous obteniez les longueurs de segment minimales.
6. Vous pouvez éventuellement ajuster une courbe spline à travers les lignes à ce stade.
7. Bénéfice.

Il faudra quelques ajustements pour que cela fonctionne bien, mais il est possible de procéder de cette manière. Une autre variante consiste à tracer les sections blanches, si elles sont plus larges que 1, 2 ou 3 pixels, et à combiner les doubles lignes par la suite.

Answer 3

Je ne pense pas que vous ayez besoin d'un algorithme génétique ou de quoi que ce soit de ridicule ; la bonne vieille récursion et la programmation dynamique devraient suffire. Je pense d'abord que vous devriez être en mesure d'atteindre votre objectif en effectuant une recherche en largeur d'abord. A partir de votre point de départ, vous visitez tous les voisins dont les scores sont supérieurs à la valeur de ce chemin (toutes les cellules commencent à l'infini, et les coûts pour les cellules noires seraient infinis, et ce sont les chemins que vous pouvez élaguer). Une fois arrivé à destination, s'il est possible de l'atteindre, vous devriez être en mesure de revenir en arrière pour trouver le chemin. C'est gourmand, mais si vos chemins se comportent bien comme ceux-ci, tout devrait bien se passer.

Pour les chemins plus gris et plus sinueux, il peut être judicieux de convertir l'image matricielle en un graphique, le poids des arêtes correspondant aux valeurs de l'échelle de gris des voisins (ou à la différence des valeurs de l'échelle de gris, en fonction de la signification réelle de ces données). Ainsi, vous devriez être en mesure d'utiliser n'importe quel algorithme de calcul des plus courts chemins sur la base de cette interprétation.

Answer 4

Si vous le faites à grande échelle ou à des fins de recherche, vous pouvez essayer le blanc. http://en.wikipedia.org/wiki/Ant_colony_optimization Mais si vous faites cela pour de l'argent, prenez quelque chose comme le flood fill. http://en.wikipedia.org/wiki/Flood_fill