Method of and apparatus for reading a two-dimensional bar code symbol and data storage medium

• US 20020020747A1
• Filed: 04/06/2001
• Published: 02/21/2002
• Est. Priority Date: 04/06/2000
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Arazaki, Shinichi, Yanagida, Satoshi, Wakamiya, Hitomi, Koyama, Fumio, Ohori, Haruyoshi
• Granted Patent: US 6,604,682 B2
• Time in Patent Office: Days
• US Class Current: 235/462.11
• 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/1456 determining the orientation of the optical code with respect to the reader and correcting therefore

Abstract

A two-dimensional bar code reading method and apparatus search the finder pattern in a scanned image of a two-dimensional bar code symbol, find orientation modules, find data modules, and convert the symbol to data characters as part of the decoding process for the scanned image of a MaxiCode symbol. In the data module search part of a MaxiCode symbol decoding process, position and shape information is calculated for data modules on an orientation axis, assuming an orientation axis passing the finder pattern center point, inside orientation module center point, and outside orientation module center point (step to S1801). Based on pixel data corresponding to the calculated location of the center point in each module, a bit pattern is generated where black data cells are 1 bits and white cells are 0 bits (S1802). The locations of MaxiCode symbol data modules in the area between orientation axes are then calculated (S1803). Pixel data corresponding to the calculated location of the center point of each data module is then converted to a bit pattern where 15 black data cells are 1 bits and white data cells are 0 bits (S1804), and the data module search process then ends.

Claims

1. A method of reading a two-dimensional bar code symbol having orientation modules and a finder pattern with a center point, the method comprising a data module search step for calculating position and shape information for all modules constituting the bar code symbol by calculating an orientation axis passing through an orientation module and the finder pattern center point in a scanned image of the bar code symbol based on finder pattern position, orientation module position, and orientation module shape information in the scanned image.

2. The method of claim 1, wherein the data module search step comprises the following steps:

(a) an orientation axis module position calculating step for calculating, based on finder pattern position information and orientation module position information and shape information, position and shape information for a plurality of modules constituting a module group on said orientation axis;

(b) an orientation axis data module bit pattern detecting step for detecting a bit pattern of said plural data modules on the orientation axis calculated by the orientation axis module position calculating step;

(c) a between-orientation axis module position calculating step for calculating, based on the position and shape information of the plural modules of the module group on the orientation axis calculated by the orientation axis module position calculating step, position information for a plurality of modules constituting a module group between adjacent orientation axes; and

(d) a between-orientation axis data module bit pattern detecting step for detecting the bit pattern of the plural data modules present between the orientation axes calculated by the between-orientation axis module position calculating step.

3. The method of claim 2, wherein the orientation axis module position calculating step comprises the following steps:

(a) an orientation axis angle correcting step for correcting the angle of the orientation axis so that the orientation axis passes the center points of the plural modules constituting a module group on the orientation axis;

(b) an orientation axis actual module width correcting step for calculating position information for a plurality of actual modules present on an orientation axis corrected by the orientation axis angle correcting step and based on the calculated position information correcting the module width, which is shape information for the plural actual modules;

(c) an orientation axis candidate module width correcting step for calculating position information for a plurality of candidate modules present on the orientation axis based on actual module position and shape information calculated by the orientation axis actual module width correcting step.

4. The method of claim 3, wherein the orientation axis angle correcting step to comprises the following steps:

(a) a first corrected center point calculating step for calculating, based on a black module group area containing one or a plurality of contiguous black modules present on the orientation axis, a first corrected center point of a black module closest to the finder pattern in the black module group;

(b) a second corrected center point calculating step for calculating a second corrected black module center point based on the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on a neighboring reserve axis parallel to an orientation axis adjacent to the orientation axis and passing through the first corrected black module center point calculated by the first corrected center point calculating step;

(c) a center point calculating step for calculating a black module center point based on the second corrected black module center point calculated by the second corrected center point calculating step, and the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on an orientation reserve axis passing the finder pattern center point; and

(d) an orientation axis correction angle calculating step for calculating a correction angle of an orientation axis passing the finder pattern center point and black module center point calculated by the center point calculating step.

5. The method of claim 3, wherein the orientation axis actual module width correcting step comprises a step for calculating a center point and module width of actual modules constituting a same-color actual module group based on the area of a same-color actual module group comprising one or a plurality of contiguous same color actual modules on the same orientation axis.

6. The method of claim 3, wherein the orientation axis candidate module width correcting step comprises the following steps:

(a) a reference orientation axis detecting step for detecting a reference orientation axis as the orientation axis having the least correction of all orientation axes;

(b) a step for calculating center points and module widths for a plurality of candidate modules present on an orientation axis based on shape information for the black module farthest from the finder pattern on the reference orientation axis detected by the reference orientation axis detecting step; and

(c) a step for calculating center points and module widths for a plurality of candidate modules present on an orientation axis other than the reference orientation axis based on actual module and candidate module positions on the reference orientation axis.

33. The method of any one of claims 1, 7, 15, 23 and 30, wherein the bar code symbol encodes data by means of alternating black and white cells.

34. The method of any one of claims 1, 7, 15, 23 and 30, wherein the bar code symbol is a MaxiCode symbol.

36. The apparatus of claim 35, wherein the data module search unit comprises:

(a) an orientation axis module position calculating unit for calculating, based on finder pattern position information and orientation module position information and shape information, position and shape information for a plurality of modules constituting a module group on said orientation axis;

(b) an orientation axis data module bit pattern detecting unit for detecting a bit pattern of said plural data modules on the orientation axis calculated by the orientation axis module position calculating unit;

(c) a between-orientation axis module position calculating unit for calculating, based on the position and shape information of the plural modules of the module group on the orientation axis calculated by the orientation axis module position calculating unit, position information for a plurality of modules constituting a module group between adjacent orientation axes; and

(d) a between-orientation axis data module bit pattern detecting unit for detecting the bit pattern of the plural data modules present between the orientation axes calculated by the between-orientation axis module position calculating unit.

37. The apparatus of claim 36, wherein the orientation axis module position calculating unit comprises:

(a) an orientation axis angle correcting unit for correcting the angle of the orientation axis so that the orientation axis passes the center points of the plural modules constituting a module group on the orientation axis;

(b) an orientation axis actual module width correcting unit for calculating position information for a plurality of actual modules present on an orientation axis corrected by the orientation axis angle correcting unit and based on the calculated position information correcting the module width, which is shape information for the plural actual modules;

(c) an orientation axis candidate module width correcting unit for calculating position information for a plurality of candidate modules present on the orientation axis based on actual module position and shape information calculated by the orientation axis actual module width correcting unit.

38. The apparatus of claim 37, wherein the orientation axis angle correcting unit comprises:

(a) a first corrected center point calculating unit for calculating, based on a black module group area containing one or a plurality of contiguous black modules present on the orientation axis, a first corrected center point of a black module closest to the finder pattern in the black module group;

(b) a second corrected center point calculating unit for calculating a second corrected black module center point based on the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on a neighboring reserve axis parallel to an orientation axis adjacent to the orientation axis and passing through the first corrected black module center point calculated by the first corrected center point calculating unit;

(c) a center point calculating unit for calculating a black module center point based on the second corrected black module center point calculated by the second corrected center point calculating unit, and the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on an orientation reserve axis passing the finder pattern center point; and

(d) an orientation axis correction angle calculating unit for calculating a correction angle of an orientation axis passing the finder pattern center point and black module center point calculated by the center point calculating unit.

39. The apparatus of claim 37, wherein the orientation axis actual module width correcting unit comprises a calculating unit for calculating a center point and module width of actual modules constituting a same color actual module group based on the area of a same-color actual module group comprising one or a plurality of contiguous same-color actual modules on the same orientation axis.

40. The apparatus of claim 37, wherein the orientation axis candidate module width correcting unit comprises:

(a) a reference orientation axis detecting unit for detecting a reference orientation axis as the orientation axis having the least correction of all orientation axes;

(b) a first computing unit for calculating center points and module widths for a plurality of candidate modules present on an orientation axis based on shape information for the black module farthest from the finder pattern on the reference orientation axis detected by the reference orientation axis detecting unit; and

(c) a second computing unit for calculating center points and module widths for a plurality of candidate modules present on an orientation axis other than the reference orientation axis based on actual module and candidate module positions on the reference orientation axis.

64. A machine-readable data storage medium carrying a program for implementing steps of the method as defined in any of claims 1, 7, 15, 23 and 30.

65. The data storage medium of claim 64, wherein the being a Compact Disc, floppy disk, hard disk, magneto-optical disk, Digital Versatile Disc (DVD), magnetic tape, or memory card.

7. A method of reading a two-dimensional bar code symbol having a finder pattern, is the method comprising a finder pattern search step for searching a scanned image of the bar code symbol for a scan line where a detected pattern in a specific scanning direction matches a specified reference pattern, detecting the finder pattern in the scanned bar code symbol image based on plural searched scan lines, and obtaining finder pattern position and shape information.

8. The method of claim 7, wherein the finder pattern search step comprises steps for:

(a) scanning a scanned image of the bar code symbol in a first scanning direction;

(b) obtaining a first detection pattern by means of the first scanning step;

(c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern;

(d) defining said scan line as a first center line when step (c) determines the first detection pattern matches the specific reference pattern;

(e) scanning the finder pattern in a second scanning direction that is different from the first scanning direction;

(f) obtaining a second detection pattern by means of the second scanning step;

(g) comparing the second detection pattern with the previously stored specific reference pattern;

(h) defining said scan line as a second center line when step (g) determines the second detection pattern matches the specific reference pattern; and

(i) setting the intersection of the first center line and the second center line as the center point of the finder pattern.

9. The method of claim 7, wherein the finder pattern search step comprises steps for:

(a) scanning a scanned image of a the bar code symbol in a first scanning direction;

(b) obtaining a first detection pattern by means of the first scanning step;

(c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern;

(d) setting said scan line as a first center line when step (c) determines the first detection pattern matches the specific reference pattern;

(e) setting the midpoint between the two intersections of the first center line and outside circumference member of the finder pattern as a first center point;

(f) repeating steps (b) to (e) after shifting parallel to the first center line to find plural first center points;

(g) calculating a distribution of said plural first center points to the second scanning direction, which is different from the first scanning direction;

(h) detecting a segment where the distribution to the second scanning direction is highest as a first line segment where the number of plural first center points in the second scanning direction is highest;

(i) scanning in a second scanning direction on a line where the number of plural center points in the second scanning direction is highest;

(j) obtaining a second detection pattern by means of the second scanning step;

(k) comparing the second detection pattern with the previously stored specific reference pattern;

(l) setting said scan line as a second center line when step (k) determines the second detection pattern matches the specific reference pattern; and

(m) setting the midpoint between the two intersections of the second center line and outside circumference member of the finder pattern as a second center point;

(n)finding plural second center points by shifting parallel to the second center line direction and repeating steps (j) to (m);

(o) calculating a distribution of said plural second center points to the first scanning direction;

(p) detecting a segment where the distribution to the first scanning direction is highest as a second line segment where the number of plural second center points in the first scanning direction is highest; and

(q) setting the finder pattern center point to the intersection of the first line segment and second line segment.

10. The method of claim 7, wherein the finder pattern search step comprises steps for:

(a) scanning a scanned image of the bar code symbol in a first scanning direction;

(b) obtaining a first detection pattern by means of the first scanning step;

(c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern;

(d) setting the midpoint between the two intersections of the scan line and outside circumference member of the finder pattern as a first center point when step (c) detects a match between the first detection pattern and the specific reference pattern;

(e) finding plural first center points by shifting parallel to the first scanning direction and repeating steps (b) to (d);

(f) scanning the finder pattern in a second scanning direction, which is different from the first scanning direction;

(g) obtaining a second detection pattern by means of the second scanning step;

(h) comparing the second detection pattern with the previously stored specific reference pattern;

(i) setting the midpoint between the two intersections of the scan line and outside circumference member of the finder pattern as a second center point when step (h) detects a match between the second detection pattern and the specific reference pattern;

(j) finding plural second center points by shifting parallel to the second scanning direction and repeating steps (g) to (i);

(k) setting the finder pattern center point to the intersection of a line connecting the plural first center points and a line connecting the plural second center points.

11. The method of claim 7, wherein the finder pattern search step comprises steps for:

(a) scanning a scanned image of the bar code symbol in a first scanning direction;

(b) obtaining a first detection pattern by means of the first scanning step;

(c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern;

(d) setting a first center line to the scan line from which the first detection pattern was obtained when step (c) detects a match between the first detection pattern and the specific reference pattern;

(e) setting the midpoint between the two intersections of the first center line and outside circumference member of the finder pattern as a first center point;

(f) scanning a second scanning direction different from the first scanning direction through the first center point;

(g) obtaining a second detection pattern by means of the second scanning step;

(h) comparing the second detection pattern with the previously stored specific reference pattern;

(i) setting a second center line to the scan line from which the second detection pattern was obtained when step (h) detects a match between the second detection pattern and the specific reference pattern;

(j) setting the midpoint between the two intersections of the second center line and outside circumference member of the finder pattern as a second center point;

(k) calculating two intersections of the first center line and inside circumference member of the finder pattern, and two intersections of the second center line and inside circumference member of the finder pattern, from the midpoint between two intersections of the second center line and outside circumference member of the finder pattern; and

(l) setting a barycenter determined from the two intersections of the first center line and inside circumference member of the finder pattern, and two intersections of the second center line and inside circumference member of the finder pattern, as the finder pattern center point.

12. The method of any of claims 8 to 11, wherein the second scanning direction is orthogonal to the first scanning direction.

13. The method of any of claims 8 to 11, wherein the finder pattern consists of plural concentric black circles and white circles, and

comparison of the specific reference pattern with the first detection pattern and/or second detection pattern uses a ratio between an edge-to-edge distance between concentric black circles, and an edge-to-edge distance between concentric white circles.

14. The method of claim 7, wherein the finder pattern search step comprises:

(a) a first step for comparing a detected black and white pattern of a finder pattern obtained by scanning in the first scanning direction with a specific black and white reference pattern;

(b) a second step for comparing a detected black and white pattern of a finder pattern obtained by scanning in the second scanning direction with a specific black and white reference pattern; and

(c) obtaining center coordinates of the finder pattern by means of the first step and second step.

16. The method of claim 15, wherein the image correction step generates a relation table achieving a specific correction precision by means of the equation indicating a correlation between the bar code symbol and a scanned image of the bar code symbol, and correcting the scanned image by means of the relation table.

17. The method of claim 15 or 16, wherein the bar code symbol exists on a specific plane in the image correction step.

18. The method of claim 15, wherein the scanned image is an image captured from an angle in the image correction step.

19. The method of claim 18, wherein the equation indicating a correlation between the bar code symbol and a scanned image of the bar code symbol is a bias angle correction equation, and the scanned image is corrected by computing the bias angle correction equation, in the image correction step.

20. The method of claim 19, wherein a circle in the scanned image is an element of the bar code symbol, or the shape of a deformed circle in the scanned image approximates an ellipse when a center of an element of the bar code symbol is on a specific circle.

21. The method of claim 20, wherein a bias angle correction table is generated by means of a bias angle correction equation for an ellipse based on a specific correction angle division indicative of a correction precision.

22. The method of claim 21, wherein a value of the bias angle correction equation at an angle equal to the correction angle division plus a specific offset angle is added to the bias angle correction table.

24. The method of claim 23, wherein the specific color template pattern in the orientation module search step comprises a first color template pattern, a second color template pattern, and a third color template pattern.

25. The method of claim 23, wherein the specific distance in the orientation module search step differs according to the first color template pattern, second color template pattern, and third color template pattern.

26. The method of claim 25, wherein the specific distance is the product of module width and a specific value.

27. The method of claim 26, wherein the module width is calculated based on shape information for the finder pattern in the scanned image of the bar code symbol, and a rate,

said rate being a specific interval value present in a specific range.

28. The method of claim 27, wherein the orientation module search step comprises steps for:

calculating one center point candidate for an orientation module located at said specific distance based on plural same-distance candidates for orientation module center points,

said plural same-distance candidates being plural pixel data groups found based on said specific distance; and

calculating an orientation module center point position from orientation module center point candidates at plural specific distances calculated at said rate.

29. The method of claim 23 or 28, wherein the orientation module search step comprises a step for converting position information of a scanned image of the bar code symbol so that the center point of a specific orientation module is in a specific position.

15. A method of reading a two-dimensional bar code symbol comprising an image correction step for calculating an equation indicating a correlation between code symbol and a scanned image of the bar code symbol, and correcting the scanned image of the bar code symbol based on the equation.

23. A method of reading a two-dimensional bar code symbol comprising an orientation module search step for finding in a scanned image of the bar code symbol plural pixel data groups whereof a black or white color pattern matches a specific color template pattern, the pixel data groups being disposed a specific distance from a specific point and at a specific angle interval,

detecting a plurality of orientation modules constituting an orientation module group in the scanned image of the bar code symbol based on the found plural pixel data groups, and

obtaining position and shape information for the plural orientation modules.

30. A method of reading a two-dimensional bar code symbol comprising a data character conversion step for converting data module bit data to codewords, and converting the converted codewords to specific data characters, by correlating the positions of data modules constituting a data module group in the scanned image of the bar code symbol to specific codewords and specific bit data in the specific codewords based on a specific codeword conversion table.

31. The method of claim 30, wherein data module positions in the data character conversion step are specified by a bit matrix table having elements of a matrix BT(n,m).

32. The method of claim 30 or 31, wherein when said specific codeword is an i-th codeword, and said specific bit data in said specific codeword is a j-th bit of the i-th codeword, the specific codeword conversion table in the data character conversion step is a codeword matrix table of which values CT(n,m) satisfy the following equations:

i=[CT(n,m)/256]j=CT(n,m)−

i*256.

35. An apparatus for reading a two-dimensional bar code symbol comprising a data module search unit for calculating position and shape information for all modules constituting the bar code symbol by calculating an orientation axis passing through an orientation module and finder pattern center point in a scanned image of the bar code symbol based on finder pattern position, orientation module position, and orientation module shape information in the scanned image.

62. The apparatus of any one of claims 35, 41, 44, 52 and 59, wherein the bar code symbol encodes data by means of alternating black and white cells.

63. The apparatus of any one of claims 35, 41, 44, 52 and 59, wherein the bar code symbol is a MaxiCode symbol.

41. A two-dimensional bar code reading apparatus comprising a finder pattern search unit for searching a scanned image of the bar code symbol for a scan line where a detected pattern in a specific scanning direction matches a specified reference pattern, detecting a finder pattern in the scanned bar code symbol image based on plural searched scan lines, and obtaining finder pattern position and shape information.

42. The apparatus of claim 41, wherein the finder pattern search unit comprises:

(a) a scanning unit for scanning the finder pattern in plural directions;

(b) a pattern detector for detecting a plurality of patterns by means of the scanning unit scanning plural directions;

(c) memory for storing a specific template;

(d) a comparison unit for comparing said plural patterns with each said specific template stored to memory; and

(e) a decision unit for setting scan lines of the scanning unit as at least two center lines, and determining finder pattern center coordinates based on said two center lines.

43. The apparatus of claim 41, wherein the finder pattern search unit comprises:

(a) a storage unit for prestoring a template determined by black and white pattern lengths;

(b) a scanning unit for scanning the finder pattern in first and second scanning directions, and obtaining a black and white pattern;

(c) a comparison unit for comparing black and white patterns of the finder pattern scanned by the scanning unit with said templates previously stored to the storage unit;

(d) a decision unit for setting the first scan line scanned by the scanning unit as a first center line when the comparison unit determines the black and white pattern obtained by scanning in the first scanning direction matches the black and white pattern of the template,

setting the second scan line scanned by the scanning unit as a second center line when the comparison unit determines the black and white pattern obtained by scanning in the second scanning direction matches the black and white pattern of the template, and

setting the finder pattern center point to the intersection of the first center line and second center line.

44. An apparatus for reading a two-dimensional bar code symbol comprising an image correction unit for calculating an equation indicating a correlation between the bar code symbol and a scanned image of the bar code symbol, and correcting the scanned image of the bar code symbol based on the equation.

45. The apparatus of claim 44, wherein the image correction unit generates a relation table achieving a specific correction precision by means of the equation indicating a correlation between the bar code symbol and a scanned image of the bar code symbol, and correcting the scanned image by means of the relation table.

46. The apparatus of claim 44 or 45, wherein the bar code symbol exists on a specific plane in the image correction unit.

47. The apparatus of claim 44, wherein the scanned image corrected by the image correction unit is an image captured from an angle.

48. The apparatus of claim 47, wherein the equation indicating a correlation between the bar code symbol and a scanned image of the bar code symbol is a bias angle correction equation, and the scanned image is corrected by computing the bias angle correction equation.

49. The apparatus of claim 48, wherein a circle in the scanned image is an element of the bar code symbol, or the shape of a deformed circle in the scanned image approximates an ellipse when a center of an element of the bar code symbol is on a specific circle.

50. The apparatus of claim 49, wherein a bias angle correction table is generated by means of a bias angle correction equation for an ellipse based on a specific correction angle division indicative of a correction precision.

51. The apparatus of claim 50, wherein a value of the bias angle correction equation at an angle equal to the correction angle division plus a specific offset angle is added to the bias angle correction table.

52. An apparatus for reading a two-dimensional bar code symbol comprising an orientation module search unit for finding in a scanned image of the bar code symbol plural pixel data groups whereof a black or white color pattern matches a specific color template pattern, the pixel data groups being disposed a specific distance from a specific point and at a specific angle interval,

detecting a plurality of orientation modules constituting an orientation module group in the scanned image of the bar code symbol based on the found plural pixel data groups, and

obtaining position and shape information for the plural orientation modules.

53. The apparatus of claim 52, wherein the specific color template pattern in the orientation module search unit comprises a first color template pattern, a second color template pattern, and a third color template pattern.

54. The apparatus of claim 52, wherein the specific distance in the orientation module search unit differs according to the first color template pattern, second color template pattern, and third color template pattern.

55. The apparatus of claim 54, wherein the specific distance is the product of module width and a specific value.

56. The apparatus of claim 55, wherein the module width is calculated based on shape information for the finder pattern in the scanned image of the bar code symbol, and a rate,

said rate being a specific interval value present in a specific range.

57. The apparatus of claim 56, wherein the orientation module search unit comprises:

(a) a first calculating unit for calculating one center point candidate for an orientation module located at said specific distance based on plural same-distance candidates for orientation module center points,

said plural same-distance candidates being plural pixel data groups found based on said specific distance; and

(b) a second calculating unit for calculating an orientation module center point position from orientation module center point candidates at plural specific distances calculated at said rate.

58. The apparatus of claim 52 or 57, wherein the orientation module search unit comprises a conversion unit for converting position information of a scanned image of the bar code symbol so that the center point of a specific orientation module is in a specific position.

60. The apparatus of claim 59, wherein data module positions in the data character conversion unit are specified by a bit matrix table having elements of a matrix BT(n,m).

61. The apparatus of claim 59 or 60, wherein when said specific codeword is an i-th codeword, and said specific bit data in said specific codeword is a j-th bit of the i-th codeword, the specific codeword conversion table in the data character conversion unit is a codeword matrix table of which values CT(n,m) satisfy the following equations:

i=[CT(n,m)/256]j=CT(n,m)−

i*256.

59. An apparatus for reading a two-dimensional bar code symbol comprising a data character conversion unit for converting data module bit data to codewords, and converting the converted codewords to specific data characters, by correlating the positions of data modules constituting a data module group in the scanned image of the bar code symbol to specific codewords and specific bit data in the specific codewords based on a specific codeword conversion table.