MULTI-STAGE LOOKUP FOR ROLLING AUDIO RECOGNITION

• US 20110173185A1
• Filed: 01/13/2010
• Published: 07/14/2011
• Est. Priority Date: 01/13/2010
• Status: Abandoned Application

• Current Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Original Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Inventors: VOGEL, BRIAN KENNETH
• Application Number:
  US12/686,804
• Publication Number:
  US 20110173185A1
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/4387 by the use of playlists
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• 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: G06F 16/9014 hash tables

Abstract

A multi-stage lookup is performed by receiving a query fingerprint of an unknown recording, generating a hash value corresponding to the query fingerprint; generating a list of candidate matches of known recordings by comparing the hash value of the query fingerprint to a hash table containing multiple hash values corresponding to audio fingerprints of the known recordings, comparing maxima of the query fingerprint to the maxima of full-recording fingerprints of the known recordings contained in a full-recording fingerprint table to obtain an identifier corresponding to the unknown recording, and returning metadata based on the identifier.

Claims

1. A method for performing a multi-stage lookup, comprising the steps of:

receiving a query fingerprint of an unknown recording;

generating at least one hash value corresponding to the query fingerprint;

generating a list of candidate matches of known recordings by comparing the at least one hash value of the query fingerprint to a hash table containing a plurality of hash values corresponding to a plurality of audio fingerprints of the known recordings;

comparing maxima of the query fingerprint to the maxima of a plurality of full-recording fingerprints of the known recordings contained in a full-recording fingerprint table to obtain an identifier corresponding to the unknown recording; and

returning metadata based on the identifier.

2. The method of claim 1, wherein the list of candidate matches of known recordings includes at least one ordered pair having a unique identifier and a time offset value, wherein the unique identifier corresponds to a known recording of the plurality of known recordings and the time offset value corresponds to a hash value generated from the known recording.

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

selecting a subset of the plurality of full-recording fingerprints contained in the full-recording fingerprint table by using the list of candidate matches.

4. The method of claim 3, wherein comparing the maxima of the query fingerprint to the maxima of the plurality of full-recording fingerprints is performed on the subset of the plurality of full-recording fingerprints.

5. The method of claim 1, wherein a score is generated based on the comparing by:

forming a matrix from the query fingerprint, wherein the matrix is constructed such that element (i,j) takes the value one for each maximum in the query fingerprint at frequency bin “

i” and

time offset “

j” and

all other elements of the matrix are equal to zero;

performing a search in the full-recording fingerprint to obtain a time offset;

extracting maxima in the full-recording fingerprint within a time interval from matchTimeOffset_i to (matchTimeOffset_i+queryLength), where matchTimeOffset_i is a time offset within a known recording corresponding to an offset of the query fingerprint, and queryLength is the length of the query fingerprint; and

obtaining, for each of the maxima in an interval having a frequency bin, Bin_j, and time offset, tempOffset_j, a corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i), and

wherein, if the corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i) is equal to one, then the score is incremented, otherwise the score remains at a current value.

6. The method according to claim 5, further comprising the steps of:

adding the score for each one of the maxima in the time interval matchTimeOffset_i to (matchTimeOffset_i+queryLength) to form a current match score for a corresponding match candidate; and

dividing the current match score by queryLength, thereby specifying a number of maxima per second in the full-recording fingerprint found in a corresponding time interval of the query fingerprint.

7. A system for performing a multi-stage lookup, comprising:

at least one processor operable to;

receive a query fingerprint of an unknown recording;

generate at least one hash value corresponding to the query fingerprint;

generate a list of candidate matches of known recordings by comparing the at least one hash value of the query fingerprint to a hash table containing a plurality of hash values corresponding to a plurality of audio fingerprints of the known recordings;

compare maxima of the query fingerprint to the maxima of a plurality of full-recording fingerprints of the known recordings contained in a full-recording fingerprint table to obtain an identifier corresponding to the unknown recording; and

return metadata based on the identifier.

8. The system of claim 7, wherein the list of candidate matches of known recordings includes at least one ordered pair having a unique identifier and a time offset value, wherein the unique identifier corresponds to a known recording of the plurality of known recordings and the time offset value corresponds to a hash value generated from the known recording.

9. The system of claim 8, the at least one processor further operable to:

select a subset of the plurality of full-recording fingerprints contained in the full-recording fingerprint table by using the list of candidate matches.

10. The system of claim 9, wherein the at least one processor compares the maxima of the query fingerprint to the maxima of the plurality of full-recording fingerprints corresponding to the subset of the plurality of full-recording fingerprints.

11. The system of claim 7, wherein the at least one processor is further operable to:

generate a score by forming a matrix from the query fingerprint, wherein the matrix is constructed such that element (i,j) takes the value one for each maximum in the query fingerprint at frequency bin “

i” and

time offset “

j” and

all other elements of the matrix are equal to zero;

perform a search in the full-recording fingerprint to obtain a time offset;

extract maxima in the full-recording fingerprint within a time interval from matchTimeOffset_i to (matchTimeOffset_i+queryLength), where matchTimeOffset_i is a time offset within a known recording corresponding to an offset of the query fingerprint, and queryLength is the length of the query fingerprint; and

obtain, for each of the maxima in an interval having a frequency bin, Bin_j, and time offset, tempOffset_j, a corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i), and

wherein, if the corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i) is equal to one, then the score is incremented, otherwise the score remains at a current value.

12. The system according to claim 11, the at least one processor further operable to:

add the score for each one of the maxima in the time interval matchTimeOffset_i to (matchTimeOffset_i+queryLength) to form a current match score for a corresponding match candidate; and

divide the current match score by queryLength, thereby specifying a number of maxima per second in the full-recording fingerprint found in a corresponding time interval of the query fingerprint.

13. A 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:

receiving a query fingerprint of an unknown recording;

generating at least one hash value corresponding to the query fingerprint;

generating a list of candidate matches of known recordings by comparing the at least one hash value of the query fingerprint to a hash table containing a plurality of hash values corresponding to a plurality of audio fingerprints of the known recordings;

comparing maxima of the query fingerprint to the maxima of a plurality of full-recording fingerprints of the known recordings contained in a full-recording fingerprint table to obtain an identifier corresponding to the unknown recording; and

returning metadata based on the identifier.

14. The computer-readable medium of claim 13, wherein the list of candidate matches of known recordings includes at least one ordered pair having a unique identifier and a time offset value, wherein the unique identifier corresponds to a known recording of the plurality of known recordings and the time offset value corresponds to a hash value generated from the known recording.

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

selecting a subset of the plurality of full-recording fingerprints contained in the full-recording fingerprint table by using the list of candidate matches.

16. The computer-readable medium of claim 15, wherein comparing the maxima of the query fingerprint to the maxima of the plurality of full-recording fingerprints is performed on the subset of the plurality of full-recording fingerprints.

17. The computer-readable medium of claim 13, wherein a score is generated based on the comparing by:

forming a matrix from the query fingerprint, wherein the matrix is constructed such that element (i,j) takes the value one for each maximum in the query fingerprint at frequency bin “

i” and

time offset “

j” and

all other elements of the matrix are equal to zero;

performing a search in the full-recording fingerprint to obtain a time offset;

extracting maxima in the full-recording fingerprint within a time interval from matchTimeOffset_i to (matchTimeOffset_i+queryLength), where matchTimeOffset_i is a time offset within a known recording corresponding to an offset of the query fingerprint, and queryLength is the length of the query fingerprint; and

obtaining, for each of the maxima in an interval having a frequency bin, Bin_j, and time offset, tempOffset_j, a corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i), and

wherein, if the corresponding element (tempBin_j, tempOffset_j−

matchTimeOffset_i) is equal to one, then the score is incremented, otherwise the score remains at a current value.

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

adding the score for each one of the maxima in the time interval matchTimeOffset_i to (matchTimeOffset_i+queryLength) to form a current match score for a corresponding match candidate; and

dividing the current match score by queryLength, thereby specifying a number of maxima per second in the full-recording fingerprint found in a corresponding time interval of the query fingerprint.