A computer graphics program for navigation by stereovision

A fast algorithm for 3D surface reconstruction from stereovision data, namely stratified triangulation, is presented. The algorithm assumes a dense set of world points obtained from passive stereovision, and reconstructs a 3D scene. The stratification of random points follows a few heuristic rules. Triangles are formed only between strata, greatly limiting the search. The separation of surfaces is implemented by the standard region growing technique, from which road segments, obstacles, and other perceptual information can be derived. Some synthetic tests are shown to verify the algorithms. The envisaged application is autonomous navigation, e.g. of mobile robots