Robot Spatial Perception by Stereoscopic Vision and 3D Evidence Grids

Hans P. Moravec

September 1996


Very encouraging results have been obtained from a new program that derives a dense three-dimensional evidence grid representation of a robot's surroundings from wide-angle stereoscopic images. The pro gram adds several spatial rays of evidence to a grid for each of about 2,500 local image features chosen per stereo pair. It was used to construct a 256x256x64 grid, representing 6 by 6 by 2 meters, from a hand- collected test set of twenty stereo image pairs of an office scene. Fifty nine stereo pairs of an 8 by 8 meter laboratory were also processed. The positive (probably occupied) cells of the grids, viewed in perspec tive, resemble dollhouse scenes. Details as small as the curvature of chair armrests are discernible. The processing time, on a 100 MIPS Sparc 20, is less than five seconds per stereo pair, and total memory is under 16 megabytes. The results seem abundantly adequate for very reliable navigation of freely roaming mobile robots, and plausibly adequate for shape identification of objects bigger than 10 centimeters. The program is a first proof of concept, and awaits optimizations, enhancements, variations, extensions and applications.

Read the report

Or download printable 42 page tech report CMU-RI-TR-96-34
PDF format, 6MB
Gzipped postscript file, 7MB

3D Grid of Office Scene

A 3D EVIDENCE GRID OF AN OFFICE: Twenty stereo pairs of images were collected by hand of one end of an office, in parallel directions, from locations on an approximately 50 cm grid on the floor, with the cameras 1.25 meters high, angled 14 degrees down. The program Crayfish processed these into a 256 by 256 by 64 cell 3D evidence grid representing a 6 by 6 by 2 meter volume. The image is a 2D projection of the 90,000 "occupied" cells of this 4 million cell 3D grid. Much information is left out in this image, including the relative strengths of the occupied cells, all the contents of the 1.5 million "empty" and 2.5 million "unknown" cells, as well as an entire dimension of separation. Some depth cues are restored by "spotlighting" 3D volumes in distinctive colors. All the occupied cells in about a dozen box-shaped volumes have been given box-specific colors. One box colors the floor layers cy an. Each of the chairs is enclosed in a box of black color, the door frame is in a magenta box, the coat is encased in red, and so on. Occupied cells outside the major colored areas, probably the result of correlation errors, are colored yellow, and give the image a noisy background.

Office Scene


Gzipped Open Inventor files of the occupied cells of the evidence grids for the 6 meter by 6 meter office pictured above, and the 8 meter by 8 meter laboratory covered in the report's appendix. These files allow the grids to be examined interactively in 3D, using ivview on Silicon Graphics workstations, for instance.

An obstacle-avoiding path in the office grid generated by an A* program written by Martin Martin.

An HTML or plain text version of the report.

The Figures

The Programs
Image and data files for the office scene