Reconstruction with Interval Constraints Propagation

M. Farenzena, A. Fusiello and A. Dovier. Department of Computer Science
University of Verona, Verona - Italy

Overview

Interval Analysis and Constraint Logic Programming can be used to obtain an accurate geometric model of a scene that rigorously takes into account the propagation of data errors and roundoff. Image points are represented as small rectangles: as a result, the output of the n-views triangulation is not a single point in space, but a polyhedron that contains all the possible solutions. Interval Analysis is used to bound this polyhedron with a box. Geometrical constraints such as orthogonality, parallellism and coplanarity are subsequently enforced in order to reduce the size of these boxes, using Constraints Logic Programming.

Method

For each couple of images the interval-based triangulation is computed;
The interval-based reconstruction is achived by intersecting the results;
Geometric constraints are semiautomatically deduced and a pointwise solution is obtained by constraints propagation.

Experiments

Sequence

Points and
Constraints

Interval-based
reconstruction

After propagation

Textured

53	points
36	orthogonalities
34	parallellisms
4	coplanarities

Average side length of the 3D boxes: 10 cm

Average side length of the 3D boxes after propagation: 5 mm

33	points
16	orthogonalities
22	parallellisms
33	coplanarities

Average side length of the 3D boxes: 70 cm

Average side length of the 3D boxes after propagation: 10 cm

Code

Matlab code for interval-based triangulation is available here.
It is based on INTLAB, Matlab toolbox for self-validating algorithms, that can be downloaded from here

Reference Paper

A. M.Farenzena, A.Fusiello, A.Dovier. Reconstruction with Interval Constraints Propagation. Proceedings of Computer Vision and Pattern Recognition, New York, June 2006. (PDF)