System for encoding and decoding data in machine readable graphic form

• US 5,243,655 A
• Filed: 03/16/1992
• Issued: 09/07/1993
• Est. Priority Date: 01/05/1990
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Inventors: Wang, Ynjiun P.
• Primary Examiner(s): CAIN, DAVID C
• Application Number:
  US07/851,505
• Time in Patent Office: 540 Days
• Field of Search: 380/51, 380/55, 380/3, 380/59, 235/462
• US Class Current: 380/51
• CPC Class Codes: G06F 3/002 Specific input/output arrangements not covered by G06F3/01 - G06F3/16 other optical apparatus G02B27/00
• CPC Class Codes: G06K 1/126 by photographic or thermographic registration recording apparatus for measuring instruments G01D15/00
• CPC Class Codes: G06K 17/00 Methods or arrangements for effecting co-operative working between equipments covered by two or more of main groups G06K1/00 - G06K15/00, e.g. automatic card files incorporating conveying and reading operations
• CPC Class Codes: G06K 17/0016 Selecting or retrieving of images by means of their associated code-marks, e.g. coded microfilm or microfiche microfilm reading G03B21/11; computers therefor G06F16/00; teaching devices G09B5/02; accessing record carriers G11B27/002; static digital stores using optical elements G11C13/04; intermediate storage of facsimile picture signals H04N1/21
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 2019/06253 for a specific application
• 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/1417 2D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• 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

A system for representing and recognizing data in machine readable graphic image form in which data to be encoded is entered into the system and a processor encodes the data into a two-dimensional bar code symbol and generates transfer drive signals representative of the symbol. A transferring device such as a printer transfers an image of the two-dimensional bar code symbol onto a carrier such as a card or paper document in response to the transfer drive signals. A recognition device converts the image on the carrier into electrical signals representative of the symbol by scanning the image. A low-level decoder decodes the signals by decoding each scan line into a vector of codeword values corresponding to the codewords in the two-dimensional bar code symbol, assigning a row number to each of the codeword values, and then filling in a two-dimensional matrix with the codeword values. A high-level decoder further decodes the codeword values into data which can then be output for processing or use.

Claims

1. An apparatus for decoding a two-dimensional bar code symbol, the bar code symbol including a plurality of ordered, adjacent rows of codewords of bar-coded information from a set of codewords, the set of codewords being partitioned into at least three mutually exclusive clusters, each row in the symbol having at least one row indicator codeword and containing only codewords from a cluster different from the codewords in an adjacent row, comprising:

means for scanning the two-dimensional bar code symbol to produce scan lines of data representing the bar-coded information in the codewords of the symbol;

means for decoding a scan line of data into a vector of codeword values corresponding to the codewords that were scanned, at least one of the codeword values being for a row indicator codeword;

means for assigning a row number to each of the codeword values in the vector based on the value of the row indicator codeword and the cluster of the codeword; and

means for filling in a codeword matrix with the codeword values in the vector according to their assigned row numbers.

2. The apparatus of claim 1, wherein the row indicator codewords contain information regarding the number of rows in the symbol and the number of codewords in each row, and wherein the apparatus further comprises

means for decoding a scan line of data to obtain a codeword value for a row indicator codeword, and

means for determining one of the number of rows and the number of codewords in each row from the codeword value for the row indicator codeword.

3. The apparatus of claim 2, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, wherein the means for decoding a scan line of data to obtain a codeword value for a row indicator codeword includes means for locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

4. The apparatus of claim 1, wherein the symbol contains at least one error correction codeword and the row indicator codewords contain information regarding the number of rows in the symbol, the number of codewords in each row, and the number of error correction codewords, and wherein the apparatus further comprises

means for decoding a scan line of data to obtain a codeword value for a row indicator codeword,

means for determining a value for one of the number of rows, the number of codewords in each row, and the number of error correction codewords from the codeword value for the row indicator codeword,

means for adjusting a confidence weight for a corresponding one of the number of rows, the number of codewords in each row, and the number of error correction codewords based on the value determined in the preceding step and a previous value obtained by decoding a row indicator codeword, and

means for initializing the codeword matrix when the confidence weights for the number of rows, the number of codewords in each row, and the number of error correction codewords all exceed a predetermined threshold.

5. The apparatus of claim 4, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, and wherein the means for decoding a scan line of data to obtain a codeword value for row indicator codeword includes means for locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

6. The apparatus of claim 1, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, and wherein the means for decoding a scan line of data into a vector of codeword values includes means for locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

7. The apparatus of claim 1, further comprising

means for assigning a confidence weight to each of the codeword values in the vector, and

means for adjusting a confidence weight of each of the corresponding codeword values in the matrix based on the codeword value in the vector and a current value of each of the corresponding codeword values in the matrix.

8. The apparatus of claim 1, wherein the symbol contains at least one error correction codeword, and wherein the apparatus further comprises

means for locating in the matrix the codeword values for any codewords that have not been successfully decoded, and

means for correcting any erroneous codeword values in the codeword matrix using the error correction codeword.

9. A method for decoding a two-dimensional bar code symbol, the bar code symbol including a plurality of ordered, adjacent rows of codewords of bar-coded information from a set of codewords, the set of codewords being partitioned into at least three mutually exclusive clusters, each row in the symbol having at least one row indicator codeword and containing only codewords from a cluster different from the codewords in an adjacent row, comprising the steps of:

scanning the two-dimensional bar code symbol to produce scan lines of data representing the bar-coded information in the codewords of the symbol;

decoding a scan line of data into a vector of codeword values corresponding to the codewords that were scanned, at least one of the codeword values being for a row indicator codeword;

assigning a row number to each of the codeword values in the vector based on the value of the row indicator codeword and the cluster of the codeword; and

filling in a codeword matrix with the codeword values in the vector according to their assigned row numbers.

10. The method of claim 9, wherein the row indicator codewords contain information regarding the number of rows in the symbol and the number of codewords in each row, and wherein the method further comprises the steps of

decoding a scan line of data to obtain a codeword value for a row indicator codeword, and

determining one of the number of rows and the number of codewords in each row from the codeword value for the row indicator codeword.

11. The method of claim 10, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data to obtain a codeword value for a row indicator codeword includes the substep of locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

12. The method of claim 9, wherein the symbol contains at least one error correction codeword and the row indicator codewords contain information regarding the number of rows in the symbol, the number of codewords in each row, and the number of error correction codewords, and wherein the method further comprises the steps of

decoding a scan line of data to obtain a codeword value for a row indicator codeword,

determining a value for one of the number of rows, the number of codewords in each row, and the number of error correction codewords from the codeword value for the row indicator codeword,

adjusting a confidence weight for a corresponding one of the number of rows, the number of codewords in each row, and the number of error correction codewords based on the value determined in the preceding step and a previous value obtained by decoding a row indicator codeword, and

initializing the codeword matrix when the confidence weights for the number of rows, the number of codewords in each row, and the number of error correction codewords all exceed a predetermined threshold.

13. The method of claim 12, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data to obtain a codeword value for a row indicator codeword includes the substep of locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

14. The method of claim 9, wherein each row of the symbol contains at least one of a start pattern and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data into a vector of codeword values includes the substep of locating a sequence of data in the scan line corresponding to one of the start pattern and the stop pattern.

15. The method of claim 9, further comprising the steps of

assigning a confidence weight to each of the codeword values in the vector,

adjusting a confidence weight of each of the corresponding codeword values in the matrix based on the codeword value in the vector and a current value of each of the corresponding codeword values in the matrix.

16. The method of claim 9, wherein the symbol contains at least one error correction codeword, and wherein the method further comprises the steps of

locating in the matrix the codeword values for any codewords that have not been successfully decoded, and

correcting any erroneous codeword values in the codeword matrix using the error correction codeword.

17. A system for representing and recognizing data on a record carrier in the form of a machine readable two-dimensional bar code structure comprising:

encoding means including;

means for entering data in said encoding means,

processing means for encoding said data into a two-dimensional bar code structure and for generating transfer drive signals, the bar code structure including a plurality of ordered, adjacent rows of codewords of bar-coded information from a set of codewords, the set of codewords being partitioned into at least three mutually exclusive clusters, each row in the two-dimensional bar code structure having at least one row indicator codeword and containing only codewords from a cluster different from the codewords in an adjacent row,

means for transferring an image of the two-dimensional bar code structure onto a portable record carrier in response to said transfer drive signals; and

recognition means including;

means for scanning the image of the two-dimensional bar code structure to produce scan lines of data representing the bar-coded information in the codewords of the two-dimensional bar code structure,

means for decoding a scan line of data into a vector of codeword values corresponding to the codewords that were scanned, at least one of the codeword values being for a row indicator codeword,

means for assigning a row number to each of the codeword values in the vector based on the values of the row indicator codeword and the cluster of the codeword, and

means for filling in a codeword matrix with the codeword values in the vector according to their assigned row numbers.

18. The system of claim 17, wherein the row indicator codewords contain information regarding the number of rows in the two-dimensional bar code structure and the number of codewords in each row, and wherein the recognition means further includes

means for decoding a scan line of data to obtain a codeword value for a row indicator codeword, and

means for determining one of the number of rows and the number of codewords in each row from the codeword value for the row indicator codeword.

19. The system of claim 18, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the means for decoding a scan line of data to obtain a codeword value for a row indicator codeword includes means for locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

20. The system of claim 17, wherein the two-dimensional bar code structure contains at least one error correction codeword and the row indicator codewords contain information regarding the number of rows in the two-dimensional bar code structure, the number of codewords in each row, and the number of error correction codewords, and wherein the recognition means further includes

means for decoding a scan line of data to obtain a codeword value for a row indicator codeword,

means for determining a value for one of the number of rows, the number of codewords in each row, and the number of error correction codewords from the codeword value for the row indicator codeword,

means for adjusting a confidence weight for a corresponding one of the number of rows, the number of codewords in each row, and the number of error correction codewords based on the value determined in the preceding step and a previous value obtained by decoding a row indicator codeword, and

means for initializing the codeword matrix when the confidence weights for the number of rows, the number of codewords in each row, and the number of error correction codewords all exceed a predetermined threshold.

21. The system of claim 20, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the means for decoding a scan line of data to obtain a codeword value for a row indicator codeword includes means for locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

22. The system of claim 17, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the means for decoding a scan line of data to obtain a codeword value for a row indicator codeword includes means for locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

23. The system of claim 17, wherein the recognition means further includes

means for assigning a confidence weight to each of the codeword values in the vector, and

for adjusting a confidence weight of each of the corresponding codeword values in the matrix based on the codeword value in the vector and a current value of each of the corresponding codeword values in the matrix.

24. The system of claim 17, wherein the two-dimensional bar code structure contains at least one error correction codeword, and wherein the recognition means further includes

means for locating in the matrix the codeword values for any codewords that have not been successfully decoded, and

means for correcting any erroneous codeword values in the codeword matrix using the error correction codeword.

25. A method for representing and recognizing data on a record carrier in the form of a machine readable two-dimensional bar code structure comprising the steps of:

entering said data into an encoding station;

encoding said data into a two-dimensional bar code structure, the two-dimensional bar code structure including a plurality of ordered, adjacent rows of codewords of bar-coded information from a set of codewords, the set of codewords being partitioned into at least three mutually exclusive clusters, each row in the two-dimensional bar code structure having at least one row indicator codeword and containing only codewords from a cluster different from the codewords in an adjacent row,

transferring an image of the two-dimensional bar code structure onto a portable record carrier;

scanning the image of the two-dimensional bar code structure to produce scan lines of data representing the bar-coded information in the codewords;

decoding a scan line of data into a vector of codeword values corresponding to the codewords that were scanned, at least one of the codeword values being for a row indicator codeword;

assigning a row number to each of the codeword values in the vector based on the value of the row indicator codeword and the cluster of the codeword; and

filling in a codeword matrix with the codeword values in the vector according to their assigned row numbers.

26. The method of claim 25, wherein the row indicator codewords contain information regarding the number of rows in the two-dimensional bar code structure and the number of codewords in each row, and wherein the method further comprises the steps of

decoding a scan line of data to obtain a codeword value for a row indicator codeword, and

determining one of the number of rows and the number of codewords in each row from the codeword value for the row indicator codeword.

27. The method of claim 26, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data to obtain a codeword value for a row indicator codeword includes the substep of locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

28. The method of claim 25, wherein the two-dimensional bar code structure contains at least one error correction codeword and the row indicator codewords contain information regarding the number of rows in the two-dimensional bar code structure, the number of codewords in each row, and the number of error correction codewords, and wherein the method further comprises the steps of

decoding a scan line of data to obtain a codeword value for a row indicator codeword,

determining a value for one of the number of rows, the number of codewords in each row, and the number of error correction codewords from the codeword value for the row indicator codeword,

adjusting a confidence weight for a corresponding one of the number of rows, the number of codewords in each row, and the number of error correction codewords based on the value determined in the preceding step and a previous value obtained by decoding a row indicator codeword, and

initializing the codeword matrix when the confidence weights for the number of rows, the number of codewords in each row, and the number of error correction codewords all exceed a predetermined threshold.

29. The method of claim 25, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data to obtain a codeword value for a row indicator codeword includes the substep of locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

30. The method of claim 25, wherein each row of the two-dimensional bar code structure contains a start and a stop pattern of bar-coded information, and wherein the step of decoding a scan line of data into a vector of codeword values includes the substep of locating a sequence of data in the scan line corresponding to one of the start and the stop pattern.

31. The method of claim 25, further comprising the steps of

assigning a confidence weight to each of the codeword values in the vector,

adjusting a confidence weight of each of the corresponding codeword values in the matrix based on the codeword value in the vector and a current value of each of the corresponding codeword values in the matrix.

32. The method of claim 25, wherein the two-dimensional bar code structure contains at least one error correction codeword, and wherein the method further comprises the steps of

locating in the matrix the codeword values for any codewords that have not been successfully decoded, and

correcting any erroneous codeword values in the codeword matrix using the error correction codeword.