2-D barcode recognition

• US 7,780,084 B2
• Filed: 06/29/2007
• Issued: 08/24/2010
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, Han, Shi, Lin, Zhouchen, Zhang, Chunhui
• Primary Examiner(s): Lee; Seung H
• Application Number:
  US11/772,069
• Publication Number:
  US 20090001165A1
• Time in Patent Office: 1,152 Days
• Field of Search: 235/454, 235/462.01, 235/462.08, 235/462.11, 235/462.24
• US Class Current: 235/462.11
• CPC Class Codes: G06K 7/1093 sensing, after transfer of the image of the data-field to an intermediate store, e.g. storage with cathode ray tube
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 3/608 by skew deformation, e.g. two-pass or three-pass rotation

Abstract

Systems and methods for 2-D barcode recognition are described. In one aspect, the systems and methods use a charge coupled camera capturing device to capture a digital image of a 3-D scene. The systems and methods evaluate the digital image to localize and segment a 2-D barcode from the digital image of the 3-D scene. The 2-D barcode is rectified to remove non-uniform lighting and correct any perspective distortion. The rectified 2-D barcode is divided into multiple uniform cells to generate a 2-D matrix array of symbols. A barcode processing application evaluates the 2-D matrix array of symbols to present data to the user.

Claims

1. A method implemented at least in part by a computing device, the method comprising:

receiving an input image comprising a 2-Dimensional (2-D) barcode;

processing the input image to obtain a binary image, wherein the processing comprises compensating for illumination variation;

identifying an area in the binary image as containing the 2-D barcode;

transforming the area in the binary image into a warped image; and

generating a 2-D barcode symbol matrix from the warped image for processing and presentation of associated information to a user.

2. The method of claim 1, wherein the receiving comprises receiving the input image from an image capturing device.

3. The method of claim 1, wherein the processing further comprises converting the input image from a color image to a grayscale image.

4. The method of claim 1, wherein the compensating for illumination variation comprises at least one of removing shadows, enhancing contrast, and stretching image intensity.

5. The method of claim 1, wherein the identifying comprises:

converting the binary image into a mask using one or more image filters, wherein the mask comprises edge points;

detecting a region in the mask, wherein the region comprises the most connected edge points; and

locating the area in the binary image, wherein the area in the binary image corresponds to the region in the mask.

6. The method of claim 5, wherein the image filter identifies edges in the binary image.

7. The method of claim 5, wherein the locating comprises computing equations for edges bounding the area using Hough transform.

8. The method of claim 1 wherein the transforming the area comprises correcting perspective distortion using a homograph.

9. The method of claim 8, wherein the transforming further comprises determining whether the area is rotationally distorted.

10. The method of claim 1, wherein the generating the 2-D barcode symbol matrix comprises:

dividing the warped image into cells;

counting a number of black pixels in a cell; and

representing the number as a symbol in the cell.

11. The method of claim 10, wherein the symbol is selected from a binary digit, a color, a dot and a ring.

12. A computing device comprising:

one or more processors; and

a memory, the memory comprising computer-program instructions executable by the processor, the computer-program instructions including a barcode localization module and a barcode rectification module, the barcode localization module being configured to locate a 2-D barcode in a binary image, the barcode rectification module being configured to generate a 2-D barcode symbol matrix for input into a symbol recognition module that presents corresponding information to a user, the 2-D barcode symbol matrix being generated from a warped image of the 2-D barcode.

13. The computing device of claim 12 wherein the computer-program instructions further comprise instructions for an image processing module configured to perform acts comprising:

compensating for illumination variation in an input image; and

converting the input image into the binary image.

14. The computing device of claim 12, wherein the barcode localization module is further configured to perform acts comprising:

converting the binary image into a mask using one or more image filters; and

identifying an area in the mask, wherein the area corresponds to the 2-D barcode.

15. The computing device of claim 14, wherein the barcode localization module is configured to identify the area in the mask by performing acts comprising:

computing a center of gravity of edge points in the mask;

defining a rectangular area of initial proportions on the mask, the center of gravity being a center of the rectangular area; and

iteratively calculating respective edge point percentages in multiple directions from the center of gravity to change dimensions of the rectangular area and the center of gravity until the respective edge point percentages correspond to a predetermined threshold value, wherein the area is the rectangular area when the respective edge point percentages correspond to the predetermined threshold value.

16. The computing device of claim 12, wherein the 2-D barcode symbol matrix comprises of one or more symbols selected from a binary digit, a color, a dot of variable size and a ring.

17. A computer-readable data storage medium having a set of computer readable instructions that, when executed by a processor, perform acts comprising:

locating a 2-D barcode in a binary image, wherein the binary image is obtained by transformation of an input image;

converting the 2-D barcode in the binary image into a warped image by homography; and

dividing the warped image into cells for generating a 2-D barcode symbol matrix for processing and presentation of associated information to a user, wherein the generating comprises;

counting a number of black pixels in a cell; and

representing the number as a symbol in the cell.

18. The computer-readable data storage medium of claim 17, wherein the transformation of the input image comprises:

converting a color image into a grayscale image; and

compensating for illumination variation in the grayscale image.

19. The computer-readable data storage medium of claim 17, wherein the input image is received from at least one of a CCD camera, a web camera, and a camera associated with a phone.

20. The computer-readable data storage medium of claim 17, wherein the locating the 2-D barcode comprises:

converting the binary image into a mask using one or more image filters; and

detecting an area in the mask, wherein the area corresponds to the 2-D barcode.