Calculer la transformation entre deux nuages de points
Hypothèses
L’objet de cet article est la minimisation d’erreur entre deux nuages de points (minimisation de l’erreur point à point). Considérons les nuages de points A en bleu et B en rouge sur la figure ci-dessous. Notre but est de trouver la transformation de B (translation et rotation) qui va permettre de minimiser les distances point à point (au sens de la minimisation des moindres carrés).
$$ A =\left[ \begin{matrix} p_1^a & p_2^a & ... & p_n^a \end{matrix} \right] =\left[ \begin{matrix} x_1^a & x_2^a & ... & x_n^a \ y_1^a & y_2^a & ... & y_n^a \end{matrix} \right] $$
$$! B =\left[ \begin{matrix} p_1^b & p_2^b & ... & p_n^b \end{matrix} \right] =\left[ \begin{matrix} x_1^b & x_2^b & ... & x_n^b \ y_1^b & y_2^b & ... & y_n^b \end{matrix} \right] $$
Nous supposerons que les points sont déjà appairés: chaque point de \(A\) est déjà associé à un point de \(B\).
Translation
Pour commencer, calculons le centre de gravité de chaque nuage de points:
$$ \begin{matrix}COG^a=\frac{1}{n}. \sum\limits_{i=1}^n p_i^a & COG^b=\frac{1}{n}. \sum\limits_{i=1}^n p_i^b \end{matrix} $$
Chaque point est translaté d’un vecteur donné par le centre de gravité de son nuage (cela revient à centrer chaque nuage sur l’origine du repère).
$$ \begin{matrix} A'=A-COG^a & B'=B-COG^b \end{matrix} $$
Rotation
Pour la rotation, les choses sont un peu plus compliquées. D’abord, calculons la matrice \(N\) suivante :
$$ N = \sum\limits_{i=1}^n {p'}_i^b.{{p'}_i^a}^T = \sum\limits_{i=1}^n \left[ \begin{matrix} {x'}_i^b \ {y'}_i^b \end{matrix} \right]. \left[ \begin{matrix} {x'}_i^a & {y'}_i^a \end{matrix} \right] $$
Décomposons \(N\) en valeurs singulières :
$$ N=U.\Sigma.V^T $$
La matrice de rotation est donnée par :
$$ R=V.U^T $$
L’angle de rotation peut être extrait de la matrice \(R\) :
$$ \alpha=atan2(R_{21},R_{11}) $$
En appliquant la rotation sur les nuages centrés, nous obtenons le résultat suivant :
Téléchargements
Crédit: Ce post a été inspiré par l’excellent rapport de Hans Martin Kjer et Jakob Wilm : Evaluation of surface registration algorithms for PET motion correction.
Voir aussi
- Splines avec la méthode de Catmull-Rom
- Tester si un nombre est premier en ligne
- Vérifier qu’un point appartient à un segment
- Produit vectoriel (cross product)
- Principales règles de dérivation
- Principales dérivées
- Produit scalaire (dot product)
- Comment calculer les points d'intersection de deux cercles ?
- Comment tester si quatre points sont coplanaires ?
- Principales primitives (calculs intégrals)
- Moindres carrés : approximation avec un polynôme du second degré
- Approximation d'un cercle avec la méthode des moindres carrés
- Approximation d'une sphère avec la méthode des moindres carrés
- Les maths derrière l'ACP
- Résoudre un polynôme du second degré
- Simplificateur de racines carrées en ligne
- Valeurs remarquables des cosinus, sinus et tangeantes
- Décomposition en valeurs singulières (SVD) d’une matrice 2×2
- Segments tangents à deux cercles
- Comprendre les matrices de covariance
- ACP pondérée
