Enhanced matrix symbol error correction method

• US 10,235,547 B2
• Filed: 01/26/2016
• Issued: 03/19/2019
• Est. Priority Date: 01/26/2016
• Status: Active Grant

• Current Assignee: Hand Held Products Incorporated (Honeywell International Inc.)
• Original Assignee: Hand Held Products Incorporated (Honeywell International Inc.)
• Inventors: Ackley, H. Sprague
• Primary Examiner(s): Vallecillo, Kyle
• Application Number:
  US15/006,561
• Publication Number:
  US 20170213064A1
• Time in Patent Office: 1,148 Days
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/1473 error correction

Abstract

A system and method for error correction for machine-readable symbols having data codewords, and having error correction (EC) codewords derived from the data codewords and redundantly indicating the location and data contents of the data codewords. The symbols use Reed-Solomon (RS) error correction to retrieve damaged codewords. RS error correction normally requires two EC codewords to identify both the location and data contents of a data codeword. The present system and method performs optical contrast analysis on the codewords, identifying those codewords with the lowest contrast levels (that is, the least difference between the reflectance of the black or white cells and the black/white threshold). Codewords with the lowest contrast levels are flagged as optically ambiguous, thereby marking, in the EC equations, the locations of the codewords most like to be in error. As a result, only a single EC codeword is required to retrieve the data for a flagged data codeword.

Claims

1. A method of error correction for a two-dimensional (2D) symbol designed for optical reading by a symbol reader, the symbol having a plurality of cells of a designated first color comprising first color cells and a designated second color comprising second color cells which cells are arranged in a two-dimensional matrix;

the symbol further having a plurality of codewords at specified locations within the symbol, each codeword comprising at least one specified group of cells;

the method comprising;

optically reading, by an optical scanner of the symbol reader, the plurality of codewords in the symbol, the plurality of codewords comprising a first plurality of data codewords storing data indicated by a pattern of the first and second color cells in the codeword, and a second plurality of error-correction (EC) codewords derived from the data codewords and providing redundancy for the data represented by the data codewords;

determining, via a hardware processor of the symbol reader, a location for a data codeword of the first plurality of data codewords which is optically ambiguous, the determining comprising

selecting the data codeword based on a standards-established set of codeword locations within the symbol; and

then performing a contrast analysis on the selected data codeword, wherein the contrast analysis identifies a minimum interior contrast level for the selected data codeword, and the performing of the contrast analysis comprises

determining reflectance of first color cells of the first plurality of cells of the selected data codeword, and

determining reflectance of second color cells of the second plurality of cells of the selected data codeword;

identifying a respective minimum interior contrast level for each codeword in the symbol; and

flagging as optically ambiguous a plurality of codewords with the lowest minimum interior contrast levels among all the codewords in the symbol, up to a specified number of codewords;

marking via the hardware processor, in an error correction (EC) equation stored in a memory of the symbol reader, the location of the optically ambiguous data codeword within the symbol; and

executing, via the hardware processor, the EC equation to correct errors in the read plurality of codewords.

2. The method of claim 1, wherein determining the location for the data codeword which is optically ambiguous comprises:

determining that the selected data codeword displays a level of contrast between the first color cells and the second color cells which is insufficient for an unambiguous decoding of the selected data codeword by the symbol reader.

3. The method of claim 1, wherein performing the contrast analysis on the selected data codeword comprises:

(i) determining a dark/light threshold level, wherein the dark/light threshold level is indicative of a reflectance above which a cell is assessed as being of the first color and below which a cell is assessed as being of the second color;

(ii) determining a level of difference between the reflectance of each cell of the selected data codeword and the dark/light threshold level; and

(iii) determining the minimum interior contrast level for the selected data codeword by determining, among all the cells within the selected data codeword, a specific cell with a lowest level of difference between the reflectance of the specific cell and the dark/light threshold level.

4. The method of claim 3, further comprising:

ranking each codeword of the symbol for a respective level of optical ambiguity, wherein each codeword is ranked for its respective level of optical ambiguity based on the minimum interior contrast level of that codeword as compared with the minimum interior contrast levels of all the other codewords in the symbol, wherein;

a first minimum interior contrast level of a first codeword is compared with a second minimum interior contrast level of a second codeword, the codeword of the two with the lower minimum interior contrast level being assigned a higher level of optical ambiguity.

5. The method of claim 3, further comprising:

(i) determining a local dark/light threshold level for a specific cell, wherein the local dark/light threshold level for the specific cell is determined based on a plurality of cells local to the specific cell;

(ii) determining a level of difference between the reflectance of each cell of the selected data codeword and each cell'"'"'s local dark/light threshold level; and

(iii) determining the minimum interior contrast level for the selected data codeword by determining, among all the cells within the selected data codeword, a specific cell with a lowest level of difference between the reflectance of the specific cell and the cell'"'"'s local dark/light threshold level.

6. An electronic system that acquires a machine-readable two-dimensional (2D) symbol designed for optical reading by the system, the symbol having a plurality of cells of a designated first color comprising first color cells and a designated second color comprising second color cells which cells are arranged in a two-dimensional matrix;

the symbol further having a plurality of codewords at specified locations within the symbol, each codeword comprising at least one specified group of cells;

the plurality of codewords comprising a first plurality of data codewords storing data indicated by a pattern of the first and second color cells in the codeword, and a second plurality of error-correction (EC) codewords derived from the data codewords and providing redundancy for the data represented by the data codewords, the electronic system comprising;

an optical scanner configured to optically receive the plurality of cells in the symbol and to convert the cell pattern of the symbol into an electrical pattern subject to electronic storage and computational analysis;

a memory configured to store the electrical pattern of the symbol, and an error-correction (EC) equation; and

a hardware processor which is configured to;

determine a location for a data codeword of the first plurality of data codewords which is optically ambiguous, comprising the hardware processor being configured to determine the location for the data codeword which is optically ambiguous by

selecting the data codeword based on a standards-established set of codeword locations within the symbol, said standards-established set being stored in the memory of the electronic system, and

then performing a contrast analysis on the selected data codeword, wherein the contrast analysis identifies a minimum interior contrast level for the selected data codeword, and the performing of the contrast analysis comprises

determining reflectance of first color cells of the first plurality of cells of the selected data codeword, and

determining reflectance of second color cells of the second plurality of cells of the selected data codeword;

identify a respective minimum interior contrast level for each codeword in the symbol;

flag as optically ambiguous a plurality of codewords with the lowest minimum interior contrast levels among all the codewords in the symbol, up to a specified number of codewords;

mark in the error correction equation the location of the optically ambiguous data codeword within the symbol; and

execute the EC equation to correct errors in the read plurality of codewords.

7. The electronic system of claim 6, wherein the hardware processor is further configured to determine the location for the data codeword which is optically ambiguous by:

determining that the selected data codeword displays a level of contrast between the first color and the second color which is insufficient for an unambiguous decoding of the selected data codeword by the electronic system.

8. The electronic system of claim 6, wherein to perform the contrast analysis on the selected data codeword the hardware processor is further configured to:

(i) determine a dark/light threshold level, wherein the dark/light threshold level is indicative of a reflectance above which a cell is assessed as being of the first color and below which a cell is assessed as being of the second color;

(ii) determine a level of difference between the reflectance of each cell of the selected data codeword and the dark/light threshold level; and

(iii) determine the minimum interior contrast level for the selected data codeword by determining, among all the cells within the selected data codeword, a specific cell with a lowest level of difference between the reflectance of the specific cell and the dark/light threshold level.

9. The electronic system of claim 8, wherein the hardware processor is further configured to:

rank each codeword of the symbol for a level of optical ambiguity, wherein each codeword of the symbol is ranked for the level of optical ambiguity based on the minimum interior contrast level of that codeword as compared with the minimum interior contrast levels of all the other codewords in the symbol, wherein;

a first minimum interior contrast level of a first codeword is compared with a second minimum interior contrast level of a second codeword, the codeword of the two with the lower minimum interior contrast level being assigned a higher level of optical ambiguity.

10. The electronic system of claim 8, wherein the hardware processor is further configured to:

(i) determine a local dark/light threshold level for a specific cell, wherein the local dark/light threshold level for the specific cell is determined based on a plurality of cells local to the specific cell;

(ii) determine a level of difference between the reflectance of each cell of the data codeword and each cell'"'"'s local dark/light threshold level; and

(iii) determine the minimum interior contrast level for the data codeword by determining, among all the cells within the data codeword, a specific cell with a lowest level of difference between the reflectance of the specific cell and the cell'"'"'s local dark/light threshold level.

11. The electronic system of claim 6, wherein the error-correction equation stored in the memory comprises Reed-Solomon error correction equations.

12. A computer-readable, non-transitory storage medium storing instructions that, when executed by a hardware processor of a symbol reader, causes the hardware processor to execute a method of error correction for a two-dimensional (2D) symbol designed for optical reading by the symbol reader, the symbol having a plurality of cells of a designated first color comprising first color cells and a designated second color comprising second color cells which cells are arranged in a two-dimensional matrix;

the symbol further having a plurality of codewords at specified locations within the symbol, each codeword comprising at least one specified group of cells;

the plurality of codewords comprising a first plurality of data codewords storing data indicated by a pattern of the first and second color cells in the codeword, and a second plurality of error-correction (EC) codewords derived from the data codewords and providing redundancy for the data represented by the data codewords;

the method comprising;

optically reading, by an optical scanner of the symbol reader, the plurality of codewords in the symbol;

determining a location for a data codeword of the first plurality of data codewords which is optically ambiguous, the determining comprising

selecting the data codeword based on a standards-established set of codeword locations within the symbol; and

then performing a contrast analysis on the selected data codeword, wherein the contrast analysis identifies a minimum interior contrast level for the selected data codeword, and the performing of the contrast analysis comprises

determining reflectance of first color cells of the first plurality of cells of the selected data codeword, and

determining reflectance of second color cells of the second plurality of cells of the selected data codeword;

identifying a respective minimum interior contrast level for each codeword in the symbol;

flagging as optically ambiguous a plurality of codewords with the lowest minimum interior contrast levels among all the codewords in the symbol, up to a specified number of codewords;

marking in an error correction (EC) equation the location of the optically ambiguous data codeword within the symbol; and

executing the EC equation to correct errors in the read plurality of codewords.

13. The computer-readable, non-transitory storage medium of claim 12, wherein determining the location for the data codeword which is optically ambiguous comprises:

determining that the selected data codeword displays a level of contrast between the first color and the second color which is insufficient for an unambiguous decoding of the selected data codeword by the symbol reader.

14. The computer-readable, non-transitory storage medium of claim 12, wherein performing the contrast analysis on the selected data codeword comprises:

(i) determining a dark/light threshold level, wherein the dark/light threshold level is indicative of a reflectance above which a cell is assessed as being of the first color and below which a cell is assessed as being of the second color;

(ii) determining a level of difference between the reflectance of each cell of the selected data codeword and the dark/light threshold level; and

(iii) determining the minimum interior contrast level for the selected data codeword by determining, among all the cells within the selected data codeword, a specific cell with a lowest level of difference between the reflectance of the specific cell and the dark/light threshold level.