Simultaneous localization and mapping using multiple view feature descriptors

• US 20050238200A1
• Filed: 12/22/2004
• Published: 10/27/2005
• Est. Priority Date: 04/27/2004
• Status: Active Grant

• Current Assignee: Honda Motor Company
• Original Assignee: Honda Motor Company
• Inventors: Gupta, Rakesh, Yang, Ming-Hsuan, Meltzer, Jason
• Granted Patent: US 7,831,094 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06F 18/21355 nonlinear criteria, e.g. embedding a manifold in a Euclidean space
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries
• 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/64 Three-dimensional objects
• CPC Class Codes: G06V 2201/11 Technique with transformation invariance effect

Abstract

Simultaneous localization and mapping (SLAM) utilizes multiple view feature descriptors to robustly determine location despite appearance changes that would stifle conventional systems. A SLAM algorithm generates a feature descriptor for a scene from different perspectives using kernel principal component analysis (KPCA). When the SLAM module subsequently receives a recognition image after a wide baseline change, it can refer to correspondences from the feature descriptor to continue map building and/or determine location. Appearance variations can result from, for example, a change in illumination, partial occlusion, a change in scale, a change in orientation, change in distance, warping, and the like. After an appearance variation, a structure-from-motion module uses feature descriptors to reorient itself and continue map building using an extended Kalman Filter. Through the use of a database of comprehensive feature descriptors, the SLAM module is also able to refine a position estimation despite appearance variations.

Claims

1. A method for wide baseline matching, comprising the steps of:

receiving a sequence of images wherein consecutive images have an incremental change;

generating a training feature descriptor, the training feature descriptor based on the incremental change;

creating a map of a scene captured by the sequence of images using the training feature descriptor and position information derived from the sequence of images;

receiving a recognition image containing an appearance variation relative to at least a last image from the sequence of images;

extracting a recognition feature descriptor from the recognition image;

matching the recognition feature descriptor to the training feature descriptor; and

determining a position within the map.

2. The method of claim 1, wherein said generating a training feature descriptor further comprises:

selecting a tracking feature from a plurality of tracking points derived from the sequence of images; and

matching the tracking points over the sequence of images.

3. The method of claim 2, wherein the step of selecting the tracking feature comprises:

selecting the tracking feature using an affine invariant tracker.

4. The method of claim 2, wherein the step of generating the training feature descriptor comprises:

building the training feature descriptor from the tracking feature using approximate Kernel Principal Component Analysis.

5. The method of claim 1, wherein the step of creating a map comprises:

generating a three-dimensional map using an extended Kalman Filter.

6. The method of claim 1, further comprising:

storing the training feature descriptor.

7. The method of claim 1, wherein the step of matching the recognition feature descriptor to the training feature descriptor comprises:

matching the recognition feature descriptor to the training feature descriptor through wide baseline correspondences.

8. The method of claim 1, wherein consecutive members of the sequence of images exhibit short-baseline viewpoint changes.

9. The method of claim 1, wherein the step of matching the recognition feature descriptor to the training feature descriptor comprises:

projecting the recognition feature descriptor onto the training feature descriptor;

determining a projection distance; and

determining whether the projection distance falls below a threshold.

10. The method of claim 1, further comprising:

estimating a current position based on an initial position and a distance traveled; and

adjusting said estimation for drift based on a difference between the training feature descriptor and the recognition feature descriptor.

11. The method of claim 1, wherein the appearance variation comprises at least one from the group containing:

a viewpoint variation, an illumination variation, a scale variation, a geometry variation and an occlusion.

12. The method of claim 1, further comprising the step of receiving an initial position.

13. The method of claim 1, further comprising the step of updating the map of the scene.

14. A method for simultaneous localization and mapping, comprising the steps of:

receiving a sequence of images wherein consecutive images have an incremental baseline change;

generating a training feature descriptor using an approximate Kernel Principal Analysis (KPCA), the training feature descriptor based on the baseline change;

creating a three-dimensional map of a scene captured by the sequence of images using an extended Kalman Filter, the training feature descriptor, and a position information derived from the sequence of images;

receiving a recognition image containing a wide baseline appearance variation relative to at least a last image from the sequence of images;

extracting a recognition feature descriptor from the recognition image;

matching the recognition descriptor to the training feature descriptor; and

determining a position within the map.

15. A system for wide baseline matching, comprising:

means for tracking within a sequence of images, wherein consecutive images have an incremental baseline change;

means for receiving a recognition image;

means for describing coupled to the means for tracking, the means for describing to generate a training feature descriptor based on the incremental baseline change;

means for matching coupled to the means for tracking, the means for matching to match a recognition feature descriptor to the training feature descriptor;

means for mapping a scene from the recognition image, coupled to the means for tracking and the means for matching, the means for mapping to create a map of a scene captured by the sequence of images, said map including the training feature descriptor and a position information derived from the sequence of images, and responsive to an appearance variation within the recognition image;

means for positioning, coupled to the means for mapping and the means for matching, the means for positioning to determine a position within the map, and responsive to the appearance variation within the recognition image.

16. The system of claim 15, wherein the means for tracking selects a tracking feature based on a plurality of tracking points from the sequence of images, and matches the tracking points among one or more of the sequence of images.

17. The system of claim 16, wherein the means for tracking selects the tracking feature using an affine invariant tracker.

18. The system of claim 15, wherein the means for describing generates the training feature descriptor with sparse data using approximate Kernel Principal Component Analysis.

19. The system of claim 15, wherein the mapping means generates a three-dimensional map with an extended Kalman Filter.

20. The system of claim 15, wherein the means for describing stores the training feature descriptor.

21. The system of claim 15, wherein the means for matching matches the recognition feature descriptor to the training feature descriptor through wide baseline correspondences.

22. The system of claim 15, wherein an image contains a short baseline viewpoint change with respect to a preceding image.

23. The system of claim 15, wherein the means for matching projects the recognition feature descriptor onto the training feature descriptor, determines a projection distance, and determines whether the projection distance falls below a threshold.

24. The system of claim 15, wherein the means for positioning estimates a current position based on an initial position and a distance traveled, and adjusts said estimate for drift based on a difference between the training feature descriptor and the recognition feature descriptor.

25. The system of claim 15, wherein the appearance variation comprises at least one from the group containing:

a viewpoint variation, an illumination variation, a scale variation, a geometry variation and an occlusion.

26. The system of claim 15, wherein the means for positioning receives an initial position.

27. A computer program product, comprising a computer-readable medium having computer program instructions and data embodied thereon for implementing a method for wide baseline matching, the method comprising the steps of:

receiving a sequence of images wherein consecutive images have an incremental change;

generating a training feature descriptor, the training feature descriptor based on the incremental change;

creating a map of a scene captured by the sequence of images using the training feature descriptor and position information derived from the sequence of images;

receiving a recognition image containing an appearance variation relative to at least a last image from the sequence of images;

extracting a recognition feature descriptor from the recognition image;

matching the recognition feature descriptor to the training feature descriptor; and

determining a position within the map.

28. The computer program product of claim 27, wherein said step of generating a training feature descriptor further comprises:

selecting a tracking feature from a plurality of tracking points derived from the sequence of images; and

matching the tracking points over the sequence of images.

29. The computer program product of claim 28, wherein the step of selecting the tracking feature comprises selecting the tracking feature using an affine invariant tracker.

30. The computer program product of claim 27, wherein the step of generating the training feature descriptor comprises:

building the training feature descriptor from the tracking feature descriptor using approximate Kernel Principal Component Analysis.

31. The computer program product of claim 27, wherein the step of creating a map comprises:

generating a three-dimensional map using an extended Kalman Filter.

32. The computer program product of claim 27, further comprising the step of storing the training feature descriptor.

33. The computer program product of claim 27, wherein the step of matching the recognition feature descriptor to the training feature descriptor comprises matching the recognition feature descriptor to the training feature descriptor through wide baseline correspondences.

34. The computer program product of claim 27, wherein consecutive members of the sequence of images exhibit short-baseline viewpoint changes.

35. The computer program product of claim 27, wherein the step of matching the recognition feature descriptor to the training feature descriptor comprises:

projecting the recognition feature descriptor onto the training feature descriptor;

determining a projection distance; and

determining whether the projection distance falls below a threshold.

36. The computer program product of claim 27, further comprising:

estimating a current position based on an initial position and a distance traveled; and

adjusting said estimate for motion drift based on a difference between the training feature descriptor and the recognition feature descriptor.

37. The computer program product of claim 27, wherein the appearance variation comprises at least one from the group containing:

a viewpoint variation, an illumination variation, a scale variation, a geometry variation, and an occlusion.

38. The computer program product of claim 27, further comprising the step of receiving an initial position.

39. The computer program product of claim 27, further comprising the step of updating the map of the scene.