Apparatus and method for generating an audio fingerprint and using a two-stage query

• US 8,886,531 B2
• Filed: 01/13/2010
• Issued: 11/11/2014
• Est. Priority Date: 01/13/2010
• Status: Active Grant

• Current Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Original Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Inventors: Vogel, Brian Kenneth
• Primary Examiner(s): He, Jialong
• Application Number:
  US12/686,779
• Publication Number:
  US 20110173208A1
• Time in Patent Office: 1,763 Days
• Field of Search: 704/273, 704/270, 704/275, 726 26- 32, 707/770, 707/736
• US Class Current: 704/239
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G10L 25/48 specially adapted for particular use

Abstract

An audio fingerprint is generated by transforming an audio sample of a recording to a time-frequency domain and storing each time-frequency pair in a matrix array, detecting a plurality of local maxima for a predetermined number of time slices, selecting a predetermined number of largest-magnitude maxima from the plurality of local maxima detected by said detecting, and generating one or more hash values corresponding to the predetermined number of largest-magnitude maxima.

Claims

1. A method comprising:

transforming a sample of a recording to a time-frequency domain and storing each time-frequency pair in a matrix array;

setting all elements of the matrix array that are below a predetermined noise floor to zero and setting all elements of the matrix array that are outside a predetermined frequency range to zero;

detecting a plurality of local maxima for a predetermined number of time slices;

selecting a predetermined number of largest-magnitude maxima from the plurality of local maxima detected by said detecting;

generating one or more hash values corresponding to the predetermined number of largest-magnitude maxima;

comparing the one or more hash values to corresponding hash values of known recordings in a first stage query to identify a set of possible matches; and

comparing the set of possible matches to a full-recording fingerprint of the sample in a second stage query, the full-recording fingerprint being a recording fingerprint of a substantial length or the entire length of a known recording.

2. The method of claim 1, further comprising the steps of:

grouping the plurality of local maxima detected by said detecting in accordance with a time-slice interval; and

grouping a plurality of time-slices intervals, thereby defining a sub-spectrogram.

3. The method of claim 2, further comprising the step of:

determining a predetermined number of highest magnitude local maxima within each sub-spectrogram.

4. The method of claim 3, wherein determining of the predetermined number of highest magnitude local maxima includes:

sorting the plurality of local maxima within each sub-spectrogram in either descending or ascending magnitude; and

selecting a predetermined number of the largest-magnitude maxima.

5. The method of claim 1, further comprising the step of:

storing each maxima in a data structure according to a time index, a frequency index and a magnitude of each maxima.

6. The method of claim 5, further comprising the step of:

generating a hash value based on at least a portion of each maxima stored in the data structure.

7. The method of claim 1, further comprising the step of:

performing noise filtering of the predetermined number of highest magnitude local maxima.

8. An apparatus comprising:

at least one processor configured to;

transform a sample of a recording to a time-frequency domain and storing each time-frequency pair in a matrix array;

set all elements of the matrix array that are below a predetermined noise floor to zero and set all elements of the matrix array that are outside a predetermined frequency range to zero;

detect a plurality of local maxima for a predetermined number of time slices;

select a predetermined number of largest-magnitude maxima from the plurality of local maxima detected by said detection;

generate one or more hash values corresponding to the predetermined number of largest-magnitude maxima;

compare the one or more hash values to corresponding hash values of known recordings in a first stage query to identify a set of possible matches; and

compare the set of possible matches to a full-recording fingerprint of the sample in a second stage query, the full-recording fingerprint being a recording fingerprint of a substantial length or the entire length of a known recording.

9. The apparatus of claim 8, further comprising:

the at least one processor further configured to;

group the plurality of local maxima detected by said detecting in accordance with a time-slice interval; and

group a plurality of time-slices intervals, thereby defining a sub-spectrogram.

10. The apparatus of claim 9, wherein the at least one processor is further configured to determine a predetermined number of highest magnitude local maxima within each sub-spectrogram.

11. The apparatus of claim 10, wherein the predetermined number of highest magnitude local maxima are determined by:

sorting the plurality of local maxima within each sub-spectrogram in either descending or ascending magnitude; and

selecting a predetermined number if the largest-magnitude maxima.

12. The apparatus of claim 8, further comprising:

a storage device configured to store each maxima in a data structure according to a time index, a frequency index and a magnitude of each maxima.

13. The apparatus of claim 12, wherein the at least one processor is further configured to generate a hash value based on at least a portion of each maxima stored in the data structure.

14. The apparatus of claim 8, further comprising:

a noise filter operable to perform noise filtering of the predetermined number of highest magnitude local maxima.

15. A non-transitory computer-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions which when executed by a computer system causes the computer system to perform:

transforming a sample of a recording to a time-frequency domain and storing each time-frequency pair in a matrix array;

setting all elements of the matrix array that are below a predetermined noise floor to zero and setting all elements of the matrix array that are outside a predetermined frequency range to zero;

detecting a plurality of local maxima for a predetermined number of time slices;

selecting a predetermined number of largest-magnitude maxima from the plurality of local maxima detected by said detecting;

generating one or more hash values corresponding to the predetermined number of largest magnitude maxima;

comparing the one or more hash values to corresponding hash values of known recordings in a first stage query to identify a set of possible matches; and

comparing the set of possible matches to a full-recording fingerprint of the sample in a second stage query, the full-recording fingerprint being a recording fingerprint of a substantial length or the entire length of a known recording.

16. The computer-readable medium of claim 15, further having stored thereon a sequence of instructions which when executed by the computer system causes the computer system to perform:

grouping the plurality of local maxima detected by said detecting in accordance with a time-slice interval; and

grouping a plurality of time-slices intervals, thereby defining a sub-spectrogram.

17. The computer-readable medium of claim 16, further having stored thereon a sequence of instructions which when executed by the computer system causes the computer system to perform:

determining as predetermined number of highest magnitude local maxima within each sub-spectrogram.

18. The computer-readable medium of claim 17, wherein determining of the predetermined number of highest magnitude local maxima includes:

sorting the plurality of local maxima within each sub-spectrogram in either descending or ascending magnitude; and

selecting a predetermined number of the largest-magnitude maxima.

19. The computer-readable medium of claim 15, further having stored thereon as sequence of instructions which when executed by the computer system causes the computer system to perform:

storing each maxima in a data structure according to it time index, a frequency index and a magnitude of each maxima.

20. The computer-readable medium of claim 19, further having stored thereon a sequence of instructions which when executed by the computer system causes the computer system to perform:

generating a hash value based on at least a portion of each maxima stored in the data structure.

21. The computer-readable medium of claim 15, further having stored thereon a sequence of instructions which when executed by the computer system causes the computer system to perform:

performing noise filtering of the predetermined number of highest magnitude local maxima.