Melodic matching techniques for large music databases

ABSTRACT

With the growth in digital representations of music, and of music stored in these representations, it is increasingly attractive to search collections of music. One mode of search is by similarity, but, for music, similarity search presents several difficulties: in particular, for melodic query support, deciding what part of the music is likely to be perceived as the theme by a listener, and deciding whether two pieces of music with different sequences of notes represent the same theme. In this paper we propose a three-stage framework for matching pieces of music. We use the framework to compare a range of techniques for determining whether two pieces of music are similar, by experimentally testing their ability to retrieve different transcriptions of the same piece of music from a large collection of MIDI files. These experiments show that different comparison techniques differ widely in their effectiveness; and that, by instantiating the framework with appropriate music manipulation and comparison techniques, pieces of music that match a query can be identified in a large collection.

REFERENCES

• 1: J.C. Bartlett and W.S. Dowling. Recognition of transposed melodies: A key-distance effect in developmental perspective. Journal of Experimental Psychology: Human Perception and Performance, 6(3):501-515, 1980.
• 2: Steven Blackburn , David DeRoure, A tool for content based navigation of music, Proceedings of the sixth ACM international conference on Multimedia, p.361-368, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290802]
• 3: Jan Borchers , Max Mühlhäuser, Design Patterns for Interactive Musical Systems, IEEE MultiMedia, v.5 n.3, p.36-46, July 1998 [doi>10.1109/93.713303]
• 4: H. Charnasse and B. Stepien. Automatic transcription of german lute tablatures: an artificial intelligence application. In Computer Representations and Models in Music, pages 143-170. Academic Press, 1992.
• 5: D. Deutsch. Grouping mechanisms in music. In The Psychology of Music, chapter 4, pages 99-134. Academic Press, Inc., 1982.
• 6: W.J. Dowling. Scale and contour: Two components of a theory of memory for melodies. Psychological Review, 85(4):341-354, 1978.
• 7: W.J. Dowling. Melodic information processing and its development. In The Psychology of Music, chapter 13, pages 413-429. Academic Press, Inc., 1982.
• 8: W.J. Dowling and D.S. Fujitani. Contour, interval and pitch recognition in memory for melodies. The Journal for the acoustical society of America, 49(2):524-531, 1971.
• 9: J.S. Downie. The musifind music information retrieval project, phase iii: evaluation of indexing options. In Canadian Association for Information Science proceedings of the 2$rd Annual Conference, Connectedness: Information, Systems, People, Organisations, pages 135-46. CAIS, 1995.
• 10: J. Edworthy. Interval and contour in melody processing. Music Perception, 2(3):375-388, 1985.
• 11: R. Frances. La Perception de Ia Musique. L. Erlbaum, Hillsdale, New Jersey, 1958. Translated by W.J. Dowling (1988).
• 12: Asif Ghias , Jonathan Logan , David Chamberlin , Brian C. Smith, Query by humming: musical information retrieval in an audio database, Proceedings of the third ACM international conference on Multimedia, p.231-236, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215273]
• 13: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 14: Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980 [doi>10.1145/356827.356830]
• 15: S. Handel. Listening: An introduction to the perception of auditory events. MIT Press, 1989.
• 16: Daniel S. Hirschberg, Serial computations of Levenshtein distances, Pattern matching algorithms, Oxford University Press, Oxford, 1997
• 17: D. Huron and M. Royal. What is melodic accent? converging evidence from musical practice. Music Perception, 13(4):489-516, 1996.
• 18: T. Kageyama, K. Mochizuki, and Y. Takashima. Melody retrieval with humming. In IC'MC Proceedings 1993, 1993.
• 19: A. Marsden. Modelling the perception of musical voices: a ca~e study in rule-bazed systems. In Computer Represents. tions and Models in Music, pages 239-263. Academic Press, 1992.
• 20: Rodger J. McNab , Lloyd A. Smith , Ian H. Witten , Clare L. Henderson , Sally Jo Cunningham, Towards the digital music library: tune retrieval from acoustic input, Proceedings of the first ACM international conference on Digital libraries, p.11-18, March 20-23, 1996, Bethesda, Maryland, United States [doi>10.1145/226931.226934]
• 21: M. Mongeau and D. Sankoff. Comparison of musical sequences. Computers and the Humanities, 24:161-175, 1990.
• 22: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 23: H. Schaffrath. The retrieval of monophonic melodies and their variants: Concepts and strategies for computer-aided analysis. In A. Marsden and A. Pople, editors, Computer Representations and Models in Music, pages 95-110. Academic Press, 1992.
• 24: H.G. Tekman. Interactions of perceived intensity, duration and pitch in pure tone sequences. Music Perception, 14(3):281-294, 1997.
• 25: H.G. Tekman. Effects of melodic accents on perception of intensity. Music Perception, 15(4):391-401, 1998.
• 26: J.M. Thomassen. Melodic accent: experiments and a tentative model. Journal of the acoustical society of America, 71(6):1596-1605, June 1982.
• 27: Alexandra L. Uitdenbogerd , Justin Zobel, Manipulation of music for melody matching, Proceedings of the sixth ACM international conference on Multimedia, p.235-240, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290776]
• 28: Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, v.92 n.1, p.191-211, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90143-4]
• 29: R. van Egmond and D.-J. Povel. Perceived similarity of exact and inexact transpositions. Acts Psychologies, 92:283-295, 1996.
• 30: Hugh E. Williams , Justin Zobel, Indexing Nucleotide Databases for Fast Query Evaluation, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.275-288, March 25-29, 1996
• 31: Justin Zobel , Philip Dart, Finding approximate matches in large lexicons, Software—Practice & Experience, v.25 n.3, p.331-345, March 1995 [doi>10.1002/spe.4380250307]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Algorithms