BACKGROUND TO THE INVENTION It is known to use products, such as documents, having such position identification markings in combination with a pen having an imaging system, such as an infra red camera, within it, which is arranged to image a small area of the product close to the pen nib. The pen includes a processor having image processing capabilities and a memory and is triggered by a force sensor in the nib to record images from the camera as the pen is moved across the document. From these images the pen can determine the position of any marks made on the document by the pen. The pen markings can be stored directly as graphic images, which can then be stored and displayed in combination with other markings on the document. In some applications the simple recognition that a mark has been made by the pen on a predefined area of the document can be recorded, and this information used in any suitable way. This allows, for example, forms with check boxes on to be provided and the marking of the check boxes with the pen detected. In further applications the pen markings are analysed using character recognition tools and stored digitally as text. Systems using this technology are available from Anoto AB and described on their website www. Anoto. com.

HP Ref. 200208368 2 Attorney Ref : ASW1581 In order to allow documents to be produced easily with the position identifying pattern on them, it is desirable for the pattern to be suitable for printing on the type of printer that is readily available to a large number of users, such as an ink jet or laser jet printer. These typically have a resolution of 300,600 or 1200 dots per inch, and the accuracy with which each dot can be located is variable. It is therefore desirable to provide a position identifying pattern which will be easy for the pen or other imaging system to read and which does not rely on very accurate printing.

SUMMARY OF THE INVENTION The present invention provides a product having a position identifying pattern thereon, the pattern defining a number of mark positions and a grid of intersecting lines having intersections each formed by the intersection of at least two lines, wherein each intersection has a plurality of marks associated with it each of which is on at least one of the intersecting lines.

Where the grid is a square grid, each intersection will be formed where two lines cross each other at right angles. Where the grid is a triangular grid, each intersection will be formed where three lines cross each other, each being at an angle of 60° to the other two. In a hexagonal grid each intersection is formed by three lines extending outwards from the intersection, each one being at an angle of 120° to the other two.

Each mark position may have a marking state, which is one of at least two possible marking states, whereby the marking state of the mark positions is used to identify position on the document. The marking state can be either the presence or absence of a mark in the mark position, or it may be defined as a feature of the mark at that position, for example its size or shape.

HP Ref : 200208368 Attorney Ref: ASW1581 Where features other than the presence or absence of a mark are used, each mark position can have more than two possible marking states.

One of the mark positions at each intersection may be at the point of intersection of the two intersecting lines. This helps the pen or other reading device to identify the grid and therefore to read the pattern.

Some of the marks may be arranged to represent positional data and some of the marks may be orientation marks arranged to indicate the orientation of the product. The use of particular marks to indicate orientation can also help the pen to read the pattern easily.

Indeed the present invention further provides a product having a position identifying pattern thereon, the pattern defining a number of mark positions and a grid of intersecting lines having intersections each formed by the intersection of two lines, wherein some of the marks are arranged to represent positional data and some of the marks are orientation marks arranged to indicate the orientation of the product.

The present invention further provides a position determining system arranged to sense position identifying marks on a product, the system comprising sensing means arranged to sense the position of marks on an area of the product, and processing means arranged to analyse the positions of the marks within said area and define from them a grid comprising lines and intersections where the lines intersect, to define a plurality of mark positions associated with each intersection each of the mark positions being on at least one of the intersecting lines, and each intersection having a plurality of marks in respective mark positions associated with it, and to determine from the sensing means a marking state of each of the mark positions thereby to determine the position of the area on the product.

A corresponding method of sensing position identifying marks on a product is also provided.

The present invention still further provides a position determining system arranged to sense position identifying marks on a product, the system comprising sensing means arranged to sense the position of marks on an area of the product, and processing means arranged to analyse the positions of the marks within said area and define from them a grid comprising lines and intersections where the lines intersect, to define a plurality of mark positions associated with each intersection, and to identify some of the mark positions as orientation mark positions, and to determine from marks in those positions the orientation of the product relative to the sensing means.

A corresponding method of sensing a position identifying pattern on a product is also provided.

The present invention further provides corresponding systems and methods for applying a position identifying pattern to a product, and a data carrier carrying data arranged to control relevant systems to operate as a system according to the invention and to perform the methods of the invention.

The data carrier can comprise, for example, a floppy disk, a CDROM, a DVD ROM/RAM (including +RW,-RW), a hard drive, a non-volatile memory, any form of magneto optical disk, a wire, a transmitted signal (which may comprise an internet download, an ftp transfer, or the like), or any other form of computer readable medium.

HP Ref : 5 Attorney Ref: ASW1581 Preferred embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 shows a document according to an embodiment of the invention and a digital pen according to an embodiment of the invention ; Figure 2 shows a part of a position identifying pattern on the document of Figure 1; Figure 3 shows a larger part of a position identifying pattern on the document of Figure 1; Figures 4 and 5 show images of the pattern of Figure 3 as reconstructed by the pen of Figure 1; Figures 6 shows an image of the pattern of Figure 3 as viewed by the pen of Figure 1; Figure 7 shows the construction of grid lines from the image of Figure 6; Figure 8 shows a position identifying pattern according to a second embodiment of the invention ; Figures 9 and 10 shows a system for producing the document of Figure 1; and Figure 11 shows a position identifying pattern according to a third embodiment of the invention.

DESCRIPTION OF THE PREFERRED EMBODIMENTS Referring to Figure 1, a document 2 according to an embodiment of the invention for use in a digital pen and paper system comprises a carrier 3 in the form of a single sheet of paper 4 with position identifying markings 5 printed on some parts of it. The markings 5, which are not shown to scale in Figure 1, form a position identifying pattern 6 on the document 2. Also printed on the paper 4 are further markings 7 which are clearly visible to a human user of the form, and which make up the content of the document 2.

The pen 8 comprises a writing nib 10, and a camera 12 made up of an infra red (IR) LED 14 and an IR sensor 16. The camera 12 is arranged to image a circular area adjacent to the tip 11 of the pen nib 10. A processor 18 processes images from the camera 12 taken at a predetermined rapid sample rate. A pressure sensor 20 detects when the nib 10 is in contact with the document 2 and triggers operation of the camera 12. Whenever the pen is being used on an area of the document 2 having the pattern 6 on it, the processor 18 can determine from the pattern 6 the position of the nib 10 of the pen whenever it is in contact with the document 2. From this it can determine the position and shape of any marks made on the patterned areas of the document 2. This information is stored in a memory 22 in the pen as it is being used. When the user has finished marking the document 2, this is recorded in a document completion process, for example by making a mark with the pen 8 in a send box 9. The pen is arranged to recognise the pattern in the send box 9 and send the pen stoke data to a pen stroke interpretation system in a suitable manner, for example via a radio transceiver 24 which provides a Bluetooth radio link with an internet connected PC. Suitable pens are available from Logitech under the trade mark Logitech Io.

Referring to Figures 2 and 3, in a first embodiment of the invention the position identifying pattern 6 is made up of a number of dots 30 arranged

HP Ref : 200208368 7 Attorney Ref: ASW1581 on an imaginary grid 32. The grid 32 can be considered as being made up of horizontal and vertical lines 34,36 defining a number of intersections 40 where they cross. The intersections 40 are of the order of 1. 0mm apart, and the dots are of the order of 100? m across. Each intersection 40 has nine dot positions 42 associated with it in the form of a cross with all of the dot positions 42 being on the horizontal and vertical lines 34,36. Each dot position 42 is only associated with one of the intersections 40. Specifically, as can best be seen in Figure 2, there is one dot position 42a on the intersection 40, which is therefore on both the horizontal and vertical lines 34,36, that meet at the intersection 40, and four further dot positions 42b, 42c, 42d, 42e, 42f, 42g, 42h, 42i, on each of the horizontal and vertical lines 34,36, two on either side of the intersection 40. As can best be seen in Figure 3, the nine dot positions at each intersection are equally spaced from each other, but there is a larger gap 44 between the dot positions 42 of one intersection and those at the adjacent intersections.

Each dot position 42 can either have a dot 30 present in it, or no dot in it.

Each dot position is therefore equivalent to a binary digit having two possible marking statuses, those being the presence or absence of a dot. In the group of nine dot positions 42 shown in Figure 2, six of the positions 42a, 42b, 42c, 42g, 42h and 42i have dots 30 present in them, and the other three 42d, 42c, 42f have no dot. The combination of dots 30 present at the intersections changes in a predetermined manner across the document so that, for any group of a sufficient number of intersections 40, the position on the document is uniquely identified.

Referring to Figure 4, when the pen 8 is held with its nib 10 in contact with the document 2, the camera 12 can view an area 50 of the document. This area is large enough to ensure that there will always be one group of four intersections 40a, 40b, 40c, 40d, in a two by two block, for which all of the

HP Ref : 200208368 g Attorney Ref: ASW1581 dot positions 42 are within the area. The processor 18 is therefore arranged to analyse each recorded image from the camera 12 to identify such a block of four intersections, identify each of the nine dot positions 42 at each of the intersections, determine whether or not there is a dot 30 in each of the dot positions 42, and determine from the presence and absence of dots 30 the position and orientation of the viewed area 50 on the document. From this information the position of the pen nib 10 on the document 2 can also be determined.

Referring to Figure 5, the processor 18 allocates a binary positional code to each of the four intersections 40a, 40b, 40c, 40d which is made up of Is and Os depending on the presence or absence of a dot 30 in each of the dot positions 42 taken in a predetermined order. To determine the order the processor 18 first determines which of the grid lines 34,36 is closest to a vertical direction defined in relation to the pen 8, which corresponds to the vertical direction as shown in Figure 5, and for that grid line defines a top and a bottom direction and a left and right direction. The dot positions 42 for the intersection 40a are then allocated an order, which in this case, referring back to Figure 2, is 42b, 42c, 42d, 42e, 42a, 42f, 42g, 42h, 42i.

For the dot pattern at the intersection 40a this gives a position code of (1,1, 1,1, 0,0, 1,0, 1). This process is then repeated for the other three intersections 40b, 40c, 40d in the group which have position codes (1, 0, 1, 1, 1, 0, 1, 1, 1), (0, 0,1, 1,1, 1,1, 0,1), and (1,1, 1,0, 1,0, 1,1, 0) respectively.

These four position codes are then combined to give the full grid reference (1,1, 1,1, 0,0, 1,0, 1,1, 0,1, 1,1, 0,1, 1,1, 0,0, 1,1, 1,1, 1,0, 1,1, 1,1, 0,1, 0,1, 1,0) for the group of four intersections 40a, 40b, 40c, 40d.

It will be appreciated that, for any position on the document 2, the full grid reference for a group of four intersections can have one of four values depending on the orientation of the pen relative to the document 2.

Provided the total pattern space from which the pattern 6 is taken is small enough, each of the four orientations gives a unique grid reference, and the processor 18 can therefore determine both the position and the orientation of the pattern 6 relative to the pen 8.

Referring to Figures 6 and 7, during normal use it is usual for the pen 8 to be held at such an angle that the view of the camera 12 is not directly orthogonal to the plane of the document 2. This results in the image of the pattern 6 in the viewed area 50 being as shown in Figure 6, with the grid lines 34,36 appearing to be not perpendicular, and the spacing of the dot positions 42 being spaced at different intervals along the'vertical'and 'horizontal'grid lines 34,36. However, because all of the dot positions 42 are on the grid lines 34,36, it is still relatively easy for the processor 18 to identify from the pattern 6 the positions of the vertical and horizontal grid lines 34,36 and the intersections 40 as shown in Figure 7. This allows the processor 18 to perform perspective correction on the viewed pattern 6 so that it can be analysed in the manner described above with reference to Figures 5 and 6.

Referring to Figure 8, in a second embodiment of the invention, the pattern 106 is again made up of a number of dots 130 defining horizontal and vertical lines 134,136 of a grid, with intersections 140 where the lines intersect. There are again nine dot positions 142 associated with each intersection 140 in the same pattern as in the first embodiment described above. However the dot positions 142a which are at the intersections are reserved for indicating the orientation of the pattern, and the remaining eight dot positions 142b, 142c, 142d, 142e, 142f, 142g, 142h, 142i are used for position coding. The intersections 140 are grouped into groups of nine intersections in a three by three block. Of the nine orientation dot positions 142a in each block, a first group 150,152, 154 are marked with dots and a

HP Ref : 20020836S 1O Attorney Ref: ASW1581 second group 156, 158, 160,162, 164,166 are left unmarked. The first group comprises one dot position 150 at one corner of the group, and the two dot positions 152, 154 adjacent to that corner on the horizontal and vertical grid lines 134,136 respectively. The first group of dot positions 150,152, 154 therefore defines a right angled triangle which has no rotational symmetry and therefore uniquely defines the orientation of the pattern 106 relative to the pen 8 which reads it.

The grid spacing in this pattern 106 is 0.5mm and any area viewed by the pen, will include at least one complete group of 9 orientation dot positions 150,152, 154,156, 158,160, 162,164, 166. This enables the processor 18 in the pen to determine the orientation of the pattern 106 relative to the pen 8.

Referring to Figures 9, a very simple system for producing printed documents having the position identifying pattern on them comprises a personal computer (PC) 200 and a printer 202. The PC 200 has a screen 204, a keyboard 206 and a mouse 208 connected to it to provide a user interface 209 as shown generally in Figure 10. As also shown in Figure 10, the PC 200 comprises a processor 210 and a pattern allocation module 212 which is a software module stored in memory. The pattern allocation module 212 includes a definition of a total area of pattern space and a record of which parts of that total area have been allocated to specific documents, for example by means of coordinate references. The PC 200 further comprises a printer driver 214, which is a further software module, and a memory 216 having electronic documents 218 stored in it. The user interface 209 allows a user to interact with the PC 200.

In order to produce the printed document 2 the processor 210 retrieves an electronic document 218 from the memory 216 and sends it to the printer

HP Ref : 200208368 Attorney Ref: ASW1581 driver. The electronic document 218 contains a definition of the content 7, and the areas of the document 2 which are to have the pattern 6 printed on it. The printer driver 214 requests the required amount of pattern from the pattern allocation module 212 which allocates by means of coordinate references an area of the pattern space to the document, generates the pattern 6 for that area using a pattern generation algorithm, and communicates the details of the pattern including the positions of all the required dots, back to the printer driver 214. The printer driver 214 then combines the content 7 and the pattern 6 into a single file which contains an image including the pattern and the content, converts the content 7 and the pattern 6 to a format suitable for the printer 202, and sends it to the printer which prints the content 7 and the pattern 6 simultaneously as a single image.

In practice the various components of the system can be spread out over a local network or the internet. For example the pattern allocation module 212 can be provided on a separate internet connected server so that it can be accessed by a number of users.

For the pattern of Figures 2 to 5, relatively low resolution printer can be used, such as a 300 dpi (dots per inch) ink jet or laser jet printer. For the pattern of Figure 8, a higher resolution printer, of at least 600 dpi is needed.

Referring to Figure 11, in a third embodiment of the invention the position identifying pattern is again made up of a number of dots 330 which define a grid of horizontal and vertical lines 334,336. In this case at each intersection 340 there is a group of five dots positions, one on the intersection 340, and one on either side of it along both the horizontal and vertical lines 334,336. Each of the dot positions is marked with either a

small dot 330a or a large dot 330b. Each dot 330 therefore represents a binary digit which can be a'1'or a'0'depending on the size of the dot 330.

In a modification to the pattern of Figure 11, each dot position may have one of three possible marking states : a small dot, a large dot, or no dot.

This increases the number of possible combinations of dot patterns at each intersection and therefore increases the total available pattern space.

It will be appreciated that there are a large number of possible variations on the position identifying pattern which still fall within the scope of the present invention. For example, the number of dot positions associated with each grid intersection can vary. Also the use of specific orientation dots can be incorporated into the pattern of Figures 2 and 3 or the pattern of Figure 11. In any case the dot positions chosen for the orientation pattern could be any suitable group of dots which has no rotational symmetry. Alternatively the orientation pattern could have some rotational symmetry, but less that the grid itself. For example with the square grid patterns described above the grid has four-fold rotational symmetry in that it appears the same in any of four rotational positions. In this case the orientation pattern could have two-fold rotational symmetry, appearing the same in only two orientations.

For example the rotational pattern could consist of two dots aligned with the vertical, or the horizontal, lines.

It will also be appreciated that the pattern may also include dots or other marks which are not located on the grid lines. For example in the embodiment of Figure 8, the orientation could be indicated by a single dot offset diagonally from the intersection, i. e. in a direction at 45° to the horizontal and vertical lines 134,136. Similarly placed dots could also be used as part of the main position identifying part of the pattern, as could

dots in other positions off the grid lines. In either case, when the reading device has identified the grid it can essentially identify mark positions anywhere, either on the grid or off the grid between the grid lines. It can then use the marking state of each of the mark positions in a viewed area of pattern to determine the position within the defined pattern space of the viewed area as described above. However, it will be understood that the higher the proportion of dots that are on the grid lines, the easier it is for the reading device to identify the grid lines and to read the pattern correctly.

Furthermore, while the embodiments described above are each formed on a square grid, similar patterns can be designed based on other grid shapes, such as a triangular grid or a hexagonal grid.