Introducción al ajuste de haces: el método de mínimos cuadrados no lineales que perfecciona las poses de la cámara y los puntos 3D.

Las poses de la cámara y los puntos 3D que Structure from Motion y Visual-SLAM obtienen mediante triangulación y PnP son, en el mejor de los casos, valores iniciales aproximados derivados de aproximaciones lineales y procesamiento secuencial. El ruido por imagen, el error de cuantización en los puntos de correspondencia y el error propagado de la estimación secuencial se acumulan, dando como resultado una reconstrucción internamente inconsistente. El ajuste de haces (BA) es la optimización final que resuelve esta inconsistencia moviendo simultáneamente cada parámetro de la cámara y cada punto 3D, minimizando la suma del error de reproyección en todos los puntos observados. El nombre "haz" proviene del ajuste simultáneo del haz de rayos de luz que va desde cada punto 3D a cada cámara, para que coincidan con las posiciones observadas.

0. Resumen de 30 segundos

• El ajuste de haces es un problema de mínimos cuadrados no lineal cuyas incógnitas son los parámetros intrínsecos/extrínsecos de las cámaras y las coordenadas de los puntos 3D, minimizando la suma del error de reproyección al cuadrado sobre todas las observaciones.

• Se resuelve iterativamente con el método de Gauss-Newton o el de Levenberg-Marquardt (LM). LM interpola suavemente, mediante un parámetro \lambda, entre el método de Gauss-Newton (inestable pero rápido) y el método de descenso más pronunciado (lento pero estable).

• Dado que una sola cámara solo está vinculada a los puntos que realmente captó, la aproximación jacobiana y hessiana adopta una forma dispersa y estructurada en bloques, organizada por cámara × punto. Esta dispersión es clave para que los problemas a gran escala sean manejables.

• El truco del complemento de Schur aprovecha la independencia mutua de los bloques de puntos 3D (diagonales de bloques), eliminando primero los puntos para resolver un pequeño "sistema de cámara reducido" que involucra únicamente las cámaras. Esto permite resolver problemas de decenas de miles de puntos y miles de cámaras en un tiempo razonable.

• El ajuste de haces (Bundle Adjustment) es muy similar a la optimización del grafo de poses de SLAM, diferenciándose en que sus incógnitas incluyen los propios puntos 3D. Es una tecnología fundamental compartida, utilizada tanto para finalizar la reconstrucción 3D a partir de movimiento (SfM) como para la optimización local/global de SLAM.

1. ¿Qué datos de entrada recibe y qué problemas resuelve?

La entrada consta de las siguientes tres estimaciones iniciales, obtenidas como resultados intermedios de SfM o Visual-SLAM:

• Valores iniciales para las poses de la cámara \{K_i, R_i, \mathbf{t}_i\} (i=1,\dots,m; en muchos casos, los parámetros intrínsecos K_i son conocidos o fijos)
• Valores iniciales para los puntos 3D \{\mathbf{X}_j\} (j=1,\dots,n; coordenadas aproximadas obtenidas por triangulación)
• La correspondencia entre qué cámara observó cada punto; es decir, las coordenadas de la imagen \mathbf{u}_{ij} para cada observación (la posición del píxel en la que la cámara i vio el punto j)

La salida son las poses de la cámara y los puntos 3D, ajustados con precisión de forma simultánea, que presentan una mayor consistencia interna en cada iteración. Observación. El hecho de que el Ajuste de Paquetes no sea un método para construir una solución desde cero, sino una optimización final que perfecciona localmente un valor inicial ya "aproximadamente correcto", es relevante para la discusión sobre la convergencia que se presenta a continuación.

2. La Función de Costo: Error de Reproyección

La discrepancia entre la proyección de un punto 3D \mathbf{X}_j en la cámara i y la coordenada de la imagen observada real \mathbf{u}_{ij} se denomina error de reproyección. Si denotamos la pose de la cámara i como R_i, \mathbf{t}_i y la función de proyección como \pi(\cdot) (el mapeo no lineal que convierte coordenadas homogéneas en coordenadas de píxeles), el residuo para una observación es:

El Ajuste de Paquetes minimiza la suma de los cuadrados de este residuo sobre el conjunto completo de pares observados \mathcal{O}=\{(i,j)\}.

\rho es una función de pérdida robusta, como la pérdida de Huber, que evita que un único valor atípico grande debido a una discrepancia distorsione toda la optimización. Esta ecuación tiene exactamente la misma forma que ya se vio en la Introducción a SfM. El ajuste de haces se encarga del núcleo computacional para resolver este problema de minimización.

3. Resolución mediante mínimos cuadrados no lineales: De Gauss-Newton a Levenberg-Marquardt

Al agrupar todas las incógnitas en un único vector \mathbf{x} (todas las poses de la cámara y todos los puntos 3D dispuestos juntos) y escribir el conjunto completo de residuos como \mathbf{r}(\mathbf{x}), el objetivo de minimización es \|\mathbf{r}(\mathbf{x})\|^2. Dado que \mathbf{r} es no lineal, utilizamos un desarrollo de Taylor de primer orden alrededor de la estimación actual \mathbf{x}_k: \mathbf{r}(\mathbf{x}_k+\Delta\mathbf{x})\approx \mathbf{r}(\mathbf{x}_k)+J\Delta\mathbf{x}. J=\partial \mathbf{r}/\partial \mathbf{x} es el jacobiano. Sustituyendo este valor y resolviendo para \Delta\mathbf{x}, obtenemos la ecuación normal del método de Gauss-Newton:

H=J^\mathsf{T}J es la aproximación del hessiano (la aproximación de Gauss-Newton, ignorando los términos de segundo orden). El procedimiento completo consiste en resolver esta ecuación para \Delta\mathbf{x}, actualizar \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x} y repetir esta operación hasta que el residuo converja.

El método de Gauss-Newton converge rápidamente cuando el valor inicial está cerca de la solución, pero tiende a divergir con un valor inicial deficiente. El método de Levenberg-Marquardt (LM), propuesto independientemente por Levenberg (1944) y Marquardt (1963), simplifica este proceso añadiendo un término de amortiguación a la ecuación normal.

D suele ser la diagonal de J^\mathsf{T}J (o una matriz de escala equivalente), y \lambda es el coeficiente de amortiguación. Cuando \lambda es pequeño, se comporta de forma similar al método de Gauss-Newton y converge rápidamente; cuando \lambda es grande, da pequeños pasos seguros que se aproximan al descenso más pronunciado. Mediante un esquema de control adaptativo —reducir \lambda para acelerar cuando el coste disminuye en cada iteración, y aumentar \lambda para rechazar y acortar el paso cuando el coste aumenta—, LM combina la velocidad de Gauss-Newton con la estabilidad del descenso más pronunciado. Casi todas las implementaciones prácticas de Ajuste de Paquetes (Ceres Solver, g2o, SBA y otras, que se describen más adelante) adoptan LM o un método de región de confianza estrechamente relacionado.

4. ¿Por qué es disperso el jacobiano?

Las incógnitas del Ajuste de Paquetes son la pose de la cámara (6 grados de libertad: 3 de rotación más 3 de traslación, si los parámetros intrínsecos son fijos) × m cámaras, y puntos 3D (3 grados de libertad) × n puntos, sumando hasta 6m+3n dimensiones. En problemas reales de SfM con decenas de miles de observaciones o más, tratar ingenuamente esta J^\mathsf{T}J como una matriz densa resulta en O((6m+3n)^3), un problema irresoluble en tiempo real.

La solución reside en la estructura que establece que el error de reproyección r_{ij} "depende únicamente de los parámetros de la cámara i y del punto j". Las derivadas parciales con respecto a cualquier otra cámara k\neq i o punto l\neq j son idénticamente cero.

En otras palabras, la fila del jacobiano generado por una sola observación tiene entradas distintas de cero solo en el bloque correspondiente a la cámara y al punto. El número de filas crece proporcionalmente al número de observaciones, pero el número de entradas no nulas por fila permanece constante (cámara 6 + punto 3, o un poco más si se incluyen parámetros intrínsecos). Esta dispersión se manifiesta, al observar J^\mathsf{T}J, como la siguiente estructura de bloques:

• B: interacciones entre parámetros de la cámara. Este valor es cero a menos que las cámaras i y k observen un punto común, por lo que presenta una estructura de bloques dispersa.

• C: interacciones entre parámetros de puntos 3D. Dado que los 3 grados de libertad de un punto j nunca están acoplados a ningún otro punto, se trata de una matriz diagonal por bloques, premisa del método del complemento de Schur que se describe en la siguiente sección. - E: interacciones entre cámaras y puntos (aparece un bloque distinto de cero para cada observación (i,j)).

5. El flujo básico

Diagram 1 · Use the button to switch views

6. El truco del complemento de Schur: Convertir la escasez en computación reducida

Utilizando la estructura de bloques de la sección anterior, podemos escribir la ecuación normal (J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r} dividida en la actualización de la cámara \Delta\mathbf{c} y la actualización del punto \Delta\mathbf{p} como:

(donde B', C' son los bloques después de agregar el término de amortiguación). Dado que C' es una matriz diagonal por bloques, independiente por punto 3D, cada bloque de 3×3 se puede invertir individualmente, con un costo aproximadamente proporcional al número de puntos n. Al usar esta C'^{-1} para eliminar \Delta\mathbf{p}, obtenemos el sistema de cámaras reducido, que solo involucra cámaras:

La matriz B'-EC'^{-1}E^\mathsf{T} del lado izquierdo se denomina complemento de Schur. Esta matriz tiene un tamaño de 6m\times 6m (que depende únicamente del número de cámaras, no del número de puntos n), y una vez resuelta \Delta\mathbf{c}, la actualización de cada punto se puede recuperar fácilmente con:

En un problema típico de SfM, el número de puntos n puede ser decenas de veces mayor que el número de cámaras m, por lo que, en lugar de resolver ingenuamente un sistema con dimensiones 6m+3n, solo es necesario manejar el complemento de Schur, de dimensión 6m. Esta es la idea central que hace que el ajuste de haces sea prácticamente resoluble incluso a escalas de decenas de miles de puntos. Fue organizado teóricamente por Triggs et al. en "Bundle Adjustment — A Modern Synthesis" (2000), y es la implementación interna estándar en bibliotecas actuales como Ceres Solver y g2o.

Ceres Solver ofrece varias opciones para resolver este sistema reducido: DENSE_SCHUR, que lo resuelve como una matriz densa (hasta unos cientos de cámaras); SPARSE_SCHUR, que aprovecha la dispersión mediante reordenamiento (miles de cámaras); y ITERATIVE_SCHUR, que aplica el gradiente conjugado al complemento de Schur (para problemas de mayor escala). Elegir entre estas opciones en función de la escala del problema es una regla práctica.

7. Libertad de calibre: las direcciones en las que la solución no está determinada de forma unívoca

El ajuste de paquetes conserva un grado de libertad que permite mover todo el conjunto de parámetros sin modificar el valor de la función de coste. Mover todas las cámaras y todos los puntos 3D simultáneamente con la misma rotación, traslación y escala deja el error de reproyección completamente inalterado (en el caso de una sola cámara, la escala absoluta también es indeterminada). Este grado de libertad se denomina libertad de calibre. Si no se aborda, provoca que J^\mathsf{T}J sea singular (de rango deficiente), lo que hace que la ecuación normal sea irresoluble o numéricamente inestable.

En la práctica, esto se soluciona fijando la pose de las dos primeras cámaras o la longitud de una línea base, o bien aprovechando que el término de amortiguación de LM, \lambda D, regulariza implícitamente esta dirección singular. Cuando se dispone de información de escala o pose absoluta —por ejemplo, procedente de GPS o una IMU—, es natural utilizarla como restricción adicional para fijar el indicador.

8. La diferencia con la optimización del grafo de pose

La optimización del grafo de pose, que se aborda en la Introducción al cierre de bucles, también pertenece al mismo marco matemático que el ajuste de haces, en el sentido de que minimiza, con una función de pérdida robusta, un residuo de mínimos cuadrados no lineal construido con el mapa \mathrm{Log}. La diferencia radica en cuáles son realmente las incógnitas.

En los sistemas Visual-SLAM reales, es común observar una división del trabajo: el ajuste de haces local (BA local), que incluye puntos 3D, refina el área alrededor de los fotogramas clave fotograma a fotograma, mientras que la optimización ligera del grafo de pose sin puntos 3D explícitos corrige rápidamente la trayectoria global cuando se detecta un cierre de bucle. El ajuste de haces completo, que incluye puntos 3D (BA global), es más preciso pero computacionalmente costoso, por lo que no se puede ejecutar con frecuencia en situaciones que exigen rendimiento en tiempo real.

9. Implementaciones representativas

• Ceres Solver: una biblioteca de mínimos cuadrados no lineales de propósito general desarrollada por Google, en uso en producción desde 2010. Incluye solucionadores basados en Schur y se utiliza como backend de ajuste de haces para muchas implementaciones de SfM/SLAM, incluyendo COLMAP.

• g2o: un marco de optimización de grafos publicado por Kümmerle et al. en ICRA 2011, capaz de gestionar tanto la optimización del grafo de poses de SLAM como el ajuste de haces dentro del mismo marco. Se ha utilizado ampliamente como backend de la familia ORB-SLAM.

• SBA (Sparse Bundle Adjustment): una de las primeras implementaciones públicas especializadas en el ajuste de haces dispersos, publicada por Lourakis y Argyros en ACM Transactions on Mathematical Software en 2009. Se cita a menudo como un ejemplo representativo que implementa explícitamente el truco del complemento de Schur.

• Ajuste de haces integrado de COLMAP: utiliza internamente el solucionador Ceres, alternando automáticamente entre el ajuste de haces local y global en cada paso de la reconstrucción incremental a partir de imágenes (SfM).

10. Condiciones difíciles y casos de fallo comunes

• Valores iniciales deficientes: El ajuste de haces es una optimización local. Si el valor inicial está lejos de la solución real, puede converger a una solución local incorrecta o no converger en absoluto. La calidad del valor inicial obtenido mediante triangulación o PnP determina la precisión final.

• Puntos con pocas observaciones o paralaje pequeño: Un punto observado a partir de un número muy reducido de imágenes, o con poco paralaje, tiende a tener un jacobiano mal condicionado y puede dejar un gran error residual concentrado exclusivamente en la dirección de profundidad.

• Contaminación por valores atípicos elevados: Con muchas discrepancias, incluso una función de pérdida robusta no puede absorberlas por completo, y los puntos vecinos correctos también pueden verse afectados y distorsionados.

• Problemas a escala extremadamente grande: para reconstrucciones a escala urbana con millones de observaciones, incluso con el complemento de Schur, los costos de computación y memoria se vuelven considerables, lo que requiere dividir y paralelizar el problema, o combinarlo con técnicas aproximadas (como la reducción de la región de confianza de LM).

• Libertad de calibre no controlada: como se mencionó anteriormente, olvidar fijar el calibre provoca inestabilidad numérica, lo que lleva a la falta de convergencia o a una solución no física.

11. Opciones prácticas

• Si se requiere precisión densa como etapa final de SfM, realizar un ajuste de haces completo al final —independientemente de si se utilizó la estrategia incremental o global— es la regla general. Seguir la configuración predeterminada de una implementación existente como COLMAP no suele generar grandes problemas.

• Para SLAM en tiempo real, el ajuste de haces completo en cada fotograma es demasiado costoso computacionalmente. Un diseño práctico combina el ajuste de haces local sobre el conjunto de fotogramas clave más reciente con la optimización del grafo de poses que solo se activa al cerrar el bucle. - Si estás creando tu propio pipeline desde cero, es recomendable basarlo en una biblioteca como Ceres Solver o g2o. Implementar el complemento de Schur desde cero ofrece pocos beneficios en comparación con el costo de verificar su corrección.

• Para reconstrucciones a gran escala, como la de ciudades, en lugar de depender de un único ajuste de haces, considera métodos que dividan el problema por región e integren jerárquicamente (esto también se suele hacer como etapa preliminar para Multi-View Stereo, que se analiza más adelante).

12. Resumen

El ajuste de haces es un problema de mínimos cuadrados no lineales que minimiza simultáneamente el error de reproyección en cada cámara y cada punto 3D, y se resuelve iterativamente mediante el método de Levenberg-Marquardt. El truco del complemento de Schur, que aprovecha la escasez de la relación de observación entre la cámara y el punto, es lo que permite que esta optimización se pueda resolver en un tiempo realista, incluso a escala de decenas de miles de puntos. Aunque comparte un marco matemático con la optimización de grafos de pose, la elección entre ambas se reduce a si se mantienen explícitamente los puntos 3D, y se trata de una tecnología fundamental compartida que, en última instancia, sustenta la precisión tanto de SfM como de SLAM.