Identifying true feature matches for vision based navigation

• US 8,447,116 B2
• Filed: 07/22/2011
• Issued: 05/21/2013
• Est. Priority Date: 07/22/2011
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Ma, Yunqian, Rao, Shrikant
• Primary Examiner(s): Seth, Manav
• Application Number:
  US13/188,836
• Publication Number:
  US 20130022233A1
• Time in Patent Office: 669 Days
• Field of Search: None
• US Class Current: 382/195
• CPC Class Codes: G01S 5/16 using electromagnetic waves other than radio waves
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters

Abstract

An example embodiment includes a method for identifying true feature matches from a plurality of candidate feature matches for vision based navigation. A weight for each of the plurality of candidate feature matches can be set. The method also includes iteratively performing for N iterations: calculating a fundamental matrix for the plurality of candidate feature matches using a weighted estimation that accounts for the weight of each of the plurality of candidate feature matches; calculating a distance from the fundamental matrix for each of the plurality of candidate feature matches; and updating the weight for each of the plurality of candidate feature matches as a function of the distance for the respective candidate feature match. After N iterations candidate feature matches having a distance less than a distance threshold can be selected as true feature matches.

Claims

1. A method for identifying true feature matches from a plurality of candidate feature matches for vision based navigation, the method comprising:

setting a weight for each of the plurality of candidate feature matches with a navigation system;

iteratively performing for N iterations with the navigation system;

calculating a fundamental matrix for the plurality of candidate feature matches using a weighted estimation that accounts for the weight of each of the plurality of candidate feature matches;

calculating a distance from the fundamental matrix for each of the plurality of candidate feature matches;

updating the weight for each of the plurality of candidate feature matches as a function of the distance for the respective candidate feature match; and

after N iterations selecting as true feature matches, candidate feature matches having a distance less than a distance threshold.

2. The method of claim 1, wherein setting a weight includes setting each weight the same.

3. The method of claim 2, wherein setting a weight includes initializing all weights to 1.

4. The method of claim 1, wherein N is within the range of 1 to 10.

5. The method of claim 1, wherein the weighted estimation includes a weighted least squares, geometric error minimization.

6. The method of claim 1, wherein calculating a distance includes calculating Sampson distance errors with respect to the fundamental matrix for each of the plurality of candidate feature matches.

7. The method of claim 1, wherein updating the weight includes using a robust loss function.

8. The method of claim 1, wherein updating the weight includes progressively reducing the weight of a candidate feature match based on where the distance falls with respect to a standard deviation of the set of distances.

9. The method of claim 8, wherein updating the weight includes reducing the weight of candidate feature matches having a distance greater than sigma, the standard deviation, and holding the weight of candidate feature matches having a distance less than sigma.

10. The method of claim 8, wherein updating the weight includes setting the weight for candidate feature matches having a distance greater than three sigma to zero.

11. The method of claim 1, wherein selecting includes discarding candidate feature matches having a distance error greater than the distance threshold for at the end of iteration N.

12. A device for provide navigation information, the device comprising:

one or more navigation sensors including at least one camera;

one or more processing devices coupled to the one or more navigation sensors;

one or more memory devices coupled to the one or more processing devices, the one or more memory devices including instructions which, when executed by the one or more processing devices cause the one or more processing devices to;

receive a frame from the at least one camera

extract a plurality of features from the frame;

identify a plurality of candidate feature matches between the plurality of features and features of another data set;

set a weight for each of the plurality of candidate feature matches;

iteratively perform for N iterations;

calculate a fundamental matrix for the plurality of candidate feature matches using a weighted estimation that accounts for the weight of each of the plurality of candidate feature matches;

calculate a distance with respect to the fundamental matrix for each of the plurality of candidate feature matches;

select a first distance threshold at an intermediate value in a set of the distances corresponding to the plurality of candidate feature matches;

select a second distance threshold at an intermediate value in a set of the distances corresponding to the plurality of candidate feature matches;

update the weight for each of the plurality of candidate feature matches as a function of the distance for a respective candidate feature match and the first distance threshold;

after N iterations select as true feature matches, candidate feature matches having a distance less than the second distance threshold for iteration N; and

calculate a navigation solution using the true feature matches.

13. The device of claim 12, wherein extract a plurality of features includes using a speed-up robust features (SURF) to extract features.

14. The device of claim 12, wherein identifying a plurality of candidate feature matches includes using one of the Mahalanobis or Euclidean distance between two features to identify a match, and wherein the other data set includes one of another frame or a map.

15. The device of claim 12, wherein calculate a navigation solution includes:

determining a navigation solution using one of visual odometry or simultaneous localization and mapping (SLAM).

16. The device of claim 12, wherein the first threshold value is one of a mean of the set of distances, a median of the set of distances, and sigma, a standard deviation, for the set of distances.

17. The device of claim 12, wherein N is within the range of 1 to 10.

18. The device of claim 12, wherein update weights includes reducing the weight of candidate feature matches having a distance greater than the first distance threshold, holding the weight of candidate feature matches having a distance less than the first distance threshold, and setting the weight for candidate feature matches having a distance greater than the second distance threshold to zero.

19. A non-transitory processor-readable medium including instructions which, when executed by a processor, cause the processor to:

set a weight for each of the plurality of candidate feature matches to a first value;

for N iterations;

calculate a fundamental matrix for the plurality of candidate feature matches using a weighted estimation that accounts for the weight of each of the plurality of candidate feature matches;

calculate a distance error with respect to the fundamental matrix for each of the plurality of candidate feature matches;

select a distance threshold at an intermediate value in a set of the distance errors corresponding to the plurality of candidate feature matches;

reduce the weight of candidate feature matches having a distance error greater than the distance threshold; and

after N iterations select as true feature matches, candidate feature matches having a distance error less than the distance threshold for iteration N.

20. The non-transitory processor-readable medium of claim 19, wherein for N iterations includes:

holding the weight of candidate feature matches having a distance error less than the distance threshold, and setting the weight for candidate feature matches having a distance error greater than three times the distance threshold to zero.