Music information retrieval using a 3D search algorithm

• US 7,488,886 B2
• Filed: 11/09/2006
• Issued: 02/10/2009
• Est. Priority Date: 11/09/2005
• Status: Expired due to Fees

• Current Assignee: Sony Deutschland GmbH (Sony Group Corp.)
• Original Assignee: Sony Deutschland GmbH (Sony Group Corp.)
• Inventors: Kemp, Thomas
• Primary Examiner(s): Donels; Jeffrey
• Application Number:
  US11/558,301
• Publication Number:
  US 20070131094A1
• Time in Patent Office: 824 Days
• Field of Search: 846/09, 846/16
• US Class Current: 84/609
• CPC Class Codes: G06F 16/632 Query formulation
• CPC Class Codes: G06F 16/634 Query by example, e.g. query by humming
• CPC Class Codes: G06F 16/68 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/683 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/685 using automatically derived transcript of audio data, e.g. lyrics speech recognition G10L15/00
• CPC Class Codes: G10H 1/0008 Associated control or indicating means
• CPC Class Codes: G10H 2210/031 Musical analysis, i.e. isolation, extraction or identification of musical elements or musical parameters from a raw acoustic signal or from an encoded audio signal
• CPC Class Codes: G10H 2240/131 Library retrieval, i.e. searching a database or selecting a specific musical piece, segment, pattern, rule or parameter set
• CPC Class Codes: G10H 2240/135 Library retrieval index, i.e. using an indexing scheme to efficiently retrieve a music piece
• CPC Class Codes: G10H 2240/141 Library retrieval matching, i.e. any of the steps of matching an inputted segment or phrase with musical database contents, e.g. query by humming, singing or playing; the steps may include, e.g. musical analysis of the input, musical feature extraction, query formulation, or details of the retrieval process
• CPC Class Codes: G10H 2250/005 Algorithms for electrophonic musical instruments or musical processing, e.g. for automatic composition or resource allocation
• CPC Class Codes: G10H 2250/021 Dynamic programming, e.g. Viterbi, for finding the most likely or most desirable sequence in music analysis, processing or composition
• CPC Class Codes: G10L 25/48 specially adapted for particular use
• CPC Class Codes: G10L 25/90 Pitch determination of speech signals

Abstract

A music information retrieval system and method that involve a query-by-humming (QbH) database system for processing queries in the form of analog audio sequences which encompass recorded parts of sung, hummed or whistled tunes, recorded parts of a melody played on a musical instrument or a speaker'"'"'s recorded voice articulating at least one part of a song'"'"'s lyrics to retrieve textual background information about a musical piece whose score is stored in an integrated database of said system after having analyzed and recognized said melody.

Claims

1. A method for the retrieval of music information based on audio input comprising:

pre-storing a defined set of music sequences with associated information;

entering at least one of speech and music information and arranging a coding representing said speech and music information, respectively, as a first (S) and a second dimension (H) of a three-dimensional search space, time (t) being the third dimension, and

carrying out a search in the three-dimensional search space in order to find the music sequence out of the set of music sequences matching best to the entered at least one of speech and music information, and

retrieving said music sequence for a user that has placed an inquiry for said information.

2. The method of claim 1, wherein the at least one of entered speech and music information is individually pre-processed before respectively being represented as a coding in the three-dimensional search space.

3. The method of any one of claims 1 or 2, further comprising:

calculating a similarity measure indicating the similarity of the entered speech and music information compared to melody and lyrics of the pre-stored music files in a database, and

generating a ranked list of said music files, the ranking of a music file depending on the similarity measure.

4. The method of claim 3, further comprising:

encoding at least one of a sung or hummed tune and a played melody consisting at least of N notes and pauses, wherein N is an integer value greater than one, by a melody reference string (REF),

retrieving encoded previously analyzed melodies consisting at least of N notes and pauses whose scores are stored in a database and encoded by a melody hypothesis strings (HYPO₀, HYPO₁, . . . , HYPO_k, . . . , HYPO_M-1),

encoding recognized phonemes from spoken parts of a recorded song'"'"'s lyrics consisting of P phonemes, wherein P is an integer value greater than one, by speech reference string (REF_s), and concatenating said speech reference string (REF_s) to said melody reference string (REF), thus yielding a combined reference string (REF_ms), retrieving phonemes of previously analyzed speech signals consisting of P phonemes, said phonemes being encoded by a second character string, from a number (Q) of pre-stored character strings, in the following referred to as speech hypothesis strings (HYPO_s0, HYPO_s1, HYPO_s2, . . . , HYPO_s,k, . . . , HYPO_s,Q-1), and concatenating said speech hypothesis strings to said melody hypothesis strings, thus yielding combined hypothesis strings (HYPO_ms0, HYPO_ms1, HYPO_ms2, . . . , HYPO_ms,k, . . . , HYPO<sub>ms,M+Q−

1</sub>), and

calculating a similarity measure indicating the similarity between the melody and lyrics of the recorded audio sequence compared to melody and lyrics of a variety of music files stored in said database by using a single two-dimensional search space in form of an (N+P−

1)×

(N+P−

1) alignment matrix (D_ms) having the character index i of the k-th combined hypothesis string (a_ms;

=(Interval₁, . . . , Interval_N-1, Phoneme₁, . . . , Phoneme_P)^T) as column coordinate and the character index j of the combined reference string (b_ms;

=(Interval₁, . . . , Interval_N-1, Phoneme₁, . . . , Phoneme_P)^T) as row coordinate.

5. The method of claim 4, wherein the step of calculating said similarity measure comprises:

creating an (N+P−

1)×

(N+P−

1) alignment matrix (D_ms) by setting the character index i of the k-th hypothesis string (a_ms;

=(Interval₁, . . . , Interval_N-1, Phoneme₁, . . . , Phoneme_P)^T) as coordinate for the columns and the character index j of the reference string (b_ms;

=(Interval₁, . . . , Interval_N-1, Phoneme₁, . . . , Phoneme_P)^T) as coordinate for the rows of said matrix and filling the alignment matrix (D_ms) by calculating and setting each (i,j)-element of said matrix according to a filling scheme for filling accumulated cost factors (d_i,j=f(d_i-1,j, d_i,j-1, d_i-1,j-1, w(a_i, b_j))) into the cells of said alignment matrix (D_ms),

executing an alignment function based on the Viterbi search algorithm to compare the combined reference string (REF_ms) with the combined hypothesis strings (HYPO_ms0, HYPO_ms1, HYPO_ms2, . . . , HYPO_ms,k, . . . , HYPO<sub>ms,M+Q−

1</sub>) of all stored melodies and lyrics, thereby returning at least one of a string of characters and a sequence of cost factors (w(a_i, b_j)) indicating which characters of the combined reference string (REF_ms) closely match with the characters of the k-th combined hypothesis string (HYPO_ms,k), and executing a backtracking algorithm which starts with the lowest cost factor in the last column of the alignment matrix (D_ms) and goes back through the alignment matrix towards the first row and the first column of said matrix along a tracking path derived by the alignment function.

6. The method of claim 5, wherein the elements (d_i,j) of said alignment matrix (D_ms) are characterized according to the following filling scheme:

$d_{\mathrm{ij}};<br><br>=\min <br><br>\{\begin{array}{cc}{d}_{i-1,j}+w<br><br>\left(a_i,0\right)& \forall <br><br>i,j\in <br><br>\left\{1,2,\mathrm{\dots <br><br>}<br><br>,N+P-1\right\}\\ d_{i-1,j-1}+w<br><br>\left(a_i,b_j\right)& \forall <br><br>i,j\in <br><br>\left\{1,2,\mathrm{\dots <br><br>}<br><br>,N+P-1\right\}\\ d_{i,j-1}+w<br><br>\left(0,b_j\right)& \forall <br><br>i,j\in <br><br>\left\{1,2,\mathrm{\dots <br><br>}<br><br>,N+P-1\right\}\end{array}$

wherein the initial conditions are

d_0,0;

=0,

d_i,0;

=d_i-1,0+w(a_i,

     0) ∀

i ε

{1, 2, 3, . . . , N+P−

1}, and

d_0,j;

=d_0,j-1+w(0, b_j) ∀

j ε

{1, 2, 3, . . . , N+P−

1},

and wherein

w(a_i, 0) is a cost factor associated with the deletion of the character a_i of the k-th hypothesis string (HYPO_ms,k),

w(0, b_j) is a cost factor associated with the insertion of the character b_j into the combined reference string (REF_ms), and

w(a_i, b_j) is a cost factor associated with the replacement of the element a, of the k-th combined hypothesis string (HYPO_ms,k) by the element b_j of the combined reference string (REF_ms), wherein w(a_i, b_j) is set to zero if a_i=b_j and set to a value greater than zero if a_i≠

b_j.

7. A computer-readable recording medium including a computer software program which, when executed by a computing device, causes the computing device to implement the method of claim 1.

8. A music information retrieval system based on audio input, comprising:

a database for prestoring a defined set of music sequences with associated information;

means for entering at least one of speech and music information;

coding means for arranging a coding representing said speech and music information respectively as a first (S) and a second dimension (H) of a three-dimensional search space, time (t) being the third dimension; and

matching means for carrying out a search in the three-dimensional search space in order to find the music sequence out of the set of music sequences matching best to the entered speech and/or music information.

9. The music information retrieval system of claim 8, wherein said coding means comprises:

an automatic music recognition system for extracting, analyzing and recognizing musical key characteristics from analog audio sequences; and

an automatic speech recognition system for extracting and analyzing acoustic-phonetic speech characteristics of the speaker'"'"'s voice and pronunciation from spoken parts of the recorded song'"'"'s lyrics and for recognizing syntax and semantics of said lyrics.

10. The music information retrieval system of claims 8 or 9, wherein said matching means comprises:

means for calculating a similarity measure indicating the similarity of melody and lyrics of the entered audio sequence compared to melody and lyrics of various music files stored in said database by performing a Viterbi search algorithm on the three-dimensional search space and for generating a ranked list of said music files.