Qual é a melhor maneira de representar e resolver um labirinto dado uma imagem?

Dada uma imagem JPEG (como visto acima), qual é a melhor maneira de lê-la, analisá-la em alguma estrutura de dados e resolver o labirinto? Meu primeiro instinto é ler a imagem em pixel por pixel e armazená-la em uma lista (matriz) de valores booleanos:True para um pixel branco eFalse para um pixel não branco (as cores podem ser descartadas). O problema com este método é que a imagem pode não ser "pixel perfeita". Com isso, quero dizer simplesmente que, se houver um pixel branco em algum lugar na parede, isso pode criar um caminho não intencional.

Outro método (que veio a mim depois de pensar um pouco) é converter a imagem em um arquivo SVG - que é uma lista de caminhos desenhados em uma tela. Desta forma, os caminhos podem ser lidos no mesmo tipo de lista (valores booleanos) ondeTrue indica um caminho ou parede,False indicando um espaço de viagem. Um problema com este método surge se a conversão não é 100% precisa e não conecta totalmente todas as paredes, criando lacunas.

Também um problema com a conversão para SVG é que as linhas não são "perfeitamente" retas. Isso resulta nos caminhos sendo curvas bezier cúbicas. Com uma lista (matriz) de valores booleanos indexados por números inteiros, as curvas não seriam transferidas facilmente, e todos os pontos dessa linha na curva teriam que ser calculados, mas não corresponderiam exatamente aos índices da lista.

Suponho que, embora um desses métodos possa funcionar (embora provavelmente não), eles são extremamente ineficientes, dada uma imagem tão grande, e que existe uma maneira melhor. Como isso é melhor (mais eficientemente e / ou com a menor complexidade)? Existe mesmo o melhor caminho?

Então vem a resolução do labirinto. Se eu usar um dos dois primeiros métodos, acabarei essencialmente com uma matriz. De acordo comesta resposta, uma boa maneira de representar um labirinto é usando uma árvore, e uma boa maneira de resolvê-lo é usando oAlgoritmo A *. Como alguém criaria uma árvore a partir da imagem? Alguma ideia?

TL; DR
Melhor maneira de analisar? Em que estrutura de dados? Como essa estrutura ajudaria / dificultaria a solução?

ATUALIZAR
Eu tentei implementar o que o @ Mikhail escreveu em Python, usandonumpycomo @Thomas recomendado. Eu sinto que o algoritmo está correto, mas não está funcionando como esperado. (Código abaixo.) A biblioteca PNG éPyPNG.

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