Algorithms for discovering repeated patterns and computing pitch names in music

Опубликовано 7 сентября 2016, 16:17

In this talk, I discuss algorithms for solving two important problems in music informatics, namely, discovering repeated patterns and computing pitch names. An algorithm that discovers the themes, motives and other perceptually significant repeated patterns in a musical work can be used, for example, in a music information retrieval system for indexing a collection of music documents so that it can be searched more rapidly. It can also be used in software tools for music analysis and composition and in a music transcription system or model of music cognition for discovering grouping structure and voice-leading structure. In most approaches to pattern discovery in music, the data is assumed to be in the form of strings. However, string-based methods require exponential time to process polyphonic music when the voice of each note is unknown (e.g., a MIDI format 0 file) or when one is interested in patterns that contain notes from more than one voice. In our approach, these limitations are overcome by representing the music as a set of points in a multidimensional Euclidean space. This point-set pattern matching approach allows the maximal repeated patterns in a passage of polyphonic music to be discovered in quadratic time and all occurrences of these patterns to be found in cubic time. More recently, we have found that the best match for a query point set within a text point set of size n can be found in O(n log n) time by incorporating randomized projection, uniform hashing and FFT into our approach. Also, by using appropriate heuristics for selecting compact maximal repeated patterns with many non-overlapping occurrences, our method can be adapted for data compression. Moreover, the compact representations generated when this compression algorithm is run on music data seem to resemble the motivic-thematic analyses produced by human experts. In the second part of this talk, I focus on pitch spelling algorithms. Such algorithms predict the pitch names (e.g., C#4, Bb5) of the notes in a passage of tonal music when given only the onset time, MIDI note number and possibly the duration and voice of each note. A pitch spelling algorithm is an essential component of a music transcription system. Knowing the letter names of the notes in a passage of music is also very useful in music information retrieval and musical pattern discovery, since it allows for diatonically identical but chromatically different patterns to be matched using fast, exact matching algorithms. The pitch spelling algorithms proposed by Longuet-Higgins, Cambouropoulos, Temperley and Chew and Chen were compared with my own ps13 algorithm by running various versions of these algorithms on a `clean`, score-derived test corpus, C, consisting of 216 movements and containing 195972 notes, equally divided between 8 classical and baroque composers. The most accurate versions of the algorithms were then tested for robustness to temporal deviations by running them on a `noisy` version of the test corpus, denoted by C`. The most accurate algorithm over both C and C` was a version of my ps13 algorithm, which I call PS13s1. This algorithm spelt correctly 99.44 of the notes in C` and was one of the fastest and simplest of the algorithms tested. Most experts claim that the pitch name of a note depends on both voice-leading and the local key. However, in PS13s1, voice-leading is ignored. The line of fifths is used in most of the algorithms tested, including PS13s1. However, in PS13s1, accuracy was improved by modelling the local key as a pitch class frequency distribution instead of a point on the line of fifths, and by keeping pitch names close to the local tonic(s) on the line of fifths rather than close on the line of fifths to the pitch names of neighbouring notes.