迷宫问题图解 : 基于骨架提取、四邻域

目录

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 ？

一开始的时候，这个地方卡了很久。

后来想到了下面这种邻域移除的方法，不能保证完全正确，但能处理自己预期的迷宫问题...

OK，here 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 循环移除分支

这里设置的是一次移除所有分支的端点，想要移除分支，只需要重复这个过程即可

1. 找到所有分支的端点
2. 移除这些端点
3. 找到新的端点
4. 移除新的端点...
5. 重复这个过程

循环处理的代码为：

最后处理的结果为：

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]],dtype=np.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_up+dst_down+dst_right+dst_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[i+1,j] + img[i,j-1]+img[i,j+1] == 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邻域加起来等于 1

4.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), interpolation=cv2.INTER_LINEAR)             # 将图像设定到固定大小_, img_pre = cv2.threshold(img_pre, 0, 255, cv2.THRESH_BINARY+cv2.THRESH_OTSU)  # 阈值处理kernel = cv2.getStructuringElement(cv2.MORPH_CROSS,(3,3))img_pre = cv2.erode(img_pre,kernel,iterations=2)                                # 腐蚀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_up+dst_down+dst_right+dst_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[i+1,j] + img[i,j-1]+img[i,j+1] == 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：

• 骨架抽取选择细化是因为，其余的方法可能会产生不连续的骨架，导致迷宫求解失败