Emilios Cambouropoulos
email: emilios@mus.auth.gr

Costas Tsougras
email: tsougras@mus.auth.gr

INFLUENCE OF MUSICAL SIMILARITY ON MELODIC SEGMENTATION: REPRESENTATIONS AND ALGORITHMS

In this paper a computational model is presented that extracts patterns from a given melodic surface and, then, following the assumption that the beginning and ending points of 'significant' repeating musical patterns influence the segmentation of a musical surface, the discovered patterns are used as a means to determine probable segmentation points of the melody. 'Significant' patterns are defined primarily in terms of frequency of occurrence and pattern length. The special status of non-overlapping immediately repeating patterns is examined. All the discovered patterns merge into a single 'pattern' segmentation profile that signifies points in the surface that are most likely to be perceived as points of segmentation. The effectiveness of the proposed melodic representations and algorithms is tested against a series of melodic examples.

INTRODUCTION

Musical similarity not only establishes relationships between different musical entities (such as rhythmic and melodic motives, themes and variations, harmonic progression groups etc.) but also enables -in the first place -the definition of such entities by directly contributing to the segmentation of a musical surface into meaningful units.

Models of melodic segmentation are often based on local Gestalt-based factors that identify points of local maximal change in various musical parameters such as IOIs, pitch intervals, dynamic changes and so on. Higher-level processes, however, play an important role as well. In this study, a central assumption is that similar musical patterns tend to be highlighted and perceived as units/wholes whose beginning and ending points influence the segmentation of a musical surface.

Pattern-matching techniques have been employed in attempts to formalise musical similarity. There have been, however, relatively few attempts to tackle the difficult issue of pattern extraction (i.e. extracting important patterns in one or more musical sequences). Overviews of the application of pattern processing algorithms on musical strings can be found in [START_REF] Crawford | String Matching Techniques for Musical Similarity and Melodic Recognition[END_REF][START_REF] Rolland | Musical Pattern Extraction and Similarity Assessment[END_REF][START_REF] Cambouropoulos | Pattern Processing in Melodic Sequences: Challenges, Caveats and Prospects[END_REF][START_REF] Meredith | Algorithms for Discovering Repeated Patterns in Multidimensional Representations of Polyphonic Music[END_REF]. Recent research that directly links pattern extraction to melodic segmentation via memory-based modeling is presented by [START_REF] Ferrand | Unsupervised Learning of Melodic Segmentation: A Memorybased Approach[END_REF] and [START_REF] References Bod | Memory-Based Models of Melodic Analysis: Challenging the Gestalt Principles[END_REF]; additionally, [START_REF] Temperley | Parallelism as a Factor in Metrical Structure[END_REF] link parallelism to metrical structure and, indirectly, to melodic segmentation.

The aim of this paper is to examine the relation between musical parallelism and segmentation via computational modeling. This study does not provide a comprehensive stand-alone computer program for melodic segmentation; it rather explores melodic surface representation issues and issues relating to the pattern extraction mechanism itself through the application of a series of different representations and algorithm variants on a number of progressively more 'difficult' melodic examples. The main goal is not to provide a comprehensive solution to the problem of melodic parallelism but rather to shed light on various aspects of the problem and to enable a better understanding of it. Throughout the paper a number of melodic examples illustrate the strengths and weaknesses of the overall approach. The current study is a continuation of the earlier research presented in [START_REF] Cambouropoulos | Musical Parallelism and Melodic Segmentation[END_REF][START_REF] Cambouropoulos | Musical Pattern Extraction for Melodic Segmentation[END_REF].

SEGMENTATION AND MUSICAL SIMILARITY

Segmentation of a musical surface is a central part of musical analysis; an initial selected segmentation can seriously affect subsequent analysis as a great number of inter-segment musical structures are excluded a priori.

The most commonly acknowledged (and perhaps most prominent) factors in musical segmentation relate to the perception of local discontinuities of the surface (e.g. longer note in between shorter ones or larger pitch interval in between smaller intervals etc.) -one such model is the Local Boundary Detection Model (LBDM) proposed by (Cambouropoulos 2001a). Higher-level processes, however, also affect the segmentation of a musical surface. Perhaps the most important of these higher-level mechanisms is musical similarity, i.e. similar musical patterns tend to be highlighted and perceived as units/wholes whose beginning and ending points influence the segmentation of a musical surface.

For instance, a model for determining local boundaries would select the interval between the 3 rd and 4 th notes of Frère Jacques (Figure 1) as a local boundary (larger pitch interval in between smaller ones) whereas it is obvious that a boundary appears between the 4 th and 5 th notes because of melodic repetition. The focus of this study is primarily a special case of melodic similarity, namely immediate repetition of melodic passages. Such repeating passages often diverge towards their endings, contain small variations and the repeated passage may be transposed. David [START_REF] Lidov | Structure and Function in Musical Repetition[END_REF] calls this kind of repetition formative repetition. Its function is to establish or to 'form' motives and phrases. It is herein assumed that it involves fundamental pattern discovery processes primarily at the melodic surface (not reductions of the surface) and essentially is independent of more abstract learned idiom-specific schemata (e.g. harmony, tonality, meter). This kind of melodic similarity is omnipresent in music.

From a cognitive point of view, it is suggested that elaborate pattern extraction processes are more likely to be applied on relatively short melodic excerpts due to the heavy computation involved. Such activity is usually more intense at the beginning of a musical piece/section where new musical materials are introduced and established. Once a number of such musical ideas have been extracted links to further new instances (varied or not) can be made more efficiently.

It is herein assumed that similarity processes for melodic segmentation tasks are confined essentially to the melodic surface in contrast to melodic categorisation tasks (i.e. creating motivic/thematic categories after segments have been defined), which require similarity measurements at deeper levels of musical structure as well (see [START_REF] Cambouropoulos | Automated Motivic Analysis Via Melodic Clustering[END_REF][START_REF] Cambouropoulos | Melodic Cue Abstraction, Similarity and Category Formation: A Formal Model[END_REF] for a computational model of melodic categorisation). This seems to be necessary because extracting patterns at reduced versions of the melodic surface would result in ambiguous segmentations, as it would not be possible to define where exactly the boundaries of the repeated patterns should be placed (since there are notes missing from the reduced version). This problem, in some sense, defeats the point of using pattern extraction at reduced versions of the surface for melodic segmentation. Of course, musical similarity appears in many guises at deeper levels of musical structure but in such cases it is likely that this sort of abstract similarity is not the most crucial factor in segmentation tasks -other factors such as gestalt-based local boundary detection factors or learned schemata (e.g. harmonic cadences) are responsible for segmenting the surface and only then are more sophisticated comparisons of segments made possible at more abstract levels of description.

The musical examples presented in this paper for testing the proposed algorithms have been selected on the basis that the segmentation process for these cases relies primarily on melodic parallelism and not on local detail grouping factors (actually, local gestalt-based factors provide clearly incorrect boundaries). It is common that these two segmentation components (i.e. local gestalt-based factors and parallelism) reinforce each other but, for the sake of clarity, examples have been selected that illustrate a conflict between the two approaches and a clear predominance of the parallelism factor.

In this paper, the pattern extraction algorithm is applied at parametric profiles of the melodic surface for pitch intervals (diatonic intervals, a step-leap representation and some further more refined representations) and for interonset intervals (IOI ratios). An important aspect of the paper is to discover which of these parameters (or combination of them) is more appropriate for the segmentation task and to show how a 'balanced' representation that is neither too specific nor too general may yield better results in more cases. It should be noted, however, that the issue of representation is examined primarily in order to show how important it is and how better representations can be devised rather than to propose a 'best' solution.

AN ALGORITHM FOR SEGMENTATION

VIA PATTERN EXTRACTION

The PAT Algorithm

The pattern extraction model (see Appendix), which consists of the exact pattern extraction algorithm and selection function, provides a means of discovering 'significant' melodic patterns. There is, however, a need for further processing that will lead to a 'good' description of the surface (in terms of exhaustiveness, economy, simplicity etc.). It is likely that some instances of the selected pitch patterns should be dropped out or that a combination of patterns that rate slightly lower than the top rating patterns may give a better description of the musical surface. In order to overcome this problem a very simple methodology has been devised -see Table 1.

Construction of the pattern boundary strength profile (PAT)

A pattern extraction algorithm is applied to one (or more) parametric sequences of the melodic surface as required. No pattern is disregarded but each pattern (both the beginning and ending of pattern) contributes to each possible boundary of the melodic sequence by a value that is proportional to its Selection Function value. That is, for each point in the melodic surface all the patterns are found that have one of their edges falling at that point and all their Selection Function values are summed. This way a pattern boundary strength profile is created (normalised from 0-1). It is hypothesised that points in the surface for which local maxima appear are more likely to be perceived as boundaries because of musical similarity.

Table 1

In the melodic example of Frère Jacques (Figure 1

The PAT algorithm (revised)

The above example consists only of exact full repetitions. This, however, is not usually the case. A very frequently encountered situation is when two patterns diverge towards their ends (see Lerdahl and Jackendoff, 1983, p.51). This intuition has been incorporated into the current model by making a very simple modification to the method described in Table 1:

only the beginnings of patterns contribute to the strength of the pattern boundary profile.

In the example of Figure 2 the revised PAT model detects correctly the beginning of the repeated phrases (the initial PAT algorithm inserts spurious peaks at the endings of the exactly repeating parts of the phrases but the revised PAT algorithm correctly identifies the beginning of the second phrase).

* *

both edges of patterns

REPRESENTATION OF THE MELODIC SURFACE

Abstract representation

The pattern boundary detection model, as described to this point, can discover repeating patterns in the diatonic pitch interval domain that may or may not diverge towards their endings (patterns may be transposed).

What happens if some intervals are not exactly the same (as, for instance, the first intervals of the repeating phrases in Figure 3)? How can rhythmic information be also taken into account? It is suggested that a more abstract representation for pitch intervals may be useful, such as the 'refined contour' representation (or step-leap representation), especially if it is coupled with duration information. The step-leap encoding comprises of 5 distinct symbols (+step, +leap, -step, -leap, same) whereby an interval of one diatonic step (i.e. minor or major 2 nd ) is a 'step', a larger interval is a 'leap' and an interval of zero steps (between repeating notes) is 'same' -this is a rather too limited alphabet. If it is combined with duration symbols (or duration ratios) then the alphabet becomes rich enough to capture all the necessary information so that the pattern boundary detection model may operate effectivelly. In this encoding each interval of a melody is represented as a tuple [step-leap interval, duration ratio].

This further adjustment to the model enables it to segment correctly more difficult cases such as the one depicted in Figure 3, giving correct results, at the same time, for the previous examples presented in this paper. The diatonic pitch interval matching fails as the first interval of the repeating phrase is a 3 rd rather than a 4 th interval -the combined step-leap and duration ratio encoding enables the correct segmentation of the melody -local boundaries are not capable of providing a correct segmentation.

A variant of the PAT algorithm for further flexibility

Approximation can be introduced into an exact patternmatching process by using a more abstract representation at the level of the initial string of symbols.

For instance, a pitch interval representation such as the step/leap representation (or even step/smallleap/medium-leap/large-leap etc.) allows different size leaps to be matched. A problem, however, is that the abstract categories in the representation have sharp boundaries and no instance may belong to more than one category -this way, borderline members can never be matched to other 'similar' members of other categories (e.g. a 3 rd interval as a member of leap can never be matched to a 2 nd interval which is a step).

Consider, for instance, the sequence of pitch intervals in figure 4. The step-leap representation allows the extraction of the two different underlined patterns (see representation A in figure 4). A musician, however, would consider the second half of the sequence as a (near-exact) repetition of the first half (the pitches of this example are taken from Bach's Well-Tempered Clavier, Book I, Fugue in F# major -see figure 7). This match can be achieved only if the first 3 rd interval in the second half of the pitch sequence can be matched with the corresponding 2 nd interval of the first half.

An abstract symbolic representation can become more flexible in terms of category gradedness and membership if instances are allowed to be members of more than one category. In the following examples, a 3 rd interval is allowed to be an instance of either step or leap (s/l) -see representation B in Figure 4. Whichever of the alternative abstractions (step or leap) allows the longest patterns to emerge is selected (the first 3 rd interval of the second half of the melody is taken to be a member of step and is thus matched to the corresponding 2 nd interval of the first half as this gives a longer melodic repetition). The case where a 2 nd and a 3 rd interval should be considered similar is not simply some rare exception in music. It is a rather common phenomenon especially when themes appear in their dominant form (see, for instance, the tonal answers of almost half of Bach's fugue themes from the two books of the Well-Tempered Clavier). In figures 5, 6 & 7 some examples are presented (NB: Bach fugue themes and their tonal aswers are presented as belonging to the same auditory stream -this is not musically correct but is not cognitively implausible -a streaming algorithm could generate tentative streaming options including the ones presented in the examples).

The exact pattern matching algorithm (described above) that extracts all repeating patterns can be adjusted so as to cope with representations that allow alternative symbols for elements of the initial string (ongoing research is examining issues of algorithm efficiency). Examples of the application of the new version of the PAT algorithm are given in Figures 5,6 step Unison 2 nd 3 rd 4 th 5 th 6 th 7 th 8 th 9 th 10 th 11 th … Figure 8 A possible abstract representation for pitch intervals -in this representation overlap between categories is allowed. Such a representation could prove to be more powerful than the more standard step-leap or contour representations as it allows rather high discriminability between intervals and also significant flexibility. It was tested on all the examples in this paper giving correct results.

CONCLUSION

Overall, the methods and results presented in this study provide an informing attempt to address formally the difficult issue of musical parallelism and its links to melodic segmentation. The examples against which the proposed algorithm was tested were known to pose serious problems for local detail grouping algorithmsadditionally these examples contain gradually more difficulties regarding melodic similarity. The proposed model is quite successful in tackling all these problems yet it requires further experimentation and development before it can be integrated in a comprehensive model of melodic segmentation.

Figure 1

 1 Figure 1 Frère Jacques -Segmentation profile according to the Local Boundary Detection Model (LBDM) and the Pattern Boundary Detection Model (PAT) for the diatonic pitch interval profile -local maxima indicate positions that may be considered as points of segmentation.

Figure 2

 2 Figure 2 Beginning of the finale theme of Beethoven's 9 th Symphony-Segmentation profile according to the Local Boundary Detection Model (LBDM) and the Pattern Boundary Detection Model (PAT) for the diatonic pitch interval profile. The strong pattern boundaries that indicate the end points of the exactly repeating parts of the two phrases (indicated by asterisks) are eliminated in the version of the model that takes into account only the beginnings of patterns.

Figure 3

 3 Figure 3Theme of Mozart's G minor Symphony K550, section III. Segmentation profile according to LBDM and the PAT model for the combined step-leap and duration ratio profile. The diatonic pitch interval matching fails as the first interval of the repeating phrase is a 3 rd rather than a 4 th interval -the combined step-leap and duration ratio encoding enables the correct segmentation of the melody -local boundaries are not capable of providing a correct segmentation.

Figure 4

 4 Figure 4 The step-leap representation allows the extraction of two patterns repeating twice each (singleand double-line underlined patterns in representation A). The proposed representation that allows overlapping of pitch categories -in this case, a 3 rd interval can be a member of either step or leap (s/l)allows the matching of the second half of the sequence to the first half (see rep. B).

Figure 5

 5 Figure5Upper voice (theme and tonal answer as one melodic 'stream') from the opening of Bach's Well-Tempered Clavier, Book I, Fugue in F# major. Segmentation profile according to LBDM and the PAT variant for the combined step-leap and duration ratio profile that allows additionally a 3 rd interval to be a member of either step or leap (the repeated pattern is correctly identified).

Figure 6 Figure 7

 67 Figure 6Opening melody of Beethoven's Piano Sonata Op.10, No.2. Segmentation profile according to LBDM and the Pattern Boundary Detection Model (PAT) variant for the combined step-leap and duration ratio profile that allows additionally a 3 rd interval to be a member of either step or leap.


Christopher Dobrian
email: dobrian@uci.edu

STRATEGIES FOR CONTINUOUS PITCH AND AMPLITUDE TRACKING IN REALTIME INTERACTIVE IMPROVISATION SOFTWARE

In a realtime interactive work for live performer and computer, the immanently human musical expression of the live performer is not easily equalled by algorithmically generated artificial expression in the computer sound. In cases when we expect the computer to display interactivity in the context of improvisation, pre-programmed emulations of expressivity in the computer are often no match for the charisma of an experienced improviser. This article proposes to achieve expressivity in computer sound by "stealing" expressivity from the live performer. By capturing, analyzing, and storing expressive characteristics found in the audio signal received from the acoustic instrument, the computer can use those same characteristic expressive sound gestures, either verbatim or with modifications. This can lead to a more balanced sense of interactivity in works for live performer and computer.

INTRODUCTION

In the genre of pieces for live instrumental performance in combination with computer, many composers are employing custom-written software that functions in real time during performance in a so-called "interactive" relationship with the live performer. The rubric of "interactivity" is in fact often applied to any work that involves realtime software, regardless of whether the software actually exemplifies true interaction between computer and human performer. A significant distinction may be drawn between software that is "reactive" and software that is truly interactive.

A shortcoming of many works for live performer of an acoustic instrument in combination with computer is that these two elements-human and computer-are inherently disparate, both in terms of sound quality and expression. Because the means of sound generation by computer is significantly different from that of traditional acoustic instruments, digitally synthesized and processed sound is often significantly different from live instrumental sound, and in many cases lacks the complexity of sound production and performance gesture found in acoustic instruments. This disparity of sound between instrument and computer can be used intentionally to create an obvious contrast, but one may also strive to introduce more complexity and interest in the computer sound. Although digital sounds can be made arbitrarily complex mathematically, this is not necessarily equivalent to the type of complexity we find engaging in human performance. This paper discusses an approach to using some of the complexity of human performance for direct control of computer audio, based on the premise of "stealing" expressivity from a live performer.

CHARACTERISTICS OF INTERACTIVITY

If a computer responds instantly to the sound or gestures of a live performer based on a programmed algorithm, this is not necessarily an example of "interactive" computer music. The program is reacting to its input in a pre-determined way. The computer can only be purported to be acting autonomously if it is programmed to make some decisions of its own that are not fully predicted by the algorithm. This implies inclusion of some elements of unpredictability: the use of pseudorandomness at some structural level. Likewise, the relationship between computer and live performer cannot be described as interactive if the performer is playing from a fully fixed score, because the unpredictable behavior of the computer will have no influence on the live performer. The prefix inter-in the word "interactivity" implies mutual influence between agents that are also in some way autonomous decision makers. Neither agent may be fully predetermined in its behavior; each must be able to modify its behavior-to improvise-based on unpredictable behavior by the other. Therefore, improvisation by both human and computer is an essential component of any truly interactive work. In order for a computer to respond effectively to improvisation by a live performer, it must have some capability for cognition as well as independent action. Although computer cognition, intelligence, and expression are all artificial, they can still give the impression of interactivity.

STEALING EXPRESSIVITY

Just as the -ivity suffix in the word "interactivity" connotes "a quality of" interaction that can only be artificial in a machine, "expressivity" for a computer can only be a demonstration of an artificial or simulated quality of being expressive in the sense that we apply it to human music making: the conveyance of meaning or feeling. Much research has been focused on formulaic or algorithmic modeling of expressive phrasing (e.g., in jazz or classical music), and on developing new control interfaces that will permit more intimate and intuitive physical control of digital sound parameters. In this article I propose a direct method of achieving expressivity in computer music, by "stealing" it from a live performer. Rather than trying to abstract a concept of musical expression and devise a formulaic generative method to simulate it, it can be more effective in some cases simply to capture and use expressive characteristics of an actual performance. This is particularly appropriate in an improvised interactive context, when the type of computer expression that might be a suitable response to the live performer may not be known in advance.

It is very difficult to describe formulaically the characteristics of computer sound that will make it seem expressive in a way that is comparable to human musical expression, but we can use human expressive gestures to shape the computer sound. The composer and programmer must determine what characteristics of the live performance are important to expression in a given work, and what characteristics of the performance can be captured and analyzed. When the live performer is using only an acoustic instrument, without MIDI, sensors, or other digital input, the primary source of information from human to computer is the sound of the instrument itself. The computer program can analyze the audio signal, derive characteristics that the composer has deemed important, and use that information directly to control the musical expressivity of its own sound.

PITCH AND AMPLITUDE TRACKING

In interactive pieces for acoustic instrument and computer, direct analysis of the audio signal received from the instrument is the main source of information for any cognitive function in the computer program.

From the audio signal we can, with varying degrees of success, analyze the pitch, amplitude, and timbre (spectral content) of the signal, and from that information we can derive some information about specific events, notes, dynamic changes, and rhythm. Because of the difficulty of performing such analysis accurately and meaningfully, one must carefully consider what information is desired-which can vary based on the musical context of the moment-and must develop strategies for acquiring that information reliably.

In my recent pieces for flute and computer, I have focused on pitch and amplitude tracking in an effort to give the computer some sense of the musical expression of the live performer. In the following paragraphs I describe some of the strategies I have used. Notably, I will focus on the tracking strategies I developed that are specially suited to the Korean flute daegeum, an instrument that idiomatically introduces some stylistic and expressive traits that are often not the focus of Western classical music.

CONTINUOUS PITCH TRACKING

For computer pitch analysis of melodic instruments, the fiddle~ software [START_REF] Brown | A High-Resolution Fundamental Frequency Determination Based on Phase Changes of the Fourier Transform[END_REF][START_REF] Puckette | Real-time audio analysis tools for Pd and MSP[END_REF] has had widespread usage among programmers in Pd [START_REF] Puckette | Pure Data[END_REF] and MSP [START_REF] Dobrian | MSP: The Documentation[END_REF][START_REF] Zicarelli | An Extensible Real-Time Signal Processing Environment for Max[END_REF]. (Other software for pitch detection in MSP exists, such as pitch~ [START_REF] Jehan | An Audio-Driven, Spectral Analysis-Based, Perceptual Synthesis Engine[END_REF], yin~ [START_REF] Cheveigné | YIN, a fundamental frequency estimator for speech and music[END_REF], and others. A comparison of all of those methods is beyond the scope of this article.) The fiddleĩ mplementation in MSP is largely successful for detecting pitch in most Western classical music contexts where the music is conceptually organized as discrete notes each having a single stable fundamental pitch.

In the idiomatic style of the daegeum, however, the identity of a note with a single stable pitch is much more difficult to specify, and indeed is musically inappropriate in many cases. Often in daegeum music, the conceptual equivalent of a note-that is, a distinct period of relative pitch stability within a scale-entails a constant fluctuation of pitch ranging as wide as a semitone above or below the conceptual pitch center. Much of the musical interest and expressivity in this idiom lies in the curve of this pitch variation, in combination with simultaneous variations of amplitude and timbre, as much as or more than the sequential organization of discrete scale steps as would be the case in most Western music. For a computer to capture the expressive nature of pitch in daegeum music, ascribing a single pitch to a note is inadequate; it is the ongoing curve of pitch fluctuation that is more important.

The fiddle~ object does provide the MSP programmer with an ongoing report of estimated pitch without trying to determine a single precise pitch per note, and it is this ongoing report that is more useful for idiomatic daegeum music. However, because of the wide range of spectral variation possible within a single sustained daegeum note, fiddle~ is prone to make some "wrong" pitch assessments that are briefly displaced by an octave from the perceived overall pitch. Although octave melodic leaps are not uncommon in daegeum music, they most commonly appear between phrases, and only much more rarely occur as a smooth legato transition; therefore it is reasonable and beneficial to ignore instantaneous leaps equal to or greater than an octave, on the assumption that they are but spurious artifacts of fiddle~'s analysis. It is also possible to ignore any of fiddle~'s pitch estimates that lie beyond the range of the instrument-estimates that may be the result of turbulent embouchure noise, an inadvertent grunt or loud inhalation by the performer, etc. Pitch estimates that occur when the note has insufficient amplitude can also be filtered out. Once the "bad" guesses are removed, and the "good" guesses have been smoothed with low pass filtering, the result is a pitch curve that perceptually very closely resembles that of the performance (Figure 1).

The continuous pitch curve, now in the form of a signal, can be used to control the pitch of synthesized sounds, modulating oscillators, pitch shifting, etc. in real time, can be transposed or modified with any standard DSP technique such as compression, and/or can be recorded in a buffer~ for later use.

AMPLITUDE TRACKING

In MSP it's a simple matter to make an envelope follower that tracks and mimics the over-all amplitude envelope of an audio signal. At a periodic control rate much lower than the audio sampling rate-usually well below the fundamental frequency of the note being analyzed-one can accumulate samples and find the maximum magnitude within the control period, using the peakamp~ object. These maxima describe the general amplitude envelope of the sound, and can be converted back to an MSP signal with interpolation, for use as a control signal for synthesized sounds (Figure 2). As with the continuous pitch curve, the amplitude envelope can be modified with DSP, repurposed to control other sonic parameters, and/or recorded into a buffer~ for later use. Once stored, these control signals derived from the live performance can be treated as musical motives that can recur verbatim or with modifications. As was done with the pitch follower described above, we may wish to ignore signals of low amplitude that we deem to be beneath the level of the desired signal, i.e. part of the ambient noise floor. When dealing with signal amplitude, eliminating low level signals can be accomplished by gating-"ducking" all the way to 0 any signal below a given threshold-or by downward dynamic expansion-increasingly reducing a signal the more it falls below a threshold. A ducking feature can easily be added to the envelope follower just by comparing the incoming peak amplitude to a threshold and converting the value to 0 if it is below the threshold (Figure 3). In actual practice, some more refinements are usually necessary. Precaution should be taken so that peak amplitude levels that hover around the threshold, fluctuating rapidly just above and just below it, do not cause the gate to be opened and shut repeatedly, which would result in a distorted envelope. This can be accomplished by setting a longer attack and/or release time for the opening and closing of the gate. It has the added advantage of creating more graceful attack and release at the beginning and end of the amplitude envelope signal, adjustable to the needs of the situation.

The following figure shows one solution, in which the amplitude envelope signal (which might be coming from the simple follower shown in Figure 2 above) is gated by a thresh~ object, with the effect of the threshb eing smoothed by rampsmooth~. In this example, thresholds and ramp times can be specified independently for the attack and release of the threshg ate (Figure 4).

NOTE BOUNDARY DETECTION

The periodic peak amplitude values gathered by peakamp~ can be used to recognize sound events and silences, which can be interpreted as the beginning and ending boundaries of individual notes or phrases. Once again, the problem is not quite so simple as just detecting when the peak amplitude goes above or below a particular threshold. An instrument such as the daegeum has a very wide dynamic range and idiomatically wide amplitude vibrato (a.k.a. tremolo) that might easily dip below the ambient noise floor many times within the course of a note. In order to avoid wrongly interpreting such an amplitude vibrato as repeated notes, one can specify a "wait time" before determining that a note has ended; if the peak amplitude goes back above the threshold before the wait time has passed, the note is presumed to be continuing. In the same spirit, one might specify a minimum note duration, less than which a note cannot be presumed to have ended. The daegeum, like most flutes, often has a very gradual attack and release, and this must be taken into account when evaluating the attack amplitude of a note. If we only look at the amplitude at the moment it passes the detection threshold, we may get an inaccurate assessment of the note's attack velocity, because the true peak of the attack-the "downbeat", or "sync point" if you will-may actually occur a fraction of a second later than when it first passes the threshold. In order to allow for this possibility, we can track the increasing amplitude from the time it passes the threshold on the attack, and only report the true peak of the attack once we see that the amplitude is steady or is starting to diminish.

The following figure demonstrates these ideas. The input amplitude is expected as a floating-point value expressed in decibels. This would come from an input signal, the peak amplitude of which is periodically evaluated by peakamp~ and then converted to decibels with atodb. Some default values for attack threshold, release threshold, minimum note duration, and "wait time" are shown here, but they can be adjusted by new values received in the inlets (Figure 5). When an amplitude value comes in, we compare it to the threshold. If it exceeds the threshold and no note is currently on, then we track future amplitudes until they are no longer increasing. At that time, the note is presumed to have reached its peak attack amplitude, so we send a 1 out the right outlet to say that an event has occurred, and we send the peak attack amplitude out the left outlet. Also, we update the note's on/off status (in the & object) and we start the note duration and wait time clocks (the delay objects). From that time on, incoming amplitudes are continually evaluated to see if they remain above the release threshold. If not, and once both the minimum duration and the wait time have passed, the note is reported as having ended.

This type of note boundary detection is very useful for triggering events or processes based on the attack detected in an incoming audio signal, and ending them when a note release is detected. For example a synthesized or recorded sound can be started and stopped in response to these note boundaries, and peak attack amplitude can be used to determine how loudly the computer will play its sound. A program might also make higher level evaluation of a series of events, such as estimating tempo, measuring and storing played rhythms, etc.

USE OF TRACKED PITCH AND AMPLITUDE DATA

The control signals derived from the amplitude and pitch of an input audio signal can be applied instantaneously to control parameters of the computer audio. Additionally, they can be modified in MSP before being used, and/or can be applied to parameters other than amplitude and pitch, such as panning, filter cutoff frequency, etc. Figure 6 shows a straightforward example of how the patches shown in the previous figures can be used to provide expression to a synthesized sound. The patches called pitchfollower~, envelopefollower~, threshgate~, and detectevent correspond to Figures 1, 2, 4, and 5 above. The patcher soundsynthesis could be any synthesis algorithm, with the four inlets being used to provide amplitude curve, frequency curve, attack peak amplitude, and note on/off indicator. Note how easily the frequency curve can be transposed, and the amplitude curve can be repurposed to control panning from left to right as the amplitude increases. This example (Figure 6) shows realtime use of expressive information signals from a live performer. Alternatively, once those control signals have been recorded into a buffer~, they become motives that can be recalled later in the performance, and can be modified by any DSP technique.

CONCLUSION

For expressivity in a realtime improvised interactive work, it is often effective to "steal" expressive information from a live performer and apply it to the computer music. In works for acoustic instrument and computer, the audio signal is the primary source of such information. Continuous curves derived from the pitch and amplitude of the sound source can be used to control parameters of the computer audio, lending a sense of human expressivity to the computer music. These expressive curves, when expressed as a signal in MSP, can be modified with DSP, can be reassigned to other sonic parameters, and can become motives for improvisational use by the computer later in the piece. The computer sounds more expressive because it is in fact basing its own sonic gestures on information derived directly from the live performance.

Figure 1 .

 1 Figure 1. Continuous pitch follower, filtering out spurious values and smoothing the curve

Figure 2 .

 2 Figure 2. Simple amplitude envelope follower

Figure 3 .

 3 Figure 3. Simple amplitude envelope follower with low amplitudes converted to 0

Figure 4 .

 4 Figure 4. Attack and release thresholds and ramp times for gated envelope follower

Figure 5 .

 5 Figure 5. Detect a sound event and report its beginning, ending, and attack amplitude

Figure 6 .

 6 Figure 6. Amplitude and pitch curves used to control synthesis and panning


Özgür Izmirli

Noel Zahler

Pattern Anchoring, Identity and Signatures in Sound, Time and Space

The process of score following requires that the automated follower be capable of making robust decisions during a performance, especially in light of the number of errors that need to be accounted for between the live performer and the follower. . Based on the idea of variable-length signatures for monophonic input we define a causal method for tracking location in score following. The signatures and their lengths are calculated prior to performance based on their novelty in a predetermined locality within the score. Results are shown using a graphical display that depicts the associations, determined by a score follower, between performed notes and the score. This display aids in visual evaluation of the performance of the score following process and specifically its capability of recovery following any of the performance aberrations.

INTRODUCTION

For some time now, our work has been focused on score following [START_REF] Izmirli | Compositional Imperatives for Implementing an Audio Alignment Program in MAX/MAP[END_REF] [START_REF] Izmirli | Melodic Pattern Anchoring for Score Following Using Score Analysis[END_REF]. Most recently, we have come to believe that methods derived from "traditional" approaches to music analysis used for parsing scores may not be the most efficient or cognitively correct models for mapping a given composition's data input to a machine oriented performance program [START_REF] Izmirli | Melodic Pattern Anchoring for Score Following Using Score Analysis[END_REF]. The need to have an unambiguous trajectory that can be easily traversed by a score follower is of great general interest. Further, we hope to shed some light on the needs of any automatic, real-time, computer assisted performance program and how this division of territory may be of use when contemplating issues related to performance, signal interpretation and fragmented data reception. Special cases, including accompaniment and spatialization, will also be considered, but we also make a special effort to show relevance to other areas where the division of a work into domains and regions may be of interest. Dance, theater, and installation art all work with texts that must be analyzed and traced. In an effort to offer a solution to such tracking, we have reappraised our own methods and those of others. We offer a possible solution as it relates to our work in score following. The method is based on finding signatures of different sizes for all notes of a score and incorporating them into a score follower capable of using such information.

PERFORMANCE

In score following, performance considerations have taken the form of tempo and beat tracking, heuristic definition of common performance mistakes, and incomplete data assessments for intelligent accompaniment (improvisation).

What has been excluded from this discussion, until recently, has been consideration of the kind of formal and analytical process with which performers overlay a score before they perform the work. Machine pre-performance score consultation has been used by one of the authors in previous work [START_REF] Baird | Implementing an Interactive Computer Performer[END_REF] but the intelligent division of a score into structurally significant areas that can be used by a score following program in much the same manner as a performer "chunks" a musical composition in order to measure his/her progress through the piece has, to our knowledge, not been used. This ability to "know" the territory through which a performer will pass has only been attempted by programs seeking to have the ability to recall and learn from each performance and the type of information extracted by these programs is quite different from what we are trying to do [START_REF] Vercoe | Synthetic rehearsal: Training the synthetic performer[END_REF]. An intelligent score following program needs to have the ability to recognize signposts, in much the same way as their human counterpart. These flagged areas, or as we have termed them, signatures, divide the score according to unique patterns whose infrequency of occurrence distinguish them from the more common "musical analysis" we have witnessed. They act as "markers" and they fly in the face of traditional methods that divide a composition into phrase, section and movement; the traditional divisions calculating similarity and repetition as markers of coherence. Why then have we found this traditional approach to marking a score poor for the purposes of score following? Why is it that we have concluded that a new morphology is needed for machine driven performance?

ANALYSIS

Just about all approaches to "musical analysis" rely on symmetry and repetition as syntactical elements in building morphological models of the compositions they examine. Symmetry has proven itself a useful tool in the definition of pattern mapping for score following but repetition, in most cases, confuses the issue by making it impossible to identify where a particular motivic signature appears in a work without a specific "time stamp." Dannenberg [START_REF] Dannenberg | New Techniques for Enhanced Quality of Computer Accompaniment[END_REF], in his early work on score following, while preparing the machine copy of the score, chose to eliminate all consecutive repetitions of the same pitch because it was impossible for the machine to differentiate between repeated instances of the same note. When dealing with larger patterns (motives), some types of compositions, say Bach fugues, the motivic material may be so similar that it is more fruitful to consider what is not "motivic" rather than what is motivic. In our own work [START_REF] Izmirli | Melodic Pattern Anchoring for Score Following Using Score Analysis[END_REF], we have shown how we calculate signatures as "anchor" points. The salient issues regarding signatures pertain to the composition of the identifying mark. In other words, what are the elements that comprise the signature and how may they be generalized? In this instance, there are a number of similarities that might be compared to data mining. In our own work, it has become clear that signatures must be of variable length to be effective markers of a body of composition. This might be of further help in generalizing the use of signatures in both gesture (theater) and space (dance). Therefore, our investigation takes on an interest in calculating what is the optimal technique of traversing a score through the unique division of its topology by markers that point to a unique location. We envision the application of these methods to continuous domains such as theater and dance through some symbolic means of representation. That is to say, for example, a score in the context of dance consists of a sequence of characteristic key frames (whether in the manner of film, video or Laban notation) defining movement in space from which the performance has ensued.

PATTERN MATCHING AND SIGNATURES

The concept of using previously calculated unique patterns as anchors in score following was introduced as a means of replacing the process of 'chunking' the score prior to performance [START_REF] Izmirli | Melodic Pattern Anchoring for Score Following Using Score Analysis[END_REF]. The signature matching mechanism was proposed as a process that had global information (within a piece), and operated above the score follower that concentrated on local information. The detection of an anchor during score following either would affirm the position of the score follower or would put it back on track if it were lost. The signatures utilized in our previous work were fixed in length and global within a piece. That is to say, the anchors were calculated for the entire piece and as the performance unfolded the current input pattern was compared to all of the remaining (uncommitted) anchors. Global anchors have shown to be useful in this context but due to the real time processing constraints that limit the size and number of anchors and the information content of the score that imposes a particular distribution of anchors over time, their use has been limited to relatively long pieces that have few fragments of repetition. This led us to explore a more flexible form of signature matching in which the anchors were of varying size and more in number. The method presented here treats each musical onset as a local anchor with an associated degree of uniqueness. Depending on the size of the pattern, appropriate values are calculated that distinguish one anchor from another. These uniqueness values are then consolidated to determine the shortest length of a pattern that best describes this point in the score.

Given a sequence of musical events, it is straightforward to calculate the similarity matrix and determine either repetitions or find unique patterns within a piece using a predetermined window size. In this case, the window size needs to be determined prior to processing and the optimal size of the window will vary depending on the music content. The choice of window size is a tradeoff between a short window, that favors real time implementation due to the reduced computational load, and a longer window for more reliable pattern matching. The aim, in the context of score following, is to find novel patterns in a work that are either locally distinct or, preferably, globally unique. These patterns, called signatures, are significant markers that act as placeholders and enable a follower to move to these points in the score without ambiguity. In the following, we describe a method for determining the minimum size signature while locally maintaining pattern novelty. As this signature mechanism will only have meaning in reference to a score follower, we also briefly discuss their integration and present the proposed algorithm for score following.

The initial problem is one of finding the shortest pattern that is unique for each note. One fundamental problem in determining signatures by analyzing the score is that of representation and pattern similarity. Similarity is pertinent to score following for the reason that any number of changes to the score can be encountered during performance due to errors made by the performer or the signal processing front-end. There has been considerable work on melodic similarity [e.g. 6, 7, 8, 9] emphasizing different approaches, and comparison of musical sequences independent of key, mode or tempo [START_REF] Mongeau | Comparison of Musical Sequences[END_REF]. In our work, we are also interested in melodic similarity but in a more isolated and information theoretic way. Hence, our model does not deal with finding melodic descriptors such as phrase structure, cadence, implied harmony etc.

We define score following to be real-time. This assumes that even though the entire score is known to the follower at all times, the information about performance is only available up to the current time during the score following process. This is in contrast to non-real-time score-performance matching in which the matcher has all the information at its disposal (e.g. [START_REF] Large | Dynamic Programming for the Analysis of Serial Behaviors[END_REF]). Heijink et al. [START_REF] Heijink | Make Me a Match: An Evaluation of Different Approaches to Score-Performance Matching[END_REF] summarize approaches to this problem and discuss methods of exploration of multiple alternative matches in order to find the optimal solution in matching a score to a performance. Our approach is different in that we calculate signatures and their lengths prior to performance, perform local searches during performance and make real-time decisions based on the available information at whatever point in time we happen to be at in the rendering of the performance.

FINDING SIGNATURES AND LENGTHS

Each note in the score is processed in relation to its neighboring notes to find its minimum size signature. Signatures are found within a locality, L, given in number of notes, around the single note under consideration. The choice of this locality is not very critical and its size can vary from a small number of notes to the length of the entire piece. Notes are represented with 2-tuples, (a,b), the first element holding the onset time value and the second holding the midi pitch value. The 'score' data structure is a list of these 2-tuples.

The time values in the score serve to express the relative durations of the notes and have no direct correspondence to the tempo of the performance in follow mode. The midi note values are absolute. The dissimilarity of two patterns in the score is calculated using the Levenshtein distance, or so called edit distance. This is calculated for each note in the score within its locality L. Overlapping of the search patterns is not allowed.

The edit distance is calculated with a dynamic programming algorithm using the following recurrence equations:

⎪ ⎩ ⎪ ⎨ ⎧ + + + = - - - - ins 1 j , i rep 1 j , 1 i del j , 1 i j , i C d C d C d d (1)
where C del , C rep and C ins are the costs associated with deletion, replacement and insertion respectively. The initial conditions are d 0,0 = 0, for all i and for all j.

del 0 , 1 i 0 , i C d d + = - ins 1 j , 0 j , 0 C d d + = -
As mentioned earlier, score following requires that midi pitches be absolute and time information be relative. For example, a transposition of a phrase with the same timing is not considered similar to the original, whereas, a time-dilated segment with the same sequence of pitches is deemed similar. The equality operator for this algorithm uses midi pitch equality and the ratio of the duration of the current note to the duration of the previous note. That is to say, two notes are equal if their pitches are equal and their duration ratios are within a percentage range determined by δ: ( ) (  )

) 1 ( a a a a 1 1 1 n n 1 m m δ + ≤ ≤ δ + - - (2)
The edit distance between a pattern at position m and a pattern at position n is calculated for various lengths, r:

( ) { r ), n ( score ), m ( score r , n , m S Ε = } (3)
where Ε is the r-element edit distance operator using the source sequence ending with note m, target sequence ending with note n in the score. That is to say, for a three element window the notes would be score(m-2), score(m-1) and score(m) with the latter having the largest time value. The minimum size pattern is then given by R(m)=r that satisfies the following:

( ) K .. 0 k , 2 1 r ) r m ( n or ) r m ( n ; r r , n , m S max ) m ( M k r , n = + = - ≤ + ≥ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = (4)
M(m) is the minimum dissimilarity and K+1 is the number of different window sizes. R(m) is the shortest pattern that is least similar to all other patterns in the locality L for note m. Here, r is chosen to take exponentially increasing values, but, the choice can be changed to a linear relationship which will in fact give more accurate minimal pattern lengths at the expense of increased computation times.

THE SCORE FOLLOWER

The score follower has been designed keeping the realtime aspect at the central focus. Although the model has access to future score information, naturally, it does not have insight into the future values of the performance. The score follower algorithm given below combines the properties of our previous score follower algorithm [START_REF] Izmirli | Compositional Imperatives for Implementing an Audio Alignment Program in MAX/MAP[END_REF] and a mechanism that incorporates signature length information on a note by note basis. The score and the performance are sequences of musical events represented by 2-tuples. They can have entirely different time scales as long as their starting tempos are comparable.

The algorithm for the score follower is given below. Some abbreviations used in the algorithm are as follows: Score Tempo (STE): holds the value of score tempo in score time units; Score Time (STI): interpolated position of the score in score time units; Score Pointer (SP): index to note in score; Performance Pointer (PP): index to performed note in the performance list; R(m) : length of signature at note m; α : similarity threshold,

( ) { } ) m ( R

RESULTS

The operation of the model is demonstrated by means of a causal simulation. Results are shown by use of an association plot in which notes of the score and the performance are displayed. This plot enables visualization of the associations of notes in the two streams. The top subplot, in each figure, shows the midi pitch value versus onset time of the notes in the score. The lower subplot shows the notes for the performance. Associations that have been established as a result of the score following are shown as lines connecting the notes of the score to the ones that have been performed. An association between a note in the score and a performance note means that the score follower is locked onto the input note stream and is following with confidence. A note in the score that is not associated however, is still played when its time is crossed by the score time variable but is an indication of ambiguity. Figure 2 shows the same piece with initially a decrease in tempo followed by an increase. Again all notes have been associated. It can be seen from the plot that the score is leading in terms of its own time scale. Nevertheless, the follower has stayed locked to the performance. Figure 3 shows a 3% slower performance compared to the score. In addition to this, for each note, a note error is introduced with a probability of 0.1. The note error can be one of note insertion, note deletion or pitch replacement with equal probabilities. If no note error is introduced then the time onset is altered with a uniform distribution of up to half the distance between the current note and its neighbors. It can be seen from the figure that some associations are missing, mainly due to deletions in the performance. This however, has not interrupted the course of the score following and as can be seen from the lower plot, the path is straight with a slope less than 45 degrees to reflect the slower performance. Figure 4 shows a similar performance using Telemann's Fantasia No.1 with 4% slower tempo, note errors and onset alterations as in the previous figure.

DISCUSSION

The choice of locality L is of particular interest. Larger locality will enable larger spans of follower awareness, enabling it to speed up and move to distant positions ahead of its current position. The disadvantage of choosing a large L is that signature patterns tend to be longer in size due to the increased probability of complete or partial repetitions of shorter patterns in the larger span. This, of course, is with the assumption that there are no exact repetitions in the piece. On the lower end, L needs to be significantly larger than the maximum signature length in order for the method to evaluate the similarities in its neighborhood.

The score following algorithm described above assumes errors are rare and are not encountered in bursts that are much longer than the maximum signature length. If such a case is encountered, the performance pointer might fall outside of the scope of the score pointer and the follower might get lost. For this particular case, a solution might be to increase the size of the maximum signature length (determined by K). This comes at the expense of increased computational cost and hence latency, both in real time and off-line (pre-processing,) and longer delays in recovering from minor errors. This also applies to repeated notes which have been problematic for score followers in general. In the presence of repeated notes and especially with the lack of rhythmic variation our follower might lose track. In this case, it will have to regain focus when new musical patterns are encountered following the sequence of repeated notes.

CONCLUSIONS

We have begun an investigation wherein the events of a performance can be unambiguously matched to a score. Accurate tracking can be facilitated with an acceptable rate of error for a score follower regardless of change in tempo because the score follower now has the ability to reference events in the score in a more precise and better suited manner. This is facilitated by a method that allows for a variable size pattern that characterizes each signature. The mechanism that utilizes this information is integrated into a score follower that has been shown to have robust qualities. This is a method that can be generalized to scores other than those used for music and will greatly facilitate the automation of text or symbol based performances.

  The parameters chosen for the following examples are as follows: L=80, C del =0.75, C rep =0.65, C ins =1 and K=3. Figure1shows an initial fragment from Bach's Partita BWV1013 Allemande. The performance is the copy of the score with identical midi pitch values and onset times. The plot at the top shows the associations and the plot below it shows the corresponding onset times of the associated notes. In this case, both streams have the exact same tempo leading to a straight line with an angle of 45 degrees. All notes have been associated in this figure.

Figure 1 .

 1 Figure 1. Fragment of Bach Partita BWV1013 with identical performance and score streams.

Figure 2 .

 2 Figure 2. Fragment of Partita with a decrease followed by an increase in tempo of performance.

Figure 3 .

 3 Figure 3. Fragment of Partita with 3% slower performance, note errors and onset alterations.

Figure 4 .

 4 Figure 4. Fragment of Telemann Fantasia with 4% slower performance, and errors as in Figure 3.


Nick Collins
email: nc272@cam.ac.uk

ON ONSETS ON-THE-FLY: REAL-TIME EVENT SEGMENTATION AND CATEGORISATION AS A COMPOSITIONAL EFFECT

Keywords: Onset Detection, Audio Capture, Real-time Segmentation, Categorisation

Compositional applications for real-time event segmentation are discussed. A causal real-time onset detector which makes onset data available as fast as possible is introduced, based on work by Klapuri, Hainsworth and Jensen and Andersen. This analysis frontend informs algorithmic cutting procedures which respect the events of the incoming audio stream. A further refinement stores events to particular buffers based on a coarse categorisation between snare, kick or hihat classes. Algorithmic composers running playback of these buffers thereby respond to changing timbral events of a live feed from an instrumentalist or other audio source. The use of an onset detection threshold to create abstracted rhythms based on some existing source is further examined.

INTRODUCTION

The automatic segmentation and labeling of audio events has many applications from content retrieval to source sensitive sound processing. Practical attempts often employ signal features including the spectral centroid, zero crossing rate or MFCC coefficients and statistics tracking these values over the time course of the sound. Rossignol et al. [START_REF] Rossignol | Automatic characterisation of musical signals: Feature extraction and temporal segmentation[END_REF] give a system that characterises signals on three scales, source differentiating speech and music, feature measuring such descriptors as harmonicity or presence of vibrato and note/phone segmenting signals into short subsecond events based on nine features. Current investigations into the classification of sounds can involve very large sets of features such that exhaustive search for the optimal subgroup is computationally intractable [START_REF] Herrera | Automatic labelling of unpitched percussion sounds[END_REF]. Spotting events requires reaction to to the perceptually critical segment boundary of the onset [START_REF] Vos | The perceptual onset of musical tones[END_REF]. Many onset detection schemes have now been proposed [START_REF] Bello | A tutorial on onset detection in music signals[END_REF][START_REF] Duxbury | Complex domain onset detection for musical signals[END_REF][START_REF] Hainsworth | Onset detection in musical audio signals[END_REF][START_REF] Klapuri | Sound onset detection by applying psychoacoustic knowledge[END_REF][START_REF] Smith | Sound segmentation using onsets and offsets[END_REF]. The offset at the end of an acoustic event is usually less reliably marked [START_REF] Smith | Sound segmentation using onsets and offsets[END_REF], though the character of the onset can also vary from wideband transient to a smooth envelope, depending on the source. The effectiveness of event detection algorithms thus vary with the signal to be tracked and the assumptions taken about the source. It is quite possible in human hearing that selection is taken from a number of detection models based on peripheral evidence of the spectral content and resolved immediate stylistic characteristics, in accord with maximising information. It is assumed herein that such higher level management of low level algorithms is sidestepped.

Onset detection work is most effective against monophonic sources, the case of polyphonic audio providing a well known problem in auditory scene analysis. Whilst some progress may be possible through independent component analysis and the like, Scherier [START_REF] Scheirer | Towards music understanding without separation: Segmenting music with correlogram comodulation[END_REF] criticises the dream of perfect segregation of streams in polyphony, rather seeking a more human goal of 'understanding without separation'. When multiple instruments are involved, overlap of parts makes the act of segmentation without component extraction guaranteed to cut a mixture of transients and steady states. There is a compositional awareness of this, common for example in the fugal forms of Bach, where the entry of parts is staggered, and the counter melodies constructed to to aid differentiation of onsets by avoiding unison events. Onsets are thus accessible, and a rhythmic aggregate may be the cognitive resultant, but the overlap of sounding objects forbids perfect separation. Pragmatically, audio can be segmented and extracted as best possible, even if some blends of decay and new onsets result. It will be argued that transient information (the likely basis for the cuts) will take precedence in perception, and interesting compositional effects are obtained.

The focus of this paper is in live performance, where a (typically monophonic) acoustic instrument or a (polyphonic) live band or ensemble is being captured and manipulated, and segmentations are performed on-the-fly. The ideal is to react as quickly as possible, though some delay for analysis of the captured events my be necessary. Conversely, no faster than real-time look ahead is possible, as in streaming an existing soundfile from disk. The time duration of the extracted events is usually under one second, fitting into the note/phone scheme of [START_REF] Rossignol | Automatic characterisation of musical signals: Feature extraction and temporal segmentation[END_REF], but large enough to allow perceptual integration (over 100mS). This level is suitable for rhythmic rate manipulation in processing, and is the sound object time scale of Roads' taxonomy [START_REF] Roads | [END_REF]. Segmenting an incoming audio stream allows the extracted sound events to be individually processed, and their reuse outside the original context.

The implementations described in this paper were undertaken by writing native code and C++ plugins for the SuperCollider3 (SC3) audio programming language [START_REF] Mccartney | Rethinking the computer music language: SuperCollider[END_REF] ( http://sourceforge.net/projects/supercollider). The orientation of this language towards realtime performance combining signal processing and algorithmic composition makes it an attractive platform for the research; it is also open source and cross platform (Linux, Mac OS X).

Section 2 provides a mathematical description of the onset detection schemes leveraged. Section 3 describes a technology for live algorithmic audio cutting, integrating onset detection. This is the basis for an on-the-fly segmenter with a ready made selection of compositional algorithms. An experimental program for realtime categorisation is introduced in section 4 and further compositional extensions explored in section 5.

ONSET DETECTION METHODS

A number of onset detection functions are being investigated to support segmentation effects. Anssi Klapuri [START_REF] Klapuri | Sound onset detection by applying psychoacoustic knowledge[END_REF] pioneered the use of the relative difference for peak detection given an amplitude envelope signal A(t). His psychoacoustic motivation was the relation to the Weber fraction ∆I/I for discrimination of intensity changes, for his function W (t) takes the form:

W (t) = d dt (A(t)) A(t) = d(log(A(t))) dt (1)
.

If A(t) is below a certain amplitude, W (t) is taken as zero.

Whilst Klapuri first applied this on the outputs of a 21 band envelope extractor and combined results across bands with a loudness model 1 , Hainsworth [START_REF] Hainsworth | Onset detection in musical audio signals[END_REF] [6, page 128] introduces an equivalent construction 2 in the context of distance measures between FFT frames for chord change detection:

d(k) = log 2 ( |X n (k)| |X n-1 (k)| ) (2)
β k=α max(d(k), 0) (3)
where α and β define lower and upper limits for a particular subset of bands and |X n (k)| is the magnitude of the k th bin for the n th frame of spectral data. Hainsworth selects 30Hz to 5KHz as his range on the basis of quality of harmonic information for his applications, though this is also of course the area of greatest sensitivity of the ear. A generalisation of this would weight the different 1 Klapuri tracks loudness in each band according to a psychoacoustic model, using this to form an overall loudness measure of the event from which to assess a detection by thresholding. 2 For a difference equation approximation to the derivative,

d(log(A(t))) dt ≈ log(A(t)) -log(A(t -1)) = log( A(t) A(t-1) )
bands, perhaps using Fletcher Munson contours based on the intensity of the input for a psychoacoustically relevant model, and perhaps in a way learnt for specific tracking tasks. The weighting may be selected so as to focus attention on particularly salient bands for an identified timbral profile. Further, such a weighting might bias detections to a desired frequency range, as in tracking only low frequency energy impulses in a bass drum or bass guitar rhythm, though this may also be achieved by pre filtering of the input.

d(k) = w(k)(log 2 ( |X n (k)| |X n-1 (k)| )) (4)
In comparison to the multiplicative difference, the additive difference is also an option:

d(k) = w(k)(|X n (k)| -|X n-1 (k)|) (5)
Where w(k) is usually a constant 1. The onset detection feature of High Frequency Content (HFC) can be expressed where w(k) = k 2 as defined by Jensen and Andersen [START_REF] Jensen | Realtime beat estimation using feature extraction[END_REF], w(k) = k as per Masri and Bateman [START_REF] Masri | Improved modelling of attack transients in music analysisresynthesis[END_REF] or a generalised w(k) = k γ where γ is to be optimised.

Figure 1 gives a comparison of different onset detection methods on rhythmic polyphonic audio (some 'intelligent dance music', compressed and with many hard transients). 1024 point FFTs were taken with an overlap of two, on a spectral range of 30-20000Hz. The first row gives the source, the second the detection function for the relative difference measure, the fourth for the Jensen and Andersen version of HFC. Rows three and five show a squared difference function of the respective detection functions which highlights their peaks. Note that the noise floor is a little higher for the relative difference function, and that there are differences of opinion of location and strength of spectral changes between the two functions. As a contrast, Figure 2 shows the same detection functions acting on a solo violin piece with many dynamic contrasts. The Hainsworth/Klapuri spectral amplitude ratio method shows some superior detections here, particularly for the slower and softer attacks. This is in no way a proof of the general properties of these detection schemes, which vary in their effectiveness based on the subject audio to analyse. It is envisaged that different onset detection algorithms may be required for different circumstances of employment, optimising for a particular performance environment and musical collaborator.

The Hainsworth FFT version of Klapuri's idea and the Jensen and Andersen HFC feature were implemented as phase vocoder UGens for SuperCollider 3. For efficiency, the SC3 implementation uses an overlap of 2 for a 1024 point FFT, the 86 or so frames a second providing a resolution of under 12 mS. Hainsworth runs his 2048 point FFT calculations at an overlap of 8, giving around 170 frames per second, whilst Klapuri downsamples his signals to about 200 samples per second. Since the detection functions will pick up on a spectral change early on in an event (near the physical onset rather than the perceptual), the onset can be stored quickly and the offset calculated as the stream continues to arrive. As long as the playback head is kept away from the record head, this allows immediate reuse or processing of events within an FFT frame of their detection. The last zero crossing or energy minima can be stored to keep track of a sample starting position for new events, though this is less effective for polyphonic or slurred monophonic audio.

BBCUT AND ONSETS

BBCut [START_REF] Collins | The BBCut Library[END_REF] is an extension library for SuperCollider specialising in realtime algorithmic audio cutting, available free under the GNU GPL from http://sicklincoln.org/code. Real-time computer generated splicing of audio material is provided in procedures inspired by a variety of styles, including dance music production drum programming and breakbeat cutting (drum and bass, intelligent dance music), thrash drumming, recursive cutting, change ringing permutation patterns and other compositional algorithms. BBCut provides a separation of the algorithmic composers that decide upon cuts from the rendering of the cuts themselves, such that the same composition code can be plugged into a cutter of incoming audio streams, or a cutter of fixed buffers; as software engineering, this encourages code reuse.

Whilst the naivest mode of cutting is to assume even slicing of the source material, there are options to adopt knowledge of the permissible onsets into a source. Onset positions are critical to audio cutting, where the paradigm is to jump around the source to make permutational use of the material rather than subsist on rigid linear playback. This generative reuse of the source material will work effectively if the source has been properly segmented into events such that there are no transient discrepancies acting as rhythmic confounds. This is conceptually the same as positioning a read pointer into a soundfile or buffered memory of a live stream, such that the start position at the beginning of a new cut lines up sensibly with events within that target 3 . Enveloping may be applied to avoid clicks and to smooth out transitions, but if natural cutting points can work without such ramping, so much the better.

How does BBCut use segmentation information for the source to be spliced, when asked to source audio data for an arbitrary length output slice? The simplest option is to restrict any choice of onset to the start positions of the segmented events of the source, and to only allow one event to be referenced at a time, such that playback is of that event alone, whatever the desired output length.

A more indirect option associates each known onset in the source to a quantised position. This location is determined with respect to an imposed rhythmic template of the algorithmic cutting 4 . A likely assumption would be that the source is a certain length in beats and of fixed tempo and time signature. The order of the onset events is preserved in such a quantisation. The advantage is that extractions of material which are of medium length (say a few beats), and may take in more than one segmented event from the source, can guarantee playback that does not clash the rhythm of the source with the rhythm of the generative cutter. Playback of successive source events occurs at separations taken from the quantise positions, whilst the audio is still read from the original known onset positions. The rhythmic template, with whatever notion of groove or swing, can be adjusted, and the quantise position of the source events updated to reflect this. In computational terms, this requires a further data array for the quantised locations; search code finds the set of quantised event starts within this array falling within a cut of some duration from a given starting point. Knowing the indices within the quantise position array tells us immediately the indices for the events in the true onset position array for the source. These events can be rendered at the appropriate time for the quantise array so they fit in with the imposed template, reading the data from the source.

To assist in discovering onsets in offline preparation of source material, a GUI for onset detection (Figure 3) was introduced in BBCut1.3, with a number of options for the detection algorithm, all of which run in realtime. Adaptations of the Hainsworth and Jensen and Andersen methods described above are provided along with a simple RMS (root mean square) amplitude derivative detector. Since the two former FFT based routines have been built into the SuperCollider distribution independent of BBCut, they are also available as general purpose realtime detectors; the GUI is just a helpful frontend. Discovered segments can be played back individually in the GUI via keyboard shortcuts and misdetects deleted or moved.

In live performance, a buffer can be allocated to receive captured audio, and event detection fully automated. As the audio is recorded, the onset detection simultaneously runs, noting times of triggers of the detection function as event onsets, and disallowing multiple detects within 50mS of each other. The event offsets are taken as a maximal fixed duration from the onset or coinciding with a new onset. This is sufficient for a single fixed capture to make the new events available via the technology already described.

As a further refinement, a continuous stream of input audio can be continually analysed for events whilst recording to a limited memory circular buffer. If the onset data is held in a list and the capture continuous, since the write pointer position is known, the list can be continuously updated with onset information, and all read pointer access will stay up to date with the changing buffer contents. Where this is required, updating the quantise array as well will keep the cut renderer in step with the incoming stream.

source depends on further assumptions or knowledge on the captured audio, obtained possibly through beat/metre induction principles.

CATEGORISATION ON-THE-FLY

The best set of signal descriptors for classification of sound can depend on the categories of sound to be judged. For general sound classification, Peeters and Rodet [START_REF] Peeters | Automatically selecting signal descriptors for sound classification[END_REF] describe the CUIDADO system which is open-ended in features and user customisable in the type of sounds to classify, discriminating a relevant subset of features for a particular classification task. Categorisation of percussive sounds is tackled by Paulus and Klapuri [START_REF] Paulus | Model-based event labelling in the transcription of percussive audio signals[END_REF] using a probabilistic model based on ten signal features, and Herrera et al. [START_REF] Herrera | Automatic labelling of unpitched percussion sounds[END_REF] exploring over two hundred.

Without tackling the best selection of features, an onthe-fly categoriser was built as an experiment in compositional application for event segmentation based on the onset detector already introduced, . The goal of this prototype is categorisation of incoming sound events as soon as possible, into one of three classes, notionally being kick, snare and hihat percussive sounds. The single feature initially used for classification in prototyping is the average spectral centroid bin:

L n=0 N/2 k=0 k|X n (k)| L (6)
Where there are L frames of an N point FFT in a given event.

Hiding certain technicalities based on blocksize calculation, pseudocode for an on-the-fly categorisation algorithm is presented in figure 4.

A SuperCollider UGen, CaptureCategorise, was written in C to implement this. The UGen has inputs for the threshold of detection, and to choose the boundaries for the feature determining classification. Defaults were average centroid bin below 90 for a kick, below 120 for a snare and a hihat above that. This was sufficient to demonstrate some live (vocal) beatbox control, with captured buffers being played back in a basic generative drum beat, and the appropriate contents continually overwritten when a new event was detected.

A more robust system would entail learning from a database of examples, even an online learning process during performance, to discover a relevant feature space for discrimination. Still, the exploration of further basic features provides some immediate compositional dividends.

FURTHER COMPOSITIONAL APPLICATIONS

In the course of an exploration of causal real-time onset detection functions, the author had recourse to listen back to sources, whilst simultaneously triggering beeps at the detections. It was noted that by changing the non-adaptive threshold of the detection function, a series of abstracted rhythms could be generated from the source. Shifting threshold gives a complexity parameter for the generated rhythms. The source may then be hidden, and the detections used to trigger arbitrary sound events. A form of onset detection cross synthesis can take place when one As one example of this technique, the capture and categorise process ran on one input stream, classifiying input events to three buffers. These buffers were played back using rhythms generated by thresholded onset detection from three separate source loops.

In an aesthetic sense, misdetections increase the abstraction and the less accurate onset detection functions and less salient signal features may still be appropriated for compositional purposes. In the on-the-fly categorisor, miscategorisations can provide some stimulating results!

CONCLUSIONS AND FUTURE WORK

Whilst an imposed rhythmic framework has provided the skeleton for reuse of sound objects in this work, the incorporation of pulsation levels and other musical knowledge extracted from a cutting target should provide a more powerful system yet. Event detection is a first stage in beat induction, providing readily available inter onset data for histogramming or autocorrelation, though the leap to the symbolic stage is not a necessity, as Scheirer's model proves [START_REF] Scheirer | Tempo and beat analysis of acoustic musical signals[END_REF]. A model which provides a higher level rhythmic framework empowers some interesting processing options, as Gouyon et al. prove [START_REF] Gouyon | Rhythmic expressiveness transformations of audio recordings: swing modifications[END_REF].

A more systematic testing of the onset detection algorithms is a necessary next stage, optimising some of the parameters indicated in section 2. It is anticipated that specific compositions, working with particular instrumentalists, may demand the use of a particular detection algorithm. The categorisation process can certainly be made more robust, and a key issue is the best personalisation to the sound world of a collaborating musician. Databasing of a timbral space during an interaction would be a worthy pursuit, which is well within reach if the composer specifies the feature space in advance. Captured events can be further analysed for the perceptual centre [START_REF] Marcus | Acoustic determinants of perceptual center (p-center) location[END_REF] so as to make sure that the physical start is appropriately scheduled. Another potential problem to be dealt with is the accidental capture of double strikes and other potential conflicting rhythmic confounds in single events which disturb the rhythmic flow of the output. This paper is a stepping stone towards a sensitive system for audio capture and processing. A number of compositional applications of real-time onset detection have been highlighted.

Figure 1 .

 1 Figure 1. Comparison of relative difference (upper) and additive difference with k 2 weighting (lower) onset detection functions for a Squarepusher dance music track

Figure 2 .

 2 Figure 2. Comparison of relative difference (upper) and additive difference with k 2 weighting (lower) onset detection functions for a John Cage solo violin piece

Figure 3 .Figure 4 .

 34 Figure 3. BBCut Onset Detector GUI for each FFT frame { store last time domain zero crossing if(recording event) { calculate running spectral centroid, power of frame if(eventlength>MAXLENGTH or power<MINPOWER) { finish recording to temporary buffer up to last zero crossing copy event data to one of three buffers based on the time averaged spectral centroid } else store frame data to temporary buffer and increment eventlength } else if(onset detected) start recording event from last zero crossing, initialise eventlength }

There may of course be conflicts between the imposed rhythm of the composition and the recorded rhythm of the sample source.

ACKNOWLEDGEMENTS

This research is supported by AHRB grant 2003/104481. Many thanks to Juan Bello, Kristoffer Jensen and Steven Hainsworth.