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

• US 9,401,154 B2
• Filed: 04/14/2014
• Issued: 07/26/2016
• Est. Priority Date: 07/31/2000
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Shazam Ivestments Ltd. (Apple Inc.)
• Inventors: Wang, Avery Li-Chun, Smith, Julius O. III
• Primary Examiner(s): McFadden, Susan
• Application Number:
  US14/252,433
• Publication Number:
  US 20140316787A1
• Time in Patent Office: 834 Days
• Field of Search: 704/270
• US Class Current: 1/1
• 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 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.

Claims

1. A method performed by a computing device, the method comprising:

receiving a media sample;

determining, by the computing device, a time-frequency representation of the media sample;

determining, by the computing device, salient points in the time-frequency representation of the media sample; and

generating, by the computing device, fingerprints of the media sample based on combinations of the salient points.

2. The method of claim 1, wherein determining the salient points in the time-frequency representation of the media sample comprises determining local maxima in the time-frequency representation.

3. The method of claim 1, wherein determining the salient points in the time-frequency representation of the media sample comprises determining local minima in the time-frequency representation.

4. The method of claim 1, wherein determining the salient points in the time-frequency representation of the media sample comprises determining zero crossings in the time-frequency representation.

5. The method of claim 1, wherein determining the salient points in the time-frequency representation of the media sample comprises determining peaks in the time-frequency representation.

6. The method of claim 1, wherein determining the time-frequency representation of the media sample comprises determining windowed and overlapped frames of the media sample using a Fast Fourier Transform (FFT).

7. The method of claim 1, wherein determining the time-frequency representation of the media sample comprises determining a spectrogram of the media sample.

8. The method of claim 1, further comprising:

determining landmark and fingerprint pairs of the media sample from the salient points of the time-frequency representation, wherein a landmark indicates a timepoint at or near the salient points and a fingerprint is determined based on the given combination of the salient points.

9. The method of claim 1, wherein a given fingerprint includes a value that summarizes a set of features in the media sample at or near a given timepoint of the media sample.

10. The method of claim 1, wherein a given fingerprint is a single numerical value that is a hashed function of multiple features of the media sample.

11. The method of claim 1, further comprising:

converting the media sample into frequency transform frames at periodic time intervals; and

determining an energy density representation of the frequency transform frames; and

determining, for the salient points, the time-frequency coordinates corresponding to local maxima of the energy density representation.

12. The method of claim 1, further comprising:

identifying a selected data point in the time-frequency representation;

determining data points in the time-frequency representation that are energy maxima of the time-frequency representation over a neighborhood around the selected data point; and

identifying the selected data point as a given salient point in the time-frequency representation based on the selected data point being a maximum-energy data point within the neighborhood of data points.

13. The method of claim 1, further comprising:

determining data points in the time-frequency representation that are energy maxima of the time-frequency representation within a given time-frequency region; and

selecting a given data point of the data points as a given salient point in the time-frequency representation based on the given data point being a maximum-energy data point within the given time-frequency region.

14. The method of claim 1, further comprising:

determining additional data points in the time-frequency representation over a neighborhood around the salient points in the time-frequency representation;

applying weights to the additional data points so as to weight the additional data points inversely based on a distance metric in the time-frequency representation, wherein more distant data points have lower weighting; and

generating the fingerprints of the media sample based on the salient points and on the weighted additional data points in the time-frequency representation over the neighborhood around the salient points.

15. The method of claim 1, wherein generating the fingerprints of the media sample based on combinations of the salient points comprises:

linking N salient points;

selecting a time of a given salient point; and

hashing together time differences between times of the N salient points with frequencies of the N salient points to form a given fingerprint.

16. The method of claim 1, further comprising:

associating a given sound identifier with a given fingerprint; and

indexing the given fingerprint and the given sound identifier within a media database index.

17. The method of claim 1, wherein determining the salient points in the time-frequency representation of the media sample comprises:

determining, as the salient points, data points in the time-frequency representation of frequencies that are near each other.

18. The method of claim 17, wherein determining the data points in the time-frequency representation of frequencies that are near each other comprises determining the data points within a target zone defined by a given time-frequency region.

19. The method of claim 1, further comprising determining, as a given salient point, a frequency spectral slice of a strongest peak within a given time-frequency region.

20. The method of claim 1, wherein generating the fingerprints of the media sample based on combinations of the salient points comprises mapping sets of coordinate values into a fingerprint value.

21. A system, comprising:

a computing device; and

a memory, the memory configured to store instructions that when executed by the computing device cause the system to perform functions comprising;

receiving a media sample;

determining a time-frequency representation of the media sample;

determining salient points in the time-frequency representation of the media sample; and

generating fingerprints of the media sample based on combinations of the salient points.

22. The system of claim 21, wherein the functions further comprise:

converting the media sample into frequency transform frames; and

determining an energy density representation of the frequency transform frames at corresponding time intervals; and

determining, for the fingerprints, the frequency transform frames corresponding to local maxima of the energy density representation.

23. The system of claim 21, wherein determining the salient points in the time-frequency representation of the media sample comprises determining one of local maxima in the time-frequency representation, local minima in the time-frequency representation, and zero crossings in the time-frequency representation.

24. A non-transitory computer readable medium having stored there instructions, that when executed by a computing device, cause the computing device to perform functions comprising:

receiving a media sample;

determining a time-frequency representation of the media sample;

determining salient points in the time-frequency representation of the media sample; and

generating fingerprints of the media sample based on combinations of the salient points.

25. The non-transitory computer readable medium of claim 24, wherein determining the salient points in the time-frequency representation of the media sample comprises determining peaks in the time-frequency representation.

26. The non-transitory computer readable medium of claim 24, wherein determining the time-frequency representation of the media sample comprises determining a spectrogram of the media sample, and wherein a given fingerprint includes a value that summarizes a set of features in the media sample at or near a given timepoint of the media sample.