Représenter et résoudre un labyrinthe à partir d'une image

Quelle est la meilleure façon de représenter et de résoudre un labyrinthe avec une image?

Étant donné une image JPEG (comme vu ci-dessus), quelle est la meilleure façon de la lire, de l'analyser dans une structure de données et de résoudre le labyrinthe? Mon premier réflexe est de lire l'image pixel par pixel et de la stocker dans une liste (tableau) de valeurs booléennes: Truepour un pixel blanc, et Falsepour un pixel non blanc (les couleurs peuvent être supprimées). Le problème avec cette méthode, c'est que l'image peut ne pas être "pixel parfait". Par cela, je veux simplement dire que s'il y a un pixel blanc quelque part sur un mur, il peut créer un chemin involontaire.

Une autre méthode (qui m'est venue après un peu de réflexion) consiste à convertir l'image en fichier SVG - qui est une liste de chemins tracés sur une toile. De cette façon, les chemins pourraient être lus dans le même type de liste (valeurs booléennes) où Trueindique un chemin ou un mur, Falseindiquant un espace de voyage. Un problème avec cette méthode se produit si la conversion n'est pas précise à 100% et ne connecte pas entièrement tous les murs, créant des écarts.

Un autre problème avec la conversion en SVG est que les lignes ne sont pas "parfaitement" droites. Il en résulte que les chemins sont des courbes de Bézier cubiques. Avec une liste (tableau) de valeurs booléennes indexées par des entiers, les courbes ne seraient pas transférées facilement et tous les points qui se trouvent sur la courbe devraient être calculés, mais ne correspondraient pas exactement aux indices de liste.

Je suppose que même si l'une de ces méthodes peut fonctionner (mais probablement pas), elles sont terriblement inefficaces compte tenu d'une si grande image et qu'il existe une meilleure méthode. Comment cela se fait-il (le plus efficacement et / ou avec le moins de complexité)? Existe-t-il même un meilleur moyen?

Vient ensuite la résolution du labyrinthe. Si j'utilise l'une des deux premières méthodes, je me retrouverai essentiellement avec une matrice. Selon cette réponse , un bon moyen de représenter un labyrinthe est d'utiliser un arbre, et un bon moyen de le résoudre est d'utiliser l' algorithme A * . Comment créer un arbre à partir de l'image? Des idées?

TL; DR La
meilleure façon d'analyser? Dans quelle structure de données? Comment cette structure aiderait-elle / entraverait-elle la résolution?

MISE À JOUR
J'ai essayé de mettre en œuvre ce que @Mikhail a écrit en Python, en utilisant numpy, comme @Thomas l'a recommandé. Je pense que l'algorithme est correct, mais il ne fonctionne pas comme espéré. (Code ci-dessous.) La bibliothèque PNG est 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, [])

Voici une solution.

1. Convertissez l'image en niveaux de gris (pas encore binaire), en ajustant les poids des couleurs afin que l'image finale en niveaux de gris soit approximativement uniforme. Vous pouvez le faire simplement en contrôlant les curseurs dans Photoshop dans Image -> Réglages -> Noir et blanc.
2. Convertissez l'image en binaire en définissant le seuil approprié dans Photoshop dans Image -> Réglages -> Seuil.
3. Assurez-vous que le seuil est bien sélectionné. Utilisez l'outil Baguette magique avec une tolérance de 0, échantillon ponctuel, contigu, sans anti-crénelage. Vérifiez que les bords auxquels les sauts de sélection ne sont pas de faux bords introduits par un mauvais seuil. En fait, tous les points intérieurs de ce labyrinthe sont accessibles depuis le début.
4. Ajoutez des bordures artificielles sur le labyrinthe pour vous assurer que le voyageur virtuel ne le contournera pas :)
5. Implémentez la recherche en largeur (BFS) dans votre langue préférée et exécutez-la depuis le début. Je préfère MATLAB pour cette tâche. Comme @Thomas l'a déjà mentionné, il n'est pas nécessaire de jouer avec la représentation régulière des graphiques. Vous pouvez travailler directement avec une image binarisée.

Voici le code MATLAB pour 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

C'est vraiment très simple et standard, il ne devrait pas y avoir de difficultés pour l'implémenter en Python ou autre.

Et voici la réponse:

Cette solution est écrite en Python. Merci Mikhail pour les conseils sur la préparation de l'image.

Une première recherche animée:

Le labyrinthe terminé:

#!/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])

Remarque: marque un pixel blanc visité en gris. Cela supprime le besoin d'une liste visitée, mais cela nécessite un deuxième chargement du fichier image à partir du disque avant de dessiner un chemin (si vous ne voulez pas une image composite du chemin final et TOUS les chemins empruntés).

Une version vierge du labyrinthe que j'ai utilisé.

Je me suis essayé à implémenter la recherche A-Star pour ce problème. Suivi de près de l'implémentation par Joseph Kern pour le framework et l'algorithme pseudocode donné ici :

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 []

Comme A-Star est un algorithme de recherche heuristique, vous devez trouver une fonction qui estime le coût restant (ici: la distance) jusqu'à ce que l'objectif soit atteint. À moins que vous ne soyez à l'aise avec une solution sous-optimale, elle ne devrait pas surestimer le coût. Un choix prudent serait ici la distance de Manhattan (ou taxi) car elle représente la distance en ligne droite entre deux points sur la grille pour le quartier de Von Neumann utilisé. (Ce qui, dans ce cas, ne surestimerait jamais le coût.)

Cependant, cela sous-estimerait considérablement le coût réel du labyrinthe en question. Par conséquent, j'ai ajouté deux autres mesures de distance au carré, la distance euclidienne et la distance de Manhattan multipliée par quatre pour comparaison. Ceux-ci pourraient cependant surestimer le coût réel et pourraient donc donner des résultats sous-optimaux.

Voici le code:

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

Voici quelques images pour une visualisation des résultats (inspirées de celle postée par Joseph Kern ). Les animations montrent une nouvelle image chacune après 10000 itérations de la boucle while principale.

Recherche en largeur:

Distance A-Star Manhattan:

Distance euclidienne au carré A-Star:

A-Star Manhattan Distance multipliée par quatre:

Les résultats montrent que les régions explorées du labyrinthe diffèrent considérablement pour l'heuristique utilisée. En tant que telle, la distance euclidienne au carré produit même un chemin différent (sous-optimal) comme les autres métriques.

En ce qui concerne les performances de l'algorithme A-Star en termes de durée d'exécution jusqu'à la fin, notez que beaucoup d'évaluation des fonctions de distance et de coût s'additionnent par rapport à la recherche de largeur en premier (BFS) qui n'a besoin que d'évaluer le "but" de chaque poste de candidat. Que le coût de ces évaluations de fonctions supplémentaires (A-Star) l'emporte ou non sur le coût du plus grand nombre de nœuds à vérifier (BFS) et surtout si les performances sont un problème pour votre application, c'est une question de perception individuelle. et ne peut bien sûr pas recevoir de réponse générale.

On peut dire en général si un algorithme de recherche informé (comme A-Star) pourrait être le meilleur choix par rapport à une recherche exhaustive (par exemple, BFS) est le suivant. Avec le nombre de dimensions du labyrinthe, c'est-à-dire le facteur de branchement de l'arbre de recherche, l'inconvénient d'une recherche exhaustive (pour une recherche exhaustive) croît de façon exponentielle. Avec une complexité croissante, il devient de moins en moins possible de le faire et à un moment donné, vous êtes à peu près satisfait de tout chemin de résultat, qu'il soit (approximativement) optimal ou non.

La recherche dans les arbres est trop. Le labyrinthe est intrinsèquement séparable le long du ou des chemins de solution.

(Merci à rainman002 de Reddit de me l'avoir signalé.)

Pour cette raison, vous pouvez rapidement utiliser des composants connectés pour identifier les sections connectées du mur de labyrinthe. Cela itère deux fois sur les pixels.

Si vous voulez transformer cela en un joli diagramme du ou des chemins de solution, vous pouvez alors utiliser des opérations binaires avec des éléments structurants pour remplir les chemins "sans issue" pour chaque région connectée.

Le code de démonstration de MATLAB suit. Il pourrait utiliser des ajustements pour mieux nettoyer le résultat, le rendre plus généralisable et le faire fonctionner plus rapidement. (Parfois quand il n'est pas 2h30 du matin.)

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

Utilise une file d'attente pour un remplissage continu de seuil. Pousse le pixel à gauche de l'entrée dans la file d'attente, puis démarre la boucle. Si un pixel en file d'attente est suffisamment sombre, il est de couleur gris clair (au-dessus du seuil) et tous les voisins sont poussés dans la file d'attente.

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 solution est le couloir entre le mur gris et le mur coloré. Notez que ce labyrinthe a plusieurs solutions. En outre, cela semble simplement fonctionner.

C'est parti: maze-solver-python (GitHub)

Je me suis amusé à jouer avec cela et j'ai étendu la réponse de Joseph Kern . Ne pas lui porter atteinte; Je viens de faire quelques ajouts mineurs pour toute autre personne qui pourrait être intéressée à jouer avec cela.

C'est un solveur basé sur python qui utilise BFS pour trouver le chemin le plus court. Mes principaux ajouts à l'époque sont les suivants:

1. L'image est nettoyée avant la recherche (c'est-à-dire la conversion en noir et blanc pur)
2. Générez automatiquement un GIF.
3. Générez automatiquement un AVI.

Dans l'état actuel des choses, les points de début / fin sont codés en dur pour cet exemple de labyrinthe, mais je prévois de l'étendre de sorte que vous puissiez choisir les pixels appropriés.

J'irais pour l'option matrice de bools. Si vous trouvez que les listes Python standard sont trop inefficaces pour cela, vous pouvez utiliser un numpy.booltableau à la place. Le stockage pour un labyrinthe de 1 000 x 1 000 pixels ne représente alors que 1 Mo.

Ne vous embêtez pas à créer des structures de données arborescentes ou graphiques. C'est juste une façon d'y penser, mais pas nécessairement une bonne façon de le représenter en mémoire; une matrice booléenne est à la fois plus facile à coder et plus efficace.

Utilisez ensuite l'algorithme A * pour le résoudre. Pour l'heuristique de distance, utilisez la distance Manhattan ( distance_x + distance_y).

Représentez les nœuds par un tuple de (row, column)coordonnées. Chaque fois que l'algorithme ( pseudocode Wikipedia ) appelle des "voisins", c'est une simple question de boucler sur les quatre voisins possibles (attention aux bords de l'image!).

Si vous trouvez que c'est encore trop lent, vous pouvez essayer de réduire l'échelle de l'image avant de la charger. Veillez à ne pas perdre de chemins étroits dans le processus.

Il est peut-être possible de faire une réduction d'échelle 1: 2 en Python également, en vérifiant que vous ne perdez en fait aucun chemin possible. Une option intéressante, mais elle nécessite un peu plus de réflexion.

Voici quelques idées.

(1. Traitement d'image :)

1.1 Chargez l'image en tant que carte de pixels RVB . En C # c'est une utilisation triviale system.drawing.bitmap. Dans les langues sans prise en charge simple de l'imagerie, il suffit de convertir l'image au format pixmap portable (PPM) (une représentation de texte Unix, produit de gros fichiers) ou un format de fichier binaire simple que vous pouvez facilement lire, comme BMP ou TGA . ImageMagick sous Unix ou IrfanView sous Windows.

1.2 Vous pouvez, comme mentionné précédemment, simplifier les données en prenant le (R + G + B) / 3 pour chaque pixel comme indicateur de ton gris, puis seuil la valeur pour produire un tableau noir et blanc. Quelque chose près de 200 en supposant que 0 = noir et 255 = blanc supprimera les artefacts JPEG.

(2. Solutions :)

2.1 Recherche en profondeur d'abord: Initiez une pile vide avec l'emplacement de départ, collectez les mouvements de suivi disponibles, choisissez-en un au hasard et poussez sur la pile, continuez jusqu'à ce que la fin soit atteinte ou une impasse. En cas de retour en arrière en faisant sauter la pile, vous devez garder une trace des positions visitées sur la carte, donc lorsque vous collectez des mouvements disponibles, vous ne prenez jamais le même chemin deux fois. Très intéressant à animer.

2.2 Recherche étendue: mentionnée précédemment, similaire à celle ci-dessus mais utilisant uniquement des files d'attente. Aussi intéressant à animer. Cela fonctionne comme un logiciel d'édition d'images. Je pense que vous pouvez résoudre un labyrinthe dans Photoshop en utilisant cette astuce.

2.3 Mur suiveur: géométriquement parlant, un labyrinthe est un tube plié / alambiqué. Si vous gardez la main sur le mur, vous finirez par trouver la sortie;) Cela ne fonctionne pas toujours. Il existe certaines hypothèses concernant les labyrinthes parfaits, etc., par exemple, certains labyrinthes contiennent des îles. Cherchez-le; c'est fascinant.

(3. Commentaires :)

C'est le plus délicat. Il est facile de résoudre des labyrinthes s'ils sont représentés dans un simple tableau formel, chaque élément étant un type de cellule avec des murs nord, est, sud et ouest et un champ de drapeau visité. Cependant, étant donné que vous essayez de le faire étant donné un croquis dessiné à la main, cela devient désordonné. Je pense honnêtement qu'essayer de rationaliser l'esquisse vous rendra fou. Cela s'apparente à des problèmes de vision par ordinateur qui sont assez impliqués. Aller directement sur la carte d'image peut être plus facile mais plus coûteux.

Voici une solution en utilisant 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)

RVB à niveaux de gris, voir: 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!

C'est ce qui se passe si vous ne remplissez pas certains pixels de bordure (Ha!) ...

Divulgation complète: j'ai moi-même posé et répondu à une question très similaire avant de trouver celle-ci. Ensuite, grâce à la magie de SO, j'ai trouvé celui-ci comme l'une des meilleures "questions connexes". Je pensais que j'utiliserais ce labyrinthe comme cas de test supplémentaire ... J'ai été très heureux de constater que ma réponse y fonctionne également pour cette application avec très peu de modifications.

la bonne solution serait qu'au lieu de trouver les voisins par pixel, ce serait fait par cellule, car un couloir peut avoir 15px donc dans le même couloir il peut prendre des actions comme à gauche ou à droite, alors que si c'était fait comme si le déplacement était un cube ce serait une action simple comme HAUT, BAS, GAUCHE OU DROITE