Automatic identification of sound recordings

• US 7,328,153 B2
• Filed: 07/22/2002
• Issued: 02/05/2008
• Est. Priority Date: 07/20/2001
• Status: Active Grant

• Current Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Original Assignee: Gracenote, Inc. (RR Donnelley & Sons Company)
• Inventors: Cheung, Kwan Fai, Cazzanti, Luca, Sukittanon, Somsak, Venkatachalam, Vidya, Dhillon, Navdeep, Wells, Maxwell
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Application Number:
  US10/200,034
• Publication Number:
  US 20030086341A1
• Time in Patent Office: 2,024 Days
• Field of Search: 704/243, 704/246, 704/245, 704/251, 704/231, 704/238, 704/270
• US Class Current: 704/231
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• 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

Abstract

Copies of original sound recordings are identified by extracting features from the copy, creating a vector of those features, and comparing that vector against a database of vectors. Identification can be performed for copies of sound recordings that have been subjected to compression and other manipulation such that they are not exact replicas of the original. Computational efficiency permits many hundreds of queries to be serviced at the same time. The vectors may be less than 100 bytes, so that many millions of vectors can be stored on a portable device.

Claims

1. A method of identifying digital recordings, comprising:

extracting at least one candidate fingerprint from at least one portion of an unidentified recording, each candidate fingerprint including a predetermined number of candidate values for corresponding frequency ranges and each reference fingerprint including the predetermined number of reference values for the corresponding frequency ranges; and

searching for a match between at least one candidate value derived from the at least one candidate fingerprint and at least one reference value in at least one reference fingerprint among a plurality of reference fingerprints, by determining whether each candidate fingerprint matches one of the reference fingerprints based on selectively weighted differences between corresponding candidate and reference values for different frequency ranges.

2. A method as recited in claim 1, wherein said searching comprises computing at least one weighted absolute difference between the at least one candidate fingerprint and the at least one reference fingerprint using a weight based on a value derived from the at least one candidate fingerprint.

3. A method as recited in claim 1, further comprising prior to said extracting, expanding dynamic range of the at least one portion of the unidentified recording.

4. A method as recited in claim 3, wherein said expanding of the dynamic range makes all sample values within the at least one portion of an unidentified recording more equally likely.

5. A method as recited in claim 1, further comprising:

storing in a cache memory matched candidate fingerprints with identifiers of corresponding reference fingerprints; and

determining whether a new candidate fingerprint is included in the matched candidate fingerprints in the cache memory prior to said searching using the new candidate fingerprint.

6. A method as recited in claim 5, further comprising:

indicating a match between the new candidate fingerprint and a corresponding reference fingerprint when the new candidate fingerprint is included in the matched candidate fingerprints in the cache memory; and

adding the new candidate fingerprint to the cache memory and associating a corresponding identifier for the corresponding reference fingerprint with new candidate fingerprint in the cache memory.

7. A method as recited in claim 1, further comprising generating each of the candidate and reference fingerprints to include values representing a magnitude of power at frequencies in frequency ranges with mid-range frequencies weighted less than high- and low-range frequencies.

8. A method as recited in claim 1, wherein generation of each of the candidate and reference fingerprints comprises:

computing power in each of a plurality of frequency bands; and

normalizing the power for each frequency within each band so that a mean of the power within each band is equal to a predetermined value.

9. A method as recited in claim 1, wherein generation of each of the candidate and reference fingerprints comprises computing a frequency distribution within each of a plurality of different frequency bands using a finer resolution at lower frequency bands than at higher frequency bands.

10. A method as recited in claim 1,

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings,

wherein said extracting produces a plurality of candidate fingerprints from successive frames at a regular time interval, and

wherein said searching identifies the unidentified recording as corresponding to a single reference recording only if matches are found between the reference fingerprints from the single reference recording and the candidate fingerprints obtained from a predetermined number of the successive frames.

11. A method as recited in claim 1,

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings,

wherein said extracting produces a plurality of candidate fingerprints, and

wherein said searching comprises:

finding a first match between a first candidate fingerprint and one of the reference fingerprints for a potentially matching reference recording; and

comparing other candidate fingerprints from the unknown recording with the reference fingerprints for the potentially matching reference recording until a predetermined number of matches are found.

12. A method as recited in claim 1

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings, and

wherein said searching includes all of the reference fingerprints, unless a match is found.

13. A method as recited in claim 1, further comprising generating the reference fingerprints for reference recordings by

extracting a principal fingerprint from a specified portion of each reference recording;

extracting auxiliary fingerprints from the reference recording at a regular time interval;

computing distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

generating a song profile based on the distance measures; and

storing the principal fingerprint combined with the song profile as the reference fingerprint for the reference recording.

14. A method as recited in claim 1, wherein said extracting comprises:

separating the at least one portion of the unidentified recording into frequency bands;

computing power spectra for the frequency bands, respectively; and

computing at least one value from each power spectra.

15. A method as recited in claim 14, wherein the frequency bands are output from filters derived from one prototype filter corresponding to an analysis wavelet.

16. A method as recited in claim 15, wherein a ratio of bandwidth to center frequency is substantially identical for all of the filters.

17. A method as recited in claim 1, wherein each of the candidate and reference fingerprints include a vector of at least 5 elements having at least 256 values each.

18. A method as recited in claim 17, wherein each of the candidate and reference fingerprints include a vector of up to 38 elements having no more than 65,536 values each.

19. A method as recited in claim 18, wherein each of the candidate and reference fingerprints include a vector of approximately 30 elements of approximately 16 bits each.

20. A method as recited in claim 1, wherein said extracting produces a plurality of candidate fingerprints, each from different copies corresponding to a single reference recording, at least one of the different copies having been modified prior to said extracting.

21. A method as recited in claim 20, wherein the at least one of the different copies having been modified by at least one of a time based audio effect, a frequency based audio effect, and a signal compression scheme.

22. A method of identifying digital recordings, comprising:

extracting first and second candidate fingerprints from the least one portion of an unidentified recording, the first candidate fingerprint having low discernability of frequency variation from the original and the second candidate fingerprint having low discernability of amplitude variation from the originals;

storing, for reference recordings, first reference fingerprints having low discernability of frequency variation and second reference fingerprints with low discernability of amplitude variation; and

comparing the first candidate fingerprint with the first reference fingerprints and the second candidate fingerprint with the second reference fingerprints to find a match for the unidentified recording among the reference recordings.

23. A method as recited in claim 22, wherein a first processor is used for said comparing of the first candidate fingerprint with the first reference fingerprints and concurrently a second processor is used for said comparing of the second candidate fingerprint with the second reference fingerprints.

24. A method as recited in claim 22, wherein a first result of said comparing of the first candidate fingerprint with the first reference fingerprints is combined with a second result of said comparing of the second candidate fingerprint with the second reference fingerprints to determine whether corresponding first and second reference fingerprints for both the first and second fingerprints are stored.

25. A method as recited in claim 22, wherein each of the at least one portion of the unidentified recording has a duration of less than 25 seconds.

26. A method as recited in claim 25, wherein each of the at least one portion of the unidentified recording has a duration of at least 10 seconds and no greater than 20 seconds.

27. A method of identifying digital recordings, comprising:

extracting weighted frequency spectra using overlapping frames with time weighting to smoothly transition between frames of an unidentified recording; and

searching for a match between at least one candidate value derived from the weighted frequency spectra and at least one reference value in at least one reference fingerprint among a plurality of reference fingerprints, by

transforming the weighted frequency spectra to transformed frequency spectra using a perceptual power scale attenuating high values relative to low values;

computing the at least one candidate value from the transformed frequency spectra; and

identifying the at least one reference value in the reference fingerprints that matches the at least one candidate value.

28. A method of identifying digital recordings, comprising:

partitioning at least one portion of an unidentified recording into time-frequency regions, each time-frequency region covering at least three ranges of time frames and at least three ranges of frequencies;

weighting the time-frequency regions to produce weighted time-frequency regions with emphasis on at least one middle-time and middle-frequency region;

computing at least one candidate value of at least one candidate fingerprint using the weighted time-frequency regions; and

searching for a match between the at least one candidate value and at least one reference value in at least one reference fingerprint among a plurality of reference fingerprints.

29. A method of identifying digital recordings, comprising;

generating reference fingerprints for reference recordings by

extracting a principal fingerprint from a specified portion of each reference recording;

extracting auxiliary fingerprints from the reference recording at a regular time interval;

computing reference distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

generating a reference song profile based on the reference distance measures; and

storing the principal fingerprint combined with the reference song profile as the reference fingerprint for the reference recording;

extracting an initial candidate fingerprint and subsequent candidate fingerprints, following the initial candidate fingerprint at the regular time interval, for an unknown digital recording; and

searching for a potentially matching reference recording for the unknown digital recording, by

comparing the initial candidate fingerprint with the principal fingerprint for at least one of the reference recordings, and

when the potentially matching reference recording is found,

computing candidate distance measures from the initial candidate fingerprint to the subsequent candidate fingerprints, respectively;

generating a candidate song profile based on the candidate distance measures; and

identifying the unknown digital recording as the potentially matching reference recording only if the candidate song profile has a predetermined correlation to the reference song profile for the potentially matching reference recording.

30. A method as recited in claim 29, wherein said comparing begins prior to completing said extracting of the subsequent candidate fingerprints.

31. A method of generating reference fingerprints of reference recordings for identifying unknown digital recordings, comprising:

extracting a principal fingerprint from a specified portion of each reference recording and auxiliary fingerprints from the reference recording at regular frame intervals, each of the principal and auxiliary;

fingerprints including a predetermined number of candidate values for corresponding frequency ranges;

computing distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

using selectively weighted difference between corresponding candidate and reference values

generating a song profile based on the distance measures; and

storing the principal fingerprint combined with the song profile as a reference fingerprint for the reference recording used to identify the unknown digital recordings.

32. At least one computer readable medium encoding instructions that when executed cause at least one processor to perform a method of identifying digital recordings, comprising:

extracting at least one candidate fingerprint from at least one portion of an unidentified recording, each candidate fingerprint including a predetermined number of candidate values for corresponding frequency ranges and each reference fingerprint including the predetermined number of reference values for the corresponding frequency ranges; and

searching for a match between at least one candidate value derived from the at least one candidate fingerprint and at least one reference value in at least one reference fingerprint among a plurality of reference fingerprints, by determining whether each candidate fingerprint matches one of the reference fingerprints based on selectively weighted differences between corresponding candidate and reference values for different frequency ranges.

33. At least one computer readable medium as recited in claim 32, wherein said searching comprises computing at least one weighted absolute difference between the at least one candidate fingerprint and the at least one reference fingerprint using a weight based on a value derived from the at least one candidate fingerprint.

34. At least one computer readable medium as recited in claim 32, further comprising prior to said extracting, expanding dynamic range of the at least one portion of the unidentified recording.

35. At least one computer readable medium as recited in claim 34, wherein said expanding of the dynamic range makes all sample values within the at least one portion of an unidentified recording more equally likely.

36. At least one computer readable medium as recited in claim 32, further comprising:

storing in a cache memory matched candidate fingerprints with identifiers of corresponding reference fingerprints; and

determining whether a new candidate fingerprint is included in the matched candidate fingerprints in the cache memory prior to said searching using the new candidate fingerprint.

37. At least one computer readable medium as recited in claim 36, further comprising:

indicating a match between the new candidate fingerprint and a corresponding reference fingerprint when the new candidate fingerprint is included in the matched candidate fingerprints in the cache memory; and

adding the new candidate fingerprint to the cache memory and associating a corresponding identifier for the corresponding reference fingerprint with new candidate fingerprint in the cache memory.

38. At least one computer readable medium as recited in claim 32, further comprising generating each of the candidate and reference fingerprints to include values representing a magnitude of power at frequencies in frequency ranges with mid-range frequencies weighted less than high- and low-range frequencies.

39. At least one computer readable medium as recited in claim 32, wherein generation of each of the candidate and reference fingerprints comprises:

computing power in each of a plurality of frequency bands; and

normalizing the power for each frequency within each band so that a mean of the power within each band is equal to a predetermined value.

40. At least one computer readable medium as recited in claim 32, wherein generation of each of the candidate and reference fingerprints comprises computing a frequency distribution within each of a plurality of different frequency bands using a finer resolution at lower frequency bands than at higher frequency bands.

41. At least one computer readable medium as recited in claim 32, wherein the portion of the unidentified recording has a duration of less than 25 seconds.

42. At least one computer readable medium as recited in claim 41, wherein the portion of the unidentified recording has a duration of at least 10 seconds and no greater than 20 seconds.

43. At least one computer readable medium as recited in claim 32,

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings,

wherein said extracting produces a plurality of candidate fingerprints from successive frames at a regular time interval, and

wherein said searching identifies the unidentified recording as corresponding to a single reference recording only if matches are found between the reference fingerprints from the single reference recording and the candidate fingerprints obtained from a predetermined number of the successive frames.

44. At least one computer readable medium as recited in claim 32,

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings,

wherein said extracting produces a plurality of candidate fingerprints, and

wherein said searching comprises:

finding a first match between a first candidate fingerprint and one of the reference fingerprints for a potentially matching reference recording; and

comparing other candidate fingerprints from the unidentified recording with the reference fingerprints for the potentially matching reference recording until a predetermined number of matches are found.

45. At least one computer readable medium as recited in claim 32,

further comprising storing a plurality of the reference fingerprints for each of a plurality of reference recordings, and

wherein said searching includes all of the reference fingerprints, unless a match is found.

46. At least one computer readable medium as recited in claim 32, further comprising generating the reference fingerprints for reference recordings by

extracting a principal fingerprint from a specified portion of each reference recording;

extracting auxiliary fingerprints from the reference recording at a regular time interval;

computing distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

generating a song profile based on the distance measures; and

storing the principal fingerprint combined with the song profile as the reference fingerprint for the reference recording.

47. At least one computer readable medium as recited in claim 32, wherein said extracting comprises:

separating the at least one portion of the unidentified recording into frequency bands;

computing power spectra for the frequency bands, respectively; and

computing at least one value from each power spectra.

48. At least one computer readable medium as recited in claim 47, wherein the frequency bands are output from filters derived from one prototype filter corresponding to an analysis wavelet.

49. At least one computer readable medium as recited in claim 48, wherein a ratio of bandwidth to center frequency is substantially identical for all of the filters.

50. At least one computer readable medium as recited in claim 32, wherein each of the candidate and reference fingerprints include a vector of at least 5 elements having at least 256 values each.

51. At least one computer readable medium as recited in claim 50, wherein each of the candidate and reference fingerprints include a vector of up to 38 elements having no more than 65,536 values each.

52. At least one computer readable medium as recited in claim 51, wherein each of the candidate and reference fingerprints include a vector of approximately 30 elements of approximately 16 bits each.

53. At least one computer readable medium as recited in claim 32, wherein said extracting produces a plurality of candidate fingerprints, each from different copies corresponding to a single reference recording, at least one of the different copies having been modified prior to said extracting.

54. At least one computer readable medium as recited in claim 53, wherein the at least one of the different copies having been modified by at least one of a time based audio effect, a frequency based audio effect, and a signal compression scheme.

55. At least one computer readable medium encoding instructions that when executed cause at least one processor to perform a method of identifying digital recordings, comprising:

extracting first and second candidate fingerprints from at least one portion of an unidentified recording, the first candidate fingerprint having low discernability of frequency variation from the original and the second candidate fingerprint having low discernability of amplitude variation from the originals;

storing, for reference recordings, first reference fingerprints having low discernability of frequency variation and second reference fingerprints with low discernability of amplitude variation; and

comparing the first candidate fingerprint with the first reference fingerprints and the second candidate fingerprint with the second reference fingerprints to find a match for the unidentified recording among the reference recordings.

56. At least one computer readable medium as recited in claim 55, wherein a first processor is used for said comparing of the first candidate fingerprint with the first reference fingerprints and concurrently a second processor is used for said comparing of the second candidate fingerprint with the second reference fingerprints.

57. At least one computer readable medium as recited in claim 55, wherein a first result of said comparing of the first candidate fingerprint with the first reference fingerprints is combined with a second result of said comparing of the second candidate fingerprint with the second reference fingerprints to determine whether corresponding first and second reference fingerprints for both the first and second fingerprints are stored.

58. At least one computer readable medium encoding instructions that when executed cause at least one processor to perform a method of identifying digital recordings, comprising:

extracting weighted frequency spectra using overlapping frames with time weighting to smoothly transition between frames of an unidentified recording; and

searching for a match between at least one candidate value derived from the weighted frequency spectra and at least one reference value in at least one reference fingerprint among a plurality of reference fingerprints, by

transforming the weighted frequency spectra to transformed frequency spectra using a perceptual power scale attenuating high values relative to low values;

computing the at least one candidate value from the transformed frequency spectra; and

identifying the at least one reference value in the reference fingerprints that matches the at least one candidate value.

59. At least one computer readable medium encoding instructions that when executed cause at least one processor to a method of identifying digital recordings, comprising:

partitioning at least one portion of an unidentified recording into time-frequency regions, each time-frequency region covering at least three ranges of time frames and at least three ranges of frequencies;

weighting time-frequency regions to produce weighted time-frequency regions with emphasis on at least one middle-time and middle-frequency region;

computing the at least one candidate value using the weighted time-frequency regions; and

identifying the at least one reference value in the reference fingerprints that matches the at least one candidate value.

60. At least one computer readable medium encoding instructions that when executed cause at least one processor to perform a method of identifying digital recordings, comprising:

generating reference fingerprints for reference recordings by

extracting a principal fingerprint from a specified portion of each reference recording;

extracting auxiliary fingerprints from the reference recording at a regular time interval;

computing reference distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

generating a reference song profile based on the reference distance measures; and

storing the principal fingerprint combined with the reference song profile as the reference fingerprint for the reference recording;

extracting an initial candidate fingerprint and subsequent candidate fingerprints following the initial candidate fingerprint at the regular time interval, for an unknown digital recording; and

searching for a potentially matching reference recording for the unknown digital recording, by

comparing the initial candidate fingerprint with the principal fingerprint for at least one of the reference recordings, and

when the potentially matching reference recording is found,

computing candidate distance measures from the initial candidate fingerprint to the subsequent candidate fingerprints, respectively;

generating a candidate song profile based on the candidate distance measures; and

identifying the unknown digital recording as the potentially matching reference recording only if the candidate song profile has a predetermined correlation to the reference song profile for the potentially matching reference recording.

61. At least one computer readable medium as recited in claim 60, wherein said comparing begins prior to completing said extracting of the subsequent candidate fingerprints.

62. At least one computer readable medium storing at least one program embodying a method of generating reference fingerprints of reference recordings for identifying unknown digital recordings, said method comprising:

extracting a principal fingerprint from a specified portion of each reference recordings and auxiliary fingerprints from the reference recording at regular frame intervals, each of the principal and auxiliary fingerprints including a predetermined number of candidate values for corresponding frequency ranges;

computing distance measures from the principal fingerprint to the auxiliary fingerprints, respectively;

using selectively weighted difference between corresponding candidate and reference values

generating a song profile based on the distance measures; and

storing the principal fingerprint combined with the song profile as the reference fingerprint for the reference recording used in identifying the unknown digital recordings.

63. A system for identifying digital recordings, comprising:

a storage unit storing reference fingerprints;

using selectively weighted differences between corresponding candidate and reference values and

a processor, coupled to said storage unit, extracting at least one candidate fingerprint from at least one portion of an unidentified digital recording, each candidate fingerprint including a predetermined number of candidate values for corresponding frequency ranges, and searching for a match between at least one candidate value derived from the at least one candidate fingerprint and at least one reference value in at least one reference fingerprint among the reference fingerprints.