Cómo calcular qué matriz transformará los puntos especificados en otros puntos especificados

Question

Quiero transformar una imagen.

Por lo que he podido averiguar, puedo conseguirlo con una matriz, ¿no?

Así que este es mi problema: ¿cómo puedo obtener esta matriz si lo único que conozco son los siguientes puntos de inicio y final?

$$\begin{matrix} \text{Starting Points} & \text{Target Points} \\ \mathrm{TL}(3,5) & \mathrm{TL}'(0,3) \\ \mathrm{TR}(5,5) & \mathrm{TR}'(3,3) \\ \mathrm{LL}(2,2) & \mathrm{LL}'(0,0) \\ \mathrm{LR}(6,1) & \mathrm{LR}'(3,0) \end{matrix}$$

Answer 1

Muchos paquetes gráficos tienen funciones para construir una transformación de 4 puntos a 4 puntos del tipo que usted necesita. Por ejemplo, Qt tiene QTransform::quadToSquare y QTransform::quadToQuad, y OpenCV tiene GetPerspectiveTransform.

La transformación no puede ser lineal o afín, tiene que ser una transformación "en perspectiva".

Si quieres codificarlo tú mismo, este artículo te dice cómo. Las fórmulas de ese artículo se muestran más claramente a continuación:

Si queremos transformar los cuatro puntos $(x_i, y_i)$ a los cuatro puntos $(u_i, v_i)$ para $i=0,1,2,3$ podemos utilizar una transformación de perspectiva de la forma $$u_i = \frac{a_0 x_i + a_1 y_i + a_2}{c_0 x_i + c_1 y_i + 1 } \quad ; \quad v_i = \frac{b_0 x_i + b_1 y_i + b_2}{c_0 x_i + c_1 y_i + 1 }$$ Los ocho coeficientes desconocidos $a_0, a_1, a_2, b_0, b_1, b_2, c_0, c_1$ se puede calcular resolviendo el siguiente sistema lineal:

$$\begin{bmatrix} x_0 & y_0 & 1 & 0 & 0 & 0 & -x_0u_0 & -y_0u_0 \\ x_1 & y_1 & 1 & 0 & 0 & 0 & -x_1u_1 & -y_1u_1 \\ x_2 & y_2 & 1 & 0 & 0 & 0 & -x_2u_2 & -y_2u_2 \\ x_3 & y_3 & 1 & 0 & 0 & 0 & -x_3u_3 & -y_3u_3 \\ 0 & 0 & 0 & x_0 & y_0 & 1 & -x_0v_0 & -y_0v_0 \\ 0 & 0 & 0 & x_1 & y_1 & 1 & -x_1v_1 & -y_1v_1 \\ 0 & 0 & 0 & x_2 & y_2 & 1 & -x_2v_2 & -y_2v_2 \\ 0 & 0 & 0 & x_3 & y_3 & 1 & -x_3v_3 & -y_3v_3 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ b_0 \\ b_1 \\ b_2 \\ c_0 \\ c_1 \end{bmatrix} = \begin{bmatrix} u_0 \\ u_1 \\ u_2 \\ u_3 \\ v_0 \\ v_1 \\ v_2 \\ v_3 \end{bmatrix}$$

Hay muchos paquetes de software disponibles para resolver sistemas lineales de ecuaciones. Una opción es el libro/paquete "Numerical Recipes", que tiene funciones llamadas ludcmp y lubksb. La primera de ellas calcula la descomposición LU de una matriz, y la segunda utiliza esta descomposición LU para resolver un sistema lineal. Hay una larga discusión sobre cómo usar ludcmp y lubksb aquí .

En su ejemplo particular, tenemos $$(x_0, y_0) = (3,5) \\ (x_1, y_1) = (5,5) \\ (x_2, y_2) = (2,2) \\ (x_3, y_3) = (6,1) \\ (u_0, v_0) = (0,3) \\ (u_1, v_1) = (3,3) \\ (u_2, v_2) = (0,0) \\ (u_3, v_3) = (3,0) \\ $$ El sistema de ecuaciones es $$3 a_0 + 5 a_1 + a_2 = 0 \\ 5 a_0 + 5 a_1 + a_2 - 15 c_0 - 15 c_1 = 3 \\ 2 a_0 + 2 a_1 + a_2 = 0 \\ 6 a_0 + a_1 + a_2 - 18 c_0 - 3 c_1 = 3 \\ 3 b_0 + 5 b_1 + b_2 - 9 c_0 - 15 c_1 = 3 \\ 5 b_0 + 5 b_1 + b_2 - 15 c_0 - 15 c_1 = 3 \\ 2 b_0 + 2 b_1 + b_2 = 0 \\ 6 b_0 + b_1 + b_2 = 0$$ He resuelto este sistema de ecuaciones utilizando Mathematica, y he obtenido $$a_0 = \frac{36}{49} \quad ; \quad a_1 = -\frac{12}{49} \quad ; \quad a_2 = -\frac{48}{49} \\ b_0 = \frac{24}{245} \quad ; \quad b_1 = \frac{96}{245} \quad ; \quad b_2 = -\frac{48}{49} \\ c_0 = \frac{8}{245} \quad ; \quad c_1 = -\frac{33}{245}$$ Por lo tanto, la transformación requerida (después de algunas simplificaciones) es $$u = \frac{60 (3 x-y-4)}{8 x-33 y+245} \\ v = \frac{24 (x+4 y-10)}{8 x-33 y+245}$$ Puedes confirmar fácilmente que esta transformación mapea correctamente los cuatro puntos dados.

Answer 2

Busquemos una transformación afín para hacer lo que te gusta. Esta transformación actuará sobre puntos del plano (vectores en $\mathbb{R}^2$ ) y producirán puntos en el plano, y estarán dados por $T(\vec{x}) = A \vec{x} + \vec{v}$ para alguna matriz $A$ y el vector $\vec{v}$ que encontraremos. Como tomamos puntos en el plano y producimos puntos en el plano, $A$ debe ser $2 \times 2$ , digamos que con entradas $a,b,c,d$ y $\vec{v}$ también está en el plano, con entradas $e,f$ .

Ahora sus puntos nos dan 8 restricciones sobre 6 variables $a,b,c,d,e,f$ - vamos a escribir un par y puedes terminar el resto y simplemente resolver el sistema de ecuaciones lineales resultante (digamos, por eliminación gaussiana, o por Wolfram Alpha).

Mapas del primer punto $(3,5) \to (0,3)$ así que $$3a+5b+e = 0 \text{ and } 3c+5d+f = 3$$ Mapas del segundo punto $(5,5) \to (3,3)$ así que $$5a+5b+e = 3 \text{ and } 5c+5d+f = 3$$ Mapas del tercer punto $(2,2) \to (0,0)$ así que $$2a+2b+e = 0 \text{ and } 2c+2d+f = 0$$ Mapas del cuarto punto $(1,6) \to (3,0)$ así que $$1a+6b+e = 3 \text{ and } 1c+6d+f = 0$$

Resumiendo llegamos a resolver $$\begin{bmatrix} 3 & 5 & 1 \\ 5 & 5 & 1 \\ 2 & 2 & 1 \\ 1 & 6 & 1 \end{bmatrix} \begin{bmatrix} a & c\\ b & d\\ e & f\end{bmatrix} = \begin{bmatrix} 0 & 3\\ 3 & 3 \\ 0 & 0 \\ 3 & 0\end{bmatrix}$$ Puedes usar los tres primeros para resolver y conectarlo al cuarto para comprobarlo.

Answer 3

Lo que (presumiblemente) buscas realizar se llama transformación afín. Una transformación afín en dos dimensiones está determinada por cómo tres Transformación de puntos. Así que puede o no haber una que haga lo que quieres aquí. Es posible (y muy común en los gráficos por ordenador) representar una transformación afín como una transformación lineal mediante la adición de una dimensión extra, pero en esta coyuntura me gustaría especular que probablemente es mejor seguir con la forma afín por ahora.

Answer 4

No has especificado si buscas una transformación lineal u otra. Dado que menciona la matriz y no las funciones de los puntos de inicio, estoy asumiendo que es una lineal que desea.

Dado que no se especifica ninguna otra condición (por ejemplo, la preservación de la longitud, los ángulos, etc.), sus coordenadas x e y no necesitan estar relacionadas por condiciones adicionales, por lo que puede escribir cada punto de inicio como $(x_i,y_i)$ y cada punto de destino como $(x^\prime_i,y^\prime_i)$ . Definir $\bf{X} = [x_1 ... x_4 y_1 ... y_4]$ y $\bf{Y} = [x^\prime_1 ... x^\prime_4 y^\prime_1 ... y^\prime_4]$ . A continuación, puede establecer un $8\times 8$ sistema lineal $\bf{Y} = A \cdot \bf{X}$ con los elementos de la matriz $A$ como incógnitas. Sin embargo, tendrá que especificar otros 4 puntos ficticios y sus imágenes para obtener una posible solución matricial.