Pattern Matching in Polyphonic Music



Introduction

Definitions

Algorithm

Example

References


Introduction

A very active area of research in the field of music information retrieval is the problem of music pattern matching. The problem of music pattern matching consists of finding occurrences of short musical patterns within larger musical pieces. This problem has many possible applications. One such application is the possible creation of “query by humming” search engines. Such search engines would enable users to find musical pieces by providing only short extracts of that piece (by humming or other means). Anyone who has ever tried to identify a musical piece without knowing the composer or the name of the piece can appreciate the potential usefulness of such an application!

The problem of music pattern matching can be divided into two different subproblems: audio music pattern matching and symbolic music pattern matching. In the former, the musical pieces and patterns are given in an audio representation, such as a recorded performance of a musical piece. In the latter method, the musical pieces and patterns are given in a symbolic representation, such as the score of a piece. For this tutorial, we will concentrate on symbolic music pattern matching.

In fact, we will concentrate on a specific geometric approach to solving the symbolic pattern matching problem. The algorithm that will be presented was originally published by Anna Lubiw and Luke Taner in Pattern Matching in Polyphonic Music as a Weighted Geometric Translation Problem. As we will see in the next sections, their algorithm gives a flexible frameword for performing approximate pattern matching on musical scores in O(nm log m) time, where n is the number of notes in the score and m is the number of notes in the query pattern.

~ ~ ~ ~ ~

Next Page: Definitions

Eric Blais, © 2004