Maxicode data extraction using spatial domain features

• US 5,637,849 A
• Filed: 05/31/1995
• Issued: 06/10/1997
• Est. Priority Date: 05/31/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 T.
• Assistant Examiner(s): FILIPEK, JEFFER
• Application Number:
  US08/456,113
• Time in Patent Office: 741 Days
• Field of Search: 235/494, 235/462, 235/454
• 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 MaxiCode dataform, having a bull'"'"'s eye pattern and a pattern of similarly aligned hexagonal data cells including orientation cells, comprising the steps of:

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

(b) locating the center of said bull'"'"'s eye pattern by sampling lines of pixel data to identify two intersecting diameters of said bull'"'"'s eye pattern, said diameters identified by a pixel data T-sequence pattern characteristic of a bull'"'"'s eye diameter;

(c) determining, by moment analysis of a portion of said pixel data, the orientation of at least one MaxiCode axis normal to sides of hexagonal data cells, said orientation corresponding to the derived moment of a group of data cells in side-to-side straight line alignment; and

(d) determining the alignment of the top of said MaxiCode in said image area, based upon the location of a plurality of said orientation cells relative to the location of said bull'"'"'s eye center, and extracting data from data cells of said MaxiCode by sampling said pixel data along lines aligned with a MaxiCode axis.

2. A method as in claim 1, wherein in step (c) said group of data cells consists of two side-to-side data cells of the same reflectivity.

3. A method as in claim 1, wherein in step (c) after determining orientation of one axis the orientation of the remaining two MaxiCode axes are determined based upon successive 120 degree separations from said one axis.

4. A method as in claim 1, wherein in step (d) said extraction of data proceeds row by row of data cells first from the top of the MaxiCode to the middle and then from the bottom to the middle of the MaxiCode.

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

(e) decoding said extracted data to recover information encoded in said MaxiCode.

6. A method of extracting data from a MaxiCode dataform, having a bull'"'"'s eye pattern and a pattern of similarly aligned hexagonal data cells, comprising the steps of:

(a) providing pixel data for an image area, said pixel data including representations of data cells, based on illumination reflected from said MaxiCode;

(b) locating the center of said bull'"'"'s eye pattern by sampling lines of pixel data to identify two intersecting diameters of said pattern, said diameters identified by a pattern of pixel data unique to a bull'"'"'s eye diameter;

(c) determining, from said representations of data cells and exclusive of Fourier type domain transfer processing;

the orientation of at least one normal traversal line having an alignment normal to sides of a sequence of hexagonal data cells; and

(d) extracting data from data cells of said MaxiCode by sampling said pixel data along a line aligned with one of said normal traversal lines and passing through all data cells of a row of data cells as represented in said image area.

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

(e) decoding said extracted data to recover information encoded in said MaxiCode.

8. A method as in claim 6, wherein in step (c) said normal traversal line orientation is determined by moment analysis of a portion of said pixel data, said orientation corresponding to the derived moment of a group of data cells in side-to-side straight line alignment.

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

10. A method as in claim 6, wherein in step (c) said normal trarversal line is aligned with a reference line defined by 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 data cell width, said traversal line thereby being nominally normal to sides of a sequence of dark and light hexagonal data cells.

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

(e) decoding said extracted data to recover information encoded in said MaxiCode.

12. A method as in claim 6, wherein in step (b) said pattern of pixel data is derived by determining transition points between dark and light areas 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.

13. A method of extracting data from a MaxiCode dataform, having a bull'"'"'s eye pattern and a pattern of similarly aligned hexagonal data cells, comprising the steps of:

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

(b) locating the center of said bull'"'"'s eye pattern by sampling lines of pixel data to identify two intersecting diameters of said pattern, said diameters identified by a pattern of pixel data unique to a bull'"'"'s eye diameter;

(c) determining, by moment analysis of a portion of said pixel data, the orientation of at least one MaxiCode axis with an alignment normal to sides of hexagonal data cells, said orientation corresponding to the derived moment of a group of data cells in side-to-side straight line alignment; and

(d) extracting data from data cells of said MaxiCode by sampling said pixel data along a line aligned with a MaxiCode axis and passing through all data cells of a row of data cells as represented in said image area.

14. A method as in claim 13, wherein in step (c) said group of cells consists of two side-by-side data cells of the same reflectivity.

15. A method as in claim 13, additionally comprising the following step:

(e) decoding said extracted data to recover information encoded in said MaxiCode.

16. A method as in claim 13, wherein in step (b) said pattern of pixel data is derived by determining transition points between dark and light areas 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 portions 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.