Recognizing dataforms in image areas

• US 5,917,945 A
• Filed: 06/15/1994
• Issued: 06/29/1999
• Est. Priority Date: 06/15/1994
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Original Assignee: Metanetics Corporation
• Inventors: Cymbalski, Robert Stanley
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/259,897
• Time in Patent Office: 1,840 Days
• Field of Search: 382/18, 382/27, 382/48, 382/50-53, 235/462, 235/463, 235/464, 235/494
• US Class Current: 382/192
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 30/2247 Characters composed of bars, e.g. CMC-7
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

Dataforms, such as bar codes and matrix codes, are recognized by analysis of histogram type data derived for a plurality of window sections of an image area. Typically, an image area 512 pixels high by 480 pixels wide is divided into 240 window areas, each including 1024 pixels in a 32 by 32 pixel square. A histogram for a window section overlying a portion of the dataform may typically exhibit two peaks representing the two principal reflective values (black and white, for example) of the elements and spaces of a dataform. A background (quiet zone) window section histogram exhibits one principal peak representing the background value (white, for example). The background window sections and the dataform window sections are assigned to two different groups. One or both groups are then used for one or more of the following: recognizing the presence of a dataform; determining whether the dataform is darker or lighter than the background; and locating the dataform within the image area. Also, a single histogram is used to identify the type of dataform, based upon the histogram signature of the dataform.

Claims

1. A method of recognizing a dataform, including elements and spaces having different reflective values, which may be present in an image area including a background area having primarily a single reflective value distinct from the reflective value of said elements, comprising the steps of:

(a) storing pixel data including pixel values representing reflection from said image area which may include said dataform;

(b) sampling pixel values, each representative of a reflective value of an incremental part of a window section of said image area which may include a portion of said dataform, to determine the number of occurrences of discrete pixel values representative of reflective values within said window section;

(c) categorizing said window section in one of the following groups (i) a first group for which said determined number of occurrences indicates the presence of at least two principal reflective values, including a relatively higher value and a relatively lower value, (ii) a second group for which said determined number of occurrences indicates the presence of one principal reflective value, representative of said background area, and (iii) a third group for other window sections;

(d) repeating steps (b) and (c) for a plurality of additional window sections of said image area;

(e) utilizing at least one of said first and second groups of window sections, with said determined number of occurrences as relevant, for carrying out at least one of the following steps;

(x) recognizing the presence of said dataform in said image area;

(y) determining whether said elements have a reflective value higher or lower than said background area reflective value; and

(z) determining the location of said dataform within said image area; and

(f) providing the results of step (e) for use in activating reading of said dataform.

2. A method of recognizing a dataform as in claim 1, wherein step (e) consists of carrying out the following step:

(x) recognizing the presence of said dataform in said image, based upon the presence of said first group of window sections characterized by two principal reflective values.

3. A method of recognizing a dataform as in claim 1, wherein step (e) consists of carrying out the following step:

(y) determining whether said elements of said dataform have a reflective value higher or lower than said distinct background area reflective value, based upon analysis of which of said relatively higher and lower values of said first group of window sections is most distinct from said one principal reflective value of said second group, which is representative of said background area.

4. A method of recognizing a dataform as in claim 1, wherein step (e) consists of carrying out the following step:

(z) determining the location of said dataform, based upon analysis of at least one of;

the composite positions of window sections of said first group, which represent portions of said dataform, and a frame effect provided by the composite positions of window sections of said second group, which represent said background area.

5. A method of recognizing a dataform as in claim 1, wherein in step (c) said second group is omitted and all window sections not meeting the criteria for said first group are included in said third group.

6. A method of recognizing a dataform as in claim 1, wherein said reflective values are representative of color, said first reflective value represents black, said second reflective value represents white and said single reflective value represents a color lighter than black.

7. A method of recognizing a dataform as in claim 1, wherein said first reflective value represents white, and said second reflective value and said single reflective value each represent a color darker than white.

8. A method of recognizing a dataform as in claim 1, wherein said first reflective value represents reflectance of electromagnetic energy at a first frequency within the electromagnetic spectrum and said second reflective value and said single reflective value each represent reflectance at a frequency different from said first frequency.

9. A method of recognizing a dataform as in claim 1, wherein step (c) further comprises categorizing said group (i) window sections into at least a first sub-group for which said determined number of occurrences indicates the presence of two principal reflective values and a second sub-group for which said determined number of occurrences indicates the presence of three principal reflective values.

10. A method of recognizing a dataform as in claim 1, wherein step (c) further comprises categorizing said group (i) window sections into sub-groups differentiated by the relative levels of occurrence of particular reflective values in each window section.

11. A method of recognizing a dataform as in claim 1, wherein said step (b) comprises determining said number of occurrences as a form of histogram data.

12. A method of recognizing a dataform as in claim 1, wherein the area of each of window sections is not larger than one one-hundredth of the area of the image area of interest.

13. A method of recognizing a dataform as in claim 1, wherein each of said window sections encompasses pixel values for at least 144 pixels.

14. A method of recognizing a dataform as in claim 1, wherein said step (c) categorizing is implemented on an automated basis including recognition of the number of principal reflective values exceeding a predetermined threshold in a representation of histogram type data for each window section, and associating identifiers with window section positions relative to the image area, said identifiers representing respective groups.

15. A method of recognizing a dataform, including elements and spaces having two different reflective values, positioned on a background area primarily characterized by a single reflective value, comprising the steps of:

(a) selecting an image area which may include said dataform;

(b) storing pixel values each representative of a reflective value of an incremental part of one window section of said image area, each said window section comprising a portion of said image area large enough to be able to encompass at least portions of a plurality of said elements of said dataform;

(c) sampling step (b) pixel values for each of a plurality of said window sections to determine, for individual ones of said window sections, the number of occurrences of discrete pixel values representative of reflective values in an individual window section;

(d) analyzing said derived data to identify at least one of (i) a first group of said window sections for which said determined number of occurrences is indicative of at least two principal reflective values, (ii) a second group of said window sections for which said determined number of occurrences is indicative of one principal reflective value and (iii) a third group of other window sections;

(e) utilizing at least one of said first and second groups of window sections, with step (c) data as relevant, for at least one of the following (i) recognizing the presence of said dataform, (ii) determining whether the reflective value of said dataform elements is higher or lower than said single reflective value corresponding to said background area, and (iii) locating said dataform relative to said image area; and

(f) providing the results of step (e) for use in activating reading of said dataform.

16. A method of recognizing a dataform as in claim 15, wherein step (e) consists of carrying out the following step:

(x) recognizing the presence of said dataform in said image, based upon the presence of said first group of window sections characterized by two principal reflective values.

17. A method of recognizing a dataform as in claim 15, wherein step (e) consists of carrying out the following step:

(y) determining whether said elements of said dataform have a reflective value higher or lower than said distinct background area reflective value, based upon analysis of which of said relatively higher and lower values of said first group of window sections is most distinct from said one principal reflective value of said second group, which is representative of said background area.

18. A method of recognizing a dataform as in claim 15, wherein step (e) consists of carrying out the following step:

(z) determining the location of said dataform, based upon analysis of at least one of;

the composite positions of window sections of said first group, which represent portions of said dataform, and a frame effect provided by the composite positions of window sections of said second group, which represent said background area).

19. A method of recognizing a dataform as in claim 15, wherein said step (b) comprises determining said number of occurrences as a form of histogram data.

20. A method of recognizing the presence of a dataform, including elements and spaces having different reflective values, comprising the steps of:

(a) storing pixel values representing reflection from an image area which includes said dataform;

(b) sampling pixel values, each representative of an incremental part of a section of said image area which includes at least a portion of said dataform, to determine the number of occurrences of discrete pixel values within said section of the image area;

(c) recognizing the presence of said dataform, based on the presence of two principal reflective values, including a relatively higher value and a relatively lower value, as indicated by said determined number of occurrences; and

(d) providing at an output port an indication of the presence of said dataform, for use in activating reading of said dataform.

21. A method of recognizing the presence of a dataform as in claim 20, wherein in step (c) said relatively higher reflective value represents a white space of said dataform and said relatively lower reflective value represents a black element of said dataform.

22. A method of recognizing the presence of a dataform as in claim 20, wherein in step (c) said relatively higher and relatively lower reflective values respectively represent two different shades of gray.

23. A method of recognizing the presence of a dataform as in claim 20, wherein said step (b) comprises determining said number of occurrences as a form of histogram data.