Accordez-moi une faveur, prenez quelques instants pour découvrir mon dernier projet.

Merci, Lulu

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).

Illustration de la transformation entre deux nuages de points

$$ 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\).

Association des points entre les deux nuages

Translation

Pour commencer, calculons le centre de gravité de chaque nuage de points:

Centre de gravité des deux nuages 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} $$

Déplacement des nuages de points sur l'origine du repère

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 :

Results of merging two set of points

Téléchargements

cloudTrans_matlab.zip

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


Dernière mise à jour : 13/04/2019