Representando e resolvendo um labirinto com uma imagem

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

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

O imagem da capa de The Scope Issue 134

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? Minha primeira instinto é ler a imagem pixel por pixel e armazená-la em uma lista (array) de valores booleanos: True para um pixel branco e False para um não-branco pixel (as cores podem ser descartadas) O problema com este método é que a imagem pode não ser "pixel perfeito". Com isso quero dizer simplesmente que se houver um pixel branco em algum lugar na parede, ele 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. Dessa forma, os caminhos podem ser lidos o mesmo tipo de lista (valores booleanos) onde True indica um caminho ou parede, False indicando um espaço transitável. Um problema com esse método surge se a conversão não for 100% precisa e não conectar totalmente todas as paredes, criando lacunas.

Também um problema com a conversão para SVG é que as linhas não são "perfeitamente " direto. Isso resulta nos caminhos sendo curvas cúbicas de bezier. Com uma lista (array) de valores booleanos indexados por 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.

Eu suponho que, embora um desses métodos possa funcionar (embora provavelmente não), eles são lamentavelmente ineficientes para uma imagem tão grande e que existe uma maneira melhor. Como isso é melhor (mais eficiente e/ou com menos complexidade ) feito? Existe mesmo uma melhor maneira?

Em seguida, vem a solução do labirinto. Se eu usar qualquer um dos dois primeiros métodos, basicamente terminarei com uma matriz. De acordo com esta resposta, uma boa maneira de representar um labirinto é usar uma árvore e uma boa maneira de resolvê-lo é usar o Algoritmo A*. Como criar uma árvore a partir da imagem? Alguma ideia?

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

ATUALIZAÇÃO
Eu tentei implementar o que @Mikhail escreveu em Python, usando numpy, como @Thomas recomendou. Sinto que o algoritmo está correto, mas não está funcionando como esperado. (Código abaixo.) A biblioteca PNG é PyPNG. p>

import png, numpy, Queue, operator, itertools def is_white(coord, image): """ Retorna se (x, y) é aproximadamente um pixel branco.""" a = True para i in xrange(3): se não for a: break a = image[coord[1]][coord[0] * 3 + i] > 240 retorna um def bfs(s, e, i, visitado): """ Realiza uma busca em largura. """ 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 visitado def main(): r = png.Reader(filename = "thescope-134.png") rows, cols, pixels, meta = r.asDirect() assert meta["planes"] == 3 # garante que o arquivo seja RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels)) start, end = (402, 985), (398) , 27) print bfs(start, end, image2d, [])