Audio fingerprinting

• US 7,080,253 B2
• Filed: 07/08/2005
• Issued: 07/18/2006
• Est. Priority Date: 08/11/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weare, Christopher Bruce
• Primary Examiner(s): Moise, Emmanuel L.
• Assistant Examiner(s): Teslovich, Tamara
• Application Number:
  US11/177,083
• Publication Number:
  US 20050289065A1
• Time in Patent Office: 375 Days
• Field of Search: None
• US Class Current: 713/176
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal

Abstract

A system and methods for the creation, management, and distribution of media entity fingerprinting are provided. In connection with a system that convergently merges perceptual and digital signal processing analysis of media entities for purposes of classifying the media entities, various means are provided to a user for automatically processing fingerprints for media entities for distribution to participating users. Techniques for providing efficient calculation and distribution of fingerprints for use in satisfying copyright regulations and in facilitating the association of meta data to media entities are included. In an illustrative implementation, the fingerprints may be generated and stored allowing for persistence of media from experience to experience.

Claims

1. A method to calculate a fingerprint for media entities, comprising the steps of:

reading a predefined amount of data from an input media entity data file, the predefined amount of data corresponding to a specified position in said media entity data file;

windowing said predefined amount of data into a plurality of sequential chunks;

for each chunk of said plurality of sequential chunks, calculating a set of psycho-acoustic spectral coefficients;

preserving a set of energetic coefficients of the set of psycho-acoustic spectral coefficients according to at least one pre-defined criterion;

calculating the inverse Discrete Fourier Transform (DFT) to generate an estimate of the salient coefficients of the set of most energetic coefficients; and

storing the results of the DFT for the plurality of sequential chunks into a matrix F, wherein a first axis of said matrix F corresponds to a slice of time of said media entities and a second axis of said matrix F correspond to a frequency band of the psycho-acoustic frequency scale.

2. The method of claim 1, wherein said first axis corresponds to columns of the matrix F and said second axis corresponds to rows, and the method further comprising:

calculating the average of each row in said matrix F;

storing the results of said calculating in a vector F;

calculating the average of a subset of elements of each row in said matrix F;

storing the average of the subset of elements of each row in a vector S;

calculating a vector D such that D is the difference between F and S; and

quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

3. The method of claim 1, wherein said first axis corresponds to rows of the matrix F and said second axis corresponds to columns, and the method further comprising:

calculating the average of each row in said matrix F;

storing the results of said calculating in a vector F;

calculating the average of a subset of elements of each row in said matrix F;

storing the average of the subset of elements of each row in a vector S;

calculating a vector D such that D is the difference between F and S; and

quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

4. The method of claim 1, wherein said first axis corresponds to columns of the matrix F and said second axis corresponds to rows, and the method further comprising:

calculating the average of each column in said matrix F;

storing the results of said calculating in a vector F;

calculating the average of a subset of elements of each column in said matrix F;

storing the average of the subset of elements of each column in a vector S;

calculating a vector D such that D is the difference between F and S; and

quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

5. The method of claim 1, wherein said first axis corresponds to rows of the matrix F and said second axis corresponds to columns, and the method further comprising:

calculating the average of each column in said matrix F;

storing the results of said calculating in a vector F;

calculating the average of a subset of elements of each column in said matrix F;

storing the average of the subset of elements of each column in a vector S;

calculating a vector D such that D is the difference between F and S; and

quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

6. The method as recited in claim 2, further comprising:

assigning a fingerprint name to the calculated and quantized vector D; and

storing said vector D with said assigned fingerprint name in a cooperating fingerprint data store.

7. A computer readable medium bearing computer executable instructions for carrying out the method of claim 1.

8. A method for identifying an unknown media entity by employing media entity fingerprints of a plurality of media entities, comprising the steps of:

calculating a fingerprint for at least one media entity of said plurality of media entities, including;

reading a predefined amount of data from said at least one media entity, the predefined amount of data corresponding to a specified position in said at least one media entity;

windowing said predefined amount of data into a plurality of sequential chunks;

for each chunk of said plurality of sequential chunks,

calculating a set of psycho-acoustic spectral coefficients;

preserving a set of energetic coefficients of the set of psycho-acoustic spectral coefficients according to at least one pre-defined criterion;

calculating the inverse Discrete Fourier Transform (DFT) to generate an estimate of the salient coefficients of the set of most energetic coefficients;

storing the results of the DFT for the plurality of sequential chunks into a matrix F, wherein a first axis of said matrix F corresponds to a slice of time of said media entities and a second axis of said matrix F correspond to a frequency band of the psycho-acoustic frequency scale;

based upon the calculating of the fingerprint of the at least one media entity, obtaining a sequence having length L of n random bits representing said calculated fingerprint;

obtaining a sequence having a length L of N random bits of said unknown media entity for identification;

comparing said n bits with said N bits; and

evaluating the results of said comparing to determine an estimate of similarity.

9. The method as recited in claim 8, wherein said comparing step is based on a Hamming distance between each fingerprint bit and the corresponding unknown media entity bit to determine the probability that two corresponding bits differ by the Hamming distance according to the relation,

P(M)=e⁻

(M−

N/2)<sup>2/2σ

2</sup> /σ

√

{square root over (2π

)},

wherein σ

is the standard deviation of the distribution expressed as,

σ

=√

{square root over (N/2)}.

10. The method as recited in claim 9, further comprising the step of calculating the probability that the Hamming distance between two sequences of random bits is less than a value M′

according to the relation,

$P<br><br><br><br>\left(M<<br><br>M^{\mathrm{\prime <br><br>}}\right)={\int <br><br>}_0^{M^{\mathrm{\prime <br><br>}}-1}<br><br>{\mathrm{e<br><br>}}^{-{\left(x-N/2\right)}^2/2<br><br>{\mathrm{\sigma <br><br>}}^2}/\mathrm{\sigma <br><br>}<br><br>\sqrt{2<br><br>\mathrm{\pi <br><br>}}<br><br><br><br>d<br><br>x.$

11. A computer readable medium bearing computer executable instructions for carrying out the method of claim 8.

12. A system for calculating a fingerprint for media entities, comprising:

means for reading a predefined amount of data from an input media entity data file, the predefined amount of data corresponding to a specified position in said media entity data file;

means for windowing said predefined amount of data into a plurality of sequential chunks;

means for calculating a set of psycho-acoustic spectral coefficients for each chunk of said plurality of sequential chunks;

means for preserving a set of energetic coefficients of the set of psycho-acoustic spectral coefficients according to at least one pre-defined criterion;

means for calculating the inverse Discrete Fourier Transform (DFT) to generate an estimate of the salient coefficients of the set of most energetic coefficients; and

means for storing the results of the DFT for the plurality of sequential chunks into a matrix F, wherein a first axis of said matrix F corresponds to a slice of time of said media entities and a second axis of said matrix F correspond to a frequency band of the psycho-acoustic frequency scale.

13. The system of claim 12, wherein said first axis corresponds to columns of the matrix F and said second axis corresponds to rows, and the system further comprises:

means for calculating the average of each row in said matrix F;

means for storing the results of said calculating in a vector F;

means for calculating the average of a subset of elements of each row in said matrix F;

means for storing the average of the subset of elements of each row in a vector S;

means for calculating a vector D such that D is the difference between F and S; and

means for quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

14. The system of claim 12, wherein said first axis corresponds to rows of the matrix F and said second axis corresponds to columns, and the system further comprises:

means for calculating the average of each row in said matrix F;

means for storing the results of said calculating in a vector F;

means for calculating the average of a subset of elements of each row in said matrix F;

means for storing the average of the subset of elements of each row in a vector S;

means for calculating a vector D such that D is the difference between F and S; and

means for quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

15. The system of claim 12, wherein said first axis corresponds to columns of the matrix F and said second axis corresponds to rows, and the system further comprises:

means for calculating the average of each column in said matrix F;

means for storing the results of said calculating in a vector F;

means for calculating the average of a subset of elements of each column in said matrix F;

means for storing the average of the subset of elements of each column in a vector S;

means for calculating a vector D such that D is the difference between F and S; and

means for quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

16. The system of claim 12, wherein said first axis corresponds to rows of the matrix F and said second axis corresponds to columns, and the system further comprises:

means for calculating the average of each column in said matrix F;

means for storing the results of said calculating in a vector F;

means for calculating the average of a subset of elements of each column in said matrix F;

means for storing the average of the subset of elements of each column in a vector S;

means for calculating a vector D such that D is the difference between F and S; and

means for quantizing each element in D to a value of 1 if said each element value is greater than zero and to a value of 0 if said each element value is less than or equal to zero.

17. The system as recited in claim 13, further comprising:

means for assigning a fingerprint name to the calculated and quantized vector D; and

means for storing said vector D with said assigned fingerprint name in a cooperating fingerprint data store.