Perspectiva-n-Punto

Dado un conjunto de n puntos 3D en un sistema de referencia global y sus correspondientes proyecciones de imagen 2D, así como los parámetros intrínsecos calibrados de la cámara, determine la pose de 6 grados de libertad de la cámara en forma de su rotación y traslación con respecto al mundo. Esto sigue el modelo de proyección en perspectiva para cámaras:

${\displaystyle s\,p_{c}=K\,[\,R\,|\,T\,]\,p_{w}}$.

dónde${\displaystyle \textstyle p_{w}={\begin{bmatrix}x&y&z&1\end{bmatrix}}^{T}}$es el punto del mundo homogéneo ,${\displaystyle \textstyle p_{c}={\begin{bmatrix}u&v&1\end{bmatrix}}^{T}}$es el punto de imagen homogéneo correspondiente,${\displaystyle \textstyle K}$es la matriz de parámetros intrínsecos de la cámara , (donde${\displaystyle \textstyle f_ {x}}$y${\displaystyle f_{y}}$son las distancias focales escaladas,${\displaystyle \textstyle \gamma}$es el parámetro de asimetría que a veces se supone que es 0, y${\displaystyle \textstyle (u_ {0}, \,v_ {0})}$es el punto principal),${\displaystyle \textstyle s}$es un factor de escala para el punto de la imagen, y${\displaystyle \textstyle R}$y${\displaystyle \textstyle T}$son la rotación 3D deseada y la traslación 3D de la cámara (parámetros extrínsecos) que se están calculando. Esto lleva a la siguiente ecuación para el modelo:

${\displaystyle s{\begin{bmatrix}u\\v\\1\end{bmatrix}}={\begin{bmatrix}f_{x}&\gamma &u_{0}\\0&f_{y}&v_{0}\\0&0&1\end{bmatrix}}{\begin{bmatrix}r_{11}&r_{12}&r_{13}&t_{1}\\r_{21}&r_{22}&r_{23}&t_{2}\\r_{31}&r_{32}&r_{33}&t_{3}\\\end{bmatrix}}{\begin{bmatrix}x\\y\\z\\1\end{bmatrix}}}$.

Existen algunos aspectos preliminares del problema que son comunes a todas las soluciones de P n P. La suposición que se hace en la mayoría de las soluciones es que la cámara ya está calibrada. Por lo tanto, sus propiedades intrínsecas ya son conocidas, como la distancia focal , el punto de imagen principal, el parámetro de sesgo y otros parámetros. Algunos métodos, como UP n P ^{[ 4 ]} o la Transformación Lineal Directa (DLT) aplicada al modelo de proyección, son excepciones a esta suposición, ya que estiman estos parámetros intrínsecos, así como los parámetros extrínsecos que conforman la pose de la cámara que el problema original de P n P intenta encontrar.

Para cada solución de PnP, las correspondencias de puntos elegidas no pueden ser colineales. Además, P n P puede tener múltiples soluciones, y elegir una solución en particular requeriría un procesamiento posterior del conjunto de soluciones . RANSAC también se usa comúnmente con un método P n P para hacer que la solución sea robusta a los valores atípicos en el conjunto de correspondencias de puntos. Los métodos P3P asumen que los datos están libres de ruido, mientras que la mayoría de los métodos PnP asumen ruido gaussiano en el conjunto de valores atípicos.

Cuando n = 3 , el problema P n P se encuentra en su forma mínima P3P y puede resolverse con correspondencias de tres puntos. Sin embargo, con solo tres correspondencias de puntos, P3P produce hasta cuatro soluciones reales y geométricamente factibles. Para niveles bajos de ruido, se puede utilizar una cuarta correspondencia para eliminar la ambigüedad. La configuración del problema es la siguiente.

Sea P el centro de proyección de la cámara, A , B y C puntos del mundo 3D con puntos de imagen correspondientes u , v y w . Sea X = |PA| , Y = |PB| , Z = |PC| ,${\displaystyle \alpha =\angle BPC}$,${\displaystyle \beta =\angle APC}$,${\displaystyle \gamma =\angle APB}$,${\displaystyle p=2\cos \alpha }$,${\displaystyle q=2\cos \beta }$,${\displaystyle r=2\cos \gamma }$,${\displaystyle a'=|AB|}$,${\displaystyle b'=|BC|}$,${\displaystyle c'=|AC|}$Esto forma los triángulos PBC , PAC y PAB , a partir de los cuales obtenemos un sistema de ecuaciones suficiente para P3P:

${\displaystyle {\begin{casos}Y^{2}+Z^{2}-YZp-b'^{2}&=0\\Z^{2}+X^{2}-XZq-c'^{2}&=0\\X^{2}+Y^{2}-XYr-a'^{2}&=0\\\end{casos}}}$.

La resolución del sistema P3P produce hasta cuatro soluciones reales geométricamente factibles para R y T. La solución publicada más antigua data de 1841. ^{[ 5 ]} Un algoritmo reciente para resolver el problema, así como una clasificación de la solución, se presenta en el artículo de 2003 de IEEE Transactions on Pattern Analysis and Machine Intelligence de Gao, et al. ^{[ 6 ]} Una implementación de código abierto del solucionador P3P de Gao se puede encontrar en el módulo calib3d de OpenCV en la función solvePnP . ^{[ 7 ]} Desde entonces se han publicado varias versiones más rápidas y precisas, incluyendo Lambda Twist P3P ^{[ 8 ]} que alcanzó un rendimiento de vanguardia en 2018 con un aumento de 50 veces en la velocidad y una disminución de 400 veces en los fallos numéricos. Lambdatwist está disponible como código abierto en OpenMVG y en https://github.com/midjji/pnp .

El método Efficient P n P (EP n P) fue desarrollado por Lepetit et al. en su artículo de 2008 publicado en el International Journal of Computer Vision ^{[ 9 ]} , el cual resuelve el problema general de P n P para n ≥ 4. Este método se basa en la idea de que cada uno de los n puntos (denominados puntos de referencia) puede expresarse como una suma ponderada de cuatro puntos de control virtuales. De esta manera, las coordenadas de estos puntos de control se convierten en las incógnitas del problema. A partir de estos puntos de control, se determina la pose final de la cámara.

Como resumen del proceso, primero observe que cada uno de los n puntos de referencia en el marco del mundo,${\displaystyle p_{i}^{w}}$y sus correspondientes puntos de imagen,${\displaystyle p_{i}^{c}}$, son sumas ponderadas de los cuatro puntos de control,${\displaystyle c_{j}^{w}}$y${\displaystyle c_{j}^{c}}$respectivamente, y los pesos se normalizan por punto de referencia como se muestra a continuación. Todos los puntos se expresan en forma homogénea.

${\displaystyle p_{i}^{w}=\sum _ {j=1}^{4}{\alpha _ {ij}c_ {j}^{w}}}$

${\displaystyle p_{i}^{c}=\sum _{j=1}^{4}{\alpha _{ij}c_{j}^{c}}}$

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}}=1}$

A partir de esto, la derivación de los puntos de referencia de la imagen se convierte en

${\displaystyle s_{i}\,p_{i}^{img}=K\sum _{j=1}^{4}{\alpha _{ij}c_{j}^{c}}}$.

Dónde${\displaystyle p_{i}^{img}}$son los puntos de referencia de la imagen con coordenadas de píxeles${\displaystyle {\begin{bmatrix}u_{i}&v_{i}&1\end{bmatrix}}^{T}}$El punto de control de imagen homogéneo tiene la forma${\displaystyle \textstyle c_{j}^{c}={\begin{bmatrix}x_{j}^{c}&y_{j}^{c}&z_{j}^{c}\end{bmatrix}}^{T}}$Al reorganizar la ecuación del punto de referencia de la imagen, se obtienen las siguientes dos ecuaciones lineales para cada punto de referencia:

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}f_{x}x_{j}^{c}+\alpha _{ij}(u_{0}-u_{i})z_{j}^{c}}=0}$

${\displaystyle \sum _{j=1}^{4}{\alpha _{ij}f_{y}y_{j}^{c}+\alpha _{ij}(v_{0}-v_{i})z_{j}^{c}}=0}$.

Utilizando estas dos ecuaciones para cada uno de los n puntos de referencia, el sistema${\displaystyle \textstyle Mx=0}$se puede formar donde${\displaystyle \textstyle x={\begin{bmatrix}c_{1}^{c^{T}}&c_{2}^{c^{T}}&c_{3}^{c^{T}}&c_{4}^{c^{T}}\end{bmatrix}}^{T}}$. La solución para los puntos de control existe en el espacio nulo de M y se expresa como

${\displaystyle x=\sum _{i=1}^{N}{\beta _{i}v_{i}}}$

dónde${\displaystyle N}$es el número de valores singulares nulos en${\displaystyle M}$y cada uno${\displaystyle v_{i}}$es el vector singular derecho correspondiente de${\displaystyle M}$.${\displaystyle N}$puede variar de 0 a 4. Después de calcular los coeficientes iniciales${\displaystyle \beta _{i}}$, el algoritmo de Gauss-Newton se utiliza para refinarlos. Las matrices R y T que minimizan el error de reproyección de los puntos de referencia del mundo,${\displaystyle p_{i}^{w}}$y sus correspondientes puntos de imagen reales${\displaystyle p_{i}^{c}}$, luego se calculan.

Esta solución tiene${\displaystyle O(n)}$complejidad y funciona en el caso general de P n P para puntos de control tanto planares como no planares. Se pueden encontrar implementaciones de software de código abierto de este método en el módulo de calibración de cámara y reconstrucción 3D de OpenCV en la función solvePnP ^{[ 7 ]} , así como en el código publicado por Lepetit et al. en su sitio web, CVLAB en EPFL ^{[ 10 ]} .

Este método no es robusto frente a valores atípicos y, en general, se compara negativamente con RANSAC P3P seguido de refinamiento no lineal .

SQPnP fue descrito por Terzakis y Lourakis en un artículo de ECCV 2020. ^{[ 11 ]} Es un solucionador no mínimo y no polinomial que plantea P n P como un programa cuadrático no lineal. SQPnP identifica regiones en el espacio de parámetros de rotaciones 3D (es decir, la 8-esfera ) que contienen mínimos únicos con garantías de que al menos uno de ellos es el mínimo global. Cada mínimo regional se calcula con programación cuadrática secuencial que se inicia en las matrices de aproximación ortogonal más cercanas .

SQPnP tiene una precisión similar o incluso superior a la de los solucionadores polinomiales de última generación, es globalmente óptimo y computacionalmente muy eficiente, siendo prácticamente lineal con respecto al número de puntos proporcionados n . Una implementación optimizada en C++ está disponible en GitHub , la cual también ha sido portada a OpenCV e incluida en el módulo de calibración de cámara y reconstrucción 3D ( función SolvePnP ). ^{[ 12 ]}

El método P n P es propenso a errores si existen valores atípicos en el conjunto de correspondencias de puntos. Por lo tanto, RANSAC puede utilizarse junto con las soluciones existentes para que la solución final de la pose de la cámara sea más robusta frente a valores atípicos. Una implementación de código abierto de los métodos P n P con RANSAC se puede encontrar en el módulo de calibración de cámara y reconstrucción 3D de OpenCV, en la función solvePnPRansac . ^{[ 12 ]}