排序点以形成连续线
image-processing
numpy
opencv
python
8
0

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

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

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

我想对列表进行排序,以便顺序代表沿线的平滑路径。 (当前不是直线向后弯曲的情况)。随后,我想使样条曲线适合这些点。

这里已经使用arcPy描述和解决了类似的问题。是否有使用python,numpy,scipy,openCV(或其他库)实现此目的的便捷方法?

以下是示例图片。结果是59(x,y)坐标的列表。 在此处输入图片说明

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

在此处输入图片说明

参考资料:
Stack Overflow
收藏
评论
共 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

更新:如果起点和终点未知,并且您的数据合理地分开了,则可以通过在图中查找集团来找到终点。起点和终点将形成集团。如果将最长的边缘从团中删除,它将在图形中创建一个自由端,可用作起点和终点。例如,此列表中的起点和终点出现在中间:

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

在此处输入图片说明

构建图之后,现在是从群组中删除最长边以找到图的自由端的情况:

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
收藏
评论

我很抱歉提前回答:P(问题不是那么简单)。

让我们从重述问题开始。找到一条连接所有点的线可以重新表示为图形中的最短路径问题,其中(1)图形节点是空间中的点,(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

针对每个最佳路径对这些点进行排序,然后计算成本(通过计算所有成对的点ii+1之间的欧式距离)。如果路径从startend开始,则成本最低,因为所有节点都是连续的。另一方面,如果路径始于行中的节点,则成本在某些时候会很高,因为它将需要从行的末端(或起点)行进到起点探索另一个方向的位置。使成本最小化的路径是从最佳点开始的路径。

opt_order = paths[minidx]

现在,我们可以正确地重建订单了:

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

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

在此处输入图片说明

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号