Investigation of point triangulation methods for optimality and performance in Structure from Motion systems

Structure from Motion (SFM) systems are composed of cameras and structure in the form of 3D points and other features. It is most often that the structure components outnumber the cameras by a great margin. It is not uncommon to have a configuration with 3 cameras observing more than 500 3D points. Therefore fast 3D point triangulation algorithms are required in the different stages of a SFM system: at the initialization of the reconstruction during the primary estimation of the camera geometry, when new points from new cameras are being added to the system, etc.

This presentation will give an overview of existing triangulation methods with emphasis on performance versus optimality, and will suggest a fast triangulation algorithm based on linear constraints. The structure and camera motion estimation in a SFM system is based on the minimization of some norm of the reprojection error between the 3D points and their images in the cameras.

Most classical methods are based on minimizing the sum of squared errors, the L2 norm, after initializing the structure by an algebraic method ([2]). It has been shown (in [4] amongst others) that first, the algebraic method can produce initial estimates that are erroneous due to its minimization of a meaningless error measure and second, the L2 norm based function is not convex, and often gets stuck in local minima.