This thesis addresses the problem of viewing graph solvability in an uncalibrated Structure-from-Motion setup. The goal is to determine whether a camera configuration can be recovered up to finitely many solutions from a given set of fundamental matrices, which is a fundamental property for multi-view reconstruction. Although existing algebraic and geometric methods provide theoretical conditions for solvability, they often become too computationally demanding and inefficient when applied to large viewing graphs and real-world datasets. To overcome these limitations, we propose a direct approach for establishing the finite solvability of viewing graphs by working within affine charts to resolve projective ambiguities. Our method characterizes solvability by evaluating the numerical rank of a global Jacobian matrix derived from the fundamental map. We introduce a direct analytical derivation of this Jacobian using matrix differential calculus, which eliminates the need for expensive symbolic computations. Furthermore, a row-normalization step is implemented to improve matrix conditioning and accelerate numerical convergence. Depending on the graph scale, we implement two computational strategies. For smaller configurations, we use a direct singular value decomposition (the rank method), while for large-scale graphs, we employ an iterative sparse eigensolver (the eigs method) which targets the smallest eigenvalue. The proposed method was evaluated on both synthetic graphs and standard real-world Structure-from-Motion benchmarks, and its performance was compared against the previous state-of-the-art method implemented for the same task. Experimental results demonstrate that our approach yields identical solvability classifications while achieving a significant speedup. This performance gap is particularly pronounced in large-scale real-world datasets, where our normalized analytical formulation maintains superior computational efficiency, offering a robust and preprocessing solution for multi-view reconstruction pipelines.
Questa tesi affronta il problema della risolvibilità dei grafi di vista (viewing graph solvability) nel contesto di Structure-from-Motion non calibrata. L'obiettivo è determinare se una configurazione di telecamere sia calcolabile a meno di un numero finito di soluzioni da un insieme di matrici fondamentali, proprietà essenziale per la ricostruzione multi-vista. Sebbene i metodi algebrici e geometrici esistenti forniscano condizioni teoriche di risolvibilità, essi risultano spesso computazionalmente onerosi e inefficienti su grafi di grandi dimensioni e dataset reali. Per superare tali limitazioni, proponiamo un approccio diretto per stabilire la risolvibilità finita dei grafi di vista operando in carte affini per eliminare le ambiguità proiettive. Il metodo caratterizza la risolvibilità valutando il rango numerico di una matrice Jacobiana globale derivata dalla mappa fondamentale. Introduciamo una derivazione analitica diretta della Jacobiana tramite calcolo differenziale matriciale, eliminando i costosi calcoli simbolici. Inoltre, applichiamo una normalizzazione delle righe per migliorare il condizionamento della matrice e accelerare la convergenza. A seconda della scala del grafo, implementiamo due strategie: una decomposizione a valori singolari diretta (il rank method) per grafi di dimensioni ridotte, e un solutore iterativo di autovalori sparsi (l'eigs method) per grafi su larga scala. Il metodo è stato valutato su grafi sintetici e benchmark reali standard di Structure-from-Motion, confrontandone le prestazioni con il precedente stato dell'arte per lo stesso task. I risultati dimostrano che il nostro approccio fornisce classificazioni identiche ottenendo un notevole incremento di velocità. Questo divario è particolarmente evidente nei dataset reali su larga scala, dove la nostra formulazione analitica normalizzata garantisce stabilità numerica ed efficienza, offrendo una soluzione robusta per le pipeline di ricostruzione multi-vista.
A direct approach to viewing graph solvability via the fundamental map
DOKMANOVIC, IRENA
2025/2026
Abstract
This thesis addresses the problem of viewing graph solvability in an uncalibrated Structure-from-Motion setup. The goal is to determine whether a camera configuration can be recovered up to finitely many solutions from a given set of fundamental matrices, which is a fundamental property for multi-view reconstruction. Although existing algebraic and geometric methods provide theoretical conditions for solvability, they often become too computationally demanding and inefficient when applied to large viewing graphs and real-world datasets. To overcome these limitations, we propose a direct approach for establishing the finite solvability of viewing graphs by working within affine charts to resolve projective ambiguities. Our method characterizes solvability by evaluating the numerical rank of a global Jacobian matrix derived from the fundamental map. We introduce a direct analytical derivation of this Jacobian using matrix differential calculus, which eliminates the need for expensive symbolic computations. Furthermore, a row-normalization step is implemented to improve matrix conditioning and accelerate numerical convergence. Depending on the graph scale, we implement two computational strategies. For smaller configurations, we use a direct singular value decomposition (the rank method), while for large-scale graphs, we employ an iterative sparse eigensolver (the eigs method) which targets the smallest eigenvalue. The proposed method was evaluated on both synthetic graphs and standard real-world Structure-from-Motion benchmarks, and its performance was compared against the previous state-of-the-art method implemented for the same task. Experimental results demonstrate that our approach yields identical solvability classifications while achieving a significant speedup. This performance gap is particularly pronounced in large-scale real-world datasets, where our normalized analytical formulation maintains superior computational efficiency, offering a robust and preprocessing solution for multi-view reconstruction pipelines.| File | Dimensione | Formato | |
|---|---|---|---|
|
Executive_Summary_Irena.pdf
accessibile in internet per tutti
Descrizione: executive summary of the thesis
Dimensione
759.06 kB
Formato
Adobe PDF
|
759.06 kB | Adobe PDF | Visualizza/Apri |
|
Thesis_Irena.pdf
accessibile in internet per tutti
Descrizione: the thesis report
Dimensione
3.07 MB
Formato
Adobe PDF
|
3.07 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/261209