Tilings of mono-code and dual-code embedded data pattern strips for robust asynchronous capture

• US 6,000,621 A
• Filed: 12/21/1995
• Issued: 12/14/1999
• Est. Priority Date: 12/21/1995
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Petrie, Glen W., Hecht, David L.
• Primary Examiner(s): Hajec, Donald
• Assistant Examiner(s): TREMBLAY, MARK STEPHEN
• Application Number:
  US08/576,630
• Time in Patent Office: 1,454 Days
• Field of Search: 382/243, 235/494, 235/487, 235/456, 235/454, 235/462, 235/462.01, 235/462.1
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/143 Glyph-codes

Abstract

To facilitate the recovery data from an embedded data pattern through the use of a appropriately sized capture window that is randomly positioned within the data pattern, the embedded data pattern is composed of a plurality of identical, one dimensionally or two dimensionally regularly tiled embedded data blocks which contain sufficient spatial addressing information to permit the logical reconstruction of a complete data block from any set of fragments that collectively provide a full cover for the surface area of any one tile. To this end, the capture window is sized to include a shape which is completely registered with the data pattern in which is capable of tiling the recording medium in accordance with the tiling vectors.

Claims

1. A process for encoding digital information into a plurality of essentially identical machine readable shear tiled embedded data blocks, said process comprising the steps of

encoding said digital information in accordance with a machine recognizable symbolic representation;

selecting at least one pair of shear tiling vectors;

laying out said shear tiled embedded data blocks in accordance with said shear tiling vectors; and

shear tiling said symbolic representation into said shear tiled embedded data blocks in accordance with said shear tiling vectors.

2. The process of of claim 1 wherein said tiled data blocks comprise a self-clocking glyph code.

3. The process of claim 2 wherein

said glyph code is composed of marks that are oriented at significantly different angles to encode different digital values.

4. The process of claim 3 wherein

said marks are oriented at +45°

and -45°

, respectively, with respect to a predetermined axis for encoding binary 1'"'"'s and 0'"'"'s, respectively.

5. A process for redundantly encoding digital framing codes in a machine readable embedded data pattern, said process comprising the steps of:

encoding said digital framing codes in accordance with a machine recognizable symbolic representation; and

selecting at least two pairs of shear tiling vectors to map a plurality of logically organized, interlaced, machine readable representations of said digital framing codes into said data patterns in accordance with a plurality of different layout geometries.

6. The process of claim 5 wherein

said tiled data pattern is a self-clocking glyph code.

7. The process of claim 6 wherein

said glyph code is composed of marks that are oriented at significantly different angles to encode different digital values.

8. The process of claim 7 wherein

said marks are oriented at +45φ

and -45φ

, respectively, with respect to a predetermined axis for encoding binary 1'"'"'s and 0'"'"'s, respectively.

9. A process for recording a machine readable encoding of logically ordered digital values on a recording medium for a spatially asynchronous readout of said encoding from said recording medium;

said encoding being composed of machine recognizable symbols which are selected to encode respective ones of said digital values and ordered to preserve the logical ordering of said values;

said process comprising the steps of;

writing multiple, essentially identical copies of said encoding and corresponding machine recognizable spatial synchronization indicia onto said recording medium to provide multiple spatially synchronizeable instances of said encoding; and

laying out said spatially synchronizeable instances of said encoding, during said writing, on a spatially periodic lattice of centers on said recording medium in accordance with a layout rule;

said layout rule spatially formatting the respective instances of said encoding uniformly while mapping said instances of said encoding into respective two dimensional, non-overlapping data blocks which are tiled on to said recording medium in at least one direction in accordance with a fixed length tiling vector to record a tiled data pattern on said recording medium;

whereby a read out of said tiled data pattern over an area spanning any number of recorded instances of said encoding with a profile covering a shape that is configured to tile said data blocks on to said recording medium in accordance with said tiling vector provides sufficient information for accurately interpreting said encoding.

10. The process of claim 9 wherein said spatial synchronization indicia are composed of machine recognizable sequences of symbols which are visually indistinguishable from the symbols that encode said digital values.

11. The process of claim 10 wherein said lattice of centers is rectangular, said data blocks are rectangular and are rectangularly oriented to align widthwise and lengthwise with rows and columns of said lattice of centers, and said data blocks are of deterministic symbol size widthwise and lengthwise.

12. The process of claim 11 wherein said symbols are angularly oriented slash-like marks, and said digital values and said spatial synchronization sequences are encoded in the angular orientations of said marks.

13. The process of claim 12 wherein said digital values and said spatial synchronization sequences are binary, and said slash-like marks are angularly oriented at approximately +45°

and -45°

with respect to the rows and columns of said centers to encode binary 1'"'"'s and 0'"'"'s.

14. The process of claim 12 wherein said data blocks are written on spatially contiguous sets of said centers.

15. The process of claim 14 wherein said digital values and said spatial synchronization sequences are binary, and said slash-like marks are angularly oriented at approximately +45°

and -45°

with respect to the rows and columns of said centers to encode binary 1'"'"'s and 0'"'"'s.

16. A process for recording a machine readable encoding of logically ordered digital values on a recording medium for a spatially asynchronous readout of said encoding from said recording medium;

said encoding being composed of machine recognizable symbols which are selected to encode respective ones of said digital values and ordered to preserve the logical order of said digital values;

said process comprising the steps of;

writing multiple, essentially identical copies of said encoding and corresponding machine recognizable spatial synchronization indiria onto said recording medium to provide multiple spatially synchronizeable instances of said encoding; and

performing said writing in accordance with a layout rule that is selected to write said instances of said encoding on a spatially periodic lattice of centers on said recording medium;

said instances of said encoding being uniformly spatially for-matted on said recording medium under said layout rule while being mapped, pursuant to said layout rule, into respective, two dimensional, non-overlapping data blocks;

said data blocks being tiled on to said recording medium, under said layout rule, in accordance with a pair of fixed length, angularly separated tiling vectors to record said instances of said encoding in a tiled data pattern;

whereby a readout of said tiled data pattern over an area that includes a region of said tiled data pattern that is appropriately shaped for tiling a plane in accordance with said tiling vectors provides sufficient information for accurately interpreting said encoding, regardless of where said area is located with respect to said data pattern.

17. The process of claim 16 wherein said spatial synchronization indicia are composed of machine recognizable sequences of symbols which are visually indistinguishable from the symbols that encode said digital values.

18. The process of claim 17 wherein said lattice of centers is rectangular, said data blocks are rectangular and are oriented to align widthwise and lengthwise with rows and columns of said lattice of centers, and said data blocks are of deterministic symbol size widthwise and lengthwise.

19. The process of claim 18 wherein said symbols are elongated slash-like marks which encode said digital values and said spatial synchronization sequences in their angular orientations.

20. The process of claim 19 wherein said digital values and said spatial synchronization sequences are binary, and said slash-like marks are angularly oriented at approximately +45°

and -45°

with respect to the rows and columns of said centers to encode binary 1'"'"'s and 0'"'"'s.

21. The process of claim 18 wherein said data blocks are written on spatially contiguous sets of said centers.

22. The process of claim 21 wherein said digital values and said spatial synchronization sequences are binary, and said slash-like marks are angularly oriented at approximately +45°

and -45°

with respect to the rows and columns of said centers to encode binary 1'"'"'s and 0'"'"'s.

23. An image capture mechanism for asynchronously reading out encoded data from a tiled embedded data pattern, said data pattern being composed of multiple, essentially identical copies of an embedded data block which are tiled onto a recording medium in at least one direction in accordance with a fixed length tiling vector, each said embedded data block comprising at least one spatial reference point residing at a predefined location;

said image capture mechanism comprising;

a capture window which is registered with a portion of said data pattern, said capture window being configured to include a shape which is registered fully with said data pattern and which is capable of tiling said data block onto said recording medium in accordance with said tiling vector, said capture window registered portion of said data pattern being referenced to said at least one spatial reference point.

24. An image capture mechanism for reading out a tiled embedded data pattern, said data pattern being composed of multiple, essentially identical copies of an embedded data block which are tiled onto a recording medium in accordance with a pair of angularly separated fixed length tiling vectors, each said embedded data block comprising at least one spatial reference point residing at a predefined location;

said image capture mechanism comprising;

a capture window which is asynchronously registered with a portion of said data pattern, said capture window being configured to include a shape that is capable of tiling said recording medium in accordance with said tiling vectors, said capture window registered portion of said data pattern being referenced to said at least one spatial reference point.

25. The image capture mechanism of claim 24 wherein one of said tiling vectors is oriented at an acute angle with respect to the other of said tiling vectors to shear tile said data block onto said recording medium.

26. The image capture mechanism of claim 25 wherein said shape conforms to an integer linear combination of said tiling vectors.

35. The process of claim 24 wherein said digital values and said synchronization sequences are binary, and said slash-like marks are oriented at approximately +45°

and -45°

with respect to an axis to encode binary 1'"'"'s and 0'"'"'s.

36. The process of claim 35 wherein said data blocks are written on spatially contiguous sets of said centers.

27. A process for logically ordering a spatially asynchronous read out of an encoding of logically ordered digital values which is written on a recording medium as a tiled data pattern that is composed of multiple spatially synchronizeable instances of said encoding;

said encoding being composed of machine recognizable symbols which are selected to encode respective ones of said digital values and ordered to preserve the logical ordering of said values;

said spatially synchronizeable instances of said encoding further including machine recognizable spatial synchronization indicia which are written into predetermined positions within each of said instances of said encoding;

said instances of said encoding being written on a spatially periodic lattice of centers on said recording medium and being mapped in to, and identically spatially formatted within, respective essentially identical, two dimensional, non-overlapping data blocks which are tiled on to said recording medium in at least one direction in accordance with a fixed length tiling vector;

said read out covering an area of said tiled data pattern over an included region that is appropriately shaped for tiling said data blocks on to said recording medium in accordance with said tiling vector;

said process comprising the steps of;

transforming the read out of said encoding into a correspondingly ordered, two dimensional representation of the digital values encoded by the symbols and of the spatial synchronization indicia contained by said read out;

performing a correlation test on said representation to identify a full cover for a spatially synchronizeable instance of said encoding, independently of the spatial formatting of the instance of said encoding that is contained by said cover;

locating the spatial synchronization indicia within said cover to establish a spatial reference for said cover; and

reading out the spatially referenced cover in an order that corresponds to the spatial formatting of said data blocks, thereby conforming the order of said read out to the logical order of the encoded values.

28. The process of claim 27 wherein

said spatial synchronization indicia are spatially ordered sets of symbols which encode a machine recognizable digital synchronization sequence and which are visually indistinguishable from the symbols that encode said digital values.

29. The process of claim 28 wherein

said data blocks are rectangular and are of deterministic symbol size independently of said correlation test;

and

said correlation test is performed along one dimension of said representation to identify said cover.

30. The process of claim 29 wherein said symbols are slash-like marks which encode said digital values and said synchronization sequences in their angular orientations.

31. The process of claim 30 wherein said digital values and said synchronization sequences are binary, and said slash-like marks are oriented at approximately +45°

and -45°

with respect to an axis to encode binary 1'"'"'s and 0'"'"'s.

32. The process of claim 31 wherein said data blocks are written on spatially contiguous sets of said centers.

33. The process of claim 28 wherein

said data blocks are rectangular;

and

said correlation test is performed along both dimensions of said representation to identify said cover.

34. The process of claim 33 wherein said symbols are slash-like marks which encode said digital values and said synchronization sequences in their angular orientations.

37. A process for logically ordering a spatially asynchronous read out of an encoding of logically ordered digital values which is written on a recording medium as a tiled data pattern that is composed of multiple spatially synchronizeable instances of said encoding;

said encoding being composed of machine recognizable symbols which are selected to encode respective ones of said digital values and ordered to preserve the logical ordering of said values;

said spatially synchronizeable instances of said encoding further including machine recognizable synchronization indicia which are written into predetermined positions within each of said instances of said encoding, said instances of said encoding being written on a spatially periodic lattice of centers on said recording medium and being mapped in to, and identically spatially formatted within, respective essentially identical, two dimensional, non-overlapping data blocks which are tiled on to said recording medium in accordance with a pair of fixed length, angularly separated tiling vectors;

said read out covering an area of said tiled data pattern over an included region that is appropriately shaped for tiling said recording medium in accordance with said tiling vectors;

said process comprising the steps of;

transforming the read out of said encoding into a correspondingly ordered, two dimensional representation of the digital values encoded by the symbols and of the synchronization indicia contained by said read out; and

performing a correlation test on said representation to identify a full cover for a spatially synchronizeable instance of said encoding, independently of the spatial formatting of the instance of said encoding that is contained by said cover.

38. The process of claim 37 wherein

said spatial synchronization indicia are spatially ordered sets of symbols which encode a machine recognizable digital synchronization sequence and which are visually indistinguishable from the symbols that encode said digital values.

39. The process of claim 38 wherein

said data blocks are rectangular and are of deterministic symbol size independently of said correlation test;

and

said correlation test is performed along one dimension of said representation to identify said cover.

40. The process of claim 39 wherein said symbols are slash-like marks which encode said digital values and said synchronization sequences in their angular orientations.

41. The process of claim 40 wherein said digital values and said synchronization sequences are binary, and said slash-like marks are oriented at approximately +45°

and -45°

with respect to an axis to encode binary 1'"'"'s and 0'"'"'s.

42. The process of claim 41 wherein said data blocks are written on spatially contiguous sets of said centers.

43. The process of claim 38 wherein

said data blocks are rectangular and are of deterministic symbol size;

and

said correlation test is performed along both dimensions of said representation to identity said cover.

44. The process of claim 43 wherein said symbols are slash-like marks which encode said digital values and said synchronization sequences in their angular orientations.

45. The process of claim 44 wherein said digital values and said synchronization sequences are binary, and said slash-like marks are oriented at approximately +45°

and -45°

with respect to an axis to encode binary 1'"'"'s and 0'"'"'s.

46. The process of claim 45 wherein said data blocks are written on spatially contiguous sets of said centers.