Найдите оптимальное жесткое преобразование по соответствующим парам точек

У меня есть источник и цель в одной системе координат. В источнике есть «n» точек, а в цели — «n» (n>=3). Переписки также известны. Я хотел бы найти оптимальную матрицу жесткого преобразования (в некоторых случаях 6 степеней свободы или меньше).

Я так понимаю, что это решается минимизацией квадратов расстояний между исходной и целевой точками.

У меня два следующих вопроса.

1) Какой лучший решатель в этих случаях? 2) В случае алгоритма Левенберга-Марквардта с кватернионами, представляющими вращения, как лучше всего вычислить матрицу Якоби?


computer-vision transformation linear-algebra numerical-methods image-registration
person Tharun    schedule 29.10.2018    source источник
comment
Как насчет решения по методу наименьших квадратов? У вас есть матрица входных координат A, матрица выходных координат B, и вы хотите найти матрицу преобразования M: B=MA -> M=B/A. Найдите B/A по методу наименьших квадратов, и все готово! (В MATLAB вы можете буквально ввести M=B/A).   -  person Cris Luengo    schedule 29.10.2018
comment
Мне нужно учитывать случаи 1,2,3,4 и 5 степеней свободы, а не только 6 степеней свободы. Я полагаю, что представление этих случаев только в матрицах не самое лучшее. Кроме того, я ищу решение на C++. Спасибо   -  person Tharun    schedule 29.10.2018
comment
Вы можете посмотреть на en.wikipedia.org/wiki/Orthogonal_Procrustes_problem Я не уверен именно то, что вы подразумеваете под «жестким преобразованием», но такие проблемы часто можно решить напрямую, а не прибегать к нелинейному методу наименьших квадратов.   -  person dmuir    schedule 29.10.2018
comment
под жестким преобразованием я имею в виду только три степени свободы вращения и три перевода. Я думаю, что упомянутая вами ссылка действительна только в случаях вращения DOF, а не в том случае, когда также включен перевод.   -  person Tharun    schedule 30.10.2018
comment
@dmuir: жесткое преобразование представляет собой комбинацию перемещения и вращения.   -  person Yves Daoust    schedule 30.10.2018

Ответы (1)


arrow_upward
1
arrow_downward

Имея точки P[] и соответствующие точки Q[], мы хотим найти сдвиг T и поворот R, чтобы минимизировать

E = Sum{ <Q[i] - (R*P[i]+T)|Q[i] - (R*P[i]+T)>}

но это

E = Sum{ <Q[i] - R*P[i] - T | Q[i] - R*P[i] - T>}

и учитывая R, значение T, которое минимизирует это, равно

T = mean { Q[i] - R*P[i]} = Qbar - R*Pbar

где Qbar — среднее значение Qs и Pbar Ps.

Подставляя это значение T, мы получаем

E = Sum{ <q[i] - R*p[i] | q[i] - R*p[i]>}
where q[i] = Q[i]-Qbar, p[i] = P[i]-Pbar

Нахождение R для минимизации E — это проблема ортогональных прокрузов. Когда это решено для R, мы можем вычислить T, как указано выше.

Модификации при поиске решения для взвешенного случая просты. Прежде всего, Pbar и Qbar должны быть средневзвешенными, а затем мы должны использовать

q[i] = sqrt( weight[i]) * ( Q[i]-Qbar)
p[i] = sqrt( weight[i]) * ( P[i]-Pbar)
person dmuir    schedule 30.10.2018
comment
Спасибо за подробное объяснение. Есть ли у вас какое-либо решение, если к каждой паре источника и цели прикреплен вес? - person Tharun; 02.11.2018