Reprezentowanie i rozwiązywanie labiryntu na podstawie obrazu

271

Jaki jest najlepszy sposób na przedstawienie i rozwiązanie labiryntu na podstawie obrazu?

Zdjęcie na okładce The Scope Issue 134

Biorąc pod uwagę obraz JPEG (jak pokazano powyżej), jaki jest najlepszy sposób, aby go odczytać, przeanalizować w jakiejś strukturze danych i rozwiązać labirynt? Moim pierwszym instynktem jest odczytanie obrazu piksel po pikselu i zapisanie go na liście (tablicy) wartości boolowskich: Truedla białego piksela i Falsedla innego niż biały piksel (kolory można odrzucić). Problem z tą metodą polega na tym, że obraz może nie być „w pikselach idealny”. Rozumiem przez to, że jeśli gdzieś na ścianie jest biały piksel, może on stworzyć niezamierzoną ścieżkę.

Inną metodą (która przyszła mi do głowy po namyśle) jest konwersja obrazu do pliku SVG - który jest listą ścieżek narysowanych na płótnie. W ten sposób ścieżki mogą zostać wczytane do tego samego rodzaju listy (wartości boolowskie), gdzie Truewskazuje ścieżkę lub ścianę, Falsewskazując przestrzeń, którą można przejechać. Problem z tą metodą powstaje, jeśli konwersja nie jest w 100% dokładna i nie łączy w pełni wszystkich ścian, tworząc luki.

Problemem przy konwersji do SVG jest również to, że linie nie są „idealnie” proste. Powoduje to, że ścieżki są sześciennymi krzywymi Beziera. Z listą (tablicą) wartości boolowskich indeksowanych liczbami całkowitymi krzywe nie byłyby łatwe do przeniesienia, a wszystkie punkty na linii musiałyby zostać obliczone, ale nie pasowałyby dokładnie do indeksów listy.

Zakładam, że chociaż jedna z tych metod może działać (choć prawdopodobnie nie), to są one niestety nieefektywne, biorąc pod uwagę tak duży obraz i że istnieje lepszy sposób. Jak to się robi najlepiej (najbardziej wydajnie i / lub przy najmniejszej złożoności)? Czy jest jakiś najlepszy sposób?

Potem przychodzi rozwiązanie labiryntu. Jeśli użyję jednej z dwóch pierwszych metod, zasadniczo skończę na matrycy. Zgodnie z tą odpowiedzią dobrym sposobem na przedstawienie labiryntu jest użycie drzewa, a dobrym sposobem jego rozwiązania jest użycie algorytmu A * . Jak stworzyć drzewo z obrazu? Jakieś pomysły?

TL; DR
Najlepszy sposób na parsowanie? W jakiej strukturze danych? W jaki sposób wspomniana struktura pomaga / utrudnia rozwiązywanie?

AKTUALIZACJA
Próbowałem swoich sił we wdrażaniu tego, co @Mikhail napisał w Pythonie, używając numpyzgodnie z zaleceniami @Thomas. Wydaje mi się, że algorytm jest poprawny, ale nie działa zgodnie z oczekiwaniami. (Kod poniżej.) Biblioteka PNG to 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, [])
Whymarrh
źródło
12
Przekształciłem labirynt na czarno-biały i użyłem metody znajdowania automatów komórkowych, aby go rozwiązać.
Dan D.
Czy musisz radzić sobie tylko z tym obrazem, czy z wieloma podobnymi obrazami? Czy istnieje opcja ręcznego przetwarzania specyficznego dla tego określonego obrazu?
Michaił
1
@ Whymarrh Nie koduję Pythona, ale jestem pewien, że powinieneś przejść visited.append(s)pod a for.ifi zastąpić go visited.append(np). Wierzchołek jest odwiedzany po dodaniu do kolejki. W rzeczywistości tablica ta powinna mieć nazwę „w kolejce”. Możesz także zakończyć BFS, gdy dotrzesz do mety.
Michaił
2
@ Whymarrh Wydaje się, że również pominąłeś implementację bloku wyodrębniania ścieżki. Bez niego możesz tylko dowiedzieć się, czy wykończenie jest osiągalne, czy nie, ale nie w jaki sposób.
Michaił
1
Aby dowiedzieć się, czy jest roztwór, UnionFind i skanowania normalny jest najszybszy algorytm. Nie daje ci ścieżki, ale daje ci zestaw płytek, które będą miały ścieżkę jako podzbiór.
st0le

Odpowiedzi:

236

Oto rozwiązanie.

  1. Konwertuj obraz na skalę szarości (jeszcze nie binarną), dostosowując wagi kolorów, aby końcowy obraz w skali szarości był w przybliżeniu jednolity. Możesz to zrobić po prostu kontrolując suwaki w Photoshopie w Image -> Adjustments -> Black & White.
  2. Konwertuj obraz na plik binarny, ustawiając odpowiedni próg w Photoshopie w Obraz -> Dopasowania -> Próg.
  3. Upewnij się, że próg został wybrany prawidłowo. Użyj narzędzia Magiczna różdżka z tolerancją 0, próbka punktowa, ciągła, bez wygładzania. Sprawdź, czy krawędzie, na których łamie się zaznaczenie, nie są fałszywymi krawędziami wprowadzonymi przez zły próg. W rzeczywistości wszystkie punkty wewnętrzne tego labiryntu są dostępne od samego początku.
  4. Dodaj sztuczne granice w labiryncie, aby mieć pewność, że wirtualny podróżnik go nie obejdzie :)
  5. Zaimplementuj wyszukiwanie według szerokości (BFS) w swoim ulubionym języku i uruchom je od początku. Wolę MATLAB do tego zadania. Jak już wspomniano @ Thomas, nie ma potrzeby, aby bałaganić regularną reprezentację wykresów. Możesz pracować bezpośrednio z binarnym obrazem.

Oto kod MATLAB dla 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

Jest to naprawdę bardzo proste i standardowe, nie powinno być trudności z implementacją tego w Pythonie lub czymkolwiek.

A oto odpowiedź:

Wpisz opis zdjęcia tutaj

Michaił
źródło
1
@ Whymarrh Cóż, dla „Just this image” faktycznie masz odpowiedź. Czy masz jakieś konkretne pytania? Pozycje 1-4 z mojej listy to przetwarzanie ręczne, o które pytałem. Pozycja 5 to BFS - bardzo podstawowy algorytm dla wykresów, ale można go zastosować bezpośrednio do obrazu, bez konwersji pikseli na wierzchołki i sąsiadów na krawędzie.
Michaił
Czuję, że wszystko załatwiłeś. Próbuję wdrożyć to, co powiedziałeś w Pythonie (używając DFS zamiast BFS, tylko dlatego, że kodowałem to już raz). Wrócę, aby zaktualizować pytanie / zaakceptować odpowiedzi za chwilę.
Whymarrh
2
@ Whymarrh DFS nie znajdzie cię najkrótszą drogą, podczas gdy BFS. Są z natury takie same, jedyną różnicą jest podstawowa struktura. Stos (FILO) dla DFS i kolejka (FIFO) dla BFS.
Michaił
3
BFS jest tutaj właściwym wyborem, ponieważ tworzy najkrótszą ścieżkę, co daje „rozsądną” ścieżkę, nawet gdy korytarze są znacznie szersze niż 1 piksel. OTOH DFS będzie miał tendencję do eksploracji korytarzy i mało obiecujących regionów labiryntu z wzorem „zalania”.
j_random_hacker
1
@JosephKern Path nie zachodzi na żadne ściany. Po prostu usuń wszystkie czerwone piksele i gotowe.
Michaił
160

To rozwiązanie zostało napisane w języku Python. Dziękuję Michaiłowi za wskazówki dotyczące przygotowania obrazu.

Animowane wyszukiwanie szerokości:

Animowana wersja BFS

The Completed Maze:

Ukończony labirynt

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

Uwaga: oznacza biały piksel odwiedzany na szaro. Eliminuje to potrzebę odwiedzania listy, ale wymaga to drugiego załadowania pliku obrazu z dysku przed narysowaniem ścieżki (jeśli nie chcesz, aby złożony obraz końcowej ścieżki i WSZYSTKIE ścieżki zostały podjęte).

Pusta wersja labiryntu, którego użyłem.

Joseph Kern
źródło
13
Ponieważ byłeś na tyle niesamowity, że wróciłeś i głosowałem nawet po odpowiedzi na twoje pytanie, stworzyłem animowany gif BFS, aby pomóc lepiej zobrazować proces.
Joseph Kern
1
Niezły, dzięki. Dla innych, którzy chcą się z tym bawić, tak jak ja, chciałbym podzielić się moimi wskazówkami w oparciu o napotkane trudności. 1) Przekształć obraz w czystą czerń i biel lub zmodyfikuj funkcję „isWhite ()”, aby zaakceptować prawie białą | czerń. Napisałem metodę „cleanImage”, która wstępnie przetworzyła wszystkie piksele, przekształcając je w czystą biel lub czerń, w przeciwnym razie algorytm nie znajdzie ścieżki. 2) Przeczytaj obraz wyraźnie jako RGB [base_img = Image.open (img_in); base_img = base_img.convert ('RGB')]. Aby uzyskać gif, wyślij kilka obrazów, a następnie uruchom polecenie „konwersja-opóźnienie 5-pętla 1 * .jpg bfs.gif”.
Stefan
1
brakujące tiret w linii 13
spowolniony
81

Próbowałem samodzielnie wdrożyć wyszukiwanie A-Star dla tego problemu. Dokładnie śledził implementację Josepha Kerna dla frameworka i pseudokodu algorytmu podanego tutaj :

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

Ponieważ A-Star jest heurystycznym algorytmem wyszukiwania, musisz wymyślić funkcję, która szacuje pozostały koszt (tutaj: odległość), aż do osiągnięcia celu. O ile nie czujesz się dobrze z rozwiązaniem nieoptymalnym, nie powinno ono przeceniać kosztów. Konserwatywnym wyborem byłaby tutaj odległość manhattan (lub taksówka), ponieważ reprezentuje ona odległość w linii prostej między dwoma punktami na siatce dla używanej dzielnicy von Neumanna. (Co w tym przypadku nigdy nie zawyżałoby kosztów).

To jednak znacznie nie docenia faktycznego kosztu danego labiryntu. Dlatego dodałem dwie inne miary odległości do kwadratu odległość euklidesowa i manhattan pomnożone przez cztery dla porównania. Mogą one jednak zawyżać faktyczny koszt, a zatem mogą dawać wyniki nieoptymalne.

Oto kod:

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

Oto kilka zdjęć do wizualizacji wyników (zainspirowanych tym, które opublikował Joseph Kern ). Animacje pokazują nową ramkę po 10000 iteracjach głównej pętli while.

Wyszukiwanie szerokości:

Szerokie wyszukiwanie

A-Star Manhattan Odległość:

A-Star Manhattan Odległość

Odległość do kwadratu euklidesowego z gwiazdką:

Kwadratowy dystans euklidesowy gwiazdy A

A-Star Manhattan Odległość pomnożona przez cztery:

A-Star Manhattan Odległość pomnożona przez cztery

Wyniki pokazują, że badane obszary labiryntu różnią się znacznie w zależności od zastosowanej heurystyki. Jako taka, kwadratowa odległość euklidesowa wytwarza nawet inną (nieoptymalną) ścieżkę niż inne metryki.

Jeśli chodzi o wydajność algorytmu A-Star pod względem czasu działania do czasu zakończenia, należy zauważyć, że wiele ocen funkcji odległości i kosztów sumuje się w porównaniu z rozszerzeniem pierwszego wyszukiwania (BFS), które musi jedynie ocenić „celność” każde stanowisko kandydujące. To, czy koszt tych dodatkowych ocen funkcji (A-Star) przeważa nad kosztem większej liczby węzłów do sprawdzenia (BFS), a zwłaszcza czy wydajność w ogóle stanowi problem dla Twojej aplikacji, jest kwestią indywidualnego postrzegania i oczywiście nie można na ogół odpowiedzieć.

Rzecz, którą można ogólnie powiedzieć o tym, czy algorytm świadomego wyszukiwania (taki jak A-Star) może być lepszym wyborem niż wyczerpujące wyszukiwanie (np. BFS), jest następujący. Wraz z liczbą wymiarów labiryntu, tj. Współczynnikiem rozgałęzienia drzewa wyszukiwania, wada wyczerpującego wyszukiwania (w celu wyczerpującego wyszukiwania) rośnie wykładniczo. Z rosnącą złożonością staje się to coraz mniej wykonalne, a w pewnym momencie jesteś całkiem zadowolony z dowolnej ścieżki wyników, czy to (w przybliżeniu) optymalnej, czy nie.

moooeeeep
źródło
1
„A-Star Manhattan Odległość pomnożona przez cztery”? Gwiazda A nie jest gwiazdą A, jeśli heurysta może przecenić odległość. (I tym samym nie gwarantuje też znalezienia najkrótszej ścieżki)
przykład
@ przykład Oczywiście, jeśli zastosujemy niedopuszczalną funkcję heurystyczną, algorytm może nie znaleźć optymalnego rozwiązania (jak wskazałem w mojej odpowiedzi). Ale nie posunąłbym się nawet do zmiany nazwy podstawowego algorytmu z tego powodu.
moooeeeep
38

Wyszukiwanie drzew to za dużo. Labirynt można z natury oddzielić wzdłuż ścieżki (ścieżek) rozwiązania.

(Podziękowania dla rainman002 z Reddit za wskazanie mi tego.)

Z tego powodu możesz szybko korzystać z podłączonych komponentów aby zidentyfikować połączone odcinki ściany labiryntu. Powtarza to dwukrotnie piksele.

Jeśli chcesz zmienić to w ładny schemat ścieżek rozwiązania, możesz następnie użyć operacji binarnych z elementami strukturyzującymi, aby wypełnić ścieżki „ślepego zaułka” dla każdego połączonego regionu.

Poniżej znajduje się kod demonstracyjny dla MATLAB. Przydałoby się ulepszenie, aby lepiej wyczyścić wynik, uczynić go bardziej ogólnym i przyspieszyć. (Kiedyś nie jest 2:30.)

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

wynik bieżącego kodu

Jim Gray
źródło
24

Wykorzystuje kolejkę do ciągłego wypełniania progu. Przesuwa piksel w lewo od wejścia do kolejki, a następnie uruchamia pętlę. Jeśli piksel w kolejce jest wystarczająco ciemny, ma kolor jasnoszary (powyżej progu), a wszyscy sąsiedzi są wypychani do kolejki.

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

Rozwiązaniem jest korytarz między szarą ścianą a kolorową ścianą. Uwaga: ten labirynt ma wiele rozwiązań. Wydaje się, że to po prostu działa.

Rozwiązanie

kylefinn
źródło
1
Ciekawa naiwna rozdzielczość oparta na metodzie „ręka na ścianie”. Rzeczywiście, nie najlepszy, ale mi się podoba.
zessx
23

Proszę bardzo: maze-solver-python (GitHub)

wprowadź opis zdjęcia tutaj

Bawiłem się dobrze z tym i poszerzyłem odpowiedź Josepha Kerna . Nie umniejszać tego; Właśnie dodałem kilka drobnych dodatków dla każdego, kto może być zainteresowany zabawą.

Jest to solver oparty na pythonie, który używa BFS do znalezienia najkrótszej ścieżki. Moje główne dodatki w tym czasie to:

  1. Obraz jest czyszczony przed wyszukiwaniem (tzn. Konwersja do czystej czerni i bieli)
  2. Automatycznie generuj GIF.
  3. Automatycznie wygeneruj AVI.

Na obecnym etapie punkty początkowe / końcowe są zakodowane na stałe dla tego przykładowego labiryntu, ale planuję rozszerzyć go tak, aby można było wybrać odpowiednie piksele.

Stefan
źródło
1
Świetnie, dzięki, nie działało na BSD / Darwin / Mac, niektóre zależności i skrypt powłoki wymagały drobnych zmian, dla tych, którzy chcą wypróbować na Macu: [maze-solver-python]: github.com/holg/maze- solver-python
HolgT
@HolgT: Cieszę się, że okazało się przydatne. Z zadowoleniem przyjmuję wszelkie prośby w tej sprawie. :)
stefano,
5

Wybrałbym opcję matrycy booli. Jeśli okaże się, że standardowe listy Pythona są zbyt nieefektywne, możesz numpy.boolzamiast tego użyć tablicy. Miejsce na labirynt 1000 x 1000 pikseli wynosi wtedy zaledwie 1 MB.

Nie przejmuj się tworzeniem struktur danych drzewa lub wykresu. To tylko sposób myślenia o tym, ale niekoniecznie dobry sposób na przedstawienie go w pamięci; macierz boolowska jest łatwiejsza do kodowania i bardziej wydajna.

Następnie użyj algorytmu A *, aby go rozwiązać. Dla heurystyki odległości używaj odległości Manhattan ( distance_x + distance_y).

Reprezentuj węzły przez krotkę (row, column)współrzędnych. Ilekroć algorytm ( pseudokod Wikipedii ) woła o „sąsiadów”, jest to prosta kwestia zapętlenia czterech możliwych sąsiadów (pamiętaj o krawędziach obrazu!).

Jeśli uznasz, że wciąż jest zbyt wolny, możesz spróbować przeskalować obraz przed załadowaniem. Uważaj, aby nie zgubić wąskich ścieżek.

Być może możliwe jest również wykonanie skalowania w dół 1: 2 w Pythonie, sprawdzając, czy faktycznie nie straciłeś żadnych możliwych ścieżek. Ciekawa opcja, ale wymaga nieco więcej przemyślenia.

Tomasz
źródło
Ten znakomity post na blogu pokazuje, jak rozwiązać labirynt w matematyce. Tłumaczenie metody na python nie powinno stanowić problemu
Boris Gorelik,
Zaktualizowałem pytanie. Jeśli wybiorę użycie potrójnego RGB zamiast booleanwartości, czy pamięć nadal będzie się porównywać? Matryca ma wtedy 2400 * 1200. Czy A * w porównaniu z BFS miałby znaczący wpływ na rzeczywisty czas działania?
Whymarrh
@ Whymarrh, głębokość bitu może się zmniejszyć, aby skompensować. 2 bity na piksel powinny wystarczyć każdemu.
Brian Cain
5

Oto kilka pomysłów.

(1. Przetwarzanie obrazu :)

1.1 Załaduj obraz jako mapę pikseli RGB . W języku C # jest to banalne system.drawing.bitmap. W językach bez prostej obsługi obrazowania wystarczy przekonwertować obraz na przenośny format pixmap (PPM) (uniksowa reprezentacja tekstowa, produkuje duże pliki) lub jakiś prosty format pliku binarnego, który można łatwo odczytać, taki jak BMP lub TGA . ImageMagick w systemie Unix lub IrfanView w systemie Windows.

1.2 Możesz, jak wspomniano wcześniej, uprościć dane, przyjmując (R + G + B) / 3 dla każdego piksela jako wskaźnika odcienia szarości, a następnie próg wartości, aby utworzyć tabelę czarno-białą. Coś bliskiego 200 przy założeniu 0 = czarny i 255 = biały usunie artefakty JPEG.

(2. Rozwiązania :)

2.1 Przeszukiwanie w głąb: Rozpocznij pusty stos z początkową lokalizacją, zbierz dostępne ruchy kontrolne, wybierz jeden losowo i pchnij na stos, kontynuuj, aż do osiągnięcia końca lub martwego punktu. Po powrocie do martwego punktu przez przerzucenie stosu musisz śledzić, które pozycje odwiedzono na mapie, więc kiedy zbierasz dostępne ruchy, nigdy nie podążasz tą samą ścieżką dwa razy. Bardzo interesujące do animowania.

2.2 Wyszukiwanie według szerokości: wcześniej wspomniane, podobnie jak powyżej, ale tylko przy użyciu kolejek. Również interesujące do animowania. Działa to podobnie jak oprogramowanie do edycji obrazu w trybie wypełniania. Myślę, że przy pomocy tej sztuczki możesz rozwiązać labirynt w Photoshopie.

2.3 Zwolennik ściany: Geometrycznie labirynt jest złożoną / zwiniętą rurką. Jeśli trzymasz rękę na ścianie, w końcu znajdziesz wyjście;) To nie zawsze działa. Istnieją pewne założenia dotyczące: doskonałych labiryntów itp., Na przykład niektóre labirynty zawierają wyspy. Spójrz na to; to jest fascynujące.

(3. Komentarze :)

To jest trudne. Łatwo jest rozwiązywać labirynty, jeśli są reprezentowane w prostym układzie tablic, przy czym każdy element jest typem komórki ze ścianami północną, wschodnią, południową i zachodnią i odwiedzanym polem flagi. Jednak biorąc pod uwagę, że próbujesz to zrobić, biorąc pod uwagę ręcznie narysowany szkic, robi się bałagan. Szczerze sądzę, że próba racjonalizacji szkicu doprowadzi cię do szału. Jest to podobne do problemów z widzeniem komputerowym, które są dość zaangażowane. Być może przejście bezpośrednio na mapę obrazu może być łatwiejsze, ale bardziej marnotrawne.

linoleum
źródło
2

Oto rozwiązanie wykorzystujące 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 na skalę szarości, patrz: 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!

rozwiązanie, które poprawnie znajduje najkrótszą ścieżkę

Dzieje się tak, jeśli nie wypełnisz niektórych pikseli granicznych (Ha!) ...

wersja rozwiązania, w której solver omija labirynt

Pełne ujawnienie: sam zadałem bardzo podobne pytanie, zanim je znalazłem. Następnie dzięki magii SO znalazłem to jedno z najważniejszych „Powiązanych pytań”. Pomyślałem, że użyję tego labiryntu jako dodatkowego przypadku testowego ... Byłem bardzo zadowolony, że moja odpowiedź tam działa również dla tej aplikacji z niewielkimi modyfikacjami.

Brian D.
źródło
0

dobrym rozwiązaniem byłoby to, że zamiast znajdować sąsiadów po pikselach, można to zrobić za pomocą komórki, ponieważ korytarz może mieć 15 pikseli, więc w tym samym korytarzu może wykonywać działania takie jak w lewo lub w prawo, a jeśli zrobiłby to tak, jakby przemieszczenie był sześcianem, byłoby to proste działanie takie jak GÓRA, DÓŁ, ​​LEWO LUB PRAWO

czarny_john
źródło
Czy możesz dodać wykres rozwiązania i algorytm jak resztę odpowiedzi, aby potwierdzić swój punkt? Lepiej będzie, jeśli możesz dodać te, aby zwiększyć wagę odpowiedzi, aby inni mogli lepiej zrozumieć twoją odpowiedź.
Himanshu Bansal