У меня следующая проблема. Во время визуализации у вас есть набор координат, которые несколько организованы в виде регулярного шаблона, такого как показан ниже
Что я хочу сделать, так это автоматически извлекать координаты, чтобы они располагались слева направо и сверху вниз. Кроме того, общее количество координат должно быть как можно большим, но включать только координаты, так что извлеченные координаты находятся на почти прямоугольной сетке (даже если координаты имеют другую симметрию, например, шестиугольную). Я всегда хочу извлечь координаты, которые следуют за прямоугольной структурой ячейки.
В примере, показанном выше, наибольшее число, содержащее такой ромбический набор, будет 8 × 8 координат (давайте назовем эти размеры: m x n), как показано в красном прямоугольнике.
Проблема в том, что данные координаты являются шумными и искаженными.
Мой подход состоял в том, чтобы создать искусственную решетку и минимизировать разницу с заданными координатами, принимая во внимание некоторое вращение, сдвиг и простое искажение решетки. Однако оказалось сложным определить функцию стоимости, которая покрывает сложность задачи, то есть минимизирует разницу между заданными координатами и подобранной решеткой, но также максимизирует компоненты сетки m x n.
Если у кого-нибудь есть разумная идея, как решить эту проблему, возможно, также с помощью алгоритмов машинного обучения, я был бы очень благодарен.
Вот код, который я использовал до сих пор:
Функция для генерации искусственной решетки с координатами m x n, которые расположены на расстоянии a и b в направлениях "n" и "m". Угол тета позволяет вращать решетку.
def lattice(m, n, a, b, theta):
coords = []
for j in range(m):
for i in range(n):
coords.append([np.sin(theta)*a*i + np.cos(theta)*b*j, np.cos(theta)*a*i - np.sin(theta)*b*j])
return np.array(coords)
Я использовал следующую функцию для измерения среднего минимального расстояния между точками, которое является хорошей отправной точкой для подгонки:
def mean_min_distance(coords):
from scipy.spatial import distance
cd = distance.cdist(coords, coords)
cd_1 = np.where(cd == 0, np.nan, cd)
return np.mean(np.nanmin(cd_1, axis=1))
Следующая функция предоставляет все возможные комбинации m x n, которые теоретически вписываются в длины координат, расположение которых предполагается неизвестным. Возможность ограничить это минимальным и максимальным значениями уже включена:
def get_all_mxn(l, min_m=2, min_n=2, max_m=None, max_n=None):
poss = []
if max_m is None:
max_m = l + 1
if max_n is None:
max_n = l +1
for i in range(min_m, max_m):
for j in range(min_n, max_n):
if i * j <= l:
poss.append([i, j])
return np.array(poss)
Определение используемой функции стоимости (для одного конкретного набора m x n). Поэтому я сначала хотел получить хорошую подгонку для определенной договоренности m x n.
def cost(x0):
a, b, theta, shift_a, shift_b, dd1 = x0
# generate lattice
l = lattice(m, n, a, b, theta)
# distort lattice by affine transformation
distortion_matr = np.array([[1, dd1], [0, 1]])
l = np.dot(distortion_matr, l.T).T
# shift lattice
l = l + np.array((shift_b, shift_a))
# Some padding to make the lists the same length
len_diff = coords.shape[0] - l.shape[0]
l = np.append(l, (1e3, 1e3)*len_diff).reshape((l.shape[0] + len_diff, 2))
# calculate all distances between all points
cd = distance.cdist(coords, l)
minimum distance between each artificial lattice point and all coords
cd_min = np.min(cd[:, :coords.shape[0] - len_diff], axis=0)
# returns root mean square difference of all minimal distances
return np.sqrt(np.sum(np.abs(cd_min) ** 2) )
Затем я запускаю минимизацию:
md = mean_min_distance(coords)
# initial guess
x0 = np.array((md, md, np.deg2rad(-3.), 3, 1, 0.12))
res = minimize(cost, x0)
Однако результаты чрезвычайно зависят от начального параметра x0, и я даже не включил подгонку m и n.