Algoritmo de ocho puntos

El algoritmo de ocho puntos es un algoritmo utilizado en visión artificial para estimar la matriz esencial o la matriz fundamental relacionada con un par de cámaras estéreo a partir de un conjunto de puntos de imagen correspondientes. Fue introducido por Christopher Longuet-Higgins en 1981 para el caso de la matriz esencial. En teoría, este algoritmo se puede utilizar también para la matriz fundamental, pero en la práctica el algoritmo normalizado de ocho puntos , descrito por Richard Hartley en 1997, es más adecuado para este caso.

El nombre del algoritmo deriva del hecho de que estima la matriz esencial o la matriz fundamental a partir de un conjunto de ocho (o más) puntos de imagen correspondientes. Sin embargo, se pueden utilizar variaciones del algoritmo para menos de ocho puntos.

Restricción de coplanaridad

Más información: geometría epipolar

Ejemplo de geometría epipolar. Dos cámaras, con sus respectivos centros de puntos de proyección O _L y O _R , observan un punto P . La proyección de P sobre cada uno de los planos de imagen se denota p _L y p _R . Los puntos E _L y E _R son los epipolos.

Se puede expresar la geometría epipolar de dos cámaras y un punto en el espacio con una ecuación algebraica. Observe que, no importa donde el punto está en el espacio, los vectores , y pertenecen al mismo plano. Llame a las coordenadas del punto en el marco de referencia del ojo izquierdo y llame a las coordenadas de en el marco de referencia del ojo derecho y llame a la rotación y traslación entre los dos marcos de referencia. St es la relación entre las coordenadas de en los dos marcos de referencia. La siguiente ecuación siempre es válida porque el vector generado desde es ortogonal a ambos y  :${\displaystyle P}$${\displaystyle {\overline {O_{L}P}}}$${\displaystyle {\overline {O_{R}P}}}$${\displaystyle {\overline {O_{R}O_{L}}}}$${\displaystyle X_{L}}$${\displaystyle P}$${\displaystyle X_{R}}$${\displaystyle P}$${\displaystyle R,T}$${\displaystyle X_{R}=R(X_{L}-T)}$${\displaystyle P}$${\displaystyle T\wedge X_{L}}$${\displaystyle T}$${\displaystyle X_{L}}$

${\displaystyle X_{L}^{T}T\wedge X_{L}-T^{T}T\wedge X_{L}=(X_{L}-T)^{T}T\wedge X_{L}=0}$

Porque obtenemos ${\displaystyle I=R^{T}R}$

${\displaystyle (X_{L}-T)^{T}R^{T}RT\wedge X_{L}=0}$.

Reemplazando con , obtenemos${\displaystyle (X_{L}-T)^{T}R^{T}}$${\displaystyle X_{R}^{T}}$

${\displaystyle X_{R}^{T}RT\wedge X_{L}=X_{R}^{T}RSX_{L}=X_{R}^{T}EX_{L}=0}$

Observe que se puede pensar en una matriz; Longuet-Higgins usó el símbolo para denotarlo. El producto a menudo se denomina matriz esencial y se denota con .${\displaystyle T\wedge }$${\displaystyle S}$${\displaystyle RT\wedge =RS}$${\displaystyle E}$

Los vectores son paralelos a los vectores y, por lo tanto, la restricción de coplanaridad se cumple si sustituimos estos vectores. Si llamamos a las coordenadas de las proyecciones de en los planos de imagen izquierdo y derecho, entonces la restricción de coplanaridad se puede escribir como${\displaystyle {\overline {O_{L}p_{L}}},{\overline {O_{R}p_{R}}}}$${\displaystyle {\overline {O_{L}P}},{\overline {O_{R}P}}}$${\displaystyle y,y'}$${\displaystyle P}$

${\displaystyle y'^{T}\mathbf {E} y=0}$

Algoritmo basico

El algoritmo básico de ocho puntos se describe aquí para el caso de estimar la matriz esencial . Consta de tres pasos. Primero, formula una ecuación lineal homogénea , donde la solución está directamente relacionada con la ecuación y luego la resuelve, teniendo en cuenta que puede no tener una solución exacta. Finalmente, se gestionan las restricciones internas de la matriz resultante. El primer paso se describe en el artículo de Longuet-Higgins, el segundo y tercer paso son enfoques estándar en la teoría de la estimación.${\displaystyle \mathbf {E} }$${\displaystyle \mathbf {E} }$

La restricción definida por la matriz esencial es${\displaystyle \mathbf {E} }$

${\displaystyle (\mathbf {y} ')^{T}\,\mathbf {E} \,\mathbf {y} =0}$

para los puntos de imagen correspondientes representados en coordenadas de imagen normalizadas . El problema que resuelve el algoritmo es determinar un conjunto de puntos de imagen coincidentes. En la práctica, las coordenadas de la imagen de los puntos de la imagen se ven afectadas por el ruido y la solución también puede estar sobredeterminada, lo que significa que puede que no sea posible encontrar cuál satisface la restricción anterior exactamente para todos los puntos. Este problema se aborda en el segundo paso del algoritmo.${\displaystyle \mathbf {y} ,\mathbf {y} '}$${\displaystyle \mathbf {E} }$${\displaystyle \mathbf {E} }$

Paso 1: formular una ecuación lineal homogénea

Con

${\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}$   y     y   ${\displaystyle \mathbf {y} '={\begin{pmatrix}y'_{1}\\y'_{2}\\1\end{pmatrix}}}$${\displaystyle \mathbf {E} ={\begin{pmatrix}e_{11}&e_{12}&e_{13}\\e_{21}&e_{22}&e_{23}\\e_{31}&e_{32}&e_{33}\end{pmatrix}}}$

la restricción también se puede reescribir como

${\displaystyle y'_{1}y_{1}e_{11}+y'_{1}y_{2}e_{12}+y'_{1}e_{13}+y'_{2}y_{1}e_{21}+y'_{2}y_{2}e_{22}+y'_{2}e_{23}+y_{1}e_{31}+y_{2}e_{32}+e_{33}=0\,}$

o

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}=0}$

dónde

${\displaystyle {\tilde {\mathbf {y} }}={\begin{pmatrix}y'_{1}y_{1}\\y'_{1}y_{2}\\y'_{1}\\y'_{2}y_{1}\\y'_{2}y_{2}\\y'_{2}\\y_{1}\\y_{2}\\1\end{pmatrix}}}$   y   ${\displaystyle \mathbf {e} ={\begin{pmatrix}e_{11}\\e_{12}\\e_{13}\\e_{21}\\e_{22}\\e_{23}\\e_{31}\\e_{32}\\e_{33}\end{pmatrix}}}$

es decir, representa la matriz esencial en forma de un vector de 9 dimensiones y este vector debe ser ortogonal al vector que puede verse como una representación vectorial de la matriz .${\displaystyle \mathbf {e} }$${\displaystyle {\tilde {\mathbf {y} }}}$${\displaystyle 3\times 3}$${\displaystyle \mathbf {y} '\,\mathbf {y} ^{T}}$

Cada par de puntos de imagen correspondientes produce un vector . Dado un conjunto de puntos 3D, esto corresponde a un conjunto de vectores y todos deben satisfacer${\displaystyle {\tilde {\mathbf {y} }}}$${\displaystyle \mathbf {P} _{k}}$${\displaystyle {\tilde {\mathbf {y} }}_{k}}$

${\displaystyle \mathbf {e} \cdot {\tilde {\mathbf {y} }}_{k}=0}$

para el vector . Dados suficientes (al menos ocho) vectores linealmente independientes , es posible determinar de una manera sencilla. Recopile todos los vectores como columnas de una matriz y debe darse el caso de que${\displaystyle \mathbf {e} }$${\displaystyle {\tilde {\mathbf {y} }}_{k}}$${\displaystyle \mathbf {e} }$${\displaystyle {\tilde {\mathbf {y} }}_{k}}$${\displaystyle \mathbf {Y} }$

${\displaystyle \mathbf {e} ^{T}\,\mathbf {Y} =\mathbf {0} }$

Esto significa que es la solución a una ecuación lineal homogénea .${\displaystyle \mathbf {e} }$

Paso 2: resolver la ecuación

Un enfoque estándar para resolver esta ecuación implica que es un vector singular izquierdo de correspondiente a un valor singular que es igual a cero. Siempre que al menos ocho vectores linealmente independientes se utilizan para construir se deduce que este vector singular es único (sin tener en cuenta la multiplicación escalar) y, en consecuencia, y luego se puede determinar.${\displaystyle \mathbf {e} }$${\displaystyle \mathbf {Y} }$${\displaystyle {\tilde {\mathbf {y} }}_{k}}$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {e} }$${\displaystyle \mathbf {E} }$

En el caso de que se utilicen más de ocho puntos correspondientes para construir es posible que no tenga ningún valor singular igual a cero. Este caso ocurre en la práctica cuando las coordenadas de la imagen se ven afectadas por varios tipos de ruido. Un enfoque común para tratar esta situación es describirla como un problema de mínimos cuadrados totales ; encontrar cuál minimiza${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {e} }$

${\displaystyle \|\mathbf {e} ^{T}\,\mathbf {Y} \|}$

cuando . La solución es elegir como vector singular izquierdo correspondiente al valor singular más pequeño de . Un reordenamiento de esto nuevamente en una matriz da el resultado de este paso, aquí referido como .${\displaystyle \|\mathbf {e} \|=1}$${\displaystyle \mathbf {e} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {e} }$${\displaystyle 3\times 3}$${\displaystyle \mathbf {E} _{\rm {est}}}$

Paso 3: hacer cumplir la restricción interna

Otra consecuencia de tratar con coordenadas de imagen ruidosas es que la matriz resultante puede no satisfacer la restricción interna de la matriz esencial, es decir, dos de sus valores singulares son iguales y distintos de cero y el otro es cero. Dependiendo de la aplicación, las desviaciones mayores o menores de la restricción interna pueden ser un problema o no. Si es crítico que la matriz estimada satisfaga las restricciones internas, esto se puede lograr encontrando la matriz de rango 2 que minimiza${\displaystyle \mathbf {E} '}$

${\displaystyle \|\mathbf {E} '-\mathbf {E} _{\rm {est}}\|}$

donde es la matriz resultante del Paso 2 y se usa la norma de la matriz de Frobenius . La solución al problema se da calculando primero una descomposición de valor singular de :${\displaystyle \mathbf {E} _{\rm {est}}}$${\displaystyle \mathbf {E} _{\rm {est}}}$

${\displaystyle \mathbf {E} _{\rm {est}}=\mathbf {U} \,\mathbf {S} \,\mathbf {V} ^{T}}$

donde son matrices ortogonales y es una matriz diagonal que contiene los valores singulares de . En el caso ideal, uno de los elementos diagonales de debería ser cero, o al menos pequeño en comparación con los otros dos que deberían ser iguales. En cualquier caso, establezca${\displaystyle \mathbf {U} ,\mathbf {V} }$${\displaystyle \mathbf {S} }$${\displaystyle \mathbf {E} _{\rm {est}}}$${\displaystyle \mathbf {S} }$

${\displaystyle \mathbf {S} '={\begin{pmatrix}s_{1}&0&0\\0&s_{2}&0\\0&0&0\end{pmatrix}},}$

donde están los valores singulares más grandes y segundos más grandes en respectivamente. Finalmente, está dado por${\displaystyle s_{1},s_{2}}$${\displaystyle \mathbf {S} }$${\displaystyle \mathbf {E} '}$

${\displaystyle \mathbf {E} '=\mathbf {U} \,\mathbf {S} '\,\mathbf {V} ^{T}}$

La matriz es la estimación resultante de la matriz esencial proporcionada por el algoritmo.${\displaystyle \mathbf {E} '}$

Algoritmo normalizado

En principio, el algoritmo básico de ocho puntos también se puede utilizar para estimar la matriz fundamental . La restricción definitoria para es${\displaystyle \mathbf {F} }$${\displaystyle \mathbf {F} }$

${\displaystyle (\mathbf {y} ')^{T}\,\mathbf {F} \,\mathbf {y} =0}$

donde están las representaciones homogéneas de las coordenadas de imagen correspondientes (no necesariamente normalizadas). Esto significa que es posible formar una matriz de manera similar a la matriz esencial y resolver la ecuación${\displaystyle \mathbf {y} ,\mathbf {y} '}$${\displaystyle \mathbf {Y} }$

${\displaystyle \mathbf {f} ^{T}\,\mathbf {Y} =\mathbf {0} }$

para lo cual es una versión remodelada de . Siguiendo el procedimiento descrito anteriormente, es posible determinar a partir de un conjunto de ocho puntos coincidentes. En la práctica, sin embargo, la matriz fundamental resultante puede no ser útil para determinar las limitaciones epipolares.${\displaystyle \mathbf {f} }$${\displaystyle \mathbf {F} }$${\displaystyle \mathbf {F} }$

Dificultad

El problema es que el resultado suele estar mal condicionado . En teoría, debería tener un valor singular igual a cero y el resto son distintos de cero. En la práctica, sin embargo, algunos de los valores singulares distintos de cero pueden volverse pequeños en relación con los más grandes. Si se utilizan más de ocho puntos correspondientes para construir , donde las coordenadas son sólo aproximadamente correctas, es posible que no haya un valor singular bien definido que pueda identificarse como aproximadamente cero. En consecuencia, la solución del sistema lineal homogéneo de ecuaciones puede no ser lo suficientemente precisa para ser útil.${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {Y} }$

Porque

Hartley abordó este problema de estimación en su artículo de 1997. Su análisis del problema muestra que el problema se debe a la mala distribución de las coordenadas de la imagen homogénea en su espacio . Una representación homogénea típica de la coordenada de imagen 2D es${\displaystyle \mathbb {R} ^{3}}$${\displaystyle (y_{1},y_{2})\,}$

${\displaystyle \mathbf {y} ={\begin{pmatrix}y_{1}\\y_{2}\\1\end{pmatrix}}}$

donde ambos se encuentran en el rango de 0 a 1000-2000 para una cámara digital moderna. Esto significa que las dos primeras coordenadas varían en un rango mucho mayor que la tercera coordenada. Además, si los puntos de imagen que se utilizan para construir se encuentran en una región relativamente pequeña de la imagen, por ejemplo en , nuevamente el vector apunta en más o menos la misma dirección para todos los puntos. Como consecuencia, tendrá un valor singular grande y los restantes serán pequeños.${\displaystyle y_{1},y_{2}\,}$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {Y} }$${\displaystyle (700,700)\pm (100,100)\,}$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {Y} }$

Solución

Como solución a este problema, Hartley propuso que el sistema de coordenadas de cada una de las dos imágenes debería transformarse, de forma independiente, en un nuevo sistema de coordenadas de acuerdo con el siguiente principio.

• El origen del nuevo sistema de coordenadas debe estar centrado (tener su origen) en el centroide (centro de gravedad) de los puntos de la imagen. Esto se logra mediante una traducción del origen original al nuevo.
• Después de la traslación, las coordenadas se escalan uniformemente para que la media de las distancias desde el origen hasta los puntos sea igual .${\displaystyle {\sqrt {2}}}$

Este principio da como resultado, normalmente, una transformación de coordenadas distinta para cada una de las dos imágenes. Como resultado, las nuevas coordenadas de imagen homogéneas vienen dadas por${\displaystyle \mathbf {\bar {y}} ,\mathbf {\bar {y}} '}$

${\displaystyle \mathbf {\bar {y}} =\mathbf {T} \,\mathbf {y} }$

${\displaystyle \mathbf {\bar {y}} '=\mathbf {T} '\,\mathbf {y} '}$

¿Dónde están las transformaciones (traducción y escala) de las coordenadas de imagen normalizadas antiguas a las nuevas . Esta normalización solo depende de los puntos de imagen que se utilizan en una sola imagen y, en general, es distinta de las coordenadas de imagen normalizadas producidas por una cámara normalizada.${\displaystyle \mathbf {T} ,\mathbf {T} '}$

La restricción epipolar basada en la matriz fundamental ahora se puede reescribir como

${\displaystyle 0=(\mathbf {\bar {y}} ')^{T}\,((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}\,\mathbf {\bar {y}} =(\mathbf {\bar {y}} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {\bar {y}} }$

donde . Esto significa que es posible utilizar las coordenadas de la imagen homogénea normalizada para estimar la matriz fundamental transformada utilizando el algoritmo básico de ocho puntos descrito anteriormente.${\displaystyle \mathbf {\bar {F}} =((\mathbf {T} ')^{T})^{-1}\,\mathbf {F} \,\mathbf {T} ^{-1}}$${\displaystyle \mathbf {\bar {y}} ,\mathbf {\bar {y}} '}$${\displaystyle \mathbf {\bar {F}} }$

El propósito de las transformaciones de normalización es que la matriz , construida a partir de las coordenadas de la imagen normalizada, en general, tenga un número de condición mejor que el que tiene. Esto significa que la solución está mejor definida como una solución de la ecuación homogénea que con respecto a . Una vez que se ha determinado y remodelado en este último, se puede desnormalizar para dar de acuerdo con${\displaystyle \mathbf {\bar {Y}} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {\bar {f}} }$${\displaystyle \mathbf {\bar {Y}} \,\mathbf {\bar {f}} }$${\displaystyle \mathbf {f} }$${\displaystyle \mathbf {Y} }$${\displaystyle \mathbf {\bar {f}} }$${\displaystyle \mathbf {\bar {F}} }$${\displaystyle \mathbf {F} }$

${\displaystyle \mathbf {F} =(\mathbf {T} ')^{T}\,\mathbf {\bar {F}} \,\mathbf {T} }$

En general, esta estimación de la matriz fundamental es mejor que la que se habría obtenido estimando a partir de las coordenadas no normalizadas.

Usando menos de ocho puntos

Cada par de puntos contribuye con una ecuación restrictiva sobre el elemento en . Dado que tiene cinco grados de libertad, debería ser suficiente con sólo cinco pares de puntos para determinar . Aunque es posible desde un punto de vista teórico, la implementación práctica de esto no es sencilla y se basa en la resolución de varias ecuaciones no lineales.${\displaystyle \mathbf {E} }$${\displaystyle \mathbf {E} }$${\displaystyle \mathbf {E} }$

Kaveh Fathian y col. propuso algoritmos para cinco, seis y siete puntos que eluden el cálculo de la matriz esencial calculando directamente el cuaternión de rotación. ^{[1] [2]}

Ver también

• Matriz esencial
  • Matriz esencial # Extracción de rotación y traslación
• Matriz fundamental
• Tensor trifocal

Referencias

1. Fathian, Kaveh (2018). "QuEst: un enfoque basado en cuaterniones para la estimación del movimiento de la cámara desde puntos de características mínimos" . IEEE Robotics and Automation Letters . arXiv : 1704.02672 . doi : 10.1109 / LRA.2018.2792142 .
2. Fathian, Kaveh (2018). "Estimación de pose relativa de cámara para servo visual utilizando cuaterniones" . Robótica y sistemas autónomos . doi : 10.1016 / j.robot.2018.05.014 .

Otras lecturas

• Richard I. Hartley (junio de 1997). "En defensa del algoritmo de ocho puntos". Transacciones IEEE sobre reconocimiento de patrones e inteligencia de máquinas . 19 (6): 580–593. doi : 10.1109 / 34.601246 .

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

• H. Christopher Longuet-Higgins (septiembre de 1981). "Un algoritmo informático para reconstruir una escena a partir de dos proyecciones". Naturaleza . 293 (5828): 133-135. doi : 10.1038 / 293133a0 .