python seaborn - Representando y resolviendo un laberinto dada una imagen.




barplot matplotlib (9)

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.

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


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


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.


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


Aquí hay una solución.

  1. 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.
  2. Convierta la imagen a binario configurando el umbral apropiado en Photoshop en Imagen -> Ajustes -> Umbral.
  3. 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.
  4. Agrega bordes artificiales en el laberinto para asegurarte de que el viajero virtual no camine alrededor de él :)
  5. 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í 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.


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.


Resulta que esto es sencillo:

from sqlalchemy.dialects import postgresql
from sqlalchemy.schema import CreateTable
from sqlalchemy import Table, Column, String, MetaData

metadata = MetaData()

users = Table('users', metadata,
              Column('username', String)
)

statement = CreateTable(users)

print(statement.compile(dialect=postgresql.dialect()))

Salidas esto:

CREATE TABLE users (
    username VARCHAR
)

Yendo más lejos, incluso puede soportar parámetros vinculados en declaraciones preparadas.

Referencia

¿Cómo renderizo expresiones SQL como cadenas, posiblemente con parámetros enlazados en línea?

...

o sin un motor:

from sqlalchemy.dialects import postgresql
print(statement.compile(dialect=postgresql.dialect()))

FUENTE: http://docs.sqlalchemy.org/en/latest/faq/sqlexpressions.html#faq-sql-expression-string

Ejemplo: Usar SQL Alchemy para generar un script de cambio de nombre de usuario

#!/usr/bin/env python
import csv
from sqlalchemy.dialects import postgresql
from sqlalchemy import bindparam, Table, Column, String, MetaData

metadata = MetaData()

users = Table('users', metadata,
              Column('username', String)
)

renames = []

with open('users.csv') as csvfile:
    for row in csv.DictReader(csvfile):
        renames.append({
            'from': row['sAMAccountName'],
            'to': row['mail']
        })

for rename in renames:
    stmt = (users.update()
            .where(users.c.username == rename['from'])
            .values(username=rename['to']))
    print(str(stmt.compile(dialect=postgresql.dialect(),
                           compile_kwargs={"literal_binds": True})) + ';')

Al procesar este users.csv:

sAMAccountName,mail
bmcboatface,[email protected]
ndhyani,[email protected]

Da salida como esta:

UPDATE users SET username='[email protected]' WHERE users.username = 'bmcboatface';
UPDATE users SET username='[email protected]' WHERE users.username = 'ndhyani';users.username = 'ndhyani';

Por qué un barco de investigación tiene una dirección de correo electrónico aún no se ha determinado. He estado en contacto con el equipo de TI de Example Inc y no he tenido respuesta.





python algorithm matlab image-processing maze