Robust estimation of the fundamental matrix : a comparison between classical techniques and particle swarm based heuristics

Two different perspective images of the same 3D scene are related one to the other because of geometrical constraints that can be described by a 3 × 3 singular matrix known as the Fundamental Matrix F. This matrix plays a key role in a huge number of Computer Vision tasks and many techniques to estimate it have been proposed in the past, the most frequently used being the Sample Consensus algorithms. Recently, interesting results for this estimation problem have been achieved by estimation algorithms based on the so-called Particle Swarm Optimization (PSO) technique. This is a meta-heuristic aimed at simulating the behavior of groups of animals having no leaders, which act in an organized way thanks to a sort of collective intelligence emerging from the simple interactions of the single individuals. Although these algorithms proved to achieve good results in the estimation of the Fundamental Matrix, they have not received much attention from Computer Vision scientists, so far. The purpose of this thesis is two-fold: first, a new algorithm for the esti- mation of the Fundamental Matrix using the PSO meta-heuristic is proposed, which is based on the existing ones. We have called it the Self-Adaptive BPSO. Then, extensive tests are performed to compare the quality of the es- timates produced by the proposed algorithm with respect to both the other existing Particle Swarm heuristics and the classical Sample Consensus algo- rithms. The results we obtained show us that the proposed algorithm produces good estimates, being superior to the majority of the other algorithms we tested, while maintaining a reasonable computational complexity.

Due diverse immagini di una medesima scena tridimensionale sono correlate tra di loro per mezzo di vincoli geometrici che possono essere convenien- temente descritti mediante una matrice singolare 3 × 3 nota come Matrice Fondamentale F. Tale matrice riveste un ruolo chiave in un ampio numero di compiti all’interno del campo della Visione Artificiale e numerose tec- niche per ottenerne una stima sono state proposte in passato; tra di esse, le più frequentemente utilizzate sono quelle basate sul paradigma di Sample Consensus. Negli ultimi anni, in tale ambito sono stati ottenuti dei risultati piut- tosto interessanti mediante algoritmi basati su una tecnica nota come Par- ticle Swarm Optimization (PSO). Quest’ultima è una meta-euristica il cui scopo è quello di simulare il comportamento di gruppi di animali privi di un leader, che agiscono in maniera organizzata grazie ad una sorta di intelligenza collettiva. Tale intelligenza scaturisce dalle semplici interazioni tra i singoli individui. Nonostante questi algoritmi abbiano dimostrato di produrre buoni risultati nella stima della Matrice Fondamentale, sinora non hanno ricevuto molta attenzione da parte degli studiosi di Visione Artificiale. Lo scopo della presente tesi è duplice: prima di tutto viene proposto un algoritmo per la stima della Matrice Fondamentale facente uso della meta- euristica PSO e basato sugli algoritmi esistenti. Ad esso abbiamo assegnato il nome di Self-Adaptive BPSO. In seguito, abbiamo eseguito dei test esaustivi per valutare la qualità delle stime prodotte dall’algoritmo proposto rispetto alle stime prodotte sia dagli algoritmi classici di Sample Consensus, sia dalle euristiche già esistenti basate sulla Particle Swarm Optimization. I risultati che abbiamo ottenuto mostrano come l’algoritmo da noi pro- posto produca delle stime accurate, dimostrandosi superiore alla maggior parte degli altri algoritmi da noi testati e mantenendo al contempo una ra- gionevole complessità computazionale.