System and method for object localization

• US 6,952,488 B2
• Filed: 08/27/2001
• Issued: 10/04/2005
• Est. Priority Date: 08/27/2001
• Status: Expired due to Fees

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Zhong, Yu, Kelly, Alonzo J.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Choobin, Barry
• Application Number:
  US09/940,095
• Publication Number:
  US 20030044047A1
• Time in Patent Office: 1,499 Days
• Field of Search: 382/104, 382/106, 382/103, 382/153, 382/169, 382/171, 382/199, 382/164, 382/173, 340/907, 340/933, 340/937, 348/113, 244/3.11, 701/28, 701/200, 700/258, 700/259, 414/1, 414/137.1
• US Class Current: 382/104
• CPC Class Codes: B66F 9/0755 Position control; Position detectors
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

A computer-assisted method for localizing a rack, including sensing an image of the rack, detecting line segments in the sensed image, recognizing a candidate arrangement of line segments in the sensed image indicative of a predetermined feature of the rack, generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack, and estimating a position and orientation of the rack based on the matrix of correspondence.

Claims

1. A computer-assisted method for localizing a rack, comprising:

sensing an image of the rack;

detecting line segments in the sensed image;

recognizing a candidate arrangement of line segments in the sensed image indicative of a predetermined feature of the rack;

generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack; and

estimating a position and orientation of the rack based on the matrix of correspondence.

2. The method of claim 1, wherein:

recognizing a candidate arrangement of line segments includes recognizing a candidate arrangement of line segments in the sensed image indicative of a pair of fork lift holes of the rack; and

generating a matrix of correspondence includes generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the pair of fork lift holes of the rack.

3. The method of claim 2, wherein recognizing a candidate arrangement of line segments includes:

grouping the line segments to form candidate shapes indicative of the pair of fork lift holes of the rack; and

selecting an arrangement of line segments which most closely corresponds to a shape of the pair of fork lift holes.

4. The method of claim 3, further comprising guiding a vehicle relative to the rack based on the estimated position and orientation of the rack.

5. A system for localizing a rack, comprising:

a sensor;

a preprocessing module in communication with the sensor for detecting line segments in an image of the rack sensed by the sensor;

a recognition module in communication with the preprocessing module for recognizing a candidate arrangement of line segments in the sensed image of the rack indicative of a predetermined feature of the rack;

a set-up module in communication with the recognition module for generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack; and

a pose refinement module in communication with the set-up module for estimating a position of orientation of the rack based on the matrix of correspondence.

6. The system of claim 5, wherein the predetermined feature of the rack is a pair of fork lift holes.

7. The system of claim 6, further comprising an integrated motion control module in communication with the pose refinement module.

8. The system of claim 7, wherein the sensor is mounted to a vehicle.

9. The system of claim 8, wherein the integrated motion control module guides the vehicle based on the estimated position and orientation of the rack.

10. The system of claim 5, wherein the sensor is a CCD camera.

11. A system for localizing a rack, comprising:

a sensor;

a first circuit in communication with the sensor for detecting line segments in an image of the rack sensed by the sensor;

a second circuit in communication with the first circuit for recognizing a candidate arrangement of line segments in the sensed image indicative of a predetermined feature of the rack;

a third circuit in communication with the second circuit for generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack; and

a fourth circuit in communication with the third circuit for estimating a position and orientation of the rack based on the matrix of correspondence.

12. The system of claim 11, wherein the predetermined feature of the rack is a pair of fork lift holes.

13. The system of claim 11, wherein the sensor is connected to a vehicle.

14. The system of claim 13, further comprising a fifth circuit in communication with the fourth circuit for guiding the vehicle based on the estimated position and orientation of the rack.

15. A system for localizing an rack, comprising:

means for sensing an image of the rack;

means for detecting line segments in the image;

means for recognizing a candidate arrangement of line segments in the sensed image indicative of a predetermined feature of the rack;

means for generating a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack; and

means for estimating a position and orientation of the rack based on the matrix of correspondence.

16. The system of claim 15, wherein the predetermined feature of the rack is a pair of fork lift holes.

17. The system of claim 15, further comprising means for guiding a vehicle based on the estimated position and orientation of the rack.

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

detect line segments in an sensed image of a rack;

recognize a candidate arrangement of line segments in the sensed image indicative of a predetermined feature of the rack;

generate a matrix of correspondence between the candidate arrangement of line segments and an expected position and orientation of the predetermined feature of the rack; and

estimate a position and orientation of the object based on the matrix of correspondence.

19. The computer-readable medium of claim 18, wherein the predetermined feature of the rack is a pair of fork lift holes.

20. The computer-readable medium of claim 19, having further stored thereon instructions which, when executed by the processor, cause the processor to:

recognize a candidate arrangement of line segments in the sensed image indicative of the pair of fork lift holes; and

generate a matrix of correspondence between the candidate arrangement of line segments indicative of the pair of fork lift holes and an expected position and orientation of the fork lift holes.

21. The computer-readable medium of claim 20, having further stored thereon instructions which, when executed by the processor, cause the processor to guide a vehicle based on the estimated position and orientation of the rack.

22. A method of stacking an upper rack on a lower rack, the upper rack having first and second legs a fixed distance apart and the lower rack having first and second receptacles a fixed distance apart, comprising:

sensing a first image including the first leg of the upper rack and the first receptacle of the lower rack;

sensing a second image including the second leg of the upper rack and the second receptacle of the lower rack;

detecting line segments in the first image;

detecting line segments in the second image;

recognizing a candidate arrangement of line segments in the first image indicative of a predetermined feature of the first leg and a predetermined feature of the first receptacle;

recognizing a candidate arrangement of line segments in the second image indicative of a predetermined feature of the second leg and a predetermined feature of the second receptacle;

generating a first matrix of correspondence between the candidate arrangement of line segments indicative of the first leg and the first receptacle and an expected position and orientation of the first leg and first receptacle;

generating a second matrix of correspondence between the candidate arrangement of line segments indicative of the second leg and the second receptacle and an expected position and orientation of the second leg and second receptacle;

determining a relative distance between the first leg and the first receptacle based on the first matrix of correspondence; and

determining a relative distance between the second leg and the second receptacle based on the second matrix of correspondence.

23. The method of claim 22, wherein sensing the first image and sensing the second image include simultaneously sensing the first and second images.

24. The method of claim 22, wherein:

sensing the first image includes sensing the first image with a first sensor; and

sensing the second image include sensing the second image a second sensor, wherein the first and second sensors are oriented at a non-zero angel relative to each other.

25. The method of claim 22, wherein recognizing a candidate arrangement of line segments in the first image includes recognizing a candidate arrangement of line segments in the first image indicative of a first fiducial on the first leg and recognizing a candidate arrangement of line segments in the first image indicative of a second fiducial on the first receptacle.

26. The method of claim 25, wherein recognizing the candidate arrangement of line segment in the first image includes recognizing a candidate arrangement of line segments in the first image indicative of a first reflective member connected to the first leg and recognizing a candidate arrangement of the line segments in the first image indicative of a second reflective member connected to the first receptacle.

27. The method of claim 25, wherein recognizing the candidate arrangement of line segments in the first image includes recognizing a candidate arrangement of line segments in the first image indicative of a first laser image projected onto the first leg and recognizing a candidate arrangement of the line segments in the first image indicative of a second laser image projected onto the first receptacle.

28. The method of claim 22, further comprising moving the upper rack such that the first leg is vertically aligned with the first receptacle and the second leg is vertically aligned with the second receptacle.

29. A system for stacking an upper rack on a lower rack, the upper rack having first and second legs a fixed distance apart and the lower rack having first and second receptacles a fixed distance apart, comprising:

a first sensor;

a second sensor, wherein the first and second sensors are oriented at a non-zero angle relative to each other;

a preprocessing module in communication with the first and second sensors for detecting line segments in images of the upper and lower racks sensed by the first and second sensors;

a recognition module in communication with the preprocessing module for recognizing a first candidate arrangement of line segments in a first image sensed by the first sensor indicative of a predetermined feature of the first receptacle of the lower rack and a predetermined feature of the first leg of the upper rack, and for recognizing a second candidate arrangement of line segments in a second image sensed by the second sensor indicative of predetermined feature of the second receptacle of the lower rack and a predetermined feature of the second leg of the upper rack;

a set-up module in communication with the recognition module for generating a first matrix of correspondence between the first candidate arrangement of line segments and an expected position and orientation of the first receptacle of the lower rack and the first leg of the upper rack, and for generating a second matrix of correspondence between the second candidate arrangement of line segments and an expected position and orientation of the second receptacle of the lower rack and the second leg of the upper rack; and

a stacking module in communication with the set-up module for determining a relative position between the first leg of the upper rack and the first receptacle of the lower rack based on the first matrix of correspondence, and for determining a relative position between the second leg of the upper rack and the second receptacle of the lower rack based on the second matrix of correspondence.

30. The system of claim 29, further comprising an integrated motion control module in communication with the stacking module.

31. The system of claim 30 wherein the first and second sensors are mounted to a vehicle for supporting the upper rack, and the integrated motion control module is for providing steering and power commands to the vehicle.

32. The system of claim 29, wherein at least one of the first and second sensors is a CCD camera.

33. The system of claim 29, wherein the predetermined feature of at least one of the first and second legs of the upper rack and the first and second receptacles of the lower rack is selected from the group consisting of a fiducial and a reflective member.

34. A system for stacking an upper rack on a lower rack, the upper rack having first and second legs a fixed distance apart and the lower rack having first and second receptacles a fixed distance apart, comprising:

a first sensor;

a second sensor, wherein the first and second sensors are oriented at a non-zero angle relative to each other;

a first circuit in communication with the first and second sensors for detecting line segments in a first image sensed by the first sensor including the first leg of the upper rack and the first receptacle of the lower rack, and for detecting a second image sensed by the second sensor including the second leg of the upper rack and the second receptacle of the lower rack;

a second circuit in communication with the first circuit for recognizing a first candidate arrangement of line segments in the first image indicative of predetermined features of the first leg and the first receptacle, and for recognizing a second candidate arrangement of line segments in the second image indicative of predetermined features of the second leg and the second receptacle;

a third circuit in communication with the second circuit for generating a first matrix of correspondence between the first candidate arrangement of line segments and an expected position and orientation of the first leg and first receptacle, and for generating a second matrix of correspondence between the second candidate arrangement of line segments and an expected position and orientation of the second leg and second receptacle; and

a fourth circuit in communication with the third circuit for determining a relative distance between the first leg and the first receptacle based on the first matrix of correspondence, and for determining a relative distance between the second leg and the second receptacle based on the second matrix of correspondence.

35. The system of claim 34, further comprising a fifth circuit in communication with the fourth circuit for moving the upper rack such that the first leg is vertically aligned with the first receptacle and the second leg is vertically aligned with the second receptacle based on the relative distances between the first leg and the first receptacle and the second leg and the second receptacle.

36. The system of claim 34, wherein at least one of the first and second sensors is a CCD camera.

37. The system of claim 34, wherein the predetermined feature of at least one of the first and second legs of the upper rack and the first and second receptacles of the lower rack is selected from the group consisting of a fiducial and a reflective member.

38. A system for stacking an upper rack on a lower rack, the upper rack having first and second legs a fixed distance apart and the lower rack having first and second receptacles a fixed distance apart, comprising:

means for sensing a first image including the first leg of the upper rack and the first receptacle of the lower rack;

means for sensing a second image including the second leg of the upper rack and the second receptacle of the lower rack;

means for detecting line segments in the first image and in the second image;

means for recognizing a first candidate arrangement of line segments in the first image indicative of a predetermined feature of the first leg and indicative of a predetermined feature of the first receptacle;

means for recognizing a second candidate arrangement of line segments in the second image indicative of a predetermined feature of the second leg and indicative of a predetermined feature of the second receptacle;

means for generating a first matrix of correspondence between the first candidate of line segments and an expected position and orientation of the first leg and first receptacle;

means for generating a second matrix of correspondence between the second candidate of line segments and an expected position and orientation of the second leg and second receptacle;

means for determining a relative distance between the first leg and the first receptacle; and

means for determining a relative distance between the second leg and the second receptacle.

39. The system of claim 38, further comprising means for moving the upper rack such that the first leg is vertically aligned with the first receptacle and the second leg is vertically aligned with the second receptacle based on the determined relative distances between the first leg and the first receptacle and the second leg and the second receptacle.

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

detect line segments in a first image of a first leg of an upper rack and a first receptacle of a lower rack;

detect line segments in a second image of a second leg of the upper rack and a second receptacle of the lower rack;

recognize a first candidate arrangement of line segments in the first image indicative of a predetermined feature of the first leg and indicative of a predetermined feature of the first receptacle;

recognize a second candidate arrangement of line segments in the second image indicative of a predetermined feature of the second leg and indicative of a predetermined feature of the second receptacle;

generate a first matrix of correspondence between the first candidate arrangement of line segments and an expected position and orientation of the first leg and first receptacle;

generate a second matrix of correspondence between the second candidate arrangement of line segments and an expected position and orientation of the second leg and second receptacle;

determine a relative distance between the first leg and the first receptacle based on the first matrix of correspondence; and

determine a relative distance between the second leg and the second receptacle based on the second matrix of correspondence.

41. The computer-readable medium of claim 40, having further stored thereon instructions which, when executed by the processor, cause the processor to provide steering and power commands to a vehicle supporting the upper rack to move the upper rack such that the first leg is vertically aligned with the first receptacle and the second leg is vertically aligned with the second receptacle.