Мне нужно найти самый короткий путь от центра лабиринта до самого внешнего круга. Я должен решить эту проблему, используя opencv и python.Как решить theta mazes используя opencv python?
0
A
ответ
3
Я ухожу!
Вы можете рассматривать каждый белый пиксел в изображении в качестве узла неориентированного взвешенного графа. Каждый пиксель (узел) соединен с его белыми соседями. Вес края, соединяющего два узла, равен 1 в горизонтальном и вертикальном направлениях, а sqrt(2)
(или просто 1.414
) в диагональном направлении.
Чем вы знаете начальную и конечную точку, вы можете запустить Dijkstra algorithm, чтобы найти кратчайший путь между началом и концом.
Я использовал Rosetta Code реализацию алгоритма Дейкстры:
Это код (на самом деле не полированный, но работает). Код находится на C++, но должен быть легко конвертирован в Python, особенно если вы можете найти хорошую реализацию алгоритма Дейкстры:
#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;
}
Смежные вопросы
- 1. Opencv HoughLines Lines Theta?
- 2. Как решить следующие рецидивы и найти Theta связаны
- 3. Ось метки Matplotlib: \ theta не работает \ Theta
- 4. как построить график на графике, используя функцию гипотезы, подставляя значение theta 0 и theta 1
- 5. Как решить ошибку в преобразовании hough в opencv и C++
- 6. Big-Theta: умножение Theta (n) и Theta (n^2) = Theta (n^3)?
- 7. Оцените ширину автомобиля сзади, используя opencv Python
- 8. Как решить _.some используя _.every?
- 9. Как решить это дифференциальное уравнение, используя scipy odeint?
- 10. Python-Как решить TypeError
- 11. Python отступы, как решить
- 12. Python-Как решить UnicodeEncodeError
- 13. Как подсчитать количество вкладок в скриншоте, используя OpenCV houghlines?
- 14. Сортировка() В Opencv + Python
- 15. Как распечатать позицию мыши после ее нажатия, используя opencv (python).
- 16. Как удалить пограничные компоненты в Python 2.7, используя OpenCV
- 17. Python - Используя OpenCV, как вставить .png в один mp4?
- 18. Постройте спираль, где r = theta^2 для 0 <= theta <= 10 * pi ... в python
- 19. Houghlines не обнаруживает всех строк opencv + python
- 20. Область интересов opencv python
- 21. используя потоки в opencv
- 22. Theta выполнения рекурсии
- 23. ValueError в Python OpenCV
- 24. Как решить выражения Long Python?
- 25. Как решить ошибку сокета python?
- 26. Python: как решить систему уравнений
- 27. python-Как решить KeyError: 2?
- 28. C++ Theta реализация функции
- 29. Нужно обнаружить книги с помощью OpenCV Python
- 30. Big Theta Proof
Удачи вам. –