Каким образом можно привести к единой координатной системе траектории движения точек?

Question

[Alexey]

В программу приходят координаты (X, Y) множества точек.

С течением времени координаты всех точек могут как смещаться относительно центра, так и поворачиваться вокруг центральной точки.

Координаты точек могут незначительно изменяться относительно друг друга, точки могут появляться и исчезать.
Необходимо привести все точки к единой координатной системе.
Каким образом лучше всего реализовать алгоритм решения данной задачи на С++?
Стоит ли попробовать использовать нейросеть или хватит обычной математики?

Answer 1

[Александр Скуснов]

В Матлабе есть Multi-object tracking, но из-за санкций теперь это ПО скорее всего недоступно. Если только почитать документацию.

Answer 2

[freeExec]

В трехмерной графике используют специальную матрицу, для смещение, поворота и масштабирования координат.

https://en.wikipedia.org/wiki/Transformation_matrix

Answer 3

[Wataru]

Хватит и метода наименьших квадратов.

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

Сначала для каждой точки в прошлом снимке найдите положение в следующем. Можно брать ближайшую точку, если там изменения от кадра к кадру небольшие. Иначе придется городить какой-нибудь градиентный спуск. Если изменение превосходит некоторое пороговое значение - считаете, что точка пропала и не включаете эту пару в рассмотрение.

Когда для каждой точки вы знаете где ее прошлое и следующее положение, у вас задача найти минимум функции
sum_i (xp_i-xp'_i)^2+(yp_i-yp'_i)^2, где
xp' = xn*cosa - yn*sina + dx
yp' = xn*sina + yn*cosa + dy.

Тут (xp, yp) - координаты i-ой точки в прошлом кадре, (xn, yn) - координаты в следующем кадре, cosa,sina,dx,dy - неизвестные. Берете производные по dx, dy и a приравниваете к 0. Получаете 3 уравнения с 3 неизвестными. Их двух первых элементарно выразить dx, dy через cosa/sina. Подставив в последнее вы получите уравнение вида cosa^2 A + sina cosa B + sina^2C + D = 0. Можно домножить D на cosa^2+sina^2, потом поделить все на sin^2 и решать квадратное уравнение относительно тангенса. Потом через арктангенс найти решение.

Если изменения от кадра к кадру могут быть большими, то надо минимизировать чуть чуть другую функцию:

sum_i min_j ((xp_j-xp'_i)^2+(yp_j-yp'_i)^2) - для каждой точки берем минимум по всем возможным прообразам и это суммируем. Поскольку оно уже не диффиренцируемо, придется использовать какой-то более хитрый метод оптимизации по dx, dy, a.