Kévin Huguenin
email: kevin.huguenin@epfl.ch

Anne-Marie Kermarrec
email: anne-marie.kermarrec@inria.fr

Konstantinos Kloudas
email: konstantinos.kloudas@inria.fr

François Taïani
email: f.taiani@lancs.ac.uk

Content and Geographical Locality in User-Generated Content Sharing Systems

Keywords: H.3.2 [Information Systems]: Information Storage and Retrieval-Information Storage Measurement, Algorithm, Design

User Generated Content (UGC), such as YouTube videos, accounts for a substantial fraction of the Internet traffic. To optimize their performance, UGC services usually rely on both proactive and reactive approaches that exploit spatial and temporal locality in access patterns. Alternative types of locality are also relevant and hardly ever considered together. In this paper, we show on a large (more than 650,000 videos) YouTube dataset that content locality (induced by the related videos feature) and geographic locality, are in fact correlated. More specifically, we show how the geographic view distribution of a video can be inferred to a large extent from that of its related videos. We leverage these findings to propose a UGC storage system that proactively places videos close to the expected requests. Compared to a caching-based solution, our system decreases by 16% the number of requests served from a different country than that of the requesting user, and even in this case, the distance between the user and the server is 29% shorter on average.

INTRODUCTION

Over the last few years, users have become the most prolific content generators on the Web, prompting the phenomenal success of user-generated content (UGC) sharing sites such as YouTube [START_REF] Cha | You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System[END_REF][START_REF] Gill | YouTube Traffic Characterization: A View From The Edge[END_REF]. This rapid growth combined with the never fulfilled user demand for better quality, makes serving UGC to an increasing number of users all around the world a daily engineering feat [START_REF] Saxena | Analyzing Video Services in Web 2.0: A Global Perspective[END_REF]. To this end, UGC sharing sites rely on Content Delivery Networks (CDNs) to place content close to consumers. To achieve this goal, CDNs employ both proactive approaches that rely on a priori knowledge (e.g., it is likely that a French-speaking video will be accessed mostly from French-speaking countries) and reactive ones where the history of a given video is analyzed to predict its future requests [START_REF] Huang | Understanding Hybrid CDN-P2P: Why Limelight Needs its Own Red Swoosh[END_REF][START_REF] Chen | On the Server Placement Problem of P2P Live Media Streaming System[END_REF][START_REF] Yin | Enhancing CDN with P2P[END_REF].

Interestingly, beyond traditional forms of locality that account for each content item independently, recent studies have shown that UGC viewing patterns are significantly influenced by the fact that content in these sites is no longer independent but is organized in a content graph. In YouTube, this content graph is embodied by the lists of "related videos" present on each video's page, and its influence on the viewing behavior of users has been clearly documented [START_REF] Khemmarat | Watching User Generated Videos with Prefetching[END_REF][START_REF] Zhou | The Impact of YouTube Recommendation System on Video Views[END_REF].

In this paper we study the geographic viewing patterns of UGC and how they are affected by the content graph. Our analysis on a novel YouTube dataset shows that (i) related videos tend to have correlated geographic viewing patterns, with most of their views coming from the same countries, and (ii) popular videos tend to have their views more uniformly spread across more countries than less popular ones. The latter category accounts for the vast majority of YouTube's content and have their views coming from a small number of countries.

Building on these insights, we propose DTube, a system that accurately predicts the origins of a video's future views by looking at its position in the content graph and proactively places its replicas close to its expected consumers. Although the impact of content locality, i.e. proximity in the content graph, on a video's views and geographically concentrated viewing patterns have been studied independently [START_REF] Scellato | Track Globally, Deliver Locally: Improving Content Delivery Networks by Tracking Geographic Social Cascades[END_REF][START_REF] Zhou | The Impact of YouTube Recommendation System on Video Views[END_REF][START_REF] Brodersen | YouTube Around the World: Geographic Popularity of Videos[END_REF], to the best of our knowledge, this is the first work that considers both aspects to optimize the placement of UGC.

We show that our system manages to deliver videos over shorter distances than a standard caching-based solution, thus reducing network latencies and improving user experience. In particular, DTube can decrease the proportion of remote requests, i.e., that cannot be served by a node in the same country as the requesting users, by as much as 16%.

We also show that DTube can decrease the average distance between users and stored videos by up to 29% for remote requests.

The rest of this paper is organized as follows. In Section 2 we show that content and geographic locality are correlated in YouTube. In Section 3 we present DTube's replica placement algorithm and we report on its evaluation in Section 4. We survey related work in Section 5 and conclude in Section 6.

LOCALITY IN UGC

Using a YouTube dataset we crawled in March 2011, we show that there is a strong correlation between the geographic distribution of a video's views and that of its related videos. We then explore how this correlation can be used to predict the geographic distribution of a video's future views.

Dataset Description

We crawled our own dataset from YouTube, during the first three weeks of March 2011, using snowball sampling with an initial set consisting of the 10 most popular videos for 25 different countries. For each video, we collected three attributes: (i) its list of related videos as provided by YouTube, (ii) its total number of views, and (iii) its View Source Vector (VSV). The VSV of a video represents how many views this video received from each country in the world. For most of the videos, the VSV is available, on the statistics page, as a color map (Fig. 1) generated by a specific URL (charts.apis.google.com) containing (country, #views) couples encoded in Google's Simple Encoding Format. In our experiments, we extracted the actual VSVs from these URLs. Tab. 1 shows the distribution of the views (top 8 countries) at the granularity of a country, over the whole dataset. The original dataset contained 1, 063, 844 videos. We removed the videos with no VSV, and filtered out noncrawled videos from the related video lists. This left us with 689, 265 videos, each having 8 related videos on average, for a maximum of 25 related videos allowed in YouTube. 1 In the following, we use the view-per-country information 1 Because the geographic information in our dataset is given

Table 1: Geographic distribution of views at the granularity of a country (top 8 countries).

contained in the VSVs to analyze the geographic distribution of views in our dataset. Our goal is to explore the feasibility of a geographically-driven proactive placement mechanism that places videos in countries where they are likely to be viewed.

Popularity vs. Geographic Distribution

We first investigate the link between a video's overall popularity and the geographical distribution of its views. To this end, we partition our dataset into six categories based on a video's number of views. The distribution of videos shown on Tab. 2 confirms earlier analysis [START_REF] Brodersen | YouTube Around the World: Geographic Popularity of Videos[END_REF][START_REF] Cha | You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System[END_REF], highlighting a longtail distribution of views. Very popular videos (categories C5 and C6) represent less than 1% of videos while accounting for almost 25% of all views. Because of the long tail, the bandwidth cost of "unpopular" videos is however far from being negligible: The 3 least popular categories (C1, C2, C3, or 95.2% of all videos) still represent more than 30% of the views.

Figure 2: Geographic cumulative distribution of views for various popularity categories

To analyze the geographic distribution of views for each category, we compute the average geographic spread of video views as follows. For a given video, we sort the countries of its VSV in decreasing order according to the proportion of views originating from each country. We then compute the cumulative distribution of views of each video and plot at the granularity of a country, we conduct our analysis at the same granularity throughout the paper. the average over each popularity category (Fig. 2). A point (n, m) on the graph means that the n top countries for videos in this category account for m% of the total number of views.

Fig. 2 clearly shows that the views of niche videos (C1, less than 10,000 views) are geographically highly concentrated: 80% of all views for videos in C1 come from less than 15 countries. This phenomenon fades out as the popularity of videos increases, to reach an almost uniform global distribution for extremely popular videos (C6).

Yet, this concentration effect remains relatively strong for all videos up to 100M views (categories C1-C5, 96.9% of all views). This shows that a proactive placement mechanism could gain from accurately predicting the top n countries from which a video's views originate. For instance, for videos in C3 (between 100,000 and 1M views, 25.18% of all views), proactively placing video replicas in (or close to) the top 25 countries would cover 80% of all views.

We further study the geographic spread of the origins of the views by taking into account the distances between the main sources of views. The motivation behind this experiment is that it is easier to serve a video with low latency, with a single replica, for users in France and in Switzerland than for users in the UK and in India. For each video, we compute the average of the pairwise distance between the main sources of views (i.e., the top country covering 80% of the views), weighted by the proportion of views each country is responsible for. For instance, for a video viewed 1, 000 times, whose three main sources are US (500 views), UK (200 views), and Japan (100 views), our metric is:

(0.5 + 0.2)d(us, uk) + (0.2 + 0.1)d(uk, jp) + (0.1 + 0.5)d(jp, us) (0.5 + 0.2) + (0.2 + 0.1) + (0.1 + 0.5) ,
In our dataset, we observed this average distance to be 26% less for unpopular videos (∼5, 200 km) than for popular ones (∼7, 000 km).

Geographic vs. Content Locality

To explore how the top n countries of a video might be predicted, we now turn to the relation between content locality and geographic locality. For each video, we compute the Spearman correlation coefficient between its sorted VSV (i.e., the list of all countries sorted by decreasing number of views) and that of each of its related videos, and plot it as function of the rank in the list of related videos (see Fig. 3). The Spearman coefficient captures the correlation between the rank of countries in two sorted VSVs, taking into account the permutations of ranks. The closer the absolute value of the coefficient to 1, the more correlated the lists. In our dataset, this correlation is relatively high for all related videos (in 0.64-0.68, Fig. 3) and decreases with the rank. This means that a video's VSV can be inferred from that of its related videos, and that the first related videos are the best candidates.

In order to see if the above finding can be translated into an efficient mechanism for proactively placing video replicas, we conduct the following experiment. For a given video V and its first related Rel(V ) [START_REF] Agarwal | Volley: Automated Data Placement for Geo-Distributed Cloud Services[END_REF], we compute for a given number m of replicas, the percentage of views covered by placing them on the first m countries of the VSV of Rel(V ) [START_REF] Agarwal | Volley: Automated Data Placement for Geo-Distributed Cloud Services[END_REF], normalized by the percentage of views covered by placing the replicas on the first m countries of the actual VSV of V . The later corresponds to an ideal case where the placement mechanism knows in advance where the views will come from. The results are presented in Fig. 4: even for a small number of replicas, this simple prediction mechanism can accurately follow the actual geographic distribution of the views of a given video. For instance, 85% of the views covered by the first 5 countries of V 's VSV are covered by the first 5 countries of Rel(V ) [START_REF] Agarwal | Volley: Automated Data Placement for Geo-Distributed Cloud Services[END_REF]'s VSV. In summary, unpopular videos, which represent a large proportion of the YouTube dataset, have (i) most of their views originating from a few countries which (ii) spread in a limited region, thus foreseeing a great potential for geographic locality-aware data placement. Furthermore, the geographic distribution of views of a video is strongly correlated with that of its related videos. This implies that the geographic distribution of views of a video can be predicted, but most importantly, it makes the case for a placement mechanism in which videos close in the content graph are stored geographically close to one another.

DTUBE

Building on the insight from the previous section, we propose DTube, a proactive placement mechanism that places videos close to their future requests, extracting geographical patterns from the content graph.

System model

We consider a UGC sharing system that uses geographically-distributed nodes as its storage infrastructure. Our findings hold for both residential gateways [START_REF] He | A Performance Evaluation of Scalable Live Video Streaming with Nano Data Centers[END_REF][START_REF] Marcon | Sharing Social Content from Home: A Measurement-driven Feasibility Study[END_REF], and peer-assisted CDN systems [START_REF] Huang | Understanding Hybrid CDN-P2P: Why Limelight Needs its Own Red Swoosh[END_REF].

DTube assumes the existence of a catalog service that holds, for each video, the location of its replicas, its current View Source Vector and its meta-data including the list of its related videos. This service is used to retrieve up-to-date meta-data about videos. We further assume the existence of a recommendation algorithm that dynamically computes videos' lists of related videos and updates the catalog accordingly.

Video placement

The key steps of DTube's placement mechanism are depicted in Fig. 5. When a new video V is uploaded to the system (a), YouTube's recommendation mechanism computes the related videos list, thus making it part of the content graph (c). DTube then estimates V 's main future view sources, VSV(V ) (d) which is later used to place replicas of V on storage nodes. is a system parameter called replication factor and corresponds to the minimum number of replicas a video must have to ensure durability in case of storage node failure. In Section 2 we showed that the higher the position of a video in V 's related videos list, the higher the correlation between its V SV and the one of V . Applying this finding, we compute VSV(V ) = VSV(Rel(V ) [START_REF] Agarwal | Volley: Automated Data Placement for Geo-Distributed Cloud Services[END_REF]) (d) by obtaining the VSV of its first related video (b) from the catalog (d). One may envision a more sophisticated prediction strategy that combines the VSV of several related videos. Yet simple, our strategy performs well (see Section 4).

Each of the replicas of V attracts a replica of each of V 's related videos Rel(V ) (e). We call this bundle of |Rel(V )|+1 videos a package, with V being a primary replica and the others, secondary replicas. This package mechanism creates a coupling between content and geographic locality, as related videos are placed on the same node. In addition, a coupling is established between a video's number of replicas (primary and secondary) and its in-degree in the content graph. This is a desirable property as it is shown in [START_REF] Zhou | The Impact of YouTube Recommendation System on Video Views[END_REF] that there is a strong correlation between the view count of a video and those of its top referrer videos, i.e., its in-degree.

Each package of a video V is placed on a node in each of the first countries of VSV(V ) (d) as most views are expected to come from these countries. To minimize transfer and storage costs, only replicas of the videos that do not exist in the country are transferred. In addition, to evenly balance the load among the nodes in the system, for a node to be eligible to store a new package, the number of videos it already stores must be lower than the average storage load over all nodes (this value can be computed with a standard averaging gossip protocol). Finally, copies of the package are transferred (i) to the selected nodes (g).

EVALUATION

In this section, we evaluate through simulations the performance of DTube with respect to the geographic distance between users and the storage nodes serving the videos and compare it against a system that employs reactive caching on top of persistent storage.

Evaluation Setup

We distribute the storage nodes in countries according to the proportion of views originating from this country as observed in our dataset (see Tab. 1). We set the number of storage nodes to 10,000 and we consider the videos from our dataset, with the corresponding popularity and the contentgraph induced by the related video feature.

We generate synthetic view traffic based on individual users' behavior, using the model proposed in [START_REF] Zhou | The Impact of YouTube Recommendation System on Video Views[END_REF], with the popularity values from our dataset: We consider a number of users (50, 000 in our experiments), distributed across all countries as storage nodes according to the geographic distribution of views observed in our dataset (see Tab. 1). The number of videos a user watches during a session is picked at random, with an average value of 10. The first video V a user watches is selected from the whole set of videos according to the probability of this video being watched in her country, i.e., the number of views for V originating from her country divided by the total number of views originating from her country (for all videos). Each subsequent video she watches is selected among the related videos of the previous video, excluding already viewed ones. The probability of a video being picked is set to be inversely proportional to the video's rank in V 's list of related videos, following a Zipf distribution.

DTube and Alternatives

We compare DTube against standard caching. For DTube, we use the placement algorithm as described in Section 3. In addition, we implement and evaluate several variations of DTube to identify the performance gains conveyed by the different mechanisms involved, namely without the use of packages (Partial DTube) and using the actual VSV of the video (Ideal DTube) instead of that of its first related video. Ideal DTube can be thought of as an upper bound on DTube's performance and reflects how the efficiency of the VSV prediction mechanism (evaluated in Section 2) translates in practice with respect to the viewer experience. In our experiments, videos are served from the node closest to the user.

As for caching, we consider a storage infrastructure composed of persistent storage nodes (e.g., YouTube servers) and CDN caching nodes (e.g., Akamai servers). The persistent storage nodes hold a complete copy of the YouTube dataset, thus ensuring durability. Videos are only served by CDN nodes, the caches of which are populated in a reactive fashion, based on the users' view traffic: Consider a user located in a given country who requests a given video. If the video is stored on a CDN node in this country, it is served from this node to the user. If not, the video is first fetched from a persistent node to a random CDN node (with free storage space) in the country and then served. If none of the CDN nodes in the country has sufficient free storage space to store the video, we apply LRU cache replacement: the least recently used video is replaced by the new entry.

Evaluation Results

We evaluate and compare the performance of all placement strategies with respect to the geographic distance between the user and the node serving the video. More specifically, we look at (i) the out-country hit-rate, that is the proportion of requests that are served from a storage node (i.e., a gateway or a CDN node) located in a different country than the user, and (ii) the distance between the user and the storage node when the video is served from a different country. We assume that networking infrastructure is usually well integrated in each country, thus in-country hits are likely to encounter better network quality and that geographic distance is a good indicator of transfer latency.

In order for DTube and caching to be comparable, we use the same storage space in both. More specifically, for a given replication factor , we first run simulations with DTube. Because it makes use of packages, the average number of replicas R per video is larger than . We therefore run simulations with caching, for a system composed of persistent storage nodes and CDN nodes with a storage space of (R-)×(total number of videos)/(number of CDN nodes), which corresponds to the same total storage space as for DTube. We evaluate our metrics at steady state, i.e., when all the caches of all CDN nodes are full. DTube decreases the proportion of out-country request from 0.25 to 0.21, that is a 16% improvement. By comparing DTube to Ideal DTube and Partial DTube, we observe that (i) the use of packages accounts for a significant part of DTube's performance, (ii) the estimation of a video's VSV from that of its related videos (i.e., based on the content graph) incurs only a little decrease in performance compared to an omniscient solution in which the actual VSV is known in advance. This illustrates the synergy between our geographic prediction and the use of packages. Similar results can be observed in Fig. 7, which depicts the average distance between the user and the storage node serving the video for out-country requests. For instance, with an average of 30 replicas per videos, DTube reduces the average distance by 29%. Note that the distance remains relatively high as the distance to the closest country can be large, e.g., ∼2000km between the US and Canada which are the two main sources of views.

RELATED WORK

YouTube has generated numerous studies on user behavior and video characteristics: Cha et al. propose to use a video's history to predict its future demand [START_REF] Cha | You Tube, Everybody Tubes: Analyzing the World's Largest User Generated Content Video System[END_REF], while Zhou et al. in [START_REF] Zhou | The Impact of YouTube Recommendation System on Video Views[END_REF] study the impact of a video's position in the content graph on its popularity. In [START_REF] Brodersen | YouTube Around the World: Geographic Popularity of Videos[END_REF], Brodersen et al. analyze the correlation between popularity and geographical locality. Finally, Torres et al. [START_REF] Torres | Dissecting Video Server Selection Strategies in the YouTube CDN[END_REF] evaluated YouTube's CDN performance.

In [START_REF] Marcon | Sharing Social Content from Home: A Measurement-driven Feasibility Study[END_REF], the authors show the feasibility of building a system like YouTube, using residential gateways. The concept of CDNs composed of gateways has been investigated for decentralized video storage and delivery in [START_REF] He | A Performance Evaluation of Scalable Live Video Streaming with Nano Data Centers[END_REF]. Peer-assisted CDNs also received a great deal of attention lately [START_REF] Huang | Understanding Hybrid CDN-P2P: Why Limelight Needs its Own Red Swoosh[END_REF][START_REF] Chen | On the Server Placement Problem of P2P Live Media Streaming System[END_REF][START_REF] Yin | Enhancing CDN with P2P[END_REF]. However, none of the proposed systems leverages the content graph.

In [START_REF] Scellato | Track Globally, Deliver Locally: Improving Content Delivery Networks by Tracking Geographic Social Cascades[END_REF], monitoring social cascades in online social networks is proposed to predict a video's future view pattern. Kangasharju et al. [START_REF] Kangasharju | Optimizing File Availability in Peer-to-Peer Content Distribution[END_REF] investigate optimal placement strategies in P2P content networks to maximize availability in content communities. Tan et al. [START_REF] Tan | Adaptive Content Placement for Peer-to-Peer Video-on-Demand Systems[END_REF] investigate the same problem for VoD but focus on upload bandwidth.

Volley [START_REF] Agarwal | Volley: Automated Data Placement for Geo-Distributed Cloud Services[END_REF] leverages the content graph to place the data so that the perceived latency is decreased. But contrary to DTube, there is only one copy of each content item as data durability is not considered. NetTube [START_REF] Cheng | NetTube: Exploring Social Networks for Peer-to-Peer Short Video Sharing[END_REF] is a peer-assisted VoD system that leverages the content graph of UGC videos through social-aware pre-fetching and overlays to optimize swarming and decrease start-up delays. Finally, SPAR [START_REF] Pujol | The Little Engine(s) That Could: Scaling Online Social Networks[END_REF] is a social partitioning and replication system that achieves one-hop replication of user profiles in social networks.

CONCLUSION

In this paper we have highlighted the correlation between content locality and geographic locality in User Generated Content (UGC). More precisely, we have shown using a large YouTube dataset that related videos present similar geographic viewing patterns and that, except for extremely popular videos, video views are concentrated in a limited number of countries.

This coupling between content and geographic locality in UGC system has led us to propose DTube, a decentralized storage infrastructure which proactively places content close to their future requests leveraging on the videos' positions in the content graph.

In the future, we plan to investigate the serving part of our UGC system: more specifically, how to adapt the number of replicas and bandwidth allocation to the popularity of the videos and how to efficiently prefetch and serve videos from multiple storage nodes. We also plan to consider how caching and geographic view prediction can be combined, e.g., by exploring how predicted views might be used in the cache's replacement strategy.

Figure 1 :

 1 Figure 1: Geographic distribution of the origin of views for a sample YouTube video.

Country

  US CA GB BR JP DE PL AU Prop. of views (%) 6.6 3.1 3.0 3.0 2.6 2.5 2.2 2.2

  in the list of related videos spearman coefficient

Figure 3 :

 3 Figure 3: Spearman correlation coefficient between a video's geographic distribution of views and that of its related videos, as a function of their rank in the list of related videos

Figure 4 :

 4 Figure 4: Views covered by placing replicas of a video V in top-countries of the VSV of V 's first related video, normalized by the number of views covered when using V 's actual VSV.

Figure 5 :

 5 Figure 5: Overview of DTube's placement strategy.

Figure 6 :

 6 Figure 6: Proportion of out-country requests with DTube and caching.

Fig. 6

 6 depicts the out-country hit-rate for the different versions of DTube and caching. It can be observed that for larger values of the average number of replicas per videos, DTube outperforms the caching-based solution. For instance, for an average number of 30 replicas per video, for out-country hits (km) average number of replicas per video DTube Partial DTube (no packages, estimated VSV) Ideal DTube (packages, actual VSV) Caching (LRU replacement)

Figure 7 :

 7 Figure 7: Average distance to storage node for outcountry requests with DTube and caching.

Category # views % of videos % of total views

	C 1 C 2 C 3 C 4 C 5 C 6	[0, 10 4 ] (10 4 , 10 5 ] (10 5 , 10 6 ] (10 6 , 10 7 ] (10 7 , 10 8 ] (10 8 , ∞)	4 2 .0 3 3 .5 1 9 .7 4 .4 0 .3 0 .04	0 .49 5 .10 2 5 .18 4 5 .02 2 1 .10 3.10

Table 2 : Popularity categories and statistics

 2

Acknowledgment

This work has been partially funded by the ERC Starting Grant GOSSPLE number 204742.


Imen Samaali

Monia Turki-Hadj Alouane

Gaël Mahé

TEMPORAL ENVELOPE CORRECTION FOR ATTACK RESTORATION IN LOW BIT-RATE AUDIO CODING

At reduced bit rates, the audio compression affects transient parts of signals, which results in pre-echo and loss of attack character. We propose in this paper an attacks restoration method based on the correction of the temporal envelope of the decoded signal, using a small set of coefficients transmitted through an auxiliary channel. The proposed approach is evaluated for single and multiple coding-decoding, using objective perceptual measures. The experimental results for MP3 and AAC coding exhibits an efficient restoration of the attacks and a significant improvement of the audio quality.

INTRODUCTION

In perceptual coders at low bit-rates, variations in the masking threshold from one frame to the next leads to different bit assignments. An artefact known as pre-echo may appear in signals with transients (see Figure 1). The silence before an attack may be affected by a relatively high quantization noise, since the masking threshold is computed using the part of the frame after the attack [START_REF] Mahieux | High-quality audio transform coding at 64 kbps[END_REF] [START_REF] Reiss | Audio Issues In MIR Evaluation[END_REF]. However, if the pre-echo is short enough, it is post-masked by the attack. The phenomenon of pre-echo is amplified by multiple coding-decoding: the quantization noise piles up at each cycle and may become audible.

Transient signals are affected by another artefact when coding at low bit-rates. Only a small low-frequency band of the signal is fully transmitted, whereas medium frequencies are restored at the decoder without phase information and higher frequencies are simply forgotten. This smoothes attacks resulting in a reduce of the percussive quality of sounds.

In order to reduce or eliminate pre-echo and enhance the audio quality, some techniques with different complexities are developed in the literature [START_REF] Mahieux | High-quality audio transform coding at 64 kbps[END_REF]. These techniques are based on the use of an adaptive window selection algorithm to switch between long and short transform window. Long windows offer higher prediction gain, and better frequency resolution, while short windows reduce the length of pre-echo.

Another technology, the "Temporal Noise Shaping" (TNS) [START_REF] Herre | Temporal Noise Shaping, Quantization and Coding Methods in Perceptual Audio Coding: a Tutorial Introduction[END_REF], used in the AAC coder, aims at resolving the problem of Temporal Masking. This approach allows the encoder to control the temporal fine structure of the quantization noise. In the same way as temporal predictive coders reshape the quantization noise spectrum, the principle of TNS, is to replace the spectral coefficients to be quantized by the This work is part of the WaRRIS project granted by the French National Research Agency (project n ¡ ANR-06-JCJC-0009) . coder with their frequency prediction residual (which flattens the temporal envelope). In the decoder, the inverse prediction filter is applied to the residual. As a consequence, the temporal shape of the quantization error is adapted to the temporal shape of the audio signal. For the MP3 coder, a similar correction is performed by the "Temporal Masking" (TM) technology [START_REF] Sinaga | Wavelet Packet Based Audio Coding Using Temporal Masking[END_REF]. Although these techniques reduce significantly the preecho phenomenon, the problems of temporal masking and attacks smoothing remain harmful for some transient signals, such as castanet, glockenspiel, triangle or certain types of speech signals. In this paper, we propose a novel method aiming at restoring attacks in coded-decoded signals. The idea is to perform a correction of the temporal envelope of the coded-decoded signal, using a small set of parameters (describing the temporal envelope of the original signal) transmitted over a very low bit-rate ( ¢ 1 kbps) auxiliary channel which we suppose to have (an audio watermarking channel for example).

This paper is structured as follows: in section 2, we present the new approach dedicated to attack restoration for the quality enhancement of audio decoded signals. Section 3 presents a performance evaluation of the proposed algorithm in the case of simple and multiple successive encodings (codings in tandem).

ENVELOPE CORRECTION

The proposed method is based on the correction of the temporal envelope of the decoded signal. The restored audio signal, xt , is given at time t by: x©t x©t dec ê©t ê©t dec [START_REF] Mahieux | High-quality audio transform coding at 64 kbps[END_REF] where x©t dec is the decoded audio signal, ê©t is an estimate of the temporal envelope of the original signal, and ê©t dec is the temporal envelope of the coded-decoded signal.

The correction approach constitutes a post-processing performed at the decoder. For this purpose, crucial parameters required for the temporal envelope estimation are extracted by the encoder and transmitted to the decoder through an auxiliary channel. Figure 2 illustrates the basic structure of the proposed approach. In addition to the standard coder/decoder blocks, the proposed system includes several components:

Frame characterization/Transient localization: characterizes the frame type as transient or not. In particular, for the transient frames, a localization of the attack's time position is performed. Temporal envelope coding and vector quantization: based on linear prediction in frequency domain. Audio signal correction: for the restoration of the audio signal according to the relation presented in equation 1.

Transient detector

Characterization of frame type:

To detect transient frames, we use the technique described in [START_REF]Advanced Audio Coding (AAC) part[END_REF]. After high-pass IIR filtering with the transfer function

H ©z 07548 ©z 1 z 05095 (2)
each frame of 1024 samples is divided into 8 sub-blocks of 128 samples and the energy of each sub-block is computed by summing up the squared samples. An attack is detected if one of these sub-block energies exceeds a sliding average of the previous energies by a constant factor attackRatio and is greater than a constant energy level minAttackNrg 10 3 [START_REF]Advanced Audio Coding (AAC) part[END_REF]. Figure 3: The audio signal (violon+castanet) and its corresponding attack ratio coefficients Figure 3 illustrates the efficiency of the proposed method. The attack ratio coefficient corresponding to the transient frame (Frame 2) exceeds the threshold fixed to 10 as in [START_REF]Advanced Audio Coding (AAC) part[END_REF].

Transient localization:

The method used to detect the transient time position is based on the stationarity index which corresponds to the Kolmogorov distance measured between the time frequency representation (TFR) of the signal at different times [START_REF] Larbi | Audio Watermarking: A Way To Stationarize Audio Signals[END_REF]. The stationarity index is given by:

SI ©t p τ 0 ∞ f ∞ NI 1 ©t ; τ f NI 2 ©t ; τ f d f dτ (3) NI 1 ©t ; τ f and NI 2 ©t ; τ f represent a normalization of re- spectively subimages I 1 ©t ; τ f and I 2 ©t ; τ f : I 1 ©t ; τ f T FR©t p ! τ f ; (4) I 2 ©t ; τ f T FR©t ! τ f (5)
The parameter p delimits the considered analysis duration at each instant t and allows the selectivity/sensivity control of the SIs: a high value of p leads to smoother SIs. As in [START_REF] Larbi | Audio Watermarking: A Way To Stationarize Audio Signals[END_REF], p is fixed to 20. As illustrated in Figure 4, the peak of SI corresponds to the attack position.

Attack position coding:

Since coding directly the transient position would require a high bit-rate, we propose to code the difference between the actual attack position given by the original frame and the attack position computed from the coded/decoded frame. A 6 bits scalar quantization technique is used for this purpose.

Temporal envelope ARMA modeling

The reduced bit-rate of the auxiliary channel implies a compact representation of the transmitted temporal envelope, through a small set of coefficients for each frame. The proposed coding approach is based on linear prediction in frequency domain providing an approximation of the temporal envelope of a signal, specifically the squared Hilbert envelope [START_REF] Athineos | Frequency-Domain linear Prediction For Temporal Features[END_REF]. The block diagrams of the temporal envelope estimation is depicted in Figure 5.

The Discrete Cosine Transform of x©t is modeled by an ARMA(p,q) model. The ARMA model was here preferred to the classically used AR model, because it ensures an accurate representation of the spectral envelope by means of a reduced number of coefficients. The autoregressive parameters a i i 1 p, of the ARMA(p,q) model are estimated by minimizing the mean square prediction error defined as follows:

H "z # $ ∑ q i%0 b i z& i 1'∑ p i%1 a i z& i ARMA(p,q) ( DCT ( x"t # ê"t # b i ) X "k # q p a i
E pre ©k X ©k ! p ∑ i1 a i X ©k i (6)
where X ©k DCT ©x ©t . The moving average parameters b i i 1

q, are computed by a Prony method.

An estimation of the temporal envelope of x©t is therefore given by: ê©t H ©e jwt [START_REF] Athineos | Frequency-Domain linear Prediction For Temporal Features[END_REF] where

H ©z ∑ q i0 b i z i 1 ! ∑ p i1 a i z i H b ©z H a ©z (8)
Each frame of 2048 samples is divided into two subframes, each modeled with an ARMA(2,3). For non transient frames, each sub-frames has 1024 samples. Transient frames are divided according to the transient position.

Figure 6 illustrates similarity between the estimated envelope and the original one for a castanet sound sampled at 44.1 kHz.

ARMA to LSF transformation

After the ARMA parameters are estimated, they must be coded and transmitted through the auxiliary communication channel. The autoregressive coefficients (AR) are characterized by large dynamic range and would require many bits per coefficient for accurate coding. In addition, small changes in the AR coefficients may result in instability of the synthesis filter. For these reasons, it is necessary to transform the The AR filter H a ©z of order p, given by equation 8, can be represented by :

H a ©z 1 2 0 P©z ! Q©z 1 ( 9
)
where P©z and Q©z are even and odd symmetric filters respectively. Their roots, z i e jθ i , lie on the unit circle [START_REF] Na | The High-speed LSF transformation Algorithm in CELP Vocoder[END_REF]. The 2θ i i 1

N 3 represent the Line Spectrum Frequency (LSF) coefficients.

To transform the Moving Average (MA) parameters into the LSF coefficients, the MA filter H b ©z (equation 8) must be modified as follows

H b ©z 1 ! q ∑ i1 b4 i z i (10)
where b4 i b i b 0 , i 1 q. In the decoder, the value of b 0 is estimated from the decoded signal.

Vector quantization

For each sub-frame, a vector grouping 5 LSF coefficients is coded using a classical vector quantization technique. The codebook C of a dimension K 5L, (K=256 and L=5 here), is obtained by training on a database of approximately 100 5K vectors taken from various kinds of audio signals. It can be computed by the Lloyd-Max algorithm [START_REF] Jayanthi | Performance Analysis of Vector Quantizer using Modified Generalized Lloyd Algorithm[END_REF].

For the proposed system, the LSF parameters are coded on 8 bits for each sub-frame. We recall that for transient frame, 6 bits are added to code the attack position. Consequently, the auxiliary channel bit-rate varies between 344 and 474 bps.

EXPERIMENTAL EVALUATION OF THE PROPOSED APPROACH

The experiments aim at validating our approach and comparing the restored audio signal to the original one. We used the PEMO-Q software described in [START_REF] Huber | PEMO-Q-A New Method for Objective Audio Quality Assessment Using a Model of Auditory Perception[END_REF] as a tool to measure the Objective Difference Grade (ODG) and the instantaneous Perceptual Similarity Measure (PSM t ). The ODG is a perceptual audio quality measure, which rates the difference between test and reference signals among a scale from 0 (imperceptible) to -4 (very annoying). The values of PSM t vary in the interval [0,1], with 1 indicating the similarity between the reference and the test signals, whereas smaller values correspond to larger deviations between them. The perceptual measures are correlated to the Subjective Difference Grade (SDG) for audio quality. At first, the audio quality is evaluated when a single coding is performed. For each experiment, the reference audio signals are coded by MP3 and AAC coders at different bitrates varying from 24 to 96 kbps. The considered reference audio signals for all the simulations are mono castanet and triangle, which exhibit a remarkable transient character.

As illustration of the proposed approach, the 56 kbps MP3 coded/decoded castanet and triangle signals and their corrected versions are shown in Figure 7. It can be seen that the MP3 coder introduces a pre-echo and smoothes attacks. At a second stage, the perceived quality in multiencoding case is analyzed. Referring to the experimental results of Reiss [START_REF] Reiss | Audio Issues In MIR Evaluation[END_REF] related to the stereo MP3 coder at 128 kbps, the perceptual audio quality deteriorates with the increase of encoding number. Similar results were obtained for mono MP3 coder at 64 kbps for castanet and triangle sequences.

The variations of the perceptual audio quality (PSM/ODG) with the number of encodings are shown in Figures 10 and11. Without correction, we observe a fast deterioration. In fact, the quantization noise from each cycle piles up, so that the pre-echo, which was post-masked by the attack in the first encodings, is not masked anymore in the next encodings and becomes annoying.

For the castanet signal, the temporal masking enhances the quality, but the reference temporal envelope for the n th coding is the deteriorated envelope of the signal from the ©n 1 th coding-decoding. Thus, with only TM, the curve converges towards that without TM, whereas with our correction (with always the same envelope), the quality remains transparent.

CONCLUSION

Low-bit-rate coding-decoding with standard coders AAC and MP3 smoothes attacks in transients signals and increases the pre-echo despite TNS/TM. We have proposed an attack restoration method, based on temporal envelope correction, using a small set of information transmitted through an auxiliary channel. Our method enhances significantly the audio quality as measured by ODG and PSM t , and avoids the dramatic fall of quality caused by multiple coding-decoding. All components of the proposed system have a reasonable complexity, except of the transient localization: other methods than computating stationarity indices should be considered. Further study will aim at using the audio watermarking as an auxiliary communication channel and evaluating the influence of the watermark detection error on the proposed system.

Figure 1 :

 1 Figure 1: Original signal (top) and pre-echo (bottom) from castanet (left) and triangle (right) coded at 56 kbps using MP3 coder

Figure 2 :

 2 Figure 2: Block diagram of the proposed approach.

Figure 4 :

 4 Figure 4: Transient frame (top), its corresponding stationary index (bottom)

Figure 5 :

 5 Figure 5: Block diagram of the temporal envelope estimation.

Figure 6 :

 6 Figure 6: The castanet signal and its corresponding temporal envelope estimate

Figure 7 :

 7 Figure 7: Attack restoration for a castanet (left) and triangle (right) signals coded by a MP3 coder at 56 kbps

Figure 8 :

 8 Figure 8: Mean of Perceptual Similarity Measure and Objective Difference Grade for castanet (left) and triangle (right) signals (MP3 coder)

Figure 9 :Figure 10 :

 910 Figure 9: Mean of Perceptual Similarity Measure and Objective Difference Grade for castanet (left) and triangle (right) signals (AAC coder)

Figure 11 :

 11 Figure 11: Effect of multiple encoding on audio quality for triangle signal (MP3 coder)

17th European Signal Processing Conference (EUSIPCO 2009) Glasgow, Scotland, August 24-28, 2009 © EURASIP, 2009


Imen Samaali
email: imensamaali@yahoo.fr

Gaël Mahé

Monia Turki-Hadj Alouane

CRITERIA TO MEASURE THE QUALITY OF TVAR ESTIMATION FOR AUDIO SIGNALS

An audio signal can be represented by a Time-Varying Auto-Regressive (TVAR) model, whose parameters can be estimated by a particle filter. Since the original parameters are unavailable for real signals, an evaluation of the estimation may be traditionally performed through indirect criteria such as the SNR of the signal denoised by a Kalman filter based on the TVAR estimated model or through a statistical analysis based on the observation. We propose a new evaluation method based on the statistical characterization of the output of the inverse TVAR estimated model. The proposed criteria are much more suitable and coherent when correlated to the direct criterion (cepstral distance), which is related to the estimated TVAR parameters.

INTRODUCTION

Non-stationary signals, like audio signals, may be represented through Time-Varying Auto-Regressive (TVAR) processes, where the AR coefficients evolve continuously in time. The current tendency is to estimate such models through Monte Carlo methods: the principle of these algorithms is to explore the space of solutions thanks to a population of particles, each of them corresponding to a candidate model [START_REF] Sanjeev | A Tutorial On Particle Filters For Online Nonlinear/Non-Gaussian Bayesian Tracking[END_REF].

When the original model of the signal is known, the performances of these algorithms can be easily evaluated by comparing the true and the estimated model. However, for natural signals, the original model is rarely available. Consequently, the quality of the TVAR estimation is traditionally evaluated through the reduction of the observation noise obtained by a Kalman filter using the estimated model [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF].

The estimated model is also validated by statistical tests on the series u t defined by:

u t = p(Y t ≤ y t |y 1:t-1 ), (1)
where Y 1 , ...,Y N are the random variables associated to the observations y 1 , ..., y t . This method has the drawback of being computationaly complex.

After a brief presentation of the TVAR model and its estimation by particle filtering in Section 2, the classical criteria for model validation will be presented in Section 3. We will propose a new method for the evaluation of the TVAR estimation in Section 4. In Section 5, the proposed method will be evaluated and compared to the classical one.

TVAR MODEL AND PARAMETERS ESTIMATION 2.1 TVAR model

The output, x t , of a TVAR process of order p is modeled at time t > 0 as follows:

x t = p ∑ i=1 a i,t x t-i + σ e t e t , (2)
where e t is a white gaussian noise (e t ∼ N (0, 1)), a t ≡ (a 1,t , ..., a p,t ) is the vector of TVAR coefficients and σ 2 e t is the variance of the TVAR innovation sequence, all depending on t.

The signal, x t , is assumed to be corrupted by an additive white gaussian noise, so the observation at time t > 0 is given by

y t = x t + σ n t n t , (3)
where n t is a white gaussian noise (n t ∼ N (0, 1)) and σ 2 n t is the time varying variance of the observation noise.

The variances of observation and innovation noise are defined by their corresponding logarithms, i.e. φ e t ≡ log σ 2 e t and φ n t ≡ log σ 2 n t . The order p is assumed to be fixed and known. The unknown parameters are then the TVAR coefficients, the variances of the excitation and the observation noise. Each of the three components of the unknown parameter vector θ t = (a t , φ e t , φ n t ) is supposed to evolve according to a firstorder Markov process, which can be defined by its initial state and by the distribution of its state transition. Those distributions are defined by:

p(a t |a t-1 ) ≡ N (a t ; a t-1 ; ∆ a ); (4)
p(φ e t |φ e t-1 ) ≡ N (φ e t ; φ e t-1 ; δ 2 e );

(5)

p(φ n t |φ n t-1 ) ≡ N (φ n t ; φ n t-1 ; δ 2 n ), (6)
where N (x; m; P) denotes a gaussian density with argument x, mean m, and covariance P.

An estimate of the parameter vector θ t is given by a conventional particle filter method.

Particle filter

The principle of the particle filtering is to generate a set of N particles θ (i) |i=1:N , each of them representing a state θ 0:t of the system which is likely to occur. According to the SIS particle filter algorithm [START_REF] Sanjeev | A Tutorial On Particle Filters For Online Nonlinear/Non-Gaussian Bayesian Tracking[END_REF], the particles evolve according to the stage of prediction, p(θ t |θ t-1 ) = p(a t |a t-1 )p(φ e t |φ e t-1 )p(φ n t |φ n t-1 ), and the weights are updated according to the observation (stage of correction: w(i) t = p(y t |θ (i) t )). However, the particle filter as described presents a major drawback. The increase of the scattering of the weights has ominous effects on the quality of the estimation and induces a long-term divergence of the filter: this phenomenon is known as "degeneration" of the weights. In order to avoid this phenomenon, a new stage called re-sampling has been introduced. It consists in duplicating the particles of strong weight and eliminating the particles of weak weight.

The TVAR parameters vector is then estimated by a Monte Carlo method: θt

≈ N ∑ i=1 θ (i) t w(i) t .
An estimate x of the original signal x is performed by a Kalman filter based on the estimated TVAR parameters [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF].

VALIDATION OF THE TVAR ESTIMATION: DIRECT AND INDIRECT CRITERIA

This part presents classical criteria used to assess the quality of the TVAR estimation:

• a direct criterion relying on the comparison between the original and estimated parameters. For audio signals, this can be performed through the cepstral distance.

• indirect criteria based either on the SNR improvement or on statistical tests carried out on the observation.

Cepstral distance measurement

For signals with known TVAR model (synthetic TVAR signals for example), the quality of the TVAR estimation obtained by the particle filtering can be evaluated by the comparison between the trajectories of the original and the estimated TVAR coefficients.

The AR coefficients are related to the cepstrum by the relation [START_REF] Faucon | Mesures Objectives De La Réduction De Bruit[END_REF]:

c t (i) = -a t (i) - i-1 ∑ n=1 (1 - n i )a t (n)c t (i -n). ( 7
)
One can compare the true and the estimated models by the cepstral distance, which is the euclidian distance between the cepstra,

d C t = p ∑ i=1 (c t (i) -ĉt (i)) 2 . ( 8
)
The cepstral distance, as shown here, allows to aggregate the evaluation of all TVAR estimated coefficients in a single and perceptually significant criterion. It will be taken as reference in the following.

SNR criteria

When the estimated TVAR parameters are used to denoise the observed signal y by a Kalman filtering, a classical measure of performance of the particle filter algorithm is the Signal to Noise Ratio improvement (SNR improvement), i.e. the difference between the SNRs after and before denoising. Referring to the experimental results of Vermaak [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF], the SNR improvement increases as the number of particles, N, increases up to 100.

However, in another experiment, we notice that the criterion of the SNR improvement is not relevant to measure the quality of the TVAR estimation. Figure 1 shows 400 samples of the test signal generated by a second-order TVAR process. The corresponding TVAR parameters, depicted in Figure 2, follow a first-order Markov process as defined in section 2.1 with fixed parameters ∆ a 1 = ∆ a 2 = 10 -2 for the TVAR coefficients and δ 2 e = δ 2 n = 10 -3 for the log-variance. The variations of the SNR improvement according to the input SNR are shown in Figure 3. They were obtained by a single run of the algorithm for each value of the input SNR, using 500 particles. The use of a single run is allowed by the small variance of the results when using 500 particles, as shown in [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF].

The SNR improvement decreases as the input SNR increases, whereas the cepstral distance decreases, indicating a better model estimation. One could suggest to take simply the SNR output as a measure of the quality but its growth does not match the decrease of the cepstral distance: the latter stops decreasing from input SNR = 20 dB while the output SNR goes on increasing.

Another drawback of the SNR criterion is its dependence on the denoising phase: what is evaluated is not the quality of the TVAR estimation but the quality of the denoising using this estimation.

At last, such a criterion implies that the original signal x is available, which is not realistic for a natural signal.

Conventional statistical approach for model adequacy

Let Y 1 , ...Y N be the random variables associated to the observations y 1 , ..y t . If the model is correct, the sequence

u t = p(Y t ≤ y t |y 1:t-1 ) (9)
is a realization of an independent random variable uniformly distributed on [0, 1]. By letting the time series v t = φ -1 (u t ), where φ is the standard normal cumulative distribution function, the TVAR model is correct if v t is i.i.d according to N (0, 1) [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF].

According to [START_REF] Vermaak | Particle Methods For Bayesian Modeling And Enhancement Of Speech Signals[END_REF], the computing of the u t requires integration over the model parameters. The latter is approximated by a Monte Carlo estimation using the particle filter. Therefore, an estimate of u t is given by:

ût 1 N N ∑ i=1 p(Y t ≤ y t |θ (i) 1:t , y 1:t-1 ), (10)
where θ

(i)
t is the i-th particle at time t.

The statistical tests employed here aim at testing the normality and the whiteness of the time series v t and are briefly described below:

Whiteness

We measure the correlation by a whiteness index given by the Ljung-Box test. This index is defined by: where N = sample size, K = number of autocorrelation lags and ri denotes the i th autocorrelation coefficient of the time series. For a white signal, q LB k is asymptotically Chi-Square distributed.

q LB K = N(N + 2) K ∑ i=1 r2 i (N -i) , ( 11

Normality

The Bowman-Shenton test evaluates the hypothesis that the time series has a normal distribution. The test is based on the skewness γ

1 = µ 3 µ (3/2) 2 and kurtosis γ 2 = µ 4 µ (2) 2
-3 of the time series, with µ i the i th central moment of the random variable associated with the time series around its mean µ. The statistic value associated to this test is given by:

q BS = γ 2 1 + γ 2 2 . ( 12
)
For a true gaussian distribution, the statistic q BS should be closer to 0.

PROPOSED APPROACH

Assuming that a signal x is produced by a TVAR system excited by a stationary gaussian white noise, the estimation is good if there exists a stationary gaussian white noise that can produce x by exciting the estimated TVAR model. The proposed method is then based on the evaluation of the statistical properties of the estimated excitation, ê(t), that can generates the TVAR signal x(n). Indeed ê(t), which is defined by

ê(t) = 1 σe t x(t) - p ∑ i=1 âi,t x(t -i) , (13)
must be stationary, white and gaussian. Note that â = ( âi,t , ..., âp,t ) is the vector of estimated TVAR coefficients and σe t corresponds to the estimated variance of the TVAR innovation sequence.

Since the original signal x is not available for natural signals under noisy observation, we replace it by the estimated signal x, given by the Kalman filter. With this approximation, an estimation for the excitation may be defined as follows:

ê(t) = 1 σe t x(t) - p ∑ i=1 âi,t x(t -i) . ( 14
)
According to (14), the principle of the method can be then illustrated with a diagram (see Figure 4). Besides the normality and whiteness that are classically evaluated, we have introduced the assessment of the estimated excitation stationarity. Indeed, the stationarity criterion is all the more crucial since the original TVAR signal is non stationary.

Stationarity

The method we choose to detect non stationarity is based on the stationarity index used in [START_REF] Laurent | Doncarli Stationarity index for abrupt changes detection in the time-frequency plane[END_REF], which is the Kolmogorov distance between the time frequency representations (TFR) of the signal at different times. The latter is given by:

SI(n) = p τ=0 +∞ f =-∞ |NI 1 (n; τ, f ) -NI 2 (n; τ, f )|d f dτ. (15)
NI 1 (n; τ, f ) and NI 2 (n; τ, f ) represent a normalization of respectively subimages I 1 (n; τ, f ) and I 2 (n; τ, f ):

NI k (n; τ, f ) = |I k (n; τ, f )| p τ=0 +∞ f =-∞ |I k (n; τ, f )|d f dτ , ( 16
)
where the two subimages I 1 (n; τ; f ) and I 1 (n; τ; f ) with equal duration p are extracted from the global TFR on both sides of instant n:

I 1 (n; τ, f ) = T FR(n -p + τ, f ); (17) I 2 (n; τ, f ) = T FR(n + τ, f ). ( 18
)
The parameter p delimits the considered analysis duration at each instant n and allows the selectivity/sensivity control of the SIs: higher p lead to smoother SIs. As used in [START_REF] Larbi | Audio Watermarking: A Way To Stationarize Audio Signals[END_REF], we fixed p to 20.

We propose to measure the stationarity of the estimated excitation ê by the variance of its stationarity index. To evaluate the normality and the whiteness of ê, we use the respective criteria presented in section 3.3.

EXPERIMENTAL RESULTS

The experiments aim at validating our approach and compare it to the one presented in subsection 3.3. Thus, we propose to study the correlation between the cepstral distance and the statistical criteria performed on both residual time series v as defined in subsection 3.3 and the estimated excitation ê.

The test signal is a synthetic TVAR signal of order 2 (see Figure 1), with ∆ a = 10 -2 I 2 for the TVAR coefficients and δ 2 e = δ 2 n = 10 -3 for the log-variance (see Figure 2). From Figure 1, one can see that the time variations of the synthetic TVAR signal are similar to those of a natural speech signal.

At a first stage, we investigated the quality of TVAR estimation according to the particles' number N. For each experiment, the time series v and the estimated excitation ê were computed and analyzed using the three statistical tests presented in sections 3.3 and 4. Since the subsection 3.2 stressed the need of a new criterion especially for input SNR > 20 dB, we fixed SNR to 30 dB. The TVAR estimation was performed for different values of N.

Figure 5 compares the variations, over N, of the standardized statistical criteria and the cepstral distance for both time series v and ê. These reported results were obtained by an averaging over 30 independent runs for each value of N. As expected, the estimation quality is improved by the increase of N: both statistical criteria and cepstral distance decrease as the particles' number increases up to 100. As a preliminary conclusion, the whiteness, the normality and the stationarity of ê and v appear as good indicators of the TVAR estimation quality, since they follow the same evolution as the cepstral distance. These reported results demonstrate that the statistical indices related to the estimated excitation ê are well correlated to the cepstral distance. The correlation degrees depends on the estimation quality . Indeed, for cepstral distances below 0.6, the whiteness, the normality and the stationarity are al- Figure 6: Correlation between statistic criteria and cepstral distance for both the estimate excitation ê ((1), ( 2), ( 3)), and the residual time series v ((4), ( 5), ( 6)).

most linearly related to the cepstral distance. Such significant correlation is not observable for v.

To support these results, we computed the correlation coefficients between the cepstral distance and each criterion. The obtained results, summarized in Table 1, confirm that the proposed approach is more coherent with the cepstral distance than the conventional assessing method (time series v). The low complexity is another advantage of the proposed method. Whereas the classical validation method based on v, requires the computation of an er f c for each particle, our method requires a simple FIR filtering based on the estimated TVAR model.

Whiteness

CONCLUSION

We have shown that the indirect criteria based on the SNR are not relevant for the evaluation of a TVAR estimation. We have proposed a new evaluation method based on the measure of the normality, the stationarity and the whiteness of the estimated excitation. The latter is the output of the inverse estimated TVAR system.

With a lower complexity than the classical method based on residual time series v, the proposed method leads to better results: the whiteness, normality and stationarity indices are strongly correlated to the cepstral distance between the true and the estimated TVAR models.

Note that the proposed method does not aim at performing a binary validation (valid / not valid). It is thought as a quantitative measure of the quality of the TVAR model estimation, which could be used for example to compare two TVAR estimations. In addition, the great advantage of this method is that it does not need any knowledge of the original model, neither of the original signal, contrary to the evaluation through SNR criteria.

  hal-00259047, version 1 -26 Feb 2008 Author manuscript, published in "15th European Signal Processing Conference (EUSIPCO 2007), Poznan : Poland (2007)"

Figure 1 :

 1 Figure 1: Time variations of the synthetic second-order TVAR signal

Figure 2 :

 2 Figure 2: Time variations of the TVAR parameters for the signal in Figure 1

Figure 3 :

 3 Figure 3: SNR improvement, output SNR and cepstral distance.

Figure 4 :

 4 Figure 4: Diagram of the proposed method.

Figure 5 :

 5 Figure 5: Cepstral distance compared to statistical criteria (whiteness (a), normality (b) and stationarity (c)) for both ê and v, according to the particle's number.

  Figure 6 shows the correlation of the statistical criteria with the cepstral distance for both time series v and ê. Each experiment is represented by a point of coordinates (d C , I) where d C is the cepstral distance and I refers to one of the three indices (whiteness / normality / stationarity) for v or ê.

Table 1 :

 1 Correlation coefficients between the statistical criteria and the cepstral distance for both the estimated excitation ê and the time series v.

			Normality Stationarity
	ê	0.93	0.6	0.95
	v	0.06	0.80	-0.7


Monia Imen Samaali
email: imen.samaali@mi.parisdescartes.fr

Turki-Hadj Alouane

Gaël Mahé
email: gael.mahe@mi.parisdescartes.fr

Attack restoration in low bit-rate audio coding, using an algebraic detector for attack localization

Keywords: Temporal envelope, ARMA modeling, audio coding, sound attack, algebraic detector, attack restoration

This paper deals with pre-echo reduction in low bit-rate audio compression. [1] proposed an attack restoration method based on the correction of the temporal envelop of the decoded signal. A small set of coefficients were then transmitted through a limited bit-rate auxiliary channel. However, the transmission of the transient position computed on the original audio signal was required. In this paper, we deployed a new method of attack localization based on differential algebraic, which guaranties a successful detection on the decoded audio signal. The algebraic method has also a reduced complexity compared to the index stationary detector used in [1]. The new proposed approach is evaluated for single audio coding-decoding, using objective perceptual measures. The experimental results for MP3 coding exhibits an efficient restoration of the attacks and a significant improvement of the audio quality.

I. INTRODUCTION

Transient waveforms, window length and psycho-acoustic bit allocation interact to produce pre-echo in low bit-rate audio coding (see Figure 1). When a transient occurs, a perceptual model allocates few bits for the quantization of the frame parameters. At the decoder, the quantization noise, supposed to be fully masked, may spread over the entire block. Therefore, this noise precede the time domain transient and then produce a potentially audible artefact known as pre-echo [START_REF] Kyle | Pre-echo Detection and Reduction[END_REF]. In addition, in a low bit-rate context, the attacks may be smoothed through coding, which reduces the percussive quality of sounds.

Many methods have been proposed to tackle the problem of echo in transform audio coding, especially for the case of modified discrete cosine transform (MDCT) coding. The most popular approach is to make the filterbank signal adaptive, using window switching controlled by transient detection [START_REF] Kyle | Pre-echo Detection and Reduction[END_REF] or close-loop decision. Usually window switching implies extra delay and complexity compared with using a nonadaptive filterbank. Another popular approach is the temporal noise shaping (TNS) [START_REF] Jrgen | Temporal Noise Shaping, Quantization and Coding Methods in Perceptual Audio Coding: a Tutorial Introduction[END_REF] which allows the encoder to control the temporal fine structure of the quantization noise.

A method was proposed in [START_REF] Samaali | Temporal envelope correction for restoration of attacks in low bit-rate audio coding[END_REF] aiming at reducing echo artifacts after transform decoding. The principle is to restore the temporal envelope of the signal. Time envelope computation is based on linear prediction in frequency domain. Note that the restoration method requires the transmission of the coefficients of the ARMA model describing the temporal envelope and the transient position as side information. We suppose that we have an auxiliary channel to convey this side information, with a reduced bit-rate ( ✂ 500 bps, for example a watermark). In order to reduce the complexity of pre-echo reduction and to allocate all the available bit-rate to the transmission of the temporal envelope parameters, we propose a new method based on an algebraic detector, to localize transient positions on the decoded audio signal. Therefore, there is no more need to the transmit transient position information.

The remain of this paper is structured as follows: in section 2, we present the algebraic detection algorithm used to estimate transient positions. In section 3, the new approach dedicated to attack restoration is developed. Section 4 presents a performance evaluation of the proposed algorithm in the case of MP3 simple encoding.

II. TRANSIENT LOCALIZATION BY ALGEBRAIC DETECTOR

The transient localization proposed in [START_REF] Samaali | Temporal envelope correction for restoration of attacks in low bit-rate audio coding[END_REF] is based on a distance measurement between successive time-frequency representations of the signal, which is quite complex. Moreover, since the localization may be inaccurate in the decoded signal, two localizations are performed in the coding part: before and after coding-decoding, in order to transmit the anticipated error of localization through the side-channel.

In order to reduce the complexity of transient localization, we propose to use the change point detection method described in [START_REF] Mboup | A delay estimation approach to changepoint detection[END_REF]. This latter is based on algebraic manipulations of a piecewise polynomial signal.

The input signal, ✄ ✆☎ ✞✝ ✠✟ , can be represented as a piecewise polynomial with maximum one discontinuity on the time

interval ✡ ☞☛ ✌ ✎✍ ✑✏ ✒ ✔✓ ✠✒ ✖✕ ✘✗ ✚✙ , ✒ ✜✛ ✎✢ . Let set ✄ ✌ ☎ ✞✝ ✠✟ ✍ ✄ ✆☎ ✒ ✣✕ ✝ ✠✟ ✓ ✝ ✥✤ ✏ ✢ ✔✓ ✠✗ ✚✙ (1)
for the restriction of the signal in ✡ ✦☛ ✌ and redefine the discon- tinuity point, say ✝ ✌ , relatively to ✡ ✦☛ ✌ with:

✧ ✝ ✌ ✍ ★✢ if ✄ ✌ ☎ ✞✝ ✠✟ is smooth ✧ ✢ ✂ ✝ ✌ ✂ ✗ otherwise
In the sense of the distribution theory, the ✩ ✫✪ ✭✬ order derivative of the input signal can be written:

✮ ☞✯ ✄ ✌ ☎ ✞✝ ✠✟ ✮ ✝ ✱✰ ✍ ✄ ✳✲ ✯ ✵✴ ✌ ☎ ✞✝ ✠✟ ✕ ✯ ✶ ✷ ✹✸ ✆✺ ✦✻ ✯ ✽✼ ✷ ✿✾ ☎ ✞✝ ❁❀ ❂✝ ✌ ✟ ✷ ✼ ✺ (2)
where ✻ ✷ is the jump of the ❃ ❄✪ ✭✬ order derivative at the point ✝ ✌ and ✄ ✲ ✯ ✵✴ ✌ represents the regular part of the ✩ ❅✪ ✭✬ order derivative of the signal.

If ✻ ❇❆ ✍ ✻ ✺ ✍ ❉❈ ❈ ❈ ✦✍ ✻ ✷ ✍ ❊✢ , there is no spike in the given interval. If ✻ •❋ ✍ ❍✢ ✔✓ ■✢ ❑❏ ✝ ✌ ❏ •✗
, there is a spike in given interval at location ✝ ✌ .

[4] proposes a detector ▲ ❅☎ ✞✝ ✠✟ , based on an algebraic determination of ✝ ✌ , computed through simple filtering of ✄ .

The detector D(t) relies on a decision function which must be greater than some threshold if a changing point exists in the interval. To illustrate the ability of the method to detect different change points in the same signal, the algorithm described below is implemented using only a third order derivative. The test signal is a batteries composed of 4 attacks (figure 2 (a)). The results in figures 2 (b) and (c) show how all the change-points are correctly detected: each change point position matches a corresponding attack position.

In the next experiment, we investigate the quality of algebraic detector versus the stationarity index detector [START_REF] Larbi | Audio Watermarking: A Way To Stationarize Audio Signals[END_REF]. Figure 3 compares error detections for both algebraic and stationarity index detector using original and mp3 decoded triangle-castanet audio signal. The error detection corresponds to the difference between the actual and estimated transient positions. The algebraic detector has high accuracy and closely approximates all the considered attacks positions.

III. PRE-ECHO REDUCTION SYSTEM

As detailled in [START_REF] Samaali | Temporal envelope correction for restoration of attacks in low bit-rate audio coding[END_REF], the restored audio signal, ▼✄ ✪ , is given at time ✝ ✛ ◆✢ by:

▼✄ ✆☎ ✞✝ ✠✟ ✍ ✄ ✆☎ ✞✝ ✠✟ ✠❖ ✹ ✱◗ ▼ | ☎ ✞✝ ✠✟ ▼ | ☎ ✞✝ ✠✟ ✠❖ ✹ ✱◗ ✓ (3)
where ✄ ✆☎ ✞✝ ✠✟ ✠❖ ✹ ✱◗ is the decoded audio signal, ▼ | ☎ ✞✝ ✠✟ is the temporal envelope of the original signal, and ▼ | ☎ ✞✝ ✠✟ ❙❖ ✹ ✱◗ is the temporal envelope of the coded-decoded signal.

The correction constitutes a post-processing performed at the decoder. The parameters related to the temporal envelope The audio signal is first fed into a frame characterization in order to check if the frame is transient or not. To detect transient frames, we use the technique described in [START_REF]Advanced Audio Coding (AAC)[END_REF]. For the transient frames, a localization of the attack time positions is performed using the algebraic detector presented in section 2. Non transient frames are divided into two equal sub-frames. An estimate of the temporal envelope is computed using a frequency domain linear prediction model (FDLP) based on an ARMA model, which parameters are transmitted over a very low bit-rate auxiliary channel. At the decoder, the received bitstream is decoded in order to extract the ARMA coefficients for computing the estimate of the original time envelope. In parallel, a frame type characterization and a transient localization are performed from the decoded signal. Estimates of the temporal envelopes for both original and decoded signals are computed. Finally, the restored audio signal, ▼✄ ❁☎ ✞✝ ✠✟ , is obtained according to 3.

A. Temporal envelope ARMA modeling

he temporal envelope is estimated using the frequency domain linear prediction (FDLP). In fact, in the same way that TDLP (Time domain linear prediction) estimates the power spectrum, FDLPO estimates the temporal envelope of the signal, specifically the square of its Hilbert envelope [START_REF] Athineos | Frequency-Domain linear Prediction For Temporal Features[END_REF]:

| ☎ ✞✝ ✠✟ ✍ ✎❞ ✼ ✺ ❢❡ ❤❣ •✐ ❦ ☎ ✞• ♠✟ ✐ ❦ ☎ ✞• ✚❀ ✘♥ ❇✟ ✮ • ❤♦ (4)
i.e. the inverse Fourier transform of the autocorrelation of the single sided (positive frequency) spectrum

✐ ❦ ☎ ❜♥ ❇✟ .
The block diagrams of the temporal envelope estimate is depicted in Figure 6. To get an approximation of the Hilbert envelope, first the Discrete Cosine Transform (DCT) is applied to a given audio segment. Next, a linear prediction is applied to the DCT transformed signal in order to get an ARMA model.

An estimation of the temporal envelope of ✄ ✆☎ ✞✝ ✠✟ is therefore given by: where ☎ ⑦ ② ✟ ✺ ❙→ ② → ⑤ and ☎ ③ ② ✟ ❆ → ② → ✇

▼ | ☎ ✞✝ ✠✟ ✍ ❍♣ q ☎ | sr ❵t ✪ ✟ ♣ ✓ (5) where q ☎ ✭✉ ✦✟ ✍ ✈ ①✇ ② ✸ ❆ ✿③ ② ✉ ✼ ② ④ ✕ ✈ ⑥⑤ ② ✸ ✆✺ ❇⑦ ② ✉ ✼ ② ✍ q ⑨⑧ ☎ ✭✉ ✦✟ q ⑨⑩ ☎ ✭✉ ✦✟ (6) ❶ ✚❶ ✥❷ ❯ ✱❸ ❹ ❺❯ ✞❻ ✿( ❇❼ ❾❽ ✚❿ ➀ ➁ ➃➂ ✠➄ ➀ ✭➅ ✹➆ ➀ ➇ ➉➈ ❽ ➋➊ ➀ ➁ ➃➂ ➃➌ ➀ ✞➅ ➆ ➀ ❸ ( ARMA(p,q) ) DCT ) ❚ ❱❯ ❳❲ ✱( ( ➍ ❯ ❳❲ ✱( ❬ ❬ ➎ ♠➏ ➐ ❵➑ ➒ ➓ ❯ ✞➔ ☞(
are the ARMA coefficients. The selection of the FDLP model order is guided by the temporal structure of signal in the same way as the TDLP model order is dictated by the formant structure. To illustrate the importance of model order, figure 7 shows a violon segment at 44.1 kHz sampling rate and its corresponding time envelope estimates obtained by ARMA(2,3) and ARMA(7,3) models. As expected, with an ARMA(2,3), only a smooth version of the time envelope is given, however, in the case of ARMA [START_REF] Athineos | Frequency-Domain linear Prediction For Temporal Features[END_REF][START_REF] Jrgen | Temporal Noise Shaping, Quantization and Coding Methods in Perceptual Audio Coding: a Tutorial Introduction[END_REF], the envelope almost fits the pitch pulses.

An evaluation of the FDLP model order based on objective measurements of the audio quality will be presented in section IV.

B. Parameter coding

After the ARMA parameters are estimated, they must be coded and transmitted through the auxiliary communication channel. The autoregressive coefficients (ARMA) are characterized by large dynamic range and would require many bits per coefficient for accurate coding. For this reasons, it is necessary to transform the ARMA coefficients into reflection coefficient (RC).

For each sub-frame, a vector grouping the RC coefficients is coded using a classical vector quantization technique. The codebook C is obtained by training on a database taken from various kinds of audio signals. It can be computed by the Lloyd-Max algorithm [START_REF] Jayanthi | Performance Analysis of Vector Quantizer using Modified Generalized Lloyd Algorithm[END_REF]. The size of the codebook and the corresponding bit-rate will be discussed in section IV.

IV. EXPERIMENTAL EVALUATION OF THE PROPOSED APPROACH

The experiments aim at validating our approach and comparing the restored audio signal to the original one. We use the PEMO-Q software described in [START_REF] Huber | PEMO-Q-A New Method for Objective Audio Quality Assessment Using a Model of Auditory Perception[END_REF] as an objective measurement to compare the score of Objective Difference Grade (ODG) and instantaneous Perceptual Similarity Measure (PSM ✪ ). The ODG is a perceptual audio quality measure, which rates the difference between test and reference signals among a scale from 0 (imperceptible) to -4 (very annoying). The values of PSM ✪ vary at the interval [0,1], with 1 indicating the best similarity between the reference and the test signals. These perceptual measures are correlated to the Subjective Difference Grade (SDG) for audio quality.

As a primary evaluation of the proposed approach, the coded/decoded castanet signal at 56 kbps and the corrected version are shown in Figure 8. It can be seen that the MP3 coder introduces a pre-echo and smoothes attacks. In the reconstructed signal, the pre-echo is considerably reduced and the attack is restored.

Given that the bit-rate offered by the auxiliary channel is limited to 20 bits per frame (434 bps), we study the influence of the ARMA order on the audio quality. Figure 9 compares the variations, over bit-rates, of the ODG and PSM ✪ for both coded/decoded signal and its restored version. For comparison, we present the system evaluation using two ARMA model orders with two different bit-rate coding: ARMA(2,3) coded at 16 bits per frame (347 bps) as used in [START_REF] Samaali | Temporal envelope correction for restoration of attacks in low bit-rate audio coding[END_REF] and ARMA(5,3) coded at 20 bits per frame (434 bps). Remain that in addition to the ARMA(2,3) parameter coefficients, 4 bits are allowed to code the transient position in [START_REF] Samaali | Temporal envelope correction for restoration of attacks in low bit-rate audio coding[END_REF]. As illustrated in Figure 9, the proposed correction using ARMA(5,3) provides a significant enhancement of the PSMt and ODG. With only ARMA(2,3) the improvement is slighter.

V. CONCLUSION

Low-bit-rate coding-decoding with standard MP3 coder smoothes attacks in transients signals and increases the preecho. We have proposed an attack restoration method, based on accurate transient localization and temporal envelope correction, using a small set of information transmitted through an auxiliary channel. Our method enhances significantly the audio quality as measured by ODG and PSM ✪ .

Fig. 1 .

 1 Fig.1. illustration of the pre-echo artefact from castanet signal coded at 56 kbps using MP3 coder

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Batterie signal (a), Decision function (b) and change point detector (c)

Fig. 5 .

 5 Fig. 5. Block diagram of treatment at the decoder .

Fig. 6 .

 6 Fig. 6. Block diagram of the temporal envelope estimation.

Fig. 7 .

 7 Fig.7. Original violon segment and temporal envelopes using ARMA[START_REF] Kyle | Pre-echo Detection and Reduction[END_REF][START_REF] Jrgen | Temporal Noise Shaping, Quantization and Coding Methods in Perceptual Audio Coding: a Tutorial Introduction[END_REF] and ARMA[START_REF] Athineos | Frequency-Domain linear Prediction For Temporal Features[END_REF][START_REF] Jrgen | Temporal Noise Shaping, Quantization and Coding Methods in Perceptual Audio Coding: a Tutorial Introduction[END_REF] model respectively.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Attack restoration for a castanet signal coded by a MP3 coder at 56 kbps