LEVERAGING CROWDSOURCED DATA FOR LOCALIZATION AND MAPPING WITHIN AN ENVIRONMENT

• US 20190355173A1
• Filed: 04/16/2019
• Published: 11/21/2019
• Est. Priority Date: 05/16/2018
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Gao, Jiang
• Granted Patent: US 11,127,203 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/50 Depth or shape recovery
• CPC Class Codes: G06T 7/74 involving reference images or patches

Abstract

Described is a system for leveraging crowd sourced data for mapping and navigation within a spatial environment. The system may merge various map fragments received from multiple devices to create a global 3D point cloud map. The system may also provide the ability to identify real-world virtual landmarks in an environment and associate these virtual coordinates with locations within the 3D point cloud map. These virtual landmarks may then be used to reference and index objects detected within the environment. Accordingly, these virtual landmarks and objects may then be used for mapping and navigation. For example, the objects may be referenced by various devices in real time for re-localization, and the virtual landmarks maybe used by various devices to triangulate accurate positions. Accordingly, described is an efficient mechanism for leveraging crowd sourced data to improve navigation within a spatial environment.

Claims

1. A method comprising:

receiving, by a computing system, a first input signal captured by a first device navigating an environment and a second input signal captured by a second device navigating the environment;

generating, by the computing system, a first three-dimensional (3D) point cloud map from the first input signal and a second three-dimensional (3D) point cloud map from the second input signal;

determining, by the computing system, the first 3D point cloud map overlaps with the second 3D point cloud map; and

merging, by the computing system, the first 3D point cloud map with the second 3D point cloud map in response to determining the first 3D point cloud map overlaps with the second 3D point cloud map.

2. The method of claim 1, further comprising:

calibrating the first device to align the first 3D point cloud map with the environment by performing one or more movements of the first device along one or more axes within a three- dimensional space.

3. The method of claim 1, wherein generating the first 3D point cloud map and the second 3D point cloud map includes generating at least portions of the first 3D point cloud map and the second 3D point cloud map simultaneously.

4. The method of claim 1, wherein determining the first 3D point cloud map overlaps with the second 3D point cloud map includes:

detecting a first set of key frames within the first input signal matches a second set of key frames within the second input signal as part of a loop detection process that executes during the generation of the first 3D point cloud map and the second 3D point cloud map.

5. The method of claim 4, wherein merging the first 3D point cloud map with the second 3D point cloud map includes:

merging a first portion of the first 3D point cloud map with a second portion of the second 3D point cloud map based on position information associated with the first set of key frames and the second set of key frames.

6. The method of claim 1, further comprising:

identifying a location captured by the first device within the environment as a virtual landmark; and

associating a physical location in the environment with a location within the first 3D point cloud map for the virtual landmark.

7. The method of claim 6, further comprising;

localizing the first device using a triangulation calculation including at least the virtual landmark.

8. The method of claim 6, further comprising:

identifying an object captured by the first device within the environment; and

indexing the object based on a position relative to the virtual landmark.

9. The method of claim 1, further comprising:

associating the first 3D point cloud map with the environment by associating a physical location of the environment with a location within the 3D point cloud map to create a virtual coordinate.

10. The method of claim 9, wherein associating the physical location of the environment with the 3D point cloud location includes:

receiving, from a user interface associated with the first device, a user input specifying the location when the user touches on the user interface.

11. The method of claim 1, further comprising:

receiving a request for a 3D point cloud map from a third device; and

providing the merged 3D point cloud map to the third device in response to determining a device identifier of the third device is associated with the merged 3D point cloud map.

12. The method of claim 1, further comprising:

receiving, from the first device, information specifying a first navigation waypoint for the first device; and

sharing, with a third device, the first navigation waypoint as part of providing the merged 3D point cloud map to the third device.

13. A computer program product, comprising a non-transitory computer-readable medium having computer-readable program code embodied therein to be executed by one or more processors, the program code including instructions to:

receive a first input signal captured by a first device navigating an environment and a second input signal captured by a second device navigating the environment;

generate a first three-dimensional (3D) point cloud map from the first input signal and a second three-dimensional (3D) point cloud map from the second input signal;

determine the first 3D point cloud map overlaps with the second 3D point cloud map; and

merge the first 3D point cloud map with the second 3D point cloud map in response to determining the first 3D point cloud map overlaps with the second 3D point cloud map.

14. The computer program product of claim 13, the program code including further instructions to:

identify a location captured by the first device within the environment as a virtual landmark; and

associate a physical location in the environment with a location within the first 3D point cloud map for the virtual landmark.

15. The computer program product of claim 14, the program code including further instructions to:

localize the first device using a triangulation calculation including at least the virtual landmark.

16. The computer program product of claim 13, the program code including further instructions to:

identify an object captured by the first device within the environment; and

index the object based on a position relative to the virtual landmark.

17. The computer program product of claim 16, the program code including further instructions to:

receive, from a user interface associated with the first device, a user input specifying the location when the user touches on the user interface.

18. A system comprising:

one or more processors; and

a non-transitory processor-readable medium storing a plurality of instructions, which when executed, cause the one or more processors to;

receive a first input signal captured by a first device navigating an environment and a second input signal captured by a second device navigating the environment;

generate a first three-dimensional (3D) point cloud map from the first input signal and a second three-dimensional (3D) point cloud map from the second input signal;

determine the first 3D point cloud map overlaps with the second 3D point cloud map; and

merge the first 3D point cloud map with the second 3D point cloud map in response to determining the first 3D point cloud map overlaps with the second 3D point cloud map.

19. The system of claim 18, the plurality of instructions, when executed, further cause the one or more processors to:

identify a location captured by the first device within the environment as a virtual landmark; and

associate a physical location in an environment with a location within the first 3D point cloud map for the virtual landmark.

20. The system of claim 19, the plurality of instructions, when executed, further cause the one or more processors to:

identify an object captured by the first device within the environment; and

index the object based on a position relative to the virtual landmark.