Mapping algorithm creates 3D maps in real time

Computer scientists at MIT and the National University of Ireland at Maynooth have developed a mapping algorithm that creates detailed 3D maps of indoor and outdoor environments in real time.

The researchers tested their algorithm on videos taken with a Kinect camera. Applying their mapping technique to these videos, the researchers said they created rich, three-dimensional maps as the camera explored its surroundings.

As the camera returned to its starting point, the researchers found that after returning to a location recognised as familiar, the algorithm was able to stitch images together to effectively “close the loop,” creating a continuous, realistic 3D map in real time.

The technique is said to solve ‘loop closure’ or ‘drift’; a situation that can occur when a camera in motion introduces slight errors in the estimated path taken.

A doorway may shift slightly to the right, or a wall may appear slightly taller than it is. Over relatively long distances, these errors can compound, resulting in a disjointed map, with walls and stairways that don’t exactly line up.

In contrast, the new mapping technique uses the researchers’ algorithm to track a camera’s position at any given moment along its route. As the Kinect camera takes images at 30 frames per second, the algorithm measures how much and in what direction the camera has moved between each frame. The algorithm simultaneously builds up a 3D model, consisting of small “cloud slices” – cross-sections of thousands of 3D points in the immediate environment. Each cloud slice is linked to a particular camera pose.

As a camera moves down a corridor, cloud slices are integrated into a global 3D map representing the larger, bird’s-eye perspective of the route so far.

The technique then takes all the camera poses that have been tracked and lines them up in places that look familiar. The technique automatically adjusts the associated cloud slices, along with their thousands of points, an approach that avoids having to determine, point by point, which to move.

‘Before the map has been corrected, it’s sort of all tangled up in itself,’ said Thomas Whelan, a PhD student at NUI. ‘We use knowledge of where the camera’s been to untangle it. The technique we developed allows you to shift the map, so it warps and bends into place.’

The technique, he said in a statement, may be used to guide robots through potentially hazardous or unknown environments. Whelan’s colleague John Leonard, a professor of mechanical engineering at MIT, also envisions a more benign application.

‘I have this dream of making a complete model of all of MIT,’ said Leonard, who is also affiliated with MIT’s Computer Science and Artificial Intelligence Laboratory. ‘With this 3D map, a potential applicant for the freshman class could sort of ‘swim’ through MIT like it’s a big aquarium. There’s still more work to do, but I think it’s doable.”

Leonard, Whelan and the other members of the team — Michael Kaess of MIT and John McDonald of NUI — will present their work at the 2013 International Conference on Intelligent Robots and Systems in Tokyo.