Coding pattern comprising translation symbols for aligning cells with tags

• US 8,118,234 B2
• Filed: 02/05/2008
• Issued: 02/21/2012
• Est. Priority Date: 02/08/2007
• Status: Expired due to Fees

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Lapstun, Paul, Silverbrook, Kia
• Primary Examiner(s): Le, Thien M.
• Assistant Examiner(s): JOHNSON, SONJI N
• Application Number:
  US12/025,751
• Publication Number:
  US 20080191040A1
• Time in Patent Office: 1,477 Days
• Field of Search: 235/487, 235/494, 235/375
• US Class Current: 235/494
• CPC Class Codes: G06F 2203/0337 Status LEDs integrated in the mouse to provide visual feedback to the user about the status of the input device, the PC, or the user
• CPC Class Codes: G06F 2203/0384 Wireless input, i.e. hardware and software details of wireless interface arrangements for pointing devices
• CPC Class Codes: G06F 3/0321 by optically sensing the absolute position with respect to a regularly patterned surface forming a passive digitiser, e.g. pen optically detecting position indicative tags printed on a paper sheet constructional details of pen-shaped pointing devices G06F3/03545, G06F3/03542, G06F3/037
• CPC Class Codes: G06F 3/03545 Pens or stylus
• CPC Class Codes: G06K 19/06 characterised by the kind of the digital marking, e.g. shape, nature, code
• CPC Class Codes: G06K 7/10722 Photodetector array or CCD scanning
• CPC Class Codes: G06T 7/32 using correlation-based methods

Abstract

A substrate having a coding pattern disposed on a surface thereof. The coding pattern comprises a plurality of target elements defining a target grid. The target grid comprises a plurality of cells, wherein neighboring cells share target elements. A plurality of data elements are contained in each cell. Tags are defined by a plurality of contiguous cells and each tag comprises respective local tag data encoded by a respective set of the data elements. Each cell comprises one or more translation symbols encoded by a respective set of the data elements. The translation symbols identify a translation of the cell relative to a tag containing the cell.

Claims

1. A substrate having a coding pattern disposed on a surface thereof, said coding pattern comprising:

a plurality of target elements defining a target grid, said target grid comprising a plurality of cells, each cell having one of said target elements positioned at each corner thereof, wherein neighboring cells share target elements;

a plurality of data elements contained in each cell; and

a plurality of tags, each tag being defined by a plurality of contiguous cells, each tag comprising respective tag data encoded by a respective set of said data elements, wherein each cell comprises one or more translation symbols encoded by a respective set of said data elements, said one or more translation symbols identifying a translation of said cell relative to a tag containing said cell.

2. The substrate of claim 1, wherein each cell comprises a pair of orthogonal translation symbols, each orthogonal translation symbol identifying a respective orthogonal translation of said cell relative to a tag containing said cell.

3. The substrate of claim 1, wherein each tag is square and comprises M² contiguous square cells, wherein M is an integer having a value of at least 2.

4. The substrate of claim 3, wherein M translation symbols in a row of M cells define a cyclic position code having minimum distance M, said code being defined by a first codeword.

5. The substrate of claim 3, wherein M translation symbols in a column of M cells define a cyclic position code having minimum distance M, said code being defined by a second codeword.

6. The substrate of claim 1, wherein each tag comprises N cells, and at least N translation symbols form a third codeword with minimum distance N, wherein N is an integer having a value of at least 4.

7. The substrate of claim 6, wherein any tag-sized portion of said coding pattern is guaranteed to contain at least N translation symbols, thereby capturing said third codeword.

8. The substrate of claim 1, wherein each cell comprises at least one orientation symbol encoded by at least one data element, such that any tag-sized portion of said coding pattern is guaranteed to contain a plurality of said orientation symbols, each orientation symbol identifying an orientation of said coding pattern with respect to said surface.

9. The substrate of claim 1, wherein said data elements are macrodots.

10. The substrate of claim 1, wherein a portion of data is represented by a macrodot occupying one of a plurality of possible positions within a cell, each position representing one of a plurality of possible data values.

11. The substrate of claim 10, wherein a n-bit portion of data is represented by a macrodot occupying one of 2ⁿ possible positions within a cell, each position representing one of 2ⁿ possible data values, wherein n is an integer.

12. The substrate of claim 1, wherein each cell defines a symbol group, each symbol group comprising a plurality of Reed-Solomon symbols encoded by a plurality of said data elements.

13. The substrate of claim 12, wherein each symbol comprises two halves, each half comprising 2 bits of data represented by a macrodot occupying one of 4 possible positions within said half.

14. The substrate of claim 12, wherein said tag data is encoded as a local codeword comprised of a set of said Reed-Solomon symbols.

15. The substrate of claim 14, wherein each tag comprises a plurality of replications of said local codeword, such that any tag-sized portion of said coding pattern is guaranteed to contain said local codeword irrespective of whether a whole tag is contained in said portion.

16. The substrate of claim 15, wherein each tag is square and comprises four replications of said local codeword, each replication being positioned within a respective quarter of said tag.

17. The substrate of claim 14, wherein each local codeword identifies a location of a respective tag.

18. The substrate of claim 12, wherein each tag comprises one or more common codewords, each common codeword being comprised of a set of said Reed-Solomon symbols, wherein said one or more common codewords are defined as codewords common to a plurality of contiguous tags.

19. The substrate of claim 18, wherein each symbol group comprises a fragment of at least one of said one or more common codewords, and contiguous symbol groups are arranged such that any tag-sized portion of said coding pattern is guaranteed to contain said one or more common codewords irrespective of whether a whole tag is contained in said portion.

20. The substrate of claim 18, wherein said one or more common codewords encode region identity data uniquely identifying a region of said surface.