python - xticks - seaborn barplot




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

¿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í 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:

  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.

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


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.





maze