Geometric matching in visual navigation systems

• US 9,965,689 B2
• Filed: 06/09/2016
• Issued: 05/08/2018
• Est. Priority Date: 06/09/2016
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: dos Santos Mendonca, Paulo Ricardo, Brunner, Christopher, Ramanandan, Arvind, Chari, Murali Ramaswamy, Ahuja, Dheeraj
• Primary Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US15/178,505
• Publication Number:
  US 20170357858A1
• Time in Patent Office: 698 Days
• Field of Search: 382104, 382153, 382190, 348 46, 348143, 348153, 348154, 701 2, 701 28
• CPC Class Codes: G01C 21/1652 with ranging devices, e.g. LIDAR or RADAR
• CPC Class Codes: G01C 21/1654 with electromagnetic compass
• CPC Class Codes: G01C 21/1656 with passive imaging devices, e.g. cameras
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/579 from motion
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle

Abstract

A first map comprising local features and 3D locations of the local features is generated, the local features comprising visible features in a current image and a corresponding set of covisible features. A second map comprising prior features and 3D locations of the prior features may be determined, where each prior feature: was first imaged at a time prior to the first imaging of any of the local features, and lies within a threshold distance of at least one local feature. A first subset comprising previously imaged local features in the first map and a corresponding second subset of the prior features in the second map is determined by comparing the first and second maps, where each local feature in the first subset corresponds to a distinct prior feature in the second subset. A transformation mapping a subset of local features to a subset of prior features is determined.

Claims

1. A processor-implemented method on a user equipment (UE) comprising a camera, the method comprising:

generating based, in part on an estimated camera pose for a current image frame, a first map comprising local features and 3D locations of the local features, wherein the local features comprise a plurality of visible features in the current image frame and a set of covisible features corresponding to the plurality of visible features, wherein, for each feature in the plurality of visible features, corresponding covisible features comprise a subset of the local features visible from prior camera poses from which the feature is also visible;

determining a second map comprising prior features and 3D locations corresponding to the prior features, wherein each prior feature was first imaged at a time prior to the first imaging of any of the local features, and wherein each prior feature is within a threshold distance of at least one local feature;

determining, based on a comparison of the first map to the second map, a first subset comprising previously imaged local features in the first map and a corresponding second subset of the prior features in the second map, wherein each local feature in the first subset corresponds to a distinct prior feature in the second subset; and

determining a transformation, wherein the transformation maps the first subset of the local features to the second subset of the prior features.

2. The method of claim 1, wherein determining the first subset and the corresponding second subset comprises:

determining that a first spatial arrangement associated with a plurality of the local features in the first map corresponds to a second spatial arrangement associated with a plurality of the prior features in the second map, wherein the plurality of the local features in the first map comprise the first subset and the plurality of the prior features in the second map comprise the second subset.

3. The method of claim 2, wherein:

the first spatial arrangement associated with the plurality of the local features in the first map is determined, based, in part, on the corresponding 3D locations of the plurality of the local features and the second spatial arrangement associated with the plurality of the prior features in the second map is determined, based, in part, on the corresponding 3D locations of the plurality of the prior features.

4. The method of claim 1, further comprising:

correcting the estimated camera pose based, in part, on the transformation to obtain a corrected camera pose.

5. The method of claim 4, further comprising:

updating the 3D locations of the local features in the first map based, in part, on the corrected camera pose.

6. The method of claim 4, wherein:

the first map comprises a first plurality of local feature descriptors, each local feature descriptor associated with a distinct local feature, and

the second map comprises a second plurality of prior feature descriptors, each prior feature descriptor associated with a distinct previously imaged feature; and

wherein,

the method further comprises;

comparing, for each local feature in the first subset, a corresponding local feature descriptor to a corresponding prior feature descriptor in the second subset; and

refining the corrected camera pose based, in part, on the comparison.

7. The method of claim 4, further comprising:

correcting an estimated trajectory of the UE based, in part, on the corrected camera pose.

8. The method of claim 1, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based using at least one of:

Random Sample Consensus (RANSAC), or

robust estimation, or

exhaustive search, or

Hough transforms.

9. The method of claim 1, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based on a translation or rigid motion model.

10. The method of claim 1, wherein determining the second map where each prior feature is within a threshold distance of the at least one feature in the first map comprises:

quantizing a 3D space being imaged by the UE into a plurality of quantization units, and

determining at least one quantization unit corresponding to the at least one local feature, and

identifying prior features located within the at least one quantization unit.

11. The method of claim 10, wherein:

the quantization units are cubes of equal cube size, wherein the cube size varies inversely relative to a map scale, wherein the map scale is associated with the first map and the second map.

12. The method of claim 1, wherein generating 3D locations corresponding to the local features comprises:

determining 3D locations corresponding to local features in the plurality of visible features based on the estimated camera pose; and

obtaining 3D locations corresponding to local features in the set of covisible features based on stored information for each of the covisible features.

13. A User Equipment (UE) comprising:

at least one image sensor capable of capturing images; and

a processor coupled to the image sensor, wherein the processor is configured to;

generate based, in part on an estimated camera pose for a current image frame, a first map comprising local features and 3D locations of the local features, wherein the local features comprise a plurality of visible features in the current image frame and a set of covisible features corresponding to the plurality of visible features, wherein, for each feature in the plurality of visible features, corresponding covisible features comprise a subset of the local features visible from prior camera poses from which the feature is also visible;

determine a second map comprising prior features and 3D locations corresponding to the prior features, wherein each prior feature was first imaged at a time prior to the first imaging of any of the local features, and wherein each prior feature is within a threshold distance of at least one local feature;

determine, based on a comparison of the first map to the second map, a first subset comprising previously imaged local features in the first map and a corresponding second subset of the prior features in the second map, wherein each local feature in the first subset corresponds to a distinct prior feature in the second subset;

determine a transformation, wherein the transformation maps the first subset of the local features to the second subset of the prior features.

14. The UE of claim 13, wherein to determine the first subset and the corresponding second subset, the processor is configured to:

determine that a first spatial arrangement associated with a plurality of the local features in the first map corresponds to a second spatial arrangement associated with a plurality of the prior features in the second map, wherein the plurality of the local features in the first map comprise the first subset and the plurality of the prior features in the second map comprise the second subset.

15. The UE of claim 14, wherein:

the first spatial arrangement associated with the plurality of the local features in the first map is determined, based, in part, on the corresponding 3D locations of the plurality of the local features and the second spatial arrangement associated with the plurality of the prior features in the second map is determined, based, in part, on the corresponding 3D locations of the plurality of the prior features.

16. The UE of claim 13, wherein the processor is further configured to:

correct the estimated camera pose based, in part, on the transformation to obtain a corrected camera pose.

17. The UE of claim 16, wherein the processor is further configured to:

update the 3D locations of the local features in the first map based, in part, on the corrected camera pose.

18. The UE of claim 16, wherein:

the first map comprises a first plurality of local feature descriptors, each local feature descriptor associated with a distinct local feature, and

the second map comprises a second plurality of prior feature descriptors, each prior feature descriptor associated with a distinct previously imaged feature; and

wherein,

the processor is further configured to;

compare, for each local feature in the first subset, a corresponding local feature descriptor to a corresponding prior feature descriptor in the second subset; and

refine the corrected camera pose based, in part, on the comparison.

19. The UE of claim 16, wherein the processor is further configured to:

correct an estimated trajectory of the UE based, in part, on the corrected camera pose.

20. The UE of claim 13, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based using at least one of:

Random Sample Consensus (RANSAC), or

robust estimation, or

exhaustive search, or

Hough transforms.

21. The UE of claim 13, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based on a translation or rigid motion model.

22. The UE of claim 13, wherein to determine the second map where each prior feature is within a threshold distance of the at least one feature in the first map, the processor is configured to:

quantize a 3D space being imaged by the UE into a plurality of quantization units, and

determine at least one quantization unit corresponding to the at least one local feature, and

identify prior features located within the at least one quantization unit.

23. The UE of claim 22, wherein:

the quantization units are cubes of equal cube size, wherein the cube size varies inversely relative to a map scale, wherein the map scale is associated with the first map and the second map.

24. The UE of claim 13, wherein to generate 3D locations corresponding to the local features, the processor is configured to:

determine 3D locations corresponding to local features in the plurality of visible features based on the estimated camera pose; and

obtain 3D locations corresponding to local features in the set of covisible features based on stored information for each of the covisible features.

25. An apparatus comprising:

image sensing means capable of capturing images;

means for generating based, in part on an estimated camera pose for a current image frame, a first map comprising local features and 3D locations of the local features, wherein the local features comprise a plurality of visible features in the current image frame and a set of covisible features corresponding to the plurality of visible features, wherein, for each feature in the plurality of visible features, corresponding covisible features comprise a subset of the local features visible from prior camera poses from which the feature is also visible;

means for determining a second map comprising prior features and 3D locations corresponding to the prior features, wherein each prior feature was first imaged at a time prior to the first imaging of any of the local features, and wherein each prior feature is within a threshold distance of at least one local feature;

means for determining, based on a comparison of the first map to the second map, a first subset comprising previously imaged local features in the first map and a corresponding second subset of the prior features in the second map, wherein each local feature in the first subset corresponds to a distinct prior feature in the second subset; and

means for determining a transformation, wherein the transformation maps the first subset of the local features to the second subset of the prior features.

26. The apparatus of claim 25, wherein means for determining the first subset and the corresponding second subset comprises:

means for determining that a first spatial arrangement associated with a plurality of the local features in the first map corresponds to a second spatial arrangement associated with a plurality of the prior features in the second map, wherein the plurality of the local features in the first map comprise the first subset and the plurality of the prior features in the second map comprise the second subset.

27. The apparatus of claim 25, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based using at least one of:

Random Sample Consensus (RANSAC), or

robust estimation, or

exhaustive search, or

Hough transforms.

28. A non-transitory computer readable medium comprising instructions, which when executed by a processor, cause the processor to:

generate based, in part on an estimated camera pose for a current image frame, a first map comprising local features and 3D locations of the local features, wherein the local features comprise a plurality of visible features in the current image frame and a set of covisible features corresponding to the plurality of visible features, wherein, for each feature in the plurality of visible features, corresponding covisible features comprise a subset of the local features visible from prior camera poses from which the feature is also visible;

determine a second map comprising prior features and 3D locations corresponding to the prior features, wherein each prior feature was first imaged at a time prior to the first imaging of any of the local features, and wherein each prior feature is within a threshold distance of at least one local feature;

determine, based on a comparison of the first map to the second map, a first subset comprising previously imaged local features in the first map and a corresponding second subset of the prior features in the second map, wherein each local feature in the first subset corresponds to a distinct prior feature in the second subset; and

determine a transformation, wherein the transformation maps the first subset of the local features to the second subset of the prior features.

29. The computer readable medium of claim 28, wherein the instructions to determine the first subset and the corresponding second subset, further cause the processor to:

determine that a first spatial arrangement associated with a plurality of the local features in the first map corresponds to a second spatial arrangement associated with a plurality of the prior features in the second map, wherein the plurality of the local features in the first map comprise the first subset and the plurality of the prior features in the second map comprise the second subset.

30. The computer readable medium of claim 28, wherein the transformation mapping the first subset of the local features to the second subset of the prior features is determined based using at least one of:

Random Sample Consensus (RANSAC), or

robust estimation, or

exhaustive search, or

Hough transforms.