FIT（情報科学技術フォーラム）2002

LF-5

Applying Voronoi Diagrams in the Automatic Grouping of Polyphony
Masatoshi Hamanaka†

Keiji Hirata‡

Abstract

2 ．Generative Theory of Tonal Music

This paper presents a method of grouping that provides a way
to automatically analyze the grouping structure of polyphony.
Sets of grouping rules have been applied in previous methods,
but these methods were not capable of resolving contradictions
among the rules. In order to solve this problem, we propose amethod where Voronoi diagrams of the notes on the piano-rollformat are used to form the groups.

The generative theory of tonal music is composed of fourmodules, in each of which assigns a separate part of thestructural description of a listener's understanding of music. The
four modules of GTTM are the grouping structure, the metricalstructure, the time span reduction and the prolongational reduction.
Grouping structure is intended to formalize the intuition thattonal music is organized into groups, which are in turn composedof subgroups. The rules for grouping of GTTM are of two kinds:grouping well-formedness rules and grouping preference rules.
Grouping well-formedness rules are necessary conditions for theassignment of a grouping structure and restrictions on thegenerated structures. When more than one structure may satisfy
the grouping well-formedness rules, grouping prefernce rules
only suggest the superiority of one structure over another, not a
deterministic procedure. This is a problem of ambiguity, asdescribed above.

１． Introduction
The purpose of this study is to automatically divide the notes
in polyphony into groups. Two kinds of grouping appear inpolyphony, one in the direction of pitch interval and the other inthe direction of time. Grouping in the interval direction divides
polyphony into multiple homophony (Figure 1a). In the time
direction, notes are grouped from time gap to time gap (Figure1b). Automation of these two forms of division not only allows
us to more deeply analyze musical structures [1]. Moreover,creating a database of the groups obtained by division gives us
the ability to reuse these groups in systems for automatic music
composition and jam session system [2].
GTTM (generative theory of tonal music) [3] is a theory ofmusic which includes a concept of grouping and thus can be used
for deriving the set of rules for the division of notes into groups.
We think that GTTM is the most promising theory of music interms of computer implementation, but there is no strict order for
applying the rules of GTTM. This may lead to ambiguities interms of the results of analysis. The implementation of GTTM as
a computer system has been attempted [4], but the resulting
system was only capable of dealing with the limited polyphonywhich is made up of two monophonies.
In this paper, we propose a method of grouping which is basedon applying the Voronoi diagram. We have developed a methodof grouping rather than naively implementing GTTM so that aresult by our method is equifinal to that of GTTM. We compare
the results of grouping by this method with the results ofgrouping by a human according to GTTM.

3. Voronoi diagrams used for groupingTo overcome the problem, we propose a method of grouping
based on the use of Voronoi diagrams. The result of GTTM is abinary tree that indicates the hierarchical structure of a piece ofmusic. In our method, the hierarchical structure of a piece ofmusic is represented by Voronoi diagrams on a piano-roll.
3.1 Voronoi diagram
A Voronoi diagram partitions a plane into cells, designated by
the set of points P, that is, {p1, p2,..., pn}, such that for each cellwhich corresponds to point pi, all points q in that cell are nearer
to pi than to any other point in P (Figure 2)[5].
dist (q, pi)< dist (q, pj) (pi, pj ∈ P, j≠i)(1)
We can form the Voronoi diagram for a given set of points ina plane as a connected set of segments of half-plane boundaries,
where each of the half-planes is formed by partitioning the plane
into two half-planes, one on either side of the bisector of the line
between each adjacent pair pi and pj.
p1

p6

a: Grouping in the direction of pitch interval.
p5

p2

p7

p4

p3

Figure 2: A Voronoi diagram.

b: Grouping in the direction of time.

3.2 Voronoi diagram for two notes
Our method adopts the piano-roll format as a score, and thus
notes are expressed as horizontal line segments on a piano-roll.
To construct a Voronoi diagram on the score, we need toconsider the Voronoi diagram for multiple horizontal linesegments, which is constructed of linear segments and quadraticsegments.
When two notes are sounding at the same time or no note issounding, the corresponding part of the Voronoi diagram is alinear segment (Figure 3a, Figure 3c). When a single note issounding, the Voronoi diagram becomes a quadratic segment(Figure 3b).

Figure 1: Examples of grouping.

† University of Tsukuba‡ NTT Communication Science Laboratories

101

FIT（情報科学技術フォーラム）2002

a. Two notes soundingb. Only one noteat the same timesoundingc. No note is sounding

Table 1: The performance of our method with three scaling
ratios.
Scaling ratio (ticks/semitone)
90
100
110
Correctness rate
78.5%
78.5%
72.8%
a. Result of our method.

Figure 3: Voronoi diagrams for pairs of notes.
3.3 Voronoi diagram for more than two notes
To construct the Voronoi diagram for more than two notes, weconstruct the Voronoi diagrams for all of the pairs of notes anddelete the irrelevant segments. For example, to construct theVoronoi diagram for notes a, b, and c, we construct threeVoronoi diagrams (Figure 4). The boundaries in the three
Voronoi diagrams then intersect at a point which is equidistantfrom each of the notes. The Voronoi diagram for notes a and b isdivided into two half-lines at the intersection. We then delete that
half-line which is nearer to c than to a or b.
b. Result of GTTM.

bac

Figure 4: Voronoi diagram for more than two notes.
3.4 Scaling problem
A problem of scaling is inevitable when we construct aVoronoi diagram of notes in the piano-roll format. Since thevertical axis of the piano-roll score indicates the pitch (insemitones) and the horizontal axis indicates time (in ticks), theshape of a Voronoi diagram depends on the ratio of the pitch
scale to the time scale. In this paper, we experiment with thefollowing three scaling ratios, 1 semitone = 90 ticks, 1 semitone= 100 ticks, and 1 semitone = 110 ticks. The rules of GTTM interms of time interval and register (GPR2 and GPR3) possibly
contradict each other, but our proposed method avoids such acontradiction by setting the scaling ratio appropriately.

Figure 5: Results of our method and GTTM.

5. Conclusion
This paper described the grouping method based on theVoronoi diagrams. This method makes it possible toautomatically analyze the grouping structure of polyphony.
Experimental results showed that our method performed
correctly, with a correctness rate being above 70 percent.
We now plan to use this method for the automatic creation ofphrase databases for our jam session system and to apply it to theanalysis of deep musical structure.

3.5 Making groups
Hierarchical groups of notes were constructed by converging
adjacent notes iteratively. Here, we introduce the following
principle for making groups; the smallest Voronoi cell is firstmerged to an adjacent group.
By changing the scaling ratio, a distinct Voronoi cell becomes
smallest, and thus a merging pattern also changes.

6. References[1] Keiji Hirata, Tatsuya Aoyagi: "Representation Method andPrimitive Operations for a Polyphony based on Music
Theory GTTM," Journal of IPS Japan, Vol. 42, No. 3, 2002.
(in Japanese)[2] Masatoshi Hamanaka, Masataka Goto, Nobuyuki Otsu:"Learning-Based Jam Session System for a Guitar Trio,"
Proc. of ICMC, 2001.
[3] Fred Lerdahl, Ray Jackendoff: "A Generative Theory ofTonal Music," The MIT Press, 1983.
[4] Kentarou Ida, Keiji Hirata, Satoshi Tojo: "The Attempt ofthe Automatic Analysis of the Grouping Structure andMetrical Structure Based on GTTM," Trans. of IPS Japan,
Vol. 2001, No. 42, 2001. (in Japanese)[5] Franz Aurenhammer: "Voronoi Diagrams - a Survey ofFundamental Geometric Data Structure," ACM ComputingSurveys, Vol. 23, 1991.

4. Experimental Results
We have implemented our method of grouping and compare
the results with correct data obtained by a human (Figure 5). We
evaluate the performance of grouping by using a correctness ratethat we define as follows.
Correctness rate =The number of notes grouped correctly
The number of notes(2)

We gave three different scaling ratios, run the program, andcalculated the correctness rate (Table 1). The correctness rate foreach of the scaling ratios is above 70 percent. The tune that weused in this experiment was the MIDI data of Turkish March.

102