Marco Liuni
email: marco.liuni@ircam.fr

Balazs Peter
email: peter.balazs@oeaw.ac.at

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

Peter Balazs

SOUND ANALYSIS AND SYNTHESIS ADAPTIVE IN TIME AND TWO FREQUENCY BANDS

HAL is a multi-disciplinary

INTRODUCTION

Traditional analysis methods based on single sets of atomic functions offer limited possibilities concerning the variation of the resolution. Moreover, the optimal analysis parameters are often set depending on an a-priori knowledge of the signal characteristics. Analyses with a non-optimal resolution result in a blurring or sometimes even a loss of information about the original signal, which affects every kind of later treatment: visual representation, features extraction and processing among others. This motivates the research for adaptive methods, conducted at present in both the signal processing and the applied mathematics communities: they lead to the possibility of analyses whose resolution locally change according to the signal features.

We present an algorithm with local automatic adaptation of time-frequency resolution. In particular, we use nonstationary Gabor frames [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF] of windows with compact time supports, being able to adapt the analysis window depending on its time or frequency location. For compactly supported windows fast reconstruction algorithms are possible, see [START_REF] Jaillet | Nonstationary Gabor Frames[END_REF][START_REF] Balazs | Theory, Implementation and Applications of Nonstationary Gabor Frames[END_REF][START_REF] Søndergaard | The Linear Time Frequency Analysis Toolbox[END_REF]: all along the paper we will in-dicate as fast a class of algorithms whose principal computational cost is due to the Fourier transform of the signal.

In the present paper we want to go a step beyond and adapt the window in time and frequency. This case has been detailed in [START_REF] Dörfler | Quilted frames -a new concept for adaptive representation[END_REF] among others. This can be possible, and frame theory [START_REF] Christensen | An Introduction To Frames And Riesz Bases[END_REF] would help in providing perfect reconstruction synthesis methods (if no information is lost). However, this is a typical case where the calculation of the dual frame for the signal reconstruction cannot in general be achieved with a fast algorithm: thus a choice must be done between a slow analysis/re-synthesis method guaranteeing perfect reconstruction and a fast one giving an approximation with a certain error. There are, at least, two interesting approaches to obtain fast algorithms:

• filter bank: the signal is first filtered with an invertible bank of P pass band filters, to obtain P different band limited signals; for each of these bands a different nonstationary Gabor frame {g p k,l } of windows with compact time support is used, with g p k the time-dependent window function. The other members of the frame are time-frequency shifts of g p k ,

g p k,l = g p k (t -a p k )e 2πib p k lt , (1)
where k, l ∈ Z and a p k , b p k are the time location and frequency step associated to the p-th frame at the time index k. We will write NGF to indicate a nonstationary Gabor frame in the time case, and we will always assume to be in the painless case [START_REF] Grossmann | Painless nonorthogonal expansions[END_REF]. Each band-limited signal is perfectly reconstructed with an expansion of the analysis coefficients in the dual frame { g k,l p }. Note that by this notation we denote the dual frame for a fixed p. By appropriately combining the reconstructed bands we obtain a perfect reconstruction of the original signal. An important remark is that the reconstruction at every time location is perfect as long as all the frequency coefficients within all the P analyses are used. On the other hand, for every analysis we are interested in considering only the frequency coefficients corresponding to the considered band, thus introducing a reconstruction error.

• analysis -weighting: the signal is first analyzed with P NGFs {g p k,l } of windows with compact time support . Each analysis is associated to a certain frequency band, and its coefficients are weighted to match this association. We look for a reconstruction formula to minimize the reconstruction error when expanding the weighted coefficients within the union of the P individual dual frames ∪ P p=1 { g k,l p }.

We focus here on the second approach, in the basic case of two bands; so we split the frequency dimension into high and low frequencies, with P = 2. We provide the algorithm for an automatic adaptation routine: in each frequency band, the best resolution is defined through the optimization of a sparsity measure deduced from the class of Rényi entropies [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF]. As for the filter bank approach, the results detailed in [START_REF] Matusiak | Sub-Nyquist sampling of short pulses: Part i[END_REF] indicate a useful solution: they give an exact upper bound of the reconstruction error when reconstructing a compactly supported and essentially band-limited signal from a certain subset of its analysis coefficients within a Gabor frame.

In the first section, the analysis-weighting method is treated with an extension of the weighted Gabor frames approach [START_REF] Balazs | Weighted and controlled frames: mutual relastionships and first numerical properties[END_REF], which will give us a closed reconstruction formula. The second section is dedicated to the sparsity measures we use for the automatic adaptation, with an insight on how weighting techniques of the analysis coefficients can lead to measures with specific features. We then close the paper with some examples and an overview on the perspectives of our research.

RECONSTRUCTION FROM WEIGHTED FRAMES

Let P ∈ N and {g p k,l } be different NGFs, p = 1, . . . , P , where k and l are the time and frequency location, respectively. We will consider weight functions 0 ≤ w p (ν) ≤ ∞: for every p, they only depend on the frequency location. The idea is to smoothly set to zero the coefficients not belonging to the frequency portion which the p-th analysis has been assigned to; in this way, every analysis will just contribute to the reconstruction of the signal portion of its pertinence, so high or low frequencies respectively when P = 2. For each NGF {g p k,l } we write c p k,l = w p (b p k l) f, g p k,l to indicate the weighted analysis coefficients, and we consider the following reconstruction formula:

f = F -1   1 p(ν) F   P p=1 k,l r(p, k, l)     , (2)
where p(ν) = ♯{p : w p (ν) ≥ ǫ} and for every

ǫ > 0, r(p, k, l) is 0 if w p (b p k l) < ǫ, else r(p, k, l) = w p (b p k l) f, g p k,l 1 w p (b p k l) g k,l p . (3)
We see that non-zero weights cancel each other: this reconstruction formula still makes sense, as the goal is exactly to find a reconstruction as an expansion of the c p k,l .

We give now an interpretation of the introduced formula. If w p is a semi-normalized sequence for each p, that is there exist constants mp and np such that 0 < mp ≤ w p (b p k l) ≤ np and ǫ ≤ mp ∀p, then p(ν) = p and the equation (2) becomes

f = 1 P P p=1 k,l w p (b p k l) f, g p k,l 1 w p (b p k l) g k,l p = f . (4)
This is related to the concept of weighted frames detailed in [START_REF] Balazs | Weighted and controlled frames: mutual relastionships and first numerical properties[END_REF], as in the hypothesis of semi-normalization the sequence w p (b p k l)g p k,l is a frame with

1 w p (b p k l) g k,l
p as one of its dual. For weights which are not bounded from below, but still non-zero, the reconstruction still works: the sequences w p (b p k l) • g p k,l are not frames anymore (for each p), but complete Bessel sequences (also known as upper semi-frames [START_REF] Antoine | Frames and semi-frames[END_REF]). This reconstruction can be unstable, though.

In our case, these hypotheses are not verified, as we need to set to zero a certain subset of the coefficients within both of the analyses; thus the equation (2) will in general give an approximation of f . In section 4.2 we give an example of reconstruction following this approach, evaluating the reconstruction error; further theoretical and numerical examinations should be realized, as we are interested to find an upper bound for the error depending on:

• the signal spectral features at frequencies ν where p(ν) > 1 ;

• the features of the w p sequences and the p(ν) function.

A first natural choice for the weights w p is a binary mask; first because this is the worst case in terms of reconstruction error, as we are multiplying in the frequency domain with a rectangular window before performing an inverse Fourier transform. Thus the analysis of the error with a binary masking establish a bound to the error obtained with a smoother mask. Moreover, with a binary mask the reconstruction formula takes the very simple form detailed in equation ( 6), allowing a direct implementation derived from the general full band algorithm. So we consider P = 2 and ωc a certain cut value, then

w 1 (ν) = 1 if ν ≤ ωc 0 if ν > ωc (5)
and w 2 (ν) = 1-w 1 (ν). In this case p(ν) = 1 for every frequency ν and the equation ( 2) becomes

f = b p k l≤ωc f, g 1 k,l g k,l 1 + b p k l>ωc f, g 2 k,l g k,l 2 . ( 6
)
The reconstruction error in this case will in general be large at frequencies corresponding to coefficients close to the cut value ωc; we envisage that a way to reduce this error is to allow the w p weights to have a smooth overlap; this results in more coefficients form different analyses contributing to the reconstruction of a same portion of signal, thus weakening their interpretation.

RÉNYI ENTROPY EVALUATION OF WEIGHTED SPECTROGRAMS

The representation we take into account is the spectrogram of a signal f : it is the squared modulus of the Short-Time Fourier Transform (STFT) of f with window g, which is defined by

Vgf (u, ξ) = f (t)g(t -u)e -2πiξt dt , (7)
and so the spectrogram is

PS f (t, ω) = |Vgf (t, ω)| 2 . Given a Ga- bor frame {g k,l } we obtain a sampling of the spectrogram coeffi- cients considering z k,l = | f, g k,l | 2 .
With an appropriate normalization, both the continuous and sampled spectrogram can be interpreted as probability densities. The idea to use Rényi entropies as sparsity measures for time-frequency distributions has been introduced in [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF]: 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 , 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 (t, ω) R PS f (t ′ , ω ′ )dt ′ dω ′ α dtdω , (8)
where R ⊆ R 2 and we omit its indication if equality holds. Given a discrete spectrogram obtained through the Gabor frame {g k,l }, we consider R as a rectangle of the time-

frequency plane R = [t1, t2] × [ν1, ν2] ⊆ R 2 .
It identifies a sequence of points G on the sampling grid defined by the frame. As a discretization of the original continuous spectrogram, every sample |z k,l | 2 is related to a time-frequency region of area ab, where a and b are respectively the time and frequency steps; we thus obtain the discrete Rényi entropy measure directly from ( 8),

H G α [PS f ] = 1 1 -α log 2 k,l∈G z k,l [k ′ ,l ′ ]∈G z k ′ ,l ′ α +log 2 (ab) . (9)
We consider now another weight function 0 ≤ w(k, l) ≤ ∞; instead of weighting the STFT coefficients f, g k,l as we did in Section 2, we weight here the discrete spectrogram obtaining a new distribution z * k,l = w(k, l)z k,l which is not necessarily the spectrogram of a signal: nevertheless, by the definition of w(k, l), its Rényi entropy can still be evaluated from [START_REF] Balazs | Weighted and controlled frames: mutual relastionships and first numerical properties[END_REF]. This value gives an information of the concentration of the distribution within the time-frequency area emphasized by the specific weight function: as we show in section 4.1, this can be useful for the customization of the adaptation procedure.

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. As α tends to one this measure converges to the Shannon entropy, which is therefore included in this larger class. 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]; in particular, given P a probability density, Hα(P ) is a non increasing function of α, so α1 < α2 ⇒ Hα 1 (P ) ≥ Hα 2 (P ) . Moreover, 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. 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 α. As long as we can give an interpretation to the α parameter, this class of measures offers a largely more detailed information about the time-frequency representation of the signal.

Adaptive procedure

We choose a finite set S of admissible scaling factors, and realize different scaled version of a window g,

g s (t) = 1 √ s g t s , (10)
so that the discretized temporal support of the scaled windows g s still remains inside G for any s ∈ S. In our case, G is a rectangle with the time segment analyzed as horizontal dimension and the whole frequency lattice as vertical: at each step of our algorithm, this rectangle is shifted forward in time with a certain overlap with the previous position. By fixing an α, the sparsest local analysis is defined to be the one with minimum Rényi entropy: thus the optimization is performed on the scaling factor s, and the best window is defined consequently, with a similar approach to the one developed in [START_REF] Jaillet | Time-frequency jigsaw puzzle: adaptive and multilayered Gabor expansions[END_REF]. With the weight functions introduced above, we are also able to limit the frequency range of the rectangle G at each time location: adaptation is thus obtained over the time dimension for each weighted spectrogram, so in our case for each frequency band enhanced. An interpolation is performed over the overlapping zones to avoid abrupt discontinuities in the tradeoff of the resolutions: in the examples given in section 4, the spectrogram segment for the entropy evaluation includes four spectrogram frames of the largest window, and the overlapping zone corresponds to three frames of the largest window. The temporal sizes of the segment and the overlap are deduced accordingly.

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

Biasing spectral coefficients through the α parameter

The α parameter in equation ( 8) introduces a biasing on the spectral coefficients; to have a qualitative description of this biasing, we first 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 DM , 1 ≤ M ≤ N such that

DM [k] = D[k] if k ≤ M D[k] 20 if k > M (11)
and then normalize to obtain a unitary sum. We then apply Rényi entropy measures with α varying between 0 and 3: these are the values that we use to adopt for music signals. As we see from figure 1, there is a relation between the number of large coefficients M and the slope of the entropy curves for the different values of α. For α = 0, H0[DM ] 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, selects 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.

The second example we consider shows that the just mentioned 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; with an extremely small α, the best window selected could vary without a reliable relation with spectral concentration, depending on the noise level within the sound. We illustrate how noise has to be taken in account when tuning the α parameter by means of another model of spectrogram: taking the same vector D considered previously, and two integers 1 ≤ Npart, 1 ≤ Rpart, we define DL like follows:

DL[k] =          1 if k = 1 D[k] Rpart if 1 < k ≤ Npart D[k] R noise if k > Npart . ( 12
)
where Rnoise = Rpart L , L ∈ [ 1 16 , 1]; then we normalize to obtain a unitary sum. This vectors are a simplified model of the spectrograms of a signal whose coefficients correspond to one main peak, Npart partials with amplitude reduced by Rpart and some noise whose amplitude varies, proportionally to the L parameter, from a negligible level to the one of the partials. Applying Rényi entropy measures with α varying between 0 and 3, we obtain the figure 2, which shows the impact of the noise level L on the evaluations with different values of α. The increment of L corresponds to a strengthening of the noise coefficients, causing the rise of the entropy values for any α. The key point is the observation of how they rise, depending on the α value: the convexity of the surface in figure 2 increases as α becomes larger, and it describes the impact of the noise level on the evaluation; the stronger convexity when α is around 3 denotes an higher robustness, as the noise level needs to be high to determine a significant entropy variation. Our tests show that, as a drawback, in this way we lower the sensitivity of the evaluation to the partials, and the measure keeps almost the same profile for every Rpart > 1.

On the other hand, when α tends to 0 the entropy growth is almost linear in L, showing the significant impact of noise on the evaluation, as well as a finer response to the variation of the partials amplitude. As a consequence, the tuning of the α parameter has to be performed according to the desired tradeoff between the sensitivity of the measure to the weak signal components to be observed, and the robustness to noise. In our experimental experience, the value of 0.7 is appropriate for both speech and music signals.

ALGORITHMS AND EXAMPLES

We give here two examples of the methods described above: the first shows an application of two different weights on the spectrogram of a given sound, which determines two different choices for the optimal resolutions; the second is a reconstruction with the algorithm detailed in Section 2.

Adaptation with Different Masks

We can privilege a certain subset of the analysis coefficients to drive the adaptation routine, instead of considering them all with the same importance. For example, the adaptation within the p-th band could be determined from the coefficients laying at a certain small distance from the band central frequency.

Figures 3 and4 are realized with an improved version of the algorithm described in [START_REF] Röbel | A reduced multiple Gabor frame for local time adaptation of the spectrogram[END_REF], which allows for a weighting of the analysis coefficients which concerns only the adaptation routine, and not the analysis and re-synthesis. Thus, we obtain different adapted analyses depending on the frequency area we wish to privilege, still preserving perfect reconstruction: the sound we analyze is a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54. We use two different complementary binary masks, the first setting to zero the spectrogram coefficients corresponding to frequencies higher than 300Hz, the second doing the opposite. As we can see in Figure 3, with the first mask we obtain an analysis where the largest window is privileged; this is the best frequency resolution for the bass guitar sound, which is prominent in the considered band. The only points where shorter windows are chosen correspond to strong transients, as bass or voice attacks, where the time precision is enhanced. With the second mask, low frequencies are ignored in the adaptation step, and as a consequence we obtain a different optimal analysis: the smallest window is generally selected, yielding an higher time resolution which is best adapted to the percussive sounds; moreover, we see that the largest window is chosen corresponding to the presence of the singing voice, whose higher harmonics belong to the considered band and determine a better frequency resolution to be privileged. In both cases we calculate the difference between the signal reconstructed and the original one; we use a 16 bit audio file, whose amplitude is represented in the range [-1, 1] with double precision: the maximum absolute value of the differences between corresponding time samples, as well as the root mean square error over the entire signal, are both of order 10 -16 .

Analysis-Weighting Example

We show here an example of the approximation of a signal applying the formula [START_REF] Grossmann | Painless nonorthogonal expansions[END_REF], within the analysis-weighting approach using a binary mask: as detailed in Sections 2 and 3, we analyze a signal with different stationary Gabor frames; the sound we consider is the same of the section 4.1, and the binary mask is still obtained with a cut frequency of 300Hz, while the sampling rate is 44.1kHz. We modify the coefficients of all these analyses with the mask w 1 (ν), and build the NGF {g 1 k,l } with resolutions adapted to the low frequencies optimizing the entropy of the masked analyses. Then we repeat this step with the mask w 2 (ν) and build the NGF {g 2 k,l }. We finally calculate the duals of the two NGFs, which can be done in these cases with fast algorithms, and re-synthesize the two signal bands: for these examples, the reconstruction is performed with the SuperVP phase vocoder by Axel Röbel [START_REF] Röbel | SuperVP[END_REF]. Figure 5 shows the spectrogram of the lower signal band, reconstructed with the low-frequencies adapted analysis. This spectrogram is computed with a fixed window, which is the largest one within the set considered; the choice of the best window is given as well, to give information about how the reconstruction is performed at each time. Figure 6 is obtained in the same way, considering the upper band reconstruction. The approximation of the original sound is then given by the sum of the two bands.

The reconstruction error we obtain is higher than the one in the previous examples: the maximum absolute value of the samples differences is 0.0568, while the root mean square error is 0.0099. With the choice of a binary mask, the only way to reduce the error is to set the cut frequency in a range where the signal energy is Figure 4: Adaptive analysis with a mask privileging frequencies above 300Hz, on a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54: on top, best window size chosen as a function of time; at the bottom, adapted spectrogram of the analyzed sound file. low: unfortunately, music signals generally do not have large lowenergy bands; moreover, the interest of our method relies in the possibility for the cut frequency to be variable, in order to freely select the adaptation criterium. Figure 7 shows the spectrogram of the difference between the original sound and the reconstructed one, and we see that the spectral content of the error is concentrated at the cut frequency. The alteration introduced has negligible perceptual effects, so that the original signal and the reconstruction are hard to be distinguished: this aspect needs to be quantified; when dealing with the approximation of music signals, the objective error measures do not give any information about the perceptual meaning of the error. The accuracy of a method has thus to be evaluated by means of measures taking into account the human auditory system as well as listening tests.

Another element to consider is the overlap between the weight functions introduced in section 2: if we allow them for an overlap over a sufficiently large frequency band, we envisage that the error would be reduced. The sense of this point can be clarified considering the causes of the reconstruction error: windows with compact time support cannot have a compactly supported Fourier transform; from the analysis point of view, this means that a spectrogram coefficient affects the signal reconstruction among the whole frequency dimension. We can limit such an influence with a choice of well-localized time-frequency atoms: even if their frequency support is not compact, they have a fast decay outside a certain region. If we cut with a binary mask outside a certain band, the reconstruction error comes mainly from the fact that we are setting to zero the contribution of atoms whose Fourier transforms spread into the band of interest: if the atoms are well-localized, only a few of them actually have an impact. Formula (2) gives an ideal reference: if the overlap is the entire frequency dimension, weights are non-zero, thus we have a perfect reconstruction from the weighted coefficients. When some weights are zero and weight functions do overlap, the normalization factor in the formula ( 2) is greater than one in the overlapping frequency interval. This reduces the impact of the errors coming from individual re-syntheses: on the other hand, the fact of summing them all imposes a limit to the achievable global error reduction. A further improvement of this formula is to put different weights at the denominator in (4), with an effective amplification or reduction of the contributions coming from individual coefficients. To keep the perfect reconstruction valid in the case of semi-normalized norms, a possibility is to obtain the different weights as a function of the analysis weights depending also on the overlap.

CONCLUSIONS AND PERSPECTIVES

We have sketched the first steps of a promising research project about the local automatic adaptation of time-frequency sound representations: a first question which arises is how to display a representation of the signal such the one described; there are two possibilities involving weighted means of the coefficients at a certain time-frequency location: In a previously proposed method [START_REF] Röbel | A reduced multiple Gabor frame for local time adaptation of the spectrogram[END_REF] the algorithm keeps the original coefficients in memory; with this approach, we can use the reconstruction scheme mentioned in [START_REF] Zyczkowski | Rényi Extrapolation of Shannon Entropy[END_REF]. A further new question would be how to reconstruct the signal from an expansion of the d k,l or d k,l is used, we also have to address the problem of the phase. This approach is useful when dealing with spectrogram transformations where the phase information is lost, as with reassigned spectrogram or spectral cepstrum. We could either use an iterative approach, like the one described in [START_REF] Griffin | Signal Estimation from Modified Short-Time Fourier Transform[END_REF] adapted to frame theory, or use a system with a high redundancy (see [START_REF] Balan | On signal reconstruction without phase[END_REF]).

From a computational point of view, we are interested in limiting the size of the signal for the direct and inverse Fourier transforms in [START_REF] Balazs | Theory, Implementation and Applications of Nonstationary Gabor Frames[END_REF], as this will largely improve the efficiency of the algorithm. A different form of the formula (2) in this sense is

f = p,k,l c p k,l F -1 1 p(ν) F g k,l p w p (b p k l) (13)
whose properties have to be further investigated.

Later we would also investigate the properties of time-variant filters by multiplying these new sets of coefficients, resulting in new kinds of frame multipliers [START_REF] Balazs | Basic definition and properties of Bessel multipliers[END_REF]. Using an optimized way to analyze acoustical signal, will, therefore, also lead to a better control of such adaptive filters.

Figure 1 :

 1 Figure 1: Rényi entropy evaluations of the DM vectors with varying α; the distribution becomes flatter as M increases. Therefore increasing α favors a sparse representation (see text).

Figure 2 :

 2 Figure 2: Rényi entropy evaluations of the DL vectors with varying α, Npart = 5 and Rpart = 2; the entropy values rise differently as L increases, depending on α: this shows that the impact of the noise level on the entropy evaluation depends on the entropy order (see text).

Figure 3 :

 3 Figure 3: Adaptive analysis with a mask privileging frequencies below 300Hz, on a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54: on top, best window size chosen as a function of time; at the bottom, adapted spectrogram of the analyzed sound file.

Figure 5 :

 5 Figure 5: Low-frequencies reconstruction from the masked adapted analysis of a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54: on top, best window size chosen as a function of time. At the bottom, spectrogram of the analyzed band with a 4096 samples Hamming window, 3072 samples overlap and 4096 frequency points; the frequency axis is bounded to 2kHz to focus on the reconstructed region.

•

  d k,l = 1 p w p • p c p k,l , displaying |d k,l |, or • d

Figure 6 :

 6 Figure 6: High-frequencies reconstruction from the masked adapted analysis of a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54: on top, best window size chosen as a function of time; at the bottom, spectrogram of the analyzed band with a 4096 samples Hamming window, 3072 samples overlap and 4096 frequency points.

Figure 7 :

 7 Figure 7: Spectrogram of the reconstruction error given by the described method on a music signal with a bass guitar, a drum set and a female singing voice starting from second 1.54; spectrogram obtained with a 4096 samples Hamming window, 3072 samples overlap and 4096 frequency points.

This work was supported by grants from region Ile de France † This work was partially supported by by the WWTF project MULAC ('Frame Multipliers: Theory and Application in Acoustics; MA07-025)


Bart Lamiroy
email: bart.lamiroy@loria.fr

Laurent Wendling
email: laurent.wendling@parisdescartes.fr

Symbol Recognition using Spatial Relations

Keywords: Vocabulary, Spatial Relations, Attributed Relational Graph, Symbol Recognition

In this paper, we present a method for symbol recognition based on the spatio-structural description of a 'vocabulary' of extracted visual elementary parts. It is applied to symbols in electrical wiring diagrams. The method consists of first identifying vocabulary elements into different groups based on their types (e.g., circle, corner ). We then compute spatial relations between the possible pairs of labelled vocabulary types which are further used as a basis for building an Attributed Relational Graph that fully describes the symbol. These spatial relations integrate both topology and directional information.

The experiments reported in this paper show that this approach, used for recognition, significantly outperforms both structural and signal-based state-of-the-art methods.

Introduction

Motivation

Symbol recognition -the core part of graphical document image analysis and recognition systems -plays an important role in a variety of applications such as automatic recognition and interpretation of circuit diagrams [START_REF] Okazaki | An automatic circuit diagram reader with loop-structure-based symbol recognition[END_REF], engineering drawings [START_REF] Yang | A dynamic-rule-based framework of engineering drawing recognition and interpretation system[END_REF] and architectural drawings [START_REF] Lladós | Symbol recognition by errortolerant subgraph matching between region adjacency graphs[END_REF][START_REF] Valveny | A model for image generation and symbol recognition through the deformation of lineal shapes[END_REF], maps [START_REF] Samet | Marco: Map retrieval by content[END_REF], musical notations [START_REF] Rebelo | Optical recognition of music symbols: A comparative study[END_REF], mathematical expressions [START_REF] Chaudhuri | An approach for recognition and interpretation of mathematical expressions in printed document[END_REF], as well as optical characters [START_REF] Yuen | Printed chinese character similarity measurement using ring projection and distance transform[END_REF]. Therefore, a symbol can be defined as a graphical entity with a particular meaning in the context of a specific domain.

Research on graphics recognition has an extremely rich state-of-the-art literature, aimed to localise/recognise symbols depending on the applications. [START_REF] Cordella | Symbol recognition in documents: a collection of techniques[END_REF][START_REF] Lladós | Symbol Recognition: Current Advances and Perspectives[END_REF] show that these methods are particularly suited for isolated line symbols, not for composed symbols connected to a complex environment. In order to exploit the information embedded in those documents, one needs to be able to extract visual parts and formalise the possible links that exist between them. This combination of symbol localisation based on extracted visual parts is going to be the core of this paper and is very much inspired by a real world industrial problem [START_REF] Tombre | Pattern recognition methods for querying and browsing technical documentation[END_REF][START_REF] Lamiroy | Inductive logic programming for symbol recognition[END_REF]. It consists in identifying a set of known symbols in aircraft electrical wiring diagrams, in order to bootstrap simulation algorithms. The main challenges come from the fact that the test symbols come in a wide variety of different forms. Symbols may either be very similar in shape, and only differ by slight details -or either be completely different from a visual point of view. Symbols may also be composed of other known and significant symbols and need not necessary be connected.

The rest of the paper is organised as follows. An overview of pertinent literature is given in Section 1.2, followed by a brief explanation of our proposed method in Section 2. We explain the way we describe symbols in Section 3, which mainly includes the concept of using spatial relations. We derive a symbol matching method from it in Section 4. Full experiments are reported in Section 5 and confront our method with current state-of-the-art algorithms. It includes a comprehensive experimental result analysis. We conclude in Section 6.

State-of-the-Art 1.2.1. Symbol Representations

Symbol recognition is a particular application of pattern recognition. Existing approaches, specifically those based on feature based matching, can be sorted into three classes: statistical, structural and hybrid. As respective examples , among others, one can cite [START_REF] Yang | Symbol recognition via statistical integration of pixel-level constraint histograms: A new descriptor[END_REF][START_REF] Zhang | Symbol recognition with kernel density matching[END_REF][START_REF] Lladós | Symbol recognition by errortolerant subgraph matching between region adjacency graphs[END_REF][START_REF] Yang | Symbol recognition via statistical integration of pixel-level constraint histograms: A new descriptor[END_REF].

Under statistical approaches, global signal-based descriptors [START_REF] Yuen | Printed chinese character similarity measurement using ring projection and distance transform[END_REF][START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF][START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF][START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]Zhang andLu, 2002, 2004] are usually quite fault tolerant to image distortions, since they tend to filter out small detail changes. This is unfortunately an inconvenient in our context. Moreover, they difficultly accommodate with connected or composite symbols. For instance, when symbols are combined, approaches that rely on centroid detection like [START_REF] Yuen | Printed chinese character similarity measurement using ring projection and distance transform[END_REF]] tend to fail. Others, like Shape Context [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] are sensible to occlusions on the symbol boundaries. Overall, they are generally not well adapted for capturing small detail changes, since they are specifically conceived to filter those out. In these statistical approaches, signatures are simple with low computational cost. However, discrimination power and robustness strongly depend on the selection of optimal set of features for each specific application.

Besides global signal-based descriptors, another idea is to decompose the symbols into either vector based primitives like points, lines, arcs etc. or into meaningful parts like circles, triangles, rectangles etc. These methods fall under structural approaches. They are then represented as Attributed Relational Graphs (ARG) [START_REF] Bunke | Efficient attributed graph matching and its application to image analysis[END_REF][START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF], Region Adjacency Graphs (RAG) [START_REF] Lladós | Symbol recognition by errortolerant subgraph matching between region adjacency graphs[END_REF], constraint networks [START_REF] Ah-Soon | Architectural symbol recognition using a network of constraints[END_REF] as well as deformable templates [START_REF] Valveny | A model for image generation and symbol recognition through the deformation of lineal shapes[END_REF]. Their common drawback comes from error-prone raster-to-vector conversion. Those errors can increase confusions among different symbols. Furthermore, variability of the size of graphs leads to computational complexity in matching. However, structural approaches provide a powerful representation, conveying how parts are connected to each other, while also preserving generality and extensibility.

To describe the symbols, it is necessary to handle relations between the decomposed parts. The following paragraph gives an overview of existing work on spatial relations and their proper usages.

Spatial Relations

Effects of spatial relations on recognition performance have been examined comprehensively for scene understanding, document analysis and recognition tasks [START_REF] Biederman | Perceiving real-world scenes[END_REF][START_REF] Bar | Spatial context in recognition[END_REF][START_REF] Xiaogang | An online composite graphics recognition approach based on matching of spatial relation graphs[END_REF][START_REF] Pham | Learning spatial relations in object recognition[END_REF]. Spatial relations can be either topological [START_REF] Egenhofer | Point-set Topological Spatial Relations[END_REF][START_REF] Egenhofer | Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases[END_REF][START_REF] Papadias | Topological relations in the world of minimum bounding rectangles: a study with rtrees[END_REF] directional [START_REF] Bloch | Fuzzy relative position between objects in image processing: New definition and properties based on a morphological approach[END_REF][START_REF] Matsakis | A New Way to Represent the Relative Position Between Areal Objects[END_REF][START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF] and metric in nature. For example, topological configurations are handled in [START_REF] Xiaogang | An online composite graphics recognition approach based on matching of spatial relation graphs[END_REF] with a few predicates like intersection, interconnection, tangency, parallelism and concentricity expressed with standard topological relations as described in [START_REF] Egenhofer | Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases[END_REF].

In a similar way, various directional relation models have been developed for a wide range of different situations.

• If the objects are far enough from each other, their relations can be approximated by their centres based on the discretised angle [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF]. This approach is robust to small variations of shape and size.

• If they are neither too far nor too close, relations can be approximated by their Minimum Bounding Rectangle (MBR) [START_REF] Lee | Spatial Reasoning and Similarity Retrieval of Images Using 2D C-string Knowledge Representation[END_REF][START_REF] Jungert | Qualitative spatial reasoning for determination of object relations using symbolic interval projections[END_REF][START_REF] Papadias | Topological relations in the world of minimum bounding rectangles: a study with rtrees[END_REF][START_REF] Papadias | Spatial relations, minimum bounding rectangles, and spatial data structures[END_REF] as long as they are regular.

• Approaches like Angle Histograms [START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF] tend to be more capable of dealing with overlapping, something the previous ones have difficulties with. However, since they consider all pixels of a shape, their computational cost increases dramatically.

• Other methods, like F-Histograms [START_REF] Matsakis | A New Way to Represent the Relative Position Between Areal Objects[END_REF] use pairs of longitudinal sections instead of pairs of points, also at the cost of high time complexity.

• Another well-known approach uses fuzzy landscapes [START_REF] Bloch | Fuzzy relative position between objects in image processing: New definition and properties based on a morphological approach[END_REF], and is based on fuzzy morphological operators.

Previously mentioned approaches address only either topological or directional relations. Managing both comes at high computational costs. Even then, no existing model fully integrates topology. They rather have various degrees of sensitivity to or awareness of topological relations. While methods like [START_REF] Xiaogang | An online composite graphics recognition approach based on matching of spatial relation graphs[END_REF] focus on topological information only, our approach unifies both topological and directional information into one descriptor [K.C. et al., 2010] without any additional running time cost.

Placing spatial relations in the context of recognition and symbol description, one should note that spatial relations also have a language-based component (related to human understanding e.g., to the right of) that can be formalised in a mathematical way (e.g., the 512 relations of the 9-intersection model [START_REF] Egenhofer | Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases[END_REF]). Therefore, qualitative and quantitative relations are another way to do categorisation of spatial relations. Consider an example, an object A extending from Right (98%) to Top (2%) with respect to B is expressed as Right -Top(A, B). This spatial predicate remains unchanged upto a reasonable change of the objects' shape and position. Taking this into account, our work uses more natural relations than the all-or-none nature of standard relations [START_REF] Freeman | The modelling of spatial relations[END_REF].

In the following section, we explain our proposed method by focusing on using spatial relations for describing and matching symbols.

Proposed Recognition Method

Our recognition method is based on a spatio-structural description of extracted visual parts that compose a symbol. This means that, to describe a symbol, we compute spatial relations between previously extracted visual parts. Without any other consideration, it is obvious that the size of the resulting relational graph is potentially very large and variable from one symbol to another. However, when grouping visual parts together according to their types (e.g., circle, corner ) and by labelling them accordingly (see Section 3.1), we can eliminate all the combinatorial problems inherent to graph matching, without sacrificing recognition quality or expressive power.

We compute the spatial relations (see Section 3.2) between the distinct labelled attributes for building an Attributed Relational Graph (ARG -see Section 3.3), achieving at the same time integration of both topological and directional information.

Since each vertex represents a different class of visual parts, the graph has a uniquely and distinctly labelled vertex set. Vertex and edge matching thus becomes trivial and can be done in near-constant time.

Symbol Description

As mentioned in Section 2, we first define our visual vocabulary in Section 3.1. In Section 3.2 we explain the way we compute pairwise spatial relations and finally use both in Section 3.3 to build an ARG and completely describe the symbol.

Visual Vocabulary

We define a set of well controlled visual elementary parts as a vocabulary [K. C. et al., 2009]. While, in the general case, this vocabulary can be of any kind from any type of bag-of-features, related to what is visually pertinent in the application context under consideration, our current vocabulary is related to electrical symbols. It can be easily extended to adapt to other domains. Such visual elementary parts are extracted with the help of image treatment analysis operations as described in [START_REF] Rendek | The search for genericity in graphics recognition applications: Design issues of the qgar software system[END_REF]. Shortly, we discuss on how we accomplished it.

thick primitive: We employ straight forward thin/thick separation by counting all thick connected components within the image. It simply uses standard skeletonisation using chamfer distance and computes the histogram of line thickness. An optimal cut value is computed from the histogram to distinguish between thick zones and thin zones.

circle primitive: We use the algorithm as described in [START_REF] Lamiroy | Robust and precise circular arc detection[END_REF] which is based on Random Sample Consensus minimization.

corner primitive: We mainly consider four types of corners such as North-East, North-West, South-East and South-West. It uses simple template matching process i.e., if the ratio of black and white pixels is greater than or equal to the template threshold, then the presence of corner is accessed.

extremity primitive: We approach to detect loose end coordinates p x from a given skeleton pixel where there is only a unique neighbouring pixel p c 1 connecting to the main skeleton, which itself is connected by a unique neighbouring pixel p c 2 .

Fig. 1 shows an illustration of visual primitives, extracted from two different symbols. Rather than using every detected element as a basis for expressing and computing spatial relations, we group them together by type as shown in Fig. 1. We denote the set of these generated groups as, T = {T thick , T circle , T corner , T extremity }.

Spatial Relation

In order to express the spatial distribution of the previously formed groups, we compute a spatial signature ℜ (defined further in Eq. ( 1)), expressing the spatial relations between two sets of pixels A and B. This section explains in detail how it is computed.

Pairwise spatial relations are often expressed by using one of the objects as reference. For example, A is to the right of B: right(A, B), where B is referenced. In our context, since the number of vocabulary types is not always the same for all symbols, it is difficult to take a particular type as a reference. To avoid such a difficulty, we first set up a unique reference point from each pair as shown in Step 1, hereafter. Then, we compute directional relations with respect to the reference point, thus avoiding potential ambiguity.

Step 1. Unique Reference Point Set We consider a unique reference set R, defined by the topology of the minimum bounding rectangles (MBR) of A and B and with the help of the 9-intersection model [START_REF] Egenhofer | Categorizing Binary Topological Relations Between Regions, Lines, and Points in Geographic Databases[END_REF]. In connection with [START_REF] Renz | Spatial reasoning with topological information[END_REF]], R is either the common portion of two neighbouring sides in the case of disconnected MBRs or the intersection in the case of overlapping, equal or otherwise connected MBRs. To do this, we simply check topological relations between them in a 9-dimensional binary space via the use of intersections of the boundaries, interiors and exteriors of two sets A and B.

Depending on the obtained topological configurations, R can range from a point to a rectangular 2D area. In what follows, we define its centroid point R p as our reference point for computing spatial relation ℜ between A and B.

Step 2. Directional Relation For a given reference point R p , we cover the surrounding space at regular radial intervals of Θ = 2π/m. As shown in Fig. 2 (a), a radial-line rotates over a cycle, and when intersecting with object X (A or B),

generates a boolean histogram H, H(X, R p ) = [I(R p , jΘ)] j=0,...,m-1
where

I(R p , θ i ) = 1 if line(R p , θ i ) ∩ X = ∅ 0 otherwise.
This boolean histogram expresses whether there are any black pixels in direction θ i . We extend this direction histogram, without loss of generality, to a histogram covering sectors defined by two successive angle values. Furthermore, rather than using boolean values, we can account for the percentage of pixels of the whole object lying in the general direction θ i . Fig. 2 (b) gives an example for both types of histogram, boolean and percentage.

Applying this to both objects A and B, our spatial relational signature ℜ(X, R p ) is the set of both histograms

ℜ(X, R p ) = {H(A, R p ), H(B, R p )}. (1)
It is important to understand that we know the visual vocabulary types to which A and B belong (cf. Section 3.1). Defining a fixed arbitrary order on the set of types T solves the potential ordering problem when comparing two relational signatures. x y

Object X Rp Θ = 3 • Histograms at Θ = 3 • resolution: boolean H(X, Rp) = [1 1 1 1 1 0 0 ... 0] 1×120 metric H(X, Rp) = [0.
14 0.21 0.24 0.28 0.12 0 0 ... 0] 1×120 (b) An example of histograms computation: boolean and metric. Illustrations. In Fig. 3 we show how our method adapts to different topological configurations. This section is not intended to give a full and formal evaluation of our approach, but rather to provide the user with an intuitive feeling on how it behaves. The figure shows various computed histograms in different configurations. These configurations were chosen to cover most topological relations between two objects one may encounter.

Let us consider the first three instances (a), (b) and (c). Keeping (a) as a reference image, we have changed a stroke thickness without changing relative positioning in (b) and moved objects closer while keeping identical topological configuration in (c). We observe that histograms do not show any significant difference. Scaling does not affect our method since H is normalised. In addition, the line rotation does not consider distance (far or near ) information as long as it does not change the angular positioning.

For false overlapping configurations, as shown in (d), the coverage angle of H changes due to the change in structure (elongating horizontal limb in both objects).

For all inclusion configurations (like the false inclusion depicted in (f), but equally for full inclusion situations), our method does not produce any histogram for the component X which is either contained in or covered by the other: it is simply H(X, R p ) = ∅.

Besides, the difference of histograms between two overlapping cases in (g) and (h) can be observed in the middle of H(B, R p ) (between 40 • -80 • ). This provides the fact that the method is able to discriminate slight changes in the object configurations even when identical topology exists.

Fig. 4 represents similar configurations taken from a real-world example, using the vocabulary extraction described in Section 3.1 Remarks. Our method captures the spatial information by the angular positions in the histogram. The magnitude of the histogram contains the structural information. Furthermore, running time does not depend on the size of the spatial objects as in the Angle Histogram approaches [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF], for instance. Our method simply counts the number of pixels in every sector made by two consecutive radial-lines while rotating. However, running time is fixed and entirely depends on the parameter Θ (rotation step) that defines the resolution of H and the global size of the image. Its value is a trade-off between precision and execution time. We establish the optimal resolution for our application in Section 5.

Attributed Relational Graph

The vocabulary developed in Section 3.1 consists of a set of fixed label attributes, while the spatial relations between the attributes are the histograms described in Section 3.2. This gives us all the elements to express symbols as a complete ARG in which each vertex represents a distinct attribute type and the edges are labelled with a numerical expression of the spatial relations ℜ.

More formally, we express the ARG as a 4-tuple G = (V, E, F A , F E ) where

V is the set of vertices;

E ⊆ V × V is the set of graph edges;

F A : V → A V
is a function assigning labelled attributes to the vertices where A V is the set of attributes type set T (cf. Section 3.1) and

F E : E → ℜ E is
a function assigning labels to the edges where ℜ represents the spatial relation of the edge E (cf. Section 3.2). Note that ℜ does not provide symmetry, ℜ(A, B) = ℜ(B, A). But, this can be solved by fixed ordering of V and R is not affected.

For instance, using symbol 1 in Fig. 1 as an example, and its corresponding spatial relations in Fig. 4 we obtain the following ARG representation:

G = { V = {T 1 , T 2 , T 3 }, E = {(T 1 , T 2 ), (T 1 , T 3 ), (T 2 , T 3 )}, F A = {(T 1 , T circle ), (T 2 , T corner ), (T 3 , T extremity )} F E = {((T 1 , T 2 ), ℜ(T 1 , T 2 )), ((T 1 , T 3 ), ℜ(T 1 , T 3 )), ((T 2 , T 3 ), ℜ(T 2 , T 3 ))}}
This forms a complete graph, and therefore has r = t(t-1) 2 edges for t attribute types.

Symbol Recognition

Now that we have set up our ARG for symbol representation, we can define our recognition process. Recognition based on maximal similarity, measured by a matching score. The score is purely based on matching the corresponding relational signatures between the two given ARGs.

We then further extend the recognition by ranking database symbols based on the order of similarity, both of which will be explained in this section.

Matching

Following the ARG description in Section 3.3, let us consider two graphs:

G q = (V q , E q , F q A , F q E ) for the query symbol and

G d = (V d , E d , F d A , F d E )
for the database symbol.

Let us remind that the set of vertices V , with |V | = t and set of edges E, with |E| = r.

In order to explain our matching strategy, we are first taking the simplifying assumption that V q and V d are identical. In other words, both symbols contain items corresponding to identical vocabulary elements, but not necessarily sharing the same spatial arrangement. Since in our ARG every single vertex bears one distinct and unique attribute type, there is no cost in matching the vertices between G q and G d . As a consequence, matching edges is equally straightforward.

Since we have temporarily taken the assumption that V q and V d contain the same vocabulary elements, we can set up a bijective matching functions ϕ : V q → V d and σ : E q → E d . This bijection exists such that uv is an edge in graph G q if and only if ϕ(u)ϕ(v) is an edge in graph G d . Also we consider that ordering is preserved over the vertices sets V q and V d . I.e.

v 1 < v 2 ⇒ ϕ (v 1 ) < ϕ (v 2 ).
Thanks to our fixed labelling of attribute types, corresponding ℜ alignment is possible between the two given graphs and we can provide a matching score between the two given graphs G q and G d ,

dist. align (G q , G d ) = r∈E δ F q E (r), F d E (σ(r) where δ(a, b) = L l=1 (a l -b l ) 2
. This is actually a very simple and straightforward metric. Given the performances of our method reported in Section 5 there is no real need to have a more complex one, unless rotational invariance is needed.

Of course, the assumption that V q and V d share the exact same vocabulary is too strong. To generalise the previously described approach to any situation, we define a binary (indicator) function τ V A : Σ T → {0, 1} to check the presence of vertices in the ARG, where the value of τ V A (T) is 1 if T is present in V and 0, otherwise. For example, for the symbol 1 shown in Fig. 1,τ V A = [0, 1, 1, 1]. This refers to the absence of thick components and the presence of circle, corner and extremity components.

We can then use a simple edit cost between τ V q A and τ V d A defined by the number of edge deletions/insertions or substitutions. To do this, we first note the number of vertices to be deleted/inserted or substituted. Then consider the number of adjacent links.

dist. edit (G q , G d ) = P p=1 c(o p ), ∀(o 1 , . . . , o P ) ∈ (G q , G d )
where (G q , G d ) denotes the set of edit paths transforming G q into G d and c, the edit cost function for operation o p . Once virtual links exist (i.e., null relation) after insertion for instance, edit cost is carried out as if matching has been done with relational alignments.

The final matching score or distance in the generic case D(G q , G d ) therefore is obtained from the fusion of edit cost and relational signatures alignment (reduced to the common node types between the two graphs). More formally, distance (matching score) between two given graphs is,

D(G q , G d ) = αdist. align (G q , G d ) + (1 -α)dist. edit (G q , G d )
where α ∈ [0, 1]. The parameter α provides weight while matching. In our experiments we use α = 0.5. The excellent results obtained and reported in Section 5.2 have not required us to tune this parameter further.

In the following, we give an example of how distance is computed.

Example. Consider V q = {T q 1 , T q 2 } T q 1 T q 2 in G q and V d = {T d 1 , T d 2 , T d 3 } T d 1 T d 2 T d 3 in G d .
Then matching score between them is,

D(G q , G d ) = α [ δ(ℜ T q 1 ,T q 2 ,ℜ T d 1 ,T d 2 ) ] dist. align +(1 -α) δ(ℜ T q 1 ,T q 3 ,ℜ T d 1 ,T d 3 ) + δ(ℜ T q 2 ,T q 3 ,ℜ T d 2 ,T d 3 ) dist. edit
where ℜ x,y = ℜ(x, y). It is clear that T q 3 has to be inserted in G q in order to transform it to G d . As a consequence, virtual connections: ℜ T q 1 ,T q 3 and ℜ T q 2 ,T q 3 exits. Then matching is straightforward due to the labelled vertices in ARG. In addition, the weighting parameters are now useful to select either only dist. align or taking both with equal as well as with different weights.

Ranking

The previously defined matching score conveys how similar/dissimilar a database symbol is with respect to a query. In order for similarity to be ranging from 1 to 0, we normalise D( ) to [0, 1] by taking all database symbols: D( ) = D( )-D min. ( ) D max. ( )-D min. ( ) . Now, the similarity is,

Similarity(G q , G d ) = 1 -D(G q , G d ).
Ranking can therefore be based on the decreasing order of similarity.

Experiments

In this section, we first give an overview of the symbols in our dataset and explain how we have labelled them with ground-truth. Then we discuss the evaluation metric, clarifying its proper usage for this application. Based on the metric, we perform a series of experiments and confront our method with the existing ones.

In the very beginning of the experiment, we consider the influence of different resolutions Θ in our relational signature. Once an optimal resolution is chosen, our spatial relation is compared with fundamental spatial relation models: Cone-shaped [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF], Angle Histogram [START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF] and MBR [START_REF] Papadias | Spatial relations, minimum bounding rectangles, and spatial data structures[END_REF]]. Then we perform another assessment in order to make comparison of the complete method with the state-of-the-art approaches. For this, we first take a few representative global signal-based descriptors: region based Zernike Moments (ZM) [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], Generic Fourier Descriptors (GFD) [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF], Shape Context (SC) [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] and R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], applied directly to the symbol. Then we take two recent pixel-based approaches: Statistical Integration of Histogram Array (SIHA) [START_REF] Yang | Symbol recognition via statistical integration of pixel-level constraint histograms: A new descriptor[END_REF] and 2D kernel density [START_REF] Zhang | Symbol recognition with kernel density matching[END_REF] based symbol representation.

Dataset and Ground-truth Formation

Dataset. We work on a real world industrial problem to identify a set of different known symbols in aircraft electrical wiring diagrams as in [START_REF] Tombre | Pattern recognition methods for querying and browsing technical documentation[END_REF][START_REF] Lamiroy | Inductive logic programming for symbol recognition[END_REF]. Fig. 5 gives some examples of symbols in the database. Symbols may either be very similar in shape -and only differ by slight details -or either be completely different from a visual point of view. Symbols may also be composed of other known and significant symbols and need not necessary be connected. It is composed of roughly 500 different known symbols. Our dataset is completely unlabelled and imbalanced i.e., neither ground-truth is given nor identical number of similar symbols exist for all queries.

Ground-truth Formation. Since there is no absolute ground-truth associated to our dataset, we have proceeded by using human validation, but by taking care of eliminating subjective bias. In order to achieve this we have asked 6 volunteers to manually select what they consider as "similar" symbols, for all queries executed in this section. Human evaluators have chosen the candidates which have similar visual overall appearance or which have significantly similar parts with respect to the chosen query. In our testing protocol, we consider that a result returned from an algorithm is correct if at least one human evaluator has selected the same result among the similar items. In more formal terms, for each query the "ground-truth" is considered to be the set of symbols formed by the union of all human selected sets. Fig. 5 provides a few examples. For instance, for query a1, evaluators have provided a list of symbols which they consider visually close, or containing parts that are visually close. The evaluators were not required to provide any ranking order nor degree of visual resemblance.

Experimental Protocol and Results

Experimental Protocol

Evaluation Metric. Our aim is not only limited to distinguish symbols but also extended to rank symbols in the provided lists. Ranking is related to similarity based on distance measure as described in Section 4.2. It becomes clear from Fig. 5 that there is a different number of pertinent documents in the database for each query. In order to be able to report retrieval results in a coherent way, we choose not to use classical precision and recall but to use the retrieval efficiency measure instead [START_REF] Kankanhalli | Cluster-based color matching for image retrieval[END_REF]. Retrieval efficiency has the advantage not to degenerate when the ranking parameter K grows bigger than the number of relevant items in the database, as would have been the case for precision and recall. For every chosen query, efficiency of retrieval for a given short list of size K is expressed as,

η K = n/N if N ≤ K n/K otherwise,
where n is the number of returned relevant symbols, N the total number of relevant symbols and K the number of ranked symbols requested. Note that η K computes the traditional recall if N ≤ K and computes precision otherwise. The main advantage of this is that the average retrieval efficiency curve is not biased even with different quantities of ground-truth for different queries, while it happens for precision measures when N < K.

Matching Scope. Because of the fact we have a fixed set of labelled vertices (i.e., vocabulary types) in our symbol description, we are able to control the matching scope for every chosen query by using a parameter s. Using the notation introduced in Section 4.1, we define s as δ(τ

Vq A , τ V d A ).
Depending on the value of s different matching strategies can be applied: s ≥ 0 : all candidates in the dataset are taken into consideration for matching.

s ≤ 1 : matching is only done between candidates differing by at most one vertex (i.e., one vertex can be absent or supplementary). s = 0 : matching is done by candidates only having the exact same set of vertices (i.e., V q = V d ).

Therefore, we have applied the three different matching strategies to evaluate the behaviour of different methods with scopes ranging from s ≥ 0 to s = 0.

Our assumption is that candidates having same set of vertices as well as exact labels are similar either for their whole structure or part of it when in composite forms. This assumption has been experimentally validated.

Results

In this section we present a series of experiments establishing the performances of our approach. We address three specific issues:

1. What is the optimal set of parameters for our method? 2. How does our spatial relation model compare to other spatial relation models? 3. How well does our recognition model do with respect to state-of-theart recognition models?

In all experiments, we have used retrieval efficiency, as described in Section 5.1. We compare the average retrieval efficiencies over the same 30 queries for all presented cases. These efficiency values have been computed for values of K = 1 to 10.

Resolution Parameter Determination. Our method, besides depending on the choice of the vocabulary, uses one main parameter: the resolution at which the angular histogram is computed1 . Its value represents the trade-off between the optimal choice of resolution -and thus precision of spatiostructural information capture -and time/space requirements. Fig. 6(a) shows the result of a series of experiments with Θ varying over

{1 • , 3 • , 5 • , 9 • }.
For each of its values we have measured the retrieval efficiency on the same set of queries. Without surprise, the lower Θ, the better the results, independently of the matching strategies used.

Based on these results, and given the relatively low gain of efficiency between 3 • and 1 • , we adopt the former for the rest of our experiments.

Other Spatial Relation Models. In order to compare our spatial relation model with others, we have adapted our ARG to function with those published in [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF][START_REF] Papadias | Spatial relations, minimum bounding rectangles, and spatial data structures[END_REF][START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF], and we have submitted them to the same testing protocol as described before. Fig. 6(b) shows their average retrieval efficiency. MBR outperforms all others in all situations. We shall further compare it to our method at the end of this section.

Global Signal-based Descriptors. In order to compare our method to other recognition methods, we have selected a set of major global signalbased shape descriptors described in Section 1.2 [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF][START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF][START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF][START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF]. For GFD, we have tuned the parameters, and selected those values for radial and angular frequency that achieved the best recognition performance on our dataset: radial frequency 6 and angular 15. For Shape Context, only 70 sample points have been selected because of the presence of smaller size images in our database. In case of ZM, we have used 36 zernike functions of order less than or equal to 7. Also, we have taken radon image intensity over the projecting angle [0, π[ by default, for R-signature. Unlike the methods based on spatial relations, we cannot establish different matching scopes, based on s as presented in Section 5.2.1 and used previously.

Again the same queries are presented and average retrieval efficiency is shown in Fig. 6(c). GFD seems to be performing the best among all tested global signal-based descriptors in our setup.

Pixel-based Approaches. We have also compared our method with two pixel-based approaches specially designed for symbol recognition: Statistical Integration of Histogram Array (SIHA) [START_REF] Yang | Symbol recognition via statistical integration of pixel-level constraint histograms: A new descriptor[END_REF] and Kernel Density Matching (KDM) [START_REF] Zhang | Symbol recognition with kernel density matching[END_REF]. In SIHA, two different length-ratio and angle-ratio histograms are taken from every two pixels in reference to a third pixel from the skeleton image. In KDM, skeleton symbols represent as 2D kernel densities and their similarity is measured by the Kullback-Leibler divergence. In Fig. 6(d), results are shown for both. In this test, we observe almost similar behaviour from the two. However, KDM performs slightly better, especially when also taking time complexity into account.

Overall, compared to our method, basic spatial relation models and global signal-based descriptors as well as recent pixel-based approaches have been lagging behind. Fig. 6(e) provides a comparison by taking the best of both classes: MBR from the spatial relation models, GFD from the global signalbased descriptors and KDM from the pixel-based approaches. Our method outperforms both with a significant difference in retrieval efficiency.

Discussions

In this section, the performance of the methods in response to the experimental results are analysed. Performance not only refers to retrieval efficiency but also to time complexity. In parallel, we discuss matching scope and its effect in ranking retrieved symbols.

To visually compare the results of our method with the best of breed solutions reported in Fig. 6(b), 6(c) and 6(d), we show a selection of queries in Fig. 7. They demonstrate the use of isolated as well as composed symbols as query. The first symbol on the top is always the chosen query and symbols are ranked from top to bottom (1 to 10) based on decreasing order of similarity. For query Q1, GFD and KDM come close to our method while MBR presents a notable difference. In case of query Q2, our method outperforms all others significantly. A similar situation happens for Q3.

Our method exploits spatio-structural description of the visual parts. The choice of the vocabulary types (i.e. collection of particular visual parts) is of course an important factor to its success. However, symbols like , etc. are retrieved for the query due to the presence of thick patterns. This shows that our relational signatures do not provide or use any shape information. Therefore, symbols having any thick pattern like, , , , , , , , , , , etc. are selected for ranking. However, spatial organisation of thick patterns with respect to other primitives helps to rank the best one first.

Running time has been measured in all experiments. An average running time (in sec.) for all methods is given below.

We used MATLAB 7.8.0 in Linux platform.

Our method has benefited from the way we describe the matching strategy (cf. Section 5.2.1). Symbol matching between the candidates which share the same sets of vertices with exact labels (i.e., s = 0), is found to be the best among all. It sufficiently reduces time of matching to symbols which are obviously irrelevant. Similarly, this happens in those tests using basic spatial relations models. But for global signal-based descriptors as well as pixel-based approaches, running time increases with number of symbols in the dataset since matching scope does not exist.

Conclusions and Further Work

In this paper, we have presented a method to describe symbols using a specific Attributed Relational Graph via the use of spatial relations between the visual elementary parts. Each vertex represents all visual parts of a particular vocabulary type within the symbol. The edges represent the spatial relations between them. The proposed method is simple and flexible, and has the ability to express spatial relations between any number of visual parts. We have validated that such a description can be used for symbol recognition. Our method has proven to significantly outperform state-of-the-art basic spatial relation models, global signal-based descriptors and pixel-based approaches for symbol recognition. Further work comprises the study of the influence of the weighting parameters in the matching score. Furthermore we are currently studying clustering techniques to enhance the discriminative power (and this enhance retrieval performance) of the thick component patterns. In addition, we are going to relate our work to [START_REF] Bai | Learning contextsensitive shape similarity by graph transduction[END_REF] in order to see how both approaches can be combined to enhance overall performance.

Figure 1 :

 1 Figure 1: Illustration of vocabulary type.

Fig. 3 and

 3 Fig. 3 and Fig. 4 provide illustrations on hand-drawn and real-world examples respectively. The illustrations show how the reference point set R is obtained and show the corresponding histogram H. They are analysed in the following section.

Figure 2 :

 2 Figure 2: Computing spatial relations using radial-line rotation.

  , R p ) H(B, R p ) (a) disconnected (b) disconnected, scaling (c) disconnected (d) disconnected, false overlapping (e) overlapping (f) disconnected, false inclusion (g) overlapping (h) overlapping

Figure 3 :

 3 Figure 3: Histograms at 3 • resolution for a few hand-drawn spatial objects A and B, having different topological configurations.

Figure 4 :

 4 Figure 4: Histograms at 3 • resolution for all possible pairs of vocabulary types from a symbol 1 as shown in Fig. 1.

Figure 5 :

 5 Figure 5: A sample of few electrical symbols. For every test symbol: a1 to a7, a few relevant symbols are enlisted based on human evaluation. It consists of both linear as well as symbols in the composite form.

  Our method using different resolutions:1 • , 3 • ,5 • and 9 • .

Figure 6 :

 6 Figure 6: Average retrieval efficiency over requested list -1 to 10: (a) Our method, (b) Fundamental spatial relation models, (c) Global signal-based descriptors, (d) Pixel-based approaches and (e) Comparison.

Figure 7 :

 7 Figure 7: Visual illustration of symbol retrieval and ranking for a few queries, showing the true ( ) and false (✪) retrieval.

The matching scope s, as introduced in Section 5.2.1 should not really be considered as a parameter, but as a measure of our method's robustness.


Marco Liuni

Axel Röbel

Marco Romito

Xavier Rodet

RÉNYI INFORMATION MEASURES FOR SPECTRAL CHANGE DETECTION

Keywords: Change detection, spectral entropy, Kullback divergence, Rényi entropies, segmentation

published or not. The documents may come

INTRODUCTION

The detection of spectral changes within an audio signal can be performed according to many different criteria, depending on the applications; the key point is what kind of spectral change has to be considered significant. A typical problem in audio classification is to identify signal segments with different contents, for example when analyzing a radio stream to separate speech, music or mix of them; another type of problem is speaker change detection, which typically occurs when indexing audio recording of conferences, interviews or lectures. In either case we have to perform a segmentation and a classification, but the interesting spectral changes are completely different. The point of view we consider is at the signal level, since our research is about adaptive resolution methods for analysis, transformation and re-synthesis of a sound.

The use of information measures to evaluate the features of a time-frequency representation of a signal is frequent in This work is supported by grants from Region Ile-de-France.

the literature: Shannon entropy is applied to evaluate the concentration of the representation seen as a probability distribution, and the derived divergence measures [START_REF] Lin | Divergence measures based on the shannon entropy[END_REF] are employed to identify variations within the representation.

The representation we consider is the spectrogram of the signal: through a normalization which gives a unitary sum, we consider the discrete spectrogram in a finite time interval as a probability distribution, and we can apply typical information measures to evaluate its concentration in the time-frequency plane. Fixing the signal f , we write

PS m = {PS f [m, k], k = 1, ..., N } to indicate the m-th anal- ysis frame in the discrete spectrogram PS f of f ,
where the FFT size N is the finite number of sample frequencies considered. Given two normalized analysis frames PS 1 and PS 2 , the Kullback K divergence [START_REF] Lin | Divergence measures based on the shannon entropy[END_REF] is usually employed to have a measure of their difference: a spectral change is detected whenever K(PS 1 , PS 2 ) is larger than a chosen threshold. A refinement of this method (see for example [START_REF] Basu | A linked-HMM model for robust voicing and speech detection[END_REF]) provides a better robustness to false alarms defining a mean spectrum PS mean and comparing its divergence with the new analysis frame.

The first method we propose is a straight extension of the one just described: we consider the divergence measure derived from the Rényi entropy [START_REF] Rényi | On Measures of Entropy and Information[END_REF] instead of the K directed divergence, allowing a tuning of the detection criteria thanks to the dependance of the measure on a parameter. The second method is not based on divergence but on Rényi entropy itself, exploiting one of its fundamental property: the entropy of a union of probability distributions can be evaluated considering the entropy values of the individual distributions. Since we do consider analysis frames as probability distributions, this property can be used to establish the expected entropy value of a certain signal segment when the following frame is added: if the actual value differs significantly from the expected one, the last frame is considered to contain a spectral change.

This kind of algorithm does not need acoustic models to refer to, nor data training: a certain metric is evaluated in a given space [START_REF] Kemp | Strategies for automatic segmentation of audio data[END_REF]. The information measures we take into account can be applied on several different representation of the signal: in [START_REF] Siegler | Automatic segmentation, classification and clustering of broadcast news audio[END_REF] the K divergence is used in a GMM framework instead of on the spectrogram. In several approach, for example in [START_REF] Foote | Automatic audio segmentation using a measure of audio novelty[END_REF], difference measures are calculated as a first step which gives a suitable analysis for segmentation and classification purposes: for all these algorithms, the class of measures we introduce could ameliorate the detection performances as they allow a further parameter of choice, while still including the K divergence for a given value of the parameter.

In the next section we give the essential properties and definitions of the measures considered, then we describe the biasing obtained with the parameter introduced. Finally we present our algorithms and give some examples: we use a speech fragment to compare the detection with the one given by the K divergence measure; we take as a reference the segmentation given on the same signal by an HMM-based phoneme segmentation method [START_REF] Lanchantin | Automatic phoneme segmentation with relaxed textual constraints[END_REF], and the voiced-unvoiced classification obtained with a PSOLA-based algorithm [START_REF] Mattheyses | Robust Pitch Marking for Prosodic Modification of Speech using TD-PSOLA[END_REF]. Our results are interesting as the methods provide a refined adjustable detection, despite of their substantial plainness and low computational cost.

RÉNYI ENTROPIES AND INFORMATION MEASURES

Given a finite probability density p and a rational number α ≥ 0, the Rényi entropy of p is defined as follows,

H α [p] = 1 1 -α log 2 N k=1 p α [k] , (1)
where p is in square brackets as we are considering the measure on discrete densities; as α tends to one this measure converges to the Shannon entropy, which is therefore included in this larger class. 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]; in particular, H α (P ) is a non increasing function of α, so α 1 < α 2 ⇒ H α1 (P ) ≥ H α2 (P ) . Moreover, 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. 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 α. Given a second finite probability density q of the same length, if p and q have exactly the same zeros the Rényi information [START_REF] Rényi | On Measures of Entropy and Information[END_REF] is defined as follows,

I α (q, p) = 1 α -1 log 2 N k=1 q α [k] p α-1 [k] , (2)
and it tends to the Kullback I divergence [START_REF] Lin | Divergence measures based on the shannon entropy[END_REF] as α tends to one. We can thus consider this class of measures to obtain different divergences as for the Kullback I one, and apply them to the spectrogram frames: as long as we can give an interpretation to the α parameter, this class of measures offers a largely more detailed information about the time-frequency representation of the signal.

Biasing spectral coefficients through the α parameter

To show the biasing introduced on the spectral coefficients by the α parameter we consider a simplified model of a spectrogram composed by a variable amount of large and small coefficients. We realize a vector U of length N = 100 generating numbers between 0 and 1 with a normal random distribution; then we consider the vectors

U M , 1 ≤ M ≤ N such that U M [k] = U [k] if k ≤ M U[k] 20 if k > M
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 [U 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. This means that increasing α we emphasize the difference between the entropy values of a peaky distribution and that of a nearly flat one. In the next section we will give an example of the exploiting of this important property, but care should be taken when applying this criterium: small coefficients in a spectrogram include signal components of weak amplitude as well as noise; choosing an extremely small α the change detection robustness to noise level significantly decreases.

The entropy prediction method

The second method we introduce is not based on a divergence criterium, but on entropy itself. We first give the definition of Rényi entropy for the case of distribution obtained with a discretization of their continuous version [START_REF] Baraniuk | Measuring Time-Frequency Information Content Using the Rényi Entropies[END_REF]: let PS f be a normalization with unitary sum of a discrete spectrogram, then the Rényi entropy of PS f is

H α [PS f ] = 1 1 -α log 2 n,k (PS f [n, k]) α + log 2 (ab) , (3)
where k varies between 1 and the FFT size N while n varies in the time interval where the evaluation has to be performed, according to the time grid.

H α [PS m ] = H α [PS k ] = H , (4)
H α [PS m , PS k ] = H + 1 . (5
As a rearrangement we mean a reordering of the frame coefficients, thus including the case of equality between frames. The idea of our method is that given the entropy of a certain signal segment H α (PS m , ..., PS m+L ) composed by L contiguous frames, we can predict H α (PS m , ..., PS m+L+1 ) supposing the new frame to be spectrally coherent and thus iso-entropic with the previous ones. If on the other hand the entropy value of the new segment largely differs from the predicted value, we assume the new frame to be incoherent with the previous and so a spectral change is detected. There is here a strong assumption concerning the equivalence between the concept of spectral coherence and the fact that two frames are obtained with a rearrangement of their elements; according to the specific needs in the applications, the detection criteria can be based on variations of the property (6) to take into account different definitions of spectral coherence: for example, considering a set of admissible operations on the analysis coefficients in relation with the entropy variation that they provide.

ALGORITHMS AND EXAMPLES

We show here an application of the detection algorithms with the measures defined: the first algorithm we analyze has the same operations for the K divergence and Rényi information (2): we calculate the spectrogram of a signal with a 1024-samples Hamming window, 768-samples overlap and 2048-points FFT size; we obtain a mean spectrum taking the first 20 analysis frames, and calculate the divergence of the next frame with respect to the mean spectrum. Once we have the first divergence value, we shift the mean spectrum of one analysis frame and consider the following 20 frames, then calculate the divergence between the new mean spectrum and the following frame. At this point, if the ratio between the last divergence value and the previous exceeds a certain threshold, a change is detected at the incoming frame; otherwise the procedure goes on. The second algorithm is a variation of the first one based on entropy prediction: once obtained the spectrogram of the signal, we calculate the Rényi entropy of the vector composed of its first 6 analysis frames; then we consider the next frame and set the predicted entropy value according to [START_REF] Foote | Automatic audio segmentation using a measure of audio novelty[END_REF]. We calculate the actual entropy of the vector obtained adding the new frame to the previous ones, and if the ratio between this value and the predicted one exceeds a certain threshold, a change is detected. Then the procedure goes on as in the previous case.

The Rényi prediction shows a slightly better accuracy at the price of a higher computational cost; this is due to the larger dimensions of the vectors managed in the entropy calculus. The tuning of the α parameter gives interesting results: as seen in figure 1, higher values rise the difference between the entropies of a peaky distribution and a flat one; thus we expect in general a more refined detection increasing α, leaving the threshold unchanged. The signal we analyze is a speech fragment of a mail voice in French language, Vénitienne et lui suce la bouche un quart d'heure. We assume two references: an automatic phoneme segmentation for French language based on Hidden Markow Model [START_REF] Lanchantin | Automatic phoneme segmentation with relaxed textual constraints[END_REF], and a voicedunvoiced classification obtained with a PSOLA-based algorithm [START_REF] Mattheyses | Robust Pitch Marking for Prosodic Modification of Speech using TD-PSOLA[END_REF]: they identify the major spectral changes in this kind of signal, so we expect our detection to confirm them. We are not interested in whether a marker belongs to one selection or the other, as this could be established in a later classification step. As we see at the top of figure 2, the Rényi prediction with α = 0.2 identifies all the voiced-unvoiced transitions in both senses except at time 2.5, and a large part of phonemes. If we need a less refined detection, setting the α parameter to 0.05 (bottom of figure 2) preserves the detection of all the unvoiced-voiced transitions, while discarding all the phonemes and the voiced-unvoiced transitions. Both the measures provide a better detection with respect to the K divergence, which shows a higher number of unexpected markers.

Fig. 1 .

 1 Fig. 1. Rényi entropy evaluations of the U M vectors with varying α.

Fig. 2 .

 2 Fig. 2. Detections obtained with different methods on a speech fragment in French language; cross markers: Rényi entropy prediction method, on top with α = 2, at the bottom with α = 1.1; square markers: K divergence; diamond markers: HMM-based phoneme segmentation method; bold line: PSOLA voiced-unvoiced classification, 0 is unvoiced.

  The term log 2 (ab) takes into account the time and frequency steps a and b of the lattice Λ used to sample the continuous spectrogram: this guarantees the stability of the discrete entropy when changing the hop and the FFT sizes, as long as the sampling grid is dense enough in the time-frequency plane. For the entropy of a single analysis frame we write H α [PS f ] = H α [PS m ] as above, where m is the time index of the analysis frame considered; for L different analyses frames, we write H α [PS f ] = H α [PS m , ..., PS m+L ] to focus on the individual vectors. The following properties are straightforward by the definitions.

Proposition 2.1 (Rényi entropy prediction). Consider a spectrogram PS f and a rational number α ≥ 0.

(i) Let PS m be an analysis frame in PS f ; if PS k is obtained rearranging the elements of PS m , then

RÉNYI INFORMATION MEASURES FOR SPECTRAL CHANGE DETECTION

Marco Liuni 1 2 , Axel Röbel 2 , Marco Romito 1 , Xavier Rodet 2