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

• US 20060122839A1
• Filed: 01/23/2006
• Published: 06/08/2006
• Est. Priority Date: 07/31/2000
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Landmark Digital Services LLC
• Inventors: Li-Chun Wang, Avery, Smith, Julius O. III
• Granted Patent: US 7,346,512 B2
• Time in Patent Office: Days
• US Class Current: 704/273
• 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-106. -106. (canceled)

107. A method for constructing database index for a database of media samples, comprising:

landmarking each media sample to generate a list of timepoints;

computing a fingerprint at or near each landmark, the finger print and corresponding landmark forming a landmark/fingerprint pair; and

generating an index set for the media sample, the index set including a list of at least one of the landmark/fingerprint pairs.

108. The method of claim 107 further comprising:

appending a corresponding sound_ID to each of the landmark/fingerprint pairs to form a list of triplets, each triplet including the landmark, the fingerprint, and the sound_ID.

109. The method of claim 108 further comprising:

collecting the list of triplets in an index list; and

sorting the index list according to the fingerprints.

110. The method of claim 109, further comprising:

segmenting the index list such that at least one of the fingerprints for each media sample is collected into a master index list, where each entry in the mast index list contains a fingerprint and a pointer to a list of landmark, sound_ID pairs.

111. The method of claim 110, further comprising:

constructing a master index list by inserting each triplet in said list of triplets into a B-tree.

112. The method of claim 110, further comprising:

updating the database index by inserting newly added fingerprints into the master index list, such that when the master index list already contains the newly added fingerprint, then the corresponding landmark, sound_ID pair is added to the entry containing the fingerprint.

113. The method of claim 107 wherein the landmarking is independent of the fingerprinting.

114. The method of claim 107 wherein the landmarking and fingerprinting are performed simultaneously.

115. The method of claim 107 wherein the fingerprinting is performed over a timeslice associated with each landmark, the timeslice formed by adding a set of time offsets to the timepoint associated with the landmark, the resulting fingerprint being a spectral slice fingerprint.

116. The method of claim 115 wherein the set of time offsets are variable offsets.

117. The method of claim 107 wherein the landmarks and fingerprints are computed from a spectrogram of the media sample.

118. A method for recognizing a media entity from a media sample, comprising:

generating correspondences between landmarks of the media sample and corresponding landmarks in a database index, the database index including landmarks and fingerprints for a plurality of media entities, wherein the landmarks of the media sample and the corresponding landmarks of database index have equivalent fingerprints; and

identifying a particular media entity from the plurality of media entities which matches the media sample, if a plurality of said correspondences between the media sample and the particular media entity have a relationship.

119. The method of claim 118 wherein the relationship is a linear relationship.

120. The method of claim 118 wherein generating the correspondences comprises:

comparing the fingerprints of the media sample with the fingerprints in the database index; and

retrieving from the data index the landmarks and IDs associated with the fingerprints from the data index that match the fingerprints from the media sample.

121. The method of claim 118 further comprising computing landmarks and fingerprints for the media sample before generating the correspondences.

122. A method of recognizing a media sample, comprising:

identifying media files that have file landmarks that are substantially linearly related to sample landmarks of the media sample;

wherein the file landmarks and the sample landmarks have equivalent fingerprints; and

wherein the file landmarks the said sample landmarks have a correspondence.

123. The method of claim 122 wherein the correspondence is a linear relationship.

124. The method of claim 122 wherein the file landmarks are stored in a database index, the database index storing fingerprint and landmark information for a plurality of media files.

125. The method of claim 122 further comprising computing landmarks and fingerprints for the media sample before identifying the media files that have file landmarks.