Stima delle rotazioni e traslazioni

Ci sono diverse tecniche per ottenere una stima ottima della trasformazione di rotazione e traslazione rigida tra punti appartenenti al medesimo spazio. Per stima ottima si intende la stima alla massima verosimiglianza, dove il rumore di osservazione $\xi_i$ è totalmente additivo nello spazio $\mathbb{R}^{n}$ in cui vivono i punti.

Siano pertanto due insiemi di punti $\left\{ \prescript{1}{}{\mathbf{x}}_i \right\}$ e $\left\{ \prescript{2}{}{\mathbf{x}}_i \right\}$ tali che siano messi in relazione da

$$\prescript{2}{}{\mathbf{x}}_i = \prescript{2}{}{\mathbf{R}}_... ...cript{1}{}{\mathbf{x}}_i + \prescript{2}{}{\mathbf{t}} + \xi_i$$ (1.68)

come in equazione (1.64) ma con il vettore rumore $\xi_i$.

Per risolvere il problema ottimo $(\hat{\mathbf{R}}, \hat{\mathbf{t}})$ che trasforma tutti i punti da $\mathbf{x}^{1}$ a $\mathbf{x}^{2}$ è richiesto un criterio ai minimi quadrati che ottimizzi una funzione costo del tipo

$$S = \sum_i w_i \Vert \left( \prescript{2}{}{\mathbf{R}}_1 \... ...{}{\mathbf{t}} \right) - \prescript{2}{}{\mathbf{x}}_i \Vert^2$$ (1.69)

dove $w_i$ sono eventuali prior associati ad ogni campione. La soluzione ai minimi quadrati in forma non lineare chiaramente ha problemi di minimi locali.

Un risultato notevole che riguarda il vettore traslazione si ricava applicando le classiche derivate $0 = \partial S / \partial \mathbf{t}$ all'equazione (1.69) che si annulla in

$$\hat{\mathbf{t}} = \bar{\prescript{2}{}{\mathbf{x}}} - \hat{\mathbf{R}} \bar{\prescript{1}{}{\mathbf{x}}}$$ (1.70)

e pertanto data $\mathbf{R}$ è immediato trovare la traslazione in forma ottima o viceversa è sufficiente ricavare la sola rotazione $\hat{\mathbf{R}}$ per risolvere il problema delle pose. A questo risultato si arriva anche da un punto di vista intuitivo: il centroide delle due serie di punti a seguito di una trasformazione rigida deve seguire la relazione di equazione (1.68).

La rotazione $\mathbf{R}$ ottima deve minimizzare pertanto

$$S = \sum_i w_i \Vert \prescript{2}{}{\mathbf{R}}_1 \prescript{1}{}{\mathbf{p}}_i - \prescript{2}{}{\mathbf{p}}_i \Vert^2$$ (1.71)

avendo definito $\mathbf{p}_i = \mathbf{x}_i - \bar{\mathbf{x}}$. Pertanto qualunque problema di registrazione di pose in $n$ dimensioni si riduce sempre ad un problema a $n$ DOF.

Una prima tecnica per calcolare la rotazione fa uso delle componenti principali (si veda sezione 2.10.1). Le componenti principali estratte da ogni insieme di punti separatamente sono una base dello spazio. È possibile determinare una rotazione che le fa combaciare tali basi in quanto ricavate le matrici degli autovettori colonna $\mathbf{R}_1$ e $\mathbf{R}_2$ si ottiene direttamente $\mathbf{R} = \mathbf{R}_2 \left( \mathbf{R}_1 \right)^{\top}$. Possono esistere tuttavia più soluzioni (e ognuna andrebbe verificata) e a causa del rumore ricavare gli assi attraverso PCA può diventare estremamente inaffidabile (ad esempio se la distribuzione risultasse circolare risulterebbe impossibile qualsiasi stima).

La cosa migliore per minimizzare (1.71) consiste nel minimizzare o meglio massimizzare:

$$\begin{array}{l} \argmin_{\mathbf{R}} \sum_i w_i \Vert \pre... ...\mathbf{P}_1 \mathbf{W} \mathbf{P}^{\top}_2 \right) \end{array}$$ (1.72)

ovvero minimizzare il sistema di equazioni (1.69) è equivalente a massimizzare la traccia della matrice $\hat{\mathbf{R}} \mathbf{H}$ dove $\mathbf{H}$ è la matrice di correlazione tra le due nuvole di punti definita come

$$\mathbf{H} = \cov (\prescript{1}{}{\mathbf{x}}, \prescript{... ...athbf{x}}_i - \bar{\prescript{2}{}{\mathbf{x}}} \right)^{\top}$$ (1.73)

Si dimostra che la matrice $\hat{\mathbf{R}}$ che massimizza la traccia di $\hat{\mathbf{R}} \mathbf{H}$ è

$$\hat{\mathbf{R}} = \mathbf{V} \mathbf{U}^{\top}$$ (1.74)

avendo decomposto a valori singolari $\mathbf{H} = \mathbf{U} \Sigma \mathbf{V}^{\top}$. Questo algoritmo per la prima volta viene descritto in (Kab76), riscoperto in (AHB87), ma sicuramente migliorato in (Ume91) (in particolare il caso $\det\hat{\mathbf{R}}=-1$) e normalmente viene chiamato algoritmo di Kabsch-Umeyama.

Questa soluzione, molto più stabile di quella basata su PCA e sempre valida per $n > 3$, richiede una attenzione particolare nei soli casi bidimensionali e tridimensionali per gestire eventuali riflessioni (in tal caso infatti il determinante della matrice risultante potrebbe risultare negativo).

Lo “svantaggio” della tecnica basata su SVD rispetto a quella basata su PCA è la richiesta che le associazioni tra i punti delle due distribuzioni siano corrette.

L'unione delle due tecniche insieme ad un approccio iterativo prende il nome di Iterative Closest Point (ICP).