Large scale stereo reconstruction by a minimum s-t cut formulation

An important problem in computer vision is the reconstruction problem which consists in reconstructing a three dimensional surface on the base of different images of the surface. The classical formulations for solving this problem work with the so called ≪epipolar lines≫ that reduce the problem to one dimensional problems. Unfortunately they are an oversimplification of the reality and often yield solutions with limited quality. In 1998 a minimum s−t cut formulation of the reconstruction problem was proposed, that achieves in general more accurate results than the classical methods but is much more expensive in computational time and memory needs. Therefore, this new formulation is only of limited usability for large problems. In this master thesis we propose methods that allow to speed up this resolution tech- nique and to find accurate approximations by parallelizing the problem. Furthermore we introduce a formulation allowing to reduce locally the reconstruction region and to profit from preliminary knowledge of the surface by imposing border and internal con- ditions. Based on this formulation we introduce a pyramidal approach that allows to reduce the complexity of the problem and that can be combined with parallelization techniques. Most of the proposed methods and algorithms were implemented in C++ such that they can be applied to real problems.