Maxicode data extraction using spatial domain features

• US 6,053,407 A
• Filed: 11/01/1996
• Issued: 04/25/2000
• Est. Priority Date: 05/31/1995
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, LLC (Zebra Technologies Corporation)
• Original Assignee: Metanetics Corporation
• Inventors: Ye, Anqi, Wang, Ynjiun P.
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): Dunn, Drew A.
• Application Number:
  US08/742,370
• Time in Patent Office: 1,271 Days
• Field of Search: 235/462, 235/463, 235/464, 235/454, 235/462.01, 235/494
• US Class Current: 235/454
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06168 the marking being a concentric barcode
• 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/1421 Circular bar codes
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore
• CPC Class Codes: G06K 7/1486 Setting the threshold-width for bar codes to be decoded
• CPC Class Codes: G06K 7/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

Prior methods of reading MaxiCode dataforms have been subject to reduced resolution image scaling and processing and speed constraints of Fourier transform computations. Described spatial domain data extraction methods provide bull'"'"'s eye center location by T-sequence pixel pattern analysis, axis identification by moment analysis of data cell pairs, and integral width square wave analysis of illumination transitions to avoid reading-line cell fragmentation. The center and top of a MaxiCode are identified in high-resolution pixel data, without scaling reduction or Fourier type frequency domain processing. Data is extracted serially from rows of data cells by sampling along lines of pixels aligned by fragmentation analysis so as to traverse complete rows of data cells. Dynamic thresholding accurately defines illumination value transitions between adjacent linear groups of data cells, each group consisting of one or more data cells of the same reflectivity. Application of disclosed methods to other types of dataforms is described.

Claims

1. A method of extracting data from a dataform having a pattern of rows of similarly aligned dark and light data cells of a regular polygon shape each having the same width between two parallel sides, comprising the steps of:

(a) providing pixel data for an image area, said pixel data representative of illumination reflected from said data cells of a regular polygon shape; and

(b) sampling said pixel data to identify a traversal line of pixel data characterized by illumination value transitions spaced along said traversal line at integral multiples of said data cell width, said traversal line thereby being nominally normal to sides of a sequence of dark and light data cells.

2. A method as in claim 1, additionally comprising the following step:

(c) extracting data from a plurality of said data cells by sampling said pixel data along a line having an orientation determined by reference to the orientation of said traversal line.

3. A method as in claim 2, additionally comprising the following step:

(d) decoding said extracted data to recover information encoded in said dataform.

4. A method as in claim 1, wherein in step (b) said transitions are transition points between dark and light areas determined by dynamic thresholding of transitional pixel data by steps comprising the following:

(w) determining a segment magnitude representing the difference between adjacent high and low gray scale values;

(x) subdividing the said gray scale into at least two sub-spectrum portions;

(y) designating a noise threshold for each said sub-spectrum portion of said gray scale; and

(z) utilizing said segment magnitude as representative of an illumination value transition on a line of pixel data, provided said segment magnitude exceeds a noise threshold applicable to said segment.

5. A method as in claim 1, wherein said dataform is a MaxiCode type of dataform.

6. A method as in claim 1, wherein step (b) additionally comprises determining the orientation of a dataform axis having one of the following orientations:

aligned with and parallel to said traversal line;

aligned with said traversal line at an angular separation of an integral multiple of 60 degrees.

7. A method as in claim 6, additionally comprising the following step:

(c) extracting data from a plurality of said data cells by sampling said pixel data along a line having an orientation determined by reference to the orientation of said traversal line.

8. A method of extracting data from a dataform having a pattern of rows of similarly aligned polygonal data cells of a regular polygon shape and of differing reflectivity values, comprising the steps of:

(a) providing pixel data for an image area, said pixel data representative of illumination reflected from said data cells of a regular polygon shape;

(b) determining the derived moment of a contiguous group of data cells of the same reflectivity value, by moment analysis of a portion of said pixel data; and

(c) determining the orientation of at least one dataform axis, said orientation corresponding to said derived moment.

9. A method as in claim 8, wherein in step (c) said group of data cells consists of two data cells of the same reflectivity.

10. A method as in claim 8, additionally comprising the following step:

(d) extracting data from a plurality of said data cells by sampling said pixel data along a line having an orientation determined by reference to the orientation of said dataform axis.

11. A method of extracting data from a dataform having a pattern of rows of similarly aligned polygonal data cells of a regular polygon shape and of differing reflectivity values, comprising the steps of:

(a) providing pixel data for an image area, said pixel data representative of illumination reflected from said data cells;

(b) identifying a reference line defined by moment analysis of a portion of said pixel data, based on the derived moment of a contiguous group of data cells of the same reflectivity value; and

(c) determining the orientation of at least one dataform axis, said axis aligned with said reference line.

12. A method as in claim 11, wherein in step (b) said group of data cells consists of two data cells of the same reflectivity.

13. A method as in claim 11, wherein said dataform is a MaxiCode type of dataform.

14. A method as in claim 11, wherein step (c) comprises determining the orientation of said dataform axis as one of the following orientations:

aligned with and parallel to said reference line;

aligned with said reference line at an angular separation of an integral multiple of 60 degrees.

15. A method as in claim 11, wherein step (b) comprises determining the orientation of said reference line as the derived moment of a group of data cells in side-to-side straight line alignment.

16. A method as in claim 11, additionally comprising the following step:

(d) extracting data from a plurality of said data cells by sampling said pixel data along a line having an orientation determined by reference to the orientation of said dataform axis.

17. A method as in claim 16, wherein step (d) comprises extracting data by determining spacings of illumination value transitions between data cell groups along said sampling line, each said data cell group consisting of one or more contiguous data cells of similar reflectivity value.