SYSTEM AND METHOD FOR MERGING MAPS

• US 20180276863A1
• Filed: 03/22/2017
• Published: 09/27/2018
• Est. Priority Date: 03/22/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Nerurkar, Esha, Lynen, Simon, Zheng, Dongfang
• Granted Patent: US 10,937,214 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/20221 Image fusion; Image merging
• CPC Class Codes: G06T 3/14 Transformations for image registration, e.g. adjusting or mapping for alignment of images
• CPC Class Codes: G06T 7/337 involving reference images or patches

Abstract

An electronic device merges a plurality of maps, or area description files (ADFs), by representing relationships among ADFs in an undirected graph, with vertices representing maps and edges representing transformations between maps. As the electronic device generates new ADFs, the electronic device merges each new ADF to a stored collection of ADFs by adding each new ADF as a vertex and transformations between the new ADF and the collection of ADFs as edges in the undirected graph. In this way, the map merger can use the undirected graph to more accurately represent the relations between any two maps, allowing more efficient merger of new maps to a previously stored collection of maps, and allowing for the development of more flexible and efficient algorithms for manipulating the merged maps.

Claims

1. A method comprising:

representing a plurality of stored maps as vertices in an undirected graph, wherein each of the maps comprises descriptors based in part on measurements by visual and inertial sensors of a physical or virtual scene;

representing transformations between maps of the plurality of stored maps as edges in the undirected graph, wherein a transformation is computed from descriptors shared between maps;

receiving a first map comprising descriptors based in part on measurements by visual and inertial sensors; and

merging the first map to at least one map of the plurality of maps in response to determining that a first transformation can be computed from descriptors shared between the first map and the at least one map, wherein merging comprises representing the first map as a vertex and representing the first transformation as a first edge in the undirected graph; and

generating a display for location-based functionality based on the merged maps.

2. The method of claim 1, wherein determining that a first transformation can be computed from descriptors shared between the first map and the at least one map comprises receiving a transformation from the visual and inertial sensors.

3. The method of claim 1, wherein determining that a first transformation can be computed from descriptors shared between the first map and the at least one map comprises matching one or more descriptors of the first map to one or more descriptors of the at least one map.

4. The method of claim 1, further comprising:

building a co-optimization problem comprising the edges of the undirected graph; and

solving the co-optimization problem.

5. The method of claim 1, wherein the first map is received following a reset of the visual and inertial sensors.

6. The method of claim 1, wherein the first map is received from a source other than the visual and inertial sensors.

20. The method of claim 1, wherein the first received map is received from a source other than the visual and inertial sensors.

7. A method comprising:

storing a plurality of maps comprising descriptors based in part on measurements of images captured by visual and inertial sensors;

representing the maps as vertices in an undirected graph; and

merging a first map and a second map of the plurality of maps in response to determining that a transformation can be computed from descriptors shared between the first map and the second map, wherein merging comprises representing the transformation as a first edge connecting the vertices of the first map and the second map in the undirected graph; and

generating a display for location-based functionality based on the merged maps.

8. The method of claim 7, wherein determining that a transformation can be computed from descriptors shared between the first map and the second map comprises receiving a transformation between the first map and the second map from the visual and inertial sensors.

9. The method of claim 7, wherein determining that a transformation can be computed from descriptors shared between the first map and the second map comprises matching one or more descriptors of the first map to one or more descriptors of the second map.

10. The method of claim 7, further comprising:

receiving a third map comprising descriptors based in part on measurements from visual and inertial sensors; and

representing the third map as a vertex in the undirected graph;

merging the third map to at least one map of the plurality of maps in response to determining that a transformation can be computed from descriptors shared between the third map and the at least one map, wherein merging comprises representing the transformation between the third map and the at least one map as a second edge connecting the vertex of the third map to the vertex of the at least one map in the undirected graph.

11. The method of claim 10, further comprising:

building a co-optimization problem comprising the edges of the undirected graph; and

solving the co-optimization problem.

12. The method of claim 10, wherein determining that a transformation can be computed from descriptors shared between the third map and the at least one map comprises receiving a transformation between the third map and the at least one map from the visual and inertial sensors.

13. The method of claim 10, wherein determining that a transformation can be computed from descriptors shared between the third map and the at least one map comprises matching one or more descriptors of the third map to one or more descriptors of the at least one map.

14. The method of claim 10, wherein the third map is received following a reset of the visual and inertial sensors.

15. The method of claim 10, wherein the third map is received from a source other than the visual and inertial sensors.

16. A device comprising:

a storage component configured to store a plurality of maps comprising data representations of physical or virtual scene, wherein each map comprises descriptors based in part on measurements of images captured by visual and inertial sensors;

a multi-map module configured to represent the maps as vertices in an undirected graph and transformations between two or more maps as edges in the undirected graph, wherein the multi-map module is further configured to merge a first received map to at least one map of the plurality of maps in response to determining that a transformation can be computed from descriptors shared between the first received map and the at least one map, and wherein merging comprises representing the first received map as a vertex and the transformation that can be computed from descriptors shared between the first received map and the at least one map as a first edge in the undirected graph;

a processor configured to refine the transformation between the first received map and the at least one map by solving a co-optimization problem comprising the first edge of the undirected graph; and

a display for displaying location-based functionality based on the merged maps.

17. The device of claim 16, wherein the multi-map module is further configured to determine that a transformation can be computed from descriptors shared between the first received map and the at least one map in response to receiving a transformation between the first received map and the at least one map from the visual and inertial sensors.

18. The method of claim 16, wherein the multi-map module is further configured to determine that a transformation can be computed from descriptors shared between the first received map and the at least one map in response to matching one or more descriptors of the first received map to one or more descriptors of the at least one map.

19. The device of claim 16, wherein the first received map is received following a reset of the visual and inertial sensors.