Giraud Mathieu

Lifl

Richard Groult

Florence Levé

DETECTING EPISODES WITH HARMONIC SEQUENCES FOR FUGUE ANALYSIS

Fugues alternate between instances of the subject and of other patterns, such as the counter-subject, and modulatory sections called episodes. The episodes play an important role in the overall design of a fugue: detecting them may help the analysis of the fugue, in complement to a subject and a counter-subject detection. We propose an algorithm to retrieve episodes in the fugues of the first book of Bach's Well-Tempered Clavier, starting from a symbolic score which is already track-separated. The algorithm does not use any information on subject or counter-subject occurrences, but tries to detect partial harmonic sequences, that is similar pitch contour in at least two voices. For this, it uses a substitution function considering "quantized partially overlapping intervals" [14] and a strict length matching for all notes, except for the first and the last one. On half of the tested fugues, the algorithm has correct or good results, enabling to sketch the design of the fugue.

INTRODUCTION

A fugue is a polyphonic piece built in imitation, where all voices appear successively sharing the same initial melodic material: a subject and, in most cases, a counter-subject. These patterns are repeated throughout the piece, either in their initial form or more often altered or transposed, building a complex harmonic texture. Many composers wrote fugues, or included fugal parts in larger pieces. The two books of Bach's Well-Tempered Clavier are a particularly consistent corpus, exploring the 24 major and minor tonalities in 48 preludes and fugues.

Fugues are often viewed as one of the pinnacle forms of Western music, and they are also used for pedagogical purposes, in music analysis as in composition. Their structure may look very formal, but still enable high levels of creativity. There are many treatises on fugues, or, more generally, on counterpoint, as for example [START_REF] Kennan | Counterpoint[END_REF] or [START_REF] Norden | Foundation Studies in Fugue[END_REF]. Some of them include a complete musicological analysis of Bach's Well-Tempered Clavier, as the books of S. Bruhn [START_REF] Siglind Bruhn | s Well-Tempered Clavier[END_REF][START_REF] Siglind Bruhn | Analyse und Gestaltung[END_REF]. The fugues are thus perfect candidates for Music Informa-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. c 2012 International Society for Music Information Retrieval.

tion Retrieval (MIR) research, stimulating the development of algorithms on symbolic scores.

A first way to analyze fugues can be to use generic tools detecting repeating patterns or themes, possibly with approximate occurrences. Similarity between parts of a piece may be computed by the Mongeau-Sankoff algorithm [START_REF] Mongeau | Comparaison of musical sequences[END_REF] and its extensions, or by other methods for approximate string matching [START_REF] Clifford | Approximate string matching for music analysis[END_REF][START_REF] Crawford | String matching techniques for musical similarity and melodic recognition[END_REF][START_REF] Orpen | Measurement of similarity in music: A quantitative approach for non-parametric representations[END_REF], allowing a given number of restricted mismatches. Several studies focus on finding maximal repeating patterns, limiting the search to non-trivial repeating patterns, that is discarding patterns that are a subpattern of a larger one with the same frequency [START_REF] Hsu | Efficient repeating pattern finding in music databases[END_REF][START_REF] Karydis | Finding maximum-length repeating patterns in music databases[END_REF][START_REF] Liu | Efficient theme and non-trivial repeating pattern discovering in music databases[END_REF]. Other studies try to find musically significant themes, with algorithms considering the number of occurrences [START_REF] Smith | Discovering themes by exact pattern matching[END_REF], but also the melodic contour or other features [START_REF] Meek | Automatic thematic extractor[END_REF].

More specifically, some MIR studies already focused on fugues. The study [START_REF] Weng | Automatic musical form analysis[END_REF] builds a tool to decide if a piece is a fugue or not, with a method to find occurrences of thematic materials. The bachelor thesis [START_REF] Browles | Creating a tool to analyse contrapuntal music[END_REF] contains methods to analyze fugues, including voice separation. It proposes several heuristics to help the selection of repeating patterns inside the algorithms of [START_REF] Hsu | Efficient repeating pattern finding in music databases[END_REF] which maximizes the number of occurrences. The web site [START_REF] Hakenberg | The Pirate Fugues[END_REF] also produces an analysis of fugues, extracting sequences of some repeating patterns, but without precise formal analysis. Finally, we proposed in [START_REF] Mathieu | Subject and counter-subject detection for fugue analysis[END_REF] a method to detect subjects and countersubjects, based on an analysis of repeating patterns with a diatonic substitution function and a specific length matching. This method finds the precise ends of these patterns in the majority of the fugues of the first book of Bach's Well-Tempered Clavier.

The subject and the counter-subject are focus of musical cognition, and will often be what is remembered from a fugue. However, the link between the different expositions of these patterns occurs in transitional sections called episodes that modulate from one tonality to another [START_REF] Kennan | Counterpoint[END_REF][START_REF] Norden | Foundation Studies in Fugue[END_REF]. The episodes have a part in the development of tension during the fugue.

To our knowledge, no previous MIR study was devoted to analysis of episodes. Episodes can be detected by the absence of subjects and counter-subjects: A perfect detection of subjects and counter-subjects should yield a perfect episode detection. In this paper, we try to retrieve episodes without using any information on subject or counter-subject occurrences. We thus look for a positive identification of episodes. Starting from a symbolic score which is already track-separated, we propose an algorithm to retrieve episodes containing partial harmonic sequences, that is similar pitch contour in at least two voices. Harmonic sequences are commonly used to modulate, and are thus an essential feature of many episodes.

As in [START_REF] Mathieu | Subject and counter-subject detection for fugue analysis[END_REF], the algorithm uses a strict length matching for all notes, except for the first and the last one. We tested several substitution functions to have a sensible and specific approximate matching. Our best results use the "quantized partially overlapping intervals" (QPI), introduced by Lemström and Laine in [START_REF] Lemström | Musical information retrieval using musical parameters[END_REF], that can be also seen as one case of the "General Pitch Interval Representation" defined by Cambouropoulos in [START_REF] Cambouropoulos | A general pitch interval representation: Theory and applications[END_REF].

The paper is organized as follows. Section 2 gives definitions and some background on fugues, Section 3 details our algorithm for episode detection through partial harmonic sequences, and Section 4 details the results on 21 fugues of the first book of Bach's Well-Tempered Clavier. These results were evaluated against a reference musicological book [START_REF] Siglind Bruhn | Analyse und Gestaltung[END_REF]. On half of the tested fugues, the algorithm has correct or good results, enabling to sketch the design of the fugue. The other cases are fugues where the episodes do not show enough harmonic sequences, or where the sequences are too short or too much altered.

PRELIMINARIES

A note x is described by a triplet (p, o, ), where p is the pitch, o the onset, and the length. The pitches can describe diatonic (based on note names) or semitone information. We consider ordered series of notes x 1 . . . x m , that is 1). The series is monophonic if there are never two notes sounding at the same onset, that is, for every i with 1 ≤ i < m, o i + i ≤ o i+1 . To be able to match transposed patterns, we consider relative pitches, also called intervals: the interval series is defined as ∆ x 2 . . . ∆ x m , where Fugue. We now introduce some notions about fugue analysis. These concepts are illustrated by Fugue #2 of the first book of Bach's Well-Tempered Clavier. This fugue has a very regular construction.

x 1 = (p 1 , o 1 , 1 ), . . . , x m = (p m , o m , m ), where 1 ≤ o 1 ≤ o 2 ≤ . . . ≤ o m (see Figure
∆ x i = ( ∆ p i , o i , i ) and ∆ p i = p i -p i-1 .
A fugue is given by a set of voices, where each voice is a monophonic series of notes. In Bach's Well-Tempered Clavier, the fugues have between 2 and 5 voices, and Fugue #2 is made of 3 voices.

The fugue is built on a theme called subject. The first three occurrences of the subject in Fugue #2 are detailed in Figure 4: the subject is exposed at one voice (the alto), beginning on a C, until the second voice enters (the soprano, measure 3). The subject is then exposed at the second voice, but is now transposed to G. Meanwhile, the first voice continues with the first counter-subject that combines with the subject. Figure 3 shows a sketch of the entire fugue. The fugue alternates between other instances of the subject together with counter-subjects and development and modulatory sections called episodes.

Episodes and sequences. The episodes "effect a smooth transition from one key to the next [and] provide variety, as well as relief from a constant emphasis on the subject as a whole" [START_REF] Kennan | Counterpoint[END_REF]. They are often built on portions of material from the subjects of counter-subjects. S. Bruhn lists three roles for an episode in the design of the fugue: "It can link two subject statements by leading from one towards the next; it can be conclusive by resolving tension that was built up by the preceding subject statement; it can represent a different register, appearing basically independent of its surroundings and serving as a color contrast." [START_REF] Siglind Bruhn | Analyse und Gestaltung[END_REF].

The Figure 3 shows the two first episodes of Fugue #2. Note that the term "episode" can also be restrained to the ones after the exposition of all voices, the first episode being called codetta [START_REF] Norden | Foundation Studies in Fugue[END_REF].

The episodes can include cadential passages for the release of tension. However, they are often composed with harmonic sequences, which are passages where a pattern is consecutively repeated starting on a different pitch. Figure 2 shows a simple harmonic sequence, outside of a fugue. Sequences can be diatonic (keeping the same key signature, possibly modulating to a neighbor tonality) or real (possibly gaining or losing some sharps or flats, often modulating to some other tonality).

EPISODE DETECTION

We propose here to detect episodes containing partial harmonic matches in at least two voices. For this, we consider consecutively repeating patterns under a substitution function using a relaxed similarity for pitch intervals, and enforcing length equalities of all notes but the first one and the last one. These are very conservative settings, to have as few false positives as possible.

Consecutively repeating patterns. Formally, in a given voice x, we look for consecutively repeating patterns of p notes, starting at note x e . The pattern x e ...x e+p-1 has a candidate second occurrence x e+p ...x e+2p-1 , and, for larger episodes, we also check for a third (x e+2p ...x e+3p-1 ) and fourth (x e+3p ...x e+4p-1 ) occurrences.

The score I(x, e, p, r) between the pattern x e ...x e+p-1 and its candidate occurrence number r (r = 2, 3 or 4) is defined by the number of intervals matched between the pattern and its candidate occurrence:

I(x, e, p, r) = δ( ∆ x e+1 , ∆ x e+(r-1)p+1 ) + δ( ∆ x e+2 , ∆ x e+(r-1)p+2 ) + • • • + δ f ( ∆ x e+p , ∆ x e+rp )
As in [START_REF] Mathieu | Subject and counter-subject detection for fugue analysis[END_REF], we propose to use a strict length matching for all notes, except for the first and the last one -the length of these notes, at the extremities of the pattern, being more frequently altered. The substitution function δ checks thus pitch intervals and lengths, whereas the substitution function, δ f , for the last note, only considers pitch intervals:

δ(( ∆ p, o, ), ( ∆ p , o , )) =    +1 if ∆ p ≈ ∆ p and = 0 if ∆ p ≈ ∆ p and = -∞ otherwise ( = ) δ f (( ∆ p, o, ), ( ∆ p , o , )) = +1 if ∆ p ≈ ∆ p 0 otherwise ( ∆ p ≈ ∆ p )
The actual comparison of lengths ( = ) also checks the equality of the rests that may be immediately before the compared notes. The length of the first note of the pattern (x e against x e+(r-1)p ) is never checked, as the score actually compares the series of intervals ∆ x e+1 . . . ∆ x e+p against ∆ x e+(r-1)p+1 . . . ∆ x e+rp .

The relation ≈ is a similarity relation on pitch intervals. We use here the "quantized partially overlapping intervals" (QPI) [START_REF] Lemström | Musical information retrieval using musical parameters[END_REF], that defines short intervals (from one to three semitones), medium intervals (from three to seven semitones), and large intervals (starting from six semitones).

These classes can be considered for upward or downwards intervals, giving, with the unison intervals, a total of 7 different interval classes. Two pitch intervals ∆ p and ∆ p will be considered as similar if there exists one class containing both of them.

There is an exact occurrence of the consecutively repeating pattern if I(x, e, p, r) = p-1. For example, on the sequence depicted on Figure 2, for any of the four voices x and for r ∈ [2, 3], we have I(x, 1, 4, r) = 3, since intervals are perfectly similar under the QPI similarity relation. An approximate occurrence can be detected if I(x, e, p, r) is at least equal to a given threshold τ (p).

Here the score I(x, e, p, r) only considers substitution operations, and can be computed in time O(p). The score can be extended to consider other edit operations, with computation through dynamic programming.

Episode detection through partial sequences. On the beginning of the Fugue #2, the consecutively repeating patterns are as follows:

• the second episode fits perfectly into an sequence: I(soprano, 58, 7, 2) = 6, I(alto, 76, 7, 2) = 6 and I(tenor, 21, 16, 2) = 15.

• the first episode has two complete occurrences, as I(soprano, 21, 5, 2) = 4 and I(alto, 41, 6, 2) = 5.

There is no complete third occurrence, as the lengths do not match for one voice: I(alto, 41, 6, 3) = -∞.

The complete algorithm computes I(x, e, p, r) for every voice x, every note x e starting right after a quarter beat, several periods (1 quarter, and 1/2, 1 and 2 measures) and for r ∈ {2, 3, 4} occurrences. The algorithm reports an episode every time that at least two different voices contain a consecutively repeating pattern after the same onset (with τ (p) = 0.5 × p). Overlapping episodes with the same period are merged into an unique episode. The result on the Fugue #2 is depicted at the bottom of Figure 3.

For testing purposes, we used a naive implementation running in O(n 2 ) worst time, where n is the total number of notes in the fugue. Even if similarities between occurrences in a sequence could be computed with tools in existing frameworks (such as the simil tool in the Humdrum toolkit [START_REF] Huron | Music information processing using the humdrum toolkit: Concepts, examples, and lessons[END_REF][START_REF] Orpen | Measurement of similarity in music: A quantitative approach for non-parametric representations[END_REF]), we coded our own implementation to be able to handle some specificities (specific length matching, partial detection in two voices).

RESULTS AND DISCUSSION

Results can be asserted in two different ways:

• We can count the sequences that are located completely or partially in episodes of the ground truth;

• More precisely, we can look at the total length of detected sequences, and compare it to the total length of all ground truth episodes, computing a ratio called length sensibility. This sensibility can be seen as a coverage of episodes by harmonic sequences: it will not reach 100%, as some episodes do not have sequences, and as the sequences may not be spanning all the episodes. We also compute a length specificity as the ratio between the lengths of true positive measures and of detected measures.

The result on Fugue #2 is shown at the bottom of Figure 3. Here 5 episodes out of 6 are detected with partial harmonic sequences. This is musically relevant, since the last episode (measures 29-31) is a cadential end, with a last exposition on the subject on a bass pedal. The ground truth has 14 1/2 measures of episodes. The algorithm outputs 10 measures (length sensibility of 68%) and falsely marks one half measure (2 quarters) as an episode (length specificity of 96%).

The false negatives are: 1 measure at the codetta (due to the shift between the two voices, only 2 occurrences are detected), 2 measures and a half at measure 24 (including a change of voices, see below), and all the 3 measures of the last episode (discussed above). The only false positive is the end of the second episode, which is extended 2 quarters below the next subject occurrence at measure 11, the soprano and the bass voices continuing the sequence (see Figure 4, last measure).

The complete test contains 21 fugues of the first book of Bach's Well-Tempered Clavier (fugues #1, #4 and #9 not showing significant episodic material). We started from .krn Humdrum files [START_REF] Huron | Music information processing using the humdrum toolkit: Concepts, examples, and lessons[END_REF], available for academic purposes at http://kern.humdrum.org/. The output of the algorithm on all these 21 fugues is available at http: //www.lifl.fr/ ˜giraud/fugues. We checked all detected episodes, and Table 1 summarizes the results. On the 1098 measures of this test set, the algorithm labels about 20% of the measures as episodes, and finally identifies 43% of all episodes. A subjective quality assessment on the predictions, looking on the detailed output of each run, gives a good mark on 6 fugues, and a correct mark for 5 out of the 21 fugues.

False positives. There are very few false positives: less than 5% of the partial harmonic sequences overlap with subject and counter-subject occurrences. As for the measure 11 in Fugue #2, this is often because the texture of the episode fades into the next section.

False negatives. The length sensibility, that is the coverage of the episodes (in the ground truth) by the prediction of harmonic sequences is, in average, only 36%. These false negatives can be explained by several facts:

• As mentioned above, the sequences often not cover all the episodes. Moreover, there are some episodes with no harmonic sequence: It is often the case for the last episode, which is thus almost always missed by the proposed method;

• There are some episodes with changes of voices (Figure 5), in which the consecutive occurrences of a pattern are not in a same voice;

• Finally, the algorithm fails to detect some partial harmonic sequences that are too much altered to be recognized with the current threshold, or too short to be discovered.

Figure 5. Partial sequence with a change of voices: the pattern is heard at the soprano, then, transposed, at the alto (measure 24 of Fugue #2).

CONCLUSIONS

We proposed an algorithm retrieving some episodes in the first book of Bach's Well-Tempered Clavier, starting from a symbolic score which is already track-separated. To our knowledge, this is the first MIR study on episodes in fugues.

The algorithm, relying only on partial harmonic sequences detection, gives very few false positives, and already gives good results on some fugues. Enabling voice changes inside harmonic sequences should naturally detect more episodes, but may produce more false positives.

Many improvements are possible to have a better analysis of episodes. Detection of other positive features of the episodes (such as cadential passages) or, most of all, of some negative features (subject and counter-subject occurrences) could probably lead to a complete fugue analysis pipeline with better results.

The algorithm could also be tested on other corpus of fugues. As an example, the web page http://www. lifl.fr/ ˜giraud/fugues shows the output of the proposed algorithm in the fugue of Mozart's Adagio and Fugue in C minor, K 546. Finally, partial or full harmonic sequence detection could be used to help the analysis of other genres. [START_REF] Siglind Bruhn | Analyse und Gestaltung[END_REF]. All lengths ( ) are given in number of measures (m) and quarters (q). The sensibility (sens.) and specificity (spec.) are computed on the lengths (see Section 4). The last column, "quality", is a subjective assessment on the output of the algorithm: find almost all episodes with ≥ 50% length sensibility, almost no false positives with ≥ 90% length specificity (good, +), find most of the episodes, few false positives (correct, =), miss many episodes or produces many false positives (bad, -).

Figure 1 .

 1 Figure 1. A monophonic series of notes (start of Fugue #2, see Figure 4), represented by (p, o, ) or ( ∆ p, o, ) triplets. In this example, onsets and lengths are counted in sixteenths, and pitches and intervals are counted in semitones through the MIDI standard.

Figure 2 .

 2 Figure2. A simple diatonic sequence[START_REF] Bitsch | Précis d'harmonie tonale[END_REF]. The values indicate the intervals from the preceding note of the same voice, in number of semitones. The occurrences #1 and #3 have exactly the same semitone intervals. The occurrence #2 is identical to these occurrences when one considers only diatonic information.

Figure 3 .

 3 Figure 3. Analysis of Fugue #2 in C minor in the first book of Bach's Well-Tempered Clavier (BWV 847). Top: ground truth (analysis by S. Bruhn, used with permission [4], [4, p. 80]). Bottom: the two lines named "detected sequences" show the output of the proposed algorithm, detecting partial harmonic sequences in 5 out of the 6 episodes and 68% of the concerned measures. The only false positive is the end of the second episode: at measure 11, it overlaps with the next occurrence of the subject (S) and counter-subject (CS).

Figure 4 .

 4 Figure 4. Start of Fugue #2 in C minor (BWV 847), showing the ground truth for the first two episodes. Non-episodic parts are grayed. The notes starting the initial patterns and the occurrences of the sequences are circled.

Table 1 .

 1 Detection of episodes in 21 fugues of the first book of Bach's Well-Tempered Clavier. The ground truth is the analysis of

	ground truth	found by the proposed algorithm

Acknowledgements. The authors would like to thank the anonymous reviewers for their valuable comments.