AU2005209709A1 - Two dimensionally phase modulated information symbol - Google Patents

Description

S&F Ref: 730231

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha, of 30-2, Shimomaruko 3-chome, Ohta-ku, Tokyo, 146, Japan Stephen Edward Ecob Spruson Ferguson St Martins Tower Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Two dimensionally phase modulated information symbol The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5845c

/V

j -1- 4 TWO DIMENSIONALLY PHASE MODULATED INFORMATION SYMBOL Field of the Invention The current invention relates to computer readable marks on printed pages and, in S particular, to computer readable marks with a high data density and with low visibility to the human eye.

Background IComputer readable marks on printed pages are commonplace, with many varieties such as the common bar code in extremely widespread use. Although the common barcode is ubiquitous, an increasing number of alternative computer readable marks are reaching the 0 marketplace. Many of these new varieties of mark provide much greater data carrying capacity than the common barcode, enabling a wider range of applications than is possible with the limiting 30 to 60 bits of data that can be stored in a common barcode. Other varieties of mark improve on the common barcode by exhibiting reduced visibility, which has the advantage that a larger portion of the page is left free to contain human readable content. An additional advantage of low visibility marks is that information can be hidden in a page, enabling applications such as steganography and watermarking.

As wider use is made of computer readable marks, and new applications for computer readable marks are found, there is an increasing need for marks that provide a high data content without consuming large areas of the page. Such marks leave most of the page free to contain human readable content, which is desirable for many applications. It is also desirable that marks be robust to the types of rough treatment that printed pages commonly receive, such as folding, wrinkling, staining and tearing.

730231 _final.doc j -2- While marks with high data density are available, and other marks with low visibility S are available, there remains a need for marks that simultaneously provide high data density, low visibility and high robustness.

Summary of the Invention In accordance with one aspect of the present invention there is provided a method of encoding a data pattern for inclusion in a document, said method comprising the steps of: identifying at least an initial reference location for the pattern to be formed; for each successive data item from which the pattern is to be formed: (ba) digitally phase modulating said reference location using a value of said 0 data item; (bb) placing a mark at the phase modulated location; and (bc) updating the reference location at least using the phase modulated location.

In accordance with another aspect of the present invention there is provided a document comprising a data pattern, said data pattern comprising a plurality of marks formed on the document, each said mark being machine readable and having a location digitally phase modulated relative to at least one reference position, the modulation representing the data of the pattern.

In accordance with another aspect of the present invention there is provided a method of decoding a pattern of marks to identify data carried thereby, said method comprising the steps of: detecting a plurality of marks forming the pattern and recording location coordinate data for each said mark; 730231_final.doc -3- L(b) identifying from the location coordinate data an ordering relationship between the marks; determining, according to at least the ordering relationship, a positional difference between adjacent ones of the marks; and from each determined positional difference, determining according to the S ordering relationship, a demodulated phase difference between adjacent marks; and decoding the respective demodulated phase differences to give corresponding data values.

In accordance with another aspect of the present invention there is provided a method 0 of encoding a data pattern for inclusion in a document, said method comprising the steps of: identifying a virtual grid of locations forming a non-visible carrier of the pattern to be formed; for each data item from which the pattern is to be formed: (ba) identifying a corresponding one of said virtual locations; (bb) digitally phase modulating said corresponding location relative to that of the grid using a value of said data item; and (bc) placing a mark at the phase modulated location.

Numerous other aspects of the invention are also disclosed.

Brief Description of the Drawings At least one embodiment of the present invention will now be described with reference to the drawings, in which: Fig. 1 illustrates equipment suitable for printing LVBCs; Fig. 2 illustrates equipment suitable for computer reading of LVBCs; 730231_final.doc 4 Fig. 3 illustrates an array of dots that have been phase modulated so that they no S longer entirely lie on a regular grid; Fig. 4 illustrates a regular array of dots lying on a regular grid; Fig. 5 shows the modulation of the dots in greater detail; S5 Fig. 6 shows the modulation of the dots in even greater detail;

N

Fig. 7 shows the ordering for the digits of an LVBC; SFig. 8 shows the method for encoding LVBC data; Fig. 9 shows the method for decoding LVBC data; Fig. 10 shows the method for locating the message header; 0 Fig. 11 gives an example of absolute phase modulation; Fig. 12 gives an example of differential modular phase modulation; and Fig. 13 is a schematic block diagram representation of a computer system in which the arrangements described can be practiced.

Detailed Description including Best Mode Low Visibility Bar Codes, herein abbreviated to LVBC, are a variety of computer readable mark that can be printed onto pages using normal printers (such as laser printers or inkjet printers) and can be computer read through the use of a normal desktop scanner. They can be used to contain binary data of tens, hundreds or even thousands of bytes per page whilst leaving the majority of the page free to contain human readable content. LVBC marks can be configured to contain a large amount of redundancy, and when this is done they are highly robust to folding, wrinkling, staining, tearing and defacement.

Fig. 1 shows equipment suitable for printing of LVBCs. A personal computer 101, for example an IBM compatible PC running the Microsoft Windows T M operating system may 730231 final.doc L4 be connected to a printer 102, such as a laser printer or inkjet printer, through a communications cable 103. The printer 102 is able to print on a piece of paper 107 or other print medium to provide a hard copy document. The data printed may include an LVBC.

Fig. 2 shows a scanner 104, such as a Canon 9900F desktop scanner, which is connected to a personal computer 106 through a communications cable 105. The personal S computers 106 and 101 may be the same computer, or they may be separate computers, operable independently or, for example, connected via a computer network. The equipment is suitable for computer reading of LVBCs, for example existing on a hard copy document scanned by the scanner 104 in to the computer 106.

0 The methods of encoding and decoding to be described are preferably practiced using a general-purpose computer system 1300, such as that shown in Fig. 13 wherein the processes of Figs. 3-12 may be implemented as software, such as an application program executing within the computer system 1300. In particular, the steps of encoding and decoding are effected by instructions in the software that are carried out by the computer. The instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part performs the encoding and/or decoding methods and a second part manages a user interface between the first part and the user. The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer preferably effects an advantageous apparatus for incorporating data into a document.

730231 _final.doc L4The computer system 1300 is formed by a computer module 1301, input devices such as a keyboard 1302, mouse 1303 and scanner 1318, and output devices including a printer 1315, a display device 1314 and loudspeakers 1317. A Modulator-Demodulator S (Modem) transceiver device 1316 is used by the computer module 1301 for communicating to and from a communications network 1320, for example connectable via a telephone line 1321 or other functional medium. The modem 1316 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN), and may be incorporated into the computer module 1301 in some implementations.

The computer module 1301 typically includes at least one processor unit 1305, and a 0 memory unit 1306, for example formed from semiconductor random access memory (RAM) and read only memory (ROM). The module 1301 also includes an number of input/output interfaces including an audio-video interface 1307 that couples to the video display 1314 and loudspeakers 1317, an 10 interface 1313 for the keyboard 1302 and mouse 1303 and optionally a joystick (not illustrated), and an interface 1308 for the modem 1316, scanner 1318 and printer 1315. In some implementations, the modem 1316 may be incorporated within the computer module 1301, for example within the interface 1308. A storage device 1309 is provided and typically includes a hard disk drive 1310 and a floppy disk drive 1311. A magnetic tape drive (not illustrated) may also be used. A CD'ROM drive 1312 is typically provided as a non-volatile source of data. The components 1305 to 1313 of the computer module 1301, typically communicate via an interconnected bus 1304 and in a manner which results in a conventional mode of operation of the computer system 1300 known to those in the relevant art. Examples of computers on which the described 730231_final.doc arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike S computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 1310 and read and controlled in its execution by the processor 1305. Intermediate storage of the program and any data fetched from the network 1320 may be accomplished using the semiconductor memory 1306, possibly in concert with the hard disk drive 1310. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 1312 or 1311, or alternatively may be read by the user from the network 1320 via the modem device 1316. Still further, the software can also be loaded 0 into the computer system 1300 from other computer readable media. The term "computer readable medium" as used herein refers to any storage or transmission medium that participates in providing instructions and/or data to the computer system 1300 for execution and/or processing. Examples of storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module 1301. Examples of transmission media include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

The application program is operative when scanning information into the computer 1301 from the scanner 1318, and also when printing to the printer 1315.

Basic structure 730231_final.doc -8- L4 Fig. 3 shows an enlarged view of the appearance of an LVBC 300. The LVBC 300 is formed by a large number of dots 302 that lie close to the intersection points 303 of a square grid 301. Note that it is only the dots 302 that form the visible LVBC 300. The grid 301 is S illustrated purely for explanation of the location of the dots 302 and may be considered "virtual" as a consequence. The appearance of an LVBC 300 is similar to that of a regular S grid of dots, but not identical.

Fig. 4 shows the appearance of a regular grid 400 of dots 402 and which lie at the intersections of a regular square grid 401. The square grid 401 has a pitch 403 herein referred to as "gp 0 The difference between a regular array of dots 400 and an LVBC 300 is that the positions of the dots 302 in the LVBC 300 are slightly modulated away from the grid positions that they would occupy if they were part of a truly regular array 400. This slight modulation serves two purposes the first is that it makes the LVBC dots 302 slightly less visible than the dots 402 of a regular grid 400. This is because the human visual system is very adept at noticing regular grids. The second purpose of the modulation is that a message in the form of digital data can be stored in the modulation of the dots 402.

Fig. 5 shows the modulation of the dots in greater detail. The dots 502 lie close to or upon the intersections of the regular grid 501, and each dot 502 is modulated to one of nine possible positions 503. The modulation, being the lateral and transverse location of each dot 502 relative to the corresponding intersection, represents the data of the pattern formed by the dots. The grid 501 is regular in the sense that it is definable and machine detectable and forms a set of reference locations about which modulation may take place for corresponding marks.

As illustrated, the nine possible positions for each dot are arranged in a three by three array 730231_final.doc centred on the relevant or corresponding grid intersection. The central position of the three by S three (3x3) array of positions 503 is located at the grid intersection, and corresponds to a modulation of zero distance horizontally and zero distance vertically. The remaining eight modulation positions are offset from the grid intersection horizontally, vertically, or both 5 horizontally and vertically. The regular grid 501 may be considered a "carrier" signal for the Smodulated dots and, like a carrier wave in radio frequency communication, is not directly observable. The horizontal and vertical distance by which the modulation positions are offset is the modulation quantum 504, herein abbreviated as The locations of the nine modulation positions, relative to the corresponding grid intersection, can be written as a list of 0 y) vectors where x indicates the horizontal direction and y indicates the vertical direction, and using the convention that rightward offsets are positive with respect to x and downward offsets are positive with respect to y. The vectors are: -mq), -mq), -mq), +mq), and +mq) Fig. 6 shows the dot modulation positions 503 in even greater detail. The positions 503 are centred on the grid intersection 604 of grid 602, and each modulation position, such as 730231_final.doc 1 position 601, has an associated digital code value 603. The digital code value 603 for the S position 601 is The nine modulation positions (including position 601) allow each dot to encode one of nine possible digital code values (including the value 603 for the position 601).

The modulation positions allow an LVBC to act as a digital data store, with each dot of the LVBC storing one base-nine digit of data. The preferred ordering of the digits of the digital data store is the ordering provided by using a rectangular array of dots as shown in Fig. 7.

This ordering starts at the topmost, leftmost dot 701 and proceeds left to right and then from top to bottom until the bottommost, rightmost dot 703 is reached. It is possible to use other orderings.

0 Encoder Fig. 8 illustrates a preferred method 800 of encoding an LVBC. The encoding is desirably performed by the software application executable within the PC 101 or computer 1301 to generate the LVBC for printing onto the medium 107 by the printer 102 dr 1315 respectively. Processing commences at step 801 which accepts as input a binary message that is to be encoded in the LVBC. In step 802, three variables M, W and H are calculated. M is the number of base-nine message symbols required to represent the message, W is the minimum width of the LVBC (expressed in LVBC dots) and H is the minimum height of the LVBC (also expressed in LVBC dots).

For a message of bit length BL, M is calculated as follows: M=Iheader+ [log9 BL |log2l The symbol "F 1" represents the "ceil" operator, which returns the smallest integer greater than or equal to the value of its argument. "header" represents the number of base- 730231_final.doc -11nine message symbols required for the message header, if required or desired. The message S header is a fixed pattern that helps a decoder of the LVBC to detect the start of an LVBC message. The header is fundamentally a string of known data values. The string has a fixed, limited length sufficient to provide for accurate detection upon decoding, and also to permit sufficient messaige data to be carried by the dot pattern to be formed. The header used in a preferred implementation is the 12 symbol long vector S Alternatively, almost any randomly selected vector of approximately this length may be used, provided the vector is long enough and random enough that the chance of the vector accidentally appearing in other "message" data conveyed by the LVBC is vanishingly small.

0 W and H are constrained by the inequality: WH> M Any integer solution to this inequality may be used, but the preferred solution is to create a square LVBC by requiring W to equal H, which means that W and H can be calculated as: W=H= 11__ In step 803 the three variables x, y and i are initialised to zero.

In step 804 one of the constituent dots of the LVBC is output. The dots can be output to any type of two dimensional substrate that can have dots placed on it, but in the preferred embodiment it is output to a piece of paper 107 being printed on by printer 102. The dot is output at the position: y) Vec[msg[i]] where "msg" is the sequence of base-nine message symbols which are to be stored in the LVBC. This sequence can readily be formed from the binary representation of the 730231_final.doc 12message accepted at step 801 by treating that message as one long binary number and then converting that number to base-nine representation using simple conversion techniques well known to those skilled in the art. The header vector is then prefixed S to the base-nine message data. "msg[i]" is the i'th digit of the message sequence, using the 0 5 convention that msg[0] is the start of the sequence. msg[z] for z M is defined as zero.

S"Vec" is an array of nine offset vectors, with the following values: Vec[0] -mq), Vec[1] Vec[2] -mq), 0 Vec[3] Vec[4] Vec[6] +mq), Vec[7] Vec[8] +mq), where mq is the aforementioned modulation quantum 504.

In step 805 the current horizontal position, x, is moved to the right by increasing x by the value gp 401. The message index i is also increased by one, so that it references the next digit of the message.

In step 806 the variable x is compared with the variable W. If x is greater than or equal to W then processing proceeds to step 807, otherwise processing returns to step 805.

In step 807 the current vertical position, y, is moved downward by increasing y by the value gp 401. The variable x is reset to zero. Processing then continues to step 808.

730231_final.doc 13- L4In step 808 the variable y is compared with the variable H. If y is greater than or equal to H then processing proceeds to step 809, otherwise processing returns to step 805.

Processing of this method concludes in step 809.

SThe end result of the method 800 is an pattern of dots forming an LVBC, each dot having a digitally phase modulated coordinate relative to a corresponding intersection of S a grid. The grid has an arbitrary origin By setting the origin 0 to a specific coordinate on the print medium 107, the PC 101 can instruct printing of the data on the medium 107, thereby resulting in the LVBC being reproduced and commencing at location Decoder 0 A method 900 for decoding an LVBC encoded as above is described in Fig. 9. The method 900 is desirably performed as a software application executable within the PC 106 having input the LVBC read via the scanner 104. The basic premise of the decoding method is to determine the correct orientation of the grid from which the encoded LVBC was formed.

Knowing the regularity of the grid itself, means that once the grid is identified, demodulation of the dot locations may directly follow. The method 900 commences in step 901, which accepts as input a scanned image of a page incorporating an LVBC, for example printed or otherwise machine readable from the page. In a preferred implementation the scan takes the form of an 8 bit greyscale JPEG image scanned at 600 dpi. In step 903, the dots which comprise the LVBC are detected, and their positions on the page recorded in a list of coordinate data. Step 903 may be performed using connected component analysis of the scanned image. In such analysis, individual pixels of the image are examined to connect and group those that are spatially adjacent. By analysing the group in terms of its shape, the presence of a mark (ie. a circular dot or generally uniform blob of pixels of the appropriate 730231_final.doc -14expected size) can be detected. The centroid of the mark may then be determined to identify a coordinate location corresponding to the detected mark (dot).

In step 905 the list of dot coordinates obtained in step 903 is analysed to detect the S regular grid which forms the carrier signal of the LVBC. This process returns the pitch (gp 401), rotation angle and modulation quantum (mq 504) of the regular grid, and also converts S the supplied list of coordinate data into a rectangular array of coordinate data, ordered as shown in Fig. 7. Upon being presented with a modulated grid representing encoded data, it is useful to determine the orientation and spacing for the modulated grid. In step 905 the grid spacing may be determined on the basis that in a modulated grid, the average spacing between 0 the dots will equal the grid spacing. The grid orientation may be determined on the basis that the average direction between adjacent dots of the modulation grid is aligned with lines of a regular square grid (or 'carrier grid'). Another parameter which may be useful to determine for such a modulated grid is referred to as the 'modulation quantum'. In relation to modulation quantum, the dots of a modulated grid lie close to intersections of the carrier grid.

In one implementation, each dot of the modulated grid may be modulated .to one of nine possible positions arranged in a three by three array centred on a corresponding carrier grid intersection point. A central position of such a three by three array is located at the corresponding carrier grid intersection point, and corresponds to a modulation of zero distance horizontally and zero distance vertically. The remaining eight modulation positions are offset from the corresponding carrier grid intersection point. The term modulation quantum refers to the horizontal and vertical distance by which the remaining modulation positions are offset' from the corresponding carrier grid interaction point.

730231_final.doc In step 907 the information stored in the position of each dot is demodulated.

S Returning to Fig. 6, this is achieved by measuring a vector that runs to each LVBC dot from the nearest grid intersection point 604 of the regular grid 602. The nearest, or most proximate grid intersection is determined by selecting a minimum magnitude vector for each demodulated dot. The measured vector is compared with the vectors from the intersection point 604 to the nine modulation positions showed in Fig. 6. In Fig. 6, the vector 605 extends from the point 604 to the modulation position 601. Similar vectors exist for each of the other modulation positions. The modulation position vector which correlates to or most closely matches the measured vector of the LVBC dot, is chosen as the correct position, and the 0 corresponding digital data value, such as the value 603, is chosen as the correct data value for the LVBC dot. The closeness of match may be determined in a number of ways. A first is to use a Euclidean comparison of vectors extending from the grid intersection position. For example, using the vectors Vl(xl, Yl) and V 2 (x 2 2 the minimum Euclidean distance off all possible nine vectors, in the described arrangement may be calculated using: De sqrt ((x 1 -x 2 2 (YI-y2) 2 Alternatively, angles relative to the grid intersection may be used if one assumes that where the angle is indeterminate due to the length of the vector being close to zero, the modulation degenerates to the intersection position. All of the dots returned by step 905 are thus processed, with processing carried out in the order shown in Fig. 7.

By this stage the LVBC .has been decoded to the point where it is in the form of a substantially rectangular array of base-nine data symbols. This array goes part of the way towards providing the correct ordering of the data symbols, but it still remains to identify which data symbol is the start of the message. This is because the rotation of the LVBC has 730231_final.doc -16not yet been fully resolved. Step 905 only detects rotation modulo 90 degrees any S rotation by 900, 1800 or 2700 has not yet been detected). This issue is addressed in step 909, which is explained in detail by Fig. Fig. 10 shows the method of step 909 for finding the start of the LVBC message data.

Processing commences in step 1001, and in step 1003 the demodulated data located at the topmost, leftmost location of the grid detected in step 905 is compared with the string of data values forming the message header. The header is a previously known, fixed vector of basenine data symbols, such as as previously described. The comparison of step 903 could be for an exact match, but in the preferred embodiment the comparison is 0 for a near match, for example where ten or more of the twelve base-nine data symbols, in the above case, match. The use of a near match makes LVBC more error resistant.

In step 1005 the result of the comparison made in step 1003 is used for branch processing. If the comparison result shows that the header was found at the topmost, leftmost location of the grid then the start of the message data has been found and processing of step 909 successfully concludes at step 1007. If, however, the comparison result shows that the header was not found, then processing proceeds to step 1009. In step 1009 a decision is made as to whether detection of the header in all four possible locations has failed. If that is the case, then processing of step 909 ends with failure in step 1011. In all other cases processing proceeds to step 1013.

In step 1013 the grid is rotated by ninety degrees in a clockwise direction. This is achieved by moving each dot by rotation through 90' centred upon the centre of the grid, and by re-interpreting the modulation of each dot to compensate for the rotation. The re- 730231_final.doc -17- L4 interpretation is achieved by replacing each modulation value with the corresponding rotated modulation value found in the following look up table: Modulation Rotated modulation 0 2 1 2 8 3 1 4 4 7 6 0 7 3 8 6 Step 1013 results in a re-interpretation of the data for a different orientation of the pattern of marks. Whilst such is described relative to a rotation of the grid, alternatively the pattern of marks may be rotated relative to the grid and new position vectors determined for each mark, from which the corresponding (rotated) data values are determined.

After the conclusion of step 1013 processing returns to step 1003. The process of step 909 then occurs for the rotated modulation. This procedure continues until a correct header is found and the step exits successfully at step 1007 or fails at step 1011. Failure ends the method 900 whereas success permits the method 900 to proceeds to step 911.

730231_final.doc -18- L4Returning to the Fig. 9, step 911. accepts as input the rectangular grid of detected base-nine data values that has been processed by step 909 until the message header is located in the topmost, leftmost position of the grid. Step 911 then assembles the decoded message S by starting at the topmost, leftmost data value and proceeding from left to right and from top to bottom, outputting base-nine data values as it goes. The order of processing the base-nine S data values is the order illustrated by Fig. 7, which has already been described. Once all data is decoded, the initial base-nine data symbols that compose the header may be discarded by step 911 so that step 911 provides a message output that does not include the header. Since the header is of fixed length, and the grid upon which the dots are carried is also fixed, the 0 message content is formed by a limited or predetermined number of the data values carried by the modulation of the dots.

The decoding process concludes in step 913.

Different modulation schemes The above described implementation uses a base-nine modulation scheme with a three by three (3x3) array of modulation positions. Alternate modulation schemes with a smaller or larger number of modulation values can be used. Those may include base-4 (2x2), base-16 (4x4), base-25 (5x5), base-36 (6x6), base-49 (7x7), and so on. In a further implementation, a base-8 scheme may be used where the central dot of the presently illustrated 3x3 is omitted. Modulation schemes based upon rectangular arrangements are also possible. For example, base-6 (2x3), base-12 (3x4), base-20 (4x5), base-30 (5x6), and base- 42 (6x7) maybe used if desired.

Differential modular phase encoding 730231_final.doc 1.9- The above described implementation uses absolute phase encoding, where each S message digit is encoded as the absolute phase of an LVBC dot, with respect to the absolute phase reference imposed by the global grid that forms the carrier signal of the LVBC on the printed page.

An alternate implementation uses differential modular phase encoding instead of absolute phase encoding. Differential modular phase encoding encodes each digit in the phase difference between two neighbouring LVBC dots. Phase difference is calculated modulo the encoding base (preferably modulo-nine, but other bases can be used, as has already been mentioned). The present inventor has found that absolute phase encoding is highly 0 susceptible to page warping, as warping results in altered LVBC dot phase in regions of the page that have been warped. The present inventor has found that differential modular phase encoding has the advantage that the modulation is highly resistant to page warping. This is because this form of encoding does not rely on global phase information, only the relative phase of adjacent dots, which is barely affected by the slowly varying warps that are found in most imaging systems. Differential modular phase encoding does have the disadvantage that the loss of a single LVBC dot results in the loss of two code symbols, instead of the loss of a single code symbol that happens with absolute phase encoding.

Fig. 11 gives an example of absolute phase modulation. Shown is an LVBC dot 1101 that encodes the base-nine digit and an LVBC dot 1102 that encodes the basenine digit A page global grid 1103 provides the phase reference for decoding the dots 1101 and 1102. The modulation scheme used in Fig. 11 is the same one that is illustrated in Fig. 6.

730231_final.doc L4Fig. 12 gives an example of differential modular phase encoding. Fig. 12 also encodes the two base-nine digits and An initial LVBC dot 1201 is shown whose phase is unimportant, and can be randomly chosen during encoding. The dot 1201 provides a S reference location for further modulation. Placement of the dot 1021 may be from differentially modulating a root reference location, for example where an array of dots is to be S formed. A second LVBC dot 1202, is adjacently located in the preferred direction of ordering, and has a phase chosen such that the phase difference between the dots 1202 and 1201 is 4 mod 9, thereby encoding the base-nine digit A third LVBC dot 1203 is also shown whose phase is chosen such that the phase difference between the dots 1203 and 1202 is 3 mod 9, 0 thereby encoding the base-nine digit A horizontal offset dx 1205 exists from the dot 1201 to the dot 1202 and a vertical offset dy 1204 exists from the dot 1201 to the 1202. The offsets dx and dy together provide a measure of the phase difference between the dots 1201 and 1202.

An array of such marks may be obtained by tracking a number of marks laid out (eg. in the xdirection) and then updating a reference location for the next "line" of marks (ie. in the ydirection). Once the reference location is updated, to start the new "line", the actual modulated mark location may be determined using each of the updated reference location and the modulation amount derived from the present encoding value and the previous modulation location. A vertical line of reference locations may be used to commence each of a corresponding horizontal line of differentially modulated locations.

Equations for demodulating the phase difference between adjacent LVBC dots are as follows: Ax round(dr x- gp mqJ 730231_final.doc -21- SAy round -d mq Odiff (3Ay Ax)mod 9 where: Odiff is the demodulated phase difference between adjacent LVBC dots, for instance the demodulated value demodulated from the phase difference between the dots 1202 and 1201; round(z) is a function that returns the integer that is closest to z; gp (403) is the grid pitch of the square grid carrier signal; and mq (504) is the modulation quantum.

0 Note that the values of dx and dy need not be integers, and best accuracy is obtained by avoiding rounding or truncation when measuring these values.

Error Correction Codes (ECC) LVBC can be advantageously combined with Error Correction Codes (ECCs) such as Reed-Solomon or Low Density Parity Check (LDPC). ECCs are widely used in all types of digital communication systems to overcome channel errors introduced between the encoding and decoding stages. The use of ECCs is well known to those skilled in the art and will not be explained in detail here. All that is required to combine an ECC with LVBC is to apply ECC encoding to the digital message that is accepted in step 801 and to apply the corresponding ECC decoding to the digital message that is returned by step 911. Utilisation of a strong ECC can make an LVBC highly robust to errors introduced by folding, wrinkling, staining, tearing and defacement.

Balanced modulation 730231_final.doc -22- L4 Well balanced modulation is desirable for correct operation of the LVBC decoder.

By "well balanced" it is meant that the modulation values are evenly distributed around the grid both horizontally and vertically. The method 905 for detecting the carrier signal works S best when the modulation is well balanced, and may fail if the modulation is extremely unbalanced. Most arbitrarily chosen data content will lead to reasonably well balanced modulation, but data content whose base-nine representation is extremely unevenly distributed across the base-nine digits will result in unbalanced modulation.

Well balanced modulation can be ensured by XOR-ing (binary exclusive OR-ing) the message data with a similarly well balanced fixed noise signal prior to encoding and XOR-ing 0 with the same well balanced fixed noise signal after decoding. XOR-ing an original message twice with a fixed signal results, of course, in no net change to that original message. XORing an original message once with a well balanced fixed noise signal results in a modified transmission-ready message that is more likely to be well balanced, as long as the well balanced fixed noise signal is not correlated with the original message data. Avoiding significant correlation between the well balanced fixed noise signal and the original message data is readily achieved in practice by generating the well balanced fixed noise signal from an unbiased (ie. balanced) random digit generator, and choosing the length of the two signals to be sufficiently long that the chance of unintended correlation is vanishingly small.

The arrangements described provide for the formation and reading of a data pattern in a document, the pattern having a plurality of marks formed in the document, each mark being machine readable and having a location digitally phase modulated relative to a reference position, such as a corresponding intersection location of a virtual grid forming a non-visible carrier of the pattern, the modulation representing the data of the pattern.

730231_final.doc -23- L4The marks are preferably dots formed by printing and collectively form a code permitting identification of the document. The size of the marks can vary depending upon the particular application and the level of visibility to be tolerated. The size can be as small as S one pixel at the print resolution for the document thereby providing for low visibility to the human eye whilst permitting scanning for electronic machine reading. The marks and the S identification data they carry represents a functional equivalent to well-known bar codes and may be termed a "bar code" even though no "bars" are actually formed. When combined with the low visibility aspect, the pattern may be considered a low visibility bar code (LVBC), even though the marks have no bars and, in some implementations, may be quite visible to the 0 human eye.

A further point to note is that whilst on encoding the array may be of a useful size sufficient to covey the desired amount of data, decoding requires a practical minimum array size to ensure that the array is accurately detected, which is essential for accurate decoding.

The present inventor has founld that a practical minimum grid/array size is about 8x8 (ie.

giving 64 marks) with reliably practical sizes being 10x 10 or 12x12. An 8x8 grid size, in the present base 9 arrangement, affords about 202 64(log29)) bits of data.

It will be apparent from the above that there is only one modulated dot for each intersection of the grid, thereby being unique for that intersection. If there were two or more dots related to an intersection, then ambiguity would prevail and decoding would produce a nonsense result. Accordingly, for any practical implementation, the possible modulated dot locations for any one intersection should not overlap with the dots possible modulated locations for another (eg. adjacent) intersection.

730231 final.doc -24- L4Some prior art approaches provided computer readable marks that are formed by dots positioned at the intersection of a regular (square) grid. In those instances, a dot may be produced at an intersection to represent a logical with no dot being produced representing S a logical This can result in ambiguity where no dot is produced in that such could be interpreted as the absence of a the computer readable mark rather than a logical In S contrast, with the presently disclosed arrangements, all data values are represented by a mark, and it is the position of the mark, relative to the corresponding intersection of the virtual grid, that determines the data value(s). Thus the likelihood of ambiguity is reduced. The mark need not be a dot, which, in its simplest rendering, may be a single droplet of ink on paper, 0 which will reveal a tiny substantially circular mark. The mark may, in some implementations, be a group of dots, forming any desired and detectable shape, such as a square or triangle, for example. A large practical dot may be equivalent to a full stop as such appears at the end of this sentence. Such, depending on font size, may occupy many displayable or printable pixels.

The arrangements described result in the formation of electronic page data which, when output to the printers 102, 1315, result in hard-copy reproduction of the page data, which may have information content and one or more LVBCs as described. The electronic data forms an electronic document that may be stored for subsequent reproduction, either electronically via the video displayl314, or via the printer 102, 1315. Similarly, the scanning of a document incorporating an LVBC as described produces an electronic document whose page data will include one or more LVBCs. Irrespective of their mode of reproduction and/or storage, such electronic documents may be communicated between computers (via the network 1320 for example) for printing or decoding.

730231_final.doc Industrial Applicability The arrangements described are applicable to the computer and data processing industries and particularly for the production and interpreting of documents for which some form of computer readable data carriage is desired.

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit S of the invention, the embodiments being illustrative and not restrictive.

For example, whilst the described arrangements make use of rectangular, and preferably square, regular grid arrangements, other shapes are possible. For example, shapes 0 such as hexagonal and parallelograms may be used. If desired, a shape such as a grid formed by concentric circles and radii, which may be considered regular in terms of r and 0, is possible. All that is required is that there is some determinable relationship between unmodulated locations (ie. grid intersections) of the chosen grid, thereby forming a basis for determining the positions of modulated marks subject to the type of encoding used.

Accordingly, once the grid, or the manner in which the grid is formed, is known, then given the modulation scheme, the marks upon an encoded document may be decoded.

(Australia Only) In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including", and not "consisting only of'. Variations of the word "comprising", such as "comprise" and "comprises" have correspondingly varied meanings.

730231_final.doc

Claims (30)

1. 2. A method according to claim 1 wherein said initial reference position for is arbitrarily selected.
2. 3. A method according to claim 1 wherein step (ba) comprises modulating the reference location in modulo fashion according to the value and an encoding base representing a number of locations to which the reference location can be modulated.
3. 4. A method according to claim 1 wherein step (bc) comprises updating the reference location using each of the phase modulated location and a root location. 730231_final.doc -27-
4. 5. A document comprising a data pattern, said data pattern comprising a plurality of S marks formed on the document, each said mark being machine readable and having a location digitally phase modulated relative to at least one reference position, the modulation representing the data of the pattern.
5. 6. A document according to claim 5 wherein said at least one reference position S comprises a position of at least one other mark of said pattern.
6. 7. A document according to claim 5 wherein said at least one reference position 0 comprises a virtual grid forming a non-visible carrier of the pattern.
7. 8. A document according to claim 5 wherein said grid is defined for generation and placement of the marks and is detectable from the locations of the marks.
8. 9. A document according to claim 8 wherein the grid comprises a regular grid. A document according to claim 9 wherein said regular grid is a rectangular grid having a minimum size of about 8x8 intersections.
9. 11. A document according to claim 5 wherein each said mark has a location digitally phase modulated relative to a uniquely corresponding intersection of said grid. 730231_final.doc I -28- L4 12. A document according to claim 11 wherein said location is one of a plurality of possible modulated locations associated with said corresponding intersection and a modulation scheme selected from the range base-4 to base-49.
10. 13. A document according to any one of claims 5 to 12 wherein the modulation of each said mark represents a digital code value of said data.
11. 14. A document according to any one of claims 5 to 12 wherein said document is one of an electronic document suitable for printing, or a hard copy document. 0 A method of decoding a pattern of marks to identify data carried thereby, said method comprising the steps of: detecting a plurality of marks forming the pattern and recording location coordinate data for each said mark; identifying from the location coordinate data an ordering relationship between the marks; determining, according to at least the ordering relationship, a positional difference between adjacent ones of the marks; and from each determined positional difference, determining according to the ordering relationship, a demodulated phase difference between adjacent marks; and decoding the respective demodulated phase differences to give corresponding data values. 730231_final.doc -29-
12. 16. A method of encoding a data pattern for inclusion in a document, said method S comprising the steps of: identifying a virtual grid of locations forming a non-visible carrier of the pattern to be formed; for each data item from which the pattern is to be formed: (ba) identifying a corresponding one of said virtual locations; (bb) digitally phase modulating said corresponding location relative to that of the grid using a value of said data item; and (bc) placing a mark at the phase modulated location. 0
13. 17. A method according to claim 16 wherein the grid comprises a regular grid.
14. 18. A method according to claim 17 wherein said regular grid is a square grid having a minimum size of about 8x8 of said virtual locations.
15. 19. A method according to claim 16 wherein said phase modulated location is one of a plurality of possible modulated locations associated with said corresponding virtual location and a modulation scheme selected from the range base-4 to base-49.
16. 20. A method according to claim 16 wherein said document is an electronic document suitable for printing and said method comprises the further step of: forming the pattern of placed marks into an electronic document. 730231_final.doc
17. 21. A method according to claim 20 further comprising the step of: printing said electronic document to a hard copy form incorporating the data pattern.
18. 22. A method of decoding a pattern of marks to identify data carried thereby, said method comprising the steps of: detecting a plurality of marks forming the pattern and recording location coordinate data for each said mark; identifying from the location coordinate data a virtual grid forming a non- 0 visible carrier of the pattern; determining, with the location coordinate data, a position of each said mark relative to a most proximate intersection location of the grid; and from each determined position, determining a corresponding data value for the corresponding said mark.
19. 23. A method according to claim 22 wherein said marks are formed upon a hard copy document and step comprises scanning the document to electronically determine the location coordinate data within the document of each of the marks.
20. 24. A method according to claim 22 where step comprises demodulating the position of each mark by correlating the corresponding determined location to one of a plurality of predetermined positions associated with the proximate intersection. 730231_final.doc __I -31 A method according to claim 24 wherein the demodulation comprises measuring a S vector extending from the intersection to the corresponding determined location and comparing the measured vector with a list of modulation position vectors to identify a most closely matching one of the modulation position vectors.
21. 26. A method according to claim 22 wherein step further comprises: (da) checking data values corresponding to a limited predetermined number of the marks against a predetermined string of data values, such that if the check produces a match, the data values of the pattern are considered correctly decoded. 0
22. 27. A method according to claim 26 wherein if the check produces a mis-match, the method further comprises: (db) rotating the pattern of marks and grid relative to each other, and determining new data values for each of the rotated marks; and (dc) repeating step (da).
23. 28. A method according to claim 27 wherein step (db) rotates the pattern relative to the grid through 90 degrees.
24. 29. A method according to claim 22 wherein the grid comprises a regular grid. 730231_final.doc -32- A method according to claim 22 wherein step comprises digital phase demodulation of the positions according to and a modulation scheme selected from the range base-4 to base-49.
25. 31. A method according to claim 22 further comprising the step of: assembling a message from a predetermined number of the decoded data values.
26. 32. A method of encoding a data pattern substantially as described herein with reference to 0 any one of the embodiments as that embodiment is illustrated in the drawings.
27. 33. to 33. Computer apparatus adapted to perform the method of any one of claims 1 to 4, and
28. 34. A computer readable medium having a computer program recorded thereon and adapted to make a computer execute a procedure to perform the method of any one of claims 1 to 14 and 15 to 33. A document comprising a data pattern substantially as described herein with reference to any one of the embodiments as that embodiment is illustrated in the drawings.
29. 36. A document comprising a differentially modular phase encoded data pattern substantially as described herein with reference to Fig. 12 of the drawings. 730231_final.doc 33 Dated this 13' Day of September 2005 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant Spruson&Ferguson
30. 730231-final.doc