Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]


Journal of Information Science and Engineering, Vol. 27 No. 1, pp. 95-110 (January 2011)

Music Matching Based on Rough Longest Common Subsequence*

Department of Computer Science and Information Engineering
Tamkang University
Tamsui, 251 Taiwan

In this paper we proposed a music matching method, called the RLCS (rough longest common subsequence) method. It is an improved version of the LCS to avoid some problems occurring in global alignment matching. First a rough equality for two notes is defined for constructing the RLCS of two music fragments. The length of the RLCS of two music sequences defined in this work is a real number, called a weighted length. It is evaluated according to the degree of similarity of every pair of matched notes from the two sequences. This method takes into account both the width-across-query (WAQ) and the width-across-reference (WAR) and combines them with the weighted length of the corresponding RLCS to define a score measurement for the RLCS. The measurement associated with WAQ and WAR enables the proposed method to tolerate dense errors. A dynamic programming algorithm is presented for simultaneously calculating the weighted length of RLCS, the WAQ, the WAR, and the score to determine the RLCS. As a result, the proposed method can perform the matching in a better and simpler manner. In order to speed up the matching process, we use the filtering algorithm proposed by Tarhio and Ukkonen [22] to filter the reference and discard most of the reference areas that do not match. We applied the proposed algorithm to content-based music retrieval. The experimental results showed that with our proposed algorithm the retrieval system provides a higher retrieval rate than that with the local alignment method proposed by Suyoto et al. [20]. The use of the filtering algorithm has been shown to greatly reduce the computation time for exact matching and for approximate matching with a low error tolerance.

Keywords: content-based music retrieval, rough longest common subsequence (RLCS), local alignment, information retrieval, musical similarity, filtering algorithm

Full Text () Retrieve PDF document (201101_07.pdf)

Received August 3, 2009; revised December 23, 2009 & April 6, 2010; accepted July 16, 2010.
Communicated by Suh-Yin Lee.
* This work was supported by the National Science Council of Taiwan, R.O.C. under Grant No. NSC-98-2221- E-032-034.