Construyendo una cuadrícula 2D a partir de una lista de candidatos potencialmente incompleta

Problema

Necesito construir una cuadrícula 2D usando un conjunto de posiciones candidatas (valores en X e Y ). Sin embargo, puede haber falsos positivos candidatos que deben ser filtrados, así como falsos negativos (donde la posición debe crearse para la posición esperada dados los valores de las posiciones circundantes). Se puede esperar que las filas y columnas de la cuadrícula sean rectas, y la rotación, si es que es pequeña.

Además, no tengo información confiable sobre dónde está la posición de la cuadrícula (0, 0). Sin embargo, sí sé:

 grid_size = (4, 4) expected_distance = 105 

(La distancia exceptuada es solo una estimación aproximada del espaciado entre los puntos de la cuadrícula, y se debe permitir que varíe en el rango del 10%).

Ejemplo de datos

Este es el dato ideal, sin falsos positivos ni falsos negativos. El algoritmo debe ser capaz de lidiar con la eliminación de varios puntos de datos y la adición de puntos falsos.

 X = np.array([61.43283582, 61.56626506, 62.5026738, 65.4028777, 167.03030303, 167.93965517, 170.82191781, 171.37974684, 272.02884615, 272.91089109, 274.1031746, 274.22891566, 378.81553398, 379.39534884, 380.68181818, 382.67164179]) Y = np.array([55.14427861, 160.30120482, 368.80213904, 263.12230216, 55.1030303, 263.64655172, 162.67123288, 371.36708861, 55.59615385, 264.64356436, 368.20634921, 158.37349398, 54.33980583, 160.55813953, 371.72727273, 266.68656716]) 

Código

La siguiente función evalúa a los candidatos y devuelve dos diccionarios.

El primero tiene cada posición candidata (como una tupla de 2 longitudes) ya que las claves y los valores son tuplas de 2 longitudes de las posiciones a la derecha y debajo de la vecina (usando la lógica de cómo se muestran las imágenes). Esos vecinos son ellos mismos una coordenada de tupla de 2 longitudes o una None .

El segundo diccionario es una búsqueda inversa del primero, de modo que cada candidato (posición) tiene una lista de las posiciones de otros candidatos que lo respaldan.

 import numpy as np from collections import defaultdict def get_neighbour_grid(X, Y, expect_dist=(105, 105)): t1 = (expect_dist[0] + expect_dist[1]) / 2.0 * 0.9 t2 = t1 * 1.222 def neighbours(x, y): nRight = None ideal = x + expect_dist[0] D = np.sqrt((X - ideal)**2 + (Y - y)**2) candidate = (X[D.argmin()], Y[D.argmin()]) if candidate != (x, y) and x + t2 > candidate[0] > x + t1: nRight = candidate nBelow = None ideal = y + expect_dist[0] D = np.sqrt((X - x)**2 + (Y - ideal)**2) candidate = (X[D.argmin()], Y[D.argmin()]) if candidate != (x, y) and y + t2 > candidate[1] > y + t1: nBelow = candidate return nRight, nBelow right_below_neighbours = dict() def _default_val(*args): return list() reverse_lookup = defaultdict(_default_val) for pos in np.arange(X.size): pos_tuple = (X[pos], Y[pos]) n = neighbours(*pos_tuple) right_below_neighbours[pos_tuple] = n reverse_lookup[n[0]].append(pos_tuple) reverse_lookup[n[1]].append(pos_tuple) return right_below_neighbours, reverse_lookup 

Aquí es donde me quedo atascado:

¿Cómo uso estos diccionarios y / o X e Y para construir la cuadrícula más compatible?

Tenía una idea para comenzar con el candidato más bajo y más a la derecha apoyado por 2 vecinos y crear iterativamente la cuadrícula usando el diccionario reverse_lookup . Pero ese diseño tiene varias fallas, la más evidente es que no puedo contar con haber detectado al candidato más bajo y más a la derecha y sus dos vecinos de apoyo.

El código para eso, aunque no se ejecutará ya que lo pre_grid = right_below_neighbours cuando me di cuenta de lo problemático que era ( pre_grid = right_below_neighbours ):

 def build_grid(pre_grid, reverse_lookup, grid_shape=(4, 4)): def _default_val(*args): return 0 grid_pos_support = defaultdict(_default_val) unsupported = 0 for l, b in pre_grid.values(): if l is not None: grid_pos_support[l] += 1 else: unsupported += 1 if b is not None: grid_pos_support[b] += 1 else: unsupported += 1 well_supported = list() for pos in grid_pos_support: if grid_pos_support[pos] >= 2: well_supported.append(pos) well_A = np.asarray(well_supported) ur_pos = well_A[well_A.sum(axis=1).argmax()] grid = np.zeros(grid_shape + (2,), dtype=np.float) grid[-1,-1,:] = ur_pos def _iter_build_grid(pos, ref_pos=None): isX = pre_grid[tuple(pos)][0] == ref_pos if ref_pos is not None: oldCoord = map(lambda x: x[0], np.where(grid == ref_pos)[:-1]) myCoord = (oldCoord[0] - int(isX), oldCoord[1] - int(not isiX)) for p in reverse_lookup[tuple(pos)]: _iter_build_grid(p, pos) _iter_build_grid(ur_pos) return grid 

Sin embargo, la primera parte podría ser útil, ya que resume el soporte para cada posición. También muestra lo que necesitaría como salida final ( grid ):

Una matriz 3D con las 2 primeras dimensiones de la forma de la cuadrícula y la tercera con longitud 2 (para la coordenada x y la coordenada y para cada posición).

Resumen

Entonces me doy cuenta de que mi bash fue inútil, pero no sé cómo hacer una evaluación global de todos los candidatos y colocar la cuadrícula más compatible con los valores de x e y de los candidatos donde sea que se encuentren. Como esto es, espero, una pregunta bastante compleja, realmente no espero que alguien dé una solución completa (aunque sería genial), pero cualquier sugerencia sobre qué tipo de algoritmos o funciones de numpy / scipy podrían usarse ser muy apreciado

Finalmente, perdón por ser una pregunta un tanto larga.

Editar

Dibujo de lo que quiero que suceda:

Bosquejo de cómo debería funcionar

Las estrellas / puntos son la X y la Y trazadas con dos modificaciones, quité la primera posición y agregué una falsa para hacer de este un ejemplo completo del algoritmo buscado.

Lo que quiero es, en otras palabras, mapear los nuevos valores de coordenadas de las posiciones en círculo rojo (los que están escritos a su lado) para que pueda obtener la coordenada antigua de la nueva (por ejemplo, (1, 1) -> (170.82191781, 162.67123288) ). También quiero que los puntos que no se aproximan a la cuadrícula ideal que los verdaderos describen sean descartados (como se muestra), y finalmente que las posiciones de la cuadrícula ideal vacías (círculo azul) se “rellenen” utilizando los parámetros de cuadrícula ideales (aproximadamente (0, 0) -> (55, 55) ).

Solución

Utilicé el código @skymandr suministrado para obtener los parámetros ideales y luego hice lo siguiente (no el código más bonito, pero funciona). Eso significa que ya no uso la get_neighbour_grid get_neighbour_grid get_neighbour_grid grid .:

 def build_grid(X, Y, x_offset, y_offset, dx, dy, grid_shape=(16,24), square_distance_threshold=None): if square_distance_threshold is None: square_distance_threshold = ((dx + dy) / 2.0 * 0.05) ** 2 grid = np.zeros(grid_shape + (2,), dtype=np.float) D = np.zeros(grid_shape) for i in range(grid_shape[0]): for j in range(grid_shape[1]): D[i,j] = i * (1 + 1.0 / (grid_shape[0] + 1)) + j rD = D.ravel().copy() rD.sort() def find_valid(x, y): d = (X - x) ** 2 + (Y - y) ** 2 valid = d  0: old_coord = (coord[0] - 1, coord[1]) elif coord[1][0] > 0: old_coord = (coord[0], coord[1] - 1) if not first_loop: #calculate ideal step x, y = grid[old_coord].ravel() x += (coord[0] - old_coord[0]) * dx y += (coord[1] - old_coord[1]) * dy #modify with observed point close to ideal if exists x, y = find_valid(x, y) #put in grid #print coord, grid[coord].shape grid[coord] = np.array((x, y)).reshape(grid[coord].shape) first_loop = False return grid 

Plantea otra pregunta: cómo iterar bien a lo largo de las diagonales de una matriz 2D, pero supongo que es digna de una pregunta propia: una forma más numpy de iterar a través de las diagonales “ortogonales” de una matriz 2D

Editar

Se actualizó el código de la solución para tratar mejor con tamaños de cuadrícula más grandes, de modo que use una posición de cuadrícula contigua que ya se pasó como referencia para la coordenada ideal para todas las posiciones. Todavía hay que encontrar una manera de implementar la mejor manera de iterar a través de la cuadrícula de la pregunta vinculada.

Aquí hay una solución bastante simple y barata, aunque no sé cuán robusta es.

En primer lugar, aquí hay una forma de obtener una mejor estimación del espaciado:

 leeway = 1.10 XX = X.reshape((1, X.size)) dX = np.abs(XX - XX.T).reshape((1, X.size ** 2)) dxs = dX[np.where(np.logical_and(dX > expected_distance / leeway, dX < expected_distance * leeway))] dx = dxs.mean() YY = Y.reshape((1, Y.size)) dY = np.abs(YY - YY.T).reshape((1, Y.size ** 2)) dys = dY[np.where(np.logical_and(dY > expected_distance / leeway, dY < expected_distance * leeway))] dy = dys.mean() 

El código calcula las diferencias internas en X e Y, y toma la media de aquellos que están dentro del 10% del espaciado deseado.

Para la segunda parte, al encontrar el desplazamiento de la cuadrícula, se puede utilizar un método similar:

 Ndx = np.array([np.arange(grid_size[0])]) * dx x_offsets = XX - Ndx.T x_offset = np.median(x_offsets) Ndy = np.array([np.arange(grid_size[1])]) * dy y_offsets = YY - Ndy.T y_offset = np.median(y_offsets) 

Esencialmente, lo que esto hace es dejar que cada posición en X "vote" por NX = grid_size[0] posiciones donde podría estar el punto inferior izquierdo, basado en X - n * dx donde n = 0 es un voto para el punto en sí, n = 1 es un voto para un punto un dx a la izquierda, etc. De esta manera, los puntos cerca del origen verdadero obtendrán la mayoría de los votos, y la compensación se puede encontrar usando la mediana.

Creo que este método es lo suficientemente simétrico alrededor del origen deseado, que la mediana se puede usar en la mayoría de los casos (si no en todos). Sin embargo, si hay muchos falsos positivos que hacen que la mediana no funcione por alguna razón, el origen "verdadero" se puede encontrar utilizando, por ejemplo, un método de histogtwig.