Представление и решение лабиринта данного изображения

Как лучше всего представить и решить лабиринт с заданным изображением?

Учитывая изображение в формате JPEG (как показано выше), как лучше всего его прочитать, разобрать в некоторую структуру данных и решить лабиринт? Мой первый инстинкт - читать изображение попиксельно и сохранять его в списке (массиве) логических значений: Trueдля белого пикселя и Falseдля небелого пикселя (цвета можно отбрасывать). Проблема этого метода заключается в том, что изображение может быть не «идеальным по пикселям». Под этим я просто подразумеваю, что если где-то на стене есть белый пиксель, он может создать непреднамеренный путь.

Другой метод (который пришёл ко мне после недолгого размышления) - преобразовать изображение в файл SVG, представляющий собой список путей, нарисованных на холсте. Таким образом, пути могут быть прочитаны в один и тот же список (логические значения), где Trueуказывается путь или стена, Falseуказывающая пространство, которое можно перемещать. Проблема с этим методом возникает, если преобразование не является точным на 100% и не полностью соединяет все стены, создавая промежутки.

Также проблема с преобразованием в SVG заключается в том, что линии не являются «идеально» прямыми. Это приводит к тому, что пути являются кубическими кривыми Безье. Со списком (массивом) логических значений, индексированных целыми числами, кривые не будут легко переноситься, и все точки, которые находятся на кривой, должны быть рассчитаны, но не будут точно соответствовать индексам списка.

Я предполагаю, что хотя один из этих методов может сработать (хотя, вероятно, нет), он ужасно неэффективен, учитывая такое большое изображение, и что существует лучший способ. Как это лучше всего (наиболее эффективно и / или с наименьшей сложностью) сделать? Есть ли даже лучший способ?

Затем идет решение лабиринта. Если я использую любой из первых двух методов, я по сути получу матрицу. Согласно этому ответу , хорошим способом представления лабиринта является использование дерева, а хорошим способом его решения является использование алгоритма A * . Как можно создать дерево из изображения? Любые идеи?

TL; DR
Лучший способ разобрать? В какую структуру данных? Как бы указанная структура помогла / помешала решению?

ОБНОВЛЕНИЕ
Я попробовал свои силы в реализации того, что @Mikhail написал на Python, используя numpy, как рекомендовано @Thomas. Я чувствую, что алгоритм правильный, но он работает не так, как хотелось бы. (Код ниже.) Библиотека PNG - это 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, [])

Вот решение.

1. Преобразуйте изображение в оттенки серого (еще не в двоичном виде), отрегулировав веса для цветов так, чтобы окончательное изображение в градациях серого было примерно одинаковым. Вы можете сделать это просто, управляя ползунками в Photoshop в Image -> Adjustments -> Black & White.
2. Преобразуйте изображение в двоичное, установив соответствующий порог в Photoshop в меню Изображение -> Настройки -> Порог.
3. Убедитесь, что порог выбран правильно. Используйте инструмент Magic Wand Tool с допуском 0, точечный образец, непрерывный, без сглаживания. Убедитесь, что ребра, у которых разрывы выбора не являются ложными ребрами, введены неправильным порогом. Фактически, все внутренние пункты этого лабиринта доступны с самого начала.
4. Добавьте искусственные границы на лабиринт, чтобы виртуальный путешественник не ходил по нему :)
5. Реализация поиска в ширину (BFS) в вашем любимом языке и запустить его с самого начала. Я предпочитаю MATLAB для этой задачи. Как уже упоминалось @Thomas, нет необходимости возиться с регулярным представлением графиков. Вы можете работать с бинаризованным изображением напрямую.

Вот код MATLAB для 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

Это действительно очень просто и стандартно, не должно быть трудностей при реализации этого в Python или чем-то еще.

И вот ответ:

Это решение написано на Python. Спасибо Михаилу за указатели на подготовку изображения.

Анимированный поиск в ширину:

Завершенный лабиринт:

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

Примечание. Отмечает посещаемый пиксель серым цветом. Это устраняет необходимость в посещенном списке, но для этого требуется вторая загрузка файла изображения с диска перед рисованием пути (если вы не хотите составное изображение окончательного пути и всех взятых путей).

Пустой вариант лабиринта, который я использовал.

Я попытался реализовать поиск A-Star для этой проблемы. Внимательно следил за реализацией Джозефом Керном для фреймворка и псевдокода алгоритма, приведенного здесь :

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

Поскольку A-Star - это эвристический алгоритм поиска, вам нужно придумать функцию, которая оценивает оставшуюся стоимость (здесь: расстояние) до достижения цели. Если вам не подходит неоптимальное решение, оно не должно переоценивать стоимость. Консервативный выбор в данном случае - это расстояние в Манхэттене (или такси), поскольку оно представляет прямолинейное расстояние между двумя точками на сетке для используемой окрестности фон Неймана. (Который, в этом случае, никогда не будет переоценивать стоимость.)

Это, однако, значительно недооценило бы фактическую стоимость данного лабиринта под рукой. Поэтому я добавил две другие метрики расстояния в квадрате евклидово расстояние и манхэттенское расстояние, умноженное на четыре для сравнения. Это, однако, может переоценить фактическую стоимость и, следовательно, может привести к неоптимальным результатам.

Вот код:

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

Вот несколько изображений для визуализации результатов (навеянное Джозефом Керном ). Анимации показывают новый кадр каждый раз после 10000 итераций основного цикла while.

Поиск в ширину:

A-Star Манхэттен Расстояние:

Квадрат евклидова расстояния A-Star:

Расстояние A-Star Manhattan, умноженное на четыре:

Результаты показывают, что исследуемые области лабиринта значительно различаются в зависимости от используемой эвристики. Таким образом, квадрат евклидова расстояния даже дает другой (субоптимальный) путь, как и другие метрики.

Что касается производительности алгоритма A-Star с точки зрения времени выполнения до завершения, обратите внимание, что по сравнению с Breadth-First Search (BFS) требуется много оценки функций расстояния и стоимости, которым нужно только оценить «целеустремленность» каждая кандидатская должность. Вопрос о том, перевешивает ли стоимость этих дополнительных оценок функций (A-Star) стоимость проверки большего количества узлов (BFS), и особенно вопрос о том, является ли производительность проблемой для вашего приложения, зависит от индивидуального восприятия. и, конечно, вообще нельзя ответить.

В общем , можно сказать, что осознанный алгоритм поиска (например, A-Star) может быть лучшим выбором по сравнению с исчерпывающим поиском (например, BFS), заключается в следующем. С количеством измерений лабиринта, т. Е. Коэффициентом ветвления дерева поиска, недостаток полного поиска (для полного поиска) возрастает в геометрической прогрессии. С ростом сложности это становится все менее и менее осуществимым, и в какой-то момент вы в значительной степени удовлетворены любым результатом, будь он (приблизительно) оптимальным или нет.

Дерево поиска слишком много. Лабиринт неотделим по пути решения пути.

(Благодаря rainman002 от Reddit за указание на это мне.)

Благодаря этому вы можете быстро использовать подключенные компоненты для идентификации подключенных участков стены лабиринта. Это перебирает пиксели дважды.

Если вы хотите превратить это в красивую диаграмму пути (путей) решения, вы можете использовать двоичные операции со структурирующими элементами, чтобы заполнить пути «тупика» для каждой связанной области.

Демо-код для MATLAB следует. Он может использовать настройку, чтобы лучше очистить результат, сделать его более обобщенным и ускорить его выполнение. (Иногда, когда не 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);

Использует очередь для непрерывного заполнения порога. Вставляет пиксель слева от входа в очередь, а затем запускает цикл. Если пиксель в очереди достаточно темный, он окрашен в светло-серый цвет (выше порога), и все соседи помещаются в очередь.

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

Решением является коридор между серой стеной и цветной стеной. Обратите внимание, что этот лабиринт имеет несколько решений. Кроме того, это просто похоже на работу.

Вот и все: лабиринт-решатель-питон (GitHub)

Я с удовольствием поиграл с этим и продолжил на Джозефе Керне ответ . Не отвлекать от этого; Я просто сделал несколько небольших дополнений для тех, кто может поиграть с этим.

Это решатель на основе Python, который использует BFS, чтобы найти кратчайший путь. Мои главные дополнения, в то время, являются:

1. Изображение очищается перед поиском (т.е. конвертируется в чисто черно-белое)
2. Автоматически генерировать GIF.
3. Автоматически генерировать AVI.

В его нынешнем виде начальная / конечная точки жестко заданы для этого образца лабиринта, но я планирую расширить его так, чтобы вы могли выбрать соответствующие пиксели.

Я бы пошел на вариант матрицы Bools. Если вы обнаружите, что стандартные списки Python слишком неэффективны для этого, вы можете использоватьnumpy.bool вместо этого массив. Память для лабиринта размером 1000x1000 пикселей составляет всего 1 МБ.

Не беспокойтесь о создании каких-либо структур данных дерева или графика. Это просто способ думать об этом, но не обязательно хороший способ представить это в памяти; Булева матрица проще в написании кода и более эффективна.

Затем используйте алгоритм A * для его решения. Для эвристики расстояния используйте Манхэттенское расстояние ( distance_x + distance_y).

Представлять узлы набором (row, column)координат. Всякий раз, когда алгоритм ( псевдокод Wikipedia ) вызывает «соседей», это просто зацикливание на четырех возможных соседях (обратите внимание на края изображения!).

Если вы обнаружите, что это все еще слишком медленно, вы можете попробовать уменьшить масштаб изображения, прежде чем загружать его. Будьте осторожны, чтобы не потерять узкие пути в этом процессе.

Возможно, в Python можно также выполнить масштабирование 1: 2, убедившись, что вы не потеряете возможные пути. Интересный вариант, но нужно немного подумать.

Вот несколько идей.

(1. Обработка изображений :)

1.1 Загрузите изображение в виде карты пикселей RGB . В C # это тривиальное использование system.drawing.bitmap. На языках без простой поддержки обработки изображений просто преобразуйте изображение в формат переносимого растрового изображения (PPM) (текстовое представление Unix, создает большие файлы) или в какой-либо простой двоичный формат файла, который вы можете легко прочитать, например, BMP или TGA . ImageMagick в Unix или IrfanView в Windows.

1.2 Вы можете, как упоминалось ранее, упростить данные, взяв (R + G + B) / 3 для каждого пикселя в качестве индикатора серого тона, а затем пороговое значение для создания черно-белой таблицы. Нечто близкое к 200 при условии, что 0 = черный, а 255 = белый, устранит артефакты JPEG.

(2. Решения :)

2.1 Поиск в глубину: Инициируйте пустой стек с начальным местоположением, соберите доступные последующие ходы, выберите один случайным образом и протолкните в стек, продолжайте до достижения конца или до конца. При возврате в обратном направлении, выталкивая стопку, вы должны отслеживать, какие позиции были посещены на карте, поэтому, когда вы собираете доступные ходы, вы никогда не идете по одному и тому же пути дважды. Очень интересно оживить.

2.2 Поиск в ширину: упоминалось ранее, аналогично описанному выше, но только с использованием очередей. Также интересно оживить. Это работает как заливка в программном обеспечении для редактирования изображений. Я думаю, что вы можете решить лабиринт в Photoshop, используя этот трюк.

2.3 Стеновой элемент: Геометрически говоря, лабиринт представляет собой сложенную / извитую трубу. Если вы будете держать руку на стене, то в конце концов найдете выход;) Это не всегда работает. Есть определенное предположение: идеальные лабиринты и т. Д., Например, некоторые лабиринты содержат острова. Ищи это; это увлекательно

(3. Комментарии :)

Это хитрый. Легко решить лабиринты, если они представлены в некотором простом формальном массиве, где каждый элемент представляет собой тип ячейки с северной, восточной, южной и западной стенами и полем посещенного флага. Однако, учитывая, что вы пытаетесь сделать это с помощью нарисованного от руки эскиза, он становится грязным. Я искренне думаю, что попытка рационализировать эскиз сведет вас с ума. Это похоже на проблемы с компьютерным зрением, которые довольно сложны. Возможно, переход непосредственно на карту изображения может быть проще, но более расточительным.

Вот решение с использованием 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 до оттенков серого, см .: 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")

Вуаля!

Это то, что происходит, если вы не заполните граничные пиксели (Ха!) ...

Полное раскрытие: я задавал и отвечал на очень похожий вопрос сам, прежде чем нашел этот. Затем, благодаря магии SO, нашел этот вопрос одним из лучших «Связанных вопросов». Я думал, что буду использовать этот лабиринт как дополнительный тестовый пример ... Мне было очень приятно узнать, что мой ответ там также работает для этого приложения с очень небольшими изменениями.

хорошим решением было бы то, что вместо того, чтобы находить соседей по пикселям, это делалось бы по ячейке, потому что коридор может иметь 15 пикселей, поэтому в том же коридоре он может выполнять действия, как влево или вправо, тогда как если бы это было сделано, как если бы перемещение был куб, это было бы простое действие, как ВВЕРХ, ВНИЗ, ВЛЕВО ИЛИ ВПРАВО