Automatic Generation of Grouping Structure based on the GTTM
Masatoshi Hamanaka1), 2), Keiji Hirata3) and Satoshi Tojo4)
1) Research Fellow of the Japan Society for the Promotion of Science,2) National Institute of Advanced Industrial Science and Technology (AIST),
3) NTT Communication Science Laboratories,
4) Japan Advanced Institute of Science and Technology
m.hamanaka@aist.go.jp

Abstract
This paper describes an automatic grouping system, which
segments the music into units such as phrases or motives,
based on the Generative Theory of Tonal Music (GTTM in
short, hereafter). The GTTM is considered to be one of themost promising theories of music in regard to computer
implementation; however, no order in applying those rules
is given and thus, more often than not, may result in conflictamong them. To solve this problem, we introduce adjustableparameters, which enable us to give priority among rules.
We show the experimental results that our method
outperformed the baseline performance by over thirty percent,tuning the parameters. In addition, we show that the system
displays the time-span tree based on these grouping rules
together with metric information given by input MusicXML.

1

Introduction

The purpose of this study is to automatically derive atime-span tree that assigns a hierarchy of `structural
importance' to the notes of a piece of music. The hierarchy
is based on the generative theory of tonal music (GTTM)(Lerdahl and Jackendoff 1983). Automatic generation of atime-span tree from the music surface enables us to analyze
the deeper structure (Hirata and Aoyagi, 2003). It also
provides a summarization of the music, which can be used
as a representation of search, and thus results in music
retrieval systems (Hirata and Matsuda 2003).
The GTTM is composed of four modules, each of whichassigns a separate structural description to a listener's
understanding of music. These four modules output thegrouping structure, metrical structure, time-span reduction,and prolongational reduction, respectively. The grouping
structure is a hierarchical segmentation which results inmotives, phrases, and sections. The result of grouping is used toderive a time-span tree, together with metrical information ofMusicXML. In this paper, we describe a method to articulate
automatically a transition of notes into groupings by the GTTM.
Previous segmentation methods have been unable toconstruct hierarchical grouping structures because they havefocused on detecting the local boundaries of the melody(Stammen and Pennycook 1994), (Temperley 2001),(Cambouropoulos 2001), (Ferrand, Nelson and Wiggins 2003).
Attempts have been made to implement several of therules of the GTTM grouping structure in computer systems,
but these methods have been incapable of resolving theconflict between the rules (Ida, Hirata, and Tojo 2001),(Touyou, Hirata, and Tojo 2002).
Our system of segmentation based on the GTTM makes
it possible to construct hierarchical grouping structures in a
top-down process using bottom-up detection of local
boundaries. The system is equipped with adjustableparameters, and they enable us to control the strength ofeach rule. When a user changes the parameters, thehierarchical grouping structures change as a result of the
new segmentation. With this system, we came to generate
time-span trees, searching for plausible parameter sets.

2

Problems of applying grouping rules

The grouping structure is intended to formalize the intuitive
belief that tonal music is organized into groups that are in turn
composed of subgroups. These groups are presented
graphically as several levels of arcs below a music staff. There
are two types of rules for grouping in the GTTM: grouping
well-formedness rules (GWFR) and grouping preference rules(GPR). Grouping well-formedness rules are necessary
conditions for the assignment of a grouping structure andrestrictions on these structures. When more than one structure
can satisfy the well-formedness rules of grouping, the grouping
preference rules (GPR) indicate the superiority of one structure
over another. The GPRs consist of seven rules: GPR1
(alternative form), GPR2 (proximity), GPR3 (change), GPR4
(intensification), GPR5 (symmetry), GPR6 (parallelism), andGPR7 (time-span and prolongational stability). GPR2 has twocases: (a) (slur/rest) and (b) (attack-point). GPR3 has four cases:(a) (register), (b) (dynamics), (c) (articulation), and (d) (length).
In this section, we specify the problems with GPRs in
terms of computer implementation.

2.1 Conflict between rules
Because there is no strict order for applying GPRs, theconflict between rules often occurs when applying GPRs
and results in ambiguities in analysis. Figure 1 shows a

simple example of the conflict between GPR2b (AttackPoint) and GPR3a (Register). GPR2b states that a relatively
greater interval of time between attack points initiates agrouping boundary. GPR3a states that a relatively greaterpitch difference in between smaller neighboring intervals
initiates a grouping boundary. Because GPR1 (alternativeform) strongly prefers that note 3 alone not form a group, aboundary cannot be perceived at both 2-3 and 3-4.
To solve this problem, we use adjustable parameters
SGPR j(= 2a, 2b, 3a, 3d, 4, 5, 6) (0≦ SGPR j ≦1) that enable us tocontrol the strength of each rule.
1

2 3

4

5

6

MusicXML[boundary strength] Low-Level boundary

Detection of
low-level boundary
Applying GPR1, 2, 3, 6

[time]

Divide by top down

Detection ofhigh-level boundary
Applying GPR1, 2, 3, 4, 5, 6

GPR3a GPR2b

Figure 1. Simple example of conflict between rules.

Grouping-XML

Figure 2. Processing flow of the system

2.2 Ambiguity in defining GPR4, 5, and 6
The GTTM does not resolve much of the ambiguity thatexists in applying GPR4, 5, and 6. For example, GPR6
(Parallelism) does not define the decision criteria forconstruing whether two or more segments are parallel or not.
The same problems occur with GPR4（Intensification）and
GPR5 (Symmetry).
To solve this problem we attempted to formalize thecriteria for deciding whether each rule is applicable or not.

3

Automatic segmentation
based on the GTTM

systemFigure 2 shows the processing flow of the system. As a
primary input format we chose MusicXML (Recordare LLC
2004) because the format is expected to be a common
interlingua in music notation, analysis, retrieval, and otherapplications. A hierarchical grouping structure wasconstructed top-down using bottom-up detection of local
boundaries. We then designed Grouping-XML as the output
format for segmentation results. In our experiments, we
restrict the music structure to mononphony to correctly
evaluate the performance of each rule.

level children of the notation element.
In this experiment, we prepared the input date inMusicXML with FinaleTM† and DoletTM for Finale plug-in, in
which such tags as dynamics and articulations were not included.

3.2 Application of GPRs
In this section, we discuss the application of GPR1, GPR2a,
GPR2b, GPR3a, GPR3d, GPR4, GPR5, and GPR6. We wereunable to apply GPR3b (articulation) and GPR3c (dynamics)
because MusicXML for our system input does not have dynamic
and articulation elements. The degree of boundary for each rulecan be expressed as DiGPR j= (1, 2a, 2b, 3a, 3d, 4, 5, 6) (0≦ DiGPR j ≦1).
Our segmentation system has thirteen adjustableparameters, which include SGPR j(= 2a, 2b, 3a, 3d, 4, 5, 6) , σ, Ws,
Wr , Wl , TGPR4 , and Tlow-level (Table 1).
Table 1: Thirteen adjustable parameters
Parameters
SGPR jσ
Ws
Wr

3.1 MusicXML
MusicXML is a music representation format based on
XML (extensible mark-up language). It has attribute
elements and note elements. The attribute element contains
the musical attributes of scores, such as the key signature,
time signature, and clef. The time signature includes thenumerator (beats) and denominator (beat-type). The noteelement has a pitch defined by step and octave elements.
Every note also has a duration based on divisions of aquarter note. Several additional elements may be associatedwith a note. Tied notes, slurs, fermatas, and arpeggios are
represented by top-level children of the notation element.
Dynamics, ornaments, articulations, and technicalindications specific to particular instruments are also top-

Wl
TGPR4
Tlow-level

Description
The strength of each rule. j =(2a,2b,3a,3d,4,5,6)
The standard deviation of a normal distribution for GPR5.
Weight of priority of the same rhythm compared with thesame register in parallel segments.
Weight of priority of one end of a parallel segmentcompared with the start of a parallel segment.
Weight of priority of large parallel segments.
The value of the threshold that decides whether GPRs 2
and 3 are relatively pronounced or not.
The value of the threshold that decides whether transition i
is a low-level boundary or not.

GPRs 2, 3, and 4. GPRs 2, 3, and 4 are the rules for atransition of four notes. The degree of the boundary of eachrule indicates whether the transition of i is heard as a groupboundary (DiGPRj =1) or not (DiGPRj =0). GPR4 has an
adjustable parameter TGPR4 (0≦ TGPR4 ≦1) to control thevalue of the threshold that decides whether GPRs 2 and 3
are relatively pronounced or not.
†See http://www.recordare.com/

resti −1 < resti and resti > resti +1

1
DiGPR2a = 
0

1
= ∑
j 0

1
yqi q j r = ∑ ∑ 
k l 
0

(1)

xqi r

resti −1 ≥ resti or resti ≤ resti +1
ioii −1 < ioii and ioii > ioii +1

1
DiGPR2b = (2)ioii −1 ≥ ioii or ioii ≤ ioii +1

0regist i −1 < regist i and regist i > regist i +1

1
DiGPR3a = 

(3)

0
1
DiGPR3d = 0regist i −1≥ regist i or regist i ≤ regist i +1

1
DiGPR4 = 0Pirest > T GPR4 or Piioi > T GPR4 or Piregist > T GPR4

leni −1 = 0 and leni ≠ 0 and leni +1 = 0

(4)

Pi

rest

≤T

GPR4

(5)

DiGPR5 =

1
2π σ

e

2

(6)

where
start : start transition of a group.
end : end transition of a group.
GPR6. GPR6 is the rule for parallelism in the grouping
structure. GPR6 has three adjustable parameters, which are
Ws (weight of priority of the same rhythm compared withthe same register in parallel segments), Wr (weight ofpriority of one end of a parallel segment compared with thestart of a parallel segment), and Wl (weight of priority oflarge parallel segments) (0≦Ws, Wr , Wl ≦1). We define
the parallel level DGPR6 as follows:Gistart
× (1 - W s )jGiendj × WsDiGPR6 = ∑ ∑ 
j r G start × (1 - W ) + G end × W
i j
s
i j
s

0

mi j = 1
mi j = 2(7)

mi j = 3
mi j = 0

wheredivision: duration of a quarter note.
r: length of parallel segments based on the divisionof quarter notes.
Gistart
=
j
Giend
j =

z qi q j r
x qi r + x q j r

× (1 − Wr ) × r 1+Wl +z qi -r q j -r r
x qi -r r + x q j -r r

1
2
mi j = 30y qi q j r
z qi q j r

× (1 − Wr ) × r 1+Wl +× Wr × r 1+Wl

y qi - r q j -r r
z qi -r q j - r r

× Wr × r 1+Wl

qi ≠ qi -1 and q j ≠ q j -1 and qi = qi +1 and q j = q j +1
qi = qi -1 and q j = q j -1 and qi ≠ qi +1 and q j ≠ q j +1
qi ≠ qi -1 and q j ≠ q j -1 and qi ≠ qi +1 and q j ≠ q j +1
else

k

l

g =1

g =1

else

([ ] : Gausian integer )1GPR1 
=
Di


0


j =i −1

GPR5. GPR5 is the rule for symmetry in a grouping
structure. We use a normal distribution with the standard
deviation σ as a symmetry level DGPR5 so that there is apreference to subdivide groups into two parts of equal length.
 i

end


 ∑ ioi j − ∑ ioi j 2 
=
=
j
start
j
start

−
2σ 2

l

g =1

GPR1. GPR1 is designed to prevent a group fromcontaining a single event. Therefore, the boundary must be
stronger than the neighboring transition. The degree of the
GPR1 boundary indicates whether the transition of i is heard
as a group boundary (DiGPR1 =1) or not (DiGPR1 =0).

rest
ioi
registi
Pirest = i +1 i , Piioi = i +1 i , Piregist = i +1
∑ rest j∑ ioi j∑ regist j
j =i −1

k

g =1

else


 i
 ∑ ioik qi =  k =1
 division and Piioi ≤ T GPR4 and Piregist ≤ T GPR4

where
resti : interval between current offset and next onset.
ioii : inter onset intervals.
registi : pitch intervals.
leni : subtraction of duration.
j =i −1(qi − q j )× division = ∑ ioig − ∑ ioig
(qi − q j )× division = ∑ ioig − ∑ ioig and registi = regist j1
zqi q j r = ∑∑ 
k l 
0

leni −1 ≠ 0 or leni = 0 or leni +1 ≠ 0

qi ≤ q j and q j ≤ qi + r
else

GPR j
GPR j
GPR j
≤
× S GPR j∑ Di −1 × S∑ Di
j = ( 2 a , 2 b ,3 a ,3 d , 6 )
j = ( 2 a , 2 b ,3 a ,3 d , 6 )

and

GPR j

∑ Di

j = ( 2 a , 2 b ,3 a ,3 d , 6 )× S GPR j ≥GPR j∑ Di +1

j = ( 2 a , 2 b ,3 a , 3 d , 6 )(8)

× S GPR jelse

3.3 Detection of low-level boundary
Low-level boundaries are detected by MusicXML using
DiGPR1, DiGPR2a, DiGPR2b, DiGPR3a, DiGPR3d and DiGPR6. Tlow-levelis an adjustable parameter for controlling the value of thethreshold that decides whether transition i is a low-levelboundary or not. The degree of low-level boundaries Dilowlevelcan be expressed as follows:
GPR j
GPR 1
1
× S GPR j > T low−level and∑ Di∑ Di−1 = 1 (9)low-level 
=
0

Di

j =(2a,2b,3a,3d ,6)j =(2a,2b,3a,3d ,6)else

3.4 Detection of high-level boundaries
A hierarchical grouping structure is constructed in the
top-down method while local-boundaries are found in thebottom-up way. A group that contains a local boundary
detected iteratively by the next level boundary iˆ iscalculated as follows:
(10)
GPR j
iˆ = argmax
D low−level ×× S GPR j
∑D
i

i

i
j = ( 2 a , 2 b , 3 a , 3 d , 4 , 5, 6 )3.5 Grouping-XML
We designed Grouping-XML as an export format forhierarchical grouping structures. Grouping-XML has groupelements, note elements, and applied elements. Noteelements align the order of onset times, which connect tonotes in MusicXML using Xpointer (W3C 2002) and Xlink(W3C 2001). All note elements are inside hierarchical groupelements. The applied elements are located between the endof a group tag and the start of the next group tag, which iswhere the GPR are applied. Figure 3 shows a simple
example of Grouping-XML. We developed a Grouping-XML
viewer to display grouping structures (Figure 4).

-<group>-<group>+<note id="P1-1-1"/>+<note id="P1-1-2"/>+<note id="P1-1-3"/>+<note id="P1-1-4"/>+<note id="P1-2-1"/></group><applied rule=”2a”/><applied rule=”6”/>-<group>+<note id="P1-2-3"/>+<note id="P1-2-4"/>+<note id="P1-2-5"/>+<note id="P1-2-6"/>+<note id="P1-3-1"/></group></group>

Table 2: F-measure for our method
Baseline
performance
1. TurkishMarch
0.09
2. Wiegenlied
0.41
3. Brindisi
0.03
4. My dearest father
0.03
5. The Nutcracker March
0.01
Melody….

::Total (100 melodies)

GPR2a, GPR6

5

Our method withconfigured parameters
0.95
1.00
0.90
0.11
0.05

:
:

:
:

0.32

0.67

Conclusion

We developed a segmentation system based on the
GTTM. This system makes it possible to constructhierarchical grouping structures. Experimental results showthat the performance of segmentation outperformed thebaseline F-measure by more than thirty percent as a result ofconfiguring the parameters. At the current stage, the timespan tree is generated only by GPR's together with metric
information given by musicXML. We are now planning to
improve the precision of trees, implementing the further
details of Time-span tree generation rules.

Figure 3 Simple example of Grouping-XML.

References

Figure 4 Screen snapshot of Grouping-XML viewer.

4

Experimental results

We evaluated the performance of segmentation using an
F-measure, which is given by the weighted harmonic meanof Precision P (the proportion of selected groupings that are
correct) and Recall R (the proportion of correct groupingsthat were identified). We did not take care that low-level
error is propagated up to higher-level; we counted wrong
answers with ignoring the difference of grouping levels.
Fmeasure = 2 ×

P×R
P+R

(11)

This evaluation required us to prepare correct grouping
data. We collected a hundred pieces of 8-bar length,monophonic, classical music pieces, and asked those whohave expertise in musicology to give them groupings
manually, faithfully with regard to GPR's. Those manual
results were cross-checked by three other experts.
The segmentation changes depending on the parameters
configured. To evaluate the baseline segmentation
performance of our system, we used default parameters,
which were SGPR j(= 2a, 2b, 3a, 3d, 4, 5, 6)=0.5, σ=0.05, Ws,=0.5
Wr =0.5, Wl=0.5, TGPR4 =0.5, and Tlow-level=0.5. It costed us
about 10 minutes on average for a piece to find a plausible
tuning of parameter sets. As a result of configuring theparameters, the performance of segmentation outperformed
the baseline F-measure by more than thirty percent (Table 2).

Lerdahl, F., and R. Jackendoff. (1983). A Generative Theory ofTonal Music. Cambridge, Massachusetts: MIT Press.
Hirata, K., and T. Aoyagi. (2003). “Computational Music Representationon the Generative Theory of Tonal Music and the Deductive
Object-Oriented Database.” Computer Music Journal 27(3), 73–89.
Hirata, K., and S. Matsuda. (2003). “Interactive Music
Summarization based on Generative Theory of Tonal Music.”
Journal of New Music Research, 32:2, 165-177.
Stammen, D. R., B. Pennycook. (1994). “Real-time Segmentationof Music using an Adaptation of Lerdahl and Jackendoff’sGrouping Principles.” In proceedings of the International
Conference on Music Perception and Cognition, pp. 269-270.
Temperley, D. (2001). The Cognition of Basic Musical Structures.
Cambridge, Massachusetts: MIT Press.
Cambouropoulos, E., (2001). “The Local Boundary Detection Model(LBDM) and its application in the study of expressive timing.” In
Proceedings of the International Computer Music Conference,
pp. 290–293. Havana, Cuba: International Computer Music Association.
Ferrand, M., P. Nelson, and G. Wiggins. (2003). “Memory and
Melodic Density: A Model for Melody Segmentation.” In
Proceedings of the XIV Colloquium on Musical Informatics(XIV CIM 2003), pp. 95–98. Firenze, Italy.
Ida, K, K. Hirata, and S. Tojo. (2001). “The attempt of theAutomatic Analysis of the Grouping Structure and Metrical
Structure based on GTTM.” SIG Technical Report, Vol. 2001,
No. 42, pp 49-54, (in Japanese).
Touyou, K, K. Hirata, S. Tojo, and K. Satoh. (2002). “Improvementof Grouping Rule Application in Implementing GTTM.” SIG
Technical Report, Vol. 2002, No. 47, pp. 121-126, (in Japanese).
Recordare LLC. (2004) “MusicXML 1.0 Tutorial.”
http://www.recordare.com/xml/musicxml-tutorial.pdf.
W3C. (2001) “XML Linking Language (XLink) Version 1.0.”
http://www.w3.org/TR/xlink/.
W3C. (2002) “XML Pointer Language (XPointer).”
http://www.w3.org/TR/xptr/.