python - 对点进行排序以形成一条连续的线

Question

我有一个 (x,y) 坐标列表，它们代表线条骨架。该列表是直接从二值图像中获得的:

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

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

我想对列表进行排序，使顺序代表沿线的平滑路径。 (目前这不是线弯曲回来的情况)。随后，我想将样条曲线拟合到这些点。

已使用 arcPy here 描述并解决了类似的问题.有没有一种方便的方法可以使用 python、numpy、scipy、openCV(或其他库？)来实现这一点？

以下是示例图像。它会生成一个包含 59 个 (x,y) 坐标的列表。

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

Answer 1

我提前为冗长的回答道歉:P(问题不是那么简单)。

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

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

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

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

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()

这里，未排序版本的点[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 NearestNeighbors

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

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

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

import networkx as nx

T = nx.from_scipy_sparse_matrix(G)

3。从源中查找最短路径

然后，魔法开始了:我们可以使用 dfs_preorder_nodes 提取路径，这将在给定一个起始节点(如果没有给出，将选择 0 节点)的情况下，本质上创建一条通过所有节点(仅通过每个节点一次)的路径。

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

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

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

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

4。从所有来源中找到成本最小的路径

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

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

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

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

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

opt_order = paths[minidx]

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

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

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