AU2007254626A1 - Data encoding and decoding using circular configurations of marks - Google Patents

Description

S&F Ref: 834352 AUSTRALIA PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT Name and Address Canon Kabushiki Kaisha, of 30-2, Shimomaruko 3 of Applicant: chome, Ohta-ku, Tokyo, 146, Japan Actual Inventor(s): Amit Kumar Gupta Address for Service: Spruson & Ferguson St Martins Tower Level 35 31 Market Street Sydney NSW 2000 (CCN 3710000177) Invention Title: Data encoding and decoding using circular configurations of marks The following statement is a full description of this invention, including the best method of performing it known to me/us: 5845c(1072098_1) - I DATA ENCODING AND DECODING USING CIRCULAR CONFIGURATIONS OF MARKS FIELD OF INVENTION The current disclosure relates to a coding pattern for data embedding using computer readable marks on printed pages. In particular, the disclosure relates to a coding 5 pattern comprising marks arranged in a circular configuration. BACKGROUND The common barcode is one example of computer readable marks that have been widely used on printed pages. An increasing number of alternative computer readable 10 marks have also become increasingly popular in the marketplace. Many of these new varieties of marks provide much greater data storage capacity than the 30 to 60 bits of data storage enabled by a common barcode, thus enabling a wider range of applications. Even so, these marks are typically able to hold only a single data message stream. Other types of marks exhibit reduced visibility, compared to the common barcode. This reduced 15 visibility enables a larger portion of the page to be filled in with human readable content. An additional advantage of these low visibility marks is in that information can be hidden in a page, enabling applications such as steganography and watermarking. Several types of coding patterns exist for data embedding using computer readable marks. One previous approach uses horizontal and vertical lines. The lines are arranged in 20 a grid of fixed distance. The presence of a line at a position encodes a one (1), the absence of a line in a position encodes a zero (0). However, it is difficult to record and decode a pattern of lines as the intersections between the lines can be difficult to record. Also, decoding will be difficult if there are too many consecutive missing lines. An alternative approach uses a position-modulation of marks to encode data. A 25 nominal position is decided and data is encoded by varying the position of the mark with respect to the nominal position. The scheme has limitations due to its dependency on the nominal position. The dependency on nominal position incurs additional complexity of finding the nominal position during decoding. 1070791-v 1 834352 - Speci -2 SUMMARY It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements or to provide a useful alternative. 5 The present invention describes a coding pattern for data embedding which has relatively low encoding and decoding complexity, low visibility and high data capacity. The coding pattern uses a plurality of marks (three or more) arranged on the circumference of a circle. The value of the encoded data is determined by the angular configuration defined by these marks, that is also referred throughout this specification as a angular 10 configuration. No reference grid is needed for encoding the data, which reduces the overall visibility of the coded data, thus enabling a larger and better quality of user-related content to be applied to the page. According to a first aspect of the present disclosure, there is provided a method for encoding data on a substrate, the method comprising printing a plurality of marks on the 15 substrate, the marks being arranged to define a predetermined closed shape or open curve, the predetermined closed shape or open curve being represented by a polynomial or a set of polynomial equations and having an associated one or more reference points, wherein the plurality of marks are arranged in one of a number of predetermined angular configurations with respect to the at least one of the one or more reference points, each angular 20 configuration defining an encoded sequence of binary data. The method preferably comprises printing three marks on a circumference of a circle, a centre point of the circle defining the reference point. According to a second aspect of the present disclosure, there is provided a method for decoding data encoded by a method according to the first aspect, the method 25 comprising; computing the location of the circumcentre of the triangle formed by the three marks to define the centre point; for each pair of marks, among the three marks, computing the angles between the two vectors, each starting from the centre point and being directed to a respective one of 30 the two marks; 1070791-v 1 834352 - Speci -3 defining, out of the computed angles, a sequence of adjacent angles, the sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size; and comparing the computed angles, ordered in the defined sequence, with reference 5 data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. According to a third aspect of the present disclosure, there is provided a system for encoding data on a substrate, the system comprising; a processing device; and 10 a printing device, controlled by the processing device, for printing three or more marks on a circumference of a circle, wherein the three or more marks are arranged in one of a number of predetermined angular configurations with respect to the centre point of the circle, each angular configuration defining an encoded sequence of binary data. According to a fourth aspect of the present disclosure, there is provided a system 15 for decoding data encoded on a substrate by way of three printed marks, the system comprising; a scanning device for scanning the surface of the substrate with the three printed marks; processing means arranged for; 20 computing the location of the circumcentre of the triangle formed by the three marks to define the centre point; for each pair of marks, among the three marks, computing the angles between the two vectors, each starting from the centre point and being directed to a respective one of the two marks; 1070791-v l 834352- Speci -4 defining, out of the computed angles, a sequence of adjacent angles, the sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size; and 5 comparing the computed angles, ordered in the defined sequence, with reference data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. According to a fifth aspect of the present disclosure, there is provided computer 10 program for decoding data encoded on a substrate by way of three printed marks, the program comprising; code for obtaining data from a scanning device, the data being obtained by the scanning device by scanning the surface of the substrate with the three printed marks; code for computing the location of the circumcentre of the triangle formed by the 15 three marks to define the centre point; code for, for each pair of marks, among the three marks, computing the angles between the two vectors, each starting from the centre point and being directed to a respective one of the two marks; code for defining, out of the computed angles, a sequence of adjacent angles, the 20 sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size; and 1070791-vi 834352 - Speci -5 code for comparing the computed angles, ordered in the defined sequence, with reference data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. Other aspects of the present disclosure are also disclosed. For example, there is 5 also provided a computer program product having a computer readable medium, wherein the computer readable medium comprises a computer program according to the fifth aspect. BRIEF DESCRIPTION OF THE DRAWINGS 10 One or more embodiments of the disclosed method will now be described with reference to the following drawings, in which: Fig. 1 illustrates the structure of a basic data unit(BDU); Fig. 2 illustrates one angular arrangement between the marks; Fig. 3 shows the positions of marks for different angular arrangements; 15 Fig. 4 is a flowchart showing the steps of decoding a single coding pattern; Fig. 5 shows the circumcentre of a triangle formed by three marks; Fig. 6A and 6B show variations of a unique angular configuration of a BDU; Fig. 7 shows an example of using multiple BDUs for data embedding; Fig. 8 shows the configuration of Fig. 7 and an exploded view of a single BDU; 20 Fig. 9 shows the BDU patterns for different angular configurations; Fig. 10 shows an example of multiple BDUs in a regular triangular arrangement; Fig. 11 shows the flowchart of a decoding process for decoding a tile including multiple BDUs; Fig. 12 shows the flowchart of the 'Process Collected Data' process, used in the BDU 25 tile decoder; Fig. 13 shows an arrangement for embedding additional data bits by using the angular configuration defined by the circumcentre 1302 and mark 1304, of one BDU, and the reference vector to an adjacent BDU in a tile; Fig. 14 shows multiple BDUs in a flexible arrangement; 1070791-v] 834352 - Sped -6 Fig. 15 shows two examples of flexible arrangements; Fig. 16 shows a schematic block diagram of a general purpose computer system upon which the described arrangements can be practiced; Fig. 17 shows variations of a unique angular configuration of marks within a BDU; 5 Fig. 18 shows an example of four marks defining an ellipse; and Fig. 19 shows a BDU defined be an open curve in the form of a parabola. DETAILED DESCRIPTION INCLUDING THE BEST MODE It is to be noted that the discussions contained in the "Background" section and that 10 relating to prior art arrangements relate to discussions of documents or devices which form public knowledge through their respective publication and/or use. Such should not be interpreted as a representation by the present inventor(s) or patent applicant that such documents or devices in any way form part of the common general knowledge in the art. The present invention relates to encoding data on a surface of a substrate using a set 15 of marks arranged in a predetermined geometrical shape. In the preferred embodiment, the substrate is in the form of sheet of paper and the set of three marks is arranged on the circumference of a circle so as to encode four binary data bits. Hardware Implementation 20 The hereinafter described methods for encoding and decoding data in the form of coding marks may be implemented using a computer system 1600, shown in Fig. 16, wherein the steps of each respective method may be implemented by way of one or more application programs executable within the computer system 1600. In particular, the various encoding and decoding steps are effected by software instructions carried out 25 within the computer system 1600. 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 and the corresponding code modules performs the described method and a second part and the corresponding code modules manage a user interface between the first part and the user. The software may be stored in 30 a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer system 1600 from the computer readable medium, and then executed by the computer system 1600. A computer readable medium 1070791-vi 834352 - Speci -7 having such software or computer program recorded on it is a computer program product. The use of the computer program product in the computer system 1600 preferably effects the hereinbefore described advantageous coding and decoding methods. As seen in Fig. 16, the computer system 1600 is formed by a computer 5 module 1601, input devices such as a keyboard 1602 and a mouse pointer device 1603, and output devices including a printer 1615, a display device 1614 and loudspeakers 1617 and a scanner 1619. An external Modulator-Demodulator (Modem) transceiver device 1616 may be used by the computer module 1601 for communicating to and from a communications network 1620 via a connection 1621. The network 1620 may be a wide-area network 10 (WAN), such as the Internet or a private WAN. Where the connection 1621 is a telephone line, the modem 1616 may be a traditional "dial-up" modem. Alternatively, where the connection 1621 is a high capacity (eg: cable) connection, the modem 1616 may be a broadband modem. A wireless modem may also be used for wireless connection to the network 1620. 15 The computer module 1601 typically includes at least one processor unit 1605, and a memory unit 1606 for example formed from semiconductor random access memory (RAM) and read only memory (ROM). The module 1601 also includes an number of input/output (1/0) interfaces including an audio-video interface 1607 that couples to the video display 1614 and loudspeakers 1617, an I/O interface 1613 for the keyboard 1602 20 and mouse 1603 and optionally a joystick (not illustrated), and an interface 1608 for the external modem 1616 and printer 1615. In some implementations, the modem 1616 may be incorporated within the computer module 1601, for example within the interface 1608. The computer module 1601 also has a local network interface 1611 which, via a connection 1623, permits coupling of the computer system 1600 to a local computer network 1622, 25 known as a Local Area Network (LAN). As also illustrated, the local network 1622 may also couple to the wide network 1620 via a connection 1624, which would typically include a so-called "firewall" device or similar functionality. The interface 1611 may be formed by an EthernetTM circuit card, a wireless BluetoothTM or an IEEE 802.11 wireless arrangement. The interfaces 1608 and 1613 may afford both serial and parallel connectivity, the 30 former typically being implemented according to the Universal Serial Bus (USB) standards and having corresponding USB connectors (not illustrated). Storage devices 1609 are provided and typically include a hard disk drive (HDD) 1610. Other devices such as a 1070791-vi 834352 - Speci -8 floppy disk drive and a magnetic tape drive (not illustrated) may also be used. An optical disk drive 1612 is typically provided to act as a non-volatile source of data. Portable memory devices, such optical disks (eg: CD-ROM, DVD), USB-RAM, and floppy disks for example may then be used as appropriate sources of data to the system 1600. 5 The components 1605 to 1613 of the computer module 1601 typically communicate via an interconnected bus 1604 and in a manner which results in a conventional mode of operation of the computer system 1600 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations, Apple Mac or alike computer systems evolved 10 therefrom. Typically, the application programs for implementing the discussed methods for coding/decoding are resident on the hard disk drive 1610 and read and controlled in execution by the processor 1605. Intermediate storage of such programs and any data fetched from the networks 1620 and 1622 may be accomplished using the semiconductor 15 memory 1606, possibly in concert with the hard disk drive 1610. In some instances, the application programs may be supplied to the user encoded on one or more CD-ROM and read via the corresponding drive 1612, or alternatively may be read by the user from the networks 1620 or 1622. Still further, the software can also be loaded into the computer system 1600 from other computer readable media. Computer readable media refers to any 20 storage medium that participates in providing instructions and/or data to the computer system 1600 for execution and/or processing. Examples of such 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 1601. Examples of 25 computer readable transmission media that may also participate in the provision of instructions and/or data 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 second part of the application programs and the corresponding code modules 30 mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display 1614. Through manipulation of the keyboard 1602 and the mouse 1603, a user of the computer system 1070791-v I 834352 - Speci -9 1600 and the application may manipulate the interface to provide controlling commands and/or input to the applications associated with the GUI(s). The discussed methods may alternatively be implemented in one or more dedicated hardware modules that may include graphic processors, digital signal processors, or one or 5 more microprocessors and associated memories. Basic Data Unit Encoding Fig. I shows an enlarged view of a Basic Data Unit (BDU) 100 of the preferred embodiment of the described coding pattern that is printed on a sheet of paper. The BDU 10 100 consists of three marks 103, 104 and 105 arranged on the circumference of a circle 101, the circle 101 having a centre 102. Only marks 103, 104 and 105 form the visible part of the BDU 100. Circle 101 and its centre 102 are illustrated purely for explanation purpose. The value encoded by a BDU is defined by the angular configuration defined by the marks 103, 104 and 105. 15 While in the described embodiments the encoding marks are in the form of dots, other suitable shapes (square, triangle etc) can also be used. The radius of the circle is a user defined parameter that depends on the target data capacity, visibility, robustness and print medium, as well as on the nature of the printing and scanning processes. Thus, the resolution characteristics of printer 1615, used for encoding of the marks, and scanner 20 1619, used for facilitating the decoding of the marks, have to also be taken into account. The marks are arranged in one or more, out of a number of, predetermined angular configurations on the circumference of a circle so that the circle passes through the centre of mass of each of the marks. An example of an angular configuration defined by the three marks is illustrated in Fig. 2. In this figure, line 201 joins the centre point 102 and mark 25 103; line 202 joins centre point 102 and mark 104; and line 203 joins centre point 102 and mark 105. The angular configuration defined by the marks is characterised by angles 204 and 205, henceforth referred to as OL, formed between line 203 and 202, and OR, formed between line 202 and 201. The various combinations of angular positions of the three marks depend on the 30 starting angle Os, not shown, which is measured from the "vertical" orientation defined by dot 104, as well as from a nominal step size A, also not shown. For example, Table 1 lists the 19 unique angular arrangements defined for angle Os = 300 and step size A = 300. An 1070791-v 1 834352 - Speci -10 appropriate value for Os and A should be selected depending on the target data capacity, visibility and robustness, printing media as well as printing/scanning processes. Also, different values Os and A may be selected to generate unique angular configurations for OL and OR.- It should be noted that the "vertical" orientation of mark 104 is defined in relative 5 terms and only shown in the discussed embodiments for convenience. In practice, the three marks can be disposed in any directions and configurations. S.No OL OR S.No. OU OR 10 1 30 30 11 90 30 2 30 60 12 90 60 3 30 90 13 90 90 4 30 120 14 90 120 5 30 150 15 120 30 15 6 60 30 16 120 60 7 60 60 17 120 90 8 60 90 18 120 120 9 60 120 19 150 30 20 10 60 150 Table I The preferred embodiment uses a starting angle Os= 300 and step size A = 300 to generate 16 unique angular configurations, as shown in Table 2, and achieve a target data rate of 4 bits/BDU. Here the expression "unique angular configuration" includes all 25 angular permutations within one angular arrangement. This is to say that each unique angular configuration, defined by a given combination of Os and A, actually comprised the plurality of angular permutations of, within the particular angular combination, as well as the plurality of all circularly rotated variations. For example, all angular permutations included in the angular configuration {300, 300, 3000}, represented in Fig. 17A, define a 30 single unique angular arrangement that is different from any other angular arrangements. This angular arrangement also includes the circularly rotated versions {3000, 300, 300} and {300, 3000, 300}, shown in Figs. 17B and 17C, respectively, as well as their angular 1070791-v 1 834352 - Speci permutations. It is to be noted that, in this instance, the labelling of the above mentioned configurations in Figs. 17A, 17B and 17C lists the angles in clockwise order, by commencing from the angle on the anticlockwise side of the "vertical" mark 104. Table 2 also maps the correspondence between the binary values encoded by a BDU 5 and the angular configurations between the dots in the described embodiment. This table is kept stored on a HDD 1610, on LAN 1622 or WAN 1620 and, upon request by the processor 1605, is retrieved via the bus 1604, or via the interfaces 1611 or 1608, The unique angular arrangement {300, 300, 3000}, discussed above, maps to the binary sequence 0000, as shown in Table 2. 10 Angular configurations Angular Configurations Data (in degrees) Data (in degrees) OL OR OL OR 0000 30 30 1000 90 30 0001 30 60 1001 90 60 0010 30 90 1010 90 90 0011 30 120 1011 90 120 0100 60 30 1100 120 30 0101 60 60 1101 120 60 0110 60 90 1110 120 90 0111 60 120 1111 30 150 Table 2 Fig. 3 shows the mark positions for different angular configurations used in the preferred embodiment. Positions 301, 302, 303 and 304 represent the position of Mark 105 for OL equal to 300, 600, 900 and 1200, respectively. Similarly positions 305, 306, 307, and 15 308 represent the position of Mark 103 for OR equal to 300, 600, 900 and 1200, respectively. The alternative angular configurations, corresponding to encoded data 0000 to 111 respectively, are shown in Fig. 9 by arrangements 901-916. It is to be noted that the dotted circle in each configuration is shown only for illustration purpose and does not form a visible part of the configuration. 1070791 -v 1 834352 - Speci - 12 The positions of the marks 103 and 105 marks can be calculated using the position of mark 104, the position of the centre point 102 and the angles eL and OR. The computation is usually effected by processor 1605. In the case of more demanding computation, a server having more computational power can be accessed by way of 5 network 1622 or 1620. This is also the case with the decoding process describe hereinafter. BDU Decoder To facilitate the decoding process, scanner 1619 scans the printed coded data and produces a corresponding bitmap. Fig. 4 shows the flowchart of the decoding process for a 10 single BDU. In step 401, the input interface 1608 takes the co-ordinates of the three BDU marks as an input form the scanner 1619. Decision step 402 checks if the three dots lie on a line. This can be simply evaluated by processor 1605 calculating /=(y, - y 2 )*(x 2 - x,)-(xs - x 2 )*(y - y) 15 If 1 is equal to zero, it means the marks lie on a line and, hence, do not constitute a BDU. In this case, the result is represented by the 'Yes' path out of the decision box and the decoder exists through output 406. If / is not equal to zero, the decoding process continues to next step 403. In step 403, the processor 1605 calculates the circumcentre 505 of the triangle 20 formed by the three dots 501, 502 and 503, as shown in Figure 5. Dots 501, 502 and 503 have coordinates (x,, yI), (x 2 , y 2 ), and (x 3 , y 3 ), respectively. The circumcentre is defined as a point of intersection of the perpendicular bisectors of the triangle sides. The coordinates (xe, y ) of the circumcentre can be generated using the following expression: 25 x,2(3 - Y2 )+x 2 2 (y, - y 3 )+x|(y 2 -Y ) +(y 2 -y 1 )(y 3 -Y )(y 3

-

2 ) 2(y 3 (xI-x 2 )+y,(x 2 -X3+y 2

(X

3 -X1)) (x 2 - X,)(X1 +x 2 - 2x) y 1 + y 2 + if y 2 *y 1 2(y, - y.) 2 yc= (x 3 - x,)(x + x 3 - 2x,) + y, + y 3 otherwise 2(y, - y,) 2 1070791 -v 1 834352 - Speci - 13 In step 404, processor 1605 takes the four pairs of coordinates (x,, y), (x 2 y, (xI, y) and (x, y), and calculates the angular configuration defined by the three dots. For this purpose, step 404 arranges the coordinates (x,, y,), (x 2 , y 2 ), and (x 3 , y) in circular order using the well known vector cross-product technique. Thus, in the case shown in Fig. 5 6 (a), the dots are arranged in the order 501, 503 and 502. Accordingly, the dots coordinates are arranged as (x,, y,), (x 3 , y) and (x 2 , y 2 ). The three angles which define the angular relationship are then the angles between vector 601 and 603, 603 and 602, and 601 and 602; referred as 013, 032 and 021 respectively as shown in Fig. 6 (a). The angles can be determined using well known cross product technique. The other possible scenario is 10 when the marks are in the order 501, 502 and 503 and their coordinates are accordingly arranged as (x,, y,), (x 2 , y 2 ) and (x 3 , y), as shown in Fig. 6 (b). In this case the angles between vector 601 and 602, 602 and 603, and 603 and 601 are generated (henceforth referred as 012, 023 and 031, respectively). Thus, without any loss of generality, henceforth we refer the three angles between circularly arranged coordinates as 012, 023 and 031. 15 Step 405 takes 012, 023 and 031 and outputs the BDU decoded data, as a hard decision (the decoded bits), the angles [012, 023, 031], the radius and the co-ordinates of the centre point of the circle formed by the three marks. The decoded data is generated by comparing 012, 023 and 031 with the angular relationships used for encoding data (Table 2). For this purpose a sequence is defined by 20 angles 012, 023 and 031 so that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size. Defining this sequence enables appropriate comparison with corresponding angles in Table 2, which follow the same sequence and size order. In this particular case, as indicated in Table 2, the angles are ordered in a sequence in which the last angle is the 25 largest, upon rotation in a clockwise direction. It should be noted that the angle corresponding to the largest of angles 012, 023 and 031, is not actually shown in Table 2. This angle can be obtained by subtracting the sum of the remaining two angles, shown in the Table, from 3600. The comparison is performed by processor 1605 computing the distance of 30 measured angles (012, 023 and 031) and their circularly rotated versions with predefined angular configurations. The angular configuration ARi can be defined, where data value i 1070791-v i 834352 - Speci - 14 represents the unsigned decimal value of 4 bits encoded by the angular arrangement and is in the range 05 i < 15. For example ARo represents the angular relationship (0, ,0, ,360 -01 - 0,) where 0 =300 and 0= 300 as per the mapping listed in Table 2. Let Df = ([0,62,23,0311 A R,) represents the distance between angles [012, 023, 031] and the 5 angular configuration AR, as per the distance measuref The distance between measured angles and AR, is defined as the minimum distance between AR, and the measured angles and its circularly shifted versions, i.e. d = min(Df(0,6 2 ,023, 0 3 1 AR,), Df (10,0 920 23 1AR,),DU9 23 ,0 1 ,0 , 2 ]AR,)) A commonly used distance function is Euclidean distance which can be generated 10 using the expression d = ((012 -OL +(023 -OR + (03, - 3 6 0 + L +0R2,112 Apart from Euclidean distance, any other common distance measures can be used, such as the Sum of Absolute Difference. Henceforth, for simplicity, the notationfwill not be shown in distance measure and d, is used to denote the distance of measured angles 15 withAR,. The data value k, which is in the range 05 k K 15, is identified as the decoded value if the distance of the measured angles with data value k is minimised with respect to the distance corresponding to other data values, i.e. dk = min[d,, d2' d3,....., d 14 , d]5 20 A maximum limit dr may be used to classify if the three marks correspond to a valid BDU or not. The marks are classified to constitute a valid BDU only if the distance corresponding to the decoded data value dk is less than d,. The maximum limit is selected depending on the printing/scanning process, radius of the circle formed by the marks and the confidence measure required for correct decoding. 25 Another way to decode the encoded BDU data is to use a quantization method. The measured angles can be quantized and circularly organized (preferably in a clockwise directions) to keep the maximum of measured angles (012, 023 and 031) at the last position. If two or more angles are equal to the maximum angle, then the angles are circularly arranged to have the minimum angle at the first position. Then, the first two angles can be 30 used as an index to identify the decoded binary data. 1070791-vi 834352 - Speci - 15 BDU decoder also outputs the three measured angles, radius of the circle formed by the marks, co-ordinates of centre point and dk value. The measured angles can be used to generate soft decoded values which can be used later by Error Correcting decoder. This is explained in details hereinafter with reference to embodiments using BDU for encoding a 5 stream of data bits. In the described coding scheme, there is no nominal position and hence there is no inherent dependency on the nominal position. The three dots define a BDU completely. Also, the described coding scheme is inherently rotation-, scale- and translation- invariant. Additionally, the described coding pattern does not use any alignment or reference marks. 10 These properties result in a relatively simple decoding process. Embodiment 1 - Encoding larger amounts of data by using multiple BDUs Larger amounts of data can be encoded on a document by way of a plurality of BDUs that are printed by printer 1615 on the document in one or more predefined configurations, such 15 as rectangular, triangular or pentagon configuration. Usually, the multiple BDUs are arranged in a tile to encode a given amount of data. Fig. 7 shows an example of a tile 701, in which multiple BDUs are arranged in a rectangular 4 x 4 array to store 64 bits of information. Other arrangements of BDU such as triangular, hexagonal etc may also be used. Fig 10 shows an example of triangular arrangement of BDUs. Rectangular tile 1001 20 comprises 17 BDUs storing 68 bits of data. Lines 1002 visualise the triangular grid. The centre points of the BDUs are arranged at the vertices of the triangles. It is to be noted that lines 1001, 1002, 1003 are shown for illustration purpose only and are not marked on the printed document. Thus, only data encoding dots are printed on the coded document. In a preferred embodiment, the minimum distance between two BDUs is selected 25 such that the marks of a BDU are closest to each other than the marks of any other BDU. The distance between two BDUs is defined as the distance between the centre points of the BDUs. The minimum distance condition requires that the distance between centre points of two neighbouring BDUs must be longer than 4r, where r is the radius of the BDUs. Multiple tiles with different data can be tessellated, to encode a larger quantity of 30 data on the printed sheet. The set of one or more tiles can be printed by printer1615 throughout the page in a regular fashion to increase robustness. However, when this occurs, it becomes difficult to determine the start position and/or the length of the message data 1070791-vl 834352- Speci - 16 sequence. To resolve these ambiguities, a data preamble signifying the beginning of the message data sequence is provided. This preamble is a known pseudorandom binary sequence q[n] that is, say, Q bits long, which is prepended to the message data sequence m[n] that is, say, M bits long, to form an overall message sequence s[n] that is S bits long, 5 where S = Q + M . Message data sequence m[n] can be any message stream or a data stream generated by any algorithm. The overall message sequence s[n] can be used to generate a tile of BDUs. The tile can be repeated, providing the potential of identifying the start positions of message data sequences m[n] by correlation techniques, well known to those skilled in the art. To further increase the robustness of the message data sequence, 10 some form of error correction coding, such as Reed Solomon, LDPC codes or Turbo codes, may be applied to the message data sequence beforehand. It is possible to avoid the inclusion of a preamble by evaluating every position as a possible start position. Such an evaluation, however, will be more computationally demanding. 15 The BDUs can be rotated randomly or in a pre-determined fashion to adjust the visibility and texture of the medium. Embodiment 1 - Decoding arrangements with multiple BDUs Fig 11 shows the flow chart of the decoding process for embodiment 1. 20 Fig. 8 shows an example of tile 801 comprising plurality of marks, defining multiple BDUs. The decoding process starts with step 1101 of finding the encoding marks on the page of the printed document. There are various known methods for detecting marks, any of which can be used. As a result of this step, the group of dots of section 802 have been detected . The centroid of each detected dot is then determined to identify a 25 coordinate location corresponding to the dot. An enlarged view 803 of section 802 shows a dot 804 (with coordinates (x,, y,)), and its two nearest neighbours 805 and 806 (with coordinates (x 2 , y 2 ) and (x 3 , y), respectively). Thus, the output of step 1101 is the three pairs of coordinates(x,,y

,

) ,(x 2 ,y 2 ) and (x 3 , y). These co-ordinates are then passed to a BDU decoder which decodes and outputs the BDU decoded data, the calculated angles, the 30 radius of the circle formed by the marks, and the co-ordinates of the centre point of the circle. 1070791-vi 834352 - Speci - 17 After receiving the output of the BDU decoder, in step 1104, the decoding continues with step 1105 which verifies whether there are more un-decoded marks. If there are more marks to decode, the process returns, via the 'Yes' path, to step 1102. If all encoded marks have been processed, decoding continues via the 'No' path to 5 step 1106 that processes the collected data to decode the overall message stream. A detailed flow chart of process 1106 is shown in Figure 12. The first step 1201 is arranging the decoded BDU data. In order to do that the user has to be able to identify the particular spatial configuration among the BDUs. For this purpose, the decoding system will have to have access to information of the configuration used by the encoder. Such information can 10 be stored on HDD 1610, or being retrieved, via interface 1608 or 1611, from LAN 1622 or WAN 1620. Alternatively, processor 1605 will have to be able to compute the configuration of BDUs using the bitmap of the detected marks, produced by scanner 1619. There are many ways to identify the spatial configuration of BDUs. One possible way is to count the total number of nearest BDU neighbours to a given BDU. For example, for a 15 square configuration, there are 4 nearest neighbours, for a regular triangular arrangement there are 6 nearest neighbours, there are 3 nearest neighbours for a regular hexagon arrangement etc. Due to inherent precision errors involved in the printing the marks, by way of printer 1615 or scanning the marks, by way of scanner 1619, the total number of nearest 20 BDU neighbours may not be constant for all BDUs. In such a case, the number of nearest neighbours, which has the highest occurrence, is used to determine the arrangement. Most error correcting codes performs better if soft probabilities associated with the decoded binary values are provided instead of hard decoded data bits, for facilitating the use of an error-correcting decoder. Thus, step 1201 can be followed by step 1202 including 25 Error Correcting decoding (if such is actually used in the decoding process). The following expression is used to estimate the probability that the angular relationship correspond to decoded decimal value i: P(BDU = i) oc dmax +dmin -dl dmax where 30 d. = max[d,, d 2 , d 3 ..... , d 14 , d 1 5 dmin = min[d, d 2 , d 3 ,....., d 14 , d 5 ] 1070791-v1 834352 - Speci - 18 The probability of a bit being zero at position p (p=0 refers to the least significant bit and p=3 refers to the most significant bit in the binary representation of i) is generated using the expression: P(b, = 0) = I P(BDU =i) 5 where S, represents the set of all decimal values which have zero in their binary representation at position p. The soft probabilities are passed to the step 1202 that represents the decoder for error-correcting codes. The decoder outputs the decoded binary sequence. In cases where a preamble has been used, step 1203 removes the preamble and step 1204 output the message 10 bits. It is also possible to avoid the use of step 1201, by considering all possible arrangements of BDUs and attempt decoding these arrangements using the Error Correcting decoder. Such an approach, however, will incur higher computational cost. 15 Embodiment 2: Higher data capacity In this second embodiment, additional data bits are encoded in a BDU by using the position of a mark in one BDU with respect to the arrangement of adjacent BDUs in a tile. Figure 13 shows the angular arrangement, defined by angle OH, between mark 1304 of BDU 1301(representing mark 104 of the BDUs in Figs I to 3) and an adjacent BDU 1306. 20 Angle 0 H is the anti-clockwise angle between the vector 1305 and vector 1303. 1305 is a vector from centre point 1302 to mark 1304, and 1303 is a vector from centre point 1302 of BDU 1301 to centre point 1308 of BDU 1306. The BDU 1306 represents an adjacent BDU as per the arrangement of multiple BDUs in a tile. For the last BDU in the arrangement, the reference vector 1303 is defined with respect to the second last BDU. 25 The total number of bits that can be encoded with the foregoing arrangement depends on the number of different angular configurations used between the intermediate dot 1304 (104) and the reference vector to the adjacent BDU. The number of the used angular positions will depend on the printing/scanning process, radius of the used BDUs, the print medium and the target data rate. Thus, once again the resolution characteristics of 30 the printer 1615 and the scanner 1619, or any other device that can be used for printing or scanning the marks, have to be taken into account. One preferred embodiment, for 1070791-vi 834352 - Speci - 19 example, uses eight angular configurations, with start angle=0 0 and step size= 450 to encode three data bits. These data bits are decoded once a tile has been identified and successfully decoded, thus obtaining the arrangement of BDUs in the tile. From this arrangement, a 5 reference vector for each BDU is easily generated. The additional data bits are decoded by calculating the anti-clockwise angle between the reference vector and vector joining the centre point of the BDU and the respective mark 104. Techniques using distance measure, quantization etc, that are similar to those used in the first embodiment, can be used to find the decoded data bits. 10 Embodiment 3 - Close Packing of BDUs In a third embodiment, the BDUs are more closely packed, compared to the arrangement in the first two embodiments. In such a case, more than two nearest neighbours are considered for decoding. In general, N nearest neighbours of a mark can be 15 considered for BDU decoding. For N nearest neighbours, there are a total of N C 2 combinations of selecting two marks. Accordingly, NC 2 sets of marks need to be evaluated. The NC 2 sets of marks are decoded using BDU decoder. Corresponding distance measure d and BDU radius values for all sets are collected. This process is repeated for all marks. The d and BDU radius values for all marks are used to identify the correct set of 20 marks constituting a single BDU. One way for doing this is by using the d and BDU radius values to identify the radius corresponding to a minimum distance measure. Afterwards, the selected radius value is used to filter out the marks constituting a circle with different radii. Among the remaining marks, the set which has the minimum d is selected, as the set constituting the BDU. 25 Other techniques may also be used in this embodiment to improve decoding performance. For example: e Only a percentage of total marks may be analyzed to generate the radius of a BDU. " A threshold value for d may be used to filter out the set of marks with higher d 30 values. 1070791-vI 834352 - Speci -20 " A number of sets having similar radii value may be analyzed. If the number of sets is smaller than a threshold value, then a radius corresponding to the 2 "d minimum distance measure is selected and so on. * A pre-defined minimum and maximum threshold limit may be placed on the 5 possible radius values; if the radius value corresponding to the minimum distance measure is not between the minimum and maximum threshold limit, then a radius corresponding to the 2 "d minimum distance measure is selected and so on. 10 Embodiment 4: Flexible Arrangement of BDUs Figure 14 shows an example of flexible arrangement of BDUs. BDUs 1401, 1406 and 1412 have centre points 1402, 1408 and 1410, respectively. Marks 1404 and 1412 correspond to mark 104 of the BDUs shown in Figs. I to 3. These marks are predetermined in a sense that each of them defines the two smaller angles, among angles 15 01, 023 and 03, and is, thus, located between these smaller angles. Vector 1405 points from centre point 1402 to mark 1404. Similarly, vector 1403 points from centre point 1402 to centre point 1408. The angle between vectors 1405 and 1407 is OF. Thus, in this flexible arrangement, the centre point of each subsequent BDU in the arrangement lies on a predefined angular arrangement (defined by angle OF), and at a predefined distance, with 20 respect to the preceding BDU. As shown in figure 14, the centre point 1408 of BDU 1406 lies on vector 1403. Similarly, the centre point of next BDU 1409 lies on vector 1411 and so on. A decoder for flexible arrangement requires the value of angle 0 , to arrange the BDUs in a tile in the particular order. Any value of OF can be used. Furthermore, a set of 25 values for OF may also be used to allow a varying degree of flexibility and complexity in the encoding and decoding processes. A predefined maximum distance between BDUs may be used to identify the BDU belonging to a tile. Many different macro-structures can be created using such a flexible arrangement method, depending on the number of BDUs included in a tile. Figure 15 shows two 30 different arrangements, 1501 and 1503, characterised by 6 BDUs per tile and angle 1070791-v l 834352 - Speci -21 O,= 90'. Frames 1502 and 1504 represent the visual representations of arrangements 1501 and 1503, respectively. To improve the decoding performance, many different constraints may be used during encoding. During decoding, all marks which do not satisfy the predefined 5 constraints are not considered as valid BDUs. Some examples of the constraints are associated with the use of: " A predefined configuration defined by the radius of a BDU and the distance between two BDUs. * Only a predefined BDU arrangement, such as square. 10 * For flexible arrangements, a predefined ratio between radius of a BDU and distance between two BDUs. Other Shapes and Curves for BDUs Apart from a circle, other predetermined closed shapes or open curves may also be 15 used to define a single BDU. In general if a closed shape is defined as a polynomial, or a set of polynomial equations, of order N,, for an x-variable, and order N,, for a y-variable, it requires maximum (N, + N + 1) points to define the shape uniquely. The minimum number of points required to define a close shape uniquely depends on the number of variables in the polynomial. For example a generic polynomial such as: 20 Ax 2 +By 2 +Cx+Dy+E=0 requires minimum five points to define variables A, B, C, D and E uniquely, assuming A, B, C, D and E are independent variables. Thus, any closed shape and appropriate number of minimum points may be used, instead of a circle, to define a BDU. The centroid of all points on the close shape may be used as a reference point for calculating the angular 25 configurations. An example of a closed shape is an ellipse which is defined as: (x-x) 2 +~o2 =1 a2 b2 An ellipse has four variables x 0 , yo, a and b ; hence minimum four points are required to define a unique ellipse. One of the foci of the ellipse or the centre point of the ellipse may be used as a reference point. Fig. 18 shows an example of an ellipse 1805 with 4 marks 30 1801, 1802, 1803 and 1804. 1070791-vl 834352 - Speci - 22 Alternatively, open curves, such as parabolas, hyperbolas etc., may also be used for defining a single BDU. In the case, the origin point (x=0, y-O) with respect to which the curve is defined, or the focus point (if it is defined for a given curve) may be used as a reference point for determining the angular relationships. 5 As an example a parabola may be used as an open curve to encode data. Let us consider a parabola described as (y-k) 2 =4(x-h) 2 This equation defines a parabola with its axis parallel to x-axis with vertex at (h, k) and focus at (h, k+]) as shown in Fig. 19. 1901 represents the parabola with its vertex at 1908 10 with coordinates (h, k). 1909 represents the axis of the parabola which is parallel to x-axis represented by 1906 (1905 represents the y-axis). 1902 represents the focus of the parabola at co-ordinates (h, k+1). 1903 and 1904 represent two marks on the parabola 1901 which extends an angle 0 (1907) at the focus. Different unique pre-defined angular relationships of two marks on the parabola curve with the focus may be used to encode data. It is to be 15 noted that only 1903 and 1904 correspond to the visible part of the curve, other curves, axes and marks are shown for illustrative purpose only. Similarly to the way in which three dots uniquely identify a circle, any given two marks define a unique parabola. Accordingly, when decoding the data encoded with the particular configuration of the pair of marks, the above equation may be solved numerically 20 to determine the vertex point (h, k). Once the vertex point is known, the focus is known as welt (at coordinates (h, k+1) ) and, hence, the angle extended by the marks at the focus can be calculated. The calculated angular value is then used to decode the data by using previously discussed distance, quantization or other techniques. Many different pre-defined constraints may be used to filter out the marks which do not constitute a valid data unit 25 such as a minimum and maximum distance limit of the marks from the vertex or focus, relative position of the marks (both marks being on the same or on different sides of the axis) etc. It is possible to extend it for a curve or shape defined using a set of polynomials and using a single or multiple predefined reference points. While such arrangement can be 30 computationally demanding, they are considered to be within the scope of this invention. Thus, the foregoing describes only some embodiments of the disclosed coding/decoding methods, and modifications and/or changes can be made thereto without 1070791-vl 834352 - Speci -23 departing from the scope and spirit of the method, the embodiments being illustrative and not restrictive. Industrial Applicability 5 The described coding/decoding methods are intended for using coding patterns for embedding data on a paper document, with or without a background image. Storing additional data onto printed documents has a range of useful applications, especially in business environments. One common application is to prevent the unauthorised copying of a printed document via detecting the presence of indicia on the printed document. Another 10 common use is directed not so much to the prevention of unauthorised copying, but rather to tracing back the source of leakage of confidential information, or to recovering the identity of the copyright owner, in the case of copyright infringement. Typically, this is achieved through encoding a unique identifier in the indicia. The invisible macro-structures can also be used as a "fragile" watermark. The 15 detection of an incomplete macro-structure can be used as an indication that the watermark has been tampered with. Multiple tiles may be used to encode a large amount of data or to increase the robustness of data encoding. A set of multiple tiles, containing a tile with predefined constraints, may be used to encode the specifications of other tiles used in the set. This may 20 assist the decoder to achieve high decoding performance. Thus, it is apparent from the above description that the described arrangements are applicable to the printing, encoding and data processing industries. 1070791-vi 834352 - Speci

Claims (10)

1. A method for encoding data on a substrate, the method comprising printing a plurality of marks on the substrate, the marks being arranged to define a predetermined closed shape 5 or open curve, the predetermined closed shape or open curve being represented by a polynomial or a set of polynomial equations and having an associated one or more reference points, wherein the plurality of marks are arranged in one of a number of predetermined angular configurations with respect to the at least one of the one or more reference points, each angular configuration defining an encoded sequence of binary data. 10

2. The method for encoding data according to claim 1, the method comprising printing three marks on a circumference of a circle, a centre point of the circle defining the reference point. 15

3. A method for decoding data, the data being encoded by the method of claim 2, the method comprising; computing the location of the circumcentre of the triangle formed by the three marks to define the centre point; for each pair of marks, among the three marks, computing the angles between the 20 two vectors, each starting from the centre point and being directed to a respective one of the two marks; defining, out of the computed angles, a sequence of adjacent angles, the sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size; and

1070791-vl 834352- Speci -25 comparing the computed angles, ordered in the defined sequence, with reference data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. 5

4. A method of encoding data using a plurality of coding patterns, each coding pattern being generated according to claim 1 or claim 2, wherein the coding patterns are arranged in a predefined spatial configuration with respect to each other.

5. A method of decoding coded data, the coded data being encoded by the method of 10 claim 4, the method of decoding coded data comprising; * using at least one group of a plurality of adjacent marks to identify at least one predetermined coding pattern; e identifying the predefined spatial configuration; e decoding each coding pattern, according to the method of claim 3; and 15 0 decoding the coded data of the plurality of coding patterns by arranging the data from each decoded pattern in a sequence defined by the identified spatial configuration.

6. A method of decoding coded data according to claim 5, wherein the predefined spatial 20 configuration is identified based on the number of coding patterns adjacent to a given coding pattern. 1070791-vi 834352- Speci -26

7. A method of decoding coded data according to any one of claims 5 or 6, the method comprising the step of computing, for each decoded binary value, soft probability associated with the binary value, for facilitating the use of an Error-Correcting decoder. 5

8. A method for decoding coded data comprising a plurality of coding patterns arranged in a predefined spatial configuration, where each coding pattern is generated according to the method of claim 1 or claim 2, the method comprising; e considering a number of adjacent marks, the number of considered marks being larger than the number of marks comprising a single coding pattern; 10 * computing a distance measure and a radius of possible coding patterns; e using the computed radius and/or distance measures to identify, among the plurality of considered marks, marks defining a predetermined coding pattern; e identifying the predefined configuration of coding patterns; * decoding each coding pattern, according to the method of claim 3; and 15 * decoding the coded data of the plurality of coding patterns by arranging the data from each decoded pattern in a sequence defined by the identified spatial configuration.

9. A method for decoding coded data according to claim 8, wherein the predefined 20 configuration of coding patterns is identified based on the number of nearest coding patterns to a given coding pattern. 1070791-v1 834352- Sped -27 10. A method for decoding data according to claim 8 or claim 9, the method comprising the step of computing, for each decoded binary value, soft probability associated with the binary value, for facilitating the use of an Error-Correcting decoder. 5 11. A method of encoding data according to claim 4, wherein the spatial configuration defined by a predetermined one of the plurality of marks defining a first coding pattern, the centre point of the constituting circle of the first coding pattern and the centre point of the constituting circle of an adjacent second coding pattern, is used to define an angular configuration for encoding additional data.

10 12. A method of decoding data according to claim 5, the method comprising; finding an angular configuration defined by the vector from the centre point to a predetermined one of the plurality of marks of a first coding pattern and the reference vector from the centre point of the circle of the first coding pattern to the centre point of the 15 circle of an adjacent second coding pattern; and decoding the additional data encoded in the obtained angular configuration. 13. A method for encoding data according to claim 4, wherein multiple coding patterns in a predefined spatial configuration have flexible arrangements such that the centre point of the 20 circle of each coding pattern is in a predefined angular configuration with respect to the centre point of the circle, and a predetermined one of the plurality of marks, of an adjacent coding pattern. 1070791-vl 834352 - Speci -28 14. A method of decoding data according to claim 5, the method comprising using a predefined angular configuration defined by a predetermined one of the plurality of marks of a first coding pattern, the centre point of the first coding pattern and the centre point of an adjacent second coding pattern, to identify the sequence of coding patterns in a plurality 5 of coding patterns. 15. A system for encoding data on a substrate, the system comprising; a processing device; and a printing device, controlled by the processing device, for printing three or more 10 marks on a circumference of a circle, wherein the three or more marks are arranged in one of a number of predetermined angular configurations with respect to the centre point of the circle, each angular configuration defining an encoded sequence of binary data. 16. A system for decoding data encoded on a substrate by way of three printed marks, the 15 system comprising; a scanning device for scanning the surface of the substrate with the three printed marks; processing means arranged for; computing the location of the circumcentre of the triangle formed by the 20 three marks to define the centre point; for each pair of marks, among the three marks, computing the angles between the two vectors, each starting from the centre point and being directed to a respective one of the two marks; 1070791-vi 834352 - Speci -29 defining, out of the computed angles, a sequence of adjacent angles, the sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order according to their size; and comparing the computed angles, ordered in the defined sequence, with reference 5 data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. 17. A computer program for decoding data encoded on a substrate by way of three printed marks, the program comprising; 10 code for obtaining data from a scanning device, the data being obtained by the scanning device by scanning the surface of the substrate with the three printed marks; code for computing the location of the circumcentre of the triangle formed by the three marks to define the centre point; code for, for each pair of marks, among the three marks, computing the angles 15 between the two vectors, each starting from the centre point and being directed to a respective one of the two marks; code for defining, out of the computed angles, a sequence of adjacent angles, the sequence being such that, upon rotation in a predetermined direction, the angles sequentially defined by the adjacent pairs of marks follow a predetermined order 20 according to their size; and code for comparing the computed angles, ordered in the defined sequence, with reference data arranged in the same order, based on angle size, to identify the encoded values corresponding to the particular angular configuration of the three marks. 1070791-vl 834352 - Speci -30 18. A computer program product having a computer readable medium, wherein the computer readable medium comprises a computer program according to claim 17 recorded therein. 5 DATED this 21st Day of December 2007 CANON KABUSHIKI KAISHA Patent Attorneys for the Applicant SPRUSON&FERGUSON 10 1070791-v i 834352 - Speci