Approximate matching algorithms for music information retrieval using vocal input

ABSTRACT

Effective use of multimedia collections requires efficient and intuitive methods of searching and browsing. This work considers databases which store music and explores how these may best be searched by providing input queries in some musical form. For the average person, humming several notes of the desired melody is the most straightforward method for providing this input, but such input is very likely to contain several errors. Previously proposed implementations of so-called query-by-humming systems are effective only when the number of input errors is small. We conducted experiments which revealed that the expected error rate for user queries is much higher than existing algorithms can tolerate. We then developed algorithms based on approximate matching techniques which deliver much improved results when comparing error-filled vocal user queries against a music collection.

REFERENCES

• 1: S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic Local Alignment Search Tool. J. Mol. Biol., 215:403--410, 1990.
• 2: S. F. Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research, 25(17):3389--3402, 1997.
• 3: R. B. Dannenberg. An on-line algorithm for real-time accompaniment. In Proc. 1984 International Computer Music Conference (ICMC '84), pages 193--198, 1984.
• 4: W. J. Dowling. Scale and contour: Two components of a theory of memory for melodies. Psychological Review, 85(4):341--354, 1978.
• 5: Stephen Downie , Michael Nelson, Evaluation of a simple and effective music information retrieval method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.73-80, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345551]
• 6: 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]
• 7: D. Greenhaus et al. Digital tradition folksong database. Available (as of this writing) at http://www.mudcat.org/folksearch.html.
• 8: A. R. Halpern. Memory for the absolute pitch of familiar songs. Memory and Cognition, 17(5):572--581, 1989.
• 9: J.-S. R. Jang, H.-R. Lee, and M.-Y. Kao. Content-based music retrieval using linear scaling and branch-and-bound tree search. In IEEE Int'l Conf. on Multimedia and Expo, Tokyo, JP, August 2001.
• 10: T. Kageyama, K. Mochizuki, and Y. Takashima. Melody retrieval with humming. In Proc. 1993 International Computer Music Conference (ICMC'93), pages 349--351, Tokyo, 1993.
• 11: N. Kosugi. Personal correspondence.
• 12: Naoko Kosugi , Yuichi Nishihara , Tetsuo Sakata , Masashi Yamamuro , Kazuhiko Kushima, A practical query-by-humming system for a large music database, Proceedings of the eighth ACM international conference on Multimedia, p.333-342, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.354520]
• 13: D. J. Levitin. Absolute memory for musical pitch: Evidence from the production of learned melodies. Perception and Psychophysics, 56(4):414--423, 1994.
• 14: D. J. Levitin and P. R. Cook. Memory for musical tempo: Additional evidence that auditory memory is absolute. Perception and Psychophysics, 58(6):927--935, 1996.
• 15: G. Li. Robust regression. In D. C. Hoaglin, F. Mosteller, and J. W. Tukey, editors, Exploring Data Tables, Trends, and Shapes, pages 281--343. Wiley and Sons, New York, 1985.
• 16: A. T. Lindsay. Using contour as a mid-level representation of melody. Master's thesis, Mass. Institute of Technology, 1996.
• 17: R. J. McNab, L. A. Smith, D. Bainbridge, and I. H. Witten. The New Zealand Digital Library MELody inDEX. D-Lib Magazine, May 1997. http://www.dlib.org/dlib/may97/meldex/05witten.html.
• 18: 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]
• 19: M. Mongeau and D. Sankoff. Comparison of musical sequences. Computers and the Humanities, 24:161--175, 1990.
• 20: S. Pauws. CubyHum: a fully operational query by humming system. In Proc. 3rd Int'l Symposium on Music Information Retrieval (ISMIR'02), pages 187--196, Paris, 2002.
• 21: E. D. Scheirer. Tempo and beat analysis of acoustic musical signals. J. Acoust. Soc. Am., 103(1):588--601, Jan 1998.
• 22: T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. J. Mol. Biol., 147:195--197, 1981.
• 23: Alexandra Uitdenbgerd , Justin Zobel, Melodic matching techniques for large music databases, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.57-66, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319470]
• 24: Wildcat Canyon Software. Autoscore Pro 2.0 computer software. Available (as of this writing) at http://www.wildcat.com.
• 25: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Audio input/output

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.5 Sound and Music Computing
          Subjects: Methodologies and techniques

General Terms:
Algorithms, Human Factors

Keywords:
music information retrieval, query by humming