Wie lässt sich ein Labyrinth bei einem bestimmten Bild am besten darstellen und lösen?

Wie lässt sich ein JPEG-Bild (wie oben dargestellt) am besten einlesen, in eine Datenstruktur zerlegen und das Labyrinth lösen? Mein erster Instinkt ist, das Bild pixelweise zu lesen und in einer Liste (Array) von Booleschen Werten zu speichern:True für ein weißes Pixel undFalse für ein nichtweißes Pixel (die Farben können verworfen werden). Das Problem bei dieser Methode ist, dass das Bild möglicherweise nicht "pixelgenau" ist. Damit meine ich einfach, dass, wenn sich irgendwo an einer Wand ein weißes Pixel befindet, ein unbeabsichtigter Pfad entstehen kann.

Eine andere Methode (die mir nach einigem Überlegen einfiel) besteht darin, das Bild in eine SVG-Datei zu konvertieren. Dabei handelt es sich um eine Liste von Pfaden, die auf einer Zeichenfläche gezeichnet sind. Auf diese Weise könnten die Pfade in dieselbe Art von Liste (boolesche Werte) gelesen werden, in derTrue zeigt einen Pfad oder eine Wand an,False Angabe eines fahrbaren Raumes. Ein Problem bei dieser Methode tritt auf, wenn die Konvertierung nicht 100% genau ist und nicht alle Wände vollständig miteinander verbunden sind, wodurch Lücken entstehen.

Ein weiteres Problem bei der Konvertierung in SVG ist, dass die Linien nicht "perfekt" gerade sind. Dies führt dazu, dass die Pfade kubische Bezierkurven sind. Bei einer Liste (Array) von Booleschen Werten, die durch Ganzzahlen indiziert sind, lassen sich die Kurven nicht leicht übertragen, und alle Punkte auf der Kurve müssten berechnet werden, stimmen jedoch nicht genau mit den Listenindizes überein.

Ich gehe davon aus, dass eine dieser Methoden zwar funktioniert (wenn auch wahrscheinlich nicht), dass sie bei einem so großen Bild jedoch absolut ineffizient sind und dass es einen besseren Weg gibt. Wie wird das am besten (am effizientesten und / oder am wenigsten kompliziert) gemacht? Gibt es überhaupt einen besten Weg?

Dann kommt das Auflösen des Labyrinths. Wenn ich eine der ersten beiden Methoden verwende, erhalte ich im Wesentlichen eine Matrix. Gemäßdiese AntwortEin guter Weg, um ein Labyrinth darzustellen, ist die Verwendung eines Baumes, und ein guter Weg, um es zu lösen, ist die Verwendung desEin * Algorithmus. Wie würde man einen Baum aus dem Bild erstellen? Irgendwelche Ideen?

TL; DR
Der beste Weg, um zu analysieren? In welche Datenstruktur? Wie würde die Struktur beim Lösen helfen / behindern?

AKTUALISIEREN
Ich habe versucht, das, was @Mikhail in Python geschrieben hat, mithilfe von zu implementierennumpy, als @Thomas empfohlen. Ich bin der Meinung, dass der Algorithmus korrekt ist, aber nicht wie erhofft funktioniert. (Code unten.) Die PNG-Bibliothek istPyPNG.

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. """
  frontier = Queue.Queue()
  while s != e:
    for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
      np = tuple(map(operator.add, s, d))
      if is_white(np, i) and 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 # ensure the file is RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])