Marco Liuni

Axel Röbel

Romito Marco

Xavier Rodet
email: xavier.rodet@ircam.frmarco.romito@math.unifi.it

Marco Romito

An Entropy Based Method for Local Time-Adaptation of the Spectrogram

Keywords: adaptive spectrogram, sound representation, sound analysis, sound synthesis, Rényi entropy, sparsity measures, frame theory

published or not. The documents may come

Introduction

Far from being restricted to entertainment, sound processing techniques are required in many different domains: they find applications in medical sciences, security instruments, communications among others. The most challenging class of signals to consider is indeed music: the completely new perspective opened by contemporary music, assigning a fundamental role to concepts as noise and timbre, gives musical potential to every sound.

The standard techniques of digital analysis are based on the decomposition of the signal in a system of elementary functions, and the choice of a specific system necessarily has an influence on the result. Traditional methods based on single sets of atomic functions have important limits: a Gabor frame imposes a fixed resolution over all the time-frequency plane, while a wavelet frame gives a strictly determined variation of the resolution: moreover, the user is frequently asked to define himself the analysis window features, which in general is not a simple task even for experienced users. This motivates the search for adaptive methods of sound analysis and synthesis, and for algorithms whose parameters are designed to change according to the analyzed signal features. Our research is focused on the development of mathematical models and tools based on the local automatic adaptation of the system of functions used for the decomposition of the signal: we are interested in a complete framework for analysis, spectral transformation and re-synthesis; thus we need to define an efficient strategy to reconstruct the signal through the adapted decomposition, which must give a perfect recovery of the input if no transformation is applied.

Here we propose a method for local automatic time-adaptation of the Short Time Fourier Transform window function, through a minimization of the Rényi entropy [START_REF] Zibulski | Analysis of multiwindow Gabor-type schemes by frame methods[END_REF] of the spectrogram; we then define a re-synthesis technique with an extension of the method proposed in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF]. Our approach can be presented schematically in three parts:

1. a model for signal analysis exploiting concepts of Harmonic Analysis, and Frame Theory in particular: it is a generally highly redundant decomposing system belonging to the class of multiple Gabor frames [START_REF] Dörfler | Gabor Analysis for a Class of Signals called Music[END_REF], [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF];

2. a sparsity measure defined on time-frequency localized subsets of the analysis coefficients, in order to determine local optimal concentration; 3. a reduced representation obtained from the original analysis using the information about optimal concentration, and a synthesis method through an expansion in the reduced system obtained.

We have realized a first implementation of this scheme in two different versions: for both of them a sparsity measure is applied on subsets of analysis coefficients covering the whole frequency dimension, thus defining a time-adapted analysis of the signal. The main difference between the two concerns the first part of the model, that is the single frames composing the multiple Gabor frame. This is a key point as the first and third part of the scheme are strictly linked: the frame used for re-synthesis is a reduction of the original multi-frame, so the entire model depends on how the analysis multi-frame is designed. The section Frame Theory in Sound Analysis and Synthesis treats this part of our research in more details.

The second point of the scheme is related to the measure applied on the coefficients of the analysis within the multi-frame to determine local best resolutions. We consider measures borrowed from Information Theory and Probability Theory according to the interpretation of the analysis within a frame as a probability density [START_REF] Cohen | Time-Frequency Distributions-A Review[END_REF]: our model is based on a class of entropy measures known as Rényi entropies which extend the classical Shannon entropy. The fundamental idea is that minimizing the complexity or information over a set of time-frequency representations of the same signal is equivalent to maximizing the concentration and peakiness of the analysis, thus selecting the best resolution tradeoff [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF]: in the section Rényi Entropy of Spectrograms we describe how a sparsity measure can consequently be defined through an information measure. Finally, in the fourth section we provide a description of our algorithm and examples of adapted spectrogram for different sounds. Some examples of this approach can be found in the literature: the idea of gathering a sparsity measure from Rényi entropies is detailed in [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF], and in [START_REF] Jaillet | Représentation et traitement temps-fréquence des signaux audionumériques pour des applications de design sonore[END_REF] a local time-frequency adaptive framework is presented exploiting this concept, even if no methods for perfect reconstruction are provided. In [START_REF] Wolfe | Multi-Gabor Dictionaries for Audio Time-Frequency Analysis[END_REF] sparsity is obtained through a regression model; a recent development in this sense is contained in [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF] where a class of methods for analysis adaptation are obtained separately in the time and frequency dimension together with perfect reconstruction formulas: indeed no strategies for automatization are employed, and adaptation has to be managed by the user. The model conceived in [START_REF] Rudoy | Superposition frames for adaptive timefrequency analysis and fast reconstruction[END_REF] belongs to this same class but presents several novelties in the construction of the Gabor multiframe and in the method for automatic local time-adaptation. In [START_REF] Lukin | Adaptive Time-Frequency Resolution for Analysis and Processing of Audio[END_REF] another time-frequency adaptive spectrogram is defined considering a sparsity measure called energy smearing, without taking into account the re-synthesis task. The concept of quilted frame, recently introduced in [START_REF] Dörfler | Quilted Gabor frames -a new concept for adaptive time-frequency representation[END_REF], is the first promising effort to establish a unified mathematical model for all the various frameworks cited above.

Frame Theory in Sound Analysis and Synthesis

When analyzing a signal through its decomposition, the features of the representation are influenced by the decomposing functions; the Frame Theory (see [START_REF] Christensen | An Introduction To Frames And Riesz Bases[END_REF], [START_REF] Gröchenig | Foundations of Time-Frequency Analysis[END_REF] for detailed mathematical descriptions) allows a unified approach when dealing with different bases and systems, studying the properties of the operators that they identify. The concept of frame extends the one of orthonormal basis in a Hilbert space, and it provides a theory for the discretization of time-frequency densities and operators [START_REF] Dörfler | Gabor Analysis for a Class of Signals called Music[END_REF], [START_REF] Sun | Asymptotic properties of Gabor frame operators as sampling density tends to infinity[END_REF], [START_REF] Borichev | Frame constants of gabor frames near the critical density[END_REF]. Both the STFT and the Wavelet transform can be interpreted within this setting (see [START_REF] Mallat | A wavelet tour on signal processing[END_REF] for a comprehensive survey of theory and applications).

Here we summarize the basic definitions and theorems, and outline the fundamental step consisting in the introduction of Multiple Gabor Frames, which is comprehensively treated in [START_REF] Dörfler | Gabor Analysis for a Class of Signals called Music[END_REF]. The problem of standard frames is that the decomposing atoms are defined from the same original function, thus imposing a limit on the type of information that one can deduce from the analysis coefficients; if we were able to consider frames where several families of atoms coexist, than we would have an analysis with variable information, at the price of a higher redundancy.

Basic Definitions and Results

Given a Hilbert space H seen as a vector space on C, with its own scalar product, we consider in H a set of vectors {φ γ } γ∈Γ where the index set Γ may be infinite and γ can also be a multi-index. The set {φ γ } γ∈Γ is a frame for H if there exist two positive non zero constants A and B, called frame bounds, such that for all

f ∈ H, A f 2 ≤ γ∈Γ | f, φ γ | 2 ≤ B f 2 . ( 1
)
We are interested in the case H = L 2 (R) and Γ countable, as it represents the standard situation where a signal f is decomposed through a countable set of given functions {φ k } k∈Z . The frame bounds A and B are the infimum and supremum, respectively, of the eigenvalues of the frame operator U, defined as

Uf = k∈Z f, φ k φ k . (2)
For any frame {φ k } k∈Z there exist dual frames

{ φk } k∈Z such that for all f ∈ L 2 (R) f = k∈Z f, φ k φk = k∈Z f, φk φ k , (3)
so that given a frame it is always possible to perfectly reconstruct a signal f using the coefficients of its decomposition through the frame. The inverse of the frame operator allows the calculation of the canonical dual frame

φk = U -1 φ k (4)
which guarantees minimal-norm coefficients in the expansion.

A Gabor frame is obtained by time-shifting and frequency-transposing a window function g according to a regular grid. They are particularly interesting in the applications as the analysis coefficients are simply given by sampling the STFT of f with window g according to the nodes of a specified lattice. Given a time step a and a frequency step b we write {u n } n∈Z = an and {ξ k } k∈Z = bk; these two sequences generate the nodes of the time-frequency lattice Λ for the frame {g n,k } (n,k)∈Z 2 defined as

g n,k (t) = g(t -u n )e 2πiξ k t ;
(5) the nodes are the centers of the Heisenberg boxes associated to the windows in the frame. The lattice has to satisfy certain conditions for {g n,k } to be a frame [START_REF] Daubechies | The Wavelet Transform, Time-Frequency Localization and Signal Analysis[END_REF], which impose limits on the choice of the time and frequency steps: for certain choices [START_REF] Daubechies | Painless nonorthogonal expansions[END_REF] which are often adopted in standard applications, the frame operator takes the form of a multiplication,

Uf (t) = b -1 n∈Z |g(t -u n )| 2 f (t) , (6)
and the dual frame is easily calculated by means of a straight multiplication of the atoms in the original frame. The relation between the steps a, b and the frame bounds A, B in this case is clear by [START_REF] Cohen | Time-Frequency Analysis[END_REF], as the frame condition implies

0 < A ≤ b -1 n∈Z |g(t -u n )| 2 ≤ B < ∞ . (7)
Thus we see that the frame bounds provide also information on the redundancy of the decomposition of the signal within the frame.

Multiple Gabor Frames

In our adaptive framework, we look for a method to achieve an analysis with multiple resolutions: thus we need to combine the information coming from the decompositions of a signal in several frames of different window functions. Multiple Gabor frames have been introduced in [START_REF] Zibulski | Analysis of multiwindow Gabor-type schemes by frame methods[END_REF] to provide the original Gabor analysis with flexible multi-resolution techniques: given a set of index L ⊆ Z and different frames {g l n,k } (n,k)∈Z 2 with l ∈ L, a multiple Gabor frame is obtained with a union of the single given frames. The different g l do not necessarily share the same type or shape: in our method an original window is modified with a finite number of scaling

g l (t) = 1 √ l g t l ; (8)
then all the scaled versions are used to build |L| different frames which constitute the initial multi-frame.

A Gabor multi-frame has in general a significant redundancy which lowers the readability of the analysis. A possible strategy to overcome this limit is proposed in [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF] where nonstationary Gabor frames are introduced, actually allowing the choice of a different window for each time location of a global irregular lattice Λ, or alternatively for each frequency location. This way, the window chosen is a function of time or frequency position in the time-frequency space, not both. In most applications, for this kind of frame there exist fast FFT based methods for the analysis and re-synthesis steps. Referring to the time case, with the abuse of notation g n(l) we indicate the window g l centered at a certain time n(l) = u n which is a function of the chosen window itself. Thus, a nonstationary Gabor frame is given by the set of atoms

{g n(l) e 2πib l kt , (n(l), b l k) ∈ Λ} , (9)
where b l is the frequency step associated to the window g l and k ∈ Z . If we suppose that the windows g l have limited time support and a sufficiently small frequency step b l , the frame operator U takes a similar form to the one in [START_REF] Cohen | Time-Frequency Analysis[END_REF],

Uf (t) = n(l) 1 b l |g n(l) (t)| 2 f (t) . (10)
Here, if

N = l 1 b l |g n(l) (s)| 2 ≃
1 then U is invertible and the set ( 9) is a frame whose dual frame is given by

gn(l),k (t) = 1 N g n(l) (t)e 2πib l kt . ( 11
)
Nonstationary Gabor frames belong to the recently introduced class of quilted frames [START_REF] Dörfler | Quilted Gabor frames -a new concept for adaptive time-frequency representation[END_REF]: in this kind of decomposing systems the choice of the analysis window depends on both the time and the frequency location, causing more difficulties for an analytic fast computation of a dual frame as in [START_REF] Flandrin | Time-Frequency/ Time-Scale Analysis[END_REF]: future improvements of our research concern the employment of such a decomposition model for automatic local adaptation of the spectrogram resolution both in the time and the frequency dimension.

Rényi Entropy of Spectrograms

We consider the discrete spectrogram of a signal as a sampling of the square of its continuous version

PS f (u, ξ) = |Sf (u, ξ)| 2 = f (t)g(t -u)e -2πiξt dt 2 , ( 12
)
where f is a signal, g is a window function and Sf (u, ξ) is the STFT of f through g. Such a sampling is obtained according to a regular lattice Λ ab , considering a Gabor frame [START_REF] Cohen | Time-Frequency Distributions-A Review[END_REF],

PS f [n, k] = |Sf [u n , ξ k ]| 2 . ( 13
)
With an appropriate normalization both the continuous and discrete spectrogram can be interpreted as probability densities. Thanks to this interpretation, some techniques belonging to the domain of Probability and Information Theory can be applied to our problem: in particular, the concept of entropy can be extended to give a sparsity measure of a time-frequency density. A promising approach [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF] takes into account Rényi entropies, a generalization of the Shannon entropy: the application to our problem is related to the concept that minimizing the complexity or information of a set of time-frequency representations of a same signal is equivalent to maximizing the concentration, peakiness, and therefore the sparsity of the analysis. Thus we will consider as best analysis the sparsest one, according to the minimal entropy evaluation.

Given a signal f and its spectrogram PS f as in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF], the Rényi entropy of order α > 0, α = 1 of PS f is defined as follows

H R α (PS f ) = 1 1 -α log 2 R PS f (u, ξ) R PS f (u ′ , ξ ′ )du ′ dξ ′ α dudξ , (14)
where R ⊆ R 2 and we omit its indication if equality holds. Given a discrete spectrogram with time step a and frequency step b as in [START_REF] Gröchenig | Foundations of Time-Frequency Analysis[END_REF], we consider R as a rectangle of the time-

frequency plane R = [t 1 , t 2 ] × [ν 1 , ν 2 ] ⊆ R 2 . It identifies a sequence of points G ⊆ Λ ab where G = {(n, k) ∈ Z 2 : t 1 ≤ na ≤ t 2 , ν 1 ≤ kb ≤ ν 2 }.
As a discretization of the original continuous spectrogram, every sample in PS f [n, k] is related to a time-frequency region of area ab; we thus obtain the discrete Rényi entropy measure directly from ( 14),

H G α [PS f ] = 1 1 -α log 2 [n,k]∈G PS f [n, k] [n ′ ,k ′ ]∈G PS f [n ′ , k ′ ] α + log 2 (ab) . (15)
We will focus on discretized spectrograms with a finite number of coefficients, as dealing with digital signal processing requires to work with finite sampled signals and distributions.

Among the general properties of Rényi entropies [START_REF] Rényi | On Measures of Entropy and Information[END_REF], [START_REF] Schlögl | Thermodynamics of chaotic systems[END_REF] and [START_REF] Zyczkowski | Rényi Extrapolation of Shannon Entropy[END_REF] we recall in particular those directly related with our problem. It is easy to show that for every finite discrete probability density P the entropy H α (P ) tends to coincide with the Shannon entropy of P as the order α tends to one. Moreover, H α (P ) is a non increasing function of α, so

α 1 < α 2 ⇒ H α1 (P ) ≥ H α2 (P ) . ( 16
)
As we are working with finite discrete densities we can also consider the case α = 0 which is simply the logarithm of the number of elements in P ; as a consequence H 0 (P ) ≥ H α (P ) for every admissible order α.

A third basic fact is that for every order α the Rényi entropy H α is maximum when P is uniformly distributed, while it is minimum and equal to zero when P has a single non-zero value.

All of these results give useful information on the values of different measures on a single density P as in [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF], while the relations between the entropies of two different densities P and Q are in general hard to determine analytically; in our problem, P and Q are two spectrograms of a signal in the same time-frequency area, based on two window functions with different scaling as in [START_REF] Daubechies | The Wavelet Transform, Time-Frequency Localization and Signal Analysis[END_REF]. In some basic cases such a relation is achievable, as shown in the following example.

Best Window for Sinusoids

When the spectrograms of a signal through different window functions do not depend on time, it is easy to compare their entropies: let PS s be the sampled spectrogram of a sinusoid s over a finite region G with a window function g of compact support; then PS s is simply a translation in the frequency domain of ĝ, the Fourier transform of the window, and it is therefore time-independent. We choose a bounded set L of admissible scaling factors, so that the discretized support of the scaled windows g l still remains inside G for any l ∈ L. It is not hard to prove that the entropy of a spectrogram taken with such a scaled version of g is given by H

G α (PS sl ) = H G α (PS s ) -log 2 l . (17)
The sparsity measure we are using chooses as best window the one which minimizes the entropy measure: we deduce from [START_REF] Mallat | A wavelet tour on signal processing[END_REF] that it is the one obtained with the largest scaling factor available, therefore with the largest time-support. This is coherent with our expectation as stationary signals, such as sinusoids, are best analyzed with a high frequency resolution, because time-independency allows a small time resolution. Moreover, this is true for any order α used for the entropy calculus. Symmetric considerations apply whenever the spectrogram of a signal does not depend on frequency, as for impulses.

The α Parameter

The α parameter in ( 14) introduces a biasing on the spectral coefficients; to have a qualitative description of this biasing, we consider a collection of simple spectrograms composed by a variable amount of large and small coefficients. We realize a vector D of length N = 100 generating numbers between 0 and 1 with a normal random distribution; then we consider the vectors

D M , 1 ≤ M ≤ N such that D M [k] = D[k] if k ≤ M D[k] 20 if k > M (18)
and then normalize to obtain a unitary sum. We then apply Rényi entropy measures with α varying between 0 and 30: as we see from figure 1, there is a relation between M and the slope of the entropy curves for the different values of α. For α = 0, H 0 [D M ] is the logarithm of the number of non-zero coefficients and it is therefore constant; when α increases, we see that densities with a small amount of large coefficients gradually decrease their entropy, faster than the almost flat vectors corresponding to larger values of M . This means that by increasing α we emphasize the difference between the entropy values of a peaky distribution and that of a nearly flat one. The sparsity measure we consider select as best analysis the one with minimal entropy, so reducing α rises the probability of less peaky distributions to be chosen as sparsest: in principle, this is desirable as weaker components of the signal, such as partials, have to be taken into account in the sparsity evaluation. But as well, this principle should be applied with care as a small coefficient in a spectrogram could be determined by a partial as well as by a noise component; choosing an extremely small α, the best window chosen could vary without a reliable relation with spectral concentration depending on the noise level within the sound.

Time and Frequency Steps

A last remark regards the dependency of ( 15) on the time and frequency step a and b used for the discretization of the spectrogram. When considering signals as finite vectors, a signal and its Fourier Transform have the same length. Therefore in the STFT the window length determines the number frequency points, while the sampling rate sets frequency values: the definition of b is thus implicit in the window choice. Actually, the FFT algorithm allows to specify a number of frequency points larger than the signal length: further frequency values are obtained as an interpolation between the original ones by properly adding zero values to the signal. If the sampling rate is fixed, this procedure causes a smaller b as a consequence of a larger number of frequency points. We have numerically verified that such a variation of b has no impact on the entropy calculus, so that the FFT size can be set according to implementation needs.

Regarding the time step a, we are working on the analytical demonstration of a largely verified evidence: as long as the decomposing system is a frame the entropy measure is invariant to redundancy variation, so the choice of a can be ruled by considerations on the invertibility of the decomposing frame without losing coherence between the information measure of the different analyses. This is a key point, as it states that the sparsity measure obtained allows a total independence between the hop sizes of the different analyses: with the implementation of proper structures to handle multi-hop STFTs we have obtained a more efficient algorithm in comparison with those imposing a fixed hop size, as [START_REF] Lukin | Adaptive Time-Frequency Resolution for Analysis and Processing of Audio[END_REF] and the first version of the one we have realized.

Algorithm and Examples

We now summarize the main operations of the algorithm we have developed providing examples of its application. For the calculation of the spectrograms we use a Hanning window

h(t) = cos 2 (πt)χ [-1 2 , 1 2 ] , (19)
with χ the indicator function of the specified interval, but it is obviously possible to generalize the results thus obtained to the entire class of compactly supported window functions. In both the versions of our algorithm we create a multiple Gabor frame as in (5), using as mother functions some scaled version of h, obtained as in [START_REF] Daubechies | The Wavelet Transform, Time-Frequency Localization and Signal Analysis[END_REF] with a finite set of positive real scaling factors L.

We consider consecutive segments of the signal, and for each segment we calculate |L| spectrograms with the |L| scaled windows: the length of the analysis segment and the overlap between two consecutive segments are given as parameters.

In the first version of the algorithm the different frames composing the multiframe have the same time step a and frequency step b: this guarantees that for each signal segment the different frames have Heisenberg boxes whose centers lay on a same lattice on the time-frequency plane, as illustrated in figure 2. To guarantee that all the |L| scaled windows constitute a frame when translated and modulated according to this global lattice, the time step a must be set with the hop size assigned to the smallest window frame. On the other hand, as the FFT of a discrete signal has the same number of points of the signal itself, the frequency step b has to be the FFT size of the largest window analysis: for the smaller ones, a zero-padding is performed. Each signal segment identifies a time-frequency rectangle G for the entropy evaluation: the horizontal edge is the time interval of the considered segment, while the vertical one is the whole frequency lattice. For each spectrogram, the rectangle G defines a subset of coefficients belonging to G itself. The |L| different subsets do not correspond to the same part of signal, as windows have different time supports. Therefore, a preliminary weighting of the signal has to be performed before the calculations of the local spectrograms: this step is necessary to balance the influence on the entropy calculus between coefficients which regard parts of signal shared or not shared by the different analysis frames. After the pre-weighting, we calculate the entropy of every spectrogram as in [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF]. Having the |L| entropy values corresponding to the different local spectrograms, the sparsest local analysis is defined as the one with minimum Rényi entropy: the window associated to the sparsest local analysis is chosen as best window at all the time points contained in G. The global time adapted analysis of the signal is finally realized by opportunely assembling the slices of local sparsest analyses: they are obtained with a further spectrogram calculation of the unweighted signal, employing the best windows selected at each time point.

In figure 4 we give an example of an adaptive analysis performed by our first algorithm with four Hanning windows of different sizes on a real instrumental sound, a B4 note played by a marimba: this sound combines the need for a good time resolution at the strike with that of a good frequency resolution on the harmonic resonance. This is fully provided by the algorithm, as shown in the adaptive spectrogram at the bottom of the figure 4. Moreover, we see that the pre-echo of the analysis at the bottom of figure 3 is completely removed in the adapted spectrogram.

The main difference in the second version of our algorithm concerns the individual frames composing the multi-frame, which have the same frequency step b but different time steps {a l : l ∈ L}: the smallest and largest window sizes are given as parameters together with |L|, the number of different windows composing the multi-frame, and the global overlap needed for the analyses. The algorithm fixes the intermediate sizes so that, for each signal segment, the different frames have the same overlap between consecutive windows, and so the same redundancy. This choice highly reduces the computational cost by avoiding unnecessary small hop sizes for the larger windows, and as we have observed in the previous section it does not affect the entropy evaluation. Such a structure generates an irregular time disposition of the multi-frame elements in each signal segment, as illustrated in figure 5; in this way we also avoid the problem of unshared parts of signal between the systems, but we still have a different influence of the boundary parts depending on the analysis frame: the beginning and the end of the signal segment have a higher energy when windowed in the smaller frames. This is avoided with a preliminary weighting: the beginning and the end of each signal segment are windowed respectively with the first and second half of the largest analysis window.

As for the first implementation, the weighting does not concern the decomposition for re-synthesis purpose, but only the analyses used for entropy evaluations.

After the pre-weighting, the algorithm follows the same steps described above: In figure 6 we give a first example of an adaptive analysis performed by the second version of our algorithm with eight Hanning windows of different sizes: the sound is still the B4 note of a marimba, and we can see that the two versions give very similar results. Thus, if the considered application does not specifically ask for a fixed hop size of the overall analysis, the second version is preferable as it highly reduces the computational cost without affecting the best window choice.

In figure 8 we give a second example with a synthetic sound, a sinusoid with sinusoidal frequency modulation: as figure 7 shows, a small window is best adapted where the frequency variation is fast compared to the window length; on window length (smps) frequency Fig. 6. Example of an adaptive analysis performed by the second version of our algorithm with eight Hanning windows of different sizes from 512 to 4096 samples, on a B4 note played by a marimba sampled at 44.1kHz: on top, the best window chosen as a function of time; at the bottom, the adaptive spectrogram. The entropy order is α = 0.7 and each analysis segment contains four frames of the largest window analysis with a two-frames overlap between consecutive segments. the other hand, the largest window is better where the signal is almost stationary.

Re-synthesis Method

The re-synthesis method introduced in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF] gives a perfect reconstruction of the signal as a weighted expansion of the coefficients of its STFT in the original analysis frame. Let S f [n, k] be the STFT of a signal f with window function h and time step a; fixing n, through an iFFT we have a windowed segment of f

f h (n, l) = h(na -l)f (l) , (20)
whose time location depends on n. An immediate perfect reconstruction of f is given by

f (l) = +∞ n=-∞ h(na -l)f h (n, l) +∞ n=-∞ h 2 (na -l) . (21)
In our case, after the automatic selection step we dispose of a temporal sequence with the best windows at each time position; in the first version we have a fixed hop for all the windows, in the second one every window has its own time step.

In both the cases we have thus reduced the initial multi-frame to a nonstationary Gabor frame: we extend the same technique of (21) using a variable window h and time step a according to the composition of the reduced multi-frame, obtaining a perfect reconstruction as well. The interest of ( 21) is that the given distribution does not need to be the STFT of a signal: for example, a transformation S * [n, k] of the STFT of a signal could be considered. In this case, [START_REF] Wolfe | Multi-Gabor Dictionaries for Audio Time-Frequency Analysis[END_REF] gives the signal whose STFT has minimal least squares error with S * [n, k].

As seen by the equations ( 9) and ( 11), the theoretical existence the mathematical definition of the canonical dual frame for a nonstationary Gabor frame like the one we employ has been provided [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF]: it is thus possible to define the whole analysis and re-synthesis framework within the Gabor theory. We are at present working on the interesting analogies between the two approaches, to establish a unified interpretation and develop further extensions.

Fig. 1 .

 1 Fig. 1. Rényi entropy evaluations of the DM vectors with varying α; the distribution becomes flatter as M increases.

Fig. 2 .

 2 Fig. 2. An analysis segment: time locations of the Heisenberg boxes associated to the multi-frame used in the first version of our algorithm.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Two different spectrograms of a B4 note played by a marimba, with Hanning windows of sizes 512 (top) and 4096 (bottom) samples.

Fig. 5 .

 5 Fig. 5. An analysis segment: time locations of the Heisenberg boxes associated to the multi-frame used in the second version of our algorithm.

Fig. 7 .

 7 Fig. 7. Two different spectrograms of a sinusoid with sinusoidal frequency modulation, with Hanning windows of sizes 512 (top) and 4096 (bottom) samples.

Fig. 8 .

 8 Fig. 8. Example of an adaptive analysis performed by the second version of our algorithm with eight Hanning windows of different sizes from 512 to 4096 samples, on a sinusoid with sinusoidal frequency modulation synthesized at 44.1 kHz: on top, the best window chosen as a function of time; at the bottom, the adaptive spectrogram. The entropy order is α = 0.7 and each analysis segment contains four frames of the largest window analysis with a three-frames overlap between consecutive segments.

⋆ This work is supported by grants from Region Ile-de-France.

Conclusions

We have presented an algorithm for time-adaptation of the spectrogram resolution, which can be easily integrated in existent framework for analysis, transformation and re-synthesis of an audio signal: the adaptation is locally obtained through an entropy minimization within a finite set of resolutions, which can be defined by the user or left as default. The user can also specify the time duration and overlap of the analysis segments where entropy minimization is performed, to privilege more or less discontinuous adapted analyses. Future improvements of this method will concern the spectrogram adaptation in both time and frequency dimensions: this will provide a decomposition of the signal in several layers of analysis frames, thus requiring an extension of the proposed technique for re-synthesis.


Tewfik Ziadi
email: tewfik.ziadi@lip6.fr

Marcos Aurélio Almeida Da Silva

Lom Messan Hillah
email: lom-messan.hillah@lip6.fr

Mikal Ziane
email: mikal.ziane@lip6.fr

A Fully Dynamic Approach to the Reverse Engineering of UML Sequence Diagrams

Keywords: reverse engineering, UML sequence diagrams, execution traces

The reverse engineering of behavioral models consists in extracting high-level models that help understand the behavior of existing software systems. In the context of reverse engineering of sequence diagrams, most approaches strongly depend on the static analysis and instrumentation of the source code to produce correct diagrams that take into account control flow structures such as alternative blocks ("if"s) and repeated blocks ("loop"s). This approach is not possible with systems for which no source code is available anymore (e.g. some legacy systems). In this paper, we propose an approach for the reverse engineering of sequence diagrams from the analysis of execution traces produced dynamically by an object-oriented application. Our approach is fully based on dynamic analysis and reuses the k-tail merging algorithm to produce a Labeled Transition System (LTS) that merges the collected traces. This LTS is then translated into a sequence diagram which contains alternatives and loops. A prototype of this approach has been tested with a real world application that has been developed independently from the present work. Our results show that this approach can produce sequence diagrams in reasonable time and suggest that these diagrams are helpful in understanding the behavior of the underlying application.

I. INTRODUCTION

Scenario formalisms, such as UML Sequence Diagrams (SDs), play an important role in software engineering. They help software engineers understand existing software through the visualisation of interactions between its objects [START_REF] Bennett | A survey and evaluation of tool features for understanding reverse-engineered sequence diagrams[END_REF]. They can also be used in testing activities [START_REF] Pickin | Test synthesis from UML models of distributed software[END_REF].

When sequence diagrams are either absent or inconsistent with the current code, as it is the case for many legacy systems, reverse engineering can be used to extract more accurate models. Reverse engineering can be done statically by analyzing the system's source code or dynamically by running the program and then analyzing the obtained execution traces to extract sequence diagrams. As underlined by [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF], dynamic analysis is better suited to the reverse engineering of sequence diagrams of object-oriented (OO) systems because of inheritance, polymorphism and dynamic binding. Indeed, it is difficult to know the dynamic type of an object reference and which methods are executed by only relying on the source code.

In this paper, we consider the reverse engineering of sequence diagrams from execution traces of object-oriented systems. An execution trace of an object-oriented system is defined as a sequence of method invocations where each method invocation represents a communication between two objects. Figure 1 shows simple traces related to the well known ATM (Automatic Teller Machine) [START_REF] Ziadi | Revisiting statechart synthesis with an algebraic approach[END_REF] example. While the mapping between method invocations in traces and messages in sequence diagrams is straightforward, two major challenges can be identified:

• Control flow detection. The first challenge concerns the detection of control structures in traces and their mapping to interaction operators in sequence diagrams. This mainly concerns the detection of the two main interaction operators included in UML sequence diagrams: alt and loop. • Multiple execution traces merging. The second challenge concerns merging execution traces. Indeed, the behavior of a system is often described by multiple execution traces that correspond to different scenarios.

Several approaches have been proposed for the reverse engineering of sequence diagrams regarding these two challenges (e.g., [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF], [START_REF] Rainer | Javavis: Automatic program visualization with object and sequence diagrams using the java debug interface (JDI)[END_REF], [START_REF] Lo | Mining modal scenariobased specifications from execution traces of reactive systems[END_REF]). In [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF] a complete review of these approaches is discussed. However, existing approaches often use static analysis by instrumenting the source code to identify if method invocations in traces are related to loop blocks in the source code. Although this solution ensures that the detected loop conforms to the source code, it can not be reused in the context where the source code is not available. Another limit related to existing work on the reverse engineering of sequence diagrams concerns the second challenge. Indeed these approaches [START_REF] Rainer | Javavis: Automatic program visualization with object and sequence diagrams using the java debug interface (JDI)[END_REF]- [START_REF] Taniguchi | Extracting Sequence Diagram from execution trace of Java Program[END_REF] only extract a sequence diagram from a single execution trace and it is not clear how they deal with multiple execution traces.

In this paper, we revisit the problem of reverse engineering sequence diagrams by a new approach which is completely based on dynamic analysis and which does not use any source code analysis. To tackle the two main challenges previously presented, our approach proposes to represent execution traces as Labeled Transition Systems (LTS). This enables us to define merging execution traces as merging LTSes using well founded algorithms such as k-tail [START_REF] Biermann | On the synthesis of finite state machines from samples of their behavior[END_REF]. To extract a sequence diagram from the obtained merged LTS, we propose to identify sequence diagrams as regular expressions. This enables us to generate them from the obtained LTS and ensure that they are trace equivalent [START_REF] Kleene | Representation of events in nerve nets and finite automata[END_REF], [START_REF] Neumann | Converting deterministic finite automata to regular expressions[END_REF].

In order to validate our approach, a prototype implementation was developed for Java systems. This prototype is able to observe a real Java system at runtime and to build a set of execution traces from it. From this set of execution traces it builds an LTS that merges the traces. From this LTS, it extracts a sequence diagram that depicts the interactions among the objects.

The paper is organized as follows. Section II introduces a background on reverse engineering of UML SD from execution traces and gives an overview of our approach. Section III deals with the extraction of LTS from execution traces. Section IV introduces our approach for sequence diagram extraction. Section V reports on first experiments using our prototype. Finally, Section VI discusses related work and Section VII concludes this paper.

II. BACKGROUND AND APPROACH

Our goal in this work is to extract UML sequence diagrams from multiple execution traces for an object-oriented system using only dynamic analysis. As underlined by [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF], dynamic analysis is better suited to the reverse engineering of sequence diagrams of object-oriented systems because of inheritance, polymorphism and dynamic binding. Before presenting an overview of our approach, we present in this section models that we used to formalize the reverse engineering of UML sequence diagrams. First, we define execution traces for object-oriented systems. Then we formalize sequence diagrams as regular expressions on method invocations.

A. Execution Traces for Object-Oriented Systems

Performing dynamic analysis of a object-oriented system starts by collecting an execution trace from its execution. An execution trace is defined as a sequence of method invocations. In the following, we formally define method invocations and traces.

Definition 1 (Method invocation): A Method invocation is a triplet caller, method, callee where:

• caller is the caller object, expressed in the form "object : class" • method is the invoked method of the callee object, expressed in the form "methodN ame()". In what follows, we introduce a definition of equivalence of method invocations which is necessary to formalize traces merging.

Definition 2 (Equivalence between method invocations): The method invocations inv1 = caller1, method1, callee1 and inv2 = caller2, method2, callee2 are equivalent if and only if:

• The two objects caller1 and caller2 are equivalent.

Two objects are equivalent if they are instances of the same class and are created (using the constructor invocation) with the same values of parameters. • method1 and method2 concern the same method and have the same signature.2 • callee1 and callee2 are two equivalent objects. To define equivalence between method invocations in our approach, we implemented in the Traces Collection step described below a component collecting all invocations of constructors in all execution traces. This allows us to check equivalence between objects using the rule defined in the definition above.

Definition 3 (Trace): A Trace is a sequence of method invocations inv 1 , inv 2 , ..inv n . Figure 1 illustrates an example of two execution traces for the well known ATM (Automatic Teller Machine) example. These traces show method invocations between four objects, instances of the classes: UserIHM, ATM, Consortium, and Bank. The first trace illustrates the execution of the ATM system where the user entered a bad password in two attempts and then decides to cancel the operation. The second trace shows a sequence of method invocations where the user cancels the operation after the password request. Note that these two traces also illustrate equivalence between method invocations as we defined above. Indeed, all method invocations labeled by the same label are equivalent events if they are related to different traces. For instance, all invocations labeled "inv3" in Trace 1 and Trace 2 are equivalent because the objects involved in these invocations are equivalent (they are created with the same values of parameters).

Note that in this paper we focus on sequential traces. If a concurrent system is considered, the traces collected from different threads are sequentially collected in a unique execution trace as described in [START_REF] Lorenzoli | Automatic Generation of Software Behavioral Models[END_REF]. In addition, in the presented example, we only presented synchronous invocations. However, our approach also supports asynchronous ones.

B. Sequence diagrams (SD)

A SD shows how a set of objects interact with each other. The diagrams considered in this paper follow the UML2 metamodel [START_REF] Omg | Unified Modeling Language: Superstructure -Version 2[END_REF]. Figure 3 shows an example of a sequence diagram which describes the interactions of two objects, instances respectively of classes UserIHM, and ATM. The vertical lines represent lifelines for the given objects. Interactions between objects, displayed as horizontal arrows, are called messages in the UML2 specification.

Each message corresponds to a method invocation. Messages located on the same lifeline are ordered from top to bottom. Interactions in sequence diagrams can be composed using operators. UML2 considers several operators among which we only kept the main ones, which also allows us to identify sequence diagrams as regular expressions: seq (for sequential composition), alt (for alternative) and loop (for iteration). Figure 3 illustrates the use of the alt operator. Notice that a sequential composition can also be implicitly given by the relative order of two messages in a diagram. For example, in Figure 3, the message displayMainScreen is specified before the message insertCard. This is equivalent to a sequential composition between these two messages 3 .

More formally, inspired by our precedent work [START_REF] Ziadi | Revisiting statechart synthesis with an algebraic approach[END_REF], SDs can be defined as algebraic expressions where atomic terms are method invocations and operators are the three operators mentioned above.

Definition 4 (Sequence Diagram (SD)): A sequence diagram is an expression of the form:

D ::= M | (D alt D) | (D seq D) | loop (D)
where M is a method invocation.

For instance, let us consider the sequence diagram in Figure 3. It can be represented by the following expression:

D = inv1 seq inv2 seq inv3 seq (inv4 alt inv5 )
where the invis are defined as:

• inv1 = (inv1. atm:ATM:|displayMainScreen() | user:userIHM), • inv2 = (inv2. user:UserIHM|insertCard() | atm:ATM), • inv3 = (inv3. atm:ATM|requestPassword | user:UserIHM), • inv4 = (inv4. user:UserIHM|enterPassword() | atm:ATM), • inv5 = (inv5. user:UserIHM|cancel() | atm:ATM).
This definition of sequence diagrams is isomorphic to regular expressions (RE) as shown below and will be used in section IV. Indeed, the seq operator in SDs is equivalent to the classical concatenation operator in REs, alt is equivalent to choice operator, and loop is equivalent to the Kleene star operator in REs. The alphabet of the corresponding regular expression is the set of method invocations of the sequence diagram.

Definition 5 (Isomorphism between REs and SDs): The mapping from REs into SDs [•] : RE → SD is defined as follows:

• [S] = S, iff S is a method invocation • [(S 1 + S 2 )] = ([S 1 ] alt [S 2 ]) • [(S 1 • S 2 )] = ([S 1 ] seq [S 2 ]) • [(S) * ] = loop [S]
The set of traces associated with a sequence diagram is defined straightforwardly as the set of traces recognized by the corresponding regular expression. This morphism is also obviously an isomorphism as all the equations are symmetrical.

C. Overview of Our Approach

The proposed approach consists of three steps outlined in Figure 2: the collection of the execution traces from a running system, the generation of a LTS that represents the merge of the input execution traces and finally the extraction of the sequence diagram.

Step 1: Traces Collection: This step consists in observing the interaction of a set of known objects in various scenarios. For each scenario, an execution trace is captured by creating a method invocation for each method call from one object to another. There are multiple strategies to collect execution traces [START_REF] Cornelissen | A systematic survey of program comprehension through dynamic analysis[END_REF]. This can include instrumentation of virtual machines or the use of a customized debugger. In Section V, we present the strategy we used to collect execution traces for Java systems. Step 2: Traces Merging: In the second step of our approach we propose a technique, based on merging Labeled Transition Systems, to merge the traces collected in the previous step. This step is detailed in Section III.

S0 S1 S2 S3 S4 S5 S6 S7 inv1 inv2 inv3 inv4 inv5 inv6 inv7 LTS of Trace 1 LTS of Trace 2 S8 inv8 S9 inv3 S10 S11 S12 S13 S14 inv4 inv5 inv6 inv7 inv8 S0' S1' S2' S3' S4' S5' S6' S7' inv1 inv2 inv3 inv9 inv10 inv11 inv12 S16 S17 S18 inv9 inv11 S15 inv10 inv12
Step 3: Sequence Diagram Extraction: This final step generates a sequence diagram using the results of Step 2. This step is detailed in Section IV.

III. MERGING TRACES

The second step of our approach deals with merging traces. Indeed, as mentioned in the previous section, one of the major challenges to reverse engineering sequence diagrams is to merge the multiple execution traces to identify common and variable method invocations throughout the input traces. To the best of our knowledge, most of existing work [START_REF] Rainer | Javavis: Automatic program visualization with object and sequence diagrams using the java debug interface (JDI)[END_REF]- [START_REF] Taniguchi | Extracting Sequence Diagram from execution trace of Java Program[END_REF] only extracts a sequence diagram from a single execution trace and consequently this challenge of merging traces is not reported. For instance, Briand et al.'s approach only generates what the authors called partial sequence diagrams which depict the method invocations within a specific execution trace [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF].

Independently from the reverse engineering of sequence diagrams, the challenge of merging traces is well identified in the grammar inference domain where several well defined techniques were proposed [START_REF] Cook | Discovering models of software processes from event-based data[END_REF]. The main idea of these techniques is to represent each input trace using a labeled transition system and then define trace merging as LTS merging. However, the grammar inference techniques are often used to infer only LTSes that specify protocols of components. In this section we propose to reuse and adapt one of these grammar inference techniques (the k-tail algorithm [START_REF] Biermann | On the synthesis of finite state machines from samples of their behavior[END_REF]) to merge execution traces in the perspective of extracting sequence diagrams. This includes two steps: Initialization and Merging.

A. Initialization

In the first step, one LTS for each captured execution trace is generated. The LTS that we generate is a variant of classical finite automata where transitions are labeled by method invocations. Figure 4 illustrates two examples of LTSes in which final states are represented by double circled states and the initial state is represented as a full small circle. Below we formally define our LTSes: Definition 6 (LTS): An LTS is a 4-tuple S, T, s 0 , s F , where S is a set of states, T is a finite set of transitions between states in S, s 0 is the initial state, and s F is the set of final states. A transition t ∈ T is a 3-tuple s, inv, s , where s, s ∈ S are the source and destination of the transition respectively, and inv is the method invocation labelling the transition. This transformation from one execution trace to an LTS is straightforward. For each method invocation in the trace, a transition and a state are created in the LTS. The generated LTS will be a sequence of states, and will contain a single final state, which corresponds to the state reached when all method invocations in the trace have proceeded.

B. Merging

In this second step, the LTSes of the different traces are merged to obtain a single LTS that merges the initial traces. This is done by using the k-tail algorithm [START_REF] Biermann | On the synthesis of finite state machines from samples of their behavior[END_REF]. The algorithm starts by initializing a new LTS which has a new common initial state and merges the initial state of all input LTSes.

The k-tail algorithm takes as input the new initial LTS, then, iteratively merges "k-equivalent" states. Two states s1 and s2 are "k-equivalent" if and only if they are defined by the same set of paths of method invocations with length k. Before defining k-equivalence between states, we define the notion of k-paths.

Definition 7 (k-Paths): Given a state s in a LTS M, a set of paths with length k, called k-paths(s), is defined as a set {path 1 , ...path r }, where path i is a sequence of method invocations in M, i.e., path i = st 1 st 2 ...st k such that there exists a sequence of transitions

(s, inv 1 , s 1 )(s 1 , inv 2 , s 2 )...(s k-1 , inv k , s k ) in the LTS M.
The notion of k-equivalence between states is defined as follows:

Definition 8 (k-equivalence): Two states s1 and s2 in the LTS M are k-equivalent if and only if k-paths(s1) = k-paths(s2).

For instance, the states s14 in the LTS of Trace 1 and s3' in the LTS of Trace 2 (see Figure 4) are 2-equivalent because:

2-paths(s14) = 2-paths(s3') = { inv9inv10 }
The k-tail algorithm iteratively identifies sets of kequivalent states, i.e., states with the same k-paths, to be merged. Merging k-equivalent states s1 and s2 for example is realized by removing s1 and adding all transitions entering or exiting s1 to s2. The process of merging k-equivalent states is repeated until there are no more such states. The obtained LTS being an automaton, classical determinization and minimization techniques are applied to obtain a rigorous deterministic finite state machine.

Figure 5 illustrates the LTS obtained from merging LTSes of Figure 4 using the k-tail with k = 2 and after minimization and determinization. Note that for the sake of clarity we labeled method invocations in transitions of the LTS of Figure 5 in the form caller:callee.method. For instance, atm:user.displayMainScreen is equivalent to the method invocation: atm:ATM |displayMainScreen()| user:userIHM.

The LTS obtained at the end of this step is thus an LTS that depicts the behavior specified in the input traces but allows other behaviors. The next step consists in extracting a SD from this LTS. Our approach for this extraction is presented in the next section.

IV. SEQUENCE DIAGRAMS EXTRACTION

This section presents our approach to extract a SD from the LTS generated by the k-tail algorithm presented in the previous section. Our approach consists in reusing the known solutions for the problem of Converting Deterministic Finite Automata to Regular Expressions to obtain a regular expression (RE) that is equivalent to the LTS [START_REF] Kleene | Representation of events in nerve nets and finite automata[END_REF], [START_REF] Neumann | Converting deterministic finite automata to regular expressions[END_REF]. The obtained regular expression is then transformed into a SD by a simple mapping defined in Section II.

Neumann [START_REF] Neumann | Converting deterministic finite automata to regular expressions[END_REF] presents a survey of existing techniques for converting finite automata to RE. We adopted the technique defined by Brzozowski in [START_REF] Brzozowski | Derivatives of regular expressions[END_REF]. This technique is based on the creation of a system of equations of regular expressions with one variable for each state in the LTS. This system is then solved to the variable associated with initial state via straightforward substitution based on the Arden's theorem [START_REF] Arden | Delayed-logic and finite-state machines[END_REF]. The solution for this system of equations is a regular expression. For instance, the regular expression obtained by this method over the LTS of Figure 5 is :

RE LT S f inal = ((inv1•inv2•inv3•inv4•inv5•inv6•inv7• (inv8•inv3•inv4•inv5•inv6•inv7) * inv8•inv3•inv9•inv10•inv11•inv12) + (inv1•inv2•inv3•inv9•inv10•inv11•inv12))
where the invi are the labels of method invocations used in Figure 1.

The obtained RE can be mapped into a SD ( see Definition 5).

The application of our mapping 5 on this regular expression results in the following sequence diagram whose expression is depicted as follows: SD LT S f inal = RE LT S f inal = alt(inv1 seq inv2 seq inv3 seq inv4 seq inv5 seq inv6 seq inv7 seq loop (inv8 seq inv3 seq inv4 seq inv5 seq inv6 seq inv7) seq inv8 seq inv3 seq inv9 seq inv10 seq inv11 seq inv12), (inv1 seq inv2 seq inv3 seq inv9 seq inv10 seq inv11 seq inv12))

The sequence diagram corresponding to the expression SD LT S f inal is illustrated in Figure 6. Analyzing the obtained sequence diagram of Figure 6 shows that combining LTS merging and the mapping of LTS to regular expressions allows us to detect interaction operators. Indeed, in addition to the seq interaction operator, the sequence diagram of Figure 6 illustrates the detection of two other operators: alt and loop. The loop operator is extracted because the initial output traces contain a repetition of method invocations related to the situation where a bad password is entered by users.

V. PRELIMINARY EVALUATION & DISCUSSION

This section presents and discusses our preliminary evaluation of the approach presented in this paper. The two main hypotheses of this section are that (i) the presented approach is implementable as part of a state of the art programming environment; and (ii) it may be used to extract sequence diagrams from a real application.

In order to test the first hypothesis, a prototype implementation of the approach was developed as a chain of Model-to-Model (M2M) transformations based on the Eclipse Modeling Framework (EMF) environment. This prototype is able to observe a real system at runtime and to build a set of execution traces from it. From this set of execution traces it builds a state machine that abstracts the traces and from it a sequence diagram that depicts the interactions among the objects. The second hypothesis was tested by the means of a case study using a medium-sized scientific prototype of a distributed peer-to-peer modeling environment that has been developed independently from the present prototype. Our results show that we could successfully extract sequence diagrams that abstract the traces obtained by observation.

This section is organized as follows: Section V-A de-scribes the prototype and details its architecture and Section V-B uses the prototype to build both behavioral models from the case study application.

A. Prototype Implementation

Our prototype implementation was developed in the Java programming language and contains 97 classes, with a total of 5.164 lines of code 4 . Approximately 50% of the code was automatically generated by Eclipse EMF.

The architecture of this prototype is organized into the 5 components described below.

• Execution Trace Collector. This component is responsible for observing the running system. To be able to perform this observation, this component uses a customized debugger to collect execution traces for Java systems. This component captures the execution traces and builds the related LTSes. The mapping from execution traces to LTSes was implemented as a M2M transformation. • LTS merger. This component takes the LTSes generated by the previous component as input and merges them into a single LTS. This is done using the k-tail algorithm explained in Section III. • Determinizer & Minimizer. We observed that the automaton generated by k-tail is non-deterministic (NFA). Therefore, in order to improve its readability, the present component uses the Graph library JFLAP 4.0 to determinize and minimize it. The output finite state machine (FSM) is the state machine generated by our approach. • Equation System Generator & Simplifier. This component generates a system of equations of regular expressions from the FSM produced by the previous component. A M2M transformation generates an initial system of equations that is simplified until a solution is found. This implementation follows the method of Brzozowski [START_REF] Brzozowski | Derivatives of regular expressions[END_REF]. • Sequence Diagram Generator. Finally, a transformation maps the regular expression that is the solution of the system generated by the last component into a sequence diagram. This mapping was described in Section IV. To visualise sequence diagrams, this component uses the Quick Sequence Diagram Editor (SDEDIT) 5 .

B. Case Study

This section describes the case study that was run with the prototype implementation described in the previous section. A medium-sized research application that has been developed independently from the present prototype was chosen as the system to be observed. It features the Praxis Peer-To-Peer Collaboration Environment6 which contains more than 500 classes and interfaces and approximately 25.000 lines of code.

This application was chosen because it contains a nontrivial set of components and interactions. It consists of a set of plug-ins to the Eclipse IDE that extend it with the possibility of peer-to-peer edition of EMF models. More specifically, this tool focuses on the management of the inconsistencies that may appear in such distributed environment. The inconsistency management is delegated to a SWI-Prolog inference engine. It is then responsible for keeping an up-to-date copy of the model currently being edited, and, under request from the Eclipse plug-ins, deliver an inconsistency report. This component, called SWIPrologBRidge, is therefore one of the core pieces of the Praxis Peer-To-Peer Collaboration Environment.

This component masks the complexity of the communication with the Prolog engine that runs in another virtual machine, and in another system process. That is why, even though the number of possible test cases being very reduced, the obtained sequence diagrams depict the interaction between many different objects.

We separated this case study into two parts. In the first one, we wanted to evaluate the performance of our approach. In order to do that, we defined 8 test cases and stress tested our approach with them. In the second part, we analyzed the obtained sequence diagrams to assess their utility in understanding the dynamic behavior of the application.

1) Performance Evaluation: 8 test cases were constructed in order to represent the most significative cases of utilization of this component. The corresponding execution traces were collected and the corresponding LTS and sequence diagram were constructed automatically by our prototype. The value of k for the k-tail was kept to 2 and the number of execution traces varied from 1 to 8 in each test case. The values of the following variables were recorded: time spent by each component, number of observed objects, number of messages in the sequence diagram and number of states and transitions in the LTS. We also recorded the number of the detected interaction operators. We particularly recorded the number of alternatives (alt) and loops in the obtained sequence diagrams. Figure 7 outlines the results of this experiment.

The time spent in each component was not divided equally. In average, 4% of the time was spent in merging the input LTSes; 81% was spent in the determinization and minimization step and 14% was spent in the equation simplification. The time spent in the transformation of the execution traces into the input LTSes and of the equations into the final sequence diagram were negligible. The time of generation of the behavioral models went from 0.65s in the simplest case to 18.87s in the most complicated one. This shows that the approach is utilizable in the context of a real application.

2) Obtained Sequence Diagrams Evaluation: Figure 8 illustrates the Sequence Diagram obtained from one of the execution test cases. This test case requires the interaction between five objects:

1) The PrologExecutionEngine represents the interface of the Praxis environment with the SWIPrologBridge component.

2) The Query object encapsulates the code necessary to send queries to the Prolog process and get their result.

3) The ProcessHolder encapsulates the SWIProlog process that runs in another process in the operating system. 4) The ReaderThread encapsulates the raw communication with the Prolog inference engine thread, and makes sure that the data read through the Query object is valid. 5) The WindowsValidator encapsulates the validation of the strings returned from the Prolog inference engine. This diagram represents a test case in which a PrologExe-cutionEngine is created and then a set of queries are sent to the SWIPrologBridge. Note that in the produced sequence digram, constructors are displayed as CreateObject() rather than the classical Java's new() invocation. This display is only imposed by the SDEDIT tool that we used to display SDs. Notice that the internal interaction between the objects cannot be deduced from the source code. This lies in the fact that the source code, in particular the Java source code, does not contain any information about the types of the objects used at runtime (like WindowsValidator, which would change in another operating system). The source code does not include a clear description of the interaction between different threads either.

When comparing the produced diagram with the source code of the original application 7 , we notice that the obtained 7 The original source code of the application is not presented here for the sake of brevity. diagram correctly represents the set of traces obtained as input. However, there are some inconsistencies. For example, there is no call to writeP hrase() and readP hrase() before the loop that continually sends queries to the Prolog engine.

This comes from the fact that our approach generalizes a set of extracted traces into a behavioral model. More specifically, this behavioral model is a sequence diagram that is an over-approximation of the input traces. Therefore, the completeness and correctness of the generated sequence diagram w.r.t. the system under analysis is hard to evaluate because it depends on the completeness of the input traces w.r.t. the same system. Even though these imperfections do not hinder the understandability of the diagram, an extension of the present work that is able to combine the present approach with a static analysis in order to rule out these imperfections is envisaged as future work.

VI. RELATED WORK

A complete survey of the reverse engineering of sequence diagrams is presented in [START_REF] Briand | Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software[END_REF]. In the same article, Briand et al. propose an approach to the reverse engineering of UML sequence diagrams for distributed Java applications. While our approach generates a sequence diagram by generalizing a collection of execution traces using the k-tail algorithm, their approach only considers one execution trace. Additionally, they discover interaction operators using source code analysis and manual instrumentation, which is a drawback when the source code is not available.

Different techniques for the reverse engineering of sequence diagrams have been published [START_REF] Rainer | Javavis: Automatic program visualization with object and sequence diagrams using the java debug interface (JDI)[END_REF]- [START_REF] Taniguchi | Extracting Sequence Diagram from execution trace of Java Program[END_REF]. Unlike our work, however, all consider one execution trace without trying to generalize from it and do not support the identification of UML interaction operators (alt, loop,...).

Many approaches for protocol state machine extraction reuse the k-tail algorithm [START_REF] Lorenzoli | Automatic Generation of Software Behavioral Models[END_REF], [START_REF] Reiss | Encoding program executions[END_REF]- [START_REF] Lo | Automatic steering of behavioral model inference[END_REF]. However, the main difference between their use of this algorithm and ours is in the nature of the input traces and consequently in the obtained LTSes. Indeed, while our LTSes used as input of the k-tail show the interaction among the system's objects, the used models in [START_REF] Reiss | Encoding program executions[END_REF]- [START_REF] Xie | Software component protocol inference[END_REF] only show the behavior of a single component through its interaction with a user via its graphical interface. We consider that our present results constitute a further validation of the k-tail family of algorithms in the context of reverse engineering of sequence diagrams.

As underlined by Lo & Khoo in [START_REF] Lo | Quark: Empirical assessment of automaton-based specification miners[END_REF], LTS merging algorithms such as k-tail can generate imprecise and overgeneralized models. This produces many false negative or false positive behaviors. In the future, we plan to investigate the use of the new variants of the k-tail algorithm that avoid such problems of imprecision. We plan in particular to investigate the use of the algorithms of [START_REF] Lorenzoli | Automatic Generation of Software Behavioral Models[END_REF], [START_REF] Lo | Automatic steering of behavioral model inference[END_REF]. Notice that the integration of these new algorithms will only modify the Traces Merging step in our approach.

VII. CONCLUSION AND FUTURE WORK

This paper proposes an approach to the reverse engineering of sequence diagrams from execution traces for object-oriented software. Our approach is completely based on a dynamic analysis. That is a very important point since in some contexts, such as in legacy or in highly secured systems, source code may not be available and some analyses should be carried out anyway without having the source code.

Our approach reuses the well-known k-tail algorithm to extract a generalized labeled transition system from a set of observed execution traces. This LTS is then translated into a sequence diagram by an intermediary mapping into regular expressions. Notice that even though the k-tail algorithm is well known and used for LTS inference, to the best of our knowledge, no other work uses it to extract sequence diagrams.

Beyond offering a systematic and semantically well founded method, our approach 1) detects interaction operators in sequence diagrams, and 2) merges multiple execution traces to obtain a single sequence diagram.

A prototype implementation of our approach was developed as a chain of Model-to-Model (M2M) transformations using the Eclipse EMF Environment. Notice that we used a customized debugger to easily collect execution traces, but that we do not depend on it directly. The same traces could be obtained by other strategies such as instrumenting the virtual machine, for example. This prototype was validated on a case study using a real application that has been developed independently from the present work. Our results show that the approach performs reasonably when it comes to analyzing real code and that the generated diagrams (although not perfect, because they are obtained from input traces without seeing the code) are helpful in the allowing an engineer understand the behavior of the system.

Our future work spans three main directions: 1) improving our generalization power by integrating other algorithms such as [START_REF] Lorenzoli | Automatic Generation of Software Behavioral Models[END_REF], [START_REF] Lo | Automatic steering of behavioral model inference[END_REF], [START_REF] Walkinshaw | Reverse engineering state machines by interactive grammar inference[END_REF]. Notice that this only affects the second step in the approach; 2) considering other UML interaction operators such as the par operator [START_REF] Omg | Unified Modeling Language: Superstructure -Version 2[END_REF] which is mandatory to support multi-threaded systems; 3) evaluating our approach on bigger object-oriented systems to assess its scalability and usability in more complicated cases. In addition, we aim at evaluating the definition of equivalence of objects that were used to implement our merging algorithm. For instance, we considered that two objects are equivalent if they are instances of the same class and were created with the same values, but this definition should be evaluated on larger case studies.

ACKNOWLEDGMENT

This work was partly funded by the ANR Project Proteus.

Figure 2 .Figure 1 .

 21 Figure 2. Overview of our approach.

Figure 3 .

 3 Figure 3. Sequence Diagram of checking account in the ATM example.

Figure 4 .

 4 Figure 4. LTSes generated from traces of Figure 1.

Figure 5 .

 5 Figure 5. The extracted final LTS from the traces of Figure 1.

Figure 6 .

 6 Figure 6. The extracted sequence diagram.

Figure 8 .

 8 Figure 8. The extracted Sequence Diagram for the Praxis Peer-To-Peer Collaboration Environment.

  1 • callee is the callee object, expressed in the form "object : class" A method invocation is displayed in the trace as: label. caller | method | callee. Labels are only used to simplify further references in the rest of the text.

In this paper we do not consider method parameters in our invocations.

In this paper we do not consider method parameters in our invocations. However we only deal with parameters of constructors, i.e., the new() method for Java systems in the perspective of defining equivalence between objects.

Note that, this interpretation is correct because the seq operator specifies a weak sequential which is different from the strict sequential composition[START_REF] Omg | Unified Modeling Language: Superstructure -Version 2[END_REF].

This includes the JFLAP 4.0 Graph library that was used to minimize and determinize LTSes.

http://sdedit.sourceforge.net/

Available at http://meta.lip6.fr/?page_id=17.


Marco Liuni
email: marco.liuni@ircam.fr

Axel Röbel

Romito Marco
email: marco.romito@math.unifi.it

Xavier Rodet
email: xavier.rodet@ircam.fr

Axel Röebel
email: axel.roebel@ircam.fr

Marco Romito

A REDUCED MULTIPLE GABOR FRAME FOR LOCAL TIME ADAPTATION OF THE SPECTROGRAM

HAL is

INTRODUCTION

The quality of analysis and synthesis processes based on timefrequency transforms is highly affected by the frames used for the decomposition and the reconstruction of the signal. Traditional methods based on single frames of atomic functions have important limits: a Gabor frame imposes a fixed resolution over all the time-frequency plane, while a wavelet frame gives a strictly determined variation of the resolution: moreover, the user is frequently asked to define himself the analysis window features, which is not always a simple task even for normally experienced users. The resolution of such analysis methods is linked to the time and frequency concentration of the basic functions involved in the decomposition. Frame Theory ( [START_REF] Gröchenig | Foundations of Time-Frequency Analysis[END_REF], [START_REF] Christensen | An Introduction To Frames And Riesz Bases[END_REF], [START_REF] Mallat | A wavelet tour on signal processing[END_REF]) extends the concept of orthonormal basis in a Hilbert space H: in our domain, it gives a unified model for the description of decomposing systems based on atomic functions. The set {φγ}γ∈Γ is a frame for H if there exist two positive non zero constants A and B, called frame bounds, such that for all f ∈ H,

A f 2 ≤ γ∈Γ | f, φγ | 2 ≤ B f 2 .
(1) * This work is supported by grants from Region Ile-de-France

The time-frequency concentration of an atom φγ in a frame can be represented through its associated Heisenberg box: it is a rectangle drawn in the time-frequency plane whose dimensions are linked respectively to the time spread of a function and to the frequency spread of its Fourier Transform. In the Short Time Fourier Transform, the boxes associated to the transpositions of the window function g have fixed dimensions in every area of the timefrequency plane: the resolution is the same for all the components of the signal. In the Wavelet Transform, lower frequency components are represented with a higher time resolution, while a higher frequency resolution is given for the higher frequency ones. This limits are not motivated when analyzing a sound without an a priori knowledge of its features, as the best resolution tradeoff is neither unique nor depending only on a single variable. It is therefore useful to search for adaptive methods of sound analysis and synthesis, and for algorithms whose operations are designed to change locally according to the analyzed signal features. Given l ∈ R + , the analysis resolution can be globally modified with a scaling operation

g l (t) = 1 √ l g t l , (2)
which has the effect of changing the ratio between the edges of the Heisenberg box associated to g while preserving its area: this means that the global time-frequency resolution is modified by privileging concentration in one dimension to the detriment of the other. The idea which has lead to the definition of multiple Gabor frames ( [START_REF] Dörfler | Gabor Analysis for a Class of Signals called Music[END_REF]) is to consider a decomposing system where all these different resolution tradeoffs coexist, providing a more detailed description of the signal. The drawback is the introduction of a high redundancy which lowers the readability of the representation: therefore methods for appropriate reductions of these multiple frames are needed, typically using sparsity criteria. A promising approach ( [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF]) takes into account Rényi entropies, a generalization of the Shannon entropy: given a unit-energy signal f ∈ L 2 (R) and a time-frequency representation Φ f (u, ξ) of f the Rényi entropy of the representation is defined for an order α > 0 as follows

Hα(Φ f ) = 1 1 -α log 2 Φ α f (u, ξ)dudξ . (3)
In this paper, the time-frequency representation Φ f (u, ξ) considered is the spectrogram, as detailed in the next section. The application to our problem is related to the concept that minimizing the complexity or information over a set of time-frequency representations of a same signal is equivalent to maximizing the concentration and peakiness of the analysis, thus selecting the best resolution tradeoff: a sparsity measure can consequently be defined through an information measure. Methods inspired by this approach have shown to give interesting results both analytically and numerically ( [START_REF] Jaillet | Représentation et traitement temps-fréquence des signaux audionumériques pour des applications de design sonore[END_REF]).

The proposed method of local time adaptation improves on the analysis multi-frame definition: the user can specify a finite arbitrary set of positive scaling factors L ⊂ R + corresponding to the resolutions available; then the algorithm composes different frames {g l n,k } (n,k)∈Z 2 with l ∈ L and g l as in (2), and a multiple Gabor frame is obtained as the union of all the given frames. The main improvement in comparison with [START_REF] Lukin | Adaptive Time-Frequency Resolution for Analysis and Processing of Audio[END_REF] is that we are not obliged to keep the same hop size within the individual frames analyses, thus avoiding unnecessary short hops for larger windows: our method employs frames which share the same redundancy, so that every analysis has the same overlap, with a significant gain in computational cost. The limit of our approach in comparison with [START_REF] Jaillet | Représentation et traitement temps-fréquence des signaux audionumériques pour des applications de design sonore[END_REF] is that we apply the entropy evaluation on the whole frequency dimension, thus providing analyses which are adapted only in the time dimension. On the other hand, the reduced multi-frame obtained with our method allows a perfect reconstruction of the signal which is not provided by [START_REF] Jaillet | Représentation et traitement temps-fréquence des signaux audionumériques pour des applications de design sonore[END_REF]: in our scheme, for any analysis segment a single original frame is retained; therefore, a re-synthesis technique can be defined as a straightforward extension of the least square error estimation from the modified STFT presented in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF]. So our method can easily be used to provide common time-frequency processing frameworks with an adaptive analysis technique.

ENTROPY EVALUATION OF A SPECTROGRAM

We will now describe the application of the entropy sparsity measure on the spectrogram distribution. We will focus on discretized spectrograms, as dealing with digital signal processing requires to work with sampled signals and distributions, even if for the most part the results can be extended to the continuous case. A Gabor frame is obtained by time shifting and frequency transposing a window function g according to a regular lattice. Given a time step a and a frequency step b we write {un} n∈Z = an and {ξ k } k∈Z = bk; these two sequences generate the nodes of the time-frequency lattice for the frame {g n,k } (n,k)∈Z 2 defined as

g n,k (t) = g(t -un)e 2πiξ k t ; (4)
the nodes are the centers of the Heisenberg boxes associated to the windows in the frame. The decomposition of a function f ∈ L 2 (R) in a Gabor frame is simply a sampling of its STFT according to such a lattice,

Sf [n, k] = f, g n,k = f (t)g(t -un)e -2πiξ k t dt , (5)
and the squared modulus of this decomposition is the discretized spectrogram,

PS f [n, k] = |Sf [n, k]| 2 . ( 6
)
Given a discrete spectrogram with time step a and frequency step b as in [START_REF] Jaillet | Représentation et traitement temps-fréquence des signaux audionumériques pour des applications de design sonore[END_REF], we look for an evaluation of its entropy over a certain rectangle of the time-frequency plane

[t1, t2] × [ν1, ν2] ⊆ R 2 .
The rectangle identifies a sequence of points

G ⊆ Z 2 where G = {(n, k) ∈ Z 2 : t1 ≤ na ≤ t2, ν1 ≤ kb ≤ ν2}.
Through an appropriate normalization we obtain the sequence

PS G f [n, k] = PS f [n, k] [n ′ ,k ′ ]∈G PS f [n ′ , k ′ ] , (7)
with [n, k] ∈ G, which can be seen as a discrete probability density. As a discretization of the original continuous spectrogram, every sample in PS G f is related to a time-frequency region of area ab; we thus obtain the Rényi entropy measure for [START_REF] Lukin | Adaptive Time-Frequency Resolution for Analysis and Processing of Audio[END_REF] directly from (3),

Hα(PS G f ) = 1 1 -α log 2 [n,k]∈G (PS G f [n, k]) α + log 2 (ab) . ( 8
)
General properties of Rényi entropies can be found in [START_REF] Rényi | On Measures of Entropy and Information[END_REF], [START_REF] Schlögl | Thermodynamics of chaotic systems[END_REF] and [START_REF] Zyczkowski | Rényi Extrapolation of Shannon Entropy[END_REF]; we recall in particular those which have a closer relation with our problem. It is easy to show that for every finite discrete probability density P the entropy Hα(P ) tends to coincide with the Shannon entropy of P as the order α tends to one. Moreover, Hα(P ) is a non increasing function of α, so

α1 < α2 ⇒ Hα 1 (P ) ≥ Hα 2 (P ) . (9)
As we are working with finite discrete densities we can also consider the case α = 0 which is simply the logarithm of the number of elements in P ; as a consequence H0(P ) ≥ Hα(P ) for every admissible order α.

A third basic fact is that for every order α the Rényi entropy Hα is maximum when P is uniformly distributed, while it is minimum and equal to zero when P has a single non-zero value. Given a generic P and its entropy Hα(P ) for a certain order α, we have that for any

β ≥ α α -1 α Hα(P ) ≤ β -1 β H β (P ) . (10)
All of these results give useful informations on the values of different measures on a single density P as in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF], while the relations between the entropies of two different densities P and Q are in general hard to determine analytically; in our problem, P and Q are two spectrograms of a same signal in a same time-frequency area, based on two window functions with different scaling as in [START_REF] Christensen | An Introduction To Frames And Riesz Bases[END_REF].

When the spectrogram of a signal does not depend on time it is easier to find such a relation, and it turns out to be the one expected: let PS G s be the sampled spectrogram of a sinusoid s over the region G with a window function h of compact support; then PS G s is simply a translation in the frequency domain of ĥ, the Fourier transform of the window, and it is therefore time-independent. We choose a bounded set L of admissible scaling factors, so that the discretized support of the scaled windows h l still remains inside G for any l ∈ L. It is not hard to prove that the entropy of a spectrogram taken with such a scaled version of h is given by

Hα(PS G sl ) = Hα(PS G s ) -log 2 l . (11)
The sparsity measure we are using looks for the window which minimizes the entropy measure: we deduce from [START_REF] Zyczkowski | Rényi Extrapolation of Shannon Entropy[END_REF] that it is the one obtained with the largest scaling factor available, so with the largest time-support. This is coherent with our expectation as stationary signals, such as sinusoids, are best analyzed with a high frequency resolution, because time-independency allows a small time resolution. Moreover, this is true for any order α used for the entropy calculus. Symmetric considerations apply whenever the spectrogram of a signal does not depend on frequency, as for impulses.

A last remark regards the dependency of (8) on the time and frequency step a and b used for the discretization of the spectrogram. When considering signals as finite vectors, a signal and its Fourier Transform have the same length. Therefore in the STFT the window length determines the number frequency points, while the sampling rate sets frequency values: the definition of b is thus implicit in the window choice. Actually, the FFT algorithm allows to ask a number of frequency points larger than the signal length: further frequency values are obtained as an interpolation between the original ones by properly adding zero values to the signal. If the sampling rate is fix, such a procedure establishes smaller b as a consequence of a larger number of frequency points. We have numerically verified that such a variation of b has no impact on the entropy calculus, so that the FFT size can be set according to implementation needs. Regarding the time step a, we are working on the analytical demonstration of a largely verified evidence: as long as the decomposing system is a frame the entropy measure is invariant to redundancy variation, so the choice of a can be ruled by considerations on the invertibility of the decomposing frame without losing coherence between the information measure of the different analyses. This is a key point, as it states that the sparsity measure obtained allows a total independence between the hop sizes of the different analyses: with the implementation of proper structures to handle multi-hop STFTs we have obtained a more efficient algorithm in comparison with the ones imposing a fixed hop size, as [START_REF] Lukin | Adaptive Time-Frequency Resolution for Analysis and Processing of Audio[END_REF].

ALGORITHM AND EXAMPLES

We now summarize the main operations of the algorithm we have developed providing examples of its application. For spectrograms calculation we have used a Hanning window

h(t) = cos 2 (πt)χ [-1 2 , 1 2 ] , (12)
with χ the indicator function of the specified interval, but it is obviously possible to generalize the results thus obtained to the entire class of compactly supported window functions. We create a multiple Gabor frame as in (4) using as mother functions some scaled version of h, obtained as in (2) with a finite set of positive real scaling factors L. Different spectrograms of segments of the signal are calculated with each one of the above frames: the length of the analysis segment and the overlap between two consecutive segments are given as parameters.

The different frames composing the multi-frame have the same frequency step b but different time steps {a l : l ∈ L}: the smallest and largest window sizes are given as parameters together with |L|, the number of different windows composing the multi-frame, and the global overlap needed for the analyses. The algorithm fixes the intermediate sizes so that for each signal segment the different frames have the same overlap between consecutive windows, and so the same redundancy. This generates an irregular time disposition of the multi-frame elements in each signal segment, as illustrated in figure 1. Such a disposition causes a different influence of the boundary parts of the signal on the different frames analyses: the beginning and the end of the signal segment have a higher energy when windowed in the smaller frames. This is avoided with a preliminary weighting: the beginning and the end of each signal segment are windowed respectively with the first and second half of the largest analysis window. Such a weighting does not concern the decomposition for re-synthesis purpose, but only the analyses used for entropy evaluations. For each signal segment we calculate the entropy of every spectrogram as in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF], where G is the rectangle with the time segment analyzed as horizontal dimension and the whole frequency lattice as vertical. The sparsest local analysis is defined to be the one with minimum Rényi entropy: the best window is thus defined consequently. Adaptation is obtained over the time dimension as for every signal segment the selected analysis involve the whole frequency dimension. An interpolation is performed over the overlapping zones to avoid abrupt discontinuities in the tradeoff of the resolutions.

The time adapted analysis of the global signal is finally realized by opportunely assembling the slices of local sparsest analyses obtained with the selected windows.

In figure 3 we give a first example of an adaptive analysis performed by our algorithm with eight Hanning windows of different sizes on a real instrumental sound, a B4 note played by a marimba: this sound combines the need for a good time resolution at the moment of the percussion, with that of a good frequency resolution on the harmonic resonance of the instrument. This is fully provided by the algorithm, as shown in the adapted spectrogram at the bottom of figure 3. Moreover, we see that the pre-echo of the analysis at the bottom of figure 2 is completely removed in the adapted spectrogram.

In figure 5 we give a second example with a synthetic sound, a sinusoid with sinusoidal frequency modulation: as figure 4 shows, a small window is best adapted where the frequency variation is fast compared to the window length; on the other hand, the largest window is better where the signal is almost stationary. The re-synthesis method introduced in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF] gives a perfect reconstruction of the signal as a weighted expansion of the coefficients of its STFT in the original analysis frame. Let S f [n, k] be the STFT of a signal f with window function h and time step a; fixing n, through an iFFT we have a windowed segment of f

f h (n, l) = h(na -l)f (l) , (13)
whose time location depends on n. An immediate perfect reconstruction of f is given by

f (l) = +∞ n=-∞ h(na -l)f h (n, l) +∞ n=-∞ h 2 (na -l) . (14)
We extend the same technique using a variable window h and time step a according to the composition of the reduced multi-frame, obtaining a perfect reconstruction as well. The interest of ( 14) is that the given distribution needs not to be the STFT of a signal: for example, a transformation S * [n, k] of the STFT of a signal could be considered. In this case, (14) gives the signal whose STFT has minimal least squares error with S * [n, k].

The theoretical existence and the mathematical definition of the canonical dual frame for reduced multi-frames like the one we employ has recently been provided in [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF]: the analysis and resynthesis framework is thus entirely defined within the Gabor theory, but no automatic adaptation is employed. We are at present working on the interesting analogies between the two approaches, to establish a unified interpretation and develop further extensions.

CONCLUSIONS

We have presented an algorithm for time-adaptation of the spectrogram resolution, which can be easily integrated in existent framework for analysis, transformation and re-synthesis of an audio signal: the adaptation is locally obtained through an entropy minimization within a finite set of resolutions, which can be defined by the user or left as default. The user can also specify the time duration and overlap of the analysis segments where entropy minimization is performed, to privilege more or less discontinuous adapted analyses. Future improvements of this method will concern the spectrogram adaptation in both time and frequency dimensions: this will provide a decomposition of the signal in several layers of analysis frames, thus requiring an extension of the proposed technique for re-synthesis.

window length (smps)

Figure 1 :

 1 Figure 1: An analysis segment: time locations of the Heisenberg boxes associated to the multi-frame used in our algorithm.

Figure 2 :

 2 Figure 2: Two different spectrograms of a B4 note played by a marimba, with Hanning windows of sizes 512 (top) and 4096 (bottom) samples.

Figure 3 :

 3 Figure 3: Example of an adaptive analysis performed by our algorithm with eight Hanning windows of different sizes from 512 to 4096 samples, on a B4 note played by a marimba sampled at 44.1kHz: on top, the best window chosen as a function of time; at the bottom, the adaptive spectrogram. The entropy order is α = 0.7 and each analysis segment contains four frames of the largest window analysis with a two-frames overlap between consequent segments.

Figure 4 :

 4 Figure 4: Two different spectrograms of a sinusoid with sinusoidal frequency modulation, with Hanning windows of sizes 512 (top) and 4096 (bottom) samples.

Figure 5 :

 5 Figure 5: Example of an adaptive analysis performed by our algorithm with eight Hanning windows of different sizes from 512 to 4096 samples, on a sinusoid with sinusoidal frequency modulation synthesized at 44.1 kHz: on top, the best window chosen as a function of time; at the bottom, the adaptive spectrogram. The entropy order is α = 0.7 and each analysis segment contains four frames of the largest window analysis with a three-frames overlap between consequent segments.