当前位置： 首页 > news >正文

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

news 2025/9/11 16:36:26

目录

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：

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

http://www.lryc.cn/news/12630.html

相关文章：

  • 设计模式 - 如何在库和主程序之间互相调用数据和函数
  • Redis面试题：1~2亿条数据需要缓存，请问如何设计这个存储案例
  • 程序员必备的软技能-《如何阅读一本书》
  • Java数据结构-栈、队列常用类（Stack、ArrayDeque、LinkedLList）
  • 拯救了大批爬虫程序员，因为一个简单的神器
  • 2023年美赛C题Wordle预测问题三、四建模及Python代码详细讲解
  • 相关性-回忆录（持续更新）
  • (必备技能)使用Python实现屏幕截图
  • 「数据仓库」怎么选择现代数据仓库?
  • 6.3 使用 Swagger 生成 Web API 文档
  • Day894.加锁规则的一些问题 -MySQL实战
  • 【Flutter入门到进阶】Dart进阶篇---Dart异步编程
  • 点云配准方法原理（NDT、ICP）
  • 大规模 IoT 边缘容器集群管理的几种架构-0-边缘容器及架构简介
  • 代码随想录算法训练营第45天动态规划 背包基础 1 2、 416. 分割等和子集
  • QT学习记录(六）类对象属性
  • Spring Cloud Alibaba从搭建到源码完整进阶教程
  • Spring Cloud Nacos实战（一）- 下载和安装
  • 深入理解设备像素比
  • Revisiting Distributed Synchronous SGD 带有Back-up机制的分布式同步SGD方法 论文精读
  • shiro CVE-2020-13933
  • 斐波那契数列(递归+迭代)
  • 2022黑马Redis跟学笔记.实战篇(六)
  • Linux-VMware常用设置(时间+网络)及网络连接激活失败解决方法-基础篇②
  • vue3学习总结1
  • SpringBoot统一功能处理
  • 2022年3月电子学会Python等级考试试卷（五级）答案解析
  • 【C++】智能指针
  • Seata架构篇 - AT模式
  • 加油站会员管理小程序实战开发教程12