Robust and invariant audio pattern matching

• US 7,627,477 B2
• Filed: 10/21/2004
• Issued: 12/01/2009
• Est. Priority Date: 04/25/2002
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Landmark Digital Services LLC
• Inventors: Wang, Avery Li-Chun, Culbert, Daniel
• Primary Examiner(s): Chawan; Vijay B
• Application Number:
  US10/978,313
• Publication Number:
  US 20050177372A1
• Time in Patent Office: 1,867 Days
• Field of Search: 704/273, 704/217, 704/257, 704/224, 341/155, 341/110, 341/144, 386/104, 348/515, 348/464, 348/500
• US Class Current: 704/273
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G10H 1/00 Details of electrophonic musical instruments
• CPC Class Codes: G10H 2240/135 Library retrieval index, i.e. using an indexing scheme to efficiently retrieve a music piece
• CPC Class Codes: G10H 2240/141 Library retrieval matching, i.e. any of the steps of matching an inputted segment or phrase with musical database contents, e.g. query by humming, singing or playing; the steps may include, e.g. musical analysis of the input, musical feature extraction, query formulation, or details of the retrieval process
• CPC Class Codes: G10H 2250/235 Fourier transform; Discrete Fourier Transform [DFT]; Fast Fourier Transform [FFT]
• CPC Class Codes: G10L 15/02 Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/10 using distance or distortion measures between unknown speech and reference templates
• CPC Class Codes: G10L 15/20 Speech recognition techniques specially adapted for robustness in adverse environments, e.g. in noise, of stress induced speech G10L21/02 takes precedence

Abstract

The present invention provides an innovative technique for rapidly and accurately determining whether two audio samples match, as well as being immune to various kinds of transformations, such as playback speed variation. The relationship between the two audio samples is characterized by first matching certain fingerprint objects derived from the respective samples. A set (230) of fingerprint objects (231,232), each occurring at a particular location (242), is generated for each audio sample (210). Each location (242) is determined in dependence upon the content of the respective audio sample (210) and each fingerprint object (232) characterizes one or more local features (222) at or near the respective particular location (242). A relative value is next determined for each pair of matched fingerprint objects. A histogram of the relative values is then generated. If a statistically significant peak is found, the two audio samples can be characterized as substantially matching.

Claims

1. A method of characterizing a relationship between a first and a second audio sample, the method comprising:

generating a first set of fingerprint objects for the first audio sample, each fingerprint object occurring at a respective location within the first audio sample, the respective location being determined in dependence upon the content of the first audio sample, and each fingerprint object characterising one or more features of the first audio sample at or near each respective location;

generating a second set of fingerprint objects for the second audio sample, each fingerprint object occurring at a respective location within the second audio sample, the respective location being determined in dependence upon the content of the second audio sample, and each fingerprint object characterising one or more features of the second audio sample at or near each respective location;

pairing fingerprint objects by matching a first fingerprint object from the first audio sample with a second fingerprint object from the second audio sample that is substantially similar to the first fingerprint object;

generating, based on the pairing, a list of pairs of matched fingerprint objects;

determining a relative value for each pair of matched fingerprint objects;

generating a histogram of the relative values; and

searching for a statistically significant peak in the histogram, the peak characterizing the relationship between the first and second audio samples.

2. The method according to claim 1 in which the relationship between the first and second audio samples is characterized as substantially matching if a statistically significant peak is found.

3. The method according to claim 1 or 2, further comprising estimating a global relative value with a location of the peak on an axis of the histogram, the global relative value further characterizing the relationship between the first and second audio samples.

4. The method according to claim 3, further comprising determining a hyperfine estimate of the global relative value, wherein determining a hyperfine estimate of the global relative value comprises:

selecting a neighbourhood around the peak, and

calculating an average of the relative values in the neighbourhood.

5. The method according to claim 1 in which each fingerprint object has an invariant component, and the first and second fingerprint objects in each pair of matched fingerprint objects have matching invariant components.

6. The method according to claim 5 in which the invariant component is generated using at least one of:

(i) a ratio between a first and a second frequency values, each frequency value being respectively determined from a first and a second local features near the respective location of each fingerprint object;

(ii) a product between a frequency value and a delta time value, the frequency value being determined from a first local feature, and the delta time value being determined between the first local feature and a second local feature near the respective location of each fingerprint object; and

(iii) a ratio between a first and a second delta time values, the first delta time value being determined from a first and a second local features, the second delta time value being determined from the first and a third local features, each local feature being near the respective location of each fingerprint object.

7. The method according to claim 6 in which each local feature is a spectrogram peak and each frequency value is determined from a frequency coordinate of a corresponding spectrogram peak.

8. The method according to claim 1 or 5 in which each fingerprint object has a variant component, and the relative value of each pair of matched fingerprint objects is determined using respective variant components of the first and second fingerprint objects.

9. The method according to claim 8 in which the variant component is a frequency value determined from a local feature near the respective location of each fingerprint object such that the relative value of a pair of matched fingerprint objects being characterized as a ratio of respective frequency values of the first and second fingerprint objects and the peak in the histogram characterizing the relationship between the first and second audio samples being characterized as a relative pitch, or, in case of linear stretch, a relative playback speed.

10. The method according to claim 9, wherein the ratio of respective frequency values is characterized as being either a division or a difference of logarithms.

11. The method according to claim 9, in which each local feature is a spectrogram peak and each frequency value is determined from a frequency coordinate of a corresponding spectrogram peak.

12. The method according to claim 8, in which the variant component is a delta time value determined from a first and a second local features near the respective location of each fingerprint object such that the relative value of a pair of matched fingerprint objects being characterized as a ratio of respective variant delta time values and the peak in the histogram characterizing the relationship between the first and second audio samples being characterized as a relative playback speed, or, in case of linear stretch, a relative pitch.

13. The method according to claim 12, wherein the ratio of respective variant delta time values is characterized as being either a division or a difference of logarithms.

14. The method according to claim 12, in which each local feature is a spectrogram peak and each frequency value is determined from a frequency coordinate of a corresponding spectrogram peak.

15. The method according to claim 8, further comprising:

determining a relative pitch for the first and second audio samples using the respective variant components, wherein each variant component is a frequency value determined from a local feature near the respective location of each fingerprint object;

determining a relative playback speed for the first and second audio samples using the respective variant components, wherein each variant component is a delta time value determined from a first and a second local features near the respective location of each fingerprint object; and

detecting if the relative pitch and a reciprocal of the relative playback speed are substantially different, in which case the relationship between the first and second audio samples is characterized as nonlinear.

16. The method according to claim 1, wherein R is a relative playback speed value determined from the peak of the histogram of the relative values, and further comprising:

for each pair of matched fingerprint objects in the list, determining a compensated relative time offset value, t−

R*t′

, where t and t′

are locations in time with respect to the first and second fingerprint objects;

generating a second histogram of the compensated relative time offset values; and

searching for a statistically significant peak in the second histogram of the compensated relative time offset values, the peak further characterizing the relationship between the first and second audio samples.

17. A computer readable storage medium having stored thereon computer executable instructions for characterizing a relationship between a first and a second audio sample, the computer executable instructions comprising instructions for:

generating a first set of fingerprint objects for the first audio sample, each fingerprint object occurring at a respective location within the first audio sample, the respective location being determined in dependence upon the content of the first audio sample, and each fingerprint object characterising one or more features of the first audio sample at or near each respective location;

generating a second set of fingerprint objects for the second audio sample, each fingerprint object occurring at a respective location within the second audio sample, the respective location being determined in dependence upon the content of the second audio sample, and each fingerprint object characterising one or more features of the second audio sample at or near each respective location;

pairing fingerprint objects by matching a first fingerprint object from the first audio sample with a second fingerprint object from the second audio sample that is substantially similar to the first fingerprint object;

generating, based on the pairing, a list of pairs of matched fingerprint objects;

determining a relative value for each pair of matched fingerprint objects;

generating a histogram of the relative values; and

searching for a statistically significant peak in the histogram, the peak characterizing the relationship between the first and second audio samples.

18. A computer system for characterizing a relationship between a first and a second audio sample, the computer system comprising:

a client for sending information for use in characterizing the relationship between the first and second audio sample; and

a server that receives the information and characterizes the relationship between the first and the second audio sample, wherein the server comprises a processor that executes computer executable instructions, and wherein the computer executable instructions comprise instructions for;

generating a first set of fingerprint objects for the first audio sample, each fingerprint object occurring at a respective location within the first audio sample, the respective location being determined in dependence upon the content of the first audio pg,20 sample, and each fingerprint object characterising one or more features of the first audio sample at or near each respective location;

generating a second set of fingerprint objects for the second audio sample, each fingerprint object occurring at a respective location within the second audio sample, the respective location being determined in dependence upon the content of the second audio sample, and each fingerprint object characterising one or more features of the second audio sample at or near each respective location;

pairing fingerprint objects by matching a first fingerprint object from the first audio sample with a second fingerprint object from the second audio sample that is substantially similar to the first fingerprint object;

generating, based on the pairing, a list of pairs of matched fingerprint objects;

determining a relative value for each pair of matched fingerprint objects;

generating a histogram of the relative values; and

searching for a statistically significant peak in the histogram, the peak characterizing the relationship between the first and second audio samples.