MELODY EXTRAPOLATION IN GTTM APPROACH
Masatoshi Hamanaka

Keiji Hirata

Satoshi Tojo

University of Tsukuba
hamanaka@iit.tsukuba.ac.jp

NTT Communication Science
Laboratories

Japan Advanced Institute of
Science and Technology

ABSTRACTWe developed a melody-morphing method in which we
input melodies A and B and not only interpolate but also
extrapolate other melodies between those two melodies.
This is done in a systematic order according to a certain
numerical measure, based on the parameters which reflect
the influential features of two input melodies. The main
advantage of our method is that a time-span tree is used,which is acquired from the music surface using a music
theory called Generative Theory of Tonal Music (GTTM).
By using our defined primitive operations of time-span trees,
we can manipulate melodies like numerical expressions.

with another melody chosen by the user. We can play, copy,
paste, or displace the morphed melodies on the pop-up.
♪ Sequence SoftwarePlay（P）

Ctrl+P

Copy（C） Ctrl+C
Paste（V） Ctrl+V
Displace(R）
Ctrl+H

1. INTRODUCTION
Figure 1. Interactive melody generator.
The purpose of this study is to construct an interactive
melody generator for professional as well as novice
composers. Because professional composers want toreflect their intensions accurately, they want to lower theabstraction level of the objects to manipulate the melody.
On the other hand, musical novices tend to raise theabstraction level so as to handle the melody more easily.
Therefore, there are trade-off relationships, which are
difficult to satisfy both professionals and novices needs.
For example, commercial music sequence software only
operates on the surface structure of a melody, that is, thepitch and note-on timing of each note, and thus it isdifficult for novices to generate melodies. On the other
hand, Mozart‟s “Musical Dice Games” [1] generates
agreeable melodies, even if a novice configures theparameters. However, it is difficult to sufficiently reflect
the composers‟ intension.
To solve this trade-off problem, there is a framework,in which a user indicates his or her intension byrepresenting an instance. For example, suppose that a user
intends to arrange melody A by adding some musicalflavor to it and he or she knows that melody B has such
taste. Then, if he or she could use a command such as "addthe nuance of melody B to melody A", he or she would be
able to accurately convey his or her intension to a system.
We call this operation, adding the nuance of melody B to
melody A, 'melody morphing'.
Figure 1 is the layout of our interactive melody
generator in which the melodies on the pop-up menu aremorphing result of a selected melody on the editing score

We have developed a melody-morphing method byusing a time-span tree, which is acquired from the music
surface using the Generative Theory of Tonal Music(GTTM) [2]. The time-span tree is a binary tree, which is ahierarchical structure describing the relative structural
importance of notes that differentiate the essential parts ofthe melody from the ornamental notes.
Our previous melody-morphing method only generates
interpolative melodies and thus the variation of the output
melodies is small [6]. In interpolative melody C generated
from melody A and B, the similarity between A and C ishigher than that of A and B, and the similarity between B
and C is higher than that of A and B. On the other hand, in
extrapolative melody C from melody A and B, a melody B
is an interpolative melody of melodies A and C, or a melody
A is an interpolative melody of melodies B and C (Figure 2).
We propose a melody-morphing method, which enables
the extrapolation of melodies that generates melody C, whichemphasizes the character of melody A or melody B. As partof this overall method, we devised a melody divisional
reduction and melody divisional augmentation methods toreduce or increase the notes of melody A in the differential
branch of the time-span tree of melodies A and B.
(a) Interpolate melody
Interpolate
melody C

Melody A

Melody B(b) Extrapolate melody
Extrapolate
melody C
Melody A

Melody B

Figure 2. Interpolative and extrapolative melodies.

2. GTTM AND MELODY MORPHING
Our melody morphing method uses time-span trees
acquired by analysing the results of the GTTM. Figure 3 isan example of abstracting a melody by using a time-span
tree. There is a time-span tree from melody D, which
embodies the results of the GTTM analyses. The importantnotes are connected to a branch nearer the root of the tree.
In contrast, the un-important notes are connected to theleaves of the tree. We can obtain an abstracted melody E
by slicing the tree in the middle and omitting notes that areconnected to branches under line E. In the same manner, if
we slice the tree higher up at line F, we can get a more
abstracted melody F. We regard the abstraction of a
melody as a kind of melody morphing because melody E is
an intermediate melody between melody D and melody F.

2.3. Melody Morphing Algorithm
Generally, morphing is the changing of one image intoanother through a seamless transition. For example, amorphing method for a face picture is used to create
intermediate pictures through the following operations.
1) Link characteristic points such as eyes and nose, in thetwo pictures (Figure 5a).
2) Rate the intensities of shape (position), color, etc… ineach picture.
3) Combine the pictures.
Similarly, our melody morphing method is used to create
intermediate melodies with the following operations.
(a)

(b)

Figure 5. Examples of linking two pictures/melodies.
3. MELODY MORPHING BY EXTRAPOLATION
Figure 3. Abstraction of melody.
2.1. ATTA
We have previously constructed an automatic time-span tree
analyzer (ATTA), which derives a time-span tree based on
an extended GTTM (exGTTM) that we proposed. The
exGTTM re-formalizes the rules of the GTTM andestablishes an algorithm for acquiring a time-span tree [3, 4].
2.2. Primitive Operations Using Time-Span Trees
For melody morphing, we use the primitive operations of thesubsumption relation (written as ⊑), meet (written as ⊓) andjoin (written as ⊔), as proposed by Hirata [5]. The
subsumption relation represents the relation "an instantiatedobject" ⊑ "an abstract object" (Figure 4a). For example, therelationship among TD, TE and TF, which are the time-spantrees (or reduced time-span trees) of melodies D, E, and F in
Figure 3, can be represented as follows:
TF ⊑TE ⊑TD
The meet operator extracts the maximally common part oftwo time-span trees of two melodies in a top-down manner(Figure 4b). The join operator joins two time-span trees inthe top-down manner as long as the structures of two timespan trees are consistent (Figure 4c).
(a)(b) TB(c) TB
T
T
A

A⊑
Instantiating Abstracting

TA ⊓ TBTA ⊔ TB

Figure 4. Examples of subsumption, ⊑meet ⊓and join ⊔.

By using the time-span trees TA and TB from melodies A andB, we can calculate the most common information TA ⊓TB
which are the essential parts of melody A as well as those of
melody B. The meet operations TA ⊓TB are abstracted from TA
and TB, and those discarded notes are regarded as thedifference information of TA and TB (Figure 6a). We consider
that there are features without the other melody in the
difference information of TA and TB. Therefore, we need amethod for smoothly increasing or decreasing these features.
The melody divisional reduction method can abstract thenotes of the melody in the differential branch of the time-spantree [6]. On the other hand, the melody divisional
augmentation method can increase the notes of the melody inthe differential branch of the time-span tree which is an inverse
process of abstraction. Before explaining melody divisional
augmentation, we will explain melody divisional reduction.
3.1. Melody Divisional Reduction
In the melody divisional reduction method [6], we canacquire melodies Cm (m=1, 2, …, n-1) from TA and TA ⊓TB,
which holds the subsumption relations as follows (Figure 6b).
T A TB TC 1 TC 2 … TC n  2 TC n 1 T A
The value of subscript m of Cm indicates the number ofnotes in the difference information of the time-span treesthat are included in TA and not included in TCm. In Figure 7a,there are nine notes included in TA but not included in TA⊓TB. Therefore, the value of n is eight, and we can acquire
eight kinds of interpolative melodies Cm between TA and TA⊓TB. Hence, melody Cm attenuates features that only have
melody A without melody B.

TA TB

Melody divisional reduction
Melody divisional augmentation

TA TB

TD6

TC5

Melody C5(a)Linking common information of the melodies

TC

Melody D6TD(b) Melody divisional
reduction (section 3.1)
TC5
TD6

TA

TB
Input melody B(d) Combining two melodies(section 3.3)

Input melody A

TC5 TD 6TC 12(c) Melody divisional
Augmentation (section 3.2)

Interpolative melody
TC12

TD6

Extrapolative melody

Figure 6. Overview of melody-morphing method.
3.2. Melody Divisional Augmentation
In the melody divisional augmentation method, we canacquire melodies Cm (m=n+1, n+2, n+3 …), which holds
the subsumption relations as follows (Figure 6c).

TA

TB

T A TC n 1 TC n  2 TC n  3…
The melody divisional augmentation method increases thenumber of notes one by one, which is the opposite processthat the melody divisional reduction method reduces thenumber of the notes one by one (Figure 7b).
Step 1: Decide the level of augmentation
A user determines parameter L, which determines the levelof augmentation. L is from 1 to the number of notes, which
the user wants to increase in the melody.
Step 2: Divide a note in the difference information
Select a note with the longest duration in the difference
information of the time-span tree that are not included in
TA ⊓TB. If two or more notes have the longest duration, we
select the first one. Then, divide the note where the beat isstrongest. The value of strength in each beat can beacquired from the GTTM analysis results [2-4].
Step 3: Determine the pitch of divided notes
If a note contains the strongest beat from two divided notes,
keep the original pitch before the dividing; otherwise, change

the pitch to the most stable one from lowest to highest pitch of
the original melody. The value of stability is calculated basedon the music theory of Tonal Pitch Space [7].
Step4: Iteration
Iterate steps 2 and 3 L times.
3.3. Combining Two Melodies
We use the join operator to combine melodies C and D,
which are results of the divisional reduction oraugmentation using time-span tree of melodies A and B(Figure 6d).
Our previously proposed melody morphing method
only generates interpolative melodies in which the
melodies C and D in Figure 6 are both acquired using
melody divisional reduction. By using the melody
divisional augmentation, we can generate extrapolative
melodies.
The simple join operator is not sufficient for combining
TC and TD, because TC ⊔TD is not always a monophonyeven if TC and TD are monophonies. In other words, theresult of the operation has chords when the time-spanstructures override and the pitches of the notes aredifferent, although both input melodies are monophonies.
To solve this problem, we introduce a special operator [n1,n2], which chooses notes n1 or n2 exclusively, as a result ofn1 ⊔n2. Then, the result of TC ⊔TD is all combinations ofmonophonies generated from the operators.

(a) Divisional Reduction(b) Divisional augmentation

TA

TA

TC 8

TC 9

To measure the similarity between melodies X and Y,
we used the following RN(X, Y), defined by Hirata [5],which indicates how much information is lacking from thetwo melodies as a result of the meet operation.
meet ( X , Y ) N(2)
R  X ,Y  Nma x X N,Y N



where |X|N indicates the number of notes in melody X.
TC - 7

TC 10

TC 6

TC 11

TC 5

TC 12

TC 4

TC 13

TC 3

TC 14

We use 10 pairs of sample melodies A and B, and as aresult of confirmation, all the extrapolative melodies M
from melodies A and B, holds the expression (1).
5.

CONCLUSION

We constructed a melody morphing method forgenerating interpolative melodies and extrapolative
melodies from two input melodies A and B by using melody
divisional reduction and augmentation, which smoothly
decreases or increases the difference information of those
melodies. To generate, interpolative, or extrapolative
melodies, all we need to do is select two input melodies andconfigure the parameters for controlling the reduction oraugmentation level of each melody. We plan to finish
developing the interactive melody generator and evaluate
whether the melody-morphing method is useful for
generating melodies.
6.

REFERENCES

TC 2

TC 15

[1] Langston, P. ''Six Techniques for Algorithmic
Composition'', Proceedings of the International
Computer Music Conference, pp. 153-156, 1989.

TC 1

TC 16

[2] Lerdahl, F., and Jackendoff, R. A Generative Theoryof Tonal Music. Cambridge, Massachusetts: MIT
Press, 1983.
[3] Hamanaka, M., Hirata, K., and Tojo, S.
''Implementing „A Generative Theory of Tonal
Music‟'', Journal of New Music Research, 35:4, 249277, 2006.

TA TB

Figure 7. Melody divisional reduction and augmentation.
4.

EXPERIMENTAL RESULTS

We tried to determine whether the method can generate
the extrapolative melody M from melody A and B whichholds following expression.

R( A, M )  R( A, B) and R( A, M )  R(B, M ), or(1)
R(B, M )  R( A, B) and R(B, M )  R( A, M )where R(X,Y) indicates the similarity between melodies
X and Y.
The meaning of the expression (1) is that a melody B isan interpolative melody of melodies A and M, or a melody
A is an interpolative melody of melodies B and M.

[4] Hamanaka, M., Hirata, K., and Tojo, S. ''FATTA:
Full Automatic Time-span Tree Analyzer'',
Proceedings of the International Computer Music
Conference, Vol. 1, pp. 153-156, 2007.
[5] Hirata, K., and Aoyagi, T. '' Computational Music
Representation Based on the Generative Theory ofTonal Music and the Deductive Object-Oriented
Database'', Computer Music Journal, 27:3, pp. 73-89,
2003.
[6] Hamanaka, M., Hirata, K., and Tojo, S. ''Melody
Morphing Method based on GTTM'', Proceedings ofthe International Computer Music Conference, pp.
155-158, 2008.
[7] Lerdahl, F. Tonal Pitch Space, Oxford University
Press, 2001.