Hexagonal, information encoding article, process and system

• US 4,874,936 A
• Filed: 04/08/1988
• Issued: 10/17/1989
• Est. Priority Date: 04/08/1988
• 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: Batterman, Eric P., Chandler, Donald G., Shah, Govind
• Primary Examiner(s): Pitts, Harold I.
• Application Number:
  US07/178,600
• Time in Patent Office: 557 Days
• Field of Search: 235/487, 235/494
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 2019/06262 with target- or other orientation-indicating feature
• 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
• CPC Class Codes: Y10S 283/901 Concealed data

Abstract

The article of the invention is an optically readable label for storing encoded information, said label comprising a data energy of a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, and having at least two different optical properties.

A process for encoding information in an optically-readable data array comprised of a honeycomb of contiguous hexagons encoded by assigning optical properties to individual hexagons in a predetermined pattern, ordering the hexagons in a predetermined sequence, and printing the hexagons with at least two optical properties.

A process for retrieving information by optically scanning an information-encoded data array of contiguous polygons, preferably hexagons, creating an optical replica of the digital bit stream representative of the optical properties of the information encoded polygons, decoding that optical replica and retrieving the decoded bit stream.

A stream for performing the foregoing encoding and decoding processes.

Claims

1. An optically readable label for storing encoded information comprising a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, each hexagon having one of at least two different optical properties.

2. An article as recited in claim 1, wherein said optical properties are the colors black, white and gray.

3. An article as recited in claim 1, wherein more important information is encoded in hexagons proximate the center of said article.

4. An article as recited in claim 1, wherein the information encoded in said hexagons includes at least a first and second message area and said first message area is located farther from the periphery of said article than said second message area.

5. An article as recited in claim 1, wherein said information-encoded hexagons are encoded with message information and error detection information, thereby allowing errors in the message information retrieved from said article to be detected.

6. An article as recited in claim 5, wherein said error detection information may be utilized to correct errors in the message information retrieved from said article.

7. An article as recited in claim 1, further comprising a plurality of Concentric Rings occupying an area on said article separate from the area occupied by said information-encoded hexagons, each Concentric Ring having one of at least two different optical properties in alternating sequence.

8. An article as recited in claim 7, wherein said Concentric Rings are centrally located on said article.

9. An article as recited in claim 8, wherein said contiguous information-encoded hexagons are arranged in up to about fifty rows and up to about fifty columns within an area of up to about one square inch.

10. An article as recited in claim 8, wherein said contiguous information-encoded hexagons are arranged in up to about thirty-three rows and up to about thirty columns within an area of up to about one square inch and wherein said Concentric Rings occupy less than about ten percent of the area of said article.

11. An article as recited in claim 7, wherein the information encoded in said hexagons includes at least a first and second message area and said first message area is located farther from the periphery of said article than said second message area.

12. An article as recited in claim 7, wherein the Concentric Rings occupy less than about twenty-five percent of the area of said article.

13. An article as recited in claim 7, wherein more important information is encoded in hexagons proximate to the center of said article.

14. An article as recited in claim 7, wherein said optical properties of said hexagons are the colors black, white and gray.

15. An article as recited in claim 14, wherein the optical properties of said Concentric Rings are the same as two of the two or more optical properties of said hexagons.

16. An article as recited in claim 15, wherein the optical properties of said Concentric Rings are alternately black and white.

17. An optically readable label for storing encoded information comprising a multiplicity of contiguously arranged, information-encoded polygons other than squares or rectangles, each polygon having one of at least two different optical properties.

18. An article as recited in claim 17, further comprising a plurality of Concentric Rings on said article, each Concentric Ring alternately having one of at least two different optical properties.

19. An article as recited in claim 18, wherein said Concentric Rings are centrally located on said article.

20. A process for encoding information in an optically-readable label comprising a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, each hexagon having one of at least two optical properties, comprising the steps of:

(a) assigning one of at least two optical properties to each hexagon to create a plurality of contiguous hexagons having different optical properties;

(b) encoding the information by ordering the hexagons in a predetermined sequence; and

(c) printing each hexagon in its assigned optical property.

21. A process as recited in claim 20, further comprising the steps of:

(d) assigning a plurality of dots in a dot matrix to define the optical property of each hexagon; and

(e) printing said plurality of dots.

22. A process as recited in claim 20, wherein step (b) includes the step of mapping groups of two or more contiguous hexagons in predetermined geographical areas on said article.

23. A process as recited in claim 21, wherein step (b) includes the step of mapping groups of two or more contiguous hexagons in predetermined geographical areas on said article.

24. A process as recited in claims 22 or 23, further comprising the steps of dividing the information being encoded into at least two categories of higher and lower priorities, and encoding said higher and lower priority information in separate, predetermined geographical areas.

25. A process as recited in claim 20, further comprising the step of encoding a plurality of selected hexagons with error detection information and interposing said error detection encoded hexagons among said hexagons.

26. A process as recited in claim 24, further comprising the step of encodng a plurality of selected hexagons with error detection information and interposing said error detection encoded hexagons among said hexagons.

27. A process as recited in claim 26, wherein separate encoded error detection information is separately applied to said higher and lower priority information.

28. A process as recited in claim 25, wherein said encoded error detection information may be utilized to correct errors in the information retrieved from said article.

29. A process as recited in claim 27, wherein said error detection information may be utilized to correct errors in the information retrieved from said article.

30. A process as recited in claims 20 or 21, wherein said encoding step is structured to optimize the number of contiguous hexagons having different optical properties.

35. A process as recited in claim 31,wherein said hexagons are encoded in accordance with the process of claim 20.

36. A process as recited in claim 31, wherein said hexagons are encoded in accordance with the process of claim 22.

41. A process as recited in claim 37, wherein said hexagons are encoded in accordance with the process of claim 20.

42. A process as recited in claim 37, wherein said hexagons are encoded in accordance with the process of claim 22.

31. A process of storing and retrieving data, comprising the steps of:

(a) printing on a label a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, each hexagon having one of at least two different optical properties;

(b) illuminating said label;

(c) optically sensing light reflected from said hexagons with an electro-optical sensor;

(d) generating analog electrical signals corresponding to the intensities of light reflected from said optical properties as sensed by individual pixels of said sensor;

(e) converting said analog electrical signals into sequenced digital signals;

(f) storing said digital signals in a storage medium connected to a computer to form a replica of said digital signals in said storage medium;

(g) decoding said replica of said digital signals to retrieve the characteristics of the intensities, locations and orientations of the individual optical properties of said hexagons; and

(h) generating a digital bit stream output from the computer representing the decoded information represented by the hexagons.

32. A process as recited in claim 31, wherein said optical properties are the colors black and white.

33. A process as recited in claim 31, wherein said optical properties are the colors black, white and gray.

34. A process as recited in claim 31, further comprising the step of normalizing the stored digital signals to predetermined digital signal levels corresponding to said optical properties.

37. A process of storing and retrieving data, comprising the steps of:

(a) printing on a label a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, and a plurality of centrally-located Concentric Rings, each hexagon having one of at least two different optical properties and said Concentric Rings having alternating optical properties corresponding to at least two of the optical properties of said hexagons;

(b) illuminating said label;

(c) optically sensing light reflected from said hexagons and said Concentric Rings with an electro-optical sensor;

(d) generating analog electrical signals corresponding to the intensities of light reflected from said hexagons and said Concentric Rings as sensed by individual pixels of said sensor;

(e) filtering said analog electrical signals through an analog bandpass filter to determine the presence of said Concentric Rings, thereby detecting the presence of said hexagons within the field of view of said sensor;

(f) converting said analog electrical signals into a sequenced digital bit stream;

(g) storing said digital signals in a storage medium to form a replica of said digital signals in said storage medium;

(h) decoding said replica of said digital signals to retrieve the characteristics of the intensities, locations and orientations of the individual optical properties of said hexagons; and

(i) generating a digital bit stream output from said computer representing the decoded hexagons.

38. A process as recited in claim 37, wherein the optical properties of said hexagons and said Concentric Rings are the colors black and white.

39. A process as recited in claim 37, wherein the optical properties of said hexagons are the colors black, white and gray and the optical properties of said Concentric Rings are the same as two of the optical properties of said hexagons.

40. A process as recited in claim 37, further comprising the step of normalizing said stored data to predetermined digital signals corresponding to said optical properties of said hexagons.

43. A process of storing and retrieving data, comprising the steps of:

(a) printing on a substrate a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, and a plurality of centrally-located Concentric Rings, each hexagon having one of at least two different optical properties, and said Concentric Rings having alternating optical properties corresponding to at least two of the optical properties of said hexagons;

(b) illuminating said substrate;

(c) optically sensing light reflected from said hexagons and said Concentric Rings with an electro-optical sensor;

(d) transmitting digital electrical signals corresponding to the intensity of light reflected from said hexagons and said Concentric Rings as recorded by individual pixels of said sensor;

(e) filtering said digital electrical signals through a digital bandpass filter to determine the presence of said Concentric Rings, thereby detecting the presence of said hexagons within the field of view of said sensor;

(f) storing said digital electrical signals in a storage medium connected to a computer to form a replica of said digital electrical signals in said storage mediu;

;

(g) decoding said replica of said digital electrical signals to retrieve the characteristics of the intensities, locations and orientations of the individual optical properties of said hexagons; and

(h) transmitting a digital bit stream output from said computer representing the decoded hexagons.

44. A process as recited in claim 43, wherein said digital bandpass filter is a two-dimensional digital bandpass filter.

45. A process for decoding a stream of digital signals representing an electro-optically sensed image corresponding to a multiplicity of contiguously-arranged polygons encoded in a predetermined pattern, each polygon having one of at least two optical properties, comprising the steps of:

(a) performing a two-dimensional clock recovery on said image to determine the coordinates and intensities of said optical properties;

(b) searching said intensities of the optical properties of step (a) to identify the optical properties of said contiguously-arranged polygons; and

(c) decoding said polygons by performing the inverse of the encoding process for said polygons.

46. A process as recited in claim 45, wherein said contiguously arranged polygons are hexagons arranged in a honeycomb pattern.

47. A process as recited in claim 45, wherein step (b) comprises:

(i) an initialization step which searches the two-dimensional clock recovered coordinates and intensities of said optical properties determined in step (a) within a predetermined area of said multiplicity of polygons to identify the position of greatest intensity; and

(ii) performing a search continuation loop step which searches the two-dimensional clock recovered coordinates and intensities of said optical properties over the entire image starting from the position of greatest intensity in step (i) and looping to each adjacent position of next greatest intensity, wherein each identified position corresponds to the center of a polygon.

48. A process as recited in claim 46, wherein step (b) comprises:

(i) performing an initialization step which searches the two-dimensional clock recovered coordinates and intensities of the optical properties determined in step (a) within a predetermined area of said image, to identify the position of greatest intensity; and

(ii) performing a search continuation loop step which searches the two-dimensional clock recovered coordinates and intensities of said optical properties over the entire image starting from the position of greatest intensity in step (i) and looping to each adjacent position of next greatest intensity, wherein each identified position corresponds to the center of a hexagon.

49. A process as recited in claim 45, wherein step (a) comprises the steps of:

(i) performing a non-linear mapping operation on said digital signals to identify transitions between adjacent polygons having different optical properties;

(ii) performing a Fourier transformation on the non-linear mapped digital signals to obtain two-dimensional, non-linear coordinates corresponding to the direction, spacing and intensity of optical property transitions of said polygons;

(iii) filtering said two-dimensional non-linear coordinates to eliminate incorrect direction and spacing of optical property transitions of said polygons; and

(iv) performing an inverse Fourier transformation on said filtered two-dimensional non-linear coordinates to restore digital signals corresponding to a replicated image of said polygons recorded by said electro-optical sensor.

50. A process as recited in claim 49, wherein said polygons are hexagons contiguously-arranged in a honeycomb pattern.

51. A process as recited in claim 49, wherein step (i) comprises creating a two-dimensional map of the transitions between adjacent polygons having different optical properties by computing the standard deviation of the optical properties of said image recorded by each pixel and pixels proximate each pixel of said electro-optical sensor, wherein larger standard deviation values correspond to transition areas at the interfaces of said polygons.

52. A process as recited in claim 47, further comprising the step of thresholding said transformed digital signals corresponding to the center of each polygon located in step (ii) to determine the respective optical properties of said polygons.

53. A process as recited in claim 52, wherein the step of determining the thresholds of said transformed digital signals is performed by constructing histograms representing the respective optical properties of said polygons.

54. A process as recited in claim 45, further comprising the step, prior to step (a), of normalizing the sensed image to predetermined levels for each respective optical property of the image.

55. A process as recited in claim 45, further comprising the step, prior to step (a), of rescaling said image to create an image with equal horizontal and vertical magnification.

56. A process as recited in claim 50, further comprising the step of determining the major axis of said hexagons by first determining all of the axes of said hexagons and then determining which of these axes has a predetermined relationship to a boundary of the image.

57. A process as recited in claim 49, further comprising the step, before performing the Fourier transformation step, of windowing the non-linear mapped digital signals to reduce the intensities of optical properties sensed by said electro-optical sensor which are not associated with said polygons.

58. A process as recited in claim 49, wherein said image sensed by said electro-optical sensor includes an acquisition target comprising a plurality of Concentric Rings of different, alternating optical properties and wherein the first step of the process is locating said acquisition target by filtering said digital signals and correlating said digital signals to a signal of predetermined frequency.

59. A combination optical mark sensing and decoding system, comprising:

(a) an optically readable label for storing encoded data comprising a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, each hexagon having one of at least two different optical properties;

(b) means for illuminating a predetermined area;

(c) means for optically imaging said predetermined illuminated area through which said label is arranged to pass and generating analog electrical signals corresponding to the intensities of light reflected from said hexagons and striking each pixel of said imaging means;

(d) means for converting said analog electrical signals into a sequenced digital bit stream corresponding to the intensities of light recorded by said pixels of said imaging means;

(e) means for storing said digital bit stream for subsequent decoding of said label; and

(f) means for decoding said digital bit stream, said decoding means producing an electrical output representative of the encoded information.

60. An apparatus as recited in claim 59, wherein said optically readable label further comprises a plurality of Concentric Rings, said Concentric Rings having alternating optical properties corresponding to at least two of the optical properties of said hexagons.

61. An apparatus as recited in claim 60, wherein said Concentric Rings are centrally located on said label.

62. An apparatus as recited in claim 61, wherein each hexagon is black, white or gray and said Concentric Rings are alternating black and white.

63. An apparatus as recited in claim 60, further comprising means for filtering said analog electrical signals to determine the presence of said Concentric Rings, thereby detecting the presence of said label within said predetermined illuminated area.

64. An apparatus as recited in claims 59 or 60, wherein said optical imaging means comprises a charged coupled device.

65. An optical mark sensing and decoding system for an optically readable label for storing encoded data comprising a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern, each hexagon having one of at least two different optical properties, comprising:

(a) means for illuminating a predetermined area;

(b) means for optically imaging said pedetermined illuminated area through which said label is arranged to pass and generating analog electrical signals corresponding to the intensities of light reflected from said hexagons and striking each pixel of said imaging means;

(c) means for converting said analog electrical signals into a sequenced digital bit stream corresponding to the intensities of light recorded by said pixels of said imaging means;

(d) means for storing said digital bit stream for subsequent decoding of said label; and

(e) means for decoding said digital bit stream, said decoding means producing an electrical output representative of the encoded information.

66. An optical mark sensing and decoding system for an optically readable label for storing encoded data comprising a multiplicity of information-encoded hexagons contiguously arranged in a honeycomb pattern and a plurality of centrallylocated Concentric Rings, each hexagon having one of at least two different optical properties and said Concentric Rings having alternating optical properties corresponding to at least two of the optical properties of said hexagons;

comprising;

(a) means for illuminating a predetermined area;

(b) means for optically imaging said predetermined illuminated area through which said label is arranged to pass and generating analog electrical signals corresponding to the intensities of light reflected from said hexagons and striking each pixel of said imaging means;

(c) means for converting said analog electrical signals into a sequenced digital bit stream corresponding to the intensities of light recorded by said pixels of said imaging means;

(d) means for storing said digital bit stream for subsequent decoding of said label; and

(e) means for decoding said digital bit stream, said decoding means producing an electrical output representative of the encoded information.

67. An apparatus as recited in claim 66, further comprising means for filtering said analog electrical signals to determine the presence of said Concentric Rings, thereby detecting the presence of said label within said predetermined illuminated area.

68. An apparatus for decoding a stream of digital signals representing an electro-optically sensed image corresponding to a multiplicity of contiguously-arranged polygons encoded in a predetermined pattern, each polygon having one of at least two optical properties, comprising:

(a) means for performing a two-dimensional clock recovery on said image to determine the coordinates and intensities of said optical properties;

(b) means for searching said intensities of the optical properties of step (a) to identify the optical properties of said polygons; and

(c) means for decoding said polygons by performing the inverse of the encoding process for said polygons.

69. An apparatus for decoding a stream of digital signals representing an electro-optically sensed image of a multiplicity of contiguously-arranged polygons encoded in a predetermined pattern and each polygon having one at least two optical properties, comprising:

(a) means for performing a non-linear mapping operation on said digital signals to identify transitions between adjacent polygons having different optical properties;

(b) means for performing a Fourier transformation on the non-linear mapped digital signals to obtain a twodimensional map corresponding to the direction, spacing and intensity of optical property transitions of said polygons;

(c) means for filtering said two-dimensional map to eliminate incorrect direction and spacing of optical property transitions of said polygons;

(d) means for performing an inverse Fourier transformation on said filtered two-dimensional map to restore digital signals corresponding to a replicated image of said polygons;

(e) means for searching the transformed digital signals to determine the optical property of the center of each polygon and its location within said multiplicity of polygons; and

(f) means for decoding said polygons by performing the inverse of the encoding process for said polygons.

70. Apparatus as recited in claim 69, wherein means (e) comprises:

(i) initialization means to search said transformed digital signals within a predetermined area of said image to identify the position of greatest intensity; and

(ii) search continuation loop means to search said transformed digital signals over the entire image starting from the position of greatest intensity in means (i) and looping to each adjacent position of next greatest intensity, wherein each identified position corresponds to the center of a polygon.

71. Apparatus as recited in claims 69 or 70, wherein said polygons are hexagons contiguously-arranged in a honeycomb pattern.

72. Apparatus as recited in claim 69, wherein said non-linear mapping means comprises means for creating a two-dimensional map of the transitions between adjacent polygons having different optical properties by computing the standard deviation of the optical properties of said image recorded by each pixel and pixels proximate each pixel of said electrooptical sensor, wherein larger standard deviation values correspond to transition areas at the interfaces of said polygons.

73. Apparatus as recited in claim 69, further comprising means for thresholding said transformed digital signals corresponding to the center of each polygon located by means (e) to determine the respective optical properties of said polygons.

74. Apparatus as recited in claim 73, wherein the thresholding means comprising means for constructing histograms representing the respective optical properties of said polygons.

75. Apparatus as recited in claim 69, further comprising means for normalizing the sensed image to predetermined optimums for each respective optical property of the image prior to performing said non-linear mapping operation.

76. Apparatus as recited in claim 75, further comprising means for rescaling the normalized image, to create an image with equal horizontal and vertical magnification prior to performing said non-linear mapping operation.

77. Apparatus as recited in claim 71, further comprising means for determining the major axis of said hexagons by first determining all of the axes of said hexagons and then determining which of these axes has a predetermined relationship to a boundary of the image.

78. Apparatus as recited in claim 69, further comprising means for windowing the non-linear mapped digital signals to reduce the intensities of optical properties sensed by said electro-optical sensor which are not associated with said polygons before performing said Fourier transformation on the non-linear mapped digital signals.

79. Apparatus as recited in claim 69, wherein said image sensed by said electro-optical sensor includes an acquisition target comprising a plurality of Concentric Rings of different, alternating optical properties and means for locating said acquisition target by filtering said digital signals and correlating said digital signals to a signal of predetermined frequency.