Finder pattern for optically encoded machine readable symbols

• US 5,189,292 A
• Filed: 10/30/1990
• Issued: 02/23/1993
• Est. Priority Date: 10/30/1990
• Status: Expired due to Term

• Current Assignee: Omniplanar, Inc. (Honeywell International Inc.)
• Original Assignee: Omniplanar, Inc. (Honeywell International Inc.)
• Inventors: Batterman, Eric P., Chandler, Donald G.
• Primary Examiner(s): LaRoche, Eugene R.
• Assistant Examiner(s): GLEMBOCKI, CHRISTOPHE
• Application Number:
  US07/606,016
• Time in Patent Office: 847 Days
• Field of Search: 235/456, 235/487, 235/494, 235/469, 382/48, 382/34, 382/56, 380/51
• US Class Current: 235/494
• CPC Class Codes: G06K 19/00 Record carriers for use with machines and with at least a part designed to carry digital markings
• 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/1417 2D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image

Abstract

An optically encoded information bearing label containing a two dimensional array of data cells includes a finder pattern comprising a plurality of spots arranged in a predetermined geometric pattern substantially analogous to the predetermined geometric pattern of said two dimensional array of data cells. The finder pattern is detected by first scanning the image area to detect spots. The locations of detected spots are compared to the known geometry of the finder pattern in order to provide for rapid and reliable finding of the finder pattern and the information bearing label. Additionally, the detected finder pattern spots provide information for decoding the two dimensional data array in order to compensate for label magnification, tilt and other distortions.

Claims

1. An optically encoded label, including an improved finder pattern, comprising:

a two dimensional data array of optically encoded data cells arranged in a predetermined geometric data array pattern; and

a plurality of spots, wherein

said plurality of spots is arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric data array pattern.

2. In an optically encoded label in accordance with claim 1 further containing a two dimensional array of data cells, an improved finder pattern further comprising:

wherein each of said plurality of spots occupies an area substantially equal to the area of a data cell of said two dimensional array of data cells.

3. In an optically encoded label in accordance with claim 2, an improved finder pattern further comprising:

wherein each of said plurality of spots occupies an area substantially equal to the area of a data cell of said two dimensional array of data cells having a first reflectivity; and

wherein each of said plurality of spots is substantially surrounded by a plurality of areas of a second reflectivity each substantially equal to the area of a data cell of said two dimensional array of data cells data cells.

4. An improved finder pattern for use in an optically encoded label in accordance with claim 1, wherein said plurality of spots are arranged in a symmetrical geometric pattern.

5. An improved finder pattern for use in an optically encoded label in accordance with claim 1, wherein said plurality of spots are arranged in an asymmetrical geometric pattern.

6. An improved finder pattern for use in an optically encoded label in accordance with claim 1, wherein said plurality of spots are arranged in a regular geometric pattern.

7. An improved finder pattern for use in an optically encoded label in accordance with claim 1, wherein said predetermined geometric pattern of said plurality of spots comprises the 6 points at the vertices of a regular hexagon plus the center point.

8. In an optically encoded label containing a two dimensional array of data cells arranged in a predetermined geometric pattern, an improved finder pattern further comprising:

a plurality of spots, wherein

said plurality of spots is arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said plurality of said data cells.

9. In a system for reading an optically encoded label having a finder pattern comprising a plurality of spots, wherein said plurality of spots is arranged in a two dimensional array having a predetermined geometric pattern, a method for detecting the location of said optically encoded label comprising:

capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

examining said stored two dimensional image to detect said plurality of spots; and

matching said detected plurality of spots to said predetermined geometric pattern.

10. A method in accordance with claim 9, wherein said step of examining said stored two dimensional image to detect said plurality of spots comprises:

determining the optical values of stored pixels surrounding a given pixel of said stored two dimensional image, said surrounding pixels being approximately a predetermined fixed distance from said given pixel.

11. A method in accordance with claim 10, wherein said predetermined fixed distance from said given pixel to each of said surrounding pixels is substantially equal to the respective diameter of each of said plurality of spots.

12. A method in accordance with claim 11, wherein said step of determining the optical values of said stored pixels surrounding a given pixel of said stored two dimensional image is repeated for each pixel in said stored two dimensional image.

13. A method in accordance with claim 12 further comprising:

identifying the corresponding locations of said given pixels for which a predetermined number of said surrounding pixels said predetermined fixed distance from said given pixel, are of a contrasting reflectivity compared to the reflectivity of each of said respective given pixels.

14. A method in accordance with claim 13, wherein the number of said surrounding pixels is equal to 8, and said predetermined number of said surrounding pixels is equal to 7.

15. A method in accordance with claim 9, wherein said step of matching said detected plurality of spots to said predetermined geometric pattern comprises:

selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern.

16. A method in accordance with claim 9, wherein said step of matching said detected plurality of spots to said predetermined geometric pattern comprises:

selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

17. A method in accordance with claim 9, wherein said step of matching said detected plurality of spots to said predetermined geometric pattern comprises:

selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

assuming said selected pair of detected spots corresponds to a radius of said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern.

18. A method in accordance with claim 9, wherein said step of matching said detected plurality of spots to said predetermined geometric pattern comprises:

selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

assuming said selected pair of detected spots corresponds to a radius of said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

19. A method in accordance with claim 9 wherein said step of matching said plurality of spots to said predetermined geometric pattern comprises:

selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern;

matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern;

assuming said selected pair of detected spots corresponds to a radius of said predetermined geometric pattern;

matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern; and

matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

20. In a system for reading an optically encoded label containing a two dimensional array of data cells arranged in a predetermined geometric pattern, a method for reading said optically encoded label data comprising:

capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

constructing a cell center sampling pattern having a plurality of points arranged in a geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells;

positioning said cell center sampling pattern over said two dimensional array of data cells at a first position;

repositioning said cell center sampling pattern over said two dimensional array of data cells at a second position substantially adjacent to said first position;

selecting an optimal position from said first and second positions of said cell center sampling pattern by optimizing a function of image pixels corresponding to said plurality of points, so that said plurality of points of said cell center sampling pattern substantially corresponds to the approximate centers of said data cells, respectively; and

reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said optimal position of said cell center sampling pattern.

21. A method in accordance with claim 20, wherein said step of positioning said cell center sampling pattern comprises:

computing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said cell center sampling pattern.

22. A method in accordance with claim 21 further comprising:

moving said cell center sampling pattern to a neighboring point surrounding the approximate centers of said data cells;

recomputing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said moved cell center sampling pattern; and

selecting the cell center sampling pattern position having the maximum computed standard deviation as the position corresponding to the approximate true centers of said data cells.

23. A method in accordance with claim 20 wherein said step of reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said positioned cell center sampling pattern comprises:

taking a histogram of said optical values substantially corresponding to the approximate centers of said data cells;

establishing a threshold between the maximum and minimum values of said optical values substantially corresponding to the approximate centers of said data cells; and

reading out the optical values of said data cells using said established threshold as a reference.

24. A method in accordance with claim 20, wherein said optically encoded label further contains a finder pattern comprising a plurality of spots arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells, wherein said step of constructing a cell center sampling pattern further comprises:

examining said stored two dimensional image to detect said plurality of spots comprising said finder pattern; and

constructing said cell center sampling pattern using said detected plurality of finder spots.

25. In a system for reading an optically encoded label containing a two dimensional array of data cells arranged in a predetermined geometric pattern, a method for reading said optically encoded label data comprising:

capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

constructing a cell center sampling pattern having a plurality of points arranged in a geometric pattern with a known predetermined relationship to the predetermined geometric pattern of said two dimensional array of data cells;

positioning said cell center sampling pattern over said two dimensional array of data cells so that said plurality of points of said cell center sampling pattern substantially corresponds to the approximate centers of said data cells;

moving said cell center sampling pattern a distance to an adjacent point, said distance moved substantially corresponding to the width of a data cell of said optically encoded label;

repositioning said moved cell center sampling pattern of said two dimensional array of data cells so that said plurality of points of said moved cell center sampling pattern substantially corresponds to the approximate centers of said data cells, respectively;

averaging the respective coordinates of the points of said positioned and repositioned cell center sampling pattern to provide a plurality of averaged data cell centers; and

reading out the optical values of said data cells using said respective averaged coordinates of said data cell centers.

26. A method in accordance with claim 25, wherein said step of positioning said cell center sampling pattern comprises:

computing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said cell center sampling pattern.

27. A method in accordance with claim 26 further comprising:

moving said cell center sampling pattern to a neighboring point surrounding the approximate centers of said data cells;

recomputing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said moved cell center sampling pattern; and

selecting the cell center sampling pattern position having the maximum computed standard deviation as the position corresponding to the approximate true centers of said data cells.

28. A method in accordance with claim 25 wherein said step of reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said positioned cell center sampling pattern comprises:

taking a histogram of said optical values substantially corresponding to the approximate centers of said data cells;

establishing a threshold between the maximum and minimum values of said optical values substantially corresponding to the approximate centers of said data cells; and

reading out the optical values of said data cells using said established threshold as a reference.

29. A method in accordance with claim 25, wherein said optically encoded label further contains a finder pattern comprising a plurality of spots arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells, wherein said step of constructing a cell center sampling pattern further comprises:

examining said stored two dimensional image to detect said plurality of spots comprising said finder pattern; and

constructing said cell center sampling pattern using said detected plurality of finder spots.

30. In a system for reading an optically encoded label having a finder pattern comprising a plurality of spots, wherein said plurality of spots is arranged in a two dimensional array having a predetermined geometric pattern, an apparatus for detecting the location of said optically encoded label comprising:

means for capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

means for examining said stored two dimensional image to detect said plurality of spots; and

means for matching said detected plurality of spots to said predetermined geometric pattern.

31. An apparatus in accordance with claim 30, wherein said means for examining said stored two dimensional image to detect said plurality of spots comprises:

means for determining the optical values of stored pixels surrounding a given pixel of said stored two dimensional image, said surrounding pixels being approximately a predetermined fixed distance from said given pixel.

32. An apparatus in accordance with claim 31, wherein said predetermined fixed distance from said given pixel to each of said surrounding pixels is substantially equal to the respective diameter of each of said plurality of spots.

33. An apparatus in accordance with claim 32, wherein said means for determining the optical values of said stored pixels surrounding a given pixel of said stored two dimensional image includes means for repeating said determination for each pixel in said stored two dimensional image.

34. An apparatus in accordance with claim 33 further comprising:

means for identifying the corresponding locations of said given pixels for which a predetermined number of said surrounding pixels said predetermined fixed distance from said given pixel, are of a contrasting reflectivity compared to the reflectivity of each of said respective given pixels.

35. An apparatus in accordance with claim 34, wherein the number of said surrounding pixels is equal to 8, and said predetermined number of said surrounding pixels is equal to 7.

36. An apparatus in accordance with claim 30, wherein said means for matching said detected plurality of spots to said predetermined geometric pattern comprises:

means for selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

means for assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

means for matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern.

37. An apparatus in accordance with claim 30, wherein said means for matching said detected plurality of spots to said predetermined geometric pattern comprises:

means for selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

means for assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

means for matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

38. An apparatus in accordance with claim 30, wherein said means for matching said detected plurality of spots to said predetermined geometric pattern comprises:

means for selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

means for assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

means for matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern.

39. An apparatus in accordance with claim 30, wherein said means for matching said detected plurality of spots to said predetermined geometric pattern comprises:

means for selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

means for assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern; and

means for matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

40. An apparatus in accordance with claim 30 wherein said means for matching said plurality of spots to said predetermined geometric pattern comprises:

means for selecting a pair of said plurality of detected spots, wherein the spacing between said selected pair of detected spots approximately corresponds to the spacing between two of said finder spots;

means for assuming said selected pair of detected spots corresponds to an edge of said predetermined geometric pattern;

means for matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern;

means for matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

means for assuming said selected pair of detected spots corresponds to a radius of said predetermined geometric pattern;

means for matching the remaining spots of said plurality of detected spots to said predetermined geometric pattern; and

means for matching the remaining spots of said plurality of detected spots to a flipped image of said predetermined geometric pattern.

41. In a system for reading an optically encoded label containing a two dimensional array of data cells arranged in a predetermined geometric pattern, an apparatus for reading said optically encoded label data comprising:

means for capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

means for constructing a cell center sampling pattern having a plurality of points arranged in a geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells;

means for positioning said cell center sampling pattern over said two dimensional array of data cells at a first position;

repositioning said cell center sampling pattern over said two dimensional array of data cells at a second position substantially adjacent to said first position;

selecting an optimal position from said first and second positions of said cell center sampling pattern by optimizing a function of image pixels corresponding to said plurality of points, so that said plurality of points of said cell center sampling pattern substantially corresponds to the approximate centers of said data cells, respectively; and

means for reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said optimal position of said cell center sampling pattern.

42. An apparatus in accordance with claim 41, wherein said means for positioning said cell center sampling pattern comprises:

means for computing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said cell center sampling pattern.

43. An apparatus in accordance with claim 42, further comprising:

means for moving said cell enter sampling pattern to a neighboring point surrounding the approximate centers of said data cells;

means for recomputing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said moved cell center sampling pattern; and

means for selecting the cell center sampling pattern position having the maximum computed standard deviation as the position corresponding to the approximate true centers of said data cells.

44. An apparatus in accordance with claim 41, wherein said means for reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said positioned cell center sampling pattern comprises:

means for taking a histogram of said optical values substantially corresponding to the approximate centers of said data cells;

means for establishing a threshold between the maximum and minimum values of said optical values substantially corresponding to the approximate centers of said data cells; and

means for reading out the optical values of said data cells using said established threshold as a reference.

45. A method in accordance with claim 41, wherein said optically encoded label further contains a finder pattern comprising a plurality of spots arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells, wherein said step of constructing a cell center sampling pattern further comprises:

means for examining said stored two dimensional image to detect said plurality of spots comprising said finder pattern; and

means for constructing said cell center sampling pattern using said detected plurality of finder spots.

46. In a system for reading an optically encoded label containing a two dimensional array of data cells arranged in a predetermined geometric pattern, an apparatus for reading said optically encoded label data comprising:

means for capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of said optically encoded label anywhere within the field of view of said stored two dimensional image;

means for constructing a cell center sampling pattern having a plurality of points arranged in a geometric pattern with a known predetermined relationship to the predetermined geometric pattern of said two dimensional array of data cells;

means for positioning said cell center sampling pattern over said two dimensional array of data cells so that said plurality of points of said cell center sampling pattern substantially corresponds to the approximate centers of said data cells;

means for moving said cell center sampling pattern a distance to an adjacent point, said distance moved substantially corresponding to the width of a data cell of said optically encoded label;

means for repositioning said moved cell center sampling pattern of said two dimensional array of data cells so that said plurality of points of said moved cell center sampling pattern substantially corresponds to the approximate centers of said data cells, respectively;

means for averaging the respective coordinates of the points of said positioned and repositioned cell center sampling pattern to provide a plurality of averaged data cell centers; and

means for reading out the optical values of said data cells using said respective averaged coordinates of said data cell centers.

47. An apparatus in accordance with claim 46, wherein said means for positioning said cell center sampling pattern comprises:

means for computing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said cell center sampling pattern.

48. An apparatus method in accordance with claim 47, further comprising:

means for moving said cell enter sampling pattern to a neighboring point surrounding the approximate centers of said data cells;

means for recomputing the standard deviation of the optical values of said pixels respectively corresponding to said respective plurality of points of said moved cell center sampling pattern; and

means for selecting the cell center sampling pattern position having the maximum computed standard deviation as the position corresponding to the approximate true centers of said data cells.

49. An apparatus in accordance with claim 46, wherein said means for reading out the optical values of said data cells respectively corresponding to said respective plurality of points of said positioned cell center sampling pattern comprises:

means for taking a histogram of said optical values substantially corresponding to the approximate centers of said data cells;

means for establishing a threshold between the maximum and minimum values of said optical values substantially corresponding to the approximate centers of said data cells; and

means for reading out the optical values of said data cells using said established threshold as a reference.

50. A method in accordance with claim 46, wherein said optically encoded label further contains a finder pattern comprising a plurality of spots arranged in a two dimensional array having a predetermined geometric pattern with a known predetermined relationship to said predetermined geometric pattern of said two dimensional array of data cells, wherein said step of constructing a cell center sampling pattern further comprises:

means for examining said stored two dimensional image to detect said plurality of spots comprising said finder pattern; and

means for constructing said cell center sampling pattern using said detected plurality of finder spots.

51. An apparatus for finding an optically encoded label having a finder pattern comprising a plurality of spots arranged in a two dimensional array having a predetermined geometric pattern, said apparatus comprising:

means for capturing a two dimensional image for storage in a memory, said stored two dimensional image containing an image of an optically encoded label anywhere within the field of view of said stored two dimensional image;

a first data processor for detecting individual ones of said plurality of spots; and

a second data processor for matching said detected individual ones of said plurality of spots to said predetermined geometric pattern.

52. An apparatus in accordance with claim 51 wherein said optically encoded label further comprises a two dimensional array of data cells having a predetermined geometric pattern with a know predetermined relationship to said predetermined geometric pattern of said plurality of spots, said apparatus further comprising:

a third data processor coupled to said second data processor for reading out data from said optically encoded label.