click image to enlarge

1996-2002
3D Grid Maps from Stereo, Learning through Color

2D grid maps blur or omit much. Different locations appear similar and objects are overlooked. In 1992 we devised representational and coding optimizations giving about 100x speedup, making 3D grid experiments just possible. In 1996 we produced our first detailed 3D maps. The 1996 image shows occupied cells of a 3D grid map of a room made from 20 stereoscopic glimpses (it can be “walked through” on a 3D display. The odd colors were manually added for clarity, using virtual “spotlights.” Large images are 3D map views, small overlays are conventional camera snapshots.)

The 1996 results used a naive sensor model: it was impractical to hand-map even a small test area to guide learning as we had in 2D. In 1999 we invented a practical 3D learning criterion. Colors from the camera images of the real scene were correspondingly projected onto the occupied cells of a trial grid. A cell usually received colors from several directions, ideally all similar, from a surface patch at the corresponding location in the physical scene. Missing or extra grid cells spoil the correspondence and mix colors from different parts of the scene. Our learning chooses sensor models that make grids maximizing mean cell color uniformity. The process also gives an average color to each cell: the nice results, of the room and a lab, are shown in the 3D maps made in 2000 from the old data.

We diagnosed and overcame other limitations in the data and programs. Interior views of 3D maps made in 2002 from a stereoscopic hallway trip resemble virtual reality. An overhead view of the grid map shows its suitability for robot navigation. 1,000 MIPS allows a near-practical update per second.