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

Les source, scripts et codes Matlab Matlab (exemple de cette page) peuvent être téléchargés ici :

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 : 11/06/2018