Sub-pixel dataform reader with dynamic noise margins

• US 5,979,763 A
• Filed: 10/13/1995
• Issued: 11/09/1999
• Est. Priority Date: 10/13/1995
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Original Assignee: Metanetics Corporation
• Inventors: Wang, Ynjiun P., Ye, Angi
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): TREMBLAY, MARK STEPHEN
• Application Number:
  US08/543,122
• Time in Patent Office: 1,488 Days
• Field of Search: 382/470, 382/472, 382/473, 235/462, 235/463, 235/462.16, 235/462.17, 235/462.27, 235/462.41
• US Class Current: 235/462.17
• 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: G06K 7/1452 detecting bar code edges

Abstract

Sub-pixel processing of image data representing a dataform, such as a 2D bar code, enables reading of dataforms including more data/smaller elements, without costly increases in sensor and memory capacity. Whole pixel processing is employed for pixel-per-element resolutions of two or better. Sub-pixel cell edge transition location in image data is enhanced by use of a dynamically implemented noise margin applied with bands of gray scale values designated within the envelope of applicable gray scale maximum and minimum values. Sub-pixel cell edge transition location employs selection of transition segments (subject to the noise margin) and determination of a dynamic threshold for each relevant transition segment. The intersection of the threshold and the transition segment is then indicative of the location of the cell edge transition along a sampling line crossing the dataform. The process is repeated for successive cell edges along image data sampling lines and for additional sampling lines crossing successive rows of dataform elements. Run length data representing cell edge transition locations is constructed and usable for dataform decoding.

Claims

1. In a dataform reader, a method of locating dataform cell edge transitions in a reflected image of a dataform which includes high and low reflectance regions, comprising the steps of:

(a) acquiring a sequence of gray scale values for pixels representing a first sampling line crossing at least a first cell edge transition of said reflected image, and wherein said high and low reflectance regions are respectively represented within a high range of gray scale values and a low range of gray scale values, which are separated by a mid-range of gray scale values;

(b) selecting a transition segment having a segment magnitude value indicative of the difference in gray scale values between a specific local maximum gray scale value and a local minimum gray scale value of said sequence, which represent the ends of said segment;

(c) determining whether said transition segment meets the following criteria;

(i) said segment magnitude value exceeds a noise margin value; and

(ii) at least one of said local maximum and local minimum gray scale values is within said mid-range between said high and low ranges of gray scale values; and

(d) if said transition segment meets at least one of said step (c) criteria, locating said first cell edge transition along said first sampling line by use of said transition segment and if neither criteria is met, not utilizing said transition segment for cell edge transition location.

2. In a dataform reader, a method as in claim 1, wherein step (d) comprises:

(d)(1) determining a transition point along said transition segment as a function of said local maximum and local minimum gray scale values; and

(d)(2) locating said first cell edge transition along said first sampling line at a point corresponding to said transition point.

3. In a dataform reader, a method as in claim 2, wherein step (d)(2) includes calculating said transition point by application of a Gaussian convolution model.

4. In a dataform reader, a method as in claim 1, additionally including the step of:

(e) repeating steps (b) through (d) for second and further cell edge transitions along said first sampling line.

5. In a dataform reader, a method as in claim 4, additionally including the step of:

(f) repeating steps (a) through (e) for a second sampling line.

6. In a dataform reader, a method as in claim 5, additionally including the step of:

(g) constructing run length data representing cell edge transitions along said sampling lines.

7. In a dataform reader, a method as in claim 6, additionally including the step of:

(h) utilizing said run length data to decode at least a portion of said dataform.

8. In a dataform reader, a method as in claim 4, additionally including the step of:

(f) utilizing cell edge transition location data to decode at least a portion of said dataform.

9. In a dataform reader, a method as in claim 1, including between steps (a) and (b) the additional step of:

(x) determining that said reflected image includes dataform cell dimensions represented at less than two pixels-per-cell nominal resolution, prior to implementing steps (b) through (d).

10. In a dataform reader, a method as in claim 1, including prior to step (c) the additional step of:

(y) determining, for use in step (c), a noise margin based upon an estimate of the magnitude of noise present in said sequence of gray scale values.

11. In a dataform reader, a method as in claim 10, wherein in step (y) said noise margin is determined by analysis of histogram data.

12. In a dataform reader, a method of locating dataform cell edge transitions in a reflected image of a dataform which includes high and low reflectance regions comprising the steps of:

(a) acquiring a sequence of gray scale values for pixels representing a first sampling line crossing at least a first cell edge transition of said reflected image, and wherein said high and low reflectance regions are respectively represented within a high range of gray scale values and a low range of gray scale values, which are separated by a mid-range of such values;

(b) selecting a first window portion of said sequence;

(c) selecting borders of said high and low gray scale ranges for said first window section;

(d) selecting a transition segment having a segment magnitude value indicative of the difference in gray scale values between a specific local maximum gray scale value and a local minimum gray scale value of said sequence, which represent the ends of said segment;

(e) determining whether said transition segment meets the following criteria;

(i) said segment magnitude value exceeds a noise margin value and (ii) at least one of said local maximum and local minimum gray scale values is within said mid-range between said high and low ranges of gray scale values; and

(f) if said transition segment meets at least one of said step (e) criteria, locating said first cell edge transition along said first sampling line by use of said transition segment and if neither criteria is met, not utilizing said transition segment for cell edge transition location.

13. In a dataform reader, a method as in claim 12, wherein in step (c) the borders of said high and low gray scale ranges are determined so that the high gray scale range includes all gray scale values representative of illumination reflected from a white portion of said dataform and the low gray scale range includes all gray scale values representative of illumination reflected from a black portion of said dataform.

14. In a dataform reader, a method as in claim 12, wherein in step (c) the borders of said high and low gray scale ranges are determined so that the high gray scale range includes the highest gray scale values represented by illumination reflected from any portion of said dataform and the low gray scale range includes the lowest gray scale values represented by illumination reflected from any portion of said dataform.

15. In a dataform reader, a method as in claim 12, wherein said first window portion comprises one of:

part of said sequence; and

all of said sequence.

16. In a dataform reader, a method as in claim 12, additionally including the following step:

(g) repeating steps (d) through (f) for a second transition segment within said first window portion.

17. In a dataform reader, a method as in claim 16, additionally including the following step:

(h) repeating steps (b) through (g) for at least a second window portion.

18. In a dataform reader, a method as in claim 17, additionally including the following steps:

(j) constructing run length data representing cell edge transition locations for at least a portion of said dataform; and

(k) utilizing said run length data to decode said dataform.