Jean-Pierre Toumazet

Franck Vautier

Erwan Roussel

Bertrand Dousteyssier

Automatic detection of complex archaeological grazing structures using airborne laser scanning data

Keywords: Archaeological structure detection, geoarchaeology, LiDAR, ALS, segmentation, template matching, Digital Terrain Model, Local Relief model, automatic detection, signal processing, pattern recognition

The use of Light Detection And Ranging (LiDAR) for archaeological purposes is becoming more prevalent in order to detect and to document remains located in forested areas. A manual digitalisation of the detected elements is possible if the aim is to focus on some particular elements. However, one of the main interests of airborne laser scanning is to put the archaeological information in their context, and to allow a better understanding of the relation between each item and its environment (other structures, paths, etc). This concept of archaeological landscape generally results in a too large amount of data to permit a manual analysis. This paper describes an approach for the automatic detection of particular archaeological artefact, archaeological grazing structures, found in high concentration in some places of Auvergne (France). First, a model of the elements of interest is designed with the archaeologist. The automatic detection of the archaeological grazing structures is then carried out, based on the evaluation of the matching degree of each element with the model. Finally, the location and the boundary of each selected elements are extracted and stored in a database. The efficiency of the method is tested, by comparison with the manual digitalisation of an expert, on a restricted zone, and the observed differences are analysed and discussed.

Introduction:

LiDAR, generally known as airborne laser scanning (ALS), is used by archaeologists to detect and map sites and to analyze past landscape since the last ten years (Cutchley and Crow, 2009;[START_REF] Masini | On the airborne lidar contribution in archaeology: from site identification to landscape investigation[END_REF][START_REF] Georges-Leroy | Le lidar: une technique de détection au service de l'archéologie[END_REF]. Because of its ability to penetrate certain types of woodland canopy, this technology is a revolutionary tool for archaeologist interested in remains mostly located under forest areas which are still relatively unexplored. Research programs using Lidar data are becoming more and more frequent. From an historiographical perspective, they are in the continuity of the landscape archaeology studies, developed in the 1980s, especially in the Mediterranean Basin. They aspire to explore vast areas, linking scales from micro-regional to regional studies. Lidar survey exhibits archaeological remains, preserved from destruction by their position in altitude or a protective vegetative cover. Over the past ten years, LiDAR technology permitted to discover unknown or partially identified archaeological sites worldwide even under dense vegetation cover [START_REF] Devereux | The potential of airborne LiDAR for detection of archaeological features under woodland canopies[END_REF][START_REF] Humme | Revealing Celtic fields from LiDAR data using Kriging based filtering[END_REF][START_REF] Doneus | Archaeological prospection of forested areas using full-waveform airborne laser scanning[END_REF][START_REF] Johnson | Rediscovering the lost archaeological landscape of southern New England using airborne light detection and ranging (LiDAR)[END_REF][START_REF] Chase | The use of LiDAR in understanding the ancient Maya landscape: Caracol and Western Belize[END_REF][START_REF] Ludemann | Airborne laser scanning of historical wood charcoal production sitesa new tool of kiln site anthropology at the landscape level[END_REF][START_REF] Evans | Uncovering Archaeological Landscapes at Angkor Using LiDAR[END_REF][START_REF] Johnson | Rediscovering the lost archaeological landscape of southern New England using airborne light detection and ranging (LiDAR)[END_REF][START_REF] Stark | Residential patterning at Angkor Wat[END_REF]. The majority of published studies examined the possibility of using ALS data for archaeological investigations by visualization and interpretation of high resolution ALS derived-DTMs (Digital Terrain Model) [START_REF] Kokalj | Application of sky-view factor for the visualisation of historic landscape features in LiDAR-derived relief models[END_REF]Bennet et al., 2012;[START_REF] Opitz | Interpreting Archaeological Topography: Lasers, 3D Data, Observation, Visualisation, and applications[END_REF] after classification procedures of bare-earth elevations (Kilian et al., 1996;[START_REF] Kraus | Determination of terrain models in wooded areas with airborne laser scanner data[END_REF][START_REF] Vosselman | Slope based filtering of laser altimetry data[END_REF][START_REF] Zhang | A progressive morphological filter for removing nonground measurements from airborne LiDAR data[END_REF]Zaksek and Pfeifer, 2006;Lasaporana et al., 2011). The ALS ground point clouds are converted to raster DTMs which are used to build derived visualization models. A broad range of models derived from the raster DTMs exist and are used as supplementary tools to detect and differentiate microtopography and therefore archaeological features, for examples, multidirectional oblique weighting hillshade (MDOW), slope, local relief model (LRM), sky-view factor (SVF), positive and negative openness or combination of those methods [START_REF] Devereux | Visualisation of LiDAR terrain models for archaeological feature detection[END_REF][START_REF] Hesse | LiDAR-derived Local Relief Modelsa new tool for archaeological prospection[END_REF][START_REF] Challis | A generic toolkit for the visualization of archaeological features on airborne lidar elevation data[END_REF]Kokaljiz et al., 2011;[START_REF] Mccoy | Airborne lidar survey of irrigated agricultural landscapes: an application of the slope contrast method[END_REF][START_REF] Bennett | A Comparison of Visualization Techniques for Models Created from Airborne Laser Scanned Data[END_REF][START_REF] Stular | Visualization of Lidar-Derived Relief Models for Detection of Archaeological Features[END_REF][START_REF] Doneus | Openness as vizualisation technique for interpretative mapping of airborne LiDAR derived Digital Terrain Models[END_REF]. These DTM treatments are usually grouped in the so-called visualization methods and the archaeologist's analytical work is to filter, rank and interpret topographic anomalies and local details enhanced by these derived-models in order to discriminate only those with an historical interest. The selected structures are then manually digitized, mapped and integrated into GIS-based environment (Doneus and Küthreiber, 2013). However, the density of archaeological features and the large areas covered by the LiDAR surveys render the manual analysis and interpretation a timeconsuming and fastidious task [START_REF] Sevara | Pixel versus object -A comparison of strategies for the semi-automated mapping of archaeological features using airborne laser scanning data[END_REF]. The manual visual interpretation is also a subjective process and can have a substantial impact on remains investigations, depending of the level of expertise of people carrying this classification : Non-sites may be identified as potential archaeological sites or on the other hand elements of archaeological relevance may be interpreted as natural [START_REF] Doneus | Full-waveform airborne laser scanning as a tool for archaeological reconnaissance[END_REF]. Specialists may also focus on singular points of their own interest, and may tend to see what they know and unconsciously neglect other elements (Cowley, 2012).

Recently, automatic analysis of satellite images [START_REF] Lasaponara | Beyond modern landscape features: New insights in the archaeological area of Tiwanaku in Bolivia from satellite data[END_REF][START_REF] D'orazio | Archaeological trace extraction by a local directional active contour approach[END_REF][START_REF] Figorito | Semi-automatic detection of linear archaeological traces fromorthorectified aerial images[END_REF][START_REF] Di Iorio | Advancement in Automatic Monitoring and Detection of Archaeological Sites Using a Hybrid Process of Remote Sensing, GIS Techniques and a Shape Detection Algorithm, Remote Sensing for Science, Education and Natural and Cultural Heritage[END_REF] or LiDAR data (Cowley, 2012;[START_REF] Trier | Automatic detection of pit structures in airborne laser scanning data[END_REF][START_REF] Casana | Regional-scale archaeological remote sensing in the age of big data: automated site discovery vs. brute force methods[END_REF][START_REF] Trier | Automatic detection of mound structures in airborne laser scanning data[END_REF][START_REF] Sevara | Pixel versus object -A comparison of strategies for the semi-automated mapping of archaeological features using airborne laser scanning data[END_REF] were applied to extract remains and to offer to archaeologists an additional visualization method to detect archaeological features in large areas or in area where remains are not visible to the naked eyes. Moreover, automatic detection may be applied to ALS data, either directly on the LiDAR point cloud or on a derived DEM with an appropriately chosen raster resolution, i.e. pixel size. Several approaches have been proposed recently : Pixel-based classification, based on the identification of high altitudinal gradients in ALS-derived raster DTM like LRM and SVF models, has been applied and compared with object oriented classification [START_REF] Sevara | Pixel versus object -A comparison of strategies for the semi-automated mapping of archaeological features using airborne laser scanning data[END_REF]. The template matching approach has also been tested for archaeological structures with simple forms [START_REF] Trier | Automatic detection of mound structures in airborne laser scanning data[END_REF][START_REF] Schneider | A template-matching approach combining morphometric variables for automated mapping of charcoal kiln sites[END_REF]. The method is then based on a geometrical template, defined from the knowledge of the morphometric characteristics of a targeted archaeological feature. The main problem is that the automatic detection is mostly limited to simple and isolated structures [START_REF] Kim | Automated crater detection, a new tool for Mars cartography and chronology[END_REF][START_REF] Krøgli | Automatic detection of circular depressions in digital elevation data in the search for potential Norwegian impact structures[END_REF][START_REF] Rack | Automated Crater Detection, A New Tool for Mars Cartography and Chronology[END_REF][START_REF] Wan | Automatic extraction of lunar impact craters from Chang'E-1 satellite photographs[END_REF]. The aim of this paper is to propose a combination between pixelbased classification and template matching, in order to detect the elementary parts of complex archaeological structures. Each elementary structure is defined by its morphometric characteristics, but also by its belonging to a complex structure, that may have various shapes and sizes.

The Lidar survey of the central part of the Chaîne des Puys (volcanic chain located in Auvergne, France), held in winter 2011, revealed, for the first time in the Dome Mountains, the presence of a typical grazing structures locally called "tras" (figure 1). These structures are rectangular or sub circular and compartmentalized. They correspond to grazing features of late medieval to early modern era [START_REF] D'aussy | Voyage d'Auvergne[END_REF][START_REF] Fournier | La vie pastorale dans les montagnes du Centre de la France. Recherches historiques et archéologiques[END_REF]). These structures are already well known in the pastoral lands of the Cézallier and Monts Dores regions, in the French Massif Central [START_REF] Sauget | Paysages et architecture rurale entre Dômes, Sancy et Artense. Cantons de Rochefort Montagne[END_REF]. They can be found in highly concentrated forms (hundreds of structures), raising a registration problem. As a consequence, only global areas are so far registered, without any information on individualized structures. The discovery of an important concentration of grazing structures (225 elementary structures for half a square km) in an area covered by the LiDAR was the opportunity to develop and to test an automatic detection tool. As several thousand of them are present in different sectors of the Massif Central, the method will be easily deployable on a much larger scale and will assist archaeologists and the archaeological services to map these grazing structures. The first part of this study concerns the characterization and the modeling of the archaeological grazing structures: The generation of a derived model of the DTM allows the identification of the structures. Then, the selection of a typical element by an expert enables to build a model. The second parts deals with the automatic detection process and the associated test of efficiency, by comparison with an expert approach. The results of the automatic detection are compared with manual interpretation and field walking which serve as reference databases, in order to evaluate the balance of the false/true detection of the automatic algorithm and if the data processing developed is a valuable tool to detect and map specific archaeological features.

Data and methods

Airborne Laser Scanner data and derived data set

LiDAR data were acquired by airborne on 23-march 2011 with a minimum of 18 emitted laser pulse per square meter. The field is dominated by deciduous (hazel, beech, birch) and rare isolated conifers allowing a dense proportion of hits of the ground: 11.5 grounds hits per square meter on average and a standard deviation of ± 8.9 points/m², with a minimum of 0 and a maximum of 47. The maxima point's densities correspond to overlapping areas and sectors without any trees, whereas low point densities correspond to regions covered by conifers. Finally 42 % of the studied area contains more than 10 points per m 2 , 50 % between 10 and 5 points per m 2 , 7 % less than 5 points per m 2 and 0.65 % contain no point. The LiDAR data were available as binary data files in the LAS file format, containing up to four returns per emitted laser pulse. Each return contains x, y and z coordinates in Lambert 93 (EPSG 2154), and a class label denoting ground and vegetation or building point. We selected only ground returns which were first interpolated using the ANUDEM method [START_REF] Hutchinson | Calculation of hydrologically sound digital elevation models[END_REF] and converted into a regularized raster DTM, with a 0.5 m grid resolution in the x-y plane. This gives 4 grid cells per square meter so as to preserve all the detail of bare earth point clouds.

In order to make possible the automatic detection of archaeological elements, a preliminary treatment of the DTM is essential to reveal the items of interest [START_REF] Stular | Visualization of Lidar-Derived Relief Models for Detection of Archaeological Features[END_REF]. Several methods are usable for this, such as Local Relief Model (LRM) [START_REF] Hesse | LiDAR-derived Local Relief Modelsa new tool for archaeological prospection[END_REF], hillshade with one or several direction of illumination [START_REF] Doneus | Openness as vizualisation technique for interpretative mapping of airborne LiDAR derived Digital Terrain Models[END_REF], or models based on the Sky View Factors (SVF) (Zalsek et al., 2011). For all these methods, the aim is to highlight the micro-relief, usually due to human activity.

In this study, MDOW, LRM, SKV and openness were calculated using the RVT software (Relief Visualization Toolbox, 2015;[START_REF] Zakšek | Relief Visualization Toolbox, version 1.1, Manual[END_REF][START_REF] Zakšek | Sky-View Factor as a relief vizualisation technique[END_REF][START_REF] Kokalj | Application of sky-view factor for the visualisation of historic landscape features in LiDAR-derived relief models[END_REF]. We chose LRM as the best candidate to test the success of the automatic detection algorithm because it's well suited in the case of slight relief and because it causes a negligible horizontal shift in the position of features [START_REF] Bennett | A Comparison of Visualization Techniques for Models Created from Airborne Laser Scanned Data[END_REF][START_REF] Mcneary | Lidar Investigation of Knockdhu Promontory and Its Environs, County Antrim, Northern Ireland[END_REF], which is important for the automatic localisation of the archaeological structures. The principle of the LRM computation is to apply a high pass filter to the DTM, so that only the highest frequencies component of dataset, corresponding to high altitude gradient dx dz or dy dz , which may be associated to anthropogenic landforms, are conserved. The lower frequencies due to natural relief are suppressed [START_REF] Bofinger | As far as the laser can reach…: laminar analysis of LiDAR detected structures as a powerful instrument for archaeological heritage management in Baden-Württemberg, Germany[END_REF]. A moving average filtering is applied to the DTM. This low pass filter replaces each matrix element by the average value of the surrounding elements:

           2 2 1 2 2 2 2 , 1 , 1 N n N n k M m M m k k k m n x M N
x where M represents the number of lines and N the number of columns of the filter The aim of this filter is to remove all the highest frequency components of the topographic variation, especially the ones of anthropogenic source. The choice of the filter size [MxN] is an important parameter, because it corresponds to the cut-off frequency of the filter: It has to correspond to the size of the element that we want to detect, in this case 6x6 m, the dimension of a typical elementary grazing structure. If the filtering area is too small, the anthropogenic structures will be only partly eliminated. On the contrary, if the filtering area is too large, the natural relief that we want to select will be distorted. Finally, this filtered DTM is subtracted to the initial one. The lower frequency variations are then erased and the remaining information correspond to high frequency components.

Description and modelling of the grazing structures

The figure 2 presents a typical configuration of the archaeological grazing structures structures. Each elementary structure is characterised by a sub circular depression, generally associated with an access corridor and surrounded by some ridges. The average measures are about 6x6 m for each elementary structure and 9x1.5 m for the corridor This typical configuration can however present several variations: for example the corridor may be missing or a smaller depression can be found, in the middle of the corridor. [START_REF] Roussel | Using airborne LiDAR in geoarchaeological contexts: Assessment of an automatic tool for the detection and the morphometric analysis of grazing archaeological structures (French Massif Central)[END_REF]. Due to their originality, their morphology, their global complexity and their spatial concentration, these structures are particularly well suited for the development of the automatic detection algorithm. They can be found isolated, as it can be the case for charcoal kiln [START_REF] Schneider | A template-matching approach combining morphometric variables for automated mapping of charcoal kiln sites[END_REF], but several structures are mostly associated together, with a great variety of typologies (Florez et al., 2013). Thus, a classical template matching approach may not be sufficient to detect them. The elementary structures arrangement can be another identification indicia, but as these groupings can have various sizes and shapes, they can't be identified by classical morphometric criteria. The proposed method combines information on both elementary and complex archaeological structures, in order to allow the detection of each elementary structure. The automatic detection and identification of complex archaeological structures become possible, from an a priori knowledge of elementary components of these structures. In this paper we use both general geometrical signatures of the complex structures and coupled template matching and pixel-based classification approach of its main elementary component to automatically detect them. In the rest of this article, each elementary part will be referred to as "elementary grazing structure", an association of several coalescing elementary structures being referred to as "complex grazing structure. (figure 2) In order to implement the automatic detection process, the elementary grazing structures have to be modelled. This model is synthesized, from a sub-raster chosen by the archaeologist and extracted from the LRM. The expert selects a structure considered as the more representative of the searched elements. It is a form well-preserved or barely degraded by the erosion and with a well-marked specific shape. The characteristic information of the reference structure (length, width, depth) are automatically extracted to be used for the automatic detection. A model of the elementary archaeological grazing structure is then designed, based on a clipped sinus cardinal function normalised to correspond to the reference structure dimensions and described by the following mathematical expression :

y x y x y x c z 2 2 2 2 2 2 ) sin( ) ( sin       
The obtained negative values are truncated, in order to equilibrate maximum and minimum values according to the characteristics of the reference structure:

if z < zmax then z = -zmax
The modelling process of the elementary grazing structure is summarized on figure 3.

Automatic detection process

The anomalies highlighted by the LRM can now be detected automatically. The first step consists in the binarization and segmentation process, based on two complementary segmentation stages: all the matrix element corresponding to positive LRM values (relative elevation above the local mean) of at least 33 % of the maximum elevation value of the LRM are selected. The coalescing elements obtained are then merged together and interpreted as potential interesting element. The same process is applied for the segmentation of elements with negative LRM values (relative elevation under the local mean). The second step consists in detecting all the objects that could be associated to a human activity, i.e. characterised by a high gradient. The third step is to classify them basically in four classes, based on their planar shapes:  Narrow linear elements with a negative relative altimetry (topographic depression) and interpreted as trails, pathways or deep gullies  Narrow linear elements with a positive relative altimetry and interpreted as small plot walls and ridges  Smalls and compact elements, with a size lower than half the one of the reference structure, interpreted as artefacts and eliminated by an erosion/dilatation process  The remaining objects, interpreted as potential grazing archaeological structures.

Two detection processes are then carried out in parallel :

A pixel based detection is implemented, based on morphometric characteristic of the structures. The potential complex structures, i.e. groups of nested elementary items are detected. These groupings are complex to identify, because they can contain a various number of basic elements, and so have variable dimensions and geometric configurations. A set of three general features have to be evaluated to characterise a complex structure: a) each candidate must have some hollow parts surrounded by element in relative elevation, leading to high elevation gradient in the LRM.

b) the minimum size of each element must be at least equal to the one of the reference structure Then, all the hollow parts being inside the complex structures and having dimensions consistent with the ones of the model are selected and interpreted as potential elementary structures.

In parallel, another step is necessary to focus on the researched archaeological structure, by carrying a template matching approach [START_REF] De Boer | Using pattern recognition to search LIDAR data for archeological sites. In The World is in Your Eyes[END_REF][START_REF] Schneider | A template-matching approach combining morphometric variables for automated mapping of charcoal kiln sites[END_REF]. A moving cross-correlation is realised between the model previously defined and the whole studied area. For each point with coordinates [i,j] of the LRM, the cross-correlation coefficient is defined as :

      ) , ( ) 2 / , 2 / ( , 1 1 2 / 2 2 / 2 1 1 LRM j j i i LRM ref N j N i ref j i Corr i i j j N N i j i N N j              
where: Corr is the result of the cross-correlation Ref correspond to the reference object (model) LRM is the whole Local Relief Model ref is the mean value of the relative elevations for the reference object LRM is the mean value of the LRM relative elevations in the analysis window, the size of the reference object Ni is the width of the model Nj is the height of the model The figure 4 shows the result of the cross-correlation process on a small area. It turns out that even if correlation peaks match well the grazing structures elementary cells, some high values of the correlation coefficient also correspond to other elements, like lanes or access corridors fragments.

Fig. 4. Visualization of the archaeological grazing structures (a) and of the associated correlation peaks (b)

These results, obtained on a small area allow defining a minimum correlation rate for the detection. In our case, this limit value chosen for the acceptable correlation rate is 60 %. Our choice was to favour the completeness of the diagnostic, rather than its accuracy. The reason of this choice will be explained in the discussion. At last, the two approaches are merged, in order to limit the number of artefacts: only the elements detected by the two complementary approaches are retained. Elements characterised by a high correlation rate with the model but not included in a complex structure can then be suppressed. The characteristics of the selected elements (centroid coordinates, length, width, depth, correlation rate with the model) are then automatically extracted and stored in a database.

The figure 5 summarizes the algorithmic approach implemented for the automatic process in MATLAB® environment. The computation is carried out on a laptop computer with Intel® Core i7-3720QM processor. The total computation time, for the detection of all the elements and the storage of the associated information in the database is 214.79 s

Testing the efficiency of the automatic detection process

The quality of the automatic detection was tested, using a comparison between the grazing structures detected automatically and the result of an expert detection. In a first step, a map of the true elementary grazing structures, which serve as reference, is produced. The mapping work is based on the digitization of each element using common visualisation tools (DEM, multi-direction hillshading and local relief models) within a GIS environment. Fieldworks were also performed to confirm the location of grazing structures using a handheld GPS (Geoexplorer XT) enabling decimetric precision.

In a second step, the pixel by pixel comparison (resolution of 50 cm) between the expert mapping and the results of the automatic detection allows the construction of a confusion matrix which count the number of pixel of the four possible outcomes: true positive (successful detections of structures), false negative (undetected structures), true negative (correct detection of the absence of structure) and false positive (erroneous detections of structures).

Fig. 5. Flowchart of the approach implemented for the automatic detection process

The confusion matrix enables the calculation of common performance metrics of the automatic detection process [START_REF] Fawcett | An introduction to ROC analysis[END_REF][START_REF] Kim | Automated crater detection, a new tool for Mars cartography and chronology[END_REF]. Four parameters are then computed:

 the sensitivity is the probability that the detection result is positive when the structure is present:

 the specificity is the probability that the detection result is negative when the structure is not present:

 the positive predictive value (PPV) is the probability that the structure is present when the detection result is positive  the negative predictive value (NPV) is the probability that the structure is not present when the detection result is negative:

Results and Discussion

3.1. Efficiency of the automatic detection process.

The quality of the automatic detection process is now evaluated at the scale of the structure and at the scale of each pixel. The table 1 gives the results of the comparison between the expert approach and the automatic detection, in terms of number of elementary structures. From the structures point of view, the automatic detection process locates 282 grazing structures whereas the results of the expert mapping and fieldwork count 225 features in the study area. This difference is due to erroneous detections (76 elements are misread as archaeological grazing structure) and to undetected structures (21 elements). 204 detection are classified as successful (automatic detection validated by the expert), representing 90.7% of the actual archaeological grazing structures. The table 2 gives the values of the quality indicators computed, in terms of number of pixel. The values of the sensitivity and specificity metrics (respectively 0.919 and 0.999) indicate that the algorithm is efficient for the detection and the location of grazing structures. More precisely, the positive predictive value (PPV) and the negative predictive value (NPV) (0.792 and 0.999 respectively) express the ability of the algorithm to locate grazing structures with a higher amount of erroneous detection (false positive) than undetected features (false negative). A total of 2712 pixels are classified as false positive and correspond to 76 topographic marks which are not grazing structures. By contrast, the number of undetected grazing structures remains relatively low, 910 false negative pixels corresponding to 21 undetected features Almost the totality (94.7%) of erroneous detections is related to archaeological or anthropic features (figure 6-A). They are mostly surrounding fragments of detected "tras" which are interpreted as independent grazing structures, like corridors (n=34) and eroded ridges (n=7). The remaining erroneous detections are modern topographic features like trails parts (n=15) and recent structures (n=16) as circular excavations for military training. Only 4 erroneous detections are attributed to natural depressions. The undetected grazing structures mostly correspond to strongly eroded features with smoothed ridges and partially filled hollows (figure 6-B). Furthermore, coalescent "tras" are detected as single structure five times, leading to the underestimation of the grazing structure count. Moreover, mapping of the results do not show distinct spatial patterns for successful, erroneous and undetected structures. It suggests that the global variation of the terrain morphology does not influence the algorithm efficiency [START_REF] Roussel | Using airborne LiDAR in geoarchaeological contexts: Assessment of an automatic tool for the detection and the morphometric analysis of grazing archaeological structures (French Massif Central)[END_REF].

Table.1 Results of the elementary structures detection

Discussion

The principle of automatic detection already exists since several years in industrial context [START_REF] Rabbani | Efficient Hough transform for automatic detection of cylinders in point clouds[END_REF][START_REF] Pourreza | Automatic Detection of Eggshell Defects Based on Machine Vision[END_REF][START_REF] Tang | Automatic detection and tracking of human heads using an active stereo vision system[END_REF][START_REF] Fazlollahi | Automatic detection of small spherical lesions using multi-scale approach in 3D medical images[END_REF]. The application to LiDAR data is much more complex, for two main reasons. First, the quality and the resolution of the digital terrain model is generally insufficient to allow a precise description of the searched pattern. In our case, the elementary structure is defined by only about a hundred pixels, whereas a classical low definition image used in industrial vision context contain at least one million of pixels. The consequence is that some elements appear sometimes distorted or fragmented, making their identification difficult. For example, paths are theoretically easy to identify, because of their linear characteristic. However, if they appear truncated, as a dotted line, each elementary part will be interpreted as standalone object. In the case of the archaeological grazing structures, the hollow part (the black pixels of the LRM) can exhibit very different shapes, even for structures with the similar size and functionalities. The figure 7, showing the result of the automatic detection, illustrates this problem. The detection process, based on finding elements characterised by enough similarity with a model, has to take into account this inaccuracy. If the degree of similarity imposed is too high, the more eroded or atypical elements won't be detected. On the contrary, if the degree of similarity imposed is too low, the number of erroneous detection will increase dramatically. It is so necessary to establish a clear detection strategy, to optimize the dilemma between the accuracy and the completeness of the algorithm. The aim is indeed to limit the number of artefacts, but especially not to forget any element, even if it's a little bit different from the model. The choice presented in this paper is to give priority to completeness, because it is easier to remove inappropriate elements from a database than complete this database with all the characteristic of the forgotten items. [START_REF] Toumazet | Automatic detection and characteristics extraction of archaeological structures using coupled Geographic Information System software and Scilab[END_REF]. But this choice is arbitrary, and it is possible to focus on the accuracy, especially if the searched elements are precisely defined. The proportion of undetected grazing structures revealed by the performance indicators and compared to erroneous detection depends on the degree of similarity expected with the model. The values obtained in this study correspond to the chosen strategy to be as exhaustive as possible on the actual structure detection, even if it causes an increase of improper detections.

Two parameters allow adapting the compromise between accuracy and completeness: the tolerances on the characteristic dimensions of the structures and the correlation rate with the model. It is important to note that the value of the correlation rate give important information on the degree of resemblance with the model. The result of the automatic detection process is thus not only binary (it is an element of interest or not), but, for each of the retained elements, it indicates the reliability of this detection. It is then possible to create classes, with an associated range of probability to correspond to the researched archaeological landform.

This consideration implies a question about the choice of the model. It has an important consequence on the result of the detection process. The question is: "What is the best model to detect all the archaeological structures?" The natural trend is obviously to choose an element as "perfect" as possible, but maybe it won't be the most adapted to detect eroded elements. For the detection step based on the correlation with the model, we chose to simplify the model as much as possible: the structure is then represented by a circular depression surrounded by a higher relative elevation area (figure 3). Another approach to explore, in further investigations, is to use several models (closer from the actual archaeological elements), reflecting the different typologies or degrees of conservation of the structures. In this approach, after the first step of selection of potential element of interest, a multi-model correlation would be carried out, in order to detect the archaeological structures, but also to classify them according to their correlation rate with each model. The probability of belonging to each class would then be computed, and the confidence level of this classification for each element would be evaluated, helping the archaeologist for the validation work.

The automatic detection of archaeological remains from LiDAR data set is a new tool to help archaeologists, just like it was for GIS and spatial analysis in the early 2000s. The aim is not merely to create a "press-button" tool but to promote a close cooperation between the archaeologist and the computer engineers. The efficiency of the pattern recognition algorithm is strongly dependent on the archaeological landforms features. This means that this tool can be successful only if the model selected to feed the algorithm is relevant, i.e. with a well characterized morphological signature that only the archaeologists are trained to find and interpret. In addition, this tool is only relevant when it is applied to large areas survey with a high number of similar structures. For examples, charcoal places, shell holes, or "tras" are good candidates for automatic detection. Validation of the results by an archaeologist will be always required, but the identification and classification work can be greatly facilitated by the upstream automatic analysis.

Conclusion

The use of LiDAR derivative dataset is now widespread in archaeological context. This paper is focused on the development of a methodology involving the automatic detection of grazing archaeological structures. Anthropogenic elements can generally be detected because of their high altitudinal gradient signature, compared to most of natural items. After filtering, the natural relief with the Local Relief Model technique, the elements identified as potential grazing archaeological structures are isolated and classified according to recognition algorithms. The quality and the limits of the automatic detection have been discussed, comparing the results with an expert approach. The results indicate that the proposed method is efficient for the detection and the location of grazing structures. They are obtained with a simple model for the sought structure. The idea is now to work on a more elaborate model, including several conservation status examples. This solution would allow a more exhaustive detection, and above all to give information on the typology of each element. This tool offers the potential to automatically produce a database of all sites. Future studies will now deal with a more detailed description of the structures, with an automatic extraction of their geographical and morphological characteristics. The aim is to undertake a quantitative analysis of forms that encompasses size, shape and orientation, and perform a spatial analysis of their distribution. With the increasing number of LiDAR surveys, there are real benefits to develop improved algorithms for remains detection, but the fieldwork knowledge and experience will remain essential to advise and to guide the development of computer tools.

Fig. 1 .

 1 Fig. 1. Study site location in the French Chaîne des Puys and localisation of the investigated zone where the LiDAR data where used for the automatic detection validation

Fig. 2 .

 2 Fig. 2. Typology of the grazing structures showing their main characteristics. aerial photography of archaeological grazing structures (Cezallier) (a), Local relief Model of a small part of the investigated zone (b). The red parts represent what we call "elementary archaeological grazing structures", surrounded by some "ridges" and sometimes associated with an "access corridor". All of these elements belong to the "complex archaeological grazing structures".

Fig. 3 .

 3 Fig. 3. Process of creation of a model of the archaeological grazing structure : choice of a representative element (a), extraction of its characteristics (b), creation of a numerical model (c)

Fig. 6 .Fig. 7 .

 67 Fig. 6. Types of erroneous detections (A) and types of undetected structure (B)

Fig. 8 .

 8 Fig. 8. visualisation of the results of the automatic detection : complex structures in green and elementary structures in red (a), example of undetected elements and illustration of the variability of the shape for the elementary grazing structures (b)

Table . 2

 . Quality indicators at the pixel scale

	True positive	True negative	False positive	False negative
	10328	8414757	2712	910
	Sensitivity	Specificity	PPV	NPV
	0.919	0.999	0.792	0.999

Acknowledgements

The work presented in this paper is a part of an interdisciplinary research program, called "Lidarcheo". The authors gratefully acknowledge the support of Clermont Communauté for the funding of this project and the support of the Centre Regional Auvergnat de l'Information Géographique (CRAIG) for the funding of LiDAR data. Authors thank Marta Florez for her support as archaeological expert and Marlene Faure, Mohamed Abadi and Stéphane Petit from Veodis-3D company, for their contribution to LiDAR data processing.


domain: spi info math

text:
Saint-Clair T Toguem
email: stoguemt@ens-paris-saclay.fr

Charyar Mehdi-Souzani

Nabil Anwer

Hichem Nouira

Customized design of artefacts for additive manufacturing

Keywords: Artefact, Additive Manufacturing, GD&T, Design guidelines

Additive manufacturing (AM) artefacts are test parts used to optimize and assess accuracy and limitations of AM systems and processes. There are several artefacts developed for AM. However, few of them are provided with complete details on the general design method used for tolerance evaluation. Also, before starting a batch production with metallic AM systems, manufacturers need to make sure that AM system's GD&T (Geometric Dimensioning and Tolerancing) capabilities fit their requirements. This can be achieved with a customized artefact designed for the evaluation of specific GD&T characteristics. This paper follows a synthesis of the common practices in AM artefact design methods. The aim here is to introduce a detailed AM artefact design method for GD&T characteristics evaluation. Based on existing design concepts, the proposed approach sets up a design guideline starting from requirements definition, to the final test part. A case study is also detailed to evaluate the general GD&T accuracy capabilities and limitations of a metal PBF system. A test part is designed, built and the AM system's characterization is performed.

Introduction

In the literature two main methods are proposed to improve AM systems and processes accuracy. The first is based on the measurement of identified characteristics directly on AM machines (online or offline metrology). This method is challenging and includes several difficulities such as the accessibility of the system's components, safety issues and technological limitation of measurement systems. The second method is based on the use of conventional measuring machines and techniques for measurement and characterization of test parts named artefacts. Currently, the second method is the most used for performance evaluation of AM systems and processes [START_REF] Moylan | An Additive Manufacturing Test Artifact[END_REF] [START_REF] Chang | Geometric element test targets for visual inference of a printer's dimension limitations[END_REF]. One advantage of the second method is the possibility to efficiently compare several AM systems and processes.

Several artefacts have been developed in the literature but the design methods used are as different as their design purposes [START_REF] Toguem | A review of AM artifact design methods[END_REF]. Also, there are few papers providing all the necessary details for AM artefact design and none of them provides a complete and detailed design guideline starting from the design purpose to the final printed part.

There are recent works conducted by the ISO technical committee on AM and the ASTM for standardization issues in AM artefacts. However, there is currently no standard artefacts introduced by standards organizations. Morover, even in case a standard artefact would be introduced, due to a large variety of AM systems and processes and other factors like available measurement systems, it can be difficult for a single artefact to be suitable for all AM systems and processes. Consequently, there exists several other artefacts designed based on specific requirements or constraints. This can explain why authors like Rupal et al [START_REF] Rupal | Feature -Based Methodology for Design of Geometric Benchmark Test Artifacts for Additive Manufacturing Processes in 28th CIRP Design[END_REF] are claiming that a standard artefact is not practically advisable and it is appropriate to consider a standard AM artefact design method.

The present work proposes a detailed design method focused on GD&T characteristics. The aim here is to introduce design guidelines that could help both for the design of customized AM artefacts and for the establishment of standards for AM artefacts.

Section 2 details the proposed AM artefact design method from the design requirements definition to the design guidelines description. Section 3 shows an implimentation of the design method through a case study.

Artefacts design method

Requirements definition

The analysis of the literature shows that there are two global approaches for artefacts design requirements definition. The first is the oldest and most used. It has been proposed by Jacobs and Richter and focuses directly on the features of the test parts and their shapes when defining design criteria. Many test parts have been developed based on this approach [START_REF] Toguem | A review of AM artifact design methods[END_REF] [5]. It suggests some requirement solutions as design criteria and is therefore restricting the scope of solutions for the designer and does not always lead to an optimal solution. For example, Jacobs and Richter's approach suggests that artefacts should include enough features for repeatability evaluation. However, as highlighted by Moylan [START_REF] Moylan | An Additive Manufacturing Test Artifact[END_REF], repeatability cannot be efficiently evaluated by repeating multiple identical features on the artefact because the system performances also depend on the location on the building surface. This can explain why most of the proposed artefacts based on Jacobs and Richter's design criteria are further criticized and ameliorated [START_REF] Toguem | A review of AM artifact design methods[END_REF]. The second approach proposed by Moylan et al [START_REF] Moylan | An Additive Manufacturing Test Artifact[END_REF] cope with this problem by defining new design requirements. However, the defined requirements need to be completed [START_REF] Toguem | A review of AM artifact design methods[END_REF].

Thus, the first step of our design approach consists in a mapping of Jacobs and Richter design criteria into design requirements. The purpose is to be precise, concise and avoid to suggest solutions while defining design requirements. These design requirements are then completed by Moylan design criteria and lead to a set of 18 design requirements which are to be used as inputs by the designer in the design process.

Design guidelines

The design method is an iterative approach starting from the design requirements previously defined. These requirements are classified according to the design purposes and the performances to be evaluated. The main requirements are then highlighted and their corresponding elementary requirements are grouped into modules of dependent requirements. Solutions are then chosen for each module including features selection, their sizes and orientations. The next steps are guided by the chosen solutions in order to obtain a final artefact fulfilling all the design requirements. Features are arranged and the CAD model is designed. The part is finally built, measured and the system is characterized (see Figure 1). If a problem occurs during the building process, the designer will either re-build the part or go back to the previous steps and change the design solution. In the requirement classification step, the designer first affects a flexibility level to each requirement to specify if the requirement is imperative or negotiable. This helps identifying requirements that are unnecessary to consider and thus avoiding them in the next steps. Requirements are then ranked by comparing them. This leads to a ranking and an identification of preponderant requirements. The result of this step depends on the design purpose, the system to be evaluated and the AM process.

In order to optimally choose solutions, requirements are grouped into modules based on the relationship between them. This leads to the definition of one solution for a set of requirements (e.g. a cube feature can help evaluate flatness, straightness, perpendicularity, surface texture and internal homogeneity of the built part). Grouping requirements into modules avoids unnecessary features and thus minimizes resources consumption (time and material). The choice of solutions includes features selection. Features sizes and orientation are then defined according to the design purpose and the measurement system constraints. This step depends on the available resources and the designer's experience and knowledge of the AM system and process to be evaluated.

For the arrangement of features, Buyn and Lee [6] proposed an approach to avoid redundancy while assuring system's performance evaluation along all the axis. Features arrangement must also consider features accessibility for measurements. Thus for an artefact designed for a specific use, measurement systems available need to be known. Their functioning and main characteristics (probe, the size of the measuring surface, etc.) also need to be considered. If the artefact is designed for a global use, features must be arranged to be as accessible as possible by any of the common measurement systems.

Once features are arranged, the CAD model of the artefact can be created. Before being transferred to the AM machine for the build, the CAD model needs to be converted into a specific file format (STL, AMF, etc.) and this step is thus subject to geometric and file conversion errors [7] [8]. It is highly recommended to check the converted file before sending it to the printing system to reduce geometric errors. The artefact can then be printed, measured and the system can be characterized.

Case study

The aim here is to evaluate the geometrical performance of an AM metal SLM (Selective Laser Melting) system. The study neither deals with fit for assembly considerations nor linking errors with their causes. In order to avoid measurement systems limitations, it is assumed that suitable measurement systems are available. However, the final artefact should deal with features accessibility optimization.

Artefact design

After classifying the input design requirements, some of them related to "fit for assembly consideration" and "linking errors with their causes", are not considered according to the initial assumptions of the problem.

Requirements are then ranked among each other. It comes that according to the initial design purpose, the preponderant requirements are related respectively to form, orientation and dimensional accuracy evaluation, measurement systems limitations and digital chain errors minimization.

Elementary requirements grouping leads to an optimal choice of solutions. For form, orientation and dimensional tolerance requirements, linear and planar features (flatness, straightness, linear/planar orientation and spatial repeatability, etc.) are grouped into different modules according to the machine's axis assessed. Also, for circularity, different modules are defined depending on the evaluated axis. Other modules are defined for coaxiality, for minimum feasible size and complex shape both extruded and holed. For each module one feature is chosen and repeated if necessary for spatial repeatability evaluation. Alternatively, features chosen as solution are used to assess other performances (related to location, dimensions, surface texture, internal structure of the material, etc.).

As shown in Figure 2, the test part consists in a set of features arranged on a base plate. A base plate is chosen for features arrangement to limit post-processing errors. The base plate facilitates handling and avoid features from warping during post-processes (extra-material removal, separation from the supports and building plate). Table 1 gives a brief description of the characteristics investigated by each feature of the proposed test artefact. Figure 3 provides an overview of the artefact's dimensions.

Building, measurement and qualification

The building strategy was a contouring coupled by a hatching to fill layers. The laser power was 190 W and 201W respectively for the contouring and the hatching. It is important to notice that the build plate was not preheated, this causes nonuniform heat distribution in the part during the building and thus increases defects on the test part. The temperature of the build chamber was set between 20 °C and 60 °C with a pressure between -10 mbar and 10 mbar. The material is NC718 (Inconel alloy 718), a Nickel alloy and the layer thickness was set to 40 µm. The building time was around height hours. Figure 4 shows the built artefact on the build plate. Measurements have been performed using a CMM with a Kreon laser-plan scanner. The collected data are cleaned to remove measurements noise and filtered to have a uniform density. Then a global inspection of the part is performed to match the measured part with its CAD model. Figure 5 shows that the average deviation from the CAD model is under 1.6 mm and that hollow features are less accurate than extruded features. Global inspection reveals important defects on overhanging features due to the lack of support structures (Figure 5 and Figure 6). This can be caused by thermal deformation occurring during the building.

To compute form and orientation deviations, a CMM with a contact stylus have been used. Deviations were evaluated according to ISO GPS standards. Processing of measurement data shows achievable accuracy (e.g. flatness of 0.01 mm for vertical planes).

Conclusion

Artefacts can be used to accurately evaluate AM systems and achievable tolerances to efficiently characterize and optimize them [6] [9] [10]. Several test parts have been developed in the literature. Among them, some test parts have been designed for standardization issues. However, few of them are provided with complete details on the design method.

In this paper, a detailed AM artefact design method has been presented starting from requirements definition to the final artefact. The design method uses tools from design theory and methodology such as module grouping to optimize the number of features and their orientation. Requirements classification is used to highlight the preponderant requirements on which the designer should focus on. Buyn and Lee's [6] features arrangement methods have been used to optimally arrange features on the test part. A case study is developed with the aim to evaluate the overall geometric accuracy of a metal SLM system. A 73.8x68.85x16.65 mm artefact is designed and printed.

Further work should focus on enhancing the proposed design requirements and solutions, developing and assessing the method for specific performance evaluation for industrial cases. Concerning the case study, the proposed artefact should be built and measured several times to evaluate the system's repeatability and to validate the results. Another interesting issue is the integration of thermomechanical deformations of the part to verify some critical designed features.

Figure 1 .

 1 Figure 1. Design flowchart

Figure 2 . 1 .Figure 3 .

 213 Figure 2. 3D model of the designed artefact

Figure 4 .

 4 Figure 4. Built test artefact on the build plate; Z-axis is the build direction.

Figure 5 .

 5 Figure 5. Global inspection of the measured test part

Figure 6 .

 6 Figure 6. Building errors on hanging features : (a)= features IEF16, (b)= features EF4