wake-up-neo.com

punkte sortieren, um eine durchgehende Linie zu bilden

Ich habe eine Liste von (x, y) -Koordinaten, die ein Liniengerüst darstellen. Die Liste wird direkt aus einem binären Bild erhalten:

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

Jetzt werden die Punkte in der Liste nach ihrer Position im Bild entlang einer der Achsen sortiert.

Ich möchte die Liste so sortieren, dass die Reihenfolge einen glatten Pfad entlang der Linie darstellt. (Dies ist derzeit nicht der Fall, wenn die Linie zurück gekrümmt ist.) Anschließend möchte ich einen Spline an diese Punkte anpassen.

Ein ähnliches Problem wurde mit arcPy hier beschrieben und gelöst. Gibt es eine bequeme Möglichkeit, dies mithilfe von Python, Numpy, Scipy, OpenCV (oder einer anderen Bibliothek) zu erreichen?

unten ist ein beispiel bild. es ergibt sich eine Liste von 59 (x, y) -Koordinaten.  enter image description here

wenn ich die Liste an die Spline-Anpassungsroutine von sciper sende, stoße ich auf ein Problem, weil die Punkte auf der Linie nicht "geordnet" sind:

 enter image description here

21
jlarsch

Ich entschuldige mich für die lange Antwort im Voraus: P (das Problem ist nicht das einfach). 

Beginnen wir mit der Umformulierung des Problems. Das Auffinden einer Linie, die alle Punkte verbindet, kann als kürzestes Pfadproblem in einem Diagramm neu formuliert werden, wobei (1) die Diagrammknoten die Punkte im Raum sind, (2) jeder Knoten mit seinen zwei nächsten Nachbarn verbunden ist und 3) der kürzeste Weg führt durch jeden der Knoten nur einmal . Diese letzte Einschränkung ist sehr wichtig (und ziemlich schwer zu optimieren). Im Wesentlichen besteht das Problem darin, eine Permutation der Länge Nzu finden, wobei sich die Permutation auf die Reihenfolge der einzelnen Knoten (Nist die Gesamtanzahl der Knoten) im Pfad bezieht.

Es ist zu teuer, alle möglichen Permutationen zu finden und deren Kosten zu bewerten (es gibt N! Permutationen, wenn ich mich nicht irre, was für Probleme zu groß ist). Ich schließe einen Ansatz an, der die besten Permutationen von N(die optimale Permutation für jeden der Nname__-Punkte) ermittelt und dann die Permutation (von diesen Nname__) findet, die den Fehler/die Kosten minimiert.

1. Erstellen Sie ein zufälliges Problem mit ungeordneten Punkten

Jetzt können wir ein Beispielproblem erstellen:

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

 enter image description here

Und hier die unsortierte Version der Punkte [x, y], um zufällige Punkte im Raum zu simulieren, die in einer Linie verbunden sind:

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

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

 enter image description here

Das Problem besteht dann darin, diese Punkte so anzuordnen, dass sie ihre ursprüngliche Reihenfolge wieder herstellen, damit die Linie richtig gezeichnet wird.

2. Erstellen Sie einen 2-NN-Graphen zwischen Knoten

Wir können zuerst die Punkte in einem [N, 2]-Array neu anordnen:

points = np.c_[x, y]

Dann können wir mit dem Erstellen eines nächsten Nachbargraphen beginnen, um jeden der Knoten mit seinen 2 nächsten Nachbarn zu verbinden:

from sklearn.neighbors import NearestNeighbors

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

Gist eine N x N-Matrix mit geringer Dichte, in der jede Zeile einen Knoten darstellt und die Nicht-Null-Elemente der Spalten den euklidischen Abstand zu diesen Punkten haben.

Wir können dann networkxverwenden, um aus dieser spärlichen Matrix ein Diagramm zu erstellen:

import networkx as nx

T = nx.from_scipy_sparse_matrix(G)

3. Suchen Sie den kürzesten Pfad von der Quelle

Und hier beginnt das magic: Wir können die Pfade mit Hilfe von dfs_preorder_nodes extrahieren, wodurch im Wesentlichen ein Pfad durch alle Knoten erstellt wird, die jeweils einen Knoten durchlaufen (if nicht angegeben, wird der 0-Knoten ausgewählt).

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

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

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

 enter image description here

Nun, ist nicht so schlimm, aber wir können feststellen, dass die Rekonstruktion nicht optimal ist. Dies liegt daran, dass der Punkt 0 in der ungeordneten Liste in der Mitte der Zeile liegt, dh er geht zuerst in eine Richtung und kommt dann zurück und endet in der anderen Richtung.

4. Finden Sie den Pfad mit den geringsten Kosten aus allen Quellen

Um also die optimale Reihenfolge zu erhalten, können wir einfach die beste Reihenfolge für alle Knoten erhalten:

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

Da wir nun von jedem N = 100-Knoten aus den optimalen Pfad haben, können wir sie verwerfen und den Pfad finden, der die Abstände zwischen den Verbindungen minimiert (Optimierungsproblem):

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

Die Punkte werden für jeden der optimalen Pfade angeordnet und dann werden die Kosten berechnet (durch Berechnen des euklidischen Abstandes zwischen allen Punktpaaren iund i+1). Wenn der Pfad am startname__- oder endname__-Punkt beginnt, hat dies die geringsten Kosten, da alle Knoten aufeinander folgen. Wenn der Pfad dagegen an einem Knoten beginnt, der in der Mitte der Linie liegt, sind die Kosten an einem bestimmten Punkt sehr hoch, da er vom Ende (oder Anfang) der Linie bis zum Anfang gehen muss Position, um die andere Richtung zu erkunden. Der Pfad, der diese Kosten minimiert, ist der Pfad, der an einem optimalen Punkt beginnt.

opt_order = paths[minidx]

Nun können wir die Reihenfolge richtig rekonstruieren:

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

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

 enter image description here

19
Imanol Luengo

Eine mögliche Lösung ist die Verwendung eines nächstgelegenen Nachbarnansatzes, der mit einem KDTree möglich ist. Scikit-learn hat eine Nice-Schnittstelle. Dies kann dann verwendet werden, um eine Diagrammdarstellung mit networkx zu erstellen. Das wird nur dann wirklich funktionieren, wenn die zu zeichnende Linie durch die nächsten Nachbarn verläuft:

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

Update: Wenn Start- und Endpunkt unbekannt sind und Ihre Daten einigermaßen gut voneinander getrennt sind, können Sie die Enden finden, indem Sie im Diagramm nach Cliquen suchen. Die Start- und Endpunkte bilden eine Clique. Wenn die längste Kante aus der Clique entfernt wird, erstellt sie ein freies Ende in der Grafik, das als Start- und Endpunkt verwendet werden kann. Zum Beispiel werden die Start- und Endpunkte in dieser Liste in der Mitte angezeigt:

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

 enter image description here

Nach dem Erstellen des Diagramms müssen Sie nun die längste Kante aus den Cliquen entfernen, um die freien Enden des Diagramms zu finden:

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

 enter image description here

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
6
kezzos

Ich arbeite an einem ähnlichen Problem, aber es hat eine wichtige Einschränkung (ähnlich wie das durch das OP gegebene Beispiel), die besagt, dass jedes Pixel entweder ein oder zwei benachbarte Pixel im 8-verbundenen Sinne hat. Mit dieser Einschränkung gibt es eine sehr einfache Lösung.

def sort_to_form_line(unsorted_list):
    """
    Given a list of neighbouring points which forms a line, but in random order, sort them to the correct order
    IMPORTANT: Each point must be a neighbour (8-point sense) to a least one other point!
    """
    sorted_list = [unsorted_list.pop(0)]

    while len(unsorted_list) > 0:
        i = 0
        while i < len(unsorted_list):
            if are_neighbours(sorted_list[0], unsorted_list[i]):
                #neighbours at front of list
                sorted_list.insert(0, unsorted_list.pop(i))
            Elif are_neighbours(sorted_list[-1], unsorted_list[i]):
                #neighbours at rear of list
                sorted_list.append(unsorted_list.pop(i))
            else:
                i = i+1

    return sorted_list

def are_neighbours(pt1, pt2):
    """
    Check if pt1 and pt2 are neighbours, in the 8-point sense
    pt1 and pt2 has integer coordinates
    """
        return (np.abs(pt1[0]-pt2[0]) < 2) and (np.abs(pt1[1]-pt2[1]) < 2)
0
redraider