Decoding visual codes

• US 9,501,681 B1
• Filed: 07/14/2015
• Issued: 11/22/2016
• 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:
  US14/799,327
• Time in Patent Office: 497 Days
• Field of Search: 23546201-47203, 235/494
• US Class Current: 1/1
• 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 display element;

a computing device processor;

a camera; and

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

capture, by the camera, an image that includes a representation of a data matrix;

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;

determine, using a connected-component algorithm, a path of adjacent pixels from the plurality of pixels, each pixel in the path of adjacent pixels having a value corresponding to the first pixel value and being associated with a location on the binarized image;

determine a plurality of distance measurements for each pixel in the path of adjacent pixels, each distance measurement of the plurality of distance measurements corresponding to a distance between a pair of pixels in the path of adjacent pixels;

select a greatest distance measurement from the plurality of distance measurements, the greatest distance measure being associated with a first pixel and a second pixel in the path of adjacent pixels, the first pixel having a first location on the binarized image and the second pixel having a second location on the binarized image;

identify a third pixel in the path of adjacent pixels, the third pixel being associated with a third location that is a furthest location from both of the first location and the second location than any pixel in the path of adjacent pixels;

estimate a fourth location of a fourth pixel using a geometric relationship between the first location, the second location, and the third location;

determine a region of interest based at least in part on the first location, second location, third location, and fourth location, the region of interest including the representation of the data matrix; and

verify the region of interest by analyzing a plurality of borders of the region of interest using a timing pattern.

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

determine a geometric shape of the region of interest, 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.

3. 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 of interest;

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.

4. The computing device of claim 1, wherein the instructions when executed to identify the third pixel further cause the computing device to:

for each pixel in the path of adjacent pixels determine a sum of distance to the first location and the second location; and

select a largest sum of distance, the largest sum of distance corresponding to the third pixel.

5. 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 a plurality of connected regions using a connected-component algorithm, the connected region including a plurality of image elements;

determine a pair of image elements from the plurality of image elements separated a greatest distance on the image, a first image element of the pair of image elements being associated with first image coordinates on the image and a second image element of the pair of image elements being associated with second image coordinates on the image;

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

verify the potential area of the image by analyzing a plurality of borders of the potential area.

6. The computing device of claim 5, wherein the instructions when executed to analyze the image to determine the connected region further cause 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, wherein converting the image to binarized includes normalizing color values for each color channel of each pixel, to be analyzed, to a value between 0 and 1; 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 plurality of connected regions.

7. The computing device of claim 5, wherein the instructions when executed to determine the pair of image elements separated the greatest distance further cause the computing device to:

for each image element in the connected region,

determine a distance measurement to each of the image elements in the connected region to generate a plurality of distance measurements; and

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

8. The computing device of claim 5, wherein the instructions when executed to determine the potential area of the image further cause the computing device to:

for each image element in the connected region,

determine a first distance measurement to the first image coordinates,

determine a second distance measure to the second image 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 image element having a third image coordinates in the connected region; and

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

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

scan a plurality of pixels in the image 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 image coordinates and the second image coordinates;

scan the plurality of pixels in the first image 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 image coordinates and the fourth image coordinates;

scan the plurality of pixels in the first image 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 image coordinates and the third image coordinates,

scan the plurality of pixels in the first image 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 image coordinates and the second image 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.

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

verify that the potential area includes the visual code using a first verification test and a second verification test; and

decode the visual code.

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

determine a geometric shape of the potential 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.

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

determine a first segment and a second segment of the potential 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.

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

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

determine coordinate information describing the potential area of the image; and

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

15. The computing device of claim 5, wherein the visual code is one of a quick response (OR) code, a data matrix, or a two-dimensional barcode.

16. The computing device of claim 5, wherein the image is obtained by one of capturing the image using a camera of a computing device or downloading the image, and wherein the image is processed on the computing device or transmitted to a remote device for processing.

17. A method, comprising:

obtaining an image of a visual code;

analyzing the image to determine a connected region of a plurality of connected regions using a connected-component algorithm, the connected region including a plurality of image elements;

determining a pair of image elements from the plurality of image elements separated a greatest distance on the image, a first image element of the pair of image elements being associated with first image coordinates on the image and a second image element of the pair of image elements being associated with second image coordinates on the image;

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

verifying the potential area of the image by analyzing a plurality of borders of the potential area.

18. The method of claim 17, wherein determining the pair of image elements separated the greatest distance further includes:

for each image element in the connected region,

determining a distance measurement to each of the image elements in the connected region to generate a plurality of distance measurements; and

selecting the pair of image elements associated with a greatest distance measurement from the plurality of distance measurements.

19. The method of claim 17, wherein determining the potential area of the image further includes:

for each image element in the connected region,

determining a first distance measurement to the first image coordinates,

determining a second distance measure to the second image 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 image coordinates in the connected region; and

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

20. The method of claim 17, further comprising:

verifying that the potential area includes the visual code using a first verification test and a second verification test; and

decoding the visual code.