Infrastructure independent position determining system

• US 6,453,223 B1
• Filed: 05/13/1999
• Issued: 09/17/2002
• Est. Priority Date: 11/05/1996
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Coulter, Robert Craig, Kelly, Alonzo James, Ollis, Mark D.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US09/311,683
• Time in Patent Office: 1,223 Days
• Field of Search: 701/28, 701/207, 701/200, 701/208, 701/217, 701/220, 701/223, 340/995, 340/998, 318/587, 318/568.16, 318/567, 901/1, 901/3, 180/167, 180/168, 180/169, 382/1
• 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 computer-assisted method for determining a position and orientation a sensor relative to a scene. The sensor has a plurality of degrees of freedom in position and orientation relative to the scene. The method includes sensing an image of the scene, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene, comparing the plurality of regions of the sensed image to a plurality of regions of a first image of the scene stored in a map, the first stored image representative of a position and orientation of the sensor relative to the scene, and determining sensor position and orientation based on the comparing.

Claims

1. A computer-assisted method for determining a position and an orientation of a sensor relative to a scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene, the method comprising:

sensing an image of the scene, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

comparing the plurality of regions of the sensed image to a plurality of regions of a first image of the scene stored in a map, the first stored image representative of a position and orientation of the sensor relative to the scene; and

determining sensor position and orientation based on the comparing.

2. The method of claim 1, wherein comparing the plurality of regions of the sensed image to a plurality of regions of the first stored image includes:

selecting a plurality of regions of the sensed image;

rotating the plurality of regions into a coordinate system of the map;

correlating the plurality of regions of the sensed image to the plurality of regions of the first stored image;

performing a least squares fit of the correlations of the plurality of regions of the sensed image to the plurality of regions of the first stored image.

3. The method of claim 1, further comprising selecting the first stored image from a plurality of images stored in the map based on a degree of correlation between the sensed image and each of the plurality of stored images.

4. The method of claim 3, further comprising receiving a secondary estimate of the position of the sensor relative to the scene.

5. The method of claim 4, wherein selecting the first stored image includes selecting the first stored image from a plurality of images stored in the map, wherein each of the plurality of stored images is representative of a position of the sensor proximate to the secondary estimate of the sensor position.

6. The method of claim 4, further comprising estimating an amount of uncertainty in sensor position based on the secondary estimate and wherein selecting the first stored image includes selecting the first stored image from a plurality of images stored in the map, wherein each of the plurality of stored images is representative of a position of the sensor within the amount of uncertainty of sensor position.

7. The method of claim 1, further comprising detecting a likelihood of false recognitions of the plurality of regions of the sensed in the first stored image.

8. The method of claim 7, further comprising detecting a likelihood of false mis-recognitions of the plurality of regions of the sensed image in the first stored image.

9. The method of claim 1, further comprising detecting whether the plurality of regions of the sensed image contain sufficient features to determine the sensor position and orientation based on the comparing.

10. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene; and

a third circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation.

11. An apparatus for determining a position and an orientation of an object relative to a scene, comprising;

a sensor rigidly connected to the object and orientated toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene;

a map for storing a plurality of images of the scene according to a coordinate system, each of the images being representative of a known position and orientation of the sensor relative to the scene;

means for comparing a plurality of regions of an image of the scene sensed by the sensor with a plurality of regions of a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene; and

means for generating a scene-referenced estimate of sensor position and orientation based on the means for comparing.

12. The apparatus of claim 11, wherein the means for comparing include;

means for selecting the plurality of regions of the sensed image;

means for rotating the plurality of regions of the sensed image into the coordinate system of the plurality of stored images;

means for correlating the plurality of regions of the sensed image to the plurality of regions of the first stored image; and

means for performing a least squares fit of the correlations of the plurality of regions of the sensed image to the plurality of regions of the first stored image.

13. The apparatus of claim 11, further comprising:

means for receiving a secondary estimate of sensor position; and

means for selecting the first stored image from the plurality of stored images based on the secondary estimate.

14. The apparatus of claim 13, further comprising means for generating an optimal estimate of sensor position and orientation based on the secondary estimate and the scene-referenced estimate.

15. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene; and

generate a scene-referenced estimate of sensor position and orientation based on the comparison.

16. The computer-readable medium of claim 15, having stored thereon further instructions, which when executed by the processor, cause the processor to select the first stored image from a plurality of images of the scene stored in the computer-readable medium based on a secondary estimate of sensor position.

17. A computer-assisted method for determining a position and an orientation of a sensor relative to a scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene, the method comprising:

sensing an image of a substantially flat surface, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the substantially flat surface;

comparing two regions of the sensed image to two regions of a first image of the substantially flat surface stored in a map, the first stored image representative of a position and orientation of the sensor relative to the substantially flat surface; and

determining sensor position and orientation based on the comparing.

18. A computer-assisted method for determining a position and an orientation of a sensor relative to a scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene, the method comprising:

sensing an image of the scene, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

comparing the plurality of regions of the sensed image to a plurality of regions of a first image of the scene stored in a map, the first stored image representative of a position and orientation of the sensor relative to the scene;

determining sensor position and orientation based on the comparing;

selecting the first stored image from a plurality of images stored in the map based on a degree of correlation between the sensed image and each of the plurality of stored images;

receiving a secondary estimate of the position of the sensor relative to the scene;

generating an optimal estimate of sensor position based on the secondary estimate and the determined sensor position; and

calibrating the map by associating a stored image representative of the optimal estimate with the determined sensor position.

19. A computer-assisted method for determining a position and an orientation of a sensor relative to a scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene, the method comprising:

sensing an image of the scene, the sensed image having a plurality of regions such that a sum of degrees of independent constraint of the plurality of regions equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

comparing the plurality of regions of the sensed image to a plurality of regions of a first image of the scene stored in a map, the first stored image representative of a position and orientation of the sensor relative to the scene;

determining sensor position and orientation based on the comparing; and

detecting whether an orientation of the scene is not an expected orientation of the scene.

20. The method of claim 19, further comprising comparing at least one additional region of the sensed image to at least one additional region of the first stored image if the orientation of the scene is not the expected orientation of the scene.

21. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

a third circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation;

a fourth circuit in communication with the second circuit for receiving a secondary estimate of sensor position; and

a fifth circuit in communication with the fourth circuit for selecting the first stored image from the plurality of stored images based on the secondary estimate.

22. The apparatus of claim 21, wherein the position estimator further includes:

a sixth circuit in communication with the fourth circuit for generating an optimal estimate of sensor position and orientation based on the secondary estimate and the scene-referenced estimate; and

a seventh circuit in communication with the sixth circuit for calibrating a stored image by associating the stored image representative of the optimal estimate with the scene-referenced estimate.

23. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene, and wherein the second circuit includes;

a third circuit in communication with the first circuit for selecting the plurality of regions of the sensed image;

a fourth circuit in communication with the third circuit for rotating the plurality of regions into a coordinate system of the plurality of images stored in the first circuit;

a fifth circuit in communication with the fourth circuit for correlating the plurality of regions of the sensed image to the plurality of regions of the first stored image; and

a sixth circuit in communication with the fifth circuit for performing a least squares fit of the correlations of the plurality of regions of the sensed image to the plurality of regions of the first stored image; and

a seventh circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation.

24. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

a third circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation;

a fourth circuit in communication with the second circuit for detecting a likelihood of false recognitions of the plurality of regions of the sensed image in the first stored image; and

a fifth circuit in communication with the fourth circuit for detecting a likelihood of false mis-recognitions of the plurality of regions of the sensed image in the stored image.

25. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

a third circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation; and

a fourth circuit in communication with the second circuit for detecting whether an orientation of the scene is not an expected orientation of the scene.

26. The apparatus of claim 25, wherein the position estimator further includes a fifth circuit in communication with the fourth circuit for comparing at least one additional region of the sensed image with at least one additional region of the first stored image when the orientation of the scene is not the expected orientation of the scene.

27. An apparatus for determining a position and an orientation of an object relative to a scene, comprising:

a sensor rigidly connected to the object and oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene; and

a position estimator in communication with the sensor, the position estimator including;

a first circuit for storing a plurality of images of the scene, each of the plurality of stored images being representative of a position and orientation of the sensor relative to the scene;

a second circuit in communication with the first circuit for comparing a plurality of regions of an image of the scene sensed by the sensor to a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

a third circuit in communication with the second circuit for generating a scene-referenced estimate of sensor position and orientation; and

a fourth circuit in communication with the second circuit for detecting whether the plurality of regions of the sensed image contain sufficient features of the scene to generate the scene-referenced estimate.

28. An apparatus for determining a position and an orientation of an object relative to a scene, comprising;

a sensor rigidly connected to the object and orientated toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene;

a map for storing a plurality of images of the scene according to a coordinate system, each of the images being representative of a known position and orientation of the sensor relative to the scene;

means for comparing a plurality of regions of an image of the scene sensed by the sensor with a plurality of regions of a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

means for generating a scene-referenced estimate of sensor position and orientation based on the means for comparing;

means for receiving a secondary estimate of sensor position;

means for selecting the first stored image from the plurality of stored images based on the secondary estimate;

means for generating an optimal estimate of sensor position and orientation based on the secondary estimate and the scene-referenced estimate; and

means for calibrating the map based on the optimal estimate.

29. An apparatus for determining a position and an orientation of an object relative to a scene, comprising;

a sensor rigidly connected to the object and orientated toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene;

a map for storing a plurality of images of the scene according to a coordinate system, each of the images being representative of a known position and orientation of the sensor relative to the scene;

means for comparing a plurality of regions of an image of the scene sensed by the sensor with a plurality of regions of a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

means for generating a scene-referenced estimate of sensor position and orientation based on the means for comparing;

means for detecting a likelihood of false recognitions of the plurality of regions of the sensed image in the first stored image; and

means for detecting a likelihood of false mis-recognitions of the plurality of regions of the sensed image in the first stored image.

30. An apparatus for determining a position and an orientation of an object relative to a scene, comprising;

a sensor rigidly connected to the object and orientated toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene;

a map for storing a plurality of images of the scene according to a coordinate system, each of the images being representative of a known position and orientation of the sensor relative to the scene;

means for comparing a plurality of regions of an image of the scene sensed by the sensor with a plurality of regions of a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

means for generating a scene-referenced estimate of sensor position and orientation based on the means for comparing; and

means for detecting whether an orientation of the scene is not an expected orientation of the scene.

31. An apparatus for determining a position and an orientation of an object relative to a scene, comprising;

a sensor rigidly connected to the object and orientated toward the scene, the sensor having a plurality of degrees of freedom in position and orientation relative to the scene;

a map for storing a plurality of images of the scene according to a coordinate system, each of the images being representative of a known position and orientation of the sensor relative to the scene;

means for comparing a plurality of regions of an image of the scene sensed by the sensor with a plurality of regions of a first stored image, wherein a sum of degrees of independent constraint of the plurality of regions of the sensed image equals or exceeds the degrees of freedom in position and orientation of the sensor relative to the scene;

means for generating a scene-referenced estimate of sensor position and orientation based on the means for comparing; and

means for detecting whether the plurality of regions of the sensed image contain sufficient features to generate the scene-referenced estimate.

32. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene;

generate a scene-referenced estimate of sensor position and orientation based on the comparison;

select the first stored image from a plurality of images of the scene stored in the computer-readable medium based on a secondary estimate of sensor position; and

generate an optimal estimate of sensor position and orientation based on the secondary estimate and the scene-referenced estimate.

33. The computer-readable medium of claim 32, having stored thereon further instructions, which when executed by the processor, cause the processor to calibrate stored images of the scene based on the optimal estimate.

34. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene;

generate a scene-referenced estimate of sensor position and orientation based on the comparison;

select the plurality of regions of the sensed image;

rotate the plurality of regions into a coordinate system of the first stored image of the scene;

correlate the plurality of regions of the sensed image to the plurality of regions of the first stored image; and

perform a least squares fit of the correlations of the plurality of regions of the sensed image to the plurality of regions of the first stored image.

35. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene;

generate a scene-referenced estimate of sensor position and orientation based on the comparison;

detect a likelihood of false recognitions of the plurality of regions of the sensed image in the first stored image; and

detect a likelihood of false mis-recognitions of the plurality of regions of the sensed image in the first stored image.

36. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene;

generate a scene-referenced estimate of sensor position and orientation based on the comparison; and

detect whether an orientation of the scene is not an expected orientation of the scene.

37. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to:

receive an image of a scene sensed by a sensor oriented toward the scene, the sensor having a plurality of degrees of freedom in position and orientation with respect to the scene and the sensed image having a plurality of regions having a sum of degrees of independent constraint equal to or exceeding the degrees of freedom of the sensor relative to the scene;

compare the plurality of regions of the sensed image to a plurality of regions of a first stored image, wherein the first stored image is representative of a known position and orientation of the sensor relative to the scene;

generate a scene-referenced estimate of sensor position and orientation based on the comparison; and

determine whether the plurality of regions of the sensed image contain sufficient features of the scene to generate the scene-referenced estimate.