Abstract
Melody is an important property for the perceptual description of Western musical pieces. A lot of applications rely on the evaluation of similarity between two melodies. While several existing techniques assume a monophonic context or extract a monophonic melody from polyphonic pieces, in this paper, we propose to consider the whole polyphonic context to evaluate the similarity without reducing to a monophonic melody. We thus propose a new model and a corresponding methodology that takes into account all the notes, even if they sound at the same time or if they overlap. Our model relies on a quotiented sequence representation of music. A quotiented sequence is a sequence graph defined with an additional equivalent relation on its vertices and such that the quotient graph is also a sequence graph. The core of the comparison method is based on an adaptation of edit-distance metrics, regularly applied in bio-informatic context. This algorithm is currently being used to evaluate the similarity between a monophonic or polyphonic query and a database of polyphonic musical pieces. First experiments show that the adaptation to polyphony does not degrade the quality of the algorithm with monophonic musical pieces. Furthermore, the results of experiments with polyphonic pieces are promising, even if they show some limitations.
This work has been partially sponsored by the French ANR SIMBALS (JC07-188930) and ANR Brasero (ANR-06-BLAN-0045) projects.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hanna, P., Ferraro, P., Robine, M.: On Optimizing the Editing Algorithms for Evaluating Similarity Between Monophonic Musical Sequences. Journal of New Music Research 36(4), 267–279 (2007)
Mongeau, M., Sankoff, D.: Comparison of Musical Sequences. Computers and the Humanities 24(3), 161–175 (1990)
Smith, T., Waterman, M.: Identification of Common Molecular Subsequences. Journal of Molecular Biology 147, 195–197 (1981)
Serrà, J., Gómez, E., Herrera, P., Serra, X.: Chroma Binary Similarity and Local Alignment Applied to Cover Song Identification. IEEE Transactions on Audio, Speech and Language Processing 16, 1138–1151 (2008)
Dannenberg, R.B., Birmingham, W.P., Pardo, B., Hu, N., Meek, C., Tzanetakis, G.: A Comparative Evaluation of Search Techniques for Query-by-Humming Using the MUSART Testbed. Journal of the American Society for Information Science and Technology (JASIST) 58(5), 687–701 (2007)
Bello, J.: Audio-based Cover Song Retrieval using Approximate Chord Sequences: Testing Shifts, Gaps, Swaps and Beats. In: Proceedings of the 8th International Conference on Music Information Retrieval (ISMIR), Vienna, Austria, September 2007, pp. 239–244 (2007)
Downie, J.S., Bay, M., Ehmann, A.F., Jones, M.C.: Audio Cover Song Identification: MIREX 2006-2007 Results and Analyses. In: Proceedings of the 9th International Conference on Music Information Retrieval (ISMIR), September 14-18, pp. 51–56 (2008)
Uitdenbogerd, A.L., Zobel, J.: Manipulation of Music for Melody Matching. In: Proceedings of the Sixth ACM International Conference on Multimedia, Bristol, England, pp. 235–240 (1998)
Paiva, R.P., Mendes, T., Cardoso, A.: On the Detection of Melody Notes in Polyphonic Audio. In: Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR), London, UK (September 2005)
Uitdenbogerd, A.L.: Music Information Retrieval Technology. PhD thesis, RMIT University, Melbourne, Australia (July 2002)
Needleman, S., Wunsch, C.: A General Method Applicable to the Search for Similarities in the Amino Acid Sequences of Two Proteins. Journal of Molecular Biology 48, 443–453 (1970)
Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
Allali, J., Hanna, P., Ferraro, P., Iliopoulos, C.: Local Transpositions in Alignment of Polyphonic Musical Sequences. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 26–38. Springer, Heidelberg (2007)
Horwood, F.J.: The Basis of Music. Gordon V. Thompson Limited, Toronto (1944)
Madsen, S., Typke, R., Widmer, G.: Automatic Reduction of MIDI Files Preserving Relevant Musical Content. In: Proceedings of the 6th International Workshop on Adaptive Multimedia Retrieval (AMR), Berlin, Germany (2008)
Lemström, K., Pienimäki, A.: Approaches for Content-Based Retrieval of Symbolically Encoded Polyphonic Music. In: Proceedings of the 9th Intermational Conference on Music Perception and Cognition (ICMPC), Bologna, Italy, pp. 1028–1035 (2006)
Pardo, B., Sanghi, M.: Polyphonic Musical Sequence Alignment for Database Search. In: Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR), London, UK, pp. 215–222 (2005)
Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery 19, 248–264 (1972)
Typke, R.: Music Retrieval based on Melodic Similarity. PhD thesis, Utrecht University (2007)
Tarjan, R.E.: Data Structures and Network Algorithms. CBMS-NFS - Regional Conference Series In Applied Mathematics (1983)
Toroslu, I.H., Üçoluk, G.: Incremental assignment problem. Information Sciences 177(6), 1523–1529 (2007)
Downie, J.S., West, K., Ehmann, A.F., Vincent, E.: The 2005 Music Information retrieval Evaluation Exchange (MIREX 2005): Preliminary Overview. In: Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR), London, UK, pp. 320–323 (2005)
Kruskal, J.B.: An orverview of sequence comparison. In: Sankoff, D., Kruskal, J.B. (eds.) Time Wraps, Strings Edits, and Macromolecules: the theory and practice of sequence comparison, pp. 1–44. Addison-Wesley Publishing Company Inc., University of Montreal, Montreal (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Allali, J., Ferraro, P., Hanna, P., Robine, M. (2010). Polyphonic Alignment Algorithms for Symbolic Music Retrieval. In: Ystad, S., Aramaki, M., Kronland-Martinet, R., Jensen, K. (eds) Auditory Display. CMMR ICAD 2009 2009. Lecture Notes in Computer Science, vol 5954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12439-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-12439-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12438-9
Online ISBN: 978-3-642-12439-6
eBook Packages: Computer ScienceComputer Science (R0)