Trinocular Stereovision: Recent Results
Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Perception. Pages 826-827.
© 1987 International Joint Conferences on Artificial Intelligence
Abstract
We present an original approach to build rapidly and reliably a 30 description of the environment of a mobile robot by means of passive stereovision using three cameras. This technique has been successfuUy applied to many indoor scenes and has proved faster than a previously developed binocular stereo technique, while providing more reliable and more accurate results. Moreover, the algorithm is highly paraUelisable and has indeed been paralldized, thus highly increasing its speed. Results showing the construction of the 30 visual map of a complex indoor scene are included.
- JI J N. AYA CHE and B . FAVERJON . A fast stereo vision matcher based on pre- diction and rec ursive verification of hypotheses. In Proceeding• of'llaird Worbhop on Computer Vi.rion: Repreuntation and Control, pages 27-37, IEEE, october 1985 . Shorter version in CVPR '85, San Francisco, 1986 .
- J2J N. AYACHE and B. FAVERJON . Efficient registration of stereo images by matching graph descriptions of edge segments . lntem4fionaJ Jouma.l of computer Vi.oion, 1(2). april 1987 .
- J3J M. YACHIDA . 3d data acquisition by multiple views . In R obotic• Re~earch: the Thinl Jntem<JtiorwJ SJifflpo.oium, pages 11-18, MIT Press, Cambridge, Mass ., 1986. 141
- N . AYACHE and F. LUSTMAN . Fast and reliable passive trinocu lar stereovi- •iun . In Proc«~Jing• of / CC V '87, London, UK, IEEE, June 1987.
- JSJ O .D . FAUGERAS and G . TOSC ANI. The calibratio n pro blem fo r stereo . In Pro<.-.eoli"'J• C VPR '86, Miami Beach, Florida , pages 15-20, IEEE, 1986.
- J6J O .D . F'AUGERAS, F . LUSTMAN, and G . TOSCANI. Motion and structure from motion from point and line matches . In Proceeding• oflCCV '81, London, UK , IEEE , June 1987 .
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
St~reovision is a technique to build a three dimensional description of a ~cene observed from several viewpoints. It is quoted as passive if 110 adJitioual lighting of the scene, for instance by a laser beam, is re<Juiretl. So defined, passive stereovision happens to be very attractive fur many applications in robotics, including 30 object recognition and localizatiou as well as 30 uavigation of mobile robots.
Most of the research on passive stereovision has been devoted to biuucular vision for which two cameras ate observing the same scene from two slightly different viewpoints (see [1[ [2[ and included refer """~·) . Pre·ently, following Yachida [3[, an increasing number of stud ies are now concerned with trinocular vision in which a third camera is u·eJ to simplify the stereovision problem. Detailed referehces can be found in [4[ .
We introduce in this article an original method for trinocular stere ovision which has the following attractive features:
- Flexibility: it allows for arbitrary positions of three different cam eras. Calibration is obtained by a simple automatic procedure.
- Speed: 200 line segments (corresponding to approximatively 3000 image points) are matched in about 2s
- Reliability: typically less than 2 percent of the found matches are erroneous. Moreover noise or occluding boundaries which are often mismatched by conventional binocular systems, are reliably checked by trinocular systems, providing safer reconstruction re sults.
- Accuracy: the use of a third camera provides an additional mea surement which increases the reconstruction accuracy of each 30 segtnent.
The scheme of the method is the following:
- Preprocessing: a graph based description of a polygonal approx imation of the contours is extracted from each image and the image· are rectified so that the epipolar geometry, becoming sim pler, less computations are needed.
·Thll work was partially supported by Esprit Project P940
3 Calibration and Reprojection
Faug~ras and To~cani I5J have defined a calibration procedure through which the parameters of the perspectiv~ transformations attached to cadi cam~ra are automatically obtained by looking at a reference pat lena in a s~4uence of known positions. From the knowledge of these transformations, it is straightforward to compute the epipolar line of any point of a given retine onto another retina (see appendix of 121 for more ddails) .
Though very simple (6 multiplications and 4 additions), this com putation of the epipolar lines and the subsequent intersection compu tations that are needed during the matching phase are done so many times that it is a substantial saving in computational coot to have the simplest possible epipolar geometry: parallel epipolar lines, horisontal if possible. Thi.s can be obtained without lou of generality by re projecting the segments of each image onto a plane parallel to the plane containing the three optical centers. Figure 2 illustrates the principle of r~projection . In thi.s plane, we can furthermore choose the three co ordinate systems of the retinas: if we choose the coordinate systems of figur~ 3, the epipolar.line of point M(:z:0 , y11 ) is y = !In in image 2 and it is a horisontalline (though a little more difficult to compute) in image 3 (cf figure 3) . This simple transformation divided the computing time by a factor of 2.

4 Structuring the image
Another operation worth optin1ising is accessing the segments lying with in a giv~n region of the image and having a given orientation. We therefore compute buckets, i-e we superimpose a virtual grid composed of square windows on the image and compute, for each window, the li.st uf segments intersecting it . This structure is computed in linear time with respect to the number of segments. Moreover, at the expense of a uni4ue preliminary sorting of the segments orientations (done with algorithmic complexity O(nLogn)), buckets are actually filled with seg m~nts sorted by increasing orientation.
Accessing a segment in a given region of the image and having a certain orientation is then reduced to a dichotomy search in each bucket of the region.
5 Matching of homologous segments

Discussion of the constraints enforced on each segment feature and of the meaning of neighborhood, as well as a description of the valida tion procedure can be found in I4J .
6 Experimental results and discussion
Thi.s s~ereo-matching technique has been tested on a number of indoor scenes. We only present the following typical results.
Three images of a room are taken sinlUltaneously with our pre viously calibrated three camera s:.stem. Two triplets are shown in figures 5 and 6. From these 512x512 pixels images, edge points are ex tracted and chains of connected edge points are built and approximated by a set of linear segments, oriented with respect to the contrast sign across the segment . This preprocessing is independent of the stereo matching program, and we believe that it could be done in a fraction of a second on dedicated hardware.
The computing times are shown in the captions. To compare with point matching algorithms, a matched segment corresponds to an av erage of 15 matched points. These times do not include the validation phase: at the present time, this phase takes about the same time as the matching process but we have serious hopes to be able to shorten that time.
In general the number of errors is less than 2 percent of the total number of matches. Figures 5 and 6 show the stereo-matching results.
The algorithm i.s highly parallel: preprocessing can be done in dependently over each of the three images and the outer loop of the matching algorithm can be split in whatever number of processors we can get. We implement.ed the algorithm on a Sequent decaprocessor machine, so that we were able to split it straightforwardly over 9 pro cessors and divide the computing time almost by 9 with respect to the sequential version .

ca111era 2
~'igure 5: Triplet of the calibration grid, angular position 0 : about ti(){J segments per image, preprocessing 0.35s per image, 580 matched segment· in 6. 7s
~'inally, 30 segments are reconstructed using the technique developed in 161 to reconstruct a 30 line from its projections on several retinas. Figure 7 shows the view from above of the reconstructed room (ob tained from a panoramic view including figures 5 and 6, but notice the horizontal line correponding to the projection of the grid of figure 5 on the right-hand side of figure 7 and the room corner of figure 6 on the l~ft-hand side of figure 7).
@inproceedings{ijcai1987p172,
title = {Trinocular Stereovision: Recent Results},
author = {Ayache, Nicholas and Lustman, Francis},
booktitle = {Proceedings of the Tenth International Joint Conference on
Artificial Intelligence, {IJCAI-87}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John McDermott},
pages = {826--827},
year = {1987},
note = {Perception},
url = {https://ijcai.org/proceedings/1987/172},
}
TY - CPAPER TI - Trinocular Stereovision: Recent Results AU - Ayache, Nicholas AU - Lustman, Francis T2 - Proceedings of the Tenth International Joint Conference on Artificial Intelligence, IJCAI-87 PB - International Joint Conferences on Artificial Intelligence PY - 1987 SP - 826 EP - 827 UR - https://ijcai.org/proceedings/1987/172 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: