Infrastructure independent position determining system

• US 5,999,866 A
• Filed: 11/05/1996
• Issued: 12/07/1999
• Est. Priority Date: 11/05/1996
• Status: Expired due to Term

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Coulter, Robert Craig, Kelly, Alonzo James
• Primary Examiner(s): Ng, Virna Lisa
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US08/744,053
• Time in Patent Office: 1,127 Days
• Field of Search: 701/23, 701/24, 701/28, 701/200, 701/26, 180/167, 180/168, 180/169, 318/587, 318/568.16, 318/567, 901/1, 901/3
• US Class Current: 701/28
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• 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

Abstract

A method and apparatus for determining position is comprised of the steps of capturing an image related to the present position and comparing the captured image with one or more images from an iconic map. The iconic map is a map which stores images of a substantially flat surface over which a robot or vehicle is to operate. The stored images contain randomly occurring characteristics such as the fibers in a carpet, brush marks appearing in brushed concrete, and the like. Although such naturally occurring features are essentially random, when analyzed in small enough images, each image becomes unique. The position is determined based upon the image from the map which provides the highest correlation. Speed, wheel slippage, and other parameters can be calculated using the disclosed method.

Claims

1. A method of determining a present position of an object relative to a surface, the surface having a plurality of randomly occurring features distributed thereon, comprising the steps of:

capturing an image of the surface containing a distribution of the features related to the present position of the object relative to the surface;

comparing the distribution of the features from said captured image to at least one distribution of the features from at least one image stored in a map, the at least one distribution in said at least one stored image being representative of a known position relative to the surface; and

determining the present position of the object relative to the surface based on said comparing step.

2. The method of claim 1 wherein said comparing step includes the step of comparing the distribution of the features from said captured image to a plurality of distributions of the features from a plurality of images taken from said map, each of the plurality of distributions being representative of a known position relative to the surface, and wherein said determining step includes the step of selecting one of said plurality of images based on a degree of correlation between the distribution of said features from said captured image and each of the plurality of distributions of said features from said plurality of images.

3. The method of claim 2 additionally comprising the step of estimating the present position of the object, and wherein said plurality of images are selected based on said estimated position.

4. The method of claim 3 additionally comprising the step of identifying a target area around said estimated position, and wherein said plurality of images are selected from said target area.

5. The method of claim 2 additionally comprising the step of maintaining a lock on a stored image containing a distribution of the features of the surface representative of the present position of the object, and wherein said plurality of images are selected based on the lock on the stored image representative of the present position.

6. The method of claim 1 wherein said step of capturing an image includes the step of capturing a image with a camera positioned perpendicular to a substantially flat surface.

7. The method of claim 1 wherein said step of capturing an image includes the step of capturing an image with a camera positioned at an angle with respect to a substantially flat surface.

8. The method of claim 1 wherein said comparing step includes the step of correlating the distribution of the features from said captured image to the at least one distribution of the features from said at least one stored image.

9. The method of claim 8 wherein said step of correlating includes the step of performing a cross-correlation.

10. The method of claim 1 additionally comprising the step of updating the at least one image stored in the map.

11. The method of claim 1 additionally comprising the step of adding images to the map.

12. The method of claim 1 additionally comprising the step of selecting a course for the object based on the determined position.

13. Apparatus for determining a present position of an object relative to a surface, the surface having a plurality of randomly occurring features distributed thereon, comprising:

means for capturing an image of the surface containing a distribution of the features related to the present position of the object relative to the surface;

means for storing a map;

means for comparing the distribution of the features from said captured image to at least one distribution of the features from at least one image stored in said means for storing a map, the at least one distribution in said at least one stored image being representative of a known position relative to the surface; and

means for determining the present position of the object in response to said means for comparing.

14. The apparatus of claim 13 wherein said means for comparing compares the distribution of the features from said captured image to a plurality of distributions of the features from a plurality of images taken from said map, each of the plurality of distributions being representative of a known position relative to the surface, and wherein said means for determining selects one of said plurality of images based on a degree of correlation between the distribution of said features from said captured image and each of the plurality of distributions of said features from said plurality of images.

15. The apparatus of claim 14 additionally comprising means for estimating the present position of the object, and wherein said plurality of images are selected based on said estimated position.

16. The apparatus of claim 15 additionally comprising means for identifying a target area around said estimated position, and wherein said plurality of images are selected from said target area.

17. The apparatus of claim 14 additionally comprising means for maintaining a lock on a stored image containing a distribution of the features of the surface representative of the present position of the object and wherein said plurality of images are selected based on the lock on the stored image representative of the present position.

18. The apparatus of claim 13 wherein said means for capturing an image includes a camera having a known relationship with a substantially flat surface.

19. The apparatus of claim 13 additionally comprising means for updating the at least one image stored in the map.

20. The apparatus of claim 13 additionally comprising means responsive to the determined position for selecting a course for the object.