A METHOD AND SYSTEM FOR HUMMING BASED MUSIC INFORMATION RETRIEVAL FOR HANDHELD DEVICES BASED ON NOVEL NORMALIZED STRING EDIT DISTANCE IMPLEMENTATION

FIELD

[0001] The present disclosure is generally related to the field of multimedia communications and more particularly relates to the field of multimedia content retrieval using human hummed queries as an input.

BACKGROUND

[0002] Conventional methods use text as the input query with additional parameters (genre, artist, film) as classification types to get a desirable list. Using such a query model can be a difficult proposition as relevant input criteria may be unknown and may be inexact. The result would be a list which includes multiple copies or may not be the user's desired list. With growing collection of songs in the database the problem becomes compounded.

[0003] The text-based query methods are limiting as the content retrieval of songs need to go through a text value identification of each record and retrieve an appropriate match. This inefficiency is addressed through Query by Humming (QBH) systems. It does a content-based retrieval where the input content is searched in a database of songs and the matching content is found. The input could be in the form of a hummed melody of a desired song and the song from the database that has the matched content is retrieved. The QBH system is a fast and effective method that retrieves the song match by only knowing the melody.

[0004] The current works on QBH focuses on retrieving this list based on melody representations, similarity scores and pitch contours. The current QBH models require database of manual hum or tag referring to the original music files. The QBH models for hand-held devices require database of manual hum or tag referring to the original music files that are stored in a server. The user query is then sent to it to match the corresponding song. There is no specific matching solution available to port the same model into hand-held devices that gives optimized feature extraction and pattern matching. Also, when finding a match the search could result in same similarity for common searched files.

OBJECT OF THE PRESENT INVENTION

[0005] In view of the state of the art mentioned above, it is the object of the present invention to provide an efficient query method which can be applied to retrieve information about a piece of music stored in a database. The comparison time between the user queried melodies with the songs listed in the database is reduced. The results or comparison can be done with the device being connected to the internet. The aforementioned object is achieved by means of the features contained in the independent claims.

SUMMARY:

[0006] Embodiments of the present disclosure described herein provide a method and system for retrieving a list of songs that matches the hummed query/melody.

[0007] An example of a method for the retrieval of songs from a multimedia database system containing melody descriptions of songs comprises listing an index of melodic fragments from a given database of songs through extracting pitch and duration vectors. The method also includes identifying the pitch estimation and note-onset location from a hummed query, wherein the pitch is estimated at short fixed interval. The method constructs a mid-level representation of pitch and note duration information, wherein the relationship between two notes are recorded. Finally the method extracts the matching music compositions from the database module, wherein the match ranks the music compositions in a similarity order.

[0008] An example of a system for retrieval of songs, the system comprises of an electronic device that has a processing segment for processing the Query based Hum (QBH). The processor in the system has a pre-processing unit for processing pulse code modulation (PCM), frequency, bits/sample and number of channels, total number of bytes from the QBH. It also has an extraction unit for extracting the pitch and note duration contours from the QBH. It has a post-processing unit that processes extracted pitch and duration contours to form a mid-level representation in a symbolic manner. Finally, it has a similarity measure unit to find matching compositions of the QBH from the database and rank them in order of similarity.

BRIEF DESCRIPTION OF FIGURES:

[0009] The accompanying figures, similar reference numerals may refer to identical or functionally similar elements. These reference numerals are used in the detailed description to illustrate various embodiments and to explain various aspects and advantages of the present disclosure.

[0010] FIG. 1 is a block diagram of a system for retrieve a music match from the database of songs, in accordance with which various embodiments can be implemented;

[0011] FIG. 2 is a flow chart illustrating the method by which the collection of songs are converted into symbolic format using mid-level representation

[0012] FIG. 3 is a flow chart illustrating the method by which the input melody is passed through feature extraction to obtain the pitch and note duration contours which are converted into symbolic format using mid-level representation

[0013] FIG. 4 is a flow chart illustrating the comparison between the source and destination strings to yield a cost which is then used in the Normalized string edit measure to obtain the optimal edit distance where the correct melody segment is located.

[0014] Persons skilled in the art will appreciate that elements in the figures are illustrated for simplicity and clarity and may have not been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of various embodiments of the present disclosure.

DETAILED DESCRIPTION:

[0015] It should be observed that method steps and system components have been represented by conventional symbols in the figures, showing only specific details that are relevant for an understanding of the present disclosure. Further, details that may be readily apparent to person ordinarily skilled in the art may not have been disclosed. In the present disclosure, relational terms such as primary and secondary, first and second, and the like, may be used to distinguish one entity from another entity, without necessarily implying any actual relationship or order between such entities.

[0016] Embodiments of the present disclosure described herein provide a method and system for retrieving a list of songs that matches the hummed query/melody.

[0017] FIG. 1 is a block diagram of a system 100 for matching the hummed query/melody. The system 100 includes an electronic device 105. Examples of the electronic device 105 include, but are not limited to, a computer, a laptop, a digital camera, a mobile device, a digital album, a digital television, a hand held device, a personal digital assistant (PDA), a camcorder, and a video player.

[0018] The electronic device 105 includes a bus 110 for communicating information, and a processor 115 coupled with the bus 110 for processing information. The electronic device 105 also includes a memory 120, for example a random access memory (RAM) coupled to the bus 110 for storing information required by the processor 115. The memory 120 can be used for storing temporary information required by the processor 115. The electronic device 105 further includes a read only memory (ROM) 125 coupled to the bus 110 for storing static information required by the processor 115. A storage unit 130, for example a magnetic disk, hard disk or optical disk, can be provided and coupled to the bus 110 for storing information.

[0019] The electronic device 105 can be coupled via the bus 110 to a display 135, for example a cathode ray tube (CRT) or liquid crystal display (LCD), for displaying information. An input device 140, is coupled to the bus 110 for communicating information to the processor 115. In some embodiments, an external microphone is used for communicating information to the processor.

[0020] In some embodiments, the steps of the present disclosure are performed by the electronic device 105 using the processor 115. The information can be read into the memory 120 from a machine-readable medium, for example the storage unit 130. In alternative embodiments, hardwired circuitry can be used in place of or in combination with software instructions to implement various embodiments.

[0021] The term machine-readable medium can be defined as a medium providing data to a machine to enable the machine to perform a specific function. The machine-readable medium can be a storage media. Storage media can include non-volatile media and volatile media. The storage unit 130 can be a non-volatile media. The memory 120 can be a volatile media. All such media must be tangible to enable the instructions carried by the media to be detected by a physical mechanism that reads the instructions into the machine.

[0022] Examples of the machine readable medium include, but are not limited to, a floppy disk, a flexible disk, a hard disk, a magnetic tape, a CD-ROM, an optical disk, punchcards, papertape, a RAM, a PROM, EPROM, and a FLASH-EPROM.

[0023] In some embodiments, the processor 115 includes one or more processing units for performing one or more functions of the processor 115. The processing units are hardware circuitry performing specified functions. The processor 115 processes a hummed query that is to be found in the database. The processor 115 includes a pre-processing unit 155 which extracts the audio information (sampling frequency, bits/sample and number of channels, total number of bytes) and Pulse-code modulation (PCM) data from the input query. The processor 115 also includes an extraction unit 160 for estimating the pitch and the note-onset location of the input melody. Further, the processor 115 includes a post-processing module 165 to find the pitch and duration contour levels for the input melody. Finally, the processor 115 includes a similarity measure module 170 that compares the distance measure from the input query to the database songs for all traversed path.

[0024] FIG. 2 shows the flow chart illustrating the method by which the songs that are in Musical Instrument Digital Interface (MIDI) format in the database are converted into symbolic representation.

[0025] The method starts at step 205

[0026] At step 210, a search is done to collect the songs in the storage unit 130 that are of MIDI type. At step 215, the given collection is then sent to the pre-processing unit for pitch detection.

[0027] At step 220, the pre-processing unit155 extracts the note duration from a given collection of songs.

[0028] At step 225, from the resultant collection of MIDI files, an index is created for all the melodic fragments. These melodic fragments are a composition of pitch and note duration vectors.

At step 230, , the pitch frequency and duration of each note is extracted from the MIDI file and is converted into cents. Then the obtained pitch contour is represented using five levels and the duration contour is represented by three levels. Table 1 and 2 depicts the said UDS conversion table. The value of Tm is equal to 0.5 * [mean of duration (cents)].

TABLE. 1
TABLE. 2

[0029] FIG. 3 shows the flow chart illustrating the method by which the input query in the form of a melody is represented to find it comparative list in the database.

[0030] The method starts at 300

[0031] At step 305, an input is given to the system 100 is given in the form of a melody of a desired song. The input can be from a recording device like microphone embedded in handheld electronic devices like mobile phones or music players The melody is in the form of a consonant (Ta') query into a microphone connected to any handheld device (like mobile phones, MP3 players etc) and personal computers (like Desktops, Laptops etc).

[0032] At step 310, the recorded input is then sent to the pre-processing unit 155 for extracting sampling frequency, bits/sample and number of channels, total number of bytes and PCM data. The input melody with its known sampling frequency is subject to a re-sampler of the pre-processing unit 155 to resample the signal to 8 KHz. For the given input signal, the maximum amplitude is found and the frequencies that are below the average sampled value are discarded.

[0033] At step 315, the re-sampled query is then transcribed into a time-frequency representation where the fundamental frequency (pitch) of the audio is estimated at short fixed intervals. The extraction unit 160 has a Fast Fourier Transform based autocorrelation that estimates the frequency level of the pitch. At step 320, the extraction unit 160 is used to identify the voiced segments from the PCM data of the input query. The extraction unit 160 finds the onset locations of the PCM data. It is done so by using a peak-picking algorithm to a detection function. The detection function is found by deriving a product of the weighting function and the power spectrum for an input hum. The weighted spectral energy of the input hum is used as input to the weighting function that performs a band-limiting filter, giving value as unity gain in the frequency region corresponding to (640, 2800 Hz) and falling off linearly to zero gain over a frequency region of 100 Hz on either side. The resultant detection function is now smoothed using a biphasic function (first order Gaussian differentiator) of length 11 and the peaks in the smoothed detection function which are lesser than the predefined threshold (-0.2) are considered as the note-onsets.

[0034] At stage 325, the post-processing unit 165 builds a relationship between a note and its neighbor. This relationship gives the mid-level representation. The post-processing unit 165 collects the note contour output from the mid-level representation and converts it into symbolic form. The post-processing unit 165 looks at the frequency and duration of each note based on pitch-tracking and note segmentation and converts it into cents.

[0035] From the extracted pitch and note-onset information, the pitch and duration contour values are obtained. Prior to this the pitch frequencies of each note are subjected to median operation. The pitch contour is represented using five levels and the duration contour is represented by three levels. Table 1 and 2 depicts the said conversion table. The value of Tm is equal to 0.5 * [mean of duration (cents)].

[0036] For all given ranges pitch contour and duration contour are represented in five and three levels respectively.

[0037] At stage 330, the mid-level representation of the input query is matched with the mid-level representation of the songs in the database.

[0038] FIG. 4 is a flow chart illustrating the comparison between the source and destination strings to yield a cost which is then used in the Normalized string edit measure to obtain the optimal edit distance where the correct melody segment is located.

[0039] The method starts at 400

[0040] At stage 405, the mid-level representation of both the source query and the songs in the database in a string format are sent to the similarity measure unit 170 for comparison.

[0041] At stage 410, the String Edit Distance (SED) is calculated. It is done so by evaluating the minimum edit operations required to match two strings. The edit operations performed between the source and the destination string involves substitution, replacement, insertion and deletion. For each of operation there is a cost associated with it. Assuming there are two strings P and Q and /, j denote positions under consideration in strings P, Q respectively.

• The substitution operation is performed when values at the two positions of strings i.e., P(i) and Q(j) are same. For P (i) = Q (j)\ the operational cost is set to zero.

• The replacement, insertion and deletion operations are performed when values at P(i) and Q(j) are different. P (i) ? Q (j); the operational cost is set to one.

• Insertion operation is performed on a shorter (source) string, which is compared with a longer (destination) string. The operational cost for the insertion operation is set to one.

• Deletion operation is performed on a longer (source) string, which is compared with a shorter (destination) string. The operational cost for the deletion operation is set to one.

[0042] All paths from the source to destination and the minimum edit distance is found by traversing the optimal path derived from the sequence of all the edit operations.

[0043] In case of longer and shorter string matching first the optimal path for general minimum edit distance is tracked and the number of replacement, substitution, deletion and insertion operations is counted in that path. Generally, the total number of replacement, substitution, deletion and insertion operations will be equal to length of optimal path. In edit distance evaluation substitution operation signifies that strings are matching, while replacement, insertion and deletion operations signify the amount of mismatch between the strings. Hence, if the number of substitutions is more it implies strings are more equivalent to each other. On the other hand if the number of replacements is more it implies strings are mismatching with each other.

[0044] For the string distance evaluation between two unequal strings a normalized edit distance (NED) is calculated as follows:

where D (N1, N2) is the basic SED measure between source string 'P, of length N1 and destination string, 'Q', of length N2 and, NR specifies the number of replacement operations in the optimal path. Here the number of replacement operation is considered as this represents the amount of mismatch between two strings. The measure is then divided by length of shorter string.

The Dn value is computed for both pitch and duration contour (Dnp and Dnn) separately and these two values are combined to obtain the final Edit Distance (ED). The final ED is computed as

[0045] The list of retrieved songs from the database module is displayed based on the output of string comparator.

[0046] In the preceding specification, the present disclosure and its advantages have been described with reference to specific embodiments. However, it will be apparent to a person of ordinary skill in the art that various modifications and changes can be made, without departing from the scope of the present disclosure, as set forth in the claims below. Accordingly, the specification and figures are to be regarded as illustrative examples of the present disclosure, rather than in restrictive sense. All such possible modifications are intended to be included within the scope of the present disclosure.

I/We claim:

1. A method for the retrieval of songs from a multimedia database system containing melody descriptions of songs comprising:

listing an index of melodic fragments from a given database of songs through extracting pitch and duration vectors;

identifying pitch estimation and note-onset location from a hummed query, wherein the pitch is estimated at short fixed intervals;

constructing a mid-level representation of pitch and note information, wherein the relationship between two notes are recorded; and

extracting matching music compositions from the database module, wherein the match ranks the music compositions in a similarity order.

2. The method of claim 1 .wherein each song in the database has its melodic representation

3. The method of claim 1, wherein pitch estimation is done using a Fast Fourier Transform (FFT) based autocorrelation.

4. The method of claim 1 .wherein note-onset locations are detected using a detection function

5. The method of claim 1, wherein mid-level representation of pitch and note duration is based on five and three levels respectively

6. The method of claim 1, wherein music compositions in a similarity order are retrieved that require minimum number of string replacement operations in the optimal path.

7. A system for retrieval of songs, the system comprising:

an electronic device comprising:

a processor for processing the Query based Hum (QBH), the processor comprising:

a pre-processing unit for processing pulse code modulation (PCM), frequency, bits/sample and number of channels, total number of bytes from the QBH;

an extraction unit for extracting the pitch and note duration contours from the QBH;

a post-processing unit that processes extracted pitch and duration contours to form a mid-level representation in a symbolic manner; and

a similarity measure unit to find matching compositions of the QBH from the database and rank them in order of similarity.

8. The system of claim 7, wherein the PCM data is processed by:

re-sampling frequency subject to a certain level;

normalizing frequency distribution, by discarding the frequencies that are below an average level.

9. The system of claim 7, wherein pitch information is extracted this comprises:
estimating the pitch of the QBH using a Fast Fourier Transform (FFT) based autocorrelation

10. The system of claim 7, wherein note-onset location is extracted this comprises:

identifying the note-onset location detection using peak-picking algorithm to a detection function the detection function is product of weight function and power spectrum of QBH wherein, the weight function is derived using weighted spectral energy with the band-limiting filter response (value unity/ zero).

subjecting the detection function to a biphasic function (first order Gaussian differentiator) setting certain threshold value to spot the peaks

11. The system of claim 7, wherein the post-processing unit is used to process pitch contour and note duration contour and listing a mid-level representation using five and three levels respectively.

12. The system of claim 7, wherein the similarity measure unit for the QBH in the database of songs that comprises:

Identifying the optimal path from the QBH to the song location using the string edit distance (SED);

Setting a cost for each operation involving substitution, replacement, insertion and deletion performed between source (query) and destination (database songs) strings;

Obtaining the minimum distance between the mid-level representation of database files and query note sequence by equating the lowest cost during comparison; and

Calculating normalized string edit distance for all matches of source and destination strings by computing the unified cost for the total number of edit operations.