Correspondance des moindres carrés purement rotationnels

11

Quelqu'un pourrait-il recommander une méthode pour le problème des moindres carrés suivant:

trouver qui minimise: , où R est unitaire (rotation) matrice.RR3×3i=0N(Rxibi)2minR

Je pourrais obtenir une solution approximative en minimisant i=0N(Axibi)2min (arbitraire AR3×3 ), en prenant matrice A et:

  • calcul SVD: A=UΣVT , drop Σ et approximation RUVT
  • calcul de la décomposition polaire: A=UP , en laissant tomber l'échelle symétrique (et positive définie dans mon cas) P et en approximant RU

Je pourrais également utiliser la décomposition QR, mais ce ne serait pas isométrique (cela dépendrait du choix du système de coordonnées).

Quelqu'un connaît-il un moyen de le faire, au moins approximativement, mais avec une meilleure approximation que les deux méthodes ci-dessus?

Sergiy Migdalskiy
la source
4
J'ai utilisé l'algorithme de Kabsch pour un problème similaire, qui est essentiellement la méthode SVD que vous avez mentionnée en.wikipedia.org/wiki/Kabsch_algorithm si je ne me trompe pas, la méthode svd minimise l'équation, je ne suis pas sûr de ce que vous entendez par un ' meilleure méthode?
isti_spl
2
OMG Je viens de recevoir la même réponse IRL. Merci! Apparemment, laisser tomber fonctionne à moins que soit négatif, auquel cas la rotation optimale inclut une réflexion (et toute rotation est également mauvaise). Cela répond techniquement à la question, cependant, quelqu'un connaît-il une méthode moins chère que le calcul de la SVD? C'est un SVD 3x3, mais je dois en faire beaucoup (c'est pour la simulation FEM, et le problème est calculé pour chaque FE) En outre, le problème s'appelle apparemment le problème de Wahba, et il apparaît apparemment en aéronautique pour déterminer un métier orientation. d e t ( U V T )Σdet(UVT)
Sergiy Migdalskiy
j'ai vu ces problèmes liés: scicomp.stackexchange.com/questions/7552/…
isti_spl
@isti_spl: Pourriez-vous s'il vous plaît migrer votre commentaire vers une réponse?
Geoff Oxberry

Réponses:

9

Le problème est appelé le problème de Wahba , un algorithme pour cela est appelé algorithme de Kabsch , et le plus populaire plus tard est appelé méthode Davenport q . Il est apparemment utilisé et étudié en aéronautique pour déterminer l'orientation d'une embarcation. Il existe de nombreuses critiques sur les méthodes.

Attention, le meilleur ajustement peut inclure la réflexion.

La méthode de Kabsch calcule une matrice de covariance 3x3 SVD et supprime le terme (réflexion modulo un, qui s'explique généralement par la négation de la dernière colonne de dans le SVD). Il est très simple de généraliser à un autre nombre de dimensions.UΣU

La méthode Davenport q est souvent présentée comme le premier algorithme pratique, peut-être que quelqu'un peut expliquer pourquoi. Il construit également une matrice de covariance 3x3, mais paramètre ensuite la matrice de rotation en fonction d'un quaternion, et le problème devient celui de calculer le vecteur propre de valeur propre max d'une matrice 4x4 symétrique.

(Certaines des) implémentations numériques les plus populaires sont appelées QUEST et FOMA . Ces méthodes sont généralement une variation sur le thème du calcul de la valeur propre maximale en écrivant et en optimisant le polynôme caractéristique (une quartique), et en le résolvant analytiquement (calculs assez compliqués, en passant par les formules de Kardano), ou avec une itération de Newton.

Schuster a également développé et analysé certaines variantes d'algorithmes itératifs.

Sergiy Migdalskiy
la source
2
Pour un peu d'histoire dans la communauté aérospatiale, lisez Humble Problems de Markley.
Damien