Randomized signal transforms and their applications

• US 7,770,014 B2
• Filed: 04/30/2004
• Issued: 08/03/2010
• Est. Priority Date: 04/30/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malkin, Michael T., Venkatesan, Ramarathnam
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Shaifer Harriman; Dant B
• Application Number:
  US10/837,563
• Publication Number:
  US 20050257060A1
• Time in Patent Office: 2,286 Days
• Field of Search: 713/176
• 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:

generating, by a computing device, a plurality of sets of basis functions, wherein each set of basis functions comprises a randlet transform, the plurality of sets of basis functions being generated based on a library of step-mother randlets, the step-mother randlets having in turn been generated from a mother randlet;

randomly selecting, by the computing device, at least one set of basis functions from the plurality of sets of generated basis functions based on a secret key, the secret key being used to seed a pseudo-random number generator to generate a random number, the random number being used to randomly select the at least one set of basis functions;

applying, by the computing device, the randomly selected set of basis functions to a signal; and

in response to the applying, outputting, by the computing device, the signal which results from the applying, whereby the outputted signal facilitates applications of randomized signal transforms.

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 two-dimensional and three-dimensional functions.

5. A method as recited in claim 1 further comprising compressing the signal, wherein the applications of randomized signal transforms include at least one of compressing, de-noising, hashing, identifying, authenticating, and watermarking.

6. A method as recited in claim 1, wherein the generating comprises randomly choosing a cardinality of the sets of basis functions to generate as part of the plurality of sets of basis functions.

7. A method as recited in claim 1, wherein the applying is characterized by applying the randomly selected set of basis functions to a signal as a discrete transform.

3. One or more non-transitory computer storage media having instructions stored thereon that, when executed, direct a machine to perform acts comprising:

generating a plurality of sets of basis functions, wherein each set of basis functions comprises a randlet transform, the plurality of sets of basis functions being generated based on a library of step-mother randlets, the step-mother randlets having in turn been generated from a mother randlet;

randomly selecting at least one set of basis functions from the plurality of sets of generated basis functions based on a secret key, the secret key being used to seed a pseudo-random number generator to generate a random number, the random number being used to randomly select the at least one set of basis functions;

applying the randomly selected set of basis functions to a signal; and

in response to the applying, outputting the signal which results from the applying, whereby the outputted signal facilitates applications of randomized signal transforms.

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

8. A method facilitating a transformation of a signal, the method comprising:

generating, by a computing device, a plurality of sets of basis functions, wherein each set of basis functions comprises a randlet transform and the generating comprises randomly choosing a cardinality of the sets of basis functions to generate as part of the plurality of sets of basis functions, the plurality of sets of basis functions being generated based on a library of step-mother randlets, the step-mother randlets having in turn been generated from a mother randlet;

randomly selecting, by the computing device, at least one set of basis functions from the plurality of sets of generated basis functions based on a secret key, the secret key being used to seed a pseudo-random number generator to generate a random number, the random number being used to randomly select the at least one set of basis functions;

applying, by the computing device, the randomly selected set of basis functions to a signal, wherein the applying is characterized by applying the randomly selected set of basis functions to the signal as a discrete transform; and

in response to the applying, outputting, by the computing device, the signal which results from the applying, whereby the outputted signal facilitates applications of randomized signal transforms, which comprise compression, de-noising, hashing, identification, authentication, data embedding, and watermarking.