System and methods for recognizing sound and music signals in high noise and distortion

• US 8,190,435 B2
• Filed: 11/24/2010
• Issued: 05/29/2012
• Est. Priority Date: 07/31/2000
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Shazam Ivestments Ltd. (Apple Inc.)
• Inventors: Li-Chun Wang, Avery, Smith, Julius O. III
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US12/954,004
• Publication Number:
  US 20110071838A1
• Time in Patent Office: 552 Days
• Field of Search: 704/273
• US Class Current: 704/270
• 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: G10L 15/26 Speech to text systems G10L15/08 takes precedence
• CPC Class Codes: G10L 17/26 Recognition of special voice characteristics, e.g. for use in lie detectors; Recognition of animal voices
• CPC Class Codes: G10L 19/018 Audio watermarking, i.e. embedding inaudible data in the audio signal
• CPC Class Codes: G10L 25/54 for retrieval
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence

Abstract

A method for recognizing an audio sample locates an audio file that most closely matches the audio sample from a database indexing a large set of original recordings. Each indexed audio file is represented in the database index by a set of landmark timepoints and associated fingerprints. Landmarks occur at reproducible locations within the file, while fingerprints represent features of the signal at or near the landmark timepoints. To perform recognition, landmarks and fingerprints are computed for the unknown sample and used to retrieve matching fingerprints from the database. For each file containing matching fingerprints, the landmarks are compared with landmarks of the sample at which the same fingerprints were computed. If a large number of corresponding landmarks are linearly related, i.e., if equivalent fingerprints of the sample and retrieved file have the same time evolution, then the file is identified with the sample. The method can be used for any type of sound or music, and is particularly effective for audio signals subject to linear and nonlinear distortion such as background noise, compression artifacts, or transmission dropouts. The sample can be identified in a time proportional to the logarithm of the number of entries in the database; given sufficient computational power, recognition can be performed in nearly real time as the sound is being sampled.

Claims

1. A method for characterizing a media sample, the method being implemented in a computer and comprising:

determining a first landmark and a second landmark via the computer, each landmark corresponding to a reproducible timepoint in the media sample;

determining a fingerprint, the fingerprint comprising a value corresponding to a vector between the first landmark and the second landmark; and

associating the fingerprint with the first landmark to form a landmark/fingerprint pair.

2. The method of claim 1, wherein determining the first landmark and the second landmark comprises calculating values of spectral components over multiple times slices of the media sample.

3. The method of claim 1, wherein determining the first landmark and the second landmark comprises calculating timepoints that occur at local maxima of spectral Lp norms of the media sample.

4. The method of claim 1, wherein the fingerprint comprises a second vector between the first landmark and a third landmark.

5. The method of claim 1, wherein the value corresponding to the vector is computed from a frequency analysis of the media sample.

6. The method of claim 1, wherein the value corresponding to the vector is computed from a spectrogram of the media sample.

7. The method of claim 1, further comprising associating a sound ID to the landmark/fingerprint pair to form a triplet.

8. A method for characterizing a media sample, the media sample being implemented in a computer and comprising:

landmarking the media sample via the computer to generate a list of reproducible timepoints;

determining a first vector between a first landmark and a second landmark;

determining a second vector between the first landmark and a third landmark;

constructing a fingerprint, the fingerprint comprising the first vector and the second vector; and

associating the fingerprint with the first landmark to a form a landmark/fingerprint pair.

9. The method of claim 8, wherein landmarking the media sample comprises calculating timepoints that occur at local maxima of spectral Lp norms of the media sample.

10. The method of claim 8, wherein the first vector is calculated by performing a frequency analysis of the media sample to determine distinctive features of the media sample.

11. The method of claim 8, wherein the first vector is calculated from a spectrogram of the media sample.

12. The method of claim 11, wherein the second vector is calculated from the spectrogram of the media sample.

13. The method of claim 8, further comprising generating a triplet by associating a sound ID with the landmark/fingerprint pair.

14. A method of characterizing a media sample, the method being implemented in a computer and comprising:

generating a spectrogram via the computer of the media sample;

identifying salient points, each salient point comprising at least a time coordinate and a frequency coordinate;

assigning at least one of the salient points as an anchor point;

determining a landmark from the time coordinate of the anchor point; and

determining a fingerprint.

15. The method of claim 14, wherein the salient points are distinctive features of the media sample selected from the group consisting of a local maxima, a local minima, and a zero crossing.

16. The method of claim 14, wherein determining the fingerprint comprises using the frequency coordinate of the anchor point.

17. The method of claim 14, further comprising generating a linked point by linking at least one of the salient points to the anchor point.

18. The method of claim 17, wherein determining the fingerprint comprises using the frequency coordinates of the salient anchor point and the linked point.

19. The method of claim 17, wherein determining the fingerprint comprises generating a timestretch invariant fingerprint using a quotient between the frequency coordinate of the linked point and the frequency coordinate of the anchor point.

20. The method of claim 14, wherein determining the fingerprint comprises hashing one or more dimensions of a salient point to form a multidimensional fingerprint.