Method for locating bar codes and symbols in an image

• US 7,181,066 B1
• Filed: 12/26/2002
• Issued: 02/20/2007
• Est. Priority Date: 12/26/2002
• Status: Active Grant

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Davis, Jason, Wagman, Adam, Nadabar, Sateesh G.
• Primary Examiner(s): DESIRE, GREGORY M
• Application Number:
  US10/329,908
• Time in Patent Office: 1,517 Days
• Field of Search: 235/454, 235/462.02, 235/462.09, 235/494, 235/462.01, 235/462.08, 235/462.1, 382/101, 382/183, 382/100
• US Class Current: 382/183
• 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/1443 locating of the code in an image
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A search method is disclosed for finding bar code symbols and various two-dimensional symbols, regardless of orientation, that is efficient, robust, and easy to use. The method works well on cluttered backgrounds, on skewed symbols, when symbols are almost touching, and when symbols are adjacent to text. The method includes choosing a candidate start region in the image, and then determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal. Next, an approximate orientation of the candidate oriented encoded signal is determined. Then, the candidate start region is grown, using the approximate orientation, so as to form a candidate symbol region that encloses an entire candidate code symbol, including at least a portion of the candidate start region. The method is finely responsive to orientation.

Claims

1. A method for omnidirectional location of bar code symbols and other graphical code symbols in an image of an object, each code symbol having an oriented encoded signal, the method comprising:

choosing a candidate start region in the image;

determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal, including;

selecting a subset of pixels, from the candidate start region, having enough information for signal detection;

computing a measure of interest of the subset of pixels for use in eliminating candidate start regions that do not contain a signal of interest, without rejecting candidate start regions that might contain a signal of interest; and

deciding whether the measure of interest is sufficient to warrant further examination of the candidate start region;

determining an approximate orientation of the candidate oriented encoded signal; and

growing the candidate start region, using the approximate orientation, so as to form a candidate symbol region that encloses an entire candidate code symbol, including at least a portion of the candidate start region.

2. The method of claim 1, further including:

deciding whether to locate another code symbol; and

choosing another candidate start region in the image.

3. The method of claim 2, wherein deciding whether to locate another code symbol includes:

determining whether a specified number of candidate code symbols were already found.

4. The method of claim 2, wherein deciding whether to locate another code symbol includes:

determining whether a specified number of candidate code symbols were successfully decoded.

5. The method of claim 2, wherein deciding whether to locate another code symbol includes:

in an image divided into a plurality of uniform tiles, processing until each uniform tile has been chosen as a candidate start region.

6. The method of claim 2, wherein deciding whether to locate another code symbol includes:

processing additional candidate start regions until a specified amount of time had elapsed.

7. The method of claim 2, wherein deciding whether to locate another code symbol includes:

processing additional candidate start regions until an external event occurs.

8. The method of claim 1, wherein choosing a candidate start region in the image includes:

dividing the entire image into a plurality of uniform tiles, and using each tile of a regular pattern of tiles as a candidate start region.

9. The method of claim 1, wherein choosing a candidate start region in the image includes:

specifying a point in the image where a code symbol is likely to appear, and choosing a set of contiguous pixels near that point to serve as the candidate start region.

10. The method of claim 9, wherein the set of contiguous pixels defines a rectangular region.

11. The method of claim 1, wherein determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal includes:

determining a number of pixels in the candidate start region that have an edge magnitude exceeding an edge magnitude threshold; and

comparing the number of pixels to a pixel count threshold.

12. The method of claim 1, further including:

deciding whether to continue refining the measure of interest;

selecting another subset of pixels, from the candidate start region, having enough information for signal detection; and

using the another subset of pixels, computing another measure of interest.

13. The method of claim 1, wherein selecting a subset of pixels includes:

selecting a plurality of horizontal stripes of the candidate start region as a subset of pixels.

14. The method of claim 1, wherein the measure of interest of the subset of pixels is used to distinguish blank regions from non-blank regions.

15. The method of claim 1, wherein computing a measure of interest of the subset of pixels includes:

determining a number of pixels in the candidate start region that have an edge magnitude exceeding an edge magnitude threshold.

16. The method of claim 1, wherein deciding whether the measure of interest is sufficient to warrant further examination includes:

comparing the measure of interest to a threshold.

17. The method of claim 1, wherein growing the candidate start region includes:

choosing a seed region that overlaps at least a portion of the candidate start region; and

growing the seed region to form the candidate symbol region, using at least the signal orientation.

18. The method of claim 1, wherein choosing a candidate start region in the image includes:

selecting a rectangular region of an image as the candidate start region; and

selecting several horizontal stripes of the rectangular region as a subset for analysis.

19. A method for omnidirectional location of bar code symbols and other graphical code symbols in an image of an object, each code symbol having an oriented encoded signal, the method comprising:

choosing a candidate start region in the image;

determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal, including analyzing a histogram of edge angles;

determining an approximate orientation of the candidate oriented encoded signal; and

growing the candidate start region, using the approximate orientation, so as to form a candidate symbol region that encloses an entire candidate code symbol, including at least a portion of the candidate start region.

20. A method for omnidirectional location of bar code symbols and other graphical code symbols in an image of an object, each code symbol having an oriented encoded signal, the method comprising:

choosing a candidate start region in the image;

determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal, including;

applying an oriented edge detector to the candidate start region to provide a plurality of edge angles;

computing an edge angle histogram based on the plurality of edge angles; and

analyzing the edge angle histogram to determining whether the candidate start region is likely to include at least a portion of a candidate oriented encoded signal;

determining an approximate orientation of the candidate oriented encoded signal; and

growing the candidate start region, using the approximate orientation, so as to form a candidate symbol region that encloses an entire candidate code symbol, including at least a portion of the candidate start region.

21. The method of claim 20, wherein analyzing the edge angle histogram includes:

detecting peaks in the edge angle histogram;

selecting a set of peaks in the edge angle histogram consistent with presence of an oriented encoded signal;

computing total area under the set of peaks; and

comparing the total area to a total area threshold.

22. A method for omnidirectional location of bar code symbols and other graphical code symbols in an image of an object, each code symbol having an oriented encoded signal, the method comprising:

choosing a candidate start region in the image, including selecting a rectangular region of the image;

determining whether the candidate start region includes at least a portion of a candidate oriented encoded signal, including;

selecting several horizontal stripes of the rectangular region as a first subset;

computing approximate edge magnitude pixels at a plurality of positions within the several horizontal stripes;

computing a first count of edge magnitude pixels by counting how many edge magnitude pixels have an edge magnitude that exceeds a first magnitude threshold;

determining whether the first count exceeds a first edge pixel count threshold;

selecting at least some of the rectangular region as a second subset;

computing edge magnitude pixels at a plurality of positions within the several horizontal stripes;

computing a second count of edge magnitude pixels by counting how many edge magnitude pixels have an edge magnitude that exceeds a second magnitude threshold; and

determining whether the second count exceeds a second edge pixel count threshold so as to determine whether the candidate start region is interesting;

determining an approximate orientation of the candidate oriented encoded signal; and

growing the candidate start region, using the approximate orientation, so as to form a candidate symbol region that encloses an entire candidate code symbol, including at least a portion of the candidate start region.

23. The method of claim 22, wherein computing edge magnitude and computing approximate edge magnitude is performed using a Roberts Cross edge detector.