Поворот/смещение объекта в трехмерном пространстве

[_genius_]

таким образом чтобы 3 (из N > 3) его точки совпали с соответствующими им другими 3мя точками.
Пользуясь этим нехитрым гайдом http://nghiaho.com/?page_id=671 я разобрался как поворачивать/смещать объект из 3 точек в 3 других точки.
Но что делать если объект состоит из бОльшего числа точек, а "попасть" мне надо именно 3мя из них в 3 другие, но так чтобы и остальные точки повернулись/сместились аналогично?
Проблема возникает на последнем этапе когда выясняется что полученную из 3 точек матрицу поворота (3,3) нельзя применить ни к чему кроме матрицы (3,3) из 3 точек.
Решение либо очень простое, либо не существует в принципе и я уже склоняюсь ко второму варианту
Прикрепляю мэпловский файл http://rgho.st/6JMLQMw6S

[arseniiv]

_genius_ в сообщении #1240978 писал(а):

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

Какие глупости. Столбцов у матрицы, в которую запихнули координаты точек, может быть сколько угодно. Преобразования разных столбцов совершенно раздельны, можно преобразовывать по столбцу за раз — разве что какая-то низкоуровневая оптимизация может заставить раскладывать их по матрицам какой-то определённой неединичной ширины.

[_genius_]

arseniiv в сообщении #1240983 писал(а):

Какие глупости

Да-да, они самые.
В общем нашел опечатку, теперь результаты отвратительные(были 1 в 1 из-за ошибки, сам не верил своему счастью), но судя по всему правильные. Удаляю .mw с хоста, т.к. первый пост мне уже не отредактировать.
Забыл упомянуть один нюанс: конечные 3 точки в принципе не могут на 100% соответствовать начальным из-за разных углов/расстояний. Любое приближение (наименьшие квадраты и т.д.) меня устроит.
У меня ощущение что я выбрал совершенно неподходящий мне метод и надо что-то в корне менять. Буду рад если мне кто-нибудь что-нибудь порекомендует.

[_genius_]

Нашел ещё один источник с тем же методом и там один-в-один то же самое, только ещё и с весами (которые мне не нужны) и с доказательствами:
https://igl.ethz.ch/projects/ARAP/svd_rot.pdf
Значит метод все же подходящий и косячу здесь только я. Но никак не пойму где.
В общем вот скрин из мэпла и сам .mw на этот раз с элементарнейшим примером который должен сходиться 1 в 1, но не сходится:
http://meson.ad-l.ink/7MlfBLtng/image.png
http://rgho.st/8gZvvkjFz

[svv]

У меня нет Maple, поэтому я могу посмотреть только файл image.png.
Скажите, вот Вы в конце используете массив ncacs для контроля. А Вы учитываете, что к этому времени уже модифицировали его, и он не такой, как был вначале?

[_genius_]

svv в сообщении #1241095 писал(а):

У меня нет Maple, поэтому я могу посмотреть только файл image.png.
Скажите, вот Вы в конце используете массив ncacs для контроля. А Вы учитываете, что к этому времени уже модифицировали его, и он не такой, как был вначале?

Я думал так и надо, но благодаря Вам теперь засомневался и применил поворот/смещение к оригинальным векторам:

Вроде как стало лучше, НО все равно далеко не фонтан. Пример ведь очень-очень простой (2 поворота на 90 градусов и небольшое смещение) и по идее точки должны совпадать 1 в 1.

[svv]

Сегодня после работы посмотрю внимательней.

[_genius_]

Теперь я совсем запутался, но каким-то чудом сделал оригинальную задачу правильно. При этом тестовый пример так исправить нельзя, поскольку там детерминант R и так положительный.
В общем я поменял способ "исправления" R на тот, что первым рекомендовался в статье, т.е. поменяв знак третьей строки Vt. Раньше я менял знаки всех строк в уже готовой матрице R.
Я просто не понимаю почему именно третьей, должно же быть все равно. Но если я меняю знаки в первой, второй, либо во всех трех строках Vt, это сильно портит результаты.

[svv]

Есть такое замечание к программе.
Вы выбрали три начальные точки $\mathbf p_1, \mathbf p_2, \mathbf p_3$ и три конечные точки $\mathbf q_1, \mathbf q_2, \mathbf q_3$. Как в одном, так и в другом наборе расстояния между точками принимают значения $\sqrt 5, \sqrt{10}$ и $\sqrt{13}$. Это хорошо. Но плохо то, что, скажем, $\sqrt 5=|\mathbf p_3-\mathbf p_1|=|\mathbf q_2-\mathbf q_1|$, то есть между соответствующими друг другу точками расстояния не равны. А для существования точного преобразования надо, чтобы были равны:
$\forall i,j:\quad|\mathbf p_i-\mathbf p_j|=|\mathbf q_i-\mathbf q_j|$

Метод ведь не подбирает преобразование, переводящее каждую начальную точку $\mathbf p_i$ в какую получится конечную точку $\mathbf q_k$. Нет, он всегда старается перевести $\mathbf p_1$ в $\mathbf q_1$, $\mathbf p_2$ в $\mathbf q_2$ и так далее:

Цитата:

Let $\mathcal{P}=\{\mathbf p_1,\mathbf p_2,\ldots,\mathbf p_n\}$ and $\mathcal{Q}=\{\mathbf q_1,\mathbf q_2,\ldots,\mathbf q_n\}$ be two sets of corresponding points in $\mathbb R^d$.

Возможно, метод «тупее», чем Вы думали. Но — что есть, то есть.

P.S. Исправил. Проверил. Всё сошлось.

[_genius_]

svv
Спасибо, теперь все понятно. Перетасовал точки в матрице конечных точек и теперь в примере все сходится на 100%. Короче метод меня устроил.
Однако вопрос с корректировкой отрицательного детерминанта остается открытым. Я уже сталкивался с этой проблемой раньше http://dxdy.ru/post1119400.html#p1119400 и тогда я просто умножал всю матрицу поворота целиком на -1. Проблем не возникало или по крайней мере я их не замечал. А сейчас такое решение почему-то сильно портит результаты и поэтому приходится умножать третью строку Vt (не R!) на -1. Зачем, почему - понятия не имею.
Для иллюстрации прикрепляю результаты решения настоящей задачи (не примера) с 17ю точками http://meson.ad-l.ink/7rH6g2z24/image.png
3 красных точки справа это желаемые конечные точки. Легко заметить что только при умножении третьей строки Vt на -1 результаты становятся приемлемыми, а во всех остальных случаях что-то не так. Вот мне бы и хотелось понять, почему именно третья? Всегда ли третья? Может с другой молекулой надо будет менять знак у второй или первой? А может есть какой-то другой способ устранения отражения, который работает всегда?

[svv]

Я почитаю статью Least-Squares Rigid Motion Using SVD, чтобы лучше разобраться. Но, скорее всего, ситуация такова.

Допустим, что равенства $|\mathbf p_i-\mathbf p_j|=|\mathbf q_i-\mathbf q_j|$ выполняются точно для всех соответствующих пар точек. Несмотря на это, требуемого преобразования (композиция вращения и сдвига) может не существовать! Пример: левую перчатку надо перевести в правую перчатку. Все соответствующие расстояния (от указательного пальца до мизинца; от среднего до центра ладони и т.д.) идеально совпадают, а вращения в собственном смысле слова не существует. Требуется вращение с отражением.
Так вот, метод у Вас спрашивает: мне какое преобразование искать — чистое вращение или вращение с отражением? Понятно, что в зависимости от заданных точек может лучше подходить одно, может другое. А в случае трёх точек можно подобрать и с отражением и без (они всегда лежат в одной плоскости, отражение относительно которой их не меняет). Свой выбор Вы задаёте с помощью выбора знака последнего диагонального элемента безымянной матрицы, входящей в формулу для $R$. Это эквивалентно умножению последнего столбца $U$ на $-1$, или последней строки $U^T$ на $-1$, есть и другие варианты.

[_genius_]

Т.е. вы хотите сказать что отрицательный дискриминант в моем случае (>3 точек) это не обязательно что-то плохое? И по-хорошему мне надо пробовать оба варианта. Только тут есть один нюанс: мне неизвестны конечные 17 точек, только 3. А значит без дополнительной информации понять, что лучше, невозможно. Ладно, была не была, попробую дописать скрипт без учета этой проблемы. Если она в итоге все же вылезет, задача сильно усложнится.

svv в сообщении #1241207 писал(а):

Это эквивалентно умножению последнего столбца $U$ на $-1$, или последней строки $U^T$ на $-1$, есть и другие варианты.

А это в свою очередь эквивалентно умножению последней строки $V^T$ на $-1$, только что проверил.

[svv]

Посмотрел статью, уточняю.

Если нам безразлично, какому преобразованию будет соответствовать наилучшая $R$ — вращению или вращению с отражением, следует находить $R$ как $VU^T$. Узнать, присутствует ли отражение, можно по значению $\det R$.

Если мы хотим, чтобы преобразование, задаваемое $R$, было вращением, найдём $\det(VU^T)$. Если определитель равен $1$, полагаем $R=VU^T$.
Если же определитель равен $-1$, значит, алгоритм решил, что с отражением можно добиться лучшего соответствия. Тогда надо громко произнести фразу: «Я принимаю ответственность за ухудшение точности попадания» и вычислить $R$ по формуле $VMU^T$, где $M$ — диагональная матрица, у которой на диагонали правый нижний элемент равен $-1$, а остальные $+1$. Можно, как было сказано, обойтись без $M$, например, умножая на $-1$ последний столбец $V$.

То, что именно правый нижний элемент $M$ должен быть $-1$, важно. Дело в том, что он соответствует наименьшему сингулярному числу матрицы $S$, и это гарантирует, что, полагая именно его равным $-1$, мы совершаем «наименьшее зло», то есть минимально ухудшаем точность.

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

[_genius_]

svv в сообщении #1241218 писал(а):

То, что именно правый нижний элемент $M$ должен быть $-1$, важно. Дело в том, что он соответствует наименьшему сингулярному числу матрицы $S$, и это гарантирует, что, полагая именно его равным $-1$, мы совершаем «наименьшее зло», то есть минимально ухудшаем точность.

Спасибо, вот оно в чем дело. Значит неслучайно третья строчка/столбец.