Abstract

Triangulation consists in finding a 3D point repro jecting the best as possible onto corresponding image points. It is classical to min- imize the repro jection error, which, in the pinhole camera model case, is nonlinear in the 3D point coordinates. We study the triangulation of points lying on a 3D line, which is a typical problem for Structure-From- Motion in man-made environments. We show that the repro jection error can be minimized by finding the real roots of a polynomial in a single variable, which degree depends on the number of images. We use a set of transformations in 3D and in the images to make the degree of this polynomial as low as possible, and derive a practical reconstruction al- gorithm. Experimental comparisons with an algebraic approximation al- gorithm and minimization of the repro jection error using Gauss-Newton are reported for simulated and real data. Our algorithm finds the op- timal solution with high accuracy in all cases, showing that the poly- nomial equation is very stable. It only computes the roots correspond- ing to feasible points, and can thus deal with a very large number of views – triangulation from hundreds of views is performed in a few sec- onds. Reconstruction accuracy is shown to be greatly improved compared to standard triangulation methods that do not take the line constraint into account.