Maurizio Naldi
email: naldi@disp.uniroma2.it

Marta Flamini
email: m.flamini@uninettunouniversity.net

The CR 4 index and the interval estimation of the Herfindahl-Hirschman Index: an empirical comparison

Keywords: Concentration indices, Competition, Herfindahl-Hirschman Index (HHI), Four-firm concentration ratio

Concentration indices are employed to measure the level of competition within an industry. Among the several indices proposed in the literature, the Herfindahl-Hirschman Index (HHI) and the Four-firm concentration ratio (CR4) are among the most established. However, the HHI requires the market shares of all market players to be known, while the CR4 requires just the top four. In order to investigate whether we can always use the CR4 in place of the HHI, we have compared the indices resulting from a selected group of datasets. This preliminary analysis shows that the relationship between the CR4 and the HHI may not be monotonic, so that the CR4 does not preserve the order relationship established through the HHI.

Introduction

Concentration indices are used in a number of contexts to measure how a quantity is distributed among a number of subjects (individuals or aggregates, such as households or companies). Several indices have been proposed in the literature and have been applied in many contexts, to see how income (or wealth) is distributed among the population, or analyze the market structure (e.g., in the analysis of merger and acquisition operations), or even to investigate the filing of patents (see, e.g., [START_REF] Liston-Heyes | Inventive concentration in the production of green technology: A comparative analysis of fuel cell patents[END_REF]). An extensive literature is surveyed for the banking sector in [START_REF] Bikker | Measures of competition and concentration in the banking industry: a review of the literature[END_REF]. Among them, two have emerged as the most widespread: the Herfindahl-Hirschman Index (often indicated with its abbreviation HHI) and the CR 4 index. The former requires the knowledge of the market shares of all the companies participating in the market, while the latter concentrates on just the top four. The HHI has been compared to concentration indices established among statisticians (namely those due to Gini, Bonferroni, and Amato) and has been shown in [START_REF] Naldi | Concentration indices and Zipf's law[END_REF] to provide the largest sensitivity in the case of the Zipf law (see [START_REF] Naldi | Rank-size distribution of teletraffic and customers over a wide area network[END_REF] for an example of application of the Zipf law also in contexts other than the distribution of firms). The CR 4 is instead periodically provided by the U.S. Census Bureau for a number of industries [START_REF] Census | Concentration ratios[END_REF].

Given the large diffusion of those two indices, it is to be seen whether they lead to the same conclusions, so that either can be taken as a measure of concentration (in this case the choice would probably fall on the more parsimonious CR 4 ), or they provide complementary views of the phenomenon (with the HHI probably reflecting a more complete panorama).

However, as hinted above, we may not be in a condition to compute both indices, since the HHI requires the complete distribution of the market. However, it has been shown that, though we cannot compute the exact value of the HHI, we can obtain an interval estimate for it if we know just the largest market shares [START_REF] Naldi | Interval Estimation of the Herfindahl-Hirschman Index Under Incomplete Market Information[END_REF]. We can then compare the two indices on a level playing field, assuming that we know in both cases just the top 4 firms (which is what we need for the less demanding of the two, the CR 4 ).

In this paper, we report a preliminary analysis, using a limited number of datasets, with the aim of comparing the conclusions suggested by the two indices. We show in the cases examined that we cannot draw a monotonic relationship between the HHI and the CR 4 , so that the latter cannot be considered as a full replacement of the more complete HHI.

After reporting the definitions of the two concentration indices in Section 2 and recalling the interval estimation of the HHI in Section 3, we describe the datasets in Section 4 and report the results in Section 5.

Concentration indices

Concentration indices are employed to measure the level of competition in an industry, often to examine whether concerns for dominant position creation exist in the case of mergers and acquisitions. Two major indices are the Herfindahl-Hirschman Index (often indicated with its abbreviation HHI) and the CR 4 index. In this section, we report their definitions and main properties.

The Herfindahl-Hirschman Index

The Herfindahl-Hirschman owes its name to the two economists who developed it, though independently. Albert O. Hirschman proposed the index in 1945 in [START_REF] Hirschman | National Power and the Structure of Foreign Trade[END_REF], while Orris C. Herfindahl presented it in 1950 in his unpublished doctoral dissertation at Columbia University, "Concentration in the U.S. Steel Industry". Hirschman himself had to somewhat untangle the paternity dispute, since his index had been attributed to Gini [START_REF] Hirschman | The paternity of an index[END_REF]. Actually, though Herfindahl proposal appeared five years later than Hirschman's, the form of the index as used today is actually that proposed by Herfindahl (which leads to an index that is the square of the original proposal).

If we consider a market where n companies are operating, and the market share of the i-th company is s i , the HHI is defined as the sum of the squares of all the market shares HHI = n i=1

s 2 i . (1)
The HHI is obviously a positive figure. If the market shares are expressed as fractions of the whole market (i.e., 0 < s i ≤ 1, ∀i), then we have 0 < HHI ≤ 1. Instead, if the market shares are expressed as percentages (i.e., 0 < s i ≤ 100, ∀i), then we have 0 < HHI ≤ 10000. In the following we opt for the first choice, which gives us a naturally normalized value for the HHI.

Actually not the whole range of values may be taken by the HHI. If we have a monopoly, where a single company takes all the market, we have n = 1 and

s 1 = 1 =⇒ HHI = 1, (2)
but the opposite case, where the market is uniformly distributed between the company (perfect competition) does not lead to HHI = 0. In a market of n companies with perfect competition, we have

s i = 1 n ∀i =⇒ HHI = n i=1 1 n 2 = 1 n , (3)
which is then the minimum value attainable by the HHI.

The value of the HHI provides an indication of the level of concentration, with the maximum value corresponding to the case of the monopoly, and the minimum corresponding to perfect competition. Hence, the higher the value of the HHI, the higher the concentration of the market in the hands of a few companies. Though a precise correspondence cannot be drawn between the numerical value of the HHI and the qualitative indication of a level of concentration (or, equivalently, of competition), some guidelines have been provided for that purpose. The European Commission, rather than stating just the levels of HHI for the same purpose of identifying horizontal competition concerns, has proposed to define both the levels of post-merger HHI and the change ∆HHI incurred by the HHI because of the merger to identify the cases of no concern. Namely, it has stated that concerns are unlikely when any of the conditions listed in Table 2 apply [START_REF]The European Union: Guidelines on the assessment of horizontal mergers under the Council Regulation on the control of concentrations between undertakings[END_REF]. All other cases are therefore likely to raise concerns about competition. The HHI has been used to measure concentration in a wide set of contexts. In a technical note of the Federal Reserve Bank, Rhoades showed with simple examples how it can be employed to analyse the competitive effects of bank mergers, by computing the HHI before and after the merger [START_REF] Rhoades | The Herfindahl-Hirschman index[END_REF]. It has also been used in civil aviation [START_REF] Lijesen | Measuring competition in civil aviation[END_REF], the book industry [START_REF] Greco | Market Concentration Levels in the U.S. Consumer Book Industry: 19951996[END_REF], the food processing industry [START_REF] Lopez | Market Power and/or Efficiency: A Structural Approach[END_REF], telecommunications, media and the Internet [START_REF] Noam | Did AT&T Die in Vain? An Empirical Comparison of AT&T and Bell Canada[END_REF] [23] [START_REF] Noam | Who Owns the Worlds Media? Research Paper 13[END_REF], and the newspaper industry [START_REF] Van Kranenburg | Mobility and Market Structure in the Dutch Daily Newspaper Market Segments[END_REF]. Some criticism has come as well as to its capability to actually explain the role of market share inequalities in the banking system [START_REF] Alegria | On measuring concentration in banking systems[END_REF] [6].

Post

The CR 4 index

The CR 4 index (the concentration ratio for the top 4 firms) has been the most relevant index to measure concentration before the advent of the HHI [START_REF] Weinstock | Using the Herfindahl Index to measure concentration[END_REF]. It is given by the sum of the market shares of the largest 4 firms in the market [START_REF] Arnold | Economics[END_REF]

CR 4 = 4 i=1 s i . (4)
A foremost shortcoming of this index is that differences in the market structure may not show up: a market in which each of the four largest firms has 20% of the market has the same CR 4 value as another market in which the top four firms have shares of 55%, 20%, 4%, and 1%, respectively, i.e., 80% on the overall, though the competition level is quite different for four equal-size firms than for four firms of disparate size. A further aspect of this issue is that monopoly or oligopoly risks deriving from mergers may not be highlighted if mergers take place between the four top firms, and go completely ignored if the market is made just of four companies (which become three after the merger). In addition, the CR 4 does not consider the whole market, but just a limited number of companies.

While it is clear that a low value of the index represents a larger competition level, while a high value (close to 100) represents oligopoly situation, there is not a general consensus on the correspondence between the value of the index and intermediate concentrations. Typically, if CR 4 < 40, the industry is considered as very competitive. A complete classification table is proposed in [START_REF] Gwin | A guide for industry study and the analysis of firms and competitive strategy[END_REF] and reported here in Table 3. 3. Levels of competition and the CR4

The CR 4 has been employed in the construction industry [START_REF] Ye | Concentration in the international construction market[END_REF], and the U.S. Census Bureau periodically updates it for a number of industries [START_REF] Census | Concentration ratios[END_REF].

Interval estimation of the HHI

In Section 2, we have provided the definition of two concentration indices: the HHI and the CR 4 . Though the HHI provides a more complete view of the market structure, in many cases we do not know the market shares of all the market players and are then unable to compute the HHI, while disposing just of the data about the top 4 firms allows us to compute the CR 4 . However, in [START_REF] Naldi | Interval Estimation of the Herfindahl-Hirschman Index Under Incomplete Market Information[END_REF] it has been shown that we can obtain an interval estimate of the HHI if we know just the market shares of the top market players. This estimate is tight, in the sense that the bounds obtained are deterministic. Its goodness, as determined by the interval width, improves with the number of known market shares and the known fraction of the market. If we know just the market shares of the top four firms, we can therefore gain a better view of the market structure by estimating the HHI in addition to the exact computation of the CR 4 . In this section, we report those bounds.

Let's consider a market made of n firms, with the market share of the i-th largest firm being represented by s i . Let's assume that we know just the market shares of the top 4 firms. We indicate by R = 1 -4 i=1 s i the residual market share, i.e. that in the hands of the remaining firms other than the top four. We also define the residual ratio Q = ⌊R/s 4 ⌋. The lower and upper bounds for the Hirschman-Herfindahl Index, as derived in [START_REF] Naldi | Interval Estimation of the Herfindahl-Hirschman Index Under Incomplete Market Information[END_REF] and reported here for the special case of the top four firms, are shown in Table 4. We do not report for sake of simplicity the derivation, which can however be found in [START_REF] Naldi | Interval Estimation of the Herfindahl-Hirschman Index Under Incomplete Market Information[END_REF].

Type Bound

Lower (n known)

4 i=1 s 2 i + (1-4 i=1 s i ) 2 n-4 Lower (n unknown) 4 i=1 s 2 i Upper (R ≤ s4) 4 i=1 s 2 i + 1 -4 i=1 si 2 Upper (R > s4) 4 i=1 s 2 i + s 2 4 Q + 1 -4 i=1 si -s4Q 2
Table 4. Bounds on HHI

The datasets

In Section 2, we have defined both the concentration indices of interest: the HHI and the CR4. In Section 3, we have shown how the HHI can be estimated if we know either the market share of the top four firms in the market. In order to investigate the relationship between the CR4 and the HHI, i.e., to see if the CR4 can be effectively used to estimate the more complete concentration index represented by the HHI, we consider a set of test cases taken from the real world. In this section, we describe the datasets adopted in this paper for such an assessment.

Here we consider 4 datasets concerning the following industries:

the U.S. consumer book industry; -the civil aviation industry; -the mobile phone industry.

For some of these cases we own the complete market data or, equivalently, the actual HHI. This gives us, or allows us to compute, the actual value of the HHI against which we can compare the estimate we obtain if we know the market share of the top four firms only. If we have just a partial knowledge of the market, i.e., we know just the market shares of the top k firms, we can gauge the goodness of the estimate by observing how wide the estimate interval is: the smaller the interval, the tighter the estimate.

We first deal with the publishing industry data, as reported in [START_REF] Greco | Market Concentration Levels in the U.S. Consumer Book Industry: 19951996[END_REF]. In Table 5, we report the market share of the top 20 firms in the U.S. consumer book industry in 1996. This is enough to compute the CR4 and to perform the interval estimate of the HHI. It wouldn't be enough to compute the HHI, but in [START_REF] Greco | Market Concentration Levels in the U.S. Consumer Book Industry: 19951996[END_REF] the true HHI value is also reported.

Our second dataset represents the production figures of smartphone worldwide. The data are reported in Table 6. In this case, we do not know the overall number of manufacturers. In addition, the number of known market shares is quite small (just the top 5 firms), which account for slightly more than 60% of the market. The data have been taken from [START_REF] Vv | Quarterly telecommunication markets observatory[END_REF].

The third and fourth datasets concern instead the civil aviation industry and reports the number of flights per carrier on two most important routes: Paris-

Results

In order to compare the two indices, we use the definition of the CR 4 and the interval estimation method presented in Section 3 for the HHI. We compare the results obtained for the two indicators in the datasets described in Section 4. In this section, we report the results.

In Table 8 we show the values of the two indicators for the four datasets. At the same time, we can plot the interval estimate of the HHI versus the CR 4 to obtain an immediate idea of the relationship between the two. Though the interval estimate for the HHI does not allow us to predict the precise value of the HHI if we know the CR 4 (or, better, the top four market shares that we employ to compute the CR 4 ), we can examine if the CR 4 can be considered as equivalent to the HHI, in the sense that it preserves the order relationship: if one market situation exhibits a larger CR 4 than another, then it also exhibit a larger HHI. In that case, we would observe a monotonic relationship between 8. Concentration indices for some industries CR 4 and HHI. We show in Fig. 1 that the monotonic relationship we may expect between the two is not confirmed. There is a growing trend for the datasets with the lowest values of the CR 4 , but with the dataset concerning the London-NY flights the HHI band falls.

Conclusions

We have performed a preliminary analysis of the relationship between two major concentration indices: the Herfindahl-Hirschman Index (HHI) and the four-firm Concentration Ratio (CR 4 ). Our analysis aims at establishing first if the HHI can be safely estimated from the same information employed to compute the CR 4 or, secondarily, if the CR 4 can be considered as equivalent to the HHI, in the sense that it preserves the order relationship.

We have employed 4 datasets, pertaining to the the U.S. consumer book industry, the civil aviation industry, and the mobile phone industry.

Our preliminary analysis shows that, if we sort results by the CR 4 values, we can observe a growing trend for the HHI (i.e., the order relationship appears to be preserved) for the first three datasets, but then the HHI for the dataset with the largest CR 4 falls, infringing the order relationship.

  Effective Competition or Monopolistic Competition 40-60 Loose Oligopoly or Monopolistic Competition >60 Tight Oligopoly or Dominant Firm with a Competitive Fringe Table

Fig. 1 .

 1 Fig. 1. Comparison of CR4 and HHI

Table 1 .

 1 The U.S. Department of Justice provided its guidelines for horizontal mergers first in 1985 and later revised them several times, till the latest version in 2010, proposing in Section 5.3 of its 2010 version a classification of markets into three types, reported in Table 1[START_REF] The | Department of Justice and the Federal Trade Commission: Horizontal Merger Guidelines[END_REF]: Levels of competition and the HHI

	HHI Competition level
	<0.15 Unconcentrated Markets
	0.15-0.25 Moderately Concentrated Markets
	>0.25 Highly Concentrated Markets

Table 2 .

 2 Alternative conditions for no competition concerns

	-merger HHI ∆HHI
	<0.1	Any
	0.1-0.2	<0.025
	>0.2	<0.015

Table 5 .

 5 Market shares in the U.S. consumer book industry

	Publisher	Market share [%]
	Random House	12.3
	Simon and Schuster	9.2
	Time Warner	8.6
	Bantam Doubleday Dell	6.7
	Reader's digest	5.7
	Harper Collins	5.2
	Penguin	4.0
	Putnam Berkeley	2.9
	Holzbrinck	2.7
	Golden books	1.7
	Rodale	2.2
	Harlequin	2.3
	Thomas Nelson	1.5
	Hearst	1.6
	Scholastic	1.6
	Andrews and McMeel	1.0
	Houghton Mifflin	0.8
	Barnes and Noble	1.2
	Disney	1.3
	IDG books	0.9
	Others	26.7
	Manufacturer Market share [%]
	Samsung	30.3
	Apple	19.1
	Huawei	4.0
	LG Electronics	3.8
	Lenovo	3.2
	Others	39.6

Table 6 .

 6 Market shares in the worldwide smartphone industryNew York and London-New York[START_REF] Lijesen | Measuring competition in civil aviation[END_REF]. Here we know the full sets of data, which are shown in Table7.

	Carrier	Paris-New York London-New York
	KLM	2	1
	Air France	6	8
	British Airways	5	12
	Lufthansa	3	2
	Delta	2	1
	TWA	1	0
	American Airlines	2	8
	United	1	5
	Continental	2	3
	US Airlines	0	1
	Canada Airlines	1	1
	Sabena	2	2
	Lingus	1	2
	Virgin	0	5
	Iceland Air	1	0
	SAS	1	2
	TAP	1	0
	Kuwait Airlines	0	1
	Iberia	1	0
	India Airlines	0	1

Table 7 .

 7 Number of flights per weekday


Martin Alain

Christine Guillemot

Dominique Thoreau

Philippe Guillotel

Clustering-based Methods for Fast Epitome Generation

Keywords: Epitome, clustering, image coding

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

The concept of epitome was first introduced in [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] by Jojic et al. as a condensed representation of the image texture. Different types of epitomes have then been proposed in the literature. The epitome in [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] is obtained using a patch-based probability model learned from the input image, and is used in different applications such as segmentation, denoising, recognition, indexing or texture synthesis. The epitome construction has been improved in [START_REF] Simakov | Summarizing visual data using bidirectional similarity[END_REF] by using a bidirectional similarity measure based on the notion of "completeness" and "coherence".

A different approach was introduced in [START_REF] Wang | Factoring repeated content within and among images[END_REF] dedicated to texture mapping, and was further extended in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] for image coding purposes. The epitome is in this case the union of epitome charts which are pieces of repeatable textures found in the image. The epitome is associated with a transform map that links patches in the epitome to original patches in the input image. These approaches rely on the search of self-similar or repeatable texture patterns, found in [START_REF] Wang | Factoring repeated content within and among images[END_REF] using the KLT algorithm [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] [START_REF] Shi | Good features to track[END_REF], and in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] using a block matching (BM) algorithm.

The self-similarities in previous approaches are found through an exhaustive search within the image, which is known to be memory and time consuming. In particular, the memory occupation can become prohibitive, especially for high resolution images. We propose in this paper a novel method to reduce the memory occupation and speed up the self-similarities search as well. The proposed approach is based on the work described in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF], with in mind image coding applications, but could also be applied to the approach in [START_REF] Wang | Factoring repeated content within and among images[END_REF]. Note however that we focus in this paper on complexity reduction results and do not present any image coding results.

In [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF], for each non-overlapping block in the image, an exhaustive search has to be performed within the image to find all the blocks whose distance is below a matching threshold ǫM . We propose here a novel approach to reduce the complexity of these searches, which do not optimize the exhaustive search itself, but instead limits the number of searches to be conducted. For this purpose, we first group together non-overlapping blocks that are similar enough and then compute the exhaustive search for each group, with regards to a representative block of said group.

Two methods are presented: in the first one we group similar blocks in lists, in the second one they are grouped in clusters. The list-based method focuses on complexity reduction, by promoting lists with large sizes. In fact using large lists decreases the overall number of lists in which blocks are grouped, and thus limits the number of exhaustive searches to be performed. However, this method may not be optimal for the exhaustive search step, since it is not necessarily conducted using the best representative block of the list. The cluster-based method addresses this issue, since we know that a good representative of the cluster will be close to the centroid. We thus improve the exhaustive searches, but it may increase the complexity compared to the first method.

The rest of the paper is organized as follows. Section 2 reviews the work on epitome generation. Section 3 describes in details the proposed methods to reduce the epitome generation complexity. Finally, experimental results are discussed in section 4.

BACKGROUND -EPITOME GENERATION

2.1. Generative model for image analysis N.Jojic and V. Cheung first introduced the notion of epitome in [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] [START_REF] Cheung | Video epitomes[END_REF]. An epitome is defined as the condensed representation (meaning its size is only a fraction of the original size) of an image (or a video) signal containing the essence of the textural properties of this image.

Given an epitome E and the input image I, a mapping φ between them can be derived. If the mapping and the epitome are given, the original image can also be lossy reconstructed. However the main applications of this approach have been for image analysis such as segmentation, denoising, recognition, indexing or texture synthesis. This patch-based probability model was shown to be of high "completeness" in [START_REF] Simakov | Summarizing visual data using bidirectional similarity[END_REF] but introduces undesired visual artifacts, which is defined as a lack of "coherence". In fact since the model is learned by compiling patches drawn from the input image, patches that were not in the input image can appear in the epitome (see Fig. 1). These artifacts can be a drawback for some applications, e.g. intra coding such as in [START_REF] Wang | Improving intra coding in H.264/AVC by image epitome[END_REF][9] because they will limit the quality of the prediction. As this paper mostly deals with epitome dedicated to image coding this generative model approach will not be discussed in more details. The rest of the paper will rely on the approach described in the next sections.

The approach discussed here was also extended into a so-called Image-Signature-Dictionary (ISD) optimized for sparse representa-tion [START_REF] Aharon | Sparse and redundant modeling of image content using an image-signature-dictionary[END_REF]. The ISD is an (see Fig. 1) that can be used as a dictionary for sparse representations and has several important features such as shift and scale flexibility. For the same reasons as the previous method it will not be considered in the rest of this paper. Fig. 1. Epitome (75x75) and ISD (75x75) generated from Barbara (512x512). Source: [START_REF] Aharon | Sparse and redundant modeling of image content using an image-signature-dictionary[END_REF].

Toward image reconstruction and coding

Wang et al. introduced in [START_REF] Wang | Factoring repeated content within and among images[END_REF] a new approach to build epitome based on self-similarity tracking within the image. This approach has been designed with in mind texture mapping rather than image analysis applications. It then inspired the approach introduced in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] dedicated to image coding. This paper focuses on the latest approach, described below. In this approach the input image I is factored in an epitome E and an assignation map φ. The input image is divided into a regular grid of non-overlapping blocks Bi (block-grid) and each block will be reconstructed from an epitome patch. The epitome itself is composed of disjoint texture pieces called "epitome chart". The assignation map links the patches from the epitome to the input image blocks.

Self-similarities search

The method first proceeds by finding the self-similarities among the image. For each block Bi ∈ I, a list of matched patches (also called matches) M L(Bi) = {Mi,0, Mi,1, ...} is computed such that the average distance between a block and its match is below a threshold ǫM . The distance used here is the sum of absolute differences (SAD). The matches are found through an exhaustive search in the pixel-grid, and the assignation map φ is composed of translation parameters. Note that in the original approach presented in [START_REF] Wang | Factoring repeated content within and among images[END_REF], the selfsimilarities were found using the KLT algorithm [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] [START_REF] Shi | Good features to track[END_REF], which also considers other transformations such as rotation and scaling. The additional parameters can considerably increase the map weight, which is prohibitive in image coding applications. In this case the reconstruction process also involves bilinear sampling, which introduces a blur that can also be an issue in our case (e.g. if the reconstructed image is used for prediction). Furthermore the KLT is more demanding in terms of complexity.

Epitome generation

Then an epitome chart is initialized by the match that can reconstruct the largest region in the reconstructed image I ′ , and is not used so far. Formally, the best match that minimizes the Mean Squared Error (MSE) between I and I ′ is selected to start a new epitome chart EC. The non-reconstructed pixels of I ′ are set to 0 for the MSE computation. The epitome chart is then extended by a set of pixel ∆EC contained in a match that overlaps with EC. The set of matches overlapping with EC defines a set of candidates, and the actual extension is selected such that it minimizes the MSE between I and I ′ while limiting the epitome growth (evaluated by the number of pixels in the epitome). Note that the blocks in I ′ can be reconstructed by the match containing ∆EC, but also all the matches overlapping between EC and ∆EC, called inferred blocks (see Fig 2).

The epitome chart growth stops when the regions reconstructed by the extent candidates ∆EC are smaller than the extent candidate itself, or when the set of matches overlapping with EC is empty. A new epitome chart is then initialized at a new location in the image. The global process iterates until the entire image is reconstructed.

Note that the epitome charts in E are originally obtained at a pixel accuracy, but for coding purpose they can be padded to suit with the block structure of an encoder. The additional blocks and inferred blocks obtained can then be used to improve the assignation map.

Once E is obtained, a refinement of the assignation map quality is performed, which consequently improves the reconstructed image quality. Thus for each non-overlapping block Bi ∈ I, a new search of matches is performed in the epitome E. If a better match than the current one is found, φ is updated. An example of epitome and such reconstructed image, obtained from Lena, is displayed in Fig. 3.

CLUSTERING-BASED METHODS FOR FAST EPITOME GENERATION

The self-similarities search method described in section 2.2.1 ensures that the best matches are found since an exhaustive search is performed. However, this method is known to be expensive in terms of memory consumption and processing time. In fact each block in the block-grid will be associated to a list that can contain a high number of matches. Different methods have been proposed to reduce the complexity of such nearest neighbor (NN) search. Video codecs such H.264 or HEVC usually integrate approximate BM algorithm. Classical approach to accelerate a NN search is to consider a hierarchical search, where the search is first conducted in sub-sampled version of the input image and the result is used to initialize the next level search. Faster approximate method for NN search based on kdimensional tree (kd-trees) have been proposed [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF]. State of the art concerning approximate NN (ANN) search optimization have been proposed in [START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF] and generalized for K-NN search in [START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF]. However all these methods are designed to find only a few best NN, i.e. use a relatively small and fixed value for K. The problem we address here is different because the number of NN, K, is not determined in advance and can reach really high values (up to several thousands, depending on ǫM ). We propose to replace the exhaustive match search by an approximate approach that takes advantage of the self-similarities within the blocks in the block-grid. In a first step, "sufficiently similar" blocks are grouped together. In a second step a match list is computed for each group, with respect to a representative block from the group. Note that this self-similarities search method is still compatible with the epitome generation step described in section 2.2.2, but here blocks in a same group will use the same match list. This not only accelerates the process since less match lists are computed but also saves memory space.

The similarity between the blocks is assessed using the average SAD. We define a tolerance error ǫA that will be used to assign blocks to groups. The assignation threshold ǫA should be smaller than the matching threshold ǫM . Thus we define ǫA via a coefficient αA such as :

ǫA = αA * ǫM , 0 ≤ αA < 1 (1)
Two grouping methods are presented below : first a novel listbased method, second a threshold-based clustering method adapted from [START_REF] Sanjiv | Adaptive K-means clustering[END_REF]. We are here interested in a clustering method working without any prior information on the cluster number, which makes the use of classical methods such as K-means algorithm uneasy.

Note that the grouping is applied only for blocks in the blockgrid.

List-based method for self-similarities search

This method was designed to obtain a simple grouping of similar non-overlapping blocks and follows the steps below:

• For each block Bi, find all blocks whose distance is below the assignation threshold ǫA. The association of Bi and such blocks form a potential list P L(Bi).

• Find the potential list P Lopt with the highest cardinal. This potential list is set as an actual list AL. Blocks in AL are removed from the other potential lists they may belong to. If the block B used to compute a potential list P L(B) is removed from this list, this potential list no longer exists and is simply not considered in future iterations.

• The previous step is iterated until all blocks belong to an actual list.

Finally for each actual list AL(Bi) we determine a match list M L(Bi) = {Mi,0, Mi,1, . . . } obtained through an exhaustive search in the pixel-grid. The list is computed with respect to Bi but is then used by all blocks in AL(Bi) for the epitome generation step. To satisfy the constraint that all the blocks have a reconstruction error inferior to ǫM , the blocks different from Bi in the list AL(Bi) only use a subset of M L(Bi) defined as:

{M ∈ M L(Bi)|d(Bi, M ) ≤ ǫM -ǫA} (2)
This solution avoids computing the distance between blocks and all elements of a match list, which can be time consuming. On one hand, this method tends to favor the creation of a few actual lists with large sizes, which is interesting since less match lists are computed. On the other hand, the blocks Bi used to compute the match lists are not necessarily the most representative blocks of the actual lists, which can limit the matches quality for the blocks in the actual list different from Bi. The method described in the subsection 3.2 addresses this issue.

Threshold-based clustering for self-similarities search

This method is derived from the threshold-based clustering algorithm presented in [START_REF] Sanjiv | Adaptive K-means clustering[END_REF], and proceeds as follow:

• A block B0 is randomly selected and used to initialize the first cluster C0.

• For every block B not assigned to a cluster, compute its distance to the centroid of all existing clusters. If all distances are higher than the assignation threshold ǫA, initialize a new cluster with B as a seed. Otherwise assign B to the closest cluster and recompute the centroid of this cluster as the average of all blocks in the cluster.

• As a result, all blocks are assigned to a cluster. For every cluster, recompute the distances between the cluster blocks and the centroid. If a block B is found to have a distance to the centroid superior to ǫA, it is considered as a singularity and remove from the cluster. B is then used as a seed to initialize a new cluster.

We thus obtain clusters whose blocks are consistent with each other, and thus for each cluster Ci a match list M L(Bi) is computed through an exhaustive search in the pixel-grid, with respect to the block Bi closest to the centroid. We choose not to use the centroid itself, as it is computed as the average of all blocks in the cluster, and as result can contain artifacts not suited for the match search. Thus except for the block Bi, all blocks in Ci will use approximate matches. As for the previous grouping method, we want to ensure that all blocks have a reconstruction error inferior to ǫM . The blocks different from Bi thus only use a subset of M L(Bi), defined as in Eq. 2.

Contrary to the method described in subsection 3.1, this method does not favor groups of large sizes and thus may produce more groups. However, the blocks Bi are better representative for their groups, which improves the quality of the matches.

Trade-off between complexity and quality

The trade-off between the complexity reduction and the matching approximations is set using the parameter αA. When αA = 0 the self-similarities search is performed for each block as in section 2.2.1 and the complexity is not reduced. αA → 1, on one hand groups of higher size are built and therefore we achieve higher complexity reduction, but on the other hand the approximation between the group blocks and the matches can lead to lower epitome quality. Furthermore the subset of matches used for the group blocks defined in Eq. 2 can be really small since ǫA → ǫM , which can degrade the efficiency of the epitome generation step. In practice a good tradeoff is obtained when αA = 0.5 (see section 4).

SIMULATIONS AND RESULTS

Experiments were conducted on a set of 4 images : a frame extracted from the Foreman sequence (CIF), Lena (512 × 512), City (1280 × 720) and Calendar (1280 × 720). The size of the blocks is set to 8 × 8, and the epitome is padded with blocks of the same size. The epitomes were computed on a processor Intel core i7 @2.1 GHz.

First tests were carried out with ǫM = {3.0, 5.0, 10.0, 15.0}. The parameter αA was here set to 0.5. Results are displayed in Table 1. Best results between list-based or cluster-based methods are displayed in bold font. The complexity reduction is assessed by the percentage of the optimized memory occupation over the original one, and the optimized method processing time over the original one. (Note that the maximum absolute processing time for the original method to generate an epitome ranges from a few seconds for CIF resolution, to several ten minutes for SD resolution.) Two processing times are displayed : the self-similarities search time, which is the algorithm step actually optimized, and the complete epitome generation time. For all images, the complexity decreases when ǫM increases, because higher approximations are allowed. Thus the more interesting results are obtained when ǫM = 10.0 or ǫM = 15.0. The cluster-based method is overall faster than the list-based method for the self-similarities search, but is overall slower for the complete epitome generation. On average, the memory occupation reduction is better with the cluster-based method, but the lowest memory occupation is achieved with the list-based method. The memory occupation is prohibitive for images City and Calendar when ǫM = 15.00 with the original method. This shows a very important limitation of the full search method for high resolution images. Note that because of this, comparative results can not be displayed, but the epitome can be still generated when using optimized methods.

The quality of the epitome produced is assessed by the reconstructed image quality. The graphs representing the reconstructed image PSNR as a function of the epitome size are displayed in figures 4, 5, 6 and 7. The epitome size approximately ranges from 10% to 80% of the input image size, and is inversely proportional to the matching threshold ǫM . The reconstruction PSNR approximately ranges from 30 dB to 45 dB. For all images, whatever the epitome generation method, the curves are almost identical. The two methods presented in this paper can thus reduce complexity while keeping the same epitome quality.

Despite some disparities in the complexity results presented in Table 1, the performances between the two methods remain overall close. Complexity results for different values of αA are displayed in Table 2, with ǫM = 10. As expected, the complexity decreases as αA increases. For αA = 0.25 and αA = 0.5, performances of the two methods remain similar, despite some disparities. However when αA = 0.75, the complexity reduction is more important for the list-based method. This illustrates the behavior of this method, which can reduce drastically the complexity when allowing important approximations. However, when evaluating average reconstruction performances (see Fig. 8), we can see that it has a negative impact, as it is the only point which increases the epitome size while decreasing the reconstruction PSNR. Note that, as for the previous experiment, the reconstruction performances are very similar for all images, but for clarity reasons we only show the average results. For the cluster-based method, the complexity gain when αA = 0.75 is limited compared to αA = 0.5, and the reconstruction PSNR seems low compared to the epitome size, even though it is not as evident as for the previous method. Therefore αA = 0.5 seems to be, for both methods, a good trade-off value between complexity and epitome quality.

CONCLUSION

This paper presents efficient algorithms for epitome generation, based on list or cluster methods. The grouping of non-overlapping blocks limits the number of subsequent exhaustive searches over all overlapping blocks, and thus reduces the memory occupation as well as the processing time. Experiments show that interesting complexity results can be obtained without degrading the epitome quality.

In future work, the methods presented in this paper will be implemented in epitome-based image coding applications.

City reconstruction performances

Original method List-based method Cluster-based method

Fig. 2 .

 2 Fig. 2. Epitome chart extension process with inferred blocks. Source: [4].

Fig. 3 .

 3 Fig. 3. Epitome of Lena (512x512) (left) and the reconstructed image (right).

Fig. 4 .Fig. 5 .

 45 Fig. 4. Reconstructed Foreman PSNR vs epitome size.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Reconstructed City PSNR vs epitome size.

5 Fig. 8 .

 58 Fig. 8. Reconstructed average PSNR vs epitome size.

Table 1 .

 1 Memory occupation and computation time % with respect to original method, depending on ǫM , with αA = 0.5.

			List-based method	Cluster-based method
	I ǫ M	Memory Search	Total	Memory Search	Total
			load (%) time (%) time (%) load (%) time (%) time (%)
	Foreman	3.0 50.18 5.0 49.54 10.0 25.00 15.0 18.08	68.62 60.72 32.65 21.61	73.93 60.12 41.39 42.37	47.85 45.22 19.06 14.59	67.31 55.80 28.58 18.00	70.15 61.88 50.36 55.25
		3.0 98.18	75.54	78.92	96.81	69.05	70.13
	Lena	5.0 63.61 10.0 29.98	61.00 37.49	65.24 51.92	48.28 23.66	56.12 31.60	66.19 55.74
		15.0 19.96	23.09	59.69	21.64	23.56	64.48
	City	3.0 60.54 5.0 60.71 10.0 51.47	66.75 64.165 64.160 65.27 48.07 60.07	55.85 56.47 48.18	68.62 62.48 47.06	69.25 62.80 59.75
	Calendar	3.0 84.66 5.0 48.43 10.0 28.33	68.36 54.76 32.58	66.44 58.83 52.97	80.69 42.08 53.98	70.36 53.25 42.43	68.02 59.94 57.91

Table 2 .

 2 Memory occupation and computation time % with respect to original method, depending on αA, with ǫM = 10.0.

			List-based method	Cluster-based method
	I α A	Memory Search	Total	Memory Search	Total
			load (%) time (%) time (%) load (%) time (%) time (%)
	Foreman Lena	0.25 70.66 0.50 25.00 0.75 9.58 0.25 79.99 0.50 29.98 0.75 9.03	53.17 32.65 21.94 60.93 37.49 23.27	61.51 41.39 24.74 72.73 51.92 26.57	67.86 19.06 7.32 70.13 23.66 15.91	51.42 28.58 19.96 56.41 31.60 25.48	58.41 50.36 46.74 65.69 55.74 53.73
	City	0.25 86.30 0.50 51.47 0.75 19.46	64.06 48.07 33.84	67.54 60.07 42.41	84.09 48.18 38.17	63.30 47.06 40.90	66.99 59.75 58.83
	Calendar	0.25 69.76 0.50 28.33 0.75 10.13	51.43 32.58 22.69	65.30 52.97 29.61	65.85 53.98 48.35	49.95 42.43 36.86	66.65 57.91 57.94

dB] Epitome size / Input image size [%]

		48.00
		46.00
		44.00
	Reconstruction PSNR [	34.00 36.00 38.00 40.00 42.00
		32.00
		30.00
		28.00
		0.00	10.00	20.00	30.00	40.00	50.00	60.00	70.00	80.00	90.00


Jean-Jacques Girardot

Amélie Bichet-Miñaro

EVALUATION OF PROJECTS FUNDED BY THE EUROPEAN COMMISSION AND OF THE EXISTING INFORMATION OF THE GDS THAT MIGHT BE RELEVANT IN THE TERRITORIAL INTELLIGENCE FIELD. COORDINATION GROUP WP4P "PROJECTS" OF CAENTI

Keywords: Territorial intelligence, Projects of territorial development, Governance, Knowledge-based society

Evaluation of projects funded by the European Commission and of the existing information of the GDs

that might be relevant in the Territorial Intelligence field. Coordination Group WP4P "Projects" of CaENTI

INTRODUCTION

The coordination research activity WP4P [Projects] relates to the evaluation of projects funded by the European Commission and of the existing information of the GDs that might be relevant in the territorial intelligence field.

It is a technical sub-activity of the work package 4 (WP4) of CAENTI. The WP4 concerns the spreading of fundamental methods and research design in territorial information analysis within the social sciences and humanities. The CAENTI, Coordination Action of the European Network of Territorial Intelligence, is a project funded by the 6 th research framework-programme of the European Union, from March 2007 to February 2009.

It is a specific activity, insofar as it corresponds to a suggestion of the CAENTI project evaluators. It was integrated in the WP4 because this work package includes a coordination activity linked to territorial information and because most of the concerned projects a priori seemed to be research projects. Thus, the WP4P coordination group mainly contributes to the second objective of the work package 4: increasing the territorial information use.

During the first six months of the CAENTI activity, the group was organized. It defined a plan of work. It selected a set of key-words that allows organizing the search and the identification of relevant projects and information in the territorial intelligence field. A first selection of projects drafted from the European directories of research projects showed that this set of key-words must be widened because this selection only focused on six projects.

During the conference, the WP4P coordination group also defined an activities plan.

ORGANIZATION, OBJECTIVES AND ACTIVITIES OF THE "Projects" COORDINATION GROUP.

During the Kick-off meeting in BESANÇON, on March 23 rd -24 th 2006, the representatives of the participants debated the consortium agreement and the composition of the coordination groups, and in particular of the WP4P "Projects". For the year 2006, the coordination group was composed by eight skilled and experienced researchers who have a good knowledge of the European projects. They work in different parts of the European territory, what allows identifying projects in the main linguistic regions, and contacting their responsible.

During the meeting of the coordination groups leaders of the work package 4 in BESANÇON, on June, the 7 th 2006, the WP4P group objectives were formulated under the form of two questions:

1. Among the projects that were supported by the European Commission, which of them have an object corresponding to the questionings of the territorial intelligence? 2. Which relevant information for territorial intelligence the General Directions of the European Commission have, in addition to those that are published on the official websites?

A first strategy was defined:

1. Identifying the projects that belong to the territorial intelligence field and dividing them according to large European regions between the members of the group so as they make a first evaluation report on the base of a frame established by the group. These evaluation reports are compared within the group.

2. Asking the general directions so as to identify the information they have, that have interest for territorial intelligence and that complete the territorial information that are identified by the WP4I group in the European data bases, especially on Internet.

In order to organize the complementarity of the WP4P and WP4I groups on the theme of the relevant information, we decided to organize a coordination meeting of the WP4I and WP4P after the coordination seminar of the work package 6 "Tools for actors" that was planned on June, the 29th in DURBUY, near to LIEGE, in Belgium, insofar as the WP4I is coordinated by the University of LIEGE and most of the members of the two groups will attend the WP6 coordination meeting.

Amélie BICHET-MIÑARO, as graduate in Political Sciences and Public Law, was in charge of a first identification of projects in the prospect of this meeting, in particular by exploiting the main projects books that are financially supported by the European Commission and the CORDIS website. It proved itself to be too selective, insofar as it only isolated three projects, mainly within two important groups of projects that are linked on the one hand to governance and on the other hand to social inclusion.

The WP4I group presented the first results about the inventory of the territorial information from European statistic bases and sites and national sites of the countries that are members of the European Union.

As regards the projects identification, the coordination group debated the opportunity to widen:

-The canvassing field to all the funding, beyond the research activity, or -The key-words used to identify projects, especially by adding:

-Territory, and -Communication and information technologies.

The debate insisted on the complexity of the identification of action projects. If each one wanted to integrate action projects, the prospect of widening of the canvassing field faced three difficulties:

-The importance of the number of concerned projects of action; -The fact that, in opposition to the research projects, the action projects are not managed by the European Commission but by national or regional relays; -Their inventory is often incomplete or disparate but there is one, because of the previous reasons.

It did not seem appropriate to work according to the funds, as the European Social Fund, the European Fund of Economic and Regional Development, but rather by programmes that have their own management; The funds define sets that are too broad and extremely diversified of ground projects. Firstly, we should rather identify programmes such as EQUAL to make the selection within more homogenous sets of projects. On the other hand, the access to projects repertories and the description of these projects are very unequal according to the programmes. An inventory of the programmes will remain to be established so as to valuate their interest in relation with territorial intelligence and the possibility to ask projects repertories.

The group eventually chose to work again on the selection of research projects with these new two key-words before widening the projects identification to all the general directions, after the selection procedure will be satisfying as regards the research projects and the repertories of action projects will have been identified.

A debate took place about the opportunity to integrate other key-words, but most of the suggested key-words, as participation, were rejected because they are in many projects and they have a different meaning according to the project. They are not selective, neither from a quantitative nor from a qualitative point of view because of their polysemy. Consequently, we should try to find keywords which meaning is relatively objective and does not very much, otherwise many projects are identified, but few are conserved after having read its summary once.

The debates also concerned the projects evaluation, after they have been selected. The group insisted on the need to ask the projects responsibles, and even to meet them.

As regards the information that are available at the GDs level, the group decided to wait for the WP4I to have finished the general inventory that was started at the territorial information level, at the end of 2006, before making a survey by asking the general directions, so as to be able to specify the information we looked for and above all to make the difference with the ones we could identify by ourselves.

We suggest a new selection of projects that remains limited to five projects:

-Achieving Sustainable and Innovative Policies through Participatory Governance in a Multi-Level Context -EXSPRO: Social Exclusion and Social Protection -the Future Role for the EU -G-FORS : Governance for sustainability Neighbourhood Govern : Neighbourhood : Governance-Capacity for Social Integration -REGIONET: Strategies for Regional Sustainable Development: An Integrated Approach Beyond Best Practice

The inventory of the action programmes was postponed because it implied to get more information from the general directions, what we planned to do about the information, at the beginning of the second period.

PROSPECTS

This part was updated according to debated that took place in ALBA IULIA.

So as to widen the first selection of research projects, we suggest making a new definition of the key-words that are used to identify projects. This proposal goes together with the proposal of diversify the research modes by using the classic search engines on Internet, as well as repertories, data bases or European websites that were identified in advance.

The direct use of the Internet search engines is able to identify as action projects as research ones. It gives a bonus to the projects that have a good visibility on Internet, without prejudge of their local visibility. It also implies the research actions are made in several languages.

Consequently it implies a more important mobilisation of the work group and the reinforcement of its coordination because:

-It decentralises the identification of the projects according to a linguistic logic -The members of the group will also inherit the charge to locate data bases and repertories of action projects which management is often divided by countries or by countries groups.

-The coordination group implies a more regular use of the cooperative workspace CooSpace, to animate the exchanges.

As a consequence we decided a coordination meeting would take place soon to organise the activity of the coordination group. It will particularly be used to widen the list of key-words, in accordance with the specificities of the direct seek on Internet, on the base of suggestions that will be centralised on CooSpace. It will have to concretely organise the prospects on the longer term.

When the projects will have been isolated by the means of key-words, they will be divided at the geographical-linguistic level so as the members of the group contact the projects responsibles, to be sure they still exist and to confirm they belong to the territorial intelligence field. They will draft an evaluation report for each of the "confirmed" projects.

Then, the sets of projects will be evaluated by the coordination group on the base of these reports, so as to make a general evaluation report.

The ten most relevant projects will be invited to an evaluation seminar with the members of the coordination group and with the CAENTI actors.

CONCLUSION

During the six first months of the CAENTI action, we firstly concentrated on the projects. Indeed, we wanted to wait for the results of the first research activities of the WP4I group about territorial information and indicators. This group started a state of the art of the territorial information that are available on Internet and on the European websites that were supplied with the European Commission.

We identified the relevant research projects thanks to a set of key words that remains open. Our first selection emphasized the great number of projects about governance and social exclusion. Nevertheless, they were only five projects that belonged to the territorial intelligence field.

The coordination team will now work to:

-Make a definitive definition of the criteria to be used for a direct research on Internet, as well as in the European on lines data bases or directories.

-Find new sources, directly or by asking general directorates, in order to explore action projects, -Confirm the relevance of each selected project; -Evaluate the selected projects, with an interview of their responsible of projects; -Globally valuate the selected projects, through the coordination group work and a seminar.

In 2007, the objective is to organize a seminar with the project leaders of the relevant projects of territorial action and with the CAENTI territorial actors, so as to study together the territorial intelligence principles and practice.

The identification of the GD information that is relevant as regards territorial intelligence will be led in close cooperation with the WP4I group, which makes research activity about territorial information.

BIBLIOGRAPHY

  She presented a first selection of research projects at the time of the coordination meeting of the WP4I and WP4P groups in LIEGE on June, the 30 th 2006. This first identification of the research projects used the following sources: -European Union-supported research in social sciences and humanities 1998-2005, briefing papers, European Commission, Community research -Social sciences and humanities in FP6, Projects' synopses all calls, Citizens and governance in a knowledge-based society, Community research -European Research, A guide to successful communications, General information, European Commission, Community research -Assessing the Social and Environmental impacts of FP internet web sites The projects that started before 1998 were rejected. This identification of relevant projects was made by using a first series of key-words: -Territorial development -Sustainable development -Governance -Knowledge-based society

  Intelligence, Territoire, Décentralisation, ou la Région à la française.", in Actes des 3 ème rencontres TIC & Territoire : quels développements ?, LILLE (France), 14 Mai 2004, Enic et Cies, ISDM, n° 16. <URL: http://isdm.univtln.fr/PDF/isdm16/isdm16a163_dumas.pdf> GIRARDOT J.-J., 2004: "Intelligence territoriale et participation", in : Actes des 3 ème rencontres TIC & Territoire : quels développements ?, LILLE (France), 14 Mai 2004, Enic et Cies, ISDM, n° 16, 13 p., <URL:http://isdm.univtln.fr/PDF/isdm16/isdm16a161_girardot.pdf> DAUMAS J.C., GIRARDOT J.-J., et al., 2002: Programme de recherche du pôle 1 "Intelligence territoriale" de la Maison des Sciences de l'Homme Claude-Nicolas Ledoux, sous la direction de F. FAVORY, BESANÇON (France).

	BERTACCHINI Y., GIRARDOT J. -J.,
	GRAMMACIA G., 2006: "De l'intelligence
	territoriale :	Théorie,	Posture,	Hypothèses,
	Définition", in : Actes du 5ème Colloque TIC &
	Territoire : quels développements ? Université de
	Franche-Comté, BESANÇON (France), 9 et 10 juin
	2006, ISDM, n° 26, 7 p. <URL: http://isdm.univ-
	tln.fr/PDF/isdm26/3.YB-JJG-GG.pdf>
	DELVOYE J.-M., GIRARDOT J.-J., et al., 2004:
	"Intelligence	territoriale	et	développement
	communautaire : application de la méthode
	Catalyse à Seraing" -2ème colloque international
	sur les programmes locaux et régionaux de santé,
	QUÉBEC (Canada), 15 octobre 2004, 4 p.
	BERTACCHINI Y., 2004: "Entre information &
	processus de communication : l'intelligence
	territoriale", in Actes des 3 ème rencontres TIC &
	Territoire : quels développements ?, LILLE
	(France), 14 Mai 2004, Enic et Cies, ISDM, n° 16,
	13	p.	<URL:	http://isdm.univ-
	tln.fr/PDF/isdm16/isdm16a154_bertacchini.pdf>
	DUMAS P., 2004: "


Sylvain Durand
email: sylvain@durandchamontin.fr

Jonathan Dumon

Nicolas Marchand

J Fermi Guerrero-Castellanos

Event-Based Control for Embedded and Networked System Application to a Mini Quadrotor Helicopter using Motion Capture

Although periodicity simplifies design and analysis in control theory, it is no more adapted for embedded and networked cyber-physical systems because it results in a conservative usage of resources. Indeed, the control signal is computed and updated at the same rate regardless whether is really required or not, and is periodically sent on the communication link. On the other hand, event-driven sampling calls for resources whenever they are indeed necessary. An event-based controller is proposed in this paper as a solution to reduce the updates from the controller to the plant. An eventbased corrector is also added to reduce the communications from the plant to the controller. The approach is tested for controlling the position of a real-time mini quadrotor helicopter using a motion capture system with deported controller. A reduction of the computing/communication resources utilization is highly demonstrated for similar final performance.

INTRODUCTION

A cyber-physical system is an integration of computing devices with physical processes. In practice, embedded computers and networks monitor and control physical processes (usually with feedback loops) which, in return, affect computations and communications. The intersection between physical and information-driven (cyber) functions hence represents a challenge and results in innovation, see [START_REF] Lee | Introduction to Embedded Systems: A Cyber-Physical Systems Approach[END_REF]. The use of digital platforms also emerges as an obvious trend to save space, weight and energy. However, their implementation can result in additional challenges, like determining how frequently the control signal needs to be updated and applied such that the stability properties are still guaranteed. Indeed, the consistently-used periodic fashion cannot be applied anymore in embedded and networked systems (with limited resources) and resource-aware implementations are required. In this context, recent works addressed alternative frameworks where the control law is event-driven. Whereas the control law is computed and updated at the same rate regardless whether is really required or not in the classical timetriggered approach, the event-based paradigm relaxes the periodicity of computations and communications in calling for resources whenever they are indeed necessary (for instance when the dynamics of the controlled system varies). Typical event-detection mechanisms are functions on the variation of the state (or at least the output) of the system, like in [START_REF] Årzén | A simple event-based PID controller[END_REF], [START_REF] Durand | Further results on event-based PID controller[END_REF], [START_REF] Sandee | Eventdriven control as an opportunity in the multidisciplinary development of embedded controllers[END_REF], [START_REF] Sánchez | On the application of different event-based sampling strategies to the control of a simple industrial process[END_REF], [START_REF] Åström | Comparison of Riemann and Lebesque sampling for first order stochastic systems[END_REF], [START_REF] Heemels | Analysis of event-driven controllers for linear systems[END_REF], [START_REF] Lunze | A state-feedback approach to event-based control[END_REF], [START_REF] Eqtami | Eventtriggered control for discrete-time systems[END_REF], [START_REF] Durand | Event-based stabilization of linear system with communication delays in the measurements[END_REF]. Although event-based control is well-motivated, only few works report theoretical results (about stability, convergence and performance) and practical implementation. It has notably been shown in [START_REF] Åström | Comparison of Riemann and Lebesque sampling for first order stochastic systems[END_REF] that the control law can be updated less frequently than with a periodic scheme while still ensuring the same performance. Stabilization of linear and nonlinear systems is analyzed in [START_REF] Velasco | On Lyapunov sampling for eventdriven controllers[END_REF], [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF], [START_REF] Marchand | A general formula for event-based stabilization of nonlinear systems[END_REF], [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF], where the events are related to the variation of a Lyapunov function or the time derivative of a Lyapunov function (and consequently to the state too).

In the present paper, networked control systems (where the control loop is closed over a network) and their communication constraints are addressed. A deported controller has to control a cyber-physical system while reducing the communications between both (delays and packet losses are not considered here). Among many embedded and networked cyber-physical systems, Unmanned Aerial Vehicles (UAVs) have received growing interest in research. In particular, the mini quadrotor helicopter gives rise to great enthusiasm because of its high manoeuvrability, its payload capacity and its ability to hover [START_REF] Castillo | Real-time stabilization and tracking of a four-rotor mini rotorcraft[END_REF]. The quadrotor is an underactuated dynamic system with four input forces and six output coordinates (attitude and position). However, this system can be broken down into two subsystems, one defining the translation movement (position) and the other one the rotation movement (attitude). These subsystems are coupled in cascade since the translational subsystem depends on the rotational one, but the rotational subsystem is independent of the translational one. Nevertheless, event-based control is quite new for UAVs systems with high constraints, since the system has to be actively actuated to remain stable: attitude control was addressed in [START_REF] Téllez-Guzmán | Event-based LQR control for attitude stabilization of a quadrotor[END_REF], [START_REF] Guerrero-Castellanos | Event-triggered nonlinear control for attitude stabilization of a quadrotor[END_REF], [START_REF] Guerrero-Castellanos | Attitude stabilization of a quadrotor by means of event-triggered nonlinear control[END_REF] and position control is addressed now. Furthermore, in order to release the platform from decision making related to guidance and navigation, position and orientation are calculated by a motion capture system here, where the movement of the vehicle is processed through high resolution cameras (based on the principle of inverse projection and triangulation).

The suggested setup to reduce the communications in such an architecture is divided into two parts. First, based on a seminal event-based PID controller (initially proposed in [START_REF] Årzén | A simple event-based PID controller[END_REF] and then improved in [START_REF] Durand | Further results on event-based PID controller[END_REF]), an event-based RST controller is proposed as a solution to reduce the communications from the controller to the plant. A RST digital controller [START_REF] Landau | The R-S-T digital controller design and applications[END_REF], [START_REF] Robert | Sampling period dependent RST controller used in control/scheduling co-design[END_REF] can be seen as the discrete-time version of the well-known PID controller for first-and second-order controlled systems. However, it allows more tuning (because the RST controller allows independent specification of tracking and regulation performance whereas a PID only operates on the regulation error) and can be extended to systems of any order (this is not treated here). Then, an event-based corrector [START_REF] Lehmann | Event-based control with communication delays[END_REF], [START_REF] Durand | Event-based stabilization of linear system with communication delays in the measurements[END_REF] is also applied in order to reduce the communications from the plant to the controller. The idea is to make a copy of the plant model, on both sides of the network, and correct them when they deviate too much from the real system. The copy of the model in the controller side is used to compute the control law and the measurement is sent to the controller side over the communication link only when it has to be corrected. The rest of the document is organized as follows. In section I, preliminaries on PID and RST controllers are introduced. The event-based PID control developed in [START_REF] Durand | Further results on event-based PID controller[END_REF] is recalled and the new event-based RST strategy is detailed. The evenbased corrector adapted from [START_REF] Durand | Event-based stabilization of linear system with communication delays in the measurements[END_REF] to the RST scheme is also presented. The experimental platform is then depicted in section II. Experimental results highlight the capabilities of the proposed approach and a significant reduction of the communications. Discussions finally conclude the paper.

I. EVENT-BASED RST CONTROLLER

A. From (time-triggered) PID to RST control

The continuous-time textbook PID controller is

u(t) = u p (t) + u i (t) + u d (t) (1)
with

u p (t) = K p e(t) u i (t) = K i t 0 e(t)dt u d (t) = K d de(t) dt
where u(t) is the control signal and

e(t) := y sp (t) -y(t) (2)
is the error between a given setpoint y sp (t) to track and the measurement of the controlled system y(t). u p (t), u i (t) and u d (t) are the proportional, integral and derivative parts of the PID controller, where K p , K i and K d are tunable parameters. A low-pass filter is also added in the derivative term (to avoid problems with high frequency measurement noise), where N is the filter gain hereafter. The control law is then written in the z-domain (more convenient for discrete-time systems), where the proportional part is straightforward, integral and derivative parts are discretized using the backward difference approximation (see [START_REF] Durand | Further results on event-based PID controller[END_REF] for more details). This gives

U p (z) = K p E(z) U i (z) = K i h 1 -z -1 E(z) U d (z) = K d N (1 -z -1 ) (N h + 1) -z -1 E(z) (3)
where h is the (constant) sampling period.

The RST digital controller form [START_REF] Landau | The R-S-T digital controller design and applications[END_REF] is preferred in the sequel. Its architecture is depicted in Fig. 1. Actually, the RST controller allows independent specification of tracking and regulation performance (through T and R parameters respectively), whereas the PID controller only operates on the regulation error (which corresponds to the particular case T = R). Furthermore, whereas the PID design is restricted to first-and second-order systems, the RST can be extended to any order (but this is not treated here).

A period-dependent expression [START_REF] Robert | Sampling period dependent RST controller used in control/scheduling co-design[END_REF] is given here (since the sampling interval will vary in the sequel in the eventbased scheme). In practice, R and S are obtained from the PID algorithm when developing (3) and considering T = R, leading to

R(z, h) S(z, h) := r 0 ( h) + r 1 ( h)z -1 + r 2 ( h)z -2 (1 -z -1 )(1 -s 1 ( h)z -1 ) (4)
where

r 0 ( h) = K p + K i h + K d N δ( h) r 1 ( h) = -K p -K p + K i h + 2K d N δ( h) r 2 ( h) = K p + K d N δ( h) s 1 ( h) = δ( h) (5)
with δ( h) := 1 1 + N h Consider a (exact or approximated) discrete-time secondorder transfer function

G(z) = B(z) A(z) := b 1 z -1 + b 2 z -2 1 + a 1 z -1 + a 2 z -2 (6)
Note that the dependence on h for parameters a 1 , a 2 , b 1 , b 2 is omitted here for the sake of simplicity, because the sampling period of the system to control will remain constant in the sequel (only the sampling interval of the control law will vary). Then, considering the system (6) and applying the RS control law (4), the closed-loop transfer function becomes

G cl (z) = B(z)R(z, h) A(z)S(z, h) + B(z)R(z, h) (7)
The RS control parameters r 0 , r 1 , r 2 and s 1 can be calculated directly in the discrete-time domain in such a way that G cl (z) matches with a desired closed-loop model. This can be done solving the Bezout's equation (also called Diophantine equation) for instance, see [START_REF] Landau | The R-S-T digital controller design and applications[END_REF], [START_REF] Robert | Sampling period dependent RST controller used in control/scheduling co-design[END_REF]. However, in the present paper, the PID control parameters K p , K i , K d and N are calculated in the continuous-time domain by pole placement, and so are then obtained the R and S parameters solving [START_REF] Durand | Further results on event-based PID controller[END_REF] for a given sampling period h (note that the same values for K p , K i , K d and N are then kept when making varying the sampling interval in the sequel). Then, the zeros of the closed-loop system [START_REF] Eqtami | Eventtriggered control for discrete-time systems[END_REF] have to be considered to calculate the filtering transfer function T . The closed-loop transfer function with the complete RST control law becomes

G cl (z) = B(z)T (z, h) A(z)S(z, h) + B(z)R(z, h) (8)
Generally, no steady-state error is required, which yields

B(1)T (1, h) A(1)S(1, h) + B(1)R(1, h) = 1 (9)
and since the controller (4) has an integrator, i.e. S(1, h) = 0, then T (1, h) = R(1, h). Therefore, the simplest choice is

T ( h) = r 0 ( h) + r 1 ( h) + r 2 ( h) (10)
More complex solutions for T are not detailed here.

B. Event-based RST control

The approach is based on an original event-based PI controller, which setup was proposed for the first time in [START_REF] Årzén | A simple event-based PID controller[END_REF] and then improved in [START_REF] Durand | Further results on event-based PID controller[END_REF]. By event-based PID control we mean a set of two functions: 1) an event function ǫ, that indicates if one needs (when ǫ ≤ 0) or not (when ǫ > 0) to recompute the control law; 2) a PID control law υ. The event function is time-triggered with the sampling period h (that is the same as for the corresponding conventional time-triggered PID). In the present paper, an event is enforced when the absolute error crosses a given detection level ē [START_REF] Durand | Further results on event-based PID controller[END_REF], this defines the event function as

ǫ(t) = ē -e(t) (11)
where e(t) is defined in [START_REF] Åström | Comparison of Riemann and Lebesque sampling for first order stochastic systems[END_REF]. On the other hand, the control signal is constant between two successive events

u(t) = υ(t k ) ∀t ∈ [t k , t k+1 [ (12)
where t k is a sampling instant (called an event) and, therefore, the length of the sampling intervals h := t k -t k-1 becomes not equidistant in time anymore. Several event-based PI strategies are suggested in [START_REF] Durand | Further results on event-based PID controller[END_REF]. In particular, the algorithm with exponential forgetting factor of the sampling interval is applied here. The approach is somehow similar to the anti-windup mechanism used in control theory, where the error induced by the saturation has to be compensated. The integral part (in the z-domain) becomes

U i (z) = K i λ i (h) 1 -z -1 E(z) (13)
with

λ i (h) = he αi( h-h)
where α i is a degree of freedom to increase/decrease the exponential sampling interval of the integral part. One can refer to [START_REF] Durand | Further results on event-based PID controller[END_REF] for further details. Based on this seminal idea, an exponential forgetting factor is also applied in the derivative term, which yields

U d (z) = K d N (1 -z -1 ) N λ d (h) + 1 -z -1 E(z) (14)
with

λ d (h) = h + (h -h)e α d ( h-h)
where α d is a degree of freedom to increase/decrease the exponential sampling interval of the derivative part. From these observations, an event-based RST controller is finally obtained R(z, h) S(z, h)

:= r 0 (h) + r 1 (h)z -1 + r 2 (h)z -2 (1 -z -1 )(1 -s 1 (h)z -1 ) T (z, h) = r 0 (h) + r 1 (h) + r 2 (h) (15)
where

r 0 (h) = K p + K i λ i (h) + K d N δ λ d (h) r 1 (h) = -K p -K p + K i λ i (h) + 2K d N δ λ d (h) r 2 (h) = K p + K d N δ λ d (h) s 1 (h) = δ λ d (h) (16)
where δ was defined in (5) for a constant sampling period, λ i and λ d are defined in ( 13) and ( 14) respectively.

C. Event-based corrector

Consider the system to control is such that

Y (z) = G(z)U (z) + H(z)P (z) (17)
where Y and U are the (measured) output and (control) input of the system, P is an exogenous disturbance. The plant to control G(z) is a discrete-time second-order transfer function as described in [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF]. The error on modeling and uncertainties are all lumped into the disturbance (not necessarily secondorder) transfer function H(z) which is not detailed here.

As already explained, a RST controller ( 4)-( 5), ( 10) can make the closed-loop system (8) matches with a desired closed-loop model. However, in the present paper an eventbased RST controller (15)-( 16) is applied instead of the classical (time-triggered) controller. Furthermore, a networked control system is considered here and communications have to be reduced. For this reason, an event-based corrector [START_REF] Lehmann | Event-based control with communication delays[END_REF], [START_REF] Durand | Event-based stabilization of linear system with communication delays in the measurements[END_REF] is used to reduce the measurement transmissions (note that neither delays nor packet losses due to the communication link are considered here). The idea behind the eventbased corrector is to have a copy of the system model (without disturbance) as defined in [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF], on both sides of the network. The control law is calculated using the copy in the controller side, whereas the second copy is used in the plant side in order to detect when the model does not behave as the real system. Both copies are then updated with the real system output.

The system architecture with both the event-based controller and the event-based corrector is presented in Fig. 2.

1) Event generator for correction: This part runs a copy of the undisturbed system model ( 6). An event is then generated for correction when the difference between the (real) perturbed system output y(t) and the output of the model copy y m (t) (in the plant node) reaches a given threshold ȳ, that is (in time domain) when

y(t j ) -y m (t - j ) = ȳ (18)
where t - j is the time just before the event, and so is corrected the value of the event generator state such that where t + j is the time just after the event. This defines the correction's event instant t j . The system output y(t j ) is then sent to the corrector (in order its model is also corrected) over the communication link.

y m (t + j ) = y(t j ) (19)
2) Corrector: The corrector itself is in the controller node. It also runs a copy of the undisturbed system model ( 6) which has also to be updated when condition ( 18) is satisfied, which yields

y c (t + j ) = y(t j ) (20)
where y c (t) is the output of the model copy in the controller node.

3) Event-based controller: In fact, the controller is not directly computed for the system to control without disturbance [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF], neither for the model copy in the plant node, but for the copy of the model available in the controller node, that is the corrector model [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF] with updates [START_REF] Tabuada | Event-triggered real-time scheduling of stabilizing control tasks[END_REF]. The control's event instants t i are hence determined by the vanishing of the event function [START_REF] Landau | The R-S-T digital controller design and applications[END_REF] applied to y c , which hence becomes

ǫ(t) = ē -e c (t) (21
) with e c (t) := y sp (t) -y c (t) Also, the control law is no more computed using the error e(t) but with e c (t) instead. The control signal u(t i ) is then sent to the plant in order to be applied to both the plant and the event generator for correction.

II. APPLICATION TO POSITION CONTROL OF A MINI QUADROTOR HELICOPTER USING MOTION CAPTURE

A. Experimental platform

The algorithms are tested with a 18 grams Blade Nano QX quadricopter 1 . Its position and orientation are calculated by a Vicon motion capture system with T40s cameras2 through Tracker software 3 . It is then sent to the control unit through a UDP frame every 2ms. Algorithms are programmed in Matlab/Simulink and implemented in real time at 200Hz to a target computer using xPC target toolbox. Finally, control variables are sent to the quadricopter through a GIPSA-lab's built-in bridge that converts UDP frames to DSMX 2.4Ghz protocol 4 . An overview of this architecture is presented in Fig. 3. The event-based RST controller is implemented in the control unit side. As regards the event-based corrector, whereas the event generator and the corrector should be implemented in the Vicon system side and the control unit side respectively, in practice both parts are also implemented in the control side in the present case. Indeed, it was decided to implement the event generator in the controller side for the sake of simplicity (because the Vicon unit algorithm is not accessible nor modifiable). As a consequence, all the blocks in Fig. 2 (except the plant) can be easily implemented in Matlab/Simulink in the control unit.

B. System model

The leveling control of the mini quadrotor helicopter (the control of pitch θ and roll φ angular velocities) is already done in a (non accessible) internal loop. Then, it is possible to control i) the yaw ψ angular velocity, ii) the altitude z and iii) the longitudinal V long and lateral V lat velocities. The aim here is to control the position x, y and z of the quadricopter (see Fig. 4 for a spacial representation). It is assumed that all the control variables can be independently controlled. It is also assumed that both longitudinal and lateral velocities similarly behave (they have the same model). The control of the yaw angle is not treated here. Several experiments showed the system is highly nonlinear, with saturation and varying parameters (with respect to the battery power, the system aging, etc...), and is time delayed (delays are neglected here). Nevertheless, a simple model of the system has been obtained. The suggested model can be far from the real system but it will be shown in the sequel that the controller is robust enough and such an approximation allows to reduce the communications anyway. Actually, the system can be divided into several independent parts:

1) The longitudinal and lateral velocity, i.e. V long and V lat respectively, are (discrete-time) second-order transfer functions as defined in [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF], that gives (after identification for the longitudinal case)

B(z) A(z) := (4.691z -1 + 4.688z -2 )10 -7 1 -1.998z -1 + 0.9981z -2 (22)
for a sampling period h = 10 ms. A comparison between the modeled system response and real experiments for the same input signal is depicted in Fig. 5.

2) The altitude z is a double integrator system, which gain decreases with respect to the battery load (this is not detailed here). One can remark that it has been decided in this paper to manage the position of the mini helicopter through a velocity control. For this reason, longitudinal and lateral velocity setpoints are dynamically build calculating the projection of the real position to the desired one, using information on x, y and ψ.

C. Performance indexes

Performance indexes, introduced in [START_REF] Sánchez | Comparative study of event-based control strategies: An experimental approach on a simple tank[END_REF], are recalled here. They allow to compare the different event-based proposals with respect to classical approaches:

• The number (Nb) of samples required to perform the test bench.

• The IAE index, which gives information on the setpoint tracking:

IAE = ∞ 0 e(t)

dt

• The IAEP index, which compares the time-based and event-based system responses:

IAEP = ∞ 0 y tb (t) -y eb (t) dt
where y tb and y eb are the time-based and event-based measurements respectively.

• The IAD index, which compares the time-based and event-based measurement errors:

IAD = ∞ 0 e tb (t) -e eb (t) dt
where e tb and e eb are the time-based and event-based errors respectively. The performance indexes obtained for the experiments detailed below are summarized in Table I. Results are discussed in the sequel.

D. Experimental results

The mini helicopter has to track three points in the space, which coordinates are (x, y, z) = (0, 0, 0.6), (1.2, 1.2, 0.6), and (1.2, 0, 0.6). It was also decided that the system goes to another point after a waiting time of 40 s in order to analyze both the point tracking and its stabilization near a given point. Note that the altitude is kept the same for the three points because the study focuses more on the longitudinal and lateral velocities control.

The system trajectory in the xy-plane are compared in Fig. 6 for several strategies: a) a classical (time-triggered) PID controller; b) an event-based PID controller (previously developed in [START_REF] Durand | Further results on event-based PID controller[END_REF]) where the control signal is calculated and updated only when the system output crosses a given level ē; c) an event-based RST controller (proposed in the present paper, based on the event-based PID version); d) an event-based RST controller using a copy of the system model (also proposed in the present paper) where the control law is computed using a copy of the system model, which is updated only when the error between the model and the real outputs crosses a given level ȳ. The strategies are independently applied to control i) the altitude, ii) the longitudinal and iii) the lateral velocities. The control parameters K p , K i , K d and N are calculated by pole placement (in the continuous-time domain) for the different controlled systems but they are identical in the different approaches. On the other hand, the event-based control parameters are ē = 20 mm, α i = 1, α d = 0.01 for the altitude and ē = 50 mm/s, α i = 10, α d = 0.01, ȳ = 10 mm for the velocities. Note that the copy of the model is not applied to the altitude but only to the control of velocities, using the identified model [START_REF] Velasco | On Lyapunov sampling for eventdriven controllers[END_REF]. The results in Fig. 6 are then discussed for each control variable z, V long and V lat .

1) Control of the altitude: Experimental results are represented in Fig. 7 for a 50 s interval time. The top plot shows the setpoint and the measured signal whereas the bottom plot shows the sampling instants in the event-based control schemes ('1' means the control law is calculated and updated during the sampling period h, '0' means the control is kept constant).

It can be seen that the altitude of the system is close to the desired 60 cm altitude. The error is larger in the event-based schemes but with a strong reduction of the control updates in return (about 30 % and 55 % of samples less with the event-based PID and RST controller respectively than with a classical time-triggered strategy, see Table I). Furthermore, the event-based RST controller gives better results than the PID version (better IAE, IAEP and IAD indexes for a smaller number of updates) in the altitude case. Note that a better performance can be reached reducing the detection level ē.

2) Control of the longitudinal and lateral velocities: Remember the dynamical model is considered as the same for longitudinal and lateral velocities. Experimental results are represented in Fig. 8 and9 respectively. As before, the top plot shows the setpoint and the measured signal whereas the bottom plot shows the sampling instants in the eventbased control schemes. An extra plot in Fig. 8(d)-9(d) shows the correction instants in the event-based control scheme with copies of the system model ('1' means the measure is sent and the models are updated with the real measurement, '0' means the control is only computed using the model). Moreover, the output of the system model used to calculate the control law is also represented in the top plot.

As regards the longitudinal velocity in Fig. 8, the frequency of control updates is also highly reduced with the event-based schemes (more than 55 %). Note that since the setpoint to track is dynamically calculated, it varies from one experiment to another and it becomes difficult to compare the performance indexes. Nonetheless, it can be seen that IAE, IAEP and IAD indexes are close for the different event-based approaches (see Table I). As before, better performance can be obtained reducing the detection level ē. Furthermore, comparing the event-based RST controllers (without and with model copies), one can remark that the event-based corrector allows to reduce more i) the number of control updates (12 % less) and ii) the correction updates (70 % of communications less between the plant and the controller) even in the present case of a poor system model. The same remarks can be done for the lateral velocity (note that the performance are damaged because the model was computed for the longitudinal velocity and then simply applied to the lateral case considering that both are identical).

To sum up, the tradeoff between performance and the frequency of control/correction updates is clearly highlighted. One can hence imagine how the computing/communication resources utilization can be reduced in embedded and networked systems. This also means that the performance of the event-based schemes can be improved when decreasing the detection levels ē and ȳ.

CONCLUSIONS AND FUTURE WORKS

This paper recalled the classical time-triggered PID control scheme as well as the event-based PID control paradigm presented in [START_REF] Durand | Further results on event-based PID controller[END_REF]. An event-based RST controller was then developed, where the control parameters are based on the PID scheme. An event-based corrector was also added. Both techniques allow to reduce the communications due to control, from the controller to the plant and from the plant to the controller respectively. The whole approach was tested on a real-time system: a mini quadrotor helicopter using a motion capture system to provide its position, where the controller is deported and communications are hence of high importance. Experimental results showed the effectiveness of the proposal with a high reduction of the computing/communication resources utilization. The advantage of an event-driven scheme was hence highlighted and the encouraging results strongly motivate to continue developing event-based control strategies.

Next step is to extend the proposed event-based RST controller to systems of any order (whereas only secondorder systems were addressed here). Furthermore, the control parameters should be calculated directly in discrete-time domain (instead of continuous-time study). A better model of the system is also mandatory in order to implement more complex (event-based) strategies. Delays will also be considered in future works, as in [START_REF] Durand | Event-based stabilization of linear system with communication delays in the measurements[END_REF]. Nonlinear strategies will also be a trajectory, with event-based control laws in the spirit of [START_REF] Marchand | A general formula for event-based stabilization of nonlinear systems[END_REF], [START_REF] Durand | Event-based stabilization of nonlinear time-delay systems[END_REF]. Eventually, a cooperative approach where several systems are controlled together through a (wireless) network will be the next application to highlight the interest of event-based techniques and its strong reduction in the communications.

Fig. 1 .

 1 Fig. 1. RST controller setup.

Fig. 2 .

 2 Fig. 2. System architecture.

Fig. 3 .

 3 Fig. 3. Experiment architecture.

Fig. 4 .

 4 Fig. 4.Representation of the different control variables in the mini quadrotor helicopter.

Fig. 5 .

 5 Fig. 5. Validation of the system model for the longitudinal velocity.

Fig. 6 .

 6 Fig. 6. Experimental results: comparison of the different strategies to track three points in the space.

  Event-based RST controller.

Fig. 7 .

 7 Fig. 7. Experimental results for the altitude.

  (d) Event-based RST controller with copies.

Fig. 8 .

 8 Fig. 8. Experimental results for the longitudinal velocity.

  (d) Event-based RST controller with copies.

Fig. 9 .

 9 Fig. 9. Experimental results for the lateral velocity.

TABLE I PERFORMANCE

 I INDEXES OBTAINED FOR THE DIFFERENT EXPERIMENTS WITH SEVERAL EVENT-BASED CONTROL STRATEGIES.

						z				Vlong			Vlat
				Nb (%)	IAE	IAEP IAD Nb (%)	IAE	IAEP	IAD Nb (%)	IAE	IAEP	IAD
		Classical PID		100	0.55	0	0	100	2.74	0	0	100	1.34	0	0
		Event-based PID	70.20	1.69	1.30	1.20	29.72	2.27	5.17	2.45	35.60	2.89	2.07	2.07
		Event-based RST	46.66	1.07	0.83	0.70	45.06	2.75	3.11	2.70	44.36	3.21	4.73	2.32
		Event-based RST with copies	-	-	-	-	39.60	2.63	4.17	2.08	58.10	4.70	5.56	3.60
			System trajectory
		1.6
			PID
		1.4	Event-based PID
			Event-based RST
		1.2	Event-based RST with copy
			Points to track
		1
		0.8
	y [m]	0.6
		0.4
		0.2
		0
		-0.2
		-0.5 -0.4	0	0.5	1		1.5	2
				x [m]

http://www.bladehelis.com/Products/Default.aspx?ProdID=BLH7680

http://www.vicon.com/System/TSeries

http://www.vicon.com/Software/Tracker

https://www.spektrumrc.com/Technology/DSMX.aspx

ACKNOWLEDGMENT

The authors would like to thank i) M. Fayet, D. Manica, P. Perraud and ii) T. Da Silva for their contribution in the context of an integrative student project and an engineer internship respectively (Ense3, Grenoble university). This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025). The experimental platform has been designed by the GISPA-lab's technical staff and partially funded by EquipEx Robotex (ANR-10-EQPX-44-01).


Christophe Parisse

Anaïs De

La Roche-Saint-André

Real words and non-words learning under or without a2en3on by children with SLI

Introduc3on

There is an important comorbidity between SLI (Specific Language Impairment) and ADHD (AMenNon disorders and HyperacNvity disorders) -see Muller and Tomblin (2012). This suggests that aMenNon difficulNes, even if the children are not considered as with ADHD, could be a key factor to explain the language deficit.

AMenNon plays an important role when memorizing new words (Garagnani, Shtyrov and Pulvermüller, 2009). In the case of low aMenNon, in a recogniNon task, subjects could not remember unknown words but only known words.

If low aMenNon makes it difficult to remember unknown words, this could make it difficult to learn new words.

Procedure

Subjects: 10 children with SLI (French-speaking, no bilinguism, no ADHD, no hearing, social or neurological idenNfied deficit) -no severe deficit in comprehension (phonological-syntacNc disorder). 10 control children matched for age

Language abiliNes were controled used the ELO (Khomsi, 2001) Training session: 8 words (4 real words and 4 non-words) were presented to the children under two condiNons:

-With aMenNon: children were asked to listen carefull to the material presented. They knew that there would be quesNons asked later about the material -No aMenNon: children were asked to play with toys. They knew that they would hear words, and that they would be asked quesNons about what tehy did with their toys and about the words that they might hear.

TesNng session: Children were presented 14 words (including the 8 they heard before) and were asked to say whether they think they heard it or not. For the no aMenNon condiNon, they were told that not being sure about their answer was not a problem.

Results

Two word lists were used and passaNon was done in two orders: aMenNon first and no aMenNon second, or the opposite. There were no effect of list order nor passaNon order.

Discussion

Real (known) words are easier to remember than non-words and aMenNon helps to remember words for all children.

For children with SLI, the situaNon without aMenNon appears to be especially difficult for real words. No special difficulNes were found for non-words, but children with SLI had even lower scores for non-words with aMenNon.

For all children, recognizing a word as absent was easier than recognizing it as present.

The difference in performance between children with SLI and control children was not specifically stronger for non-words without aMenNon as predicted, but children with SLI had lower performance in comparison with control children only in the non-aMenNon case. This suggests that a high level of aMenNon is a specially required for children with SLI in recogniNon tasks.

Results

• Controls were beMer than SLI: F(1,78) = 7.66, p = .007

• Results with aMenNon were beMer than without aMenNon: F(1,78) = 12.3, p = .0007 • Real words were beMer recognized than non-words: t(153) = 4.62, p < .0001 • There was a significant interacNon between type of children (CTR vs. SLI) and aMenNon (with aMenNon vs. no aMenNon), but only for real words, F(1,76) = 5.88, p = .01, and not for non-words.