Introduzione alla ricostruzione 3D da immagini (Structure from Motion): recupero simultaneo di posizione 3D e posizione della telecamera da una serie di foto non ordinate.

Contents — find the section you need

Raccogliere centinaia di foto scattate da sconosciuti dello stesso punto di riferimento in un luogo turistico e ricostruire un modello 3D di quell'edificio insieme a ogni posizione di ripresa: questo è Structure from Motion (SfM). Da un insieme di immagini di cui non si conoscono a priori l'ordine di scatto, le posizioni relative delle telecamere e persino l'obiettivo utilizzato, il metodo ricostruisce congiuntamente una nuvola di punti 3D geometricamente coerente e le pose delle telecamere. Mentre Visual SLAM e Voice/Vio-Of-Initial (VO/VIO) tracciano la posizione "attuale" di un robot o di una telecamera in tempo reale, SfM viene eseguito principalmente offline, dando priorità alla precisione per ricostruire un'intera scena. Questo articolo analizza la struttura interna di SfM partendo dalle basi, concentrandosi su questa distinzione.

0. Riepilogo di 30 secondi

La SfM (Scenemating From Motion) è il processo di ricostruzione simultanea della nuvola di punti 3D sparsa di una scena e dei parametri intrinseci ed estrinseci di ciascuna telecamera a partire da numerose immagini, tramite corrispondenza di punti caratteristici e verifica geometrica.
Esistono sostanzialmente due strategie di ricostruzione: la SfM incrementale, che aggiunge le telecamere una alla volta in sequenza, e la SfM globale, che prima calcola la posa relativa di ogni coppia di telecamere e poi risolve il problema per le pose globali in un'unica soluzione.
La SfM incrementale è robusta, ma essendo sequenziale, è soggetta a deriva (errore cumulativo). La SfM globale risolve tutto in una volta e quindi resiste alla deriva, ma è meno efficace nel caso di pose relative con molti valori anomali.
I punti 3D e le pose delle telecamere ottenuti tramite triangolazione sono, di per sé, solo stime approssimative influenzate dal rumore dell'immagine. La minimizzazione simultanea dell'errore di riproiezione da parte del Bundle Adjustment (Bundle Adjustment) è ciò che in definitiva determina la precisione di SfM.
SfM e Visual-SLAM condividono la stessa geometria di base, ma differiscono nella filosofia di progettazione: SfM è un'elaborazione batch offline che privilegia la precisione e la completezza, mentre SLAM è un'elaborazione online in tempo reale che privilegia l'immediatezza e la continuità.

1. Cosa riceve in input SfM e cosa produce in output?

L'input è un insieme di immagini $\{I_1,\dots,I_N\}$ il cui ordine di scatto e le cui posizioni relative sono sconosciuti. Ogni immagine può anche essere stata scattata con una fotocamera diversa, un obiettivo diverso e in un momento diverso. L'output è costituito da tre elementi:

La posizione della telecamera $P_i=K_i[R_i\mid\mathbf{t}_i]$ di ciascuna immagine $i$ (parametri intrinseci ed estrinseci)
Un insieme di punti 3D nella scena $\{\mathbf{X}_j\}$ (principalmente una nuvola di punti sparsa corrispondente ai punti caratteristici)
La corrispondenza (traccia) tra quali immagini hanno osservato quali punti 3D

Mentre il manuale sulla calibrazione della telecamera recupera i parametri intrinseci di una singola telecamera a partire da uno schema di calibrazione fisso, la SfM (Scene from Motion) è un problema inverso più ampio: recuperare simultaneamente i parametri intrinseci ed estrinseci di molte telecamere non calibrate o parzialmente calibrate, insieme alla struttura della scena, esclusivamente a partire dai vincoli geometrici tra i punti corrispondenti. Se i metadati EXIF includono una lunghezza focale, questa viene utilizzata come valore iniziale, ma la precisione finale dipende dai vincoli geometrici delle immagini stesse.

Schema del risultato SfM in cui cinque immagini registrate e un'immagine non registrata producono pose stimate della telecamera, punti 3D sparsi e tracce di osservazione — Figura 1. Risultati tipici di SfM. Una ricostruzione contiene non solo una nuvola di punti 3D, ma anche lo stato di registrazione delle immagini, le pose stimate della telecamera e le tracce che indicano quali immagini osservano ciascun punto 3D. Questo è uno schema strutturale, non un risultato di accuratezza derivante da dati misurati.

In un visualizzatore di risultati, verificare innanzitutto se le telecamere si raggruppano in una regione incredibilmente piccola, se la nuvola di punti si divide o si duplica e se qualche immagine non è stata registrata correttamente. Un aspetto simile a un edificio da solo non dimostra l'accuratezza. Valutare l'errore di riproiezione, la lunghezza della traccia e il numero di immagini registrate; se è disponibile una lunghezza rilevata o un valore GNSS, confrontarlo anche con tale scala esterna. La SfM monoculare ha una scala globale arbitraria, quindi una distanza mostrata dal visualizzatore di nuvole di punti non è automaticamente una distanza in metri.

2. La pipeline di base

Le fasi precedenti — estrazione delle caratteristiche, corrispondenza e verifica geometrica — sono esattamente le stesse tecniche elementari trattate in The Feature Detection Primer e The Epipolar Geometry Primer. Le decisioni di progettazione specifiche per la SfM entrano in gioco nella fase successiva all'individuazione di ciascuna relazione tra le coppie di immagini: come assemblare ogni immagine e ogni punto in un unico sistema di coordinate coerente e privo di contraddizioni – ed è qui che le due strategie di SfM incrementale e SfM globale divergono.

3. SfM incrementale: aggiunta di telecamere una alla volta

La SfM incrementale inizia scegliendo una coppia di immagini iniziale con parallasse e corrispondenze sufficienti, e costruendo la prima ricostruzione a due viste stimando la Matrice Essenziale/Fondamentale tramite geometria epipolare. Da lì, ripete i seguenti passaggi:

Scegliere una nuova immagine che abbia già corrispondenze 2D con punti 3D registrati e determinarne la posa tramite PnP.
Triangolare i punti non ancora ricostruiti in 3D, a partire dalle corrispondenze tra la nuova immagine e quelle esistenti.
Perfezionare la posa e la struttura con un bundle adjustment locale o globale ogni tot immagini.
Ricominciare dal punto 1 finché tutte le immagini non sono state elaborate o finché non è più possibile aggiungerne altre.

Questo approccio, ampiamente utilizzato sin da Photo Tourism di Snavely et al. (2006), è adottato anche dalla pipeline standard di COLMAP come Incremental SfM. Poiché incrementa solo un piccolo numero di incognite alla volta, in modo sequenziale, si tratta di un'implementazione robusta ed è facile individuare ed escludere una coppia di immagini errate. D'altra parte, poiché le pose vengono accumulate un'immagine alla volta, piccoli errori iniziali si propagano alle immagini successive e i dataset contenenti grandi loop (un gruppo di immagini che rivisitano lo stesso luogo) tendono ad accumulare deriva. La regolazione periodica dei bundle, insieme al rilevamento delle rivisitazioni equivalente alla chiusura del ciclo, è la chiave per tenere sotto controllo questo errore accumulato.

4. SfM globale: risoluzione simultanea di tutte le relazioni a coppie

L'SfM globale non registra le immagini in sequenza: prima trova la posa relativa $(R_{ij},\mathbf{t}_{ij}/\|\mathbf{t}_{ij}\|)$ per ogni coppia di immagini (o per un sottoinsieme selezionato di esse). Quindi stima congiuntamente l'intero grafo in due fasi.

La media delle rotazioni trova un insieme di rotazioni della telecamera $\{R_i\}$ globalmente minimamente incoerenti dall'insieme di rotazioni relative a coppie $R_{ij}$ . Una metrica di errore comunemente utilizzata si basa sulla mappa logaritmica del gruppo di Lie $SO(3)$ :

\min_{\{R_i\}}\sum_{(i,j)\in\mathcal E}\rho\left(\left\|\mathrm{Log}\left(R_{ij}^\mathsf{T}R_i^\mathsf{T}R_j\right)\right\|^2\right)

$\rho$ è una funzione di perdita robusta che sopprime l'influenza di pose relative errate che agiscono come outlier.

La media delle traslazioni, una volta fissate le rotazioni, trova le posizioni della telecamera $\{\mathbf{t}_i\}$ dall'insieme delle direzioni di traslazione relative $\mathbf{t}_{ij}$ . Poiché una traslazione relativa monoculare fornisce solo una direzione (vedi l'ambiguità di scala discussa nel manuale di geometria epipolare), è necessario risolvere per una configurazione coerente a partire da molti vincoli direzionali a coppie: per questo sono stati proposti approcci come 1DSfM, che includono la rimozione degli outlier.

Poiché la SfM globale utilizza simultaneamente le informazioni di ogni immagine, è, in linea di principio, meno soggetta alla deriva sequenziale che si verifica nella SfM incrementale, ed è anche più facile da parallelizzare computazionalmente. Tuttavia, se i valori anomali sono mescolati alle singole pose relative, l'intera soluzione globale risulta distorta a meno che non vengano rilevati ed esclusi nella fase di media. Il lavoro di Moulon et al. (ICCV 2013) è un esempio rappresentativo che ha notevolmente migliorato la praticità della SfM globale, combinando una media di rotazione robusta con la stima della direzione di traslazione utilizzando il tensore trifocale.

Aspetto	SfM incrementale	SfM globale
Modalità di ricostruzione	Aggiunge un'immagine alla volta da una coppia iniziale	Risolve prima tutte le relazioni a coppie, poi ottimizza congiuntamente
Resistenza alla deriva	Soggetta a propagazione sequenziale ed errore accumulato	Errore accumulato minimo poiché è globalmente ottimale

Resistenza ai valori anomali | Facile da rilevare e rimuovere singolarmente durante l'aggiunta di un'immagine | La rimozione dei valori anomali prima della media determina la precisione |

Costo computazionale | Sequenziale nel numero di immagini, tende a diventare oneroso su larga scala | Parallelizzabile, ma richiede un'ottimizzazione globale per la media |

Difficoltà di implementazione | Numerosi esempi di implementazione, facile da ottimizzare per la robustezza | La teoria e l'implementazione della media di rotazione/traslazione sono più complesse |

Esempi rappresentativi | Bundler, COLMAP (predefinito), VisualSFM | openMVG (pipeline Global SfM), Theia |

In pratica, anziché trattare i due approcci come un'alternativa rigida, si stanno studiando anche approcci ibridi: si costruisce una posa globale approssimativa con Global SfM e la si perfeziona gradualmente, oppure si utilizzano solo le coppie ad alta confidenza in modo globale e si aggiungono le restanti in modo incrementale.

5. Triangolazione e gestione delle tracce

Una volta individuate le pose per un gruppo di immagini, la triangolazione dei punti corrispondenti per ottenere punti 3D è di per sé un'estensione dell'operazione geometrica di base a due viste. La specificità della SfM risiede nella gestione della corrispondenza, chiamata "traccia", quando lo stesso punto fisico viene osservato in tre o più immagini.

Poiché la corrispondenza delle caratteristiche viene eseguita a coppie, le corrispondenze tra le immagini A-B e B-C dovrebbero, idealmente, implicare anche una corrispondenza tra A-C, ma in pratica ciò non sempre si verifica a causa delle distanze reali dei descrittori. Un controllo di coerenza trifocale garantisce la qualità delle tracce.
Maggiore è il numero di osservazioni contenute in una traccia, più stabile diventa la triangolazione, ma una traccia composta solo da immagini con una piccola parallasse tra di loro risulterà comunque instabile in termini di profondità.

Anche una singola corrispondenza errata inserita in una traccia non solo distorce la posizione 3D di quel punto, ma influisce anche sui residui dell'intero processo di bundle adjustment. La verifica in stile RANSAC per ogni traccia e il rifiuto delle tracce con un elevato errore di riproiezione sono entrambi necessari.

6. Il ponte verso il Bundle Adjustment

La posa e la struttura ottenute dalla triangolazione lineare o dal PnP sequenziale sono, nella migliore delle ipotesi, valori iniziali. Minimizzare simultaneamente l'errore di riproiezione su tutte le immagini —

\min_{\{K_i,R_i,\mathbf{t}_i,\mathbf{X}_j\}} \sum_{(i,j)\in\mathcal{O}}\rho\left(\left\|\pi\left(K_i(R_i\mathbf{X}_j+\mathbf{t}_i)\right)-\mathbf{u}_{ij}\right\|^2\right)

— è il Bundle Adjustment, ed è ciò che in definitiva determina l'accuratezza finale della SfM. Il motivo per cui questa ottimizzazione ha una struttura sparsa e perché il complemento di Schur la rende risolvibile anche su larga scala, sono questioni computazionali trattate in dettaglio nel Bundle Adjustment Primer. Ciò che è importante tenere a mente è la differenza nel modo in cui viene utilizzato: l'SfM incrementale esegue un bundle adjustment locale ogni poche immagini aggiunte, mentre l'SfM globale esegue un singolo bundle adjustment completo una volta che tutte le pose globali sono state acquisite.

7. Differenze e punti in comune con Visual-SLAM

SfM e Visual-SLAM condividono gli stessi strumenti matematici: corrispondenza delle caratteristiche, geometria epipolare, PnP e bundle adjustment. La differenza risiede nei loro obiettivi e vincoli.

Aspetto	Structure from Motion	Visual-SLAM
Stile di elaborazione	Elaborazione batch prevalentemente offline	Elaborazione sequenziale online in tempo reale
Ordine di input	Può essere non ordinato (qualsiasi ordine, è possibile utilizzare più telecamere contemporaneamente)	Presuppone frame cronologicamente consecutivi
Obiettivo principale	Ricostruzione 3D di alta qualità con priorità a precisione e completezza	Mantenimento della posizione corrente in tempo reale

Ambito di ottimizzazione | Possibilità di regolazione globale del bundle su tutte le immagini | Ottimizzazione locale/globale limitata ai keyframe, con forti vincoli di budget computazionale |

Gestione delle rivisitazioni | Possibilità di verificare ogni coppia offline | Rilevamento e correzione della chiusura del loop online |

Implementazioni rappresentative | COLMAP, openMVG, Bundler | Famiglia ORB-SLAM, famiglia VINS |

In pratica, sono comuni anche combinazioni come l'utilizzo di una mappa 3D ad alta precisione creata con SfM come mappa iniziale o riferimento di scala per SLAM, oppure l'elaborazione offline della traiettoria dei keyframe di SLAM con SfM per aumentarne la precisione. Le due tecnologie non sono in competizione, bensì si completano a vicenda lungo l'asse temporale offline/online.

8. Implementazioni rappresentative

COLMAP: incentrato sulla SfM incrementale, è attualmente l'implementazione di ricerca e produzione più citata, fornendo una pipeline coerente dall'estrazione delle caratteristiche, alla corrispondenza, alla verifica geometrica e alla ricostruzione fino alla compensazione del bundle e alla spettroscopia multivista.
openMVG (Open Multiple View Geometry): una libreria che implementa pipeline SfM sia incrementali che globali. Spesso utilizzata in combinazione con openMVS per la ricostruzione densa.
Bundler: l'implementazione pionieristica di SfM incrementale che ha reso pubblici i risultati di Photo Tourism ed è diventata un punto di riferimento per molti lavori successivi.
Meshroom (AliceVision): uno strumento di fotogrammetria open-source con un'interfaccia grafica che gestisce tutto, dalla SfM alla MVS fino alla texturizzazione, in un unico passaggio.

Quando si sceglie una libreria, il criterio "più recente significa più accurata" non è quello giusto: valutate in base al numero di immagini da gestire, alle risorse GPU/CPU, all'affidabilità della lunghezza focale EXIF, alla strategia di corrispondenza (esaustiva/sequenziale/ad albero del vocabolario) e alla necessità di un'unica pipeline coerente fino alla generazione di MVS e texture.

9. Condizioni difficili e casi di errore comuni

Scene con texture povere o altamente ripetitive: muri uniformi, superfici piastrellate e file di colture in un campo non producono alcuna corrispondenza o generano frequenti discrepanze.
Set di immagini con parallasse estremamente ridotta: le foto di una scena distante scattate con un teleobiettivo rendono la triangolazione instabile, causando errori di profondità significativi.
Oggetti in movimento e variazioni di illuminazione: i set di foto di luoghi turistici includono persone, veicoli e differenze stagionali o di orario, introducendo corrispondenze che violano l'ipotesi di scena statica.
Cluster di immagini isolate: se le riprese sono divise in due gruppi senza sovrapposizione del campo visivo, SfM non è in grado di unificarle in un unico sistema di coordinate coerente e la ricostruzione si frammenta in diversi pezzi scollegati.
Scene simmetriche: le facciate simmetriche degli edifici, ad esempio, possono convergere verso una soluzione speculare geometricamente coerente ma fisicamente errata.

10. Scelte pratiche

Se le riprese sono completamente ordinate (video o fotogrammi continui di un robot), la selezione della coppia iniziale di Incremental SfM diventa semplice e la pipeline predefinita di COLMAP è spesso sufficiente.
Per grandi raccolte di immagini come le foto turistiche online, dove l'ordine di ripresa e la sovrapposizione sono sconosciuti, la scalabilità di Global SfM tende ad essere vantaggiosa.
Per applicazioni che richiedono prestazioni in tempo reale (robot, realtà aumentata, settore automobilistico), si consiglia di considerare Visual-SLAM o VIO al posto di SfM. Il campo di applicazione principale di SfM è la ricostruzione offline ad alta precisione.
Se hai bisogno di una forma 3D densa (una mesh o un modello con texture), parti dalla nuvola di punti sparsa e dalla posa di SfM, quindi passa a Multi-View Stereo.

11. Riepilogo

Structure from Motion è una tecnologia che ricostruisce congiuntamente le pose della telecamera e la struttura 3D, tramite corrispondenza di caratteristiche e verifica geometrica, a partire da un insieme non ordinato di immagini, utilizzando la strategia Incremental SfM o Global SfM. La strategia Incremental è robusta ma soggetta a deriva, mentre la Global resiste alla deriva ma è sensibile ai valori anomali: un compromesso simmetrico. Con entrambe le strategie, la precisione finale è garantita dal bundle adjustment, che si collega direttamente a Visual-SLAM, la sua tecnologia gemella che opera su un asse temporale diverso, e a Multi-View Stereo, una tecnologia di ricostruzione densa.

Verifica la tua comprensione

Le distanze ricostruite con SfM sono automaticamente espresse in metri?

La ricostruzione monoculare conserva un'ambiguità di scala.

Utilizzare dimensioni note o informazioni di posizionamento per stabilire la scala metrica.

Riferimenti

What to read next

Review the backgroundGuida introduttiva a PnP: recupero della posizione della telecamera a partire da soli punti 3D e un'immagine.Continue the seriesIntroduzione al Bundle Adjustment: il metodo dei minimi quadrati non lineari che perfeziona le pose della fotocamera e i punti 3D.Explore another aspect of this fieldLab di luminosità e luminanza — esposizione, gamma e clipping

#Structure from Motion #SfM #COLMAP #3D Reconstruction #Bundle Adjustment #Computer Vision