2 The 3D reconstruction algorithm

We consider the classical static stereo: from an image stereo pair and using a feature-based approach, common features in the two images are extracted. Then, using the information about the disparities of the features, we reconstruct the best approximation of the scene under study. The procedure is summarized in Figure 1. In detail, it is composed of the following steps:

Figure 1: Elementary steps in the reconstruction algorithm: (step 1) image acquisition, (step 2) feature extraction, (step 3) feature matching, (step 4) fundamental matrix and roto-translation parameters estimation, (step 5) rectification, (step 6) triangulation and polyhedrization.

• Input: from a set of images of a scene the user selects a stereo pair;
• Feature extraction: corners are identified in the images using the SUSAN extraction method [5];
• Feature matching: matching of corners is performed using an SSD (Sum of Squared Differences) algorithm; a set of corresponding features for the stereo pair is obtained;
• Fundamental matrix estimation: the fundamental matrix is estimated using the eight-point algorithm [12]; since this method is noise sensitive, an LMedS (Least Median of Squares) method [6] for robust estimation is employed to increase stability;
• Camera relative position: the two camera positions are related by a roto-translation in the 3D space; from the fundamental matrix the parameters of this roto-translation are estimated;
• Image rectification: from fundamental matrix and roto-translation parameters, the input stereo pair can be rectified using the procedure described in [7]. After this step, the epipolar lines in the rectified images are collinear, which simplifies the subsequent steps;
• Reconstruction of surface points: starting from the matched features that satisfy a confidence threshold, the 3D positions of the visible points of the stereo pairs are triangulated;
• Polyhedrization: using Delaunay triangulation the 3D space is decomposed into simple polyhedra;
• Identification of boundary surface: by creating a list of polyhedral faces and eliminating repeated faces, the exterior boundary of the objects is reconstructed;
• Texturing: textures are extracted from the images of the input stereo pair and applied to the external surface (polygons of the reconstructed 3D model);
• Export of the model: the final model is exported and encoded in VRML language.