François Tilmant

F Bourgin

A.-L Véron

F Rousset

J.-M Willemet

D François

M Le Lay

J.-P Vergnes

C Perrin

C Magand

M Morel

IAHS 2022 Scientific Assembly

• Operational phase (since 2015)

Materials and methods

• Catchments

• 464 catchments for 33 operational users -including 10 catchments in La Réunion Island (oversea)

• Almost 1000 catchments for nation-wide outlook (from 5 to 110 000 km²)

• Limited human influences • Forecast meteorological scenario

• Historic climatic data (SAFRAN reanalysis, more than 60 members, to generate ensemble streamflow prediction -ESP)

• 90-day lead time

• ECMWF forecasts processed by Météo-France (51 members)

• 15-day lead time • Computation time (1000 catchments) : 25 min.

• Text files and summary PDF sheets

Visualisation platform

Link to PDF sheets Probability to be under threshold

Some results

• MAM7 : mean annual minimum for 7 days

Conclusion and perspectives

• PREMHYCE : an operational tool for low-flow forecasting

• 5 hydrogical models + simple multi-model approach

• Real-time update of hydroclimatic database

• Daily forecasts for almost 1000 catchments using ECMWF and ESP scenario

• Dynamic visualisation platform

• Good estimation of mean annual minimum for 7 days

•

  Water uses affected by water shortages in rivers • Climate change: perspectives of more severe low flows • Lack of forecasting tool at national scale Source : Propluvia -http://propluvia.developpement-durable.gouv.fr/ 7th Sept. 2021 PREMHYCE project (low-flow forecasting using hydrological models, comparison, evaluation) • Research project (2011 -2014) • Comparison of hydrological models for low-flow forecasting • Evaluation of their capacity to anticipate low-flow periods (magnitude and maximum lead time)

  14-day ahead forecast issued on the 1 st of June using ECMWF scenario 02/06/2022 IAHS 2022 Scientific Assembly, Montpellier

Perspectives••

  Tool to evaluate model calibration (visualisation, criteria…) Seamless meteorological forecasts (from one day to several months) • Human influences • Uncertainties quantification • CIPRHES research project • 2021 -2025 • Funded by the French national research agency (ANR) • Site web : https://www6.inrae.fr/ciprhes -Twitter : @ACiprhes 02/06/2022 IAHS 2022 Scientific Assembly, Montpellier Perspectives • Related communications during IAHS 2022 Scientific Assembly : Seamless meteorological forecast production and evaluation towards hydrological decision-making in France : CIPRHES project Talardia Gbangou & al. Low flow characterization and forecasting in a non-stationary context Hajar El Khalfi & al. (Poster) Integrated chain for the hydrometeorological forecasting of low flows and droughts in France. The CIPRHES project Charles Perrin & al. (Poster) 14The CIPRHES project is funded by the French National Research Agency (grant ANR-20-CE04-0009-03). The PREMHYCE platform receives funds from the French Biodiversity Agency (OFB) and the Ministry for ecology(MTE)

ANNEXES

Materials and methods

•

  At administrative department scale:

		•	1-month forecast lead time (ESP)
		•	Update every month
	02/06/2022	IAHS 2022 Scientific Assembly, Montpellier

Context

• Recurrent droughts on France

Some results

• L5101810 -Gartempe River at Folles (567 km²) • Mean annual streamflow: 7.9 m 3 /s


Alassane Sidibe
email: alassane.sidibe@laas.fr

Mohamed Abo Kassem
email: mohamed.abokassem@laas.fr

Julien Dachy
email: julien.dachy@uwinloc.com

Alexandru Takacs
email: alexandru.takacs@laas.fr

Autonomous and Battery-Free Wireless Tag combining UWB and BLE Technology

Keywords: Energy harvesting, Wireless power transmission, sensors, Ultra-wideband technology, Bluetooth low energy, Localisation, UHF antennas

This paper presents a multifunctional, battery-free tag combining Bluetooth Low Energy (BLE) and Ultra-Wideband (UWB) technology powered by the far-field wireless power transmission technique. The proposed tag, with a size of 9 x 8 cm², can be used for asset tracking via UWB at a center frequency of 4 GHz or for wireless temperature and humidity monitoring via BLE at 2.45 GHz. The tag is powered by a highly efficient radiofrequency (RF) energy harvesting (EH) solution at 868 MHz. The proposed solution has been optimised for low power consumption of 5-15 µJ (for a single UWB transmission) and can provide reliable performance in terms of data sensing and geolocation at a low ambient power density. The electronic module that includes the features of the energy harvester (rectifier) and the UWB transceiver was previously developed by Uwinloc. Simulation results for both antennas (UWB and RF EH) were presented. The transmission rate in BLE and UWB configuration was also evaluated as a function of the EIRP power level.

I. INTRODUCTION

The development of low-power wireless communication technologies has increased the use of the Internet of Things (IoT). In addition, we are faced with the need for monitoring and having the continuous position of a large volume of assets. Solutions are proposed to solve indoor location problems as presented in [START_REF]Summary of available indoor location techniques -Google Scholar[END_REF]. Ultra-Wideband (UWB) technology outperformed the current technologies used for geolocation (e.g. Bluetooth, WIFI and GPS [START_REF]ultrawideband.pdf[END_REF]). It has the advantages of presenting a high-ranging accuracy, robustness to multipath effects and high refresh rates for real-time localisation, and is becoming a potential technology for daily life applications [START_REF] Feng | A human-tracking robot using ultra wideband technology[END_REF], [START_REF] Mokhtari | Non-wearable UWB sensor for human identification in smart home[END_REF]. It can also cover space applications in the tracking of floating objects inside space stations [START_REF] Dardari | An ultra-wideband battery-less positioning system for space applications[END_REF].

For long-range data transmission and low power consumption, BLE is the most suitable technology for sensorbased IoT applications [START_REF]Bluetooth Technology Overview[END_REF]. However, most devices are battery operated and may sometimes deal with a limited lifetime and regular maintenance for battery replacement. Thus, for a longer lifetime, it may be necessary to harvest the energy by using farfield Wireless Power Transmission (WPT) [START_REF] Visser | Far-Field Wireless Power Transfer for IoT Sensors[END_REF].

Recent research activities have enabled the development of a battery-free system for sensing and data communication as in [START_REF] Rosa | An Energy-Autonomous Wireless Sensor with Simultaneous Energy Harvesting and Ambient Light Sensing[END_REF] for light-sensing through Bluetooth Low Energy (BLE) protocol. Other activities are more focused on finding a hybrid solution UWB/BLE tag for tracking elderly persons but is battery-powered [START_REF] Kolakowski | UWB/BLE tracking system for elderly people monitoring[END_REF].

The work in this paper is part of the needs of Uwinloc company which develops and commercialises an indoor location solution using a battery-free tag [START_REF]UWINLOC | New Indoor Location System for assets tracking[END_REF]. The commercialised tag is wirelessly powered by electromagnetic (EM) waves radiated by a Radiofrequency Identification (RFID) source at 868 MHz. For an accurate and reliable location, the tag emits a signal using UWB technology at centre frequency of 4 GHz.

To the authors' best knowledge, this paper proposes the first battery-free UWB/BLE tag with sensing (temperature & humidity) and localisation capabilities.

II. ARCHITECTURE AND DESIGN OF THE PROPOSED TAG PROTOTYPE

The tag developed consists of a combination of a geolocation module (GM), enabling RF energy harvesting and UWB transmission for accurate location, a temperature/humidity sensor, and a BLE transceiver. It is powered wirelessly by a far-field WPT and uses a Power Management Unit (PMU) to boost, store (in a capacitor) and manage the available power from the harvester as seen in Fig. 1. The proposed solution has been prototyped on a 1.55 mm thick FR-4 substrate. Thanks to the jumper (J1), different combinations are possible to allow multiple functionalities of the tag:

(i) The use of the tag for geolocation only in UWB mode. In this mode, the harvested power (Pout) obtained at the output pin of the harvester is connected (by using the jumpers J1) to the input pin (Vcc) of the GM and other chips are disconnected. Humidity and temperature sensing are also possible by supplying the sensor with the right combination of jumper J1.

This first developed board does not yet allow simultaneously the geolocation through UWB and the BLE sensing. J2 is used for I2C communication either by the GM or by the BLE System on Chip (SoC). (ii) The use of the tag for temperature and humidity monitoring through BLE communication. The harvested DC power is directly managed by the PMU and is stored in the capacitor. The BLE transceiver and active sensors are then supplied when there is sufficient energy available in the capacitor. The right combination on J1 allows this configuration.

A. Bluetooth Low Energy sensing and communication

For data transmission, we opted for the ultra-low-power BLE SoC from NXP [START_REF]QN908x: Ultra-Low-Power Bluetooth Low Energy System on Chip (SoC) Solution | NXP Semiconductors[END_REF] and a conventional meandered Planar Inverted-F Antenna (PIFA) designed at 2.4 GHz as suggested in the application note [START_REF]Compact Planar Antennas for 2.4 GHz Communication[END_REF]. Knowing that the instantaneous power available from the harvester is not sufficient to supply the BLE transceiver and active sensors, we decided to use a storage capacitor of 220 µF and the BQ25570 as low-power PMU (its minimum input DC power is around 15 µW for 100 µF according to the datasheet) [START_REF]BQ25570 datasheet | TI.com[END_REF]. Its DC output voltage is chosen to 1.9 V to achieve the best compromise for low power consumption by the BLE transceiver and sensors. To save energy, the BLE transceiver is programmed to operate as a transmitter (broadcaster) only, sending the measured temperature and humidity data in advertising (Adv.) mode. A paper has examined the packed collision for BLE advertising mode [START_REF] Ghamari | Detailed examination of a packet collision model for Bluetooth Low Energy advertising mode[END_REF]. The probability of packet collisions can be reduced by increasing the advertising time and number of packets at the expense of increasing the energy consumption. We found out a trade-off by sending 4 advertising events with an interval of 250 ms. Each advertising event is composed of 3 advertising packets over the 3 allocated channels (37, 38, and 39). The BLE advertisement profile can be obtained thanks to the QN9080 NPX development board via the power measurement tool of MCUXpresso IDE software as seen in Fig. 2.

The broadcasting phase begins from a sleep state with an inrush current followed by the initialisation and measurement of data and ends with a function (stop Adv). This function stops the timer used to periodic advertising after 4 times and also forces the discharge of the storage capacitor for another cycle.

The packets are sent to the observer which is a QN9080 NPX development board configured in observer mode [START_REF]QN9080SIP Development Kit[END_REF]. An integrated low-power temperature and humidity sensor HDC2080 is chosen from Texas Instrument (TI) [START_REF]HDC2080 datasheet[END_REF]. The operation of the sensor and the BLE SoC requires an energy consumption of about 756 µJ for 3 advertising events and 942 µJ for the broadcasting phase. The PMU is configured to have a minimum and maximum DC voltage thresholds at 1.97 V and 3.55 V, respectively. The storage capacitor (Cstorage), EEEFK0J221P from Panasonic was carefully chosen to be 220 µF, to store the sufficient energy for the active components and to allow a low leakage current [START_REF]EEEFK0J221P -Aluminum Electrolytic Capacitors (Surface Mount Type) -Aluminum Electrolytic Capacitors -Industrial Devices & Solutions -Panasonic[END_REF]. Thus, the maximum energy stored by the capacitor is about 1.39 mJ during the first charge (cold start phase) from an empty state (Vstorage = 0 V) to maximum voltage allowed by the PMU (Vstorage = 3.55 V) and 960 µJ during each subsequent recharge (before each sensing and data transmission). During these recharges, the minimum voltage allowed at the output of the capacitor before the advertising stop is set at 1.97 V.

B. Harvester and Ultra-Wideband Module

The battery-free geolocation module developed by Uwinloc company, allows the real-time tracking of assets.

The GM was developed to allow two differential inputs for the energy harvesting features. One is used for the proposed solution and the other is connected to an SMA connector for additional experimentation (not reported in this paper). The harvester is based on Greinacher doubler topology optimised for low-power density available from a dedicated RF energy source operating in the Industrial Scientific Medical (ISM) frequency band at 868 MHz. To achieve this, the power consumption of the GM module has been significantly reduced by minimising the power required by the microcontroller, the transmitter as well as the leakage current of the first storage capacitor (60 µF included in the harvester block, see Fig. 1b) for UWB operation. More details about the energy harvesting circuit can be found in the patent [START_REF] Uspto | Radio-frequency Energy Harvesting Circuit And Communication Device Integrating Such A Radio-frequency Energy Harvesting Circuit Patent Application[END_REF]. The GM needs about 5 to 10 µJ for a single UWB transmission. Once enough energy is stored, the tag transmits an ultra-wideband pulse through the UWB antenna to UWB beacons (not presented in this paper). The 3-Dimensional (3D) position of the tag is accurately computed thanks to triangulation algorithm.

The design of the antenna is particularly important to achieve the best compromise in terms of high sensitivity at low power density to be received, UWB transmission range, and accuracy for localisation. To avoid additional lumped components and thus insertion losses, UWB and Ultra High Frequency (UHF) antennas have been designed to have an impedance that is the complex conjugate of the input impedance of the UWB transmitter (25 -j • 9 Ω) and harvester (30 -j • 250 Ω). The UHF antenna (used for energy receiving) consists of a modified folded dipole antenna based on a T-match structure at 868 MHz. The high value of the imaginary part of the input impedance of GM is compensated by the Coplanar Wave Guided Grounded (CPWG) coupled transmission lines. The maximum simulated gain at the desired frequency is around +1.13 dBm for the theta angle equal to 90° in the YoZ plane (Phi = 90°) which will correspond to the horizontal position (H-pos) for the experiments. The vertical position (Vpos) will also correspond to the orientation in which the antenna has a gain of 0 dBi at theta equal to 0° in the YoZ plan as presented in Fig. 2.

The UWB antenna is based on a novel modified loop antenna to have a wideband behavior (Fig. 2 (a)). However, the presence of the UHF antenna and the wider ground plane, have modified the radiation pattern to be more directional in a certain direction. The two crossed arms at the corner of the loop are used to improve the radiation pattern of the antenna. According to the simulation, it has a maximum gain of +3.8 dBi at 4 GHz.

III. EXPERIMENTAL RESULTS

A. Bluetooth Low Energy Performances

In this part, the tag was configured to operate with the harvester, PMU, sensors, and the BLE SoC. The prototyped tag (operating in BLE mode) was tested in an anechoic chamber with a dedicated RF source composed of a transmitting patch antenna (placed at a distance d about 2 meters from the tag under test) connected to an RF signal generator (Anritsu MG3694B) through a cable to provide the power PRF at the frequency of 868 MHz. The losses due to the cable were accurately measured using a power meter and the average value is estimated to be -0.5 dB. The measurement setup is shown in Fig. 4. Prior to the measurements, all the capacitors are manually discharged to perform an accurate measurement of the time during the cold start phase. The BLE receiver operates as observer/listening device and is connected to a laptop. The QN9080 development kit is used to achieve this function. Next, the emission rate (i.e., the time elapsed between two consecutive temperature/humidity measurements sent by the battery-less tag through the advertising channels during the broadcasting phase) is evaluated by doing the time difference between each broadcasting phase. The time required for the cold start mode and the average emission rate as a function of the Effective Isotropic Radiated Power (EIRP) power of the RF source (placed at 2 meters from the tag) are shown in Fig. 5. Knowing that the measurement was operated in an anechoic chamber without any reflection, the Friis formula in (1) enables the calculation of the received power at the output of the UHF antenna.

 𝑃 ( ) = 𝑃 + 𝐺 + 𝐺 + 20 • log • •  
Since the transmitted power is greater than +23.5 dBm EIRP (corresponding to an estimated received power of -12.65 dBm at the input of the harvester) the cold start time is less than 28 minutes. By extrapolating with the formula (1), this result for a maximum EIRP power of +33 dBm, it is possible to estimate the maximum range around 6 meters for an average equivalent emission rate of 1246 seconds.

B. Ultra-Wideband Performances

The prototyped tag is now configured to work with the GM only for preliminary results. The evaluation of the emission rate was performed under the same conditions as the BLE part with the setup shown in Fig. 4, but the BLE receiver is replaced by a UWB beacon. In this case, two distinct positions of the tag were chosen. The horizontal position (H-pos) corresponds to the one used in the BLE tests and the vertical (V-pos) corresponds to the orientation in which the tag is placed vertically in front of the transmitting antenna. According to the simulation, the UHF antenna has less gain in the V-pos than in the H-pos. The maximum emission rate allowed for a given EIRP power was set at about 10 minutes (Fig. 6) to allow fast monitoring of the evolution of the tag location/position. Comparing the emission rate at each position, the time difference (tag in H-pos versus tag in V-pos) is larger at low power due to the nonlinearity of the harvester and the losses. By using the formula (1), we can estimate that an UWB emission is possible as far as the received RF power at the input of the rectifier is higher than -20 dBm. The UHF antenna of the tag at 868 MHz has a simulated gain of +1.13 dBi (in H-Pos) and the RF source with an EIRP of +18 dBm was located at 2 m far away from tag. Once UWB communication capability between tag and beacon is evaluated inside an anechoic chamber we have performed an experiment to evaluate the UWB localisation performances in a real scenario. For this purpose, an indoor test was conducted in a 300 m² test warehouse containing multiple obstructions from Uwinloc company. The configuration of the test area and the number of beacons are company specific and have not been adapted for the test in this paper. A detail about the method and device for the detection of the UWB pulse is presented in [START_REF] Uspto | Method And Device For The Detection Of A Pulse Of A Signal Patent Application[END_REF]. Two prototyped tags were placed separately in the test area as seen in Fig. 7. Energy sources were configured respecting the ESTI standard [START_REF]Electromagnetic compatibility and Radio spectrum Matters (ERM); Short Range Devices (SRD) intended for operation in the bands 865 MHz to 868 MHz and 915 MHz to 921 MHz; Guidelines for the installation and commissioning of Radio Position of beacons Tag position (a) (b) Frequency Identification (RFID) equipment at UHF', iTeh Standards Store[END_REF] with the continuous wave (CW) at the RFID frequency band with a power levels at 2 W. The beacons enabling to receive the UWB signal are placed in the corners and the facades of the test area at a height of 5-6 meters (whose coordinates are known) as shown in Fig. 8 (a). Among the 13 beacons configured, 11 of them have received the UWB signal. The location is then calculated by an algorithm to display the position on the software graphic interface developed by Uwinloc (Fig. 8 (b)).

This accuracy depends on the tag position in relation to the location of the beacons. Based on the tests available the date of submission, the position accuracy is lower than 1 m and this is strongly dependent on the tag position and orientation. The realtime position of the tags is obtained on the map by filtering its unique identification via the user interface. Works are in progress to evaluate the performance of the tag in a harsh environment by embedding it in a concrete beam and to also implement the sensing capability in UWB mode. IV. CONCLUSION This paper has presented for the first time a unique solution of a battery-free multifunction tag combining geolocation in UWB mode and wireless sensing in BLE mode. The prototyped tag is based on an electronic module developed by Uwinloc Company that enables RF EH and UWB transmission. The design has included UHF antenna at 868 MHz and UWB antenna at 4 GHz with a maximum simulated gain of +1.13 dBi and +3.8 dBi, respectively. The prototyped tag was first configured in BLE mode with sensors to evaluate its performance. As a function of the EIRP of the RF source, the measured cold start time was between 80 seconds (EIRP = +32.5 dBm) and 28 minutes (EIRP = +23.5 dBm) while the periodicity of sensing (that is identical with the BLE emission rate in advertising mode) was between 44 seconds (EIRP = +32.5 dBm) and 21 minutes (EIRP= +23.5 dBm). In UWB mode, the average emission rate was measured, and the tag was placed in a 300 m² indoor test area to have a preliminary estimation of the location precision. As confirmed by the experimental results, the location accuracy is lower than 1 m and strongly dependent of the tag position and the obstructions presented in the test area.

Fig. 1 .

 1 Fig. 1. (a) Architecture of the battery-free UWB-BLE tag; (b) Photo of prototyped tag.

Fig. 2 .

 2 Fig. 2. Current consumption of the tag configured in BLE mode: the average value (red) and the evolution as function of the time of the current (blue) during the broadcasting time.

Fig. 3 .

 3 Fig. 3. Antenna design and simulation of the tag: (a) Proposed design of the UWB antenna; (b) 3D Radiation pattern of the UWB antenna at 4 GHz; (c) Proposed design of the UHF antenna; (d) 3D Radiation pattern of the UHF antenna at 868 MHz.

Fig. 4 .Fig. 5 .

 45 Fig. 4. BLE measurement setup of the tag in an anechoic chamber.

Fig. 6 .

 6 Fig. 6. Average emission rate of the tag in localisation mode without sensor.

Fig. 7 .

 7 Fig. 7. Geolocation setup of the tags in the 300 m² test area. Thirteen beacons (only six are visible here) and two tags (placed at various position) have been used.

Fig. 8 .

 8 Fig. 8. (a) Mapping of the geolocation tag in the test area: each beacon (fixed position) is represented by its unique identification. (b) The position of the geolocated tag: only one tag was shown inside the overall volume of the test area (1800 m 3 ).


Cassandra Potier Watkins
email: cassandra.potier-watkins@cea.fr

Olivier Dehaene

Stanislas Dehaene

Stanislas Dehaene Automatic

Network Seiji

Eva Millán

Amy Ogan

Peter Hastings

Bruce Mclaren

Automatic Construction of a Phonics Curriculum for Reading Education Using the Transformer Neural Network

Keywords: phonics instruction, g2p, attention

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Early phonics introduction is endorsed as the foundation of successful reading instruction in both education research (meta-analysis by the National Reading Panel [START_REF] Cunningham | The National Reading Panel Report[END_REF], [START_REF] Castles | Ending the Reading Wars: Reading Acquisition From Novice to Expert[END_REF]) and cognitive neuroscience [START_REF] Brem | Brain sensitivity to print emerges when children learn letter-speech sound correspondences[END_REF][START_REF] Dehaene | How Learning to Read Changes the Cortical Networks for Vision and Language[END_REF]. However, phonics instruction is not universally used. One factor for its relative disaffection could be that knowing what grapheme-phoneme (GP) correspondences to teach, and in what order to teach them, can be a difficult task, given that letter-sound relationships do not all have a one-to-one relationship. Take for example Spanish, a highly transparent language, meaning that a given letter is nearly always pronounced the same. In stark contrast is English, which can have many different sounds for a single grapheme (e.g. the 'a' in 'cat', 'mate', 'what' or 'about'). Cross-language research demonstrates that orthographic transparency influences the time and difficulty children have in learning to read [START_REF] Seymour | Foundation literacy acquisition in European orthographies[END_REF][START_REF] Goswami | Children's orthographic representations and linguistic transparency: Nonsense word reading in English, French, and Spanish[END_REF][START_REF] Landerl | Influences of orthographic consistency and reading instruction on the development of nonword reading skills[END_REF][START_REF] Serrano | Variations in reading and spelling acquisition in Portuguese, French and Spanish: A cross-linguistic comparison[END_REF][START_REF] Ziegler | Orthographic Depth and Its Impact on Universal Predictors of Reading: A Cross-Language Investigation[END_REF] . Orthographic transparency is also a conundrum in neural network text-tospeech applications that rely on grapheme-to-phoneme (g2p) transcription. G2p refers to converting words to their phonemes. The current state-of-the art applies long shortterm memory (LSTM) networks and recurrent neural networks using sequence-tosequence (seq2seq) modeling combined with an attention-mechanism [START_REF] Toshniwal | Jointly Learning to Align and Convert Graphemes to Phonemes with Neural Attention Models[END_REF]. More recently, the Transformer model has brought notable improvements in neural machine language transcription and language parsing [START_REF] Vaswani | Attention Is All You Need[END_REF]. These tasks that are fairly analogous to g2p transcription (both depend on long range dependencies and contextual influences). Improvement made by the Transformer model is in part due to parallel position encoding that curtails the need for recurrence and a self-attention field that enables the concatenation of information between sequences, regardless of their distance. The goal of the current project, GPA4.0 (Fig. 1), is to test for g2p transcription improvements, for the first time to our knowledge, using the Transformer model. With this achieved, we take advantage of the Transformer's attention mechanism to align grapheme input to phoneme output, thus permitting the construction of a phonics progression based on the frequency and consistency of all found GP correspondences for any alphabetic language word list.

Experiment

We tested the Transformer model for improved g2p transcription compared to the current-state-of-the-art results [START_REF] Toshniwal | Jointly Learning to Align and Convert Graphemes to Phonemes with Neural Attention Models[END_REF][START_REF] Rao | Grapheme-to-phoneme conversion using Long Short-Term Memory recurrent neural networks[END_REF] on the CMUDict database [START_REF] Weid | The CMU Pronouncing Dictionary[END_REF] while also comparing, for the first time to our knowledge, the results of five different languages of varying orthographic transparency: Spanish<Portuguese<French<English. Training was done using one 1080TI NVIDIA GPU on the base models for a total of 10,000 steps. We use Tensor2Tensor (T2T) [START_REF] Vaswani | Tensor2Tensor for Neural Machine Translation[END_REF] an open-source system for training deep learning models in TensorFlow [START_REF] Abadi | TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems[END_REF]. G2p alignment in our model is made possible using the attention weights of the Transformer model. G2p alignment accuracy was analyzed in French, the only language for which we had a reference for comparison. Table 1 describes the word lists used and provides the minor adjustments made to accommodate the small amount of training data. Training was conducted on 80% of the data. The model's performance was tested on the remaining 20% of data.

To generate a language's phonics progression, we extract all the GP correspondences in the list of g2p aligned words. For each GP correspondence found, we measure its frequency, g2p consistency and phoneme-to-grapheme consistency. The GP correspondences are then sorted by an aggregate weight of the prementioned measures' z-scores (we apply weights of 0.7, 0.25 and 0.05 respectively, but these can be adjusted in the code). The weights are designed to 1) give priority to the most frequent GP correspondences when a pair is particularly consistent and less frequent but highly consistent correspondences.

Results

g2p Transcription

The standard measures of word error rate (WER and phoneme error rate (PER) are reported in Table 2. WER is the total number of output errors in which there is at least one phoneme error / total number of words. PER is the Levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF] (the minimum number of single-character edits needed to change one word to the other) of the predicted phoneme sequence to the reference from the original database / the number of phonemes in the reference. Language WER and PER scores reflect, as expected, decreasing orthographic transparency. We report a slight gain over Toshniwal and Livescu's best prior score on the CMUdict database.

g2p Alignment

Fig. 2 provides an example of encoder-decoder attention (taken from layer-4 multi-head attention in the decoder, see Fig. 1). As the network reads the word "bonjour" or "banane", it attends to distant information required to know if a vowel followed by the letter 'n' will make a single nasal sound (e.g. 'on') or two distinct phonemes (e.g. a+ n). GPA4.0 aligns graphemes to phonemes based on the attention carrying the most weight. G2p alignment error rate was assessed for French using the sequence error rate, a correct or incorrect score for each word and the g2p alignment error rate (Levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF]). We report scores of 27.76% and 10.20% respectively. The relatively high sequence error rate compared to the low g2p alignment score is due to the difficulty in parsing silent letters not coded in the phonology of the trained wordlist. 56% of words in the list contain silent letters.

Conclusion

Our results demonstrate improved g2p transcription by the Transformer model. Our submodule, GPA4.0, takes a novel approach to developing applicable phonics tools for the classroom by taking advantage of neural network performance in g2p transcription and, in particular, the attention field for g2p alignment. This work highlights the difficulties for neural networks to learn the GP correspondences in decreasingly transparent languages. The phonics progressions for the four languages analyzed and their ordered wordlists are freely available. These datafiles can be used as a 'paper' support to guide reading instruction, or as stimuli for game-based reading applications (e.g. the GraphoGame software [START_REF] Brem | Brain sensitivity to print emerges when children learn letter-speech sound correspondences[END_REF][START_REF] Richardson | The GraphoGame Method: The Theoretical and Methodological Background of the Technology-Enhanced Learning Environment for Learning to Read[END_REF]). We hope that the GPA4.0 submodule will be taken up as a tool for researchers and educators to generate their own phonics lessons with 100% decodable reading materials. GPA4.0 combines cognitive science and neural network technology for evidence-based reading education. Phonics progressions and word lists for the four different languages analyzed in this paper, as well as the GPA4.0 submodule code, can be downloaded at https://github.com/OlivierDehaene/GPA4.0.

Bibliography

Fig. 1 .

 1 Fig. 1. GPA4.0 steps to constructing a phonics progression. 1) g2p transcription is done using the Transformer neural network. 2) g2p alignment uses attention weights to align the 'grapheme inputs' to their 'phoneme outputs'. 3) a phonics progression is built by according each g2p alignment an aggregated z-score based on frequency and consistency in the word corpus.

Fig. 2 .

 2 Fig. 2. Encoder-decoder attention in g2p transcription

Table 1 .

 1 Language wordlists used and adjustments made to the Transformer architecture

	language	number of words used for training	number of words used for testing	number of hidden layers	3
	Spanish [16]	10,400	2,600	hidden size, number of neurons per layer	256
	Portuguese [17]	31,200	7,800	filter size	512
	French [18]	8,000	2,000	h, number of attention heads	4
	English [19]	8,000	2,000	attention dropout rate	0.2
	English [13]	95,069	23,767	dropout rate	0.3

Table 2 .

 2 Word error rate (WER) and Phoneme error rate (PER) in four languages of decreasing orthographic transparency

		Spanish<	Portuguese<	French<	English	CMUDict
	WER	0.38%	2.77%	3.18%	15.04%	20.87%
	PER	0.07%	0.55%	0.89%	4.50%	4.59%
			Previous best results using the CMUDict database: WER=21.69%
						PER=5.04%


Keywords: Reconstruction de formes en 3D, reconstruction de surfaces, fonction distance, digramme de Voronoi, diagramme de Morse-Smale, flow complex., persistence topologique

Reconstruction d'ensembles compacts 3D

Résumé : Reconstruire un modèle à partir d'échantillons est un problème central se posant en médecine numérique, en ingénierie inverse, en sciences naturelles, etc. Ces applications ont motivé une recherche substantielle pour la reconstruction de surfaces, la question de la reconstruction de modèles plus généraux n'ayant pas été examinée. Ce travail présente an algorithme visant à changer le paradigme de reconstruction en 3D comme suit.

Premièrement, l'algorithme reconstruit des formes générales-des ensembles compacts et non plus des surfaces. Sous des hypothèses appropriées, nous montrons que la reconstruction a le type d'homotopie de l'objet de départ. Deuxièmement, l'algorithme ne génère pas une seule reconstruction, mais un ensemble de reconstructions plausibles. Troisièmement, l'algorithme peut être couplé à la persistance topologique, afin de sélectionner les traits les plus stables du modèle reconstruit. Enfin, en cas d'échec de la reconstruction, la méthode permet une identification aisée des régions sous-echantillonnées, afin éventuellement de les enrichir.

Ces points clefs sont illustrés sur des modèles difficiles, et devraient permettre de mieux tirer parti de leurs caractéristiques dans les application sus-citées.

Introduction

Reconstructing models from samples. Reconstruction is the generalisation of the connect-the-dots problem: given a sampling of an unknown model, provide a plausible reconstruction of this model from the samples. Since a variety of devices capturing points on/within a 3D model exist, such as laser range scanners, X-ray, CT or MRI machines, reconstruction has countless applications, namely that of organs in medicine, of computer models (spare parts, mock-ups) in reverse engineering, of art pieces in cultural heritage projects, of plants in natural sciences, etc.

The reconstruction should match the model in terms of geometric and topological properties. To ease the process, assumptions on the geometry and/or topology of the model may be used. Such a-priori do alleviate the reconstruction problem, which yet remains challenging for two reasons. First, the samples may not comply with the hypothesis made on the model. In particular, they might be too sparse for the reconstruction to successfully capture challenging details such as thin parts, holes or boundaries. Second, even for a sampling compliant with these features, a satisfactory reconstruction may not be unique.

For shapes in the ambient 3D Euclidean space, a standard assumption is that the model is a smooth surface. Algorithms reconstructing surfaces report a smooth model or a combinatorial representation, typically a triangle mesh. These two categories have opposite pros and cons, since the latter corresponds to approaches offering flexibility to represent local features, such as holes and boundaries, while the former features strategies returning more compact yet globally defined surfaces. Example algorithms in the first realm are those based on level sets [START_REF] Zhao | Fast surface reconstruction using the level set method[END_REF], radial basis functions [CBC + 01] and moving least squares [ABCO + 01]. As surveyed in [START_REF] Cazals | Delaunay triangulation based surface reconstruction[END_REF], examples in the second area are intimately related to the Voronoi diagram of the samples, and its dual the Delaunay triangulation [AB99, GJ02, BC02, ACDL00, Cha03, CSD04, Ede04].

Three-dimensional Reconstruction based upon the flow complex. Because reconstruction boils down to establishing neighborhood connections between samples, geometric complexes encoding proximity relationships may be used as a background. While it has long been recognized that the Delaunay triangulation contains, under mild assumptions, a satisfactory reconstruction [START_REF] Boissonnat | Geometric structures for three-dimensional shape representation[END_REF], it has recently been shown that the flow complex also does so. Prosaically, the flow complex consists of the watersheds associated to the critical points of the distance function to a point cloud [START_REF] Giesen | The flow complex: A data structure for geometric modeling[END_REF][START_REF] Cazals | Robust construction of the three-dimensional flow complex[END_REF]. For points sampled on a smooth surface, it has been shown that selected stable manifolds provide a suitable reconstruction [START_REF] Dey | Critical points of the distance to an epsilon-sampling of a surface and flow based surface reconstruction[END_REF]. Also, the unstable manifolds have been shown to provide an approximation of the medial axis of the sampled surface [START_REF] Giesen | Medial axis approximation and unstable manifolds[END_REF], with applications to the identification of cylindrical and flat regions [START_REF] Goswami | Identifying flat and tubular regions of a shape by unstable manifolds[END_REF].

Contributions and paper overview. In spite of their successes, the reconstruction strategies just outlined only accommodate manifold shapes, and since a single reconstruction is reported, are unable to shed light on the potential ambiguities of the sampling. The goal of this paper is to change this paradigm in three ways, by developing an algorithm (i) handling general shapes-compact sets, (ii) reporting a collection of plausible reconstructions, and (iii) selecting the most stable features. Most importantly, the algorithm does not make any assumption on the model being reconstructed, be it its geometry or topology. Moreover, it is effective on challenging datasets, and we believe it is the first such algorithm.

Pre-requisites on the flow complex are recalled in section 2. The algorithm and its theoretical guarantees are respectively exposed in sections 3 and 4. Section 5 illustrates the main features of the algorithm on challenging examples.

Background: The Flow Complex and its Hasse Diagram

Morse theory. Morse theory is concerned with the study of functions on manifolds. Following classical terminology in differential topology, a critical point of a differentiable function is a point where the differential of the function vanishes, and the function is called a Morse function if its critical points are isolated and nondegenerate. The stable (unstable) manifold W s (p) (W u (p)) of a critical point p is the union of all integral curves associated to the gradient of the function, and respectively ending (originating) at p. The function is termed Morse-Smale provided its stable and unstable manifolds intersect transversely [START_REF] Palis | Geometric Theory of Dynamical Systems[END_REF]. For such a function, the Morse-Smale complex is the subdivision of M formed by the connected components of the intersections W s (p) ∩ W u (q), where p and q range over all critical points. A topological sketch of the manifold can be obtained from a CW complex built from the stable manifolds of the critical points and their incidence.

Morse theory of the distance function to a point cloud. The previous ideas can be instantiated in the following setting. Let P be a finite 3D point set, and denote d P (p) the distance from any point p to P . This distance function is closely related to the Voronoi diagram of P , which features the points in 3D space equidistant from at least two points in P . It is easily seen that function d P is smooth everywhere besides at the points in P and on the lower dimensional Voronoi faces. But a generalized gradient ∇d P can be defined [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type than its medial axis[END_REF], together with the accompanying notions from Morse theory. In particular, a critical point of d P is a point which is contained in the interior of the convex hull of its nearest neighbors. The stable (unstable) manifolds of these critical points are defined as in the smooth setting. The collection of these stable and unstable manifolds defines the flow complex [START_REF] Giesen | The flow complex: A data structure for geometric modeling[END_REF].

Of particular interest for our reconstruction algorithm are the stable manifolds. The stable manifold of an index i critical point is i-dimensional1 , and is bounded by the stable manifolds of critical points of index i -1. This recursive structure, which corresponds to incidences between critical points in co-dimension one is encoded in a graph called the the Hasse diagram of the flow complex: a node associated to an index i critical point a is connected to a node associated to an index i + 1 critical point b iff there exists an orbit leaving a and ending at b. In the Hasse diagram, the successors (resp. ancestors) of node a are denoted Out(a) (resp. In(a)). See Fig. 1 for a 2D illustration.

Algorithm

The description of the algorithm is organized as follows: first, we present the building blocks; next, we present the basic version; finally, we present a refined version, which exploits a simplification of the Hasse diagram based upon topological persistence [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF].

Building Blocks

The algorithm consists of incrementally adding stable manifolds to the reconstruction, a process controlled by a threshold t r encoding the ratio of critical values of incident critical points. Since these manifolds are selected from the Hasse diagram and since there is a one-to-one correspondence between stable manifolds and nodes of the Hasse diagram, we shall abuse terminology and say that we add nodes to the reconstruction. Similarly, the index of a node refers to the index of the critical point associated to this node. Finally, the critical value V (c) associated to a node c is the value of d P (c) at the corresponding critical point. If a node c already in the reconstruction triggers the insertion of node d, then node c is called a sponsor of node d. As we shall see, a node may have several sponsors, and the discovery of new sponsors occurs through three extension operations called regularization, upflow extension, horizontal extension. The priority associated with a sponsorship relationship is measured by a (regularization / upflow / horizontal) ratio, i.e. a real number ≥ 1. To describe these operations, we consider two nodes c and d, with node c in the reconstruction.

Reconstruction initialization. The reconstruction is initialized from selected one dimensional stable manifolds. In general, it can be shown that these stable manifolds are exactly the Gabriel edges, namely the Delaunay edges whose diametral ball is empty. In our case, we retain a Gabriel edge e = (v 0 , v 1 ) as an initialization edge iff v 1 if the nearest neighbor of v 0 , or vice-versa.

Regularization. The reconstruction shall be a complex. Recall that a stable manifold of an index i critical point is bounded by stable manifolds of index i -1 critical points. Therefore, a node c belonging to the reconstruction is said to be regularized if (i) the reconstruction also contains all its ancestors, i.e. all nodes d with d ∈ In(c) (ii) these nodes are themselves regularized. A node c is called a regularization sponsor of each of its ancestors, and the regularization ratio of such a pair (c, d) is set to one, that is r r (c, d) = 1. Horizontal extension. In this last operation, index one nodes sponsor nodes with the same dimension. More precisely, let c and d be two nodes which are the successors of a common node b in the Hasse diagram, and define the horizontal ratio as r h (c, d) = V (d)/V (c). The pair (c, d) satisfies the horizontal criterion provided that r h (c, d) < t r , in which case node c is termed a horizontal sponsor of node d.

Algorithm Without Persistence

The iterative reconstruction uses a priority queue Q R which contains all the nodes sponsored as defined above. The priority of a node in the queue is the least upflow / horizontal / regularization ratio over its sponsors included in the reconstruction so far. Nodes in the queue are precisely those which can trigger the insertion of additional nodes thanks to the three extension operations.

More precisely, the queue initialization consists of inserting into Q R the nodes sponsored by the initialization edges, through upflow and horizontal extension. (The regularization of an edge consists of inserting its vertices into the reconstruction.) Then, the algorithm consists of iteratively popping the node with least priority, so as to perform the regularization, upflow extension, and horizontal extension, in this order. To see how, let c be the node popped. Thanks to the regularization, node c sponsors all its ancestors In(c). Thanks to the upflow extension, node c sponsors a subset of its successors Out(c). Thanks to the horizontal extension, node c sponsors a subset of its siblings. Notice that for a pair (c, d) discovered while performing an extension operation, one faces two situations: if node d is already in Q R , its priority is updated if the ratio of the pair (c, d) is less than that already in the queue; if not, node d is inserted into Q R with the priority as defined by its sponsor.

The following comments are in order: ❼ Since the regularization ratio is set to one-the least possible priority, the regularization of a node is immediate and precedes any upflow or horizontal extension.

❼ The fact that the extension always proceeds with the node associated with the least priority provides a canonical ordering of the nodes found in the reconstruction. In particular, if t r1 and t r2 are two thresholds such that t r1 < t r2 , the sequences of operations for the reconstructions associated with t r1 and t r2 are nested.

Simplifying the Hasse diagram

While the above algorithm is already provably correct, as we will see in the next section, a number of practical situations significantly benefit from a pre-processing aiming at widening the gap between stable manifolds corresponding to the object being reconstructed and those corresponding to its complement. It can be shown that during the simplification process, the pairs are being cancelled in order of increasing topological persistence. We stop the process when the ratio of the next pair exceeds a threshold t p ≥ 1. The original algorithm may then be run on the simplified Hasse diagram, retaining for the initialization step only the initial edges that have not been cancelled.

σ 0 σ 1 σ 4 σ 3 M 2 p 0 p 1 p 2 p 3 (a) (b) (c)

Theoretical Guarantees

Our proof of correctness builds on recent inference results obtained in [START_REF] Chazal | A sampling theory for compacts in Euclidean spaces[END_REF] using the framework of distance functions. Before stating the guarantees of our algorithm, we briefly recall the latter results.

Sampling conditions. Let K be a compact subset of R n . Though the distance function2 d K is not differentiable on the medial axis of R 3 \ K, it is possible to define a notion of generalized gradient, denoted by ∇d K , that shares many properties with usual gradients [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type than its medial axis[END_REF]. Denoting by Γ(x) the set of points on K closest to x ∈ R 3 , it can be shown that ||∇d K (x)|| is the cosine of the (half) angle of the smallest cone with apex x that contains Γ(x). In particular ||∇d K (x)|| equals 1 outside the medial axis of R 3 \ K.

Definition 1 (µ-reach). The µ-medial axis of a compact set K ⊂ R n is the set of points x / ∈ K such that ||∇d K (x)|| < µ. The µ-reach of K, denoted by r µ (K), is the minimum distance between a point in K and a point in the closure of its µ-medial axis.

For µ = 1, the µ-reach coincides with the minimum of the local feature size function [START_REF] Amenta | Surface reconstruction by Voronoi filtering[END_REF], also called reach [START_REF] Federer | Curvature measures[END_REF]. The main advantage of the µ-reach over the reach is that it is non-zero -for a suitable value of µ-for a large class of non-smooth shapes, such as polyhedra. Using the concept of µ-reach, one can formulate a sampling condition similar to the ε-sample condition introduced by Amenta et al [START_REF] Amenta | Surface reconstruction by Voronoi filtering[END_REF]. To state it, we use the following notations. For a positive number α, we denote by K α the α-offset of K, namely the set of points at distance at most α from K. The Hausdorff distance d H (K, P ) between compact subsets K and P is the least value α such that K ⊂ P α and P ⊂ K α . The condition reads as follows:

Definition 2 ((κ, µ)-approximation). Given two non-negative real numbers κ and µ, we say that a compact set P ⊂ R n is a (κ, µ)-approximation of a compact set K ⊂ R n if the Hausdorff distance between K and P does not exceed κ times the µ-reach of K. Note that polyhedra for example admit finite (κ, µ)-approximation for suitable µ, whereas they do not admit finite ε-samples since they have zero reach. The following theorem, proved in [START_REF] Chazal | A sampling theory for compacts in Euclidean spaces[END_REF], shows that a compact set can be reconstructed in a topologically correct way from a (κ, µ)-approximation using simple offsets (see [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF] for related results in the smooth case):

Theorem 1. Let P ⊂ R n be a (κ, µ)-approximation of a compact set K. If κ < µ 2 5µ 2 + 12
then P α is homotopy equivalent to K η for sufficiently small η, provided that

4d H (K, P ) µ 2 ≤ α < r µ (K) -3d H (K, P )
A key argument in the proof of the above theorem is that the distance function d P does not have any critical value in the interval ]4d H (K, P )/µ 2 , r µ (K) -3d H (K, P )[. We note that η cannot be set to 0 in general in the theorem due to certain pathological examples.

Correctness. We say that a point cloud P is a ρ-uniform approximation of a compact set K if half the distance between the two closest sample points in P is at least ρ times the the Hausdorff distance between P and K, where 0 < ρ < 1. Using the results from the previous paragraph, the following theorem is proved in section 7.1: Theorem 2. Let K be a compact subset of R 3 and assume point cloud

P is a ρ-uniform (κ, µ)-approximation of K. If 4 ρµ 2 < t r < µ 2 4κ -1
then the output of the algorithm is homotopy equivalent to K η for small enough η.

It should be noted that the sampling condition in the above theorem is uniform, meaning that it requires that the sampling density is everywhere at least a certain fraction of the global feature size. However, our algorithm itself is adaptive, in the sense that it can cope with situations where no such global density threshold exists.

Experiments

This section illustrates key features of our algorithm, whose implementation is sketched in section 7.2.

Models and Parameters

Models used. We report results on two models: first, two intersecting hemi-spheres (3,000 pts), to illustrate (i) the reconstruction of non-manifold shapes, and (ii) the enumeration of plausible shapes; second, the vase model (2,699 pts), to highlight (i) the importance of persistence to select prominent features, and (ii) the homotopy type preservation. Additional illustrations on a mechanical part (12,593 pts) and a beech tree (20,956 pts) are reported in the supplement in section 7.3. Running times on a standard desktop computer range from from 8 seconds for the vase model, to 120 seconds for the beech tree. (Details in section 7.2.)

Parameters. The persistence and reconstruction thresholds t p and t r should be finite and larger than one. We thus adopt the following conventions: t p = 0 means that no persistence is used, and t r = ∞ means that all the possible reconstruction steps are carried out. An experimental justification of the values used for t r and t p is provided in section 7.4.

Artwork conventions for illustrations. Critical points of index 0/1/2/3 are respectively depicted as grey/yellow/orange/red cubes. Gabriel edges used for the reconstruction initialization are represented as blue line-segments. Index two stable manifolds are depicted as green triangulated surfaces. To represent index three stable manifolds, we display line-segments joining the index three critical point to the index two critical points found on the boundary of the corresponding stable manifold. Regarding persistence, any two points paired by the persistence algorithm are linked by a pink line-segment.

Results

Accommodating non manifold shapes. As an example of non-manifold reconstruction, consider the two hemi-spheres on Fig. 3(a). As seen from Figs. 3(b,c), the persistence algorithm helps in cancelling maxima that yield a thickening of the reconstruction near the intersection. As seen from Fig. 3(d), the reconstruction of the circle arc found at the intersection consists of a sequence of edges of multiplicity four and cycles mixing edges of multiplicity one, three and five. The former case corresponds to a locally homeomorphic reconstruction. The latter corresponds to a transverse stretching of the intersection circle into a homotopic region, as seen on Fig.

3(e).

Enumerating plausible reconstructions. Reconstruction is an ill-posed problem, which, in general, does not admit a unique solution. As an example, consider Fig. 4(a). Do the circled points feature a hole on the surface or not? Our reconstruction strategy offers the possibility to consider both situations, since increasing t r results in filling the hole -Fig. 4(b).

Assessing the role of persistence. Models which are noisy and/or under-sampled may feature undesired critical points. The successors and ancestors of these points in the Hasse diagram may yield undesired stable manifolds in the reconstruction.

As an example, the fin of Fig. 5(a) is clearly erroneous in the reconstruction of the vase model. By tracking backward the extension operations performed, as seen from Fig. 6(a,b), it appears that a jump has been made between a surface critical point of index one and an index two critical point located on the fin. On the other hand, this latter critical point is located very close from an index two critical point. Running the persistence algorithm with threshold t p = 1.05 mates the two critical points, and the jump from the surface critical point is now beyond the threshold t r = 1.7, as seen from Fig. 5(b). The effect of persistence is also easily seen from the so-called reconstruction profiles, presented in the supplemental-section 7.4.

Notice however, that persistence may prevent from inserting selected stable manifolds in the reconstruction. To see why, consider an index two critical point a paired by the persistence algorithm to a maximum M , and also assume that the outflow of a consists of M and of the critical point at infinity. When updating the Hasse diagram as explained in section 3.3, the stable manifold of b is associated to nodes in the outflow of node a, that is to the maximum at infinity. Thus, the stable manifold of node a cannot be part of the reconstruction since the maximum at infinity is never reached. Should this happen, notice that the size of the hole on the surface is comparable to the size of the 3D hole associated to the index 3 critical point paired, a characterization of under-sampling.

Finally, notice that the possibility to track back the extension operations, which is illustrated on Fig. 6(a,b), offers a unique way to control under-sampled regions in the point cloud processed, so as to further guide the acquisition process. In spite of these novel features, a number of questions deserve further work. Complexity-wise, our algorithm relies on the flow complex, whose construction is the bottleneck. However, one could design a strategy interleaving the flow complex construction and the reconstruction, so as to compute the former on demand. Such an algorithm would have output-sensitive complexity, since one step ahead only would be required with respect to the final reconstruction. In terms of output, the reconstruction consists of stable manifolds of the flow complex. In particular, the surface patches correspond to index two stable manifolds, whose triangles may have arbitrary aspect ratio. This observation calls for further work so as to approximate the surface patches of the reconstruction using Delaunay triangles.

Finally, since our algorithm accommodates non manifold shapes, it should allow the development of strategies computing stratifications of complex shapes, with applications to morphological analysis.

Reconstruction Profiles

As observed in section 3.2, the reconstructions for two thresholds t r1 and t r2 such that t r1 < t r2 are nested. Assume that at the ith iteration on Q R , a node with priority r i is popped. The sequence (r i ) i≥1 for t r = ∞ encompasses all possible reconstructions, and is termed the reconstruction profile of the model. The interests of profiles are twofold.

First, profiles provide an easy assessment of the influence of the simplification of the Hasse diagram. When no persistence is used, situations where one extension with arbitrary extension ratio is followed by a number of extensions with ratio close to one are frequent: these situations correspond to the numerous crenels observed on Figs. 9(a), 11(a), 13(a), 15(a). When persistence is used, since critical points whose critical values are close get matched, these crenels disappear even with a modest persistence threshold-Figs. 9(b), 11(b), 13(b), 15(b).

Second, profiles encodes the magnitude of the cuts between the critical points located on/in the objects and in its complement. As seen from Fig. 10 for the two hemi-spheres, one does not see any significant gap between both sets of critical points. The distance function does not have any critical point on the medial axis this model. The situation is different on the vase and the mechanical part, as seen from Figs. 12 and 14. For these models, one indeeds observes a clear cut between the critical values, which accounts for the reconstruction threshold taken around t r = 2. Notice in particular that in both cases, the number of critical points on/in the object and in its complement are incommensurable: while the former are related to the sampling density, the latter are related to the number features of the complement. Finally, the beech tree model-see Fig. 16 corresponds to a more complex setting, where several reconstruction scales coexist.

In passing, we note that the quality of the reconstruction is not sensitive to the thresholds used: values of t p ∈ [1.02, 1.2] and t r ∈ [1.9, 2.1] yield comparable results.

Figure 1 :

 1 Figure 1: Distance function dP to a 2D point set P = {p0, . . . , p3}. (a) Critical points. (b) Associated Hasse diagram with one node per critical point-the projection of nodes along the x axis is immaterial.

  Upflow extension. If c and d are incident nodes in the Hasse diagram, with c in the reconstruction, this extension operation consists of inserting node d provided that the ratio between the critical values of the two nodes is bounded by t r . That is, let c and d be two incident nodes with dim(d) = dim(c) + 1, and define the upflow ratio of the pair as r u (c, d) = V (d)/V (c). Nodes c and d satisfy the upflow condition provided that r u (c, d) < t r , in which case node c is called an upflow sponsor of node d.

  The preprocessing consists of iteratively simplifying the Hasse diagram by a sequence of cancellations, also called elementary reductions in [KMM04]. At each iteration, we choose to cancel the pair of incident nodes e = (a, b) with the least ratio r u (a, b). Since a and b are incident their indices differ by 1. Assume w.l.o.g. that dim(b) = dim(a)+1. Consider the bipartite graph over the sets In(b) and Out(a). To get the new Hasse diagram, we simply add all edges in the previous graph to the current Hasse diagram, counting multiplicities modulo 2. In particular, nodes a and b are not connected to any node anymore and can thus be removed from the graph. During the cancellation, we also redistribute the stable manifolds attached to the node b to the nodes of Out(a). The process is illustrated on Fig. 2.

Figure 2 :

 2 Figure 2: Simplifying the example of Fig. 1. (a) Cancelling the pair (σ2, M1) in the Hasse diagram consists of reversing the flow from M1 to σ2. (b) Local structure of the Hasse diagram after the cancellation: dashed edges have been removed. Notice that the stable manifold of the maximum M1, which recursively contains the stable manifold of σ2 and its endpoints has been redistributed to M2. (c) Geometrically, reversing the flow from M1 to σ2 consists of virtually making the triangle p0p1p2 obtuse.

INRIA

Figure 3 :Figure 4 :

 34 Figure 3: Reconstructing non-manifold shapes (a) Reconstruction of two intersecting hemi-spheres with tr = 1.9, tp = 0. (b) Transparent view of a section of the reconstruction in (a): the stable manifolds of the circled maxima correspond to a thickening of the reconstruction. (c) Same region as in (b) with parameters tr = 2.5, tp = 1.05: the maxima have been cancelled by the persistence algorithm. (d) Reconstruction for parameters tr = 2.5, tp = 1.05: Gabriel edges of multiplicity zero (green), one (purple), three (blue), four (orange) and five (yellow). (e) Circled region of Fig. (d): the intersection curve from p0 to p1 has been stretched to a topological disk, namely the union of the stable manifolds of the index two critical points c and d-triangles of the stable manifolds not shown.

Figure 5 :

 5 Figure 5: Assessing the importance of persistence (a) At tr = 1.7, tp = 0, a fin between two handles of the vase model is observed, while one back handle is disconnected-circled region. (b) At tr = 2, tp = 1.02, the fin is gone. Note also the preservation of the homotopy type of a solid handle, which is reconstructed as a polyline.

Figure 6 :

 6 Figure 6: Untangling the role of persistence in Fig. 5(a,b). (a,b)The extension path followed by the algorithm-red arrows. The circled region features an upflow extension between a surface critical point c and a medial axis critical point d. (c) Using persistence, the critical point d has been paired to an index one critical point e. The upflow extension from the surface critical point c is now forbidden at threshold tr = 2, whence the reconstruction of Fig. 5(b).

Figure 7 :

 7 Figure 7: Reconstruction of a mechanical part-a genus 3 surface, with parameters tr = 2.1, tp = 1.1. Inset: circled points make up the boundary (a topological circle) of the cylindrical depression to the right of the largest hole.

Figure 8 :

 8 Figure 8: Beech tree reconstruction, with parameters tr = 2.2, tp = 1.1 (a) Overview of this noisy and under-sampled model (b,c) Zoom near a an under-sampled peduncle. The point cloud is courtesy of J-C. Chambelland et al, UMR 547 PIAF -INRA/UBP.

Figure 9 :

 9 Figure 9: Reconstruction profiles for intersecting spheres (a) tp = 0, tr = ∞ (b) tp = 1.1, tr = ∞

Figure 11 :Figure 12 :Figure 13 :

 111213 Figure 11: Reconstruction profiles for the vase (a) tp = 0, tr = ∞ (a) tp = 1.1, tr = ∞

Figure 15 :Figure 16 :

 1516 Figure 15: Reconstruction profiles Beech tree (a) tp = 0, tr = ∞ (b) tp = 1.1, tr = ∞

RR n➦ 6868

For stable manifolds of index two, an additional constraint is required: the stable manifold should not contain any Voronoi vertex.

The distance function d P to a point cloud is a particular case of the distance function d K to a general compact set.INRIA

Supplemental

Proof of theorem 2

We prove the theorem for the basic algorithm, without resorting to Hasse diagram simplification. It is apparent from the proof that the guarantee also holds for the full version of the algorithm, as long as the chosen persistence threshold t p does not exceed t r .

Proof. Since ρ and µ do not exceed 1, the condition implies that µ 2 /(4κ) -1 > 4, so κ < µ 2 /20. As µ ≤ 1, 20 > 5µ 2 + 12, so the reconstruction theorem can be applied. In particular, d P does not have any critical value in the interval ]4d H (K, P )/µ 2 , r µ (K) -3d H (K, P )[.

We now show the output of our reconstruction algorithm is the union of the stable manifolds of critical points of d P whose distance to P does not exceed 4d H (K, P )/µ 2 . Let c be such a critical point. Consider a downward path starting at c and ending at an index 1 critical point d in the Hasse diagram of P 's flow complex. We clearly have d P (d) < d P (c). Let x be one of the sample points in the boundary of the stable manifold of d, and e be the edge joining x and its closest sample point. Edge e belongs to the reconstruction by construction. Also, the critical value corresponding to e (i.e. its half length) is at least ρd H (K, P ) by assumption. Hence the ratio between the (half) lengths of e and of the stable manifold of d is at most 4/(ρµ 2 ) < t r , which shows that the stable manifold of d must have been included in the reconstruction through a horizontal extension step. Now the ratio d P (c)/d P (d) is also at most 4/(ρµ 2 ), so the stable manifold of c must have been included in the reconstruction through upflow extensions from d.

It is not difficult to show that stable manifolds of critical points with value at least r µ (K) -3d H (K, P ) do not belong to the reconstruction. Indeed, this would imply an upflow extension from a critical point with value at most 4d H (K, P )/µ 2 , but the ratio between the two values is:

which is larger than threshold t r by assumption. To conclude the proof of the theorem, it is sufficient to use the fact that the union of the stable manifolds of critical points with value less than some threshold α is homotopy equivalent to the α-shape of the point cloud P [DGJ03], or equivalently to its α-offset P α [START_REF] Edelsbrunner | The union of balls and its dual shape[END_REF]. Indeed, from the reconstruction theorem, the latter offset is homotopy equivalent to K η for sufficiently small η.

Implementation Outline

Our implementation of the reconstruction algorithm meets the C++ standards of Computational Geometry Algorithms Library (CGAL, see www.cgal.org) and is parametrized by a traits class corresponding the Hasse diagram of the distance function to the samples. The construction of this Hasse diagram is carried out with our implementation of the flow complex [START_REF] Cazals | Robust construction of the three-dimensional flow complex[END_REF]. More precisely, incidences between index one and index two critical points are discovered while building the stable manifolds of the latter; incidences between index two and index three critical points are discovered while computing the unstable manifolds of the former. As reported in [START_REF] Cazals | Robust construction of the three-dimensional flow complex[END_REF], this latter stage is the limiting step, due to cascaded constructions and predicates on such.

The code was compiled with CGAL 3.3, using GMP 4.2, with the GNU compiler g++ 4.1.2. The machine used for the experiments was a PC running Linux Fedora Core 7, with 2MB of memory and a 3GHz Pentium 4 processor.

Additional Illustrations

This section provides illustrations on two additional models: the mechanical part of Fig. 7 is a typical model in computer aided geometric design / reverse engineering; the beech tree of Fig. 8