python - barplot - pandas plot

Representando y resolviendo un laberinto dada una imagen. (9)

¿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 para un píxel blanco y False 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) donde True indica una ruta o muro, False 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 con 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 crearía un árbol a partir de la imagen? ¿Algunas ideas?

TL; DR
¿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, usando numpy , como lo recomendó @Thomas. Siento que el algoritmo es correcto, pero no funciona como se esperaba. (Código abajo.) 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 algunas ideas.

(1. Procesamiento de imágenes :)

1.1 Cargar la imagen como mapa de píxeles RGB . En C# es trivial utilizando 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 Como se mencionó anteriormente, puede simplificar los datos tomando (R + G + B) / 3 para cada píxel como un indicador de tono gris y luego umbralizar 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 en profundidad: inicie una pila vacía con la ubicación inicial, recopile los movimientos de seguimiento disponibles, elija una al azar y empújela en la pila, continúe hasta que se alcance el final o un callejón sin salida. En el backtrack sin salida al abrir la pila, debes hacer un seguimiento de las posiciones que se visitaron en el mapa para que cuando recojas los movimientos disponibles nunca tomes el mismo camino dos veces. Muy interesante para animar.

2.2 Búsqueda de amplitud: mencionada anteriormente, similar a la anterior pero solo con colas. También interesante para animar. Esto funciona como relleno de software de edición de imágenes. 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 / enrevesado. Si mantiene la mano en la pared, finalmente encontrará la salida;) Esto no siempre funciona. Hay ciertas suposiciones con respecto a: laberintos perfectos, etc., por ejemplo, ciertos laberintos contienen islas. Buscarlo Es fascinante.

(3. Comentarios :)

Este es el complicado. Es fácil resolver los laberintos si se representan en una simple matriz formal, cada elemento es un tipo de celda con las 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 problemas de visión de computadora que están bastante involucrados. Tal vez ir directamente al mapa de la imagen puede ser más fácil y más desperdicio.

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://.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 (¡Ha!) ...

Revelación completa: yo mismo hice y contesté una pregunta muy similar antes de encontrar esta. Luego, a través de la magia de SO, encontré a 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.

Aquí hay una solución.

Convierta la imagen a escala de grises (que aún no sea binaria), ajustando los pesos de los colores para que la imagen de escala de grises final sea aproximadamente uniforme. Puede hacerlo simplemente controlando los controles deslizantes en Photoshop en Imagen -> Ajustes -> Blanco y negro.
Convierta la imagen a binario configurando el umbral apropiado en Photoshop en Imagen -> Ajustes -> Umbral.
Asegúrese de que el umbral está seleccionado a la derecha. Utilice la herramienta Varita mágica con tolerancia 0, muestra de puntos, contigua, sin suavizado. Compruebe que los bordes en los que los saltos de selección no sean bordes falsos introducidos por un umbral incorrecto. De hecho, todos los puntos interiores de este laberinto son accesibles desde el principio.
Agrega bordes artificiales en el laberinto para asegurarte de que el viajero virtual no camine alrededor de él :)
Implemente la búsqueda en primer lugar (BFS) en su idioma favorito y ejecútela desde el principio. Prefiero MATLAB para esta tarea. Como @Thomas ya mencionó, no es necesario meterse con la representación regular de gráficos. Puedes trabajar directamente con imagen binarizada.

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:

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

Me divertí jugando con esto y extendí la respuesta de Joseph Kern . 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 incorporaciones, en su momento, son:

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

En su estado actual, los puntos de inicio / fin están codificados para este laberinto de muestra, pero planeo extenderlo de tal manera que pueda elegir los píxeles apropiados.

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

Una búsqueda de amplitud animada:

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. 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é.

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

No te molestes en crear estructuras de datos de árboles o gráficos. Esa es solo una forma de pensar en ello, pero no necesariamente una buena manera 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 ).

Representa los nodos mediante una tupla de coordenadas (row, column) . Siempre que el algoritmo ( pseudocódigo de Wikipedia ) pida "vecinos", es simplemente una cuestión de bucle sobre los cuatro vecinos posibles (¡cuidado con los bordes de la imagen!).

Si descubre que aún es demasiado lento, puede intentar reducir la escala de la imagen antes de cargarla. Tenga cuidado de no perder ningún camino estrecho en el proceso.

Tal vez también sea posible realizar una reducción de escala 1: 2 en Python, verificando que no se pierda ningún camino posible. Una opción interesante, pero necesita un poco más de reflexión.

La búsqueda de árboles es demasiado El laberinto es intrínsecamente separable a lo largo de las rutas de la solución.

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

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

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

Código de demostración para MATLAB sigue. 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 AM).

% 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);

Traté de implementar la búsqueda A-Star para este problema. Siguió de cerca la implementación de Joseph Kern para el marco y el algoritmo de pseudocódigo here :

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ística, debe crear una función que estime el costo restante (aquí: distancia) hasta que se alcance 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 de Von Neumann usado. (Lo que, 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 de distancia euclidiana y la distancia de Manhattan multiplicada por cuatro para comparar. Sin embargo, estos pueden sobreestimar el costo real y, por lo tanto, pueden producir 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 (inspirada por la publicada por Joseph Kern ). Las animaciones muestran un nuevo cuadro después de 10000 iteraciones del bucle while principal.

Búsqueda de amplitud:

A-Star Manhattan Distancia:

Distancia euclidiana cuadrada A-Star:

A-Star Manhattan Distancia multiplicada por cuatro:

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

En lo que respecta al rendimiento del algoritmo A-Star en términos de tiempo de ejecución hasta la terminación, tenga en cuenta que muchas funciones de evaluación de distancia y costo se suman en comparación con la Búsqueda por Ancho (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 de la mayor cantidad de nodos a 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 puede ser contestada generalmente.

Una cosa 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 de manera exhaustiva) crece exponencialmente. Con la creciente complejidad, cada vez es menos factible hacerlo y, en algún momento, está bastante satisfecho con cualquier ruta de resultados, ya sea (aproximadamente) óptima o no.

Utiliza una cola para un umbral de relleno continuo. Empuja el píxel a la izquierda de la entrada a la cola y luego comienza el ciclo. Si un píxel en la cola es lo suficientemente oscuro, es de color gris claro (por encima del umbral), y todos los vecinos se colocan en 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.