Randomized signal transforms and their applications

• US 20050257060A1
• Filed: 04/30/2004
• Published: 11/17/2005
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Venkatesan, Ramarathnam, Malkin, Michael T.
• Granted Patent: US 7,770,014 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467
• CPC Class Codes: H04N 7/167 Systems rendering the television signal unintelligible and subsequently intelligible

Abstract

Techniques are disclosed to provide randomized signal transforms and/or their applications. More particularly, a signal (e.g., an audio signal, an image, or a video signal) is transformed by applying randomly-selected basis functions to the signal. The applications of the randomized signal transforms include, but are not limited to, compression, denoising, hashing, identification, authentication, and data embedding (e.g., watermarking).

Claims

1. A method comprising:

randomly selecting a plurality of generated basis functions; and

applying the randomly selected basis functions to a signal.

2. A method as recited by claim 1, wherein the basis functions are generated from a set of functions that are selected from one or more items of a group comprising one-dimensional, two-dimensional, and three-dimensional functions.

3. A method as recited by claim 1, wherein each of the basis functions is generated by an act selected from a group comprising scaling, rotating, translating, discretizing, and normalizing a mother randlet.

4. A method as recited by claim 3, wherein the basis functions are constrained by allowing only a finite set of scaling and rotation operations.

5. A method as recited by claim 3, wherein instead of defining each basis function independently of all others, a library of non-translated basis functions is generated by randomly scaling and rotating the mother randlets.

6. A method as recited by claim 3, wherein when scaling, a wavelet family is chosen.

7. A method as recited by claim 3, wherein the mother randlet is selected from a group comprising Gaussian, half, Mexican Hat, wavelet randlets, and combinations thereof.

8. A method as recited by claim 1, wherein the applying comprises:

projecting each selected basis function onto the signal;

subtracting each projection from the signal;

projecting each selected basis function onto a residue of the previous basis function;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

storing the quantized transform coefficients; and

computing a next residue.

9. A method as recited by claim 1, wherein the method is used for compressing the signal and the applying comprises:

projecting each selected basis function onto the signal;

subtracting each projection from the signal;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

eliminating select quantized transform coefficients; and

storing the quantized transform coefficients.

10. A method as recited by claim 1, wherein the method is used for denoising the signal by de-emphasizing relatively smaller basis functions and super-positioning remaining basis functions.

11. A method as recited by claim 1, wherein the method is used for hashing the signal and the applying comprises:

scaling the signal;

projecting each selected basis function onto the scaled signal;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

applying error correction to the quantized transform coefficients; and

storing the quantized transform coefficients.

12. A method as recited by claim 11, wherein a value of the hashed signal is utilized for identification or authentication.

13. A method as recited by claim 1, wherein the method is used for watermarking the signal and the applying comprises:

scaling the signal;

projecting each selected basis function onto the scaled signal;

computing a transform coefficient for each basis function;

applying a watermark to the transform coefficients; and

inserting the watermark into the signal.

14. A method as recited by claim 1, wherein the applying provides a transformed signal and the transformed signal is reconstructed by acts comprising:

multiplying each basis function by a corresponding transform coefficient; and

summing results of the multiplying.

15. A system comprising:

a randlet transform (RT) module to receive a signal and apply a plurality of randomly selected basis functions to the signal; and

a pseudorandom generator coupled to the RT module to generate a random number utilized by the RT module to select the randomly selected basis functions.

16. A system as recited by claim 15, wherein the pseudorandom generator utilizes a secret key as a seed to generate the random number.

17. A system as recited by claim 16, wherein the seed is a bit stream.

18. A system as recited by claim 15, wherein each of the basis functions is generated by scaling, rotating , translating, discretizing, and normalizing a mother randlet.

19. One or more computer-readable media having instructions stored thereon that, when executed, direct a machine to perform acts comprising:

randomly selecting a plurality of generated basis functions; and

applying the randomly selected basis functions to a signal.

20. One or more computer-readable media as recited by claim 19, wherein the basis functions are generated from a set of functions that are selected from one or more items of a group comprising one-dimensional, two-dimensional, and three-dimensional functions.

21. One or more computer-readable media as recited by claim 19, wherein each of the basis functions is generated by scaling, rotating, translating, discretizing, and normalizing a mother randlet.

22. One or more computer-readable media as recited by claim 21, wherein the basis functions are constrained by allowing only a finite set of scaling and rotation operations.

23. One or more computer-readable media as recited by claim 21, wherein instead of defining each basis function independently of all others, a library of non-translated basis functions is generated by randomly scaling and rotating the mother randlets.

24. One or more computer-readable media as recited by claim 21, wherein when scaling, a wavelet family is chosen.

25. One or more computer-readable media as recited by claim 21, wherein the mother randlet is selected from a group comprising Gaussian, half, Mexican Hat, wavelet randlets, and combinations thereof.

26. One or more computer-readable media as recited by claim 19, wherein the applying comprises:

projecting each selected basis function onto the signal;

subtracting each projection from the signal;

projecting each selected basis function onto a residue of the previous basis function;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

storing the quantized transform coefficients; and

computing a next residue.

27. One or more computer-readable media as recited by claim 19, wherein the acts are used for compressing the signal and the applying comprises:

projecting each selected basis function onto the signal;

subtracting each projection from the signal;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

eliminating select quantized transform coefficients; and

storing the quantized transform coefficients.

28. One or more computer-readable media as recited by claim 19, wherein the acts are used for denoising the signal by de-emphasizing relatively smaller basis functions and super-positioning remaining basis functions.

29. One or more computer-readable media as recited by claim 19, wherein the acts are used for hashing the signal and the applying comprises:

scaling the signal;

projecting each selected basis function onto the scaled signal;

computing a transform coefficient for each basis function;

quantizing the transform coefficients;

applying error correction to the quantized transform coefficients; and

storing the quantized transform coefficients.

30. One or more computer-readable media as recited by claim 29, wherein a value of the hashed signal is utilized for identification or authentication.

31. One or more computer-readable media as recited by claim 19, wherein the acts are used for watermarking the signal and the applying comprises:

scaling the signal;

projecting each selected basis function onto the scaled signal;

computing a transform coefficient for each basis function;

applying a watermark to the transform coefficients; and

inserting the watermark into the signal.

32. One or more computer-readable media as recited by claim 19, wherein the applying provides a transformed signal and the transformed signal is reconstructed by acts comprising:

multiplying each basis function by a corresponding transform coefficient; and

summing results of the multiplying.