Reconstruction of virtual raster

(54) NAME Reconstruction of a virtual grid (56) PUBLISHING: - - - (57) SUMMARY: A procedure aims to identify, based on objects in a digital image, a virtual grid included in a coding pattern. The objects in the image represent at least partial markings on a substrate, each mark being associated with a respective intersection point for grid lines belonging to the virtual grid. The method comprises the steps of matching sets of the objects to a cell unit which corresponds to a recurring, known basic element of said raster; that when a set matches the cell unit, identify the objects included in the set as approved; and to reconstruct the virtual grid based on the position of the approved objects.

A computer program, a storage medium and a position determination device are also described.

<img file="SE520682C2_D0001.tif" />

Load grayscale image

<img file="SE520682C2_D0002.tif" />

The numbers in brackets indicate international identification code, INID code. Letter Within the pinch indicates international document code.

520 682

SUMMARY

A method aims to identify, based on objects in a digital image, a virtual grid included in a coding pattern. The objects in the image represent at least partial markings on a substrate, each mark being associated with a respective intersection point for raster lines belonging to the virtual grid. The method comprises the steps of matching sets of the objects to a cell unit which corresponds to a recurring, known basic element of said raster; that when a set matches the cell unit, identify the objects included in the set as approved; and to reconstruct the virtual grid based on the position of the approved objects.

A computer program, a storage medium and a position determination device are also described.

520 682

Technical area

The present invention relates generally to the identification of coding patterns in digital images. More particularly, the invention relates to a method, a computer program, and a storage medium for use in reconstructing a virtual grid included in such a coding pattern.

The invention also relates to a device for decoding positions from digital images of a coding pattern.

Background of the Invention

It is known to embed information of some kind into a passive substrate using a coding pattern, such as a paper, a writing board or the like. An appropriately programmed scanner, fax machine, camera or digital pen can then read, reproduce and use the information embedded locally in the documentation. For example, graphical information on a substrate can be supplemented with embedded information that enhances the functionality of the substrate. Such embedded information may refer to commands, file data, absolute positions, hyperlinks, etc.

Coding patterns are usually built around some kind of machine-readable symbols or markings that are placed in relation to the raster points of a regular, invisible raster on the substrate. Examples of such coding patterns are given in WO 00/73983, WO 01/26032, US-A-5 477 012 and US-A-5 221 833.

In general, and especially when the coding pattern is detected with a handheld device, such as a digital pen, the resulting image will, in addition to objects corresponding to the markings, also contain noise interference, geometric distortion, signal level irregularities, etc.

520 682

Thus, it is a common problem to identify the objects before decoding the coding pattern in a computationally efficient and noise-insensitive manner.

The above problems and previously proposed solutions will be elucidated in the following in connection with a particular coding pattern, which is described in detail in the above patent publication WO 01/26032. The coding pattern consists of a grid and markings, which are located at each grid point. The markings are preferably substantially round and are offset relative to the dot points in either of four orthogonal directions. The grid is virtual and thus invisible to both the eye and sensors.

For example, a coding pattern of this type can be used to encode absolute positions on a substrate. This enables digital registration of information that is written and / or drawn by hand with a digital pen on the substrate. During pen movement, continuous images of the coding pattern are recorded locally at the tip of the pen. A subset of the objects in each of the images is decoded to a position. The decoded positions together form a digital description of the pen's movement across the ground.

In patent publication WO 01/26034, an iterative technique for reconstructing the virtual grid is described in a digital image of the above coding pattern. At each iteration, the steps are identified to identify two adjacent objects, to determine, with knowledge of the position of one object relative to its raster point, and on the basis of a measured distance between the objects, the raster point of the other object, and to search for a new point of view thus determined. objects within a search area defined with knowledge of the raster's nominal main directions. When all objects have been processed, objects have been risen object by object through the image and identified associated raster points, thereby reconstructing the virtual raster.

520 682

This technique is fast but relatively sensitive to interference, because it is based on local decisions about individual objects and assessment of their locations relative to the grid points.

An alternative technique is described in WO 01/75783. Here, Fourier analysis is used for extracting directional vectors from a point set, which reflects the location of the objects in the digital image. First, the overall point vectors of the point set are determined, which are then used in correcting the point set with respect to rotation and scale errors in the image plane. Subsequently, additional principal vectors are calculated in different parts of the corrected point set, for extraction of measures of perspective effects and phase shift. Then, the point quantity is finally corrected on the basis of these measures, whereupon the virtual grid is given by the overall head vector of the resulting point quantity. The technique is relatively insensitive to interference, but may in some contexts be undesirable computationally intensive.

Summary of the Invention

The object of the present invention is therefore to provide a technique that overcomes the above problems, and more particularly to provide a technique which enables robust and / or computationally efficient identification of a virtual screen in a digital image of a coding pattern.

These and other objects, which will become apparent from the following description, are achieved, in whole or in part, by a method, a computer program, a storage medium and a positioning device according to the following claims 1, 19, 20 and 21. Preferred embodiments are defined in the dependent claims.

Because sets of the objects in the digital image are matched against a cell unit corresponding to a recurring, known basic element of the grid, the effect of interference in the form of fictitious objects is limited, since the majority of them are not placed in accordance with the cell unit and are therefore filtered off. at the match. If any single object in the match incorrectly

520 682 is identified as approved, the matching of surrounding objects is only affected to a limited extent. The matching can also be carried out in a calculation-efficient manner.

From a computational point of view, it can be advantageous, during both the matching and the reconstruction, to let the objects in the image be represented by a number of points. Thus, each object can be represented by a point whose position may correspond to a center of gravity of the object, a maximum or minimum luminance value of the object, etc.

The above-mentioned cell unit may be represented by a polygon whose vertically connected vertices are associated with each object. Such a polygon thus corresponds to the basic element of the grid with respect to the number of sidelines and the number of associated markings. In contrast, the extent and shape of the cell unit may differ from that of the basic element, to allow for geometric distortion in the digital image.

According to one embodiment, matching is performed as a regular comparison between sets of objects in the digital image and a number of possible cell units of various extents and shapes, taking into account the imaging conditions. Alternatively, the image is first corrected, at least with respect to rotation in the image plane, whereupon the matching is effected by comparing the sets with a cell unit identical to the base element.

According to an alternative, preferred embodiment, a data structure is first created which specifies the neighboring conditions of the objects. In the matching, the data structure is then used to identify said sets among the objects. Thus, a neighbor criterion is used to select the sets of objects that may be matched to the cell unit at all, which makes the matching more efficient. Thanks to the preparatory selection, it may also be possible to apply a less strict matching criterion, such as that the set and the cell unit need only have the same number of objects, which can reduce the risk of correcting

520 682 objects are missed at the match, especially at the coding pattern initially described whose markings are offset relative to their intersection points. The above-mentioned neighbor criterion may be that the objects in a set should form a cyclic structure of neighbors and that this cyclic structure should correspond to the cell unit, at least with respect to the number of objects associated with it. Thus, the matching step can be reduced to identifying cyclic structures with a given number of objects, which can easily be accomplished through a sequence of lookups in the data structure.

To further increase the resistance to interference, the matching can be preceded by the elimination of all objects that are not mutual neighbors, that is, the matching is performed only for those objects which according to some criterion have each other as the most likely neighbor.

Resistance to interference can be further increased by reconstructing the virtual grid on the basis of an object subset, which contains approved objects that form a contiguous region corresponding to several adjacent cell units. Conveniently, the contiguous region is formed to at least comprise the approved objects that are joined in pairs by a sideline common to two cell units.

The virtual grid can be reconstructed by assigning the approved objects, at least those in the aforementioned object subset, to a raster position in a raster coordinate system on the mapped substrate, and reconstructing the virtual raster by linking the location of the objects in the digital image to their mapped raster position. on the substrate.

In one example, the grid lines of the grid are calculated by regression fitting the position of the approved objects along given directions, which directions can be extracted from the above grid positions.

In another example, a homogeneous transformation matrix is ​​calculated based on the coupling between the positions of the well known objects and the corresponding positions of the intersection points.

According to an embodiment for processing a sequence of digital images, a current digital image for rotation in the image plane is first corrected via a first transformation matrix, after which the above-mentioned homogeneous transformation matrix is ​​calculated from the rotation-corrected image. Prior to processing a new current image, the first transformation matrix is ​​updated based on the last calculated homogeneous transformation matrix. This embodiment is computationally efficient in that the first transformation matrix does not need to be calculated from the objects in each current image.

Brief description of the drawings

The invention is described below by way of example with reference to the accompanying drawings, which schematically illustrate presently preferred embodiments.

Fig. 1 is a schematic view of a set of 4x4 markings in a coding pattern.

Fig. 2 is a schematic view of a handheld apparatus which can be used to detect the coding pattern of Fig. 1.

Fig. 3 schematically represents a digital image of a coding pattern of the kind shown in Fig. 1.

Figure 4 shows a figure 3 corresponding to the amount of points after compensation for rotation and scale errors in the image plane and after identification of the neighboring conditions between the points.

Fig. 5 illustrates a local environment of a point and associated search areas for identification of neighboring points.

Fig. 6 shows a data structure for recording neighboring conditions in the digital image.

Fig. 7 shows a figure 4 corresponding to the amount of points after extracting points with mutual neighbors, which are shown as dashes in Fig. 7.

520 682

Fig. 8 shows a figure 7 corresponding to the amount of points after extracting points contained in cyclic structures of a given format.

Fig. 9 is a flow chart showing overall steps performed in identifying the subset to be finally used in reconstructing the points' positions relative to a virtual grid.

Fig. 10 illustrates, from the point set of Fig. 8, a first partial step of the reconstruction according to a first embodiment.

Fig. 11 illustrates the end result of the reconstruction according to the first embodiment.

Fig. 12 illustrates, from the point set of Fig. 8, a reference point set used in the reconstruction according to a second embodiment.

Fig. 13 illustrates the end result of the reconstruction according to the second embodiment.

Fig. 14 is a flow chart showing overall steps that can be performed in the reconstruction according to the second embodiment.

FIG. 15 is a FIG. 7 corresponding view of an alternate point set after extracting points with reciprocal neighbor conditions.

Description of preferred embodiments

The description below is directed to position determination based on digital images of a position coding pattern. The position coding pattern may be of any kind, for example, any of the patterns initially pointed out. However, in the following, the invention is exemplified in connection with the pattern described in the applicant's patent publications WO 01/16691, WO 01/26032 and WO 01/26033. This pattern is briefly described below with reference to Fig. 1.

The position coding pattern comprises a screen 10 which is constructed of a number of screen lines 11. The screen 10 is virtual in such a way that it is neither visible to the human eye nor can be detected directly by a device which

520 682 shall determine positions on the surface. The grid 10 can be seen as made up of a plurality, side by side, mutually identical basic elements, in this case squares. The position coding pattern also includes a plurality of markings 12, each of which, depending on its location, represents one of four values ​​1 to 4. The value of the markings 1 2 depends on where it is placed relative to its nominal position 13. The nominal position 13, which can also be referred to as a raster point, is represented by the intersection of the raster lines 11.

In the example of Fig. 1, there are four possible locations, one on each of the raster lines starting from the nominal position 13. The displacement from the nominal position 13 is equal for all values. Each marking 12 is offset with its center of gravity relative to its nominal position 13, ie no marking is located in the nominal position. Furthermore, there is a single marker 12 per nominal position 13.

The offset is preferably 1/6 of the raster line distance, since it becomes relatively easy to determine which nominal position to which a particular mark belongs. The offset should be at least about 1/8 of the raster line distance, as it may be difficult to determine an offset, i.e., the resolution requirements become large. On the other hand, the offset should be less than about 1/4 of the grid line distance in order to determine the nominal position.

Each mark 12 in this example consists of a more or less circular dot with a radius about equal to the offset or slightly smaller. The radius can be between 25% to 120% of the displacement. If the radius becomes much larger than the offset, it may be difficult to determine the raster lines. If the radius becomes too small, larger resolution is needed to register the markings. However, the markings need not be circular or round, but may be of any suitable shape,

520 682 such as square, triangular, elliptical, filled, unfilled etc.

The patterns described above can be designed to encode a very large number of absolute positions. For example, the pattern may be such that 6x6 adjacent markings together encode a substrate, in the form of an x-coordinate and a y-coordinate. If a subset of the pattern is applied to a substrate, an electronic representation of what is written or drawn on the substrate can be obtained with a pen by continuously determining the position of the pen on the product by reading the local combination of markings. This reading can be done by optical detection.

Fig. 2 shows a handheld device 20, hereinafter called a pen, which is used for optical detection of the position coding pattern in Fig. 1. The following is a brief description of the main components of the pen according to one embodiment. For a more complete description, reference is made to the above-mentioned patent publications WO 01/16691, WO 01/26032 and WO 01/26033.

The pen 20 has a pen-shaped housing 21 defining at its one short end an opening 22. The short end is intended to abut against or be kept at a small distance from the surface on which the position determination is to be made.

One or more infrared LEDs 23 are arranged at the aperture 22 to illuminate the surface area to be imaged, and an IR-sensitive area sensor 24, such as a CCD or CMOS sensor, is arranged to record a two-dimensional image of the surface area.

The area sensor 24 is coupled to a data processor 25 which is arranged to determine a position based on the image recorded by the sensor 24. The data processor 25 may contain a processor means 25a programmed to process images from the sensor 24, or memory assigned to a sensor 24, for position determination on the basis of these images.

Processor means 25a may comprise a microprocessor such as a CPU (Central Processing Unit), a DSP (Digi520 682 speech signal processor) or any other programmable logic device such as an FPGA. The processor means 25a may alternatively, or additionally, comprise a hardware circuit, such as an Application-Specific Integrated Circuit (ASIC) and / or discrete analog and digital components.

The memory means 25b preferably comprises various types of memory, such as working memory (RAM), read memory (ROM / FLASH) and write memory (FLASH). In known manner, the working memory can store data while it is processed by the processor means 25a, the read memory can store the program code executed by the processor means 25a in the working memory, and the write memory can store the result of the processing, such as position coordinates.

The pen 20 also has a pen tip 26 which deposits marking fluid on the substrate. Thus, the user can physically write on the substrate while the written is digitally recorded via optical detection of the position coding pattern. The marking liquid is suitably transparent for infrared light, while the marking pattern markings 12 (Fig. 1) are absorbent for infrared light. This avoids the selection fluid interfering with the detection of the pattern.

Thus, when the pen 20 is moved over a position-coded support, the area sensor 24 records a sequence of digital grayscale images transmitted to the data processor 25 for position determination. In the pictures, the markings 12 (Fig. 1) appear as dark objects against a light background. Usually, each item covers several pixels.

In order to decode an image, the data processor must reconstruct the virtual grid and determine a given number of object locations relative to it.

Prior to the reconstruction of the virtual grid, the data processor first executes a so-called segmentation process to isolate the objects from the background of the grayscale image and thereby reduce the amount of data to process in subsequent steps. This can be done by a well-known thresholding operation, which results

520 682 in a binary image. To further reduce the amount of data, the data processor can extract a point amount from the binary image, for example, by calculating the center of gravity of each object. Thus, the end result of the segmentation process may be a binary image (bitmap), where each object is identified by a pixel (pixel), or some other data structure containing a location determination for each pixel or sub pixel resolution object.

The segmentation process will generally also identify fictitious objects, ie, objects without equivalent in the depicted subset of the position coding pattern, for example as a result of noise, lighting variations, or artifacts (dirt, unevenness, etc.) of the position-coded substrate. Such fictitious objects can interfere with the decoding process.

Fig. 3 schematically shows a digital image of the coding pattern described above. In Fig. 3, objects with rings and the corresponding set of points are indicated by a cross. The virtual grid 10 is also inscribed to facilitate understanding. Obviously, the digital image is registered with twisting and sharp tilting of the sensor relative to the position-coded substrate. It should be emphasized that Fig. 3 is a schematic example, and in the practical case the number of n objects can be considerably larger. Although each position is encoded by 36 (6 x 6) objects, each digital image generally includes more objects, typically n = 100-200.

After segmentation, the binary image is subjected to a correction process which results in a point set substantially without twisting in the image plane. This can be accomplished via Fourier analysis of the point amount, as described in detail in the above-mentioned patent publication WO 01/75783. The Fourier analysis results in overall head vectors for the point set, i.e., overall directions and distances in the binary image. Next, a linear transformation matrix is ​​calculated which transfers the main vectors to result vectors whose direction and length substantially correspond to the original grid (Fig. 1), in this case mutually orthogonal vectors having a 1: 1 aspect ratio. The point quantity is then corrected for torsion and scale errors by operating the transformation matrix on the original point quantity. Figure 4 shows the result of the point quantity correction process in Figure 3. For reasons of clarity, the virtual grid 10, which has not yet been reconstructed, is also shown. It can be seen that a non-linear component, ie perspective distortion, remains with the corrected point set.

Thereafter, the data processor executes a search process, which aims to identify the points' neighboring conditions. Specifically, for each point in the point set, a neighboring point is searched in given search directions.

The search process is further illustrated in Figure 5, starting from two result vectors v_x, v₂ as above. In the search process, four are used, based on these result vectors v_LZ v₂ defined, search vectors: v_LZ v₂, v₃= -v₁ and V₄= -v₂. Each search vector is in turn assigned to a search area I-IV, the extent of which is set with knowledge of the structure of the coding pattern. The search areas are suitably large enough to ensure detection of a point belonging to an adjacent raster intersection, but small enough to avoid detection of points belonging to other raster intersections (cf. Fig. 1). In the current coding pattern, each marker is offset 1/6 of the grid line distance, so the smallest distance between the marks is 2/3 grid line distance (marks that are offset towards each other). Perspective effects in the image can reduce this distance, so the radius of the search areas in the present example has been set to about 1/2 grid line distance.

From a point A in Fig. 5, a neighbor point D in the search area I, two potential neighbors B and C in the search area II, and no neighbor points in the search areas III-IV are identified.

520 682

If several potential neighboring points are identified per search area, the neighboring point that is closest to the center of the search area is selected, ie the tip of the search vector. This selection process can also take into account the surface size of the objects corresponding to the points, for example in relation to the known nominal size of the objects. Thus, the effect of noise can be reduced, which usually results in objects of small surface size.

During the search process, the data processor creates a table, list, or other data structure containing a neighbor point in the respective search direction, for each point in the point set, as indicated in Fig. 6. This table defines a skeleton of neighbor conditions for use in reconstructing the virtual grid.

In Fig. 4, the arrows represent the neighboring conditions determined for the set of points in Fig. 3.

However, the above skeleton is further refined in two control steps before the data processor executes the reconstruction of the grid.

In the first control step, only the points that are mutual neighbors are extracted, as indicated by bidirectional arrows in Figure 4. The corresponding skeleton is shown in Figure 7, in which single bars indicate mutual neighbor conditions.

In the second control step, schematically shown in Figure 9, the skeleton of Figure 7 is first matched to cyclic structures of known format (step 901). The cyclic structures can be seen as cell units which correspond to the basic element of the original grid. In the example, the basic elements are squares and the cell elements are arbitrary four-corner polygons with each one point. The cyclic structures can be identified from the data structure of Fig. 6, by checking for a current point the data processor for a first neighbor in the first search direction._LZ if the first neighbor has a second neighbor in the second search direction v₂, if the second neighbor has a third neighbor in the third search direction

520 682 v₃, if the third neighbor has a fourth neighbor in the fourth search direction v₄, and if the fourth neighbor is identical to the current point. In this case, these points are extracted and identified as part of a cell unit. Figure 8 shows the cell units identified from Figure 7.

The links between the points are then classified. If the link is included as a sideline in two cell units, the link is classified as strong (step 902), otherwise weak (step 903).

The classification is then used to identify a contiguous area of ​​the skeleton to use in reconstruction. This is done by the data processor selecting a starting point (step 904) from the points contained in the cell units and identifying all strong points, ie points that can be reached from the starting point via strong links (step 905). Subsequently, the data processor identifies all weak points, ie points that can be reached from the strong points via one and only one weak link (step 906). The data processor forms a first component or subset of the identified strong and weak points (step 907), and then repeats the above search for other starting points (step 908). These starting points may conveniently be selected from those points not yet included in any component, or at least among those points not yet rated as strong. In the latter case, weak points can thus be included in several components. When all possible starting points have been tested, the component containing the most points, or the strongest points (step 909) is selected.

Figure 8 shows the result of the second control step for the points extracted from the skeleton of Figure 7, starting from the starting point S. Strong and weak links are shown with double and single dashes respectively, and strong and weak points are shown with filled and unfilled circles respectively.

520 682

Figure 8 also shows that the strong and weak points, at least in the selected component, are assigned their respective raster positions in a raster coordinate system which may, but need not, be centered at the starting point S. Each raster position is given in the example of two raster coordinates in the form of integers. . These raster positions are used to connect the points of the component to the raster intersections of the original coding pattern, as will be described in more detail below.

The above classification of the links aims to minimize the occurrence of errors when a component is formed by several locally identified cell units. Figure 15 shows an example of a skeleton of reciprocal neighboring points / objects in an image. Although each cell unit seems correctly identified in its local environment, the cell units as a whole contain a geometric error. If the component is built on the basis of only strong links, then this type of geometric error is minimized since the strong links are part of two cell units and are thus determined with greater security than the weak links.

However, as the subsequent reconstruction improves with the number of points included in the selected component, weak links can be allowed to contribute to the component with an additional point, as described in the above example. Although not shown in the example of Fig. 8, it may be convenient to reduce the impact of the weak points relative to the strong points, for example by giving the weak points a raster position determined in only one dimension, and more precisely so, that a weak point is assigned to the grid coordinate common to the weak point and the strong point that links the weak point to the current component.

Next, the virtual grid will be reconstructed based on the selected component of Figure 8.

520 682

In a first embodiment, the data processor performs a regression fit of groups of points to straight lines approximating raster lines, as indicated in Figure 10. Specifically, the points are grouped according to their raster positions. Starting from Fig. 8, vertical groups have been formed with points whose raster positions in a first dimension are given by -1, 0, 1, 2 and 3, respectively, and horizontal groups with points whose raster positions in a second dimension are given by -1, 0, 1. , 2, 3 and 4. The direction of each individual line can be of low precision, due to the low number of points per line, especially at the periphery of the selected component. Therefore, the data processor performs a complementary regression adjustment, in which the slope coefficient of the vertical and horizontal lines is adjusted to a linear function in the horizontal and vertical lines respectively. Perspective effects mean that parallel lines are directed towards a common perspective. This is shown, for example, in the aforementioned patent publication WO 01/75783, which is incorporated herein by reference.

After the second regression adjustment, new raster lines can be calculated which constitute a substantially correct reconstruction of the virtual raster 10, as shown in Fig. 11.

Alternatively, the data processor can execute the complementary regression adaptation by adjusting the mutual distances between adjacent vertical and horizontal lines to a linear function along a horizontal and vertical direction vector, respectively. Also in this case, it is possible to reconstruct the raster lines that form the virtual grid.

With knowledge of the virtual grid, the data processor can then decode the points in the selected component and on the basis thereof calculate the position of the sensor device on the position-coded support. For details on decoding, refer to the aforementioned patent publications

520 682

WO 01/16691, WO 01/26032 and WO 01/26033, which are incorporated herein by reference.

In a second embodiment, the data processor performs the reconstruction by calculating a homogeneous transformation matrix. In this case, each point in the selected component, as shown in Fig. 8, is compared to the corresponding raster intersection in an ideal raster, as shown in Fig. 12. Here, the raster positions are used to identify points and corresponding raster intersections, as also indicated in Figs. 8 and 12. . Thus, an equation system can be set up containing twelve unknown parameters (of the transformation matrix) and equations that are twice the number of the points in the selected component, similarly described in Digital Image Processing by RF Gonzalez and RE Woods, Addison-Wesley, 1992, pp. 67-68. With the knowledge that all points originate from one and the same geometric plane (ie the ground), the number of unknown parameters can be reduced to eight.

There are a variety of known numerical methods for solving such overdetermined equation systems. The presently preferred embodiment is based on a least squared fit.

Unexpectedly, a correctly homogeneous transformation matrix can be calculated by coupling the points in Figure 8 to the grid junctions in Figure 12, since the points through their offsets (cf. Figure 1) do not exactly correspond to the grid junctions. However, the calculated transformation matrix represents some kind of mean over a large number of points, so the displacements mathematically essentially outweigh each other.

Once the homogeneous transformation matrix has been calculated, it is operated at the points of the selected component, which are then transferred to their correct locations relative to a reconstructed raster whose raster intersections are given by the raster positions, as indicated in Fig. 13.

520 682

In the following, overall process steps performed by the data processor in processing a sequence of grayscale images are described in connection with Fig. 14.

First, a current grayscale image (step 141) is loaded, which, via a segmentation process, forms a current binary image (step 142). Then, a current set of points is preferably extracted from the current binary image. Then, a linear transformation matrix LTM is calculated, for example via Fourier analysis of the current set of points (step 143). The linear transformation matrix is ​​then used to correct the current set of points for rotation and possible scale errors (step 144). Next, the search process (step 145), as well as the first and second control steps (steps 146-147), which results in a selected component, ie a selected subset of points, are executed. Finally, the data processor calculates a homogeneous transformation matrix HTM based on the points of the selected component (step 148), after which the homogeneous transformation matrix is ​​operated at the component points to create a reconstructed raster with associated points (step 149), which are then decoded (step 150).

When digitizing handwriting, this should be recorded for accurate reproduction at a sampling rate of about 50-100 Hz. At this sampling rate, however, relatively small changes occur in the rotation and tilting of the pen between subsequent images. This can be utilized to minimize the computational work of developing a new linear transformation matrix LTM for a subsequent grayscale image. Instead of performing a relatively time- and computationally demanding analysis, for example via Fourier transform, the linear parameters of the homogeneous transformation matrix HTM are copied into the linear transformation matrix LTM (step 143 '), and the updated transformation matrix thus used is used during the correction process (144). ). Thus, processing power can be released in the data processor for other calculations, such as decoding.

520 682

The above procedure can be implemented by program code executed in the digital pen's processor means, or in an external processing unit connected to the pen. The program code may be provided on a storage medium, for example in the form of a floppy disk, a CD-ROM, or propagating signals via a computer network. Alternatively, the method may be implemented by a hardware circuit and / or discrete analog / digital components, possibly in combination with the execution of program code as above.

It should be noted that the scope of the patent protection sought is not limited by the above described examples. The invention can be varied and modified in a number of ways within the scope of the appended claims.

For example, the inventive technique is also applicable to coding patterns based on other basic elements, such as hexagons, rectangles, triangles, etc., or other markings, such as dashes, triangles, two-dimensional barcodes, etc., placed with or without offset relative to the intersection points of a virtual grid pattern.

Furthermore, it should be noted that the above correction process is not linked to the use of Fourier transforms, but can be carried out by another method accepted for the purpose, such as Hough transformer, Walsh transformer etc. Otherwise it is not even necessary to carry out any correction, but the search process can are executed on the basis of the overall main vectors instead of the result vectors. However, an initial correction can facilitate the implementation of the subsequent search process, as the same search areas can be used for all points and images.

According to a further alternative without a correction process, the second control process is executed as a regular geometric matching of the point quantity against a set of different possible cell units. For example, the data processor may be arranged to retrieve possible cell units from, based on a currently calculated perspective.

520 682 a library in its memory organ. For example, a square sum of the deviations between points and the corresponding corners of the respective cell unit can be used as a matching criterion, where the square sum should fall below a limit value for conformity to be considered.

According to another possible alternative, an initial correction process takes place, after which a regular geometric matching is effected by the set of points against the known element of the coding pattern. Here, too, a square sum of the differences between points and corner positions can be used as a matching criterion.

520 682