Identification of virtual raster pattern

• US 7,050,653 B2
• Filed: 03/21/2001
• Issued: 05/23/2006
• Est. Priority Date: 04/05/2000
• Status: Expired due to Fees

• Current Assignee: Anoto Group AB
• Original Assignee: Anoto Group AB
• Inventors: Edsö, Tomas, Ericson, Petter
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US09/812,907
• Publication Number:
  US 20020044138A1
• Time in Patent Office: 1,889 Days
• Field of Search: 382/276, 382/181, 382/190, 382/197, 382/232, 382/280, 382/100, 382/287, 382/288, 382/286, 382/306, 382/252, 382/112, 382/168, 382/465, 382/203, 375/240.16, 359/29, 359/559, 324/76.21, 324/76.22, 324/307, 345/179, 235/462.15, 235/494, 235/470
• US Class Current: 382/280
• 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/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06V 10/17 using hand-held instruments
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions

Abstract

A method aims to identify a virtual raster pattern in an image of a surface that is provided with a plurality of position-coding marks. Each mark is associated with a respective intersection of raster lines belonging to the raster pattern. By means of the method, the virtual raster pattern is identified via Fourier analysis of the image. A computer program product and a device for position determination are also described.

Claims

1. A method for identifying a virtual raster pattern in an image of a plurality of marks, comprising:

distinguishing at least some of the plurality of marks in the image, wherein each mark is associated with a respective intersection of raster lines belonging to the raster pattern; and

identifying the virtual raster pattern based upon Fourier analysis of the image.

2. The method according to claim 1, comprising:

converting the image to a set of unit pulses before the Fourier analysis, which unit pulses are placed at the positions of the marks in the image.

3. The method according to claim 2, wherein each unit pulse is placed at a center of gravity of the corresponding mark.

4. The method according to claim 1, further comprising:

calculating a spatial frequency spectrum in two dimensions based upon said image;

identifying at least two main vectors in said image, based on said frequency spectrum; and

identifying the raster lines in the raster pattern based upon said main vectors.

5. The method according to claim 4, wherein the spatial frequency spectrum is calculated based on a two-dimensional Fourier transform along at least two directions in said image.

6. The method according to claim 4, wherein the spatial frequency spectrum is calculated on the basis of a central part of the image.

7. The method according to claim 4, wherein the identifying at least two main vectors further comprises:

localizing in the spatial frequency spectrum positions of peaks that exceed a given threshold value; and

selecting said at least two main vectors based upon said positions.

8. The method according to claim 4, wherein the calculating a spatial frequency spectrum and the identifying main vectors therein further comprises:

changing a direction of a direction vector in steps within an angle range;

calculating at least one absolute value of the two-dimensional Fourier transform for the image based upon each such direction vector; and

identifying absolute values that exceed said threshold value.

9. The method according to claim 8, wherein a length of the direction vector is changed within a frequency range that comprises a nominal spatial frequency of the raster pattern.

10. The method according to claim 9, wherein the length of the direction vector is changed in steps.

11. The method according to claim 8, wherein the calculating of the spatial frequency spectrum identifies peaks, the position of each of said peaks being localized by calculation of the center of gravity of the absolute values that exceed said threshold value and that areadjacent to each other in the spatial frequency spectrum.

12. The method according to claim 7, wherein the selecting at least two main vectors comprises:

letting each position identify a candidate vector;

letting at least one current image transform, which provides a given change in a relationship between two vectors, operate on said candidate vectors; and

selecting as main vectors the candidate vectors that provide a required mutual relationship for said at least one current image transform.

13. The method according to claim 12, wherein each current image transform corresponds to a given image relationship between a sensor which records said image and an object which is provided with said plurality of marks.

14. The method according to claim 12, comprising:

sequentially letting a series of different current image transforms operate on said candidate vectors, at least until a required mutual relationship is achieved between said candidate vectors.

15. The method according to claim 12, wherein the raster pattern is identified based upon the image transform that gave rise to the required relationship between the candidate vectors.

16. The method according to claim 12, wherein the current image transform is selected on the basis of an earlier image transform that gave rise to the required relationship for a previous image.

17. The method according to claim 4, wherein said main vectors are selected on the basis of earlier main vectors that were determined for a previous image.

18. The method according to claim 4, further comprising:

transforming said marks with the main vectors as bases for producing a rotation-corrected image in which rotation of the marks over the plane of the image is essentially eliminated.

19. The method according to claim 18, further comprising:

compensating for perspective in the rotation-corrected image.

20. The method according to claim 18 wherein calculating of the spatial frequency spectrum identifies peaks therein, the method further comprising:

determining a width of the peaks corresponding to the main vectors in a spatial frequency spectrum of said rotation-corrected image; and

compensating for perspective in the rotation-corrected image if the width exceeds a given width value.

21. The method according to claim 19, compensating for perspective further comprises:

measuring an inclination variation for the raster pattern along each main vector in the rotation-corrected image;

calculating a perspective transform based upon the measured inclination variation, which perspective transform essentially eliminates said inclination variation; and

producing a perspective-corrected image by means of the perspective transform.

22. The method according to claim 21, wherein the measurement of the inclination variation for the raster pattern along a selected main vector further comprises:

calculating at least one subset main vector for each subset via Fourier analysis of at least two subsets of the rotation-corrected image distributed along the selected main vector;

identifying an initial position in the associated subset for each subset main vector; and

calculating the inclination variation along the selected main vector based upon said subset main vectors and initial positions.

23. The method according to claim 22, wherein the initial position is identified based upon the center of gravity of the marks incorporated in the respective subset.

24. The method according to claim 18, further comprising:

measuring a phase displacement of one of the rotation-corrected and perspective-corrected image along the respective main vector based upon Fourier analysis of one of the rotation-corrected and perspective-corrected image; and

localizing the raster pattern relative to said marks in the image based upon the measured phase displacements.

25. The method according to claim 24, further comprising:

calculating a normalizing transform that places intersections of the raster pattern a given distance apart; and

operating the normalizing transform on the image in order to produce a normalized image.

27. A computer-readable computer program product which comprises a computer program with instructions for causing the computer to implement a method according to claim 1.

28. A device for position determination, comprising:

a sensor for producing an image of a partial surface of a surface which is provided with a position code in the form of a plurality of marks, wherein each of which is associated with one of a plurality of intersections belonging to a virtual raster pattern; and

an image-processor which is arranged to calculate a position for the partial surface based on a subset of the surface, wherein the image-processor identifies the virtual raster pattern in accordance with claim 1.

29. A device according to claim 28, which is hand-held.

30. A device according to claim 28, further comprising:

a transceiver which wirelessly transmits position information.

26. A method for identifying a virtual raster pattern (5) in an image of a plurality of marks (4), each of which is associated with a respective intersection (6) of raster lines (7) belonging to said raster pattern (5), characterized by the steps of

detecting main vectors of the image via Fourier analysis,

compensating for rotation in the plane of the image on the basis of said main vectors,

detecting a perspective in the image,

if necessary, compensating for said perspective, and

identifying the virtual raster pattern (5) on the basis of said main vectors.

31. A method of identifying a coordinate reference in an image containing a representation of a plurality of marks, for determining two-dimensional positions on a surface, comprising:

placing unit pulses at the positions of at least some of the representations of the plurality of marks;

generating a spectrum in two-dimensions based on the unit pulses;

determining at least two main vectors based on the spectrum, wherein the main vectors are associated with the dominant frequencies in the image;

detecting artifacts introduced during image acquisition; and

identifying the coordinate reference based upon the main vectors and detected artifacts.

32. The method according to claim 31, wherein each of the plurality of marks determine a value used in encoding position based on their direction of offset from intersection points of the coordinate reference.

33. The method according to claim 31, wherein unit pulses are placed at the center of gravity corresponding to each identified mark.

34. The method according to claim 31, wherein the two-dimensional spectrum is determined based on a portion of the image.

35. The method according to claim 31, wherein the determining further comprises:

finding positions of peaks having vector magnitude values exceeding a threshold value in the two-dimensional spectrum; and

selecting the at least two main vectors based upon the positions.

36. The method according to claim 35, further comprising:

incrementally changing the angle of a direction vector within a range;

calculating at least one magnitude value of the two-dimensional spectrum associated with the direction vector; and

identifying the magnitude value or values exceeding the threshold value.

37. The method according to claim 36, further comprising:

changing the length of the direction vector within a frequency range that includes a nominal spatial frequency of the coordinate reference.

38. The method according to claim 35, wherein the finding further comprises:

calculating a center of gravity of the adjacent magnitude values which exceed the threshold value; and

determining positions of the centers of gravity.

39. The method of claim 35, wherein the selecting further comprises:

representing each position by a candidate vector;

transforming the candidate vectors using a current transform chosen from a plurality of transforms, wherein the plurality of transforms modify a mutual relationship among the candidate vectors; and

selecting transformed candidate vectors associated with the current transform which produces a desired mutual relationship, and designating the transformed candidate vectors as the main vectors.

40. The method of claim 35, wherein the selecting further comprises:

representing each position by a candidate vector;

transforming sequentially the candidate vectors using a plurality of transforms, wherein the plurality of transforms modify a mutual relationship among the candidate vectors, until a desired mutual relationship is achieved; and

designating the transformed candidate vectors satisfying the mutual relationship as the main vectors.

41. The method according to claim 39, wherein the current transform corresponds to a geometric relationship between a sensor recording the image and a surface provided with the plurality of marks.

42. The method according to claim 39, further comprising:

identifying the coordinate reference based on the image transform corresponding to the desired relationship among the candidate vectors.

43. The method according to claims 39, further comprising:

selecting the current image transform based on a transform producing the desired relationship for a previous image.

44. The method according to claim 31, further comprising:

selecting the main vectors based upon main vectors determined for a previous image.

45. The method according to claim 31, wherein the detecting and applying compensations further comprises compensating the image for unknown rotations.

46. The method according to claim 45, further comprising:

removing the rotation from the image by transforming the unit pulses using the main vectors as a reference.

47. The method according to claim 31, wherein the detecting and applying compensations further comprises compensating for unknown perspective in the image.

48. The method according to claim 47, further comprising:

detecting the amount of perspective distortion by dividing the image into a plurality of subsets, and detecting at least one direction in each subset, in the two-dimensional spectrum of the respective subset; and

computing a transform which compensates for the perspective in the image and applying the transform to the image.

49. The method according to claim 31, wherein the detecting and applying compensations further comprises compensating for position displacements of the coordinate reference with respect to the unit pulses in the image.

50. The method according to claim 49, further comprising:

measuring phase values based upon the two-dimensional spectrum; and

computing at least one displacement correction based upon the phase values.

51. The method of claim 31 further comprising applying compensation to a representation of said image to correct the detected artifacts.

58. The apparatus according to claim 34, wherein the processor executes further instructions comprising:

identifying the coordinate reference based on the image transform corresponding to the desired relationship among the candidate vectors.

52. An apparatus which identifies a coordinate reference for determining two-dimensional positions on a surface, comprising:

a sensor for acquiring an image of the surface containing a plurality of marks; and

a processor which executes instructions for

placing unit pulses at the positions of at least some representations of the plurality of marks in the image,

generating a spectrum in two-dimensions based on the unit pulses,

determining at least two main vectors based on the spectrum, wherein the main vectors are associated with the dominant frequencies in the image,

detecting artifacts introduced during image acquisition, and

identifying the coordinate reference based upon the main vectors and detected artifacts.

53. The apparatus according to claim 52, wherein the processor executes further instructions comprising:

finding positions of peaks having vector magnitudes exceeding a threshold value in the two-dimensional spectrum; and

selecting the at least two main vectors based upon the positions.

54. The apparatus according to claim 53, wherein the processor executes further instructions comprising:

incrementally changing the angle of a direction vector within a range;

calculating at least one magnitude value of the two-dimensional spectrum associated with the direction vector; and

identifying the magnitude value or values exceeding the threshold value.

55. The apparatus according to claim 54, wherein the processor executes further instructions comprising:

changing the length of the direction vector within a frequency range that includes a nominal spatial frequency of the coordinate reference.

56. The apparatus according claim 53, wherein the processor executes further instructions comprising:

representing each position by a candidate vector;

transforming the candidate vectors using a current transform chosen from a plurality of transforms, wherein the plurality of transforms modify a mutual relationship among the candidate vectors; and

selecting transformed candidate vectors associated with the current transform which produces a desired mutual relationship, and designating the transformed candidate vectors as the main vectors.

57. The apparatus according to claim 56, wherein the current transform corresponds to a geometric relationship between a sensor recording the image and a surface provided with the plurality of marks.

59. The apparatus according to claim 52, wherein the compensating further comprises compensating the image for unknown rotations.

60. The apparatus according to claim 52, wherein the processor executes further instructions comprising:

removing the rotation from the image by transforming the unit pulses using the main vectors as a reference.

61. The apparatus according to claim 52, wherein the compensating further comprises compensating for unknown perspective in the image.

62. The apparatus according to claim 61, wherein the processor executes further instructions comprising:

detecting the amount of perspective distortion by dividing the image into a plurality of subsets, and detecting at least one direction in each subset, in the two-dimensional spectrum of the respective subset; and

computing a transform which compensates for the perspective in the image and applying the transform to the image.

63. The apparatus according to claim 52, wherein the compensating further comprises compensating for position displacements of the coordinate reference with respect to the unit pulses in the image.

64. The apparatus according to claim 63, wherein the processor executes further instructions comprising:

measuring phase values based upon the two-dimensional spectrum; and

computing at least one displacement correction based upon the phase values.

65. The apparatus of claim 52 wherein said processor further performs the step of compensating a representation of the image to identify the coordinate reference.