Representar y resolver un laberinto dado una imagen

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

Dada una imagen JPEG (como se ve arriba), ¿cuál es la mejor manera de leerla, analizarla en alguna estructura de datos y resolver el laberinto? Mi primer instinto es leer la imagen en píxeles por píxel y almacenarla en una lista (matriz) de valores booleanos: Truepara un píxel blanco y Falsepara un píxel no blanco (los colores se pueden descartar). El problema con este método es que la imagen puede no ser "perfecta de píxeles". Con eso simplemente quiero decir que si hay un píxel blanco en algún lugar de una 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 forma, las rutas podrían leerse en el mismo tipo de lista (valores booleanos) donde Trueindica una ruta o muro, lo que Falseindica un espacio que puede viajar. Un problema con este método surge si la conversión no es 100% precisa y no conecta completamente todas las paredes, creando espacios.

También un problema con la conversión a SVG es que las líneas no son "perfectamente" rectas. Esto hace que los caminos sean curvas cúbicas de Bezier. Con una lista (matriz) de valores booleanos indexados por enteros, las curvas no se transferirían fácilmente, y todos los puntos que se alinean en la curva 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) que son lamentablemente ineficientes dada una imagen tan grande, y que existe una mejor manera. ¿Cómo se hace esto mejor (más eficientemente y / o con la menor complejidad)? ¿Hay incluso una mejor manera?

Luego viene la resolución del laberinto. Si uso cualquiera de los dos primeros métodos, esencialmente terminaré con una matriz. Según esta respuesta , una buena manera de representar un laberinto es usar un árbol, y una buena manera de resolverlo es usar el algoritmo A * . ¿Cómo se podría crear 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 / obstaculizaría dicha estructura a la resolución?

ACTUALIZACIÓN
He intentado implementar lo que @Mikhail ha escrito en Python, utilizando numpy, como recomendó @Thomas. Siento que el algoritmo es correcto, pero no funciona como se esperaba. (Código a continuación). La biblioteca PNG es 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, [])

Aquí hay una solución.

1. Convierta la imagen a escala de grises (aún no binaria), ajustando los pesos de los colores para que la imagen final en escala de grises sea aproximadamente uniforme. Puede hacerlo simplemente controlando los controles deslizantes en Photoshop en Imagen -> Ajustes -> Blanco y negro.
2. Convierta la imagen a binario estableciendo el umbral apropiado en Photoshop en Imagen -> Ajustes -> Umbral.
3. Asegúrese de que el umbral esté seleccionado correctamente. Utilice la herramienta Varita mágica con tolerancia 0, muestra puntual, contigua, sin suavizado. Compruebe que los bordes en los que los saltos de selección no son bordes falsos introducidos por un umbral incorrecto. De hecho, todos los puntos interiores de este laberinto son accesibles desde el principio.
4. Agregue bordes artificiales en el laberinto para asegurarse de que el viajero virtual no caminará por él :)
5. Implemente la búsqueda de amplitud primero (BFS) en su idioma favorito y ejecútelo desde el principio. Prefiero MATLAB para esta tarea. Como @Thomas ya mencionó, no hay necesidad de meterse con la representación regular de gráficos. Puede trabajar con imágenes binarizadas directamente.

Aquí está el código MATLAB para BFS:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

Es realmente muy simple y estándar, no debería haber dificultades para implementar esto en Python o lo que sea.

Y aquí está la respuesta:

Esta solución está escrita en Python. Gracias Mikhail por los consejos sobre la preparación de la imagen.

Una búsqueda animada de Breadth First:

El laberinto completado:

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):

    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list

    while not queue.empty():

        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

Nota: Marca un píxel blanco visitado como gris. Esto elimina la necesidad de una lista visitada, pero esto requiere una segunda carga del archivo de imagen del disco antes de dibujar una ruta (si no desea una imagen compuesta de la ruta final y TODAS las rutas tomadas).

Una versión en blanco del laberinto que utilicé.

Intenté implementar la búsqueda de A-Star para este problema. Seguimos de cerca la implementación de Joseph Kern para el marco y el pseudocódigo del algoritmo que se proporciona aquí :

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

Como A-Star es un algoritmo de búsqueda heurístico, debe crear una función que calcule el costo restante (aquí: distancia) hasta alcanzar el objetivo. A menos que se sienta cómodo con una solución subóptima, no debe sobreestimar el costo. Una opción conservadora sería aquí la distancia de Manhattan (o taxi), ya que representa la distancia en línea recta entre dos puntos en la cuadrícula para el vecindario Von Neumann utilizado. (Lo cual, en este caso, nunca sobreestimaría el costo).

Sin embargo, esto subestimaría significativamente el costo real del laberinto en cuestión. Por lo tanto, he agregado otras dos métricas de distancia al cuadrado euclidiana y la distancia de Manhattan multiplicada por cuatro para comparar. Sin embargo, estos podrían sobreestimar el costo real y, por lo tanto, podrían arrojar resultados subóptimos.

Aquí está el código:

import sys
from PIL import Image

def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

start = (400, 984)
goal = (398, 25)

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]

path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # red

path_img.save(sys.argv[2])

Aquí hay algunas imágenes para una visualización de los resultados (inspiradas en la publicada por Joseph Kern ). Las animaciones muestran un nuevo cuadro cada 10000 iteraciones del ciclo while principal.

Breadth-First Search:

A-Star Manhattan Distancia:

Distancia Euclidiana Cuadrada A-Star:

A-Star Manhattan Distance multiplicada por cuatro:

Los resultados muestran que las regiones exploradas del laberinto difieren considerablemente para la heurística utilizada. Como tal, la distancia euclidiana al cuadrado incluso produce una ruta diferente (subóptima) como las otras métricas.

Con respecto al rendimiento del algoritmo A-Star en términos del tiempo de ejecución hasta la finalización, tenga en cuenta que se suman muchas evaluaciones de las funciones de distancia y costo en comparación con la Búsqueda de Breadth-First (BFS) que solo necesita evaluar el "objetivo" de cada puesto candidato Si el costo de estas evaluaciones de funciones adicionales (A-Star) supera o no el costo del mayor número de nodos para verificar (BFS) y especialmente si el rendimiento es un problema para su aplicación, es una cuestión de percepción individual y, por supuesto, no se puede responder en general.

Lo que se puede decir en general acerca de si un algoritmo de búsqueda informado (como A-Star) podría ser la mejor opción en comparación con una búsqueda exhaustiva (por ejemplo, BFS) es lo siguiente. Con el número de dimensiones del laberinto, es decir, el factor de ramificación del árbol de búsqueda, la desventaja de una búsqueda exhaustiva (para buscar exhaustivamente) crece exponencialmente. Con la creciente complejidad, cada vez es menos factible hacerlo y, en algún momento, está bastante contento con cualquier camino de resultados, sea (aproximadamente) óptimo o no.

La búsqueda de árboles es demasiado. El laberinto es inherentemente separable a lo largo de la (s) ruta (s) de solución.

(Gracias a rainman002 de Reddit por señalarme esto).

Debido a esto, puede usar rápidamente componentes conectados para identificar las secciones conectadas de la pared del laberinto. Esto itera sobre los píxeles dos veces.

Si desea convertir eso en un buen diagrama de la (s) ruta (s) de solución, puede usar operaciones binarias con elementos estructurantes para completar las rutas de "callejón sin salida" para cada región conectada.

Sigue el código de demostración para MATLAB. Podría usar ajustes para limpiar mejor el resultado, hacerlo más generalizable y hacerlo correr más rápido. (En algún momento cuando no son las 2:30 a.m.)

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

Utiliza una cola para un umbral de llenado continuo. Empuja el píxel a la izquierda de la entrada en la cola y luego inicia el bucle. Si un píxel en cola es lo suficientemente oscuro, es de color gris claro (por encima del umbral), y todos los vecinos son empujados a la cola.

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

La solución es el corredor entre la pared gris y la pared de color. Tenga en cuenta que este laberinto tiene múltiples soluciones. Además, esto simplemente parece funcionar.

Aquí tienes: maze-solver-python (GitHub)

Me divertí jugando con esto y me extendí a Joseph Kern la respuesta de . Para no restarle valor; Acabo de hacer algunas adiciones menores para cualquier otra persona que pueda estar interesada en jugar con esto.

Es un solucionador basado en Python que usa BFS para encontrar la ruta más corta. Mis principales adiciones, en ese momento, son:

1. La imagen se limpia antes de la búsqueda (es decir, convertir a blanco y negro puro)
2. Generar automáticamente un GIF.
3. Generar automáticamente un AVI.

Tal como está, los puntos de inicio / finalización están codificados para este laberinto de muestra, pero planeo extenderlo de manera que pueda elegir los píxeles apropiados.

Yo elegiría la opción de matriz de bools. Si encuentra que las listas estándar de Python son demasiado ineficientes para esto, podría usar unnumpy.bool matriz en su lugar. El almacenamiento para un laberinto de 1000x1000 píxeles es de solo 1 MB.

No se moleste en crear estructuras de datos de árbol o gráfico. Esa es solo una forma de pensarlo, pero no necesariamente una buena forma de representarlo en la memoria; una matriz booleana es más fácil de codificar y más eficiente.

Luego usa el algoritmo A * para resolverlo. Para la heurística de distancia, use la distancia de Manhattan ( distance_x + distance_y).

Representar nodos por una tupla de (row, column)coordenadas. Siempre que el algoritmo ( pseudocódigo de Wikipedia ) llame a "vecinos", es una simple cuestión de recorrer los cuatro vecinos posibles (¡cuidado con los bordes de la imagen!).

Si encuentra que todavía es demasiado lento, puede intentar reducir la escala de la imagen antes de cargarla. Tenga cuidado de no perder caminos estrechos en el proceso.

Tal vez también sea posible hacer una reducción de escala 1: 2 en Python, verificando que en realidad no pierda ninguna ruta posible. Una opción interesante, pero necesita un poco más de reflexión.

Aquí hay algunas ideas.

(1. Procesamiento de imagen :)

1.1 Cargue la imagen como mapa de píxeles RGB . En C # es trivial usando system.drawing.bitmap. En idiomas sin soporte simple para imágenes, simplemente convierta la imagen a formato de mapa de píxeles portátil (PPM) (una representación de texto Unix, produce archivos grandes) o algún formato de archivo binario simple que pueda leer fácilmente, como BMP o TGA . ImageMagick en Unix o IrfanView en Windows.

1.2 Puede, como se mencionó anteriormente, simplificar los datos al tomar (R + G + B) / 3 para cada píxel como un indicador de tono gris y luego limitar el valor para producir una tabla en blanco y negro. Algo cercano a 200 suponiendo que 0 = negro y 255 = blanco eliminará los artefactos JPEG.

(2. Soluciones :)

2.1 Búsqueda de profundidad primero: inicie una pila vacía con la ubicación inicial, recopile los movimientos de seguimiento disponibles, elija uno al azar y empuje hacia la pila, continúe hasta llegar al final o un punto muerto. En el backdend muerto haciendo estallar la pila, debe realizar un seguimiento de las posiciones que se visitaron en el mapa, de modo que cuando reúne los movimientos disponibles, nunca toma el mismo camino dos veces. Muy interesante para animar.

2.2 Breadth-First Search: mencionado anteriormente, similar al anterior pero solo usando colas. También interesante para animar. Esto funciona como un software de edición de imágenes de relleno de inundación. Creo que puedes resolver un laberinto en Photoshop usando este truco.

2.3 Seguidor de pared: Geométricamente hablando, un laberinto es un tubo doblado / contorneado. Si mantienes tu mano en la pared, eventualmente encontrarás la salida;) Esto no siempre funciona. Hay ciertos supuestos re: laberintos perfectos, etc., por ejemplo, ciertos laberintos contienen islas. Búscalo; Es fascinante.

(3. Comentarios :)

Este es el complicado. Es fácil resolver laberintos si se representa en una matriz simple formal con cada elemento como un tipo de celda con paredes norte, este, sur y oeste y un campo de bandera visitado. Sin embargo, dado que está intentando hacer esto dado un boceto dibujado a mano, se vuelve desordenado. Sinceramente, creo que intentar racionalizar el boceto te volverá loco. Esto es similar a los problemas de visión por computadora que están bastante involucrados. Quizás ir directamente al mapa de la imagen puede ser más fácil pero más derrochador.

Aquí hay una solución usando R.

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://i.stack.imgur.com/TqKCM.jpg"
download.file(url, "./maze.jpg", mode = "wb")
jpg <- readJPEG("./maze.jpg")

### reshape array into data.frame
library(reshape2)
img3 <- melt(jpg, varnames = c("y","x","rgb"))
img3$rgb <- as.character(factor(img3$rgb, levels = c(1,2,3), labels=c("r","g","b")))

## split out rgb values into separate columns
img3 <- dcast(img3, x + y ~ rgb)

RGB a escala de grises, consulte: https://stackoverflow.com/a/27491947/2371031

# convert rgb to greyscale (0, 1)
img3$v <- img3$r*.21 + img3$g*.72 + img3$b*.07
# v: values closer to 1 are white, closer to 0 are black

## strategically fill in some border pixels so the solver doesn't "go around":
img3$v2 <- img3$v
img3[(img3$x == 300 | img3$x == 500) & (img3$y %in% c(0:23,988:1002)),"v2"]  = 0

# define some start/end point coordinates
pts_df <- data.frame(x = c(398, 399),
                     y = c(985, 26))

# set a reference value as the mean of the start and end point greyscale "v"s
ref_val <- mean(c(subset(img3, x==pts_df[1,1] & y==pts_df[1,2])$v,
                  subset(img3, x==pts_df[2,1] & y==pts_df[2,2])$v))

library(sp)
library(gdistance)
spdf3 <- SpatialPixelsDataFrame(points = img3[c("x","y")], data = img3["v2"])
r3 <- rasterFromXYZ(spdf3)

# transition layer defines a "conductance" function between any two points, and the number of connections (4 = Manhatten distances)
# x in the function represents the greyscale values ("v2") of two adjacent points (pixels), i.e., = (x1$v2, x2$v2)
# make function(x) encourages transitions between cells with small changes in greyscale compared to the reference values, such that: 
# when v2 is closer to 0 (black) = poor conductance
# when v2 is closer to 1 (white) = good conductance
tl3 <- transition(r3, function(x) (1/max( abs( (x/ref_val)-1 ) )^2)-1, 4) 

## get the shortest path between start, end points
sPath3 <- shortestPath(tl3, as.numeric(pts_df[1,]), as.numeric(pts_df[2,]), output = "SpatialLines")

## fortify for ggplot
sldf3 <- fortify(SpatialLinesDataFrame(sPath3, data = data.frame(ID = 1)))

# plot the image greyscale with start/end points (red) and shortest path (green)
ggplot(img3) +
  geom_raster(aes(x, y, fill=v2)) +
  scale_fill_continuous(high="white", low="black") +
  scale_y_reverse() +
  geom_point(data=pts_df, aes(x, y), color="red") +
  geom_path(data=sldf3, aes(x=long, y=lat), color="green")

Voila!

Esto es lo que sucede si no rellenas algunos píxeles de borde (¡Ja!) ...

Revelación completa: pregunté y respondí una pregunta muy similar antes de encontrar esta. Luego, a través de la magia de SO, encontré esta como una de las principales "Preguntas relacionadas". Pensé que usaría este laberinto como un caso de prueba adicional ... Me complació mucho encontrar que mi respuesta allí también funciona para esta aplicación con muy poca modificación.

la buena solución sería que en lugar de encontrar a los vecinos por píxel, se haría por celda, porque un corredor puede tener 15 píxeles, por lo que en el mismo corredor puede tomar acciones como izquierda o derecha, mientras que si se hiciera como si fuera el desplazamiento era un cubo, sería una acción simple como ARRIBA, ABAJO, IZQUIERDA O DERECHA