SYSTEMS AND METHODS FOR VSLAM OPTIMIZATION

• US 20160154408A1
• Filed: 02/03/2016
• Published: 06/02/2016
• Est. Priority Date: 09/24/2010
• Status: Active Grant

• Current Assignee: iRobot Corporation
• Original Assignee: iRobot Corporation
• Inventors: Eade, Ethan, Munich, Mario E., Fong, Philip
• Granted Patent: US 9,910,444 B2
• Time in Patent Office: Days
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0253 extracting relative motion information from a plurality of images taken successively, e.g. visual odometry, optical flow determining position or orientation from images G06T7/70
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

The invention is related to methods and apparatus that use a visual sensor and dead reckoning sensors to process Simultaneous Localization and Mapping (SLAM). These techniques can be used in robot navigation. Advantageously, such visual techniques can be used to autonomously generate and update a map. Unlike with laser rangefinders, the visual techniques are economically practical in a wide range of applications and can be used in relatively dynamic environments, such as environments in which people move. Certain embodiments contemplate improvements to the front-end processing in a SLAM-based system. Particularly, certain of these embodiments contemplate a novel landmark matching process. Certain of these embodiments also contemplate a novel landmark creation process. Certain embodiments contemplate improvements to the back-end processing in a SLAM-based system. Particularly, certain of these embodiments contemplate algorithms for modifying the SLAM graph in real-time to achieve a more efficient structure.

Claims

1. A method for navigating a mobile system, the method implemented on one or more computer systems, comprising the steps of:

matching landmarks in a mobile device by;

retrieving features from a global database, wherein the global database comprises a plurality of landmarks and each landmark corresponds to a collection of 3-D features and corresponding 2-D features from which the 3-D features are computed;

ranking landmarks by visual similarity;

selecting a plurality of candidate landmarks;

for each of the plurality of candidate landmarks;

retrieving features in a local database, wherein the local database comprises a collection of 3-D features and corresponding 2-D features from which the 3-D features are computed for a specific landmark from the plurality of landmarks in the global database;

performing robust pose estimation;

performing bundle adjustment;

determine an observation pose and covariance;

selecting the best candidate as the matching landmark.

3. The method of claim 1, wherein the mobile system comprises a camera system that provides a stereoscopic view from which 3-D features of a landmark can be identified.

4. The method of claim 1, the method further comprising the steps of:

estimating course and distance traveled from a prior pose; and

using change in pose information to update one or more poses and maps maintained by a SLAM module within the mobile device.

5. The method of claim 4, wherein estimating course and distance traveled from a prior pose further comprises computing a relative pose of the mobile device with respect to one or more identified landmarks.

6. The method of claim 5, wherein computing a relative pose of the mobile device with respect to one or more identified landmarks further comprises finding a relative pose of the mobile device that minimizes projection error from 3-D features onto 2-D coordinates of a visible feature of the one or more landmarks.

7. The method of claim 1, wherein the method further comprises the steps of:

observing a new physical landmark; and

determining displacements from the mobile device to the features of a new physical landmark.

8. The method of claim 7, wherein determining displacements from the robot to the features of a new physical landmark further comprises using a current position of the mobile device reference frame as an initial estimate of a landmark reference frame.

9. The method of claim 7, wherein the method further comprises the step of storing a set of 3-D features and corresponding 2-D features that visually identify the new physical landmark in the global database.

10. The method of claim 9, wherein the 2-D features are selected from the group consisting of SIFT features, SURF features, and BRIEF features.

11. The method of claim 9, wherein storing a set of 3-D features and corresponding 2-D features that visually identify the new physical landmark in the global database further comprises:

retrieving a group of at least two images for analysis, where the images are selected based upon a baseline between the at least two images;

analyzing the group of at least two images to identify 2-D features that are common to the images in the group;

determining that there are enough features detected to reliably identify the landmark; and

computing 3-D local reference frame positions to the common 2-D features based upon observed disparity and the baseline between the at least two images.

12. The method of claim 11, wherein retrieving a group of at least two images for analysis, where the images are selected based upon a baseline between the two images comprises determining the baseline between the two images using dead reckoning.

13. The method of claim 11, wherein determining that there are enough features detected to reliably identify the landmark comprises detecting 10 or more features.

14. The method of claim 11, wherein computing 3-D local reference frame positions to the common 2-D features based upon observed disparity and the baseline between the at least two images further comprises solving a structure and motion problem using a trifocal tensor method.

15. The method of claim 11, wherein storing a set of 3-D features and corresponding 2-D features that visually identify the landmark in the global database further comprises identifying each feature of the new physical landmark within the global database using a Landmark ID and a Feature ID.

2. A method for navigating a mobile system, the method implemented on one or more computer systems, comprising the steps of:

creating landmarks in a mobile device by;

finding inlier matches by camera motion and epipolar geometry by selecting a temporally local image pair and establishing candidate correspondences, where a correspondence comprises a pair of matching features consisting of a feature in one image and a corresponding feature in the other image in the temporally local image pair;

refining camera motion using inlier matches;

determining if sufficient inliers exist;

determining if a tolerance has been reached;

adjusting a tolerance based on the determination that a tolerance has been reached; and

returning inliers and camera motion as a new landmark.

16. The method of claim 2, wherein selecting a temporally local image pair comprises selecting successive or nearly successive images captured by a single camera.

17. The method of claim 16, wherein:

finding inlier matches by camera motion and epipolar geometry further comprises;

determining if a differential estimate is available, where a differential estimate comprises a motion estimate of motion from one instant to the next; and

establishing candidate correspondences further comprises;

taking advantage of motion estimates.

18. The method of claim 2, wherein selecting a temporally local image pair comprises capturing a stereoscopic image pair.

19. The method of claim 2, wherein refining camera motion using inlier matches further comprises utilizing epipolar geometric constraints to iteratively eliminate outliers.

20. The method of claim 19, wherein utilizing epipolar geometric constraints to iteratively eliminate outliers further comprises projecting each feature in a frame A to its estimated epipolar line in a frame B using estimated camera motion.