Représentation et résolution d'un labyrinthe donné une image

Question

Quel est le meilleur moyen de représenter et résoudre un labyrinthe donné sous forme d'image?

Étant donné une image JPEG (comme celle ci-dessus), quel est le meilleur moyen de la lire, de la parser dans une structure de données et de résoudre le labyrinthe? Mon premier instinct est de lire l'image pixel par pixel et de la stocker dans une liste (tableau) de valeurs booléennes: Vrai pour un pixel blanc, et Faux pour un pixel non blanc (les couleurs peuvent être ignorées). Le problème avec cette méthode, c'est que l'image peut ne pas être "parfaite au pixel près". Autrement dit, s'il y a un pixel blanc quelque part sur un mur, cela peut créer un chemin non voulu.

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

Un autre problème avec la conversion en SVG est que les lignes ne sont pas "parfaitement" droites. Cela entraîne les chemins étant 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 situés sur la courbe devraient être calculés, mais ne correspondraient pas exactement aux indices de la liste.

Je suppose qu'alors que l'une de ces méthodes pourrait fonctionner (bien que probablement pas), elles sont extrêmement inefficaces pour une image aussi grande, et il doit exister un moyen meilleur. Comment cela peut-il être fait de la meilleure façon (de manière la plus efficace et/ou avec le moins de complexité)? Existe-t-il même un meilleur moyen?

Ensuite vient 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
Meilleur moyen de parser? En quelle structure de données? Comment cette structure aiderait-elle/entraverait-elle la résolution?

MISE À JOUR
J'ai essayé d'implémenter ce que @Mikhail a écrit en Python, en utilisant numpy, comme l'a recommandé @Thomas. Je pense que l'algorithme est correct, mais cela 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):
  """ Renvoie si (x, y) est approximativement un pixel blanc."""
  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):
  """ Effectue une recherche en largeur. """
  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 # s'assurer que le fichier est en RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])

Answer 1

Voici une solution.

1. Convertir l'image en niveaux de gris (pas encore binaire), en ajustant les poids pour les couleurs de sorte que l'image en niveaux de gris finale soit approximativement uniforme. Vous pouvez le faire simplement en contrôlant les curseurs dans Photoshop dans Image -> Adjustments -> Black & White.
2. Convertir l'image en binaire en définissant un seuil approprié dans Photoshop dans Image -> Adjustments -> Threshold.
3. Assurez-vous que le seuil est correctement sélectionné. Utilisez l'outil Baguette magique avec une tolérance de 0, un échantillon ponctuel, contigu, sans lissage. Vérifiez que les bords auxquels la sélection se brise 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épart.
4. Ajoutez des bordures artificielles sur le labyrinthe pour vous assurer que le voyageur virtuel ne pourra pas marcher autour :)
5. Implémenter recherche en largeur d'abord (BFS) dans votre langage préféré et exécutez-le depuis le départ. Je préfère MATLAB pour cette tâche. Comme l'a déjà mentionné @Thomas, il n'est pas nécessaire de manipuler la représentation régulière des graphes. Vous pouvez travailler directement avec l'image binarisée.

Voici le code MATLAB pour BFS :

fonction chemin = résoudre_le_labyrinthe(fichier_img)
  %% Initialiser les données
  img = imread(fichier_img);
  img = rgb2gray(img);
  labyrinthe = img > 0;
  départ = [985 398];
  fin = [26 399];

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

  function push(p, d)
    q = p + d;
    if labyrinthe(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(départ, [0 0]);

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

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

  %% Extraction du chemin
  chemin = fin;
  while true
    q = chemin(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    chemin(end + 1, :) = p;
    if isequal(p, départ) 
      break;
    end
  end
end

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

Et voici la réponse :

Answer 2

Cette solution est écrite en Python. Merci à Mikhail pour les indications sur la préparation des images.

Une recherche en largeur 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) # voir note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "La file d'attente a été épuisée. Aucune réponse n'a été trouvée."

if __name__ == '__main__':

    # invoke: python mazesolver.py  [.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) # rouge

    path_img.save(sys.argv[2])

Note: Marque un pixel blanc visité en gris. Cela évite le besoin d'une liste des pixels visités, mais cela nécessite un deuxième chargement du fichier image depuis le disque avant de dessiner un chemin (si vous ne voulez pas une image composite du chemin final et DE TOUS les chemins pris).

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

Answer 3

J'ai essayé moi-même de mettre en œuvre la recherche A-Star pour ce problème. J'ai suivi de près l'implémentation de Joseph Kern pour le framework et le pseudocode de l'algorithme 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 créer une fonction qui estime le coût restant (ici : distance) jusqu'à ce que le but soit atteint. À moins que vous ne soyez à l'aise avec une solution sous-optimale, elle ne doit pas surestimer le coût. Un choix conservateur ici serait la distance manhattan (ou taxicab) car cela représente la distance en ligne droite entre deux points sur la grille pour le voisinage utilisé de Von Neumann. (Ce qui, dans ce cas, ne surestimerait jamais le coût.)

Cependant, cela sous-estimerait significativement le coût réel pour le labyrinthe donné. Par conséquent, j'ai ajouté deux autres métriques de distance, la distance euclidienne au carré et la distance de manhattan multipliée par quatre pour la comparaison. Cependant, elles pourraient 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  [.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 par celles postées par Joseph Kern). Les animations montrent une nouvelle image après 10000 itérations de la boucle principale.

Recherche en largeur d'abord :

A-Star Distance de Manhattan :

A-Star Distance Euclidienne au Carré :

A-Star Distance de Manhattan multipliée par quatre :

Les résultats montrent que les régions explorées du labyrinthe diffèrent considérablement en fonction des heuristiques utilisées. Ainsi, la distance euclidienne au carré produit même un chemin différent (sous-optimal) par rapport aux autres métriques.

En ce qui concerne les performances de l'algorithme A-Star en termes de temps d'exécution jusqu'à la terminaison, notez qu'une grande quantité d'évaluations des fonctions de distance et de coût s'additionnent par rapport à la recherche en largeur d'abord (BFS) qui doit seulement évaluer la "direction vers le but" de chaque position candidate. Que le coût de ces évaluations de fonctions supplémentaires (A-Star) l'emporte sur le coût du plus grand nombre de nœuds à vérifier (BFS) et notamment si les performances posent problème pour votre application, est une question de perception individuelle et ne peut bien sûr pas être répondue de manière générale.

Une chose qui peut être dite en général sur le fait de savoir si un algorithme de recherche informé (comme A-Star) pourrait être le meilleur choix par rapport à une recherche exhaustive (par exemple, BFS) est la suivante. Avec le nombre de dimensions du labyrinthe, c'est-à-dire le facteur de branchement de l'arbre de recherche, le désavantage d'une recherche exhaustive (rechercher exhaustivement) croît de manière exponentielle. Avec la complexité croissante, il devient de moins en moins faisable de le faire et, à un certain point, vous êtes assez satisfait de tout résultat du chemin, qu'il soit (approximativement) optimal ou non.

Answer 4

La recherche d'arbre est trop lourde. Le labyrinthe est intrinsèquement séparable le long du(s) chemin(s) de solution.

(Merci à rainman002 de Reddit de m'avoir signalé cela.)

En raison de cela, vous pouvez rapidement utiliser les composantes connectées pour identifier les sections connectées du mur du labyrinthe. Cela parcourt les pixels deux fois.

Si vous souhaitez transformer cela en un joli diagramme du(des) chemin(s) de solution, vous pouvez ensuite utiliser des opérations binaires avec des éléments de structuration pour combler les "impasses" de chaque région connectée.

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

% lire et inverser l'image
im = 255 - imread('maze.jpg');

% l'affiner pour corriger les petits canaux flous
% seuiller à 15% binaire
% exécuter les composantes connectées
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purger les petites composantes (par exemple, les lettres)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% fermer les voies sans issue
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

% effectuer la sortie
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);

Answer 5

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 coloré en 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")

Solution est le corridor entre un mur gris et un mur coloré. Notez que ce labyrinthe a plusieurs solutions. De plus, cela semble simplement fonctionner.