Ajuste de paquete

Técnica en fotogrametría y visión artificial

Matriz dispersa obtenida al resolver un problema de ajuste de fibrado de tamaño modesto. Este es el patrón de dispersión en forma de punta de flecha de una matriz de ecuaciones normales (es decir, hessiana aproximada) de 992 × 992. Las regiones negras corresponden a bloques distintos de cero.

En fotogrametría y visión estereoscópica por computadora , el ajuste de haces es el refinamiento simultáneo de las coordenadas 3D que describen la geometría de la escena, los parámetros del movimiento relativo y las características ópticas de la(s) cámara(s) empleada(s) para adquirir las imágenes, dado un conjunto de imágenes que representan una serie de puntos 3D desde diferentes puntos de vista . Su nombre se refiere a los haces geométricos de rayos de luz que se originan en cada característica 3D y convergen en el centro óptico de cada cámara , que se ajustan de manera óptima de acuerdo con un criterio de optimalidad que involucra las proyecciones de imagen correspondientes de todos los puntos.

Usos

El ajuste de paquetes casi siempre se utiliza ^{[ cita requerida ] como el último paso de los algoritmos} de reconstrucción 3D basados ​​en características . Equivale a un problema de optimización en la estructura 3D y los parámetros de visualización (es decir, la posición de la cámara y posiblemente la calibración intrínseca y la distorsión radial), para obtener una reconstrucción que sea óptima bajo ciertas suposiciones con respecto al ruido perteneciente a las características de la imagen observada ^{[1] : Si el error de la imagen es} gaussiano de media cero , entonces el ajuste de paquetes es el estimador de máxima verosimilitud . ^{[2] : 2} El ajuste de paquetes se concibió originalmente en el campo de la fotogrametría durante la década de 1950 y los investigadores de visión por computadora lo han utilizado cada vez más durante los últimos años. ^{[2] : 2}

Enfoque general

El ajuste de paquetes se reduce a minimizar el error de reproyección entre las ubicaciones de la imagen de los puntos de imagen observados y predichos, que se expresa como la suma de los cuadrados de una gran cantidad de funciones no lineales de valor real. Por lo tanto, la minimización se logra utilizando algoritmos de mínimos cuadrados no lineales. De estos, Levenberg-Marquardt ha demostrado ser uno de los más exitosos debido a su facilidad de implementación y al uso de una estrategia de amortiguamiento efectiva que le otorga la capacidad de converger rápidamente a partir de una amplia gama de conjeturas iniciales. Al linealizar iterativamente la función que se minimizará en la vecindad de la estimación actual, el algoritmo Levenberg-Marquardt implica la solución de sistemas lineales denominados ecuaciones normales . Al resolver los problemas de minimización que surgen en el marco del ajuste de paquetes, las ecuaciones normales tienen una estructura de bloques dispersa debido a la falta de interacción entre los parámetros para diferentes puntos 3D y cámaras. Esto se puede aprovechar para obtener enormes beneficios computacionales empleando una variante dispersa del algoritmo Levenberg-Marquardt que aprovecha explícitamente el patrón de ceros de las ecuaciones normales, evitando almacenar y operar sobre elementos cero. ^{[2] : 3}

Definición matemática

El ajuste de paquetes equivale a refinar conjuntamente un conjunto de estimaciones iniciales de parámetros de la cámara y la estructura para encontrar el conjunto de parámetros que predicen con mayor precisión las ubicaciones de los puntos observados en el conjunto de imágenes disponibles. De manera más formal, ^[3] supone que los puntos 3D se ven en las vistas y sea la proyección del punto th en la imagen . Sea las variables binarias que son iguales a 1 si el punto es visible en la imagen y 0 en caso contrario. Suponga también que cada cámara está parametrizada por un vector y cada punto 3D por un vector . El ajuste de paquetes minimiza el error de reproyección total con respecto a todos los parámetros de la cámara y el punto 3D, específicamente ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \mathbf {x} _{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \displaystyle v_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle \mathbf {a} _{j}}$ ${\displaystyle i}$ ${\displaystyle \mathbf {b} _{i}}$

${\displaystyle \min _{\mathbf {a} _{j},\,\mathbf {b} _{i}}\displaystyle \sum _{i=1}^{n}\;\displaystyle \sum _{j=1}^{m}\;v_{ij}\,d(\mathbf {Q} (\mathbf {a} _{j},\,\mathbf {b} _{i}),\;\mathbf {x} _{ij})^{2},}$

donde es la proyección prevista del punto en la imagen y denota la distancia euclidiana entre los puntos de la imagen representados por los vectores y . Debido a que el mínimo se calcula sobre muchos puntos y muchas imágenes, el ajuste de paquete es por definición tolerante a las proyecciones de imagen faltantes, y si la métrica de distancia se elige de manera razonable (por ejemplo, la distancia euclidiana), el ajuste de paquete también minimizará un criterio físicamente significativo. ${\displaystyle \mathbf {Q} (\mathbf {a} _{j},\,\mathbf {b} _{i})}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle d(\mathbf {x} ,\,\mathbf {y} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$

Véase también

• Ajuste de las observaciones
• Estereoscopia
• Algoritmo de Levenberg-Marquardt
• Matriz dispersa
• Ecuación de colinealidad
• Estructura a partir del movimiento
• Localización y mapeo simultáneo

Referencias

1. B. Triggs; P. McLauchlan; R. Hartley; A. Fitzgibbon (1999). "Ajuste de paquetes: una síntesis moderna" (PDF) . ICCV '99: Actas del Taller internacional sobre algoritmos de visión . Springer-Verlag. págs. 298–372. doi :10.1007/3-540-44480-7_21. ISBN . 3-540-67973-1.
2. MIA Lourakis y AA Argyros (2009). "SBA: un paquete de software para el ajuste genérico de paquetes dispersos" (PDF) . ACM Transactions on Mathematical Software . 36 (1): 1–30. doi :10.1145/1486525.1486527. S2CID  474253.
3. RI Hartley y A. Zisserman (2004). Geometría de vista múltiple en visión artificial (2.ª ed.). Cambridge University Press. ISBN 978-0-521-54051-3.

Lectura adicional

• A. Zisserman. Ajuste de paquetes. CV Online.

Enlaces externos

Software

• [1]: Apero/MicMac, un software fotogramétrico gratuito de código abierto. Licencia Cecill-B.
• sba: Un paquete genérico de ajuste de paquetes dispersos en C/C++ basado en el algoritmo Levenberg–Marquardt ( C , MATLAB ). GPL.
• cvsba Archivado el 24 de octubre de 2013 en Wayback Machine : Un contenedor OpenCV para la biblioteca sba ( C++ ). GPL.
• ssba: Paquete de ajuste de paquetes dispersos simple basado en el algoritmo Levenberg–Marquardt (C++). LGPL.
• OpenCV: Librería de Visión Artificial en el módulo de unión de imágenes. Licencia BSD.
• mcba: Ajuste de paquete de múltiples núcleos (CPU/GPU). GPL3.
• libdogleg: solucionador de mínimos cuadrados no lineales dispersos de propósito general, basado en el método dogleg de Powell. LGPL.
• ceres-solver: un minimizador de mínimos cuadrados no lineal. Licencia BSD.
• g2o: Optimización general de gráficos (C++): marco con solucionadores para funciones de error no lineales basadas en gráficos dispersos. LGPL.
• DGAP: El programa DGAP implementa el método fotogramétrico de ajuste de haces inventado por Helmut Schmid y Duane Brown. GPL.
• Bundler: un sistema de estructura a partir del movimiento (SfM) para colecciones de imágenes no ordenadas (por ejemplo, imágenes de Internet) por Noah Snavely. GPL.
• COLMAP: Un pipeline de propósito general de Structure-from-Motion (SfM) y Multi-View Stereo (MVS) con una interfaz gráfica y de línea de comandos. Licencia BSD.
• Theia: una biblioteca de visión artificial cuyo objetivo es proporcionar algoritmos eficientes y confiables para Structure from Motion (SfM). Nueva licencia BSD.
• Ames Stereo Pipeline tiene una herramienta para el ajuste de paquetes (licencia Apache II).