Technique for reading bar codes

• US 4,873,426 A
• Filed: 08/03/1988
• Issued: 10/10/1989
• Est. Priority Date: 08/03/1988
• Status: Expired due to Fees

• Current Assignee: Image Business Systems Corp.
• Original Assignee: Image Business Systems Corp.
• Inventors: Mailick, Daniel, Sarna, David E. Y.
• Primary Examiner(s): Pitts, Harold I.
• Application Number:
  US07/227,826
• Time in Patent Office: 433 Days
• Field of Search: 235/462, 235/463
• US Class Current: 235/462.1
• 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/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code

Abstract

A technique for reading a bar code representative of message information is stored electronically in bit-map form. The bit map is obtained by optically scanning a document carrying non-bar code information also to convert pixel information into bit information. A row is identified in the bit map which is the most likely one to pass through an area in the bit map containing bar code information. The data stored in the bit map is compared with assigned data corresponding to designated bar code components. Once such a row is identified, processing of rows above and below it in the bit map reveals whether rows more likely to agree with the coded message information can be found. Initially, a fast processing mode is selected involving processing of only a few rows to maximize processing speed in case acceptable data can be found. If acceptable bar code data is not found, then the processing is switched into a slow processing mode which involves processing of a greater number of rows. Once a row likely to contain the bar code data of interest is identified, the information it contains is converted into signals which are used for converting the coded bar code data into the message represented thereby.

Claims

1. A bar code apparatus for processing digitized bar code data stored electronically in bit map form and representative of a bar code having parallel bar code components including alternating dark bars and blank spaces carried on a light reflective surface, said bar code data being obtained by scanning said surface in lines along a primary scanning direction substantially perpendicular to the bar code components and at a resolution of a predetermined number of pixels per unit length to generate for a line of said pixels respective bar code signals having values related to the amount of light reflected by said dark bars and blank spaces, respectively, and scanning in a secondary scanning direction substantially perpendicular to said primary scanning direction to traverse a plurality of said scanning lines at a resolution of a predetermined number of lines per unit length, said bit map being produced from said bar code signals and having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, the bit map bits having a bit value related to the bar code signal value of the corresponding pixels;

said apparatus comprising;

memory means for storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar code components;

means for comparing the bit map with the stored bar code component data to identify said bar code components in said bit map; and

conversion means for providing from said identified bar code components a bar code reading result for converting the bar code to the message it represents.

2. The bar code reading apparatus of claim 1, wherein the assigned bar code component data includes a range of bits allotted to at least one of said preselected bar code components for a dimension extending along said primary scanning direction.

3. The bar code reading apparatus of claim 1, wherein the comparing means comprises counting means for identifying sets of bits in a bit map row, with each set consisting of a number of contiguous bits of the same value, and means to count the number of contiguous bits in each set.

4. The bar code reading apparatus of claim 1, wherein the conversion means comprises means for indicating whether all bar code components in the bar code corresponding to the entire message information carried on the surface have been identified.

5. The bar code reading apparatus of claim 1, wherein said bit map includes rows with data corresponding to other than said selected message information, said comparing means includes means for locating at least one row in the bit map into which bar code component data corresponding to the coded version of the selected message information has been stored.

6. The bar code reading apparatus of claim 5, wherein said row locating means comprises means for counting a string of consecutive bar code components identified by said comparing means for each of at least two rows of the bit map, and selecting the row with the longest string.

7. The bar code reading apparatus of claim 6, wherein said row locating means comprises means for designating said at least two rows of the bit map based on a dimension of the bar code components in the secondary scanning direction relative to the number of rows in the bit map.

8. The bar code reading apparatus of claim 7, where the designating means follows the relationship N=N=MN/(BH-1), where N is the number of designated rows, MN is the number of rows in the bit map, and BH is said dimension of the bar code in the secondary direction, as expressed in rows.

9. The bar code reading apparatus of claim 8, wherein the spacing between the at least two designated rows is chosen based on the relationship INT=MN/N, where INT is said spacing expressed in rows.

10. The bar code reading apparatus of claim 9, wherein the first row of the at least two designated rows is chosen by the choosing means to be INT/2.

11. The bar code reading apparatus of claim 6 wherein said row locating means comprises further means for designating additional rows in the bit map vicinity of the selected row, and for determining whether any of the additional designated rows includes a longer string than the longest string found in said at least two designated rows and, if so, selecting such additional row.

12. The bar code reading apparatus of claim 11, wherein said row locating means includes confirming means for indicating whether all bar code components corresponding to the entire message information in the bar code carried on the surface have been identified.

13. The bar code reading apparatus of claim 12, wherein said further means chooses an initial number A of additional designated rows and, if said confirming means indicates a failure, it chooses a number B of additional designated rows, with B>

A.

14. The bar code reading apparatus of claim 13, wherein said additional designated rows include at least one above and at least one below said selected row.

15. The bar code reading apparatus of claim 6, wherein said conversion means includes means for processing only bits stored in the longest string of the selected row.

16. Apparatus for determining a bar code from a bit map obtained by a plurality of optically scanned lines of a light reflective surface area, at least part of which carries said bar code having components including alternating dark bars and blank spaces representative of selected message information, and scanned with a resolution of a predetermined number of pixels per unit length to input data into said bit map related to light reflected by respective pixels of said surface, said bit map having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, comprising:

means for storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar components;

means for designating at least two rows in said bit map;

means for comparing the at least two designated rows with said assigned bar code component data to provide an identified bar code component signal;

means coupled to the comparing means for identifying the longest string of consecutive bar code components for each of said designated rows;

means for selecting whichever of said designated rows has the longest string of consecutive bar code components; and

means coupled to the selecting means for obtaining a bar code reading result from the selected designated row for converting the bar code to said selected message information.

17. The apparatus of claim 16, wherein the bar code has a given height in a direction substantially perpendicular to said scanned lines of pixels and said bit map having rows with data corresponding to other than said selected message information, said designating means comprising means for setting the location of, and spacing between, said at least two designated rows to have at least one of such rows coincide with a row in the bit map having data representing said bar code stored therein which corresponds to the selected message information.

18. The bar code reading apparatus of claim 17, wherein the assigned bar code component data includes a range of bits allotted to at least one of said preselected bar code components for a dimension extending along said scanning lines.

19. The bar code reading apparatus of claim 18, wherein the comparing means comprises counting means for identifying sets of bits in a bit map row, with each set consisting of a number of contiguous bits of the same value, and means to count the number of contiguous bits in each set.

20. The bar code reading apparatus of claim 19, wherein said conversion means comprises means to generate a match signal when coincidence is found between the number of bits in a set and said assigned bar code component data, and means for relating a particular match signal to a particular bar code component to produce said identified bar code component signals.

21. The bar code reading apparatus of claim 16, wherein said row designating means comprises means for designating said at least two rows of the bit map based on the number of rows in the bit map relative to a dimension of the bar code components in a direction perpendicular to the scanning lines.

22. The bar code reading apparatus of claim 21, where the designating means follows the relationship N=MN/(BH-1), where N is the number of designated rows, MN is the number of rows in expressed in rows, in a direction perpendicular to the scanning lines.

23. The bar code reading apparatus of claim 22, wherein the spacing between the at least two designated rows is chosen based on the relationship INT=MN/N, where INT is said spacing expressed in rows.

24. The bar code reading apparatus of claim 23, wherein the first row of the at least two designated rows is chosen by the choosing means to be INT/2.

25. The bar code reading apparatus of claim 24, wherein said row designating means comprises further means for designating additional rows in the bit map vicinity of the selected row, and for determining whether any of the additional designated rows includes a longer string than the longest string found in said at least two designated rows and, if so, selecting such additional row.

26. The bar code reading apparatus of claim 25, wherein said row designating means includes confirming means for indicating whether all bar code components corresponding to the entire message information in the bar code carried on the surface have been identified.

27. The bar code reading apparatus of claim 26, wherein said further means chooses an initial number A of additional designated rows and, if said confirming means indicates a failure, it chooses a number B of additional designated rows, with B>

A.

28. The bar code reading apparatus of claim 27, wherein said additional designated rows include at least one above and at least one below said selected row.

29. The apparatus of claim 16, further comprising means for retrieving from the bit map at least one additional row in the vicinity of said selected designated row;

said comparing means, identifying means, and selecting means providing a processed designated row indicative of whether the at least one additional row includes a string of consecutive bar code components longer than in said selected designated row.

30. The bar code reading apparatus of claim 16, wherein said conversion means includes means for processing only bits stored in the longest string of the selected row.

31. A bar code reading apparatus comprising:

means for optically detecting a bar code with which selected message information has been converted into a coded version, said bar code having parallel bar code components including alternating dark bars and blank spaces carried on a light reflective surface, said detecting means scanning said surface in lines along a primary scanning direction substantially perpendicular to the bar code components and at a resolution of a predetermined number of pixels per unit length to generate for a line of said pixels respective bar code signals having values related to the amount of light reflected by said dark bars and blank spaces, respectively, said detecting means moving in a secondary scanning direction substantially perpendicular to said primary scanning direction to traverse a plurality of said scanning lines at a resolution of a predetermined number of lines per unit length;

means coupled to the detecting means for producing from said bar code signals a bit map having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, the bit map bits having a bit value related to the bar code signal value of the respective corresponding pixels;

memory means for storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar code components;

means for comparing the bit map with the stored bar code component data to identify said bar code components in said bit map; and

conversion means for providing from said identified bar code components a bar code reading result for converting the bar code to said selected message information.

32. The bar code reading apparatus of claim 31, wherein said detecting means comprises an analog signal generating means for providing an output signal having an amplitude related to the amount of light reflected by the bar code components, and means for digitizing said output signal for each of said pixels to be input to the bit map.

33. The bar code reading apparatus of claim 31, wherein said bit map producing means comprises a memory having addressable memory locations corresponding to bits in said bit map.

34. The bar code reading apparatus of claim 31, wherein the assigned bar code component data includes a range of bits allotted to at least one of said preselected bar code components for a dimension extending along said primary scanning direction.

35. The bar code reading apparatus of claim 31, wherein the comparing means comprises counting means for identifying sets of bits in a bit map row, with each set consisting of a number of contiguous bits of the same value, and means to count the number of contiguous bits in each set.

36. The bar code reading apparatus of claim 35, wherein said conversion means comprises means to generate a match signal when coincidence is found between the number of bits in a set and said assigned bar code component data, and means for relating a particular match signal to a particular bar code component to produce said identified bar code component signals.

37. The bar code reading apparatus of claim 31, wherein the conversion means comprises means for indicating whether all bar code components in the bar code corresponding to the entire message information carried on the surface have been identified.

38. The bar code reading apparatus of claim 31, wherein the conversion means includes validating means to confirm whether all the identified bar code components in each processed row of the bit map correspond to a valid bar code.

39. The bar code reading apparatus of claim 31, wherein said bit map includes rows with data corresponding to other than said selected message information, said comparing means includes means for locating at least one row in the bit map into which bar code component data corresponding to the coded version of the selected message information has been stored.

40. The bar code reading apparatus of claim 39, wherein said row locating means comprises means for counting a string of consecutive bar code components identified by said comparing means for each of at least two rows of the bit map, and selecting the row with the longest string.

41. The bar code reading apparatus of claim 40, wherein said row locating means comprises means for designating said at least two rows of the bit map based on a dimension of the bar code components in the secondary scanning direction relative to the number of rows in the bit map.

42. The bar code reading apparatus of claim 41, where the designating means follows the relationship N=MN/(BH-1), where N is the number of designated rows, MN is the number of rows in the bit map, and BH is said dimension of the bar code in the secondary direction, as expressed in rows.

43. The bar code reading apparatus of claim 42, wherein the spacing between the at least two designated rows is chosen based on the relationship INT=MN/N, where INT is said spacing expressed in rows.

44. The bar code reading apparatus of claim 43, wherein the first row of the at least two designated rows is chosen by the choosing means to be INT/2.

45. The bar code reading apparatus of claim 40, wherein said row locating means comprises further means for designating additional rows in the bit map vicinity of the selected row, and for determining whether any of the additional designated rows includes a longer string than the longest string found in said at least two designated rows and, if so, selecting such additional row.

46. The bar code reading apparatus of claim 45, wherein said row locating means includes confirming means for indicating whether all bar code components corresponding to the entire message information in the bar code carried on the surface have been identified.

47. The bar code reading apparatus of claim 46, wherein said further means chooses an initial number A of additional designated rows and, if said confirming means indicates a failure, it chooses a number B of additional designated rows, with B>

A.

48. The bar code reading apparatus of claim 47, wherein said additional designated rows include at least one above and at least one below said selected row.

49. The bar code reading apparatus of claim 40, wherein said conversion means includes means for processing only bits stored in the longest string of the selected row.

50. A method for processing digitized bar code data stored electronically in bit map form and representative of a bar code having parallel bar code components including alternating dark bars and blank spaces carried on a light reflective surface, said bar code data being obtained by scanning said surface in lines along a primary scanning direction substantially perpendicular to the bar code components and at a resolution of a predetermined number of pixels per unit length to generate for a line of said pixels respective bar code signals having values related to the amount of light reflected by said dark bars and blank spaces, respectively, and scanning in a secondary scanning direction substantially perpendicular to said primary scanning direction to traverse a plurality of said scanning lines at a resolution of a predetermined number of lines per unit length, said bit map being produced from said bar code signals and having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, the bit map bits having a bit value related to the bar code signal value of the corresponding pixels;

said method comprising the steps of;

storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar code components;

comparing the bit map with the stored bar code component data to identify said bar code components in said bit map; and

providing from said identified bar code components a bar code reading result for converting the bar code to the message it represents.

51. A method for determining a bar code from a bit map obtained by a plurality of optically scanned lines of a light reflective surface area, at least part of which carries said bar code having components including alternating dark bars and blank spaces representative of selected message information, and scanned with a resolution of a predetermined number of pixels per unit length to input data into said bit map related to light reflected by respective pixels of said surface, said bit map having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, comprising the steps of:

storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar components;

designating at least two rows in said bit map;

comparing the at least two designated rows with said assigned bar code component data to provide an identified bar code component signal;

identifying the longest string of consecutive bar code components for each of said designated rows;

selecting whichever of said designated rows has the longest string of consecutive bar code components; and

obtaining a bar code reading result from the selected designated row for converting the bar code to said selected message information.

52. A method for reading a bar code comprising the steps of:

optically detecting a bar code with which selected message information has been converted into a coded version, said bar code having parallel bar code components including alternating dark bars and blank spaces carried on a light reflective surface, said surface being scanned in lines along a primary scanning direction substantially perpendicular to the bar code components and at a resolution of a predetermined number of pixels per unit length to generate for a line of said pixels respective bar code signals having values related to the amount of light reflected by said dark bars and blank spaces, respectively, said scanning also moving in a secondary scanning direction substantially perpendicular to said primary scanning direction to traverse a plurality of said scanning lines at a resolution of a predetermined number of lines per unit length;

producing from said bar code signals a bit map having a plurality of bits arranged in rows, said rows corresponding, respectively, to the scanning lines, and the bits in each row corresponding to the pixels in a corresponding one of said scanning lines, the bit map bits having a bit value related to the bar code signal value of the respective corresponding pixels;

storing assigned bar code component data related to a number of bits allotted, respectively, in a row of said bit map to said bar code components;

comparing the bit map with the stored bar code component data to identify said bar code components in said bit map; and

providing from said identified bar code components a bar code reading result for converting the bar code to said selected message information.