Music Indexing with Extracted Main Melody by Using Modified Lempel-Ziv Algorithm

摘要

Extraction of repetitive patterns of the main melody in a given music piece is investigated in this research. A dictionary-based approach is proposed to achieve the task. The input to the proposed system is a piece of music consisting of numerical music scores (e.g. the MIDI file format), and other music forms such as the sound wave have to be converted to numerical music scores first. In the system, segmentation is done based on the tempo information and a music score is decomposed into bars. Each bar is indexed, and a bar index table is built accordingly. Then, an adaptive dictionary-based algorithm known as the Lempel Ziv 78 (LZ-78) is modified and applied to the bar-represented music scores to extract repetitive patterns. The LZ78 algorithm is slightly modified to achieve better results, and the modified LZ78 is named the "Exhaustive Search with Progressive LEngth" (ESPLE). After this step, pruning is applied to this dictionary to remove non-repeating patterns. Modified LZ78 and pruning are repetitively applied to the updated dictionary, which is generated from the previous cycle, until the dictionary converges. Experiments are performed on MIDI files to demonstrate the superior performance of the proposed algorithm.