METHOD OF AND APPARATUS FOR HIGH-BANDWIDTH STEGANOGRAPHIC EMBEDDING OF DATA IN A SERIES OF DIGITAL SIGNALS OR MEASUREMENTS SUCH AS TAKEN FROM ANALOG DATA STREAMS OR SUBSAMPLED AND/OR TRANSFORMED DIGITAL DATA

• US 6,768,980 B1
• Filed: 07/06/2000
• Issued: 07/27/2004
• Est. Priority Date: 09/03/1999
• Status: Expired due to Term

• Current Assignee: Time Warner Cable Enterprises LLC (Charter Communications Incorporated), Josslyn M Meyer
• Original Assignee: Josslyn Motha Meyer, Thomas W. Meyer
• Inventors: Meyer, Josslyn Motha, Meyer, Thomas W.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Lerner, Martin
• Application Number:
  US09/611,151
• Time in Patent Office: 1,482 Days
• Field of Search: 704/500, 704/501, 704/503, 382/100, 382/239, 382/248, 382/251, 713/176
• US Class Current: 704/500
• CPC Class Codes: G06T 1/0021 Image watermarking
• CPC Class Codes: G06T 1/0035 Output size adaptive watermarking
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0053 Embedding of the watermark in the coding stream, possibly without decoding; Embedding of the watermark in the compressed domain
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations
• CPC Class Codes: H04N 1/32154 Transform domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32277 Compression
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A novel technique for high-bandwidth steganographic embedding of supplemental data in a series of digital signals or measurements, such as taken from analog data streams or subsampled and/or transformed digital data, wherein the series of measurements are derived through functional transformations and involving quantization and/or aliasing, with the supplemental data bits modulating or modifying the quantized and/or aliased components with only slight adjustments thereof to embed the supplemental data without substantially affecting the quality of the measurements; and all, preferably, through not exclusively, with the use of least-significant-bit parity encoding designed to choose the appropriate components to be so modulated or modified

Claims

1. The method of steganographically embedding substantial supplemental digital data in a series of digital measurements derived from one of an analog data stream and subsampled and/or transformed digital data, that comprises, deriving such series of digital measurements through functional transformation from a set of input data converted into a set of output data of successive quantized and/or aliased components;

transforming the substantial supplemental digital data into a series of successive bits; and

introducing the successive bits into the quantized and/or aliased components to modulate from a few percent to a substantial percentage of the successive components through but slight adjustments of the same, thereby to embed the supplemental data in from a few percent to a substantial percentage of the series of digital measurements without substantially affecting the quality thereof.

2. The method of claim 1 wherein the measurements represent a media file, and the embedded supplemental data provides additional content to the media file format in playback without changing that format.

3. The method of claim 2 wherein the additional content is selected from the group consisting of an added high-bandwidth digital channel, ads, interactive ads, games, additional program materials, and subtitles and the media is audio, image or video.

4. The method of claim 2 wherein the supplemental data is embedded in from at least about 2 to about 9 percent of the media file content.

5. The method of claim 1 wherein the embedding is effected with least significant-bit parity encoding arranged to choose which measurement or component or coefficient representing the same is to be modified and by which bit, while only minimally affecting the accuracy.

6. The method of claim 5 wherein the choosing is selected for one or both of minimum noise and psycho-perceptual measures.

7. The method of claim 5 wherein only selected bits of the digital stream are modified as determined by pre-computation of the data embedding.

8. The method of claim 1 wherein the embedding is effected by an encoding technique selected from the group consisting of parity encoding, higher-order parity encoding, variable data rate and variable length encoding, and black-box encoding.

9. The method of claim 8 wherein the encoding technique is black-box encoding and wherein the embedding in the measurements is effected semi-independently of the details of the function used to transform the measurements, through use of adaptive feedback.

10. The method of claim 1 wherein the encoded measurement data is extracted by straightforward reversal of the encoding process.

11. The method of claim 1 wherein the functional transformation is selected from the group consisting of Fourier, Cosine, Sine and Wavelet transforms providing series of coefficient representations of the measurement data.

12. The method of claim 11 wherein the low bits of coefficients of the transformed and quantized and/or aliased series of measurements are modified by embedding successive of the supplemental data bits therein.

13. The method of claim 12 wherein the choosing of the coefficients to be so modified is effected from psycho-perceptual information.

14. The method of claim 1 wherein the series of measurements are selected from the group consisting of media file formatted data;

audio waveform for measurements such as PCM algorithms, compressed audio files such as mp3;

image value measurements such as a scanned image, a fax, or a compressed image file such as JPEG;

time-varying image value measurements such as a digitized movie or compressed video files such as mpeg; and

data consisting of a series of physical measurements such as machine control data, process monitoring and temperature or pressure measurements.

15. The method of claim 1 wherein the functional transformation is effected from a set D of input continuous or discrete data points into a set D¹ of output discrete data points, and creating a modified version D¹¹ closely related to D¹ but having the added feature of encoding a second or supplemental data bit stream therein through the modifying or modulating of the quantization and/or aliasing components inherent in the conversion from D to D¹ with the bits of the supplemental data bit stream, and with only minimal and insignificant affecting of the accuracy of the data.

16. The method of claim 15 wherein the input data is derived from a media file format, and the modifying or modulating involved in the encoding and embedding of the supplemental data is effected with such sufficiently small changes in D¹ as not substantially to affect the perceptual experience in playing back the encoded data.

17. The method of claim 1 wherein from about 3 to about 25 percent of the successive components are modulated with supplemental data bits.

18. Apparatus for steganographically embedding substantial supplemental digital data in a series of digital measurements derived from one of an analog data stream and subsampled and/or transformed digital data, having, in combination, functional transformation means for deriving such series of digital measurements from a set of input data converted into a set of output data of successive quantized and/or aliased components;

means for transforming the substantial supplemental digital data into a series of successive bits; and

encoder means for introducing the successive bits into the quantized and/or aliased components to modify from a few percent to a substantial percentage of the successive components through but slight adjustments of the same, thereby to embed the supplemental data in from a few to a substantial percentage of the series of digital measurements without substantially affecting the quality thereof.

19. The apparatus of claim 18 wherein the measurements represent a media file and the embedded supplemental data provides additional content to the media file format in playback without substantially changing that format.

20. The apparatus of claim 19 wherein the additional content is selected from the group consisting of added high bandwidth digital channels, ads, interactive ads, games, additional program materials, and subtitles and the media is audio, image or video.

21. The apparatus of claim 19 wherein the supplemental data is embedded from at least about 2 to about 9 percent of the media file content.

22. The apparatus of claim 19 wherein the embedding is effected with least-significant-bit parity encoding means arranged to choose which measurement or component or coefficient representing the same is to be modified and by which bit, while only minimally affecting the accuracy.

23. The apparatus of claim 22 wherein the choosing is selected for one or both of minimum noise and psycho-perceptual measures.

24. The apparatus of claim 22 wherein only selected bits of the digital stream are modified as determined by means for effecting pre-computation of the data embedding.

25. The apparatus of claim 23 wherein the encoding means is variable data rate encoding means responsive to psycho-perceptual measures to embed data at higher bit rates for the more robust portion of the media file, and at lower bit rates where the media file is more sensitive to the data embedding.

26. The apparatus of claim 25 wherein the media file is an audio file containing silent portions, and means is provided for embedding the data at the highest rate where the data embedding adds audible distortion to the silent portions.

27. The apparatus of claim 18 wherein the embedding is effected by an encoding means selected from the group consisting of encoders for parity encoding, higher-order parity encoding, variable data rate and variable length encoding, and black-box encoding.

28. The apparatus of claim 27 wherein the encoder is a black-box encoder wherein the embedding in the measurements is effected semi-independently of the details of the functional transformation means used to transform the measurements, through use of adaptive feedback means.

29. The apparatus of claim 18 wherein a decoder is provided adapted to extract the encoded measurement data by straightforward reversal of the encoding process effected by the encoder means.

30. The apparatus of claim 18 wherein from about 3 to about 25 percent of the successive components are modulated with supplemental data bits.

31. In a series of digital measurements derived from one of an analog data stream and subsampled and/or transformed digital data, a method of steganographically embedding substantial supplemental digital data representing from a few percent to a substantial percent of the series of digital measurements into the same, that comprises, deriving such series of digital measurements through functional transformation from a set of input data converted into a set of output data of successive quantized and/or aliased components;

transforming the substantial supplemental digital data into a series of successive bits; and

introducing the successive bits into the quantized and/or aliased components to modulate successive components through but slight adjustments of the same, thereby to embed the supplemental data in the series of digital measurements without substantially affecting the quality thereof, wherein the measurements represent a media file, and the embedded supplemental data provides additional content to the media file format in playback without changing that format and wherein the additional content is selected from the group consisting of an added high-bandwidth digital channel, ads, interactive ads, games, additional program materials, and subtitles and the media is audio, image or video, and further wherein the embedding is effected with least significant-bit parity encoding arranged to choose which measurement or component or coefficient representing the same is to be modified and by which bit, while only minimally affecting the accuracy.

32. The method of claim 31 wherein the measurements represent a media file and the supplemental data is embedded in from at least about 2 to about 9 percent of the media file content.

33. The method of claim 31 wherein from about 3 to about 25 percent of the successive components are modulated with supplemental data bits.

34. The method of claim 31 wherein the measurements represent an audio media file and said successive bits are introduced at rates of the order of thousands of bits per second and more into a media file encoded on the order of 100 kilobits per second and higher.

35. The method of steganographically embedding substantial supplemental digital data into a series of digital measurements representing a media file containing audio content derived from one of an analog data stream and subsampled and/or transformed digital data, that comprises, deriving such series of digital measurements through functional transformation from a set of input data converted into a set of output data of successive quantized and/or aliased components;

transforming the substantial supplemental digital data into a series of successive bits; and

introducing the successive bits at rates of the order of thousands of bits/second and more into the quantized and/or aliased components of the file to modulate successive components through but slight adjustments of the same, thereby to embed the supplemental data in the series of digital measurements of the media file without substantially affecting the quality thereof.

36. The method of claim 35 wherein the embedding is effected with least significant-bit parity encoding arranged to choose which measurement or component or coefficient representing the same is to be modified and by which bit, while only minimally affecting the accuracy.