Searching in a melody database

• US 20070162497A1
• Filed: 11/22/2004
• Published: 07/12/2007
• Est. Priority Date: 12/08/2003
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips N.V.
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Pauws, Steffen
• Application Number:
  US10/596,135
• Publication Number:
  US 20070162497A1
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Abstract

A system for searching for a query string, that represents an audio fragment, in a melody database (114) includes an input (122, 132) for receiving the query string from a user. The melody database (114) stores respective representations of plurality of audio fragments. A processor (116) is used to decompose (117) the query string into a sequence of a plurality of query sub-strings. Each sub-string is independently searched (118) in the database for at least a respective closest match for the sub-string. In dependence on the search results for the respective sub-strings, a closest match for the query string is determined (119).

Claims

1. A method of searching for a match for a query string, that represents an audio fragment, in a melody database;

the method including;

decomposing the query string into a sequence of a plurality of query sub-strings;

for each sub-string, independently searching the database for at least a respective closest match for the sub-string; and

in dependence on the search results for the respective sub-strings, determining at least a closest match for the query string.

2. A method of searching for a query string as claimed in claim 1, wherein the step of decomposing the query string includes decomposing the query string into sub-strings that each substantially correspond to a phrase.

3. A method of searching for a query string as claimed in claim 1, including enabling a user to input the query string mixing a plurality of query input modalities.

4. A method of searching for a query string as claimed in claim 3, wherein at least one of the query input modalities is one of:

humming, singing, whistling, tapping, clapping, percussive vocal sounds.

5. A method of searching for a query string as claimed in claim 3, wherein a change in query input modality substantially coincides with a sub-string boundary.

6. A method of searching for a query string as claimed in claim 1, wherein the step of decomposing the query string includes:

estimating how many (N_s) sub-strings are present in the query string;

dividing the query string in N_s sequential sub-strings;

each sub-string being associated with a respective centroid that represents the sub-string;

iteratively;

for each centroid determining a respective centroid value in dependence on the corresponding sub-string; and

determining for each of the sub-string corresponding sub-string boundaries by minimizing a total distance measure between each of the centroids and its corresponding sub-string;

until a predetermined convergence criterion is met.

7. A method of searching for a query string as claimed in claim 2, wherein the step of estimating how many (N_s) sub-strings are present in the query string includes dividing a duration of the audio fragment by an average duration of a phrase.

8. A method of searching for a query string as claimed in claim 5, wherein the step of decomposing the query string includes retrieving for each of the input modalities a respective classification criterion and using a classification algorithm for based on the classification criteria detecting a change in query input modality.

9. A method of searching for a query string as claimed in claim 3, including constraining a substring to fall within two successive changes in query input modality.

10. A method of searching for a query string as claimed in claim 1, wherein the step of searching for each sub-string in the database includes generating for the sub-string an N-best list (N>

=2) of the N most closest corresponding parts in the database with a corresponding measure of resemblance; and

performing the determining of the at least closest match for the query string based on the measures of resemblance of the N-best lists of the sub-strings.

11. A computer program product operative to cause a processor to execute the steps of the method as claimed in claim 1.

12. A system for searching for a query string, that represents an audio fragment, in a melody database;

the system including;

an input (122, 132) for receiving the query string from a user;

a melody database (114) for storing respective representations of plurality of audio fragments;

at least one processor (116) for, under control of a program,

decomposing (117) the query string into a sequence of a plurality of query sub-strings;

for each sub-string, independently searching (118) the database for at least a respective closest match for the sub-string; and

in dependence on the search results for the respective sub-strings, determining (119) at least a closest match for the query string.