排序点以形成一条连续线 [英] sorting points to form a continuous line

问题描述

我有一个表示线骨架的 (x,y) 坐标列表.该列表直接从二进制图像中获得:

将 numpy 导入为 nplist=np.where(img_skeleton>0)

现在列表中的点根据它们在图像中沿轴之一的位置进行排序.

我想对列表进行排序，以便该顺序代表沿着线的平滑路径.(目前情况并非直线向后弯曲).随后，我想为这些点拟合一个样条.

使用 arcPy 描述并解决了类似的问题

当我将列表发送到 scipy 的样条拟合程序时，我遇到了一个问题，因为线上的点没有有序":

解决方案

我很抱歉提前回复了冗长的答案 :P(问题不是那那么简单).

让我们从重新表述问题开始.找到一条连接所有点的线，可以重新表述为图中的最短路径问题，其中(1)图节点是空间中的点，(2)每个节点都连接到它的 2 个最近的邻居，并且(3) 最短路径通过每个节点仅一次.最后一个约束非常重要(并且很难优化).本质上，问题是找到一个长度为N的排列，其中排列是指每个节点的顺序(N是节点的总数)路径.

找到所有可能的排列并评估它们的成本太昂贵了(如果我没记错的话，有 N! 个排列，这对于问题来说太大了).波纹管我提出了一种方法，可以找到 N 个最佳排列(每个 N 点的最佳排列)，然后找到排列(从那些 N代码>)，最大限度地减少错误/成本.

1.用无序点创建一个随机问题

现在，让我们开始创建一个示例问题:

将 matplotlib.pyplot 导入为 plt将 numpy 导入为 npx = np.linspace(0, 2 * np.pi, 100)y = np.sin(x)plt.plot(x, y)plt.show()

这里，点 [x, y] 的未排序版本模拟空间中连接成一条线的随机点:

idx = np.random.permutation(x.size)x = x[idx]y = y[idx]plt.plot(x, y)plt.show()

然后问题是对这些点进行排序以恢复其原始顺序，以便正确绘制线条.

2.在节点之间创建 2-NN 图

我们可以先重新排列[N, 2]数组中的点:

points = np.c_[x, y]

然后，我们可以从创建一个最近邻图开始，将每个节点连接到它的 2 个最近邻:

from sklearn.neighbors import NearestNeighborsclf = NearestNeighbors(2).fit(points)G = clf.kneighbors_graph()

G 是一个稀疏的 N x N 矩阵，其中每一行代表一个节点，列的非零元素是到这些点的欧几里德距离.

然后我们可以使用 networkx 从这个稀疏矩阵构建一个图:

将 networkx 导入为 nxT = nx.from_scipy_sparse_matrix(G)

3.从源中寻找最短路径

而且，这里开始魔法:我们可以使用

嗯，还不错，但我们可以注意到重建不是最优的.这是因为无序列表中的点0位于线的中间，即它首先向一个方向前进，然后返回并在另一个方向结束.

4.从所有源中找出代价最小的路径

所以，为了得到最优顺序，我们可以得到所有节点的最优顺序:

paths = [list(nx.dfs_preorder_nodes(T, i)) for i in range(len(points))]

既然我们有从每个 N = 100 节点开始的最佳路径，我们可以丢弃它们并找到最小化连接之间距离的那个(优化问题):

mindist = np.infminidx = 0对于我在范围内(len(点)):p = path[i] # 节点的顺序ordered = points[p] # 有序节点# 通过点 (i) 和 (i+1) 之间的欧几里得距离之和找到该订单的成本成本 = (((有序[:-1] - 有序[1:])**2).sum(1)).sum()如果成本<思想家:头脑主义者 = 成本minidx = i

对每条最优路径的点进行排序，然后计算成本(通过计算所有点i和i+1之间的欧几里德距离)).如果路径从 start 或 end 点开始，它将具有最小的成本，因为所有节点都是连续的.另一方面，如果路径从位于线中间的节点开始，则在某个点上的成本会非常高，因为它需要从线的末端(或起点)到初始位置探索另一个方向.使该成本最小的路径是从最佳点开始的路径.

opt_order = 路径[minidx]

现在，我们可以正确地重构顺序了:

xx = x[opt_order]yy = y[opt_order]plt.plot(xx, yy)plt.show()

I have a list of (x,y)-coordinates that represent a line skeleton. The list is obtained directly from a binary image:

import numpy as np    
list=np.where(img_skeleton>0)

Now the points in the list are sorted according to their position in the image along one of the axes.

I would like to sort the list such that the order represents a smooth path along the line. (This is currently not the case where the line curves back). Subsequently, I want to fit a spline to these points.

A similar problem has been described and solved using arcPy here. Is there a convenient way to achieve this using python, numpy, scipy, openCV (or another library?)

below is an example image. it results in a list of 59 (x,y)-coordinates.

when I send the list to scipy's spline fitting routine, I am running into a problem because the points aren't 'ordered' on the line:

解决方案

I apologize for the long answer in advance :P (the problem is not that simple).

Lets start by rewording the problem. Finding a line that connects all the points, can be reformulated as a shortest path problem in a graph, where (1) the graph nodes are the points in the space, (2) each node is connected to its 2 nearest neighbors, and (3) the shortest path passes through each of the nodes only once. That last constrain is a very important (and quite hard one to optimize). Essentially, the problem is to find a permutation of length N, where the permutation refers to the order of each of the nodes (N is the total number of nodes) in the path.

Finding all the possible permutations and evaluating their cost is too expensive (there are N! permutations if I'm not wrong, which is too big for problems). Bellow I propose an approach that finds the N best permutations (the optimal permutation for each of the N points) and then find the permutation (from those N) that minimizes the error/cost.

1. Create a random problem with unordered points

Now, lets start to create a sample problem:

import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(0, 2 * np.pi, 100)
y = np.sin(x)

plt.plot(x, y)
plt.show()

And here, the unsorted version of the points [x, y] to simulate a random points in space connected in a line:

idx = np.random.permutation(x.size)
x = x[idx]
y = y[idx]

plt.plot(x, y)
plt.show()

The problem is then to order those points to recover their original order so that the line is plotted properly.

2. Create 2-NN graph between nodes

We can first rearrange the points in a [N, 2] array:

points = np.c_[x, y]

Then, we can start by creating a nearest neighbour graph to connect each of the nodes to its 2 nearest neighbors:

from sklearn.neighbors import NearestNeighbors

clf = NearestNeighbors(2).fit(points)
G = clf.kneighbors_graph()

G is a sparse N x N matrix, where each row represents a node, and the non-zero elements of the columns the euclidean distance to those points.

We can then use networkx to construct a graph from this sparse matrix:

import networkx as nx

T = nx.from_scipy_sparse_matrix(G)

3. Find shortest path from source

And, here begins the magic: we can extract the paths using dfs_preorder_nodes, which will essentially create a path through all the nodes (passing through each of them exactly once) given a starting node (if not given, the 0 node will be selected).

order = list(nx.dfs_preorder_nodes(T, 0))

xx = x[order]
yy = y[order]

plt.plot(xx, yy)
plt.show()

Well, is not too bad, but we can notice that the reconstruction is not optimal. This is because the point 0 in the unordered list lays in the middle of the line, that is way it first goes in one direction, and then comes back and finishes in the other direction.

4. Find the path with smallest cost from all sources

So, in order to obtain the optimal order, we can just get the best order for all the nodes:

paths = [list(nx.dfs_preorder_nodes(T, i)) for i in range(len(points))]

Now that we have the optimal path starting from each of the N = 100 nodes, we can discard them and find the one that minimizes the distances between the connections (optimization problem):

mindist = np.inf
minidx = 0

for i in range(len(points)):
    p = paths[i]           # order of nodes
    ordered = points[p]    # ordered nodes
    # find cost of that order by the sum of euclidean distances between points (i) and (i+1)
    cost = (((ordered[:-1] - ordered[1:])**2).sum(1)).sum()
    if cost < mindist:
        mindist = cost
        minidx = i

The points are ordered for each of the optimal paths, and then a cost is computed (by calculating the euclidean distance between all pairs of points i and i+1). If the path starts at the start or end point, it will have the smallest cost as all the nodes will be consecutive. On the other hand, if the path starts at a node that lies in the middle of the line, the cost will be very high at some point, as it will need to travel from the end (or beginning) of the line to the initial position to explore the other direction. The path that minimizes that cost, is the path starting in an optimal point.

opt_order = paths[minidx]

Now, we can reconstruct the order properly:

xx = x[opt_order]
yy = y[opt_order]

plt.plot(xx, yy)
plt.show()

这篇关于排序点以形成一条连续线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！