Postnet bar code decoder

• US 5,428,211 A
• Filed: 05/02/1994
• Issued: 06/27/1995
• Est. Priority Date: 05/02/1994
• 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: Li, Wenhua, Zheng, Joe
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): LEE, MICHAEL GUNYOUNG
• Application Number:
  US08/237,550
• Time in Patent Office: 421 Days
• Field of Search: 235/462, 235/472, 235/380, 235/454
• US Class Current: 235/462.02
• CPC Class Codes: G06K 7/1093 sensing, after transfer of the image of the data-field to an intermediate store, e.g. storage with cathode ray tube
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

Abstract

A method and apparatus is provided which decodes Postnet bar code regardless of position or orientation. By scanning the code, deriving transition points, and assuming various angles at orientation, position and orientation is estimated. Fine tuning and error correction is likewise provided. A localized sorting method is also used for decoding to binary status.

Claims

1. A method for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said Postnet bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said method comprising the steps of:

a) optically scanning line-by-line said two dimensional physical surface including said Postnet bar code with a CCD sensor in said scan direction along each line, said physical surface comprised of finite physical surface portions arranged in parallel rows of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said rows being substantially parallel to said scan direction;

b) storing data into computer memory as a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

e) identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars; and

f) estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points.

2. The method as claimed in claim 1, further comprising the following steps after element "f":

g) locating the pixel values corresponding to the start and end points of the Postnet code; and

h) recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

3. The method as claimed in claim 2, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

4. The method as claimed in claim 3, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

5. The method as claimed in claim 1, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

6. The method as claimed in claim 5, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

7. A method for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said Postnet bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said method comprising the steps of:

a) optically scanning line-by-line said two dimensional physical surface including said Postnet bar code with a CCD sensor in a scan direction along said lines, said physical surface comprised of finite physical surface portions arranged in parallel rows of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said rows being substantially parallel to said scan direction;

b) storing data into computer memory as a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) assuming said bar axis is oriented relative to said scan direction at a first assumed slope less than 45 degrees;

e) identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

f) identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars; and

g) determining if the number of candidate points correspond to those expected for said first assumed slope set forth in step "d";

h) repeating steps "e" and "f" at least once while assuming a second, smaller, assumed slope if step "g" is unsatisfied; and

i) if step "g" is satisfied, estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points.

8. The method as claimed in claim 7, further comprising

the following steps after element "i":

g) locating the pixel values corresponding to the start and end points of the Postnet code; and

h) recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

9. The method as claimed in claim 8, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

10. The method as claimed in claim 9, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

11. The method as claimed in claim 7, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

12. The method as claimed in claim 11, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

13. A method for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said method comprising the steps of:

a) optically scanning said two dimensional physical surface including said Postnet code with a CCD sensor in a scan direction, said physical surface comprised of finite physical surface portions arranged in parallel lines of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said columns being substantially parallel to said scan direction;

b) storing data into computer memory as a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

e) identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars;

f) estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points and establishing a slope line; and

g) determining of normal or reverse coding by checking the location said slope line intersects a particular Postnet bar relative to the ends of that bar.

14. The method as claimed in claim 13, further comprising the following steps after element "f":

g) locating the pixel values corresponding to the start and end points of the Postnet code; and

h) recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

15. The method as claimed in claim 14, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

16. The method as claimed in claim 15, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

17. The method as claimed in claim 13, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

18. The method as claimed in claim 17, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

19. A method for decoding a bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional digital input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said method comprising the steps of:

a) dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bound by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

b) determining a plurality of intensity information values representative of the intensities of corresponding sections by summing pixel values derived from said input image lying in each of said sections;

c) forming a one-dimensional intensity projection signal by arranging said plurality of intensity information values along an axis, said one dimensional intensity projection signal having a plurality of corresponding peaks having differing heights;

d) determining the existence of a bar of the Postnet bar code and its relative length based upon a comparison of the relative heights of said peaks of said one dimensional intensity projection signal.

20. A method for decoding a bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional digital input image being comprised of gray scale pixel values received from a CCD sensor, said bar code symbol said Postnet bar code having a bar axis being randomly oriented relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said method comprising the steps of:

a) dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bound by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

b) determining a plurality of intensity information values representative of the intensities of corresponding sections by summing pixel values derived from said input image lying in each of said sections;

c) locally sorting said plurality of intensity information values by positivity or negativity to create a plurality of locally sorted groups each sharing either negative or positive intensity information values;

d) selecting from each group the intensity information value having the highest absolute value to create an ordered set of absolute values; and

e) determining the existence of a bar of the Postnet bar code and its relative length based upon a comparison of adjacent absolute values within said set of absolute values.

21. An apparatus for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said Postnet bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said apparatus comprising:

a) a CCD sensor for optically scanning line-by-line said two dimensional physical surface including said Postnet bar code in said scan direction along each line, said physical surface comprised of finite physical surface portions arranged in parallel rows of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said rows being substantially parallel to said scan direction;

b) computer memory for storing data as a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) a processor for dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) a processor for identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

e) a processor for identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars; and

f) a processor for estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points.

22. The apparatus as claimed in claim 21, further comprising:

g) a processor for locating the pixel values corresponding to the start and end points of the Postnet code; and

h) a processor for recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

23. The apparatus as claimed in claim 22, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

24. The apparatus as claimed in claim 23, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

25. The apparatus as claimed in claim 21, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

26. The apparatus as claimed in claim 25, wherein in step "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

27. An apparatus for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said Postnet bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, said apparatus comprising:

a) a CCD sensor for optically scanning line-by-line said two dimensional physical surface including said Postnet bar code in a scan direction along said lines, said physical surface comprised of finite physical surface portions arranged in parallel rows of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said rows being substantially parallel to said scan direction;

b) computer memory for storing data as a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) a processor for dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) a processor for assuming said bar axis is oriented relative to said scan direction at a first assumed slope less than 45 degrees;

e) a processor for identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

f) a processor for identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars; and

g) a processor for determining if the number of candidate points correspond to those expected for said first assumed slope set forth in step "d";

h) a processor for repeating the processes in elements "e" and "f" at least once while assuming a second, smaller, assumed slope if step "g" is unsatisfied; and

i) a processor used if step "g" is satisfied, estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points.

28. The apparatus as claimed in claim 27, further comprising:

g) a processor for locating the pixel values corresponding to the start and end points of the Postnet code; and

h) a processor for recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

29. The apparatus as claimed in claim 28, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

30. The apparatus as claimed in claim 29, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

31. The apparatus as claimed in claim 27, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

32. The apparatus as claimed in claim 31, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

33. An apparatus for optically reading and decoding a Postnet bar code symbol from a two dimensional digital input image representative of said Postnet bar code symbol, said two dimensional input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented from parallel to approaching perpendicular relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, comprising:

a) a CCD sensor for optically scanning said two dimensional physical surface including said Postnet code in a scan direction, said physical surface comprised of finite physical surface portions arranged in parallel rows of physical surface portions and parallel columns of physical surface portions, each of said physical surface portions being in one of said rows and also in one of said columns, said columns being substantially parallel to said scan direction;

b) a processor for storing data into a two dimensional digital input image corresponding to said two dimensional surface, said two dimensional digital input image being comprised of individual gray scale pixel values received from said CCD sensor and each corresponding to one of said surface portions;

c) a processor for dividing said two dimensional digital input image into a plurality of non-overlapping elongated two-dimensional digital input image rows, each of which correspond to at least one row of said physical surface portions;

d) a processor for identifying one or more transition points within each of said digital input image rows by comparing adjacent pixel values within each of said digital input image rows, said transition point corresponding to at least one pixel;

e) a processor for identifying a candidate point within each of said digital input image rows by determining if a preselected number of transition points have a particular spaced-apart relationship within each of said digital input image rows, said spaced-apart relationship dependent upon the spacing of said tall and short bars;

f) a processor for estimating the slope of said bar code relative to said scan direction based upon the location of said candidate points and establishing a slope line; and

g) a processor for determining of normal or reverse coding by checking the location said slope line intersects a particular Postnet bar relative to the ends of that bar.

34. The apparatus as claimed in claim 33, further comprising:

g) locating the pixel values corresponding to the start and end points of the Postnet code; and

h) recalculating the slope of the bar code relative to the scan direction by use of said start and end points.

35. The apparatus as claimed in claim 34, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row.

36. The apparatus as claimed in claim 35, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

37. The apparatus as claimed in claim 33, wherein in element "c", said plurality of non-overlapping elongated two-dimensional dimensional digital input image rows are all spaced apart at least one row.

38. The apparatus as claimed in claim 37, wherein in element "c", said plurality of non-overlapping elongated two-dimensional digital input image rows are all spaced apart at least one row in a manner to assure that each short bar creates at least one transition point regardless of code orientation relative to scanning.

39. An apparatus for decoding a Postnet bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional digital input image being comprised of gray scale pixel values received from a CCD sensor, said Postnet bar code having a bar axis being randomly oriented relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, comprising:

a) a processor for dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bound by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

b) a processor for determining a plurality of intensity information values representative of the intensities of corresponding sections by summing pixel values derived from said input image lying in each of said sections;

c) a processor for forming a one-dimensional intensity projection signal by arranging said plurality of intensity information values along an axis, said one dimensional intensity projection signal having a plurality of corresponding peaks having differing heights;

d) a processor for determining the existence of a bar of the Postnet bar code and its relative length based upon a comparison of the relative heights of said peaks of said one dimensional intensity projection signal.

40. An apparatus for decoding a Postnet bar code symbol oriented in a bar direction from a two dimensional digital input image representative of said bar code symbol, said two dimensional digital input image being comprised of gray scale pixel values received from a CCD sensor, said bar code symbol said Postnet bar code having a bar axis being randomly oriented relative to a scan direction and located on a two-dimensional substantially planar physical surface and including a plurality of substantially parallel spaced-apart tall and short bars with all bars extending in a common direction from said bar axis, comprising:

a) a processor for dividing said two dimensional input image into a plurality of non-overlapping two dimensional sections, each of said two dimensional sections being bound by first and second reference lines substantially parallel to said bar direction and third and fourth reference lines substantially perpendicular to said bar direction, wherein said first, second, third and fourth reference lines are oriented omnidirectionally with respect to the rows and columns of pixels in said input image;

b) a processor for determining a plurality of intensity information values representative of the intensities of corresponding sections by summing pixel values derived from said input image lying in each of said sections;

c) a processor for locally sorting said plurality of intensity information values by positivity or negativity to create a plurality of locally sorted groups each sharing either negative or positive intensity information values;

d) a processor for selecting from each group the intensity information value having the highest absolute value to create an ordered set of absolute values; and

e) a processor for determining the existence of a bar of the Postnet bar code and its relative length based upon a comparison of adjacent absolute values within said set of absolute values.