Triangulación (visión artificial)

En visión artificial triangulación se refiere al proceso de determinación de un punto en el espacio 3D dadas sus proyecciones en dos o más imágenes. Para resolver este problema es necesario conocer los parámetros de la función de proyección de 3D a 2D de las cámaras involucradas, que en su versión más simple se representan por sus matrices de cámara. La triangulación a veces se la denomina reconstrucción.

El problema de triangulación es trivial en la teoría. Como cada punto en una imagen corresponde a una línea (denominado rayo de proyección o recta proyectante) en el espacio 3D, todos los puntos de esa línea 3D se proyectan al mismo punto 2D de la imagen. La proyecciones de un punto 3D en varias imágenes se denominan puntos correspondientes en esas imágenes. Los rayos de proyección de estos puntos correspondientes se intersectan en el espacio, en el punto 3D buscado. Más adelante se presenta una variedad de formulaciones algebraicas para determinar este punto 3D.

En la práctica, sin embargo, las coordenadas de los puntos de una imagen no se pueden medir con precisión arbitraria. Varios tipos de ruido, tales como error geométrico por distorsión de lente o error de método de detección del punto característico, modelizan la disparidad entre las coordenadas medidas y sus valores reales exactos desconocidos. Como consecuencia, los rayos de proyección generados a partir de imágenes no se intersectan en el espacio 3D. Entonces el problema se replantea en la determinación del punto 3D óptimo que mejor encaje con las mediciones. La literatura propone varias definiciones de optimalidad, y de cada una deriva un método de cálculo, cada uno de ellos con un resultado ligeramente diferente.

A continuación se asume que la triangulación se realiza sobre un par de puntos correspondientes obtenidos de dos cámaras estenopeicas.

La imagen a la izquierda ilustra el geometría epipolar de un par de cámaras estenopeicas estéreo. Utilizando álgebra lineal básica se puede determinar el punto 3D de la intersección de manera directa.

La imagen a la derecha muestra el caso real. Las proyecciones no se pueden obtener con absoluta precisión, por una serie de motivos:

• Distorsión geométrica, por ejemplo la distorsión de lente, la que implica desvíos de la proyección 3D a 2D . Hasta cierto punto estos errores pueden ser compensados mediante un modelo de antidistorsión, reduciendo el desvío a un error geométrico residual.
• Las lentes dispersan cada rayo de luz. La mancha proyectada se reduce a un punto por medio de un modelo matemático de dispersión de luz. El punto resulta de un cálculo y no de una medición directa, y su posición difiere del óptimo.
• Las cámaras digitales discretizan la imagen en píxeles, perdiéndose la información entre píxeles. Los métodos de precisión subpíxel interpolan las coordenadas del punto proyectado, aproximando al punto óptimo, pero nunca de manera exacta.
• Los puntos de imagen y1' e y2' se suelen obtener con un algoritmo de detección de puntos característicos, cada uno con un tipo de error inherente al método.

Como consecuencia, los puntos de imagen medidos son $\mathbf {y} '_{1}$ e $\mathbf {y} '_{2}$ en vez de $\mathbf {y} _{1}$ e $\mathbf {y} _{2}$. Sus líneas de proyección (azules) no se cruzan en el espacio 3D y pero, pueden no pasar cerca de x. Sólo se cruzan las líneas que satisfacen la restricción epipolar definido por la matriz esencial o fundamental. Dado el ruido inherente a la medición y determinación de los puntos proyectados $\mathbf {y} '_{1}$ e $\mathbf {y} '_{2}$ , la restricción epipolar no se satisface nunca o eventualmente sólo de manera casual e irrelevante.

Esta observación conduce al problema que debe resolver la triangulación. ¿Cuál es la mejor estimación x_est de x dados $\mathbf {y} '_{1}$, $\mathbf {y} '_{2}$ y la geometría de los cámaras? La respuesta se encuentra definiendo un error que dependa de x_est , y luego minimizando este error. En las secciones siguientes se presentan algunos de los varios métodos para computar x_est presentes en la literatura.

Todos los métodos de la triangulación resultan en xest = x si $\mathbf {y} _{1}=\mathbf {y} '_{1}$ e $\mathbf {y} _{2}=\mathbf {y} '_{2}$ , excepto para singularidades. Los métodos presentan resultados diferentes sólo cuando la restricción epipolar no se satisface.

Propiedades de métodos de triangulación

Un método de triangulación se puede describir en términos de una función $\tau \,$ de modo que

$\mathbf {x} \sim \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})$

donde $\mathbf {y} '_{1},\mathbf {y} '_{2}$ son las coordenadas homogéneas de los puntos 2D detectados sobre la imagen y $\mathbf {C} _{1},\mathbf {C} _{2}$ son las matrices de cámara. x (punto 3D) es la representación homogénea del punto 3D resultante. El signo $\sim \,$indica proporcionalidad, de modo que $\tau \,$arroja un valor proporcional a x, pues está expresado en coordenadas homogéneas.

Antes de abordar los métodos concretos, conviene atender algunos conceptos generales.

Singularidades

Los métodos fallan al estimar x (punto 3D) cuando éste se encuentra en cierta región del espacio, denominada región singular. Un punto en esta región se denomina singularidad.

Algunos efectos de las singularidades sobre el sistema de ecuaciones de cada métodoː

• el sistema de ecuaciones queda indeterminado y no tiene solución única
• el método no puede expresar infinitos

Tal región es la recta que une los focos de las dos cámaras. Un punto de esa recta no se puede triangular, el sistema queda indeterminado.

Otra región singular es la de los puntos 3D en el infinito. Algunos métodos no incorporan la capacidad de expresar puntos en el infinito, de modo que para esos métodos esta región es singular.

Métodos reales y métodos ideales

Los métodos de triangulación ideales tienen solución en forma cerrada con interés teórico y académico solamente, pues fallan al llevarlos a la práctica. Los métodos de triangulación reales asumen que los rayos proyectivos son alabeados (es decir, no se cruzan) y denominan error a la distancia entre las proyecciones medidas y las reproyecciones (las proyecciones del punto 3D triangulado).

Los métodos de triangulación reales calculan el punto 3D que minimice ese error. La principal diferencia entre los diversos métodos radica en la forma en que se evalúa el error. El error cuadrático computa la distancia euclidiana y es se lo denomina estándar de oro, pero tal como demostraron Harley y Sturm (ver Método polinomial), el problema no tiene solución analítica y requiere cálculo numérico. Ante esta situación se han propuesto otras formulaciones de la función error que simplifican el análisis matemático a costa de producir una triangulación menos certera. Algunos errores utilizados reformulan la manera de calcular las distanciasː

• distancia de Sampson
• distancia de Kanatani
• distancia Manhattan (error de primer orden)

Complejidad computacional

La función $\tau$ es sólo una representación matemática de una computación que suele ser relativamente compleja. Algunos métodos resultan en una formulación de $\tau$ en forma cerrada, mientras que otros en forma de serie infinita. Estos últimos son métodos iterativos. Esto implica que la complejidad computacional y el tiempo de cómputo varía fuertemente entre los diversos métodos.

Algunos métodos de triangulación encontrados en la literatura

Algunos métodos usuales de triangulación para aplicar en casos reales:

• Método del punto medio
  • obtiene el punto común más cercano a ambas rectas proyectivas
  • es el más simple y de resultados más pobres
• DLT: transformación lineal directa
  • utiliza el algoritmo DLT para resolver la triangulación
• Métodos lineales
  • plantean una ecuación lineal que se puede resolver por varios métodos, por ejemploː
    • Método lineal con cuadrados mínimos
    • Método lineal con autovalores
• Métodos basados en matriz esencial
  • varios métodos que procuran hacer cumplir la restricción epipolar

Método del punto medio

Cada proyección $\mathbf {y} '_{1}$e $\mathbf {y} '_{2}$ tiene una recta proyectiva asociada (líneas azules en la imagen de la izquierda arriba), aquí denotadas $\mathbf {L} '_{1}$ y $\mathbf {L} '_{2}$. Sea $d\,$ la función de distancia entre una línea L1' y un punto 3D x tal que

  $d(\mathbf {L} ,\mathbf {x} )=$ distancia euclidiana entre $\mathbf {L}$ y $\mathbf {x}$

El método del punto medio determina x_est que minimiza

$d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}$

Como resultado x_est se encuentra exactamente en el medio del segmento de línea más corto que une las dos líneas de proyección.

Éste es un método simple pero con malos resultados, pues el punto medio no guarda relación con los errores de mediciónː el punto medio no minimiza el error. Tiene un planteo sobresimplificado que no ataca el problema central. El método se menciona con frecuencia por ser uno de los primeros, pero se encuentra en desuso en favor de otros más sofisticados con resultados mucho mejores.

Método lineal

Consiste en replantear el problema bajo la forma matricial A.x = 0. La solución trivial no resulta útil, hay varios métodos para obtener el punto x de esta ecuación.

Siendo u la expresión homogénea de la proyección en una imagen del punto 3D x (también en coordenadas homogéneas)ː

${\mathsf {u}}=w(u,v,1)^{T}$

${\mathsf {u}}=Px$

P es la matriz de proyección, de 3x4. Llamando p_i a cada fila de Pː

${\begin{cases}wu=p_{1}x\\wv=p_{2}x\\w=p_{3}x\end{cases}}$

Eliminando wː

${\begin{cases}up_{3}x=p_{1}x\\vp_{3}x=p_{2}x\end{cases}}$

Despejando x se obtienen dos ecuaciones correspondientes a la proyección de x en una imagenː

${\begin{cases}(p_{1}-up_{3})x=0\\(p_{2}-vp_{3})x=0\end{cases}}$

De manera similar, la proyección de x en la segunda imagen proporciona dos ecuaciones más, llegando a la forma deseadaː

$Ax=0$

donde A es una matriz de 4x4.

La solución trivial x = (0) es indeterminada en coordenadas homogéneas. El punto x triangulado se obtiene agregando una restricción matemática que deje fuera la solución trivial, para lo que existen dos métodos popularesː

• autovectores
• cuadrados mínimos

Método lineal con autovectores

Plantea la restricción ||Ax|| = 1, que se resuelve con autovectores, siendo x el menor autovector de A^TA.

Este autovector se puede obtener por descomposición en valores singulares, o con el método de Jacobi para obtener autovalores de matrices simétricas.

Método lineal con cuadrados mínimos

Plantea la restricción de coordenada homogénea normal (es decir, su 4º elemento es 1)ː

$x=(x,y,z,1)^{T}$

Con esta restricción el sistema de ecuaciones se reescribe con 4 ecuaciones y 3 incógnitas, sobredeterminado e incompatible, con la solución corresponde a x que minimiza ||Ax||, y que se resuelve mediante pseudoinversa o por descomposición en valores singulares.

Método polinomial

Este método, conocido también como método óptimo, fue propuesto por Richard Harley y Peter Sturm en su paper Triangulation,​ y consiste en determinar el punto que minimiza las distancias de cada medición y a la línea epipolar correspondiente x_est. Más precisamente, minimiza el error cuadrático medio, siendo esa distancia una medida del error.

x_est es aquel que minimiza la función de error cuadrático medio. Los mínimos y máximos de esta función se hallan donde su derivada es cero. La función derivada es un polinomio de orden 6º cuyas raíces no se pueden obtener analíticamente.

El algoritmo se triangulación es el siguienteː

1. determinar mediante cálculo numérico las raíces de la derivada de la función error (que es un polinomio de orden 6)
   1. puede haber una raíz en infinito
2. evaluar el error en todas las raíces calculadas, y elegir aquella de menor error
   1. esto conlleva evaluar el error no sólo en los mínimos sino también en los máximos, y suele ser más eficiente que un test para descartar los máximos

El costo computacional del método radica en el esfuerzo para hallar los ceros del polinomio de 6º orden. En algunos casos se prefieren métodos subóptimos pero más eficientes computacionalmente.

Véase también

• Structure from motion
• Detección de características
• Descomposición en valores singulares
• DLT: transformación lineal directa

Referencias

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3. 

Enlaces externos

• Triangulación de dos vista en Matlab

• Datos: Q4389056