формула наилучшего приближения для центра двумерного вращения с малыми углами

Question

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

1. Иметь N баллов (N> = 2) с координаты Xn, Yn на поверхности 2D твердое тело.
2. Твердое тело имеет небольшое вращение (ниже Пи / 180) в сочетании с небольшими сдвигами (расстояние менее 1% между любыми 2 точками N). Возможно также небольшая деформация (<< 0,001%) </li>
3. Те же N точек имеют новые координаты с именем XXn, YYn
4. Рассчитать с наилучшим приближением местоположение центра вращения в виде точки C с координатами XXX, YYY.

Спасибо

Answer 1

Если вы знаете соответствие (то есть вы знаете, какие точки одинаковы до и после преобразования) и хотите разрешить масштабирование, то проблема состоит в наборе линейных уравнений. Если у вас есть 2 или более очков, вы можете найти решение наименьших квадратов без особых затруднений.

Для начальных точек (xi, yi) и преобразованных точек (xi ', yi') у вас есть уравнения вида

xi' = a xi + b yi + c
yi' =-b xi + a yi + d

, который вы можете переставить в линейную систему

A x = y 

, где

A = | x1  y1 1 0 | 
    | y1 -x1 0 1 |
    | x2  y2 1 0 |
    | y2 -x2 0 1 |
    |    ...     |
    | xn  yn 1 0 |
    | yn -xn 0 1 |

x = | a |
    | b |
    | c |
    | d |

y = | x1' |
    | y1' |
    | x2' |
    | y2' |
    | ... |
    | xn' |
    | yn' |

стандартная форма "наименьших квадратов"

A^T A x = A^T y

и имеет решение

x = (A^T A)^-1 A^T y

с A^T в качестве транспонирования A и A^-1 в качестве инверсии A. Обычно вы используете SVD или QR-декомпозицию для вычисления решения, поскольку они должны быть более стабильными и менее вычислительно интенсивными, чем обратные.

Как только вы нашли x (и, таким образом, четыре элемента преобразования a, b, c и d), тогда различные элементы преобразования задаются как

scale       = sqrt(a*a+b*b)
rotation    = atan2(b,a)
translation = (c,d)/scale

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

Редактировать: Я забыл включить центр вращения. Вращение theta вокруг произвольной точки p является последовательностью

translate(p) rotate(theta) translate(-p)

если вы расширите все это как аффинное преобразование (по сути, то, что мы имеем выше), тогда термины перевода придут к

dx = px - cos(theta)*px + sin(theta)*py
dy = py - sin(theta)*px - cos(theta)*py

мы знаем theta (rotation), dx (c) и dy (d) из приведенных выше уравнений. Приложив немного усилий, мы можем решить для px и py

px = 0.5*(dx - sin(theta)*dy/(1-cos(theta)))
py = 0.5*(dy + sin(theta)*dx/(1-cos(theta)))

Вы заметите, что уравнения не определены, если тета равен нулю, потому что нет центра вращения, когда вращение не выполняется.

Я думаю, что все правильно, но сейчас у меня нет времени перепроверять все.

Answer 2

Посмотрите "Алгоритм Кабша". Это универсальный алгоритм для создания матриц вращения с использованием N известных пар. Kabsch создал его для помощи в создании шумных стереофотографий. Вы поворачиваете элемент на изображении A на рисунок B, и если он не находится в заданном положении, это шум. http://en.wikipedia.org/wiki/Kabsch_algorithm

Answer 3

См. О расчете конечного центра вращения для жесткого плоского движения для относительно простого решения.Я говорю «относительно просто», потому что он все еще использует такие вещи, как псевдообращения и SVD (разложение по сингулярным числам).А вот статья в Википедии о мгновенном центре вращения .И еще одна статья: ОЦЕНКА КОНЕЧНОГО ЦЕНТРА ВРАЩЕНИЯ В ПЛАНАРНЫХ ДВИЖЕНИЯХ .

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

Answer 4

Прежде всего, проблема нетривиальна.

«Простое» решение. Это работает лучше всего, когда многоугольник напоминает круг, а точки распределены равномерно.

• перебрать N
• Как для старого, так и для нового набора данных, найдите 2 самые дальние точки точки N. Итак, теперь у вас есть треугольник до и после преобразования. Используйте направление по часовой стрелке от центра каждого треугольника для нумерации его вершин как [0] (= N-я точка в исходном наборе данных), [1] и [2] (2 самые дальние точки).
• Рассчитайте центр вращения и деформацию (и x, и y) этого треугольника. Если деформация больше вашего 0,001% - отбросьте данные для этого треугольника, в противном случае сохраните его.
• Рассчитать среднее для центров вращения.

Правильное решение: определить функцию Err (Точка BEFORE [N], Точка AFTER [N], двойная TFORM [3] [3]), где BEFORE - постоянные старые точки данных, AFTER - постоянные новые точки данных, TFORM [3] [3] аффинная матрица преобразования, функция Err (...), которая возвращает значение скалярной ошибки, 0,0, когда TFORM переводится ДО точного ПОСЛЕ, или некоторое> 0,0 значение ошибки. Затем используйте любую числовую математику, которую хотите найти минимум ошибки (TFORM): например, градиентный поиск.

Answer 5

Выберите любые 2 точки на теле, P1, P2, до и после вращения. Найти векторы между этими точками до и после. Скрестите эти векторы с вектором, перпендикулярным плоскости вращения. Это приводит к двум новым векторам, пересечению линий, образованных начальными точками, и эти два новых вектора являются центром вращения.

{
если P1after = P1 перед возвратом P1after
если P2after = P2 перед возвращением P2after
Вектор V1 = P1after - P1before
Вектор V2 = P2after - P2before
normal = Vn // может быть грязно для произвольной трехмерной ориентации, но это просто, если вы знаете ориентацию, например, normal = (0,0,1) для объекта в плоскости x, y)

Вектор VL1 = V1 x Vn // Вектор V1, перекрестное произведение с Vn
Вектор VL2 = V2 x Vn
return intersectLines (P1after, VL1, P2after, VL2) // Центр вращения - это пересечение двух линий
}

линии пересечения (точка P1, вектор V1, точка P2, вектор V2)
{
// пересекаем две линии, используя точку, направление линии
// возвращает точку
}

Answer 6

Если я правильно понимаю вашу проблему, это можно решить следующим образом:

• найти конечности (самые дальние точки, вероятно, по нескольким осям)
• масштабировать либо один для соответствия
• их вращение теперь должно быть тривиальным (?)

Answer 7

Рассчитать полигональные центры O1 и O2. Определите линейные формулы для O1 с (X0, Y0) и O2 с (XX0, YY0). Найти пересечение линий, чтобы получить C.