Représenter et résoudre un labyrinthe à partir d’une image

| | | | | | | | | | | | | | | | | | | | | | | | |

Quelle est la meilleure façon de représenter et de résoudre un labyrinthe à partir d'une image ?

Le cover image of The Scope Issue 134

Étant donné une image JPEG (comme vu ci-dessus), quelle est la meilleure façon de la lire, de l'analyser dans une structure de données et de résoudre le labyrinthe ? Mon premier l'instinct est de lire l'image pixel par pixel et de la stocker dans une liste (tableau) de valeurs booléennes : True pour un pixel blanc, et False pour un non blanc pixel (les couleurs peuvent être ignorées). Le problème avec cette méthode, c'est que l'image peut ne pas être "pixel parfaite". Par là, je veux simplement dire que s'il y a un pixel blanc quelque part sur un mur, cela peut créer un chemin involontaire.

Une autre méthode (qui m'est venue après un peu de réflexion) consiste à convertir l'image en un fichier SVG - qui est une liste de chemins tracés sur un canevas. De cette façon, les chemins pourraient être lus dans le même type de liste (valeurs booléennes) où True indique un chemin ou un mur, False indiquant un espace voyageable. Un problème avec cette méthode survient si la conversion n'est pas précise à 100 % et ne relie pas complètement tous les murs, créant des espaces.

Un autre problème avec la conversion en SVG est que les lignes ne sont pas "parfaitement " droit. Il en résulte que les chemins sont des courbes de Bézier cubiques. Avec une liste (tableau) de valeurs booléennes indexées par des nombres entiers, les courbes ne seraient pas transférées facilement et tous les points de cette ligne sur la courbe devraient être calculés, mais ne correspondraient pas exactement aux indices de la liste.

Je suppose que même si l'une de ces méthodes peut fonctionner (mais probablement pas), elles sont terriblement inefficaces compte tenu d'une image aussi grande et qu'il existe un meilleur moyen. Comment est-ce le meilleur (le plus efficace et / ou avec le moins de complexité ) terminé ? Y a-t-il même une meilleure façon ?

Vient ensuite la résolution du labyrinthe. Si j'utilise l'une des deux premières méthodes, je vais essentiellement me retrouver avec une matrice. Selon cette réponse, une bonne façon de représenter un labyrinthe est d'utiliser un arbre, et une bonne façon de le résoudre est d'utiliser le Algorithme A*. Comment créer un arbre à partir de l'image ? Des idées ?

TL;DR
La meilleure façon d'analyser ? Dans quel da ta structure? Comment ladite structure aiderait/entraverait-elle la résolution ?

MISE À JOUR
J'ai essayé d'implémenter ce que @Mikhail a écrit en Python, en utilisant numpy, comme l'a recommandé @Thomas. Je pense que l'algorithme est correct, mais il ne fonctionne pas comme espéré. (Code ci-dessous.) La bibliothèque PNG est PyPNG.

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Retourne si (x, y) est approximativement un pixel blanc.""" a = Vrai pour i in xrange(3): si pas a: break a = image[coord[1]][coord[0] * 3 + i] > 240 return a def bfs(s, e, i, started): """ Effectue une recherche en largeur d'abord. """ frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)] : np = tuple(map(operator.add, s, d)) si is_white(np, i) et np not in visited : frontier.put(np) visited.append(s) s = frontier.get() return visited def main(): r = png.Reader(filename = "thescope-134.png") rows, cols, pixels, meta = r.asDirect() assert meta["planes"] == 3 # assurez-vous que le fichier est RVB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) start, end = (402, 985), (398 , 27) print bfs(début, fin, image2d, [])