Melody retrieval system

• US 7,919,706 B2
• Filed: 12/10/2007
• Issued: 04/05/2011
• Est. Priority Date: 03/13/2000
• Status: Expired due to Fees

• Current Assignee: Perception Digital Technology Shenzhen Limited
• Original Assignee: Perception Digital Technology Limited
• Inventors: Tsui, Chi-ying, Yung, Chi Wai, Shi, Bertram
• Primary Examiner(s): Enad; Elvin G
• Assistant Examiner(s): Millikin; Andrew R
• Application Number:
  US11/953,215
• Publication Number:
  US 20080148924A1
• Time in Patent Office: 1,212 Days
• Field of Search: 707/749, 700/94, 846/09, 846/15, 846/16, 846/18
• US Class Current: 84/618
• CPC Class Codes: G09B 15/023 Electrically operated
• CPC Class Codes: G10H 1/0008 Associated control or indicating means
• CPC Class Codes: G10H 2210/066 for pitch analysis as part of wider processing for musical purposes, e.g. transcription, musical performance evaluation; Pitch recognition, e.g. in polyphonic sounds; Estimation or use of missing fundamental
• CPC Class Codes: G10H 2210/076 for extraction of timing, tempo; Beat detection tempo display G10H2220/081; tempo control G10H2210/375
• CPC Class Codes: G10H 2240/111 User Password, i.e. security arrangements to prevent third party unauthorised use, e.g. password, id number, code, pin
• 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 2240/251 Mobile telephone transmission, i.e. transmitting, accessing or controlling music data wirelessly via a wireless or mobile telephone receiver, analog or digital, e.g. DECT GSM, UMTS smartphone, PDA or palmtop used for musical purposes G10H2230/015; mobile ringtone G10H2230/021
• CPC Class Codes: G10H 2240/305 Internet or TCP/IP protocol use for any electrophonic musical instrument data or musical parameter transmission purposes
• CPC Class Codes: G10H 2250/031 Spectrum envelope processing
• CPC Class Codes: G10H 2250/135 Autocorrelation
• CPC Class Codes: G10H 2250/645 Waveform scaling, i.e. amplitude value normalisation
• CPC Class Codes: G10H 3/125 Extracting or recognising the pitch or fundamental frequency of the picked up signal

Abstract

A music retrieval system which take an input melody as the query. In one embodiment, changes or differences in the distribution of energy across the frequency spectrum over time are used to find breakpoints in the input melody in order to separate it into distinct notes. In another embodiment the breakpoints are identified based on changes in pitch over time. A confidence level is preferably associated with each breakpoint and/or note extracted from the input melody. The confidence level is based on one or more of: changes in pitch, absolute values of a spectral energy distribution indicator, relative values of the spectral energy distribution indicator, and the energy level of the input melody. The process of matching the input melody with songs in the music database is based on minimizing a cost computation that takes into account errors in the insertion and deletion of notes, and penalizes these errors in accordance with the confidence levels of the breakpoints and/or notes.

Claims

1. A method of retrieving at least one entry from a music database, wherein each of said entries is associated with a sequence of pitches and beat durations, said method comprising:

receiving a digitized representation of an input melody;

identifying breakpoints in said melody in order to define notes therein, each of said notes being delineated by adjacent breakpoints;

assigning a confidence level to each note or each breakpoint;

determining a pitch and beat duration for each note of said melody;

determining a score for each of said entries based on a search which minimizes cost of matching the pitches and beat durations of said melody and said entry, wherein said search considers at least one deletion or insertion error in a selected note of said melody and, in this event, penalizes the cost of matching based on the confidence level of the selected note or a breakpoint associated therewith; and

presenting said at least one entry to a user based on its score.

2. The method according to claim 1, wherein said pitches and beat durations are relative pitches and relative beat durations.

3. The method according to claim 1, wherein

the cost of matching a given note Xi of said melody with a given note Y_j associated with said entry is:

match_cost(X_i, Y_j)=α

|YRF_j−

XRF_j|+β

|YRT_j−

XRT_i|, where YRF_j and YRT_j respectively represent the relative pitch and relative beat duration of the note associated with said entry, and

XRF_i and XRT_j respectively represent the relative pitch and relative beat duration of the note associated with said melody; and

α and

β

are weights.

4. The method according to claim 1, wherein:

a confidence level is assigned to each note and each breakpoint; and

said search considers deletion and insertion errors for any given note of said melody and, in this event, penalizes the cost of matching based on the confidence level of the given note and the confidence level of a breakpoint associated with the given note.

5. The method according to claim 4, wherein:

X is a sequence of notes, X_i, of said melody, each X_i, having components XRF_i, XRT_j XICON_i, and XDCON_i which respectively represent the relative pitch, relative beat duration, confidence level of the breakpoint and confidence level of the note associated with said melody;

Y is a sequence of notes, Y_j, of said entry, each Y_j having components YRF_j and YRT_J which respectively represent the relative pitch and relative beat duration of the note associated with said entry;

X and Y form a matrix, and at a matching point (X_i, Y_j) said search seeks to identify a preceding set of notes {(X<sub>i−

1−

k</sub>,Y <sub>j−

1</sub>)(X<sub>i−

1</sub>, Y<sub>j−

1−

k</sub>)} 0<

k<

max_k, which minimize a match cost defined as follows;

if k=0, α

|YRF_j−

XRF<sub>u−

l</sub>|+β

|YRT<sub>j−

1</sub>−

XRT<sub>i−

1</sub>|, else if k>

0,

6. The method according to claim 1, further comprising:

segmenting the melody into a series of frames, wherein adjacent breakpoints encompass one or more sequential frames;

executing at least two of the following three steps,

(a) computing a spectral energy distribution (SED) indicator for each frame,

(b) estimating the pitch of each frame, and

(c) determining the energy level of each frame,

deriving the confidence levels based on at least two of the following three characteristics, (i) the SED indicator, (ii) changes in pitch, and (iii) the energy level.

7. The method according to claim 6, wherein the confidence level for a given breakpoint is computed as a weighted combination of at least two of three numbers, the first number based on value of the SED indicator in the vicinity of the given breakpoint, the second number being based on a change in pitch in the frames before and after the given breakpoint, and the third number being based on the energy level of the frames in the immediate vicinity of the breakpoint.

8. The method according to claim 6, wherein the confidence level for a given note is computed as a weighted combination of at least two of three numbers, the first number based on value of the SED indicator in the given note, the second number being based on the variation in pitch in the given note, and the third number being based on the energy level of the frames in the given note.

9. The method according to claim 1, further comprising:

segmenting the melody into a series of frames, wherein adjacent breakpoints encompass one or more sequential frames;

computing a spectral energy distribution (SED) indicator for each frame;

estimating the pitch of each frame; and

deriving the confidence levels based on the SED indicator and changes in pitch.

10. The method according to claim 9, wherein the confidence level for a given breakpoint is computed as a weighted combination of a first number based on value of the SED indicator in the vicinity of the given breakpoint and a second number based on a change in pitch in the frames before and after the given breakpoint.

11. The method according to claim 9, wherein the confidence level for a given note is computed as a weighted combination of a first number based on value of the SED indicator within the given note and a second number based on the variation in pitch within the given note.

12. The method according to claim 9, wherein value of the SED indicator for a given frame is relatively large if an energy distribution associated with the frame is concentrated in one or more specified frequency bands.

13. The method according to claim 12, including filtering the melody with a high pass filter prior to segmenting the melody into frames.

14. The method according to claim 13, wherein the energy distribution is determined from a normalized energy spectrum of the frame.

15. The method according to claim 14, wherein the specified frequency band is in the upper portion of a 0-4 kHz frequency range.

16. The method according to claim 1, further comprising:

segmenting the melody into a series of frames, wherein adjacent breakpoints encompass one or more sequential frames;

computing a spectral energy distribution (SED) indicator for each frame;

determining the energy level of each frame; and

deriving the confidence levels based on the SED indicator and the energy level.

17. The method according to claim 16, wherein the confidence level for a given break point is computed as a weighted combination of a first number based on value of the SED indicator in the vicinity of the given breakpoint and a second number based on the energy level of the frame in the immediate vicinity of the breakpoint.

18. The method according to claim 16, wherein the confidence level for a given note is computed as a weighted combination of a first number based on value of the SED indicator in given note and a second number based on the energy level of the frames in the given note.

19. The method according to claim 16, wherein value of the SED indicator for a given frame is relatively large if an energy distribution associated with the frame is concentrated in one or more specified frequency bands.

20. The method according to claim 19, including filtering the melody with a high pass filter prior to segmenting the melody into frames.

21. The method according to claim 20, wherein the energy distribution is determined from a normalized energy spectrum of the frame.

22. The method according to claim 21, wherein the specified frequency band is the upper portion of a 0-4 kHz frequency range.

23. An apparatus for retrieving at least one entry from a music database, wherein each of said entries is associated with a sequence of pitches and beat durations, said apparatus comprising:

means for receiving a digitized representation of an input melody;

a melody-to-note conversion subsystem for identifying breakpoints in said melody in order to define notes therein, said subsystem determining a pitch and beat duration for each note of said melody and associating each note or each breakpoint with a confidence level;

a note-matching engine for determining a score for each of said entries based on a search which minimizes cost of matching the pitches and beat durations of said melody and said entry, wherein said search considers at least one deletion or insertion error in a selected note of said melody and, in this event, penalizes the cost of matching based on the confidence level of the selected note or a breakpoint associated therewith; and

an output subsystem for presenting said at least one entry to a user based on its score.

24. A method of retrieving at least one entry from a music database, wherein each of said entries is associated with a sequence of pitches and beat durations, said method comprising:

receiving a digitized representation of an input melody;

identifying breakpoints in said melody in order to define notes therein, each of said notes being delineated by adjacent breakpoints;

associating a confidence level with each note pertaining to likelihood that said note contains a note insertion error;

determining a pitch and beat duration for each note of said melody;

determining a score for each of said entries based on a search which minimizes cost of matching the pitches and beat durations of said melody and said entry, wherein said search considers at least one insertion error in a selected note of said melody and, in this event, penalizes the cost of matching based on the confidence level associated with the selected note; and

presenting said at least one entry to a user based on its score.

25. A method of retrieving at least one entry from a music database, wherein each of said entries is associated with a sequence of pitches and beat durations, said method comprising:

receiving a digitized representation of an input melody;

identifying breakpoints in said melody in order to define notes therein, each of said notes being delineated by adjacent breakpoints;

associating a confidence level with each note pertaining to likelihood that said note contains a note deletion error;

determining a pitch and beat duration for each note of said melody;

determining a score for each of said entries based on a search which minimizes cost of matching the pitches and beat durations of said melody and said entry, wherein said search considers at least one deletion error in a selected note of said melody and, in this event, penalizes the cost of matching based on the confidence level associated with the selected note; and

presenting said at least one entry to a user based on its score.