Determination of a position code

Field of the invention

The present invention relates to a product having a surface provided with a coding pattern, comprising symbols having at least two different values ​​and each comprising at least one marking and a raster point, which is part of a raster extending over the surface. . Background of the invention

In many contexts, it is desirable to be able to determine an absolute position on a surface. An example is when digitizing drawings. Another is when you want to provide an electronic version of handwritten information.

US 5,852,434 describes a device for determining an absolute position. The device comprises a writing surface provided with a position coding pattern by means of which XY coordinates can be determined, a detector which can detect the position coding pattern and a processor which on the basis of the detected position coding pattern can determine the position of the detector in relation to the writing surface. The device enables a user to enter handwritten and hand-drawn information into a computer at the same time as the information is written / drawn on the writing surface.

Three examples of position coding are given in US 5,852,434. The first example is symbols, each of which is made up of three concentric circles. The outermost circle represents the X coordinate and the middle Y coordinate. The two outermost circles are further divided into 16 parts which, depending on whether they are filled or not, indicate

517 445 different numbers. This means that each coordinate pair X, Y is coded with a complex symbol with a special appearance.

In the second example, the coordinates at each point on the writing surface are indicated by means of a bar code, a bar code for the X coordinate being indicated above a bar code for the Y coordinate.

As a third example, it is stated that a checkerboard pattern can be used to encode the X and Y coordinates. However, there is no explanation for how the checkerboard10 pattern is structured or how it can be translated into coordinates.

A problem with the known pattern is that it is made up of complex symbols and the smaller these symbols are made the more difficult it becomes to produce the patterned writing surface and the greater the risk of incorrect position determinations, but the larger the symbols are made the worse the position resolution.

A further problem is that the processor's processing of the detected position coding pattern becomes rather complicated due to the fact that it is complex symbols that are to be interpreted.

Another problem is that the detector must be designed so that it can register four symbols at the same time so that it can safely include at least one symbol in its entirety, which is required for the position determination to be carried out.

The applicant's Swedish patent application SE 9901954-9, which was filed on 28 May 1999 and which was not public at the time of filing the present application and thus does not belong to the state of the art, describes a position coding pattern which largely alleviates the above problems.

517 445

Summary of the invention

An object of the present invention is to completely or partially remedy the above-mentioned problems of the prior art.

This object is achieved with a product according to claim 1. Preferred embodiments are stated in the subclaims.

More particularly, the invention relates to a product having a surface provided with a coding pattern, which comprises symbols, each representing at least two different values ​​and each comprising at least one marking and a raster point, which is part of a raster which extends over the surface. The invention is characterized in that the value of each symbol is indicated by the position of said marking in relation to a raster point.

In the prior art, each position is coded with a complex symbol which requires recognition of many different elements and which therefore becomes sensitive to disturbance. According to the invention, a symbol is used instead, the value of which is indicated by the position of a mark in relation to a raster point. So there is a type of symbol for each value. Thus, a device which is to perform the position determination need only be able to detect the presence of a mark and it need not be able to distinguish between different elements, such as the different bars in a bar code, in order to be able to determine the position. This makes detection easier and less sensitive to noise.

The design of the symbol according to the invention further means that a surface which is provided with a coding pattern according to the invention becomes more aesthetically pleasing.

Furthermore, in relation to the information density, a large distance between the markings is made possible, which makes the coding less sensitive to motion blur.

517 445

In the position coding pattern in the above-mentioned SE 9901954-9, points of different sizes are used to graphically represent the position coding. The symbols of the present invention can be advantageously used instead of the dots in the position coding pattern.

The markings may have different appearances, but in a preferred embodiment essentially all markings are identical, whereby the coding pattern becomes easier to detect and easier to apply to a surface.

The symbols described above can be used to encode any type of information, but are advantageously used to encode positions. In the prior art, each position is mentioned as mentioned with a single symbol which must therefore be rather complex. According to the invention, each position can instead be coded with a plurality of symbols. Thus, each individual symbol can be made less complex and thus easier to detect with greater certainty.

In the prior art, each position is further coded with a symbol which is isolated from the symbols of surrounding positions. Thus, the position resolution is limited by the area occupied by the symbol for a position. The position coding pattern according to the invention can be constructed in a corresponding manner, each position being coded by an isolated group of symbols. However, in a preferred embodiment of the invention, each symbol contributes to the coding of more than one position. In this way, a fluid transition is created between different positions. Described differently, each position is partially encoded by the same symbols as the adjacent positions. The liquid coding is advantageous because it makes it possible to increase the position resolution. Furthermore, the ratio may decrease between, on the one hand, the number of symbols that a position determining device must register in order to be able to perform a position determination safely and, on the other hand, the number of symbols encoding a position.

In a preferred embodiment, each symbol contributes to the coding of both a first and a second position coordinate. There is thus no need for different symbols for the different coordinates, which makes the position code easier and the position resolution better. The coordinate system can suitably be Cartesian, but other types of coordinate systems are also conceivable.

Furthermore, the value of each symbol may advantageously be translatable to at least a first digit used for coding the first coordinate and at least a second digit used for coding the second coordinate, the symbols in the position coding pattern together representing a first position code for the first coordinate and a second position code for the second coordinate. The two coordinates can then be coded independently of each other, which makes the coding easier when the coding is fluid. Preferably, the value of the symbol is represented binary, a first bit being used for the coding of a first coordinate and a second bit for the coding of a second coordinate.

The position coding pattern is advantageously based on a first cyclic, preferably binary, series of numbers which has the property that no sequence with a first predetermined number of digits occurs more than once in the series of numbers.

By building the position coding pattern in this way, it will contain inherent information about the positions so that the coordinates can be calculated with predetermined rules. This is advantageous because it means that the decoding of the position coding pattern can be implemented in an efficient manner in, for example, soft goods. In addition, it becomes much easier to produce the position coding pattern in this way compared to if one were to randomly try to generate a unique position coding pattern of the liquid type.

In an advantageous embodiment, the product may comprise a plurality of writing surfaces, each of which comprises the position coding pattern. The product can, for example, consist of a notepad with several leaves. The position coding patterns then differ for the different writing surfaces by the sequence in the cyclic speech series that a predetermined column or row begins with. The same pattern can thus be used for several writing surfaces, which can be separated or integrated with each other, by letting, for example, the first column start in different positions in the number series.

The position coding pattern can be realized with any parameter that can be used to provide symbols of the above type that can be detected by a detector. The parameter can be electrical or chemical or of another type. However, the position coding pattern is preferably optically readable because then it becomes easier to apply to the surface. The pattern must therefore be able to reflect light, but the light does not have to be in the visible area.

The grid and / or the grid points can be realized on the surface. However, in a preferred embodiment, the raster and raster points are virtual. The raster is thus not marked on the surface at all, but only constitutes an imaginary raster which forms the basis for the coding, but which can be located on the basis of the locations of the markings.

The idea described above to translate the value of a symbol into a first digit for encoding the first coordinate and a second digit in the value of each symbol for

517 445 coding of the second coordinate can of course be used regardless of the exact design of the symbols.

The product described above can be any product having a surface with a coding pattern. It can be used for a variety of applications. It can be used, for example, to continuously register the position of a pen that is moved over the writing surface. It can further be used in determining the position of a tool, an instrument or the like. It can also be used as a mouse pad. Those skilled in the art can devise many other applications.

Short figure description

In the following, the invention will be described in more detail by means of an exemplary embodiment with reference to the accompanying drawings, in which

Fig. 1 schematically shows an embodiment of a product provided with a position coding pattern;

Fig. 2 schematically shows how the symbols can be designed in an embodiment of the invention.

Fig. 3 schematically shows an example of 4x4 symbols used to encode a position.

Fig. 4 schematically shows a device that can be used for position determination.

Description of a preferred embodiment

Fig. 1 shows a part of a product in the form of a paper 1, which on its surface 2 is provided with an optically readable position coding pattern 3 which enables position determination. The position coding pattern consists of symbols 4, which are systematically arranged over the surface 2, so that it has a patterned appearance. The paper has an x-coordinate axis and a y-coordinate axis. In this case, position determination can be performed on the entire surface of the product. In other cases, the surface that allows position determination may be

517 445 a minor part of the product. The paper can, for example, be used to provide an electronic representation of information written or drawn on the surface. The electronic representation can be achieved by continuously while writing on the surface with a pen, determining the position of the pen on the paper by reading the position coding pattern.

The position coding pattern comprises a virtual raster, which is thus neither visible to the human eye nor can be detected directly by a device which is to determine positions on the surface, and a plurality of symbols 4, each of which can assume one of four values ​​as described below. In this context, it should be pointed out that the position coding pattern in Fig. 1 is greatly enlarged for the sake of clarity. In addition, it appears on only part of the paper.

The position coding pattern is arranged so that the position of a partial surface on the writing surface is coded by the symbols on this partial surface. A first and a second sub-surface 5a, 5b are shown in broken lines in Fig. 1. The part of the position coding pattern (here 3x3 symbols) which is on the first sub-surface 5a encodes a first position, and the part of the position coding pattern which is on the second sub-surface 5b encodes a second position. The position coding pattern is thus partly common to the adjacent first and second positions. Such a position coding pattern is referred to in this application as floating.

Figures 2a-d show an embodiment of a symbol which can be used in the position coding pattern according to the invention. The symbol comprises a virtual raster point 6, which is represented by the intersection point between the raster lines, and a mark 7 which has the shape of a point. The value of the symbol depends on where the marking is located. In the example i

517 445 Fig. 2 there are four possible locations, one on each of the raster lines starting from the raster points. The offset from the raster point is the same for all values. In the following, the symbol in Fig. 2a has the value 1, in Fig. 2b the value 2, in Fig. 2c the value 3 and in Fig. 2d the value 4. In other words, there are four different types of symbols.

Each symbol can thus represent four values ​​1-4. This means that the position coding pattern can be divided into a first position code for the x-coordinate, and a second position code for the y-coordinate. The division is made as follows:

<td>Symbol value</td><td>x-code</td><td>y-code</td>

<td> 1</td><td> 1</td><td> 1</td>

<td> 2</td><td> 0</td><td> 1</td>

<td> 3</td><td> 1</td><td> 0</td>

<td> 4</td><td> 0</td><td> 0</td>

The value of each symbol is thus translated into a first digit, this bit, for the x-code and a second digit, this bit, for the y-code. In this way you get two completely independent bit patterns. The patterns can be combined into a common pattern, which is coded graphically by means of a plurality of symbols according to Fig. 2.

Each position is coded using a plurality of symbols. In this example, 4x4 symbols are used to encode a position in two dimensions, ie an x-coordinate and a y-coordinate.

The position code is built up using a series of numbers of ones and zeros, which has the property that no sequence of four pieces occurs more than once in the series. The speech series is cyclical, which means that the property also applies when connecting the end of the series with its beginning. One

517 445 four-bit sequence thus always has a uniquely determined position in the speech series.

The series can be a maximum of 16 bits long if it is to have the above-described property of four-bit sequences. In this example, however, only a seven bit long series is used as follows:

0001010.

This series contains seven unique four-bit sequences that encode a position in the series as follows:

<td>Position in the series</td><td>Sequence</td>

<td> 0</td><td> 0001</td>

<td> 1</td><td> 0010</td>

<td> 2</td><td> 0101</td>

<td> 3</td><td> 1010</td>

<td> 4</td><td> 0100</td>

<td> 5</td><td> 1000</td>

<td> 6</td><td> 0000</td>

To encode the x-coordinates, the number series is written sequentially in columns over the entire area to be encoded. The coding is based on the difference or position15 offset between numbers in adjacent columns. The size of the difference is determined by in which position (ie with which sequence) in the number series the column is allowed to begin. More specifically, if you take the difference modulo seven between, on the one hand, a number, which is coded by a four-bit sequence in a first column and which can therefore have the value (position)

0-6, and on the other hand the corresponding number (ie the sequence at the same height) in an adjacent column, the result will be the same regardless of where along the two columns one makes the comparison. Using the difference between the two

517 445 columns, you can thus encode an x-coordinate that is constant for all y-coordinates.

Since each position on the surface is coded with 4x4 symbols in this example, you have access to three differences (with the value 0-6) as above to code the x-coordinates. The coding is then done in such a way that of the three differences, one will always have the value 1 or 2 and the other two will have values ​​in the interval 3-6. No differences must therefore be zero in the x-code. In other words, the x-code is constructed so that the differences are as follows: (3-6) (3-6) (1-2) (3-6) (3-6) (1-2) (3-6) ( 3-6) (1-2) ...

Each x-coordinate is thus coded with two numbers between 3 and 6 and a subsequent number that is 1 or 2. If you subtract three from the high numbers and one from the low, you get a number in mixed base, which directly gives a position in the x-direction, from which the x-coordinate can then be determined directly, as shown in the example below.

Using the principle described above, one can thus code x-coordinates 0,1,2 ..., with the help of numbers that represent three differences. These differences are coded with a bit pattern based on the speech series above. The bit pattern can finally be coded graphically using the symbols in Fig. 2.

In many cases, when loading 4x4 symbols, you will not get a complete number that encodes the x-coordinates, but parts of two numbers. However, since the least significant part of the numbers is always 1 or 2, a complete number can be easily reconstructed.

The y-coordinates are coded according to the same principle used for the x-coordinates. The cyclic speech series is repeatedly written in horizontal lines across the surface to be position coded. Just as for the x-coordinates, you let the lines start in different positions, ie with different sequences, in the number series. For the y-coordinates, however, you use

517 445 does not differentiate but encodes the coordinates with numbers based on the starting position of the number series on each line. Once you have determined the x-coordinate for 4x4 symbols, you can namely determine the starting positions in the series of numbers for the lines that are included in the y-code in the 4x4 symbols. In the y-code, the most significant number is determined by letting it be the only one that has a value in a particular range. In this example, a row of four is allowed to begin at position 0-1 in the series of numbers, to indicate that this row refers to the least significant number in a y-coordinate, and the other three begin at position 2-6. In the y-direction there is thus a series of numbers as follows:

(2-6) (2-6) (2-6) (0-1) (2-6) (2-6) (2-6) (0-1) (2-6) ... Every y -coordinate is thus coded with three numbers between 2 and 6 and a subsequent number between 0 and 1.

If you subtract 1 from the low number and 2 from the high ones, you get in the same way as for the x-direction a position in the y-direction in a mixed base from which you can directly determine the y-coordinate.

With the method above you can code 4x4x2 = 32 positions in x-direction. Each such position corresponds to three differences, giving 3 x 32 = 96 positions. Furthermore, you can code 5 x 5 x 5 x 2 = 250 positions in y-direction. Each such position corresponds to 4 rows, giving 4 x 250 = 1000 positions. In total, 96000 positions can be coded. However, since the x-coding is based on differences, you can choose in which position the first series of numbers begins. If you take into account that this first series of numbers can start in seven different positions, you can code 7 x 96000 = 672000 positions. The starting position of the first series of numbers in the first column can be calculated when the x-coordinate has been determined. The above seven different

517 The 445 starting positions for the first series can encode different sheets or writing surfaces on a product.

To further illustrate the invention according to this embodiment, here follows a specific example which is based on the described embodiment of the position code.

Fig. 3 shows an example of an image with 4x4 symbols read by a position determining device.

These 4x4 symbols have the following values:

4 4 2

2 3 4

4 2 4

2 4

These values ​​represent the following binary x and y codes:

x-code:

0 0 0

10

0 0 0

110 0 y-code:

0 0 1

10 0

0 10

10

The vertical x-sequences encode the following positions in the number series: 2046. The differences between the columns become -242, which modulo 7 gives: 542, which in mixed base encodes position (5-3) x 8 + (4-3) x 2 + ( 2-1) = 16 + 2 + 1 = 19. Since the first coded x-position is position 0, the difference which lies in the interval 1-2 and which is seen in the 4x4 symbols is the twentieth such difference. Furthermore, since there are a total of three columns on each such difference and there is a starting column, the vertical sequence at the far right of the 4x4517 445 x code belongs to the 61st column of the x code (3 x 20 + 1 = 61) and the far left on the 58th.

The horizontal y-sequences encode the positions 0 4 1 3 in the speech series. Since these series begin in the 58th column, the starting position of the rows is these numbers minus 57 modulo7, giving the starting positions 6302. Translated to numbers in the mixed base, this becomes 6-2,

3-2, 0-0, 2-2 = 4 1 0 0, where the third digit is the least significant digit in the current number. The fourth digit is then the most significant digit in the next number. In this case, it must be the same as in the current number. (The exceptional case is when the current number consists of the highest possible numbers in all positions. Then you know that the beginning of the next number is greater than the beginning of the current number.)

The position for the four-digit number in the mixed base is 0x50 + 4x10 + 1x2 + Oxl = 42.

The third row in the y-code is thus the 43rd which has a starting position 0 or 1, and since there are four rows in total on each such row, the third row is number 43x4 = 172.

In this example, the position of the upper left corner of the 4x4 symbol group is (58,170).

Since the x-sequences in the 4x4 group start on row 170, the entire x-columns of the pattern start in the position series positions ((2046) -169) mode 7 = 1635. Between the last starting position (5) and the first starting position, the numbers 0-19 are coded in the mixed base, and by summing the representations of the numbers 0-19 in the mixed base, you get the total difference between these columns. A naive algorithm for doing this is to generate these twenty numbers and directly sum up their numbers. The er517 445 held sum cold s. The sheet or writing surface is then given by (5-s) modulo7.

In the example above, an embodiment has been described where each position is coded with 4x4 symbols and a series of numbers with 7 bits is used. This is of course just an example. Positions can be coded with more or fewer symbols. There does not have to be as many in both drawings. The speech series can have different lengths and does not have to be binary, but can be based on a different base. Different speech series can be used for coding in the x-direction and coding in the y-direction. The symbols may have different numbers of values.

In the example above, the selection is also a point. Of course, it can have a different look. It can, for example, consist of a line starting at the virtual raster point and extending from it to a specific position.

In the example above, the symbols within a square sub-area are used to encode a position. The sub-surface can have another shape, for example hexagonal. The symbols also do not have to be arranged in rows and columns at a 90 degree angle to each other but can also be arranged in other arrangements.

In order for the position code to be detected, the virtual grid needs to be determined. This can be done by studying the distance between different markings. The shortest distance between two markings must be derived from two adjacent symbols with the value 1 and 3 so that the markings are on the same grid line between two grid points. Once such a pair of markings has been detected, the associated grid points can be determined with knowledge of the distance between the grid points and the displacement of the markings from the grid points. Once two raster points have been located, additional raster points can be determined by means of measured distances to other markings and with knowledge of the mutual distances of the raster points.

An embodiment of a position determining device is shown schematically in Fig. 4. It comprises a housing 11, which is shaped approximately like a pencil. In the short end of the housing there is an opening 12. The short end is intended to abut or be kept at a small distance from the surface on which the position determination is to take place.

The housing essentially houses an optics part, an electronics part and a power supply.

The optical part comprises at least one LED 13 for illuminating the surface to be imaged and a light-sensitive area sensor 14, for example a CCD or CMOS sensor, for detecting a two-dimensional image. Optionally, the device may also contain a lens system.

The power supply to the device is obtained from a battery 15 which is mounted in a separate compartment in the housing.

The electronic part contains image processing means 16 for determining a position on the basis of the image registered with the sensor 14 and more particularly a processor unit with a processor which is programmed to read images from the sensor and perform position determination on the basis of these images.

The device also comprises in this embodiment a pen tip 17, with the aid of which one can write ordinary dye-based writing on the surface on which the position determination is to take place. The pen tip 17 can be folded in and out so that the user can control whether it is to be used or not. In some applications, the device need not have a pen tip at all.

517 445

The device further comprises buttons 18 by means of which the device is activated and controlled. It also has a transceiver 19 for wireless transmission, for example with IR light or radio waves, of information to and from the device. The device may further comprise a display 20 for displaying positions or registered information.

The applicant's Swedish patent no. 9604008-4 describes a device for registering text. This device can be used for position determination if it is programmed appropriately. If it is to be used for dye-based writing, it must also be supplemented with a pencil tip.

The device may be divided into different physical envelopes, a first envelope containing components necessary to take pictures of the position coding pattern and to transmit these to components present in a second envelope and which perform the position determination on the basis of the recorded image or images.

The position determination is made as mentioned by a processor which must therefore have software for locating and decoding the symbols in an image and for determining positions from the codes thus obtained. Those skilled in the art can, based on the example above, design software that performs position determination based on the image of a part of a position coding pattern.

Furthermore, the person skilled in the art can, on the basis of the description above, design software for printing the position coding pattern.

In the embodiment above, the pattern is optically readable and the sensor is thus optical. As mentioned, the pattern may be based on a parameter other than an optical parameter. In such a case, of course, the sensor must be of a type that can read the current parameter.

517 445

In the exemplary embodiment above, the grid is a grid. It can also have other forms.

In the embodiment above, the longest possible cyclic speech series is not used. This provides a certain redundancy that can be used, for example, to control the rotation of the loaded group of symbols.

in? G; '' Vat \ CH \, ViS \ .L.999_;2S9if? F. Sti ΪΡ! pPsmsd 2 3999P9-3P 1139 doc