Methods, apparatus, computer program and storage medium for position decoding

• US 7,672,513 B2
• Filed: 04/29/2004
• Issued: 03/02/2010
• Est. Priority Date: 04/29/2003
• Status: Expired due to Fees

• Current Assignee: Anoto Group AB
• Original Assignee: Anoto Group AB
• Inventors: Bjorklund, Andreas, Edso, Tomas
• Primary Examiner(s): Chawan; Sheela C
• Application Number:
  US10/554,231
• Publication Number:
  US 20060239505A1
• Time in Patent Office: 2,133 Days
• Field of Search: 382/188, 382/179, 382/181, 382/305, 382/173, 358/473, 358/406, 358/401, 358/402, 345/156, 345/157, 345/103, 345/104, 345/164, 345/165, 345/167, 345/173, 345/179, 345/162, 178/18.01, 178/18.09, 235/494
• US Class Current: 382/188
• 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: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A method, in an apparatus for position decoding, operates to extract a sequence of positions from a sequence of images of a position-coding pattern, as recorded by a sensor. The method, which may be embodied as a computer program on a computer-readable storage medium, involves the steps of retrieving at least one reference position (P1, P1′); and extracting the sequence of positions solely by matching information obtained from each of the images with a corresponding pattern reference area (MA), which represents a known subset of the position-coding pattern with a given, direct or indirect, spatial relation to the reference position(s).

Claims

1. A processor-implemented method for position decoding, in which a sequence of positions is extracted from a sequence of images, recorded by a sensor, of a position-coding pattern, said method comprising steps performed by a processor of:

retrieving at least one reference position, the at least one reference position corresponding to a preceding position extracted from a prior image of the position-coding pattern; and

extracting said sequence of positions by matching information obtained from each of said images with a corresponding pattern reference area, which represents a known subset of the position-coding pattern with a given spatial relation to said reference position.

2. A method as in claim 1, wherein each position in said sequence of positions is extracted by:

determining a relative location, within said pattern reference area, of a match between said information and said pattern reference area; and

adjusting said spatial relation by said relative location to thereby derive said position.

3. A method as in claim 1, wherein the method further comprises generating said pattern reference area for each image.

4. A method as in claim 1, wherein said spatial relation is given by a predicted position, the method comprising the step of estimating said predicted position based on said at least one reference position.

5. A method as in claim 4, wherein said pattern reference area is generated with a given positional relationship to said predicted position.

6. A method as in claim 5, wherein said predicted position is included in the known subset of the position-coding pattern.

7. A method as in claim 4, wherein said step of estimating is effected for each image, to generate a sequence of predicted positions.

8. A method as in claim 7, wherein said sequence of predicted positions are converted, by said step of extracting by matching, to said sequence of positions.

9. A method as in claim 4, wherein the predicted position is estimated based on at least two reference positions, the at least two reference positions corresponding to at least two preceding positions extracted from said sequence of images of the position-coding pattern.

10. A method as in claim 9, in which said predicted position is estimated by polynomial extrapolation of said at least two preceding positions.

11. A method as in claim 4, said sequence of images being recorded by way of an electronic handwriting tool, wherein said predicted position is estimated based on said at least one reference position and at least one of the following:

a predefined direction of movement, a detected direction of movement, speed of said handwriting tool, and acceleration of said handwriting tool.

12. A method as in claim 1, in which the at least one reference position is retrieved by calculating a position based on an image of said position-coding pattern in another way than said step of extracting by matching.

13. A method as in claim 12, wherein said step of calculating a position includes at least one of:

extracting symbol data from an isolated image preceding said sequence of images;

deriving position data by effecting one or more lookup operations, using said symbol data, in one or more data structures that contain fundamental coding data of the position-coding pattern; and

inputting said symbol or position data to a mathematical formula for explicit calculation of an absolute position.

14. A method as in claim 1, further comprising the step of merging said at least one reference position with said sequence of positions.

15. A method as in claim 1, wherein said step of retrieving is effected intermittently to update said at least one reference position.

16. A method as in claim 1, wherein, for an individual image among said sequence of images, the corresponding pattern reference area includes a plurality of partial areas defining a plurality of respective candidates to a position that is represented by the position-coding pattern in said individual image.

17. A method as in claim 16, wherein said step of extracting by matching includes comparing the information obtained from said individual image with each of said plurality of partial areas included in the corresponding pattern reference area.

18. A method as in claim 17, wherein said step of extracting by matching includes selecting, for an individual image among said sequence of images, one of said plurality of respective candidates for which the comparing step indicates correspondence between the information obtained from said individual image and one of said plurality of partial areas.

19. A method as in claim 1, wherein the position-coding pattern comprises a plurality of marks and wherein each mark codes one of at least two different values in at least one dimension.

20. A method as in claim 19, in which said step of extracting by matching includes obtaining said information from an individual image among said sequence of images by generating a probability matrix, said probability matrix representing a subarea of the position-coding pattern which is included in said individual image and containing one matrix element for each mark in said subarea, wherein each matrix element is adapted to store either a value which represents a most probable estimated value of its mark, or a value which represents that no value has been estimated for its mark.

21. A method as in claim 20, wherein said value which represents a most probable estimated value is an integer value.

22. A method as in claim 20, wherein each mark codes a binary value in a first dimension and a binary value in a second dimension, and wherein a first probability matrix is generated for the values of the marks in said first dimension and a second probability matrix is generated for the values of the marks in said second dimension.

23. A method as in claim 20, wherein the corresponding pattern reference area includes a plurality of partial areas defining a plurality of respective candidates to a position that is represented by the position-coding pattern in said individual image, wherein said step of extracting by matching includes comparing the probability matrix with each of said plurality of partial areas included in the corresponding pattern reference area.

24. A method as in claim 20, wherein the plurality of marks in the at least one dimension of the position-coding pattern being based on shifts of a cyclic main number sequence, wherein any subsequence, of a first predetermined length or longer, of said cyclic main number sequence has an unambiguously determined position in said cyclic main number sequence, and based on a sequence of difference numbers representing differences in shifts between pairs of said main number sequence in the position-coding pattern, wherein any subsequence, of a second predetermined length or longer, of said sequence of difference numbers has an unambiguously determined position in said sequence of difference numbers, said step of extracting by matching including:

obtaining a first set of difference numbers for said pattern reference area;

obtaining a second set of difference numbers from the probability matrix;

matching said second set of difference numbers with said first set of difference numbers; and

extracting a position of said position-coding pattern, in said dimension, upon determination of a match in said matching step.

25. A method as in claim 24, wherein said step of obtaining a second set of difference numbers includes:

matching respective rows or columns of the probability matrix with said main number sequence so as to estimate main number sequence positions for said rows or columns; and

deriving the second set of difference numbers by subtracting the estimated main number sequence positions for pairs of rows or columns of the probability matrix.

26. A method as in claim 1, wherein said sequence of positions represents at least a part of a handwriting stroke performed by way of an electronic handwriting tool.

27. A computer-readable storage medium on which is stored a computer program which, when executed in a computer, causes the computer to carry out a method according to claim 1.

28. A method as in claim 1, wherein said extracting said sequence of positions is performed solely by matching the information obtained from each of said images with the corresponding pattern reference area.

29. A processor-implemented method for position decoding by determining a position on the basis of information obtained from a partial area, recorded by a sensor, of a position-coding pattern, the position-coding pattern comprising a plurality of marks, each mark coding one of at least two different values in at least one dimension, said method comprising steps performed by a processor of:

generating a probability matrix, said probability matrix containing one matrix element for each mark in said partial area, each matrix element being adapted to store either a value which represents a most probable estimated value of its mark, or a value which represents that no value has been estimated for its mark;

matching said probability matrix with information about how the position-coding pattern is composed in a pattern reference area of said position-coding pattern, said pattern reference area being larger than said partial area and including said partial area, and said pattern reference area defining a plurality of positions; and

selecting, as the position to be determined, one of the positions defined by said pattern reference area for which the matching step indicates correspondence between said probability matrix and said one of the positions defined by the pattern reference area.

30. A method as in claim 29, wherein said value of a matrix element of said probability matrix which represents a most probable estimated value is an integer value.

31. A method as in claim 29, wherein each mark codes a binary value in a first dimension and a binary value in a second dimension, and said probability matrix is formed by a first probability matrix for the values of the marks in said first dimension and a second probability matrix for the values of the marks in said second dimension.

32. A computer-readable storage medium on which is stored a computer program which, when executed in a computer, causes the computer to carry out a method according to claim 29.

33. An apparatus for position decoding, comprising a signal-processing unit which is adapted to extract a sequence of positions from a sequence of images, recorded by a sensor, of a position-coding pattern, wherein the signal-processing unit is further adapted to:

retrieve at least one reference position, the at least one reference position corresponding to a preceding position extracted from a prior image of the position-coding pattern; and

extract said sequence of positions by matching information obtained from each of said images with a corresponding pattern reference area, which represents a known subset of the position-coding pattern with a given spatial relation to said reference position.

34. An apparatus as in claim 33, wherein the signal-processing unit is further adapted to extract said sequence of positions solely by matching the information obtained from each of said images with the corresponding pattern reference area.

35. An apparatus for position decoding, comprising a signal-processing unit which is adapted to determine a position on the basis of information obtained from a partial area, as recorded by a sensor, of a position-coding pattern, the position-coding pattern comprising a plurality of marks, each mark coding one of at least two different values in at least one dimension, wherein the signal-processing unit is further adapted to:

generate a probability matrix, said probability matrix containing one matrix element for each mark in said partial area, each matrix element being adapted to store either a value which represents a most probable estimated value of its mark, or a value which represents that no value has been estimated for its mark;

match said probability matrix with information about how the position-coding pattern is composed in a pattern reference area of said position-coding pattern, said pattern reference area being larger than said partial area and including said partial area; and

select, as the position to be determined, the one of the positions defined by said pattern reference area for which the matching step indicates correspondence between said probability matrix and said pattern reference area.