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

Question

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

Представьте, что у меня есть два набора точек в 2d - скажем, каждый набор имеет ровно 50 очков.

например. установить A = {x1, y1, x2, y2, ..., x50, y50}

набор B = {x1 ', y1', x2 ', y2', ..., x50 ', y50'}

Я хочу найти комбинацию поворота и перемещения, которая ближе всего подходит к набору набора A на набор B. Думаю, я бы определил «ближайший», так как минимизирует среднее расстояние между точками в A и соответствующими точками в BIe, минимизирует среднее расстояние между (x1, y1) и (x1 ', y1') и т. д.

Полагаю, я мог бы использовать грубую силу, проверяя все возможные перемещения и повороты, но это было бы крайне неэффективно. Кто-нибудь знает более простой способ?

Спасибо!

Answer 1

Эта задача имеет очень элегантное решение с точки зрения разложения по сингулярности матрицы близости (расстояния между парами точек).Название этого - ортогональная проблема Прокруста , после греческой легенды о человеке, который предложил путешественникам кровать, которая подойдет любому.

Решение приходит от нахождения ближайшей ортогональной матрицы кданная (не обязательно ортогональная) матрица.

Answer 2

Если вы исправите какое-то вращение, вы можете получить ответ, используя троичный поиск .Запустите поиск по x и для каждого проверенного x запустите его по y, чтобы получить наилучшее значение.Это даст вам правильный ответ, поскольку функция (сумма соответствующих расстояний) является выпуклой (это можно доказать, наблюдая, что ограничение функции на любую линию является одномерной выпуклой функцией, а последнее является стандартным фактом:сумма нескольких выпуклых функций выпукла).Вместо грубой силы по углу я могу предложить такой метод, основанный на троичном поиске.Выберите небольшой шаг S. Вычислите целевую функцию для каждого угла в (0, S, 2S, ...).Тогда, если S достаточно мало, мы можем исключить некоторые из сегментов (iS, (i + 1) S) из рассмотрения.А именно с относительно большими значениями функции с углами iS и (i + 1) S.При тщательном применении это может дать ответ и сделать это быстрее, чем грубая сила.

Answer 3

Я бы сделал это в Excel, создав пару столбцов, представляющих точки.Ячейки, представляющие вращение / перемещение набора (не нужно вращать и переводить их обоих).Затем столбцы, представляющие те же точки, повернуты / переведены.
Затем еще один столбец для расстояния между точками повернутых / переведенных точек.
Затем ячейка суммы расстояний между точками.Наконец, используйте Solver для оптимизации ячеек вращения и перемещения.