Vincent Richefeu
email: richefeu@lmgc.univ-montp2.fr

Moulay Saïd

El Youssoufi

Farhang Radjaï
email: radjai@lmgc.univ-montp2.fr

Shear Strength of Unsaturated Soils: Experiments, DEM Simulations, and Micromechanical Analysis

Introduction

The interest of scientists for granular materials is motivated by the important place they occupy in our natural environment. Well-known examples are soils, rocks and powders. In addition, many industrial processes implement transformations of granular materials such as pharmaceutical tablets, agricultural and food products, building materials (Bika et al., 2001;Iveson et al., 2002). The mechanical behavior of these materials, in particular soils, was widely developed in the context of macroscopic continuum approach. This approach is based on the concept of Representative Elementary Volume (REV) which is not well-established for granular media. Moreover, it introduces many parameters that require a large number of identification experiments. In addition, most continuum approaches do not account for grain-scale mechanisms such as the initiation and propagation of shear bands or cracks.

On the other hand, the discrete character of granular materials makes it possible to identify unambiguously the grain scale and thus the proper kinematics and mechanical behavior at this scale. Grain-scale properties depend on composition, form, size or surface state of grains. A discrete approach requires furthermore a rigorous definition of the interactions of each grain with its close neighbors through mechanical contacts, friction and/or cohesion. External actions like the moisture, temperature and pressure can also act on the evolution of these interactions. This is a promising approach for understanding all the complexity and often surprising properties of granular materials if adequate techniques can be developed. Such techniques are often referred to as Discrete Elements Method (DEM). This method has been successfully applied to study classical problems in soil mechanics as shear bands localization [START_REF] Bardet | [END_REF], slope stability (Staron et al., 2002) and shear strength (Jiang et al., 2004;Thornton and Antony, 2000;[START_REF] Richefeu | Approche par éléments discrets 3D du comportement de matériaux granulaires cohésifs faiblement contraints[END_REF].

In this paper, we investigate shear strength properties of wet granular materials as a function of water content in the pendular state. Sand and glass beads were wetted and tested in a direct shear cell. In parallel, we carried out DEM simulations by means of a 3D numerical code (tapio-K) based on molecular dynamics approach developed in our laboratory. We used an explicit expression of the capillary force as a function of interparticle distance, water bridge volume and surface tension. A peculiar feature of our system is that the effects of capillary bonding can be observed only if the confining pressure is of the same order of magnitude or below the tensile strength or the Coulomb cohesion. The latter is proportional to the strength of capillary bonds and inversely proportional to the particle size [START_REF] Richefeu | [END_REF]. For fine sand, typical values are below 1 kPa, imposing us to work with low confining pressure.

We find good agreement between experiments and numerical simulations. We show that the shear strength is mostly controlled by the distribution of liquid bonds. This property results in the saturation of shear strength as a function of water content. We arrive at the same conclusion by analyzing the shear strength from the microstructure and by accounting for grain polydispersity. Finally, we discuss the applicability of the discrete element approach to unsaturated soils under more general loading paths.

Discrete Element Method

We developed a DEM code based on the Molecular Dynamics (MD) method (Cundall and Strack, 1979;[START_REF] Allen | Computer Simulation of Liquids[END_REF]. The grain motions are explicitly integrated by accounting for their interactions (e.g., contact, friction, capillary cohesion, magnetisation . . . ). Here, we present the interaction laws used for the contact, friction and capillary cohesion in the case of spherical grains.

Contact and Friction Laws

The normal contact law is modeled as a spring and a dashpot in parallel. The normal force f ctc n is given by

f ctc n = -k n δ n + γ n v n , (1)
where δ n is the normal distance (negative or zero when the grains are in contact), k n is the normal stiffness, v n is the relative normal velocity, and γ n is a damping coefficient.

The friction law expresses the tangential force as a function of the sliding velocity v s . The friction force f t , contained in the contact plane, obeys a viscous-regularized Coulomb law:

f t = min{γ t v s , µf ctc n } v s v s , (2)
where γ t is the tangential viscosity and µ is the coefficient of friction.

Capillary Cohesion Law

In the presence of water, the grains can be connected by a liquid bridge as illustrated in Fig. 1a. The liquid bridge gives rise to an attractive force, the force of capillary cohesion, between the grains. This force results from the combined action of the difference in pressure between the liquid and gas phases and the liquid surface tension γ (Pierrat and Caram, 1997;[START_REF] Willett | Richefeu macro: svmult[END_REF]Gröger et al., 2003;[START_REF] Soulié | [END_REF]. We use the explicit expression of the capillary law of cohesion proposed by [START_REF] Soulié | [END_REF] in the polydisperse case (Fig. 1b). This law, expressing the capillary force f c as a function of the normal distance δ n , is given by

f c =    -πγ √ R 1 R 2 {exp(A δn R2 + B) + C} for δ n > 0 -πγ √ R 1 R 2 {exp(B) + C} for δ n ≤ 0 (3)
where R 1 and R 2 are the grains radii (R 1 < R 2 ); A, B and C are parameters which depend on the volume V b of the liquid bond and on the contact angle θ; δ 0 is the rupture distance. From a theoretical study of a liquid bridge between two spheres, Lian et al. (1993) proposed the following rupture criterion:

δ 0 = (1 + 0.5θ)V 1/3 b . (4)
We used this criterion which was validated by local experiments [START_REF] Soulié | Cohésion par capillarité et comportement mécanique de milieux granulaires[END_REF]. It is also necessary to define a criterion for the formation of a liquid bond. It is considered that a liquid bridge can be formed (or to reform itself) when the grains are in contact (δ n ≤ 0). At the numerical level, the main difficulty comes from the management of the distribution of the total volume of water between the grains, i.e. the determination of local volumes of the capillary bonds. In the simulations presented in this paper, the total volume of water is distributed over all the possible bonds of the sample in proportion to the radii of the touching grains. This corresponds to a global and homogeneous management of the distribution of water, which makes it possible to connect the local water volumes to the macroscopic water content. Local water redistributions were considered, too, see [START_REF] Richefeu | Approche par éléments discrets 3D du comportement de matériaux granulaires cohésifs faiblement contraints[END_REF]. The distribution protocol plays a determining role in the mechanical resistance of material, as we shall see below. However, this information remains difficult to reach in experiments with real materials.

Direct Shearing at Low Confining Stresses

Several modifications were made to the standard Casagrande's shear box in order to be able to measure the shear strength of granular materials to very low confining pressures (lower than 1 kPa). We present here the main experimental and numerical results obtained. These results will be analyzed through a theoretical expression of the Coulomb cohesion resulting from a microscopic analysis.

Experiments and Simulations

Figure 2 shows a schematic view of the setup, its dimensions, and certain notations used. A normal pressure σ = g(m N /S + ρ h) is applied to the sample by means of a flask whose mass m N can be modified by pouring sand into it. ρ is the bulk density and g is the gravity. A shear stress τ = m T /S is incrementally imposed by gradually filling a cup connected to the moving part of the box by a system of pulley. The stress reached during the rupture of the sample is the yield shear stress. Several tests carried out with various normal stresses allow us to estimate the yield locus in the Mohr-Coulomb plane. In direct shearing, the boundary conditions are such that the finite size effects cannot be fully eliminated [START_REF] Thornton | A DEM comparison of different shear testing devices[END_REF]. We did not check such size effects in our experiments. Given the system size, this requires using considerably more particles with smaller size, affecting thus the level of Coulomb cohesion in the presence of water. But we checked that the measured strengths are reproducible and in good agreement with analytical estimates (see below).

Figure 3a shows the yield loci obtained for a sand made up of angular grains of diameters ranging from 0.1 to 0.4 mm with various water contents w (ratio of the water mass on grains mass). One can notice that the experimental points are well fit to straight lines, in agreement with the Mohr-Coulomb model τ = tan ϕ σ + c characterized by two parameters: the macroscopic cohesion c and the internal friction angle ϕ. This figure also shows the good Fig. 2. Experimental Setup reproducibility of the experiments. The angle ϕ does not seem to vary appreciably with w in contrast to the parameter of cohesion which increases in a nonlinear way with water content and is saturated to a value c m for a water content w m (Fig. 3b). For the water contents above 5%, we leave the pendular regime.

The numerical tests are similar to the experimental tests (same level of loading, same dimensions of the box . . . ). A numerical sample of 7307 spherical grains was prepared with a solid fraction φ = 0.6. The number of particles is imposed by the system dimensions and particle size in order to reach the same level of packing fraction as in experiments. Various water contents were obtained by distributing the total water volume over all the contacts (δ n ≤ 0) in this sample. A set of 15 simulations (three levels of the normal stress and five values of the water content) were performed. Figure 4 presents the stressstrain plots obtained for w = 0% and w = 1%. The rupture stress is considered to be the residual shear stress because the shear stress approaches the residual state passing by a peak state. As for the experiments, the evolution of the macroscopic cohesion can be analyzed as a function of the water content.

Figure 5a shows the estimates of yield loci obtained numerically. One can that the numerical model reproduces the experimental data. The water content does not have an influence on the internal angle of friction and the cohesion parameters increases in a nonlinear way and saturates at a relatively low level of the water content (Fig. 5b).

Micromecanical Analysis

From a micromechanical analysis, a theoretical expression of the Coulomb cohesion was established [START_REF] Richefeu | [END_REF]:

c th = 3 2π µκs φz D , (5)
where κ is a parameter that depends essentially on the surface tension of water, s is a factor related to the polydispersity of material, z is the average number of liquid bonds per grain, and D is the average diameter of the grains. The validity of this expression was shown by comparing the predicted theoretical values of Coulomb cohesion with experimental and numerical measurements (Table 1). This comparison shows also that the numerical results are in quantitative agreement with the experiments. In Table 1, we show also experimental results of three other materials [START_REF] Richefeu | [END_REF][START_REF] Richefeu | Approche par éléments discrets 3D du comportement de matériaux granulaires cohésifs faiblement contraints[END_REF]: (1) tightly-graded polydisperse glass beads with diameters from 0.4 mm to 0.5 mm (denoted by GB1), (2) wellgraded polydisperse glass beads with diameters from 0.4 mm to 0.8 mm (denoted by GB2), and (3) monodisperse glass beads of diameter 1 mm (denoted by GB3).

Conclusions

Experiments and the simulations based on discrete element simulations were used with the aim of studying and analyzing the shear strength of unsaturated granular materials in the pendular state at low levels of loading. It was shown that the Coulomb cohesion increases with the water content and that it is saturated to a maximum value which depends only on the nature of the material. A theoretical analysis based on micromechanics allows us, on one hand, to validate the numerical modeling and, on the other hand, to show that the increase in the shear strength with water content is primarily due to an increase in the number of liquid bonds per unit volume.

In the extension of this work, it is essential to evaluate the limits of the model by considering other materials and non monotonous loading paths. In particular, we would like to study the shear strength of granular media with a larger polydispersity than materials that were used in the present investigation. Since the distribution of liquid bonds seems to be a major parameter for the cohesion of unsaturated granular materials, it also merits to be investigated in more detail experimentally. Finally, an interesting application of the ideas put forward in this paper would be to examine by which mechanisms the cohesion of a sample of unsaturated sand increases as a result of compactification.

Fig. 1 .

 1 Fig. 1. Capillary cohesion law. (a) Physical and geometric parameters of a capillary bond. (b) Typical behavior of the capillary strength as a function of the normal distance

Fig. 3 .Fig. 4 .

 34 Fig. 3. Experimental results. (a) Yield loci estimated for a (b) Coulomb cohesion as a function of water content

Fig. 5 .

 5 Fig. 5. Simulation results. (a) Estimated yield loci. (b) Coulomb cohesion as a function of water content (experiments were carried out with 1 mm glass beads)

Table 1 .

 1 Measured and theoretical parameters for the experimental and numerical samples

		Sand GB1 GB2 GB3 Simulations
	D (mm) 0.16 0.45 0.60 1.00 1.65
	s	0.50 0.99 0.91 1.00 0.79
	z	6	6	6	6	9
	φ	0.6	0.6	0.6	0.6	0.6
	tan ϕ	0.66 0.58 0.58 0.46 0.48
	cm (Pa)	600	350 300 150 120
	c th (Pa)	709	438 302 158 118

Page: 4 job: Richefeu macro: svmult.cls date/time: 18-Oct-2006/20:26


Raphaël Jaries

Vincent Vantilcke

Philippe Clevenbergh

Jocelyne Adoissi

Rachida Boukhari

Caroline Misslin

Mathieu Nacher

Stephen Vreden

Anne Jolivet

Raphael Jaries

Population movements and the HIV cascade in recently diagnosed patients at the French Guiana -Suriname border

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

ABSTRACT:

Border areas are particular "hot spots" generating high levels of HIV vulnerability and facing great challenges to control epidemics. The objective of this study is to describe the sociodemographic, clinical and biological profiles of newly HIV diagnosed people at the French Guiana-Suriname border, to construct an HIV care cascade and compare it with the Surinamese one. HIV-patients aged over 15 years newly diagnosed in western French Guiana in 2011 and 2012 were included in a retrospective cohort study. Patients were identified using different sources (n=121). The male-tofemale ratio was 0.8, 85% of the patients were of foreign origin, 72% were undocumented migrants, 21% were living in Suriname and 48% had baseline CD4 cell counts <200 cells/mm3. After one year, 34% were lost to follow-up, 54% received treatment, 34% had controlled viremia and 6% died. We observed a disappointing HIV cascade, like that of Suriname, requiring to develop a coordinated healthcare offer on both sides of the border. Targeted efforts through a bi-national collaboration are needed to address the specific issues of cross-border patients to reach the 90*3 UNAIDS's diagnosis, link to care and treatment targets and better control the local epidemic.

KEY WORDS:

HIV, French Guiana, Suriname, Migrant, Health Policy

INTRODUCTION:

There is growing evidence linking HIV prevalence and population mobility (International Organization for Migration [IOM], 2009). Mobile populations, and even more so undocumented migrants, constitute vulnerable populations at higher risk of HIV acquisition and lower access to care and support [START_REF] Tanser | HIV treatment cascade in migrants and mobile populations[END_REF]. In addition, some people living with HIV (PLHIV) may migrate to avoid stigmatization or to access comprehensive HIV care. Border areas are particular "hot spots" generating HIV vulnerability and facing great challenges to control epidemics [START_REF] Espinoza | Increases in HIV diagnoses at the U.S.-Mexico border, 2003-2006[END_REF][START_REF] Hemhongsa | TB, HIV-associated TB and multidrug-resistant TB on Thailand's border with Myanmar, 2006-2007[END_REF][START_REF] Lyttleton | Sister cities and easy passage: HIV, mobility and economies of desire in a Thai/Lao border zone[END_REF][START_REF] Servin | Healthcare provider perspectives on barriers to HIV-care access and utilisation among Latinos living with HIV in the US-Mexico border[END_REF]. Transborder discrepancies in access to care and social services and lack of collaboration on health issues may further increase these challenges [START_REF] Coker | Health-care system frailties and public health control of communicable disease on the European Union's new eastern border[END_REF].

French Guiana (Guiana) is a French overseas territory. Saint Laurent du Maroni (SLM) lies along the Maroni River marking the French-Suriname border. There have been dramatic population changes since the early 90's, when civil war in Suriname forced a massive flux of refugees into western Guiana. In 2013, the city counted 41,800 inhabitants, but its hospital serves an estimated 80,000 persons. It has a rapidly growing (+7%/year), multicultural, multi-lingual, highly mobile population.

Compared to the rest of the costal Guiana, the economy and the health care offer are less developed [START_REF] Carde | The French Health Care System Challenged by the Over-Sea : Some Inequalities in French Guyana[END_REF].

For 20 years, Guiana has had the highest HIV prevalence in France [START_REF] Nacher | What is driving the HIV epidemic in French Guiana[END_REF]. In 2014, 560 HIV patients were followed at SLM's hospital, representing 30% of all HIV patients followed in Guiana. The features of the HIV epidemic in western Guiana are unique. Concurrent partnerships may be one of the main drivers of the epidemic [START_REF] Nacher | What is driving the HIV epidemic in French Guiana[END_REF], while stigma remains very high [START_REF] Van Melle | Prevalence and predictive factors of stigmatizing attitudes towards people living with HIV in the remote villages on the Maroni River in French Guiana[END_REF]. Mobile populations, notably boatmen [START_REF] Gaubert-Marechal | Knowledge, Attitudes, Beliefs and Practices on HIV/AIDS among Boatmen on the Maroni River: A Neglected Bridging Group[END_REF], had an important role in the rapid increase of HIV prevalence since the 90's acting as a bridging group between vulnerable sex workers and the general population. However, mobility along and across the Maroni has many motives: economic (gold mining, and informal transborder's economy), farming and "family-related". Table 1. The objective of the study was to describe the characteristics of newly diagnosed HIV-patients in western Guiana, to construct the HIV care cascade and compare it with the Surinamese one.

Guiana and Suriname are compared in

METHODS:

Between January 1 st 2011 and December 31 st 2012, all patients aged over 15 years, newly-diagnosed with HIV-infection in Western Guiana were included in a retrospective cohort analysis. Patients were identified from the French Hospital Database on HIV, from SLM's Hospital laboratory, or from other health providers involved in HIV-screening in western Guiana. Sociodemographic data (age, gender, country of birth, residency status, place of residence), characteristics of HIV screening (place and testing mode, baseline CD4 count), treatment outcome at one year were collected from medical records. Patients were considered "lost-to-follow up" if they had not consulted for >6 months.

The HIV-care cascade, was a denominator-denominator linked cascade which used the exact same group of individuals for all stages of the cascade [START_REF] Haber | Constructing the cascade of HIV care: methods for measurement[END_REF]. We constructed 4 stages, using the same definitions as the Surinamese cascade (MoH Suriname, 2015) : "HIV diagnosed", "Linked to HIV-Care" (at least one CD4 count), "on ART" (initiation of ART) and "suppressed viral load" (at least one estimation of viral load ≤ 1000 copies/ml after 6 to 12 months of treatment).

This protocol was approved by the institutional review board of the SLM Hospital.

Statistical analysis was carried out with Epi Info 7 software.

RESULTS:

The study included 121 patients. Sociodemographic, screening and baseline data are described in table 1. Most new HIV patients were females (56%), born in Suriname (60%) and undocumented (72%). Most patients (56%) lived in SLM and 21% in Suriname (Paramaribo 12%, Albina: 5%, other: 4%). 48% had baseline CD4 cell counts <200/mm 3 .

A small proportion of cases (9%) had previously been diagnosed; mostly (9/11) in Suriname. At one year, 34% were lost to follow-up, 6% were referred to another clinic and 6% had died.

Figure 1 represents the HIV care cascades in western Guiana and Suriname between 2007 and 2012.

Among the 121 HIV-diagnosed patients, 89% were linked to HIV care. Treatment was indicated for 74% of the patients and initiated in 73% of them. Forty-one patients (34%) had viral load <1000 copies/ml after 6 months. Other patients were either non-adherent to therapy (21%) or were not tested for viral load (79%). Using a threshold at 50 copies/ml, we found a 29% suppression rate.

The migratory status did not influence the cascade. Forty-seven treated patients were tested for HIV drug-resistance and 9 (19%) presented resistances to ARVs: 6 (12.8%) to at least one NNRTI, 4 (8.5%) to NRTI, 1 (2.1%) to PI and 2 (4.2%) to NtRTI. Three out of eight (38%) known HIV-infected patients showed HIV drug-resistance.

DISCUSSION:

Most of newly diagnosed HIV-infected patients were women, contrarily to mainland France (2.1) [START_REF] Morlat | Prise en charge médicale des personnes vivant avec le VIH. Recommandations du groupe d'experts[END_REF] and to other parts of Guiana (1) [START_REF] Melin | Surveillance des infections à VIH et du SIDA dans les départements français d'Amérique: données 2013 et évolutions depuis 2003[END_REF]. However, this is similar to the Caribbean Region (UNAIDS, 2012), where HIV/AIDS disproportionately affects women and adolescent girls.

Most of patients were of foreign origin (85%) with a precarious legal status (72% were undocumented migrants), whereas among the general adult population living in SLM these proportions are estimated at 58% and 26%, respectively [START_REF] Jolivet | Migrant health in French Guiana: Are undocumented immigrants more vulnerable?[END_REF]. Migrants and undocumented migrants are therefore overrepresented among PLHIV.

Almost half (48%) of patients had low baseline CD4 cell counts, whereas this proportion was 29% for patients followed in Cayenne Hospital (Regional Coordination Center for the Fight against HIV [COREVIH -French Guiana], 2015). The death rate at one year (6%) was much higher compared to the whole Guiana HIV cohort where it dropped below 1% per year since 2005 (COREVIH, 2015).

Twenty-one per cent of the patients in care at SLM were currently living in Suriname. HIV-infection was already diagnosed in Suriname for 7% of the cohort. Some of them may have received treatment in Suriname. The proximity and the perception of having better healthcare facilities in SLM was one of the main reasons for patients living in Suriname to seek pregnancy and emergency care in SLM's hospital [START_REF] Jolivet | Migration, health, and care in French overseas territories[END_REF]. The high level of stigmatisation in that area [START_REF] Van Melle | Prevalence and predictive factors of stigmatizing attitudes towards people living with HIV in the remote villages on the Maroni River in French Guiana[END_REF] is probably an additional factor to seek HIV care elsewhere. Unfortunately, we did not have information on patient itineraries. Further research should aim to better understand Surinamese patients' health seeking itineraries. Migration of PLHIV across the border has considerable implications in relation to health service provision and public health surveillance systems. Therefore, in Suriname as well as in Western Guiana, the estimation of HIVprevalence as well as the whole HIV care cascade may be affected.

We observed a disappointing HIV care cascade where only 34% of the cohort had controlled viremia mainly due to the high rate of lost to follow-up. In comparison with the Surinamese HIV cascade (MoH Suriname, 2015), more patients were linked to care and on ART in Guiana (where treatment initiation threshold is higher), but we found a similar rate of patients lost to follow-up after treatment initiation. Some patients lost to follow-up in Suriname could presumably be found in SLM and vice-versa. Factors associated with follow-up interruption could not be identified in this small study. Other local studies [START_REF] Nacher | Risk factors for follow-up interruption of HIV patients in French Guiana[END_REF] showed that younger patients, foreigners and undocumented patients were more likely to be lost to follow-up, as well as those not receiving any treatment or with CD4< 500 mm/3 when diagnosed. Precarious living conditions of migrants, presumably explain adherence difficulties. In Guiana, the full healthcare package including ARV according to French national guidelines is accessible FOC to all patients, including undocumented migrants, under the precept of emergency care. However, provision of chronic care is hampered by administrative hurdles and discriminations in accessing health services [START_REF] Carde | Les discriminations selon l'origine dans l'accès aux soins[END_REF] leading to frequent disruptions in health insurance and follow-up. Linguistic barriers, illiteracy, lack of information and support in mother tongue may also explain these results.

Finally, as a probable consequence of cross-border patient mobility and low adherence, we observed a high prevalence of drug resistance among our cohort: 19% compared to 12.2% in France among newly diagnosed HIV patients [START_REF] Morlat | Prise en charge médicale des personnes vivant avec le VIH. Recommandations du groupe d'experts[END_REF], 6.3% in Latin America and the Caribbean Region [START_REF] Frentz | Temporal changes in the epidemiology of transmission of drug-resistant HIV-1 across the world[END_REF], and 4.6% in the whole Guiana (among treatment-naive patients with a CD4 cell count above 350/mm3) [START_REF] Darcissac | HIV-1 Pol Gene Polymorphism and Antiretroviral Resistance Mutations in Treatment-Naive Adult Patients in French Guiana Between 2006 and 2012[END_REF]. This makes research and coordinated strategies urgent in this area.

The main limitations of the study were the small study population, the retrospective design and the frequent missing data. Moreover, our cascade, was based on a limited number of patients during a limited period and did not include undiagnosed HIV. With an estimation of 40% of undiagnosed HIV (MoH Suriname, 2015), our rate of suppressed viral load would drop to 20%.

  In eastern Suriname, clinics only provide primary care and only few HIV patients are followed (around 20 patients in 2014). Antiretroviral drugs (ARV) are available, but those requiring CD4-count, viral load, or radiology need to travel about 150 Km to Paramaribo on their own expenses. There, public hospitals provide non-emergency care free of charge (FOC) for persons of Surinamese citizenship only.

Finally, the comparison

  with Surinamese's cascade is also limited because of different time-frames and different methods in data surveillance and data analysis.CONCLUSION:Our study shows that PLHIV living on the French-Suriname border are vulnerable and deserve specific attention. This requires bi-national collaboration to address the specific issues of crossborder patients. Both countries should first reinforce the care offer and facilitate its access. Both systems must work together to systematize exchanges of medical information to support continuity of care for mobile patients. Joint research efforts should aim to better estimate and understand the high level of follow-up interruption in both countries. Much remains to be done in the general population, to provide information on HIV transmission, improve testing and reduce stigma and discrimination. A strong support from national and regional health authorities is essential in both countries to reach these goals.

Table 1 :

 1 General and HIV data in French Guiana and Suriname

	French Guiana	Suriname

*** French Guiana regional register of births (

2014

) ǂ (MoH Suriname, 2015) ǂ ǂ Regional Coordination Center for the Fight against HIV (COREVIH) French Guiana 14

Table 2 :

 2 Patients characteristics

	N	%

* including : Deterioration of general status (weight loss, asthenia, anorexia) (24), isolated fever (4) , diarrhea (4), primoinfection (2), Opportunistic infection (zona (3), histoplasmosis (2), TB (2), candidosis (1)), neurologic symptom (2), dermatosis (1), other STD (2), other (1).

For Peer

Figure 1: The HIV care cascade in Western French Guiana (2011)(2012) and Suriname (2007Suriname ( -2012) )


Duy Lê

Yongchao Huỳnh

Thierry Xu

Géraud

Morphology-Based Hierarchical Representation with Application to Text Segmentation in Natural Images

Keywords: Mathematical Morphology, Tree of Shapes, Non-linear Laplace Operator, Text Segmentation, Document Binarization

Many text segmentation methods are elaborate and thus are not suitable to real-time implementation on mobile devices. Having an efficient and effective method, robust to noise, blur, or uneven illumination, is interesting due to the increasing number of mobile applications needing text extraction. We propose a hierarchical image representation, based on the morphological Laplace operator, which is used to give a robust text segmentation. This representation relies on several very sound theoretical tools; its computation eventually translates to a simple labeling algorithm, and for text segmentation and grouping, to an easy tree-based processing. We also show that this method can also be applied to document binarization, with the interesting feature of getting also reverse-video text.

I. INTRODUCTION

With the dramatic increase of images and video acquired with mobile devices, content-based analysis techniques have received a great deal of attention over the last few years; this is in particular the case of text detection. In this paper, we focus on text segmentation, that is, finding candidate components for text characters in natural images.

Text localization methods are often classified into slidingwindows-based and connected-components-based approaches. For the former approaches, a classifier is used to determine if a window contains text, which can be SVM [START_REF] Coates | Text detection and character recognition in scene images with unsupervised feature learning[END_REF], AdaBoost [START_REF] Lee | Adaboost for text detection in natural scene[END_REF], or Convolutional Neural Networks (CNN) [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF]. Such methods are relatively expensive due to the number of windows to take into account. The latter approaches consider as text candidates connected components extracted from the image thanks to, e.g., keypoints [START_REF] Bušta | FASText: Efficient unconstrained scene text detector[END_REF], the Stroke Width Transform (SWT) [START_REF] Epshtein | Detecting text in natural scenes with stroke width transform[END_REF], the Toggle Mapping Morphological Segmentation (TMMS) [START_REF] Fabrizio | TextCatcher: A method to detect curved and challenging text in natural scenes[END_REF], or the Maximally Stable Extrema Region (MSER) [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF]. Actually many methods in ICDAR 2015 "Robust Reading" competition are based on MSER or on Extremal Regions (ER) [START_REF] Karatzas | ICDAR 2015 competition on robust reading[END_REF]. Let us mention that a non-window-based text detection method, using Fully Convolutional Networks (FCN) to make pixels-to-pixels text prediction, has just been proposed in [START_REF] Zhang | Multioriented text detection with fully convolutional networks[END_REF]. Last, we shall notice that some very recent methods have put the emphasis on getting good run-time performances [START_REF] Zhang | Symmetry-based text line detection in natural scenes[END_REF], [START_REF] Bušta | FASText: Efficient unconstrained scene text detector[END_REF], [START_REF] Neumann | Real-time lexicon-free scene text localization and recognition[END_REF]. For a larger bibliography, the reader can refer to [START_REF] Ye | Text detection and recognition in imagery: A survey[END_REF], [START_REF] Fabrizio | TextCatcher: A method to detect curved and challenging text in natural scenes[END_REF], and [START_REF] Zhu | Scene text detection and recognition: Recent advances and future trends[END_REF].

We propose a hierarchical image representation based on the morphological Laplace operator, also called morphological Laplacian, with an application that segments text characters (so it is a component-based approach), and groups them into text boxes / lines thanks to two kinds of spatial relations: adjacency and inclusion. The contributions of this paper are the following:

• a hierarchical (i.e., tree-based) representation of the image contents, where adjacency between components is related to inclusion; • a character segmentation method which is a good tradeoff between efficiency (linear time complexity) and quality (with a competitive F-score); • an efficient grouping of characters into text boxes, taking fully advantage of the tree structure; • an illustration on another application (document binarization) of the capabilities of the proposed tree-based representation.

As compared to many methods of the literature, the method that we propose features many properties: it is invariant to contrast inversion (so we also extract reverse-video text without any special processing); it is invariant to contrast change; it is invariant to scale and rotation; and it handles a large variety of scripts (Latin, Hebrew, Chinese, etc.). Note that we only use the hierarchical representation to extract text candidates; although we filter out some irrelevant components, we do not include a false positive elimination step (whereas many methods do). This paper does not contain an evaluation at text-line level of a complete text detection pipeline. Yet we give some quantitative results of text segmentation, which reveals that our method outperforms some widely used text component extraction methods.

In Sec. II we recall the theoretical background in mathematical morphology and digital topology that is used in our approach. In Sec. III we detail the different aspects of our approach: the hierarchical Laplacian-based representation and how we rely on it to segment text. In Sec. IV we proceed to experiments and show that we compete with classical component-based text segmentation methods. Last we conclude and give perspectives in Sec. V.

II. THEORETICAL BACKGROUND

This section gives a brief introduction to the theoretical tools involved in the proposed method. The impact of these tools is to obtain strong properties without making the method more complicated, and actually, they allow for simplification.

A. Morphological Laplace Operator

In order to detect text in images, many methods first look for candidate regions for characters. A seminal method, based on contour detection, is to consider the 0-crossings of a discrete Laplace operator (denoted by ∆): given a gray-level image u, the contours of interest are given by ∆u = u xx + u yy = 0. This method is interesting for several reasons: 1) it is a very simple approach; 2) it provides closed contours; 3) labeling the components of the image having the same sign, resp. positive and negative, gives a segmentation; 4) it is self-dual, i.e., it processes dark objects and bright ones in the same way.

The simplest discretization of this linear operator relies on a cross-shaped convolution kernel. Yet this elementary operator is very sensitive to noise, so many 0-crossings arise as it can be seen in Figure 1(b). To get rid of this problem, one can rely on a larger kernel, e.g., by considering the approximate given by the Laplacian of Gaussian (LoG) operator. Unfortunately, its smoothing effect alter the localization of contours, as illustrated by Figure 1(c).

An elementary morphological Laplace operator has been defined in [START_REF] Van Vliet | An edge detection model based on non-linear laplace filtering[END_REF] by ∆ N = (δ N -id) -(id -ε N ), relying on the elementary dilation (δ) and erosion (ε) morphological operators. A natural extension of the elementary operator uses a structuring element B to replace the neighborhood N ; it is depicted in Figure 1(d) with B being a centered square (denoted by ◻) of size 17 × 17. Although it has the same "simplification strength" as the linear LoG version, one can see when comparing the resulting 0-crossings (LoG in Figure 1(c) vs. morphological in Figure 1(e)) that the morphological nonlinear version features a much higher fidelity to actual object contours than the linear version. Furthermore, when increasing the size of the structuring element, 0-crossing contours keep a strong fidelity to data, as illustrated in Figure 1(f) with B now being a 51 × 51 square.

One can also observe that the salient object contours are curiously very stable-they are not altered-when the size of the structuring element (the "morphological kernel") increases. From Figure 1(e) to Figure 1(f), the contours of the "Yes" word remain the same, whereas spurious non-interesting contours disappear. Furthermore, the size of the structuring element B, a 51×51 square, is much larger than the character thickness (note that the input image u has 130×100 pixels). It means that obtaining salient contours thanks to the morphological Laplace operator hardly depends on the size of B. Despite of this great advantage, the morphological Laplacian has been almost never used in the literature [START_REF] Soille | Morphological Image Analysis-Principles and Applications[END_REF], [START_REF]Mathematical Morphology-From Theory to Applications[END_REF].

B. Tree of Shapes

The tree of shapes is a morphological self-dual representation of an image; see [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF] for history, implementation, and references. This tree encodes the inclusion of the level sets, i.e., the connected components obtained by thresholding. An illustration is given on a very simple image by Figure 2.

Given an image u ∶ X → Z and any scalar λ ∈ Z, the lower level sets are defined as

[ u < λ ] = { x ∈ X u(x) < λ },
and the upper level sets as

[ u ≥ λ ] = { x ∈ X u(x) ≥ λ }, with X = Z 2 for a 2D image.
Considering the connected components of these sets (obtained by the CC operator), and using the cavity-fill-in operator (denoted by Sat), the tree of shapes of an image u is defined by: S

(u) = { Sat(Γ) Γ ∈ CC([u < λ]) ∪ CC([u ≥ λ]) } λ .
Such a tree is called selfdual since many self-dual operators can be derived from this tree [START_REF] Xu | Connected filtering on tree-based shape-spaces[END_REF].

C. Well-Composed Sets and Maps

A sub-class of sets defined on the cubical grid, called wellcomposed, has been proposed in [START_REF] Latecki | Well-composed sets[END_REF], where all connectivities are equivalent, thus avoiding many topological problems. This notion of well-composedness has been extended in [START_REF] Latecki | 3D well-composed pictures[END_REF] from sets to functions: a gray-level image u is well-composed if any set [u ≥ λ] is well-composed. A straightforward characterization of well-composed gray-level images is that every Step 1

Step 2

Step 3

Step 4

Step 5

Fig. 4: Overview of the proposed method: hierarchical representation (Steps 1 to 4) and application (Step 5).

Well-composed gray-level images are interesting because every contour of any level set component is a Jordan curve.

To get a well-composed image from a primary image, one can compute an interpolation of the primary image that is wellcomposed. Figure 3 gives an example of an image which is not well-composed, but whose interpolation is well-composed. In [START_REF] Boutry | How to make nD functions well-composed in a self-dual way[END_REF], the authors have proposed a very simple method to get a self-dual interpolation, that makes sense when considering the tree of shapes of an image.

III. DESCRIPTION OF THE PROPOSED METHOD

In this section, we focus both on the proposed morphological hierarchical representation and how it can be used to segment text in images.

A. Method Overview

The method that we propose to segment text in natural images is very simple; put very shortly, text components are selected among the 0-crossing lines of the Laplace operator of the gray-level input image. Yet, the very "classical" scheme of considering the 0-crossings obtained with the linear operator as object contours does not work well in practice (see Figures 1(b) and 1(c)). So let us explain what the different steps of our method are, and let us give the reasons why their combination (depicted in Figure 4) is effective.

The four first steps aim at computing a hierarchical representation of the input image, and the final step is an example of how this hierarchical representation can serve to segment text and extract text lines.

Step 1. We first start by taking the luminance of the input color image. With the resulting gray-level image, we have lost color information but we observed in our experiments that it almost never negatively affects text retrieval.

Step 2. With a 11 × 11 square structuring element, we compute its morphological dilation δ ◻ and erosion ε ◻ to directly deduce two images. First we get the morphological gradient ∇ ◻ = δ ◻ -ε ◻ , which is a scalar thick gradient, used later to discard contours that are not enough contrasted. Second we get the morphological Laplace operator Fig. 5: The inclusion tree is the tree of shapes of the Laplacian sign image: positive and negative regions are respectively green and red nodes of the ToS, and 0-crossing regions are white nodes.

∆ ◻ = δ ◻ + ε ◻ -2 id.
The text character boundaries are expected to belong to the 0-crossing contours of this non-linear operator; actually they are, and their localization is precise (as shown later in Table I).

Step 3. We compute a particular interpolated image, ∆ wc ◻ , of the Laplacian image ∆ ◻ , having 4 times more pixels than the original. (We will see in Sec. III-D that this step can be emulated, so it is cost-free.) This resulting image is wellcomposed, meaning that the boundaries of every components of any threshold set are Jordan curves. Thus the 0-crossings (precisely the external 1D contours of the 0-crossings) are simple closed curved, so they cannot have the shape of a '8'. As a consequence, they are disjoint, and this set of curves can be organized in an inclusion tree. That contrasts with the 0-crossings depicted in Figure 1, where the Laplacian images are not well-composed; it is especially visible within the blue circles in Figures 1(c) and 1(e), where we cannot say what are the inclusion relationships between (white) regions.

Step 4. Due to the fact that ∆ wc ◻ is well-composed, the regions delimited by the 0-crossings can be labeled very efficiently (by the classical blob labeling algorithm), and their inclusion tree is built. In addition, many 0-crossings are discarded on the fly during the labeling, because they are not contrasted enough (we use ∇ ◻ ), or because they do no satisfy some geometrical criteria (when they are too small for instance). The resulting "tree + label image" are depicted on the bottom-right part of Figure 4. This 4th step can be seen as the computation of the tree of shapes of the "sign of the Laplacian" image, as depicted by Figure 5. This image, v = sign(∆ wc ◻ (u)), is a ternary-valued image (with pixels set to -1, 0, or 1). To compute its tree of shapes, we run the classical queue-based "blob labeling" algorithm, which is very efficient. (Note that actually we do not want regions representing null values in the final tree, so we group nodes corresponding to 0-crossings with their parent; it is displayed by the light colored backgrounds in Fig. 5

(b).)

Step 5 (application). Last we group components together to form text boxes. For that, we only consider the bottom of this tree (the leaves and sometimes their parent): for each component, we search spatially in the label image what are their left and right components to be grouped into a text box. In this step, we highly take advantage of the tree structure: it allows very easily to discard many regions as non-text, and to determine if a leaf region is a character hole or a plain character.

The key features of this method are the following: 1. It runs very fast since the processing chain is very simple and since all operations have a linear time complexity (see Sec. III-E); 2. The proposed method, based on the morphological Laplace operator, outperforms more "classical" component-based methods that select candidate regions for characters (see Sec. IV); 3. The fact that regions form an inclusion tree, thanks to the wellcomposedness property, allows for powerful decision taking when grouping regions into text boxes.

B. Computing the Hierarchical Representation (Step 4)

The algorithm of the labeling process and tree creation, Step 4 in Fig. 4, is depicted in Algo. 1. 'label' is the label image to compute, 'parent' is an array encoding the parenthood relationship of the inclusion tree (e.g., having parent(l 1 ) = l 2 means the region with label l 1 is included in the region with label l 2 ), Q is a queue of pixels, isContour is an auxiliary binary image, and is the current label.

We browse the pixels in raster scan order (main loop, line 4). When we reach an unlabeled pixel p, we follow the contour of the unlabeled region, which is a hole in the label image, thanks to the isContour image. This is performed in the CONTOURIZE routine, line 6. The routine CONTOURIZE computes on the fly the bounding box of the hole and the average of gradient's magnitude of its contour. If the bounding box is too tiny or if the gradient magnitude is very low (meaning respectively that a 0-crossing contour is due to noise or occurs in a flat region), we will not create a new node / a new label for this hole region. With p -1 being the pixel just before p in the raster scan order (p -1 is thus guaranteed to be labeled), the routine CONTOURIZE performs: ′ ← + 1 and parent( ′ ) ← label (p -1 ) if the hole region is a new region, otherwise ′ ← label (p -1 ) and this spurious region will be ignored (because merged with its parent). Eventually ′ is the label value to label the considered (yet unlabeled) hole region. For that, we initialize a queue-based propagation, line 7, and we proceed to the classical "blob labeling" algorithm, lines 8 to 13. The blob/region to be labeled is characterized by the connected set of pixels having the same Laplacian sign as p or being null (Cf. Fig. 5). During this propagation, we update the auxiliary isContour image (line 13) to memorize the contours of the holes included in this region. The leaves (and sometimes their parents) of the resulting tree are then grouped together to form text line candidates (Step 5 in Figure 4). We only consider roughly horizontal words, containing at least two characters. Thanks to the Laplacian 0-crossings inclusion, the characters of a same word belong to the same background; this implies that they have the same parent in the tree structure. As a consequence, the grouping process can be performed efficiently: the only candidate regions for characters to be grouped into text lines are siblings in the tree structure. Starting from each tree leaf, we thus use a classical search in the image space to group siblings (some additional geometric information such as region height and maximal inter-distance between regions are also used to control the grouping process). Note that we know when a leaf is a character hole, because both left and right neighbor regions are its grand-parent in the inclusion tree (the background region being the parent); we then consider its parent node (its background being the character). An illustration is given in Figure 6.

D. Space Optimization

A drawback of this method seems to be the need of multiplying by 4 the number of pixels (when computing the well-composed interpolation of the Laplacian image, and then proceeding to the labeling, and the final grouping). Actually we do not need to duplicate the number of pixels: we just can do as if there were an interpolation. Indeed we can emulate that the Laplacian image is well-composed, during the labeling and the contour browsing. Considering Fig. 4, it means that Step 3 is useless and that all the processing chain is performed on images having the same size as the input image.

E. Complexity Analysis

The morphological gradient and Laplacian rely on a dilation and erosion using a square structuring element, which can be efficiently implemented thanks to a 2-pass (horizontal then vertical) incremental (heap-based) process. In addition this [START_REF] Epshtein | Detecting text in natural scenes with stroke width transform[END_REF] 0.464192 0.8861 0.609232 0.505042 ER [START_REF] Neumann | Real-time lexicon-free scene text localization and recognition[END_REF] 0.613059 0.892023 0.629221 0.726689 TMMS [START_REF] Fabrizio | TextCatcher: A method to detect curved and challenging text in natural scenes[END_REF] 0.784568 0.7522 0.768043 0.791303 Our 0.636168 0.933058 0.756528 0.849754 local process is easily parallelizable, and eventually it has a linear time complexity w.r.t. the number of pixels. The blob labeling process (see Algo. 1) has also a linear time complexity: every pixels are only visited once with the main 'for' loop and the queue-based propagation, and browsing the 0-crossings contours is also limited by the number of pixels. Last the grouping process, dealing with very few nodes of the tree and browsing a few pixels of the label image, is trivially linear.

IV. EXPERIMENTAL RESULTS

A. Quantitative Results on Text Segmentation

We have evaluated the proposed method of text segmentation in the context of task 2 of Challenge 2 in ICDAR 2015 "Robust Reading" competition. The dataset contains 233 natural images with focused scene texts. The ground truth of text segmentation results is available. Some qualitative results are given by Figure 7; they include reverse-video, uneven illumination, fancy fonts, blur, and different text sizes.

We have compared our method with three popular methods for generating text candidate regions: Stroke Width Transform (SWT) [START_REF] Epshtein | Detecting text in natural scenes with stroke width transform[END_REF] with the implementation provided by https:// sites.google.com/site/roboticssaurav/strokewidthnokia, text detection based on Extremal Regions (ER) [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF], [START_REF] Neumann | Real-time lexicon-free scene text localization and recognition[END_REF] (implemented in OpenCV), and Toggle Mapping Morphological Segmentation (TMMS) [START_REF] Fabrizio | TextCatcher: A method to detect curved and challenging text in natural scenes[END_REF]. The first two methods are widely used as the first step of many state-of-the-art pipelines. For fair comparison, we compare the performance of text candidate region generation of the four methods, that is text segmentation, and we discard the rest of the pipeline (mainly false positive removal). For that, we only consider generated regions that touch the ground truth (GT) texts. We use the evaluation scheme proposed by [START_REF] Calarasanu | What is a good evaluation protocol for text localization systems? Concerns, arguments, comparisons and solutions[END_REF], [START_REF] Calarasanu | From text detection to text segmentation: a unified evaluation scheme[END_REF], based on the recall and precision scores in terms of pixels; we also compute a consistency value measuring how much ground-truth text components are split into several pieces. The results are given by Table I; our method achieves a competitive recall with a high precision. Figure 8 depicts in detail how each method behaves w.r.t. all the ground-truth texts in the dataset: the plots illustrate the distribution of the segmented text components at different coverage level (left) and accuracy level (right). The coverage (resp. accuracy) represents the percentage of the matched surface between the GT and a detection object with respect to the GT (resp. detection) surface; see [START_REF] Calarasanu | Using histogram representation and Earth Mover's Distance as an evaluation tool for text detection[END_REF] for details. One can see that our method covers the ground-truth texts at relatively high coverage levels (mostly distributed between 50% to 100%), which is not the case of the other methods.

B. Qualitative Interpretation of Results

Many methods extract objects thanks to what can be interpreted as "local thresholding". For instance, for Sauvola's binarization approach (see [START_REF] Lazzara | Efficient multiscale Sauvola's binarization[END_REF] for a multiscale version), the thresholds computed at pixel-level do not vary a lot for the same object (given than the window used to compute thresholds has to be large). Another examples are the MSER and ER approaches [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF], where objects come from the image level sets. As acknowledged in [START_REF] Bušta | FASText: Efficient unconstrained scene text detector[END_REF], there is only a partial match between the boundaries of actual objects and the contours of level sets (called level lines). Due to the presence of uneven illumination, these classical approaches and many others just fail to properly detect the object boundaries. Conversely, these boundaries belong to the 0-crossings of the morphological

C. Applying the Method to Document Binarization

The method proposed in this paper has been applied to binarize documents in the challenge #2 (Smartphone OCR) of "ICDAR 2015 Competition on Smartphone Document Capture and OCR (SmartDoc)" [START_REF] Burie | ICDAR2015 competition on smartphone document capture and OCR (SmartDoc)[END_REF]. We ranked 2nd in this competition among 8 contestants, with a character accuracy of 95.85% (note that the winner has taken advantage of the redundancy of documents in the test set to correct each individual document). Relying on the Laplace operator has turned out to be robust for the binarization of both blurred text and low-contrasted text. In addition, our method is self-dual since it naturally handles the same way the case of dark objects over bright background and the opposite case, as depicted in Figure 9.

V. CONCLUSION

In this paper we have presented a hierarchical representation of the image contents based on the inclusion of the 0-crossings of the morphological Laplace operator. Thanks to the wellcomposedness property, we guarantee that this tree-based representation exists, and we have given an algorithm with linear time complexity to compute this representation (from our first experiments with an ordinary computer, it runs in about 0.2s on a 1M Pixel image). We have explained how to rely on this representation to segment text lines in natural images, and we have shown that it competes with classical methods of text candidate extraction. We also have applied an about similar scheme to document image binarization, which has been used in the ICDAR 2015 SmartDoc competition. As a perspective, we intend to integrate our text segmentation approach in a text detection pipeline-thus including false positives detection-to get an end-to-end evaluation. Another perspective is to make the component grouping step be able to handle multi-oriented text, such as in [START_REF] Fabrizio | TextCatcher: A method to detect curved and challenging text in natural scenes[END_REF]. In addition we plan to study quantitatively the robustness of the morphological Laplace operator when involved in various applications.

  (a) Input u. (b) ∆ 4 (u) = 0. (c) LoG 17 (u) = 0. (d) ∆◻ 17 (u). (e) ∆◻ 17 (u) = 0. (f) ∆◻ 51 (u) = 0.

Fig. 1 :

 1 Fig. 1: Zero-crossing contours of different Laplace operators: (b) and (c) come from classical linear operators; (e) and (f) come from the morphological operators. On (d), the scalar morphological Laplacian is depicted with positive and negative values tinted resp. in green and red.

  Its tree of shapes.

Fig. 2 :

 2 Fig. 2: Representation of an image by its tree of shapes.

  A well-composed interpolation.

Fig. 3 :

 3 Fig. 3: Having a well-composed interpolation (right) of an image (left) ensures that level sets contours (depicted in black) are Jordan curves.

2 × 2

 22 block of pixels values (a, d)(c, b) should verify: intvl(a, b) ∩ intvl(c, d) ≠ ∅, where intvl(v, w) = min(v, w), max(v, w) .

  (a) ∆ wc ◻ (u).

  Tree S(v) with v = sign(∆ wc ◻ (u)).

1 6 (Algorithm 1 :

 61 LABELING(∆ wc ◻ , ∇◻) 2 for all p do label (p) ← 0, isContour (p) ← false 3 ← 0 4 for all p do 5 if label (p) ≠ 0 then continue; parent, ′ , ) ← CONTOURIZE( , p, ∇◻, isContour ); 7 label (p) ← ′ , Q.push(p); 8 while not Q.is empty() do 9 q ← Q.pop(); 10 for all n ∈ N (q) do 11 if label (n) = 0 and ∆ wc ◻ (p) × ∆ wc ◻ (n) ≥ 0 then 12 label (n) ← ′ , Q.push(n); 13 else isContour (n) ← true; 14 return (parent, label ) Blob labeling and tree computation.

  (a) Original image. (b) Morphological Laplacian. (c) Result of labeling. (d) Node selection and text boxes.

Fig. 6 :

 6 Fig.6: Illustration of the proposed method: mathematical morphology tools are contrast-invariant so we successfully deal with low-contrasted data (note that the Laplacian image (b) has been lightened to be readable).

  (a) Some results. (b) A case of failure.

Fig. 7 :

 7 Fig. 7: Qualitative results using "ICDAR 2015 Robust Reading" DB: input (left), labeling (middle), final boxes (right).

Fig. 8 :

 8 Fig.8: Evaluation based on coverage and accuracy[START_REF] Calarasanu | Using histogram representation and Earth Mover's Distance as an evaluation tool for text detection[END_REF].

  (a) Original image. (b) Self-dual binarization.

Fig. 9 :

 9 Fig. 9: Text segmentation with our method can be seen as a binarization technique, providing also reverse-video text.

TABLE I :

 I Text segmentation comparison.

	Method	Recall	Precision	F-score	Consistency
	SWT

ACKNOWLEDGMENT

The authors want to thank Jonathan Fabrizio and Ana Stefania Calarasanu for their help, and the reviewers for their comments.

This work has been conducted in the context of the MOBIDEM project, part of the "Systematic Paris-Region" and "Images & Network" Clusters (France). This project is partially funded by the French Government and its economic development agencies.


Anaël Grandjean
email: anael.grandjean@lirmm.fr

Constant acceleration theorem for extended von Neumann Neighbourhoods

We study 2-dimensional cellular automata as language recognizers. We are looking for closure properties, similar to the one existing in one dimension. Some results are already known for the most used neighbourhoods, however many problems remain open concerning more general neighbourhoods. In this paper we provide a construction to prove a constant acceleration theorem for extended von Neumann neighbourhoods. We then use this theorem and some classical tools to prove the equivalence of those neighbourhoods, considering the set of languages recognizable in real time.

Introduction

Cellular automata are deterministic dynamical models. Introduced in the 1940s by S. Ulam and J. von Neumann [START_REF] John Von Neumann | Theory of Self-Reproducing Automata[END_REF] to study self replication in complex systems they were rapidly considered as computation models and language recognizers [START_REF] Alvy | Real-time language recognition by one-dimensional cellular automata[END_REF]. Contrary to some other classical computation models that inherently work on words, they can be considered naturally in any dimension (the original cellular automaton studied by Ulam and von Neumann were 2-dimensional) and are therefore particularly well suited to recognize picture languages. Language recognition is performed by encoding the input in an initial configuration and studying the (deterministic) evolution of the automaton from that configuration. Time and space complexities can be defined in the usual way.

One-dimensional cellular automata have been widely studied as language recognizers, and especially concerning real-time and linear time recognition. Some of the most interesting results in this field have been several closure properties as in [START_REF] Poupet | Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods Theory of Computing Systems[END_REF][START_REF] Mazoyer | A linear speed-up theorem for cellular automata[END_REF][START_REF] Alvy | Real-time language recognition by one-dimensional cellular automata[END_REF]. This paper tries to expand two of those properties to 2-dimensional cellular automata.

The first theorem we present is a constant acceleration theorem for some specific set of neighbourhoods. Although such an acceleration is known in one dimension for all neighbourhoods, it was only known in two dimensions for the von Neumann and Moore neighborhoods. This result also extends the constant acceleration theorem for the von Neumann Neighbourhood, based upon a construction from V. Terrier. Althought some other proofs may exists, none is currently published.

The second theorem, which is a consequence of the first one, states the equivalence, with respect to real time recognition, of some neighbourhoods (the ones for which the first theorem is true). Althought in one dimension all complete neighbourhoods are known to be equivalent [START_REF] Poupet | Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods Theory of Computing Systems[END_REF], it has been shown by V. Terrier in [START_REF] Terrier | Two-dimensional cellular automata recognizer[END_REF] that at least two classes of complete neighborhoods exist in two dimensions.

1 Definitions

1.1 Cellular Automata Definition 1 (Cellular Automaton). A cellular automaton (CA) is a quadru- ple A = (d, Q, N , δ) where -d ∈ N is the dimension of the automaton ; -Q is a finite set whose elements are called states ; -N is a finite subset of Z d called neighbourhood of the automaton ; -δ : Q N → Q is the local transition function of the automaton. Definition 2 (Configuration). A d-dimensional configuration C over the set of states Q is a mapping from Z d to Q.
The elements of Z d will be referred to as cells and the set of all d-dimensional configurations over Q will be denoted as Conf d (Q).

Given a CA A = (d, Q, N , δ), a configuration C ∈ Conf d (Q) and a cell c ∈ Z d ,
∆(C) = Z d → Q c → δ(N C (c))
The action of the global transition rule makes A a dynamical system over the set Conf d (Q). Because of this dynamics, in the following we will identify the CA A with its global rule so that A(C) is the image of a configuration C by the action of the CA A. More generally A t (C) is the configuration resulting from applying t times the global rule of the automaton from the initial configuration C. Definition 4 (a-b-Neighbourhood).

We denote by a-b-Neighbourhood (shortly N a,b ), the following two-dimensional neighbourhood :

N a,b = {(x, y) ∈ Z 2 | b|x| + a|y| ≤ ab}
Note that such a neighbourhood is convex and symmetric with respect to the origin. For completeness reasons we also require a and b to be strictly positive. Furthermore, the neighbourhood N

Picture Recognition

From now on we will only consider 2-dimensional cellular automata (2DCA), and the set of cells will always be Z 2 . Definition 5 (Picture). For n, m ∈ N and Σ a finite alphabet, an (n, m)picture (picture of width n and height m) over Σ is a mapping

p : 0, n -1 × 0, m -1 → Σ Σ n,m
denotes the set of all (n, m)-pictures over Σ and Σ * , * = n,m∈N Σ n,m the set of all pictures over Σ. A picture language over Σ is a set of pictures over Σ.

Definition 6 (Picture Configuration). Given an (n, m)-picture p over Σ, we define the picture configuration associated to p with quiescent state q 0 / ∈ Σ as

C p,q0 :    Z 2 → Σ ∪ {q 0 } x, y → p(x, y) if (x, y) ∈ 0, n -1 × 0, m -1 q 0 otherwise
Definition 7 (Picture Recognizer). Given a picture language L over an alphabet Σ, we say that a

2DCA A = (2, Q, N , δ) such that Σ ⊆ Q recognizes L with quiescent state q 0 ∈ Q \ Σ and accepting states Q a ⊆ Q in time τ : N 2 → N if,
for any picture p (of size n × m), starting from the picture configuration C p,q0 at time 0, the origin cell of the automaton is in an accepting state at time τ (n, m) if and only if p ∈ L. Formally,

∀n, m ∈ N, ∀p ∈ Σ n,m , A τ (n,m) (C p,q0 )(0, 0) ∈ Q a ⇔ p ∈ L
We then say that the language L can be recognized in time τ (n, m) with neighbourhood N .

Since cellular automata work with a finite neighbourhood, the state of the origin cell at time t (after t actions of the global rule) only depends on the initial states on the cells in N t , where N 0 = {0} and for all n, N n+1 = {x + y, x ∈ N n , y ∈ N }. The real time function is informally defined as the smallest time such that the state of the origin may depend on all letters of the input : Definition 8 (Real Time). Given a neighbourhood N ⊂ Z d in d dimensions, the real time function τ N : N d → N associated to N is defined as

τ N (n 1 , n 2 , . . . , n d ) = min{t, 0, n 1 -1 × 0, n 2 -1 × . . . × 0, n d -1 ⊆ N t }
When considering the specific case of the 2-dimensional von Neumann neighbourhood, the real time is defined by τ NvN (n, m) = n + m -2. There is however a well known constant speed-up result : Proposition 1 (folklore). For any k ∈ N, any language that can be recognized in time (τ NvN + k) by a 2DCA working on the von Neumann neighbourhood can also be recognized in real time by a 2DCA working on the von Neumann neighbourhood.

So, it will be enough to prove that a language is recognized in time (n, m) → n + m + k for some constant k to prove that it is recognized in real time.

Main Result

Theorem 1 (constant acceleration). For any a,b and k positive integers, any language that can be recognized in time (τ N a,b + k) by a 2DCA working on N a,b can also be recognized in real time by a 2DCA working on the same neighbourhood.

Proof. To prove the theorem one only needs to be able to accelerate one step of the calculation (that is, recognize in real time any language recognized in real time plus one). We then only have to repeat the process a finite number of times.

As in the one dimensional case, the idea is to make each cell "guess" the state of some further cells, so that at real time, the origin cell guesses are correct, and allow it to perform one more step of computation.

Fix some language L and some automaton A recognizing this language in real time plus one step. This automaton works on the a-b-Neighbourhood N a,b . We will now construct an automaton A with the same neighbourhood, recognizing L in real time.

The potential initial configurations of both automata are the same, from now on we fix one initial configuration and explain what happens on the run starting from this configuration in A , depending on what happens in the run starting from this same configuration in A.

Let us introduce some notations : A(c, t) represents the state of the cell c at time t in the original automaton A. We denote as G all the following set :

G all = {(xa, yb) ∈ Z 2 1 < x + y ≤ 2; 0 ≤ x; 0 ≤ y; x ≤ y + 1; y ≤ x + 1}
This is a subset of the north east quarter of N 2 , depicted in green in Fig 3 .  Similarly we define G lef t and G bottom as follows, depicted in light blue in Fig 3 :

G lef t = {(xa, yb) ∈ Z 2 1 < x + y ≤ 2; 0 ≤ x; 0 ≤ y; x ≤ y + 1; y ≥ x + 1} G bottom = {(xa, yb) ∈ Z 2 1 < x + y ≤ 2; 0 ≤ x; 0 ≤ y; x ≥ y + 1; y ≤ x + 1} Fig. 3. A partition of N 2
Each cell c of the new automaton A will "contain" many states of cells of A. More formally the state set of A is a power of the state set of A. A cell c of A contains, at time t ≥ 1, the following informations :

-A(c, t) -A(c , t -1) for every c ∈ N (c).

g(c, c , t -1) for every c ∈ G all (c).

g(c, c , t -1) for every c ∈ G bottom (c) if c is on the bottom border of the input word. g(c, c , t -1) for every c ∈ G lef t (c) if c is on the left border of the imput word.

We call E(c) (extended neighbourhood) the set of cells c such that c holds either A(c , t) or g(c, c , t). Remark that E(0) is exactly the north east quarter of N 2 .

The state g(c, c , t) is some sort of guess, made by the cell c, of what could be A(c , t). For every cells c and c , g(c, c , 0) = #, the quescient state of A. The update rule of g(c) will depend on the available information for the cell c. The new state g(c, c , t + 1), is the result of applying the local rule of A on the neighbours of c , using the state of A when it is available to c, and a guess of another cell otherwise.

To better understand this update rule, we need to focus on what information is available for each cell of A during the computation. A cell c can "see" every information contained its neighbouring cells. This way, for example, at time t, a cell c have access to all A(c , t-1) for c ∈ N 2 (c), as each cell of its neighbourhood contain this information for each cell of its own neighbourhood. This way it is easy to update every state of A, directly using the local rule of A.

Remark that one cell can see several times the same information, as it is contained in more than one cell of its neighbourhood. As the information about the states of A(c, t) results from a direct simulation, all its occurences are coherent. On the contrary, guesses about one cell state can depend on which cell is making the guess. To avoid incoherence issues, a cell c will only use the information contained in the guesses of its leftmost and uppermost neighbours, and completely ignore all other guesses (including its own previous guesses).

Some quick math calculations shows that the neighbourhood of each cell in

E(c) is indeed contained in N 2 (c) ∪ E(c + (a, 0)) ∪ E(c + (0, b)), as depicted in Fig 4.
A cell whose state is # formally stays in this state, but is "read" as if its extended neighbourhood was filled with #.

This equation is not true for the cells on the left border and on the bottom border, those cells needs to use some guesses about cells outside the computation. However those cells will always remain in the quescient state, therefore no information is actually missing.

We will say that a cell is correct if all the g(c, c , t) in its extended neighbourhood are equal to A(c , t). After the first time step, all the cells of the upmost row and of the rightmost column are correct. Moreover all the cells with the top right corner cell in its neighbourhood are correct. As all the cells outside the computation also correct, we can note that each cell which is above or on the right of a correct cell is also correct. At time t + 1 a cell c is correct if both c + a and c + b are correct. This is also true for the cells on the borders, using the fact that every cell outside the border is in state #.

Because of the shape of the set of correct cells at time 1, it is easy to see that a time t, the set of correct cells will contain N -t ((n, m)) where n and m are respectively the length and height of the input.

Because of the shape of the neighbourhood, this cell is the farthest from the origin. Then, the real time is equal to the minimal t such that the origin cell is in N -t (n, m). Thus, at real time, denoted τ (n, m), the origin cell is correct, and therefore knows the state of every cell of its extended neighbourhood at time τ -1, in the automaton A. The extended neighbourhood of the origin consists of all the cells in N 2 (0) which are not in state #. This information is enough to compute the state of all cells in N ((0, 0)) at time τ in A. Then it is engouh information to compute the state of the origin cell at time τ + 1 in A.

The accepting states of A are all the "configurations" of the extended neighbourhood of the origin cell which lead to an acceptation in A at time τ + 1.

Theorem 2 (Equivalence of the a-b-Neighbourhoods). For any a, b, c, d positive integers, any language that can be recognized in real time by an automaton with N a,b can also be recognized in real time by an automaton with N c,d .

Proof. The proof of this theorem is based upon the two following lemmas : The first lemma is well known for one dimensional cellular automata, and is an easy corollary of the constant acceleration theorem. First note that the real time function for N and the one for N k are very similar. Indeed τ N k = τ N k . As an automaton A with neighbourhood N k can simulate k steps of computation of an automaton A with neighbourhood N in a single step, in real time it can simulate at least τ N steps of A, proving one inclusion.

The other inclusion needs the constant acceleration theorem. Indeed, an automaton A with neighbourhood N needs k steps to simulate one step of an automaton A with the neighbourhood N k . Thus it needs at most τ N + k steps to compute τ n k steps of A. Thanks to the first theorem of this paper, we can build another automaton with neighbourhood N recognizing the same language in real time, completing the proof.

In order to prove the second lemma, we will have to perform a compression of the input. Let A be an automaton recognizing L with neighbourhood N ka,b in real time. Once again the two neighbourhoods we consider have very similar real time :

τ N ka,b (n, m) = n ka + m b τ N a,b (n, m) = n a + m b Now consider the following neighbourhood : M = {(x, 0)| -ka ≤ x ≤ ka} ∪ {(0, y)| -b ≤ y ≤ b}
M have exactly the same convex hull as N ka,b , but is not convex. However thanks to Delacourt and Poupet [START_REF] Delacourt | Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-Convex Neighborhoods MFCS[END_REF] we know that there is an automaton A with neighbourhood M which recognizes L in time at most τ N ka,b + c for some constant c.

We will now build an automaton B which simulates A . Each cell of B will be able to store up to k states of A . First the automaton will perform a compression of the input, line by line, by a factor k. This takes ((k-1)n ka time steps. After the compression each cell of B contains k cells of A , and can simulate the computation of A for each of those cells without losing any time. In Fig 6 the automaton B is represented after a compression by factor 3. Each blue dot in a cell correspond to a cell of . Here, N 1,2 is the neighbourhood of B, depicted in red. N 3,2 is the neighbourhood of A. The green dots represents the neighbourhood of the blue dot circled in green. The four light green dots are the one which are in N 3,2 but not in M with respect to the circled dot. With similar ideas we can prove that N c,d is more powerful than N a,b , proving the announced result.

  we denote by N C (c) the neighbourhood of c in C : N C (c) : N → Q n → C(c + n) From the local transition function δ of a CA A = (d, Q, N , δ), we can define the global transition function of the automaton ∆ : Conf d (Q) → Conf d (Q) obtained by applying the local rule on all cells :

Definition 3 (

 3 Von Neumann and Moore Neighbourhoods). In d dimensions, the most commonly considered neighbourhoods are the von Neumann neighbourhood N vN = {c ∈ Z d , ||c|| 1 ≤ 1} and the Moore neighbourhood N M = {c ∈ Z d , ||c|| ∞ ≤ 1}.

Figure 1

 1 illustrates these two neighbourhoods in 2 dimensions.

Fig. 1 .

 1 Fig. 1. The von Neumann (left) and Moore (right) neighbourhoods in 2 dimensions.

Fig. 2 .

 2 Fig. 2. N2,1 (left) and N2,3 (right)

Fig. 4 .

 4 Fig. 4. Available and needed information for updating cells

Lemma 1 .

 1 For any a, b and k positive integers, the sets of languages recognized in real time with N a,b and with N k a,b are the same. We say that N a,b and N k a,bare equivalent with respect to the real time.

Fig. 5 .

 5 Fig. 5. correct cells at the first steps

Fig. 6 .

 6 Fig. 6. Available information after compression

  1,1 is exactly the von Neumann Neighbourhood. Some examples are depicted in Fig 2.


P N Dinh

Alain † -P H Quan
email: tquan@pmail.vnn.vn

‡ -D D Trong

SINC APPROXIMATION OF THE HEAT DISTRIBUTION ON THE BOUNDARY OF A TWO-DIMENSIONAL FINITE SLAB *

Keywords: heat equation, heat distribution, Sinc series, ill-posed problem, regularization Mathematics Subjects Classification 2000. 35K05, 31A25, 44A35

We consider the two-dimensional problem of recovering globally in time the heat distribution on the surface of a layer inside of a heat conducting body from two interior temperature measurements. The problem is ill-posed. The approximation function is represented by a two-dimensional Sinc series and the error estimate is given.

Introduction

In this paper, we consider the problem of recovering the heat distribution on the surface of a thin layer inside of a heat conducting body from transient temperature measurements. The problem is raised in many applications in Physics and Geology. In fact, in many physical situation (see, e.g. [B]) we cannot attach a temperature sensor at the surface of the body (for example, the skin of a missile). On the other hand, we can easily measure the temperature history at an interior point of the body. Hence, to get the heating history in the body, we want to use temperature measured in the interior of the body. In the simplest model, the heat-conducting body is assumed to have a constant conductivity and represented by the half-line x > 0 (see, e.g. [C, EM, LN, TV]),. While giving many useful results, this model is not suitable for the case of a body having a series of superposed layers, each of which has a constant conductivity.

Precisely, we shall consider the problem corresponding to a thin layer of the body represented by the strip R×(0, 2), say. Let u be the temperature in the strip. For the uniqueness of solution, we shall have to measure the temperature history at two interior lines R × {y = 1} and R × {y = 2}. From these measurements, we can identify uniquely the heating history inside of the layer (see, e.g., [B]). The problem is of finding the surface heat distribution u(x, 0, t) = v(x, t). In fact, despite uniqueness, the global solution in L 2 (R × R + ) is unstability and hence, in this point of view, a sort of regularization is in order.

As discussed in the latter paragraph, the main purpose of our paper is to present a regularization of the problem. Moreover, an effective way of approximating the heat distribution v is also worthy of considering. There are many methods for regularizing the equation (see [TA, B]). In the most common scheme (see, e.g., [Blackwell]), the computation is divided into two steps. In the first step, one considers the problem of finding the heat flux u y (x, 1, t) from the interior measurements u(x, 1, t), u(x, 2, t). The problem is classical and can be changed to the one of finding the solution of a convolution of Volterra type which can be solved in any finite time interval by the iteration (see, e.g., [F]). But even in the "classical" problem as mentioned in many documents, it is worthy of insisting that the problem is ill-posed if we consider the problem over the whole time interval R + with respect to the L 2 -norm and the literature on this way is very scarce. In the second step, one considers the "really" ill-posed problem which is of recovering the surface temperature history u(x, 0, t) from data u(x, 1, t), u y (x, 1, t). In the present paper, we can (and shall) regularize the function u(x, 0, t) directly from u(x, 1, t), u(x, 2, t) without using the flux function u y (x, 1, t). We emphasize that, using our method, we can unify two steps of the classical scheme and find simultaneously two functions u(x, 0, t) and u y (x, 1, t). However, our main purpose is of regularizing the surface temperature. Hence, we shall omit the problem of finding the interior heat flux u y (x, 1, t).

Moreover, using the method of truncated integration, one can approximate the Fourier transform of the solution by a function having a compact support in R 2 . Therefore, the solution can be represented by an expansion of two dimensional Sinc series (see [AGTV]). The Sinc method is based on the Cardinal functions

S(p, d)(z) = sin[(π(z -pd))/d] π(z -pd)/d , p ∈ Z, d > 0
which dates back to the works of many mathematicians (Bohr, de la Vallee Poussin, E. T. Whittaker, ...). The one dimensional version of the method is studied very clearly and completely in [S]. Some primary results related to the two dimensional Sinc approximation were given in [AGTV]. As is known, the Sinc series converges very rapidly at an incredible 0(e -cn 1/2 ) rate, where c > 0 and n is the dimension of approximation (see [S]). Hence, this method, which is new in our knowledge, is very effective.

The remainder of the present paper is divided into two sections. In Section 2 , we state precisely the problem, change it into an integral equation of convolution type, and state main results of our paper. In Section 3, we give the proof of main results.

Notations and main results

Consider the problem of determining the heat distribution

u(x, 0, t) = v(x, t) (1)
where u satisfies ∆u -

∂u ∂t = 0 x ∈ R, 0 < y < 2, t > 0, (2)
subject to the boundary conditions

u(x, 2, t) = g(x, t), x ∈ R, t > 0, (3) u(x, 1, t) = f (x, t), x ∈ R, t > 0, (4)
and the initial condition

u(x, y, 0) = 0, x ∈ R, 0 < y < 2. ( 5
)
Here f, g are given. We shall transform the problem (1)-( 5) into a convolution intergral equation.

Put

Γ(x, y, t, ξ, η, τ ) = 1 4π(t -τ ) exp - (x -ξ) 2 + (y -η) 2 4(t -τ ) (6)
and G(x, y, t, ξ, η, τ ) = Γ(x, y, t, ξ, η, τ ) -Γ(x, 4 -y, t, ξ, η, τ ). ( 7)

We have

G ξξ + G ηη + G τ = 0.
Integrating the identity

div(G∇u -u∇G) - ∂ ∂τ (uG) = 0 over the domain R × (1, 2) × (0, t -ε) and letting ε → 0, we have +∞ -∞ t 0 g(ξ, τ )G η (x, y, t, ξ, 2, τ )dξdτ + +∞ -∞ t 0 G(x, y, t, ξ, 1, τ )u y (ξ, 1, τ )dξdτ - +∞ -∞ t 0 f (ξ, τ )G η (x, y, t, ξ, 1, τ )dξdτ + u(x, y, t) = 0. Hence +∞ -∞ t 0 G(x, y, t, ξ, 1, τ )u y (ξ, 1, τ )dξdτ = -u(x, y, t) + +∞ -∞ t 0 G η (x, y, t, ξ, 1, τ )f (ξ, τ )dξdτ - +∞ -∞ t 0 g(ξ, τ )G η (x, y, t, ξ, 2, τ )dξdτ . (8)
Letting y → 1 + in (8), we have

+∞ -∞ t 0 1 2π(t -τ ) exp - (x -ξ) 2 4(t -τ ) - 1 2π(t -τ ) exp - (x -ξ) 2 + 4 4(t -τ ) u y (ξ, 1, τ )dξdτ = -f (x, t) - 1 2π +∞ -∞ t 0 1 (t -τ ) 2 exp - (x -ξ) 2 + 4 4(t -τ ) f (ξ, τ )dξdτ + 1 2π +∞ -∞ t 0 g(ξ, τ ) 1 (t -τ ) 2 exp - (x -ξ) 2 + 1 4(t -τ ) dξdτ . (9)
We put N (x, y, t, ξ, η, τ ) = Γ(x, y, t, ξ, η, τ ) -Γ(x, -y, t, ξ, η, τ )

Integrating the identity

div(N ∇u -u∇N ) - ∂ ∂τ (uN ) = 0 over the domain (-n, n) × (0, 1) × (0, t -ε) and letting n → ∞, ε → 0 +∞ -∞ t 0 N (x, y, t, ξ, 1, τ )u y (ξ, 1, τ )dξdτ - +∞ -∞ t 0 f (ξ, τ )N η (x, y, t, ξ, 1, τ )dξdτ + +∞ -∞ t 0 v(ξ, τ )N η (x, y, t, ξ, 0, τ )dξdτ -u(x, y, t) = 0. ( 10
)
Letting y → 1 -, the identity (10) becomes

1 2π +∞ -∞ t 0 1 t -τ exp - (x -ξ) 2 4(t -τ ) -exp - (x -ξ) 2 + 4 4(t -τ ) u y (ξ, 1, τ )dξdτ - 1 2π +∞ -∞ t 0 f (ξ, τ ) 1 (t -τ ) 2 exp - (x -ξ) 2 + 4 4(t -τ ) dξdτ + 1 2π +∞ -∞ t 0 1 (t -τ ) 2 exp - (x -ξ) 2 + 1 4(t -τ ) v(ξ, τ )dξdτ -3f (x, t) = 0 (11)
From ( 9) and ( 11), we have the main convolution equation

- 1 π +∞ -∞ t 0 1 (t -τ ) 2 exp - (x -ξ) 2 + 4 4(t -τ ) f (ξ, τ )dξdτ + 1 2π +∞ -∞ t 0 g(ξ, τ ) 1 (t -τ ) 2 exp - (x -ξ) 2 + 1 4(t -τ ) dξdτ + 1 2π +∞ -∞ t 0 1 (t -τ ) 2 exp - (x -ξ) 2 + 1 4(t -τ ) v(ξ, τ )dξdτ -4f (x, t) = 0
which can be rewritten as

S * v(x, t) = 2R * f (x, t) -S * g(x, t) + 4f (x, t) (12)
where we define that v(x, t) = f (x, t) = g(x, t) = 0 as t < 0,

R(x, t) = 1 t 2 exp -x 2 +4 4t (x, t) ∈ R × [0, +∞) 0 (x, t) ∈ R × (-∞, 0) and S(x, t) = 1 t 2 exp -x 2 +1 4t (x, t) ∈ R × [0, +∞) 0 (x, t) ∈ R × (-∞, 0) Put F (x, t) = 2R * f (x, t) -S * g(x, t) + 4f (x, t).
Taking the Fourier-transform of (12), we get

Ŝ(z, r)v(z, r) = F (z, r) where Ŝ(z, r) = 1 2π +∞ -∞ +∞ -∞ S(z, r)e -i(xz+tr) dxdt = 2e -1 √ 2 √ √ z 4 +r 2 +z 2 cos 1 √ 2 z 4 + r 2 -z 2 -isgn(r) sin 1 √ 2 z 4 + r 2 -z 2 and Ŝ(z, r) = 2e -1 √ 2 √ √ z 4 +r 2 +z 2 .
We have

Theorem 1

Let γ ∈ (0, 2) and ε ∈ 0, e

-3 γ . Assume that v 0 ∈ L 2 (R 2
) is the (unique) solution of ( 12) corresponding to the exact data

f 0 , g 0 ∈ L 2 (R 2 ) and that f, g ∈ L 2 (R 2 ) are measured data satisfying f -f 0 2 ≤ ε and g -g 0 2 ≤ ε where . 2 is the L 2 (R 2 )-norm.
Then we can construct from g, f a function

v ε ∈ L 2 such that v ε -v 0 2 ≤ Cε 2-γ + η(ε)
where C is constant and η(ε) → 0 as ε ↓ 0.

Moreover, if we assume in addition that

v 0 ∈ H m (R 2 ) ∩ L 1 (R 2 ), m > 0 and 0 < ε < min{e -e 2 , e -4m 2 } then v ε -v 0 2 < D ln 1 ε -m
where D > 0 depends on v 0 .

Theorem 2

With v ε as in theorem 1, we have

v ε (x, t) = +∞ n=-∞ |m|≤|n| v ε mπ a ε , nπ a ε S(m, π/a ε )(x)S(n, π/a ε )(t)
where

S(p, d)(z) = sin[π(z -pd)/d] π(z -pd)/d , p ∈ Z, d > 0.

Proofs

Proof of theorem 1

We put

F (x, t) = 2R * f (x, t) -S * g(x, t) + 4f (x, t)
and

F 0 (x, t) = 2R * f 0 (x, t) -S * g 0 (x, t) + 4f 0 (x, t) then F -F0 2 = F -F 0 2 ≤ (4 + 2 R 1 ) f -f 0 2 + S 1 g -g 0 2 ≤ (4 + 2 R 1 + S 1 ) ε. Put v ε (x, t) = 1 2π Dε F (z, r) Ŝ(z, r) e i(xz+tr) dzdr (13)
where

D ε = {(z, r)/ |z| ≤ b ε and |r| ≤ b 2 ε with b ε = 1 √ 2 √ √ 2+1 ln 4 ε γ .
We have xz+tr) dzdr

v ε -v 0 2 2 = vε -v0 2 2 = Dε F (z, r) -F0 (z, r) Ŝ(z, r) 2 dzdr + R 2 \Dε |v 0 (z, r)| 2 dzdr ≤ ε 2-γ (4 + 2 R 1 + S 1 ) 2 + R 2 \Dε |v 0 (z, r)| 2 dzdr If we put η(ε) = R 2 \Dε |v 0 (z, r)| 2 dzdr then η(ε) → 0 as ε ↓ 0. Now, we assume v 0 ∈ H m (R 2 ), m > 0, put a ε = √ 2 √ 2 + 1 ln 1/ε ln m (1/ε) > 1 Q ε = [-a ε , a ε ] × [-a ε , a ε ] and v ε (x, t) = 1 2π Qε F (z, r) Ŝ(z, r) e i(
We have

v ε -v 0 2 2 = Qε F (z, r) -F0 (z, r) 2 Ŝ(z, r) 2 dzdr + R 2 \Qε |v 0 (z, r)| 2 dzdr ≤ 4ε 2 (4 + 2 R 1 + S 1 ) 2 e √ 2 √ √ 2+1aε + R 2 \Qε (z 2 + r 2 ) m |v 0 (z, r)| 2 (z 2 + r 2 ) m dzdr ≤ C 1 ε 2 e √ 2 √ √ 2+1aε + 1 (2a 2 ε ) m
where

C 1 = max 4 (4 + 2 R 1 + S 1 ) 2 , (z 2 + r 2 ) m/2 v0 (z, r) 2 2 2 m
This implies that

v ε -v 0 2 2 ≤ C 1   ε 2 1/ε ln m (1/ε) 2 + 1 ln 2m 1/ε ln m (1/ε)   ≤ C 1   1 ln 2m (1/ε) + 1 ln 2m 1/ε ln m (1/ε)   ≤ C 1 1 ln 2m (1/ε) + 2 m ln 2m (1/ε) = D 2 1 ln 2m (1/ε) where D = C 1 (1 + 2 m ).
This completes the proof.

Proof of theorem 2

We have

supp vε ⊂ D ε ⊂ [-a ε , a ε ] × [-a ε , a ε ].
As in [AGLT], p.121, we have theorem 2. This completes the proof.

Numerical results

We present some results of numerical comparison of the regularized representation of the solution given by theorem 2 and the corresponding exact solution of the problem.

Let the problem ∆u -∂u ∂t = 0, (x, y) ∈ R × (0, 2), t > 0 ( 14)

u(x, 1, t) = 1 t e -x 2 -1 4t ; u(x, 2, t) = 1 t e -x 2 -4 4t ; u(x, y, 0) = 0 (15) whose the unknown is v(x, t) = u(x, 0, t), x ≥ x 0 > 0, t > 0 (16)
The exact solution of this problem is

v(x, t) = 1 t e -x 2 4t .
The approximated solution is calculated from the expansion of two-dimensional Sinc series given by theorem 2 associated to formula (13) in which

F = 4 e - √ r 2 +z 4 √ r 2 + z 4 , Ŝ = 2e - √ r 2 +z 4
Thus we have

F -F0 L 2 (R 2 ) = ε
which is a perturbation similar to the one operated on the two given functions f and g.

With ε = 1 50 , N = 50 (the size of the double series) and for (x, t) ∈ [0.25, 1.3] × [0, 4] we have drawn the corresponding approximate surface solution (x, t) -→ v ε (x, t) in Fig. 1.

To calculate the double integral in (10) we have used the rectangle rule which gives good accuracy if one integrates on the interval [ε, 1/ε] × [ε, 1/ε]. The time of calculus with a good computer is very long: 2 hours for 900 points M = (x, t) ∈ [0.25, 1.3] × [0, 4]. It is the reason for which we are limited ourselves to a relatively small size of the double series (N = 20). For comparison in Fig. 2 we have drawn the exact solution (x, t) -→ v(x, t).

  Fig.1: regularized solution of the problem (14), (15)