Алгоритм: найти 2d ориентацию из созвездия известных точек?

Question

Задача

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

т.е. Предположим, я делаю «снимок» известного набора 2d точек на стене. Я хочу знать, в каком положении находилась камера относительно «вертикально и по центру», когда был сделан снимок. Некоторые из точек могут быть не видны на картинке (они могут быть закрыты). (в этой аналогии предположим, что камера ортогональна и всегда направлена ​​прямо на плоскость стены, поэтому вам не нужно принимать во внимание искажения или перспективу)

---

Предлагаемый подход:

Шаг 1: масштаб B до того же «диапазона», что и у A

Не знаю как; открыт для предложений. Возможно, возьмите область выпуклой оболочки вокруг всех точек в B и масштабируйте ее почти до площади выпуклой оболочки вокруг A. Это сложно, потому что точки могут отсутствовать в B.

Шаг 2: сопоставить произвольную точку в "B" с ее двойником в "A"

Выберите некоторую случайную точку в наборе B. Назовите эту точку K. Каким-то образом возьмите «отпечаток пальца» K относительно всех других точек в B (используя только расстояние). Найдите его соответствие в A, сняв отпечатки пальцев во всех точках в A и взяв точку с наиболее похожим отпечатком пальца K.

Шаг 3: вращайте B (вокруг K), пока все точки в B не будут совмещены с точкой в ​​A

Возможно несколько решений, поэтому продолжайте вращаться, хотя 360d ищет решения.

---

Это просто выстрел из бедра, я могу быть далеко от базы. У кого-нибудь есть идеи?

Answer 1

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

Сначала вычислите среднее значение x0 исходного облака, затем вычислите среднее значение x1 подмножества облака. Разница средних векторов, x1-x0, является хорошей оценкой требуемого перевода.

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

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

Answer 2

«Дай мне место, на котором я буду стоять, и я переверну Землю» Архимед

Я думаю, что мы должны следовать шагам Архимеда

Алгоритм Арпи: Мы должны выбрать точку (X1) множества A с координатами (0, 0). (это место, где можно стоять)

Выберите другую точку (X2) и поместите ее в вектор OX (для упрощения)

Координаты всех остальных точек из набора A будут рассчитываться на основе координат X1 (0, 0) и X2 (some_Coordinate, 0).

Теперь выберите точку из набора B (Y1), и она будет центром набора B. Выберите другую точку из набора B (Y2) и поместите ее в OX из набора B. Теперь у нас есть скалярная шкала и угол поворота. Если это будет решением, тогда Y1 в наборе B представляет X1 из набора A, а Y2 из набора B представляет X2 из набора A. Если мы сможем найти карту между множеством B и множеством A на основе этого, используя все точки множества B и Yi <> Yj, если i <> j, где i и j - индексы точек в нашем представлении, чем У нас есть потенциальное решение, и мы храним это. Конец алгоритма Арпи

Чтобы найти все потенциальные решения, вы должны сделать следующее:

foreach point in A as X1 do
    foreach point in A as X2 do
        arpi's algoritm(X1, X2)

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

Answer 3

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

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