如何使用 opencv python 解决 theta 迷宫问题？

Question

我必须找到从迷宫中心到最外圈的最短路径。我必须使用 opencv 和 python

来解决这个问题

Answer 1

我出去了！

您可以将图像中的每个白色像素视为无向加权图的节点。每个像素（节点）都连接到它的白色邻居。连接两个节点的边的权重在水平和垂直方向上都是1，在对角线方向上sqrt(2)（或者简称1.414）。

那么，既然知道起点和终点，就可以运行 Dijkstra algorithm找到起点和终点之间的最短路径。

我使用了 Rosetta Code Dijkstra 算法的实现：

这是代码（不是很完善，但可以工作）。该代码是用 C++ 编写的，但应该很容易转换为 Python，特别是如果您能找到 Dijkstra 算法的良好实现：

#include <opencv2/opencv.hpp>


#include <iostream>
#include <vector>
#include <string>
#include <list>

#include <limits> // for numeric_limits

#include <vector>
#include <set>
#include <utility> // for pair
#include <algorithm>
#include <iterator>

using namespace cv;
using namespace std;

typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = std::numeric_limits<double>::infinity();

struct neighbor {
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }

    bool operator == (const neighbor& other) const {
        return target == other.target;
    }
};

typedef std::vector<std::vector<neighbor> > adjacency_list_t;


void DijkstraComputePaths(vertex_t source,
    const adjacency_list_t &adjacency_list,
    std::vector<weight_t> &min_distance,
    std::vector<vertex_t> &previous)
{
    int n = adjacency_list.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    std::set<std::pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(std::make_pair(min_distance[source], source));

    while (!vertex_queue.empty())
    {
        weight_t dist = vertex_queue.begin()->first;
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());

        // Visit each edge exiting u
        const std::vector<neighbor> &neighbors = adjacency_list[u];
        for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
            neighbor_iter != neighbors.end();
            neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t distance_through_u = dist + weight;
            if (distance_through_u < min_distance[v]) {
                vertex_queue.erase(std::make_pair(min_distance[v], v));

                min_distance[v] = distance_through_u;
                previous[v] = u;
                vertex_queue.insert(std::make_pair(min_distance[v], v));

            }

        }
    }
}


std::list<vertex_t> DijkstraGetShortestPathTo(
    vertex_t vertex, const std::vector<vertex_t> &previous)
{
    std::list<vertex_t> path;
    for (; vertex != -1; vertex = previous[vertex])
        path.push_front(vertex);
    return path;
}

struct lessPoints
{
    bool operator() (const Point& lhs, const Point& rhs) const {
        return (lhs.x != rhs.x) ? (lhs.x < rhs.x) : (lhs.y < rhs.y);
    }
};

int main()
{
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE);
    resize(img, img, Size(), 0.5, 0.5);

    copyMakeBorder(img, img, 1, 1, 1, 1, BORDER_CONSTANT, Scalar(0));

    Point startPt(150, 150);
    Point endPt(160, 10);

    Mat1b mask = img > 200;

    vector<Point> pts;
    findNonZero(mask, pts);


    map<Point, int, lessPoints> mp;
    for (size_t i = 0; i < pts.size(); ++i) {
        mp[pts[i]] = i;
    }

    adjacency_list_t adj(pts.size());
    for (size_t i = 0; i < pts.size(); ++i) {

        int r = pts[i].y;
        int c = pts[i].x;

        // TODO: Check valid range

        if (mask(r - 1, c - 1)) { // Top Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r - 1)], 1.414));
        }
        if (mask(r - 1, c)) { // Top 
            adj[i].push_back(neighbor(mp[Point(c, r - 1)], 1.0));
        }
        if (mask(r - 1, c + 1)) { // Top Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r - 1)], 1.414));
        }
        if (mask(r, c - 1)) { // Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r)], 1.0));
        }
        if (mask(r, c + 1)) { // Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r)], 1.0));
        }
        if (mask(r + 1, c - 1)) { // Bottom Left
            adj[i].push_back(neighbor(mp[Point(c - 1, r + 1)], 1.414));
        }
        if (mask(r + 1, c)) { // Bottom
            adj[i].push_back(neighbor(mp[Point(c, r + 1)], 1.0));
        }
        if (mask(r + 1, c + 1)) { // Bottom Right
            adj[i].push_back(neighbor(mp[Point(c + 1, r + 1)], 1.414));
        }
    }


    vertex_t start_vertex = mp[startPt];
    vertex_t end_vertex = mp[endPt];

    std::vector<weight_t> min_distance;
    std::vector<vertex_t> previous;
    DijkstraComputePaths(start_vertex, adj, min_distance, previous);

    Mat3b dbg;
    cvtColor(mask, dbg, COLOR_GRAY2BGR);
    circle(dbg, startPt, 3, Scalar(0, 255, 0));
    circle(dbg, endPt, 3, Scalar(0, 0, 255));

    std::list<vertex_t> path = DijkstraGetShortestPathTo(end_vertex, previous);

    for (vertex_t v : path) {
        dbg(pts[int(v)]) = Vec3b(255, 0, 0);
        int vgfd = 0;
    }

    imshow("Solution", dbg);
    waitKey();

    return 0;
}

Answer 2

您可以使用skimage.graph轻松实现它。

import skimage.graph
### give start (y1,x1) and end (y2,x2) and the binary maze image as input
def shortest_path(start,end,binary):
    costs=np.where(binary,1,1000)
    path, cost = skimage.graph.route_through_array(
        costs, start=start, end=end, fully_connected=True)
    return path,cost

如何使用 opencv python 解决 theta 迷宫问题？

how to solve theta mazes using opencv python?

python

opencv

maze

numpy

我出去了！