Decoding visual codes

• US 9,747,486 B2
• Filed: 09/30/2016
• Issued: 08/29/2017
• 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 KIM
• Application Number:
  US15/282,829
• Publication Number:
  US 20170024595A1
• Time in Patent Office: 333 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 of a visual code;

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 pixels coordinates;

determine an area 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 area;

analyze the plurality of borders using a first verification test and a second verification test; and

verify the area includes the visual code based at least in part on the first verification test and the second verification test.

2. 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.

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

for each pixel in the connected region of pixels,

determine a distance measurement to each pixel 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.

4. 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, each pixel 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.

5. 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 each color channel of each pixel to a value between 0 and 1.

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

for each pixel 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, and

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.

7. The computing device of claim 6, 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.

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

decode the visual code.

9. The computing device of claim 8, wherein the instructions, when executed to verify that the area includes the visual code using the first verification test further enable the computing device to:

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

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.

10. The computing device of claim 8, wherein the instructions, when executed to verify that the area includes the visual code using the second verification test further enable the computing device to:

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

determine a ratio of the length and the width; and

determine that the ratio meets at least one aspect ratio threshold.

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

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

provide the visual code to a decoding component.

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

determine coordinate information describing the area of the image; and

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

13. A method, comprising:

obtaining an image of a visual code;

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 pixels coordinates;

determining an area 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 area;

analyzing the plurality of borders using a first verification test and a second verification test; and

verifying the area includes the visual code based at least in part on the first verification test and the second verification test.

14. The method of claim 13, further comprising:

for each image element in the connected region of pixels,

determining a distance measurement to each of the 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.

15. The method of claim 13, wherein determining the area of the image further includes:

for each image element 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, and

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

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

16. The method of claim 13, 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.

17. 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 of a visual code;

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 pixels coordinates;

determine an area 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 area;

analyzing the plurality of borders using a first verification test and a second verification test; and

verifying the area includes the visual code based at least in part on the first verification test and the second verification test.

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

for each pixel in the connected region of pixels,

determining a distance measurement to each pixel 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.

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

for each image element 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, and

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

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

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

decoding the visual code.