Decoding visual codes

• US 10,169,629 B2
• Filed: 08/03/2017
• Issued: 01/01/2019
• Est. Priority Date: 07/14/2015
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Wang, Chun-Kai, Lou, Yu
• Primary Examiner(s): Vo, Tuyen K
• Application Number:
  US15/668,501
• Publication Number:
  US 20170330009A1
• Time in Patent Office: 516 Days
• Field of Search: 23546201-46209, 235494
• CPC Class Codes: G06K 7/10722 Photodetector array or CCD scanning
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image

Abstract

Various algorithms are presented that enable an image of a data matrix to be analyzed and decoded for use in obtaining information about an object or item associated with the data matrix. The algorithms can account for variations in position and/or alignment of the data matrix. In one approach, the image is analyzed to determine a connected region of pixels. The connected region of pixels can be analyzed to determine a pair of pixels, included in the connected region of pixels, that is separated a greatest distance wherein a first pixel and second pixel of the pair of pixels is associated with image coordinates. Using the image coordinates of the pair of pixels, a potential area of the image that includes the visual code can be determined and the potential area can be analyzed to verify the presence of a potential data matrix.

Claims

1. A computing device, comprising:

a computing device processor;

a memory device including instructions that, when executed by the computing device processor, cause the computing device to;

obtain an image including a visual code, the visual code being one of a plurality of format types and having an arbitrary orientation with respect to the image;

analyze the image to determine a connected region of pixels of a plurality of pixels;

determine a first pixel of the connected region of pixels associated with first pixel coordinates and a second pixel associated with second pixel coordinates;

determine a region of the image that includes the visual code based at least in part on the first pixel coordinates and the second pixel coordinates;

determine a plurality of borders associated with the region;

determine a geometric shape of the region based at least in part on the plurality of borders of the region, the geometric shape having a length and a width;

determine a ratio of the length and the width of the geometric shape;

determine whether the ratio meets at least one aspect ratio threshold;

verify the region includes the visual code when the ratio of the length and the width meets the at least one aspect ratio threshold;

determine the format type of the visual code; and

rectify the visual code from the arbitrary orientation to a rectified orientation suitable for a decoder for the format type; and

decode the visual code using the decoder.

2. The computing device of claim 1, wherein the instructions, when executed further enable the computing device to:

determine a first segment and a second segment of the region;

determine a first pattern of pixels for the first segment;

determine a second pattern of pixels for the second segment; and

determine that the first pattern of pixels and the second pattern of pixels satisfies a ratio of first pixels values to second pixel values.

3. The computing device of claim 1, wherein the instructions, when executed to decode the visual code further enable the computing device to:

crop the potential region from the image to generate a cropped image that includes the visual code; and

provide the visual code to a decoding component.

4. The computing device of claim 1, wherein the instructions, when executed to decode the visual code further enable the computing device to:

determine coordinate information describing the region of the image; and

provide the image and the coordinate information to a decoding component.

5. The computing device of claim 1, wherein the first pixel and the second pixel are part of a pair of pixels of the connected region of pixels, and wherein the pair of pixels is separated a greatest distance of the connected region of pixels.

6. The computing device of claim 5, wherein the instructions when executed further enable the computing device to:

for individual pixels in the connected region of pixels,

determine a distance measurement to pixels in the connected region of pixels to generate a plurality of distance measurements; and

select the pair of pixels associated with a greatest distance measurement from the plurality of distance measurements.

7. The computing device of claim 1, wherein the instructions when executed to analyze the image further enable the computing device to:

convert the image to a binarized image, the binarized image including a plurality of pixels, individual pixels of the plurality of pixels being associated with one of a first pixel value or a second pixel value; and

analyze the binarized image using one of a connected-component analysis algorithm, a blob extraction algorithm, a region labeling algorithm, a blob discovery algorithm, or a region extraction algorithm to identify the connected region of pixels.

8. The computing device of claim 1, wherein the instructions when executed to convert the image further enable the computing device to:

normalize color values for individual color channels of individual pixels to a value between 0 and 1.

9. The computing device of claim 1, wherein the instructions when executed to determine the region of the image further enable the computing device to:

for individual pixels in the connected region of pixels,

determine a first distance measurement to the first pixel coordinates,

determine a second distance measure to the second pixel coordinates,

determine a sum of the first distance measure and the second distance measure to generate a plurality of distance sums,

select a greatest distance sum of the plurality of distance sums, the greatest distance sum being associated with a third pixel associated with third pixel coordinates in the connected region of pixels; and

estimate fourth pixel coordinates of a fourth pixel using a geometric relationship between the first pixel coordinates, the second pixel coordinates, and the third pixel coordinates.

10. The computing device of claim 9, wherein the instructions when executed further enable the computing device to:

scan the plurality of pixels in a first direction to determine a first set of pixels, the first set of pixels being positioned along a first path between the first pixel coordinates and the second pixel coordinates;

scan the plurality of pixels in a second direction to determine a second set of pixels, the second set of pixels being positioned along a second path between the first pixel coordinates and fourth pixel coordinates;

scan the plurality of pixels in a third direction to determine a third set of pixels, the third set of pixels being positioned along a third path between the fourth pixel coordinates and the third pixel coordinates,

scan the plurality of pixels in a fourth direction to determine a fourth set of pixels, the fourth set of pixels being positioned along a fourth path between the third pixel coordinates and the second pixel coordinates; and

determine a first intersection point, a second intersection point, a third intersection point, and a fourth intersection point based at least in part on an intersection of the first set of pixels, the second set of pixels, the third set of pixels, and the fourth set of pixels.

11. A method, comprising:

obtaining an image including a visual code, the visual code being one of a plurality of format types and having an arbitrary orientation with respect to the image;

analyzing the image to determine a connected region of pixels of a plurality of pixels;

determining a first pixel of the connected region of pixels associated with first pixel coordinates and a second pixel associated with second pixel coordinates;

determining a region of the image that includes the visual code based at least in part on the first pixel coordinates and the second pixel coordinates;

determining a first border and a second border associated with the region;

determining a ratio of a first length of the first border and a second length of the second border;

verifying the region includes the visual code based at least in part on whether the ratio meets at least one aspect ratio threshold;

determining the format type of the visual code; and

rectifying the visual code from the arbitrary orientation to a rectified orientation suitable for a decoder for the format type; and

decoding the visual code using the decoder.

12. The method of claim 11, further comprising:

for individual pixels in the connected region of pixels,

determining a distance measurement to pixels in the connected region of pixels to generate a plurality of distance measurements; and

selecting a pair of pixels associated with a greatest distance measurement from the plurality of distance measurements, the pair of pixels including the first pixel and the second pixel.

13. The method of claim 11, wherein determining the region of the image further includes:

for individual pixels in the connected region of pixels,

determining a first distance measurement to the first pixel coordinates,

determining a second distance measure to the second pixel coordinates,

determining a sum of the first distance measure and the second distance measure to generate a plurality of distance sums,

selecting a greatest distance sum of the plurality of distance sums, the greatest distance sum being associated with a third pixel associated with third pixel coordinates in the connected region of pixels; and

estimating fourth pixel coordinates of a fourth pixel using a geometric relationship between the first pixel coordinates, the second pixel coordinates, and the third pixel coordinates.

14. The method of claim 11, further comprising:

converting the image to a binarized image, the binarized image including a plurality of pixels, each pixel of the plurality of pixels being associated with one of a first pixel value or a second pixel value; and

analyzing the binarized image using one of a connected-component analysis algorithm, a blob extraction algorithm, a region labeling algorithm, a blob discovery algorithm, or a region extraction algorithm to identify the connected region of pixels.

15. The method of claim 11, further comprising:

verifying that the region includes the visual code using one of a first verification test and a second verification test.

16. A non-transitory computer readable storage medium storing one or more sequences of instructions executable by one or more processors to perform a set of operations comprising:

obtaining an image including a visual code, the visual code being one of a plurality of format types and having an arbitrary orientation with respect to the image;

analyzing the image to determine a connected region of pixels of a plurality of pixels;

determining a first pixel of the connected region of pixels associated with first pixel coordinates and a second pixel associated with second pixel coordinates;

determining a region of the image that includes the visual code based at least in part on the first pixel coordinates and the second pixel coordinates;

determining a plurality of borders associated with the region;

determining a geometric shape of the region based at least in part on the plurality of borders of the region, the geometric shape having a length and a width;

determining a ratio of the length and the width of the geometric shape;

determining whether the ratio meets at least one aspect ratio threshold;

verifying the region includes the visual code when the ratio of the length and the width meets the at least one aspect ratio threshold;

determining the format type of the visual code;

rectifying the visual code from the arbitrary orientation to a rectified orientation suitable for a decoder for the format type; and

decoding the visual code using the decoder.

17. The non-transitory computer readable storage medium of claim 16, further comprising instructions executed by the one or more processors to perform the set of operations of:

for individual pixels in the connected region of pixels,

determining a distance measurement to pixels in the connected region of pixels to generate a plurality of distance measurements; and

selecting a pair of pixels associated with a greatest distance measurement from the plurality of distance measurements, the pair of pixels including the first pixel and the second pixel.

18. The non-transitory computer readable storage medium of claim 16, further comprising instructions executed by the one or more processors to perform the set of operations of:

for individual pixels in the connected region of pixels,

determining a first distance measurement to the first pixel coordinates,

determining a second distance measure to the second pixel coordinates,

determining a sum of the first distance measure and the second distance measure to generate a plurality of distance sums,

selecting a greatest distance sum of the plurality of distance sums, the greatest distance sum being associated with a third pixel associated with third pixel coordinates in the connected region of pixels; and

estimating fourth pixel coordinates of a fourth pixel using a geometric relationship between the first pixel coordinates, the second pixel coordinates, and the third pixel coordinates.

19. The non-transitory computer readable storage medium of claim 16, further comprising instructions executed by the one or more processors to perform the set of operations of:

cropping the region from the image to generate a cropped image that includes the visual code;

or

determining coordinate information describing the region of the image; and

decoding the visual code.

20. The non-transitory computer readable storage medium of claim 16, further comprising instructions executed by the one or more processors to perform the set of operations of:

determining a first segment and a second segment of the region;

determining a first pattern of pixels for the first segment;

determining a second pattern of pixels for the second segment; and

determining that the first pattern of pixels and the second pattern of pixels satisfies a ratio of first pixels values to second pixel values.