Amélie Charles
email: acharles@audencia.com.

Olivier Darné
email: olivier.darne@univ-nantes.fr.

Jean-François Hoarau
email: jfhoarau@univ-reunion.fr.

Lemna

How resilient is La Réunion in terms of international tourism

Keywords: External shocks, La Réunion, life cycle model, tourism, unit root. JEL Classification: C22; L83

published or not. The documents may come

How resilient is La Réunion interms of international tourism attractiveness: an assessment from unit root tests with structural breaks from1981-2015

Introduction

Undoubtedly, tourism is one of the most dynamic exporting sectors in the world economy. For some countries, this activity contributes more to domestic economic growth than traditional exports' sources like agriculture or manufacturing industry.

The role of tourism is even more relevant in the context of small island economies (SIE). For most SIEs, it is a notable and perhaps the only alternative to the industrial sector [START_REF] Logossah | Does tourism specialization mean sustainable growth for small developing islands ?[END_REF][START_REF] Bertram | A world of islands: an island studies reader, Canada and Malta[END_REF]. Notably, despite positive economic spillovers, tourism is prone to vulnerability and weakens sustainable development for small entities in the long term.

Four main problems with relying on tourism must be exposed. First, several leakages can offset the increase in domestic income due to tourist expenditures [START_REF] Nowak | Le tourisme, un danger pour les pays en développement ? Secteur Prové & Développement[END_REF]. Second, a strong competition may occur between sectors in terms of land, labour, and capital, which generates a 'Dutch disease' dynamic resulting in the fall of earlier exporting sectors [START_REF] Nowak | Coastal tourism and dutch disease in a small island economy[END_REF]. Third, tourism specialisation can be the cause of its own destruction. Beyond a specific threshold (the so-called tourist carrying capacity), the number and behaviour of tourists damage the attractiveness of the destination based on ecological and cultural balance that leads to a decline [START_REF] Butler | Tourism area life cycle: Contemporary tourism reviews[END_REF]. Fourth, tourism is prone to instability (UNEP and WTO, 2006) because of conjunctural fluctuations in the foreign source markets and international events like financial and economic crises or unexpected large external shocks (e.g. health crises, natural disasters, wars, terrorism).

The case of La Réunion is a good example [START_REF] Perrain | Spécialisation touristique et vulnérabilité: Réalités et enjeux pour le développement soutenable des petits territoires insulaires[END_REF].

The importance of the tourism sector for the local economy is significant: by 2012, foreign tourists' expenditures were e315 million, making tourism the primary export, followed by goods (e307 million). Despite of hopeful growth in the 1980s and 1990s (an annual average rate of approximately 8%), since the beginning of the 2000s international arrivals to the French overseas territory are observed to be locked in a stage of stagnation with an average of approximately 425,000 tourists per year.

Evolution of the share of foreign tourism expenditures in the GDP confirms this global trend: we observe a growth phase that increases to a maximum in 2000 of 3.2% of GDP, followed by a decrease to 2.2% in 2012. Moreover, the destination is very exposed to large unanticipated exogenous shocks. Alongside potential natural disasters due to cyclone phenomena that regularly damage the island, several major external and internal events, namely, the context of terrorism following the September 11 terrorist attacks, health crisis of 'Chigungunya' in [2005][2006], international financial crisis in 2008, and shark crisis since 2012, could have hurt the local economy dramatically.

Considering this high degree of exposure to natural risks, observers question the vulnerability of this destination that is the real possibility of a sustainable development process based on tourism for the French small island. Some studies have shown that tourist arrivals are affected by major external or internal events due to financial crises, terrorist attacks, changes in political regimes or natural disasters, such as the 1999 earthquake in Taiwan (Huang and Min, 2002), 1987 political coup in Fiji [START_REF] Narayan | Testing the unit root hypothesis when the alternative is a trend break stationary process: an application to tourist arrivals in Fiji[END_REF], Bali bombing [START_REF] Smyth | I've been to Bali too' (and I will be going back): are terrorist shocks to Bali's tourist arrivals permanent or transitory?[END_REF], Asian crisis [START_REF] Narayan | Examining the behavior of visitor arrivals to Australia from twenty different countries: An application of panel unit root tests[END_REF], and the September 11 attack [START_REF] Verma | Do external shocks have a permanent or a transitory effect on Thailand's tourism industry?[END_REF].

The topic of whether these large shocks have permanent or transitory effects on tourist arrivals has important policy implications in the context of the sustainability of the tourism industry. If large shocks on tourist arrivals are permanent, empirical support is provided for questioning the sustainability of the tourist sector due to the vulnerability of the tourism to shocks, suggesting the government should initiate reforms to increase the diversity and sustainability of the economy; however, if the external shocks are short-lived (transitory), the long-run returns from investment in the tourist industry are sustainable. All the examples in literature have found that the large shocks have transitory effects.

The aim of this paper is to examine whether tourist arrivals (total arrivals, by source markets, and by category) in La Réunion are affected by permanent or transitory shocks due to major external or internal events over the period 1981-2015. We consider that these major events represent large shocks that occur infrequently (lowfrequency shocks), but the time of their arrival is random. Our approach results from the numerous examples of random, heterogeneous, and infrequent events that could have a dramatic impact on tourist-arrival time series. This type of event includes, for example, the September 11 terrorist attacks, health crisis of 'Chigungunya' in [2005][2006], international financial crisis in 2008, and shark crisis since 2012. For this reason, we search for the presence of these infrequent large shocks (permanent and/or temporary) in the form of outliers in the number of tourist arrivals to La Réunion. The points are identified and corrected by using intervention analysis, originally proposed by [START_REF] Box | Intervention analysis with applications to economic and environmental problems[END_REF] and improved by [START_REF] Chen | Joint estimation of model parameters and outlier effects in time series[END_REF] and Gómez and Maravall (1997). We also detect structural breaks in the slope of the trend, which we observed to be the case for La Réunion from the early 2000s, by using the test developed by [START_REF] Perron | Testing for shifts in trend with an integrated or stationary noise component[END_REF], whose breaks would be rather endogenous. This type of approach should provide information concerning the nature and magnitude of the shocks on the number of tourist arrivals.

We also examine whether tourist arrivals in La Réunion are best characterised by a unit root process (random walk) or stationary process. If tourist arrivals are characterised by a unit root process, the implication is that effects of shocks, assumed to be randomly generated for every observation period (frequent small shocks), will have a permanent effect and tourist arrivals will not return to their stable long-term growth path. Otherwise, these permanent shocks due to innovations in tourism infrastructure are the main source of tourist-arrival growth trends. Notably, if international tourist arrivals are characterised as a stationary process, the implication is that following a (frequent small) shock, tourist arrivals return to their long-run trend path and the impact of the shock on varied tourist numbers will be only transitory.

Therefore, movements in tourist arrivals are associated with temporary fluctuations so that a (frequent small) shock such as innovation should have no impact on long-run tourist numbers. The random walk hypothesis for visitor arrivals in La Réunion is examined in this study by applying appropriate unit root tests according to the breaks detected in the previous step. Conducting univariate unit root tests is crucial, because source markets may respond differently to a shock. According to our review of the literature, this study is the first to analyse the effect of large shocks and stationary properties of tourist arrivals in La Réunion. 1 The remainder of the paper is organised as follows. Section 2 highlights major stylised facts for La Réunion in the field of tourism development. Section 3 presents the theoretical framework by asserting the usual suspects that explain the potential vulnerability of the small French island's tourism arrivals. Section 4 exposes the empirical methodology. Section 5 displays and analyses the empirical findings. Section 6 concludes. international comparisons with the other SIE. This French overseas territory is one of the least dependent islands regarding tourism earnings with Suriname and Haiti (Perrain and Jean-Pierre, 2016). This finding is observed to be more obvious when considering its insular neighbours (Table 1).

Contrary to La Réunion contribution of tourism to wealth creation is significant in Maldives (14.0%), Seychelles (6.4%), and Mauritius (3.8%). The same conclusion holds for the other French overseas regions (Polynesia, Martinique, Guadeloupe and Guyana). The economic impact per capita for La Réunion (US$516) is also far behind that for the other islands, except for Comoros. This relative weak economic contribution of the tourism sector can be analysed on the quantitative and structural sides. A first relevant explanation emerges from the evolution of tourist arrivals over the period 1989-2015 (Graph1). Two main regimes are present. From 1989 to the beginning of the 2000s, a phase of dynamic growth was observed with tourist inflows to La Réunion increasing from 181,769 to 429,999, that is, by a multiplicative factor of 137%. This boom resulted from two joined factors: a strong demand from the French market in search for new 'sun' destinations and a local supply, in terms of hotel infrastructures and air transport conditions that grew in accordance with this dynamic demand [START_REF] Rochoux | Spécialisation touristique et vulnérabilité: Réalités et enjeux pour le développement soutenable des petits territoires insulaires[END_REF]. Since 2000, the destination has been in a phase of stagnation, with total tourist numbers, in average, of 425,000 per year.

In this study, two arguments can be asserted to explain these data. First, many large exogenous events had deep negative effects on La Réunion over the recent period:

The theoretical framework

Theoretical roots of the tourism vulnerability of La Réunion can be found in the 'tourism optimum' literature. The concept of tourism optimum is the alternative vision of the so-called 'tourism-led-growth' hypothesis [START_REF] Balaguer | Tourism as a long-run economic growth factor: The Spanish case[END_REF]. Nobody contests the positive role of tourism in the short term, but no such evidence exists concerning the sustainability of economic growth in the long term due to the presence of negative economic, social, and ecological spillover effects [START_REF] Logossah | Does tourism specialization mean sustainable growth for small developing islands ?[END_REF]). 2 In other words, a maximum level exists, namely, an optimal level, from which negative effects of tourism specialisation dominate positive effects and overrule the sustainability of the tourist activity (Lozato-Giotart, 2003; Lozato-Giotart and Balfet, 2004).

The Standard approach: the Tourism Area Life Cycle model

Despite several conceptual and empirical limits [START_REF] Choy | Life cycle models for Pacific island destinations[END_REF][START_REF] Bianchi | Tourism development and tourism dynamics: an alternative approach[END_REF][START_REF] Prideaux | The resort development spectrum (a new approach to modelling resort development)[END_REF][START_REF] Aguilo | The persistence of the sun and sand tourism model[END_REF][START_REF] Mckercher | Are psychographics predictors of destination life cycles?[END_REF], the tourism area life cycle (TALC) model remains the more influential theoretical approach in the field [START_REF] Butler | The concept of the tourist area life cycle of evolution: implications for management of resources[END_REF][START_REF] Butler | Tourism area life cycle: Contemporary tourism reviews[END_REF]). 3 In short, the TALC model states that all tourism destinations are characterised by a common dynamic process reproducing a S-shaped curve and experiencing a series of stages from exploration to involvement, development, consolidation, stagnation, and post-stagnation (see Graph4).

Exploration and involvement are the first steps of a nascent industry where the numbers and frequency of visits remain weak. of tourism activity is now apparent based on the number of tourists per year, which can equal and even exceed the number of permanent residents. Then, the destination enters stagnation, that is, the tourism optimum stage that represents the maximum number of visits per year the resort experiences in its life cycle. The final stage is post-stagnation.

Notably, the destination's performance (rejuvenation or decline) depends on the ability of the policymakers in charge of the territorial policy to manage or restore, if necessary, the economic, social, and ecological carrying capacity. 4Figure 4: The TALC model Considering the time shape of the total tourist arrivals series (Figure 1), the TALC model indicates that La Réunion has been in the stagnation phase since 2000. Such a conclusion would be mistaken, because this phase characterises mature and mass tourism destinations that do not correspond to the situation of the small French island.

More precisely, running a clustering analysis based on the components of the Tourism Penetration Index developed by McElroy and de Albuquerque (1998) 5 over a sample of 47 SIE for the year 2013, Blancard and Hoarau (2016) asserted that La Réunion belongs to the cluster of the least penetrated tourism entities, that is, the cluster corresponding to the exploration stage. Then, the standard TALC model is not very informative concerning the dynamics conditioning the evolution of this destination.

Adding Chaos principles

The quasi linearity of the evolution curve stated by the TALC approach is theoretically funded but actually corresponds to the very long term. By contrast, observation shows that actual tourist destinations are confronted by strong instability, generating gaps from the trend given by the TALC curve in the short and medium term. 6Russel and [START_REF] Russell | Entrepreneurship, chaos, and the tourism area life cycle[END_REF], Russel (2006), and [START_REF] Cole | A logistic tourism model: Resort cycles, globalization, and chaos[END_REF] argue that providing a better appreciation for the paradoxical nature of a destination by combining the principles of chaos and complexity with the TALC model is possible. Specifically, the transition from one stage to the next is not linear or deterministic insofar as the tourism destination, whatever its maturity, highly depends on a set of unpredictable triggers. Moreover, the perturbations resulting from impacts of these unpredictable triggers are also unpredictable with a magnitude out of proportion to the initial shock.

Notably, each phase of the life cycle may enter into a period of instability, driven by fundamental shifts in relationships between the stakeholders of destination and the tourists. In each phase of its development, specific manifestations of chaos are present ('butterfly' effect, lock-in effect, bifurcation, 'edge of chaos'), implying that the tourism destination is a process continuously evolving and adapting. According to the specific combinations of the triggering factors, chaos effects can either facilitate or impede growth, progressing the cycle or causing stagnation and decline.

Consequently, it is more appropriate to represent the new approach by combining the TALC model with chaos principles as cyclic (Graph5). Obviously, this theoretical framework is more informative concerning the case of La Réunion. By considering these new conceptual insights and empirical results from [START_REF] Blancard | La détermination d'un optimum touristique à travers la construction d'un Indicateur multidimensionnel de Pénétration Touristique pour les économies insulaires[END_REF] together, the French destination is observed to be persistently locked in the stage of exploration.

According to our review of the literature, two types of triggers have been identified according to their exogenous or endogenous nature (Faulkner and Russel, 2001). First,

Methodology

To assess the vulnerability of La Réunion relative to shock exposure, we implement an econometric strategy based on three stages. The first two steps aim to detect the presence of exogenous and endogenous breaks in the series of foreign tourism inflows.

In a third step, we use a set of unit root tests adapted to the nature of identified breaks to draw conclusions regarding the temporary or persistent effect of shocks. All the tests are presented in detail in the Appendix.

Detecting breaks 4.1.1 Detection of exogenous breaks

Breaks in macroeconomic series reflect extraordinary, infrequently occurring events or shocks that have major effects on modeling macroeconomic time series. There are several methods stemming from the statistical field for detecting breaks or outliers based on the so-called intervention analysis approach, as originally put forward by [START_REF] Box | Intervention analysis with applications to economic and environmental problems[END_REF]. In this paper, we implement an improved detection algorithm proposed by Chen and Liu (1993), which is readily available with slight modifications by Gómez and Maravall (1997). Especially, we focus on break detection from AutoRegessive Integrated Moving-Average (ARIMA) models to emphasize the large shocks that have affected the series.

Let's assume that we observe (y t ) the annual series which follows the following process:

y t = z t + f (t) (1)
where

z t = θ(L) α(L)φ(L) a t a t ∼ N(0, σ 2 a ) (2)
where z t is an ARIMA(p, d, q) process 7 (L being the usual lag operator), and f (t) contains exogenous disturbances or breaks. Following Chen and Liu (1993), we will consider three various types of breaks: additive outlier (AO), level shift (LS) and temporary change (TC). The specifications for different f (t) are as follows:

AO:

f AO (t) = ω AO I t (τ j ) LS: f LS (t) = [1/(1 -L)]ω LS I t (τ j ) TC: f TC (t) = [1/(1 -δL)]ω TC I t (τ j ) (3)
where ω i , for i = AO, LS, TC, denotes the magnitude of the break8 , I t (τ j ) is an indicator function that takes the value of 1 at time t = τ j and 0 otherwise; τ j being the unknown date at which the break occurs, with j = 1, . . . , m, and m is the number of breaks. These various types of breaks differently affect the observations: AO causes an immediate and one-shot effect on the observed series; LS produces an abrupt and permanent step change in the series (permanent shock); TC produces an initial effect which dies out gradually with time (transitory shock). In this latter case, the parameter δ controls the pace of the dynamic dampening effect (0 < δ < 1). Note also that the detection algorithm provides an estimated date for the break through a sequential procedure.

Detection of endogenous breaks

We now study the presence of endogenous breaks , i.e. breaks in the level and/or the slope of the trend function.

The test is based on the following general model:

y t = µ 0 + β 0 t + K ∑ j=1 β j DT jt + u t , t = 1, . . . , T, u t = αu t-1 + v t , t = 2, . . . , T, u 1 = v 1 ,
where DT jt = (t -T j )I(t > T j ), j = 1, . . . , K. A break in the trend occurs at time

T j = [T λ j ] when β j = 0.
The dates of breaks (T j ) and the number of breaks (K) are treated as unknown. The error u t is allowed to be either I(0)(|α| < 1) or I(1)(α = 1).

The stochastic process {v t } is assumed to be stationary but not necessarily i.i.d.

thereby permitting a general error structure for u t .

Firstly, we test for the presence of one structural break in the slope (K = 1) which is formulated by the null hypothesis that β 1 = 0 versus an alternative hypothesis β 1 = 0 (ExpW test). Perron and Yabu (2009b) propose a hypothesis testing approach on the slope coefficient of a linear trend model when no information about the nature of the noise component is available. In case of rejection of the null, we test for the presence of two structural breaks in the slope (K = 2) using the testing approach of Kejriwal and Perron (2010) (ExpW (2|1) test). The null hypothesis is β 2 = 0 against β 2 = 0.

Kejriwal and Perron (2010) extend the work of Perron and Yabu (2009b) and propose a sequential test that allows to test the null of K breaks versus an alternative hypothesis of (K + 1) breaks and which is consistent whether the noise component is I(0) or I(1).

The rejection of the null will suggest the existence of two breaks in the slope and one if the test fails to reject.

Stationarity tests

Given evidence of the trend function characteristics (change in slope or not), appropriate unit root tests have to be implemented. Due to the strong change in the behavior of the series, we test the presence of a unit root in subsamples, defined according to the break in slope. However, it is well-known that performance of unit root tests depends whether or not they include a deterministic trend. For that, we use the procedure suggested by Perron and Yabu (2009a) who propose a test (t RQF β test)

on the slope of the trend function without no prior knowledge to the non-stationary properties of the noise component.

The test assumes that y t is generated by

y t = µ 0 + β 0 + u t , t = 1, .., T (4)
u t = αu t-1 + ∞ ∑ i=0 a * i L i ∆u t-i + e t , (5)
where µ 0 a finite constant, a * i = -∑ ∞ j=i+1 a j ; e t ∼ i.i.d.(0, σ 2 ). Here -1 < α ≤ 1 so that both stationary or integrated errors are allowed.

Following the results on the presence or not of the linear trend (t RQF β ) we apply the unit root tests of [START_REF] Elliott | Efficient tests for an autoregressive unit root[END_REF] (ADF GLS test) with the appropriate deterministic component.

Empirical results and comments

In the empirical study, we use annual data collected from several statistical surveys, entitled 'Enquête sur la fréquentation touristique à La Réunion', generated over the period 1981-2015 by the National Institute of Statistics and Economic Studies. 9 Three types of series are considered, namely, (i) total tourist arrivals to La Réunion; (ii) tourist arrivals to La Réunion disaggregated from major source markets, namely, from France, the European Union, and others (e.g. Mauritius, Madagascar, Mayotte, China); and (iii) tourist arrivals to La Réunion disaggregated from visiting motivations (categories), namely, leisure tourism, business tourism, visiting family or friends, and others forms (sport, healthcare . . . ). The selection of samples and time series span are, of course, dictated by data availability. Therefore, the results should be taken cautiously due to this small sample. Moreover, all data were converted in natural logarithmic form.

Breaks detection and unit root tests

Following the aforementioned methodology, we begin our investigation by testing if the tourism series have been affected by exogenous breaks. In Table 2, all detected exogenous breaks are given by series, with their type, t-statistics, and timing. Our results indicate that the series relative to total arrivals, tourism from continental France, tourism from the European Union, leisure tourism, and visiting family or friends are affected by one break in 2006. This break has a short-lived effect (AO), namely, one year, for total arrivals and visiting family or friends, with a decrease of 32% and 27%, respectively. The effect is also temporary (TC) for tourism from continental France and leisure tourism, which dies out gradually after few years, with an initial dramatic negative impact of 37% and 50%, respectively. For European Union arrivals, the turbulence is observed to have, instead, a permanent impact (LS) that implies a change in the series, but only on the level and not on the slope of the trend. No impact on the growth rate is found, that is, after the shock the growth rate of tourist arrivals converges towards its long-term equilibrium path. The year 2006 corresponds to the health crisis of 'Chickgungunya,' which led to several hundred deaths in few months.

By contrast, no exogenous outliers or breaks (large shocks) are detected for the series of other source markets, business tourism, and other tourism motivations. Surprisingly, at this stage, no statistical effect of the well-known adverse events associated with a large shock (the terrorism context associated with the September 11 terrorist attacks, the international financial crisis in 2008, or the shark crisis damaging the local economy since 2012) is found from our simulations. 9 For the period 1981-1988, the database was reconstructed from information given in DCBFODT (1994). Next, we examine if the tourism series has been subject to (endogenous) slope breaks. The tests of Perron and Yabu (2009b) and Kejriwal and Perron (2010) are employed for this purpose on the raw series for other source markets, business tourism, and other tourism motivations and the corrected-outlier series for total arrivals, tourism from continental France, tourism from the European Union, leisure tourism, and visiting family or friends. Table 2 displays the results of the zero versus one slope break (ExpW ), and one versus two slope breaks (ExpW (2|1)). [START_REF] Kejriwal | Unit roots, level shifts, and trend breaks in per capita output: A robust evaluation[END_REF] labelled the case of a break in slope with possible shifts in the level as the 'growth shift' hypothesis.

Our empirical results are notable and potentially informative for economic policy.

First, one endogenous break is detected in 2000 for total arrivals and continental France tourists. Similarly, one slope break is present in 1999 for leisure tourism and other source markets, in 2004 for tourists visiting family and friends, and in 1997 for other visiting motivations. More precisely, before the break is an increasing deterministic trend and no trend after the break, except for the series of other source markets where we observe a weak declining trend. The stagnation occurring since the end of the 1990s for the series of other source markets (mainly tourists from Comoros, Mayotte, Madagascar, Mauritius, and the Seychelles) and other motivations has the same origins. Starting in the 1990s, important structural changes in the healthcare system within the Southern Indian ocean region were implemented and based on (i) major improvements in medical infrastructure in Mayotte with the implementation of a modern hospital in 1996, and (ii) the growing preference of patients from Mauritius and Seychelles for treatment in South Africa and India due to a significant gap pricecompetitiveness [START_REF] Dupilet | Prises en charge spécialisées des patients des pays de l'Océan Indien dans les hôpitaux de La Réunion : Etats des lieux et propositions[END_REF]. For the other series, even if no apparent event can be associated with these dates at this point, a possible explanation relies on the structure of the domestic tourism industry and failure of local governance in accordance with the theoretical insights exposed.

Second, the break in the slope for European arrivals identified in 1995 is followed by a strong accelerating trend over the more recent period. This corresponds to a positive change, unfortunately too modest, in the tourist product design more in phase with the expectations of German or Swiss customers. Notably, during the 1990s local authorities in charge of tourism development abandoned the old strategy based on traditional seaside tourism for a more adapted strategy that focused on the combination of the mountains, volcano, sea, and culture. Finally, no evidence of break in the slope was observed for business tourism.

The last important question is if the shocks that are the impetus for the fluctuations of tourist arrivals have permanent or transitory effects on tourist arrivals in La Réunion.

Sources:

The authors.

Comparing to the literature

Our results are consistent with the literature, in that a consensus emerges regarding the rejection of the hypothesis of non-stationarity and then supports the finding that external shocks have only a transitory effect on tourist arrivals. By using the Sen

Conclusion

This paper aimed to study whether the absence of growth in international tourist arrivals to La Réunion since 2000 was due to some large external shocks affecting the growth of this economy (such as the September 11 terrorist attacks, 'Chigungunya' crisis in 2005-2006, international financial crisis in 2008, and shark attacks since 2012). We implemented univariate unit root tests with structural breaks and found no evidence of the permanent impact of external shocks on tourism flows to La Réunion over the period 1989-2015, except for tourists arriving from the European Union; notably, the European source market represents a small part of total tourism. Moreover, only one major shock, namely, the Chigungunya crisis, was observed to have a significant effect on the level of inflows without changing the growth rate.

Nevertheless, the results must be considered with caution due to the small sample of the data.

Our findings have operational consequences for economic policy. La Réunion is locked into the phase of exploration of the TALC model, not because of external events, but potentially because of oppressive impediments inside the tourism industry.

In short, the trouble is not exogenous but obviously endogenous. Thus, by following the TALC model, the destination should firstly improve the supply side. Building new hotel infrastructure, opening the air traffic with new companies from emerging source markets, and designing a strong and clear tourism identity are examples of policies that must be undertaken urgently.

Otherwise, the findings provide strong support for the recent report from the National Court of auditors in 2014, concerning the tourism performance of the French overseas regions including La Réunion. Resuming the conclusion of this report, 'the decrease in tourist arrivals results especially from structural reasons and by the lack of dynamism of implemented public policies. The successive regional councils do not succeed in coordinating a sector concerning all levels of local administration. A preference is conferred to promoting initiatives but they are largely inefficient, while the supply do not correspond to the expectations of international tourism' (National Court of auditors, 2014).

7 Appendix: Methodology These expressions can be viewed as a regression model for ât , i.e., ât = ω i x i,t + a t i = AO, LS, TC, with x i,t = 0 for all i and t < τ, x i,t = 1 for all i and t = τ, and for t > τ and k ≥ 1,

x AO,t+k = -π k (AO), x LS,t+k = 1 -∑ k j=1 π j (LS), and x TC,t+k = δ k -∑ k-1 j=1 δ k-j π jπ k (TC), with k = 1, . . . , Tτ. Breaks are identified by running a sequential detection procedure, consisting of outer and inner iterations. In the outer iteration, assuming that there are no breaks, an initial ARIMA(p, d, q) model is estimated and the residuals ( ât ) are obtained. The results from the outer iteration are then used in the inner iteration to identify breaks.

The LR test statistics for the four types of outliers are calculated for each observation.

The largest absolute value of these test statistics: τmax = max|τ i (τ)| i = AO, LS, TC and τ = 1, . . . , T is compared with a critical value, and if the test statistic is larger, a break is found at time t = τ 1 and its type is selected (i * ). When a break is detected, the effect of this break is removed from the data as follows: the observation z t is adjusted at time t = τ 1 to obtain the corrected y t via (1) using the estimated magnitude ωi * and the appropriate structure of break f (t) i * as in (3), i.e.

y t = z t -f (t) i *
We also compare the second largest absolute value of the LR statistics for the three types of breaks to the critical value, i.e. τmax = max|τ i (τ)| with τ = τ 1 , and so on.

This process is repeated until no more breaks can be found. Next, we return to the outer iteration in which another ARIMA(p, d, q) model is re-estimated from the breakcorrected data, and start the inner iteration again. This procedure is repeated until no break is found. Finally, a multiple regression is performed on the various detected breaks to identify (possible) spurious breaks.

Detection of endogenous breaks

Perron and Yabu (2009b) extend the procedure of Perron and Yabu (2009a) to address the issue of testing for structural break in the trend function. The test starts by assuming a data generating process (DGP) for a scalar random variable y t to have the following specification:

y t = x t Ψ + u t , t = 1, .., T (7)
u t = αu t-1 + ∞ ∑ i=0 a * i L i ∆u t-i + e t , (8)
where x t = (1,t, DT t ) , Ψ = (µ 0 , β 0 , β1) , DT t = 1(t > T 1 )(t -T 1 ), T 1 = [λ 1 T ]=the break date. The null hypothesis of the test for a shift in slope (allowing for a shift in intercept) is H 0 : β 1 = 0 versus H 1 : β 1 = 0.

The Wald test statistic W RQF is constructed for a given break fraction λ 1 and depending on the value of αMS

W RQF (λ 1 ) = βFG 1 (λ 1 )
2 ĥυ [(X X) -1 ] 44 [START_REF] Baum | Revisiting the TALC: Is there an off-ramp[END_REF]

  (i) the international tourism turmoil in 2001-2002 following the terrorist attacks of September 11, (ii) health crisis of 'Chigungunya' in 2006, (iii) international financial crisis in 2008-2009, and (iv) the shark attacks that began in 2012. Second, some observers highlight that the absence of a common vision from the stakeholders creates a further slowdown of development of the destination. In particular, the absence of a consensus prevented the establishment of the necessary environmental conditions to create a clear identity for the destination and 'attract vibrant entrepreneurs who have the vision, the drive, and the cash to revolutionise the market'(Russell and Faulkner, 2004, p.564).

Figure 1 :

 1 Figure 1: Total tourist arrivals to La Réunion (numbers per year)

Figure 2 :Figure 3 :

 23 Figure 2: Tourist arrivals to La Réunion by source markets (numbers per year)

Figure 5 :

 5 Figure 5: The TALC approach with chaos

  denotes significance at the 10% level. t RQF β denotes the Perron and Yabu (2009a) test for the deterministic trend. ADF GLS represent the ADF-GLS statistic proposed by Elliot et al. (1996).

( 2003 )

 2003 test for one break in linear trending data to investigate whether shocks to visitor arrivals to Fiji from three main source markets (Australia, New Zealand and the United States) have a permanent or transitory effect, Narayan (2005) concluded that tourism arrivals over the period 1970-2002 are finally trend-reverting. By using the panel unit root tests of Maddala and Wu (1999) and Im, Pesaran and Shin (2003) for the period 1980-1999, Bhattacharya and Narayan (2005) indicated that visitor arrivals in India are inconsistent with the random walk hypothesis. Smyth et al. (2009) applied univariate and panel LM unit root procedures with one and two structural breaks to test for the null hypothesis that tourist arrivals to Bali contain a unit root. They showed that the univariate unit root tests with and without structural breaks did not reject the null of non-stationarity; however, the panel LM ones with one and two structural breaks are able to reject the joint null for the 11 major tourist source markets of Bali, then arguing for jointly trend stationary with transitory shocks. Lean and Smyth (2009) also considered the univariate LM unit root tests with one and two breaks to analyse the effect of shocks for the sustainability of the Malaysian tourism sector over the period 1995-2005 but were unable to reject the unit root null for the 10 main source markets of Malaysia, then validating the hypothesis of trend-stationary with transitory shocks. Lastly, Saleh et al. (2011) conducted univariate and panel LM unit root tests with structural breaks for tourist arrivals to Thailand from its 10 major sources from 1988 to 2007 and found evidence for trend stationarity.

7. 1

 1 Detection of exogenous breaksChen and Liu (1993) and Gómez and Maravall (1997) suggest the following procedure to detect outliers: An ARIMA model is fitted to y t in equation (2) and the residuals are obtained:ât = π(B)z t(6)whereπ(B) = α(B)φ(B)/θ(B) = 1π 1 Bπ 2 B 2 -. . . .For the three types of breaks in (1), the equation (6) becomes:AO: ât = a t + ω AO π(B)I t (τ) LS: ât = a t + ω LS [π(B)/(1 -B)]I t (τ)TC: ât = a t + ω TC [π(B)/(1 -δB)]I t (τ)

  The detection of the outliers is based on likelihood ratio [LR] statistics, given by:AO: τAO (τ) = [ ωAO (τ)/ σa ]/ (τ) = [ ωLS (τ)/ σa ]/for i = AO, LS, TC, and ωIO (τ) = âτ where ωi (τ) (i = AO, LS, TC) denotes the estimation of the break impact at time t = τ, and σa is an estimate of the variance of the residual process.

2 Main stylised facts

	By 2012, global tourism (foreign visitors and locals) in La Réunion was 8% of GDP,
	that is, e846 million. If we focus on the foreign side, tourism represents approximately
	2.2% of GDP, corresponding to a receipt of e315 million (Perrain and Jean-Pierre,
	2016) and 3.2% of total employment. Tourism is the primary export of La Réunion
	and far ahead of exports of goods; however, a contrasting conclusion emerges from
	1 Notably, few studies have examined the effect of large shocks and stationary properties of tourist
	arrivals (e.g., Huang and Min, 2002; Bhattacharya and Narayan, 2005; Narayan, 2005; Narayan and
	Prasad, 2008; Lean and Smyth, 2009; Saleh et al., 2011) but with different methodology approaches. See
	subsection 5.2 for a discussion on these studies.

Table 1 :

 1 Foreign tourism earnings for a several small island economies

	Pays	in % of GDP (2012) dollar per capita (2013)
	Maldives	14.0	4741
	Polynesia	6.9	1455
	Seychelles	6.4	2593
	Mauritius	3.8	1118
	Martinique	3.6	1252
	Guadeloupe	3.2	1433
	Comoros	3.2	41
	Guyana	2.4	..
	La Réunion	2.2	516
	Sources: Blancard and Hoarau (2016), Perrain and Jean-Pierre (2016).

Table 2 :

 2 Results of exogenous and endogenous breaks -1981-2015

		Exogenous break	Endogenous break
	Series	type t-stat date	ExpW ExpW (2|1) TB
	Nb. of tourists
	Total	AO -6.54 2006	30.1 *	0.81	2000
	Residence
	Metropole	TC -7.66 2006	1.29 * * *	1.60	2000
	European Union	LS -3.94 2005	13.6 *	0.91	1995
	Other resid.	-	-	-	5.57 *	1.16	1999
	Category
	Leisure tourism	TC -6.97 2006	3.75 *	0.56	1999
	Business tourism	-	-	-	-0.13	-	-
	Visit family	AO -3.99 2006	8.77 *	1.22	2004
	Other visiting	TC -6.06 2008	1.37 * * *	0.75	1997

Notes: The test statistics ExpW and ExpW (2|1) denote the Perron-Yabu (2009b) and

[START_REF] Kejriwal | A sequential procedure to determine the number of breaks in trend with an integrated or stationary noise component[END_REF]

statistics, respectively. The corresponding critical values are 1.67 and 2.56, respectively. * , * * and * * * denotes significance at the 1%, 5% and 10% level, respectively. Sources: The authors.

Table 3

 3

	presents the results of the univariate unit root tests. Four main findings must
	be underlined: (i) a different stationary process for business tourism; (ii) a change
	in persistence after the break date in the slope from trend stationarity to difference
	stationarity for European visitors; (iii) a change in persistence from either difference
	stationarity or trend stationarity to stationarity without trend due to the break date in the
	slope for the series of total arrivals, leisure tourism, other visiting motivations, French
	tourist arrivals and tourists visiting family and friends; and (iv) a change in persistence
	resulting from the slope break from difference stationarity to trend stationarity for
	tourist arrivals from other market sources. Overall, our simulations tend to support the
	transitory effect of external shocks, except for European tourist arrivals and business
	visitation. however, these two types of tourism represent only marginal inflows. Thus,
	the actual difficulties of La Réunion's tourism sector are not rooted in the presence of
	external shocks.

Table 3 :

 3 Results of unit root tests

See Butler (2011) for a complete discussion about these different stages.

This composite indicator is created from three variables: the visitor spending per resident population, average daily visitors density per 1,000 population, and number of hotel rooms per square kilometer.

[START_REF] Butler | Tourism in the future: Cycles, waves and wheels?[END_REF] admits that the TALC model conforms to old destinations but is unsuitable for the new products characterized by differentiation and rapid innovative changes in a context of high international competition, strong mobility of potential visitors, and unprecedented reduction in the distance (i.e. transport times and costs). In particular, the model does not accommodate the unpredictable factors that trigger development or decay.

The orders p and q of the ARIMA model are based on specification tests and information criteria.

More precisely, it is considered that AOs are outliers which are related to an exogenous change in the series with no permanent effects, whereas TCs and LSs are more in the nature of structural changes. TCs represent short-lived shifts in a series with a return to previous levels whereas LSs are more the reflection of permanent shocks. In the remainder of the paper, we use the term "break" for AO, TC and LS.

where X = [x 1 , (1 -αMS L)x t (t = 2, ..., T )], and βFG 1 is quasi FGLS estimate of β 1 . 10 Following Andrews (1993) and Andrews and Ploberger (1994), Perron and Yabu (2009b) consider the Exp functional of the Wald test for different break dates as they found the limit distributions to be nearly identical in the I(0) and I(1) cases. The test statistic needs to be evaluated for each break date candidate and then, the Exp functional as defined as follows is evaluated:

Kejriwal and Perron (2010) extend the approach of Perron and Yabu (2009b) and propose a sequential test that allows to test the null hypothesis of l breaks against the alternative hypothesis of (l + 1) changes. The procedure is consistent to wether the data are stationary or not. As in Perron and Yabu (2009b), [START_REF] Kejriwal | A sequential procedure to determine the number of breaks in trend with an integrated or stationary noise component[END_REF] use the Exp functional over all permissible break dates.

ExpW RQF

where τ ∈ Λ i,ε = {τ : λi-1 + ( λiλi-1 )ε ≤ τ ≤ λi -( λiλi-1 )ε} with λi = Ti /T and

RQF is the one break test in segment i. For i = 1, ..., l + 1, the sequential test is the application of a single change in slope (allowing for shift in level) test in the (l + 1) segments and examine if the maximum is significant. The test is given by:

The first step is to investigate if there at least one break (F T (1|0)). In case of rejection, the test F T (2|1) is applied. If the statistic is sufficiently large we conclude in favor of two breaks in the DGP. Notice that the test is repeated by increasing l sequentially until the test fails to reject the null hypothesis of no structural change, the number of breaks corresponding then to the number of rejections. However, in our study we limited l to unity. 10 The approach consists to consider the quasi FGLS estimate of the parameters of the equation [START_REF] Butler | The concept of the tourist area life cycle of evolution: implications for management of resources[END_REF] using αMS :

t = 2, ..., T , and

Denote the resulting estimates by ΨFG = (μ FG 0 , μFG 1 , βFG 0 , βFG 1 ) .

Trend test

Perron and Yabu (2009a) recommend the following steps for testing the slope of the trend function without no prior knowledge to the non-stationary properties of the noise component:

1. Estimate the residuals ût from detrended y t by OLS.

2. Estimate α from the following regression:

The order k is selected using the Modified AIC of Ng and perron (2001) (MAIC), with k ∈ [0; 12(T /100) 4. Apply the quasi feasible generalized least square (FGLS) procedure using αMS to obtain the estimate of the trend parameter β 0

t = 2, ..., T , and y 1 = µ 0 + β 0 + u 1 . Denote the resulting estimates of β 0 by βFG 0 .

5. Construct the t-statistic t RQF β (where RQF stands for robust quasi FGLS)

where

)] for t = 2, ..., T , and

. h υ is a consistent estimate of (2π times) the spectral density function at frequency zero of υ t = (1-αL)u t . They use an autoregressive spectral density estimate.

Stationary test

The unit root test proposed by [START_REF] Elliott | Efficient tests for an autoregressive unit root[END_REF] is based on the following regression:

in which ỹt representing the locally detrended data process under the local alternative α, is given by: ỹt = y t -ψ z t where z t = (1,t) in the case with drift, and ψ being the generalized least squares (GLS) regression coefficient of Xt on zt defined by:

The test statistic ADF-GLS is the usual t-statistic for the null hypothesis β 0 = 0 against the alternative of β 0 < 0. Elliott et al. (1996) recommend that the parameter c, defining the local alternative through α = 1 -(c/T ), be set equal to 13.5 if the series seems to contain a trend (drift), and 7 for an intercept. The lag order k is selected using the modified information criteria suggested by [START_REF] Ng | Lag length selection and the construction of unit root tests with good size and power[END_REF] with the modification proposed by [START_REF] Perron | A simple modification to improve the finite sample properties of Ng and Perron's unit root tests[END_REF].


Chuquimia Orlando

Andrea Pinna

Marsala Christophe

Xavier Dray

Bertrand Granado

FPGA-based Real Time Embedded Hough Transform Architecture for circles detection

, this technique can be generalized to parametric curves as circles. For a real time execution and embedded integration, several optimizations are necessary due to the large memory and computational requirements. This paper presents an efficient real-time pipelined architecture with a FPGA implementation of our Hough Transform for multi-circles detection. The computation of center candidates was improved. A three stages pipeline architecture was designed in order to reduce the processing latency and cadence. The architecture has been integrated into a Xilinx Zynq-7000 XC7Z020 containing a FPGA Artix-7. The global system uses 78.5 BRAMs, 153 DSP slices, 21638 LUTs. Our global system can support a maximum clock frequency of 128.89 MHz. We validate our architecture using a 125MHz clock frequency and we obtain a latency of 33.214 ms and an interval between two images of 16,607 ms for a 1920x1080 pixels image. According to our results, our architecture offer a throughput more than 4 times better than the faster state of the art architecture.

I. INTRODUCTION

Most of 95% [START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF] of colorectal cancers begin as a growth on the inner lining of the colon or rectum called as polyp.

To reduce the incidence of Colorectal cancer, authors in [START_REF] Orlando | Polyps recognition using fuzzy trees[END_REF], [START_REF] Silva | Toward embedded detection of polyps in wce images for early diagnosis of colorectal cancer[END_REF] proposed a new paradigm of Wireless Capsule Endoscopy [START_REF] Iddan | Wireless capsule endoscopy[END_REF] that can automaticaly recognize polyp in situ.

They have proposed a specific processing chain embedded in a System on Chip integrated inside a capsule.

In this chain they use the Hough transform to detect circles in HD images as Regions candidates to contain a polyp. It is a widely used technique, for object localization since 1962 [START_REF] Hough | Method and means for recognizing complex patterns[END_REF], that can be generalized to parametric curves as circles [START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF]. Once regions are selected they use a learning algorithm to decide if there is a polyp in the region.

In this article, we have studied only the Hough transform part to determine if it can be embedded in real time, this can be a first step in order to determine if it can be embedded in the next generation of capsule that will embed a HD images. We focused on it because we have measured its execution on an embedded processor, an ARM Cortex A9, using OpenCV library and running at 667 MHz and see that it takes 998.260 ms for an image of size 1920x1080. This execution time is too high, 25 times higher than the expected goal that is to proccess images with the same video quality of an endoscope, that acquire a 1920x1080 pixel image every 40 ms. This result excludes an optimized software embedded implementation and obliges us to a custom digital hardware implementation in FPGA.

II. STATE OF THE ART

A state of the art has been realized to analyse the implementation of the Hough transform in a FPGA considering timing contraints. Here, we present the highlights found, a survey of Hough transform methods can be read in [START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF] and [START_REF] Mukhopadhyay | A survey of hough transform[END_REF]. We can notice some facts:

1) all the FPGA implementations [START_REF] Alim | Modified circular hough transform using fpga[END_REF], [START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF], [START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF], [START_REF] Seo | Efficient architecture for circle detection using hough transform[END_REF], [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF], [START_REF] Kumar | Hardware accelerators for iris localization[END_REF] use embedded internal memories or BRAMs (Block RAMs), 2) all the works consider only the acceleration of the voting process of the Hough transform. In this process the goal is to accumulate intersection points in the Hough parameter space, corresponding to the number of possible circles. Then a vote is done to find the local maximum that are considered as real circle. This process is memory and time consuming, two different approaches emerged, the first approach uses the original Hough transform algorithm were the parametric equations of a circle are used to find the center and the radius of the circles [START_REF] Alim | Modified circular hough transform using fpga[END_REF], [START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF], [START_REF] Seo | Efficient architecture for circle detection using hough transform[END_REF], [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF], [START_REF] Kumar | Hardware accelerators for iris localization[END_REF] and the second approach uses a modified version of Hough transform called One dimensional Hough transform algorithm [START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF]. We describe below the works related to both approaches.

A. Original Hough transform Implementations

For the original Hough transform implementation, in [START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF], authors demonstrate that using an external memory to store the voting procedure is limited due to the data transfer bandwidth. In this implementation an efficient internal memory structure is considered for the voting process, where the size of the Hough space is reduced. Computations are distributed in mathematical units, each unit has access to its own memory module with a double buffer technique to avoid external memory, this allows multiple parallel read/write operations at the same time.

In [START_REF] Alim | Modified circular hough transform using fpga[END_REF], authors use a CORDIC algorithm to implement the Hough transform. Specificity of this work is that it detects only one circle owning of the target application, an iris detection. The same approach is used in [START_REF] Kumar | Hardware accelerators for iris localization[END_REF], where a FPGAbased hardware accelerator for iris localization is introduced.

In [START_REF] Seo | Efficient architecture for circle detection using hough transform[END_REF], authors adopt the scanline-based ball detection algorithm for the edge detection stage and edge-flag algorithm for the voting process.

In [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF], authors propose a Hough transform algorithm combined with a graph clustering algorithm for FPGA-based multi-circle detection.

B. 1D Hough transform algorithm Implementation

Goneid et al. introduce a modified version of Hough transform dedicated to detect multi-circles [START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF] in 1997. This method, called 1D Hough Transform multi-circles detection can successfully extract non-overlapping circles and ellipses in binary images, even in the presence of random noise. This method is easy to implement since each of the object's parameters is accumulated in its own one-dimensional parameter space. Zhou and al. [START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF] implement it on a FPGA.

This modified version of Hough Transform algorithm can be represented by the simplified pseudocode in Algorithm 1 and can be summarized as follow:

1) From a contour image, first, to create a histogram of the middle of the segments constituted by the points of contours. At first, for the horizontal segments, we create histogram V x (steps [START_REF] Alim | Modified circular hough transform using fpga[END_REF][START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF][START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF][START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF][START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF][START_REF] Hough | Method and means for recognizing complex patterns[END_REF][START_REF] Iddan | Wireless capsule endoscopy[END_REF] of algorithm 1 and in a second time for the vertical segments, we create histogram V y (Steps [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF][START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF][START_REF] Kulpa | On the properties of discrete circles, rings, and disks[END_REF][START_REF] Kumar | Hardware accelerators for iris localization[END_REF][START_REF] Mamonov | Automated polyp detection in colon capsule endoscopy[END_REF][START_REF] Mukhopadhyay | A survey of hough transform[END_REF][START_REF] Orlando | Polyps recognition using fuzzy trees[END_REF] of algorithm 1. We obtain the center candidates (i, j) from combination of local maximums of line and column histograms. 2) We build a 3D histogram V r of the distances between all the point of contour and the center candidates.

Steps [START_REF] Romain | Towards a multimodal wireless video capsule for detection of colonic polyps as prevention of colorectal cancer[END_REF][START_REF] Seo | Efficient architecture for circle detection using hough transform[END_REF][START_REF] Silva | Toward embedded detection of polyps in wce images for early diagnosis of colorectal cancer[END_REF][START_REF] Walther | A unified algorithm for elementary functions[END_REF][START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF][20][21][22][23][24] of algorithm 1, the more voted distance r become the radius of the center candidate (i, j); 3) If the value V r (i, j, r) is greater than f * 4 √ 2r then ||(x, y) -(i, j)|| = r becomes a circle. Steps [20-22] of algorithm 1. f can be adapted as the sensitivity threshold to detect circles. In [START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF], authors propose an architecture based on FPGA implementation of algorithm 1. They choose a 9-bit integer words for the data in histogram V x and histogram V y and a 17-bit integer words for the histogram V r . They use multiple BRAMs to implement these histograms by 100 voting modules in parallel. The number of x-coordinate or y-coordinates of center candidates is set to 10, therefore, 100 center candidates are constructed. Finally the radius is coded with 13-bit integer.

C. Analysis of the state of the art

The implementations performance are shown in table I. As we can see in table I, there is no FPGA work using larger image sizes as 1920x1080. In table I we have extrapolated for each referenced work, using a simple size factor, the latency for a 1920x1080 image size. We can see that none of these state of the art method reach a latency less than 40 ms for this image size. Then it is necessary to design a new digital hardware architecture to accelerate the Hough transform computation.

Polyps can be show as protrusions and detected using the local curvature of the edge-image searching circular for each edge I(i, j) with j from 1 to W -1 do 3:

for each edge I(i, k) with k from j + 1 to W do 4:

V x ( j+k 2 ) = V x ( j+k 2 ) + 1 5:
end for 6:

end for 7: end for 8: for each column i from 1 to W do 9:

for each edge I(j, i) with j from 1 to H -1 do 10:

for each edge I(k, i) with k from j + 1 to H do 11:

V y ( j+k 2 ) = V y ( j+k 2 ) + 1 12:
end for 13:

end for 14: end for 15: for each local maximum

V x (i) in V x do 16:
for each local maximum V y (j) in V y do 17:

for all edge I(k, m) in image do 18: V r(i,j,||I(k,m)-(i,j)||) = V r(i,j,||I(k,m)-(i,j)||) + 1 19: end for 20: if maximum value of V r (i, j, r) > f * (4 √ 2r) then 21: ||(x, y) -(i, j)|| = r is a circle 22: end if 23:
end for 24: end for or elliptical shapes [START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF], [START_REF] Mamonov | Automated polyp detection in colon capsule endoscopy[END_REF]. Based on analyses of polyps images from colon examination [START_REF] Romain | Towards a multimodal wireless video capsule for detection of colonic polyps as prevention of colorectal cancer[END_REF], it was observed that polyps do not always have a regular circular or elliptical shape, it depend of the noisy level, quality and resolution of the image. In addition, in [START_REF] Zhou | An efficient implementation of the one-dimensional hough transform algorithm for circle detection on the fpga[END_REF] the key technique for accelerating Goneid algorithm is an efficient usage of DSP slices and block RAMs. Based on these constatations we have choose to investigate Goneid algorithm to realize an optimized version that can compute Hough Transform in less than 40 ms for a 1080x1920 image size.

III. PROPOSED METHOD

Our FPGA based architecture for a real-time implementation of the 1D Hough transform multi-circles detection is focused on the acceleration of the construction of histograms V x and V y, [1 -7] and [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF][START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF][START_REF] Kulpa | On the properties of discrete circles, rings, and disks[END_REF][START_REF] Kumar | Hardware accelerators for iris localization[END_REF][START_REF] Mamonov | Automated polyp detection in colon capsule endoscopy[END_REF][START_REF] Mukhopadhyay | A survey of hough transform[END_REF][START_REF] Orlando | Polyps recognition using fuzzy trees[END_REF] respectively to the algorithm 1. Our solution significantly reduces the use of memory and the latency execution. First, we propose an equivalent algorithm, algorithm 2, which gives the same results, that is to say the same x-coordinate and y-coordinate histograms as in steps [1 -7] and [START_REF] Irwansyah | Fpga-based circular hough transform with graph clustering for vision-based multi-robot tracking[END_REF][START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF][START_REF] Kulpa | On the properties of discrete circles, rings, and disks[END_REF][START_REF] Kumar | Hardware accelerators for iris localization[END_REF][START_REF] Mamonov | Automated polyp detection in colon capsule endoscopy[END_REF][START_REF] Mukhopadhyay | A survey of hough transform[END_REF][START_REF] Orlando | Polyps recognition using fuzzy trees[END_REF] of the algorithm 1.

Algorithm 2 is obtained first by rewriting the steps [START_REF] Alim | Modified circular hough transform using fpga[END_REF][START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF][START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF][START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF][START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF][START_REF] Hough | Method and means for recognizing complex patterns[END_REF][START_REF] Iddan | Wireless capsule endoscopy[END_REF] of the algorithm 1 as shown in algorithm 3, taking into account all the points of the image instead of just taking the contour points.

In second, we change the order of the for-loops and obtain a new formulation of the steps [START_REF] Alim | Modified circular hough transform using fpga[END_REF][START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF][START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF][START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF][START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF][START_REF] Hough | Method and means for recognizing complex patterns[END_REF][START_REF] Iddan | Wireless capsule endoscopy[END_REF] shown in algorithm 4.

Finally, we can rewrite the i-loop as a sum, and rewrite the steps [START_REF] Alim | Modified circular hough transform using fpga[END_REF][START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF][START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF][START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF][START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF][START_REF] Hough | Method and means for recognizing complex patterns[END_REF][START_REF] Iddan | Wireless capsule endoscopy[END_REF] as proposed in steps [START_REF] Alim | Modified circular hough transform using fpga[END_REF][START_REF] Antolovic | Review of the hough transform method, with an implementation of the fast hough variant for line detection[END_REF][START_REF] Elhossini | Memory efficient fpga implementation of hough transform for line and circle detection[END_REF][START_REF] Ferlay | Cancer incidence and mortality worldwide: sources, methods and major patterns in globocan 2012[END_REF][START_REF] Goneid | A method for the hough transform detection of circles and ellipses using a 1-dimensional array[END_REF] of the algorithm 2. for each column k from j + 1 to W do 3:

V x ( j+k 2 ) = V x ( j+k 2 ) + H i=1 I(i, j) * I(i, k) 4:
end for 5: end for 6: for each row j from 1 to H -1 do 7:

for each row k from j + 1 to H do 8:

V y ( j+k 2 ) = V y ( j+k 2 ) + W i=1 I(j, i) * I(k, i) 9:
end for 10: end for 11: for each local maximum

V x (i) in V x do 12:
for each local maximum V y (j) in V y do for each point I(i, j) with j from 1 to W -1 do 3:

for each point I(i, k) with k from j + 1 to W do 4:

V x ( j+k 2 ) = V x ( j+k 2 ) + I(i, j) * I(i, k) 5:
end for for each column k from j + 1 to W do 3:

for each row i from 1 to H do 4:

V x ( j+k 2 ) = V x ( j+k 2 ) + I(i, j) * I(i, k) 5:
end for 6:

end for 7: end for The advantage of our histogram construction process show in algorithm 2 is that we obtain the accumulation value for each coordinate of the x-coordinate each two j-loops, that means that we obtain an x-coordinate accumulation value every two columns read and a y-coordinate accumulation value every two rows read. It has a singnificant impact in latency computation and resources consommation as it is explained in section IV-A.

We have validated our algorithm on image of closed contour as show in figure 1. In this image f correspond to the sensitivity threshold visible in step [START_REF] Seo | Efficient architecture for circle detection using hough transform[END_REF] of our algorithm 2. A green circle indicates that we have localized a closed contour. In the next section we describe our digital hardware architecture that implement our algorithm.

IV. CHT ARCHITECTURE

In figure 2, we introduce our architecture to implement the algorithm 2. The overall architecture is composed by five modules described below:

• x-coordinate and y-coordinate computation modules, these modules compute N c x-coordinates and N c ycoordinates. They produce N c 2 center candidates from combination of each x-coordinates and y-coordinates;

• radius computation, this module builds for each center candidate a histogram using Euclidean distance between this center candidate and each edge point. Once the histogram is built, this module assigns the most accumulated Euclidean distance as the radius. This module selects as a real circle the center candidates and radius where the accumulation value is > f * 4 √ 2r ; • Registers module, this module register the N c xcoordinates and the N c y-coordinates of centers candidates and the N c 2 circles in parallel.

In the next sections we describe each module of our architecture. A. x-coordinate and y-coordinate computation module 2 DSP48 slices are used to add the votes between the input column and every two columns. The total votes are accumulated in the blue registers to be added each H cycles (when the input column is totally read). With this architecture, we compute a x-coordinate histogram value every column read.

In the second stage, the vote values are filtered in order to find the local maximum. A sliding window of size F , that corresponds to minimum Euclidian-distance between two centers candidates, is used to compare a vote value with the F 2 previous values and with the F 2 posterior values. The output is the vote corresponding to the largest histogram value for a x-coordinate. If there are two circles with centers separated by an Euclidean-distance less than F pixels in the image, only the circle with more edge points will be detected.

Finally, in the third stage, all the local maximum histogram values are stored in registers R i and C i following the next rules:

• if R i > C i then the register R i+1 = R 1 else R i+1 = 0; • if R i > C i+1 and R i > C i then the register C i = C i+1 else if R i > C i+1 and R i < C i then the register C i = R i else C i = C i .
Hence, the larger values will be gradually transferred to the right side through the registers C i . This process is executed until all the columns in the image are read.

B. Radius computation module

In figure 4, we present our fully pipelined module proposed for the radius computation. In this module, in the first stage, an Euclidean-distance histogram is built in parallel for each center candidate. This stage computes the Euclideandistance between one center candidate and all edge points. Each add and substract computations are performed in 2 cycles, the multiplication computation is performed in 3 cycles. Each operation is executed using one DSP slice. We use the Xilinx CORDIC IP core [START_REF] Walther | A unified algorithm for elementary functions[END_REF] to compute the square root of the Euclidean-distance with a 16 bits integer number in 8 cycles. To vote the Euclidean-distance we use a memory, we propose the architecture illustrated in figure 5, in this architecture each memory is implemented in one BRAM of 18Kbits that enables a simultaneous read and write in one cycle and avoid the collisions.

Once all edge points of the image are read, in the second stage, for each center candidate, all the values of the memory are read in order to find the most voted Euclidean-distance in N 2 cycles. This Euclidean-distance r becomes the radius of this center candidate. We compare this radius r to a threshold of 4 √ 2r [START_REF] Kulpa | On the properties of discrete circles, rings, and disks[END_REF] to determine if it corresponds to a true circle. It is possible to modify this threshold in order to make the verification more sensitive.

Each radius that corresponds to a true circle and the corresponding center become inputs to the shift registers.

In total, 4N c + N c 2 DSP slices and Nc 2 2 BRAMs of 36 Kbits are necessay to perform the radius voting process for N c 2 center candidates and obtain their radius in W * H + 18 + Dm 2 cycles.

V. SOC IMPLEMENTATION

To validate our architecture, we prototype it on a SoC-based system, the Digilent ZedBoard Zynq-7000 ARM/FPGA XC7Z020 SoC Development Board. Zynq is not the final platform, as it cannot be integrated inside a capsule, we plan to integrate it in a new Artix7 from Xilinx, compatible with a capsule, that was not available at the time we make the experiments. Our first goal was to validate our Hough Transform IP and measure its execution time on a real SoC not to far to the final device.

In figure 6, we illustrate the integration of our architecture, the Circle Hough Transform (CHT) IP in this SoC.

We have realised a pipeline of three operations that are: first, write an image into the DRAM memory and read computed circles, second, center computation and third, radius computation. The pipeline execution in the global system is shown in figure 7.

As we can see, we use two address in DRAM (@1, @2) in order to read and write an image at the same time. The CHT IP uses one HP master AXI ports to read images to compute centers candidates and calculate the radius in parallel.

To store the image in a block memory we use BRAMs of 36 Kb that can shift 36K W rows at the same time, as we already shift D m rows in y-coordinate computation module, 2 is limited by the number of BRAM and DSP48 that we have.

We have realised an implementation to detect N c 2 = 25 circles with a maximum circle diameter of D m = 108 and a sliding window F = 40. We consider an image of size 1920x1080. Detail of the implementation can be see in table II. As we can see in table II our Hough Transform can work with a maximum frequency of 149.16 MHz alone and 128.885 MHz in the global system. That is due to the distance between the furthest DSP slice and the AXI AMBA interconnection. Our digital architecture can process an image of 1920x1080 pixels in less thant 40 ms as it is expected and give a 62 fps throughput.

With table III, we can compare our Hough Transform architecture with the state of the art in table I. We calculate the processing time, BRAM and DSP of our architecture to realize a fair comparison with the same sizes of image. As we notice, our architecture is the better and offer a throughput 4 times better than the faster state of the art architecture.

VI. CONCLUSIONS

In this paper we proposed a efficient real-time pipelined architecture Hough Transform for multi-circles detection to help to localise polyps in gastrointestinal tract images. In the our architecture, an efficient method is implemented to significantly reduce internal use of memory and reduce time execution. Our architecture supports a maximum clock frequency of 149.16 MHz alone and 128.885 MHz in a global system to detect until 25 circles with a maximum circle diameter of 108 pixels. Our design has been validated on a Xilinx Zynq-7000 XC7Z020 using 78.5 BRAMs, 153 DSP slices, 21638 LUTs with a 125MHz clock. It obtains a latency of 33.214 ms and an interval between two images of 16,607 ms for a 1920x1080 pixels image. This architecture can process 62 images per second, and it offers a throughput 4 times better than the faster state of the art architecture.

Algorithm 1

 1 Original 1D Hough Transform algorithm Require: edge image I of [W, H] size 1: for each row i from 1 to H do 2:

13 : 3

 133 for all edge I(k, m) in image do14: V r(i,j,||I(k,m)-(i,j)||) = V r(i,j,||I(k,m)-(i,j)||) if max value of V r (i, j, r) > f * (4 √ 2r)then17: ||(x, y) -(i, j)|| = r is a circle 18: 1D Hough Transform multi-circles detection algorithm detail modification: optimization of the edge point 1: for each row i from 1 to H do 2:

4 1 :

 41 1D Hough Transform multi-circles detection algorithm detail modification: change the order of the forloops for each column j from 1 to W -1 do 2:

Fig. 1 .

 1 Fig. 1. Algorithm validation with different value of the sensitivity threshold f

Fig. 2 .

 2 Fig. 2. Our digital architecture.

Fig. 3 .

 3 Fig. 3. x-coordinate computation architecture.

  Finally the largest local maximum histogram values are stored in C i and their respective coordinates correspond to the N c x-coordinates of the circles candidates. Using a similar architecture, N c y-coordinates are calculated. For an image of W xH size, Dm(W +H) 36K BRAMs of 36Kbits and D m DSP48 slices are necessary to calculate the x-and y-coordinates in W * H + 2 + Dm 2 + F 2 + N c cycles. Each one x-and y-coordinates are combined to obtain N c 2 center candidates.

Fig. 4 .

 4 Fig. 4. Radius computation module architecture.

Fig. 5 .

 5 Fig. 5. Proposed radius histogram memory architecture.

Fig. 6 .Fig. 7 .36K + Nc 2 2

 672 Fig. 6. System diagram of our AXI CHT IP core integrated on a Zynq architecture.

TABLE I STATE

 I OF THE ART OF HOUGH TRANSFORM HARDWARE IMPLEMENTATION.

	Authors	FPGA	Resources	Image	Latency [ms] /	Throughput	Latency [ms] extrapoled
			used	resolution [pixel]	frequency [MHz]	[Mpixel/s]	for 1920x1080 resolution
	Ferhat et al, 2012 [1]	Virtex 2	578 slices, 8 BRAM	one circle	-/ 66.9	-	-
	Elhossini et al, 2012 [3]	Virtex 4	256Kb of BRAM	800x600	33.33 / -	14.40	144
	Zhou et al, 2014 [19]	Virtex-7	5562Kb of BRAM, 398 DSP48	400x400	5.338 / 181.812	29.974	69.18
	Seo et al, 2015 [16]	Kintex 7	internal memory	640x480	10 / 250	30.720	67.5
				1024x1024 scaled
	Irwansyah et al, 2015 [8]	Virtex 4	512Kb of BRAM	by factor 2 (512x512)	7.8125 / 135	33.554	61.8
	Kumar et al, 2017 [11]	Artix 7	52 BRAMs of 36Kb	320x240	3.46 / 203	22.197	93.42
	Algorithm 2 Our Modified 1D Hough Transform multi-
	circles detection algorithm to compute histograms Vx and
	Vy

1:

for each column j from 1 to W -1 do 2:

TABLE II AXI

 II CHT IP CORE IMPLEMENTATION RESULTS.

	Architecture	CHT	AXI CHT	Full
			IP core	System
	LUT	20637	20770	21638
	LUTRAM	275	278	373
	FF	18629	18697	19706
	BRAM (36Kb)	78.5	78.5	78.5
	DSP	153	153	153
	Freq. maximum[MHz]	149.16	147.99	128.89
	Latency[ms]	27.805	28.025	32.178
	Interval[ms]	13.902	14.012	16.089
	Throughput[Mpixel/s]	149.154	147.984	128.89
	fps[frame/s]	72	71	62

TABLE III COMPARISON

 III WITH THE STATE OF THE ART.

	Our method	Artix7 with a frequency of 128.89MHz
		Estimated and simulated	Implemented
	Resolution	320	400	512	640	1920
	-[pixel]	x240	x400	x512	x480	x1080
	BRAM of 36Kb	17.5	20.5	22.5	28.5	78.5
	DSP48 slices	153	153	153	153	153
	Latency [ms]	1.19	2.48	4.07	4.77	32.18
	Interval [ms]	0.60	1.24	2.03	2.38	16.08
	fps [frames]	1676	805	491	419	62
	Throughput
	-[Mpixel/s]	128.8	128.9	128.9	128.9	128.9

LIP6, CNRS UMR 7606, Sorbonne Université, Paris, France.

APHP, Hôpital Saint-Antoine, Sorbonne Université, Paris, France.