M.Sc Thesis

M.Sc StudentOkun Uri
SubjectImage Registration by Probabilistic Multi-Assignment Graph
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Israel Cohen
Full Thesis textFull thesis text - English Version


Image registration is a fundamental task to many computer vision applications, such as object recognition, mapping, scene reconstruction, autonomous navigation and many more. The common general methodology for image registration can be outlined as a two stage process: In the first, features of interest are detected in both images, and in the second, those features are matched using geometrical and appearance related cues. In this thesis we address the matching stage, with particular concern to the wide-baseline stereo case.

In recent years two distinct paradigms for conducting the matching stage have evolved in parallel. One robustly estimates the pinhole perspective epipolar constraint over the set of the putative correspondences while pruning non-compliant features, and the other uses graph matching in order to find a consistent set in an affinity graph representing feature-groups' geometrical-consistency. Both matching paradigms suffer from performance degradation when facing wide-baseline scenarios: Epipolar robust estimation starts failing as inlier rate decreases due to local appearance deformations, and graph-based matching is inadequate to deal with complex or discontinuous transformations, which are often formed in wide-baseline stereo scenarios.

We propose MAGMA (Multi-Assignment Graph Matching Algorithm), a unified probabilistic image matching approach that utilizes both piecewise graph matching and epipolar-geometry-based constraints. The suggested approach takes advantage of the graph matching strength of rigid robust cluster matching, without giving up the flexibility of complex perspective transformation. This is done by first extending the applicability of the graph matching approach to wide-baseline stereo matching, by relaxing the demand for one global consistent component and replacing it with the more adequate model of several local components, each with its own geometric consistent transformation. We derive a new optimization scheme for solving the multiple-assignment problem in a probabilistic way, via factorizing the affinity graph using a stochastic semi-normalized constrained factorization (SCMF), which can be seen as a special case of nonnegative matrix factorization (NMF). Next, we propose using the epipolar prior information as a global constraint binding these components together, and improving the robustness to outliers and noise. Finally, we combine the two steps in a probabilistic formulation to derive a stable, fast-converging iterative process.

Our approach is comprehensively verified by applying it to simulated data in various challenging setups, as well as real image sequences. MAGMA is shown to compare favorably with contemporary state-of-the-art algorithms, and outperform them in many cases.