# Hierarchisation algorithm for MORFOS: a music analysis software

Joséphine Calandra, Jean-Marc Chouvel, Myriam Desainte-Catherine

► To cite this version:

Joséphine Calandra, Jean-Marc Chouvel, Myriam Desainte-Catherine. Hierarchisation algorithm for MORFOS: a music analysis software. 2025 International Computer Music Conference (ICMC 2025), Jun 2025, Boston, MA, United States. hal-05066154

HAL Id: hal-05066154

https://hal.science/hal-05066154v1

Submitted on 13 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hierarchisation algorithm for MORFOS : a music analysis software

**Joséphine Calandra**

IReMus, STMS-IRCAM

Collegium Musicæ, Sorbonne Université

calandra@ircam.fr

**Jean-Marc Chouvel**

IReMus

Sorbonne Université

jeanmarc.chouvel@free.fr

**Myriam Desainte-Catherine**

LaBRI

Bordeaux INP

myriam@labri.fr

## ABSTRACT

MORFOS is a music analysis software that offers a hierarchical representation of the musical form called multi-scaled formal diagram. This representation aims at modeling music listening and visualizing an organized segmented music representation.

The notion of hierarchy is fundamental to the definition of structure. Different levels of structure can be defined as, for example, levels containing elements of different temporal scales. For example, a musical work may have a level of structure at the note level, but also a level of structure at the motif or phrase level.

In this article, we present the main algorithm that constitutes MORFOS software: It is a recursive algorithm that allows the construction of the multi-scale formal diagram in real time. We also present the underlying data structures that make memory access and algorithms easier.

## 1. INTRODUCTION

A variety of software tools have been developed to assist in the analysis of musical works. These tools offer diverse approaches to representing and interpreting music, ranging from spectral analysis to real-time performance synchronization. Nevertheless, there is a need for a more comprehensive approach that takes into account the chronological progression and hierarchical organization of musical materials.

The Acousmographe [1] from the Ina-GRM generates representations based on the spectral analysis of the audio signal, with possible annotation. In its continuity, Pierre Couperie developed EAnalysis [2], a software that visualizes sonograms and waveforms, provides analytical data, and allows the creation of graphical representations suited for electroacoustic music. Gabriel Sargent [3] offers a structural analysis inspired by linguistic paradigms and tagms to label and segment musical blocks, but without hierarchy or temporality. As real-time analysis software, Antescofo (IRCAM) [4] synchronizes a score with the musician's performance, predicts the tempo, and tracks musical events in real-time. In the meantime, OSSIA SCORE [5] is a software that models a hierarchical and interactive score for execution.

However, most tools overlook dynamic and hierarchical construction in their analyses. Therefore, we propose a software that incorporates the chronology of musical materials and an ascending construction, based on lower hierarchical levels.

If, according to Luciano Berio [6] "Music is what we hear intending to listen to music", the relation between the musical object, the listener, and its cognitive system must be taken into account. Since H. Schenker [7], music is understood through its underlying hierarchy: "The musical organization is made according to a musical hierarchy that depends on the importance of the musical events". MORFOS is a music analysis software that aims to model musical listening in the continuity of information theory (Shannon [8]) but taking into account some aspects of semiology as presented, for example, by Nattiez [9] or Delalande [10]. The concept of MORFOS is to represent the musical form as a hierarchical organization obtained by segmentation and classification of musical objects.

Hierarchical models of the structure, such as the Generative Theory of Tonal Music by Lerdhal and Jackendhoff [11], are often limited to tonal music. McFee et al. [12] propose enhancing segmentation studies by automatically extending representations to a hierarchical three-level structure. Shibata et al. [13] explore segmentation using clustering methods based on a hierarchical semi-Markov hidden model, focusing on criteria such as homogeneity, repetition, novelty, and regularity. They [14] also propose a hybrid approach with the previous model and an LSTM (Long-Short-Term Memory) neural network. MORFOS, that is not limited to tonal music, is based on the Cognitive Algorithm [15] and relies on general segmenting rules derived from listening understanding provided by the cognitive sciences of music.

In fact, our software MORFOS relies on two main operations: first, the stream is *segmented* into *objects*, then the objects segmented are *classified* according to the previously analyzed objects. Then, the same two operations are repeated at a higher level of segmentation: the objects are gathered into a sequence of objects and *segmented*, then the segmented concatenation of objects is *classified* according to the previously segmented group of objects. The segmented objects are represented by oracles [16] (the oracle is described in section 2.3) at every hierarchical level and related to each other with an augmentation of the data structure called Multi-scale Oracle. In this article, only hierarchical construction is described in detail, while the other algorithms of segmentation and classification are not elaborated upon.

Section 2 presents the definitions and notations for the

Copyright: ©2025 Joséphine Calandra et al. This is an open-access article distributed under the terms of the [Creative Commons Attribution License 3.0 Unported](https://creativecommons.org/licenses/by/3.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
MORFOS algorithm. The next section presents the MOR-FOS algorithms: the main algorithm, and briefly the segmentation and classification algorithms. The fourth section present an analysis on the RWCPop database and the last section discusses then the application of polyphony to the algorithm and presents the perspectives.

## 2. DEFINITIONS AND NOTATIONS

In this section, we define the Formal Diagram, the Multi-scale formal diagram, and its underlying structure, the Multi-scale Oracle.

### 2.1 The Formal Diagram

A Formal Diagram is a paradigmatic representation of materials of a musical work as a function of time.

Materials are classes of substitutable elements. For example, the concept of note A3 is a material, but it can be of any type such as musical phrases or even noise. It is close to the concept of *paradigm*.

We will call *object* an occurrence of a material in a specific musical work. For example, the note A3 at instant t equals 0 in a musical work is an object, and this note played 3 seconds later is another object.

Figure 1 represents the Geisslerlied *Maria Muoter Reinu Maît*, a flagellation song from the XIVth century. The score (top) and the corresponding formal diagram (bottom) are presented in this figure.

The musical material here corresponds to the musical note: The materials are therefore entered in order of appearance on the y-axis, and a cell is entered for the duration of the object at the moment it appears on the x-axis.

A fundamental notion of the formal diagram is the chronological appearance order of the musical materials: the formal diagrams are produced as we go along with the initial representation (score or audio file).

<figure><img src="image_2.png" /><figcaption>Figure 1. Score (top) and Formal Diagram (bottom) of Geisslerlied</figcaption></figure>

### 2.2 Multi-scale formal diagram

A Multi-scale Formal Diagram is the hierarchical and assembled organization of formal diagrams for a given analysis. We define a level of hierarchy by the temporal scale of its constituent elements (note, motif, phrase, etc.)

A multi-scale oracle based on the Geisslerlied is presented in figure 2.

Let us introduce the representation $r^{(n)}$ of level $n$ which corresponds to the word obtained by concatenating all the labels of the materials at level $n$. Each letter corresponds to an acquired *object*. In the example figure 2, we have : $r^0 = abcdadbbdbcddcdeaa faedaedcd$.

<figure><img src="image_3.png" /><figcaption>Figure 2. Multi-scale formal diagram based on the Geisslerlied</figcaption></figure>

The segmented representation $s^n$ at level $n$ represents the segmented materials that constitute the upper-level representation. Segmentations are represented by parenthesized expressions. Each parenthesized expression is called a factor. In the example figure 2, we have :

$$s^0 = (abcd)(adbb)(dbcdd)(cdeaa)(faed)(aedcd).$$

One thing that must be considered is that the multi-scale formal diagram is constructed over time and these representations evolve as new elements are acquired.

### 2.3 Data structures: The Multi-scale Oracle

We propose a hierarchical data structure called the *Multi-Scale Oracle* to store objects and model memory access. The multi-scale oracle is made up of *levels*, each one containing the following 5 data structures: the *oracle*, the *ongoing concatenated object*, the *links table*, the *formal diagram*, and the *material memory*.

These structures are represented on the diagram in figure 3 and are an improvement and formalization of a first implementation described in [17].

#### 2.3.1 The oracle

The objects acquired in the software are represented in memory by a Variable Markov Oracle as presented by [16] and used by [18], and [19]. The oracle is a data structure initially used for compression, then for improvisation. It is an automaton that quickly finds the longest string of similar characters previously heard in the software. Each state of the automaton corresponds to the observation at time $t$ of a discrete time series, while the links represent possible successions and include (for forward links) a label associated with the state to which they point.

However, the oracle does not perform segmentation, so we must create rules to segment the data structures to store objects and access the different levels. To do this, we create different $O^{(n)}$ oracles at each existing level $n$, and we complement them with other data structures that store the information connecting each level: this is the *Multi-Scale Oracle (MSO)*.

#### 2.3.2 The ongoing concatenated object

Intuitively, the *ongoing concatenated object* corresponds to the musical elements we are currently listening to and cognitively constructing (not yet segmented) at each time
<figure><img src="image_4.png" /><figcaption>Figure 3. Multi-scale Oracle</figcaption></figure>

scale. The process of grouping the elements of the current scale is under process, and gives rise to provisional hypotheses concerning future elements.

The ongoing concatenated object $o_c^{(n)}$ of level $n$ is represented by the word corresponding to the string of all the characters read since the last segmentation in this level. At each segmentation, this character string is reset by the new character corresponding to the last heard material, and the new objects are concatenated until a new segmentation takes place.

Let's take the example of the string *abaca* when acquiring the fifth object *a* at level 0

$$r^{(0)} = a_0 b_0 a_0 c_0 a_0$$

$$s^{(0)} = (a_0 b_0)(a_0 c_0)$$

$$r^{(1)} = a_1 b_1$$

At level 0, the last segmentation took place just before the index 4 (starting from index 0), the object being constituted corresponds to all the characters read from it in the representation of level 0: we, therefore, have $o_c^{(0)} = a_0$. At level 1, the last segmentation is before index 1 so $o_c^{(1)} = a_1 b_1$.

This word is the one that is compared at each stage of acquisition with the materials already heard.

### 2.3.3 The links table

The factor oracle is usually purely linear [16]. In MOR-FOS, we have to connect multiple oracles at different levels of the hierarchy. For that purpose, we need to create a new data structure called links table.

The links table $Tl^{(n)}$ of level $n$ is a list that associates each state of the automaton with the index of the corresponding state in the upper-level oracle. This table is updated at each segmentation. During segmentation, all characters in the ongoing concatenated object, which correspond

to several states of the oracle of level $n$, are associated with a single character at level $n+1$. Thus, we add as many elements to the links table as there are characters contained in the ongoing concatenated object of level $n$. These indices have the same value, which is the maximum value of the links table incremented by 1. This value corresponds to the index of the state of level $n+1$ associated with the new segmented object.

In the previous example, when we acquired the fifth level 0 object, we have:

$$r^{(0)} = a_0 b_0 a_0 c_0 a_0$$

$$s^{(0)} = (a_0 b_0)(a_0 c_0)$$

$$r^{(1)} = a_1 b_1$$

$$Tl^{(0)} = (0, 1, 1, 2, 2)$$

<figure><img src="image_5.png" /><figcaption>Figure 4. Oracles and Links Tables on the example $r^{(0)} = a_0 b_0 a_0 c_0 a_0$ upon acquisition of the fifth level 0 object.</figcaption></figure>

Indeed, the first two level 0 objects, $a_0$ and $b_0$, are associated with the first level 1 object ($a_0 b_0$), while the two following level 0 objects, $a_0$ and $c_0$, are associated with the second level 1 object, that is ($a_0 c_0$). The fifth level 0 object, $a_0$, has not yet been raised to the higher level, so it is not yet associated with a higher-level state.

In the same way, level 2 does not yet exist, so $Tl^{(1)} = (0)$. The index 0 corresponds to the initial state of the oracle and not information from the formal diagram. This example is presented in figure 4.

This table gives access to all the levels above and below a given level.

### 2.3.4 The formal diagram

The formal diagram $Df^{(n)}$ of level $n$ corresponds to the formal representation of the current state of the oracle at hierarchical level $n$. This diagram is represented by a matrix $Df = (d_{i,j})$ of size $m \times l$ where $m$ is the number of materials heard so far at level $n$ and $l$ the number of objects heard at level $n$ since the start of the analysis. For each index, $d_{i,j} = 1$ if at time $j$ the material $i$ is analyzed and $d_{i,j} = 0$ otherwise.

Updating the formal diagram then takes place in three distinct steps:
* Adding a material row (if necessary)

* Adding an object column

* Representing the object

A row is added if the rank of the material corresponding to the acquired object is greater than the size of the matrix $Df$. Here, $rg$ is a function used to obtain the rank of a letter defined on an alphabet $A^{(n)}$. The concatenation operation `concat(s)` takes as input a coordinate $s$ among $(col, lin)$. This coordinate indicates if a row $(lin)$ containing $l$ zeros is concatenated, or if a column $(col)$ containing $m$ zeros is concatenated. So we have:

If $rg(x_t) > m$:

$$Df_{m,l} \xrightarrow{concat \atop lin} Df_{m+1,l}$$

A column of the size of the current material count is then concatenated:

$$Df_{m+1,l} \xrightarrow{concat \atop col} Df_{m+1,l+1}$$

The representation of the object in the formal diagram then consists of assigning the value 1 to the index $d_{i,j}$ with $i = rg(x_t)$ and $j = l + 1$.

Let us return to the example *abaca*, this time during the acquisition of the second object of level 1, that is to say before the classification of the second factor of the segmented representation of level 0. Before classification at level 1, we have:

$$ 
\begin{aligned}
r^{(0)} &= a_0 b_0 a_0 c_0 a_0 \\
s^{(0)} &= (a_0 b_0)(a_0 c_0) \\
r^{(1)} &= a_1
\end{aligned}
$$

$$Df^{(0)} = b_0 \begin{pmatrix} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix} \\ c_0 \begin{pmatrix} 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

with $a_0, b_0, c_0 \in A^{(0)}$ and

$$Df^{(1)} = a_1 \begin{pmatrix} 1 \end{pmatrix}$$

with $a_1 \in A^{(1)}$

The material labels are not stored in the matrix because they are directly correlated to the line number. They are displayed here on these first examples for informational and educational purposes.

### 2.3.5 The material memory

The material memory $Mm^{(n)}$ of level $n$ corresponds to the two following data structures: The *history table*, and the *autosimilarity matrix*.

The level $n$ history table provides the correspondence between all the level $n + 1$ materials obtained up to time $l$ and the materials that constitute them at level $n$. This is an array of pairs $(x_i, w_i)$ where $x_i$ is a letter corresponding to the top-level material $n + 1$ and $w_i$ is a factor corresponding to the equivalent word of the current level $n$. In this way, the history table enables the relationship between materials on different levels to be memorized outside time.

In the example after the acquisition of the fifth object and classification of the segmented object (ac), we have:

$$Th^{(0)} = ((a_1, a_0 b_0), (b_1, a_0 c_0))$$

and

$$Th^{(1)} = ()$$

The self-similarity matrix corresponds to the matrix $S = (s_{i,j})_{1 \le i,j \le m}$ where $m$ is the number of materials heard, such that $\forall i, \forall j \in [1, m], s_{i,j} = sim(w_i, w_j)$ where $sim(w_i, w_j)$ is the function which returns the similarity value between the factors $w_i$ and $w_j$ of $A^{(n)}$.

## 3. MORFOS HIERARCHICAL ALGORITHMS

This section presents the MORFOS's pseudo-algorithm. It is divided into three parts: The Main Algorithm is the algorithm's main loop, which updates all the data structures and creates the hierarchy. The Segmentation Algorithm determines whether or not segmentation is taking place, and the Classification Algorithm classifies objects in an optimized way. These algorithms are recursive and are applied to each level of the hierarchy in the same way.

### 3.1 The main algorithm

The main algorithm consists of calling the function `cognitive_algorithm(level n, partial representation rp, marker m)`. A partial representation $rp$ is defined as a subword of size 1 to $l$ of a representation $r = x_1...x_l$. The function takes as argument a level $n$ generally initialized to 0, a partial representation $rp$ initialized to $r^{(0)}$, and an end-of-algorithm marker $m$ initialized to 0. The algorithm 1 presents the main function.

**Algorithm 1** cognitive_algorithm(level $n = 0$, partial representation $rp = r^{(0)}$, marker $m = 0$)

If level $n$ does not exist and $m == 0$
    init_mso_n()

While $rp$ is analysed:

$c \leftarrow parse rp$
    $Df^{(n)}(c, t) \leftarrow 1$
    print($Df^{(n)}$)

If (segmentation(n, c, cs) and $m == 0$) or ($m == 1$ and $|o_c^{(n)}| > 0$)
        $sup_level(n + 1, m)$
        $o_c^{(n)} \leftarrow concatenate(o_c^{(n)}, c)$

If $n == 0$ and EOS
        $m \leftarrow 1$

If $m == 1$
        $sup_level(n + 1, m)$

$o_c^{(n)} \leftarrow concatenate(o_c^{(n)}, c)$

**Algorithm 2** init_mso_n()

$O^{(n)} \leftarrow init_oracle params$
    $Tl^{(n)} \leftarrow [0]$
    $Mm^{(n)} \leftarrow (tab empty), matrix empty)$
    $Df^{(n)} \leftarrow matrix empty$
    $o_c^{(n)} \leftarrow string empty)$
In the algorithm 2, $Tl^{(n)}$, $Df^{(n)}$, $o_c^{(n)}$ and $Mm^{(n)}$ are the data structures of the links table, the formal diagram, the ongoing concatenated object and the material memory of level $n$ as defined above. The function init_oracle initializes the variable markov oracle $O^{(n)}$ according to a set of default parameters params and parse rp takes as argument a partial representation rp and returns the first object of this representation. The algorithm 3 is presented and corresponds to the function for moving to the next level. It takes the same arguments as the main function.

<caption>**Algorithm 3** sup_level(level n, object c, marker m)</caption>

```
s ← classification(n, cc)
t_{n+1} ← max(Tl^{(n)}) + 1
For i in range(|o_c^{(n)}|)
    Tl^{(n)} ← concatenate(Tl^{(n)}, t_{n+1})
o_c^{(n)} ← string empty
    cognitive_algorithm(n + 1, s, m)
```

The main function is recursive and it is divided into three parts.

The first part corresponds to the initialization of the various data structures at the current level if they do not exist. The $O^{(n)}$ oracle of level $n$ is initialized with the initialization function provided in the module variable markov oracle developed in [19]. The links table $Tl^{(n)}$ of level $n$ is initialized with a node of value 0 which corresponds to the index of the initial state of the oracle. The material memory $Mm^{(n)}$ of level $n$ is initialized with an empty table and an empty matrix, while $Df^{(n)}$, the formal diagram of level $n$, is initialized with an empty matrix. The ongoing concatenated object $o_c^{(n)}$ of level $n$ is also initialized with an empty character string. The function starts a loop that analyses the partial representation rp supplied as an argument to the function. It adds the new object acquired at this level to the data structures. First, an object called c is retrieved, corresponding to the first object read from the rp representation and obtained using the parse function. Firstly, a state corresponding to the character c analyzed on the string s is added to oracle_n with the appropriate function provided in the module variable markov oracle. Then, the formal diagram $Df^{(n)}$ is updated, i.e. the material corresponding to object c is added by adding an extra line to the formal diagram if it doesn't already exist, and the value of the matrix corresponding to material c and time t is set to 1. The updated formal diagram is then displayed.

In the second part, a segmentation test is carried out according to a certain number of segmentation criteria cs, the level n (and more precisely the data structures that make it up), and the newly acquired object c. This test is performed by a function segmentation(n, c, cs) which returns 1 if there is segmentation at time t and 0 otherwise. This function is described in more detail in the next section.

The classification operation is performed if the segmentation test is validated at time t. This operation also considers the data structures at level n and a set of classification criteria cc. It returns the material corresponding to the ongoing concatenated object $o_c^{(n)}$. This function is also detailed in the following section. The ongoing concatenated object at level n is then compared with the objects of a higher

level that already exist in the history table of the material memory and s becomes the label of the next level corresponding to the ongoing concatenated object. If the object does not exist, the history table $Th^{(n)}$ is updated with the pair $(s, o_c^{(n)})$ with s as the new label. After classification, the links table at level n is updated with the corresponding index of the higher-level node. The ongoing concatenated object is then reset to the empty string and the function cognitive_algorithm(n+1, s, m) is called at the upper level with s as the upper-level representation, the new object s corresponding to an instance object of the material associated with the ongoing concatenated object. At upper levels, the character string corresponds to a single object, and the function returns to the lower level when there is no segmentation. So, if the function is called at the first level, the representation $r^{(0)}$ is read as long as there is no segmentation. Finally, whether there is segmentation or not, $o_c^{(n)}$ is updated by concatenating the analyzed character c.

The question of terminating the algorithm without creating an infinite number of levels arises. To solve this, we use a marker. This brings us to the third part: when the last character of the initial representation $r^{(0)}$ is read, the marker goes and remains to one. The segmentation at each level is then systematically applied. The sup_level function is therefore called again for the last characters of each level, without creating a new state for each level. Then, the reading and segmentation of the remaining characters in the intermediate levels are completed a few steps later.

## 3.2 The segmentation algorithm

The segmentation function is defined as segmentation(level n, object c, criteria cs): boolean, which returns 1 if segmentation occurs and 0 otherwise.

The parameter level n provides access to all data structures associated with the current level, including:

* The ongoing concatenated object, which contains the level n objects forming the higher-level n+1 object.

* The oracle of level n, that enables comparisons with similar objects previously identified.

* The links table, which provides segmentation information between objects within the oracle.

The parameter c, representing the object, supplies details about the most recently acquired object.

The segmentation criteria consists of a predefined set of rules used to determine whether segmentation occurs. To support modularity, one of the software's primary goals, we aim to allow developers to define and integrate their own segmentation rules.

## 3.3 The classification algorithm

The classification algorithm is implemented as the function classification(level n, criteria cs): material. This function adds a new object, formed from the ongoing concatenated object at the current level, to the higher-level oracle. The addition process involves an optimized comparison, leveraging the oracle's structure for efficient integration.
## 4. EXAMPLES ON RWCPOP DATABASE

A study was carried out on the RWC pop database<fnref n="1" />, a corpus consisting of 100 pieces of pop music produced by the Japan's National Institute of Advanced Industrial Science and Technology (AIST). Each track is provided in audio and MIDI format, and a symbolic analysis was computed by [20]. We are interested here in the analysis of the symbolic format. Each work is structured on three musical scales: time, bar, and section. Each cell in the file corresponds to a musical bar, and the chords contained in the bars are annotated according to a precise methodology. Each line of the file also corresponds to a section, the label of which is specified in the first column according to naming conventions. We have processed the file in such a way as to describe each beat of the work by a chord and then convert this notation into a character string in the format supported by MORFOS. In this way, each chord notation is translated into a different symbol, even if it is a variation of a given chord. We then fed the string to the software and analyzed the segmentations obtained.

### 4.1 MIREX Analysis

One approach is to compare the segmentations obtained at the higher level (section) of the reference segmentations proposed by Bimbot et al. with the equivalent segmentation obtained with MORFOS. To do this, we propose to use the evaluation tasks defined in the MIREX2 (Music Information Retrieval Evaluation eXchange) framework defined by [21]. We are interested in five specific measures to accurately measure the quality of the segmentation obtained:

* Precision (measured at 0.5 seconds and 3 seconds);

* Recall (measured at 0.5 seconds and 3 seconds);

* F-measure (measured at 0.5 seconds and 3 seconds);

* Ref-to-est deviation;

* Est-to-ref deviation.

The measurements were calculated using the Python library `mir_eval` with the function `mir_eval`. `evaluate(ref Intervals, ref labels, est Intervals, est labels)` which takes the segmentation intervals and the associated reference label and estimated labels as arguments.

One difficulty, however, is to know which level of the multi-scale formal diagram to use to compare with the reference segmentations at the section level: for each formal hierarchical diagram, we kept the values of the level for which the F-measure at 3.0' was the maximum, to strike a happy medium between over-segmentation and under-segmentation. We performed the same analysis on the entire database, using the following rules:

* For the classification rule, we used the Needleman-Wunsch alignment techniques [22]. If the alignment is higher than a threshold defined at 0.976, then the compared segments are similar.

* For the segmentation rules, we used a panel of the grammatical rules implemented in MORFOS. Those are defined by:

$$1. (ab + a \Rightarrow (ab)(a)$$

$$2. (ab)(ab + c \Rightarrow (ab)(ab)(c)$$

$$3. (ab)(a + b \Rightarrow (ab)(ab)$$

$$4. (a + a \Rightarrow (aa \text{ and } a + b \Rightarrow (ab)$$

$$5. |(a...b + a| < low\_bound \Rightarrow (a...ba \text{ and } |(a...b + c| > high\_bound \Rightarrow (a...b)(c)$$

$$6. (a + a \Rightarrow (aa \text{ and } (aa + b = (aa)(b)$$

where + means the acquisition of the following object, `low_bound` equals 3 elements and `high_bound` equals 16 elements, `|.` is the length of the word, and the closed parenthesis '}' means that there is a segmentation meanwhile the opened parenthesis starts a new word. We will call this set of rules Set 1.

The synthesized MIDI files have a tempo of around 120 bpm, which corresponds to two beats per second. We therefore propose an analysis at two beats per second i.e. a margin of error of 1 beat (0.5") and 6 beats (3.0"). The results obtained are presented in table 1.

<table><caption>**Table 1.** Results of precision, recall, and f-measure of the RWC pop database at 0.5 seconds and 3.0 seconds for a tempo of 120 bpm.</caption><tr><td>P@0.5</td><td>R@0.5</td><td>Fm@0.5</td><td>P@3.0</td><td>R@3.0</td><td>Fm@3.0</td><td>RE dev.</td><td>ER dev.</td></tr><tr><td>0.41</td><td>0.49</td><td>0.39</td><td>0.56</td><td>0.63</td><td>0.53</td><td>2.89</td><td>2.18</td></tr></table>

We have an average precision of 41% and a recall of 49%. This rises to a precision of 56% and a recall of 63% in the 6 beats around the reference segmentation. The average deviation is 2.89' and 2.18' for a track at 120 bpm, which corresponds between 5 and 6 beats.

Several factors may explain these results: firstly, the automatic estimation of the level may be inadequate and distort the results: this is reflected in a strong imbalance between the measurement of precision and recall (Pop 82 for example). On the other hand, when we look at the detailed results, we can see that some pieces performed very well (e.g. Pop 62). In contrast, other pieces show very poor results (Pop 99 for example): on the one hand, the weak results may be due to the robustness of the software that has a strong impact on the subsequent segmentation of the current level, as well as for higher levels. Another observation is that precisely the same rules are not necessarily the most appropriate for the entire database. The rule where the size of the word is chosen will not necessarily be the same depending on whether the music piece is binary or ternary. One suggestion is, therefore, to subdivide the database into sets of relevant rules, or test several rules on the database and keep the best results from each rule. Table 2 shows the results obtained for the specific examples 52, 66, and 99.

<table><caption>**Table 2.** Results of precision, recall, and f-measure at 0.5 seconds and 3.0 seconds for a tempo of 120 bpm of RWC Pop 62, 82 and 99.</caption><thead><tr><th>rwc pop n°</th><th>level</th><th>P@0.5</th><th>R@0.5</th><th>Fm@0.5</th><th>P@3.0</th><th>R@3.0</th><th>Fm@3.0</th><th>RE dev.</th><th>ER dev.</th></tr></thead><tbody><tr><td>62</td><td>3</td><td>0.78</td><td>0.78</td><td>0.78</td><td>0.78</td><td>0.78</td><td>0.78</td><td>0.0</td><td>0.0</td></tr><tr><td>82</td><td>3</td><td>1.0</td><td>0.18</td><td>0.3</td><td>1.0</td><td>0.18</td><td>0.3</td><td>32.0</td><td>0.0</td></tr><tr><td>99</td><td>2</td><td>0.15</td><td>0.18</td><td>0.17</td><td>0.46</td><td>0.55</td><td>0.5</td><td>2.0</td><td>4.0</td></tr></tbody></table>

<footnote n="1">¹ https://staff.aist.go.jp/m.goto/RWC-MDB/rwc-mdb-p.html
11/21/2024</footnote>

<footnote n="2">² https://mir-evaluation.github.io/mir.eval/ 11/21/2024</footnote>
## 4.2 specific case of RWC Pop 11

We have chosen to focus on one specific example: RWC Pop 11. To simplify reading, we have added vertical cross-segments between the levels to indicate the segmentation of a given level and the corresponding moment in time of the lower levels.

Figure 5 shows the formal diagram of the RWC Pop 11 piece obtained with the parameters described above as Set 1. The segmentations obtained are shown in grey, while the reference segmentations are shown in red. We have also annotated the segmentations of the reference sections, also presented in table 3, with the corresponding letters.

<table><caption>Table 3. Reference segmentation of RWC Pop 11.</caption><tr><td>1/2</td><td>16</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>J1/C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>A</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>B</td><td>32</td><td>BbM7</td><td>C7</td><td>A7d9*</td><td>Am7</td></tr><tr><td>C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>A'</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>Am7</td></tr><tr><td>B</td><td>32</td><td>BbM7</td><td>C7</td><td>A7d9*</td><td>D7s4</td></tr><tr><td>C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>B</td><td>32</td><td>BbM7</td><td>C7</td><td>A7d9*</td><td>D7s4</td></tr><tr><td>C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>1/2</td><td>16</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>J2/C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>C</td><td>32</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr><tr><td>(5/4)J3*/C</td><td>40</td><td>Dm7</td><td>G7</td><td>Bb&9</td><td>FM7</td></tr></table>

In this case, we can see precise segmentation, but over-segmentation in the section scale at level 2 and under-segmentation regarding the section scale at level 3. With regard to labeling, one striking observation is that the dimension studied for the analysis, harmony, is not sufficient to distinguish the different annotated sections. In fact, almost the entire work is made up of the same 4 chords: it is therefore the instrumentation, which is not studied here, that makes it possible to determine the segmentation: thus, segments I, J, a and C are considered identical by the algorithm and made up of materials a, b, c and d from levels 0 and 1. Only section B, recognized at both occurrences and made up of materials *fghifhjk* is distinguished. It is therefore necessary to put this hierarchical formal diagram into perspective with another formal diagram on another dimension such as rhythm or instrumentation.

## 5. DISCUSSION AND PERSPECTIVES

The data structure of the multi-scale oracle is an augmentation of the factor oracle. The factor oracle is chosen because it models the links between elements that follow the longest similar states, enabling to model attention phenomena in cognitive mechanisms. Nevertheless, this oracle is linear, whereas we wish to model hierarchical processes: the links table is created and connects states of upper and lower time scales, representing structure. The remaining states, not yet segmented, are stored in the ongoing concatenated object, while the segmented characters are stored in the material history and represented in the formal diagram. The multi-scale oracle, which distinguishes each level, may be limiting when analysing musical works that might represent "intermediate" levels, for example when the music suddenly switch from a binary to a ternary metric. While the grouping of ternary elements would correspond to a higher level than the grouping of binary elements, for the moment they are in the same level, which can create a potential decay of the higher levels. We could then introduce a "flexibility" of the levels where they

would correspond to the duration of the segmented objects, by changing the indexation of the hierarchy in the model.

Evaluation on the RWC Pop database gives mixed results, highlighting potential problems with rule generalization and automatic segmentation level estimation. Further investigation and development of adaptive strategies may be required.

The processing mechanisms described above operate on an information flow in which the end of one object marks the beginning of the next. Consequently, they do not allow polyphonic analysis in the contrapuntal sense. This limitation is explained by the choice, when automating the algorithm, to concentrate on the problem of hierarchy, leaving aside that of voice separation. It will then be necessary to adapt the Multi-scale Oracle. A first step would be to test it with audio files with separated voices. Then, the algorithm would read separated streams for the different voices in the software, but which would share the same memory. Each object in the different voices should be analyzed in the chronological order in which they appear, and the software should then alternately scan each voice to select the next element to be analyzed. Elements played simultaneously will therefore be processed successively but as a grouped process: a note of a chord processed second will be evaluated without considering the acquisition in the memory of the first processed note of the chord.

## 6. CONCLUSION

After presenting the multi-scale formal diagram and its representations, we describe the Multi-Scale Oracle data structure that stores objects and models memory access. The multi-scale oracle is made up of levels, each containing the oracle, the ongoing concatenated object, the links table, the formal diagram, and the material memory.

The main loop of the MORFOS algorithm is also presented: it is built on the recursion principle. Each time a new material is acquired, the data structures are updated and a segmentation test is performed. If segmentation is achieved, then the classification test for the higher-level object is carried out when the higher-level object is acquired, where the algorithm is called up again. Nevertheless, polyphonic music pieces cannot be analysed now and an adaptation of the data-structure and hierarchical algorithm should be made.

## 7. REFERENCES

[1] Y. Geslin and A. Lefevre, "Sound and musical representation: the Acousmographe software," in *In Proceedings Of The 2004 International Computer Music Conference (ICMC 2004)*, 2004.

[2] P. Couprie, "EAnalysis: Developing a Sound Based Music Analytical Tool," *S. Emmerson, L. Landy (éd.)*, *Expanding The Horizon Of Electroacoustic Music Analysis*, Cambridge, Cambridge University Press, vol. 27, pp. 170–194, 2016.

[3] G. Sargent, "Estimation de la structure de morceaux de musique par analyse multi-critères et contrainte de régularité," Ph.D. dissertation, PhD Thesis, Rennes University, 2013.
<figure><img src="image_6.png" /><figcaption>**Figure 5.** Multi-scale formal diagram of RWC Pop 11.</figcaption></figure>

[4] A. Cont, "ANTESCOFO: Anticipatory Synchronization and Control of Interactive Parameters in Computer Music." in *International Computer Music Conference (ICMC)*, Belfast, Ireland, 2008, pp. 33–40.

[5] J.-M. Celerier, P. Baltazar, C. Bossut, N. Vuaille, J.-M. Couturier, and al., "OSSIA: Towards a unified interface for scoring time and interaction," in *Proc. Int. Conf. on Technologies for Music Notation and Representation - TENOR 2015*, Paris, France, 2015.

[6] L. Berio, *Entretiens avec Rossana Dalmonte*. Paris, Lattès, 1983.

[7] H. Schenker, *Das Meisterwerk in der Musik: Ein Jahrbuch*. Munich, Vienna and Berlin: Drei Masken Verlag, 1925-30, 1925, vol. 3 vols, Vol. 1.

[8] C. Shannon, "A Mathematical Theory of Communication," *The Bell System Technical Journal*, vol. 27, pp. 379-423, 1948.

[9] J. Nattiez, *Musicologie générale et sémiologie*. Christian Bourgois, 1987.

[10] F. Delalande, *La musique au-delà des notes*. Presse Universitaires de Rennes, 2019.

[11] F. Lerdhal and R. Jackendoff, *A generative theory of tonal music*. Cambridge, Mass.: MIT Press, 1983.

[12] B. McFee and K. Kinnaird, "Improving structure evaluation through automatic hierarchy expansion," in *20th International Society for Music Information Retrieval Conference, Delft, The Netherlands*, 2019.

[13] G.Shibata, R.Nishikimi, E.Nakamura, and K.Yoshii, "Statistical Music Structure Analysis Based on a Homogeneity-, Repetitiveness-, and Regularity- Awar e Hierarchical Hidden Semi-Markov Model," in *Proc. of the 20st Int. Society for Music Information Retrieval Conf., Delft, The Netherlands*, 2019.

[14] G.Shibata, R.Nishikimi, and K.Yoshii, "Music Structure Analysis Based on an LSTM-HSMM Hybrid Model," in *in Proc. of the 20st Int. Society for Music Information Retrieval Conf., Delft, The Netherlands*, 2019.

[15] J.-M. Chouvel, *Analyse Musicale, sémiologie et cognition des formes temporelles*. L'Harmattan, Paris, 2006.

[16] C. Allauzen, M. Crochemore, and M. Raffinot, "Factor oracle: a new structure for pattern matching; Theory and Practice of Informatics." in *Proceedings of SOF-SEM'99*, Paris, France, 1999.

[17] Author1, Author2, and Author3, "Title," in *Conference*, 2021.

[18] S. Dubnov, G. Assayag, and A. Cont, "Audio Oracle Analysis of Musical Information Rate," 10 2011, pp. 567–571.

[19] C.-i. Wang and S. Dubnov, "Pattern discovery from audio recordings by Variable Markov Oracle: A music information dynamics approach," in *2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, 2015, pp. 683–687.

[20] F. Bimbot, G. Sargent, E. Deruty, C. Guichaoua, and E. Vincent, "Semiotic Description of Music Structure: an Introduction to the Quaero/Metiss Structural Anno-tations," *Proceedings of the AES International Conference*, 01 2014.

[21] J. Downie, M. Bay, A. Ehmann, and M. Jones, "Audio Cover Song Identification: MIREX 2006-2007 Results and Analyses." 01 2008, pp. 468–474.

[22] S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," *Journal of Molecular Biology*, vol. 48, no. 3, pp. 443–453, 1970.