| 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] |
¡@
HWEI-JEN LIN, HUNG-HSUAN WU AND CHUN-WEI WANG+
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.
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.