Представление и решение лабиринта данного изображения
Как лучше всего представить и решить лабиринт с заданным изображением?
Учитывая изображение в формате 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, [])
9 ответов
Вот решение.
- Преобразуйте изображение в оттенки серого (еще не в двоичном виде), отрегулировав веса для цветов так, чтобы окончательное изображение в градациях серого было примерно одинаковым. Вы можете сделать это просто, управляя ползунками в Photoshop в разделе Изображение -> Настройки -> Черно-белый.
- Преобразуйте изображение в двоичное, установив соответствующий порог в Photoshop в меню Изображение -> Настройки -> Порог.
- Убедитесь, что порог выбран правильно. Используйте инструмент Magic Wand Tool с допуском 0, точечный образец, непрерывный, без сглаживания. Убедитесь, что ребра, у которых разрывы выбора не являются ложными ребрами, введены неправильным порогом. Фактически, все внутренние точки этого лабиринта доступны с самого начала.
- Добавьте искусственные бордюры в лабиринт, чтобы виртуальный путешественник не ходил по нему:)
- Реализуйте поиск в ширину (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);
Вот и все: лабиринт-решатель-питон (GitHub)
Я с удовольствием поиграл с этим и расширил ответ Джозефа Керна. Не отвлекать от этого; Я просто сделал несколько небольших дополнений для тех, кто может поиграть с этим.
Это решатель на основе Python, который использует BFS, чтобы найти кратчайший путь. Мои основные дополнения, в то время, являются:
- Изображение очищается перед поиском (т.е. конвертируется в чисто черно-белый)
- Автоматически генерировать GIF.
- Автоматически генерировать AVI.
В нынешнем виде начальные / конечные точки жестко запрограммированы для этого образца лабиринта, но я планирую расширить его так, чтобы вы могли выбрать соответствующие пиксели.
Использует очередь для непрерывного заполнения порога. Вставляет пиксель слева от входа в очередь, а затем запускает цикл. Если пиксель в очереди достаточно темный, он окрашен в светло-серый цвет (выше порога), и все соседи помещаются в очередь.
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")
Решением является коридор между серой стеной и цветной стеной. Обратите внимание, что этот лабиринт имеет несколько решений. Кроме того, это просто, кажется, работает.
Я бы пошел на вариант матрицы 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 Поиск в глубину: Инициируйте пустой стек с начальным местоположением, соберите доступные последующие ходы, выберите один случайным образом и протолкните в стек, продолжайте, пока не будет достигнут конец или отступление. При возврате deadend путем выталкивания стека вы должны отслеживать, какие позиции были посещены на карте, поэтому, когда вы собираете доступные ходы, вы никогда не идете по одному и тому же пути дважды. Очень интересно оживить.
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://stackru.com/images/ef5d9b6db99cd397636dcbe488120a7667d20876.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 до оттенков серого, см.: /questions/31903217/konvertirovat-jpg-v-csv-v-ottenkah-serogo-ispolzuya-r/31903233#31903233
# 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 пикселей, поэтому в том же коридоре он может выполнять такие действия, как влево или вправо, а если бы это было сделано, как если бы смещение был кубом, это было бы простое действие, например ВВЕРХ, ВНИЗ, ВЛЕВО ИЛИ ВПРАВО