分拣点形成一条连续的线

Question

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

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

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

我想对列表进行排序,使得顺序代表沿线的平滑路径.(目前不是线条向后弯曲的情况).随后,我想为这些点拟合样条.

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

下面是一个示例图像.它产生了59(x,y)坐标的列表.

当我将列表发送到scipy的样条拟合程序时,我遇到了一个问题,因为这些点在行上没有"排序":

Answer 1

我提前为长期答复道歉:P(问题不是那么简单).

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

找到所有可能的排列并评估它们的成本太昂贵了(N!如果我没有错,那就有排列,这对问题来说太大了).Bellow我提出了一种方法,可以找到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()

Answer 2

一种可能的解决方案是使用最近邻法,可以使用KDTree.Scikit-learn有一个很好的界面.然后,可以使用它来使用networkx构建图形表示.只有当要绘制的线应该通过最近的邻居时,这才会真正起作用:

from sklearn.neighbors import KDTree
import numpy as np
import networkx as nx

G = nx.Graph()  # A graph to hold the nearest neighbours

X = [(0, 1), (1, 1), (3, 2), (5, 4)]  # Some list of points in 2D
tree = KDTree(X, leaf_size=2, metric='euclidean')  # Create a distance tree

# Now loop over your points and find the two nearest neighbours
# If the first and last points are also the start and end points of the line you can use X[1:-1]
for p in X
    dist, ind = tree.query(p, k=3)
    print ind

    # ind Indexes represent nodes on a graph
    # Two nearest points are at indexes 1 and 2. 
    # Use these to form edges on graph
    # p is the current point in the list
    G.add_node(p)
    n1, l1 = X[ind[0][1]], dist[0][1]  # The next nearest point
    n2, l2 = X[ind[0][2]], dist[0][2]  # The following nearest point  
    G.add_edge(p, n1)
    G.add_edge(p, n2)


print G.edges()  # A list of all the connections between points
print nx.shortest_path(G, source=(0,1), target=(5,4))
>>> [(0, 1), (1, 1), (3, 2), (5, 4)]  # A list of ordered points

更新:如果起点和终点未知并且您的数据相当分离,您可以通过在图表中查找派系来找到目标.起点和终点将形成一个集团.如果从clique中移除最长边,它将在图中创建一个自由端,可用作起点和终点.例如,此列表中的起点和终点显示在中间:

X = [(0, 1), (0, 0), (2, 1),  (3, 2),  (9, 4), (5, 4)]

在构建图形之后,现在可以从clique中删除最长的边缘以找到图形的自由端:

def find_longest_edge(l):
    e1 = G[l[0]][l[1]]['weight']
    e2 = G[l[0]][l[2]]['weight']
    e3 = G[l[1]][l[2]]['weight']
    if e2 < e1 > e3:
        return (l[0], l[1])
    elif e1 < e2 > e3:
        return (l[0], l[2])
    elif e1 < e3 > e2:
    return (l[1], l[2])

end_cliques = [i for i in list(nx.find_cliques(G)) if len(i) == 3]
edge_lengths = [find_longest_edge(i) for i in end_cliques]
G.remove_edges_from(edge_lengths)
edges = G.edges()

start_end = [n for n,nbrs in G.adjacency_iter() if len(nbrs.keys()) == 1]
print nx.shortest_path(G, source=start_end[0], target=start_end[1])
>>> [(0, 0), (0, 1), (2, 1), (3, 2), (5, 4), (9, 4)]  # The correct path

Answer 3

我同意 Imanol_Luengo Imanol Luengo的解决方案，但是如果您知道第一点的索引，那么有一个仅使用 NumPy 的相当简单的解决方案：

def order_points(points, ind):
    points_new = [ points.pop(ind) ]  # initialize a new list of points with the known first point
    pcurr      = points_new[-1]       # initialize the current point (as the known point)
    while len(points)>0:
        d      = np.linalg.norm(np.array(points) - np.array(pcurr), axis=1)  # distances between pcurr and all other remaining points
        ind    = d.argmin()                   # index of the closest point
        points_new.append( points.pop(ind) )  # append the closest point to points_new
        pcurr  = points_new[-1]               # update the current point
    return points_new

这种方法似乎适用于正弦曲线示例，特别是因为很容易将第一个点定义为最左边或最右边的点。

对于img_skeleton问题中引用的数据，通过算法获得第一个点（例如作为最上面的点）同样容易。

# create sine curve:
x      = np.linspace(0, 2 * np.pi, 100)
y      = np.sin(x)

# shuffle the order of the x and y coordinates:
idx    = np.random.permutation(x.size)
xs,ys  = x[idx], y[idx]   # shuffled points

# find the leftmost point:
ind    = xs.argmin()

# assemble the x and y coordinates into a list of (x,y) tuples:
points = [(xx,yy)  for xx,yy in zip(xs,ys)]

# order the points based on the known first point:
points_new = order_points(points, ind)

# plot:
fig,ax = plt.subplots(1, 2, figsize=(10,4))
xn,yn  = np.array(points_new).T
ax[0].plot(xs, ys)  # original (shuffled) points
ax[1].plot(xn, yn)  # new (ordered) points
ax[0].set_title('Original')
ax[1].set_title('Ordered')
plt.tight_layout()
plt.show()