Fiducial markers with a small set of values

• US 10,223,666 B1
• Filed: 08/29/2016
• Issued: 03/05/2019
• Est. Priority Date: 06/06/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Palamarchuk, Andriy, Brazeau, Jeremiah David
• Primary Examiner(s): Dunn, Alex C
• Application Number:
  US15/250,611
• Time in Patent Office: 918 Days
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• 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: G06F 16/29 Geographical information databases
• CPC Class Codes: G06K 7/10861 sensing of data fields affixed to objects or articles, e.g. coded labels postal sorting B07C3/14, conveying articles B65G47/48
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

A system for managing inventory items includes a portable inventory holder and an unmanned drive unit configured to move the inventory holder between locations in an inventory facility. The inventory facility includes a plurality of uniquely identifiable fiducial markers having a small set of values distributed in a pattern. The drive unit captures at least one image of a subset of the plurality of the fiducial markers. The at least one captured image is processed to determine a location of the drive unit within the facility. A path is determined along which the drive unit moves to an inventory holder and moves the inventory holder to another location. The pattern of fiducial markers can include one or more repeated instances of uniquely identifiable fiducial markers. A fiducial marker can encode information using a readable code and at least one attribute of the fiducial marker.

Claims

1. A method for managing inventory items, the method comprising:

placing a pattern of fiducial markers including repeated instances of one or more uniquely identifiable fiducial markers within an inventory facility;

creating a reference map associating locations within the inventory facility with fiducial markers in the pattern of fiducial markers;

capturing a local image of a portion of the pattern of fiducial markers with an image capture device mounted to an unmanned drive unit;

processing the local image, by a processor, using relative locations between fiducial markers, of the pattern of fiducial markers, in the local image in conjunction with a pattern matching algorithm and the reference map to determine a location of the unmanned drive unit within the inventory facility; and

controlling, by the processor, the unmannned drive unit to move to a second location within the inventory facility based at least in part on the determined location.

2. The method of claim 1, wherein the pattern of fiducial markers includes 100 or fewer uniquely identifiable fiducial markers.

3. The method of claim 2, wherein the pattern of fiducial markers includes 20 or fewer uniquely identifiable fiducial markers.

4. The method of claim 1, wherein creating the reference map includes:

capturing one or more images of the pattern of fiducial makers; and

processing the one or more images to correlate each of the fiducial markers with a respective location within the inventory facility.

5. The method of claim 4, wherein capturing one or more images of the pattern of fiducial markers includes imaging the pattern of fiducial markers with a second image capture device mounted on a second unmanned drive unit navigated within the inventory facility.

6. The method of claim 1, wherein controlling the unmanned drive unit to move to the second location includes:

capturing a second local image of a second portion of the pattern of fiducial markers with the image capture device mounted to the unmanned drive unit while controlling the unmanned drive unit to move to the second location;

processing the second local image, by the processor, using relative locations between fiducial markers, of the pattern of fiducial markers, in the second local image in conjunction with the pattern matching algorithm and the reference map to determine a third location of the unmanned drive unit within the inventory facility; and

processing the third location to track movement of the unmanned drive unit to the second location.

7. The method of claim 1, further comprising controlling operations of the unmanned drive unit based at least in part on the determined location, the operations including at least one of stopping the unmanned drive unit, rotating the unmanned drive unit, redirecting the unmanned drive unit, and changing operations of the unmanned drive unit.

8. The method of claim 1, further comprising controlling, via the processor, the unmanned drive unit to move an inventory holder within the inventory facility.

9. A method for managing inventory items, the method comprising:

placing a pattern of fiducial markers within an inventory facility, each of the pattern of fiducial markers encoding respective fiducial value information using a readable code and at least one attribute of the fiducial marker, the at least one attribute including at least one of;

(a) an orientation of the fiducial marker relative to a reference direction, (b) a color of the fiducial marker, (c) a size of the fiducial marker, or (d) a shape of the fiducial marker;

creating a reference map associating locations within the inventory facility with fiducial markers in the pattern of fiducial markers;

capturing a local image of a portion of the pattern of fiducial markers with an image capture device mounted to an unmanned drive unit;

processing the local image, by a processor, to;

detect a fiducial marker, of the pattern of fiducial markers, in the local image,

determine the at least one attribute of the detected fiducial marker;

read the readable code of the detected fiducial marker;

decode the fiducial value information of the detected fiducial marker using the determined at least one attribute of the detected fiducial marker and the readable code of the detected fiducial marker;

determine a location of the unmanned drive unit within the inventory facility based on the fiducial value information of the detected fiducial marker, a location of the detected fiducial marker within the local image, and the reference map; and

controlling, by the processor, the unmanned drive unit to move to a second location within the inventory facility based at least in part on the determined location.

10. The method of claim 9, wherein:

the pattern of fiducial markers includes 100 or fewer uniquely identifiable fiducial markers; and

the local image is processed, by the processor, using relative locations between fiducial markers, of the pattern of fiducial markers, in the local image in conjunction with a pattern matching algorithm and the reference map to determine the location of the unmanned drive unit within the inventory facility.

11. The method of claim 10, wherein the pattern of fiducial markers includes 20 or fewer uniquely identifiable fiducial markers.

12. The method of claim 9, wherein creating the reference map includes:

capturing one or more images of the pattern of fiducial makers; and

processing the one or more images to correlate each of the fiducial markers with a respective location within the inventory facility.

13. The method of claim 12, wherein capturing one or more images of the pattern of fiducial markers includes imaging the pattern of fiducial markers with a camera mounted on a second unmanned drive unit navigated within the inventory facility.

14. The method of claim 11, wherein controlling the unmanned drive unit to move to the second location includes:

capturing a second local image of a second portion of the pattern of fiducial markers with the image capture device mounted to the unmanned drive unit while controlling the unmanned drive unit to move to the second location;

processing the second local image to determine a third location of the unmanned drive unit within the inventory facility; and

processing the second third location to track movement of the unmanned drive unit to the second location.

15. The method of claim 9, wherein the readable code includes at least one of:

(a) bar code, (b) QR code, (c) MaxiCode, (d) Data Matrix, or (e) EZ Code.

16. The method of claim 9, wherein the at least one attribute includes at least two of:

(a) the orientation of the fiducial marker relative to the reference direction, (b) the color of the fiducial marker, (c) the size of the fiducial marker, or (d) the shape of the fiducial marker.