Сопоставление двух 2D-массивов и возврат индексов совпадений - PullRequest
Новая
       95

Сопоставление двух 2D-массивов и возврат индексов совпадений

1 голос
/ 06 августа 2020

У меня есть два массива A и B формы (m, 2) и (n, 2), соответственно, с n >> m. В моем случае n = 8013 и m = 71. Каждая строка (x, y) каждого массива представляет координаты точечного источника на астрономическом изображении в пиксельных единицах. Все строки в A имеют очень близкие значения к некоторым из строк B, но не совсем такие же. В некоторых случаях разница заключается в некоторых десятичных дробях, в других, возможно, в одном или двух целых числах, например, одна строка в A - (1158, 1304.8974), а соответствующая ей строка в B - (1160, 1304.6578).

Мой вопрос: : как найти индексы элементов в B, которые являются ближайшими к элементам в A?

Моя первая попытка: 

matched = []
indexes = []
for k in np.arange(0, len(A)):
    idx = np.where((B[:, 0].astype(int) == A[k, 0].astype(int)) & 
                   (B[:, 1].astype(int) == A[k, 1].astype(int)))
    matched.append(B[idx])
    indexes.append(idx)

Но это только возвращает индексы строк в A, целые числа которых точно такие же, как элементы в B, и, следовательно, не соответствуют всем элементам. Если я удалю astype(int), у меня будет еще меньше совпадений.

Вторая попытка, которую я пробовал, для одной строки: 

value = A[0]
X = np.abs(B - value)
idx = np.where(X == X.min())
B[idx[0]]

Но вычисляются только самые близкие значение столбца x или y, но не обоих. Это означает, что если у меня есть одна строка в A, которую я хочу сопоставить, например (1230, 980), и две строки в B, например (3450, 981) и (1233, 975), последняя является правильным соответствием и ожидаемым output, эта вторая реализация возвращает элемент (3450, 981) в качестве правильного совпадения с (1230, 980), поскольку точка y = 980 ближе к y = 981, чем к y = 975.

Ответы [ 2 ]

0 голосов
/ 06 августа 2020

Вы ищете расстояние в самой обычной форме: евклидово.

Поскольку ваши числа составляют ~ 10k на ~ 100, вычисление расстояний между ними не будет особенно затратным с точки зрения времени или памяти. на любом достаточно современном оборудовании. Если бы это было дорого, я бы порекомендовал что-то вроде scipy.spatial.KDTree, которое эффективно реализует правильную пространственную сортировку.

Самый простой способ получить расстояния между каждым набором точек - использовать scipy.spatial.distance.cdist. Это не всегда так быстро, как вычисление расстояния «вручную», но будет достаточно быстро: 

dist = cdist(A, B)

dist - это массив (m, n). Вы можете найти индексы минимального расстояния в каждой строке, используя np.argmin: 

idx = np.argmin(dist, axis=1)

Соответствующие элементы B: 

matches = B[idx, :]

Это предполагает, что ваши входные массивы A и B изначально являются массивами numpy. Если это не так, начните с преобразования их в массивы: 

A = np.array(A)
B = np.array(B)

Если вы хотите установить расстояние «вручную», что будет быстрее, вы можете использовать широковещательную передачу для вычислить квадрат root сумм квадратов разностей: 

dist = np.sqrt(sum((A.reshape(-1, 1, 2) - B.reshape(1, -1, 2))**2, axis=-1))

Окончательный квадрат root не нужен, если вы просто хотите найти минимум, так как квадрат root монотонно увеличивается, а минимум квадрата расстояния возникает на минимальном расстоянии.

0 голосов
/ 06 августа 2020

Вы можете изменить регистр своего определения idx на допустимый диапазон, например: 

idx = np.where((B[:, 0].astype(int) >= A[k, 0].astype(int) - 3) & (B[:, 0].astype(int) <= a(k,0].astype(int + 3)) & (B[:, 1].astype(int) == A[k, 1].astype(int)))
...