Cómo resolver un sistema sobredeterminado de mapeos de puntos mediante rotación y traslación

Question

Tengo un conjunto de puntos en un sistema de coordenadas $P_1, \ldots, P_n$ y sus correspondientes puntos en otro sistema de coordenadas $Q_1, \ldots , Q_n$ . Todos los puntos están en $\mathbb{R}^3$ .

Estoy buscando una transformación que se ajuste al máximo y que consista en una rotación y una traslación. Por ejemplo

$$ \min_{A,b} \sum (A p_i + b - q_i)^2 , \quad A \in \operatorname{SO}(3), b \in \mathbb{R}^3$$

¿Puede alguien darme alguna pista en qué dirección debo buscar?

Ya he mirado:

http://en.wikipedia.org/wiki/Least_squares (no sé cómo incluir la restricción a las matrices ortogonales)

http://en.wikipedia.org/wiki/Singular_value_decomposition (He pensado en empezar con una matriz de $\operatorname{GL}(3)$ y utilizar después la "matriz ortogonal de mejor ajuste" como se indica en http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem pero eso parecía demasiado complicado)

Answer 1

Como se describe en mi comentario, primero hay que restar los centroides para reducir el problema a

$$ \min_A\sum_i\|Ap_i-q_i\|^2\;,\quad A\in SO(3)\;. $$

Ese problema está resuelto aquí (página 9), con los vectores $p_i$ y $q_i$ ensamblados en las matrices $B$ y $A$ (con el presente $A$ correspondiente a $Q$ ), pero lo escribiré con los vectores en su notación.

El problema parece ser cuadrático en $A$ pero no lo es, ya que

$$ \begin{align} \|Ap_i-q_i\|^2&=(Ap_i-q_i)^\top(Ap_i-q_i) \\ &=p_iA^\top Ap_i+q_i^\top q_i-2q_i^\top Ap_i \\ &= p_ip_i+q_i^\top q_i-2q_i^\top Ap_i\;, \end{align} $$

desde $A$ es ortogonal. Por lo tanto, todo lo que tenemos que hacer es maximizar

$$ \def\tr{\operatorname{tr}} \sum_iq_i^\top Ap_i=\sum_i\tr q_i^\top Ap_i=\sum_i\tr p_iq_i^\top A=\tr\left(\left(\sum_ip_iq_i^\top\right)A\right)=:\tr B^\top A $$

sujeto a la restricción $A\in SO(3)$ . Ese problema se resuelve en el documento enlazado anteriormente, utilizando el descomposición de valores singulares $B=U\Sigma V^\top$ . Para $A\in O(3)$ la solución es $A=UV^\top$ mientras que si $A$ se limita a $SO(3)$ la solución es $A=UZV^\top$ , donde $Z$ es la matriz identidad, pero con el último elemento diagonal sustituido por $-1$ si esto es necesario para hacer $\det A$ positivo.

Ver también esta pregunta [que mientras tanto ha recibido otra respuesta que deriva la solución anterior a $\tr B^\top A\to\min$ para el caso $A\in O(n)$ ].

Answer 2

Intento resumir lo que tengo que hacer en esta respuesta:

1. Convertir el $P_i$ s y $Q_i$ s:

   $\overline{p}$ y $\overline{q}$ son el centro de gravedad del conjunto de puntos a cartografiar: $$ \overline{p} := \frac1i\sum_iP_i, \quad \overline{q} := \frac1i\sum_iQ_i$$ Haz que los puntos sean relativos a sus respectivos centros de gravedad: $$ p_i := P_i - \overline{p}, \quad q_i := Q_i - \overline{q}$$ Esto elimina la necesidad de considerar la traducción $b$ en la optimización. $b$ se puede calcular como $\overline{q} - A \overline{p}$ una vez que hayamos determinado el $A$ .

2. Calcular $B$ como $$B = \left(\sum_i p q^\top \right)^\top = \sum_i q p ^\top$$

3. Realizar la descomposición SVD de $B$ : $$ B = U \Sigma V^\top$$

4. Óptimo $A$ si $A \in \operatorname{O}(3)$ (no $A \in \operatorname{SO}(3)$ como se indica en la pregunta): $$ A := U V^\top $$ Óptimo $b$ : $$ b := \overline{q} - A \overline{p}$$

5. Óptimo $A$ si $A \in \operatorname{SO}(3)$ iría aquí pero creo que $A \in \operatorname{O}(3)$ es lo que realmente estoy buscando.