opencv解迷宫

用opencv来解迷宫，听起来还是挺好玩的，就娱乐一下吧。

一.总体思路

直接从起点开始，全给它搜一遍，只要存在一条路径能达到终点，就肯定能搜索到它，这样不就能找到这条路径了吗。最简单的就是用广度优先搜索或者深度优先搜索啦。那么到底是广度优先还是深度优先呢？
肯定是广度优先啦。先复习一下两者的区别。

1.深度优先搜索

深度优先搜索，就是一条道先走到头再说。

这里参考《算法（第4版）》中的插图，这里是无向图，只要是连着的节点，都能互相到达。

• 起点为0，0的邻居是2和1，先走到2。
• 2的邻居是0（0不能再走）、1、3、4，先走到1。好，到头了。因为1的邻居虽然有0和2，但它两都走过了。走过的节点是不能再走的
• 退回到2（退回并不算再走一次哦），2走到3
• 3走到5，到头了。
• 退回到3，3走到4，到头了。
• 退回到2，也到头了（因为0、1、3、4全走过了）
• 退回到0，也到头了。
• 没有可退的了，结束！

2.广度优先搜索

广度优先，就是从起点开始，向所有能走的方向各走一步，达到各自的新的起点，然后在所有的新的起点上再向所有能走的方向各走一步。就比如把一盆水倒在水平的地面上，水均匀地向所有方向扩散一样。

还是参照《算法（第4版）》的插图

• 从0开始，依次到达2、1、5
• 从2开始，依次到达3、4，（1已经到过了）
• 从1开始，没啥好到了
• 从5开始，也没啥好到的了
• 结束！

对了，光看这个步骤好像还是不是很明白，代码到底是怎么处理的呢？

• 首先有一个先进先出的队列，把起点0放进队列
• 从队列中取一个点（刚开始自然是起点0啦）
• 遍历它的所有邻居，如果这个邻居是没有被访问过的，则将它加入队列，所以这里把2、1、5都加队列里了
• 从队列中取一个点（2先进去，所以取出2）
• 遍历2的所有邻居（0、1、3、4），0和1都访问过了，所以把3、4加入队列。现在队列中的东西为【1、5、3、4】
• 接下来还是一样的流程，只是会发现1、5、3、4的所有邻居都访问过了，所以没有新节点加入队列。
• 队列空了，结束！
  另外再说一下，如果是深度优先搜索的话，并不一定非要用递归，把这里的队列换成“栈”，就变成了深度优先搜索哦！

3.到底是用深度优先还是广度优先？

虽然我们不是严格意义上去找一个最短路径，但是如果特意绕了一个超级长的路径，那明显也不是迷宫的答案。如果用深度优先搜索，那它就会去找一个超级长的路径。比如有一条死路，它会一头钻进去，然后再钻出来，不信我先放上深度优先搜索的实际效果。
先放上迷宫的正确答案如下：

而深度优先的结果为：

二.预处理

现在已经确定就用广度优先搜索来遍历了，设定一个起点，然后遍历它的邻居，然后遍历它的邻居的邻居，以此类推，步步为营，最终就能找到一条可能不是严格意义上的最短，但也长不了多少的路径。
另外如果在遍历的过程中遇到墙（也就是黑色的点），自然是不能遍历这些点的，所以我们不可能会“穿过墙”。

• 不过有一点，如果以灰度模式读取这张图，它上面的点非黑即白吗？即像素值只会有0和255吗？自然不是，由于存在插值，所以自然会有0-255之间的值，我们做一下二值化就行啦。这很简单。
• 还有一个似乎更严重的问题，图像4周也是白的，如果我们不做任何处理，直接上广度优先算法，它完全有可能直接从图像外围搜索过去。就像下图这样：
  
  一个简单的策略就是，我直接判断一下最外围的黑色像素的边界，然后我们的探索范围不能越过这个边界不就行了吗？大致思路是这样 ，但是最好能灵活一点，比如迷宫图有可能不是方的，是圆的，是三角的。如下 ：
  
  我们可以用开操作，把迷宫内部全搞成黑的，这样剩下的外围的白的不就能获取到了麻。但是我们可能会用一个很大的kernel来做开操作，如果迷宫外围的空间本来就不大的话，有可能开操作把整个图都搞成黑的了。
  这个其实也简单，我们把图先移到一张更大的白色图像上（它有更大的外围空间），足以我们完成开操作。完成了之后，再把图像再移回去，不就行了吗。直接上代码：

def close_out(src_img, edge_add=100, kernel_size=100, close_again_kernel_size=5):
    # src_img为灰度图
    assert len(src_img.shape) == 2
    h, w = src_img.shape

    # 先把图像平移到一个更大的白色图像上，外围足够大（大于等于kernerl就行了），足以完成开操作
    bigger_img = np.ones((h + edge_add * 2, w + edge_add * 2), dtype=src_img.dtype) * 255
    bigger_img[edge_add:edge_add + h, edge_add:edge_add + w] = src_img

    # 开操作之后，外围是白的，整个迷宫是黑的
    open_img = cv2.morphologyEx(bigger_img, cv2.MORPH_OPEN, np.ones((kernel_size, kernel_size), dtype=np.uint8))
    # cv2.namedWindow('open_img', cv2.WINDOW_NORMAL)
    # cv2.imshow('open_img', open_img)
    # cv2.waitKey()

    # open_img取反，就是外围变成黑的，整个迷宫变成白的，再和原图（其实是更大的图）做与操作，就可以把迷宫外面变成黑的了
    bigger_img = bigger_img & ~open_img

    # 移回到原图上
    dest_img = bigger_img[edge_add:edge_add + h, edge_add:edge_add + w]

    # 这里又做一次开操作，是因为有可能迷路边界上还有一点点白色的部分。暂时没有仔细研究~~，直接把它们开掉！
    if close_again_kernel_size > 0:
        dest_img = cv2.morphologyEx(dest_img, cv2.MORPH_OPEN,
                                    np.ones((close_again_kernel_size, close_again_kernel_size), dtype=np.uint8))

    # cv2.namedWindow('dest_img', cv2.WINDOW_NORMAL)
    # cv2.imshow('dest_img', dest_img)
    # cv2.waitKey()

    return dest_img

效果图如下

圆形迷宫效果如下

稍微有点遗憾的是有可能看不出入口在哪了，但是我本来设想的就是由人来在图上点击入口与出口，问题不是太大（对照着原图来点吧~~）。操作步骤如下：
按照图上的提示，在入口处点击鼠标左键一次，不要点到黑色区域。

再点击出口点（对了，也不一定是出口，或者叫终点也行）

然后就可以等待程序找出路径并画出来了。界面交互代码就不单独放出来了，最终代码一起展示。

三.广度优先搜索

首先建立广度优先搜索的类，相应的属性见下面的注释 ，注意这里的self.edge_to的描述。

class BFSSearch:
    def __init__(self, src_img, s, e):
        assert len(src_img.shape) == 2
        self.h, self.w = src_img.shape

        # 外围已经除黑的灰度图，转成list是因为numpy数组不适合循环遍历，速度会很慢
        self.src_img = src_img.tolist()
        self.mark = np.zeros_like(src_img).tolist()  # 访问过的点标记为1，不会重复访问同一个点

        # 记录每一个点是由谁走过来的，比如由(3, 4)走到(3, 5)，则edge_to[5][3]=(3, 4)，注意索引的时候是先y（行）再列（x）
        self.edge_to = (np.ones((self.h, self.w, 2), np.int32) * -1).tolist()

        self.s = s  # 起点(x, y)
        self.e = e  # 终点(x, y)

        start_time = time.time()
        self.bfs()
        end_time = time.time()
        print(f'bfs time: {end_time - start_time}秒')

在构造函数里面调了self.bfs()，该函数如下：

    def bfs(self):
        assert self.s != self.e

        points = deque()
        points.append(self.s)

        while points:
            # 注意，如果把这里的popleft()改成pop()，即从右端pop()，那就变成后进先出，就变成深度优先搜索了哦。
            px, py = points.popleft()
            for nb_x, nb_y in self.get_neighbors(px, py):
                # 0就是墙
                if self.src_img[nb_y][nb_x] == 0 or self.mark[nb_y][nb_x]:
                    continue

                self.edge_to[nb_y][nb_x] = (px, py)
                self.mark[nb_y][nb_x] = 1

                if (nb_x, nb_y) == self.e:
                    break

                points.append((nb_x, nb_y))

这里面的逻辑非常简单，就是在第1节中说的广度优先搜索的逻辑，用一个队列就能轻松实现。注意这里self.edge_to的赋值，在完成bfs()之后，最终倒过来从终点在它里面一步步就能找到从起点过来的路径。
另外还要说一下的就是self.get_neighbors(px, py)，一个点的邻居就是上下左右（如果没有到达墙），即4邻域。

四.完整代码

import cv2
import numpy as np
from collections import deque
import time
from pathlib import Path


class BFSSearch:
    def __init__(self, src_img, s, e):
        assert len(src_img.shape) == 2
        self.h, self.w = src_img.shape

        # 外围已经除黑的灰度图，转成list是因为numpy数组不适合循环遍历，速度会很慢
        self.src_img = src_img.tolist()
        self.mark = np.zeros_like(src_img).tolist()  # 访问过的点标记为1，不会重复访问同一个点

        # 记录每一个点是由谁走过来的，比如由(3, 4)走到(3, 5)，则edge_to[5][3]=(3, 4)，注意索引的时候是先y（行）再列（x）
        self.edge_to = (np.ones((self.h, self.w, 2), np.int32) * -1).tolist()

        self.s = s  # 起点(x, y)
        self.e = e  # 终点(x, y)

        start_time = time.time()
        self.bfs()
        end_time = time.time()
        print(f'bfs time: {end_time - start_time}秒')

    def get_neighbors(self, px, py):
        nbs = []
        if px - 1 >= 0:
            nbs.append((px - 1, py))

        if py - 1 >= 0:
            nbs.append((px, py - 1))

        if px + 1 < self.w:
            nbs.append((px + 1, py))

        if py + 1 < self.h:
            nbs.append((px, py + 1))
        return nbs

    def path_to(self, e=None):
        if e is None:
            e = self.e
        e_x, e_y = e

        queue_path = deque()
        while (e_x, e_y) != self.s:
            queue_path.append((e_x, e_y))

            if not self.mark[e_y][e_x]:
                print(f'can not get to {e_x, e_y}')
                return []
            e_x, e_y = self.edge_to[e_y][e_x]
        else:
            queue_path.append((e_x, e_y))
        return list(reversed(queue_path))


    def bfs(self):
        assert self.s != self.e

        points = deque()
        points.append(self.s)

        while points:
            # 注意，如果把这里的popleft()改成pop()，即从右端pop()，那就变成后进先出，就变成深度优先搜索了哦。
            px, py = points.popleft()
            for nb_x, nb_y in self.get_neighbors(px, py):
                # 0就是墙
                if self.src_img[nb_y][nb_x] == 0 or self.mark[nb_y][nb_x]:
                    continue

                self.edge_to[nb_y][nb_x] = (px, py)
                self.mark[nb_y][nb_x] = 1

                if (nb_x, nb_y) == self.e:
                    break

                points.append((nb_x, nb_y))


dest_img_copy = None
start_p = None
end_p = None

def mouse_callback(event, x, y, flags, param):
    global dest_img_copy, start_p, end_p

    if event == cv2.EVENT_LBUTTONDOWN:
        print(dest_img_copy[y, x])

        if dest_img_copy[y, x].tolist() == [0, 0, 0]:
            raise ValueError(f'{x, y} is black!')

        if start_p is None:
            start_p = (x, y)
            print(f'start_p: {x, y}')
        elif end_p is None:
            end_p = (x, y)
            print(f'end_p: {x, y}')


def close_out(src_img, edge_add=100, kernel_size=100, close_again_kernel_size=5):
    # src_img为灰度图
    assert len(src_img.shape) == 2
    h, w = src_img.shape

    # 先把图像平移到一个更大的白色图像上，外围足够大（大于等于kernerl就行了），足以完成开操作
    bigger_img = np.ones((h + edge_add * 2, w + edge_add * 2), dtype=src_img.dtype) * 255
    bigger_img[edge_add:edge_add + h, edge_add:edge_add + w] = src_img

    # 开操作之后，外围是白的，整个迷宫是黑的
    open_img = cv2.morphologyEx(bigger_img, cv2.MORPH_OPEN, np.ones((kernel_size, kernel_size), dtype=np.uint8))

    # open_img取反，就是外围变成黑的，整个迷宫变成白的，再和原图（其实是更大的图）做与操作，就可以把迷宫外面变成黑的了
    bigger_img = bigger_img & ~open_img

    # 移回到原图上
    dest_img = bigger_img[edge_add:edge_add + h, edge_add:edge_add + w]

    # 这里又做一次开操作，是因为有可能迷路边界上还有一点点白色的部分。暂时没有仔细研究~~，直接把它们开掉！
    if close_again_kernel_size > 0:
        dest_img = cv2.morphologyEx(dest_img, cv2.MORPH_OPEN,
                                    np.ones((close_again_kernel_size, close_again_kernel_size), dtype=np.uint8))

    # cv2.namedWindow('dest_img', cv2.WINDOW_NORMAL)
    # cv2.imshow('dest_img', dest_img)
    # cv2.waitKey()

    return dest_img


if __name__ == '__main__':
    img_path = r'd:\tmp\pics\migong1.png'
    img = cv2.imread(img_path, 0)
    _, img = cv2.threshold(img, 50, 255, cv2.THRESH_BINARY)

    cv2.namedWindow('img', cv2.WINDOW_NORMAL)
    cv2.setMouseCallback("img", mouse_callback)

    dest_img = close_out(img)

    font_scale = 1.5
    thickness = 2
    (text_w, text_h), _ = cv2.getTextSize('click start point in white area', cv2.FONT_HERSHEY_SIMPLEX, font_scale, thickness)
    text_w += 40
    if text_w > img.shape[1]:
        font_scale /= text_w / img.shape[1]

    dest_img_copy = dest_img.copy()[:, :, None] * np.ones((1, 1, 3), dtype=np.uint8)
    cv2.putText(dest_img_copy, 'click start point in white area', (20, 50), cv2.FONT_HERSHEY_SIMPLEX, font_scale,
                (0, 0, 255), thickness, cv2.LINE_AA)
    cv2.imshow('img', dest_img_copy)

    while start_p is None:
        cv2.waitKey(1)

    dest_img_copy = dest_img.copy()[:, :, None] * np.ones((1, 1, 3), dtype=np.uint8)
    cv2.putText(dest_img_copy, 'click end point in white area', (20, 50), cv2.FONT_HERSHEY_SIMPLEX, font_scale,
                (0, 0, 255), thickness, cv2.LINE_AA)
    cv2.imshow('img', dest_img_copy)

    while end_p is None:
        cv2.waitKey(1)

    search = BFSSearch(dest_img, start_p, end_p)
    path_to_end = search.path_to()
    if path_to_end:
        show_img = img[:, :, None] * np.ones((1, 1, 3), dtype=np.uint8)
        for x, y in path_to_end:
            cv2.circle(show_img, (x, y), 1, (0, 0, 255), 1, cv2.LINE_AA)

        cv2.namedWindow('show_img', cv2.WINDOW_NORMAL)
        cv2.imshow('show_img', show_img)
        cv2.waitKey()

        img_path = Path(img_path)
        dest_path = img_path.parent / (img_path.stem + "_result" + img_path.suffix)
        cv2.imwrite(str(dest_path), show_img)
        print(f'write result to {dest_path}')
    else:
        raise ValueError('cat not find the path')

    cv2.destroyAllWindows()

效果如下：

圆形迷宫效果如下：

五.贴墙问题

有一个不太好的地方，就是路径喜欢贴着墙走，导致不是很美观（暂且不论严格的最短路径）。我暂时想到的一个笨办法，就是改变邻居的遍历顺序，本来是固定的左、上、右、下（具体见def get_neighbors(self, px, py)）。现在我们要把它排个序，规定一个领域范围（还是正方形的领域），谁的邻域范围内的白色点最多，就优先遍历谁。因为靠墙的点的邻域内的白色点肯定少，它就不会优先被遍历到。
只要修改def get_neighbors(self, px, py)就行了，让它最后调用sorted_nbs()对邻居列表排序。这里默认用的领域范围是5乘5的(2+1+2)乘(2+1+2)。

    def sorted_nbs(self, nbs, r=2):
        nbs_white_nums = []
        for x, y in nbs:
            white_num = 0
            for i in range(x - r, x + r + 1, 1):
                for j in range(y - r, y + r + 1, 1):
                    if i < 0 or i >= self.w or j < 0 or j >= self.h:
                        continue

                    if self.src_img[j][i] == 255:
                        white_num += 1
            nbs_white_nums.append(white_num)

        nbs_merge = [(x, y, white_num) for (x, y), white_num in zip(nbs, nbs_white_nums)]
        nbs_merge.sort(key=lambda item: item[2], reverse=True)
        return [(item[0], item[1]) for item in nbs_merge]

    def get_neighbors(self, px, py):
        nbs = []
        if px - 1 >= 0:
            nbs.append((px - 1, py))

        if py - 1 >= 0:
            nbs.append((px, py - 1))

        if px + 1 < self.w:
            nbs.append((px + 1, py))

        if py + 1 < self.h:
            nbs.append((px, py + 1))

        if nbs:
            # random.shuffle(nbs)
            nbs = self.sorted_nbs(nbs)
        return nbs

可以看到，确实路径稍微偏离黑色一点了！那是因为我们设的邻域还不够大，只有5乘5。但是我们并不能简单地把它设很大。因为差不多1000乘1000的图，我们的bfs就已经耗时1秒多了。用上这个5乘5的邻域之后，时间就变成25秒了。如果再调大邻域，那就更长了，而且这个邻域的时间复杂度可是平方级别的。

• 不过这里其实是有很多浪费的计算的，上下左右4个点，离的并不远，所以它们的邻域有很多是重合的，如果共享重合的计算，复杂度甚至能除4
• 似乎并不一定真的要计算一个方形邻域，尤其是这个方形的迷宫，直接计算横竖两个方向不就行了麻
  下面注释掉的代码就是方形的邻域，新增的代码就是只计算两个方向，重合的计算先不管了（嘿嘿），这样修改后的领域就是线性时间复杂度了，我们直接把r改成10

    def sorted_nbs(self, nbs, r=10):
        nbs_white_nums = []
        for x, y in nbs:
            white_num = 0
            # for i in range(x - r, x + r + 1, 1):
            #     for j in range(y - r, y + r + 1, 1):
            #         if i < 0 or i >= self.w or j < 0 or j >= self.h:
            #             continue
            #
            #         if self.src_img[j][i] == 255:
            #             white_num += 1

            for i in range(x - r, x + r + 1, 1):
                if i < 0 or i >= self.w:
                    continue

                if self.src_img[y][i] == 255:
                    white_num += 1

            for j in range(y - r, y + r + 1, 1):
                if j < 0 or j >= self.h:
                    continue

                if self.src_img[j][x] == 255:
                    white_num += 1
            nbs_white_nums.append(white_num)

        nbs_merge = [(x, y, white_num) for (x, y), white_num in zip(nbs, nbs_white_nums)]
        nbs_merge.sort(key=lambda item: item[2], reverse=True)
        return [(item[0], item[1]) for item in nbs_merge]

离墙更远了一点，而且时间仍然是25秒。好，就先抛砖引玉到此吧。