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

• US 10,203,209 B2
• Filed: 05/25/2017
• Issued: 02/12/2019
• Est. Priority Date: 05/25/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.), Regents of The University of Minnesota (University of Minnesota)
• Original Assignee: Regents of The University of Minnesota (University of Minnesota)
• Inventors: Roumeliotis, Stergios I., Nerurkar, Esha D., Hesch, Joel, Guo, Chao, DuToit, Ryan C., Sartipi, Kourosh, Georgiou, Georgios
• Primary Examiner(s): Alharbi, Adam M
• Application Number:
  US15/605,448
• Publication Number:
  US 20170343356A1
• Time in Patent Office: 628 Days
• CPC Class Codes: G01C 21/1656 with passive imaging devices, e.g. cameras
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: H04W 4/026 using orientation information, e.g. compass
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information

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.

Claims

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 composite map into a plurality of regions; and

select 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 cooperative mapping server.

16. The vision-aided inertial navigation system of claim 15, wherein to select the equal number subset of the features, the cooperative mapping server is further configured to:

rank, within each of the regions, the features based on the number of VINS that commonly observed the feature; and

select, for each of the regions, the features that were commonly observed by the most number of the mobile devices until the number of features for inclusion within the subset has been selected.

17. The vision-aided inertial navigation system of claim 15, wherein to select the subset of the features for each of the region, the cooperative mapping server is further configured to:

project 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;

select the features for the subset from the projected features on the X-Y plane.

18. The vision-aided inertial navigation system of claim 11, wherein to generate the relative estimates, the cooperative mapping server is further configured to:

construct a tree in which each node represents a different one of the mobile devices and each link between pairs of nodes is assigned a weight representing the number of commonly observed features between the pair of mobile devices;

select, based on the weights of the links, a chain through the tree that links all of the nodes; and

determine the transformations only between pairs of the mobile devices that are neighboring nodes along the selected chain.

19. The vision-aided inertial navigation system of claim 11, wherein the cooperative mapping server is further configured to communicate the composite map to a mobile device for navigation within the environment.

20. The vision-aided inertial navigation system of claim 11, wherein the mobile devices comprise any of a tablet computer, a laptop computer, a mobile phone, a wearable computing device, a robot, a vehicle, or an unmanned aircraft system (UAS).

21. A non-transitory computer-readable medium comprising instructions that, when executed, cause one or more hardware-based processors of a computing platform to:

receive 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;

determine, 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

generate, based on the transformations, a composite map that specifies positions within the environment for the features observed by any of the VINS devices.