Method and device for decoding a position-coding pattern

• US 7,999,798 B2
• Filed: 09/14/2006
• Issued: 08/16/2011
• Est. Priority Date: 10/29/2001
• Status: Active Grant

• Current Assignee: Anoto Group AB
• Original Assignee: Anoto Group AB
• Inventors: Pettersson, Mats-Petter, Björklund, Andreas
• Primary Examiner(s): Eisen; Alexander
• Assistant Examiner(s): Marinelli; Patrick
• Application Number:
  US11/532,038
• Publication Number:
  US 20070064818A1
• Time in Patent Office: 1,797 Days
• Field of Search: 345/17.9, 345156-183, 178 1801- 2004, 382313-315, 235/494, 341/5
• US Class Current: 345/179
• 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/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06V 10/17 using hand-held instruments
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions

Abstract

In a method for position decoding, a position is calculated on the basis of information determined from a partial area, imaged by a sensor, of a position-coding pattern. If the position calculation fails, the information from the partial area recorded by the sensor is matched with information about how the position-coding pattern is designed in a plurality of matching partial areas, which each define a position in the position-coding pattern. The position of the positions defined by the matching partial areas, which according to the matching step is the most probable position in the position-coding pattern for the imaged partial area is accepted as the decoded position. A device and a computer program for carrying out the method are also described.

Claims

1. A method of coding positions in two dimensions on a surface, comprising:

coding positions along an x-axis using a first difference number sequence having the property that each partial sequence of a predetermined length has an unambiguously determined place within the first difference number sequence, each position along the x-axis being coded by one of said partial sequences,

coding positions a long a y-axis using a second difference number sequence having the property that each partial sequence of a predetermined length has an unambiguously determined place within the second difference number sequence, each position along the y-axis being coded by one of said partial sequences,

coding the numbers of the first difference number sequence by differences in circular shifts between instances of a first main number sequence running orthogonally to the first difference number sequence; and

coding the numbers of the second difference number sequence by differences in circular shifts between instances of a second main number sequence running orthogonally to the second difference sequence.

2. The method as claimed in claim 1, wherein the first and second difference number sequences are identical.

3. The method as claimed in claim 1, wherein the first and second main number sequences are identical.

4. The method as claimed in claim 1, wherein a base of at least one of the first and second difference number sequences is greater than two.

5. The method as claimed in claim 1, wherein at least some of the differences in circular shifts between adjacent instances of one of the main number sequences are greater than one.

6. The method as claimed in claim 1, wherein the first and second main number sequences are binary.

7. The method as claimed in claim 1, wherein the position code is graphically coded on the surface using a plurality of substantially similar marks.

8. The method as claimed in claim 7, wherein each mark is a dot.

9. The method as claimed in claim 7, wherein each mark codes one bit from the first main number sequence and one bit from the second main number sequence.

10. The method as claimed in claim 7, wherein each one of said plurality of substantially similar marks is displaced from a nominal position defined by a regular grid.

11. The method as claimed in claim 7, wherein each one of said plurality of substantially similar marks codes one bit from the first main number sequence and one bit from the second main number sequence and is displaced in one of four predetermined directions from a nominal position defined by a regular grid.

12. The method as claimed in claim 1, wherein each position along the x-axis is defined by five difference numbers.

13. The method as claimed in claim 1, wherein each one of the first and the second main number sequences has the property that each partial sequence of a first predetermined length has an unambiguously determined place within the first main number sequence and the second main number sequence, respectively.

14. The method as claimed in claim 13, wherein the predetermined length of the partial sequence of the first and second main number sequences is six numbers.

15. The method as claimed in 13, wherein at least one of the first and the second main number sequences has the property that each partial sequence of a second predetermined length has an unambiguously determined place within the main number sequence, but does not occur backwards in the main number sequence.

16. The method as claimed in 13, wherein at least one of the first and the second main number sequences has the property that each partial sequence of a second predetermined length has an unambiguous place within the main number sequence, but does not occur inverted in the main number sequence.

17. The method as claimed in 13, wherein at least one of the first and the second main number sequences has the property that each partial sequence of a second predetermined length has an unambiguously determined place within the main number sequence, but does not occur with one bit inverted in the main number sequence.

18. A method for decoding a subset of a position code, which subset codes an x-coordinate and a y-coordinate for at least one point on a surface, comprising:

receiving a digital representation of the subset of the position code,

identifying, based on said digital representation, first partial sequences of instances of a first main number sequence which run perpendicularly to an x-axis of the position code and second partial sequences of instances of a second main number sequence which run perpendicularly to a y-axis of the position code,

determining, based on the first partial sequences, first differences in circular shifts between instances of the first main number sequence, said first differences constituting a partial sequence of a first difference number sequence, which defines the x-axis and has the property that any partial sequence of predetermined length in the first difference number sequence has an unambiguously determined place within the first difference number sequence and codes an x-coordinate;

determining the x-coordinate for said at least one point using the partial sequence of the first difference number sequence;

determining, based on the second partial sequences, second differences in circular shifts between instances of the second main number sequence, said second differences constituting a partial sequence of a second difference number sequence, which defines the y-axis and has the property that any partial sequence of predetermined length in the second difference number sequence has an unambiguously determined place within the second difference number sequence and codes a y-coordinate; and

determining the y-coordinate for said at least one point using the partial sequence of the second difference number sequence.

19. A method as claimed in claim 18, wherein the first and second difference number sequences are identical.

20. A method as claimed in claim 18, wherein the first and second main number sequences are identical.

21. A method as claimed in claim 18, wherein a base of at least one of the first and second difference number sequences is greater than two.

22. A method as claimed in claim 18, wherein at least some of the differences in circular shifts between adjacent instances of the main number sequences are greater than one.

23. A method as claimed in claim 18, wherein each one of the first and second main number sequence has the property that any partial sequence of predetermined length in the cyclic main number sequence is unique within the main number sequence.

24. A method as claimed in claim 18, further comprising determining a rotation of the subset of the position code for which the determination of the x-coordinate and the y-coordinate is to be carried out.

25. A method as claimed in claim 18, wherein the rotation is determined using the fact that each one of the first and second main number sequences has the property that any partial sequence of a predetermined length of the cyclic main number sequence has an unambiguous place within the main number sequence, but does not occur backwards and inverted in the main number sequence.

26. A method as claimed in claim 18, further comprising using table look-ups for determining the x-coordinate and the y-coordinate.

27. A method as claimed in claim 18, wherein determining the x-coordinate comprises converting the partial sequence of the first difference number sequence to a plurality of partial sequences of a set of secondary difference number sequences having smaller bases than the base of the first difference number sequence.

28. A method as claimed in claim 18, further comprising determining at least one additional coordinate by determining the circular shift of a first instance of the main number sequence running perpendicularly to the x-axis or the y-axis in the position code.

41. A computer-readable media having stored thereon program code, which when executed by a processor, causes the processor to carry out a method as claimed in claim 18.

29. A device for decoding a subset of a position'"'"'code, which subset codes an x-coordinate and a y-coordinate for at least one point on a surface, comprising a processor configured to identify, based on a digital representation of the position code, first partial sequences of instances of a first cyclic main number sequence which run perpendicular to an x-axis of the position code and second partial sequences of instances of a second cyclic main number sequence which run perpendicularly to a y-axis of the position code;

to determine, based on the first partial sequences, first differences in circular shifts between instances of the first cyclic main number sequence, said first differences constituting a partial sequence of a first difference number sequence, which defines the x-axis and has the property that any partial sequence of predetermined length in the first difference number sequence has an unambiguously determined place in the first difference number sequence and codes an x-coordinate;

to determine the x-coordinate for said at least one point using the partial sequence of the first difference number sequence;

to determine, based on the second partial sequences, second differences in circular shifts between instances of the second cyclic main number sequence, said second differences constituting a partial sequence of a second difference number sequence, which defines the y-axis and has the property that any partial sequence of predetermined length in the second difference number sequence has an unambiguously determined place in the second difference number sequence and codes a y-coordinate, and to determine the y-coordinate for said at least one point using the partial sequence of the second difference number sequence.

30. A device as claimed in claim 29, further comprising a sensor for providing the digital representation of the subset of the position code to be decoded.

31. A device as claimed in claim 29, wherein the first and second difference number sequences are identical.

32. A device as claimed in claim 29, wherein the first and second main number sequences are identical.

33. A device as claimed in claim 29, wherein a base of at least one of the first and second difference number sequences is greater than two.

34. A device as claimed in claim 29, wherein at least some of the differences between adjacent instances of the main number sequences are greater than one.

35. A device as claimed in claim 29, wherein each one of the first and second main number sequence has the property that any partial sequence of predetermined length in the cyclic main number sequence has an unambiguously determined place in the main number sequence.

36. A device as claimed in claim 35, further comprising a memory storing a table that converts partial sequences of the first and second main number sequences into places in the main number sequences.

37. A device as claimed in claim 29, wherein the processor is further configured to convert the partial sequence of the first difference number sequence to a plurality of partial sequences of a set of secondary difference number sequences having smaller bases than the base of the first difference number sequence.

38. A device as claimed in claim 29, wherein the processor is further configured to determine a rotation of the subset of the position code for which the determination of the x-coordinate and the y-coordinate is to be carried out.

39. A device as claimed in claim 38, wherein the processor is configured to determine the rotation using the fact that each one of the first and second main number sequences has the property that any partial sequence of a predetermined length of the cyclic main number sequence has an unambiguously determined place in the cyclic main number sequence, but does not occur backwards and inverted in the cyclic main number sequence.

40. A device as claimed in claim 29, wherein the processor is further configured to determine at least one additional coordinate by determining the circular shift of the first instance of the cyclic main number sequence running perpendicularly to the x-axis or the y-axis in the position code.

42. A product having a surface, the product being provided with a position code that codes positions on the surface in two dimensions, the positions along an x-axis being coded by a first difference number sequence having the property that each partial sequence of a predetermined length has an unambiguously determined place within the first difference number sequence, each position along the x-axis being coded by one of said partial sequences, the positions along a y-axis being coded by a second difference number sequence having the property that each partial sequence of a predetermined length has an unambiguously determined place within the second difference number sequence, each position along the y-axis being coded by one of said partial sequences, the numbers of the first difference number sequence being coded by differences in circular shifts between instances of a first main number sequence running orthogonally to the first difference number sequence;

and the numbers of the second difference number sequence being coded by differences in circular shifts between instances of a second main number sequence running orthogonally to the second difference sequence.