Least Squares Fit encontrar transformación entre puntos

Question

Estamos utilizando la biblioteca OpenCV estimateRigidTransform función para encontrar una correspondencia entre dos 2D punto de conjuntos. La asignación de apoyos de rotación uniforme, escala y traslación.

$$T=\left[ \begin{array}{cc|c} s\cos(\theta)&-s\sin(\theta)&T_x\\ s\sin(\theta)&s\cos(\theta)&T_y \end{array} \right] $$

La documentación de las reclamaciones de la función que resuelve el siguiente problema.

$$[A^*|b^*] = arg \min _{[A|b]} \sum _i \| \texttt{dst}[i] - A { \texttt{src}[i]}^T - b \| ^2$$ Aquí el lado izquierdo es nuestro transformar $T$ $dst$ $src$ son el punto dos conjuntos. Parece que para encontrar la transformación que minimiza el error (distancia) entre el $dst$ de punto de ajuste y el $src$ punto de ajuste después de la transformación.

El más definida problema de $N$ ecuaciones se convierte en un sistema de 4 ecuaciones y 4 incógnitas ($s\cos(\theta)$, $s\sin(\theta)$, $T_x$, $T_y$) como se muestra a continuación. $(a_x,a_y)$ es un punto en el primer punto de set $A$, e $(b_x,b_y)$ es un punto en el segundo punto de set $B$. Tanto el punto de conjuntos de contener $N$ puntos. Los puntos que ya han sido igualado entre los dos conjuntos, por lo que el primer punto de set $A$ deben asignar al primer punto de set $B$ y así sucesivamente.

Todas las sumatorias se producen en el conjunto de la $N$ punto de pares.

$$\left[ \begin{array}{cccc} \sum_{} (a_x^2+a_y^2)&0&\sum_{} a_x&\sum_{} a_y\\ 0&\sum_{} (a_x^2+a_y^2)&-\sum_{} a_y&\sum_{} a_x\\ \sum_{} a_x&-\sum_{} a_y&N&0\\ \sum_{} a_y&\sum_{} a_x&0&N\\ \end{array} \right]\left[ \begin{array}{c} s\cos(\theta)\\ s\sin(\theta)\\ T_x\\ T_y\\ \end{array} \right]=\left[ \begin{array}{c} \sum_{} (a_xb_x+a_yb_y)\\ \sum_{} (a_xb_y-a_yb_x)\\ \sum_{} b_x\\ \sum_{} b_y\\ \end{array} \right] $$

Tengo estas ecuaciones a partir de ingeniería inversa del código fuente. La documentación dice que autovalor de descomposición se utiliza para resolver el sistema. Estoy tratando de determinar dónde este conjunto de ecuaciones que ha venido. La primera y la segunda filas son un misterio para mí. Reconozco la tercera y cuarta filas como sumar ambos lados de la ecuación para la asignación de $x$$y$.

$$s\cos(\theta)\sum_{} a_x-s\sin(\theta)\sum_{} a_y+NT_x=\sum_{} b_x$$ $$\sum_{} (a_xs\cos(\theta)-a_ys\sin(\theta)+T_x)=\sum_{} b_x$$ y $$s\cos(\theta)\sum_{} a_y+s\sin(\theta)\sum_{} a_x+NT_y=\sum_{} b_y$$ $$\sum_{} (a_xs\sin(\theta)+a_ys\cos(\theta)+T_y)=\sum_{} b_y$$ ¿Alguien sabe donde la primera y la segunda filas? Supongo OpenCV es la aplicación de alguna forma de mínimos cuadrados apropiado para encontrar la transformación que mejor asigna los puntos.

EDITAR:

Después de jugar un poco más, he de reconocer que la primera fila como: $$a_x*row3+a_y*row4$$ Y la segunda fila como: $$-a_y*row3+a_x*row4$$ Las dos primeras filas se crean mediante la combinación de los 2 últimos de diferentes maneras. No esta de crear un conjunto de ecuaciones que no son independientes? ¿O es que el sumatorias en las ecuaciones y el error residual de alguna manera de mantener su independencia?

Answer 1

Supongo OpenCV es la aplicación de alguna forma de mínimos cuadrados apropiado para encontrar la transformación que mejor asigna los puntos.

Tienes razón, y esta idea está en el núcleo de lo que está pasando aquí. Básicamente usted desea

$$\begin{bmatrix} a_x & -a_y & 1 & 0 \\ a_y & a_x & 0 & 1 \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}\cdot\begin{bmatrix} s\cos\theta \\ s\sin\theta \\ T_x \\ T_y \end{bmatrix}\approx\begin{bmatrix} b_x \\ b_y \\ \vdots \end{bmatrix}$$

Este es un sobredeterminada sistema de ecuaciones con dos ecuaciones para cada par de puntos, $2N$ ecuaciones en total. Para solucionar esto usando lineal de mínimos cuadrados aproximación, se multiplican ambos lados con la transposición de la izquierda de la matriz.

$$ \begin{bmatrix} a_x & a_y & \cdots \\ -a_y & a_x & \cdots \\ 1 & 0 & \cdots \\ 0 & 1 & \cdots \end{bmatrix}\cdot \begin{bmatrix} a_x & -a_y & 1 & 0 \\ a_y & a_x & 0 & 1 \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}= \begin{bmatrix} \sum(a_x^2+a_y^2) & 0 & \sum a_x & \sum a_y \\ 0 & \sum(a_x^2+a_y^2) & -\sum a_y & \sum a_x \\ \sum a_x & -\sum a_y & N & 0 \\ \sum a_y & \sum a_x & 0 & N \end{bmatrix} $$

para el lado izquierdo y

$$ \begin{bmatrix} a_x & a_y & \cdots \\ -a_y & a_x & \cdots \\ 1 & 0 & \cdots \\ 0 & 1 & \cdots \end{bmatrix}\cdot \begin{bmatrix} b_x \\ b_y \\ \vdots \end{bmatrix}= \begin{bmatrix} \sum(a_xb_x+a_yb_y) \\ \sum(a_xb_y-a_yb_x) \\ \sum b_x \\ \sum b_y \end{bmatrix} $$

para el lado derecho. Si ahora fuera a resolver esto mediante el inverso de la parte izquierda de la matriz, tendría que ser esencialmente el uso de un Moore-Penrose pseudoinverse, pero por lo general hay maneras más fáciles de resolver un sistema de ecuaciones, por ejemplo, usando eliminación Gaussiana o los vectores propios que usted ha mencionado. Así que la solución de la modificación del sistema de ecuaciones de darle la solución a su problema de mínimos cuadrados.

Espero que la nota era bastante clara. Tenga en cuenta que todas las filas resp. las columnas vienen en pares de dos, y yo sólo incluye el primer como el de la pareja.