In lieu of an abstract, here is a brief excerpt of the content:

  • Algorithms for Computing Geometric Measures of Melodic Similarity
  • Greg Aloupis, Godfried Toussaint, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, and David Rappaport

We have all heard numerous melodies, whether they come from commercial jingles, jazz ballads, operatic arias, or any of a variety of different sources. How a human detects similarities in melodies has been studied extensively (Martinez 2001; Hofmann-Engl 2002; Müllensiefen and Frieler 2004). There has also been some effort in modeling melodies so that similarities can be detected algorithmically. Some results in this fascinating study of musical perception and computation can be found in a collection edited by Hewlett and Selfridge-Field (1998).

Similarity measures for melodies find application in content-based retrieval methods for large music databases such as query by humming (QBH) (Ghias et al. 1995; Mo, Han, and Kim 1999) but also in other diverse applications such as helping prove music copyright infringement (Cronin 1998). Previous formal mathematical approaches to rhythmic and melodic similarity, such as the one taken in this article, are based on methods like one-dimensional edit-distance computations (Toussaint 2004), approximate string-matching algorithms (Bainbridge et al. 1999; Lemström 2000), hierarchical correlation functions (Lu, You, and Zhang 2001), two-dimensional augmented suffix trees (Chen et al. 2000), transportation distances (Typke et al. 2003; Lubiw and Tanur 2004), and maximum segment overlap (Ukkonen, Lemström, and Mäkinen 2003). [End Page 67]


Click for larger view
View full resolution
Figure 1.

The first two measures of a well-known melody are shown below our representation using an orthogonal polygonal chain.

Ó Maidín (1998) proposed a geometric measure of the difference between two melodies Ma and Mb. The melodies are modeled as monotonic pitch-duration rectilinear functions of time, as depicted in Figure 1. This rectilinear representation of a melody is equivalent to the triplet melody representation in Lu, You, and Zhang (2001). Ó Maidín measures the difference between the two melodies by the minimum area between the two polygonal chains, allowing vertical translations. The area between two polygonal chains is found by integrating the absolute value of the vertical L1 distance between Ma and Mb over the domain Θ. Arkin et al. (1991) show that the minimum integral of any distance Lp (p ≥ 1) between two orthogonal cyclic chains, allowing translations along Θ and z, is a metric.

In a more general setting such as music retrieval systems, we might consider matching a short query melody against a larger stored melody. Furthermore, the query can be presented in a different key (transposed in the vertical direction) and in a different tempo (scaled linearly in the horizontal direction). Francu and Nevill-Manning (2000) compute the minimum area between two such chains, taken over all possible transpositions. They do this for a constant number of pitch values and scaling factors, and each chain is divided into m and n equal time steps. They claim (without describing in detail) that their algorithm takes O(nm) time, where n and m are the number of unit time-steps in each query. This time bound can be achieved with a brute-force approach.


Click for larger view
View full resolution
Figure 2.

Two orthogonal periodic melodies.

In some music domains such as Indian classical music, Balinese gamelan music and African music, the melodies are cyclic, i.e., they repeat over and over. In Indian music the rhythmic cycles (meter) are called talas (Morris 1998), and in the music of north Bali they are called lambatan (Ornstein 1971). If timbre is added to the talas in the form of drum sounds we obtain what are called thekas, which may be considered in effect as cyclic melodies (Clayton 2000). Such cyclic melodies are also a fundamental component of African and Balinese music (Montfort 1985). Although the untrained listener may assume that African drumming is not melodic, this is far from the truth. In the words of A. M. Jones, "the drums are not merely beating time, for each note has to be beaten on its own correct pitch" (Jones 1954). Furthermore, in the Afro-Cuban Batá drumming, where several double-skinned drums are used, the skins are tuned...

pdf

Share