这是使用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的魔力,发现这是最重要的“相关问题”之一。我以为我会把这个迷宫作为一个额外的测试用例...我很高兴地发现,我的答案也几乎不需要修改就能用于该应用程序。
0
代表并解决给定图像的迷宫的最佳方法是什么?
给定一个JPEG图像(如上所示),读取它,将其解析为某种数据结构并解决迷宫的最佳方法是什么?我的第一个本能是逐像素读取图像并将其存储在布尔值列表(数组)中:对于白色像素为
True
,对于非白色像素为False
(可以丢弃颜色)。这种方法的问题在于图像可能不是“像素完美”的。我的意思只是说,如果墙壁上某处有一个白色像素,可能会产生意外的路径。另一种方法(经过一番思考后才想到)是将图像转换为SVG文件-这是在画布上绘制的路径的列表。这样,可以将路径读入相同的列表(布尔值)中,其中
True
表示路径或墙壁,False
表示可移动的空间。如果转换不是100%准确,并且不能完全连接所有墙,从而产生间隙,则此方法会出现问题。转换为SVG的另一个问题是这些线不是“完美”的直线。这导致路径是三次贝塞尔曲线。使用由整数索引的布尔值列表(数组),曲线将不易转移,并且必须计算曲线上直线的所有点,但不会与列表索引完全匹配。
我假设虽然其中一种方法可能会(虽然可能不会)起作用,但鉴于如此大的图像,它们的效率很低,并且存在更好的方法。如何做到最好(最有效和/或最低复杂度)?有没有最好的方法?
然后是迷宫的解决。如果我使用前两种方法中的任何一种,则基本上将得到一个矩阵。根据此答案 ,表示迷宫的一种好方法是使用树,而使用A *算法来解决它的好方法。一个人如何根据图像创建一棵树?有任何想法吗?
TL; DR
解析的最佳方法?变成什么数据结构?所述结构将如何帮助/阻碍解决?
更新
我已经尝试使用@Thomas推荐的
numpy
实现@Mikhail用Python编写的内容。我认为该算法是正确的,但无法正常运行。 (下面的代码。)PNG库是PyPNG 。