Introduzione al Bundle Adjustment: il metodo dei minimi quadrati non lineari che perfeziona le pose della fotocamera e i punti 3D.

Le pose della telecamera e i punti 3D che Structure from Motion e Visual-SLAM ottengono tramite triangolazione e PnP sono, nella migliore delle ipotesi, valori iniziali approssimativi derivanti da stime lineari ed elaborazione sequenziale. Il rumore per immagine, l'errore di quantizzazione nei punti di corrispondenza e l'errore propagato dalla stima sequenziale si accumulano, lasciando una ricostruzione internamente incoerente. Il Bundle Adjustment (BA) è l'ottimizzazione finale che risolve questa incoerenza spostando simultaneamente ogni parametro della telecamera e ogni punto 3D, minimizzando la somma dell'errore di riproiezione su tutti i punti osservati. Il nome "bundle" deriva dal fatto che il fascio di raggi luminosi che va da ogni punto 3D a ogni telecamera viene regolato simultaneamente, in modo che corrispondano alle posizioni osservate.

0. Riepilogo di 30 secondi

• Il Bundle Adjustment è un problema non lineare ai minimi quadrati le cui incognite sono i parametri intrinseci/estrinseci delle telecamere e le coordinate dei punti 3D, minimizzando la somma dei quadrati degli errori di riproiezione su tutte le osservazioni.

• Viene risolto iterativamente con il metodo di Gauss-Newton o con il metodo di Levenberg-Marquardt (LM). Il metodo LM interpola in modo continuo, tramite un parametro \lambda, tra il metodo di Gauss-Newton, instabile ma veloce, e il metodo della discesa più ripida, lento ma stabile.

• Poiché una singola telecamera è collegata solo ai punti effettivamente osservati, l'approssimazione della matrice jacobiana e dell'hessiana assume una forma sparsa, strutturata a blocchi e organizzata per telecamera × punto. Questa sparsità è la chiave che rende trattabili i problemi su larga scala.

• Il trucco del complemento di Schur sfrutta il fatto che i blocchi di punti 3D sono mutuamente indipendenti (diagonali), eliminando prima i punti per risolvere un piccolo "sistema di telecamere ridotto" che coinvolge solo le telecamere. Questo è ciò che permette di risolvere problemi su scala di decine di migliaia di punti e migliaia di telecamere in tempi realistici.

Il Bundle Adjustment è strettamente imparentato con l'ottimizzazione del Pose Graph di SLAM, differenziandosi per il fatto che le sue incognite includono i punti 3D stessi. Si tratta di una tecnologia fondamentale condivisa, utilizzata sia per completare SfM sia per l'ottimizzazione locale/globale di SLAM.

1. Quali sono i dati di input e cosa risolve?

L'input consiste nelle seguenti tre stime iniziali, ottenute come risultati intermedi da SfM o Visual-SLAM:

• Valori iniziali per le pose della telecamera \{K_i, R_i, \mathbf{t}_i\} ( i=1,\dots,m ; in molti casi i parametri intrinseci K_i sono noti o fissi)
• Valori iniziali per i punti 3D \{\mathbf{X}_j\} ( j=1,\dots,n ; coordinate approssimative ottenute tramite triangolazione)
• La corrispondenza tra quale telecamera ha osservato quale punto, ovvero le coordinate dell'immagine \mathbf{u}_{ij} per ogni osservazione (la posizione del pixel in cui la telecamera i ha visto il punto j )

L'output è costituito dalle pose della telecamera e Punti 3D, tutti finemente regolati simultaneamente, che risultano più coerenti internamente tra ogni osservazione. Il fatto che il Bundle Adjustment non sia un metodo per costruire una soluzione da zero, ma piuttosto un'ottimizzazione di finitura che perfeziona localmente un valore iniziale già "approssimativamente corretto", è rilevante per la discussione sulla convergenza che segue.

2. La funzione di costo: errore di riproiezione

La discrepanza tra la posizione in cui un punto 3D \mathbf{X}_j viene proiettato nella telecamera i e la coordinata dell'immagine effettivamente osservata \mathbf{u}_{ij} è chiamata errore di riproiezione. Indicando con R_i, \mathbf{t}_i la posa della telecamera i e con \pi(\cdot) la funzione di proiezione (la mappa non lineare che converte le coordinate omogenee in coordinate pixel), il residuo per una singola osservazione è:

Il Bundle Adjustment minimizza la somma dei quadrati di questo residuo sull'intero insieme di coppie osservate \mathcal{O}=\{(i,j)\}.

\rho è una funzione di perdita robusta, come la perdita di Huber, che impedisce a un singolo valore anomalo di grandi dimensioni, dovuto a una discrepanza, di distorcere l'intero processo di ottimizzazione. Questa equazione ha esattamente la stessa forma già vista nel Manuale introduttivo di SfM — il Bundle Adjustment si occupa del nucleo computazionale per la risoluzione di questo problema di minimizzazione.

1. Risoluzione con il metodo dei minimi quadrati non lineari: da Gauss-Newton a Levenberg-Marquardt

Raccogliendo tutte le incognite in un singolo vettore \mathbf{x} (tutte le pose della telecamera e tutti i punti 3D disposti insieme) e scrivendo l'intero insieme dei residui come \mathbf{r}(\mathbf{x}), l'obiettivo di minimizzazione è \|\mathbf{r}(\mathbf{x})\|^2. Poiché \mathbf{r} è non lineare, utilizziamo uno sviluppo di Taylor del primo ordine attorno alla stima corrente \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} è lo Jacobiano. Sostituendo questo valore e risolvendo per \Delta\mathbf{x} si ottiene l'equazione normale del metodo di Gauss-Newton:

H=J^\mathsf{T}J è l'approssimazione hessiana (l'approssimazione di Gauss-Newton, ignorando i termini di secondo ordine). Risolvere questa equazione per \Delta\mathbf{x}, aggiornare \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x} e ripetere questa operazione fino alla convergenza del residuo costituisce l'intera procedura.

Il metodo di Gauss-Newton converge rapidamente quando il valore iniziale è vicino alla soluzione, ma tende a divergere con un valore iniziale non ottimale. Il metodo di Levenberg-Marquardt (LM), proposto indipendentemente da Levenberg (1944) e Marquardt (1963), attenua questo problema aggiungendo un termine di smorzamento all'equazione normale.

D è solitamente la diagonale di J^\mathsf{T}J (o una matrice di scala equivalente), e \lambda è il coefficiente di smorzamento. Quando \lambda è piccolo, il comportamento è simile a quello di Gauss-Newton e la convergenza è rapida; quando \lambda è grande, compie piccoli passi sicuri avvicinandosi alla discesa più ripida. Attraverso uno schema di controllo adattivo — riducendo \lambda per accelerare ogni volta che il costo diminuisce a ogni iterazione, e aumentando \lambda per rifiutare e accorciare il passo ogni volta che il costo aumenta — LM unisce la velocità di Gauss-Newton alla stabilità della discesa più ripida. Quasi tutte le implementazioni pratiche di Bundle Adjustment (Ceres Solver, g2o, SBA e altre, discusse di seguito) adottano il metodo LM o un metodo di regione di fiducia strettamente correlato.

4. Perché la matrice jacobiana è sparsa?

Le incognite del Bundle Adjustment sono la posizione della telecamera (6 gradi di libertà: 3 di rotazione più 3 di traslazione, se i parametri intrinseci sono fissi) × m telecamere e il punto 3D (3 gradi di libertà) × n punti, per un totale di 6m+3n dimensioni. Nei problemi SfM reali con decine di migliaia di osservazioni o più, trattare ingenuamente questa J^\mathsf{T}J come una matrice densa costa O((6m+3n)^3) — non risolvibile in tempi realistici.

Ciò che viene in aiuto in questo caso è la struttura per cui l'errore di riproiezione r_{ij} "dipende solo dai parametri della telecamera i e dai parametri del punto j". Le derivate parziali rispetto a qualsiasi altra telecamera k\neq i o punto l\neq j sono identicamente zero.

In altre parole, la riga della matrice jacobiana generata da una singola osservazione ha elementi non nulli solo nel blocco corrispondente alla telecamera e nel blocco corrispondente al punto. Il numero di righe cresce in proporzione al numero di osservazioni, ma il numero di elementi non nulli per riga rimane costante (telecamera 6 + punto 3, o un po' di più se si includono i parametri intrinseci). Questa sparsità si manifesta, osservando J^\mathsf{T}J, come la seguente struttura a blocchi.

• B: interazioni tra i parametri della telecamera. Questo valore è zero a meno che le telecamere i e k non osservino un punto comune, quindi ha una struttura a blocchi sparsi.

• C: interazioni tra i parametri dei punti 3D. Poiché i 3 gradi di libertà di un punto j non sono mai accoppiati a nessun altro punto, questa è una matrice a blocchi diagonali — il presupposto per il trucco del complemento di Schur nella sezione successiva.

• E: interazioni tra telecamere e punti (un blocco diverso da zero appare per ogni osservazione (i,j)).

5. La pipeline di base

Diagram 1 · Use the button to switch views

7. Libertà di gauge: le direzioni lungo le quali la soluzione non è univocamente determinata

Il Bundle Adjustment mantiene un grado di libertà che consente di spostare l'intero insieme di parametri senza modificare il valore della funzione di costo. Spostando contemporaneamente tutte le telecamere e tutti i punti 3D con la stessa rotazione, traslazione e scala, l'errore di riproiezione rimane completamente invariato (nel caso di una ripresa monoculare, anche la scala assoluta è indeterminata). Questo grado di libertà è chiamato libertà di gauge. Se non viene gestito, rende J^\mathsf{T}J singolare (a rango deficitario), il che rende l'equazione normale irrisolvibile o numericamente instabile.

In pratica, questo problema viene aggirato fissando la posizione delle prime due telecamere o una lunghezza della linea di base, oppure sfruttando il fatto che il termine di smorzamento \lambda D del modello LM regolarizza implicitamente questa direzione singolare. Quando sono disponibili informazioni sulla scala assoluta o sulla posizione assoluta, ad esempio da GPS o da un'IMU, è naturale utilizzarle come ulteriore vincolo per fissare il gauge.

8. La differenza rispetto all'ottimizzazione del grafo delle pose

L'ottimizzazione del grafo delle pose, trattata nel manuale introduttivo sulla chiusura del ciclo, appartiene allo stesso quadro matematico del Bundle Adjustment, in quanto minimizza, con una funzione di perdita robusta, un residuo non lineare dei minimi quadrati costruito con la mappa \mathrm{Log}. La differenza sta nella natura delle incognite.

Utilizzo principale | Rifinitura finale di SfM, affinamento delle mappe locali/globali | Correzione della deriva globale in SLAM (dopo la chiusura del ciclo) |

Nei sistemi Visual-SLAM reali, è comune osservare una divisione del lavoro: il bundle adjustment locale (BA locale), che include punti 3D, affina l'area intorno ai keyframe fotogramma per fotogramma, mentre l'ottimizzazione leggera del Pose Graph senza punti 3D espliciti corregge rapidamente la traiettoria globale ogni volta che viene rilevata una chiusura del ciclo. Il bundle adjustment completo, che include punti 3D (BA globale), è più preciso ma computazionalmente oneroso, quindi non può essere eseguito frequentemente in situazioni che richiedono prestazioni in tempo reale.

9. Implementazioni rappresentative

• Ceres Solver: una libreria di minimi quadrati non lineari di uso generale sviluppata da Google, in produzione dal 2010. Include risolutori basati su Schur ed è utilizzata come backend per il bundle adjustment in molte implementazioni SfM/SLAM, tra cui COLMAP.

• g2o: un framework di ottimizzazione di grafi pubblicato da Kümmerle et al. all'ICRA 2011, in grado di gestire sia l'ottimizzazione del Pose Graph di SLAM che il bundle adjustment all'interno dello stesso framework. È stato ampiamente utilizzato come backend della famiglia ORB-SLAM.

• SBA (Sparse Bundle Adjustment): una delle prime implementazioni disponibili pubblicamente, specializzata per il bundle adjustment sparso, pubblicata da Lourakis e Argyros su ACM Transactions on Mathematical Software nel 2009. Viene spesso citata come esempio rappresentativo che implementa esplicitamente il trucco del complemento di Schur.

• • BA integrato in COLMAP: utilizza internamente Ceres Solver, passando automaticamente tra bundle adjustment locale e globale a ogni passo dell'SfM incrementale.

10. Condizioni difficili e casi di errore comuni

• Valori iniziali scadenti: il Bundle Adjustment è un'ottimizzazione locale: se il valore iniziale è lontano dalla soluzione reale, può convergere a una soluzione locale errata o non convergere affatto. La qualità del valore iniziale ottenuto tramite triangolazione o PnP determina l'accuratezza finale.

• Punti con poche osservazioni o parallasse ridotta: un punto osservato da un numero molto limitato di immagini, o con una parallasse ridotta, tende ad avere una matrice jacobiana mal condizionata e può lasciare un grande errore residuo concentrato esclusivamente lungo la direzione della profondità.

• Forte contaminazione da outlier: con molti errori di corrispondenza, anche una funzione di perdita robusta non riesce ad assorbirli completamente e i punti vicini corretti possono risultare trascinati e distorti.

• Problemi di scala estremamente ampia: per ricostruzioni su scala urbana con milioni di osservazioni, anche con il complemento di Schur, i costi computazionali e di memoria diventano non trascurabili, rendendo necessario suddividere e parallelizzare il problema, oppure combinarlo con tecniche approssimate (come la riduzione della regione di fiducia del modello lineare).

• Genderità di gauge non gestita: come già accennato, dimenticare di fissare il gauge causa instabilità numerica, con conseguente mancata convergenza o deriva verso soluzioni non fisiche.

11. Scelte pratiche

• Se è necessaria un'elevata precisione come fase finale della ricostruzione 3D per la modellazione 3D (SfM), l'esecuzione di un bundle adjustment completo alla fine, indipendentemente dal fatto che si utilizzi una strategia incrementale o globale, è la regola standard. Seguire le impostazioni predefinite di un'implementazione esistente come COLMAP difficilmente porterà a risultati errati.

• Per lo SLAM in tempo reale, il bundle adjustment completo su ogni singolo frame è troppo oneroso dal punto di vista computazionale. Una progettazione pratica combina la regolazione locale del bundle (bundle adjustment) solo sull'ultimo set di keyframe con l'ottimizzazione del Pose Graph che si attiva solo alla chiusura del ciclo.

• Se si sta costruendo una pipeline da zero, è ragionevole basarla su una libreria come Ceres Solver o g2o. Scrivere un'implementazione del complemento di Schur da zero offre pochi vantaggi in termini di apprendimento rispetto al costo della verifica della sua correttezza.

• Per ricostruzioni su larga scala, a livello di città, anziché affidarsi a un singolo bundle adjustment, si possono considerare metodi che suddividono il problema per regione e lo integrano gerarchicamente (questo viene comunemente fatto anche come fase preliminare per Multi-View Stereo, discusso di seguito).

12. Riepilogo

Il Bundle Adjustment è un problema non lineare dei minimi quadrati che minimizza simultaneamente l'errore di riproiezione su ogni telecamera e ogni punto 3D, risolto iterativamente tramite il metodo di Levenberg-Marquardt. Il trucco del complemento di Schur, che sfrutta la sparsità della relazione tra la telecamera e il punto di osservazione, è ciò che rende questa ottimizzazione risolvibile in tempi realistici anche su una scala di decine di migliaia di punti. Sebbene condivida un quadro matematico con l'ottimizzazione del Pose Graph, la scelta tra i due si riduce alla necessità di mantenere esplicitamente i punti 3D, ed è una tecnologia fondamentale condivisa che in definitiva è alla base dell'accuratezza sia di SfM che di SLAM.

Riferimenti

• Triggs, McLauchlan, Hartley & Fitzgibbon, Bundle Adjustment — A Modern Synthesis (Vision Algorithms: Theory and Practice, 2000)
• Kümmerle, Grisetti, Strasdat, Konolige & Burgard, g2o: A General Framework for Graph Optimization (ICRA 2011)
• Lourakis & Argyros, SBA: A Software Package for Generic Sparse Bundle Adjustment (ACM Transactions on Mathematical Software, 2009)
• [Documentazione ufficiale di Ceres Solver: Non-linear Least Squares]( https://ceres-solver.readthedocs.io/latest/nnls_tutorial.html - Documentazione ufficiale di Ceres Solver: Risolutori lineari basati su Schur
• Hartley e Zisserman, Geometria a viste multiple nella visione artificiale (pagina ufficiale degli autori)

-