Systems and methods for determining whether to add a landmark for visual simultaneous localization and mapping

• US 8,095,336 B2
• Filed: 07/20/2010
• Issued: 01/10/2012
• Est. Priority Date: 12/17/2002
• Status: Expired due to Term

• Current Assignee: iRobot Corporation
• Original Assignee: Evolution Robotics Inc. (iRobot Corporation)
• Inventors: Goncalves, Luis Filipe Domingues, Di Bernardo, Enrico, Pirjanian, Paolo, Karlsson, L. Niklas
• Primary Examiner(s): WACHSMAN, HAL D
• Application Number:
  US12/839,821
• Publication Number:
  US 20100284621A1
• Time in Patent Office: 539 Days
• Field of Search: 702/150, 702152-153, 702/155, 702158-160, 701/23, 701 25- 26, 701/28, 701207-211, 701/217, 348/119, 348/135, 348/137, 348/139, 348/142
• US Class Current: 702/152
• CPC Class Codes: G01C 21/12 executed aboard the object being navigated; Dead reckoning
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05D 1/0231 using optical position detecting means position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0248 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0278 using satellite positioning signals, e.g. GPS
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: Y10S 901/01 Mobile robot
• CPC Class Codes: Y10S 901/46 Sensing device
• CPC Class Codes: Y10S 901/47 Optical
• CPC Class Codes: Y10S 901/50 Miscellaneous

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. Such visual techniques can be used to autonomously generate and update a map. Unlike with laser rangefinders, the visual techniques are practical in a wide range of applications and can be used in relatively dynamic environments, such as environments in which people move. One embodiment further uses multiple particles to maintain multiple hypotheses with respect to localization and mapping. One embodiment maintains the particles, thereby permitting the SLAM processes to be performed in software using microprocessor-based computer systems.

Claims

1. A method of determining whether to add a landmark to a map for navigation, the method comprising:

autonomously navigating a mobile device using the map, and while navigating the mobile device, performing the following;

retrieving an image from a visual sensor;

comparing features from the image to a plurality of stored features;

generating a list of matching landmarks from the comparison;

filtering matching landmarks from the list based on reliability tests;

proceeding to a landmark creation process when there are no remaining matching landmarks in the list; and

providing match results to a simultaneous localization and mapping process for navigation of the mobile device when at least one matching landmark remains in the list;

wherein navigating, retrieving, comparing, generating, filtering, and proceeding are performed under the control of electronic hardware.

2. The method as defined in claim 1, wherein the visual sensor is coupled to a mobile robot.

3. The method as defined in claim 1, wherein filtering matching landmarks further comprises:

comparing the number of features common to the image and to a landmark to a predetermined number; and

filtering the landmark from the list when the number of common features for the landmark is below the predetermined number.

4. The method as defined in claim 1, wherein filtering matching landmarks further comprises:

initiating a computation of a camera pose from a subset of features from the image and corresponding matching features from the landmark; and

filtering the landmark from the list upon a failure of the computation to converge to a result.

5. The method as defined in claim 1:

wherein landmark poses associated with landmarks correspond to a pose of the mobile device when the landmark is created or updated when a previously created landmark is re-observed;

wherein an initial estimate of a landmark pose of a newly created landmark corresponds to a global robot pose from when the landmark was created.

6. The method as defined in claim 1, wherein at least one reliability test of the reliability tests comprises an evaluation of a root mean square (RMS) projection error corresponding to a computed relative pose of the mobile device with respect to a landmark pose associated with the landmark.

7. An apparatus comprising:

a computer program embodied in a tangible non-transitory computer-readable medium for determining whether to add a landmark to a map for navigation, the computer program comprising;

program instructions configured to navigate a mobile device using the map;

program instructions configured to retrieve an image from a visual sensor;

program instructions configured to compare features from the image to a plurality of stored features;

program instructions configured to generate a list of matching landmarks from the comparison;

program instructions configured to filter matching landmarks from the list based on reliability tests;

program instructions configured to proceed to a landmark creation process when there are no remaining matching landmarks in the list; and

program instructions configured to provide match results to a simultaneous localization and mapping process for navigation of the mobile device when at least one matching landmark remains in the list and

a processor configured to execute the program instructions of the computer program.

8. The apparatus as defined in claim 7, wherein the visual sensor is coupled to a mobile robot.

9. The apparatus as defined in claim 7, wherein the module with instructions configured to filter matching landmarks further comprises:

program instructions configured to compare the number of features common to the image and to a landmark to a predetermined number; and

program instructions configured to filter the landmark from the list when the number of common features for the landmark is below the predetermined number.

10. The apparatus as defined in claim 7, wherein the program instructions configured to filter matching landmarks further comprises:

program instructions configured to initiate a computation of a camera pose from a subset of features from the image and corresponding matching features from the landmark; and

program instructions configured to filter the landmark from the list upon a failure of the computation to converge to a result.

11. The apparatus as defined in claim 7:

wherein landmark poses associated with landmarks correspond to a pose of the mobile device when the landmark is created or updated when a previously created landmark is re-observed;

wherein an initial estimate of a landmark pose of a newly created landmark corresponds to a global robot pose from when the landmark was created.

12. The apparatus as defined in claim 7, wherein at least one reliability test of the reliability tests comprises an evaluation of a root mean square (RMS) projection error corresponding to a computed relative pose of the mobile device with respect to a landmark pose associated with the landmark.