¿Cuál es la mejor manera de representar y resolver un laberinto con una imagen?

Dada una imagen JPEG (como se ve arriba), ¿cuál es la mejor forma de leerla, analizarla en alguna estructura de datos y resolver el laberinto? Mi primer instinto es leer la imagen píxel por píxel y almacenarla en una lista (matriz) de valores booleanos:True por un pixel blanco, yFalse para un píxel no blanco (los colores se pueden descartar). El problema con este método, es que la imagen puede no ser "píxel perfecto". Con eso quiero decir simplemente que si hay un píxel blanco en algún lugar de la pared, puede crear un camino no deseado.

Otro método (que se me ocurrió después de pensarlo un poco) es convertir la imagen en un archivo SVG, que es una lista de rutas dibujadas en un lienzo. De esta manera, las rutas podrían leerse en el mismo tipo de lista (valores booleanos) dondeTrue indica un camino o muro,False que indica un espacio capaz de viajar. Un problema con este método surge si la conversión no es 100% precisa y no conecta completamente todas las paredes, creando brechas.

También un problema con la conversión a SVG es que las líneas no son "perfectamente" rectas. Esto hace que las trayectorias sean curvas bezier cúbicas. Con una lista (matriz) de valores booleanos indexados por enteros, las curvas no se transferirían fácilmente, y todos los puntos de esa línea tendrían que calcularse, pero no coincidirán exactamente con los índices de la lista.

Supongo que si bien uno de estos métodos puede funcionar (aunque probablemente no), son muy ineficientes dada una imagen tan grande, y que existe una mejor manera. ¿Cómo se hace esto mejor (de la manera más eficiente y / o con la menor complejidad)? ¿Hay incluso una mejor manera?

Luego viene la resolución del laberinto. Si utilizo alguno de los dos primeros métodos, esencialmente terminaré con una matriz. De acuerdo aesta respuesta, una buena manera de representar un laberinto es usar un árbol, y una buena manera de resolverlo es usar el árbolAlgoritmo A *. ¿Cómo se crearía un árbol a partir de la imagen? ¿Algunas ideas?

TL; DR
¿La mejor manera de analizar? ¿En qué estructura de datos? ¿Cómo ayudaría / dificultaría la resolución dicha estructura?

ACTUALIZAR
He probado mi mano en implementar lo que @Mikhail ha escrito en Python, usandonumpy, como recomienda @Thomas. Siento que el algoritmo es correcto, pero no funciona como se esperaba. (Código abajo.) La biblioteca PNG esPyPNG.

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, [])