Transformación lineal directa

La transformación lineal directa ( DLT ) es un algoritmo que resuelve un conjunto de variables a partir de un conjunto de relaciones de similitud:

${\displaystyle \mathbf {x} _{k}\propto \mathbf {A} \,\mathbf {y} _{k}}$   para${\displaystyle \,k=1,\ldots ,N}$

donde y son vectores conocidos, denota igualdad hasta una multiplicación escalar desconocida, y es una matriz (o transformación lineal) que contiene las incógnitas a resolver. ${\displaystyle \mathbf {x}_{k}}$${\displaystyle \mathbf {y} _ {k}}$${\estilo de visualización \,\propto }$${\displaystyle \mathbf {A}}$

Este tipo de relación aparece con frecuencia en la geometría proyectiva . Algunos ejemplos prácticos son la relación entre los puntos 3D de una escena y su proyección sobre el plano de la imagen de una cámara estenopeica ^[1] y las homografías .

Un sistema ordinario de ecuaciones lineales

${\displaystyle \mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}}$   para${\displaystyle \,k=1,\ldots ,N}$

se puede resolver, por ejemplo, reescribiéndola como una ecuación matricial donde las matrices y contienen a los vectores y en sus respectivas columnas. Dado que existe una única solución, ésta viene dada por ${\displaystyle \mathbf {X} =\mathbf {A} \,\mathbf {Y} }$${\displaystyle \mathbf {X}}$${\displaystyle \mathbf {Y}}$${\displaystyle \mathbf {x}_{k}}$${\displaystyle \mathbf {y} _ {k}}$

${\displaystyle \mathbf {A} =\mathbf {X} \,\mathbf {Y} ^{T}\,(\mathbf {Y} \,\mathbf {Y} ^{T})^{-1} .}$

También se pueden describir soluciones en el caso de que las ecuaciones estén sobre o subdeterminadas.

Lo que hace que el problema de transformación lineal directa sea distinto del caso estándar anterior es el hecho de que los lados izquierdo y derecho de la ecuación definitoria pueden diferir en un factor multiplicativo desconocido que depende de k . Como consecuencia, no se puede calcular como en el caso estándar. En cambio, las relaciones de similitud se reescriben como ecuaciones homogéneas lineales adecuadas que luego se pueden resolver mediante un método estándar. La combinación de reescribir las ecuaciones de similitud como ecuaciones lineales homogéneas y resolverlas mediante métodos estándar se conoce como algoritmo de transformación lineal directa o algoritmo DLT . DLT se atribuye a Ivan Sutherland. ^[2]${\displaystyle \mathbf {A}}$

Supongamos que . Sean y dos vectores conocidos, y queremos encontrar la matriz tal que ${\displaystyle k\en \{1,...,N\}}$${\displaystyle \mathbf {x} _{k}=(x_{1k},x_{2k})\in \mathbb {R} ^{2}}$${\displaystyle \mathbf {y} _{k}=(y_{1k},y_{2k},y_{3k})\in \mathbb {R} ^{3}}$${\displaystyle 2\times 3}$${\displaystyle \mathbf {A}}$

${\displaystyle \alpha _ {k}\,\mathbf {x} _ {k}=\mathbf {A} \,\mathbf {y} _ {k}}$

¿Dónde está el factor escalar desconocido relacionado con la ecuación k ? ${\displaystyle \alpha _{k}\neq 0}$

Para deshacerse de los escalares desconocidos y obtener ecuaciones homogéneas, defina la matriz antisimétrica

${\displaystyle \mathbf {H} ={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}}$

y multiplica ambos lados de la ecuación con desde la izquierda ${\displaystyle \mathbf {x} _{k}^{T}\,\mathbf {H} }$

${\displaystyle {\begin{alineado}(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\alpha _{k}\,\mathbf {x} _{k} &=(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\mathbf {A} \,\mathbf {y} _{k}\\\alpha _{k}\,\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}&=\mathbf { x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}\end{alineado}}}$

Dado que las siguientes ecuaciones homogéneas, que ya no contienen los escalares desconocidos, están a la mano ${\displaystyle \mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}=0,}$

${\displaystyle \mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}=0}$

Para resolver este conjunto de ecuaciones, considere los elementos de los vectores y la matriz : ${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {y} _{k}}$${\displaystyle \mathbf {A} }$

${\displaystyle \mathbf {x} _{k}={\begin{pmatrix}x_{1k}\\x_{2k}\end{pmatrix}}}$,   , y   ${\displaystyle \mathbf {y} _{k}={\begin{pmatrix}y_{1k}\\y_{2k}\\y_{3k}\end{pmatrix}}}$${\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix}}}$

y la ecuación homogénea anterior se convierte en

${\displaystyle 0=a_{11}\,x_{2k}\,y_{1k}-a_{21}\,x_{1k}\,y_{1k}+a_{12}\,x_{2k}\,y_{2k}-a_{22}\,x_{1k}\,y_{2k}+a_{13}\,x_{2k}\,y_{3k}-a_{23}\,x_{1k}\,y_{3k}}$   para${\displaystyle \,k=1,\ldots ,N.}$

Esto también se puede escribir en forma matricial:

${\displaystyle 0=\mathbf {b} _{k}^{T}\,\mathbf {a} }$   para${\displaystyle \,k=1,\ldots ,N}$

donde y ambos son vectores de 6 dimensiones definidos como ${\displaystyle \mathbf {b} _{k}}$${\displaystyle \mathbf {a} }$

${\displaystyle \mathbf {b} _{k}={\begin{pmatrix}x_{2k}\,y_{1k}\\-x_{1k}\,y_{1k}\\x_{2k}\,y_{2k}\\-x_{1k}\,y_{2k}\\x_{2k}\,y_{3k}\\-x_{1k}\,y_{3k}\end{pmatrix}}}$   y   ${\displaystyle \mathbf {a} ={\begin{pmatrix}a_{11}\\a_{21}\\a_{12}\\a_{22}\\a_{13}\\a_{23}\end{pmatrix}}.}$

Hasta ahora, tenemos 1 ecuación y 6 incógnitas. Un conjunto de ecuaciones homogéneas se puede escribir en forma matricial.

${\displaystyle \mathbf {0} =\mathbf {B} \,\mathbf {a} }$

donde es una matriz que contiene los vectores conocidos en sus filas. La incógnita se puede determinar, por ejemplo, mediante una descomposición en valores singulares de ; es un vector singular derecho de correspondiente a un valor singular que es igual a cero. Una vez que se ha determinado, los elementos de la matriz se pueden reorganizar a partir del vector . Observe que la escala de o no es importante (excepto que debe ser distinta de cero) ya que las ecuaciones definitorias ya permiten la escala de incógnitas. ${\displaystyle \mathbf {B} }$${\displaystyle N\times 6}$${\displaystyle \mathbf {b} _{k}}$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {A} }$

En la práctica, los vectores y pueden contener ruido, lo que significa que las ecuaciones de similitud son solo aproximadamente válidas. En consecuencia, puede que no haya un vector que resuelva la ecuación homogénea de manera exacta. En estos casos, se puede utilizar una solución de mínimos cuadrados totales eligiendo como vector singular correcto el valor singular más pequeño de${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {y} _{k}}$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {0} =\mathbf {B} \,\mathbf {a} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {B} .}$

El ejemplo anterior tiene y , pero la estrategia general para reescribir las relaciones de similitud en ecuaciones lineales homogéneas se puede generalizar a dimensiones arbitrarias para ambos y${\displaystyle \mathbf {x} _{k}\in \mathbb {R} ^{2}}$${\displaystyle \mathbf {y} _{k}\in \mathbb {R} ^{3}}$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {y} _{k}.}$

Si y las expresiones anteriores aún pueden conducir a una ecuación ${\displaystyle \mathbf {x} _{k}\in \mathbb {R} ^{2}}$${\displaystyle \mathbf {y} _{k}\in \mathbb {R} ^{q}}$

${\displaystyle 0=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}}$   para   ${\displaystyle \,k=1,\ldots ,N}$

donde ahora es Cada k proporciona una ecuación en los elementos desconocidos de y juntas estas ecuaciones se pueden escribir para la matriz conocida y el vector 2q -dimensional desconocido . Este vector se puede encontrar de manera similar a antes. ${\displaystyle \mathbf {A} }$${\displaystyle 2\times q.}$${\displaystyle 2q}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {B} \,\mathbf {a} =\mathbf {0} }$${\displaystyle N\times 2\,q}$${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {a} .}$

En el caso más general y . La principal diferencia con respecto a antes es que la matriz ahora es y antisimétrica. Cuando el espacio de dichas matrices ya no es unidimensional, es de dimensión ${\displaystyle \mathbf {x} _{k}\in \mathbb {R} ^{p}}$${\displaystyle \mathbf {y} _{k}\in \mathbb {R} ^{q}}$${\displaystyle \mathbf {H} }$${\displaystyle p\times p}$${\displaystyle p>2}$

${\displaystyle M={\frac {p\,(p-1)}{2}}.}$

Esto significa que cada valor de k proporciona M ecuaciones homogéneas del tipo

${\displaystyle 0=\mathbf {x} _{k}^{T}\,\mathbf {H} _{m}\,\mathbf {A} \,\mathbf {y} _{k}}$   por     y para${\displaystyle \,m=1,\ldots ,M}$${\displaystyle \,k=1,\ldots ,N}$

donde es una base M -dimensional del espacio de matrices antisimétricas. ${\displaystyle \mathbf {H} _{m}}$${\displaystyle p\times p}$

En el caso de que p = 3 se pueden elegir las tres matrices siguientes${\displaystyle \mathbf {H} _{m}}$

${\displaystyle \mathbf {H} _{1}={\begin{pmatrix}0&0&0\\0&0&-1\\0&1&0\end{pmatrix}}}$,   ,   ${\displaystyle \mathbf {H} _{2}={\begin{pmatrix}0&0&1\\0&0&0\\-1&0&0\end{pmatrix}}}$${\displaystyle \mathbf {H} _{3}={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&0\end{pmatrix}}.}$

En este caso particular, las ecuaciones lineales homogéneas se pueden escribir como

${\displaystyle \mathbf {0} =[\mathbf {x} _{k}]_{\times }\,\mathbf {A} \,\mathbf {y} _{k}}$   para   ${\displaystyle \,k=1,\ldots ,N}$

donde es la representación matricial del producto vectorial . Observe que esta última ecuación tiene un valor vectorial; el lado izquierdo es el elemento cero en . ${\displaystyle [\mathbf {x} _{k}]_{\times }}$${\displaystyle \mathbb {R} ^{3}}$

Cada valor de k proporciona tres ecuaciones lineales homogéneas en los elementos desconocidos de . Sin embargo, dado que tiene rango = 2, como máximo dos ecuaciones son linealmente independientes. En la práctica, por lo tanto, es común usar solo dos de las tres matrices , por ejemplo, para m = 1, 2. Sin embargo, la dependencia lineal entre las ecuaciones depende de , lo que significa que en casos desafortunados habría sido mejor elegir, por ejemplo, m = 2, 3. Como consecuencia, si el número de ecuaciones no es una preocupación, puede ser mejor usar las tres ecuaciones cuando se construye la matriz. ${\displaystyle \mathbf {A} }$${\displaystyle [\mathbf {x} _{k}]_{\times }}$${\displaystyle \mathbf {H} _{m}}$${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {B} }$

La dependencia lineal entre las ecuaciones lineales homogéneas resultantes es una preocupación general para el caso p > 2 y debe abordarse ya sea reduciendo el conjunto de matrices antisimétricas o permitiendo que se vuelvan más grandes de lo necesario para determinar${\displaystyle \mathbf {H} _{m}}$${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {a} .}$

• Richard Hartley y Andrew Zisserman (2003). Geometría de vista múltiple en visión artificial . Cambridge University Press. ISBN 978-0-521-54051-3.

• Estimación de homografía por Elan Dubrofsky (§2.1 describe el "algoritmo DLT básico")

• Un solucionador DLT basado en MATLAB de Hsiang-Jen (Johnny) Chien