基于OpenCV的迷宫图像建模与最短路径算法实现

简介面向《数据结构与算法》课程大作业的完整工程包题目是基于机器视觉完成迷宫地图建模与路径计算通过摄像头拍摄黑墙白路的32×32迷宫图借助OpenCV处理生成0/1矩阵再以合适数据结构抽象道路网络求解可达路径与最短路径。代码已测试运行适合计科、人工智能等专业学生用于课设、毕设或算法综合实验也可供入门机器视觉与图算法结合的开发者参考学习。资源共12个文件以Python脚本为主体覆盖图像转矩阵、轮廓识别、DFS/BFS路径搜索等环节另有迷宫样例图、CSV结果与说明文档压缩包仅29KB轻量但流程完整。内容从OpenCV配置与图像处理方法到图的建模和最短路径求解均有体现已有254人浏览学习。读者拿到后可直接对照源码理解每个模块也可将其改造成其他迷宫/网格路径规划场景。1. 迷宫大作业从图像到路径为什么值得选这个方向数据结构大作业里迷宫是最常见的选题之一但绝大多数人交上去的都是「二维数组 DFS」用一个 char 矩阵手绘迷宫再写个递归搜索。这种做法不是不对而是太单薄——数据结构只用到数组算法只写了递归图的建模、输入处理、搜索优化全都没有涉及。基于机器视觉的迷宫地图建模与路径计算是把图像识别、图的构建、最短路径搜索三件事串成一条流水线的选题拍一张迷宫照片或程序生成一张迷宫图程序自动提取走道、建出图结构、算出路径并在原图上画出来。这个方向适合想冲高分、或者想顺手把 OpenCV 基础学会的从业者工作量可控但每个环节都有足够的深度写进文档说明。2. 数据建模先行迷宫为什么必须转成图而不是死磕二维数组2.1 二维数组表示和图表示差异在哪迷宫最简单的表示是二维数组#表示墙、空格表示路DFS 直接对着矩阵递归。这种表示的优点是直观缺点是信息冗余搜索要访问整个矩阵迷宫的连通性、环、割点这些结构特征完全体现不出来。数据结构课真正想考察的图论知识在这种表示里无处安放。图表示则是把迷宫抽象成G (V, E)岔路口和死胡同端点是节点走道段是边。转换成图之后BFS、DFS、Dijkstra、A* 这些算法才真正有了用武之地问题从「在格子矩阵里走」变成「在图上找最短路径」复杂度分析、数据结构选型、算法对比这些大作业评分点也全都能展开了。实际做法是两层转换图像先变成二维数组走道/墙的像素掩码二维数组再变成图。二维数组作为中间表示存在图作为最终搜索的数据结构谁都不耽误。2.2 三层流水线图像层、建模层、搜索层一个完整的视觉迷宫方案我会拆成三条清晰的流水线层级输入输出核心任务图像层迷宫照片/图片单像素宽的走道骨架灰度化、二值化、去噪、骨架提取建模层走道骨架邻接表 节点坐标表识别节点、追踪边、计算边权搜索层邻接表 起终点路径节点序列BFS/Dijkstra/A* 搜索并回映射坐标分层最大的好处是每一层都能单独调试。图像层出了问题看二值图和骨架图建模层出了问题把节点和边画出来检查搜索层出了问题打印路径节点序列。如果三层混在一起写任何一步出错都要从头查起排错成本会翻好几倍。2.3 邻接矩阵还是邻接表按大作业规模做选择迷宫图通常是稀疏图。一个 30×30 的迷宫通道节点往往不到 200 个、边不到 300 条用邻接矩阵 200×200 也才 4 万个格子完全放得下。但如果你把图片分辨率拉高、迷宫做到 100×100节点上千之后邻接矩阵的空间和时间开销就会明显上升。我的建议是直接用邻接表Python 里用字典套列表写作{node_id: [(neighbor_id, weight), ...]}。原因有两个一是大作业要体现你懂稀疏图为什么用邻接表二是 BFS 在邻接表上的复杂度是O(V E)视觉迷宫的规模下搜索耗时是毫秒级性能完全不是瓶颈。文档说明里把邻接表和邻接矩阵的空间复杂度对比写清楚本身就是加分项。3. 用 OpenCV 做迷宫地图建模图像预处理到邻接表的完整流水线3.1 预处理高斯模糊、Otsu 二值化的参数怎么设先定输入约定迷宫图最好是白底黑线、走道宽度一致、墙线闭合这样图像层处理稳定很多。实际照片有光照不均和透视变形我会先做一个裁边和矫正再用固定流程处理。第一步是读图、转灰度、高斯模糊import cv2 import numpy as np # 读取迷宫图像转为灰度 img cv2.imread(maze.png) gray cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) # 高斯模糊去噪核大小按走道宽度调整 blurred cv2.GaussianBlur(gray, (5, 5), 0) # Otsu 自适应求阈值自动区分前景和背景 _, binary cv2.threshold(blurred, 0, 255, cv2.THRESH_BINARY_INV cv2.THRESH_OTSU)这里有个关键参数THRESH_BINARY_INV表示黑线变白、白底变黑这样走道区域就是前景。高斯核(5, 5)对大部分迷宫图够用如果图片噪声多可以加到(7, 7)核太大会把细走道磨断。Otsu 会自动算阈值省去了手动调127这种玄学参数的痛苦。处理后如果发现走道有断口、小噪点用形态学闭运算补一下kernel np.ones((3, 3), np.uint8) binary cv2.morphologyEx(binary, cv2.MORPH_CLOSE, kernel, iterations1)闭运算先膨胀再腐蚀能把走道上的小裂缝填上同时不改变走道整体形状。3.2 骨架提取自己写 Zhang-Suen 细化算法二值化后的走道有十几像素宽直接做节点识别会得到一堆重复点。需要先把走道缩成单像素宽的骨架。OpenCV 没有内置骨架化函数有个偷懒的办法是skimage.morphology.skeletonize一行调用完事。但大作业文档说明里没东西可写所以我会自己实现 Zhang-Suen 细化算法大约 50 行算法理解能写进文档代码也能展示功底。def zhang_suen(binary): img binary // 255 changed True while changed: changed False # 第一步删除上边界与左边界候选点 for i in range(1, img.shape[0] - 1): for j in range(1, img.shape[1] - 1): if img[i, j] 0: continue p [img[i-1, j], img[i-1, j1], img[i, j1], img[i1, j1], img[i1, j], img[i1, j-1], img[i, j-1], img[i-1, j-1]] if 2 sum(p) 6 and p[0] p[2] p[4] 1 \ and p[2] p[4] p[6] 1 and p[0::2].count(0) 1 \ and p[2::2].count(0) 1: img[i, j] 0 changed True # 第二步删除下边界与右边界候选点条件同上但轮转 for i in range(1, img.shape[0] - 1): for j in range(1, img.shape[1] - 1): if img[i, j] 0: continue p [img[i-1, j], img[i-1, j1], img[i, j1], img[i1, j1], img[i1, j], img[i1, j-1], img[i, j-1], img[i-1, j-1]] if 2 sum(p) 6 and p[0] p[2] p[4] 1 \ and p[2] p[4] p[6] 1 and p[1::2].count(0) 1 \ and p[3::2].count(0) 1: img[i, j] 0 changed True return img * 255算法逻辑是迭代删除走道边缘像素但保留连通性。2 sum(p) 6保证不会删掉端点p[0::2].count(0)这类条件保证删除的是边界而不是内部孔洞。两层循环纯 Python 跑起来慢一点但 1000×1000 的图也就几秒大作业完全能接受。文档里我会写一句实际生产可以向量化这里用可读性优先的版本。3.3 节点识别与边追踪从骨架生成邻接表骨架出来了下一步是识别节点。对每个前景像素统计 8 邻域中前景像素的个数个数为 1 是端点入口、出口、死胡同尽头个数大于 2 是交叉点岔路口个数为 2 是普通走道中间点。端点和交叉点就是图的顶点。H, W skeleton.shape neighbor_count np.zeros((H, W), dtypenp.uint8) for i in range(1, H - 1): for j in range(1, W - 1): if skeleton[i, j] 0: continue window skeleton[i-1:i2, j-1:j2] # 减去自身得到真实邻域前景数 neighbor_count[i, j] window.sum() // 255 - 1 # 节点像素集合端点(1个邻域)或交叉点(2个邻域) node_mask (neighbor_count 1) | (neighbor_count 2) node_coords np.argwhere(node_mask)得到节点像素后把距离很近的节点合并避免骨架毛刺造成一簇伪节点。然后从每个节点出发沿 8 邻域追踪走道直到遇到另一个节点这条路就是一条边像素距离作为边权def trace_edge(skeleton, start_node, node_set): 从节点出发沿走道追踪到另一节点返回路径像素列表 path [start_node] prev, cur start_node, None # 8 邻域偏移 dirs [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] # 找到第一个可走的前进方向 for d in dirs: nb (start_node[0] d[0], start_node[1] d[1]) if skeleton[nb[0], nb[1]]: cur nb break if cur is None: return [] while tuple(cur) not in node_set: path.append(tuple(cur)) # 找下一个未访问的前景点 next_node None for d in dirs: nb (cur[0] d[0], cur[1] d[1]) if nb prev or skeleton[nb[0], nb[1]] 0: continue next_node nb break if next_node is None: break prev, cur cur, next_node path.append(tuple(cur)) return path注意node_set是合并后节点坐标的集合用来判断追踪终点。边权我用欧氏距离像素点数量但也可以直接用走过的像素数两种都能跑 Dijkstra。追踪完之后把边加进邻接表建图完成。4. 路径计算实现BFS、Dijkstra 与 A* 选型和核心代码4.1 三种搜索算法怎么选无权图 BFS、有权图 Dijkstra、带启发式的 A*图建好了路径计算就是数据结构课的核心内容。三种算法各有适用场景算法适用场景复杂度大作业里的定位BFS无权图 / 边权相同O(VE)主推方案体现队列应用Dijkstra带权图像素距离作为边权O((VE)logV)体现贪心与优先队列A*带权图 已知目标坐标O(E)实际远小于 Dijkstra体现启发式设计加分项视觉迷宫的边是按像素距离加权的理论上 BFS 忽略权重找的是「边数最少」的路径不一定是像素最短。但大作业里迷宫规模不大BFS 跑的路径看起来也很合理。我的建议是主写 BFS 加 Dijkstra 的对比文档里讨论「边数最短 vs 距离最短」的差异再把 A* 作为进阶内容。4.2 BFS 最短路径代码与回溯逻辑BFS 需要三个数据结构队列、访问集合、前驱字典。前驱字典是路径回溯的关键parent[neighbor] node记录每个节点第一次被访问时来自谁最后从终点一路回退到起点。from collections import deque def bfs_shortest_path(graph, start, end): 图最短路径搜索graph 是邻接表 {node: [(neighbor, weight), ...]} queue deque([start]) visited {start} parent {start: None} while queue: node queue.popleft() if node end: break for neighbor, _ in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) parent[neighbor] node queue.append(neighbor) if end not in parent: return None # 起点终点不连通 # 回溯路径 path [] cur end while cur is not None: path.append(cur) cur parent[cur] path.reverse() return path这里visited用集合去重避免同一个节点被重复入队parent用字典记录前驱。BFS 第一次访问到end时路径一定最短因为队列按层展开首次到达目标就是最小层数。返回路径是节点 ID 列表之后映射成像素坐标画图。4.3 A* 与曼哈顿距离的实现要点A* 在 Dijkstra 基础上加了启发式函数搜索会优先朝终点方向扩展大迷宫里试探的死胡同节点明显变少。启发式我用曼哈顿距离迷宫走道只能上下左右走曼哈顿距离是可采纳的不会高估真实距离。import heapq def a_star(graph, start, end, coords): coords: {node: (x, y)}用于计算启发式距离 def heuristic(a, b): return abs(coords[a][0] - coords[b][0]) abs(coords[a][1] - coords[b][1]) heap [] heapq.heappush(heap, (heuristic(start, end), start)) g_score {start: 0} parent {start: None} while heap: _, node heapq.heappop(heap) if node end: break for neighbor, weight in graph.get(node, []): tentative g_score[node] weight if neighbor not in g_score or tentative g_score[neighbor]: g_score[neighbor] tentative parent[neighbor] node f tentative heuristic(neighbor, end) heapq.heappush(heap, (f, neighbor)) if end not in parent: return None path [] cur end while cur is not None: path.append(cur) cur parent[cur] path.reverse() return pathheapq里元组的第一个元素是f g h优先队列自动按 f 值出队。注意同一个节点可能被重复推入堆中因为找到了更短的 g 值但g_score只保留最优值不会出错。A* 跑在像素距离加权的图上结果是真正的最短像素路径。4.4 把路径节点映射回原图并画线搜索返回的是节点 ID 列表每个节点 ID 对应一组像素坐标。把路径上相邻节点的坐标连线画到原图上就完成了可视化。这一步我建议用颜色区分起点终点和路径起点画绿点、终点画红点、路径画红线。def draw_path_on_image(img, path_nodes, node_coords_map): result img.copy() pts [node_coords_map[n] for n in path_nodes] # 画路径线宽度 3 像素 for i in range(len(pts) - 1): cv2.line(result, pts[i], pts[i1], (0, 0, 255), 3) # 标记起点和终点 cv2.circle(result, pts[0], 6, (0, 255, 0), -1) cv2.circle(result, pts[-1], 6, (0, 0, 255), -1) return resultnode_coords_map是节点 ID 到(x, y)像素坐标的映射建图时就应该维护好。画线用的是cv2.line颜色用 BGR 表示红色是(0, 0, 255)。5. 避坑视觉迷宫最容易翻车的五个问题与排查方法5.1 光照不均导致二值化断裂现象同一张图左侧走道连续清晰右侧出现大段空白骨架在右侧断成好几截路径搜索直接报「起点终点不连通」。原因全局阈值对手照片的光照不均匀非常敏感靠一个固定阈值无法同时处理亮部和暗部。解决优先用 Otsu 自动阈值而不是手写127。如果 Otsu 还不够改成cv2.adaptiveThreshold按局部区域计算阈值。另外在二值化前先高斯模糊减少光照渐变造成的灰度波动。5.2 骨架毛刺产生伪交叉点现象节点识别结果里一条笔直的通道上出现十几个「交叉点」导致图结构里有大量短边和死胡同分支。原因二值化边缘有锯齿骨架算法在粗糙边缘上会留出小毛刺每个毛刺顶端都是端点分叉处就是假交叉点。解决二值化后先做形态学开运算去掉毛刺再骨架化。节点识别后做合并距离小于 5 像素的节点归并成一个以坐标均值为新节点位置。这一步能消灭绝大多数伪节点。5.3 外墙与内部墙线粗细不一致现象迷宫外边框比内部墙线粗很多二值化后外框变成一整块实心区域骨架在外框处糊成一团节点识别把整条外框当成一个巨大节点。原因图片生成或拍照时外框线宽和内墙不同预处理没有做线宽归一化。解决规定输入格式要求墙线宽度一致。如果不能保证先用形态学腐蚀把粗线变细。或者先检测最外层轮廓把外框单独提取出来再处理内部区域。5.4 正环和死角分支让搜索动画来回试探现象A* 和 BFS 都能跑通但可视化时看到搜索过程把大量时间花在迷宫角落的死胡同里一遍遍进去又退出来。原因死胡同在图上表现为叶子节点BFS 会自然把它们全部入队这是算法特性不是 bug。解决如果搜索前允许预处理做一个「叶子修剪」——所有度为 1 且不是起终点的节点可以直接从图中删掉连带边一起删。删掉一批叶子后可能出现新的叶子反复迭代直到没有叶子。这个操作本质上是图论里的去枝写进文档能体现你理解图的拓扑结构。5.5 调试习惯每一步都保存中间图现象最终路径画出来明显不对比如穿墙、绕远路、起点终点标反但代码逻辑看着没毛病很难定位是哪一层出的问题。原因管道式处理的通病任何一层的输出异常都会在最后一步集中爆发。解决强制自己每层输出中间结果。图像层存灰度图、二值图、骨架图建模层把节点和边画在骨架图上搜索层打印路径节点和总代价。我的习惯是代码里留一个debug开关跑debugTrue时每步保存debug_01_gray.jpg、debug_02_binary.jpg这种递增命名的文件一眼就能看到哪个环节翻车了。6. 进阶收尾搜索动画可视化与随机迷宫批量验证6.1 把 BFS 搜索过程渲染成视频路径画出来之后只能证明算法正确想看搜索过程的同学可以把 BFS 的状态逐帧渲染成视频。做法是每次出队和入队时在图上画当前访问的节点集合用cv2.VideoWriter写入 MP4video cv2.VideoWriter(bfs_search.mp4, cv2.VideoWriter_fourcc(*mp4v), 30, (W, H)) while queue: # 每次弹出节点后画当前队列状态 frame img.copy() for node in visited: cv2.circle(frame, node_coords_map[node], 2, (255, 0, 0), -1) video.write(frame)这一步做出来演示环节的观感会大幅提升。录出来的视频还能放进文档说明里作为附件答辩时演示比纯静态图更有说服力。6.2 随机迷宫批量验证与性能对比只跑一张图不能证明方案稳定我会用随机迷宫生成器做批量验证。迷宫生成算法本身也是数据结构内容可以用并查集随机打通墙或者递归回溯生成完美迷宫。生成 20 张不同规模的迷宫图分别跑 BFS 和 A*记录节点数和耗时迷宫规模图节点数BFS 耗时A* 耗时20×20581.2ms0.8ms50×502106.5ms3.1ms100×10051218.3ms7.6ms这张表放进文档能直观展示启发式搜索在大迷宫上的收益。验证时我踩过一次坑随机生成 100 个迷宫前面 99 个都正常第 100 个突然搜不出路径最后发现是生成器把入口和出口所在的墙也打穿了导致起终点根本不在同一连通分量里。后来我在生成器里加了一步连通性检查用 BFS 跑一遍确认起终点连通再输出。整个方案做完最值钱的部分不是那几百行代码而是「图像 → 图 → 路径」这条建模思路。数据结构大作业真正考察的是抽象能力把现实世界的问题转化成图再选择合适的算法求解。希望这篇笔记能帮你的大作业少走几条弯路。本文还有配套的精品资源点击获取