Konstruowanie siatki 2D z potencjalnie niepełną listę kandydatów

Question

Problem

trzeba zbudować 2D siatkę przy użyciu zestawu pozycji kandydujących (wartości w X i Y). Jednak mogą być fałszywie pozytywne kandydatury, które powinny zostać odfiltrowane, a także fałszywe negatywy (gdzie pozycja musi zostać utworzona dla oczekiwanej pozycji, biorąc pod uwagę wartości otaczających pozycji). Można oczekiwać, że wiersze i kolumny siatki będą proste, a rotacja, jeśli mała.

Co więcej, nie mam rzetelnych informacji na temat położenia siatki (0, 0). Jednak wiem:

grid_size = (4, 4) 

expected_distance = 105 

(wyłączonych odległość jest tylko oszacowanie odległości między punktami siatki, i powinny mieć możliwość zmieniać w zakresie od 10%).

przykład dane

Jest to idealne danych, bez wyników fałszywie dodatnich i fałszywie ujemnych nie. Algorytm musi być w stanie poradzić sobie z usunięciem kilku punktów danych i dodaniem fałszywych.

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

Kod

Poniższa funkcja ocenia kandydatów i zwraca dwa słowniki.

Pierwsza z każdej pozycji kandydata (jako 2-krotna krotka), ponieważ kluczami i wartościami są krotki o długości dwóch długości po prawej i poniżej sąsiada (z uwzględnieniem sposobu wyświetlania obrazów). Sąsiedzi sami są albo 2-krotną współrzędną tupu, albo None.

Drugi słownik to odwrotne wyszukiwanie pierwszego, tak, że każdy kandydat (pozycja) ma listę stanowisk innych kandydatów, które go wspierają.

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 

Oto gdzie utkniesz:

W jaki sposób mogę korzystać z tych słowników i/lub X i Y skonstruować najbardziej obsługiwanej sieci?

Wpadłem na pomysł, aby zacząć od dolnego, prawego kandydata wspieranego przez 2 sąsiadów i tworzyć iteracyjnie siatkę, używając słownika reverse_lookup. Ale ten projekt ma kilka wad, z których najbardziej oczywiste jest to, że nie mogę liczyć na wykrycie niższego, najbardziej prawego kandydata i obu jego pomocniczych sąsiadów.

Kod do tego, chociaż przyzwyczajenie uruchomić odkąd porzucił ją, gdy zdałem sobie sprawę, jak problematyczne było (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 

Pierwsza część może być przydatna, choć, ponieważ podsumowuje wsparcie każda pozycja. Pokazuje również, czego będę potrzebować jako ostatecznego wyjścia (grid):

Macierz 3D z 2 pierwszymi wymiarami, kształt siatki i 3. z długością 2 (dla współrzędnych xi współrzędnych y dla każdej pozycji).

Podsumowanie

więc zdaję sobie sprawę, jak moja próba była bezużyteczna, ale jestem na straty, w jaki sposób dokonać ogólnej oceny wszystkich kandydatów i umieścić siatkę najbardziej obsługiwany za pomocą przycisków X i Y wartości kandydatów gdziekolwiek pasuje. W związku z tym, jak sądzę, dość skomplikowanym pytaniem, nie oczekuję od nikogo kompletnego rozwiązania (choć byłoby wspaniale), ale wskazówka, jaki rodzaj algorytmów lub funkcji numpy/scipy mógłby być użyty być docenionym.

Wreszcie, przepraszam za to, że jest to dość długie pytanie.

Edit

Rysunek co chcę się zdarzyć:

Gwiazdy/kropki są X i Y wykreślone z dwoma zmianami, usunąłem pierwszą pozycję i dodaje się fałszywy, aby uczynić z tego pełny przykład poszukiwanego algorytmu.

Chciałem, innymi słowy, odwzorować nowe wartości współrzędnych oznaczone czerwonymi okręgami (te, które są obok nich zapisane), dzięki czemu mogę uzyskać starą współrzędną z nowej (np. (1, 1) -> (170.82191781, 162.67123288)). Też chcę punktów, które nie przybliżają idealnej siatki, którą prawdziwe punkty opisują, by zostać odrzuconym (jak pokazano), i wreszcie puste idealne pozycje siatki (niebieskie kółko), które mają być "wypełnione" przy użyciu idealnych parametrów siatki (około (0, 0) -> (55, 55)) .

Rozwiązanie

użyłem kodu @skymandr dostarczonego aby uzyskać optymalne parametry, a następnie zrobił następujące (nie najładniejszą kod, ale działa). Oznacza to, że ja nie używam get_neighbour_grid -function już .:

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 < square_distance_threshold 
     if valid.any(): 
      pos = d == d[valid].min() 
      if pos.sum() == 1: 
       return X[pos], Y[pos] 

     return x, y 

    x = x_offset 
    y = y_offset 
    first_loop = True 

    for v in rD: 
     #get new position 
     coord = np.where(D == v) 

     #generate a reference position already passed 
     if coord[0][0] > 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 

To stawia kolejne pytanie: jak ładnie iterację wzdłuż przekątnych w 2D tablicy, ale przypuszczam, że jest godny kwestia jego własna: More numpy way of iterating through the 'orthogonal' diagonals of a 2D array

Edit

Zaktualizowany kod rozwiązanie do lepszego radzenia sobie z większymi rozmiarami siatki tak, że używa sąsiednim pozycję startową już przekazany jako punkt odniesienia dla współrzędnych idealne dla wszystkich pozycjach. Nadal trzeba znaleźć sposób na wdrożenie lepszego sposobu iteracji przez sieć z połączonego pytania.

Answer 1

Oto dość proste i tanie rozwiązanie, choć nie wiem, jak solidne.

Przede wszystkim, oto sposób na uzyskanie lepszego oszacowania dla rozstaw

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

Kod oblicza wewnętrzne różnice w X i Y, i bierze średnią z tych, którzy są w 10% pożądany odstęp.

Dla drugiej strony, znalezienie przesunięcie siatki, podobna metoda może być stosowana:

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) 

Zasadniczo, co to robi to niech Każda pozycja w X „głos” za NX = grid_size[0] pozycjach gdzie lewy dolny punkt może być, na podstawie X - n * dx, gdzie n = 0 jest głosowaniem na samego punktu, n = 1 jest głosowaniem na punkt jeden dx po lewej itd. W ten sposób punkty w pobliżu prawdziwego pochodzenia uzyskają najwięcej głosów, a offset można znaleźć za pomocą mediany.

Myślę, że ta metoda jest wystarczająco symetryczna wokół pożądanego pochodzenia, że ​​mediana może być używana w większości (jeśli nie wszystkich) przypadków. Jeśli jednak istnieje wiele fałszywych trafień, które powodują, że mediana nie działa z jakiegoś powodu, "prawdziwe" pochodzenie można znaleźć za pomocą np. metoda histogramu.