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

• US 20020083060A1
• Filed: 04/20/2001
• Published: 06/27/2002
• Est. Priority Date: 07/31/2000
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Landmark Digital Services LLC
• Inventors: Smith, Julius O. III, Wang, Avery Li-Chun
• Granted Patent: US 6,990,453 B2
• Time in Patent Office: Days
• US Class Current: 707/10
• 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 comparing a media sample and a media file, comprising:

computing a set of sample fingerprints, each sample fingerprint characterizing a particular location within said media sample;

obtaining a set of file fingerprints, each file fingerprint characterizing at least one file location within said media file;

generating correspondences between said particular locations of said media sample and said file locations of said media file, wherein corresponding locations have equivalent fingerprints; and

identifying said media sample and said media file if a plurality of said corresponding locations are substantially linearly related.

2. The method of claim 1 wherein said particular locations within said media sample are computed in dependence on said media sample.

3. The method of claim 1 wherein each sample fingerprint represents one or more features of said media sample near said particular location.

4. The method of claim 1 wherein said sample fingerprints and said file fingerprints have numerical values.

5. The method of claim 1 wherein values of said sample fingerprints specify a method for computing said sample fingerprints.

6. The method of claim 1 wherein said media sample is an audio sample.

7. The method of claim 6 wherein said particular locations are timepoints within said audio sample.

8. The method of claim 7 wherein said timepoints occur at local maxima of spectral Lp norms of said audio sample.

9. The method of claim 6 wherein said sample fingerprints are computed from a frequency analysis of said audio sample.

10. The method of claim 6 wherein said sample fingerprints are selected from the group consisting of spectral slice fingerprints, LPC coefficients, and cepstral coefficients.

11. The method of claim 6 wherein said sample fingerprints are computed from a spectrogram of said audio sample.

12. The method of claim 11 wherein salient points of said spectrogram comprise time coordinates and frequency coordinates, and wherein said particular locations are computed from said time coordinates, and said fingerprints are computed from said frequency coordinates.

13. The method of claim 12, further comprising linking a plurality of said salient points to an anchor salient point, wherein one of said particular locations is computed from a time coordinate of said anchor salient point, and a corresponding fingerprint is computed from frequency coordinates of at least one of said linked salient points and said anchor point.

14. The method of claim 13, wherein said linked salient points fall within a target zone.

15. The method of claim 14, wherein said target zone is defined by a time range.

16. The method of claim 14, wherein said target zone is defined by a frequency range.

17. The method of claim 14, wherein said target zone is variable.

18. The method of claim 13 wherein said corresponding fingerprint is computed from a quotient between two of said frequency coordinates of said linked salient points and said anchor point, whereby said corresponding fingerprint is time-stretch invariant.

19. The method of claim 13 wherein said corresponding fingerprint is further computed from at least one time difference between said time coordinate of said anchor point and said time coordinates of said linked salient points.

20. The method of claim 19, wherein said corresponding fingerprint is further computed from a product of one of said time differences and one of said frequency coordinates of said linked salient points and said anchor point, whereby said corresponding fingerprint is time-stretch invariant.

21. The method of claim 6 wherein said particular locations and said sample fingerprints are computed from salient points of a multidimensional function of said audio sample, wherein at least one of said dimensions is a time dimension and at least one of said dimensions is a non-time dimension.

22. The method of claim 21 wherein said particular locations are computed from said time dimensions.

23. The method of claim 21 wherein said sample fingerprints are computed from at least one of said non-time dimensions.

24. The method of claim 21 wherein said salient points are selected from the group consisting of local maxima, local minima, and zero crossings of said multidimensional function.

25. The method of claim 6 wherein said sample fingerprints are time-stretch invariant.

26. The method of claim 6 wherein each sample fingerprint is computed from multiple timeslices of said audio sample.

27. The method of claim 26 wherein said multiple timeslices are offset by a variable amount of time.

28. The method of claim 27 wherein each fingerprint is computed in part from said variable amount.

29. The method of claim 1 wherein said identifying step comprises locating a diagonal line within a scatter plot of said corresponding locations.

30. The method of claim 29 wherein locating said diagonal line comprises forming differences between said corresponding locations.

31. The method of claim 30 wherein locating said diagonal line further comprises sorting said differences.

32. The method of claim 30 wherein locating said diagonal line further comprises calculating the peak of a histogram of said differences.

33. The method of claim 1 wherein said identifying step comprises computing one of a Hough transform and a Radon transform of said correspondences.

34. The method of claim 33 wherein said identifying step further comprises locating a peak of said Hough transform.

35. The method of claim 1 wherein said identifying step comprises determining whether said the number of correspondences exceeds a threshold value.

36. The method of claim 1 further comprising:

obtaining from a database index additional fingerprints characterizing file locations of additional media files;

generating additional correspondences between said particular locations of said media sample and said file locations of said additional media files, wherein corresponding locations have equivalent fingerprints; and

identifying media files for which a plurality of said corresponding locations are substantially linearly related.

37. The method of claim 36 further comprising selecting a winning media file from said identified media files, wherein said winning media file has a largest plurality of substantially linearly related corresponding locations.

38. The method of claim 36 wherein identifying said media files for which a plurality of said corresponding locations are substantially linearly related comprises searching a first subset of said additional media files.

39. The method of claim 38 wherein additional media files in said first subset have a higher probability of being identified than additional media files that are not in said first subset.

40. The method of claim 39 wherein said probability of being identified is computed in dependence on a recency of previous identification.

41. The method of claim 39 wherein said probability of being identified is computed in dependence on a frequency of previous identification.

42. The method of claim 38 wherein identifying said media files for which a plurality of said corresponding locations are substantially linearly related further comprises searching a second subset of said additional media files, wherein said second subset is searched if no media files in said first subset are identified.

43. The method of claim 36, further comprising ranking said additional media files according to a probability of being identified.

44. The method of claim 43 wherein said probability is computed in part in dependence on a recency of previous identification.

45. The method of claim 44 wherein said probability is computed in part by increasing a recency score of a particular media file when said particular media file is identified.

46. The method of claim 44 wherein said probability is computed in part by decreasing recency scores of said additional media files at regular time intervals.

47. The method of claim 46 wherein said recency scores are decreased exponentially in time.

48. The method of claim 43 wherein identifying said media files for which a plurality of said corresponding locations are substantially linearly related comprises searching said additional media files according to said ranking.

49. The method of claim 36 wherein identifying said media files for which a plurality of said corresponding locations are substantially linearly related comprises terminating said search at a media file having a number of said substantially linearly related corresponding locations that exceeds a predetermined threshold.

50. The method of claim 1 wherein said method is implemented in a distributed system.

51. The method of claim 50 wherein said computing step is performed in a client device, said obtaining, generating, and identifying steps are performed in a central location, and the method further comprises transmitting said sample fingerprints from said client device to said central location.

52. The method of claim 1, further comprising repeating said computing, obtaining, generating, and identifying steps for sequentially growing segments of said media sample.

53. The method of claim 1 wherein said obtaining, generating, and identifying steps are performed at periodic intervals on a rolling buffer storing said computed fingerprints.

54. The method of claim 1, further comprising obtaining said media sample, wherein said computing step and said obtaining step are performed simultaneously.

55. A method for comparing a media sample and a media file, comprising:

receiving a set of sample fingerprints, each sample fingerprint characterizing a particular location within said media sample;

obtaining a set of file fingerprints, each file fingerprint characterizing at least one file location within said media file;

generating correspondences between said particular locations of said media sample and said file locations of said media files, wherein corresponding locations have equivalent fingerprints; and

identifying said media sample and said media file if a plurality of said corresponding locations are substantially linearly related.

57. The method of claim 56, further comprising repeating said method for additional segments of said media sample.

58. The method of claim 56 wherein said computing, storing, and removing steps are performed in a client device and said locating and identifying steps are performed in a central location, and wherein the method further comprises transmitting said sample fingerprints from said client device to said central location.

59. The method of claim 56 wherein said computing step is performed in a client device and said storing, locating, identifying, and removing steps are performed in a central location, and wherein the method further comprises transmitting said fingerprints from said client device to said central location.

56. A method for recognizing a media sample, comprising:

computing a set of sample fingerprints characterizing a segment of said media sample;

storing said fingerprints in a rolling buffer;

obtaining a set of matching fingerprints in a database index, each matching fingerprint characterizing at least one media file and matching at least one fingerprint in said rolling buffer;

identifying at least one media file having a plurality of matching fingerprints; and

removing at least one sample fingerprint from said rolling buffer.

60. A method for characterizing an audio sample, comprising:

computing a set of reproducible locations in said audio sample; and

computing a set of fingerprints characterizing said reproducible locations in said audio sample.

61. The method of claim 60, wherein said reproducible locations and said fingerprints are computed simultaneously.

62. A program storage device accessible by a computer, tangibly embodying a program of instructions executable by said computer to perform method steps for comparing a media sample and a media file, said method steps comprising:

computing a set of sample fingerprints, each sample fingerprint characterizing a particular location within said media sample;

obtaining a set of file fingerprints, each file fingerprint characterizing at least one file location within said media file;

generating correspondences between said particular locations of said media sample and said file locations of said media file, wherein corresponding locations have equivalent fingerprints; and

identifying said media sample and said media file if a plurality of said corresponding locations are substantially linearly related.

63. A system for recognizing a media sample, comprising:

a landmarking and fingerprinting object for computing a set of particular locations within said media sample and a set of sample fingerprints, each sample fingerprint characterizing one of said particular locations;

a database index containing file locations and corresponding file fingerprints for at least one media file; and

an analysis object for;

locating a set of matching fingerprints in said database index, wherein said matching fingerprints are equivalent to said sample fingerprints;

generating correspondences between said particular locations of said media sample and file locations of said at least one media file, wherein corresponding locations have equivalent fingerprints; and

identifying at least one media file for which a plurality of said corresponding locations are substantially linearly related.

64. A computer-implemented method for creating a database index of at least one audio file in a database, comprising:

computing a set of fingerprints representing features of each audio file, each fingerprint characterizing a particular location within said audio file; and

storing within a memory said fingerprints, said locations, and an identifier of each media file, wherein each corresponding fingerprint, location and identifier is associated in said memory.

65. The method of claim 64, further comprising sorting said database index by fingerprint value.

66. The method of claim 64 wherein said particular locations of each audio file are computed in dependence on said audio file.

67. The method of claim 64 wherein each fingerprint represents at least one feature of said audio file near said particular location.

68. The method of claim 64 wherein said fingerprints are numerical values.

69. The method of claim 64 wherein values of said fingerprints specify a method for computing said fingerprints.

70. The method of claim 64 wherein said particular locations are timepoints within said audio file.

71. The method of claim 70 wherein said timepoints occur at local maxima of spectral Lp norms of said audio file.

72. The method of claim 64 wherein said fingerprints are computed from a frequency analysis of said audio file.

73. The method of claim 64 wherein said fingerprints are selected from the group consisting of spectral slice fingerprints, LPC coefficients, and cepstral coefficients.

74. The method of claim 64 wherein said fingerprints are computed from a spectrogram of said audio file.

75. The method of claim 74 wherein salient points of said spectrogram comprise time coordinates and frequency coordinates, and wherein said particular locations are computed from said time coordinates, and said fingerprints are computed from said frequency coordinates.

76. The method of claim 75, further comprising linking a plurality of said salient points to an anchor salient point, wherein one of said particular locations is computed from a time coordinate of said anchor salient point, and a corresponding fingerprint is computed from frequency coordinates of at least one of said linked salient points and said anchor point.

77. The method of claim 76, wherein said linked salient points fall within a target zone.

78. The method of claim 77, wherein said target zone is defined by a time range.

79. The method of claim 77, wherein said target zone is defined by a frequency range.

80. The method of claim 77, wherein said target zone is variable.

81. The method of claim 76, wherein said corresponding fingerprint is computed from a quotient between two of said frequency coordinates of said linked salient points and said anchor point, whereby said corresponding fingerprint is time-stretch invariant.

82. The method of claim 76, wherein said corresponding fingerprint is further computed from at least one time difference between said time coordinate of said anchor point and said time coordinates of said linked salient points.

83. The method of claim 82, wherein said corresponding fingerprint is further computed from a product of one of said time differences and one of said frequency coordinates of said linked salient points and said anchor point, whereby said corresponding fingerprint is time-stretch invariant.

84. The method of claim 64 wherein said particular locations and said fingerprints are computed from salient points of a multidimensional function of said audio file, wherein at least one of said dimensions is a time dimension and at least one of said dimensions is a non-time dimension.

85. The method of claim 84 wherein said particular locations are computed from said time dimensions.

86. The method of claim 84 wherein said fingerprints are computed from at least one of said non-time dimensions.

87. The method of claim 84 wherein said salient points are selected from the group consisting of local maxima, local minima, and zero crossings of said multidimensional function.

88. The method of claim 64 wherein said fingerprints are time-stretch invariant.

89. The method of claim 64 wherein each fingerprint is computed from multiple timeslices of said audio file.

90. The method of claim 89 wherein said multiple timeslices are offset by a variable amount of time.

91. The method of claim 90 wherein said fingerprints are computed in part from said variable amounts.

92. A method for recognizing a media sample, comprising:

for each of a plurality of media files, providing a file representation of said media file;

providing a sample representation of said media sample; and

identifying at least one similar file representation among said file representations, wherein said similar file representation is similar to said sample representation, by searching said file representations, wherein said searching is performed in part in dependence on a probability of identification of said file representations.

93. The method of claim 92 wherein said at least one similar file representation exceeds a threshold similarity to said sample representation.

94. The method of claim 92 wherein said identifying step comprises searching a first subset of said file representations, wherein said first subset contains file representations having a higher probability of identification than file representations that are not in said first subset.

95. The method of claim 94, further comprising searching a second subset of said file representations if said first subset does not comprise said at least one similar file representation.

96. The method of claim 92, further comprising ranking said file representations by said probability of identification, wherein said identifying step comprising searching said file representations in order of said ranking.

97. The method of claim 96, further comprising terminating said search when said at least one similar file representation is identified.

98. The method of claim 92 wherein said probability of identification is computed in part in dependence on a recency of previous identification.

99. The method of claim 98 wherein a recency score of a particular file representation is increased when said particular file representation is identified.

100. The method of claim 98 wherein recency scores of said file representations are decreased at regular time intervals.

101. The method of claim 100 wherein said recency scores are decreased exponentially in time.

102. The method of claim 92 wherein said probability of identification is computed in part in dependence on a frequency of previous recognition.

103. A method for recognizing a media sample, comprising identifying media files for which locations of a substantial plurality of equivalent features of said media files and said media sample are substantially linearly related.

104. A method for comparing an audio sample and an audio file, comprising:

for each of at least one audio file, computing a plurality of file fingerprints representing said audio file;

computing a plurality of sample fingerprints representing said audio sample; and

identifying said audio sample and said audio file if at least a threshold number of said file fingerprints are equivalent to said sample fingerprints;

wherein said sample fingerprints are invariant to time stretching of said audio sample.

105. The method of claim 104 wherein said sample fingerprints comprise quotients of frequency components of said audio sample.

106. The method of claim 104 wherein said sample fingerprints comprise products of frequency components of said audio sample and time differences between points in said audio sample.