Hash value computer of content of digital signals

• US 7,240,210 B2
• Filed: 11/04/2004
• Issued: 07/03/2007
• Est. Priority Date: 04/24/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mihcak, M. Kivanc, Venkatesan, Ramarathnam
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): Dinh, Minh
• Application Number:
  US10/980,919
• Publication Number:
  US 20050065974A1
• Time in Patent Office: 971 Days
• Field of Search: 713/176, 713180-181, 704/203, 704/230, 704269-270, 382/100, 382/232, 382/248, 382/251
• US Class Current: 713/180
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G10H 1/0058 Transmission between separate instruments or between individual components of a musical system G10H1/0083 takes precedence

Abstract

Described herein is a technology for facilitating the recognition of the content of digital signals. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Claims

1. A computer-implemented hashing method, comprising:

transforming a digital signal into a digital signal transform;

computing a first hash value representative of the digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values, wherein the computing of the first hash value comprises;

obtaining the digital signal transform of the digital signal;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

computing a second hash value representative of the digital signal such that perceptually distinct digital signals result in second hash values that are approximately independent of one another and perceptually same digital signals result in identical second hash values, wherein the computing of the second hash value comprises;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values; and

storing the first and second hash values in relationship with the digital signal.

2. A computer-implemented method as recited in claim 1, wherein the digital signals are selected from a group consisting of digital audio signals, digital image signals, digital video signals, and digital multimedia signals.

3. A system for processing digital signals, comprising:

a digital signal hashing unit configured to compute at least two hash values, wherein;

a first hash value is representative of a digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values and

a second hash value is representative of the digital signal such that perceptually distinct digital signals result in second hash values that are approximately independent of one another and perceptually same digital signals result in identical second hash values; and

a storage to hold the first and second hash values;

wherein the digital signal hashing unit is further configured to compute the first hash value by;

transforming the digital signal into a digital signal transform;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

wherein the digital signal hashing unit is further configured to compute the second hash value by;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values.

4. A system as recited in claim 3, wherein the digital signals are selected from a group consisting of digital audio signals, digital image signals, digital video signals, and digital multimedia signals.

5. One or more computer-storage media having computer-executable instructions, which when executed on a processor, direct a computer to:

transform a digital signal into a digital signal transform;

compute a first hash value representative of the digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values, wherein the computer computes of the first hash value by;

obtaining the digital signal transform of the digital signal;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

compute a second hash value representative of the digital signal such that perceptually distinct digital signals result in second hash values that are approximately independent of one another and perceptually same digital signals result in identical second hash values, wherein the computer computes of the second hash value by;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values; and

store the first and second hash values in relationship with the digital signal.

6. A computer-implemented hashing method, comprising acts of:

transforming a digital signal into a digital signal transform;

computing a first hash value representative of the digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values, wherein the computing of the first hash value comprises;

obtaining the digital signal transform of the digital signal;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

computing a second hash value representative of the digital signal based upon intrinsic characteristics of the digital signal, wherein perceptually distinct digital signals have computed second hash values that are approximately independent of one another and perceptually same digital signals have computed second hash values are substantially identical, wherein the computing of the second hash value comprises;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values;

storing the first and second hash values in relationship with the digital signal.

7. A computer-implemented method as recited in claim 6, wherein the digital signals are selected from a group consisting of digital audio signals, digital image signals, digital video signals, and digital multimedia signals.

8. A computer-implemented method as recited in claim 6 further comprising indexing the digital signal using the first and second hash values.

9. A computer-implemented method as recited in claim 6 further comprising watermarking the digital signal using, in part, the second hash value to produce a watermarked digital signal.

10. One or more computer-storage media having a tangible component and having computer-executable instructions, which when executed on a computer, perform acts comprising:

transforming a digital signal into a digital signal transform;

computing a first hash value representative of the digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values, wherein the computing of the first hash value comprises;

obtaining the digital signal transform of the digital signal;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

computing a second hash value representative of the digital signal based upon intrinsic characteristics of the digital signal, wherein perceptually distinct digital signals have computed second hash values that are approximately independent of one another and perceptually same digital signals have computed second hash values are substantially identical, wherein the computing of the second hash value comprises;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values;

storing the first and second hash values in relationship with the digital signal.

11. One or more computer-storage as recited in claim 10, wherein the digital signals are selected from a group consisting of digital audio signals, digital image signals, digital video signals, and digital multimedia signals.

12. One or more computer-storage as recited in claim 10 further comprising indexing the digital signal using the first and second hash values.

13. One or more computer-storage as recited in claim 10 further comprising watermarking the digital signal using, in part, the second hash value to produce a watermarked digital signal.

14. A system comprising:

first computing means for computing a first hash value representative of a digital signal such that perceptually distinct digital signals result in first hash values that are approximately independent of one another and perceptually similar digital signals result in proximal first hash values, wherein the computing of the first computing means comprises;

obtaining a digital signal transform of the digital signal;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

based upon the geometrical-region-grown digital signal transform, generating the first hash value;

second computing means for computing a second hash value representative of the digital signal based upon intrinsic characteristics of the digital signal, wherein perceptually distinct digital signals have computed second hash values that are approximately independent of one another and perceptually same digital signals have computed second hash values are substantially identical, wherein the computing of the second computing means comprises;

obtaining the digital signal transform of the digital signal;

randomly dividing the digital signal transform into multiple chunks, each chunk containing signal data, wherein the dividing is carried out recursively to form hierarchical levels of overlapping chunks;

averaging, for each of the chunks, the signal data to produce corresponding chunk averages;

generating, based in part on the chunk averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the chunk averages to one of the quantization levels to produce rounded values;

hashing a composite of the rounded values;

storing means for storing the first and second hash values in relationship with the digital signal.

15. A system as recited in claim 14, wherein the digital signals are selected from a group consisting of digital audio signals, digital image signals, digital video signals, and digital multimedia signals.