High resolution surface reconstruction from overlapping multiple-views
by Nader Salman and Mariette Yvinec from the Geometrica team-project in INRIA.
Three dimensional reconstruction of real world scenes from sequences of overlapping images is a topic of much interest in Computer Vision, Computer Graphics and Computational Geometry.
Its application areas range from preservation of historical heritage
to virtual reality walkthroughs through computer animation, movie production and e-commerce.
The challenge is to recover simplicial models of complex scenes from a set of images taken from various viewpoints around the scene.
The models sought after are either surface meshes or 3D meshes of objects in the scene.
The first step of the process consists of using a stereo algorithm
to extract a set of 3D points from the images.
To speed up the extraction phase,
the GYROVIZ project, produces sequences of located images
describing for each image, the position of the camera as well as the shooting parameters.
Most matchmoving softwares require highly coherent image sequences and generate sparse point clouds.
The software of [ENPC/Certis-CSTB/Mod-EVE] we use requires located frames and generates quasi dense point clouds.
In both cases the output of the image processing step is a set of tracks,
where each track is a 3D point associate to a list of images where the point is visible.
The set of images and tracks constitute the input of our reconstruction algorithm.
The extracted tracks are not perfect,
they include redundancies, outliers and noise.
First, some multiple tracks correspond to the same 3D feature point and must be merged.
As tracks are coming from characteristic points detected in the images,
their 3D locations should be densely spread over the surface of the scene objects.
Thus, we detect outliers by computing the average squared distance to the k-nearest neighbors for each track.
Another criterion is based upon the camera positions.
For each track P we compute the smallest cone with apex at P
that contains all cameras C that observed point P.
Tracks with small aperture cone angles are discarded.
The final preprocessing step is straightforward
as it smoothes the remaining tracks using a jet-fitting and reprojection algorithm.
At this stage the goal is to extract from the preprocessed tracks and the input images,
a set of higher level primitives conforming to the surface of the objects in the scene.
The final reconstruction sought after must respect the sharp creases of the scene.
To detect those edges we perform into the input images a simple contour extraction algorithm
based on Frei-Chen edge convolution masks.
We will use the detected contours to create in each image
a constrained Delaunay triangulation.
Let us first define the constraints.
In each image, we consider the projection of the tracks observed in this image,
and perform a classification of these tracks
depending on their proximity to the extracted contours.
We now consider the complete graph over all the contour tracks
and select the edges of this graph which lay over the detected contours.
At this stage the selected edges may not form a correct input for a constrained 2D triangulation.
To avoid collinear segments,
when two selected edges form a small angle we eliminate the longest one.
Now, to avoid intersections,
when two selected edges intersect we eliminate the longest one.
The remaining edges are used as input segments to
a 2D constrained Delaunay triangulation
with all projected tracks as vertices.
The triangles of this triangulation are then
lifted in 3D space using the 3D coordinates
computed by the stereo algorithm.
This process is repeated for each image.
The output is a 3D triangle soup in which the vast majority of the triangles correspond to the
actual surface regions in the scene.
However, at occlusion boundaries the present scheme may produce
triangles which connect foreground to background surfaces.
Two filtering steps are applied to the created triangle soup to
further enforce visibility consistency
and to remove erroneous triangles.
If a triangle belongs to the final surface then
it should not be intersected by any sight segment
joining a track 3D position to one of the cameras observing this track.
We now filter the big triangles;
where the longest edge is more than a given fraction of the bounding box.
Among these triangles we distinguish anamorphic and well-shaped triangles.
Anamorphic triangles
are likely to lie in free space and should be discarded.
Whereas well-shaped big triangles
may or not lie on the surface of the scene,
and are classified by measuring the cross correlation between images where they have been seen.
We generate the final scene surface by
computing the Delaunay triangulation of the tracks restricted to the triangle soup.
Outdoor scene example 1.
Outdoor scene example 2.