messwerte - python plot title




Ein Labyrinth darstellen und lösen, das ein Bild gegeben wird (6)

Was ist der beste Weg, ein Labyrinth angesichts eines Bildes darzustellen und zu lösen?

Bei einem JPEG-Bild (wie oben zu sehen), wie lese ich es am besten ein, analysiere es in eine Datenstruktur und löse das Labyrinth? Mein erster Instinkt besteht darin, das Bild Pixel für Pixel zu lesen und es in einer Liste (Array) von booleschen Werten zu speichern: True für ein weißes Pixel und False für ein nicht weißes Pixel (die Farben können verworfen werden). Das Problem bei dieser Methode ist, dass das Bild möglicherweise nicht "pixelgenau" ist. Damit meine ich einfach, dass ein weißer Pixel irgendwo auf einer Wand einen unbeabsichtigten Pfad erzeugen kann.

Eine andere Methode (die mir nach einigem Nachdenken kam) ist, das Bild in eine SVG-Datei zu konvertieren - das ist eine Liste von Pfaden, die auf einer Leinwand gezeichnet sind. Auf diese Weise könnten die Pfade in die gleiche Art von Liste (boolesche Werte) gelesen werden, wobei True einen Pfad oder eine Wand angibt, wobei False ein verfahrbares Leerzeichen angibt. Ein Problem mit dieser Methode tritt auf, wenn die Konvertierung nicht 100% genau ist und nicht alle Wände vollständig verbindet, wodurch Lücken entstehen.

Ein Problem bei der Konvertierung zu SVG ist auch, dass die Linien nicht "perfekt" gerade sind. Dies führt dazu, dass die Pfade kubische Bezierkurven sind. Mit einer Liste (Array) von booleschen Werten, die durch Ganzzahlen indiziert werden, würden die Kurven nicht leicht übertragen, und alle Punkte, die auf der Kurve liegen, müßten berechnet werden, stimmen aber nicht genau mit den Listenindizes überein.

Ich gehe davon aus, dass eine dieser Methoden zwar funktioniert (wenn auch wahrscheinlich nicht), dass sie angesichts eines so großen Bildes ineffizient sind und dass es einen besseren Weg gibt. Wie wird das am besten (am effizientesten und / oder mit der geringsten Komplexität) durchgeführt? Gibt es überhaupt einen besten Weg?

Dann kommt das Lösen des Labyrinths. Wenn ich eine der ersten beiden Methoden verwende, werde ich im Wesentlichen mit einer Matrix enden. Entsprechend dieser Antwort ist ein guter Weg, ein Labyrinth darzustellen, ein Baum, und ein guter Weg, es zu lösen, benutzt den A * -Algorithmus . Wie würde man einen Baum aus dem Bild erstellen? Irgendwelche Ideen?

TL; DR
Beste Art zu analysieren? In welche Datenstruktur? Wie würde diese Struktur zur Lösung beitragen?

AKTUALISIEREN
Ich habe versucht, was @Mikhail in Python geschrieben hat, mit numpy , wie es @Thomas empfohlen hat. Ich fühle, dass der Algorithmus korrekt ist, aber es funktioniert nicht wie erhofft. (Code unten.) Die PNG-Bibliothek ist 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, [])

Baumsuche ist zu viel. Das Labyrinth ist von Natur aus entlang des Lösungsweges trennbar.

(Danke an rainman002 von Reddit, dass er mich darauf hingewiesen hat.)

Aus diesem Grund können Sie schnell verbundene Komponenten verwenden , um die verbundenen Abschnitte der Labyrinthwand zu identifizieren. Dies wiederholt zweimal die Pixel.

Wenn Sie das in ein schönes Diagramm des Lösungswegs (der Lösungswege) umwandeln möchten, können Sie dann binäre Operationen mit Strukturierungselementen verwenden, um die "Sackgassen" -Wege für jede verbundene Region auszufüllen.

Demo-Code für MATLAB folgt. Es könnte Tweaking verwenden, um das Ergebnis besser zu bereinigen, es verallgemeinerbarer zu machen und es schneller laufen zu lassen. (Manchmal, wenn es nicht 2:30 Uhr ist.)

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


Diese Lösung ist in Python geschrieben. Danke Mikhail für die Hinweise auf die Bildvorbereitung.

Eine animierte Breitensuche:

Das fertige Labyrinth:

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

Hinweis: Markiert ein weiß besuchtes Pixel grau. Dies beseitigt die Notwendigkeit einer besuchten Liste, aber dies erfordert ein zweites Laden der Image-Datei von der Festplatte vor dem Zeichnen eines Pfades (wenn Sie kein zusammengesetztes Bild des endgültigen Pfades und ALLE Pfade wollen).

Eine leere Version des Labyrinths, das ich benutzt habe.


Hier ist eine Lösung.

  1. Konvertieren Sie das Bild in Graustufen (noch nicht binär), indem Sie die Gewichte für die Farben so anpassen, dass das endgültige Graustufenbild ungefähr gleichförmig ist. Sie können es einfach tun, indem Sie Schieberegler in Photoshop unter Bild -> Anpassungen -> Schwarz-Weiß steuern.
  2. Konvertieren Sie das Bild in Binär, indem Sie den entsprechenden Schwellenwert in Photoshop unter Bild -> Anpassungen -> Schwellenwert einstellen.
  3. Stellen Sie sicher, dass der Schwellenwert richtig ausgewählt ist. Verwenden Sie das Zauberstab-Werkzeug mit 0 Toleranz, Punktmuster, zusammenhängend, kein Anti-Aliasing. Überprüfen Sie, dass Kanten, bei denen die Auswahl bricht, keine falschen Kanten sind, die durch einen falschen Schwellenwert eingeführt wurden. Tatsächlich sind alle inneren Punkte dieses Labyrinths von Anfang an zugänglich.
  4. Fügen Sie künstliche Grenzen in das Labyrinth ein, um sicherzustellen, dass virtuelle Reisende nicht herumlaufen :)
  5. Implementieren Sie Breitensuche (BFS) in Ihrer bevorzugten Sprache und führen Sie sie von Anfang an aus. Ich bevorzuge MATLAB für diese Aufgabe. Wie bereits von Thomas erwähnt, muss man sich nicht mit der regulären Darstellung von Graphen herumschlagen. Sie können direkt mit einem binarisierten Bild arbeiten.

Hier ist der MATLAB-Code für 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 ist wirklich sehr einfach und Standard, es sollte keine Schwierigkeiten bei der Implementierung in Python oder was auch immer sein.

Und hier ist die Antwort:


Hier sind ein paar Ideen.

(1. Bildverarbeitung :)

1.1 Laden Sie das Bild als RGB Pixel Map. In C# es trivial, system.drawing.bitmap . In Sprachen ohne einfache Unterstützung für das Imaging konvertieren Sie einfach das Bild in das portable Pixmap-Format (PPM) (eine Unix-Textdarstellung, erzeugt große Dateien) oder ein einfaches binäres Dateiformat, das Sie leicht lesen können, wie BMP oder TGA . ImageMagick in Unix oder IrfanView in Windows.

1.2 Sie können, wie bereits erwähnt, die Daten vereinfachen, indem Sie (R + G + B) / 3 für jedes Pixel als Indikator für den Grauton verwenden und dann den Wert schwellen, um eine Schwarz-Weiß-Tabelle zu erzeugen. Etwas nahe bei 200 unter Annahme von 0 = Schwarz und 255 = Weiß wird die JPEG-Artefakte entfernen.

(2. Lösungen :)

2.1 Tiefensuche: Lege einen leeren Stapel mit Startposition an, sammle verfügbare Folgeaktionen, wähle einen zufällig aus und drücke auf den Stapel, fahre fort, bis das Ende erreicht ist, oder gehe zu einem Deadend. Wenn du den Stack zurücklegst, musst du den Überblick darüber behalten, welche Positionen auf der Karte besucht wurden. Wenn du also verfügbare Züge sammelst, nimmst du nie den gleichen Weg zweimal. Sehr interessant zu animieren.

2.2 Breitensuche: Wie oben erwähnt, aber nur mit Warteschlangen. Auch interessant zu animieren. Dies funktioniert wie eine Fülle von Bildbearbeitungssoftware. Ich denke, dass Sie ein Labyrinth in Photoshop mit diesem Trick lösen können.

2.3 Wall Follower: Geometrisch gesehen ist ein Labyrinth eine gefaltete / gewundene Röhre. Wenn du deine Hand an der Wand hältst, wirst du schließlich den Ausgang finden;) Das funktioniert nicht immer. Es gibt eine gewisse Annahme: perfekte Labyrinthe usw., zum Beispiel enthalten bestimmte Labyrinthe Inseln. Schau es dir an; Es ist faszinierend.

(3. Kommentare :)

Das ist der heikle. Es ist einfach, Labyrinthe zu lösen, wenn sie in einem einfachen Array-Format dargestellt werden, wobei jedes Element ein Zelltyp mit Nord-, Ost-, Süd- und Westwänden und einem besuchten Flaggenfeld ist. Wenn Sie jedoch versuchen, dies mit einer handgezeichneten Skizze zu tun, wird es unordentlich. Ich glaube ernsthaft, dass der Versuch, die Skizze zu rationalisieren, Sie in den Wahnsinn treiben wird. Dies ist vergleichbar mit Computer Vision Probleme, die ziemlich beteiligt sind. Vielleicht ist es einfacher, auf die Imagemap zu gehen, aber es ist verschwenderischer.


Ich würde für die Matrix-of-Bools-Option gehen. Wenn Sie feststellen, dass Standard-Python-Listen dafür zu ineffizient sind, können Sie stattdessen ein numpy.bool Array verwenden. Der Speicherplatz für ein 1000x1000 Pixel großes Labyrinth beträgt dann nur 1 MB.

Machen Sie sich keine Mühe, irgendwelche Baum- oder Diagrammdatenstrukturen zu erstellen. Das ist nur eine Art, darüber nachzudenken, aber nicht unbedingt eine gute Möglichkeit, es im Gedächtnis zu repräsentieren; Eine boolesche Matrix ist sowohl einfacher zu programmieren als auch effizienter.

Dann benutze den A * -Algorithmus, um es zu lösen. Verwenden Sie für die Entfernungsheuristik die Manhattan-Entfernung ( distance_x + distance_y ).

Stellen Sie die Knoten nach einem Tupel von (row, column) Koordinaten dar. Wann immer der Algorithmus ( Wikipedia Pseudocode ) nach "Nachbarn" ruft, ist es eine einfache Sache, die vier möglichen Nachbarn zu durchlaufen (beachte die Ränder des Bildes!).

Wenn Sie feststellen, dass es immer noch zu langsam ist, können Sie das Bild verkleinern, bevor Sie es laden. Achten Sie darauf, dabei keine engen Pfade zu verlieren.

Vielleicht ist es auch möglich, ein 1: 2-Downscaling in Python durchzuführen, um zu überprüfen, dass Sie keine möglichen Pfade verlieren. Eine interessante Option, aber es braucht ein bisschen mehr Gedanken.


Verwendet eine Warteschlange für eine kontinuierliche Füllung mit Schwellenwert. Verschiebt das Pixel links vom Eingang in die Warteschlange und startet dann die Schleife. Wenn ein eingereihtes Pixel dunkel genug ist, ist es hellgrau (über dem Schwellenwert) und alle Nachbarn werden in die Warteschlange geschoben.

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

Lösung ist der Korridor zwischen grauer Wand und farbiger Wand. Beachten Sie, dass dieses Labyrinth mehrere Lösungen bietet. Auch das scheint nur zu funktionieren.







maze