Techniques for decoding images of barcodes

• US 20090078772A1
• Filed: 09/20/2007
• Published: 03/26/2009
• Est. Priority Date: 09/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ofek, Eyal, Loomis, Anne
• Granted Patent: US 7,886,978 B2
• Time in Patent Office: Days
• US Class Current: 235/462.40
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1465 using several successive scans of the optical code
• CPC Class Codes: G06K 7/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

Techniques for enhancing the reliable and efficient decoding of images of computer-readable symbols, which represent information encoded using a one- or two-dimensional visual symbology, are discussed. In accordance with one technique, prior to attempting to decode a particular image, a likelihood of successfully decoding the visual symbology from the image is determined based on a success metric. The success metric is calculated based on the blurriness of the image, or the tilt of the camera that captured the image, or both. Levels of blurriness or tilt, and the likelihood of decoding success, are ascertained with respect to predetermined reference values associated with generally decodable images. In accordance with another technique, image-sharpening algorithms are applied at select locations within the image. Such locations generally correspond to centers of modules within the visual symbology of the computer-readable symbol, which are assigned values based on grayscale values of proximate pixels in the image.

Claims

1. A computer-readable storage medium encoded with computer-executable instructions which, when executed by a processor, perform a method comprising:

identifying a first image of a computer-readable symbol obtained by an image capture device, the computer-readable symbol representing information encoded using a visual symbology arranged on a surface, the visual symbology comprising a plurality of modules of predetermined sizes, each module having a binary reflectance value;

based on either the blurriness of the first image or the tilt of the image capture device relative to the surface or both, calculating a success metric associated with the first image;

based on the success metric, prior to attempting to decode the visual symbology within the first image, determining a likelihood of successfully decoding the visual symbology within the first image;

when there is determined to be a likelihood of successfully decoding the visual symbology within the first image, arranging for decoding the visual symbology within the first image; and

when there is determined not to be a likelihood of successfully decoding the visual symbology within the first image,

not arranging for decoding the visual symbology within the first image,

identifying a second image of the computer-readable symbol obtained by the image capture device,

based on either the blurriness of the second image or the tilt of the image capture device relative to the surface or both, calculating a success metric associated with the second image, and

based on the success metric associated with the second image, determining a likelihood of successfully decoding the visual symbology within the second image.

2. The computer-readable medium according to claim 1, wherein the visual symbology is selected from the group consisting of:

a two-dimensional visual symbology; and

a linear visual symbology.

3. The computer-readable medium according to claim 1, wherein the method step of identifying an image of a computer-readable symbol comprises receiving the image from the image capture device.

4. The computer-readable medium according to claim 1, wherein the method step of ascertaining a tilt of the image capture device relative to the surface further comprises:

locating at least three points in the first image, the at least three points corresponding to finder patterns within the visual symbology;

defining a first point, a second point, and a third point from among the at least three points;

determining a first distance between the first point and the second point;

determining a second distance between the first point and the third point;

calculating a ratio value based on the first distance and the second distance; and

calculating a scale value based on a maximum of the first distance and the second distance.

5. The computer-readable medium according to claim 4, wherein the method step of calculating a success metric associated with the first image based on the tilt of the image capture device relative to the surface further comprises:

identifying test scale values and test ratio values associated with a plurality of test images obtained using a predetermined image capture device;

expressing the test scale values relative to the test ratio values in a predetermined manner;

based on the step of expressing the test scale values relative to the test ratio values, identifying a first range of the test scale values relative to the test ratio values, and a second range of the test scale values relative to the test ratio values;

expressing the calculated ratio value and the calculated scale value relative to each other in the predetermined manner to determine an image tilt value;

ascertaining whether the image tilt value is within the first range or the second range; and

calculating the success metric based on whether the image tilt value is within the first range or the second range.

6. The computer-readable medium according to claim 5, wherein

the predetermined manner of expressing comprises a graphical representation,

the first range comprises a first area of the graphical representation and the second range comprises a second area of the graphical representation, and

the image tilt value comprises a point within the graphical representation.

7. The computer-readable medium according to claim 1, wherein the method step of ascertaining a level of blurriness of the first image further comprises:

within the first image, identifying locations estimated to correspond to centers of modules within the visual symbology;

assigning a grayscale value to each identified location to form an array of grayscale values;

identifying at least two proximate grayscale values within the array estimated to correspond to modules having different reflectance values; and

calculate a sharpness gradient based on the at least two proximate grayscale values.

8. The computer-readable medium according to claim 7, wherein the method step of calculating a success metric based on the blurriness of the first image further comprises:

defining a threshold value of the sharpness gradient;

comparing the calculated sharpness gradient to the threshold value; and

calculating the success metric based on whether the sharpness gradient is above the threshold value or below the threshold value.

9. The computer-readable medium according to claim 1, wherein the method step of determining a likelihood of successfully decoding the visual symbology within the first image further comprises:

comparing the success metric to a predetermined success threshold; and

based on the step of comparing, determining whether there is a likelihood of successfully decoding or whether there is not a likelihood of successfully decoding.

10. The computer-readable medium according to claim 1, further comprising:

when there is determined not to be a likelihood of successfully decoding, prior to identifying the second image,

arranging to provide feedback to a user of the image capture device, the feedback relating to the tilt of the image capture device relative to the surface, the user able to use the feedback to obtain the second image.

11. The computer-readable medium according to claim 1, wherein the computer-executable instructions are executable by a processor selected from the group consisting of:

a client-side processor and a network-side processor.

18. The computer-readable medium according to claim 1, wherein the computer-executable instructions are executable by a processor selected from the group consisting of:

a client-side processor and a network-side processor.

12. A computer-readable storage medium encoded with computer-executable instructions which, when executed by a processor, perform a method for decoding an image of a computer-readable symbol obtained by an image capture device, the computer-readable symbol representing information encoded using a visual symbology arranged on a surface, the visual symbology comprising a plurality of modules, each module having a binary reflectance value, the image comprising a plurality of pixels, each pixel having a grayscale value, the method comprising:

within the image, identifying a number of groups of pixels, each group of pixels estimated to correspond to a particular module;

within the image, identifying locations estimated to correspond to centers of modules within the visual symbology, each location having associated therewith proximate pixels from one or more groups of pixels, the proximate pixels within a predetermined proximity to the location;

assigning a first value to each identified location to form an array of first values, each first value based on a relationship between grayscale values of the proximate pixels associated with the location;

applying a predetermined image processing algorithm to the array of first values to produce an array of a second values for each identified location; and

based on the array of second values, arranging to estimate the binary reflective values of the modules corresponding to the identified locations within the image, the estimated binary reflective values usable to retrieve the information encoded using the visual symbology.

13. The computer-readable medium according to claim 12, wherein the visual symbology is selected from the group consisting of:

a two-dimensional visual symbology; and

a linear visual symbology, and wherein the plurality of modules are selected from the group consisting of;

two-dimensional shapes; and

lines.

14. The computer-readable medium according to claim 12, wherein the relationship between grayscale values of proximate pixels associated with a particular location comprises an average of the grayscale values of the proximate pixels, and wherein the assigned first values comprise the averages of grayscale values.

15. The computer-readable medium according to claim 14, wherein the predetermined image processing algorithm comprises an edge enhancement filter configured to improve contrast between the averages of the grayscale values.

16. The computer-readable storage medium according to claim 12, wherein the modules of the visual symbology are of predetermined sizes and arranged in accordance with a coordinate system, each module having a position specifiable with reference to the coordinate system, the method step of identifying locations within the image estimated to correspond to centers of modules within the visual symbology further comprising:

within the image, identifying a plurality of sections, each section having a number of groups of pixels associated therewith, each section estimated to correspond to a finder pattern within the visual symbology that includes a number of modules;

within each section, estimating centers of at least some of the groups of pixels;

within each section, estimating distances between the estimated centers based on the sizes of the modules;

identifying a predetermined reference pattern of binary reflectance values of modules within the finder patterns;

within each section, ascertaining an alignment location through which a horizontal line, a vertical line, or both, would pass through a sequence of estimated distances corresponding to the predetermined reference pattern;

based on the alignment locations, defining a mapping between the modules within the visual symbology and the groups of pixels in the image; and

based on the mapping, identifying locations within the image estimated to correspond to centers of modules within the visual symbology.

17. The computer-readable medium according to claim 16, wherein the predetermined reference pattern comprises a dark-light-dark-light-dark pattern having a sequence of 11311, and wherein the sequence of estimated distances comprises 1221.

19. An electronic device, comprising:

an image capture device operable to obtain an image of a computer-readable symbol, the image comprising a plurality of pixels, each pixel having a grayscale value, the computer-readable symbol representing information encoded using a visual symbology arranged on a surface, the visual symbology comprising a plurality of modules, each module having a binary reflectance value;

a computer-readable storage medium; and

a processor responsive to the computer-readable storage medium and to a computer program, the computer program, when loaded into the processor, operable to;

receive the image from the image capture device;

within the image, identify at least three sections, each section estimated to correspond to a finder pattern within the visual symbology;

based on information obtained via examination of the at least three sections, ascertain a tilt of the image capture device relative to the surface or a level of blurriness of the image, or both;

based on the tilt or the level of blurriness or both, determine a likelihood of successfully decoding the visual symbology within the image; and

when there is determined to be a likelihood of successfully decoding the visual symbology,

identify within the image a number of groups of pixels, each group of pixels estimated to correspond to a particular module,

within the image, identify locations estimated to correspond to centers of modules within the visual symbology, each location having associated therewith proximate pixels from one or more groups of pixels, the proximate pixels within a predetermined proximity to the location,

assign a first value to each identified location to form an array of first values, each first value based on a relationship between grayscale values of the proximate pixels associated with the location,

apply a predetermined image processing algorithm to the array of first values to produce an array of a second values for each identified location, and

based on the array of second values, arrange to estimate the binary reflective values of the modules corresponding to the identified locations within the image, the estimated binary reflective values usable to retrieve the information encoded using the visual symbology.

20. The apparatus according to claim 19, wherein the apparatus selected from the group consisting of:

a digital camera;

a personal digital assistant;

a mobile phone;

a personal computer; and

a portable media player.