Global metadata embedding and decoding

• US 7,421,439 B2
• Filed: 04/22/2005
• Issued: 09/02/2008
• Est. Priority Date: 04/22/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Qiang, Dang, Yingnong, Wu, Jiang, Li, Yue, Wang, Jian, Lin, Zhouchen, Zhang, Chunhui
• Primary Examiner(s): Lu; Kuen S.
• Assistant Examiner(s): Kerzhner; Aleksandr
• Application Number:
  US11/112,672
• Publication Number:
  US 20060242561A1
• Time in Patent Office: 1,229 Days
• Field of Search: 707/100, 235/472.03, 235/462.49, 235/494
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0321 by optically sensing the absolute position with respect to a regularly patterned surface forming a passive digitiser, e.g. pen optically detecting position indicative tags printed on a paper sheet constructional details of pen-shaped pointing devices G06F3/03545, G06F3/03542, G06F3/037
• CPC Class Codes: G06F 3/03545 Pens or stylus
• CPC Class Codes: G06F 40/171 by use of digital ink

Abstract

Global metadata, such as a document identifier, which may be a globally unique identifier, is embedded into an embedded interactive code document by combining a first m-array and a plurality of copies of the first m-array to generate a combined m-array with encoded global metadata such that respective start positions (x_d,y_d)ⁱ of the plurality of copies of the first m-array in the combined m-array are each shifted, by respective amounts that are based on respective portions of the global metadata, relative to a start position of the first m-array in the combined m-array. Global metadata may be decoded from the combined m-array by determining the respective amounts by which the plurality of copies of the first m-array are shifted, relative to the first m-array, in the combined m-array and by combining the respective amounts to produce a decoded value of the global metadata.

Claims

1. A system that embeds global metadata into an embedded interactive code document, the system comprising:

a first m-array that contains a first repeating sequence of bits;

global metadata that specifies a document-identification information for the embedded interactive code document;

a plurality of copies of the first m-array; and

a storage device having a global-meta-data-encoding module stored upon that contains computer-executable instructions that are recorded on a computer-readable medium and that, when executed by a processor, combine the first m-array and the plurality of copies of the first m-array to generate a combined m-array with encoded global metadata such that respective start positions (x_d,y_d)ⁱ of the plurality of copies of the first m-array in the combined m-array are each shifted, by respective amounts that are based on respective portions of the global metadata, relative to a start position of the first m-array in the combined m-array;

wherein the respective start positions (x_d,y_d)ⁱ of the plurality of copies of the first m-array in the combined m-array are calculated as

$x_d^i=\mathrm{mod}<br><br>\left(\mathrm{global}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i,2^{\frac{n}{2}}+1\right),<br><br>y_d^i=\mathrm{int}<br><br>\left(\frac{\mathrm{global}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i}{2^{\frac{n}{2}}+1}\right),$

where n is an order of the first m-array and 0≧

global metadata portion_i≧

2ⁿ−

2.

2. The system of claim 1, wherein the first m-array is a position m-array.

3. The system of claim 2, wherein the plurality of copies of the first m-array are global-metadata m-array s.

4. The system of claim 1, wherein the global metadata is a globally unique identifier.

5. A system that decodes global metadata from an embedded interactive code document, the system comprising:

a combined m-array with encoded global metadata, wherein global metadata is encoded in the combined m-array via respective start positions (x_d,y_d)ⁱ of a plurality of copies of a first m-array in the combined m-array being shifted, by an amount that is based on respective portions of the global metadata, relative to a start position of the first m-array in the combined m-array with encoded global metadata;

a storage device having a global-meta-data-decoding module stored upon that contains computer-executable instructions that are recorded on a computer-readable medium and that, when executed by a processor, decode the global metadata from the combined m-array by determining the respective amounts by which the plurality of copies of the first m-array are shifted, relative to the first m-array, in the combined m-array and by combining the respective amounts to produce a decoded value of the global metadata;

wherein the global-meta-data-decoding module decodes, from the combined m-array, the first m-array and each of the plurality of copies of the first m-array separately from one another;

wherein the global-meta-data-decoding module determines a first position (x_p,y_p) of a point P in the first m-array and respective shifted positions (x_m,y_m)ⁱ of the point P in the plurality of copies of the first m-array; and

wherein the global-meta-data-decoding module calculates respective values for the portions of global metadata as

$\mathrm{global}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i=\mathrm{mod}<br><br>\left(y_p-y_m^i,2^{\frac{n}{2}}-1\right)·<br><br>\left(2^{\frac{n}{2}}+1\right)+\mathrm{mod}<br><br>\left(x_p-x_m^i,2^{\frac{n}{2}}+1\right),$

where n is an order of the first m-array.

6. The system of claim 5, wherein the first m-array is a position m-array and the plurality of copies of the first m-array are global-metadata m-arrays.

7. The system of claim 5, wherein, for a plurality of images of the embedded interaction code document, respective values of global metadata portion_i that occur most often are selected for use as respective global metadata portion values for calculating the decoded value of the global metadata.

8. The system of claim 7, wherein the decoded value of the global metadata is calculated as

$\mathrm{decoded}\; <li></li><br><br>\mathrm{global}<br><br><br><br>\mathrm{metadata}=\underset{i=0}{\overset{j}{\sum <br><br>}}<br><br>\mathrm{selected}<br><br><br><br>\mathrm{global}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i·<br><br>{\left(2^n-1\right)}^i,$

where j is a number of dimensions in which the global metadata was encoded and n is an order of the first m-array.

9. A computer-readable medium having recorded thereon computer-executable instructions for embedding global metadata into an embedded interactive code document by combining a first m-array and a plurality of copies of the first m-array to generate a combined m-array with encoded global metadata such that respective start positions (x_d,y_d)ⁱ of the plurality of copies of the first m-array in the combined m-array are each shifted, by respective amounts that are based on respective portions of the global metadata, relative to a start position of the first m-array in the combined m-array;

and

for calculating the respective start positions (x_d,y_d)ⁱ of the plurality of copies of the first m-array in the combined m-array as

$x_d^i=\mathrm{mod}<br><br>\left(\mathrm{global}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i,2^{\frac{n}{2}}+1\right),<br><br>y_d=\mathrm{int}<br><br>\left(\frac{g<br><br>\mathrm{lobal}<br><br><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i}{2^{\frac{n}{2}}+1}\right),$

where n is an order of the first m-array and 0≧

global metadata portion_i≧

2ⁿ−

2.

10. The computer-readable medium of claim 9, having recorded thereon further computer-executable instructions for decoding the global metadata from the combined m-array by determining the respective amounts by which the plurality of copies of the first m-array are shifted, relative to the first m-array, in the combined m-array and by combining the respective amounts to produce a decoded value of the global metadata.

11. The computer-readable medium of claim 10, having recorded thereon further computer-executable instructions for decoding, from the combined m-array, the first m-array and each of the plurality of copies of the first m-array separately from one another.

12. The computer-readable medium of claim 11, having recorded thereon further computer-executable instructions for determining a first position (x_p,y_p) of a point P in the first m-array and respective shifted positions (x_m,y_m)ⁱ of the point P in the plurality of copies of the first m-array.

13. The computer-readable medium of claim 12, having recorded thereon further computer-executable instructions for calculating respective values for the portions of global metadata as

$\mathrm{global}\; <li></li><br><br>\mathrm{metadata}<br><br><br><br>{\mathrm{portion}}_i=\mathrm{mod}<br><br><br><br>\left(y_p-y_m^i,2^{\frac{n}{2}}-1\right)·<br><br>\left(2^{\frac{n}{2}}+1\right)+\mathrm{mod}<br><br><br><br>\left(x_p-x_m^i,2^{\frac{n}{2}}+1\right),$

where n is an order of the first m-array.

14. The computer-readable medium of claim 13, having recorded thereon further computer-executable instructions for selecting, for a plurality of images of the embedded interaction code document, respective values, which occur most often, of global metadata portion, for use as respective global metadata portion values for calculating the decoded value of the global metadata.

15. The computer-readable medium of claim 14, having recorded thereon further computer-executable instructions for calculating the decoded value of the global metadata as

$\mathrm{decoded}$

⁢

global ⁢

⁢

metadata = ∑

i = 0 j ⁢

selected ⁢

⁢

global ⁢

⁢

metadata ⁢

⁢

portion i ·

( 2 n - 1 ) i ,

where j is a number of dimensions in which the global metadata was encoded and n is an order of the first m-array.