Techniques for decoding images of barcodes

• US 7,886,978 B2
• Filed: 09/20/2007
• Issued: 02/15/2011
• Est. Priority Date: 09/20/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Loomis, Anne, Ofek, Eyal
• Primary Examiner(s): Le; Thien M.
• Assistant Examiner(s): STANFORD, CHRISTOPHER J
• Application Number:
  US11/903,178
• Publication Number:
  US 20090078772A1
• Time in Patent Office: 1,244 Days
• Field of Search: 235/462.1, 235/462.11
• US Class Current: 235/462.1
• 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;

estimating a tilt of the image capture device relative to the surface, by

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 comprising a ratio of the first distance and the second distance,

calculating a scale value comprising a maximum of the first distance and the second distance, and

graphically expressing the calculated ratio value and the calculated scale value as a tilt coordinate comprising a point in a two-dimensional coordinate system;

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

graphically expressing the test scale values relative to the test ratio values as points in the two-dimensional coordinate system;

within the two-dimensional coordinate system, identifying a first range of points comprising the test scale values relative to the test ratio values, and a second range of points comprising the test scale values relative to the test ratio values;

ascertaining whether the tilt coordinate is within the first range of points or the second range of points;

calculating a success metric associated with the first image based on either a level of blurriness of the first image or whether the tilt coordinate is within the first range of points or the second range of points;

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 the first image of the computer-readable symbol comprises receiving the first image from the image capture device.

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

ascertaining the level of blurriness of the first image by

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.

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

the method step of calculating the success metric 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.

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

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

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

9. 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 stored in the computer-readable storage medium, 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, estimate a tilt of the image capture device relative to the surface by

locating at least three points in the 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 comprising a ratio of the first distance and the second distance,

calculating a scale value comprising a maximum of the first distance and the second distance, and

graphically expressing the calculated ratio value and the calculated scale value as a tilt coordinate comprising a point in a two-dimensional coordinate system;

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

graphically express the test scale values relative to the test ratio values as points in the two-dimensional coordinate system;

within the two-dimensional coordinate system, identify a first range of points comprising the test scale values relative to the test ratio values, and a second range of points comprising the test scale values relative to the test ratio values;

ascertain whether the tilt coordinate is within the first range of points or the second range of points;

based on whether the tilt coordinage is within the first range of points or the second range of points, or on a level of blurriness of the image 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.

10. The apparatus according to claim 9, wherein the apparatus selected from the group consisting of:

a digital camera, a personal digital assistant, a mobilephone, a personal computer, and a portable media player.