Trouver une matrice rotation qui best-fit 2 ens. de vect.

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Trouver une matrice rotation qui best-fit 2 ens. de vect.

par Benjamin » 25 Oct 2018, 13:26

Bonjour,

La question est simple. J'ai un ensemble de vecteurs de départ, et un ensemble de vecteurs d'arrivée.
Je dois trouver la matrice de rotation qui approxime au mieux le fait que les vecteurs de départ transformés soient les vecteurs d'arrivée.

Le premier problème est la définition du "au mieux". J'hésite entre maximiser les produits scalaires entre les vecteurs de départ transformés et le vecteurs d'arrivée ou minimiser la différence entre les vecteurs de départ transformés et le vecteurs d'arrivée. Mais peut-être que ça revient au même ?

Le second point, et comment trouver cette fameuse matrice rotation tel que A = M*B pour tout couple (A,B) que je possède.

Merci d'avance pour toute idée que vous pourrez m'apporter :)



LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par LB2 » 25 Oct 2018, 14:40

Bonjour,

il faut donner un sens à "approximer au mieux". Une solution très souvent envisagée est d'utiliser une distance euclidienne, type norme 2. C'est la méthode des moindres carrés ordinaires. (Least Mean Squares en anglais)

Mais bien sûr il faut préciser sur quel espace tu raisonnes, et surtout pour quel produit scalaire.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par LB2 » 25 Oct 2018, 14:43

Un truc du style : minimiser la somme des carrés des normes de f(u_i)-v_i, pour i parcourant ton ensemble de vecteurs, et où v_i est l'image désirée de u_i, me paraît pas mal par exemple.

FLBP
Habitué(e)
Messages: 289
Enregistré le: 25 Aoû 2017, 03:07

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par FLBP » 25 Oct 2018, 14:47

Comme l'a dit LB2, le mieux serait de le faire au sens des moindres carrés : quelles sont les dimensions de tes vecteurs ?

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 25 Oct 2018, 14:58

Re-bonjour,

J'ai effectivement oublié de préciser deux choses de base : tous mes vecteurs sont de norme égale à 1 (si jamais ça peut servir). Et je suis en dimension 3 (d'où l'aspect rotation).

Ma famille de vecteurs a une trentaine d'éléments.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 25 Oct 2018, 21:33

Salut,
Déjà, si tout tes vecteurs sont unitaires, alors de minimiser le carré de l'écart des normes ou bien de maximiser le produit scalaire, c'est pareil vu que .

Ensuite, si on note les matrices formées de tes vecteurs de départ et d'arrivé (en colonne) et la matrice de rotation cherchée alors,
- Tu as 6 contraintes (quadratiques) sur les pour traduire que la matrice est orthogonale (3 pour les normes égales à 1 et 3 pour les produits scalaires égaux à zéro).
- Le truc à maximiser est linéaire et plus précisément, c'est .
Écrit de façon théorique, ça revient donc à chercher le max de [où est une matrice connue] sous contrainte (et ).
Donc ça semble être "relativement simple" comme problème de max sous contrainte et je me demande si on peut pas trouver la solution générale "théorique" en fonction de .

Je regarderais demain si j'ai le temps...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 26 Oct 2018, 20:25

Bonjour,

Merci pour ton message Ben. Ca serait en effet super cool si il y avait une solution théorique au truc :)

On m'a également suggéré de faire une sorte de produit scalaire sur des fonctions de bases. On considèrerait que les coordonnées de mes vecteurs A et B sont une fonction paramétrique xA=f(t), xB=g(t) etc... On appliquerait des transformations unitaires Rx, Ry, Rz sur mes vecteurs A pour connaitre la signature de ces transformations sur f(t), puis on projeterait g(t) sur ses fonctions de bases signatures pour trouver Rx, Ry et Rz. Ca serait rendu possible par le fait qu'on sait que les angles de la transformation sont très faibles (<<1°). Qu'en penses-tu ?

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par LB2 » 26 Oct 2018, 20:58

Si les angles de la transformation sont très faibles tu peux même faire un développement limité et la transformation est plus simple je pense

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 26 Oct 2018, 21:55

Bonsoir LB2,

Faire un développement limité de quoi ? A priori, je ne connais pas de formulation analytique de mes f(t), g(t) etc...
Merci :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 26 Oct 2018, 22:42

Je sais pas si on s'en sort jusqu'au bout de façon théorique (i.e. en dimension quelconque) :

On cherche le max de [où est connue] sous contrainte (et ).
Si l'espace tangent en à est formé de l'ensemble des matrices est antisymétrique. Donc est point critique ssi pour toute matrice antisymétrique c'est à dire ssi est symétrique.
Or, si tel est le cas, on a donc est une des matrices symétriques "racines carrées" de la matrice symétrique définie positive et ça, sauf erreur on sait le calculer relativement facilement (je doit pouvoir retrouver comment ça se fait numériquement parlant).
Le petit problème, c'est qu'une fois qu'on a les différentes solutions pour , pour en déduire , ben il faut supposer inversible pour écrire . Ensuite, il faut regarder les différentes valeurs que ça donne pour pour voir laquelle maximise le bidule.

Si tu avait un jeux de valeurs à peu prés cohérent avec une dizaine de vecteurs de départ et d'arivée où tu sait que c'est "presque" des images par une rotation, je pourrait peut-être faire un bout de code (sous Python par exemple) pour vérifier que j'ai pas écrit trop de connerie...

(*) à voir si ça coûte cher comme hypothèse...

EDIT : une autre solution, c'est peut être de bien rester dans R^3 et d'écrire qu'une rotation de R^3, c'est de la forme est un vecteur directeur unitaire de l'axe et où est l'angle de la rotation.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 26 Oct 2018, 23:09

Salut Ben,

Je ne sais pas si ça coûte cher de considérer C inversible. De ce que je comprends, inverser pas trop mal C correspond à trouver la solution M au sens du RMS de mes résidus, et si jamais j'ai pile poil la même rotation pour tout le monde, C est forcément inversible ?
De toute façon, je pense que c'est un faux problème que C soit inversible. J'ai matlab et dans ce cas, j'utilise la fonction mldivide qui résout CM=S de façon rigoureuse (numériquement parlant bien sûr). Tu peux trouver des infos sur l'algorithme ici : https://www.mathworks.com/help/matlab/ref/mldivide.html Ca fait du 'Gaussian elimination'.
De même pour la racine carré de la matrice, je peux utiliser sqrtm ( https://fr.mathworks.com/help/matlab/ref/sqrtm.html )
Ils disent qu'il existe une unique solution pour laquelle les valeurs propres ont des parties réelles positives. Tu penses qu'on peut passer à côté de quelque chose si on utilise cette solution particulière ?

Merci en tout cas, j'ai toujours aimé échanger avec toi sur mes problèmes de maths où tu apportes toujours un cadre théorique super rigoureux à mes problèmes de physique :)

Je n'ai pas de vecteurs sous la main là, je t'en passerai demain :)

EDIT : j'y avais pensé à l'écriture de Rodrigues, mais j'ai pas trouvé quoi en faire :/

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 26 Oct 2018, 23:56

En fait, vu que , pour que soit non inversible, il faut (et encore c'est pas suffisant) que ou soit de rang <2, c'est à dire que tes vecteurs de départ ou bien que ceux d'arrivé soient tous coplanaires.
Donc ça me semble pas une condition "super draconienne" de supposer qu'ils le sont pas.
Modifié en dernier par Ben314 le 27 Oct 2018, 00:10, modifié 2 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 27 Oct 2018, 00:01

Je te confirme qu'ils ne sont pas coplanaires :)
Mais du coup, je ne vois pas où est le truc qui fait qu'on n'a pas une solution rigoureuse à B=tM*A (ce qui est le cas en pratique).

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 27 Oct 2018, 00:10

Benjamin a écrit:De même pour la racine carré de la matrice, je peux utiliser sqrtm ( https://fr.mathworks.com/help/matlab/ref/sqrtm.html )
Ils disent qu'il existe une unique solution pour laquelle les valeurs propres ont des parties réelles positives. Tu penses qu'on peut passer à côté de quelque chose si on utilise cette solution particulière ?
Ca effectivement, c'est LA bonne question.
Mais en fait, je pense que c'est plus ou moins O.K. de prendre cette solution là :
est symétrique définie positive donc diagonalisable dans une base orthonormée et à valeur propres réelles strictement positive : avec orthogonale et diagonale à coeff. diagonaux .
Donc les 8 matrices symétriques telles que , c'est les est une des 8 matrices diagonales avec les sur la diagonale. Ce qui donne et le truc à maximiser est qui est maximal lorsque l'on prend des + partout.

Le seul "hic", c'est qu'avec tout ça, est bien orthogonale, mais par contre a le même signe que et que je vois pas vraiment pourquoi ce dernier serait positif.
Donc ça risque de te donner une antirotation et pas une rotation comme optimum.
Sauf si tu sait d'avance que tes vecteurs d'arrivé sont "pas super loin" d'être des images par une rotation des vecteurs de départ auquel cas il est plus que probable que la meilleure isométrie soit bien une rotation et pas une antirotation.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 27 Oct 2018, 14:33

Bonjour,

Avec les données que j'ai essayé jusqu'à présent, ça semble fonctionner. Ma trace est maximale pour la racine de C*tC qui prend les racines positives des valeurs propres. Et à chaque fois, j'avais le déterminant de M qui valait 1 et non -1.

Je vais essayer une autre méthode à base de curve fit pour voir si j'obtiens bien la même matrice M avec les deux façons de faire, ce qui serait rassurant sur le fait que ta solution théorique est béton :) (comme d'habitude ;))

Merci en tout cas !

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 27 Oct 2018, 14:50

De toute façon, sur la principe, s'il s'avère que ta matrice M a un déterminant =-1, ça signifie que, parmi les 8 matrices solutions de , il faut prendre les 4 où il y a un nombre impair de signe - sur la diagonale (pour que ça change le signe de det(M)).
Et pour maximiser la trace, il faut bien évidement mettre un unique signe - devant la racine carrée de la plus petite valeur propre de .
Sauf que ça signifie que tu peut plus utiliser "direct" la procédure mathlab qui calcule l'unique racine carrée à valeur propres positives....

Sinon, je redit ce que j'ai déjà dit : si, vu le problème concret que tu étudie, tu sait à l'avance qu'il existe une rotation qui donne à peut prés les bon vecteurs d'arrivé, alors il serait extrêmement étonnant que l'isométrie qui minimise les erreurs soit indirecte. Je pense que les cas où ça risque de se produire c'est ceux où les vecteurs de départ ou d'arrivé sont "presque" coplanaires suivant un plan P et où une symétrie orthogonale par rapport à P (donc de det.=-1) ne modifie que très peu les vecteurs.
Enfin, bref, ça parait quand même sain de mettre au minimum dans ta procédure un test pour vérifier que le déterminant est bien = +1 et de mettre un message de "warning" si ce n'est pas le cas.
Modifié en dernier par Ben314 le 27 Oct 2018, 15:08, modifié 1 fois.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 27 Oct 2018, 15:07

Ben314 a écrit:Si l'espace tangent en à est formé de l'ensemble des matrices est antisymétrique. Donc est point critique ssi pour toute matrice antisymétrique c'est à dire ssi est symétrique.

Re,

Est-ce que tu pourrais expliciter un peu plus ce que j'ai cité ci-dessus pour un profane ? Qu'appelles-tu "point critique" ? J'ai pas compris le lien entre trace(CM) est max et trace(CMA)=0 pour tout A anti-symétrique.
A quoi sert de parler des espaces tangents à SO3 ?

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21483
Enregistré le: 11 Nov 2009, 23:53

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Ben314 » 27 Oct 2018, 15:41

Y'a 36 façons de voir le chmilblick. Si tu est pas super familer avec la notion de variétés, on peut le voir uniquement en terme de fonctions :
L'ensemble des matrices orthogonale, c'est l'ensemble des matrices telles que et avec ce point de vue, ton problème s'énonce de façon archi. classique sous la forme : Déterminer le max de sous la contrainte .
Et dans cas, comme dans celui des maximum sans contraintes de fonctions de plusieurs variables, il y a une notion de "point critiques" qui sont les "candidats potentiels" pour être des min/max locaux :
Si on se place en un point (qui ici est une matrice, mais on s'en fout) tel que et qu'on fait une "petite perturbation" on a est la différentielle de au point appliquée au vecteur . Donc pour que soit lui aussi (approximativement) dans , il faut que c'est à dire que soit dans le noyau (c'est ce noyau qu'on appelle "espace tangent à au point M"). Ensuite, concernant la fonction à maximiser, on a aussi et donc pour que soit un candidat potentiel pour être un max ou un min local (sous contrainte), il faut que pour tout on ait (sinon, suivant cette direction on pourrait faire augmenter/diminuer en restant dans ) donc en résumé, il faut que (*).

Et pour revenir au cas qui nous intéresse, vu que est linéaire, on a pour tout point et concernant , on a :
pour petit.
Donc et donc ssi est antisymétrique (i.e. ), c'est à dire avec antisymétrique. Donc dans ce cas, la condition en rouge ci dessus s'énonce sous la forme pour toute matrice antisymétrique .

(*) En temps que physicien, tu as sûrement déjà vu ce truc là qui, en terme calculatoire, s'énonce sous sous la forme de "multiplicateurs de Lagrange" et je pense que le reste doit aussi évoquer des choses pour toi mais sans doute avec un formalisme différent.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Benjamin
Modérateur
Messages: 2337
Enregistré le: 14 Avr 2008, 12:00

Re: Trouver une matrice rotation qui best-fit 2 ens. de vect

par Benjamin » 27 Oct 2018, 21:46

Ok je vois. C'est un peu comme quand on fait des gradients pour trouver les extremas.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 61 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite