open - read image cv2 python

puntos de clasificación para formar una línea continua

Question

Tengo una lista de (x, y) -coordinadas que representan un esqueleto de línea. La lista se obtiene directamente de una imagen binaria:

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

Ahora los puntos en la lista están ordenados según su posición en la imagen a lo largo de uno de los ejes.

Me gustaría ordenar la lista de modo que el orden represente un camino uniforme a lo largo de la línea. (Este no es actualmente el caso donde la línea se curva hacia atrás). Posteriormente, quiero ajustar una spline a estos puntos.

Un problema similar ha sido descrito y resuelto usando arcPy here . ¿Hay alguna manera conveniente de lograr esto usando python, numpy, scipy, openCV (u otra biblioteca)?

A continuación se muestra una imagen de ejemplo. da como resultado una lista de 59 (x, y) -coordinadas.

cuando envío la lista a la rutina de ajuste de spline de Scipy, me encuentro con un problema porque los puntos no están "ordenados" en la línea:

Answer 1

Estoy trabajando en un problema similar, pero tiene una restricción importante (como el ejemplo dado por el OP) que es que cada píxel tiene uno o dos píxeles adyacentes, en el sentido de 8 conectados. Con esta restricción, hay una solución muy simple.

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)

Answer 2

Pido disculpas por la respuesta larga por adelantado: P (el problema no es tan simple).

Vamos a empezar por reformular el problema. Encontrar una línea que conecte todos los puntos, se puede reformular como un problema de ruta más corta en una gráfica, donde (1) los nodos de la gráfica son los puntos en el espacio, (2) cada nodo está conectado a sus 2 vecinos más cercanos, y ( 3) la ruta más corta pasa por cada uno de los nodos una sola vez . Esa última restricción es muy importante (y bastante difícil de optimizar). Esencialmente, el problema es encontrar una permutación de longitud N , donde la permutación se refiere al orden de cada uno de los nodos ( N es el número total de nodos) en la ruta.

Encontrar todas las permutaciones posibles y evaluar su costo es demasiado costoso (hay N! Permutaciones si no estoy equivocado, lo cual es demasiado grande para los problemas). A continuación, propongo un enfoque que encuentra las N mejores permutaciones (la permutación óptima para cada uno de los N puntos) y luego encuentro la permutación (de esas N ) que minimiza el error / costo.

1. Crea un problema aleatorio con puntos no ordenados.

Ahora, comencemos a crear un problema de muestra:

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

Y aquí, la versión sin clasificar de los puntos [x, y] para simular puntos aleatorios en el espacio conectado en una línea:

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

El problema es, entonces, ordenar esos puntos para recuperar su orden original para que la línea se trace correctamente.

2. Crea una gráfica 2-NN entre nodos.

Primero podemos reorganizar los puntos en una matriz [N, 2] :

points = np.c_[x, y]

Luego, podemos comenzar creando un gráfico de vecino más cercano para conectar cada uno de los nodos a sus 2 vecinos más cercanos:

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

G es una matriz dispersa de N x N , donde cada fila representa un nodo, y los elementos no nulos de las columnas, la distancia euclidiana a esos puntos.

Luego podemos usar networkx para construir un gráfico a partir de esta matriz dispersa:

import networkx as nx
T = nx.from_scipy_sparse_matrix(G)

3. Encuentra la ruta más corta desde la fuente

Y, aquí comienza la magia : podemos extraer las rutas usando dfs_preorder_nodes , que esencialmente creará una ruta a través de todos los nodos (que pasan a través de cada uno de ellos exactamente una vez) dado un nodo de inicio (si no se da, se seleccionará el nodo 0) .

order = list(nx.dfs_preorder_nodes(T, 0))
xx = x[order]
yy = y[order]
plt.plot(xx, yy)
plt.show()

Bueno, no está tan mal, pero podemos notar que la reconstrucción no es óptima. Esto se debe a que el punto 0 en la lista desordenada se encuentra en el centro de la línea, es decir, primero va en una dirección y luego regresa y termina en la otra dirección.

4. Encuentra el camino con el menor costo de todas las fuentes.

Entonces, para obtener el orden óptimo, podemos obtener el mejor orden para todos los nodos:

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

Ahora que tenemos la ruta óptima a partir de cada uno de los N = 100 nodos, podemos descartarlos y encontrar el que minimice las distancias entre las conexiones (problema de optimización):

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

Los puntos se ordenan para cada una de las rutas óptimas, y luego se calcula el costo (calculando la distancia euclidiana entre todos los pares de puntos i e i+1 ). Si la ruta comienza en el punto start o end , tendrá el menor costo, ya que todos los nodos serán consecutivos. Por otro lado, si la ruta comienza en un nodo que se encuentra en el centro de la línea, el costo será muy alto en algún momento, ya que tendrá que viajar desde el final (o principio) de la línea hasta la línea inicial. Posición para explorar la otra dirección. La ruta que minimiza ese costo, es la ruta que comienza en un punto óptimo.

opt_order = paths[minidx]

Ahora, podemos reconstruir el orden adecuadamente:

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

Answer 3

Una posible solución es utilizar un enfoque de vecinos más cercanos, posible mediante el uso de un KDTree. Scikit-learn tiene una interfaz agradable. Esto se puede usar para construir una representación gráfica usando networkx. Esto solo funcionará si la línea a dibujar debe pasar por los vecinos más cercanos:

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

Actualización: Si los puntos de inicio y finalización son desconocidos y sus datos están razonablemente bien separados, puede encontrar los finales buscando camarillas en el gráfico. Los puntos de inicio y final formarán una camarilla. Si se elimina el borde más largo de la camarilla, se creará un extremo libre en el gráfico que se puede usar como punto de inicio y final. Por ejemplo, los puntos de inicio y fin de esta lista aparecen en el medio:

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

Después de construir el gráfico, ahora es un caso de quitar el borde más largo de las camarillas para encontrar los extremos libres del gráfico:

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