Granted Patent B2

US 12,392,628 · App. 16/917,803 · Granted Aug 19, 2025

Inventors: Luca Del Pero (London, GB); Karim Tarek Mahmoud Elsayed Ahmed Shaban (London, GB)

Assignee: Lyft, Inc.

G01C21/3635G01C21/32G01C21/3614G06F16/29G06V20/56

Abstract

Claims (61)

1. A computer-implemented method comprising:

generating a local map portion of a geographical environment based on sensor data captured by a device, wherein the sensor data comprises digital image data and the local map portion comprises local map structure data generated by processing the captured digital image data using a technique for determining structure from a first series of images within the captured digital image data, and wherein the local map structure data comprises (i) a first three-dimensional (3D) representation of the geographical environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) first sequential pose data associated with the first series of images that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images;

accessing existing map structure data of an existing map, wherein the existing map structure data is aligned to a global coordinate system and is predetermined from map structure data that was previously generated by processing previously-captured digital image data using a technique for determining structure from a second series of images within the previously-captured digital image data, and wherein the existing map structure data comprises (i) a second 3D representation of the geographic environment that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images and (ii) second sequential pose data associated with the second series of images that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying pose correlations between (i) poses included in the first sequential pose data that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) poses included in the second sequential pose data that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying feature correlations between (i) visible features included in the first 3D representation environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) visible features included in the second 3D representation that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

determining a transformation of the local map portion relative to the existing map based on the identified pose correlations and the identified feature correlations; and

determining a localization of the device within the global coordinate system by using the determined transformation to align the local map portion with the existing map.

2. The computer-implemented method of claim 1 , wherein using the determined transformation to align the local map structure data with the existing map comprises manipulating the local map structure data by one or more of (i) seven degrees of freedom, (ii) rotation, (iii) dilation, (iv) contraction (v) reflection, (vi) scaling, or (vii) shear mapping operations.

3. The computer-implemented method of claim 1 , further comprising:

determining a matching pair of images based on the identified feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation, wherein the matching pair of images comprises one image from the first series and one image from second series.

4. The computer-implemented method of claim 1 , wherein identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation comprises:

identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation using one or more of a visual feature matching technique or an edge detection technique.

5. The computer-implemented method of claim 1 , wherein identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation comprises:

detecting one or more two-dimensional (2D) visible features in each of the first series of images and each of the second series of images;

identifying feature correlations between 2D visible features detected in the first series of images and 2D visible features detected in the second series of images; and

using the identified feature correlations between the 2D visible features detected in the first series of images and 2D visible features detected in the second series of images as a basis for identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation.

6. The computer-implemented method of claim 1 , wherein determining the localization of the device within the global coordinate system comprises:

performing a pose comparison between the local map portion and the existing map.

7. The computer-implemented method of claim 1 , wherein the visible features included in the first 3D representation and the visible features included in the second 3D representation each comprise one or more of (i) a landmark, (ii) a building, (iii) a street furniture, (iv) a pedestrian sidewalk, (v) a curb, or (vi) a corner or an edge of a visible structure.

8. The computer-implemented method of claim 1 , wherein determining the transformation of the local map structure data relative to the existing map based on the identified pose correlations and the identified feature correlations further comprises:

determining the transformation by applying a constraint-based optimization process that uses the identified pose correlations as pose constraints.

9. The computer-implemented method of claim 1 , wherein the technique for determining structure from the first series of images within the digital image data and the technique for determining structure from the second series of images comprise structure from motion techniques.

10. The computer-implemented method of claim 1 , further comprising:

performing an initial localization within the global coordinate system to identify the existing map structure data of the existing map, wherein the initial localization comprises using satellite navigation.

11. The computer-implemented method of claim 1 , wherein using the determined transformation to align the local map portion with the existing map further comprises:

using the determined transformation to warp the local map portion in order to align it with the existing map.

12. The computer-implemented method of claim 1 , wherein identifying the pose correlations between the poses included in the first sequential pose data and the poses included in the second sequential pose data comprises:

based one or more of location similarities, directional similarities, or visual similarities, determining overlapping poses between (i) the first sequential pose data and (ii) the second sequential pose data.

13. A non-transitory computer-readable medium comprising program instructions stored thereon that, when executed by at least one processor of a computing system, cause the computing system to perform functions comprising:

generating a local map portion of a geographical environment based on sensor data captured by a device, wherein the sensor data comprises digital image data and the local map portion comprises local map structure data generated by processing the captured digital image data using a technique for determining structure from a first series of images within the captured digital image data, and wherein the local map structure data comprises (i) a first three-dimensional (3D) representation of the geographical environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) first sequential pose data associated with the first series of images that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images;

accessing existing map structure data of an existing map, wherein the existing map structure data is aligned to a global coordinate system and is predetermined from map structure data that was previously generated by processing previously-captured digital image data using a technique for determining structure from a second series of images within the previously-captured digital image data, and wherein the existing map structure data comprises (i) a second 3D representation of the geographic environment that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images and (ii) second sequential pose data associated with the second series of images that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying pose correlations between (i) poses included in the first sequential pose data that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) poses included in the second sequential pose data that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying feature correlations between (i) visible features included in the first 3D representation environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) visible features included in the second 3D representation that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

determining a transformation of the local map portion relative to the existing map based on the identified pose correlations and the identified feature correlations; and

determining a localization of the device within the global coordinate system by using the determined transformation to align the local map portion with the existing map.

14. The non-transitory computer-readable medium of claim 13 , further comprising program instructions stored thereon that, when executed by the at least one processor of the computing system, cause the computing system to perform a function of:

determining a matching pair of images based on the identified feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation, wherein the matching pair of images comprises one image from the first series and one image from second series.

15. The non-transitory computer-readable medium of claim 13 , wherein identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation comprises:

detecting one or more two-dimensional (2D) visible features in each of the first series of images and each of the second series of images;

identifying feature correlations between 2D visible features detected in the first series of images and 2D visible features detected in the second series of images; and

using the identified feature correlations between the 2D visible features detected in the first series of images and 2D visible features detected in the second series of images as a basis for identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation.

16. The non-transitory computer-readable medium of claim 13 , wherein determining the localization of the device within the global coordinate system comprises:

performing a pose comparison between the local map portion and the existing map.

17. A computing system comprising:

at least one processor;

a non-transitory computer-readable medium; and

program instructions stored on the non-transitory computer-readable medium that are executable by the at least one processor such that the computing system is configured to perform functions comprising:

generating a local map portion of a geographical environment based on sensor data captured by a device, wherein the sensor data comprises digital image data and the local map portion comprises local map structure data generated by processing the captured digital image data using a technique for determining structure from a first series of images within the captured digital image data, and wherein the local map structure data comprises (i) a first three-dimensional (3D) representation of the geographical environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) first sequential pose data associated with the first series of images that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images;

accessing existing map structure data of an existing map, wherein the existing map structure data is aligned to a global coordinate system and is predetermined from map structure data that was previously generated by processing previously-captured digital image data using a technique for determining structure from a second series of images within the previously-captured digital image data, and wherein the existing map structure data comprises (i) a second 3D representation of the geographic environment that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images and (ii) second sequential pose data associated with the second series of images that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying pose correlations between (i) poses included in the first sequential pose data that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) poses included in the second sequential pose data that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

identifying feature correlations between (i) visible features included in the first 3D representation environment that is generated during the processing of the captured digital image data using the technique for determining structure from the first series of images and (ii) visible features included in the second 3D representation that is generated during the processing of the previously-captured digital image data using the technique for determining structure from the second series of images;

determining a transformation of the local map portion relative to the existing map based on the identified pose correlations and the identified feature correlations; and

determining a localization of the device within the global coordinate system by using the determined transformation to align the local map portion with the existing map.

18. The computing system of claim 17 , further comprising program instructions stored on the non-transitory computer-readable medium that are executable by the at least one processor such that the computing system is configured to perform a function of:

determining a matching pair of images based on the identified feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation, wherein the matching pair of images comprises one image from the first series and one image from second series.

19. The computing system of claim 17 , wherein identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation comprises:

detecting one or more two-dimensional (2D) visible features in each of the first series of images and each of the second series of images;

identifying feature correlations between 2D visible features detected in the first series of images and 2D visible features detected in the second series of images; and

using the identified feature correlations between the 2D visible features detected in the first series of images and 2D visible features detected in the second series of images as a basis for identifying the feature correlations between the visible features included in the first 3D representation and the visible features included in the second 3D representation.

20. The computing system of claim 17 , further comprising program instructions stored on the non-transitory computer-readable medium that are executable by the at least one processor such that the computing system is configured to perform a function of:

performing an initial localization within the global coordinate system to identify the existing map structure data of the existing map, wherein the initial localization comprises using satellite navigation.

Assignments (2)

Continuity (1)

References Cited (17)