Reconstruction of virtual raster

• US 6,929,183 B2
• Filed: 12/06/2002
• Issued: 08/16/2005
• Est. Priority Date: 12/06/2001
• Status: Expired due to Term

• Current Assignee: Anoto Group AB
• Original Assignee: Anoto Group AB
• Inventors: Pettersson, Mats Petter
• Primary Examiner(s): LE, THIEN MINH
• Application Number:
  US10/310,941
• Publication Number:
  US 20030122855A1
• Time in Patent Office: 984 Days
• Field of Search: 23546201-46245, 235/472.01, 235/472.02, 235/472.03, 235/454, 235/455, 235/494, 382/240, 382/248, 382/251, 382/233, 382/238
• US Class Current: 235/462.25
• 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: G06T 3/00 Geometric image transformations in the plane of the image
• CPC Class Codes: G06V 10/19 by sensing codes defining pattern positions
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/247 by affine transforms, e.g. correction due to perspective effects; Quadrilaterals, e.g. trapezoids
• CPC Class Codes: G06V 30/142 using hand-held instruments; Constructional details of the instruments
• 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 aims at identifying, starting from objects in a digital image, a virtual raster included in a coding pattern. The objects in the image at least partially reproduce marks on a base, each mark being associated with a respective point of intersection of raster lines belonging to the virtual raster. The method comprises the steps of matching sets of objects against a cell unit, which corresponds to a recurring known basic element of said raster; when a set corresponds with the cell unit, identifying the objects in the set as approved; and reconstructing the virtual raster on the basis of the mutual arrangement of the approved objects. A computer program, a storage medium and a device for position determination are also described.

Claims

1. A method for reconstruction of a virtual raster based on objects in a digital image, the objects at least partially reproducing marks on a base, and each mark being associated with a respective point of intersection of raster lines belonging to the virtual raster, said method comprising:

matching sets of objects against a cell unit, which corresponds to a recurring known basic element of said raster;

when a set corresponds with the cell unit, identifying the objects in the set as approved; and

reconstructing the virtual raster on the basis of the mutual arrangement of the approved objects.

2. The method as claimed in claim 1, in which the objects in the image are represented by a ensemble of points.

3. The method as claimed in claim 1, in which the cell unit is associated with a given number of objects.

4. The method as claimed in claim 1, in which the cell unit is a polygon whose corners connected via side lines are each associated with an object.

5. The method as claimed in claim 1, comprising:

forming a subset of objects containing approved objects which form a contiguous area corresponding to a plurality of adjacent cell units; and

reconstructing the virtual raster on the basis of the subset of objects.

6. The method as claimed in claim 5, in which the contiguous area is formed so as to at least comprise the approved objects which are connected in pairs by a side line common to two cell units.

7. The method as claimed in claim 5, in which the subset of objects is formed so as to contain the greatest possible number of approved objects.

8. The method as claimed in claim 1, comprising the initial step of creating a data structure containing the neighbor relationships of the objects, the matching comprising identifying said sets by using the data structure.

9. The method as claimed in claim 1, further comprising:

determining, in the digital image, main vectors which reproduce its general raster line directions and raster line spacings;

on the basis of the main vectors, identifying the neighbor relationships of the objects by identifying, for each object, another object as neighbor in the respective raster line direction; and

subsequently carrying out the matching step on the basis of the neighbor relationships of the objects.

10. The method as claimed in claim 8, in which the objects included in a set are identified as approved if they form as neighbors a cyclic structure which corresponds to the cell unit, at least with respect to the number of objects associated therewith.

11. The method as claimed in claim 9, in which the objects included in a set are identified as approved if they form as neighbors a cyclic structure which corresponds to the cell unit, at least with respect to the number of objects associated therewith.

12. The method as claimed in claim 1, comprising:

allocating each of the approved objects a raster position in a raster coordinate system on the imaged base, the virtual raster being reconstructed on the basis of the location of the objects in the digital image and their allocated raster position on the base.

13. The method as claimed in claim 1, in which reconstructing the virtual raster comprises computing the raster lines by regression adaptation of the location of the approved objects along given directions.

14. The method as claimed in claim 5 or 13, in which the directions are given by raster positions, preferably by integer coordinates in a raster coordinates system, which raster positions are assigned the approved objects in conjunction with the step of forming the subset of objects.

15. The method as claimed in claim 1, in which the step of reconstructing the virtual raster comprises computing a homogeneous transformation matrix based on the positional relationships between the approved objects and the corresponding points of intersection which are located on the base and whose mutual arrangement is defined by the basic element.

16. The method as claimed in claim 6 or 15, in which the positional relationships are given by raster positions, preferably by integer coordinates in a raster coordinate system, which raster positions are assigned the approved objects in conjunction with the step of forming the subset of objects.

17. The method as claimed in claim 16, for processing of a sequence of digital images, comprising:

correcting a current digital image for rotation in its plane, by means of a first transformation matrix;

, computing the homogeneous transformation matrix based on the image thus rotation-corrected; and

updating the first transformation matrix before processing of a subsequent digital image.

18. The method as claimed in claim 17, in which the updating of the first transformation matrix comprises extracting relevant linear parameters from the homogeneous transformation matrix.

19. The method as claimed in claim 1, in which the matching is carried out only for the objects which are mutual neighbors.

20. A computer program which comprises program code which, when executed in a computer, causes the computer to implement a method as claimed in any one of claims 1-13, 15, and 17-19.

21. A computer-readable storage medium on which a computer program is stored which, when executed in a computer, causes the computer to implement a method as claimed in any one of claims 1-13, 15, and 17-19.

22. A device for position-decoding which computes a position on the basis of a digital representation of a partial area of a position-coding pattern, said position-coding pattern comprising marks which are each associated with a respective point of intersection of raster lines belonging to a virtual raster, said digital representation comprising objects which at least partially reproduce said marks;

wherein said device comprises;

means for matching sets of said objects against a cell unit which corresponds to a recurring known basic element of said raster;

means for identifying, when a set corresponds with said cell unit, the objects in said set as approved;

means for reconstructing the virtual raster on the basis of the mutual arrangement of the thus-approved objects; and

means for computing said position on the basis of said virtual raster and said objects in said digital representation.