Method and apparatus for decoding bar code symbols using ratio analysis of module size

• US 5,767,497 A
• Filed: 12/04/1996
• Issued: 06/16/1998
• Est. Priority Date: 12/04/1996
• Status: Expired due to Term

• Current Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Original Assignee: United Parcel Service Of America Incorporated (United Parcel Service Incorporated)
• Inventors: Lei, Ming
• Primary Examiner(s): Hajec, Donald T.
• Assistant Examiner(s): Eisenberg, Jacob
• Application Number:
  US08/759,402
• Time in Patent Office: 559 Days
• Field of Search: 235/462, 235/463, 235/470, 235/472, 235/494
• US Class Current: 235/462.12
• 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/1486 Setting the threshold-width for bar codes to be decoded

Abstract

A method and apparatus for decoding bar code symbols using an analysis of the ratios of the module size for the bars and spaces of the bar code. The invention is applicable to any bar code having one or more nominal widths in the bars and spaces, and is particularly useful in bar codes having multiples widths in the specification for the bar code and in situations where the bar code signal has a low signal-to-noise ratio, or is degraded because of a damaged, smudged, or dirty bar code, or where the bar code is read at less than the optimum angle. The invention identifies mis-decoded characters and uses adaptive techniques to decode characters previously non-decodable or mis-decoded by standard methods, thereby improving the decode rate as compared to prior techniques. The decoding rate is improved without having to re-scan the bar code for a new signal, thereby making the invention particularly useful for high-speed or one-pass decoding operations.

Claims

1. A method of decoding characters of a bar code including a start code and a stop code, each character of the bar code being represented by a series of elements comprising bars and spaces, a width of each such element being a multiple of a unit bar module width or a unit space module width, comprising the steps of:

(a) scanning a bar code and assigning a value to the width of each element encountered in the scan;

(b) decoding a start or stop character of the bar code;

(c) calculating a first average unit bar module width by dividing a sum of the bar widths of the start or stop character by a known number of bar unit modules in the start or stop character;

(d) calculating a first average unit space module width by dividing the sum of the space widths of the start or stop character by a known number of space unit modules in the start or stop character;

(e) attempting to decode a second character of the bar code;

(f) if said attempt to decode said second character fails, marking said second character as non-decodable;

(g) if said attempt to decode said second character succeeds, calculating a second average unit bar module width by dividing the sum of the bar widths of the second character by a known number of bar unit modules in the second character, and continuing with steps (h)-(j);

(h) calculating a second average unit space module width by dividing the sum of the space widths of the second character by a known number of space unit modules in the second character;

(i) accepting the decoding of said second character if a ratio of the second to the first average unit bar module widths is within a predetermined tolerance of 1;

1, and a ratio of the second to the first average unit space module widths is within a predetermined tolerance of 1;

1; and

marking said second character as mis-decoded if said ratios are outside said predetermined tolerance.

2. The method of claim 1, further comprising the steps of:

(k) if the decoding of said second character is accepted, calculating a running average of the first and second average unit bar module widths and a running average of the first and second average unit space module widths;

(l) decoding a third character of the bar code;

(m) if said attempt to decode said third character fails, marking said third character as non-decodable;

(n) if said attempt to decode said third character succeeds, calculating a third average unit bar module width by dividing the sum of the bar widths of the third character by a known number of bar unit modules in the third character, and continuing with steps (o)-(r);

(o) calculating a third average unit space module width by dividing the sum of the space widths of the third character by a known number of space unit modules in the third character;

(p) accepting the decoding of said third character if the ratio of the third average unit bar module width to the running average unit bar module width is within a predetermined tolerance of 1;

1, and the ratio of the third average unit space module width to the running average unit space module width is within a predetermined tolerance of 1;

1;

(q) marking said third character as mis-decoded if said third-to-running ratios are outside said predetermined tolerance; and

(r) if the decoding of said third character is accepted, calculating an updated running average of the third and running average unit bar module widths and an updated running average of the third and running average unit space module widths.

3. The method of claim 1, further comprising repeating steps (l)-(r) for a fourth and all subsequent characters in said bar code, resulting in accepted, mis-decoded, and non-decodable characters and a final running average unit bar module width and a final running average unit space module width.

4. The method of claim 3, further comprising re-decoding one of said marked non-decodable or mis-decoded characters by:

(s) dividing the width of each bar element by the final running average unit bar module width, and the width of each space element by the final running average unit space module width, to obtain a series of quotients;

(t) rounding the quotients obtained in step (s) to a closest integer;

(u) decoding the series of integers of step (t) to obtain a new character;

(v) calculating a new character average unit bar module width by dividing the sum of the bar widths of said one character by a known number of bar unit modules in the new character;

(w) calculating a new character average unit space module width by dividing the sum of the space widths of said one character by a known number of space unit modules in the new character;

(x) accepting the decoding of said one character as the new character if the ratio of the new character average unit bar module width to final running average unit bar module width is within a predetermined tolerance of 1;

1, and the ratio of the new character average unit space module width to final average unit space module width is within a predetermined tolerance of 1;

1.

5. The method of claim 4, further comprising, if the new character decoded from said series of integers in step (u) is the same as the previously decoded non-accepted character, accepting said character.

6. The method of claim 4, further comprising, prior to decoding the new character in step (u), determining whether the sum of said series of integers equals a known total number of modules in said new character.

7. The method of claim 3, comprising:

decoding one of a start code or stop code in step (b);

repeating steps (l)-(r) until encountering a bad area meeting predetermined criteria prior to encountering the other of the start code or stop code;

decoding the other of the start code or stop code at the opposite end of the bar code; and

repeating steps (l)-(r) from the other of the start code or stop code toward the bad area.

8. A method of decoding a bar code of a particular kind, wherein the bar code is comprised of a number of characters in an order, each character of which is represented by a series of elements of a plurality of types, the width of each element in the series being in one of a plurality of fixed ratios to a unit module width corresponding to the element type, the plurality of fixed ratios being determined by a particular kind of a bar code, comprising the steps of:

(a) scanning the bar code and assigning a value to the width of each element encountered in the scan;

(b) grouping the width values into ordered sets corresponding to the order of the characters in the bar code;

(c) finding an initialization character among the ordered sets resulting from step (b) above;

(d) determining the particular kind of the bar code;

(e) determining an average unit module width corresponding to each element type;

(f) comparing the width values in the ordered set next in order to a table of standard character values for the particular kind of bar code; and

;

(f)(i) if no match is found, marking the ordered set as non-decodable;

(f)(ii) if a match is found, subjecting the width values in the ordered set to ratio analysis, and;

if the ratio analysis is unsuccessful, marking the ordered set as mis-decoded; and

if the ratio analysis is successful, updating the average unit module width corresponding to each element type; and

(g) re-decoding the marked characters by applying a standard decoding method to a series of integers derived from the widths of the elements of the marked character divided by the appropriate average unit module width.

9. A method of decoding a bar code according to claim 8, wherein said ratio analysis comprises the steps of:

(h) computing a current unit module width based on the next ordered set;

(i) comparing the current unit module width with the average unit module width;

(j) declaring a successful ratio analysis if the result of the comparison in step (i) above is approximately a 1;

1 ratio.

10. A method of decoding a bar code according to claim 9, wherein at least one ordered set is marked as non-decodable or mis-decoded, all of such sets so marked being called marked sets, further comprising the steps of:

(k) dividing the width values for each of the elements in a marked set by the average unit module width corresponding to the element type;

(l) rounding the quotients obtained in step (k) to a closest integer value;

(m) adjusting said integer values to make the sum of said integer values equal a known number of modules in a character represented by said marked set.

11. A method of decoding a bar code according to claim 10, wherein said step (m) of adjusting said integer values comprises the steps of:

(n) summing the integers determined in step (l) above for the marked set;

(o) determining if the sum obtained in step (n) above is a proper sum for the kind of bar code; and

(p) if not, selecting an element by a confidence analysis and adjusting the number of unit modules in the selected element according to the result of the confidence analysis.

12. A method of decoding a bar code according to claim 11, wherein said confidence analysis comprises the steps of:

(q) determine whether a unique parity for bars is satisfied by the integer values determined in step (l), and, if so, set a high confidence value to prevent adjustment of the number of bar elements;

(r) determine whether a unique parity for spaces is satisfied by the integer values determined in step (l), and, if so, set a high confidence value to prevent adjustment of the number of space elements;

(s) if the bar code is a multi-width bar code, set a high confidence level for extreme elements of the bar code;

(t) for the element with the least confidence value, increment the module number if the module number was previously rounded down, and decrement the module number if the module number was previously rounded up; and

(u) if the module number is not adjusted in step (t), apply the method of step (t) to next element with higher confidence until step (o) above is satisfied or until the module numbers of all the elements have been adjusted.

13. A computing device having executable instructions for decoding characters of a bar code including a start code and a stop code, each character of the bar code being represented by a series of elements comprising bars and spaces, the width of each such element being a multiple of a unit bar module width or a unit space module width, according to the steps of:

(a) scanning a bar code and assigning a value to the width of each element encountered in the scan;

(b) decoding a start or stop character of the bar code;

(c) calculating a first average unit bar module width by dividing a sum of the bar widths of the start or stop character by a known number of bar unit modules in the start or stop character;

(d) calculating a first average unit space module width by dividing a sum of the space widths of the start or stop character by a known number of space unit modules in the start or stop character;

(e) attempting to decode a second character of the bar code;

(f) if said attempt to decode said second character fails, marking said second character as non-decodable;

(g) if said attempt to decode said second character succeeds, calculating a second average unit bar module width by dividing the sum of the bar widths of the second character by a known number of bar unit modules in the second character, and continuing with steps (h)-(j);

(h) calculating a second average unit space module width by dividing the sum of the space widths of the second character by a known number of space unit modules in the second character;

(i) accepting the decoding of said second character if the ratio of the second to the first average unit bar module widths is within a predetermined tolerance of 1;

1, and the ratio of the second to the first average unit space module widths is within a predetermined tolerance of 1;

1; and

(j) marking said second character as mis-decoded if said ratios are outside said predetermined tolerance.

14. The computing device of claim 13, having further executable instructions for decoding characters according to the steps of:

(k) if the decoding of said second character is accepted, calculating a running average of the first and second average unit bar module widths and a running average of the first and second average unit space module widths;

(l) decoding a third character of the bar code;

(m) if said attempt to decode said third character fails, marking said third character as non-decodable;

(n) if said attempt to decode said third character succeeds, calculating a third average unit bar module width by dividing the sum of the bar widths of the third character by a known number of bar unit modules in the third character, and continuing with steps (o)-(r);

(o) calculating a third average unit space module width by dividing the sum of the space widths of the third character by a known number of space unit modules in the third character;

(p) accepting the decoding of said third character if the ratio of the third average unit bar module width to the running average unit bar module width is within a predetermined tolerance of 1;

1, and the ratio of the third average unit space module width to the running average unit space module width is within a predetermined tolerance of 1;

1;

(q) marking said third character as mis-decoded if said third-to-running ratios are outside said predetermined tolerance; and

(r) if the decoding of said third character is accepted, calculating an updated running average of the third and running average unit bar module widths and an updated running average of the third and running average unit space module widths.

15. The computing device of claim 14, having further executable instructions for decoding characters according to the steps of:

repeating steps (l)-(r) for a fourth and all subsequent characters in said bar code, resulting in accepted, mis-decoded, and non-decodable characters and a final running average unit bar module width and a final running average unit space module width.