使用opencv寻找图像上一组6个点的最短路径

Question

我成功地在二维图像上找到了六个兴趣点。现在，我需要绘制一条连接这些点的最短距离的路径。

路径从点 0 开始，不会循环回到该点。

我将从点 0 到下一个最近的点绘制一条线，然后从该点开始，我将绘制一条到下一个最近的点的线，依此类推，直到到达最后一个未连接的点。

将六个兴趣点保存为 Point2f 类型的数组。该数组的索引 0 是起点。其余索引的剩余点没有按特定顺序存储。

如有任何帮助，我们将不胜感激

Answer 1

cv::norm 可用于查找两点之间的距离。我在 200 x 200 的棋盘上随机取了 6 个点。

现在我刚刚循环了其余的点，使用 cv::norm 找到最小距离，然后与下一个点交换其索引。我的结果是：

抱歉，代码是Python的：

import cv2
import numpy as np

def find_nn(point, neighborhood):
"""
Finds the nearest neighborhood of a vector.

Args:
    point (float array): The initial point.
    neighborhood (numpy float matrix): The points that are around the initial point.

Returns:
    float array: The point that is the nearest neighbor of the initial point.
    integer: Index of the nearest neighbor inside the neighborhood list
"""
min_dist = float('inf')
nn = neighborhood[0]
nn_idx = 0
for i in range(len(neighborhood)):
    neighbor = neighborhood[i]
    dist = cv2.norm(point, neighbor, cv2.NORM_L2)
    if dist < min_dist:
        min_dist = dist
        nn = neighbor
        nn_idx = i
nn_idx = nn_idx + j + 1
return nn, nn_idx 

#taking 6 random points on a board of 200 x 200
points = [(10, 10), (115, 42), (36, 98), (78, 154), (167, 141), (189, 4)]
board = np.ones((200, 200, 3), dtype = np.uint8) * 255
for i in range(6):
    cv2.circle(board, points[i], 5, (0, 255, 255), -1)

for j in range(5):
    nn, nn_idx = find_nn(points[j], points[j+1:])
    points[j+1], points[nn_idx] = points[nn_idx], points[j+1]

for i in range(5):
    cv2.arrowedLine(board, points[i], points[i+1], (255, 0, 0), 1, tipLength = 0.07)
cv2.imshow('image', board)
cv2.waitKey(0)
cv2.destroyAllWindows()

Answer 2

c++代码：

#include <opencv2/imgcodecs.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#include <iostream>
#include <vector>

using namespace cv;
using namespace std;

/////////////  Images  //////////////////////


void main() {

    //Blank Image 
    Mat img(512, 512, CV_8UC3, Scalar(255, 255, 255));

    float center_point_width = img.size().width / 2;
    float center_point_height = img.size().height / 2;

    Point2f center_point(center_point_width, center_point_height);

    float points_around_center[][2] = { {10.0, 10.0}, {115.0, 42.0}, {36.0, 98.0}, {78.0, 154.0}, {167.0, 141.0}, {189.0, 4.0} };
    
    int rows = sizeof points_around_center / sizeof points_around_center[0];
    int columns = sizeof points_around_center[0] / sizeof points_around_center[0][0];
    float width = 0;
    float height = 0;

    vector<float> list_of_line_lengths = {};

    for (int row = 0; row < rows; row++)
    {
        for (int column = 0; column < columns; column ++)
        {
            if (column == 0)
            {
                width = points_around_center[row][column];
            }
            if (column == 1)
            {
                height = points_around_center[row][column];
                Point2f target(width, height);
                Point2f difference = center_point - target;
                float line_length = sqrt(difference.x * difference.x + difference.y * difference.y);
                list_of_line_lengths.push_back(line_length);
            }
        }
    }

    for (int i = 0; i < list_of_line_lengths.size(); i++)
    {
        cout << list_of_line_lengths[i] << endl;
    }

    bool swapp = true;
    while (swapp) {
        swapp = false;
        for (size_t i = 0; i < list_of_line_lengths.size() - 1; i++) {
            if (list_of_line_lengths[i] > list_of_line_lengths[i + 1]) {
                list_of_line_lengths[i] += list_of_line_lengths[i + 1];
                list_of_line_lengths[i + 1] = list_of_line_lengths[i] - list_of_line_lengths[i + 1];
                list_of_line_lengths[i] -= list_of_line_lengths[i + 1];
                swapp = true;
            }
        }
    }

    cout << "********" << endl;

    for (int i = 0; i < list_of_line_lengths.size(); i++)
    {
        cout << list_of_line_lengths[i] << endl;
    }

    waitKey(0);
}

结果：

256.275
270.858
205.154
145.417
260.755
********
145.417
205.154
256.275
260.755
270.858
347.896