Robust homography estimation for image matching

An estimation of homography transformation between a pair of images is widely used in applications of computer vision, such as image mosaicing, image registration, augmented reality, visual metrology, 3D scene reconstruction. A homography is fitted to the set of point correspondences between the images that are found by image matching algorithms. Point correspondences are often corrupted by outliers, therefore the homography fitting problem requires the usage of robust estimation algorithms. The Random sample consensus (RANSAC) algorithm and its modifications are the most used robust estimators in computer vision. The RANSAC method has a lot of limitations, such as poor performance on data with the prevalence of outliers and the non-robustness to Gaussian noise. The Locally Optimized Random Sample Consensus (LO-RANSAC) method that is the RANSAC algorithm modification aims to improve the latter disadvantage by introducing the local optimization subroutine that refines the estimated model, in particular, mitigates the error induced by Gaussian noise. The problem of robust homography fitting can also be treated as a search for an underlying subspace that contains all inlier point correspondences. The Dual Principal Component Pursuit (DPCP), the robust subspace learning method that can be adapted for homography estimation task, has been recently proposed by Vidal and Tsakiris. It gains an increasing interest of the computer vision research community. In this thesis the robustness of DPCP method was analyzed, in particular: (i) the number of outliers the method can tolerate, (ii) the minimal number of inliers in the input data required for the method to succeed, (iii) the robustness to Gaussian noise. A comparative assessment of DPCP method performance has been conducted for problem formulations of different relative subspace dimensions. The results of the analysis showed that the performance of the DPCP method strongly depends on the properties of data distribution. Also, the minimal number of inliers in the data required for the method to succeed starts from 20. These findings limit the spectra of practical applications of the DPCP method for homography fitting tasks. However, the additional set of experiments has confirmed the theoretical results shown by authors of the method, namely that the DPCP algorithm is robust to mild levels of Gaussian noise added to the data. This could be considered as a useful advantage of the method in the context of homography estimation. Based on the observed properties of the DPCP method, in this thesis the modification of LO-RANSAC method is proposed, which uses the DPCP method as the primary estimator of the inlier number in the data. The performance of the proposed method has been analyzed in several experiments and compared with the performances of classical algorithms for robust homography estimation. The results of the experiments have shown that the proposed method succeeds to estimate the model for some images with wide baselines and high outliers/inliers ratios when the other methods fail. For the image pairs with relatively short baselines and the prevalence of inliers it demonstrates lower computational time with respect to some competitors and the lowest number of runs of local optimization procedure, while not losing in the estimation accuracy.

La stima di un'omografia tra una coppia di immagini è ampiamente utilizzata in applicazioni di computer vision, quali la mosaicatura di immagini, la registrazione tra viste, la realtà aumentata, la fotogrammetria e la ricostruzione della scena 3D. Un'omografia è stimata a partire dall'insieme di corrispondenze tra le immagini che sono trovate da algoritmi di matching. Le corrispondenze sono spesso contaminate da outlier, quindi la stima di un'omografia richiede l'uso di algoritmi robusti. L'algoritmo Random sample consensus (RANSAC) e le sue varianti sono gli stimatori robusti più usati nella computer vision. Il metodo RANSAC ha molte limitazioni, tra cui la scarsa prestazione su dati corrotti da outlier e la poca efficienza rispetto al rumore gaussiano. Il metodo Locally Optimized Random Sample Consensus (LO-RANSAC) migliora RANSAC introducendo una ottimizzazione locale che raffina il modello stimato, in particolare, attenuando l'errore indotto dal rumore gaussiano. Il problema della stima robusta di un'omografia può anche essere trattato come una ricerca di un sottospazio lineare che contiene tutte le corrispondenze degli inlier. Il Dual Principal Component Pursuit (DPCP), il metodo di recupero robusto del sottospazio che può essere adattato al compito di stima dell'omografia, è stato recentemente proposto da Vidal e Tsakiris. Nel lavoro di tesi analizziamo la robustezza del metodo DPCP, rispetto a (i) il numero di outlier che il metodo può tollerare, (ii) il numero minimo di inlier nei dati di input richiesto perché il metodo abbia successo, (iii) la robustezza al rumore gaussiano. Un confronto delle prestazioni del metodo DPCP è condotta per formulazioni di problemi di diverse dimensioni relative del sottospazio. I risultati dell'analisi hanno mostrato che la performance del metodo DPCP dipende fortemente dalla distribuzione dei dati. Inoltre, il numero minimo di inliers perché il metodo abbia successo è 20. Questi risultati limitano lo spettro delle applicazioni pratiche del metodo DPCP. Tuttavia, l'ulteriore serie di esperimenti ha confermato i risultati teorici mostrati dagli autori del metodo, cioè che l'algoritmo DPCP è robusto a lievi livelli di rumore gaussiano sui dati. Questo potrebbe essere considerato come un utile vantaggio del metodo nel contesto della stima dell'omografia. Sulla base di queste analisi, in questa tesi viene proposta una variante del metodo LO-RANSAC, che utilizza il metodo DPCP come stimatore primario del numero di inlier nei dati. Le prestazioni del metodo proposto sono state analizzate in diversi esperimenti e confrontate con le prestazioni degli algoritmi classici per la stima robusta dell'omografia. I risultati degli esperimenti hanno mostrato che il metodo proposto riesce a stimare il modello per alcune immagini con un'ampia baseline e alti rapporti outliers/inliers quando gli altri metodi falliscono. Per le coppie di immagini con baseline relativamente corte la variante proposta migliora il tempo di calcolo senze perdere nell'accuratezza della stima.