Mathieu Lagrange

Gustavo Luis

Jennifer Martins

George Murdoch

Tzanetakis

Normalized cuts for predominant melodic source separation

teaching and research institutions in France or abroad, or from public or private research centers.

Normalized Cuts for Predominant Melodic Source Separation

Mathieu Lagrange, Member, IEEE, Luis Gustavo Martins, Jennifer Murdoch, Student Member, IEEE, and George Tzanetakis, Member, IEEE Abstract-The predominant melodic source, frequently the singing voice, is an important component of musical signals.

In this paper we describe a method for extracting the predominant source and corresponding melody from "real-world" polyphonic music. The proposed method is inspired by ideas from Computational Auditory Scene Analysis. We formulate predominant melodic source tracking and formation as a graph partitioning problem and solve it using the normalized cut which is a global criterion for segmenting graphs that has been used in Computer Vision. Sinusoidal modeling is used as the underlying representation. A novel harmonicity cue which we term Harmonically Wrapped Peak Similarity is introduced. Experimental results supporting the use of this cue are presented. In addition we show results for automatic melody extraction using the proposed approach.

Index Terms-AUD CONT,AUD SSEN (EDICS), music information retrieval, computational auditory scene analysis, sinusoidal modeling, normalized cut

I. INTRODUCTION

T HE voice and melodic characteristics of singers are some of the primary features of music to which listeners relate to. Most listeners, independently of their music education, are capable of identifying specific singers even in recordings they have not heard before. In addition, especially in pop and rock music the singing voice carries the main melodic line that can be used to identify a particular song of interest.

Music Information Retrieval (MIR) is a field that has been rapidly evolving over the past few years. It encompasses a wide variety of ideas, algorithms, tools, and systems that have been proposed to handle the increasingly large and varied amounts of musical data available digitally. Typical MIR systems for music signals in audio format represent statistically the entire polyphonic sound mixture [START_REF] Pachet | A classification of musical genre[END_REF], [START_REF] Tzanetakis | Musical genre classification of audio signals[END_REF]. There is some evidence that this approach has reached a "glass ceiling" [START_REF] Aucouturier | Improving timbre similarity: How high is the sky?[END_REF] in terms of retrieval performance.

One obvious direction for further progress is to attempt to individually characterize the different sound sources comprising the polyphonic mixture. The singing voice is arguably one of the most important of these sources and its separation and characterization of the singing voice has a large number of applications in MIR. Most existing query-by-humming This work was supported by the National Science and Research Council of Canada (NSERC), the Canada Foundation for Innovation (CFI), the Portuguese Foundation for Science and Technology (FCT), and the Fundac ¸ão Calouste Gulbenkian (Portugal).

M. Lagrange, J. Murdoch and G. Tzanetakis are with the University of Victoria, Canada (email: {lagrange,jmurdoch, gtzan}@uvic.ca). L. G. Martins is with INESC Porto / FEUP, Portugal (email: lmartins@inescporto.pt).

systems [START_REF] Ghias | Query by Humming: Musical Information Retrieval in an Audio Database[END_REF], [START_REF] Dannenberg | The MUSART testbed for query-by-humming evaluation[END_REF] can only retrieve songs from a database containing music in symbolic format. By performing pitch extraction on the extracted voice signals, it is possible to perform query-by-humming in databases of audio signals.

Another potential application is singer identification that is independent of the instrumentation or the "album" effect [START_REF] Kim | Towards quantifying the album effect in artist identification[END_REF]. Other possible applications include automatic accompaniment, music transcription, and lyrics alignment.

There has been limited work on singing voice separation from monaural recordings. Many existing systems require predominant pitch detection in order to perform separation [START_REF] Li | Singing voice separation from monaural recordings[END_REF] or rely on prior source models [START_REF] Ozerov | One microphone singing voice separation using source-adapted models[END_REF]. Other approaches are based on statistical methods such as Independent Component Analysis (ICA) and Non-Negative Matrix Factorization (NMF) [START_REF] Vembu | Separation of vocals from polyphonic audio recordings[END_REF]. The non-stationarity of the singing voice and music signals as well as their heavy computational requirements are some of the challenges of applying statistical methods to this problem. Another related research area is predominant pitch estimation and melody transcription in polyphonic audio [START_REF] Poliner | Melody transcription from music audio: Approaches and evaluation[END_REF] in which only the pitch of the predominant melody or singing voice is estimated.

In contrast, our approach attempts to directly separate the prominent melodic source without first estimating the predominant pitch based on basic perceptually-inspired grouping cues inspired by ideas from Auditory Scene Analysis [START_REF] Bregman | Auditory Scene Analysis: The Perceptual Organization of Sound[END_REF]. A separation of the leading voice is achieved by this approach since the singing voice (if any) is usually the most prominent source of the mixture. A description of an earlier version of the algorithm and some of the experiments described in section III-B appear in [START_REF] Lagrange | Sound source tracking and formation using normalized cuts[END_REF].

A fundamental characteristic of the human hearing system is the ability to selectively attend to different sound sources in complex mixtures of sounds such as music. The goal of computational auditory scene analysis (CASA) [START_REF]Computational Auditory Scene Analysis[END_REF] is to create computer systems that can take as input a mixture of sounds and form packages of acoustic evidence such that each package most likely has arisen from a single sound source. Humans use a variety of cues for perceptual grouping in hearing such as similarity, proximity, harmonicity and common fate. For example, sound components that change frequency by the same amount are more likely to be grouped together as belonging to the same sound source (common fate) than if they are changing independently. As another example, two notes played by the same type of instrument are more likely to be grouped together than two notes played on different instruments (similarity). An excellent overview of the current state of the art in CASA is provided in [START_REF] Wang | Computational Auditory Scene Analysis: Principles, Algorithms and Applications[END_REF].

Many of the computational issues of perceptual grouping for hearing are still unsolved. In particular, considering the several perceptual cues altogether is still an open issue [START_REF] Vincent | Musical source separation using time-frequency priors[END_REF], [START_REF] Roweis | One microphone source separation[END_REF]. We propose in this paper to cast this problem into a graph cut formulation using the normalized cut criterion. This global criterion for graph partitioning has been proposed for solving similar grouping problems in computer vision [START_REF] Shi | Normalized cuts and image segmentation[END_REF].

The normalized cut is a representative example of spectral clustering techniques which use an affinity matrix to encode topological knowledge about a problem. Spectral clustering approaches have been used in a variety of applications including high performance computing, web mining, biological data, image segmentation and motion tracking.

To the best of our knowledge there are few applications of spectral clustering to audio processing. It has been used for the unsupervised clustering of similar sounding segments of audio [START_REF] Ellis | Minimal-impact audio-based personal archives[END_REF], [START_REF] Cai | Unsupervised content discovery in composite audio[END_REF]. In these approaches, each audio frame is characterized by a feature vector and a self-similarity matrix across frames is constructed and used for clustering. This approach has also been linked to the singular value decomposition of feature matrices to form audio basis vectors [START_REF] Dubnov | Audio segmentation by singular value clustering[END_REF]. These approaches characterize the overall audio mixture without using spectral clustering to form and track individual sound sources.

Spectral clustering has also been used for blind onemicrophone speech separation [START_REF] Bach | Blind one-microphone speech separation: A spectral learning approach[END_REF], [START_REF] Bach | Learning spectral clustering, with application to speech separation[END_REF]. Rather than building specific speech models, the authors show how the system can separate mixtures of two speech signals by learning the parameters of affinity matrices based on various harmonic and non-harmonic cues. The entire STFT magnitude spectrum is used as the underlying representation.

Closer to our approach, harmonicity relationships and common fate cues underlie a short-term spectra-based similarity measure presented by Srinivasan [START_REF] Srinivasan | Harmonicity and dynamics based audio separation[END_REF]. To integrate time constraints, it is alternatively proposed in [START_REF] Srinivasan | Auditory blobs[END_REF] to cluster previously tracked partials to form auditory "blobs" according to onset cues. Normalized cut clustering is then carried out on these blobs. In contrast, a short-term sinusoidal modeling framework is used in our approach. It results in more accurate and robust similarity relations as well as significantly smaller affinity matrices that are computationally more tractable.

Sinusoidal modeling is a technique for analysis and synthesis whereby sound is modeled as the summation of sine waves parameterized by time-varying amplitudes, frequencies and phases. In the classic McAulay and Quatieri method [START_REF] Mcaulay | Speech analysis/synthesis based on sinusoidal representation[END_REF], these time varying quantities are estimated by performing a short-time Fourier transform (STFT) and locating the peaks of the magnitude spectrum. Partial tracking algorithms track the sinusoidal parameters from frame to frame, and determine when new partials begin and existing ones terminate [START_REF] Lagrange | Enhancing the tracking of partials for the sinusoidal modeling of polyphonic sounds[END_REF]. If the goal is to identify potential sound sources then a separate stage of partial grouping is needed. Typically grouping cues such as common onsets and spectral proximity are used.

In this paper we use the term sound source tracking and formation to refer to these two processes of connecting peaks over time to form partials (tracking) and grouping them to form potential sound sources (formation). They roughly correspond to the sequential and simultaneous aspects of organization described by Bregman [START_REF] Bregman | Auditory Scene Analysis: The Perceptual Organization of Sound[END_REF]. Although frequently implemented as separate stages as in [START_REF] Srinivasan | Harmonicity and dynamics based audio separation[END_REF], [START_REF] Srinivasan | Auditory blobs[END_REF], these two organizational principles directly influence one another. For example, if we have knowledge that a set of peaks belong to the same source, then their correspondence with the next frame is easier to find. Similarly, the formation of sound sources is easier if peaks can be tracked perfectly over time. Methods that apply these two stages in a fixed order tend to be brittle as they are sensitive to errors and ambiguity.

To cope with this chicken-and-egg problem, we show how both sound source tracking and formation can be jointly optimized within a unified framework using the normalized cut criterion. We model the problem as a weighted undirected graph, where the nodes of the graph are the peaks of the magnitude spectrum and an edge is formed between each pair of nodes. The edge weight is a function of the similarity between nodes and utilizes various grouping cues such as frequency, amplitude proximity and harmonicity. We also propose a novel harmonicity criterion that we term Harmonically Wrapped Peak Similarity (HWPS), that is described in section II-D. Clustering is performed in the same way for all peaks within a longer "texture window" independently of whether they belong to the same frame or not. The resulting algorithm can be used to separate the singing voice or predominant melody from complex polyphonic mixtures of "real-world" music signals.

The algorithm is computationally efficient, causal, and realtime. Another important aspect of our method is that it is data-driven, without requiring a priori models of specific sound sources as many existing approaches to separation do [START_REF] Vincent | Musical source separation using time-frequency priors[END_REF].

The remainder of the paper is organized as follows. In the next section, singing voice tracking and formation is formulated as a spectral clustering problem using sinusoidal peaks as the underlying representation. Using this formulation several perceptual grouping criteria such as amplitude proximity, frequency proximity and harmonicity are integrated into a unified framework. Section III describes experimental results demonstrating the potential of the proposed algorithm as a front end for MIR tasks, and conclusions are given in Section IV.

II. SINGING VOICE FORMATION AND TRACKING USING THE NORMALIZED CUT

A. System Overview

In this section we provide an overview of our proposed method and define the terminology used in the remainder of this article. Figure 1 shows a block diagram of the process; each step of the process is described in more detail in the following subsections. The following terms are important for understanding these descriptions.

• Frames or analysis windows are used to estimate sinusoidal peaks from the complex spectrum computed using a Short Time Fourier Transform. For the experiments described in this paper a frame size corresponding to 46 ms and a hop size of 11 ms are used. the local maxima of the spectrum are estimated. Each peak is characterized by amplitude, frequency and phase.

• Texture windows correspond to an integer number of frames. Clustering of peaks across both frequency and time is performed for each texture window rather than per frame. For the experiments described in this paper a texture window corresponding to 10 frames (≈ 150 ms) is used. • Similarity cues are used to calculate the similarity between sinusoidal peaks belonging to the same texture window. These cues are inspired by perceptual grouping cues [START_REF] Bregman | Auditory Scene Analysis: The Perceptual Organization of Sound[END_REF] such as amplitude and frequency proximity, and harmonicity. • The similarity or affinity matrix is calculated by considering the similarity of every peak to every peak within a texture window. Hence, the similarity matrix represents the similarity between peaks within the same frame (simultaneous integration) and across time (sequential integration) within the "texture window". • Clusters are groups of peaks that are likely to originate from the same sound source. By approximately optimizing the normalized cut criterion, the overall peak similarity within a cluster is maximized and the similarity between clusters is minimized. The audio corresponding to any set of peaks (one or more clusters) can be conveniently resynthesized using a bank of sinusoidal oscillators. • Source Formation is the process of approximately reconstructing a particular sound source from a decomposition of the polyphonic mixture.

B. Sinusoidal Modeling

Sinusoidal modeling aims to represent a sound signal as a sum of sinusoids characterized by amplitudes, frequencies, and phases. A common approach is to segment the signal into successive frames of small duration so that the parameters can be considered as constant within the frame. The discrete signal x k (n) at frame index k is then modeled as follows:

x k (n) = L k l=1 a k l cos 2π F s f k l • n + φ k l (1)
where F s is the sampling frequency, φ k l is the phase at the beginning of the frame of the l-th component of L k sinusoids, and f k l and a k l are respectively the frequency and the amplitude. Both are considered as constant within the frame.

For each frame k, a set of sinusoidal parameters

S k = {p k 1 , • • • , p k L k } is estimated.
The system parameters of this Short-Term Sinusoidal (STS) model S k are the L k triplets p k l = {f k l , a k l , φ k l }, often called peaks. These parameters can be efficiently estimated by picking some local maxima from a Short-Term Fourier Transform (STFT).

We further improve the precision of these estimates by using phase-based frequency estimators which utilize the relationship between phases of successive frames [START_REF] Puckette | Accuracy of frequency estimates using the phase vocoder[END_REF], [START_REF] Marchand | On the equivalence of phase-based methods for the estimation of instantaneous frequency[END_REF], [START_REF] Lagrange | Estimating the instantaneous frequency of sinusoidal components using phase-based methods[END_REF]. Assuming that the frequencies of the pseudo-periodic components of the analysed signal are constant during the time-interval between two successive short-term spectra, with a hop size of H samples, the frequency can be estimated from the phase difference:

ω = 1 2πH ∆φ (2)
The smaller the hop size the more accurate is this assumption. We consider two successive short-term spectra separated by one sample. The frequency is estimated directly from the phase difference ∆φ ensuring that the phase is unwrapped so that the difference is never negative. The resulting estimator, known as the difference estimator, is:

f k l = F s 2π (∠S[m l , n k + 1] -∠S[m l , n k ]) unwrap (3)
where ∠S denotes the phase of the complex spectrum S, m l is the frequency bin index of the peak p k l within the spectrum, and n k is the index of the first sample of analysis frame k. The frame index k is omitted in the remainder of this subsection.

During the analysis of natural sounds, presence of several frequency components in the same spectral bin or noise may lead to incoherent estimates. If the frequency f l of a local maximum located at bin m l is closer to the frequency of another bin, the local maximum should have been located at this bin. Therefore, a local maximum with an estimated frequency that does not satisfy the following condition is discarded:

|N/F s • f l -m l | ≤ 0.5.
Since that the power spectrum of an ideal sinusoid signal has the shape of the power spectrum of the analysis window, centered around the sinusoid frequency, the increase of frequency precision can be used to estimate more precisely the amplitude:

a l = 2 |S[m l ]| |W H (f l -m l F s /N )| (4)
where |S[m l ]| is the magnitude of the complex spectrum, W H (f ) is the spectrum of the Hann window used for the STFT computation, f being the frequency in Hz. These more precise estimates of frequency and amplitude parameters are important for calculating more accurate similarity relations between peaks. Other frequency estimation methods can also be used, such as parabolic interpolation [START_REF] Abe | Design Criteria for Simple Sinusoidal Parameter Estimation based on Quadratic Interpolation of FFT Magnitude Peaks[END_REF] or subspace methods [START_REF] Badeau | High resolution spectral analysis of mixtures of complex exponentials modulated by polynomials[END_REF].

The importance of more precise frequency estimation for our method compared to the basic approach of directly converting the FFT frequency bin number to frequency is explored in some of the experiments in Section III. Sinusoidal modeling is particularly suited for sustained sounds with a definite pitch and harmonic structure such as the vowels of a singing voice. Consonants can still be represented but require a large number of sinusoidal components to be represented accurately [START_REF] Mcaulay | Speech analysis/synthesis based on sinusoidal representation[END_REF]. Vowels in singing voices tend to last much longer than in speech therefore in practice a sinusoidal model can capture most of the singing voice information that is useful for MIR applications such as the melodic line and the timbral characteristics.

C. Grouping Criteria

In order to simultaneously optimize partial tracking and source formation we construct a graph over each "texture" window. Unlike approaches based on local information [START_REF] Mcaulay | Speech analysis/synthesis based on sinusoidal representation[END_REF], we utilize the global normalized cut criterion to partition the graph over the entire "texture" window. Edges are formed both for peaks within a frame and peaks across frames. Each partition is a set of peaks that are grouped together such that the similarity within the partition is maximized and the similarity between different partitions is minimized. If L k is the number of peaks in frame k, then the number of peaks in a "texture" window is T resulting in a similarity matrix of size T * T :

T = k L k (5)
The maximum L k used in our experiments is set to 20. By picking the highest amplitude peaks of the spectrum, we usually achieve fair resynthesis quality using a small number of sinusoids per frame with a significant savings in computation time. For example if the entire STFT spectrum is used as in Bach [START_REF] Bach | Blind one-microphone speech separation: A spectral learning approach[END_REF] the similarity matrix for 10 analysis frames of 512 samples would have a size of 5120 * 5120 whereas in our case would be have a maximum possible size of 200 * 200. In a first approach, the edge weight connecting two peaks p k l and p k+n m depends on both frequency W f and amplitude W a proximity (k is the frame index and l,m are peak indices, n ∈ {0 . . . N -1} is the frame offset between the peaks, and N is the "texture" window size; n = 0 is used for peaks of the same frame):

W f a (p k l , p k+n m ) = W f (p k l , p k+n m ) * W a (p k l , p k+n m ) (6)
We use radial basis functions (RBFs) to model the frequency and amplitude similarities:

W f a (p k l , p k+n m ) = e - f k l -f k+n m σ f 2 * e - a k l -a k+n m σa 2 (7)
The standard deviations of frequencies and amplitudes are calculated separately for each texture window. For these two similarities the amplitudes are measured in Decibels (dB) and the frequencies are measured in Barks (approximately linear below 500 Hz and logarithmic above). Amplitude and frequency cues are not enough for multiple overlapping harmonic sound sources. In the following subsection we describe a harmonic similarity measure between peaks that works well for these cases.

D. Harmonically Wrapped Peak Similarity

A wide variety of sounds produced by humans are harmonic, from singing voice and speech vowels, to musical sounds. As a result the harmonicity cue has been widely studied. As explained by de Cheveigné in [START_REF] Wang | Computational Auditory Scene Analysis: Principles, Algorithms and Applications[END_REF] for the case of multiple fundamental frequency estimation, most approaches use an iterative method whereby the fundamental frequency of the dominant source is identified and then used to remove the corresponding source from the mixture. Few studies have focused on the identification of harmonic relations between peaks without any prior fundamental frequency estimation.

The goal is to define a similarity measure between two frequency components (peaks) that is high for harmonically related peaks and low for peaks that are not harmonically related. Most existing approaches [START_REF] Virtanen | Separation of harmonic sound sources using sinusoidal modeling[END_REF], [START_REF] Srinivasan | Harmonicity and dynamics based audio separation[END_REF], [START_REF] Rosier | Unsupervised classification techniques for multipitch estimation[END_REF], [START_REF] Martins | PCM to MIDI transposition[END_REF] use the mathematical properties of the harmonically related frequencies to build such a similarity measure for a single frame. For example, Virtanen [START_REF] Virtanen | Separation of harmonic sound sources using sinusoidal modeling[END_REF] considers whether the ratio of the frequencies of the components is a ratio of small positive integers, while Martins [START_REF] Martins | PCM to MIDI transposition[END_REF] selects peaks that are equally far apart in frequency to form harmonic clusters. I). Used for Figures 3,4,5.

There are several issues concerning these approaches, both from the technical and perceptual points of view. First, these type of measures can not be safely considered for peaks belonging to different frames, which is a strong handicap for our application. The reason of this restriction is that the fundamental frequency of the source can change across frames. Secondly, these mathematical conditions are not sufficient to determine whether two peaks are part of an harmonic source. From a perceptual point of view, two peaks are close on the "harmonic" axis if these peaks belong to a perceptible compound of harmonically-related peaks in the spectrum. This fact perhaps explains why most separation algorithms first attempt to identify the pitch of the sounds within the mixture by considering the spectral information globally, and then assign frequency components to each estimated pitch. In contrast, our proposed similarity measure works reasonably well without estimating the underlying pitch.

To address these problems, we introduce a new similarity measure that we term Harmonically Wrapped Peak Similarity (HWPS). The main goal of the HWPS measure is to take advantage of the flexibility of an harmonically-related similarity between peaks that not only considers each peak in isolation but also the entire spectral information associated with the remaining peaks. This measure can be used both for peaks within the same frame and among peaks of different frames.

The basic mechanism behind the HWPS measure is to assign each peak a spectral pattern. The pattern captures information about the spectrum in relation to the specific peak. The degree of matching between two spectral patterns is used as a similarity measure between the two peaks thus utilizing more spectral information than just the amplitude and frequency of the two peaks. As the spectral pattern of a peak might shift when changing frames and contains peaks belonging to multiple harmonic sources we use a harmonically wrapped frequency space to align the two spectral patterns corresponding to the peaks. The goal is that the similarity between peaks belonging to the "same" harmonic complex is higher than the similarity of peaks belonging to different harmonic complexes. The three steps of this process are described below in more detail: Shifted Spectral Pattern: Our approach relies on a description of the spectral content using estimates of the frequency and amplitude of local maxima of the power spectrum, i.e. the peaks. We therefore propose to assign to each peak, p k l (l is the peak index, and k is the frame index), a given spectral pattern, F k l , based on the set of frequencies (in Hz), F k l = {f k i }, shifted within the frame k as follows:

F k l = { f k i | f k i = f k i -f k l , ∀i ∈ [1, L k ]} (8)
where L k is the highest peak index of frame k.

The spectral pattern is essentially a shift of the set of peak frequencies such that the frequency of the peak corresponding to the pattern maps to 0 (when i is equal to l). One can easily see that two peaks of different frames modeling the same partial will have roughly similar spectral patterns under the assumption that the spectral parameters evolve slowly with time. This spectral pattern forms a peak-specific view of the spectral content which is used to calculate a pitch invariant representation using a wrapped frequency space as described in the following subsection. The top graphs of Figures 3 and4 show overlaid peak-specific spectral patterns for two pairs of peaks from the harmonic mixture of Figure 2.

Wrapped Frequency Space: To estimate whether two peaks p k l and p k+n m belong to the same harmonic source, we propose to measure the correlation between the two spectral patterns corresponding to the peaks. To achieve this, we would like to transform the peak-specific spectral patterns in such a way that when the peaks under consideration belong to the same harmonic complex the correlation is higher than when they belong to different harmonic sources. In order to achieve this the following operations are performed: the energy distribution of an harmonic source along the frequency axis can be seen as a cyclic unfolding with periodicity equal to the fundamental frequency of the source. To concentrate these energies as much as possible before correlating them, we propose to wrap the frequencies of each spectral pattern as follows:

f k i = mod f k i h , 1 (9)
where h is the wrapping frequency function and mod is the real modulo function. This wrapping operation would be perfect with the prior knowledge of the fundamental frequency. With this knowledge we can parametrize the wrapping operation with:

h = min(f 0 k l , f 0 k+n m ) (10)
where f 0 k l is the fundamental frequency of the source of the peak p k l . Without such prior, we consider a conservative approach which tends to over estimate the fundamental frequency with:

h = min(f k l , f k+n m ) (11)
Notice that the value of the wrapping frequency function h is the same for both patterns corresponding to the peaks under consideration. Therefore the resulting wrapped frequency spectra will be more similar if the peaks belong to the same harmonic source. The resulting wrapped frequency spectra are pitch invariant and can be seen in the middle plot of Figures 3 and4. Discrete Cosine Similarity: The last step is now to correlate the two harmonically wrapped spectral patterns ( F k l and F k+n m ) to obtain the HWPS measure between the two corresponding peaks. This correlation can be done using an algorithmic approach as proposed in [START_REF] Lagrange | Assessing the quality of the extraction and tracking of sinusoidal components: Towards an evaluation methodology[END_REF], but this was found not to be reliable or robust in practice. Alternatively, we propose to discretize each harmonically wrapped spectral pattern into an amplitude weighted histogram, H k l , corresponding to each spectral pattern F k l . The contribution of each peak to the histogram is equal to its amplitude and the range between 0 and 1 of the Harmonically-Wrapped Frequency is divided into 20 equal-size bins. In addition, the harmonically wrapped spectral patterns are also folded into an octave to form a pitchinvariant chroma profile. For example, in Figure 3, the energy of the spectral pattern in wrapped frequency 1 (all integer multiples of the wrapping frequency) is mapped to histogram bin 0.

The HWPS similarity between the peaks p k l and p k+n m is then defined based on the cosine distance between the two corresponding discretized histograms as follows:

W h (p k l , p k+n m ) = e c(H k l ,H k+n m ) √ c(H k l ,H k l )•c(H k+n m ,H k+n m ) 2 (12)
where

c(H b a , H d c ) = i H b a (i) * H d c (i). (13)
One may notice that due to the wrapping operation of Equation 9, the size of the histograms can be relatively small (around 20), thus saving computational time.

To illustrate this, let us consider the case of the mixture of two pitched sound sources, A and B, each composed of 4 harmonics with fundamental frequencies of 440 Hz and 550 Hz respectively, as presented in Table I and Figure 2. For the experiments, random frequency deviations of a maximum of 5 Hz are added to test the resilience of the algorithm to frequency estimation errors. If we consider two peaks of the same source A 0 and A 1 , the quantized version of the harmonically-wrapped sets of peaks are highly correlated, as can be seen in the bottom of Figure 3. On the other hand, if we consider two peaks of different sources, A 1 and B 0 , the correlation between the two discretized histograms is low (see Figure 4). The correlation between two histograms of harmonically related peaks still works (although to a lesser extent) if instead of using the true fundamental f 0 as the wrapping frequency we use any harmonic of it.

Figure 5 (left) shows a HWPS similarity matrix computed among the peaks of two overlapping harmonic sounds within a frame (also shown in Figure 2) with perfect knowledge of the fundamental frequency for each peak respectively. As can be seen clearly from the figure, the similarity is high for pairs of peaks belonging to the same source and low for pairs belonging to different sources. Figure 5 (right) shows the HWPS similarity matrix computed among the peaks of the same two overlapping harmonic sounds within a frame using the conservative approach to estimate the wrapping frequency (basically considering the lower peak as the "wrapping" frequency). As can be seen from the figure, although the similarity matrix on the right is not as clearly defined as the one on the left, it still clearly shows higher values for pairs of peaks belonging to the same sound source.

E. Spectral Clustering and the Normalized Cut Criterion

The normalized cuts algorithm, presented in [START_REF] Shi | Normalized cuts and image segmentation[END_REF], aims to partition an arbitrary set of data points into n clusters. The data set is modeled as a complete weighted undirected graph G = (V, E), the nodes V representing the data points and each edge E weight, w(i, j), representing the relative similarity between the two nodes i and j. The graph is represented internally by an affinity matrix, W , that specifies all edge weights. The partitioning is achieved by recursively dividing one of the connected components of the graph into two until n complete components exist. The formulation of the N cut measure addresses the bias towards partitioning out small sets of isolated nodes in a graph which is inherent in the simpler minimal cut disassociation measure (cut) between two graph partitions A, B:

cut(A, B) = u∈A,v∈B w(u, v) (14)
The criterion that is minimized in order to establish the optimal partitioning at any given level is the normalized cut disassociation measure (N cut):

N cut(A, B) = cut(A, B) asso(A, V ) + cut(A, B) asso(B, V ) (15)
where asso(X, V ) = u∈X,t∈V w(u, t) is the total of the weights from nodes in cluster X to all nodes in the graph. An analogous measure of the association within clusters is the following (Nasso):

Nasso(A, B) = asso(A, A) asso(A, V ) + asso(B, B) asso(B, V ) (16)
where asso(X, X) is the total weight of edges connecting nodes within cluster X. We note the following relationship between N cut and Nasso:

Ncut(A, B) = 2 -Nasso(A, B) (17)
Hence, the attempt to minimize the disassociation between clusters is equivalent to maximizing the association within the clusters. The hierarchical clustering of the data set via the minimization of the Ncut measure, or the equivalent maximization of the Nasso measure may be formulated as the solution to an eigensystem. In particular, [START_REF] Shi | Normalized cuts and image segmentation[END_REF] show that the problem is equivalent to searching for an indicator vector y such that y i {1, b} depending on which of the two subpartitions node i is assigned and b is a function of the sum of total connections of the nodes. By relaxing y to take on real values, we can find a partition that minimizes the Ncut criterion by solving the generalized eigenvalue system:

(D -W)y = λDy ( 18
)
where D is a N × N diagonal matrix with each element of the diagonal d(i) being the total connection from node i to all other nodes d(i) = j w(i, j), and W is a N × N symmetrical matrix containing the edge weights. As described in Shi and Malik [START_REF] Shi | Normalized cuts and image segmentation[END_REF] the second smallest eigenvector of the generalized eigensystem of equation ( 18) is the real valued solution to the Normalized Cut minimization. For discretizing the eigenvectors to produce indicator vectors we search among l evenly spaced splitting points within the eigenvector for the one that produces a partition with the best (i.e. smallest) Ncut(A, B) value. The graph is recursively sub-divided as described above until n clusters of peaks have been extracted.

One of the advantages of the normalized cut criterion for clustering over clustering algorithms such as K-means or mixtures of Gaussians estimated by the EM algorithm is that there is no assumption of convex shapes in the feature representation. Furthermore, the divisive nature of the clustering does not require a priori knowledge of the number of output clusters. Finally, compared to point based clustering algorithms such as K-means, the use of an affinity matrix as the underlying representation enables expression of similarities that can not be computed as a distance function of independently calculated feature vectors. The Harmonically Wrapped Peak Similarity measure proposed in this paper and described in section II-D, is an example of such as a similarity measure.

F. Cluster Selection

Among the several clusters, C i , identified using the normalized cut clustering for each texture window, we want to select the cluster that most likely contains the voice signal. The proposed approach is straightforward and does not rely on any prior knowledge of the voice characteristics. This criterion is therefore more general and may apply to the selection of any predominant harmonic source.

A cluster of peaks corresponding to a predominant harmonic source should be dense in the feature space in which we compute similarities. The reason is that peaks belonging to a prominent harmonic audio source have more precise parameter estimates and therefore comply better to the implicit model expressed by the various similarity functions. The peaks of a prominent source will therefore tend to be more similar (mostly in terms of harmonicity) to peaks belonging to the same source than to other sources. Thus, the intra-cluster similarities should be high for this particular cluster. Let us consider a cluster of peaks P c of cardinality #P c defined as the set of peaks whose Ncut label is c:

P c = {p k m |label(p k m ) = c} (19)
We then consider the density criterion: where k, j are the frame indices within the texture window and l, m are respectively the peak indices within the frames k and j. The function W f ah refers to the overall similarity weight that takes into account frequency, amplitude, and harmonicity. It is the product of the corresponding weights:

d(P c ) = 1 #P c 2 p k l ∈Pc p j m ∈Pc W f ah (p k l , p j m ) (20)
W f ah (p l , p m ) = W f (p l , p m ) * W a (p l , p m ) * W h (p l , p m ) (21)
For the experiments described in section III we computed 3 clusters for each texture window and selected the two clusters with the highest density as the ones corresponding to the voice signal. The peaks corresponding to the selected clusters are used to resynthesize the extracted voice signal using a bank of sinusoidal oscillators.

III. EXPERIMENTAL EVALUATION

The main goal of the experiments described in the following subsections is to demonstrate the potential of the proposed method. The algorithm is efficient and requires no training or prior knowledge. The source code of the algorithm is available as part of Marsyas, a cross-platform open source software framework for audio analysis and synthesis 1 . We hope that making the algorithm publicly available will encourage other researchers to use it and experiment with it. We have also made available on a website2 more information about the method (such as MATLAB code for the HWPS calculation), as well as the audio datasets described in this section.

A. Corpus description and experimental setup

Three datasets were used for the experiments. The first dataset was used for tuning the algorithm and the evaluation of the HWPS similarity cue described in subsection III-B. It consists of synthetically-created mixtures of isolated instrument sounds, voice, harmonic sweeps and noise. Each clip is approximately 1 second long.

The second dataset consists of 10 polyphonic music signals for which we have the original vocal and music accompaniment tracks before mixing as well as the final mix. Although relatively small, this dataset is diverse and covers different styles of singing and music background. It contains the following types of music: rock (6), celtic (3), hiphop [START_REF] Pachet | A classification of musical genre[END_REF]. In addition, we also evaluate melody extraction on the corpus used for the series of MIREX audio melody extraction evaluation exchanges; it consists of 23 clips of various styles including instrumental and MIDI tracks, for which case we estimate the dominant melodic voice.

B. Evaluation of the HWPS cue

The HWPS is a novel criterion for computing similarity between sinusoidal peaks that are potentially harmonically related. It is critical for separating harmonic sounds which are particularly important for musical signals. In this subsection we describe experiments showing the improvement in separation performance achieved by using the HWPS similarity cue compared to two existing cues proposed in Srinivasan [START_REF] Srinivasan | Harmonicity and dynamics based audio separation[END_REF] and Virtanen [START_REF] Virtanen | Separation of harmonic sound sources using sinusoidal modeling[END_REF].

Existing Cues: Srinivasan consider an harmonicity map that can be precomputed to estimate the harmonic similarity between two spectral bins. Considering two bin indexes i and j, the map is computed as follows:

hmap(i, j) = 1 if mod(i, j) = 0 or mod(j, i) = 0 ( 22
)
This map is next smoothed to allow increasing level of inharmonicity using a Gaussian function, normalized so that the sum of its elements is unity. The standard deviation of the Gaussian function is set to be 10% of its center frequency, see [START_REF] Srinivasan | Harmonicity and dynamics based audio separation[END_REF] for further details. The similarity between peaks p l and p m is then:

W s (p l , p m ) = shmap(M l , M m ) ( 23
)
where shmap is the smoothed and normalized version of hmap, and M l corresponding to the bin index of peak p l . The frames indexes are omitted for clarity sake. According to Virtanen [START_REF] Virtanen | Separation of harmonic sound sources using sinusoidal modeling[END_REF], if two peaks p l and p m are harmonically related, the ratio of their frequencies f l and f m is a ratio of two small positive integers a and b (which correspond to the harmonic rank of each peak, respectively). By assuming that the fundamental frequency cannot be below the minimum frequency found by the sinusoidal modeling front-end (i.e. f min = 50 Hz), it is possible to obtain an upper limit for a and b, respectively a < f l fmin and b < fm fmin . A harmonic distance measure can be defined:

W v (p l , p m ) = 1 -min a,b log f l /f m a/b (24)
by considering all the ratios for possible a and b and choosing the closest to the ratio of the frequencies.

Evaluation criteria: To compare our proposed cue with the existing ones, we use the signal-to-distortion ratio (SDR) as a simple measure of the distortion caused by the separation algorithm [START_REF]Signal Processing Methods for Music Transcription[END_REF]. It is defined in decibels as:

SDR[dB] = 10 log 10 t s(t) 2 t [ŝ(t) -s(t)] 2 (25)
where s(t) is the reference signal with the original separated source and ŝ(t) is the extracted source. The main use of the SDR measure in this section is to evaluate the relative improvement in separation performance achieved by the use of the HWPS cue. The SDR is only an approximate measure of the perceptual quality of the separated signals. We also encourage the readers to listen to the examples on the provided webpage.

No post-processing of the extracted signals was performed in order to provide better insight about the algorithm and its limitations. For example a dominant cluster is always selected independently of the presence of a singing voice.

For the first set of experiments we utilize an experimental setup inspired by the "old+new" heuristic described by Bregman [START_REF] Bregman | Auditory Scene Analysis: The Perceptual Organization of Sound[END_REF]. Similar experiments were described in [START_REF] Lagrange | Sound source tracking and formation using normalized cuts[END_REF]. Each sample is created by mixing two sound sources in the following way: for the first part of the sound only the "old" sound source is played followed by the addition of the "new" sound source (old+new) in the second part of the sample. Normalized cut clustering is performed over the entire duration of the clip. The clusters that contain peaks in the initial "old"only part are selected as the ones forming the separated source. The remaining peaks are considered to be part of the "new" sound source. The SDR measures the distortion/interference caused by this "new" sound source to the separation algorithm.

Table II compares different mixtures of isolated sounds separated using only frequency and amplitude similarities, and also separated with the additional use of the HWPS similarity. The following conventions are used in Table II: X is saxophone, N is noise, V is violin, S is harmonic sweep, and C is voice. A, F, H correspond to using amplitude, frequency and HWPS similarities, respectively. As can be seen from the table, in almost all cases the use of the HWPS improves the SDR measure of separation performance.

For the second set of experiments shown in Table III the "old+new" mixtures are separated directly using the approach described in subsection II-F to select the dominant sound source. Unlike the previous experiments, the spectral clustering is performed separately for each "texture" window and the highest density cluster is selected as the separated voice. This is a more realistic scenario as no knowledge of the individual sound sources is utilized. As expected the SDR values are lower but again the use of the HWPS improves separation performance in most cases.

The third set of experiments, shown in Table IV, illustrate the improvement in separation performance using the HWPS cue for the case of singing voice extraction from monaural polyphonic audio recordings. As a reference signal for computing the SDR we use a sinusoidal representation of the original voice-only track using 20 sinusoidal peaks per analysis frame. This way the SDR comparison is between similar representations and therefore more meaningful. This representation of the reference signal is perceptually very similar to the original voice-only signal and captures the most important information about the singing voice, such as the identity of the singer, pitch, vibrato, etc. The first column of Table IV shows the performance of our approach using only the amplitude and frequency similarities. The other columns show the performance of using the three different harmonicity similarities in addition to amplitude and frequency. All the configurations utilize the same parameters for the Normalized Cut algorithm and the only thing that changes is the definition of the similarity function. As can be seen, in most cases the HWPS similarity provides better results than the Virtanen similarity (HV) and the Srinivasan similarity (HS) and behave similarly otherwise. Finally the last two column show the importance of precise frequency estimation (HWPS) described in section II-B compared to rough frequency estimation directly from FFT bins (rHWPS). A similar drop in performance between rough and precise estimation was also observed for HV and HS but not included in the table.

C. Melodic Pitch Extraction

The melodic line is a critical piece of information for describing music and is very influential in the identity of a musical piece. A common approach to automatic melody extraction is to attempt multiple pitch extraction on the polyphonic mixture and select the predominant pitch candidate as the pitch of the signing voice [START_REF] Li | Singing voice separation from monaural recordings[END_REF], [START_REF] Klapuri | Multiple fundamental frequency estimation by summing harmonic amplitudes[END_REF]. The detected pitch can then be used to inform source separation algorithms. In our method the singing voice is first separated and the melodic pitch is subsequently extracted directly from the separated audio.

For each song in our dataset of 10 songs (for which the original voice-only tracks are available) the pitch contours were calculated for three configurations: the original clean vocal signal, the polyphonic recording with both music and vocals (V M ), and the vocal signal separated by our algorithm (V Sep). Two pitch extraction algorithms were utilized: a time domain autocorrelation monophonic pitch extraction algorithm implemented in Praat [START_REF] Boersma | Praat: doing phonetics by computer (version 4.5.06)[END_REF], and a recent multipitch estimation algorithm developed by Klapuri [START_REF] Klapuri | Multiple fundamental frequency estimation by summing harmonic amplitudes[END_REF]. Both approaches were configured to estimate fundamental frequencies in the range [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]2200] Hz, using a hop size of 11ms and an analysis window with a length of about 46ms.

The pitch contours estimated using Praat from the polyphonic recordings with both music and vocals will be referred in the text, figures, and tables as V M praat , while the ones extracted using Klapuri's algorithm will be referred as V M klap . Similarly, for the separated vocal signals we use V Sep praat . For ground truth we extract a reference pitch contour using Praat from the original voice-only track of each song. We confirmed that this ground truth is correct by listening to the generated contours.

For the purpose of this specific evaluation we only consider the singing segments of each song, identified as the segments in the ground truth pitch contours that present non-zero frequency values. For each pitch contour we compute at each frame the normalized pitch error as follows:

N E[k] = log 2 f [k] f ref [k] (26)
where Given that this evaluation is related to (musical) pitch estimation, we also defined a chroma-based error measure N E chr derived from N E, where errors are folded into a single octave as follows:

f ref [k] corresponds
N E chr [k] =      0 if N E[k] = 0 1 if N E[k] = 0 ∧ mod(N E[k], 1) = 0 mod(N E[k], 1) otherwise (27)
where mod() is the real modulo function. This allows bringing to evidence the chromatic distribution of the errors, wrapping all pitch inaccuracies into the interval [0, 1], where 0 corresponds to no pitch estimation error and 1 accumulates all the octave-related errors.

Table V shows the normalized pitch errors across our dataset of 10 songs for the different evaluation scenarios. It also presents the gross error (GE) for each case, defined as the sum of all errors bigger than half a semitone (i.e. for N E > 1 24 ). This tolerance allows accepting estimated frequencies inside a one semitone interval centered around the true pitch as correct estimates. Also presented is the gross error excluding all octave errors (GE -8 ve ). Octave ambiguities can be accepted as having smaller impact than other errors for many musical applications.

From the results obtained from the V M praat evaluation, a GE in excess of 82% confirms the expected inability of monophonic pitch detectors such as the Praat algorithm to accurately estimate the most prominent pitch on polyphonic music recordings. However, if using the same exact pitch estimation technique on the voice signal separated by our system (i.e. V Sep praat ), the results demonstrate a clear improvement, reducing the gross error rate GE to about 64%. Although the proposed scheme do not compare favourably to the stateof-the-art multipitch algorithm by Klapuri (GE of 55.7%), it shows the ability of our method to simplify the acoustic scene by focusing on the dominant harmonic source.

It is also interesting to look at the distribution of errors. Figure 6 shows the distribution of the normalized and octave wrapped errors as percentages over the total number of estimated pitch frames (the upper plot presents the significant section of the N E distribution while the lower plot shows the N E chr distribution). All three evaluations presented in the plots show a similar tendency to output one-octave ambiguities (i.e. about 6% for N E = 1). V M praat presents several additional high-valued error peaks caused by incorrect pitches estimated due to the presence of multiple overlapping notes from the musical background. These errors are significantly reduced in the case of the pitch estimation on the separated signal using our method. When compared to V M klap most of the pitch estimation errors from V Sep praat result from octave and perfect-fifth (i.e N E chr = 7/12) ambiguities.

We also conducted similar experiments using the corpus used for the MIREX automatic melody extraction evaluation exchange 3 . In this case we had no access to the original melody-only tracks, but ground truth pitch contours were provided for the evaluation. The MIREX examples include some synthesized MIDI pieces, which are simpler to separate as they do not include reverberation and other artifacts found in realworld signals. Most of the examples also have a more pronounced vocal line or dominant melody than the corpus used for the previous experiments, and therefore most of the results were better. Table VI shows the normalized pitch errors and gross errors for the MIREX corpus. The distribution of the normalized errors are depicted in Figure 7.

D. Voicing Detection

Voicing detection refers to the process of identifying whether a given time frame contains a "melody" pitch or not. The goal of the experiments described in this subsection was to determine whether the proposed voice separation algorithm can be used to improve voicing detection accuracy in monaural polyphonic recordings. The dataset of the 10 polyphonic music pieces for which we have the original separate vocal track was used for the experiments. The voiced/unvoiced decisions extracted using Praat [START_REF] Boersma | Praat: doing phonetics by computer (version 4.5.06)[END_REF] from the original vocal track were used as the ground truth. A supervised learning approach was used to train voiced/unvoiced classifiers for three configurations: V M M F CC refers to using Mel-Frequency Cepstral Coefficients (MFCC) [START_REF] Davis | Experiments in syllable-based recognition of continuous speech[END_REF] calculated over the mixed voice and music signal, V Sep M F CC refers to MFCC calculated over the automatically separated voice signal, and V Sep CP R refers to using the cluster peak ratio (CPR), a feature that can be directly calculated on each extracted clusters of peaks. It is defined as:

CP R = max(A k ) mean(A k ) (28)
where A k are the extracted peak amplitudes for frame k.

Voiced frames tend to have more pronounced peaks than unvoiced frames and therefore higher CPR values. The experiments were performed using the Weka machine learning framework, where NB refers to a Naive Bayes classifier and SVM to a support vector machine trained using the sequential minimal optimization (SMO) [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. The ZeroR classifier classifies everything as voiced and was used as a baseline. The goal was to evaluate the relative improvement in classification performance when using the separated voice signal rather than building an optimal voicing detector. No smoothing of the predictions was performed.

Table VII shows the classification accuracy (i.e the percentage of frames correctly classified using these 3 configurations). All the results were computed using 10-fold cross-validation over features extracted from the entire corpus. In 10-fold cross-validation the feature matrix is shuffled and partitioned into 10 "folds". The classification accuracy is calculated by using 9 of the folds for training and 1 fold for testing and the process is repeated 10 times so that all partitions become the testing set once. The classification results are averaged. 10-fold cross-validation is used to provide a more balanced estimate of classification accuracy that is not as sensitive to a particular choice of training and testing sets [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. Using the automatically separated voice results in significant improvements in voicing detection accuracy. Additionally, the use of the simple and direct CPR feature still outperforms a more complex classifier trained on the mixed data.

IV. CONCLUSIONS AND FUTURE WORK

We described how spectral clustering using the normalized cut criterion for graph partitioning can be used for predominant melodic source separation. Our proposed method is based on a sinusoidal peak representation which enables close to real-time computation due to its sparse nature. Grouping cues based on amplitude, frequency and harmonicity are incorporated in a unified optimization framework. Harmonically-Wrapped Peak Similarity (HWPS), a novel harmonicity similarity measure was also proposed. Experimental results evaluating HWPS and the proposed method in the context of mixture separation, audio melody extraction and voicing detection were presented. The proposed algorithm is causal, efficient and doesn't require any prior knowledge or song-specific parameter tuning.

There are many possible directions for future work. Although not necessary for the operation of the algorithm, prior knowledge such as sound source models or score representations could easily be incorporated into the similarity calculation. For example the likelihood that two peaks belong to the same sound source model [START_REF] Vincent | Musical source separation using time-frequency priors[END_REF] could be used as an additional similarity cue. Additional cues such as common amplitude and frequency modulation as well as the use of timing information such as onsets are interesting possibilities for future work. Another interesting possibility is the addition of common panning cues for stereo signals as proposed in [START_REF] Jourjine | Blind separation of disjoint orthogonal signals: Demixing n sources from 2 mixtures[END_REF], [START_REF] Avendano | Frequency-domain source identification and manipulation in stereo mixes for enhancement, suppression, and re-panning applications[END_REF].

Limitations of the current method suggest other directions of future work. Even though some grouping of components corresponding to consonants is achieved by the amplitude and frequency similarity cues, the sinusoidal representation is not particularly suited for non-pitched sounds such as consonants sounds. Alternative analysis front-ends such as perceptually-informed filterbanks or sinusoids+transient representations could be a way to address this limitation.

In the current system, the cluster selection and resynthesis are performed for the entire song independently of whether a singing voice is present or not. The use of a singing voice detector to guide the resynthesis would surely result in better results. Implementing such a singing voice detector directly based on properties of the detected cluster is an interesting possibility. The resynthesis also suffers from artifacts that result from the limitations of the sinusoidal representation. An interesting alternative would be to retain the sinusoidal modeling front-end for grouping but use the entire STFT spectrum for the resynthesis of the extracted voice. As studied in [START_REF] Lagrange | Semi-Automatic Mono to Stereo Up-mixing using Sound Source Formation[END_REF], such a resynthesis stage is more flexible and reduces artifacts.

Finally, in the current implementation, clustering and cluster selection are performed independently for each "texture" window. In the future we plan to explore cluster continuity constraints (for example neighbouring clusters in time corresponding to the same source should have similar overall characteristics) as well as more sophisticated methods of cluster selection.

We believe our work shows the potential of spectral clustering methods for sound source formation and tracking. We hope it will stimulate more research in this area as it can have significant impact in many MIR applications such as singer identification, music transcription and lyrics alignment.

Fig. 1 .

 1 Fig. 1. Block-diagram of the voice segregation chain.

Fig. 2 .

 2 Fig.2. Two sets of harmonically related peaks (same data as TableI). Used forFigures 3,[START_REF] Ghias | Query by Humming: Musical Information Retrieval in an Audio Database[END_REF][START_REF] Dannenberg | The MUSART testbed for query-by-humming evaluation[END_REF]

Fig. 3 .

 3 Fig. 3. HWPS calculation for peaks A 0 ♦ and A 1 * , from Figure 2. From top to bottom: Shifted Spectral Pattern, Harmonically-Wrapped Frequency and Histogram of Harmonically-Wrapped Frequency. Notice the high correlation between the two histograms at the bottom of the figure.

Fig. 4 .

 4 Fig. 4. HWPS calculation for peaks A 1 ♦ and B 1 * , from Figure 2. From top to bottom: Shifted Spectral Pattern, Harmonically-Wrapped Frequency and Histogram of Harmonically-Wrapped Frequency. Notice the lack of correlation between the two histograms at the bottom of the figure.

Fig. 5 .

 5 Fig.5. Harmonically-Wrapped Peak Similarity (HWPS) matrix for two harmonic sources using the correct f 0 estimates (left), and using the conservative estimate of wrapping frequency (likely a harmonic of the "true" f 0 ) (right). High similarity values are mapped to black and low similarity values to white.

Fig. 6 .

 6 Fig.6. Distribution of errors as percentages of total pitch estimates across corpus. The top plot presents a segment of the normalized error distribution, N E (no significant error values exist outside the plotted ranges), while the bottom plot depicts the corresponding octave wrapped error distribution, N E chr . The pitch errors from using Praat on the separated voice signals are represented in black colour, while its use on mixed signals is represented by the slashed line and white bars. The multiple pitch approach of Klapuri is represented in gray.

Fig. 7 .

 7 Fig. 7. Distribution of errors over the MIREX audio melody extraction dataset. The top plot presents a segment of the normalized error distribution, N E (no significant error values exist outside the plotted range), while the bottom plot depicts the corresponding octave wrapped error distribution, N E chr . The pitch errors from using Praat on the separated voice signals are represented in black colour, while its use on mixed signals is represented by the slashed line and white bars. The multiple pitch approach of Klapuri is represented in gray.

•

  Peaks are the output of the sinusoidal modeling stage. For each frame, a variable number of peaks corresponding to

		Texture Window	Similarity Computation
	Spectral Peaks	Spectral Peaks (over Texture Window)	Cluster Selection	Spectral Peaks
	Sinusoidal			Sinusoidal
	Analysis			Synthesis
			Normalized Cut
	46ms	150ms		46ms

TABLE V NORMALIZED

 V PITCH ERRORS AND GROSS ERRORS ACROSS CORPUS

		N E	N E chr	GE(%) GE -8 ve (%)
	V Mpraat	8.62	0.51	82.44	66.00
	V Seppraat	3.89	0.35	64.45	55.23
	V M klap	0.55	0.26	55.70	48.68

  to the frequency values of the ground truth pitch contour, measured in Hertz, and k is the frame index. f [k] is either related to the frequency value of the pitch contour extracted from the mixed signal (i.e. V M praat or V M klap ), or to the pitch contour extracted using the vocal track separated by our algorithm (i.e. V Sep praat ). The normalized error N E is zero when the pitch estimation is correct, and an integer number for octave errors (i.e. whenf [k] = 2 n × f ref [k], n ∈ N).Since we are only considering the singing segments of the signals, both f [k] and f ref [k] will never be zero.

TABLE VI NORMALIZED

 VI PITCH ERRORS AND GROSS ERRORS FOR MIREX DATASET

					N E	N E chr		GE(%) GE -8 ve (%)
				V Mpraat	3.29	0.48		76.02	55.87
				V Seppraat	1.34	0.36		54.12	34.97
				V M klap	0.34	0.15		34.27	29.77
		15
	Distribution of Errors (%)	5 10								VM praat VM klap VSep praat
		0	0	0.5	1	1.5	2	2.5	3	3.5	4
						Normalized Pitch Error (NE)
		25
	Distribution of Errors (%)	5 10 15 20							VM praat VM klap VSep praat
		0	0	1/12 2/12 3/12 4/12 5/12 6/12 7/12 8/12 9/12 10/12 11/12	1
					Normalized and Octave Wrapped Pitch Error (NE chr )

http://marsyas.sourceforge.net

http://opihi.cs.uvic.ca/NormCutAudio

http://www.music-ir.org/mirex2005/index.php/Main_

ACKNOWLEDGMENTS

The authors would like to thank Kirk McNally and Ewenn Camberlein for providing part of the testing corpus used for the experiments. In addition Luis Filipe Teixeira helped a lot with solving various coding problems related to the use of Marsyas. The authors would also like to thank Anssi Klapuri for kindly providing the multi pitch estimator code [37]. Finally, we would like to thank the anonymous reviewers for their thorough comments and suggestions for improvement.


Olivier Sename
email: olivier.sename@inpg.fr

New trends in vehicle dynamics: from modelling to control

I. SESSION TOPIC

Over the past few years, automotive engineering has been characterized by rapid growth in active systems. Many research works have therefore been devoted to the control of such active subsystems, as braking, steering or suspension actuators. In particular the use of different actuators (braking, steering, suspension ...) allow to tackle emergency situations such as rollover, too large lateral and yaw accelerations, slipping .... [START_REF] Tanelli | Combining slip and deceleration control for brake-by-wire control systems: a sliding-mode approach[END_REF], [START_REF] Botero | On the reformulation of the ABS logic by sensing forces and moments at the wheels[END_REF], [START_REF] Gáspár | Rollover stability control for heavy vehicles by using LPV model[END_REF].

On the other hand the control of suspension systems still remains of interest as this subsystem influences comfort and road handling as well [START_REF] Hrovat | Survey of advanced suspension developments and related optimal control applications[END_REF], [START_REF] Zin | Robust lpv -H∞ control for active suspensions with performance adaptation in view of global chassis control[END_REF]. New advances control approaches such as H ∞ approach for Linear Parameter Varying systems and Model predictive control have shown to be efficient in this framework [START_REF] Gáspár | Active suspension design using LPV control[END_REF], [START_REF] Poussot-Vassal | A new semi-active suspension control strategy through lpv technique[END_REF], [START_REF] Canale | Semi-active suspension control using fast model-predictive techniques[END_REF].

On the other hand, the complex and multivariable inherent nature of the vehicle asks for the need of integrated approaches, in order to account for the coupling dynamics (roll, yaw, pitch, vertical, longitudinal and lateral behaviors) and to deal with different actuators.

The aim of this invited session is to give some recent results on vehicle dynamics control through the use of new innovative systems and control tools.

II. SESSION GOALS AND COHESIVENESS

The session goal and cohesiveness is to present various recent and innovative works where the vehicle dynamical behavior is improved thanks to the use of different kind of actuators (suspension, braking, steering,...). This needs new methods for modelling and control of subsystems and of the vehicle.

The session will be organized as follows:

• Papers 1 and 2 concern the development of control design methods for semi-active suspensions.

• In paper 3, a LPV approach is considered to control the vehicle dynamics (e.g. rollover) through active suspensions, even in the presence of fault actuators. • Paper 4 concerns the application of nonlinear Internal Model Control for the yaw dynamics.

• In paper 5, a new LPV approach is proposed for the vehicle dynamics control using braking and steering actuators.

• In paper 6 , the braking subsystem is considered for the stop-and-go system.

• In Paper 7 a new method for vehicle speed estimation is proposed • Paper 8 deals with the H ∞ control of a landing gear steering system.

III. PAPERS OF THE SESSION

A. Paper 1 Title:A new concept of semi-active suspension with controllable damper and spring. Authors:Cristiano Spelta, Maurizio Cutini, Carlo Bisaglia, Simone A. Bertinotti, Sergio M. Savaresi, Fabio Previdi and Paolo Bolzern

The problem considered in this paper is the design and analysis of implementable architectures and control strategies for semi-active suspensions characterized by a regulation of both damping and stiffness coefficients. Nowadays reliable and cost-effective technologies for the modulation of spring coefficient are not available. The first contribution of this paper is the introduction of a suspension architecture that makes possible the emulation of the behavior of an ideal suspension with variable spring. Taking into account the comfort objective, a full analysis on the advantages and drawbacks of this kind of suspension is provided. The main trade-off arising from the use of this kind of suspension consists on one hand in a better filtering of the road disturbances due to possibility of modulating the spring characteristic, and on the other hand in the end-stop hits that occur due to the spring stiffness modulation. This paper proposes a novel comfort-oriented stiffness-damping control algorithm that overcomes this critical trade-off while ensuring better performances compared to classical semi-active strategies with damping modulation only. In this paper, a semi-active control strategy is developped to improve comfort and roadholding of a ground vehicle. The system under study is an industrial damper designed by SOBEN to be controlled by means of a small servomechanism. The main controller is a static state feedback controller synthesized in the H ∞ /LP V framework to compute the required damping force that minimizes the movements of the vehicles body on one hand, and the deflection of the tire on the other hand. A scheduling strategy is developped on the basis of the real damper behavior to improve performances without using active damping forces which would be useless for such a semi-active system. Here the controller takes the constraints of the technology and the damper behavior into account and is easy to implement in an industrial application. The control of the servomechanism is provided by a simple PID controller that makes the damper provide the required force. The performance of the overall is illustrated on an identified nonlinear model of the damper included into a quarter car model. The comfort and roadholding level of the semi-active suspension are studied using some adapted criteria and compared with the passive ones. Some simulations emphasize the comfort and roadholding improvements of this control stategy that will be tested by SOBEN on the new Renault Laguna III in the next weeks.

C. Paper 3 Title:LPV-based reconfigurable chassis design Authors: P. Gaspar, Z. Szabo, J. Bokor This paper proposes the design of reconfigurable and fault-tolerant suspension systems in road vehicles. The purpose of the suspension system is to improve passenger comfort, road holding and safety during travel and various maneuvers. When a rollover is imminent the suspension system generates a stabilizing moment to balance the overturning moment and reduce the rollover risk. When pitching dynamics is significant during abrupt and hard braking the suspension system generates a moment to improve road holding and comfort. In the modeling the nonlinearities of the suspension system, the changes in the forward velocity and the change of the adhesion coefficient between the tire and the road are taken into consideration. The effects of the longitudinal or lateral load transfers during maneuvers or abrupt hard brakings are monitored in order to reduce their harmful effects on handling and comfort. Moreover, when a fault (loss in effectiveness) occurs at one of the suspension actuators a reconfiguration is required in order to guarantee fault-tolerant operation. In the control design the bound of the unmodelled dynamics is also taken into consideration. The design of the proposed control system is based on an Hinf Linear Parameter Varying (LPV) method that uses monitored scheduling variables of the travel. The use of a novel approach to nonlinear internal model control (NIMC) is investigated in vehicle yaw control context. The proposed control technique is based on recent results for left inversion of nonlinear dynamical systems from data in a set membership (SM) environment which avoid the direct derivation of the inverse model. Such inverse model is the basic element of the NIMC controller which contains also a nonlinear model of the vehicle dynamics identified via SM methodologies directly from data. Perforamance of the introduced control scheme is tested through simulation results obtained using a nonlinear model of the vehicle.

E. Paper 5 Title:Robust Automotive Steering and Braking Controller Authors: Charles Poussot-Vassal, Olivier Sename and Luc Dugard

This paper is concerned with the synthesis of a robust steering and braking controller to enhance automotive vehicle yaw stability and lateral performances. The contribution of this work is to provide a methodology, based on the H ∞ theory, to synthesize such a controller, while taking into account the braking actuator limitations. In the proposed solution, the controller structure is designed in an original way and is coupled with a local ABS strategy to guarantee slip stability and make the solution complete for implementation issues. Time and frequency -domain simulations on a complex nonlinear full vehicle model, subject to critical driving situations, shows the reliability and efficiency of the proposed solution. In this paper, we propose a model free control approach to deal with automotive longitudinal control in the case of Stop-and-Go scenario. Stop-and-Go attempts to place automatically the vehicle at safe distances in urban environments. In this case, accelerating and braking maneuvers are very demanding in short time intervals, but the corresponding torques are often difficult to obtain because of the uncertainty of dynamics, not only at the chassis level but also at the engine/brake model. In order to compensate the losses related to the neglected dynamics, a free model control approach will be used at the engine/brake level. Simulation results are presented to illustrate our method.

G. Paper 7 Title:Vehicle Speed Estimation with Compensation of Wheel Measures Noise Authors: Osvaldo Barbarisi, Luigi Glielmo

The longitudinal vehicle speed estimation is commonly realized by using longitudinal acceleration sensor and rotational speed sensors of each wheel. This information is depreciated when during regular manoeuvres such as steering, braking, accelerating, the slip ratio of a wheel is too high. In this paper we introduce a Kalman filter which considers the stochastic properties of the signal.

H. Paper 8 Title:Reduced order H ∞ control design of a Nose Landing Gear steering system Authors: Gaëtan Pouly, Jean-Philippe Lauffenburger and Michel Basset

In recent years, aeronautics has witnessed the emergence of increased electrical on board equipment. Today, the reverse thrust, the engine starter, the braking system can operate electrically. The present paper describes the use of a new nose landing gear steering system, using an electromechanical actuator. More specifically, a reduced order H ∞ solution helps to control the actuator and so, to steer the aircraft front wheel. The paper first presents the nose landing gear model coupled with the electromechanical actuator, then discusses the use of the HIFOO tool to synthesize a reduced order controller. Various control strategies are considered, different simulations are proposed and finally, the impact of the controller order is discussed.

B. Paper 2

 2 Title:Semi-active H ∞ /LPV control for an industrial hydraulic damper Authors: S. Aubouet, L. Dugard, O. Sename, B. Talon, C. Poussot-Vassal

D. Paper 4

 4 Title: A nonlinear IMC approach to vehicle yaw control Authors: M. Canale, C. Novara, M.C. Signorile

F. Paper 6

 6 Title: Model free control of automotive engine and brake for Stop-and-Go scenario Authors: Sungwoo Choi, Brigitte d'Andréa-Novel, Michel Fliess, Hugues Mounier, Jorge Villagra