Resource-aware large-scale cooperative 3D mapping using multiple mobile devices

Patent metadata

Field	Value
Publication number	US-10203209-B2
Application number	US-201715605448-A
Country	US
Kind code	B2
Filing date	May 25, 2017
Priority date	May 25, 2016
Publication date	Feb 12, 2019
Grant date	Feb 12, 2019

Abstract

A method includes: receiving, with a computing platform, respective trajectory data and map data independently generated by each of a plurality of vision-aided inertial navigation devices (VINS devices) traversing an environment, wherein the trajectory data specifies poses along a path through the environment for the respective VINS device and the map data specifies positions of observed features within the environment as determined by an estimator executed by the respective VINS device; determining, with the computing platform and based on the respective trajectory data and map data from each of the VINS devices, estimates for relative poses within the environment by determining transformations that geometrically relate the trajectory data and the map data between one or more pairs of the VINS devices; and generating, with the computing platform and based on the transformations, a composite map specifying positions within the environment for the features observed by the VINS devices.

First claim

What is claimed is:

1. A method comprising:
receiving, with a computing platform having one or more hardware-based processors, respective trajectory data and map data independently generated by each of a plurality of vision-aided inertial navigation devices (VINS devices) traversing an environment, wherein the trajectory data specifies poses along a path through the environment for the respective VINS device and the map data specifies positions of observed features within the environment as determined by an estimator executed by the respective VINS device;
determining, with the computing platform and based on the respective trajectory data and map data from each of the VINS devices, estimates for relative poses within the environment by determining transformations that geometrically relate the trajectory data and the map data between one or more pairs of the VINS devices; and
generating, with the computing platform and based on the transformations, a composite map that specifies positions within the environment for the features observed by any of the VINS devices.

2. The method of claim 1 , further comprising:
identifying features that are commonly observed by two or more of the VINS devices;
for each of the commonly observed features, determining, with the computing platform, a geometric constraint that imposes geometric consistency for the feature based on the map data from each of the two or more VINS devices that observed the feature; and
generating composite maps based on the transformations geometrically relating the map data received from the plurality of VINS devices and by imposing the geometric constraints computed from the commonly observed features.

3. The method of claim 2 , further comprising selecting, based on computing resources available within the computing platform, only a subset of the commonly observed features for which to compute respective geometric constraints to be applied when generating the composite map.

4. The method of claim 3 , wherein, while generating the composite map, excluding computation of respective geometric constraints for any unselected commonly observed features and instead treating any unselected commonly observed feature as different features within the map data for the two or more VINS that observed the feature.

5. The method of claim 3 , wherein selecting only the subset of the commonly observed features for which to compute the respective geometric constraints further comprises:
partitioning the composite map into a plurality of regions; and
selecting an equal number subset of the features within each of the regions, wherein the number of features for inclusion in the subsets is determined based on the computing resources within the computing platform.

6. The method of claim 5 , wherein selecting the equal number subset of the features comprises:
ranking, within each of the regions, the features based on the number of VINS that commonly observed the feature; and
selecting, for each of the regions, the features that were commonly observed by the most number of the VINS devices until the number of features for inclusion within the subset has been selected.

7. The method of claim 5 , wherein selecting the subset of the features for each of the regions comprises:
projecting each of the features within the respective region onto a two dimensional X-Y plane for that region such that features within the region having the same X-Y positions are combined on the X-Y plane;
selecting the features for the subset from the projected features on the X-Y plane.

8. The method of claim 1 , wherein generating the relative estimates further comprises:
constructing a tree in which each node represents a different one of the VINS devices and each link between pairs of nodes is assigned a weight representing the number of commonly observed features between the pair of VINS devices;
selecting, based on the weights of the links, a chain through the tree that links all of the nodes; and
determining the transformations only between pairs of the VINS devices that are neighboring nodes along the selected chain.

9. The method of claim 1 , further comprising communicating the composite map to a VINS device for navigation within the environment.

10. The method of claim 1 ,
wherein the features represent objects visible within the environment, and
wherein the vision-aided inertial navigation system is integrated within a tablet computer, a laptop computer, a mobile phone, a wearable computing device, a robot, a vehicle, or an unmanned aircraft system (UAS).

11. A vision-aided inertial navigation system comprising:
a plurality of mobile devices, each of the mobile devices comprising:
at least one image source to produce image data along a trajectory of the mobile device within an environment, wherein the image data contains a plurality of features observed within the environment at a plurality of poses of the mobile device along the trajectory;
an inertial measurement unit (IMU) to produce IMU data indicative of motion of the vision-aided inertial navigation system; and
a hardware-based processing unit comprising an estimator that determines, based on the image data and the IMU data, trajectory data specifying a position and orientation of the mobile device for a plurality of poses of the mobile device along the trajectory and map data specifying positions with the environment for features observed from the poses; and
a cooperative mapping server configured to:
receive respective trajectory data and map data independently generated by each of mobile devices;
determine transformations that geometrically relate the trajectory data and the map data between one or more pairs of the mobile devices; and
generating, with the computing platform and based on the transformations, a composite map that specifies positions within the environment for the features observed by any of the mobile devices.

12. The vision-aided inertial navigation system of claim 11 , wherein the cooperative mapping server is further configured to:
identify features that are commonly observed by two or more of the mobile devices;
for each of the commonly observed features, determine a geometric constraint that imposes geometric consistency for the feature based on the map data from each of the two or more mobile devices that observed the feature; and
generate composite maps based on the transformations geometrically relating the map data received from the plurality of mobile devices and by imposing the geometric constraints computed from the commonly observed features.

13. The vision-aided inertial navigation system of claim 12 , wherein the cooperative mapping server is further configured to select, based on computing resources available within the cooperative mapping serve, only a subset of the commonly observed features for which to compute respective geometric constraints to be applied when generating the composite map.

14. The vision-aided inertial navigation system of claim 13 , wherein, while generating the composite map, the cooperative mapping server is further configured to exclude computation of respective geometric constraints for any unselected commonly observed features and instead treat any unselected commonly observed feature as different features within the map data for the two or more mobile devices that observed the feature.

15. The vision-aided inertial navigation system of claim 13 , wherein, to select only the subset of the commonly observed features for which to compute the respective geometric constraints, the cooperative mapping server is further configured to:
partition the c

Assignees

• Univ Minnesota
• Google Llc

Inventors

• Roumeliotis Stergios I
• Nerurkar Esha D
• Hesch Joel
• Guo Chao
• Dutoit Ryan C
• Sartipi Kourosh
• Georgiou Georgios

Classifications

• G06T19/003

  Navigation within 3D models or images · CPC title

• H04W4/026

  using orientation information, e.g. compass · CPC title

• G01C21/165 Primary

  combined with non-inertial navigation instruments · CPC title

• G06T7/00

  Image analysis · CPC title

• G01C21/32

  Structuring or formatting of map data · CPC title