Method and apparatus for embedding auxiliary information within original data

• US 7,532,740 B2
• Filed: 03/27/2007
• Issued: 05/12/2009
• Est. Priority Date: 09/25/1998
• Status: Expired due to Fees

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Levy, Kenneth L.
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/691,938
• Publication Number:
  US 20080040811A1
• Time in Patent Office: 777 Days
• Field of Search: 382/100, 382/232, 382/240, 713/176, 713/179, 380/51, 380/54
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0083 whereby only watermarked image required at decoder, e.g. source-based, blind, oblivious
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

This patent application is generally related to watermarking and steganography. In one implementation, a method of embedding auxiliary information within original data is provided. The original data is divided into a series of groups, with each group in the series of groups associated with a value. The method includes: investigating a first group to determine a presence of a local masking opportunity; and if there exists a presence of a local masking opportunity with the first group, embedding data by setting a value of one or more groups in a neighborhood of the first group, including the first group, in accordance with a value associated with at least a portion of the auxiliary data. Other implementations and embodiments are provided as well.

Claims

1. A method of embedding auxiliary data within original data, the original data being divided into a series of groups, each group in the series of groups characterized by a value, the method comprising:

a. investigating a first group to determine a presence of a local masking opportunity, including determining using a processor whether the first group exceeds a first predetermined threshold, and whether a value associated with a second group differs from a value associated with a first group by a second predetermined threshold;

b. if there exists a presence of a local masking opportunity with the first group, embedding using a processor auxiliary data in the original data by setting a value of one or more groups in a neighborhood of the first group, the neighborhood including the first group, in accordance with a value associated with at least a portion of the auxiliary data.

2. The method of claim 1 wherein said investigating a first group to determine a presence of a local masking opportunity further includes determining whether the first group includes a peak.

3. The method of claim 2 wherein said act of embedding auxiliary data in the original data by setting the value of one or more groups in the neighborhood of the first group comprises setting a difference between the first group and the one or more groups associated with the portion of the auxiliary data.

4. The method of claim 1 wherein

a. said act of investigating the first group to determine the presence of a local masking opportunity further comprises examining a value associated with the first group and a relationship of the value of the first group to a value of at least one other group in the series of groups;

and

b. said act of embedding auxiliary data in the original data by setting the value of one or more groups in the neighborhood of the first group includes setting a value dependent upon the value of the first group and on the value associated with at least the portion of auxiliary data.

5. The method of claim 1 wherein said act of investigating the first group to determine the presence of a local masking opportunity includes determining whether:

a value associated with a previous group relative to the first group did not exceed the first predetermined threshold.

6. The method of claim 5 wherein said act of investigating the first group to determine the presence of a local masking opportunity includes determining whether:

a change in value slope from the previous group to a group following the first group is less than a third predetermined threshold.

7. The method of claim 6 wherein said act of investigating the first group to determine the presence of a local masking opportunity includes determining whether:

a difference between the value associated with the first group and the value associated with the previous group is less than a user defined value.

8. The method of claim 7 wherein said act of embedding data by setting the value of one or more groups in the neighborhood of the first group includes setting the value such that a change in value slope of at least two previous group values prior to the first group is set by at least the portion of auxiliary data.

9. The method of claim 1 wherein said act of embedding data by setting a value of one or more groups in the neighborhood of the first group includes changing a value of one or more bits associated with the first group.

10. The method of claim 1 wherein each group in the series of groups represents a value of a same quantity measured at a different frequency.

11. The method of claim 1 wherein the original data represents or is associated with scaling factors or frequency coefficients of bit-rate reduced data.

12. The method of claim 11 wherein the bit-rate reduced data comprises MPEG data.

13. The method of claim 1 wherein each group in the series of groups is associated with a sample of audio data.

14. A method of retrieving auxiliary information from within host data, the host data being divided into a series of groups, each group in the series of groups being characterized by a numerical value, the method comprising:

(a) investigating a first group in the series of groups to determine a presence of a local masking opportunity including determining using a processor whether the first group exceeds a first predetermined threshold, and whether a value associated with a second group differs from a value associated with the first group by a second predetermined threshold;

(b) if there exists a presence of a local masking opportunity with the first group, retrieving information by measuring using a processor a value associated with one or more groups in a neighborhood of the first group, the neighborhood including the first group.

15. The method of claim 14 wherein said investigating a first group in the series of groups to determine a presence of a local masking opportunity further includes determining whether the first group includes a peak.

16. The method of claim 15 wherein said act of retrieving information by measuring a value associated with one or more groups in a neighborhood of the first group is measured from a difference between the value associated with first group and the value associated with the second group.

17. The method of claim 14 wherein:

a. said act of investigating a first group in the series of groups to determine a presence of a local masking opportunity includes examining the value associated of the first group and the first group'"'"'s relationship to a value associated with at least one other group near or associated with the first group; and

b. said act of retrieving information by measuring a value associated with one or more groups in a neighborhood of the first group includes measuring a value that is dependent upon the value of the first group and dependent on at least a portion of the auxiliary information.

18. The method of claim 14 wherein said act of investigating a first group in the series of groups to determine a presence of a local masking opportunity includes determining whether a value associated with a previous group relative to the first group did not exceed the first predetermined threshold.

19. The method of claim 18 wherein said act of investigating a first group in the series of groups to determine a presence of a local masking opportunity includes determining whether a change in value slope from the previous group to a following group is less than a third predetermined threshold.

20. The method of claim 19 wherein said act of investigating a first group in the series of groups to determine a presence of a local masking opportunity includes determining whether a value difference between the first group and the previous group is less than a user defined value.

21. The method of claim 20 wherein said act of retrieving information by measuring a value associated with one or more groups in a neighborhood of the first group is measured from a change in slope using at least two values associated with two previous groups prior to the first group.

22. The method of claim 14 wherein said act of retrieving information by measuring a value associated with one or more groups in a neighborhood of the first group includes measuring one or more bits of the value.

23. The method of claim 14 in which each group in the series of groups represents or is associated with a value of the same quantity measured at a different frequency.

24. The method of claim 14 in which the host data represents scaling factors or frequency coefficients of bit-rate reduced data.

25. The method of claim 24 wherein the bit-rate reduced data comprises MPEG data.

26. The method of claim 14 in which each group in the series of groups represents or is associated with a sample of audio.

27. An apparatus to embedding auxiliary information comprising:

a. a logic processor; and

b. a storage unit, wherein the logic processor or storage unit includes;

(i) a comparer to compare a value associated with a first group in a series of groups with first predetermined data and with at least one other value associated with a second group in the series of groups to determine whether the other value and the value associated with a first group differ by second predetermined data, a result of which is used to determine whether the value associated with the first group represents a local masking opportunity;

(ii) a data writer to store the original data and auxiliary information onto a storage media, the data writer changing a group value of the original data in a vicinity of a local masking opportunity to embed the auxiliary information in the original data to produce combined data, the local masking opportunity reducing a likelihood of perceptibility of the auxiliary data when the combined data is presented to a user, and

wherein said comparer determines additional local masking opportunities and the data writer changes corresponding group values in a vicinity of the additional local masking opportunities until all the auxiliary information is embedded in the original data or until no additional local masking opportunities are located or required.

28. An apparatus to embedding auxiliary data comprising:

a. a logic processor; and

b. a storage unit, wherein the logic processor or storage unit includes;

a comparer to compare a group value associated with a first group in a series of groups with first predetermined data and with at least one other value associated with a second, nearby group in the series of groups to determine whether the other value and the value associated with a first group differ by second predetermined data, a result of which is used to determine whether the value associated with the first group represents a local masking opportunity, said comparer providing auxiliary data determined from the local masking opportunity, and said comparer determining additional local masking opportunities and determining auxiliary data bits there from.

29. The apparatus of claim 28 wherein a nearby group comprises a group within at least 50 sequential groups of the first group.

30. A method of preventing unauthorized copying of an audio data file, the audio data file being divided into a series of samples, each sample in the series being associated with a value, the method comprising:

a. determining using a processor whether a first sample of the series of samples represents a local masking opportunity by examining a first value associated with the first sample and a second value associated with at least one other sample, and comparing the first value to first predetermined data and determining whether the first value and the second value differ in a predetermined manner;

b. if the first sample represents a local masking opportunity, embedding using a processor a portion of unauthorized copy prevention data by setting a value associated with a second sample in accordance with a value of at least a portion of the copy prevention data, the local masking opportunity allowing the at least a portion of the unauthorized copy prevention data to be embedded in the audio file with minimal perceptibility by a user of the audio file; and

c. locating additional local masking opportunities in the audio data file to embed additional portions of the unauthorized copy prevention data therein.

31. The method of claim 30, wherein upon receipt of an embedded audio file and an attempt to copy the audio data file, verifying whether the embedded audio file includes unauthorized copy prevention data and, if so, preventing a copy from being produced.

32. A method of retrieving auxiliary information from within host data, the host data being divided into a series of groups, each group in the series of groups being characterized by a numerical value, the method comprising:

(a) obtaining host data over a transmission channel, obtained host data including the auxiliary information;

(b) investigating a first group in the series of groups to determine a presence of a local masking opportunity including determining using a processor whether the first group exceeds a predetermined threshold, the predetermined threshold being associated with non-transformed host data;

(c) if there exists a presence of a local masking opportunity with the first group, retrieving information by measuring using a processor a value associated with one or more groups in a neighborhood of the first group, the neighborhood including the first group, said retrieving utilizing only the obtained host data.