Unordered matching of audio fingerprints

• US 10,540,395 B2
• Filed: 07/17/2018
• Issued: 01/21/2020
• Est. Priority Date: 05/06/2013
• Status: Active Grant

• Current Assignee: iHeartMedia Management Services, Inc. (iHeartMedia, Inc.)
• Original Assignee: iHeartMedia Management Services, Inc. (iHeartMedia, Inc.)
• Inventors: Anniballi, Dyon
• Primary Examiner(s): King, Simon
• Application Number:
  US16/037,346
• Publication Number:
  US 20180322191A1
• Time in Patent Office: 553 Days
• CPC Class Codes: G06F 16/638 Presentation of query results
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content

Abstract

A method includes computing match scores for each portion of multiple portions of a first audio fingerprint. The match scores are based on a comparison of the portion with each of multiple portions of a second audio fingerprint. The method includes applying a positional penalty to a highest score of the match scores for a portion of the first audio fingerprint and generating a list of runs based on the highest score for each portion of the multiple portions of the first audio fingerprint. The method includes determining, based on the list of runs, an unordered match between a set of consecutive portions of the first audio fingerprint and a set of non-consecutive portions of the second audio fingerprint. The method includes, in response to determining that a length of the unordered match satisfies a length criterion, outputting an indicator that the first audio fingerprint matches the second audio fingerprint.

Claims

1. A method comprising:

computing, at a processor of a device, match scores for each portion of multiple portions of a first audio fingerprint, the match scores for a particular portion based on a comparison of the particular portion with each of multiple portions of a second audio fingerprint;

identifying, at the processor, a highest score of the match scores for each portion of the multiple portions of the first audio fingerprint;

applying, at the processor, a positional penalty to the highest score of the match scores for a first portion of the first audio fingerprint;

generating, at the processor, a list of runs based on the highest score for each portion of the multiple portions of the first audio fingerprint;

determining, based on the list of runs, an unordered match between a set of consecutive portions of the first audio fingerprint and a set of non-consecutive portions of the second audio fingerprint; and

in response to determining that a length of the unordered match satisfies a length criterion, outputting an indicator that the first audio fingerprint matches the second audio fingerprint.

2. The method of claim 1, wherein the positional penalty is applied in response to determining that the highest scores of the match scores for a first set of consecutive portions of the first audio fingerprint correspond to a first set of non-consecutive portions of the second audio fingerprint, and wherein the first set of consecutive portions includes the first portion of the first audio fingerprint.

3. The method of claim 1, wherein the match scores for the first portion of the first audio fingerprint include a first score corresponding to a first portion of the second audio fingerprint, wherein the first score is the highest score of the match scores for the first portion of the first audio fingerprint, and wherein applying the positional penalty includes updating the match scores for the first portion of the first audio fingerprint by reducing the first score corresponding to the first portion of the second audio fingerprint.

4. The method of claim 3, further comprising, subsequent to updating the match scores for the first portion of the first audio fingerprint, identifying an updated highest score of the match scores for each portion of the multiple portions of the first audio fingerprint, wherein the list of runs is based on the updated highest score for each portion of the multiple portions of the first audio fingerprint.

5. The method of claim 1, wherein determining the unordered match includes determining that at least one match score corresponding to each portion of the set of consecutive portions of the first audio fingerprint and a corresponding portion of the set of non-consecutive portions of the second audio fingerprint satisfies a similarity threshold.

6. The method of claim 1, further comprising, prior to determining the unordered match:

determining that a number of portions of the first audio fingerprint have a highest match score corresponding to a first particular portion of the second audio fingerprint; and

in response to determining that the number of portions exceeds a threshold, removing a particular match score corresponding to the first particular portion of the second audio fingerprint from the match scores.

7. The method of claim 1, wherein the length criterion is user-configurable.

8. The method of claim 1, further comprising receiving the first audio fingerprint from a listening device, wherein the indicator includes data indicating a station associated with the second audio fingerprint, a timestamp corresponding to the first audio fingerprint, a user identifier associated with the listening device, or a combination thereof, and wherein the listening device comprises a microphone, a mobile device, a personal media monitor, or any combination thereof.

9. The method of claim 1, further comprising:

receiving the second audio fingerprint from a field recorder; and

storing the second audio fingerprint.

10. The method of claim 1, further comprising selecting a probe from the second audio fingerprint, wherein the match scores are computed in response to determining that the probe substantially matches at least one portion of the first audio fingerprint.

11. The method of claim 10, wherein the probe comprises sixteen audio samples that are each one tenth of a second in length.

12. The method of claim 1, wherein:

the list of runs includes alternating below-threshold runs and above-threshold runs,

each below-threshold run corresponds to a sequence of one or more of the multiple portions of the first audio fingerprint that have a highest score that is less than a similarity threshold, and

each above-threshold run corresponds to a sequence of one or more of the multiple portions of the first audio fingerprint that have a highest score that is greater than or equal to the similarity threshold, wherein the unordered match is based on determining that a longest above-threshold run in the list of runs corresponds to the set of consecutive portions of the first audio fingerprint and to the set of non-consecutive portions of the second audio fingerprint.

13. The method of claim 12, further comprising replacing a below-threshold run in the list of runs with an aggregate of the below-threshold run and neighboring above-threshold runs in response to determining that the aggregate has an average match score that is greater than or equal to the similarity threshold.

14. The method of claim 12, further comprising replacing an above-threshold run in the list of runs with an aggregate of the above-threshold run and neighboring below-threshold runs in response to determining that the aggregate has an average match score that is less than the similarity threshold.

15. The method of claim 1, further comprising determining the length of the unordered match based on a size of each portion of the set of consecutive portions of the first audio fingerprint and a count of portions in the set of consecutive portions of the first audio fingerprint.

16. The method of claim 1, further comprising, in response to determining that the length of the unordered match satisfies the length criterion, updating a count indicating a number of times media content has been played over a time period, wherein the second audio fingerprint represents the media content.

17. An apparatus comprising:

a communication interface configured to receive a first audio fingerprint from a listening device; and

a processor configured to;

compute match scores for each portion of multiple portions of the first audio fingerprint, the match scores for a particular portion based on a comparison of the particular portion with each of multiple portions of a second audio fingerprint;

identify a highest score of the match scores for each portion of the multiple portions of the first audio fingerprint;

apply a positional penalty to the highest score of the match scores for a first portion of the first audio fingerprint;

generate a list of runs based on the highest score for each portion of the multiple portions of the first audio fingerprint;

determine, based on the list of runs, an unordered match between a set of consecutive portions of the first audio fingerprint and a set of non-consecutive portions of the second audio fingerprint; and

in response to determining that a length of the unordered match satisfies a length criterion, generate an indicator that the first audio fingerprint matches the second audio fingerprint.

18. The apparatus of claim 17, wherein the length criterion is based at least in part on a programming element represented by the second audio fingerprint, wherein the programming element comprises an advertisement programming element or a song programming element.

19. A computer-readable storage device storing instructions that, when executed by a computer, cause the computer to perform operations comprising:

computing match scores for each portion of multiple portions of a first audio fingerprint, the match scores for a particular portion based on a comparison of the particular portion with each of multiple portions of a second audio fingerprint;

identifying a highest score of the match scores for each portion of the multiple portions of the first audio fingerprint;

applying a positional penalty to the highest score of the match scores for a first portion of the first audio fingerprint;

generating a list of runs based on the highest score for each portion of the multiple portions of the first audio fingerprint;

determining, based on the list of runs, an unordered match between a set of consecutive portions of a first audio fingerprint and a set of non-consecutive portions of the second audio fingerprint; and

in response to determining that a length of the unordered match satisfies a length criterion, outputting an indicator that the first audio fingerprint matches the second audio fingerprint.

20. The computer-readable storage device of claim 19, wherein the operations further comprise:

in response to determining that a first station is associated with the second audio fingerprint, setting the length criterion to indicate a first length; and

in response to determining that a second station is associated with the second audio fingerprint, setting the length criterion to indicate a second length.