SYSTEM AND METHOD FOR ROBUST REAL-TIME 1D BARCODE DETECTION

• US 20130193211A1
• Filed: 01/26/2012
• Published: 08/01/2013
• Est. Priority Date: 01/26/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: BAQAI, Farhan, ATHALYE, Vivek, NATEGH, Neda, SACHS, Todd
• Granted Patent: US 8,608,073 B2
• Time in Patent Office: Days
• US Class Current: 235/462.04
• CPC Class Codes: G06K 7/1413 1D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1452 detecting bar code edges
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

Abstract

A fast image-based barcode detection and recognition technique allows a user of a device to analyze an image containing a barcode, locating the barcode containing region of the image automatically, without requiring a user to frame and align the image. In one embodiment, the technique may locate multiple omni-directional barcode regions simultaneously.

Claims

1. A method of detecting a barcode in an image, comprising:

partitioning an image captured by an image capture device into a plurality of subimages;

determining the plurality of subimages that contain at least a portion of the barcode, comprising;

filtering the plurality of subimages using a parallel line filter, comprising;

quantizing edge pixels contained in a subimage into one of a predetermined number of bins corresponding to an angular direction of an edge pixel gradient; and

selecting a region of the image containing the barcode, comprising the plurality of subimages that contain at least a portion of the barcode.

2. The method of claim 1, further comprising:

preprocessing the image prior to partitioning the image, comprising;

converting the image from a color image to a grayscale image;

subsampling the image to a predetermined number of pixels; and

converting the image into an edge-detected image.

3. The method of claim 1, further comprising:

providing the selected region of the image to a barcode decoder.

4. The method of claim 1, wherein determining the plurality of subimages that contain at least a portion of the barcode further comprises:

filtering the plurality of subimages using a density filter; and

filtering the plurality of subimages according to a number of edge pixel lines in a subimage.

5. The method of claim 4, wherein filtering the plurality of subimages using a density filter comprises:

comparing a number of edge pixels contained in a subimage to a predetermined threshold value.

7. The method of claim 1, wherein quantizing edge pixels is performed on all pixels of the subimage.

8. The method of claim 4, wherein filtering the plurality of subimages according to a number of edge pixel lines in a subimage comprises:

filtering the plurality of subimages with a Hough line filter.

9. The method of claim 8, wherein filtering the plurality of subimages according to a number of edge pixel lines in a subimage comprises:

calculating a singular value decomposition of a subimage;

calculating an orientation of the barcode in the subimage from the singular value decomposition of the subimage; and

filter the plurality of subimages according to a number of edge pixel lines in the subimage having the calculated orientation of the barcode.

10. The method of claim 9, wherein filtering the plurality of subimages according to a number of edge pixel lines in a subimage further comprises:

calculating a significance of the orientation; and

filtering out subimages wherein the significance of the orientation is less than a predetermined threshold value.

6. (canceled)

11. An apparatus, comprising:

an image sensor;

a programmable control device;

a memory coupled to the programmable control device, wherein instructions are stored in the memory, the instructions causing the programmable control device to;

partition an image captured by the image sensor into a plurality of subimages;

select a plurality of barcode subimages from the plurality of subimages, according to a predetermined density threshold, a predetermined parallel line threshold, and a predetermined line count threshold, comprising instructions to cause the programmable control device to;

filter the plurality of images using a parallel line filter, comprising instructions that cause the programmable device to;

quantize edge pixels into one of a predetermined number of bins corresponding to an angular direction of an edge pixel gradient; and

select an oriented region of the image containing the barcode, comprising the plurality of barcode subimages.

12. The apparatus of claim 11, wherein the instructions further cause the programmable control device to:

preprocess the image before the image is partitioned into subimages, comprising causing the programmable control device to;

subsample the image to a predetermined number of pixels.

13. The apparatus of claim 11, wherein the instructions further cause the programmable control device to:

preprocess the image before the image is partitioned into subimages, comprising causing the programmable control device to;

convert the image into a grayscale image.

14. The apparatus of claim 11, wherein the image sensor produces a grayscale image.

15. The apparatus of claim 11, wherein the instructions that cause the programmable control device to select a plurality of barcode subimages from the plurality of subimages, according to a predetermined density threshold, a predetermined parallel line threshold, and a predetermined line count threshold comprise instructions to cause the programmable control device to:

filter the plurality of images using a density filter, the density filter comparing a number of edge pixels contained in a subimage to a predetermined threshold value.

17. The apparatus of claim 11, wherein the instructions that cause the programmable control device to select a plurality of barcode subimages from the plurality of subimages, according to a predetermined density threshold, a predetermined parallel line threshold, and a predetermined line count threshold comprise instructions to cause the programmable control device to:

filter the plurality of subimages using a line count filter.

18. The apparatus of claim 17, wherein the line count filter is a Hough line filter.

19. The apparatus of claim 17, wherein the instructions that cause the programmable control device to select a plurality of barcode subimages from the plurality of subimages, according to a predetermined density threshold, a predetermined parallel line threshold, and a predetermined line count threshold comprise instructions to cause the programmable control device to:

determine an orientation of lines in the subimage; and

filter the plurality of subimages using a line count filter, counting only lines having the determined orientation.

20. The apparatus of claim 17, wherein the instructions to cause the programmable control device to determine an orientation of lines in the subimage comprises instructions to cause the programmable control device to:

calculate a singular value decomposition of the subimage; and

determine an orientation of lines from a singular value of the singular value decomposition of the subimage.

21. The apparatus of claim 20, wherein the instructions to cause the programmable control device to determine an orientation of lines in the subimage further comprises instructions to cause the programmable control device to:

determine a significance of the orientation.

16. (canceled)

22. A non-transitory program storage device, readable by a programmable control device, comprising instructions stored thereon for causing the programmable control device to:

subsample an image containing a barcode captured by an image sensor to a predetermined number of pixels;

convert the subsampled image into a grayscale image.

partition grayscale image into a plurality of subimages;

determine the plurality of subimages that contain at least a portion of the barcode, comprising instructions to cause the programmable control device to;

filter the plurality of images using a parallel line filter, comprising instructions that cause the programmable device to;

quantize edge pixels into one a predetermined number of bins corresponding to an angular direction of an edge pixel gradient; and

select a region of the image containing the barcode, comprising the plurality of subimages that contain at least a portion of the barcode.

23. The non-transitory program storage device of claim 22, wherein the instructions stored thereon to cause the programmable control device to determine the plurality of subimages that contain at least a portion of the barcode comprise instructions to cause the programmable control device to:

select subimages of the plurality of subimages that contain at least a predetermined number of parallel lines.

24. The non-transitory program storage device of claim 23, wherein the instructions stored thereon to cause the programmable control device to select subimages of the plurality of subimages that contain at least a predetermined number of parallel lines comprise instructions for causing the programmable control device to:

filter the plurality of subimages with a density filter; and

determine an orientation of lines in a subimage; and

select a subimage of the plurality of subimages with the predetermined number of parallel lines in the determined orientation.

25. The non-transitory program storage device of claim 22, wherein the instructions stored thereon to cause the programmable control device to select a region of the image containing the barcode, comprising the plurality of subimages that contain at least a portion of the barcode, comprises instructions to cause the programmable control device to:

create a bounding box surrounding a region of the image comprising the plurality of subimages that contain at least a portion of the barcode;

crop and rotate the bounding box to produce a vertical barcode;

generate a contrast map of the region surrounded by the bounding box;

block smooth the contrast map;

create a colormap of the contrast map;

create a binarized contrast map from the colormap; and

morphologically close the binarize contrast map.