M Makki

C Lartigue
email: lartigue@lurpa.ens-cachan.fr

C Tournier

F Thiébaut

Direct duplication of physical models in discrete 5-axis machining

Keywords: Tool path generation, Area-by-area machining, Point cloud Segmentation

This paper deals with the feasibility of direct duplication of physical objects as regards a classical approach based on Reverse Engineering. The object surface acquisition is performed using optical devices. Algorithms for tool path generation directly from the cloud of points have been developed in 3-axis machining. A n-buffer simulation completed by the real machining emphasize that direct duplication is efficient in terms of conformity to the geometry. As the surface reconstruction step is removed, the proposed process is faster and simple to implement. The last step is concerned with the extension to discrete 5-axis machining. The main issue is related to the determination of the part set-ups and the corresponding point cloud segmentation.

Introduction

Physical object duplication is nowadays an important issue for it permits to recreate hand-made objects or prototypes. Most methods for physical object duplication rely on Reverse Engineering (RE).

The process basically consists of three majors independent steps: (1) data acquisition using 3D digitizing;

(2) CAD model construction from the data points and (3) NC tool path generation from the CAD model (OuYang et al., 2005).

The step of data acquisition consists of measuring the physical object using non contact digitizing systems such as 3D laser scanners. This generally provides a large cloud of points representative of the object's surfaces. The process of converting data points into a usable CAD model (also well-known as RE) includes various phases: data pre-processing, data segmentation, data fitting, and final model construction [START_REF] Varady | Reverse Engineering of geometric models -an introduction[END_REF]. Despite the advances in CAD modelling of discrete data and the new RE software systems now available, this step is seldom automatic. It is generally time-consuming, tedious and the quality of the resulting surface strongly depends on the possibilities offered by the software, in particular in the area of segmentation and precision surface fitting for complex objects [START_REF] Feng | Iso-planar piecewise linear NC tool path generation from discrete measured data points[END_REF]. The obtained CAD model thus constitutes an approximation, more or less correct, of the digitized data. Concerning NC tool path generation, many robust methods exist for continuous surfaces applicable in 3-axis machining as well as in 5-axis machining. However, as the calculated tool path is also an approximation of the CAD model, the combined procedure suffers from error accumulation and inefficiency [START_REF] Feng | Iso-planar piecewise linear NC tool path generation from discrete measured data points[END_REF].

As the stage of RE is a restraint to automation and precision of the process, recent research has addressed the issue of direct duplication. Direct duplication consists in generating tool path machining directly from data points. In the last decade, several investigations have been made in this direction.

The first method reported is the work by Lin and Liu [START_REF] Lin | Automatic generation of NC cutter path from massive data points[END_REF]. Authors create a rectangular mesh, a Z-map, from the digitizing lines obtained with contact or non-contact measuring devices. The rectangular mesh is oriented according to the driving measuring direction, and is the support for tool path generation. Park and Chung [START_REF] Park | Tool-path generation from measured data[END_REF] proposed a method for both roughing and finishing. Rough machining is performed slice by slice. Taking advantages of the digitizing lines, authors defined finishing tool paths as a series of point sequence curves. When the collected points form an inhomogeneous cloud of data, their algorithms can not be applied. [START_REF] Feng | Iso-planar piecewise linear NC tool path generation from discrete measured data points[END_REF] present a method to generate tool path for which machining error and surface finish are explicitly considered. A CL-net (Cutter Location net) is created which consists of 2D cells sequentially ordered. The size of the cell net is defined relatively to the machining tolerance (for its length) and the maximum scallop height allowed (for its side size). Each cell node corresponds to a CL point. Due to the absence of continuity, authors evaluate machining errors based on two adjacent tool swept surfaces of the ball-end cutter tool. An optimization method of the position of the cell node is thus proposed to minimize the machining error. More recently, Teng et al [START_REF] Teng | generating tool paths from point cloud data via machining area segmentation[END_REF] introduced the concept of area by area machining of complex parts in order to increase machining efficiency. The point cloud is segmented in function of the geometric complexity of points. The latter is defined considering local curvature, and possible gouging. Therefore, points with the same complexity are grouped together to form distinct machining areas. Tool paths are generated for each machining area using the method developed in authors' previous work [START_REF] Feng | Iso-planar piecewise linear NC tool path generation from discrete measured data points[END_REF]. However, the point cloud proposed for illustration comes from the sampling of a CAD model, and not a real part digitizing. Peng and Ying [START_REF] Peng | Direct tool path regeneration for physical object modification from digitized points in reverse engineering[END_REF] have handled the issue of tool path regeneration if a modification in the design process must be taken into account. The authors assumed that the original tool path is generated from B-spline surfaces constructed by selecting some measured points as control points. With the base of Bspline surfaces, only modified regions are identified and corresponding tool paths are easily regenerated. In their work, Ou Yang et al [START_REF] Ou Yang | Determining gouge-free ball-end mills for 3D surface machining from point cloud data[END_REF] exposed the algorithm they have developed to automatically select an optimized cutter-tool size for 3-axis ball end milling of a point cloud. Algorithm efficiency was merely tested using simulated point cloud data sets. Concerning 5axis machining, the approach developed in [START_REF] Chui | Direct 5-axis tool-path generation from point cloud input using 3D biarc fitting[END_REF] is interesting. Authors based their method on a 3D triangular mesh construction directly from the cloud of points. For each facet, the local normal is following obtained using the facet and its neighbours. The axis tool is thus oriented from the normal using a value of the tilt angle set by the user.

Therefore, literature mentions little work for tool-path generation on large clouds of points obtained by the digitizing according to various sensor configurations. Indeed, in this case, collected points form a large cloud of points, non-ordered, dense, noisy, and inhomogeneous. Moreover, few approaches address the problem of discrete 5-axis machining directly from the cloud of points without surface or meshing reconstruction. For each part set-up, the portion of surface accessible by the tool (most generally a ball-end cutter tool) is machined using 3-axis machining algorithms. The issue is to find the minimal number of set-ups allowing the whole surface to be machined.

With the objective to machine large point clouds, dense, inhomogeneous, noisy and incomplete, we have proposed algorithms for tool path generation that evolved from 3-axis machining [START_REF] Osty | Free-form copying from point clouds; A tool-path calculation method using B-Spline interpolation[END_REF] to discrete 5-axis machining [START_REF] Breteau | Towards an approach for rapid copying of freeform surfaces in 5-axis machining[END_REF]. The paper deals with the presentation of those algorithms in the context of direct duplication of physical objects. Hence, a specific attention is given to show the efficiency of direct duplication as regards classical methods of duplication based on surface reconstruction (RE). The paper is organized as follows. Section 2 presents algorithms of tool path generation in 3 axes from massive data points, integrating both the roughing and finishing operations. No meshing or continuous surface construction is necessary. An illustration of direct duplication of a complex physical object is exposed. A comparison is done with a classical method of duplication relying on RE. Section 3 concerns the extension to 5-axis direct duplication. As discrete machining is used, the first step aims at finding points that can be machined with the same tool orientation, defining thus a part set-up. This involves determining tool visibility and accessibility. The following step concerns the point cloud segmentation into areas, each one corresponding to a part setup. Each area is machined in 3 axes using algorithms exposed in section 2. The application proposed in section 4 highlights issues that required specific developments and optimization. The paper is ended by some conclusions.

Tool path generation in 3-axis ball end-milling for direct duplication

As the objective is to produce a copy of an existing object, based on data points collected on the physical object surfaces, the main issue is tool path generation directly from discrete data, including both roughing and finishing milling operations. Although there are many methods for tool path finishing trajectories, a few ones address the specific case of roughing. Lin and Liu [START_REF] Lin | Automatic generation of NC cutter path from massive data points[END_REF] have proposed a method based on the classical Z-level roughing method. In order to overcome, difficulties linked to the huge amount of data, and the lack of continuity their work relies on a structure of the data through a Z-map calculated from the digitizing lines. Hence, to be efficient, algorithms for tool path generation requires a structure of the data.

In the present section, we propose a methodology for 3-axis milling duplication which encompasses roughing and finishing. For both milling operations, algorithms developed take advantages of a voxelisation of the data, which consists in splitting up the cloud points into cells, so that each cell contains a minimum of points. As only non-empty cells (or voxels) are considered, attributes linked to points included in the space of the voxel can be calculated, and associated to each voxel. The barycentre of the points and the normal to the least-square plane that best-fits the points included in the voxel are the most useful attributes for tool path generation. Therefore, voxelisation gives data structure, pseudo-continuity and a lightened representation which will facilitate further calculations.

Roughing

The Z-level strategy is adopted, for which the roughing is performed layer-by-layer, in a direction perpendicular to the Z-axis tool. In each level (or layer) Zi, the machining mode is the "zig-zag" mode, and the trajectory Ti is calculated according to the roughing parameters (Figure 1).

Figure1. Roughing strategy

For this purpose, the voxelisation of the data is carried out as regards those parameters. The voxel height corresponds to the cutting depth. In each layer, a grid (X,Y) is built. The longitudinal step is defined in the feed rate direction whereas the transversal step corresponds to the step over. Those parameters provide the quality of the milled surface as regards machining time. Grid nodes n ij are organized in function of the sweeping direction adopted. For each node n ij, interferences between the tool and the barycentre of the neighbour voxels are checked. Nodes which are interference free define points of the trajectory Ti for the layer Zi. For each point in interference, an off-machining trajectory is inserted to avoid collision with the part (Figure 2).

Figure 2. Resulting roughing trajectory

The link between trajectories is ensured thanks to off-machining trajectories. To avoid tool damages, axial plunges are forbidden, and the tool must follow a ramp (Figure 3): the tool plunges down to the level Z i-1 , then it follows a slope down to the level Zi.

Figure 3. Ramp mode approach

The previously described algorithm has been implemented using Matlab. As the verification of interferences are not yet managed for ramp mode approach, only the machining of part without internal pockets is allowed, which is convenient for the complex free-form parts tested. An illustration will be proposed in section 2.3.

Finishing

The finishing operation is a classical 3-axis ball-end milling. The method we have developed for tool path generation relies on the z-buffer inverse method [START_REF] Suzuki | Development of the CAD/CAM System based on parallel processing and inverse offset method[END_REF]. As for roughing, a grid in the xy-plane is built the dimensions of which are linked to the classical machining parameters, the machining tolerance Mt, and the maximum scallop height allowed, hm. The ordering of the grid nodes is processed according to the machining strategy. Let R be the tool radius, for each grid node K ij , a tool positioning is calculated as follows (Figure 4) [START_REF] Breteau | Towards an approach for rapid copying of freeform surfaces in 5-axis machining[END_REF]:

1. Collect the points P k belonging to the point cloud that are included in a cylinder the radius of which is R, and which axis is the Z-axis passing through the considered node.

2. For each point P k , calculate the intersection Z k between the Z-axis and a sphere of radius R, centred at the point.

3. Tool positioning CL ij is defined by the maximal Z k value. For the first implementations, grid parameters are chosen uniform; the final result is thus not optimized as regards part quality. Indeed, in order to avoid facets, the grid parameter is determined in function of the most discriminating areas of the point cloud as regards the chord deviation criterion. This involves over-quality for other portions. To overcome this problem, a solution should be the use of an adaptive longitudinal step. In such a case, a maximum distance is imposed between two successive points of the trajectory instead of two successive nodes of the grid. The integration of this solution is presently in progress.

Comparison with classical methods based on RE

In this section, we propose to compare the efficiency of direct duplication with regard to a classical approach based on RE. The comparison aims to assess the relevance of direct duplication vis à vis the classical RE methods, especially in terms of rapidity and fidelity.

A mask, the CAD model of which is unknown, is first digitized using a laser-scanner mounted on a CMM. Three different orientations are used leading to 470 000 points. The completeness is ensured by using an automated scan planning strategy [START_REF] Mehdi-Souzani | Scan planning strategy for a general digitized surface[END_REF]. In order to lighten the point cloud, a filtering operation based on the chord error is applied, leading to 170 000 points (Figure 5a).

Both approaches are thus conducted in parallel.

For the RE method, the surface is reconstructed using the module Quick Surface Reconstruction of CATIA V5®. The point cloud is split into sub-sets to which a patch is associated. All the patches are therefore linked together, and remaining holes are filled so that the final surface is at least C0 continuous (Figure 5b). In order to decrease processing time, a scaling factor of 7/20 is applied to the surface. Tool paths are afterwards generated from this surface using the module Advanced Machining of CATIA V5®. Roughing is performed starting from a raw material, which dimensions are:

100mmx100mmx60mm, and using a cylindrical tool the radius of which is D R = 10mm.The finishing stage is carried out according to the parallel plane strategy. Machining parameters are reported in Table 1.

Tool diameter:

D= 8mm

Machining tolerance:

Mt = 0.01mm
Feedrate:

Vf = 5 m/min
Max. Scallop height:

hm = 0.01mm
Table1. Machining parameters

The part machining is carried out on the milling centre of the laboratory: Mikron UCP 710 equipped with a CN unit Siemens 840D. In order to smooth trajectories, a real-time polynomial interpolation is applied with a tolerance of 0.01mm.

As direct duplication is concerned, the same scaling factor is applied to the point cloud. Tool paths are generated using the algorithms described above. Tool diameters are identical to those used for the RE method. For the roughing operation, the voxel size is chosen equal to 2mm, which defines the cutting depth and the longitudinal step. As the tool diameter is D R = 10mm, the step over is given by D R /2. In order to avoid possible tool breaking and to uniform the material remaining before finishing, a semifinishing operation is performed. Trajectories for semi-finishing are the same that for finishing except that the tool used during machining is chosen of a smaller value (D = 6mm), which leads to a uniform thickness of 1 mm. For the finishing operation, grid steps are chosen identical for both x and y directions: 0.2mmx0.2mm. To check that trajectories are interference free, they are integrated into CATIA V5®, and the simulation of the machining is carried out (Figure 5c). Algorithms for trajectory simulations based on the voxel-map are presently in progress.

The part is thus machined on the Mikron milling centre with the same feed rate. The result reported in figure 5c shows the feasibility of the approach. However, it is necessary to assess direct duplication in terms of geometrical conformity to the initial shapes. For this purpose, a comparison is made through simulations.

The method developed is a classical N-buffer simulation method, and consists in, considering finishing only, simulating the envelope of the tool trajectory (Jerard et al. 1987). Geometrical deviations between the envelope and the initial cloud of points are calculated for both approaches (Classical RE and direct duplication). N-buffer requires a representation point/surface of the surface to be machined. The CAD model is used as the reference to calculate the normal at each cloud point.

Despite imperfections introduced using such approximation, the default in normal orientation is of little influence on the geometrical conformity. Once the surfel (set of points and normals) is obtained, simulation is carried out by intersecting the surfel with the tool trajectory. The algorithm is applied on a lightened cloud points (20 000 points) (Figure 6). In the case of direct duplication, geometrical deviations reported are nearly all positive, which is consistent with the tool positioning method.. Details of the physical object are revealed: deformation of the left cheek, marks on the temples, inferior lip well-drawn, (Figure 7). Therefore, direct duplication quality is essentially linked to tool accessibility (tool diameter) and to the grid step. Indeed, deviations are negative only for vertical zones located near the chin for which the longitudinal step is too large.

Similarly, the large transversal step provides important cups for the vertical zones at the vicinity of the temples. Concerning the approach based on RE, deviations are both positive and negative due to the surface reconstruction: the surface best-fits the points according to the least-square criterion. This provides waves as well as the smoothing of the details, which is particularly noticeable for the nose and the lips (Figures 6 and7). The geometrical conformity is thus weaker. Nonetheless, the machining tolerance and the maximum scallop height are better managed with the software. The efficiency of direct duplication is proved. However, 3-axis machining is not capable of produced parts with complex shapes, such as statues for instance. An alternative is the use of 5-axis machining. The two additional degrees of freedom, allows the machining of sculptured surfaces with complex shapes. As some difficulties remain in interference-free tool path calculation for 5-axis machining, an alternative is the use of discrete 5-axis machining. In this approach, the surface to be machined is subdivided into areas with similar shapes, so that each area can be machined with the same tool orientation [START_REF] Chen | Automated surface subdivision and tool path generation for 3 1/2 1/2 axis CNC machining of sculptured parts[END_REF]. A valid tool orientation defines a part set-up for which the surface can be machined without gouging and interference. Therefore, the area accessible by the tool can be machined according to 3-axis strategy.

In the next section, we propose an extension of 3-axis duplication to 5-axis direct duplication in order to increase the diversity of objects that can be reproduced. Hence, the basic issue of discrete 5-axis machining can be formulated as follows: given the point cloud and the 5-axis machine tool, find the minimum number of tool orientations so that all the points are accessible. Actually, this is equivalent to a machining area-by-area problem, for which the data need to be partitioned based on their accessibility [START_REF] Teng | generating tool paths from point cloud data via machining area segmentation[END_REF]. The method developed consists of two main stages: topological and technological data segmentation, and tool path generation. During the segmentation stage, data are partitioned based on accessibility criteria to form groups of points that will be machined with the same tool orientation. Once, points are grouped, algorithms developed in section 2 are applied to generate tool trajectories for both roughing and finishing operations.

Data processing for area-by-area machining

For most of the algorithms developed, a crucial issue is the calculation of geometrical differential properties on discrete data. Indeed, the loss of continuity and the lack of data structure involve that these properties can only be estimated. The major problem concerns in particular the calculation of the local normal. Many authors have investigated this issue [START_REF] Meek | On surface normal and Gaussian curvature approximations given data sampled from a smooth surface[END_REF]) [START_REF] Park | Elliptic Gabriel graph for finding neighbors in a point set and its application to normal vector estimation[END_REF]. As for machining, the normal is simply evaluated from a voxelisation of the data (see §2). For each voxel, the normal is calculated as the normal to the plane that best-fits the points included in the considered voxel. The calculated normal can be interpreted as a local normal, representative of a small portion of the surface (a small sub-set of points). The size of an elementary cell is fixed in function of the free form surface geometry and of the dimension of the tool radius used for the milling. This method is efficient as long as the point number allows the calculation of the least-square plane. When the voxel number is not sufficient (generally, when located at the vicinity of boundaries) the normal is calculated using the voxel and its 27 neighbours. At final, a voxel-map is created: a set of triplets (voxel, normal, barycentre). This voxel-map acts as a filtering of the data.

Global visibility

The computation of tool accessibility at each point is divided into two steps: calculation of the local tool visibility followed by the calculation of the global visibility.

The visibility is evaluated at each point of the voxel-map (each barycentre). A visibility cone is built, which axis is defined by the normal, and the angle of which is directly linked to the tool geometry. Let us denote, ν the cone angle: ν = 0° for cylindrical tool, ν = 90° for a ball-end cutter tool (or hemispherical tool) and, 0< ν < 90° for a filleted-end tool. In the paper, only the case of the hemispherical tool is investigated (Figure 9). In order to improve the efficiency of the cutting during machining, the cutting zone of the tool is reduced; tool axis orientations parallel to the normal or perpendicular are forbidden. This reduces the visibility zone of the tool as shown in figure 9, which means the possible orientations of the tool relatively to the surface normal. This visibility is thus called tool visibility or local visibility. Anyway, it is important to notice that as points result from a digitizing operation, they are necessarily visible according to the sensor direction that is used to collect them. Although these directions may not be optimal as regards cutting efficiency, they provide a good process initialization.

Once local visibility is calculated, it is necessary to check that the tool body is not in interference with the cloud of points. The verification is performed only for the tool body, without considering the cutting zone of the tool. Indeed, by definition the positioning method is interference-free (see § 2.2).

To simplify calculations, the tool body is sampled. At final, this provides for each point, tool configurations that are not in interference with the point cloud.

Figure 10. Interference between the tool body and the point cloud

In a last step, machine accessibility must be verified as it is essential to check that each direction of global visibility is included within the visibility space of the machine tool. If not, the tool orientation can not be considered as defining a possible set-up. Machine accessibility requires the geometric model of the machine to be known. This last step provides the global visibility.

Segmentation for area-by-area machining

The point cloud segmentation for area-by-area machining, must provide all the set-ups allowing the complete surface machining; it is thus a key point. The efficiency of the approach relies on the use of a visibility matrix (Figure 11). Rows of the matrix correspond to the voxel-map points, and its columns are tool orientations obtained from the visibility step. The value is 1 or 0, whether the point is visible or not according to the given orientation. The column with the greater number of "1" is first retained, and defines the first set-up. Corresponding points are removed from the visibility matrix, and the search continues as follows:

 Find the column with the maximum number of "1",  Check that the number of points is greater than a given threshold,

 Check that the number of set-ups is less than a given threshold,  Group the corresponding points to form a sub-set associated to the given set-up  Remove those points from the matrix Once, all the set-ups are found according to the previous criteria, isolated points or small point sub-sets are investigated. Most generally, the algorithm attempts to integrate them to neighbour sub-sets.

Figure 11. Matrix of visibility

First application

The proposed approach is applied for the duplication of a little figurine representing a cartoon character (Figure 13).

The scanning of the object is carried out thanks to a laser plane sensor mounted on a CMM as discussed in §2.3. Sensor configurations are chosen to guarantee the completeness of the digitized points as regards the whole object surface [START_REF] Mehdi-Souzani | Scan planning strategy for a general digitized surface[END_REF]. Five sensor directions are used; z, x, -x, y, -y. The resulting point cloud is strongly dense and inhomogeneous. The voxel-map is thus built from the points, with a cell size of 2mm giving 1437 voxels (Figure 13).

To simplify the problem in this first application, the 5 sensors orientations are considered as possible tool orientations. Corresponding orientations on the machine tool are calculated: (A=0,C=0), (A=90,C=-90) ,(A=90,C=90), (A=90,C=180), (A=90,C=0). Therefore, for each one, local and global visibilities are checked, with a cone angle equal to 60°. As all the 5 orientations are validated, the point cloud is segmented into 5 areas, defining 5 point sub-sets.

For each set-up, or each point sub-set, the tool-path is calculated according to algorithms developed in section 2.3. The machining zone is defined as follows:

-For each set-up, define a plane perpendicular to the tool axis, -Project all the voxel vertices that belong to the considered point sub-set; the limits of the rectangular grid are created (Figure 12).

-For each node, if the tool axis intersects the voxels, calculate the Cutter Location point.

Figure 12. Machining area by set-up At final, the part machining is carried out on the machine MIKRON UCP 710. Figure 13 shows the result of the milling, which includes both roughing and finishing operations. Due to the limit of the tool radius, some surfaces can not be machined such as the neck of the little character. Nevertheless, some details like the eyes or the wind-breaker buttons are visible which brings out the efficiency of this approach. Although the use of sensor orientations allows limiting the number of part set-ups, the result is not optimized as regards overlapping areas. Some geometrical defects are clearly visible at the machining area junctions, probably due to re-positioning errors on the machine-tool (Figure 14). Those defects are related to machine tool geometric errors (axis straightness, axis perpendicularity…). Although nowadays machine tools have high-performance, geometric errors still remain. Some authors propose to optimize the part set-up in order to minimize those errors [START_REF] Anotaipaiboon | Optimal setup for five-axis machining[END_REF]. Other works address the issue of trajectory compensation in order to remove kinematics errors [START_REF] Mir | Tool path error prediction of a five axis machine tool with geometric errors[END_REF]. Some tests performed on the Mikron UCP shown that registration errors related to tool orientation changes may be close to 0.1mm in some cases. Additional tests must be performed in order to provide kinematics errors of the considered machine tool.

Therefore, overlaps must be limited which adds a constraint to data segmentation. Overlapping zones can be identified as the boundaries of the machining areas. Taking advantages of the voxel-map, these zones can be identified as the voxels; voxels defining the contour of the area constitute the overlapping line. The investigation of the optimisation problem is in progress.

Conclusion

In the paper, a novel method for duplication of physical models is proposed. The aim is to produce a copy of an existing object which has been digitized using non-contact devices. The step of digitizing generally provides a large cloud of points, dense, noisy and inhomogeneous. To avoid critical issues linked to the RE stage, direct machining of the point cloud is implemented. Algorithms developed for 3-axis ball end milling, for roughing and finishing operations are detailed. The efficiency of direct machining is shown thanks to a simple example. The comparison done with classical methods based on RE highlights the efficiency of the approach in terms of geometrical conformity to the initial surface object. An extension to discrete 5-axis machining is carried out to increase the diversity of forms that can be machined. The main problem is the point cloud segmentation in areas that can be machine with the same tool orientation, defining then a part set-up.

To solve this difficulty, a visibility matrix is built. For each point, possible tool orientations, corresponding to part set-ups, are identified according to visibility and accessibility criteria. Points that can be machined with the same tool orientation are grouped to form a point sub-set. Each point sub-set is afterwards machined in 3-axis machining according to algorithms previously developed. The feasibility of direct duplication in 5 axis machining is proved through the duplication of a little figurine. The solution is yet not optimized, and some improvements must be done in particular concerning the overlapping areas.

Figure 4 .

 4 Figure 4. Finishing strategy

Figure 5 .

 5 Figure 5. Duplication of a mask using RE and using direct duplication a -Digitizing system and resulting point cloud b -Method based on Reverse Engineering c -Direct duplication

Figure 6 .

 6 Figure 6. Comparison of machining simulations a. Direct duplication, b. Reverse Engineering

Figure 7 .

 7 Figure 7. Details of the machined parts a. Direct duplication, b. Reverse Engineering, c. Physical model

Figure 8

 8 Figure 8. 5-axis machine tool (RRTTT structure)

Figure 9 .

 9 Figure 9. The local visibility a-Definition of the local visibility b-Visibility for a hemispherical tool c-Reduced visibility zone

Figure 13 .

 13 Figure 13. Direct duplication in 5-axis discrete machining.

Figure 14 .

 14 Figure 14. Overlapping defects on the figurine


Cyril Grouin

Sophie Rosset

Pierre Zweigenbaum
email: pierre.zweigenbaum@limsi.frkaren.fort@inist.fr

Karën Fort

Olivier Galibert
email: olivier.galibert@lne.fr

Ludovic Quintard
email: ludovic.quintard@lne.fr

Proposal for an Extension of Traditional Named Entities: From Guidelines to Evaluation, an Overview

Within the framework of the construction of a fact database, we defined guidelines to extract named entities, using a taxonomy based on an extension of the usual named entities definition. We thus defined new types of entities with broader coverage including substantivebased expressions. These extended named entities are hierarchical (with types and components) and compositional (with recursive type inclusion and metonymy annotation). Human annotators used these guidelines to annotate a 1.3M word broadcast news corpus in French.

This article presents the definition and novelty of extended named entity annotation guidelines, the human annotation of a global corpus and of a mini reference corpus, and the evaluation of annotations through the computation of inter-annotator agreement. Finally, we discuss our approach and the computed results, and outline further work.

Introduction

Within the framework of a project multimedia indexing, we organized an evaluation campaign on named entity extraction, with the aim to build a fact database in the news domain, the first step being to define what kind of entities are needed. This campaign focused on broadcast news corpora in French. While traditional named entities include three major classes (persons, locations and organizations), we decided to extend the coverage of our campaign to new types of entities and to broaden their main parts-of-speech from proper names to substantives, this extension being necessary for ever-increasing knowledge extraction from documents. We thus produced guidelines to specify the way corpora had to be annotated, and launched the annotation process.

In this paper, after covering related work (Section 2), we describe the taxonomy we created (Section 3) and the annotation process and results (Section 4), including the corpora we gathered and the tools we developed to facilitate annotation. We then present inter-annotator agreement measures (Section 5), outline limitations (Section 6) and conclude on perspectives for further work (Section 7).

2 Related work

Named entity definitions

Named Entity recognition was first defined as recognizing proper names [START_REF] Coates-Stephens | The analysis and acquisition of proper names for the understanding of free text[END_REF]. Since MUC-6 [START_REF] Grishman | Message Understanding Conference -6: A brief history[END_REF][START_REF] Saic | Proceedings of the seventh message understanding conference (MUC-7)[END_REF], named entities have been proper names falling into three major classes: persons, locations and organizations. Proposals have been made to sub-divide these entities into finer-grained classes. For example, the "politicians" subclass was proposed for the "person" class by [START_REF] Fleischman | Fine grained classification of named entities[END_REF] while the "cities" subclass was added to the "location" class by [START_REF] Fleischman | Automated subcategorization of named entities[END_REF][START_REF] Lee | Heuristic methods for reducing errors of geographic named entities learned by bootstrapping[END_REF]. The CONLL conference added a miscellaneous type that includes proper names falling outside the previous classes. Some classes have thus sometimes been added, e.g. the "product" class by [START_REF] Bick | A named entity recognizer for danish[END_REF][START_REF] Galliano | The ESTER 2 evaluation campaign for the rich transcription of French radio broadcasts[END_REF]. Specific entities are proposed and handled in some tasks, for example "language" or "shape" for question-answering systems in specific domains [START_REF] Rosset | The LIMSI participation to the QAst track[END_REF], "email address" or "phone number" to process electronic messages [START_REF] Maynard | Named entity recognition from diverse text types[END_REF]. Some numeric types are also often described and used. They include "date", "time", and "amount" types (the latter category generally covers money and percentage). In specific domains, entities such as gene, protein, DNA, etc., are also handled [START_REF] Ohta | The genia corpus: An annotated research abstract corpus in molecular biology domain[END_REF], and campaigns are organized for gene detection [START_REF] Yeh | BioCreAtIvE task 1A: gene mention finding evaluation[END_REF]. At the same time, extensions of named entities have been proposed. For example, [START_REF] Sekine | Definition, dictionaries and tagger of extended named entity hierarchy[END_REF]) defined a complete hierarchy of named entities containing about 200 types.

Named Entities and Annotation

As for any other kind of annotation, some aspects are known to lead to difficulties in obtaining coherence in the manual annotation process [START_REF] Ehrmann | Les entités nommées, de la linguistique au TAL : statut théorique et méthodes de désambiguïsation[END_REF][START_REF] Fort | Towards a Methodology for Named Entities Annotation[END_REF]. Three different classes of problems are distinguished: (1) to choose the correct category in cases of ambiguity, where one entity can fall into several classes, depending of the context (for example, Paris can be a town or a person name);

(2) to detect the boundaries (e.g., in a person designation, is only the proper name to be annotated or the trigger Mr too?) and (3) to annotate metonymies (e.g., France can be a sports team, a country, etc.).

In the ACE Named Entity task [START_REF] Doddington | The automatic content extraction (ACE) program tasks, data, and evaluation[END_REF], a complex task, the obtained inter-annotator agreement was 0.86 in 2002 and 0.88 in agreement. [START_REF] Desmet | Towards a balanced named entity corpus for dutch[END_REF] described the Named Entity annotation realized within the Sonar project, where NE are clearly simpler. They follow the MUC Named Entity definition with the subtypes as proposed by ACE. The agreement computed over the Sonar Dutch corpus ranges from 0.91 to 0.97 (kappa values) depending of the emphasized elements (span, main type, subtype, etc.).

Taxonomy

Guidelines production

Having in mind the objective of building a fact database through the extraction of named entities from texts, we defined a richer taxonomy than those used in other information extraction works.

Following [START_REF] Bonneau-Maynard | Semantic Annotation of the French Media Dialog Corpus[END_REF][START_REF] Alex | Agile Corpus Annotation in Practice: An Overview of Manual and Automatic Annotation of CVs[END_REF], the annotation guidelines were first written from December 2009 to May 2010 by three researchers managing the manual annotation campaign. During guidelines production, we evaluated the feasibility of this specific annotation task and the usefulness of the guidelines by annotating a small part of the target corpus. Then these guidelines were delivered to the annotators. They consist of a description of the objects to annotate, general annotation rules and principles, and more than 250 prototypical and real examples extracted from the corpus. Rules are important to set the general way annotations must be produced. Additionally, examples are essential for human annotators to grasp the annotation rationale more easily.

Indeed, while producing the guidelines, we knew that the given examples would never cover all possible cases because of the specificity of language and of the ambiguity of formulations and situations described in corpora, as shown in [START_REF] Fort | Towards a Methodology for Named Entities Annotation[END_REF]. Nevertheless, guidelines examples must be considered as a way to understand the final objective of the annotation work. Thanks to numerous meetings from May to November 2010, we gathered feedback from the annotators (four annotators plus one annotation manager). This feedback allowed us to extend and clarify the guidelines in several directions. The guidelines are 72 pages long and consist of 3 major parts: general description of the task and the principles (25% of the overall document), presentation of each type of named entity (57%), and a simpler 'cheat sheet' (18%).

Definition

We decided to use the three general types of named entities: name (person, location, organization) as described in [START_REF] Grishman | Message Understanding Conference -6: A brief history[END_REF][START_REF] Saic | Proceedings of the seventh message understanding conference (MUC-7)[END_REF], time (date and duration), and quantity (amount). We then included named entities extensions proposed by [START_REF] Sekine | Definition, dictionaries and tagger of extended named entity hierarchy[END_REF][START_REF] Galliano | The ESTER 2 evaluation campaign for the rich transcription of French radio broadcasts[END_REF] (respectively products and functions) and we extended the definition of named entities to expressions which are not composed of proper names (e.g., phrases built around substantives). The extended named entities we defined are both hierarchical and compositional. For example, type pers (person) is split into two subtypes, pers.ind (individual person) and pers.coll (collective person), and pers entities are composed of several components, among which are name.first and name.last.

Hierarchy

We used two kinds of elements: types and components. The types with their subtypes categorize a named entity. While types and subtypes have been widely used previously [START_REF] Sekine | Definition, dictionaries and tagger of extended named entity hierarchy[END_REF][START_REF] Ace | Entity detection and tracking, phase 1, ACE pilot study. Task definition[END_REF][START_REF] Galliano | The ESTER 2 evaluation campaign for the rich transcription of French radio broadcasts[END_REF], we consider that structuring the contents of an entity (its components) is important too. Components categorize the elements inside a named entity.

Our taxonomy is composed of 7 main types (person, function, organization, location, product, amount, and time) and 32 subtypes (Table 1). Types and subtypes refer to the general category of a named entity. They give general information about the annotated expression. Almost each type is then specified using subtypes that either mark an opposition between two major subtypes (individual person vs. collective person), or add precisions (for example for locations: administrative location, physical location, etc.).

Our two-level representation of named entities, with types and components, constitutes a novel approach.

Types and subtypes To deal with the intrinsic ambiguity of named entities, we defined two specific transverse subtypes: 1. other for entities with a different subtype than those proposed in the taxonomy (for example, prod.other for games), and 2. unknown when the annotator does not know which subtype to use.

Types and subtypes constitute the first level of annotation. They refer to a general segmentation of the world with major categories. Within these categories, we defined a second level of annotation we call components.

Components Components can be considered as clues that help the annotator to produce an annotation: either to determine the named entity type (e.g. a first name is a clue for the pers.ind named entity subtype), or to set the named entity boundaries (e.g. a given token is a clue for the named entity, and is within its scope, while the next token is not a clue and is outside its scope). Components are second-level elements, thus can never be used outside the scope of a type or subtype element. An en-tity is thus composed of components that are of two kinds: transverse components and specific components (Table 2). Transverse components can be used in several types of entities, whereas specific components can only be used in one type of entity.

Composition

Another original point in this work is the compositional nature of the annotations.

Entities can be compositional for three reasons: (i) a type contains a component, as seen above; (ii) a type includes another type, used as a component; and (iii) to cases of metonymy, as explained below. During the Ester II evaluation campaign, there was an attempt to use compositionality in named entities for two categories: persons and functions, where a person entity could contain a function entity (e.g. <pers.hum> <func.pol> président </func.pol> <pers.hum> Chirac </pers.hum> </pers.hum>). Nevertheless, the Ester II evaluation did not take this inclusion into account and only focused on the encompassing annotation (here, only <pers.hum> président Chirac </pers.hum>). In the present work, we drew our inspiration from this experience, and allowed the annotators and the systems to use compositionality in the annotations.

Cases of inclusion can be found in the function type, e.g. in new minister of budget (see Figure 1, with type tags in red), where type func.ind, which spans the whole expression, includes type org.adm, which spans the single word Budget (and includes component name). In this case, we consider that the designation of this function (minister of Budget) includes both the kind (minister) and the name (Budget) of the ministry, which itself is typed as is relevant (org.adm: administrative organization). Recursive cases of embedding can be found when a subtype includes another named entity annotated with the same subtype (Figure 2).

Cases of metonymy include strict metonymy (a term is substituted with another one in a relation of contiguity) and antonomasia (a proper name is used as a substantive or vice versa). In such cases, the entity must be annotated with both types, first (inside) with the intrinsic type of the entity, then (outside) with the type that corresponds to the result of the metonymy. Country names (Figure 3) basically correspond to 'national administrative' loca- Transverse components name (name of the entity), kind (hyperonym of the entity), qualifier (qualifying adjective), demonym (inhabitant or ethnic group name), demonym.nickname (inhabitant or ethnic group nickname), val (a number), unit (a unit), extractor (an element in a series), range-mark (range between two values), time-modifier (a time modifier tions (loc.adm.nat) but they can also designate the administration (org.adm) of the country.

Boundaries

Our definition of the scope of entities excludes relative clauses, subordinate clauses, and interpolated clauses: the annotation of an entity must end before these clauses. If an interpolated clause occurs inside an entity, its annotation must be split. In the same way, two distinct persons sharing the same last name must be annotated as two separate enti- 4 Annotation process

Corpus

We managed the annotation of a corpus of about one hundred hours of transcribed speech from several French-speaking radio stations France and Morocco. Both news and entertainment shows were transcribed, including dialogs, with speaker turns1 .

Once annotated, the corpus was split into a development corpus: 1 file from one French radio station2 ; a training corpus: 188 files from five French stations3 and one Moroccan station4 ; and a test corpus: 18 files from two French stations already studied in the training corpus5 and from unseen sources, both radio6 and television7 , in order to evaluate the robustness of systems; these data have been used for the 2011 Quaero Named Entity evaluation campaign.

The distribution of these sources allows us to perform different evaluations, depending of the knowledge the systems have of the source (source seen in the training corpus vs. unseen source), the kind of show (news vs. entertainment), the language style (popular vs. refined), and the type of media (radio vs. television).

Tools for annotators

To perform our test annotations (see Section 2.2), we developed a very simple annotation tool as an interface based on XEmacs. We provided the human annotators with this tool and they decided to use it for the campaign, despite the fact that it is very simple and that we told them about other, more generic, annotation tools such as GATE8 or Glozz9 . This is probably due to the fact that apart from being very simple to install and use, it has interesting features.

The first feature is the insertion of annotations using combinations of keyboard shortcuts based on the initial of each type, subtype and component name. For example, combination F2 key + initial keys is used to annotate a subtype (pers.ind, loc.adm.nat, etc.), F3 + keys for a transverse component (name, kind, etc.), F4 + keys for a specific component (name.first, zip-code, etc.), and F5 to delete the annotation selected with the cursor (both opening and closing tags).

The second feature is boundary management: if the annotator puts the cursor over the token to annotate, the annotation tool will handle the boundaries of this token; opening and closing tags will be inserted around the token.

However, it presents some limitations: tags are inserted in the text (which makes visualization more complex, especially for long sentences or in cases of multiple annotations on the same entity), no personalization is offered (tags are of only one color), and there is no function to express annotator uncertainty (the user must choose among several possible tags the one that fits the best 10 ; while producing the guidelines, we did not consider it could be of interest: as a consequence, no uncertainty management was implemented). Therefore, this tool allows users to insert tags rapidly into a text, but it offers no external resources, as real annotation tools (e.g. GATE) often do. These simplistic characteristics combined with a fast learning curve allow the annotators to rapidly annotate the corpora. Annotators were allowed not to annotate the transverse component name (only if it was the only component in the annotated phrase, e.g. "Russia" in Figure 3, blue tag) and to events, even though we do not focus on this type of entity as of yet. We therefore also provided a normalization tool which adds the transverse component name in these instances, and which removes event annotations.

Corpus annotation

Global annotation It took 4 human annotators two months and a half to annotate the entire corpus (10 man-month). These annotators were hired graduate students (Master in linguistics). The overall corpus was annotated in duplicate. Regular comparisons of annotations were performed and allowed the annotators to develop a methodology, which was subsequently used to annotate the remaining documents.

Mini reference corpus

To evaluate the manual annotations, we built a mini reference corpus by randomly selecting 400 sentences from the training corpus and distributing them into 4 files. These files were annotated by 4 graduate human annotators from two research institutes (Institute 1 and Institute 2 in Figure 5) with 2 humans per institute, in approximatively 10 hours per annotator. We merged the annotations of each file within a given institute (1.5 h per pair of annotators), then merged the results across the two institutes (2 hours). Finally we merged the results with the annotations of the hired annotators (8 hours). We thus spent about 90 hours to annotate and merge annotations in this mini reference corpus (0.75 man-month).

Annotation results

Our broadcast news corpus includes 1,291,225 tokens, among which there are 954,049 nonpunctuation tokens. Its annotation contains 113,885 named entities and 146,405 components (see Ta-ble 3), i.e. 1 entity per 8.4 non-punctuation tokens, and 1 component per 6.5 non-punctuation tokens. There is an average of 6 annotations per line. 5 Inter-Annotator Agreement

!"#$#%#&'( !"#$#%#&" !"#$#%#&') *$!$'+&,&-&!.& // /!!0#1#0-" // 230413'.0-5%"

Procedure

During the annotation campaign, we measured several criteria on a regular basis: inter-annotator agreement and disagreement. We used them to correct erroneous annotations, and mapped these corrections to the original annotations. We also used these measures to give the annotators feedback to the encountered problems, discrepancies, and residual errors. Whereas we performed these measurements all along the annotation campaign, this paper focuses on the final evaluation on the mini reference corpus.

Metrics

Because human annotation is an interpretation process [START_REF] Leech | Introducing corpus annotation[END_REF], there is no "truth" to rely on. It is therefore impossible to really evaluate the validity of an annotation. All we can and should do is to evaluate its reliability, i.e. the consistency of the annotation across annotators, which is achieved through computation of the inter-annotator agreement (IAA).

The best way to compute it is to use one of the Kappa family coefficients, namely Cohen's Kappa [START_REF] Cohen | A Coefficient of Agreement for Nominal Scales[END_REF] or Scott's Pi [START_REF] William | Reliability of Content Analysis: The Case of Nominal Scale Coding[END_REF], also known as Carletta's Kappa [START_REF] Carletta | Assessing Agreement on Classification Tasks: the Kappa Statistic[END_REF] 11 , as they take chance account [START_REF] Artstein | Inter-Coder Agreement for Computational Linguistics[END_REF]. However, these coefficients imply a comparison with a "random baseline" to establish whether the correlation between annotations is statistically significant. This baseline depends on the number of 'markables', i.e. all the units that could be annotated.

In the case of named entities, as in many others, this "random baseline" is known to be difficultif not impossible-to identify [START_REF] Alex | Agile Corpus Annotation in Practice: An Overview of Manual and Automatic Annotation of CVs[END_REF]. We wish to analyze this in more detail, to see how we could actually compute these coefficients and what information it would give us about the annotation. In the present case, we could for example consider that, potentially, all the noun phrases can be annotated (row U3 in Table 4, based on the PAS-SAGE campaign [START_REF] Vilnat | Passage syntactic representation: a minimal common ground for evaluation[END_REF]). Of course, this is a wrong approximation as named entities are not necessarily noun phrases (see, e.g., "à partir de l'automne prochain", from next autumn). We could also consider all n-grams of tokens in the corpus (row U1). However, it would be more relevant to limit their size. For a maximum size of 6, we get the results shown in row U2. All this, of course, is artificial, as the named entity annotation process is not random. To obtain results that are closer to reality, we could use numbers of named entities from previous named entity annotation campaigns (row U4 based on the Ester II campaign [START_REF] Galliano | The ESTER 2 evaluation campaign for the rich transcription of French radio broadcasts[END_REF]), but as we consider here a largely extended version of those, the results would again be far from reality. Another solution is to consider as "markables" all the units annotated by at least one of the annotators (row U5). In this particular case, units not annotated by any of the annotators (i.e. silence) are overlooked. The lowest IAA will be the one computed with this last solution, while the high- 5).

Markables

est IAA will be equal to the F-measure (i.e. the measure computed with all the markables as shown in row U1 in Table 4). We notice that the first two solutions (U1 and U2 with n-grams) are not acceptable because they are far removed from reality; even extended named entities are sparse annotations, and just considering all tokens as 'markables' is not suitable. The last three ones seem to be more relevant because they are based on an observed segmentation on similar data. Still, the U3 solution (NPs) overrates the number of markables because not all noun phrases are extended named entities. Although the U4 solution (Ester entities) is based on the same corpus used for a related task, it underrates the number of markables because that task produced 16.3 times less annotations. Finally the U5 solution (pooling) gives the lower bound for the κ estimation which is an interesting information but may easily undervalue the quality of the annotation.

As [START_REF] Hripcsak | Technical brief: Agreement, the f-measure, and reliability in information retrieval[END_REF] showed, in our case κ tends towards the F-measure when the number of negative cases tends towards infinity. Our results show that it is hard to build a justifiable hypothesis on the number of markables which is larger than the number of actually annotated entities while keeping κ significantly under the F-measure. But building no hypothesis leads to underestimating the κ value. This reinforces the idea of using the F-measure as the main inter-annotator agreement measure for named entity annotation tasks.

Limitations

We used syntax to define some components (e.g. a qualifier is an adjective) and to set the scope of entities (e.g. stop at relative clauses). Nevertheless, this syntactic definition cannot fit all named entities, which are mainly defined according to semantics: the phrase dans les mois qui viennent (in the coming months) expresses an entity of type time.date.rel where the relative qui viennent is part of the entity and contributes the time-modifier component.

The distinction between some types of entities may be fuzzy, especially for the organizations (is the Social Security an administrative organization or a company?) and for context-dependent annotations (is lemonde.fr a URL, a media, or a company?). As a consequence, some entity types might be converted into specific components in a future revision, e.g. the func type could become a component of the pers type, where it would become a description of the function itself instead of the person who performs this function (Figure 6).

Conclusion and perspectives

In this paper, we presented an extension of the traditional named entity categories to new types (functions, civilizations) and new coverage (expressions built over a substantive). We created guidelines that were used by graduated annotators to annotate a broadcast news corpus. The organizers also annotated a small part of the corpus to build a mini reference corpus. We evaluated the human annotations with our mini-reference corpus: the actual computed κ is between 0.71 et 0.85 which, given the complexity of the task, seems to indicate a good annotation quality. Our results are consistent with other studies [START_REF] Dandapat | Complex Linguistic Annotation -No Easy Way Out! A Case from Bangla and Hindi POS Labeling Tasks[END_REF] in demonstrating that hu-man annotators' training is a key asset to produce quality annotations. We also saw that guidelines are never fixed, but evolve all along the annotation process due to feedback between annotators and organizers; the relationship between guidelines producers and human annotators evolved from "parent" to "peer" [START_REF] Akrich | Le mode d'emploi, genèse, forme et usage[END_REF]. This evolution was observed during the annotation development, beyond our expectations. These data have been used for the 2011 Quaero Named Entity evaluation campaign.

Extensions and revisions are planned. Our first goal is to add a new type of named entity for all kinds of events; guidelines are being written and human annotation tests are ongoing. We noticed that some subtypes are more difficult to disambiguate than others, especially org.adm and org.ent (definition and examples in the guidelines are not clear enough). We shall make decisions about this kind of ambiguity, either by merging these subtypes or by reorganizing the distinctions within the organization type. We also plan to link the annotated entities using relations; further work is needed to define more precisely the way we will perform these annotations. Moreover, the taxonomy we defined was applied to a broadcast news corpus, but we intend to use it in other corpora. The annotation of an old press corpus was performed according to the same process. Its evaluation will start in the coming months.

Figure 1 :

 1 Figure 1: Multi-level annotation of entity types (red tags) and components (blue tags): new minister of budget , François Baroin.

Figure 2 :

 2 Figure 2: Recursive embedding of the same subtype (org.ent): Collective of the Human Rights Organizations in Sahara.

Figure 3 :

 3 Figure3: Annotation of types and components, with a metonymic use of country 'Russia' (loc.adm.nat) as its government (org.adm): for several months , Russia....

Figure 4 :

 4 Figure 4: Separate (coordinated) named entities.

Figure 5 :

 5 Figure 5: Creation of mini reference corpus and computation of inter-annotator agreement.

Figure 6 :

 6 Figure 6: Possible revision: current annotation (left), transformation of func from entity to component (right).

Table 1 :

 1 Types (in bold) and subtypes (in italic)

		Person			Function
	pers.ind (individual	pers.coll (group of	func.ind (individual	func.coll (collectivity
	person)		persons)		function)		of functions)
		Location			Production
	administrative (loc.adm.town, loc.adm.reg, loc.adm.nat, loc.adm.sup)	physical (loc.phys.geo, loc.phys.hydro, loc.phys.astro)	facilities (loc.fac), oronyms (loc.oro), address (loc.add.phys, loc.add.elec)	prod.object (manufac-tured object) prod.doctr (doctrine) prod.art	prod.serv (transporta-tion route) prod.rule (law) prod.media	prod.fin (financial products) prod.soft (software) prod.award
		Organization			Time
	org.adm (administra-	org.ent (services)	time.date.abs		time.hour.abs
	tion)				(absolute date),		(absolute hour),
		Amount		time.date.rel (relative	time.hour.rel (relative
	amount (with unit or general object), includ-	date)		hour)
	ing duration

  ).

	pers.ind	loc.add.phys	time.date.*	amount
	name.last, name.first,	address-number, po-box,	week, day, month, year,	object
	name.middle, pseudonym,	zip-code,	century, millennium,	prod.award
	name.nickname, title	other-address-component	reference-era	award-cat

Table 2 :

 2 Transverse and specific components

		func.ind		pers.ind
			org.adm
	qualifier	kind	name	name.first	name.last
	nouveau	ministre	du Budget	, François	Baroin

Table 3 :

 3 Statistics on annotated corpora.

	P P P P P P P P P Inf. Data	Training	Test
	# shows	188	18
	# lines	43,289	5,637
	# words	1,291,225 108,010
	# entity types	113,885	5,523
	# distinct types	41	32
	# components	146,405	8,902
	# distinct comp.	29	22

Table 4 :

 4 Inter-Annotator Agreements (κ stands for Cohen's Kappa, π for Scott's Pi, and F for F-measure). IAA values were computed by taking as the reference the hired annotators' annotation or that obtained by merging from both institutes (see Figure

Potential named entities may be split across several segments or turns.

2 News from France

Culture. 3 News from France Culture (refined language), France Info (news with short news headlines), France Inter (generalist radio station), Radio Classique (classical music and economic news), RFI (international radio broadcast out

of France).4 News from RTM (generalist French

speaking radio). 5 News from France Culture, news and entertainment

from France Inter.6 A popular

entertainment show from Europe 1.7 News from Arte (public channel with art and culture), France 2 (public generalist channel), and TF1 (private generalist popular channel).

http://gate.ac.uk/

http://www.glozz.org/

Uncertainty can be found in cases of lack of context.

For more details on terminology issues, we refer to the introduction of[START_REF] Artstein | Inter-Coder Agreement for Computational Linguistics[END_REF].

Acknowledgments

We thank all the annotators who did such a great work on this project, as well as Sabine Barreaux (INIST-CNRS) for her work on the reference corpus. This work was partly realized as part of the Quaero Programme, funded by Oseo, French State agency for innovation and by the French ANR Etape project.


Christophe Krzeminski

Christophe Delerue

Guy Allan

Dominique Vuillaume

R M Metzger

Theory of electrical rectification in a molecular monolayer

teaching and research institutions in France or abroad, or from public or private research centers.

I. INTRODUCTION

Molecular electronics has gained large-scale interest in recent years. A promising system is the electrical rectifier based on suitably engineered molecules. At the origin of this idea, Aviram and Ratner 1 proposed in 1974 to use D-σ-A molecules, where D and A are, respectively, an electron donor and an electron acceptor, and σ is a covalent "sigma" bridge. Electrical rectification was observed only recently, in particular in Langmuir-Blodgett (LB) multilayers or monolayers of γ-hexadecylquinolinium tricyanoquinodimethanide (C 16 H 33 Q-3CNQ, 1, Fig. 1) sandwiched between metallic electrodes [2][3][4][5][6] . Even if these results represent an important progress to achieve molecular electronics, the physical mechanism responsible for the rectification is not clear. One critical issue is to know if the Aviram-Ratner model can be applied to 1, because it is a D(+)-π-A(-) molecule 5 . On the theoretical side, these molecular diodes are complex systems, characterized by large and inhomogeneous electric fields, which result from the molecular dipoles 5 in the layer, the applied bias, and the screening induced by the molecules themselves and the metallic electrodes. A theoretical treatment of these effects is presently lacking, as it requires a self-consistent resolution of the quantummechanical problem, including the effect of the applied bias on the electronic structure. Our aim in this paper is to present such a theory, and its application to the systems experimentally studied in Refs. 3,4,6 . Combining ab initio and semi-empirical calculations, we show that the direction of easy current flow (rectification current) depends not only on the position of the HOMO and LUMO, relative to the Fermi levels of the metal electrodes before bias is applied, but also on their shift after the bias is applied: this situation is more complex than the Aviram-Ratner mechanism, and can provide a rectification current in the opposite direction. We calculate that the electrical rectification results from the asymmetric profile of the electrostatic potential across the system. We obtain that the C 16 H 33 tail plays an important role in this asymmetry, and we predict a more symmetric I(V ) curve in the case of molecules with a small alkyl chain. Quite generally, our work emphasizes the importance of the electrostatic potential profile in a molecular system and suggests that this profile could be chemically designed to build new devices.

To calculate the electronic structure and the geometry of the free molecules (gas phase), we have performed ab initio calculations, using the DMOL code 7 in the local density approximation (LDA) with the functional of Ref. [START_REF] Vosko | [END_REF] , and in the generalized gradient approximation (GGA) of Ref. 9 . The two approximations give very close results. We use a double numerical basis set(two atomic orbitals for each occupied orbital in the free atom), together with polarization functions (2p for H, and 3d for N and C). As the molecular diode is a complex system, which cannot be treated in LDA, we have developed self-consistent tight binding (TB) calculations, as described in Ref. 10 . We start from the GGA optimized geometries. C and N atoms are represented by one s and three p atomic orbitals, and H atoms by one s orbital. The diagonal terms of the Hamiltonian matrix are charge-dependent 10,11 (in atomic units):

H iα,iα = H 0 iα,iα - j Q j R 2 ij + ( e 2 U 2 0 ) -eV ext (i) (1)
where α is the orbital index, i and j are atomic indices (j runs over all the atoms of the system), Q j is the net charge on atom j, R ij is the distance between atoms i and j, U 0 is the intra-atomic Coulomb energy and the quantities H 0 iα,iα define the s and p atomic levels. V ext (i) is the potential induced by the charges on the electrodes. It is calculated using a self-consistent solution of the Schrödinger and Poisson equations, with the boundary condition imposed by the applied bias. The second term in eqn. 1 is evaluated using the method of Ewald 12 , taking into account the two-dimensional periodicity of the LB film. The molecules are ordered on a 9 Å× 6.5 Å rectangular lattice, corresponding to a molecular area of 58.5 Å2 , close to the experimental value of ∼ 50 Å2 3 . The molecules are inclined by 45 • , as measured experimentally 3 . Chemical interactions between molecules are supposed to be negligible. The LB film is sandwiched between two planar Al or Au electrodes, which we put at 3.2 Å from the edges of the molecule, a reasonable value for molecules in weak interaction with a metallic surface 13 . We applied our calculations to 1, but 3 also to molecules with a smaller alkyl chain or without alkyl chain (Q-3CNQ, 2) for reasons which will become clear later. As expected, the electronic structure cose to the gap does not depend on the length of the alkyl chain for the free molecules. We predict a large dipole moment of 21 D in LDA and 27 D in TB. The general results in LDA and in TB are quite similar, and agree with recent calculations 15 . Fig. 1 describes the original Aviram-Ratner mechanism 1 for a D-σ-A molecule. The electronic states are supposed to be totally localized either on the D side or on the A side. The HOMO(D) and LUMO(D) are high in energy, compared to, respectively, the HOMO(A) and LUMO(A). Therefore, a current can be established at relatively small positive bias, such that the Fermi level at the A side is higher than LUMO(A), and the Fermi level at the D side is lower than HOMO(D), providing that the electrons can tunnel inelastically through the σ bridge. Thus we expect an asymmetric I(V ) curve with an important rise of the current at positive bias above a given threshold (the electrode at A side is grounded, as in the experiments 3,4,6 ). In the case of our D(+)-π-A(-) molecules (1 and 2), LDA and TB calculations show that the HOMO and the LUMO are strongly delocalized on the whole molecule. Even if the HOMO is more localized on the A part and the LUMO on the D part, the extension of the wave functions on the opposite side exceeds 30%. Thus the two parts of the molecules cannot be decoupled, as in the original Aviram-Ratner model. This is obviously due to the π bridge between the donor and acceptor sites.

Because of the large dipole of the free molecule (27 D in TB), electrostatic interactions play an important role in the LB film. We plot in Fig. 2 the intensity of the dipole, when we vary the molecular area in a free monolayer without a metallic electrode. At a molecular area of 58.5 Å2 , the dipole is screened by a factor 2.6, due to the Coulomb interaction between the parallel dipoles. When the metallic electrodes are included, the dipole moment is enhanced, because of the attractive interaction between the charges in the dipole and those induced in the electrodes. We obtain a final dipole of 19 D in the diode at zero bias. This dipole layer gives rise to a built-in potential between the two sides of the film, as shown in Fig. 3, where we plot the average electrostatic potential in the system. In presence of the electrodes and at zero bias, opposite charges appear on the electrodes (5.8×10 -03 nelectrons/ Å2 ), so that the induced potential drop exactly cancels the one created by the dipole layer. When a bias is applied to the diode, the HOMO and the LUMO energies become linear functions of the voltage (V ), with the same slope (η) for the two levels (Fig. 4), which is another consequence of their delocalization. Indeed, if the two states wre localized at opposite sides of the molecule, the energy of the state closer to the grounded electrode would vary less than the other. For example, it was shown recently on D-σ-A molecules that the HOMO-LUMO gap is strongly distorted by the electric field 15 , because the two states are localized on different sites. In contrast, in our case of a D-π-A molecule, the gap is almost independent of the applied voltage. The slope η, obtained from the self-consistent calculation, strongly depends on the length of the alkyl chain (Fig. 5). It can be estimated, by comparing the center of the chromophore of the molecule with the molecular length. Thus, for Q-3CNQ, η = 0.49 (close to 1/2), because the potential drop is symmetrically shared in the molecule, while for molecule 1 it is 0.21 (close to 1/4), because the states are localized in the Q-3CNQ part, close to the grounded electrode, whereas a large part of the potential drop takes place in the alkyl chains, which have a small polarizability due to their large gap 16 . This important effect is particularly striking in Fig. 3, where we compare the electrostatic potential in the system at zero bias and at +2 V. The voltage drop in the molecular layer, and thus the factor η, can be simulated, using a simple dielectric model, where the different parts of the structure are described by a dielectric medium. We consider three regions: the vacuum gaps between the molecules and the metal electrodes, the Q-3CNQ part, and the alkyl chain, with respective widths d vacuum , d π , d alkyl , and respective dielectric constants ǫ π and ǫ alkyl .

We obtain easily:

η = 1 2 • 1 1 + ǫ π • d alkyl ǫ alkyl•(dπ + d vaccuum • ǫ π ) (2)
This equation explains well the dependence of η with the length of the alkyl chain (Fig. 5). The best fit is obtained with ǫ π = 10.0 and ǫ alkyl = 1.6, in agreement with the fact that the alkyl chains have a small polarizability. Measurements on monolayers of alkyl chains between metal electrodes give values of ǫ alkyl between 2.0 and 2.5, but for a density of one molecule per surface of 20-22 Å2 17 (compared to 58.5 Å2 in our case). Our calculations for such a monolayer with a molecular area of 20 Å2 gives ǫ alkyl = 2.1 , in agreement with the experiments.

III. CALCULATION OF THE CURRENT

The current intensity is calculated using the Landauer formula [18]

I = 2e h +∞ -∞ [f L (ǫ) -f R (ǫ)]T r{G a (ǫ)Γ R (ǫ)G r (ǫ)Γ L (ǫ)}dǫ (3)
where f L (ǫ) and f R (ǫ) are the Fermi-Dirac distribution functions in the left and right leads, respectively. G r,a (ǫ) are the retarded and advanced Green's functions of the molecule, and the Γ L,R (ǫ) matrices that describe the coupling of the molecule to the electrodes [START_REF] Meir | [END_REF] .

The Green's functions of the semi-infinite metal electrodes are calculated in TB [START_REF]Tight binding parameters for Al and Au have been fitted on a LDA band structure[END_REF] , using the decimation method 20 . The hopping matrix elements between metal orbitals (γ) and molecular orbitals (β) are restricted to the interactions with metal atoms of the top surfaces.

They are written

V γβ = S γβ (d) S γβ (d 0 ) V H γβ (d 0 ) ( 4
)
where d is the inter-atomic distance, d 0 is the sum of the covalent radii of the two atoms, and V H γβ (d 0 ) is the hopping integral, calculated from Harrison's rules 21 at the inter-atomic distance is the hopping matrix element, as calculated by Chen [START_REF] Chen | Introduction to scanning tunneling microscopy[END_REF] to study the current in a scanning tunneling microscope. The advantages of expression (4) are: i) at small distance d close to d 0 , the couplings are close to Harrison's values, which give a good description of the chemical interactions 21 ; ii) at larger distances (d >> d 0 ), the exponential dependence of the hopping integrals with d is correctly described by the expressions given by Chen [START_REF] Chen | Introduction to scanning tunneling microscopy[END_REF] . For a given bias, we calculate the self-consistent electronic structure and the Green's functions of the molecule in the LB film. The Green's functions of the whole system are calculated by coupling the molecules to the leads.

IV. RESULTS FOR AL ELECTRODES

Let us consider the case of Al electrodes. We need to discuss the problem of the position of the molecular levels with respect to the Fermi level of the electrodes at zero bias. We have considered three situations (a, b, c), which are summarized in Fig. 6. The first situation (a) corresponds to the vacuum level alignment, a common approximation for physisorbed molecules. The HOMO and LUMO energy levels are fixed, with respect to the metal work function (4.2 eV), by the ionization potential I and the electron affinity A, respectively.

A and I include the charging energy of the molecule, corresponding to its ionization when the current flows through the structure. We have calculated these values in LDA (I = 6.9 eV, A = 2.7 eV for 1 and 2). But, for an ionized molecule in the diode, we must also consider the screening due to the electrodes, i.e. the interaction energy between the extra charge (an electron in the LUMO ψ e or a hole in the HOMO ψ h and the image charges induced in the electrodes [START_REF] Ishii | Additional screening comes from the polarization of the surrounding molecules. A calculation of the transverse polarizability of the molecules in LDA shows that this effect is small[END_REF] . It is given fairly accurately, in first-order perturbation theory, by Σ h(e) =< ψ h(e) |V ind |ψ h(e) >/2 , where V ind is the electrostatic energy of a charge between two metallic electrodes. We obtain in TB Σ e = 0.53eV and Σ h = 0.62eV for 1 (resp. 0.90 eV and 0.97 eV for 2). We fix the molecular levels by applying a rigid shift to all unoccupied (occupied) states, such that the LUMO (HOMO) level position is given by A + Σ e (I-Σ h ). Fig. 6 (case a) shows that the Al Fermi level is closer to the LUMO level than the HOMO.

In fact, the vacuum level alignment does not occur in many metal-organic systems 25 . In our case, the alignment may be influenced by charge distributions in the thin Al oxide, which is unavoidably present between the Al electrodes and the LB monolayer 4 . The main effect is a rigid shift of the whole set of molecular energy levels 25 . Thus, in order to investigate a broad range of possible experimental situations, we have considered a second situation (b) corresponding to the Al Fermi level at the middle of the HOMO-LUMO gap and, a third situation (c), symmetric to the first one, where the Al Fermi level is closer to the LUMO level. The calculated I(V ) characteristics are plotted in Fig. 7 for molecule 1, with its long alkyl chain. In the level configuration (a), we predict an asymmetric I(V ) curve with a forward behavior at negative bias, contrary to the Aviram-Ratner situation. The onset of the current at -1.1 V corresponds to the resonance of the LUMO level with the Fermi level of the D(+)-side electrode, as shown in Fig. 4. The electrical rectification arises from the asymmetric profile of the electrostatic potential across the system, leading to η = 1 2 . The resonance of the LUMO with the Fermi level of the A(-)-side electrode could only occur at high positive bias (3.7 V). In configuration (b), the resonance with the LUMO shifts to a more negative voltage (-1.8 V) but there is an additional onset at +1.8 V, corresponding to the resonance with the HOMO level (almost invisible in Fig. 7 because the transmission coefficient is small). Finally, in configuration (c), only this latter resonance is possible at +1.0 V, giving rise to a rectification at positive bias. The situation is completely different in the case of Q-3CNQ (inset of Fig. 7), where η ≈ 1 2 . If a Fermi level of an electrode energetically reaches some molecular level at a given bias, the same effect occurs symmetrically with the Fermi level of the other electrode at the opposite bias (Fig. 4). This leads to -almost 26symmetric I(V) curves for the three configurations (a, b, c). Experimental studies [3][4][5] have been made on molecules 1 with a long alkyl chain; some Al|monolayer|Al devices show (i) a rectification at positive bias and relatively low current 5 ,(ii) some have symmetrical I(V ) curves, and (iii) some have relatively high currents and rectification at negative bias 4 . The calculations presented here would make case (i) correspond to configuration c, where the HOMO level is close to the metal Fermi level, and case (iii) correspond to configuration a, where the LUMO level crosses the Fermi level of the Al electrode with bias applied to it. All this experimental variability is either due to molecules turning upside down after film deposition and before measurement 3 , or it is due to non-uniform charges in the thin Al oxide 5 .

V. RESULTS FOR AU ELECTRODES

Recent experiments 6 have been performed on LB films of the same molecules but using oxide-free Au electrodes. All the operating devices (not short-circuited) are rectifying at positive bias with a threshold at ∼ +1.6 V (Fig. 8). The main difference between Au and Al electrodes comes from the metal work function (resp. 5.3 eV and 4.2 eV). Shifting the zero bias Fermi level at -5.3 eV, we can just transpose the results of Fig. 4, from which we calculate the voltages for the resonance between the HOMO-LUMO levels and the Fermi levels. As oxide charges cannot be invoked in the case of Au electrodes, we have only considered the situation (a) where levels are aligned with respect to the vacuum level. We obtain in this case a rectification at positive bias (+1.24 V) in agreement with the experiments, corresponding to the resonance of the HOMO with the Fermi level at the D(+)-side electrode (situation close to the case c for Al). The resonance with the Fermi level at the A(-)-side only occurs at -4.6 V. We compare in Fig. 8 one typical experimental I(V ) curve 6 with the calculated one for Au|C 16 H 33 Q-3CNQ|Au. As discussed above, the theory predicts a rectification at positive bias, in agreement with the experiments. But we have been obliged to multiply the calculated current by a factor 10 3 to be on the experimental scale. We have checked that there is no way to explain this factor by reducing the distance between the molecules and the electrodes. Thus one possible explanation is that some metal of the top Au electrode deposited on the LB film has slightly diffused in the molecular layer. This is equivalent to a reduction of the length of the alkyl chain, which acts as a barrier for the tunneling of the electrons. Fig. 8 shows that a correct magnitude of the current is obtained for Au|C 8 H 17 Q-3CNQ|Au, or equivalently for a diffusion of gold over a length of ∼ 4 Å(taking into account the tilting of the molecules). This is quite realistic with gold electrodes, even if the experimental procedure of Ref. 6 has been designed to avoid at maximum the diffusion of the metal. The theory predicts a saturation of the current at high voltage, which is not observed experimentally as the experimental threshold (∼ +1.6 V) is at higher voltage. We must add that the step-like dependence of the calculated current would be broadened by taking into account the interactions between the molecules or the coupling to molecular vibrations. On the experimental side, the application of high bias starts to degrade the molecular diode 6 .

VI. CONCLUSION

In conclusion, we have presented detailed calculations of the I(V ) characteristics in a LB film of C 16 H 33 Q-3CNQ sandwiched between two Al or Au electrodes. We show the importance to include Coulomb interactions and screening effects in a self-consistent manner. Inescapable conclusions are that the placement of the electroactive part of the molecule within the gap between metal electrodes is very important, and that an important experimental issue in the future will be to control the band alignment at the organic-metal interface. 13

FIG. 1 :FIG. 2 :FIG. 3 :FIG. 4 :FIG. 5 :FIG. 6 :

 123456 FIG. 1: Top (a): Schematic representation of C 16 H 33 Q-3CNQ and of the diode. Bottom (b): the Aviram-Ratner mechanism for molecular rectification.

FIGURESFIG. 8 :

 8 FIGURES

Acknowledgments

The Institut d'Electronique et de Microélectronique du Nord is UMR 8520 of CNRS.

20


Christophe Krzeminski

Christophe Delerue

Guy Allan

Tight binding description of the electronic response of a molecular device to an applied voltage

teaching and research institutions in France or abroad, or from public or private research centers.

I. INTRODUCTION

Recent measurements of single molecule transport properties [START_REF]Molecular Electronics: Science and Technology[END_REF][START_REF] Reed | [END_REF][3] represent important contributions to the eventual realization of molecular electronics. This is accompanied by an increasing theoretical effort to understand the relationship between the electronic structure of the molecules and the current-voltage I(V ) characteristics. Until recently, most of the calculations based on tight binding (TB) or ab initio methods 1 did not explicitly include the effect of the applied voltage on the electronic structure of the molecules. This is a severe drawback since several volts can be applied to the electrodes in contact with a single molecule. In the some cases 4 , the energy of the molecular electronic levels is approximated by a linear function of the voltage but its slope is not calculated or is approximated by 1/2.

An approach to overcome these limitations has been proposed 5,6 recently on the basis of a Hubbard Hamiltonian 7 and has been applied to the azulene molecule 5 and to polyacene wires 6 . But the Hubbard Hamiltonian is a model Hamiltonian which only gives qualitative predictions. On the other hand, ab initio methods cannot be easily applied to complex systems. Thus there is a need for simpler methods which correctly predict the response of the molecules and the dependence of the electronic levels as function of the applied bias. This is a prerequisite to calculate the I(V ) characteristics of a molecular device. In this paper, we present self-consistent TB calculations of various molecules. We study the evolution of the dipole and of the electronic levels with the voltage. We obtain results in good agreement with ab initio calculations in the local density approximation (LDA). This is a good test of our method and allows to extend it to large systems. We conclude that our self-consistent TB technique is a promising approach to study the transport properties in a molecular device and that it may be applied to a wide range of systems.

II. CALCULATIONS

The molecules considered in this work are shown in Figure 1. In order to compare with previous results 5,6 , we study tetracene and azulene molecules as prototypes of molecular wires. The calculations are also applied to quinolinium tricyanoquinodimethanide (Q-3CNQ) and to 3,5-dinitrobenzyl 7-(1-oxohexylamino)-pyren-2-ylcarbamate (OHAPy-C-DNB) which are respectively D-π-A and D-σ-A molecules. D and A are respectively elec-tron donor and acceptor. π and σ are respectively "pi" and "sigma" bridges. These two molecules are intensively studied to make molecular diodes 8,9 . The electronic structure of all the molecules is obtained in LDA and in TB. In LDA, we use the DMOL code 11 with a double numerical basis set (two atomic orbitals for each occupied orbital in the free atom) together with polarization functions (2p for H, 3d for N, O and C). The exchange-correlation energy is approximated by the density functional of ref [START_REF] Vosko | [END_REF] . The self-consistent TB technique is presented in another publication 13 where we calculate the electronic structure of thienylenevinylene oligomers, showing a good agreement with LDA calculations and experiments. C, N, O atoms are represented by one s and three p atomic orbitals, and H atoms by one s orbital. The non-diagonal terms of the Hamiltonian matrix H are restricted to first nearest-neighbor interactions and to two-center integrals. They depend on the interatomic distance following Harrison's rules [START_REF] Harrison | Electronic Structure and the Properties of Solids[END_REF] . The self-consistency is incorporated in the diagonal terms H iα,iα (α is the orbital index, i is the atomic index)

H iα,iα = H 0 iα,iα - j Q j R 2 ij + ( e 2 U 2 0 ) -eV ext (i) (1)
where H 0 iα,iα define the atomic levels, U is the intra-atomic Coulomb energy, R ij is the distance between atoms i and j, and Q j is the net charge on the atom j. The TB parameters are determined by a fit of the LDA electronic structure of simple molecules 13 . The parameters for C-C and C-H interactions are given in Ref 13 , those for C-N, N-H, C-O, N-O interactions are in Table I. The selfconsitency is obtained with an usual iterative method which is converged when the atomic charges Q j in eq. ( 1) correspond to the charges calculated from the eigenstates of the Hamiltonian. V ext in eq. ( 1) is the electrostatic potential resulting from the applied electrostatic field which, for simplicity, is assumed homogeneous, corresponding to a situation where the electrodes would be far from the molecule. Obviously, to calculate the I(V ) curve, we should consider the chemical and electrostatic interactions between the molecule and the electrodes. This can be done in TB but this is beyond the scope of the present paper.

The applied electric field E is parallel to the long axis (z) of the molecules (Figure 1).

The origin of the electrostatic potential (V ext = 0 ) is defined at 2 Å from the left side of the molecules. Thus V ext (i) = Ez i where z i is the coordinate of the atom i along the axis z. All the results presented in this paper are plotted as a function of the electrostatic potential at 2 Å from the right side of the molecules. Equivalently, a bias of 1 V corresponds to an applied electric field of 88 mV/ Å, 64 mV/ Å, 57 mV/ Å and 46 mV/ Å respectively for azulene, tetracene, Q-3CNQ and OHAPy-C-DNB (the inter-electrode distance is 11.4 Å, 15.5 Å, 17.4 Å and 21.6 Å, respectively). We plot in Figure 2 the voltage dependence of the dipole moment of the four molecules. Azulene has a small permanent dipole moment resulting from its nonalternant character [START_REF] March | Advanced Organic Chemistry[END_REF] . Q-3CNQ is characterized by a large dipole moment due to charge transfer between acceptor and donor sites. OHAPy-C-DNB have weaker acceptor and donor characters. We see that the agreement with LDA is good. In particular, the overall magnitude and the slopes of the curves (or the polarizabilities) agree well. It means that the charge transfers induced by the applied bias are correctly described.

In ref 5 , the dipole moment of azulene was not calculated, but equivalently the charge on the five-membered ring was plotted as a function of the voltage. Between -3 V and +3 V, a variation of this charge of 0.5e is reported to be compared with our much smaller value of 0.3e. We present in Figure 3 the voltage dependence of the energy levels of tetracene. A very good agreement is obtained with LDA results, which was not the case with the Hubbard Hamiltonian 7 . The variation of the levels is mainly linear, with a slope 1/2 as expected from the symmetry of the molecule. In spite of an asymmetric atomic structure, quite similar results are obtained for Q-3CNQ (Figure 4) with a slope 0.52 for the highest occupied orbital (HOMO) level and 0.49 for the lowest unoccupied orbital (LUMO) level in TB (resp. 0.56 and 0.55 in LDA). This is a consequence of the delocalization of these orbitals over the whole molecule, which results from an efficient coupling between acceptor and donor sites through the π bridge. The situation is completely different in the case of OHAPy-C-DNB (Figure 5) because the σ bridge leads to a much smaller coupling between the acceptor and donor parts. Therefore, the HOMO is mainly localized on the acceptor site and the LUMO on the donor site. As the donor site is closer to z = 0 where the origin of the potential is defined, the voltage dependence is smaller for the HOMO than for the LUMO. All these important tendancies are predicted similarly in LDA and TB, even if TB calculations underestimate the HOMO-LUMO gap compared to LDA in the case of OHAPy-C-DNB. Thus, even if Q-3CNQ and OHAPy-C-DNB are donor-acceptor molecules, their electrical characteristics will completely differ because of different voltage dependence of the levels. We have also studied the effect of an applied voltage on other molecules like thienylenevinylene oligomers 13 and the γ-hexadecylquinolinium tricyanoquinodimethanide (C 16 H 33 Q-3CNQ, Figure 1). The response is also linear between -3V and +3V, and the agreement between TB and LDA remains good. The case of C 16 H 33 Q-3CNQ is interesting because it differs from Q-3CNQ only by the replacement of an hydrogen atom by an hexadecyl group. Thus the HOMO and the LUMO are almost the same in the two molecules. However, their voltage dependence in C 16 H 33 Q-3CNQ is characterized by a much smaller slope (∼ 0.2) due to the fact that a large part of the voltage drop takes place in the long C 16 H 33 group which is weakly polarizable, while the HOMO and the LUMO are localized in the remaining part of the molecule. Once again, we expect completely different I(V ) curves for these two molecules in spite of their important similarities.

IV. CONCLUSION

We have presented a self-consistent TB method to study the response of molecules to an electric field. Our work justifies for a broad range of molecules the hypothesis of a linear dependence of the molecular levels with respect to an applied voltage 4 , even up to several volts. The self-consistent TB method provides a simple approach to calculate this dependence with enough accuracy. It represents a good compromise between model Hamiltonians and ab-initio calculations. It will be useful to simulate more complex systems, to calculate the charging energy of molecules 13 and to predict the I(V ) characteristics of molecular devices.

(ss σ) -3.62 -

FIG. 1 :FIG. 2 :FIG. 3 :FIG. 4 :

 1234 FIG. 1: Molecular structure of a) azulene, b) tetracene, c) C 16 H 33 Q-3CNQ, d) OHAPy-C-DNB. The line at the left side of the molecules defines the zero of the potential V ext .

TABLE I :

 I TB parameters in electron volts. The first nearest-neighbor interactions are given for an interatomic distance d 0 ( Å)

			7.54 -3.32 -2.90 -6.96
	(sp σ)	+4.96 6.03 +4.50 +3.68 3.66
	(pp σ)	+5.31	+4.55 +5.23
	(pp π)	-2.00	-1.98 -2.00
	d 0	1.54 1.07 1.54	1.07
	Atomic levels N	O
	E s	-12.17 -16.17
	E p	-7.97 -8.77

Acknowledgments

The Institut d'Electronique et de Microélectronique du Nord is UMR 8520 of CNRS.