新郑市网站建设,自适应网站模板公司,网站访客抓取系统,用wordpress插件推荐目录
1. 迷宫的连通域
2. How to remove branch #xff1f;
3. 基于4邻域的 remove 分支
3.1 找到分支的端点
3.2 4邻域的 remove 分支
3.3 循环移除分支
3.4 code
4. 迷宫路线
4.1 预处理
4.2 提取骨架
4.3 分支的端点
4.4 去除分支的端点
4.5 循环去除分支
4…目录
1. 迷宫的连通域
2. How to remove branch
3. 基于4邻域的 remove 分支
3.1 找到分支的端点
3.2 4邻域的 remove 分支
3.3 循环移除分支
3.4 code
4. 迷宫路线
4.1 预处理
4.2 提取骨架
4.3 分支的端点
4.4 去除分支的端点
4.5 循环去除分支
4.6 迭代过程展示
4.7 结果展示
4.8 代码
5. show
6. Acknowledge 1. 迷宫的连通域
之前对迷宫求解的问题感兴趣看了很多求解的算法大部分都是深度搜索啥的。
由于本人对算法不是很敏感因此想看看能不能将自己所学的和迷宫问题联系起来。从俯视的角度来看迷宫就是一直2d图片既然是图像就可以尝试使用数字图像处理的方法来解决。 例如一副迷宫图像黑色的是围墙白色的是道路。 迷宫求解其实就是在白色的像素域中找到一条可以连接出入口的连通域 连通域很好找这里不再介绍opencv里面也有专门的函数找连通域。
但是问题就是往往这种连通域里面有很多的分支会将迷宫路线走向死路。所以现在求解迷宫问题的思路就是如何将分支去除 2. How to remove branch
一开始的时候这个地方卡了很久。
后来想到了下面这种邻域移除的方法不能保证完全正确但能处理自己预期的迷宫问题...
OKhere we go ....
当时想了很久其实我当时一直陷入了一个误区。
例如从A点走到B点显然红线是唯一的路径两条黑线就是死路。所以问题是在这一条连通域当中怎么去除黑线只保留红线。 当时想了很多例如距离变换中草原大火的概念从端点开始点火或者计算连通域当中像素点的个数只保留最大的那条连通域等等。问题是这条红色的线是人为标记出来的能通的路线对计算机来看黑色和红色的线没有任何差异所以之前的想法压根不起作用。 在误区里面卡了很久后来在一副图里面突然有了灵感类似下面这种的闪电图。 从这幅图来看其实天空就是迷宫的起点大地就是迷宫的出口。闪电划过有一道连接了天空和大地就是迷宫的解其余的分支就是迷宫中对应的死路。 这样看这副闪电图片很容易联想到树枝主干长成后分支慢慢向四周长开。
类似这个闪电图假设图中最粗的主干迷宫解的路线是最先形成的其余的细小的分支是慢慢从主干上形成的。那么去除这些分支不就是从分支的端点慢慢向主干靠拢的过程吗(相当于分支形成的逆过程) 简单来说就是找到所以分支的端点然后顺着分支慢慢往回走直到走到主干上这条分支就被消除了。 3. 基于4邻域的 remove 分支
一般来说迷宫都是上下左右的道路这里不考虑那些斜着走的迷宫。
这里用数组建立一个小型的迷宫为下面展示用 3.1 找到分支的端点
这里先来介绍如何找到分支的端点
因为迷宫都是上下左右的路线那么对于分支来说端点只有四种情况。
红色代表主干黑色是分支端点的四种情况A、B、C、D
A就是分支是从右往左走的端点B就是分支是从左往右走的端点C就是分支是从下往上走的端点D就是分支是从上往下走的端点因为端点只有这四种情况那么找到端点只需要找到匹配的模板就行了。因此 找端点这里利用 形态学 - 击中-击不中变换 特性 击中-击不中 变换大概的意思就是和 kernel 一样的图像区域会被显示不一样的显示为背景。 击中-击不中的kernel中1代表前景0代表不感兴趣的点、-1代表背景点 这里代码很简单不做解释。就是将四周分支端点的情况放在 3 * 3 的模板里面和原图去匹配即可。
但是分支要注意一点因为出入口其实也是一个端点只不过是主干的端点。所以这里要去除这两个点这里假设出入口就在图片的四周上 注意出入口必须在整幅图像的四周。 利用击中击不中特性找到的端点为 3.2 4邻域的 remove 分支
现在来看看怎么移除这些分支
因为这里考虑的迷宫路线都是上下左右的线路
因此只要在端点的4邻域中找到可以走的道路那么一定就是分支也就是要移除的路线。
那么问题来了怎么知道分支已经结束了呢或者说怎么判断分支走到了主干上
很简单因为分支一定是从主干的的中间分出来的。也就是说分支连接在主干的端点肯定有两条路可以走一个通到出口一个通到入口。对应于数字图像的表达就是从远离主干的分支端点出发如果4邻域中只有一个可以通的道路那么这个点在分支上。如果这个点4邻域有两个或者以上的点那么这个点在主干上。
代码如下 这里要传入两张图片一个是find_corner返回的端点图一个是原图。
因为这里迷宫的可以走的路线设置为1因此如果4邻域上的只有一个可以走的路那么4邻域加起来等于1 3.3 循环移除分支
这里设置的是一次移除所有分支的端点想要移除分支只需要重复这个过程即可
找到所有分支的端点移除这些端点找到新的端点移除新的端点...重复这个过程
循环处理的代码为 最后处理的结果为 3.4 code
import numpy as np
import cv2# 建立迷宫0为墙壁1为道路
img np.array([[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0],[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0],[0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0],[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0],[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]],dtypenp.uint8)# 拷贝地图
source img.copy()# 找到分支的端点
def find_corner(x):kernel_right np.array([[0, -1, 0], [1, 1, -1], [0, -1, 0]]) # rightdst_right cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_right)kernel_left np.array([[0, -1, 0], [-1, 1,1], [0, -1, 0]]) # leftdst_left cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_left)kernel_up np.array([[0, 1, 0], [-1, 1, -1], [0, -1, 0]]) # updst_up cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_up)kernel_down np.array([[0, -1, 0], [-1, 1, -1], [0, 1, 0]]) # downdst_down cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_down)dst dst_updst_downdst_rightdst_left# 去除出入口dst[0,:] 0 # 去除上面dst[-1,:] 0 # 去除下面dst[:,0] 0 # 去除左面dst[:,-1] 0 # 去除右面return dst.astype(np.uint8)# 去除一次端点
def branch(corner_img,img):x,y np.where(corner_img)for i,j in zip(x,y): # 各个角点的坐标if (img[i-1,j] img[i1,j] img[i,j-1]img[i,j1] 1):img[i,j] 0return img# 去除分支
while True:img_copy img.copy() # 拷贝地图用作退出循环ret find_corner(img) # 找到端点img branch(ret,img) # 去除端点if (img_copy img).all(): # 如果两次结果相同则退出循环breakprint(source)
print(img)4. 迷宫路线
将代码修改即可绘制出图像的迷宫路线 4.1 预处理
首先将图像进行预处理 首先将图像进行缩放阈值处理将图像变成二值图像腐蚀可以增大背景图像缩小前景像素点。为下面的细化减少运算量也可以突出迷宫的最外层墙壁最后将像素点变成0 1 二值图像。因为四邻域中设置的是4邻域加起来等于 14.2 提取骨架
提取迷宫道路的骨架可以方便更好的找出路线
具体的参考形态学 - 细化
细化算法需要的kernel 循环做击中击不中变换找到骨架 4.3 分支的端点
和之前的一样 4.4 去除分支的端点 4.5 循环去除分支 4.6 迭代过程展示 4.7 结果展示 4.8 代码
完整代码
import numpy as np
import cv2# 预处理
def pre_process(x):img_pre cv2.resize(x, (400, 400), interpolationcv2.INTER_LINEAR) # 将图像设定到固定大小_, img_pre cv2.threshold(img_pre, 0, 255, cv2.THRESH_BINARYcv2.THRESH_OTSU) # 阈值处理kernel cv2.getStructuringElement(cv2.MORPH_CROSS,(3,3))img_pre cv2.erode(img_pre,kernel,iterations2) # 腐蚀dst img_pre / 255 # 将像素值变成 0 1return dst.astype(np.uint8)# 提取骨架
def thin(img): # 细化算法# 8 个细化 kernelB1 np.array([[-1, -1, -1], [0, 1, 0], [1, 1, 1]])B2 np.array([[0, -1, -1], [1, 1, -1], [1, 1, 0]])B3 np.array([[1, 0, -1], [1, 1, -1], [1, 0, -1]])B4 np.array([[1, 1, 0], [1, 1, -1], [0, -1, -1]])B5 np.array([[1, 1, 1], [0, 1, 0], [-1, -1, -1]])B6 np.array([[0, 1, 1], [-1, 1, 1], [-1, -1, 0]])B7 np.array([[-1, 0, 1], [-1, 1, 1], [-1, 0, 1]])B8 np.array([[-1, -1, 0], [-1, 1, 1], [0, 1, 1]])while True: # 循环迭代tmp img # 将上一步的操作暂存for i in range(8): # 循环迭代八次ret1 cv2.morphologyEx(img, cv2.MORPH_HITMISS, B1) # B1 对图像做 击中-击不中变换ret1 img - ret1 # 原图 减去 上一步击中-击不中的结果ret2 cv2.morphologyEx(ret1, cv2.MORPH_HITMISS, B2) # 将上步的结果作为新的输入ret2 ret1 - ret2ret3 cv2.morphologyEx(ret2, cv2.MORPH_HITMISS, B3)ret3 ret2 - ret3ret4 cv2.morphologyEx(ret3, cv2.MORPH_HITMISS, B4)ret4 ret3 - ret4ret5 cv2.morphologyEx(ret4, cv2.MORPH_HITMISS, B5)ret5 ret4 - ret5ret6 cv2.morphologyEx(ret5, cv2.MORPH_HITMISS, B6)ret6 ret5 - ret6ret7 cv2.morphologyEx(ret6, cv2.MORPH_HITMISS, B7)ret7 ret6 - ret7ret8 cv2.morphologyEx(ret7, cv2.MORPH_HITMISS, B8)ret8 ret7 - ret8img ret8 # 八次迭代完成 保存结果if (img tmp).all(): # 如果所有结构元遍历的结果不再发生变化则操作完成dst img # 保留细化结果breakreturn dst.astype(np.uint8)# 找到端点
def find_corner(x):kernel_right np.array([[0, -1, 0], [1, 1, -1], [0, -1, 0]]) # rightdst_right cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_right)kernel_left np.array([[0, -1, 0], [-1, 1,1], [0, -1, 0]]) # leftdst_left cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_left)kernel_up np.array([[0, 1, 0], [-1, 1, -1], [0, -1, 0]]) # updst_up cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_up)kernel_down np.array([[0, -1, 0], [-1, 1, -1], [0, 1, 0]]) # downdst_down cv2.morphologyEx(x, cv2.MORPH_HITMISS, kernel_down)dst dst_updst_downdst_rightdst_leftdst[0,:] 0 # 去除上面dst[-1,:] 0 # 去除下面dst[:,0] 0 # 去除左面dst[:,-1] 0 # 去除右面return dst.astype(np.uint8)# 去除一次分支
def branch(corner_img,img):x,y np.where(corner_img)for i,j in zip(x,y): # 各个角点的坐标if (img[i-1,j] img[i1,j] img[i,j-1]img[i,j1] 1):img[i,j] 0return imgimg cv2.imread(c.png,0) # 读取图像
img pre_process(img) # 预处理之后的图像
source img.copy() # 拷贝图像
img thin(img)# 去除分支
while True:img_copy img.copy() # 拷贝原图,用于退出循环ret find_corner(img) # 找到角点img branch(ret,img) # 去除角点# 显示路线的过程#cv2.imshow(img, img * 255)#cv2.waitKey()if (img_copy img).all():breaksource * 255
dst source img *120
cv2.imshow(img,np.hstack((source,dst)))
cv2.waitKey()
cv2.destroyAllWindows() 5. show
这里是网上找到迷宫和利用代码找到的迷宫解法 6. Acknowledge
存在的问题
输入的迷宫图片必须按照指定的格式。例如图片的四周必须是墙壁且出入口在四周迷宫需要保证黑色为墙壁白色为道路。迷宫的走法是上下左右没有斜着走的Tips
骨架抽取选择细化是因为其余的方法可能会产生不连续的骨架导致迷宫求解失败
