Analog waveform decoder utilizing histogram of edge sizes

• US 5,311,001 A
• Filed: 07/23/1993
• Issued: 05/10/1994
• Est. Priority Date: 09/13/1991
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Inventors: Joseph, Eugene B., Pavlidis, Theodosios
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): FILIPEK, JEFFER
• Application Number:
  US08/096,579
• Time in Patent Office: 291 Days
• Field of Search: 235/462, 235/454, 235/463, 235/470
• US Class Current: 235/462.07
• 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 for decoding information contained in an analog waveform representative of a bar code symbol comprising the steps of identifying a decodable portion of an analog waveform; processing said decodable portion to obtain a plurality of waveform descriptors; and performing a high and low density decoding process to one or more of said plurality of waveform descriptors for decoding information contained in either a high or low density symbol respectively, is disclosed. The high density decoder used for decoding high density symbols utilizes extrema extents, i.e., areas of the peaks and valleys of the analog waveform which directly correlate to the size of the bars/spaces of a high density bar code. After locating the seed point of the waveform, each extrema extent is generated and thresholded at each peak/valley location to decide its size. The high density decoder is adaptive in that the thresholding extent value is updated as the solution grows away from the seed point. The low density decoder used for decoding low density symbols utilizes the widths of the peaks/valleys for decoding purposes and utilizes a histogramming and backtracking technique for removing noise levels from the analog waveform. Backtracking allows another decode attempt to be made if one is unsuccessful.

Claims

1. In a symbol scanning system, an analog waveform decoder that operates directly upon an analog waveform representative of a symbol for decoding information contained in said symbol, said analog waveform decoder comprising:

means for identifying a decodable portion of said waveform;

means responsive to said decodable portion of said waveform for obtaining a plurality of waveform descriptors defining said decodable portion of said waveform;

first decoding means responsive to one or more of said plurality of waveform descriptors for producing a first decode signal representative of information contained in a high density symbol or producing a non-decode signal;

second decoding means responsive to one or more of said plurality of waveform descriptors for producing a second decode signal representative of information contained in a low density symbol in response to said non-decode signal;

means for outputting said first decode signal when said symbol is a high density symbol; and

means for outputting said second decode signal when said symbol is a low density symbol,

wherein said means for obtaining said plurality of waveform descriptors includes;

a) means for obtaining extrema locations representative of peaks and valleys of said analog waveform;

b) means for determining edge sizes that connect adjacent extrema locations; and

c) means for determining inflection point triplets of said analog waveform.

2. The analog waveform decoder as recited in claim 1 wherein said first decoding means includes:

a) means for identifying a seed point from a sequence of said edge sizes;

b) means for generating an extrema extent at each extrema location wherein said extrema extents are generated starting from said seed point and ending at said boundaries;

c) means for classifying the size of each extrema extent.

3. The analog waveform decoder as recited in claim 2 wherein said classifying means includes:

means for determining a current threshold extent having a value based upon one or more generated extrema extents; and

means for comparing said current threshold extent value to a generated extrema extent.

4. The analog waveform decoder as recited in claim 3 wherein the means for determining said current threshold extent value includes updating means for changing said current threshold extent value to reflect the size of an extrema extent determined prior to the one being updated.

5. The analog waveform decoder as recited in claim 1 wherein said second decoding means includes means for determining an extrema width of each peak and valley of said waveform from information contained at extrema located at each peak and valley and extrema located adjacent thereto.

6. The analog waveform decoder as recited in claim 5 further including means for generating a histogram of said edge sizes and means for determining noise level thresholds from said histogram.

7. The analog waveform decoder as recited in claim 6 further including means for removing noise information from said analog waveform based upon a noise level threshold obtained from said histogram.

8. The analog waveform decoder as recited in claim 7 further including a backtracking means for returning said analog waveform with noise information removed, into said second decoding means.

9. The analog waveform decoder as recited in claim 1 wherein said first decoding means utilizes only said extrema locations and said edge sizes for decoding the information contained in said high density symbol.

10. The analog waveform decoder as recited in claim 1 further including means for computing high order derivatives of said waveform and for determining zero points of said derivatives.

11. In a symbol scanning system, an analog waveform decoder that operates directly upon an analog waveform representative of a high density symbol for decoding information contained in said high density symbol, said analog waveform decoder comprising:

means for identifying boundaries of said analog waveform to identify a decodable portion of said waveform;

means responsive to said decodable portion of said waveform for obtaining a plurality of waveform descriptors defining said decodable portion of said waveform;

high density decoder means responsive to one or more of said plurality of waveform descriptors for decoding information contained in said high density symbol; and

means for outputting a signal representative of information contained in said symbol,

wherein said means for obtaining said plurality of waveform descriptors includes;

a) means for obtaining extrema locations representative of peaks and valleys of said analog waveform;

b) means for determining edge sizes that connect adjacent extrema locations; and

c) means for determining inflection point triplets of said analog waveform.

12. The analog waveform decoder as recited in claim 11 wherein said high density decoding means includes:

a) means for identifying a seed point from a sequence of said edge sizes;

b) means for generating an extrema extent at each extrema location wherein said extrema extents are generated starting from said seed point and ending at said boundaries; and

c) means for classifying the size of each extrema extent.

13. The analog waveform decoder as recited in claim 12 wherein said classifying means includes:

means for determining a current threshold extent having a value based upon one or more generated extrema extents; and

means for comparing said current threshold extent value to a generated extrema extent.

14. The analog waveform decoder as recited in claim 13 wherein the means for determining said current threshold extent value includes updating means for changing said current threshold extent value to reflect the size of an extrema extent determined prior to the one being updated.

15. The analog waveform decoder as recited in claim 11 wherein said high density decoder means utilizes only said extrema locations and said edge sizes for decoding the information contained in said high density symbol.

16. A method for decoding an analog waveform representative of information contained in a symbol comprising the steps of:

determining boundaries of said analog waveform to identify a decodable portion of said waveform;

processing said decodable portion of said analog waveform to obtain a plurality of waveform descriptors defining said decodable portion of said waveform;

performing a first decoding process on one or more of said plurality of waveform descriptors for producing a first decode signal representative of information contained in a high density symbol or producing a non-decode signal;

performing a second decoding process on one or more of said plurality of waveform descriptors in response to said non-decode signal for producing a second decode signal representative of information contained in a low density symbol; and

outputting said first decode signal when said symbol is a high density symbol and outputting said second decode signal when said symbol is a low density symbol,

wherein the processing step includes the steps of;

obtaining extrema locations representative of peaks and valleys of said analog waveform;

determining edge sizes that connect adjacent extrema locations; and

determining inflection point triplets of said analog waveform.

17. The method for decoding an analog waveform as recited in claim 16 wherein said first decoding process includes the steps of:

identifying a seed point from a sequence of said edge sizes;

generating an extrema extent at each extrema location starting from said seed point and ending at said boundaries;

classifying the size of each extrema extent generated.

18. The method for decoding an analog waveform as recited in claim 17 wherein the classifying step includes the steps of:

determining a current threshold extent having a value based upon one or more generated extrema extents; and

comparing said current threshold extent value to a generated extrema extent.

19. The method for decoding an analog waveform as recited in claim 18 wherein the step of determining a current threshold extent value includes the step of updating said current threshold extent value to reflect the size of an extrema extent determined prior to the one being updated.

20. The method for decoding an analog waveform as recited in claim 16 wherein said second decoding process includes the step of determining an extrema width of each peak and valley of said waveform from information contained at extrema located at each peak and valley and extrema located adjacent thereto.

21. The method for decoding an analog waveform as recited in claim 20 further including the steps of generating a histogram of said edge sizes and determining noise level thresholds from said histogram.

22. The method for decoding an analog waveform according to claim 21 further including the step of removing noise information from said analog waveform based upon a noise level threshold obtained from said histogram.

23. The method for decoding an analog waveform as recited in claim 22 further including the steps of returning said analog waveform with said noise information removed, into said low density decoder means.

24. The method for decoding an analog waveform as recited in claim 16 wherein said first decoding process includes the step of utilizing only said extrema location and said edge sizes for decoding information contained in said symbol.

25. A method for decoding an analog waveform representative of information contained in a high density symbol comprising the steps of:

determining boundaries of said analog waveform to identify a decodable portion of said waveform;

processing said decodable portion of said analog waveform to obtain a plurality of waveform descriptors defining said decodable portion of said waveform;

performing a high density decoding process on one or more of said plurality of waveform descriptors for producing a decode signal representative of information contained in said high density symbol; and

outputting said signal representative of information contained in said symbol,

wherein said processing step includes the steps of;

obtaining extrema locations representative of peaks and valleys of said analog waveform;

determining edge sizes that connect adjacent extrema locations; and

determining inflection point triplets of said analog waveform.

26. The method for decoding an analog waveform as recited in claim 25 wherein said high density decoding process step includes the steps of:

identifying a seed point from a sequence of said edge sizes;

generating an extrema extent at each extrema location starting from said seed point and ending at said boundaries; and

classifying the size of each extrema extent generated.

27. The method of decoding an analog waveform as recited in claim 26 wherein said classifying step includes the steps of:

determining a current threshold extent having a value based upon one or more generated extrema extents; and

comparing said current threshold extent value to a generated extrema extent.

28. The method for decoding an analog waveform as recited in claim 27 wherein the step of determining a current threshold extent value includes the step of updating said current threshold extent value to reflect the size of an extrema extent determined prior to the one being updated.

29. In a symbol scanning system, an analog waveform decoder that operates directly upon an analog waveform representative of a symbol for decoding information contained in said symbol, said analog waveform decoder comprising:

means for identifying a decodable portion of said waveform;

means responsive to said decodable portion of said waveform for obtaining a plurality of waveform descriptors defining said decodable portion of said waveform;

first decoding means responsive to one or more of said plurality of waveform descriptors for producing a first decode signal representative of information contained in a high density symbol or producing a non-decode signal;

second decoding means responsive to one or more of said plurality of waveform descriptors for producing a second decode signal representative of information contained in a low density symbol in response to said non-decode signal;

means for outputting said first decode signal when said symbol is a high density symbol; and

means for outputting said second decode signal when said symbol is a low density symbol,

wherein said symbol is a bar code symbol, and said decoder further includes a means responsive to said plurality of waveform descriptors for deblurring said decodable portion of said waveform and for obtaining an additional set of descriptors that define successive edges of said bar code.

30. The analog waveform decoder as recited in claim 29 wherein said second decoding means is additionally responsive to said additional set of descriptors for producing a decode signal representative of information obtained in a bar code symbol.

31. A decoder comprising:

means receptive of an analog signal having a waveform representative of a decodable symbology and including a decodable portion;

means for locating the decodable portion of the waveform;

means for producing a plurality of waveform descriptors relating to edge sizes of the decodable portion of the waveform; and

means for decoding information contained in the decodable symbology in response to the descriptors.

32. The decoder according to claim 31, wherein the means for decoding comprises means for producing a histogram of the edge sizes of the decodable portion of the waveform.

33. A method of decoding comprising the steps of:

receiving an analog signal having a waveform representative of a decodable symbology and including a decodable portion;

locating the decodable portion of the waveform;

producing a plurality of waveform descriptors relating to edge sizes of the decodable portion of the waveform; and

decoding information contained in the decodable symbology in response to the descriptors.

34. The method according to claim 33, wherein the step of decoding comprises producing a histogram of the edge sizes of the decodable portion of the waveform.

35. A system for reading and decoding symbology comprising:

a light source;

means for directing light from the light source on a decodable symbology;

means receptive of reflected light from the symbology for producing an analog signal having a waveform representative of the decodable symbology and including a decodable portion; and

decoding means receptive of the analog signal for decoding the symbology and comprising means for locating the decodable portion of the waveform, means for producing a plurality of waveform descriptors relating to edge sizes of the decodable portion of the waveform and means for producing a decode signal representative of information contained in the decodable symbology in response to the descriptors.

36. The system according to claim 35, wherein the means for producing the decode signal comprises means for producing a histogram of the edge sizes in the decodable portion of the waveform.

37. A method for reading and decoding symbology comprising the steps of:

directing a light from a light source on a decodable symbology;

receiving reflected light from the symbology to produce an analog signal having a waveform representative of the decodable symbology and including a decodable portion; and

decoding the symbology by locating the decodable portion of the waveform, producing a plurality of waveform descriptors relating to edge sizes of the decodable portion of the waveform and producing a decode signal representative of information contained in the decodable symbology in response to the descriptors.

38. The method according to claim 37, wherein the step of producing the decode signal comprises producing a histogram of the edge sizes in the decodable portion of the waveform.