Patent Description:
Machine-readable symbols provide a means for encoding information in a compact printed form (or embossed form) which can be scanned and then interpreted by an optical-based symbol detector. Such machine readable symbols are often attached to (or impressed upon) product packaging, food products, general consumer items, machine parts, equipment, and other manufactured items for purposes of machine-based identification and tracking.

One exemplary type of machine-readable symbol is a bar code that employs a series of bars and white spaces vertically oriented along a single row. Groups of bars and spaces correspond to a codeword. The codeword is associated with an alpha-numeric symbol, one or more numeric digits, or other symbol functionality.

To facilitate encoding of greater amounts of information into a single machine-readable symbol, two-dimensional bar codes have been devised. These are also commonly referred to as stacked, matrix and/or area bar codes. Examples of such two-dimensional symbologies include Data Matrix, Code One, PDF-<NUM>, MaxiCode, QR Code, and Aztec Code. 2D matrix symbologies employ arrangements of regular polygon-shaped cells (also called elements or modules) where the center to center distance of adjacent elements is uniform. Typically, the polygon-shaped cells are squares. The specific arrangement of the cells in 2D matrix symbologies represents data characters and/or symbology functions.

As an example of a 2D matrix symbol technology, a Data Matrix code is a two-dimensional matrix barcode consisting of high-contrast "cells" (typically black and white cells) or modules arranged in either a square or rectangular pattern. The information to be encoded can be text or numeric data, or control symbols. The usual data size ranges from a few bytes up to <NUM> bytes. Specific, designated, standardized groups of cells -- typically eight cells -- are each referred to as a "symbol character. " The symbol characters have values which are referred to as "codewords. " With a black cell interpreted as a <NUM> (zero) and a white cell interpreted as a <NUM> (one), an eight-cell codeword can code for numbers <NUM> through <NUM>; in turn, these numeric values can be associated with alphanumeric symbols through standard codes such as ASCII, EBCDIC, or variations thereon, or other functionality.

The codewords -- that is, the designated groups of cells in a symbol -- have specific, standardized positions within the overall symbol. The interpretation of a symbol in a given context (for example, for a given manufacturer and/or a given product) therefore depends on the codewords within the symbol; and in particular, the interpretation depends on both: (i) the contents of each codeword (that is, the pattern of cells in each codeword), and (ii) the placement or position of each codeword in the symbol.

Typically, for sequential alphanumeric data (for example, a product identification number or a street address), each sequential data character is assigned to the symbols of a codeword in a standardized order. For example, the order may be left-to-right along the rows of the symbol, or according to a standardized diagonal pattern of placement. Because the codewords have specific, standards-specified placements within a symbol -- and because no information about the placement is contained in the symbol character -- the symbols may also be referred to as "matrix symbols" or "matrix symbology barcodes.

Bar code readers are employed to read the matrix symbols using a variety of optical scanning electronics and methods. Ideally, the machine-readable symbols which are scanned by a bar code reader are in perfect condition, with all of the cells of consistent, uniform size; each cell being fully filled with either total black or total white; and the contrast between black and white cells being <NUM>%.

In real, practical application the machine-readable symbols which are scanned by a bar code reader may be imperfect. They may be smudged by external substances (grease, dirt, or other chemicals in the environment); or the surface on which the symbols were printed may be stretched, compressed, or torn; or the printing process itself may be flawed (for example, due to low ink levels in a printer, clogged printheads, etc.). The defects in actual symbols may introduce errors in the machine reading process.

To address these practical problems, error correction techniques are often used to increase reliability: even if one or more cells are damaged so as to make a codeword unreadable, the unreadable codeword can be recovered through the error-correction process, and the overall message of the symbol can still be read.

For example, machine-readable symbols based on the Data Matrix ECC <NUM> standard employ Reed-Solomon codes for error and erasure recovery. ECC <NUM> allows the routine reconstruction of the entire encoded data string when the symbol has sustained <NUM>% damage (assuming the matrix can still be accurately located).

Under this standard, approximately half the codewords in a symbol are used directly for the data to be represented, and approximately half the codewords are used for error correction. The error-correction (EC) symbols are calculated using a mathematical tool know as the Reed-Solomon algorithm. The codewords for the symbol are the input to the Reed-Solomon algorithm, and the error-correction (EC) symbols are the output of the Reed-Solomon algorithm. The complete machine-readable symbol includes both the data codewords and the EC codewords.

For a given symbol format (such as Data Matrix, PDF-<NUM>, QR-Code, Aztec Code, and others), and for a given size of the symbol matrix, there are a fixed, designated numbers of EC codewords. To recover any one, particular damaged (unreadable) codeword, two things must be recovered: (i) the location of the damaged data codeword within the symbol, and (ii) the contents (the bit pattern) of the damaged data codeword. In turn, to recover both the location and the bit pattern for a single codeword requires two of the available EC symbols. It follows that if a machine-readable symbol has two damaged codewords, four EC codewords are required to recover the full symbol. Generally, if a symbol has "N" damaged codewords, then <NUM> * N EC codewords are required to recover the full symbol.

The number of EC codewords in a symbol is limited. This places a limit on the number of damaged, unreadable data codewords which can be recovered. Generally with error correction techniques, and using present methods, the number of damaged data codewords which can be recovered is half the total number of EC codewords. For example, in a Data Matrix symbol with 16x16 cells, the total number of EC codewords is <NUM>. This means that at most <NUM> damaged data codewords can be recovered. If more than <NUM> of the data codewords are damaged, the complete symbol may be unreadable.

However, if the location of the data codeword in error is already known, then only one EC codeword is needed to correct the error. This technique is called "erasure decoding". Unfortunately, in Matrix Code symbols generally, the location of the errors is not known.

Therefore, there exists a need for a system and method for recovering more damaged data codewords in a symbol than may be recovered based on only the error-correcting symbols by themselves. More particularly, what is needed is a system and method for determining the location of a damaged or erroneous data codeword, independent of the information stored in the EC codewords.

<CIT> is reflected in the preamble of claim <NUM>.

Accordingly, in one aspect, the present invention solves the problem of not being able to use erasure decoding with matrix symbologies by evaluating the gray-level information available in the scanner and keeping track of those codewords with the least contrast difference. The decoder then utilizes erasure decoding on these least-contrast codewords. Since the location of the erroneous data codewords has been estimated via the contrast detection, only one EC codeword is required to recover the data in the damaged codeword. (And so, only one EC codeword is required to fully recover the damaged data codeword, both its location and data.

Because only one EC codeword is required instead of two, more EC codewords remain unused and available for decoding other possible errors. This increases the total number of data codewords that can be corrected. This is particularly useful in applications where symbols get dirty (e.g. automotive assembly), damaged (e.g. supply chain), have specular components (e.g. direct part marking (DPM)) and need to be scanned over a greater range (e.g. all applications).

The algorithm of the present invention has the effect of nearly doubling the number of codewords that can be corrected in matrix symbology decodes, thereby greatly improving the performance over what is currently available.

The foregoing illustrative summary, as well as other exemplary objectives and/or advantages of the invention, and the manner in which the same are accomplished, are further explained within the following detailed description and its accompanying drawings.

In the following description, certain specific details are set forth in order to provide a thorough understanding of various embodiments. However, one skilled in the art will understand that the invention may be practiced without these details. In other instances, well-known structures associated with imagers, scanners, and/or other devices operable to read machine-readable symbols have not been shown or described in detail to avoid unnecessarily obscuring descriptions of the embodiments.

Unless the context requires otherwise, throughout the specification and claims which follow, the word "comprise" and variations thereof, such as, "comprises" and "comprising" are to be construed in an open sense, that is as "including, but not limited to.

The headings provided herein are for convenience only and do not interpret the scope or meaning of the claimed invention.

The present system and method embraces devices designed to read machine-readable symbols.

In an exemplary embodiment, such a device may be a hand-held scanner. <FIG> is a perspective view of an exemplary hand-held symbol reader <NUM> acquiring data from a machine-readable symbol <NUM>.

The machine-readable symbol <NUM> is affixed to a package <NUM> or the like such that the user points the hand-held symbol reader <NUM> towards the machine-readable symbol <NUM>. The symbol reader <NUM> may be a line scanner operable to emit and sweep a narrow beam of electromagnetic energy across a field-of-view <NUM> over two-dimensional (2D) machine-readable symbol <NUM>. In other embodiments, an aperture means, mirror, lens or the like is adjusted to sweep across a symbol line to receive returning electromagnetic energy from a relatively small portion (e.g., cell) of the machine-readable symbol, which is detected by an optical detector system.

In yet other embodiments, a 2D array symbol reader acquires a captured image of the machine-readable symbol (and a suitable region of quiet area around the machine-readable symbol). For the present system and method, which relies upon a contrast analysis of the cells within the symbol <NUM>, the acquisition of a captured image of the symbol may be a preferred method of operation for the symbol reader <NUM>. Suitable image processing hardware <NUM> and software running on processors <NUM>, <NUM> are used to deconstruct the capture image to determine the data bits represented by the cells, and to perform the contrast analysis of the present system and method (see <FIG> below).

The machine-readable symbol reader <NUM> is illustrated as having a housing <NUM>, a display <NUM>, a keypad <NUM>, and an actuator device <NUM>. Actuator device <NUM> may be a trigger, button, or other suitable actuator operable by the user to initiate the symbol reading process.

The machine-readable symbol <NUM> shown in the figure is intended to be generic and, thus, is illustrative of the various types and formats of machine-readable symbols. For example, some machine-readable symbols may consist of a single row of codewords (e.g., barcode). Other types of machine-readable symbols (e.g., matrix or area code) may be configured in other shapes, such as circles, hexagons, rectangles, squares and the like. It is intended that many various types and formats of machine-readable symbologies be included within the scope of the present system and method.

An internal block diagram of an exemplary symbol reader <NUM> of a type which may implement the present system and method is shown in <FIG>.

In one embodiment of the present system and method, the symbol reader <NUM> may be an optical reader. Optical reader <NUM> may include an illumination assembly <NUM> for illuminating a target object T, such as a 1D or 2D bar code symbol <NUM>, and an imaging assembly <NUM> for receiving an image of object T and generating an electrical output signal indicative of the data which is optically encoded therein. Illumination assembly <NUM> may, for example, include an illumination source assembly <NUM>, such as one or more LEDs, together with an illuminating optics assembly <NUM>, such as one or more reflectors, for directing light from light source <NUM> in the direction of target object T. Illumination assembly <NUM> may be eliminated if ambient light levels are certain to be high enough to allow high quality images of object T to be taken.

In an embodiment, imaging assembly <NUM> may include an image sensor <NUM>, such as a 2D CCD or CMOS solid state image sensor, together with an imaging optics assembly <NUM> for receiving and focusing an image of object T onto image sensor <NUM>. The array-based imaging assembly shown in <FIG> may be replaced by a laser scanning based imaging assembly comprising a laser source, a scanning mechanism, emit and receive optics, a photodetector and accompanying signal processing circuitry. The field of view of the imaging assembly <NUM> will depend on the application. In general, the field of view should be large enough so that the imaging assembly can capture a bit map representation of a scene including an image data reading region at close reading range.

In an embodiment of the present system and method, exemplary symbol reader <NUM> of <FIG> also includes programmable controller <NUM> which may comprise an integrated circuit microprocessor <NUM> and an application specific integrated circuit (ASIC) <NUM>. Processor <NUM> and ASIC <NUM> are both programmable control devices which are able to receive, output and process data in accordance with a stored program stored in either or both of a read/write random access memory (RAM) <NUM> and an erasable read only memory (EROM) <NUM>. Processor <NUM> and ASIC <NUM> are also both connected to a common bus <NUM> through which program data and working data, including address data, may be received and transmitted in either direction to any circuitry that is also connected thereto. Processor <NUM> and ASIC <NUM> may differ from one another, however, in how they are made and how they are used.

In one embodiment, processor <NUM> may be a general purpose, off-the-shelf VLSI integrated circuit microprocessor which has overall control of the circuitry of <FIG>, but which devotes most of its time to decoding image data stored in RAM <NUM> in accordance with program data stored in EROM <NUM>. Processor <NUM>, on the other hand, may be a special purpose VLSI integrated circuit, such as a programmable logic or gate array, which is programmed to devote its time to functions other than decoding image data, and thereby relieve processor <NUM> from the burden of performing these functions.

In an alternative embodiment, special purpose processor <NUM> may be eliminated entirely if general purpose processor <NUM> is fast enough and powerful enough to perform all of the functions contemplated by the present system and method. It will, therefore, be understood that neither the number of processors used, nor the division of labor there between, is of any fundamental significance for purposes of the present system and method.

In an embodiment, exemplary symbol reader <NUM> includes a signal processor <NUM> and an analog-to-digital (A/D) chip <NUM>. These chips together take the raw data from image sensor <NUM> and convert the data to digital format, which in an exemplary embodiment may be a gray-level digital format, for further processing by programmable controller <NUM>.

In an embodiment, the system and method of the present invention employs algorithms stored in EROM <NUM> which enable the programmable controller <NUM> to analyze the image data from signal processor <NUM> and A/D <NUM>. In an embodiment, and as described further below, this image analysis may include analyzing gray-level information (contrast levels) in the image data. In an embodiment, and in part based on the contrast level analysis, programmable controller <NUM> may then implement an improved system and method of error correction for matrix symbols by relying on optical contrast-level analysis, as also described further below.

Exemplary symbol reader <NUM> may also include input/output (I/O) circuitry <NUM>, for example to support the use of the keyboard <NUM> and trigger <NUM>. Symbol reader <NUM> may also include output/display circuitry <NUM> to support display <NUM>.

<FIG> illustrates several exemplary machine-readable 2D symbols <NUM> labeled <NUM> and <NUM>.

Symbol <NUM> is an exemplary machine-readable symbol encoded according to the Data Matrix barcode (ECC <NUM>) standard. The symbol <NUM>, which is a 24x24 array, has two solid black borders <NUM> forming an "L-shape" which are the finder pattern, enabling the symbol reader to determine the location and orientation of the 2D symbol. The symbol also has two opposing borders of alternating dark and light cells which form a "timing pattern" <NUM> which help the symbol reader identify the size (the number of rows and columns) of the symbol.

Interior to the finder pattern <NUM> and timing pattern <NUM> are rows and columns of interior cells <NUM> which encode information. As may be evident from the figure, an ideal machine-readable symbol has a very high contrast level between the first color dark cells and the second color light cells, in many cases achieved by employing clearly printed, unobscured cells which are either all black or all white.

Symbol <NUM> is an exemplary 16x16 machine-readable symbol encoded according to the Data Matrix barcode (ECC <NUM>) standard. In symbol <NUM>, and for purposes of illustration only, the interior black data cells are omitted, and boundaries between the interior cells <NUM> are suggested by shaded, dotted lines which are not normally present in actual printed data matrix symbols.

Also not normally present in actual printed symbols, but included here for purposes of illustration, are solid borders which indicate the boundaries of the codewords <NUM> formed by the interior cells <NUM>. In an embodiment, each codeword <NUM> is composed of eight cells representing a single byte of data. It will be seen that there are several types of codewords, including data codewords <NUM> which encode the actual data to be represented by the symbol; error-correcting (EC) codewords <NUM> which are generated from the data codewords according to the Reed-Solomon algorithm; and padding codewords <NUM>.

The figure also identifies one exemplary bar (black) cell <NUM>. B and one exemplary space (white) cell <NUM>.

The illustration here of machine-readable symbols based on the Data Matrix barcode standard, as well as the size, shape, and data contents illustrated, are exemplary only and should not be construed as limiting. The present system and method is applicable to a wide variety of 2D matrix barcodes according to a variety of known standards, as well as being applicable to other 2D machine-readable symbols which may be envisioned in the future.

As discussed above, the data content of symbols <NUM> is stored or presented in the form of cells <NUM> of contrasting colors within codewords <NUM>. In an embodiment of the present system and method, the light cells (typically white) represent ones (<NUM>'s) and the dark cells (typically black) represent zeros (<NUM>'s). In an alternative embodiment, a light cell represents zero (<NUM>) and the dark cells represent (<NUM>). In alternative embodiments, other colors or levels of shading may be employed. As a general matter, however, for the coding to be effective the symbol reader <NUM> must be readily able to distinguish the dark cells from the light cells. Also, the data is stored not only in terms of the cells <NUM> per se, but also in terms of the positions of the cells <NUM> within the codewords <NUM>, and the positions of each codeword <NUM> within the symbol <NUM>.

If a symbol <NUM> is damaged, there may be insufficient contrast between light cells and dark cells for the symbol reader <NUM> to reliable distinguish the cells. Similarly, damage to the symbol may render it difficult for the symbol reader to identify the location or boundaries of cells <NUM> and codewords <NUM>. In other cases damage to cells <NUM> can cause a change from black to white or vice-versa. This in turn calls upon the error-correction methods, such as Reed-Solomon, already discussed above. The present system and method is intended to augment Reed-Solomon and similar error-correction methods with information based on contrast analysis.

<FIG> provides two views <NUM>. D2 of an exemplary symbol <NUM>. D which is damaged, so that the original high-contrast has been lost while the symbol <NUM> is in use in the field.

In the first view, the damaged symbol <NUM>. D1 shown in the figure was photographed in a real-world automotive manufacturing plant. It is apparent that there is a dark vertical scuff mark <NUM> which is approximately down the middle of the symbol <NUM>. The scuffing is sufficiently dark that, when read with a standard symbol reader <NUM>, the reader <NUM> mistakes many individual cells <NUM> for black when (as printed, and without damage or scuffing) they are white cells. This in turns causes codeword errors. This symbol <NUM>. D1 will not read with current scanners.

The actual value of the codewords in symbol <NUM>. D1 is listed here (codewords before the colon are data codewords, those after the colon are error-correction codewords):
<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM> :<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>.

The values for the codewords determined by a symbol reader <NUM> are shown here, with the incorrect codewords underlined:
<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM> <NUM> <NUM> <NUM><NUM><NUM><NUM><NUM> <NUM> <NUM> <NUM> <NUM><NUM> :<NUM><NUM> <NUM> <NUM> <NUM> <NUM><NUM><NUM><NUM><NUM><NUM><NUM> <NUM> <NUM> <NUM><NUM><NUM><NUM>.

As is apparent in the image of symbol <NUM>. D1, throughout the smudged region <NUM> the contrast between many individual cells is small, and is close to the threshold level between black and white. Compare for example a cluster of low contrast cells <NUM> within the smudged region <NUM> with a non-damaged, machine-readable high contrast region <NUM>.

In the second view, the damaged symbol <NUM>. D2 is illustrated as it was interpreted by an actual scanner <NUM> in the field. As shown by the codewords with shaded cells <NUM> in the illustration, there were eleven codewords <NUM> which provided flawed readings from the scanner <NUM>, and may be described as flawed codewords <NUM>.

Erasure vs. Error: By way of terminology, it is noted here that if the position of an erroneous codeword is known, but the data is not known (or is ambiguous), the codeword is referred to as an "erasure. " If the data of an erroneous codeword is unknown and the position of the codeword is also unknown, the codeword is referred to as an "error.

In an embodiment, the present system and method includes application of error-correcting codes and analyses, augmented with optical analysis of a machine-readable symbol <NUM>, to detect and correct errors in the machine-readable symbol <NUM>. Various mathematical methods of error correction are well-known in the art, and a detailed description is beyond the scope of this document. However, review of a few basic elements of an exemplary error-correction method may aid in the understanding of the present system and method.

All standardized 2D matrix symbologies utilize the Reed-Solomon methodology. In Reed-Solomon codes, a set of data elements, such as bytes of data, may be redundantly encoded in a second set of error-correcting elements (also typically in byte form), which for present purposes can be referred to as EC codewords <NUM>. The error-correcting codewords are transmitted or presented along with the principle data elements, enabling reconstruction of damaged data elements.

Methods of constructing the Reed-Solomon EC codewords (based on a given, particular data set) are outside the scope of this document. It suffices for present purposes to understand that Reed-Solomon-derived EC codewords <NUM> can be calculated, and the resulting EC codewords are included as part of 2D matrix symbols, as already described above.

There are a variety of methods of decoding a message with Reed-Solomon error correction. In one exemplary method, the values of the data codewords <NUM> of a symbol <NUM> are viewed as the coefficients of a polynomial s(x) that is subject to certain constraints (not discussed here):
<MAT>.

It will be noted that not only the values of the data codewords <NUM> matter, but also their order. The ordinal placement of the codewords (<NUM>st, <NUM>nd, <NUM>rd, etc.) in the polynomial maps to the physical ordering of the data codewords <NUM> in the machine-readable symbol <NUM>.

If the machine-readable symbol <NUM> is damaged or corrupted, this may result in data codewords <NUM> which are incorrect. The erroneous data can be understood as a received polynomial r(x):
<MAT>
<MAT>
where ei is the coefficient for the ith power of x. Coefficient ei will be zero if there is no error at that power of x (and so no error for the corresponding ith data codeword <NUM> in the symbol <NUM>); while the coefficient ei will be nonzero if there is an error. If there are v errors at distinct powers ik of x, then:
<MAT>.

The goal of the decoder is to find the number of errors (v), the positions of the errors (ik), and the error values at those positions (e_ik). From those, e(x) can be calculated, and then e(x) can be subtracted from the received r(x) to get the original message s(x).

There are various algorithms which can be employed, as part of the Reed-Solomon scheme, to identify the error positions (ik) and the error values at those positions (e_ik), based solely on the received data codewords <NUM> and the received EC codewords <NUM>. The processes involved, however, are generally a two-stage processes, where:.

It will be seen then that in the prior art, correcting errors is a two-stage process, where identifying error locations generally precedes, and is an input to, identifying the corrected data at each location. It is a goal of the present system and method to either reduce or possibly eliminate the calculations of stage (I), by using analyses apart from Reed-Solomon error correction to determine identify or mark the erroneous data codewords <NUM>.

Persons skilled in the art will recognize that the non-zero error positions ik calculated via the alternative methods (discussed further below) can be input directly into stage (II), thereby enabling the calculations of the correct data values in stage (II).

Importantly, in the mathematics of standard Reed-Solomon error correction, errors (both location and data unknown) requires the use of two error correcting code words to repair a damaged codeword. If, on the other hand, knowledge of the location of the error exists, then the error is considered an erasure, and only one error correction codeword is required to repair the erased codeword.

Stated another way: Normally, error-correction in 2D matrix symbologies is used to correct codewords which are errors, meaning that both the location and contents of the codeword are unknown. The goal of the present system and method is to independently flag errors so that they are instead treated as erasures, for which the location is known, thereby requiring only one EC codeword for correction.

As discussed above, Reed-Solomon error correction requires the use of two EC codewords <NUM> to correctly recover both the location and the data contents of a single data codeword <NUM> which is flawed. However, the present system and method aims to enable the identification (at least provisionally) of the locations of the flawed or damaged codewords <NUM>. F -- and to make such identification independently of the EC codewords <NUM> in the symbol <NUM>. Such alternative means of locating the data codewords <NUM> which are flawed supplements the data in the EC codewords <NUM>; as a result, only a single EC codeword <NUM> is required to identify the data in a data codeword <NUM> Flawed codewords <NUM>. F may also be referred to as codewords which have a "decoding disadvantage.

To identify the locations of the codewords with a decoding disadvantage, independent of the error-correcting information within the symbol <NUM> itself, the present system and method identifies those codewords <NUM> in the symbol <NUM> which have a low level of optical clarity, or equivalently, a high level of optical ambiguity. By "optical clarity" is meant any codeword <NUM> which, as presented to the reader <NUM>, is sufficiently clear and distinct (e.g., has high optical contrast) to be read very reliably by the symbol reader's optical system <NUM>, <NUM>. If a codeword <NUM> is not optically clear -- for example, due to poor printing, smudging or marking in the field, ripping or tearing, or other causesthen the codeword is deemed optically ambiguous; there is a significant probability that the data for an optically ambiguous codeword, as determined by a reader <NUM>, will not match the intended data of the same codeword.

<FIG> presents a flow-chart of an exemplary method <NUM> for optically enhanced Reed-Solomon error-correction for a symbol <NUM>. The steps of exemplary method <NUM> are generally performed via the processor(s) <NUM>, memory <NUM>, and other components of the symbol reader <NUM>.

In step <NUM>, the symbol reader <NUM> identifies the location of the symbol <NUM> and the appropriate parameters such as the size. For example, for a DataMatrix symbol, the reader <NUM> finds the "L-shape" <NUM> and finds the clock track <NUM> to identify the number of rows and columns in the symbol. The L-shape <NUM> and clock track <NUM> help the reader <NUM> determine the symbol's tilt and orientation, and provide reference points from which to decode the matrix of data cells.

In step <NUM>, the symbol reader <NUM> creates a matrix or array of sample points (pixels), indicating the reflectances (bright or dark) of points within the symbol <NUM>. These sample points are used to determine reflectance of cells <NUM> within the symbol. A single cell <NUM> may have multiple sample points measured, and together these may be used (for example, averaged) to determine the reflectance of each cell <NUM>.

As discussed above, the symbol <NUM> is composed of codewords <NUM> with standardized positions, that is, which are made up of standardized clusters of cells <NUM> with designated positions within the symbol matrix <NUM>.

In step <NUM>, the method <NUM> determines a level of optical clarity for each codeword <NUM>. A high level of optical clarity, which is desirable, means the codeword's cells are distinctive and that the data value of the codeword can be read with a high probability of accuracy.

A low level of optical clarity -- or equivalently, a high level of optical ambiguity -- may result from physical damage to a symbol, or from dirt or grease marking the symbol, or other causes as discussed above. Low optical clarity, or high optical ambiguity, means that the codeword's cells are not distinctive and the codeword has a decoding disadvantage. The low level of optical clarity therefore means that the data value of the codeword can be ascertained only with a suboptimal degree of reliability.

Optical clarity/ambiguity may be determined in a variety of ways. In one embodiment of the present system and method, discussed in detail below, the optical clarity/ambiguity is determined based on an analysis of the contrast level between cells <NUM> within each codeword <NUM>. Codewords <NUM> which exhibit the lowest internal contrast levels may be marked as optically ambiguous.

In an alternative embodiment, optical clarity/ambiguity may be determined based on analysis of the degree to which a codeword <NUM> is in-focus or not in-focus. In an alternative embodiment, optical clarity/ambiguity may be determined based on analysis of the definition or lack of definition of lines separating the dark cells <NUM> from light cells <NUM>.

In an alternative embodiment, optical clarity/ambiguity may be determined based on a degree to which the horizontal and vertical lines of the codewords <NUM> are parallel to, or are not parallel to, the border-L shape. Other methods of assessing optical clarity of a codeword <NUM> may be envisioned as well, and fall within the scope of the present system and method.

In step <NUM>, exemplary method <NUM> ranks the codewords <NUM> according to optical clarity, for example from highest to lowest in optical clarity. In step <NUM>, method <NUM> identifies the lowest ranked codewords (those which are most optically ambiguous), up to the number of codewords <NUM> to be used as erasures.

In steps <NUM> and <NUM>, the lowest-ranked codewords <NUM> identified in step <NUM> -- that is, the codewords with the highest optical ambiguity -- are marked as erasures in the error-correction equations, and the Reed-Solomon error-correction equations are then executed. Steps <NUM> and <NUM> thereby reduce or eliminate the calculations discussed above for a phase (I) of the Reed-Solomon error correction process, and thereby also reduce or eliminate the use of EC codewords <NUM> to identify the locations of flawed codewords <NUM>.

In one embodiment, the present system and method identifies codewords <NUM> with high optical ambiguity (low optical clarity) via contrast analysis of the codewords within the symbol <NUM>.

The present system and method employs a "matrix-cell contrast analysis algorithm," "gray-scale contrast analysis algorithm," or simply "contrast analysis algorithm" (CAA) for short. The contrast analysis algorithm of the present system and method determines the actual gray level of each cell <NUM> in the symbol <NUM>. The CAA also identifies the black/white contrast threshold for the symbol <NUM>. The black/white contrast threshold is the brightness level above which a cell <NUM> is considered to be white, and below which a cell is considered to be black. The algorithm then determines the difference between the contrast level of each cell <NUM> and the black/white threshold. If the differential is comparatively low for one or more cells <NUM> in a particular codeword <NUM>, the codeword <NUM> may have a decoding disadvantage.

More generally, the CAA may identify a light/dark threshold level, which is a brightness level above which a cell <NUM> is considered to be of a first, lighter color (for example, white); and below which a cell is considered to be of a second, darker color (for example, black).

A scanner <NUM> will conventionally store, in memory <NUM>, the "color" of each cell <NUM>, for example, a red-green-blue (RGB) value or a hue-saturation-brightness (HSB) value. The present system and method will also store, in the memory (<NUM>) of the scanner <NUM>, an actual, measured gray-scale level for each cell <NUM>.

<FIG> presents a flow-chart of an exemplary method <NUM> for contrast analysis according to the present system and method. Steps <NUM> through <NUM> of exemplary method <NUM> collectively may be considered to be one exemplary embodiments of step <NUM> of method <NUM>, already discussed above. (Step <NUM> determines an optical clarity for each codeword <NUM> in the symbol <NUM>. ) Step <NUM> of exemplary method <NUM> may be considered to be one exemplary embodiment of step <NUM> of method <NUM>, that is, ranking the codewords for optical clarity.

Where exemplary method <NUM> was directed to generally determining and ranking codewords <NUM> by optical clarity, the exemplary method <NUM> particularly employs an exemplary approach to contrast analysis in order to determine and rank optical clarity. The steps of exemplary method <NUM> are generally performed via the processor(s) <NUM>, memory <NUM>, and other components of the symbol reader <NUM>.

In step <NUM>, the symbol reader <NUM> determines a local black/white contrast threshold (BWCT). The black/white contrast threshold (BWCT), as described above, is a reflectance level above which a cell <NUM> is considered white, and below which a cell <NUM> is considered black. This is typically determined by (i) identifying the reflectance of all the cells <NUM> in the symbol; (ii) identifying the highest reflectance value and the lowest reflectance value; and (iii) identifying a middle-value, such as the mean or the median, and using the middle-value as the BWCT. The present system and method refines this by employing a local BWCT for each cell <NUM>. In an exemplary embodiment, a local BWCT for a given cell <NUM> may be determined by considering only those other cells local to the given cell <NUM>, and then identifying the mean or median reflectance among those cells. In an embodiment, the number of local cells used to determine the local BWCT may be twenty (<NUM>). In an alternative embodiment the number of local cells used to determine the BWCT for a given cell may be higher or lower than twenty (<NUM>).

In step <NUM>, the method <NUM> selects a particular codeword <NUM>, (as specified in the appropriate standards for the size and shape of the symbol <NUM>), and identifies the contrast level (the grayscale level) of each cell in the codeword.

In step <NUM>, the method <NUM> determines, for the particular codeword at hand, a bar cell (<NUM>. B) with a contrast value closest to the BWCT; and a space cell (<NUM>. S) with a contrast value closest to the BWCT; and then stores these two cell contrast values in a codeword contrast values array in memory (see <FIG> below for an example). The contrast values may be labeled as RSmin for the space cell (<NUM>. S) closest to the BWCT, and RBmax for the bar cell (<NUM>. B) closest to the BWCT. An equivalent phrasing: RSmin is the smallest space cell reflectance (darkest), and RBmax is the largest bar cell reflectance (lightest).

Steps <NUM> and <NUM> are repeated for all codewords <NUM> in the symbol <NUM>. This results in a listing of RSmin and RBmax for each codeword <NUM> in the symbol.

In step <NUM>, the method <NUM> identifies the largest space cell value in the entire array, that is the largest value for RSmin. This value, which may be labeled as RSmm, is used for normalization in the following step.

In step <NUM>, the method <NUM> divides all space gap value entries (ESgap) by the largest space cell ("white cell") value in the array, RSmm, generating an Sgap% value for each codeword. (Sgap% = ESgap/RSmm)
In step <NUM>, the method <NUM> identifies the largest bar cell ("black cell") value in the entire array, that is the largest value for RBmin. This value, which may be labeled as RBmm, is used for normalization in the following step.

In step <NUM>, the method <NUM> divides all bar gap value entries (EBgap) by the largest bar cell value in the array, RBmm, generating a Bgap% value for each codeword. (Bgap% = EBgap/RBmm).

Sgap% and Bgap%, then, are the percentage relative closeness of the deviant cell to the black/white contrast threshold. These percentage values, Sgap% and Bgap%, may also be referred to as the minimum interior contrast levels <NUM> for each cell <NUM>. The minimum interior contrast levels <NUM> are a measure of the optical clarity of the codewords <NUM> in the symbol <NUM>. Specifically: Those codewords <NUM> with the lowest values for Sgap% and/or the lowest values for Bgap% have the highest optical ambiguity (and therefore the least or worst optical clarity).

As noted above, the preceding steps <NUM> through <NUM> of method <NUM> may collectively be considered to be one exemplary embodiment of step <NUM> of method <NUM>, already discussed above, that is, determining an optical clarity for each codeword <NUM> in the symbol <NUM>.

In step <NUM>, and based on the Sgap% and Bgap% values determined in steps <NUM> and <NUM>, the method <NUM> ranks the lowest gap percent values up to the number of error correction codewords to be used as erasures. Step <NUM> of exemplary method <NUM> may be considered to be one exemplary embodiment of step <NUM> of method <NUM>, that is, ranking the codewords for optical clarity/ambiguity.

These lowest ranked, least clear codewords are the codewords with the lowest optical clarity (or highest ambiguity), which are then used as erasures in the Reed-Solomon equations (step <NUM> of method <NUM>).

<FIG> presents an exemplary codeword contrast values array <NUM> of the kind which may be constructed according to exemplary method <NUM>, above. The array contains actual codeword measurements for the symbol image <NUM>. D2 of <FIG>, above. In array <NUM>, CW is the codeword number; and, as per discussion above:.

<FIG> illustrates an exemplary case-analysis demonstrating how poor cell contrast can identify a majority of flawed codewords <NUM>. The damaged symbols shown in the figure are the same as the damaged symbol pictured and illustrated in <FIG>, above. In <FIG>, numbered codeword locations <NUM> are identified (by a standardized number scheme) for those codewords which are flowed or damaged.

D2, reproduced here from <FIG> for convenience, is the damaged symbol as it was interpreted by an actual scanner <NUM> in the field.

Symbol <NUM>. D3 is the same symbol as it was interpreted according the exemplary contrast analysis algorithms discussed above in conjunction with <FIG> and <FIG>.

As can be seen in <FIG>, there are two codewords <NUM> which were assessed as being in error by the present system and method, but which were actually read correctly by the scanner <NUM>. Of the latter codewords, one was in the damaged region <NUM> (codeword <NUM>) and another was a codeword where there is a scratch through the dark cell, making it lighter (codeword <NUM>).

As can also be seen from <FIG>, there is one codeword <NUM> which was actually read in error by the scanner <NUM>, but was not flagged by the gray-scale contrast analysis algorithm of the present system and method.

All the remaining, identified codewords <NUM> (a total of ten) which were flagged as being in error based on contrast analysis are codewords which were, in fact, read in error by the scanner <NUM>.

The codeword that the analysis missed (codeword <NUM>) is easily decoded using the <NUM> error correction codewords still remaining. This is an example of a symbol <NUM>. D that was far from being decodable using standard decoding methods, yet using a gray-scale contrast analysis algorithm, the symbol can sustain this and slightly more damage and still be decodable.

The example shown (in <FIG> and <FIG>) clearly benefits from the gray-scale contrast analysis decoding since the damage to the symbol <NUM>. D2 is contrast based. However, the present system and method will also work with other types of damage such as matrix distortion, uniform dark or light damage and for DPM cell variation. When these types of distortion are present, there will be many sample points that rest on cell boundaries which will be recorded as reduced contrast values. As long as the matrix distortion (such as wrinkling) is localized or the dark/light damage is less than approximately one-third of the symbol, the present system and method will substantially improve decoding rates on all types of problem symbols <NUM>.

Claim 1:
A method of error correction of a two-dimensional, 2D, symbol, the method comprising:
accessing, by a processor, a plurality of codewords in the 2D symbol;
determining, by the processor, a contrast threshold associated with each codeword of the plurality of codewords;
determining, by the processor, a minimum interior contrast level for each codeword of the plurality of codewords, wherein determining the minimum interior contrast level comprises:
determining, within a codeword of the plurality of codewords, a space cell having a smallest space cell reflectance value and a bar cell having a largest bar cell reflectance value; and
determining an erasure gap for bars and an erasure gap for spaces, wherein the erasure gap for bars is determined based on the largest bar cell reflectance value and the contrast threshold, and wherein the erasure gap for spaces is determined based on the smallest space cell reflectance value and the contrast threshold;
identifying, by the processor, an optically ambiguous codeword of the plurality of codewords in the 2D symbol, wherein the optically ambiguous codeword corresponds to a codeword having a lowest minimum interior contrast level amongst the minimum interior contrast levels for each codeword of the plurality of codewords; and
correcting, by the processor, errors in the optically ambiguous codeword based on a location of the optically ambiguous codeword and an erroneous decoded value associated with the optically ambiguous codeword.