Apparatus and method for decoding damaged optical codes

• US 6,685,095 B2
• Filed: 03/05/2001
• Issued: 02/03/2004
• Est. Priority Date: 05/05/1998
• Status: Expired due to Term

• Current Assignee: Psion Inc (Zebra Technologies Corporation)
• Original Assignee: Symagery Microsystems, Inc. (Motorola Solutions, Inc.)
• Inventors: Roustaei, Alex, Priddy, Dennis G., Xia, Wenji
• Primary Examiner(s): LE, THIEN MINH
• Application Number:
  US09/801,111
• Publication Number:
  US 20020041712A1
• Time in Patent Office: 1,065 Days
• Field of Search: 235/462.01, 235/462-2-4, 235/462-7-4, 235/471-1-4
• US Class Current: 235/472.01
• CPC Class Codes: G06K 7/10544 by scanning of the records by radiation in the optical part of the electromagnetic spectrum
• CPC Class Codes: G06K 7/10811 Focalisation
• CPC Class Codes: G06K 7/1098 the scanning arrangement having a modular construction
• 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/1473 error correction

Abstract

An improved optical code reading system and method that enhances the ability of a reader to locate a symbol within a field of view and enhances the error-correcting properties of the encoding scheme commonly used in 2D bar codes. The reader offsets the effects of damaged finder patterns and missing symbol perimeters and, thereafter, detects high-level symbol information such as the code type, symbol size, and the number of rows and columns in the symbol. The reader then identifies those missing portions of a damaged symbol and marks each missing data bit location with a predetermined indicator. A decoding algorithm then interprets the missing bit indicator as an error of known location (e.g., an “erasure”), thereby nearly doubling the error correcting strength of all bar codes employing the Reed-Solomon error correction scheme.

Claims

1. A method of decoding a code contained in an image, comprising:

identifying an area within said image that contains a code;

tracing a contour of said code;

locating at least a portion of a finder pattern within the code;

scanning at least one region of the code to detect a known characteristic of the code;

labeling at least a portion of said at least one region as an erasure region based on whether said known characteristic is detected; and

decoding the code.

2. The method of claim 1 wherein said code comprises a 2D Data Matrix code and said step of locating at least a portion of a finder pattern comprises scanning from an edge of the code toward the center of the code until at least a portion of an “

L”

-shaped finder pattern is located.

3. The method of claim 2 wherein said portion of said “

L”

-shaped finder pattern comprises 50% of the “

L”

-shaped finder pattern.

4. The method of claim 2 further comprising:

measuring a width and height of said Data Matrix code based on said contour of the code;

scanning a horizontal edge and a vertical edge of said Data Matrix code to calculate an average element width and height, respectively;

calculating the number of rows and columns in the code by dividing the measured width and height by the average element width and height, respectively; and

identifying defective elements within said “

L”

-shaped finder pattern based on expected dimensions of the finder pattern based on the calculated number of rows and columns in the code.

5. The method of claim 1 wherein said code type is a Data Matrix code type and said step of scanning at least one region of the code comprises:

scanning a horizontal edge of the code to detect alternating light and dark elements located along the horizontal edge;

measuring a width for each of a plurality of light and dark elements along the horizontal edge;

calculating an average element width based on at least a subset of the measured widths of said elements along the horizontal edge;

scanning a vertical edge of the code to detect alternating light and dark elements located along the vertical edge;

measuring a height for each of a plurality of light and dark elements along the vertical edge;

calculating an average element height based on at least a subset of the measured heights of said elements along the vertical edge;

calculating a number of rows in said code by dividing said measured height of the code by said average element height; and

calculating a number of columns in said Data Matrix code by dividing said measured width of the code by said average element width.

6. The method of claim 5 wherein said characteristic comprises a number of alternating light and dark elements along the horizontal and vertical edges equal to said calculated number of columns and rows, respectively, and wherein said step of labeling said at least one region comprises labeling detected defective elements along said horizontal and vertical edges as erasures.

7. The method of claim 1 wherein said code comprises a MaxiCode symbol and said step of locating a finder pattern comprises scanning from a center region of the symbol outwardly toward an edge until at least a portion of a circular finder pattern is located.

8. The method of claim 7 wherein said step of scanning comprises scanning at least one portion of the code to detect a substantially uniformly black area and said step of labeling comprises labeling the substantially uniformly black area as an erasure region if it is detected.

9. The method of claim 7 wherein said step of scanning comprises:

applying a scan line through the middle of said code to measure a minimum element width;

calculating a number of rows and columns in said code based on the minimum element width;

comparing the calculated number of rows and columns to an expected number of rows and columns; and

if said calculated number of rows and columns does not match said expected number of rows and columns, scanning said code to identifying defective elements.

10. The method of claim 1 wherein said code is a PDF417 code and wherein said step of locating at least a portion of a finder pattern comprises:

scanning at least a portion of the code to detect a start bar sequence;

determining a minimum element width based on the start bar sequence; and

determining a width of a row segment based on the minimum element width.

11. The method of claim 1 wherein:

said step of scanning comprises;

applying a plurality of parallel scan lines across said code to detect a number of rows within the code;

measuring a height for a first segment of each detected row; and

said step of labeling comprises labeling as an erasure region any row segments having a measured height not within a predetermined height range.

12. A method of decoding a code contained in an image, comprising:

identifying an area within said image that contains a code;

tracing a contour of said code;

locating at least one portion of a finder pattern within the code;

determining a code type for said code based on said at least one portion of said finder pattern;

scanning at least one region of the code to detect a known characteristic of the code type;

labeling at least a portion of said at least one region as an erasure region based on whether said known characteristic is detected; and

decoding the code.

13. The method of claim 12 wherein if it is determined that said code type is a DataMatrix code, said step of locating at least a portion of a finder pattern comprises scanning from an edge of the code toward the center of the code until at least a portion of an “

L”

-shaped finder pattern is located.

14. The method of claim 13 wherein said portion of said “

L”

-shaped finder pattern comprises 50% of the “

L”

-shaped finder pattern.

15. The method of claim 13 further comprising:

measuring a width and height of said Data Matrix code based on said contour of the code;

scanning a horizontal edge and a vertical edge of said Data Matrix code to calculate an average element width and height, respectively;

calculating the number of rows and columns in the code by dividing the measured width and height by the average element width and height, respectively; and

identifying defective elements within said “

L”

-shaped finder pattern based on expected dimensions of the finder pattern determined from the calculated number of rows and columns in the code.

16. The method of claim 12 wherein if said code type is determined to be a DataMatrix code, said step of scanning at least one region of the code comprises:

scanning a horizontal edge of the code to detect alternating light and dark elements located along the horizontal edge;

measuring a width for each of a plurality of light and dark elements along the horizontal edge;

calculating an average element width based on at least a subset of the measured widths of said elements along the horizontal edge;

scanning a vertical edge of the code to detect alternating light and dark elements located along the vertical edge;

measuring a height for each of a plurality of light and dark elements along the vertical edge;

calculating an average element height based on at least a subset of the measured heights of said elements along the vertical edge;

calculating a number of rows in said code by dividing said measured height of the code by said average element height; and

calculating a number of columns in said Data Matrix code by dividing said measured width of the code by said average element width.

17. The method of claim 16 wherein said characteristic comprises a number of alternating light and dark elements along the horizontal and vertical edges equal to said calculated number of columns and rows, respectively, and wherein said step of labeling said at least one region comprises labeling detected defective elements along said horizontal and vertical edges as erasures.

18. The method of claim 12 wherein if said code type is determined to be a MaxiCode symbol, said step of locating a finder pattern comprises scanning from a center region of the symbol outwardly toward an edge until at least a portion of a circular finder pattern is located.

19. The method of claim 18 wherein said step of scanning comprises scanning at least one portion of the code to detect a substantially uniformly black area and said step of labeling comprises labeling the substantially uniformly black area as an erasure region if it is detected.

20. The method of claim 19 wherein said step of scanning comprises:

applying a scan line through the middle of the said code to measure a minimum element width;

calculating a number of rows and columns in said code based on the minimum element width;

comparing the calculated number of rows and columns to an expected number of rows and columns; and

if said calculated number of rows and columns does not match said expected number of rows and columns, scanning said code to identifying defective elements.

21. The method of claim 12 wherein if said code type is determined to be a PDF417 code, said step of locating at least a portion of a finder pattern comprises:

scanning at least a portion of the code to detect a start bar sequence;

determining a minimum element width based on the start bar sequence; and

determining a width of a row segment based on the minimum element width.

22. The method of claim 21 wherein:

said step of scanning comprises;

applying a plurality of parallel scan lines across said code to detect a number of rows within the code;

measuring a height for a first segment of each detected row; and

said step of labeling comprises labeling as an erasure region any row segments having a measured height not within a predetermined height range.