System and methods for feature selection and matching

• US 9,082,008 B2
• Filed: 12/03/2012
• Issued: 07/14/2015
• Est. Priority Date: 12/03/2012
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian, Mohr, Benjamin, Visker, Christopher Jon
• Primary Examiner(s): Lefkowitz, Sumati
• Assistant Examiner(s): Wang, Carol
• Application Number:
  US13/692,436
• Publication Number:
  US 20140153788A1
• Time in Patent Office: 953 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/3602 Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

Systems and methods for feature selection and matching are provided. In certain embodiments, a method for matching features comprises extracting a first plurality of features from current image data acquired from at least one sensor and extracting a second plurality of features from a prior map, wherein the prior map represents an environment containing the navigation system independently of data currently acquired by the at least one sensor. The method also comprises identifying at least one first feature in the first plurality of features and at least one second feature in the second plurality of features that have associated two-dimensional representations; and identifying at least one corresponding pair of features by comparing a three-dimensional representations of the at least one first feature to a three-dimensional representation of the at least one second feature.

Claims

1. A navigation system, the system comprising:

at least one sensor configured to acquire a three-dimensional representation of the environment containing the navigation system;

a memory unit configured to store executable instructions and a prior map of the environment, wherein the prior map represents the environment containing the navigation system independently of data currently acquired by the at least one sensor; and

a processing unit configured to execute the executable instructions, wherein the executable instructions direct the processing unit to;

extract a first plurality of features from current image data;

extract a second plurality of features from the prior map;

compare two-dimensional representations of the first plurality of features to two-dimensional representations of the second plurality of features to find at least one first feature in the first plurality of features that associate with at least one second feature in the second plurality of features; and

compare a three-dimensional representation of the at least one first feature to a three-dimensional representation of the at least one second feature to identify at least one corresponding pair of features.

2. The navigation system of claim 1, wherein the processing unit is further configured to:

divide the current image data into a plurality of image data segments;

divide the prior map into a plurality of map segments;

select an image data segment from the plurality of image data segments and a map segment from the plurality of map segments; and

extract the first plurality of features from the image data segment and the second plurality of features from the map segment.

3. The navigation system of claim 2, wherein the processing unit selects the image data segment and the map segment based on an estimated position of the navigation system within the environment.

4. The navigation system of claim 1, wherein the at least one first feature is a first set of features and the at least one second feature is a second set of features, wherein an image feature in the first set of features is associated with at least one map feature in the second set of features and the associated features are ordered according to a likelihood of corresponding to one another.

5. The navigation system of claim 1, wherein the prior map is a database storing terrain information of the environment.

6. The navigation system of claim 1, wherein the three-dimensional representation of the at least one first feature and the three-dimensional representation of the at least one second feature are three-dimensional histograms.

7. The navigation system of claim 6, wherein the three-dimensional histograms are centered on data associated with the location of a feature.

8. The navigation system of claim 6, wherein the three-dimensional histograms illustrate the position of a feature and neighboring environment along the surface of the terrain and the difference between the elevation of a surface of the feature and the surface of the neighboring environment.

9. The navigation system of claim 1, wherein features are extracted using at least one of:

a scale-invariant feature transform extraction method;

a speeded up robust features extraction method; and

a Kanade Lucas Tomasi feature extraction method.

10. The navigation system of claim 1, wherein two-dimensional representations of features are associated with one another according to feature identifiers calculated when the features were extracted.

11. The navigation system of claim 1, wherein the processing unit is further configured to identify a navigation solution for the navigation system based in part on the location of the features in the matched pair of features in relation to the navigation system.

12. A method for matching features, the method comprising:

extracting a first plurality of features from current image data acquired from at least one sensor;

extracting a second plurality of features from a prior map, wherein the prior map represents an environment containing the navigation system independently of data currently acquired by the at least one sensor;

identifying at least one first feature in the first plurality of features and at least one second feature in the second plurality of features that have associated two-dimensional representations;

and identifying at least one corresponding pair of features by comparing a three-dimensional representation of the at least one first feature to a three-dimensional representation of the at least one second feature.

13. The method of claim 12, further comprising:

determining the location of the at least one corresponding pair of features in relation to the location of the at least one image sensor; and

determining a navigation solution for a vehicle having the at least one sensor mounted thereon based in part on the location of the features in the corresponding pair of features in relation to the at least one image sensor; and

providing at least one of the navigation solution to a user through a human machine interface and commands based on the navigation solution to control the motion of a vehicle.

14. The method of claim 12, further comprising:

dividing the current image data into a plurality of image data segments;

dividing the prior map into a plurality of map segments;

selecting an image data segment from the plurality of image data segments and a map segment from the plurality of map segments; and

extracting the first plurality of features from the image data segment and the second plurality of features from the map segment.

15. The method of claim 12, wherein the at least one first feature is a first set of features and the at least one second feature is a second set of features, wherein an image features in the first set of features is associated with at least one map feature in the second set of features and the associated features are ordered according to a likelihood of corresponding to one another.

16. The method of claim 12, wherein the prior map is a database storing terrain information of the environment.

17. The method of claim 12, wherein the three-dimensional representation of the at least one first feature and the three-dimensional representation of the at least one second feature are three-dimensional histograms.

18. The method of claim 17, wherein the three-dimensional histograms are centered on data associated with the location of a feature.

19. A program product for identifying corresponding features, the program product comprising a plurality of instructions tangibly stored on a non-transitory storage medium, the instructions operable, when executed, to cause a processing unit to:

extract a first plurality of features from current image data acquired from at least one sensor configured to acquire a three-dimensional representation of an environment containing the at least one sensor;

extract a second plurality of features from a prior map of the environment, wherein the prior map represents the environment independently of data currently acquired by the at least one sensor;

identify at least one first feature in the first plurality of features and at least one second feature in the second plurality of features that have associated two-dimensional representations; and

identify at least one corresponding pair of features by comparing a three-dimensional histogram of the at least one first feature to a three-dimensional histogram of the at least one second feature.

20. The program product of claim 19, wherein the instruction are further operable to cause the processing unit to calculate a navigation solution for a vehicle having the at least one sensor mounted thereon, wherein the calculation is based in part on the location of the features in the at least one corresponding pair of features in relation to the vehicle.