Junfang Zhu
email: junfang.zhu@gmail.com

Hui Zhang
email: huizhang@tsinghua.edu.cn

Yamei Wen
email: yamei.wen@gmail.com

A new reconstruction method for 3D buildings from 2D v ector floor plan

Keywords: 3D reconstruction, vector floor plan, space information

This paper proposes a method to analyze the geometry and semantic information of 2D vector floor plans, and reconstruct the corresponding 3D building models automatically. First, the Shape-opening graph (SOG) is introduced to recognize Structural Components (SCs) and describe the relationships between SCs and openings which are architectural components separating spaces. A priority principle algorithm is developed to replace openings with wall equivalent lines for the purpose of later loop searching. Then, we present an odd-even-based edge breaking algorithm to preprocess wall lines in order to search loops directly and exactly. After that, all the interior-space contours, which are in fact rooms or aisles, and exterior boundary contour can be obtained. With the hierarchical component tree presented, the topological relations of the whole building can be obtained. Finally, 3D models can be generated after extruding loops to the wall height and cutting openings from the walls. A drawing with several floor plans can also be reconstructed to multi-floor building after aligning their dimensions. Moreover, the intermediate result after analyzing the 2D floor plan can be the input of other architectural software to generate 3D models.

INTRODUCTION

2D architectural floor plans are a standard way to express design by architects and are widely used in the field of architecture. Fig. 1 is a real 2D vector architectural floor plan. 3D building models are intuitive and also support many applications. Using 3D building models for fire simulations can give valuable insight into building usability and safety [START_REF] Lewis | Generation of 3D building models from 2D architectural plans[END_REF]. Rendering on 3D building models makes the building more realistic. The popularity of navigation through virtual 3D environments is also rapidly growing. However, creating the 3D model of a set of floor plans manually is nontrivial and requires s k i l l a n d t i m e [ 1 5 ] . S o c o n v e r s i o n o f 2 D f l o o r p l a n s i n t o 3 D m o d e l s a u t o m a t i c a l l y i s o f g r e a t significance. A building in real life is usually composed of many functional spaces, such as rooms, corridors, etc. Functional spaces are separated by walls, and openings such as doors and windows. Corresponding to the 2D architectural floor plan, functional spaces are presented by loops which are made up of wall lines and openings. So, reconstructing a 2D architectural floor plan to 3D model has three main tasks: 1) recognizing component symbols such as walls, doors, windows; 2) loop searching to get space information; 3) extrusion to get the finally 3D models.

Since vector architectural floor plans from real-life are in various styles, we assume that a typical architectural floor plan has the following characteristics:

x There are only lines, arcs and text existing in the drawing. Other types of graphic items, such as POLYLINEs, are converted into lines and arcs first in our preprocessing automatically. x

Structural Components like walls and openings like doors can-not be isolated. They must be connecting to or near to other openings or Structural Components.

The rest of this paper is organized as follows. Related work is summarized in Section2. Section 3 presents the Shape-opening graph (SOG) to detect walls and create wall equivalent lines for openings. In Section 4, we describe loop searching method to get space information and build the topological tree. Experimental results are shown in Section 5. Finally, we conclude the paper in Section 6.

RELATED WORK

There are two main formats for the existing architectural floor plans: digitally scanned format and vector format. Some early architectural drawings are drawn on papers. These drawings have been kept and handed down in the format of raster image. As far as we know, almost all the existing methods convert the raster image into vector format first, except [START_REF] Ahmed | A: Improved Automatic Analysis of Architectural Floor Plans[END_REF] which processed directly on the raster images to analyze drawing and recognize symbols. Ah-Soon [START_REF] Ah-Soon | K: Network-based recognition of architectural symbols[END_REF][START_REF] Ah-Soon | Variations on the analysis of architectural drawings[END_REF] proposed a network-based method to recognize architectural symbols. Dosch [START_REF] Dosch | Reconstruction of the 3D Structure of a Building from the 2D Drawings of its Floors[END_REF][START_REF] Dosch | G: A complete system for the analysis of architectural drawings[END_REF] presented a system for the analysis of architectural drawings. They designed a method for dividing large image into tiles, each of them being processed and analyzed independently. Or [START_REF] Or | Highly automatic approach to architectural floor plan image understanding and model generation[END_REF] proposed a highly automated approach to generate 3D model from a 2D floor plan. It assumed that two polylines with opposite propagating directions and in a certain distance should correspond to a wall. Kishen [START_REF] Kishen Moloo | 3-Phase Recognition Approach to Pseudo 3D Building Generation from 2D Floor Plan[END_REF] devised a 3-Phase recognition approach to generate 3D building from 2D floor plan. They used clustering technique to group lines into bounding boxes, each representing a potential wall. Park [START_REF] Park | Main wall recognition of architectural drawings using dimension extension line[END_REF] suggested a method for recognizing main walls based on extension lines, assuming that a main wall contains an auxiliary dimension line inside it. This kind of methods rely heavily on the robustness of the vectorization algorithm and focus on low-level process, i.e., segmentation, detection of arc from scanned drawings. Because all the exiting vectorization methods are not good enough, these methods usually involves human interactions.

Since 1990s, architectural drawings produced by CAD software (e.g. AutoCAD) have become popular, making the storage, editing and processing of data much easier than before. Therefore, in this paper we only focus on the reconstruction of vector architectural floor plans.

So [START_REF] So | H: Reconstruction of 3D virtual buildings from 2D architectural floor plans[END_REF] first incorporated automated approaches to the three streams to accomplish the reconstruction goal: wall extrusion, object mapping, and ceiling and floor reconstruction. The processing time has been shrunk approximately 10% to 15% of the overall manual tasks, but it still needs a lot of manual work.

Lewis [START_REF] Lewis | Generation of 3D building models from 2D architectural plans[END_REF] developed a semi-automatic system to create 3D polyhedral building models from AutoCAD DXF geometry description format. The system has utilised room label as seed point to find interior space contours and replaced each door symbol with two separate edges. Because of extruding each edge separately, the system still needs a few days to accomplish a building under some sort of human intervention.

Zhi [START_REF] Zhi | A graph-based algorithm for extracting units and loops from architectural floor plans for a building evacuation model[END_REF] presented an automatic approach to transfer computer-dawn architectural plans into a building fire evacuation simulator model. The system assumed that the drawing is a combination of units and a unit is a combination of loops. They searched loops using a graph directly in the drawing under suitable layers. The limitation is that this system can't handle drawings composed of complicated graphical primitives. Dom´Önguez [START_REF] Dom´önguez | Semiautomatic detection of floor topology from CAD architectural drawings[END_REF] presented a method for detecting the topology of building floors semiautomatically. The method involves the detection of walls and joint points amid walls and openings, and the search of intersection points amid walls. For the representation of opening with wall segments, it must involve user interaction and they assumed that doors and windows are represented by blocks.

Lu developed systems to construct models from computer-drawn construction structural drawings [START_REF] Lu | A new recognition model for electronic architectural drawings[END_REF] and architectural working drawings [START_REF] Lu | Shijie Cai: Automatic Analysis and Integration of Architectural Drawings[END_REF] which have no labels to indicate component types. Based on the three types of the most frequently occurring shapes T, X, L, it detects parallel line-segment pairs as walls and removes them from the drawing. The remaining architectural symbols are detected by finding features that match with predefined patterns.

In this paper, we focus on getting the topological and semantic information of spaces as well as generating 3D models after analyzing 2D architectural floor plans. The hierarchy tree which presents the relationships among space and architectural components is also created for some applications and being output to other software. We can also construct multi-floor 3D models after analyzing the 2D architectural drawing of its floors by matching their axes in the drawing.

COMPONENT SYMBOL RECOGNITION

2D architectural floor plans contain inner spaces such as rooms and corridors, and the outer contour of building. Different spaces are separated by walls and openings. Therefore, after all basic geometric elements are obtained from vector architectural floor plans, we first recognize openings such as doors, windows, decorative components such as furnitures, and Structural Components such as walls before reconstruction.

Decorativ e Sy mbol Recognition

Definition 1 (Wall Side): The direction of a wall is from the lower left points to the upper right points of its wall lines. The left or right side of the wall direction is called the Wall side.

After openings and decorative components were recognized by the symbol recognition algorithm based on key features proposed by Guo [START_REF] ; Z H A N G | A n I m p r o v e d E x a m p l e -D r i v e n S y m b o l R e c o g n i t i o n A p p r o a c h i n Engineering Drawings[END_REF], more semantic information of some key symbols, such as doors, slide doors windows and bay windows, is analyzed in order to provide basis for more realistic 3D models.

The semantic information of door is facing direction and door-axis. The facing direction can be obtained from determining its Wall Side while door-axis can be determined according to the position of the arc and wall lines beside the door. Fig. 2(a) is a door symbol. It faces upside and its door-axis is on the left as Fig. 2(e) shows. Based on the position of the wall next to the door-axis, a rectangle (red lines in Fig. 2(e)) to represent the 2D model of the door is created. The length of the rectangle is the radius length of the arc and the width is a default value. All these semantic rectangles will not be used for recognizing walls in Section 3 and searching loops of spaces in Section 4. They are for constructing 3D models for openings in Section 5.

Wall Element Identification

After openings and decorative symbols are recognized, Structural Components are then detected in the remaining basic geometric elements. In vector floor plans, Structural Components, such as walls and beams, are usually presented by two parallel lines (PP). Because a large number of other parallel lines such as dimensions exist, detecting two parallel lines within a certain distance directly in the drawing cannot be used to identify walls.

Through analysis of PPs, Lu [START_REF] Dosch | Reconstruction of the 3D Structure of a Building from the 2D Drawings of its Floors[END_REF] proposed a method to detect walls by recognizing the three types L, T, X at the intersection of walls. Besides these three types, we find another shape I which is actually a wall not intersecting with other walls, which means it has openings on its both sides. The I shape is represented as a rectangle which is made up of two pairs of PPs intersecting at the endpoints of each PP line in 2D floor plans. After analyzing a large number of drawings, we find that each Basic Structural Element must have one or more neighboring Basic Structural Elements. That means X, L, T shapes either intersect with other shapes or be adjacent to openings, and I shape has openings at its both sides. An opening is adjacent to shapes or other openings. Based on such basis, openings that have already been recognized can be used to identify walls.

We introduce the Shape-Opening Graph SOG = (N, E), where N is a node set and E is an edge set. Nodes in the graph are one-to-one corresponding to the Basic Structural Elements and edges present the relationships between Basic Structural Elements. The graph generation process is the process of identifying PPs as well as building the topological relationships between PPs and openings. The outline of the algorithm is: First, select any of the recognized openings as the initial node of SOG. Then add nodes that have relationships with nodes in SOG and create edges between them. Recursive these two processes until all the openings are added to SOG.

The shapes in SOG are obtained in the following method: The three shapes T, L and X can be recognized using the algorithm of Lu [START_REF] So | H: Reconstruction of 3D virtual buildings from 2D architectural floor plans[END_REF] and the I shape can be got from the intersecting PPs as follows: If there are two PPs, P1 and P2, and the endpoints of the two lines in P1 are the endpoints of the two lines in P2, then P1 and P2 form an I shape.

After the SOG is established, each PP in SOG makes up a wall and the lines of a PP are called wall lines.

Fig. 4(a) is the original architectural floor plan. Fig. 4(b) shows the recognized shapes and wall lines. In Fig. 4(b), there are several shapes not intersecting with others, as the blue shapes shown in Fig. 4(b), our method can identify them correctly, while they can not be handled by the algorithm proposed by Lu [START_REF] So | H: Reconstruction of 3D virtual buildings from 2D architectural floor plans[END_REF].

Wall Equiv alent Lines

Because walls are cut off by openings, several recognized PPs may represent the different parts of the same wall. In order to restore the integrity of the wall, we introduce the Wall Equivalent Lines (WELs) to replace openings. A WEL is represented by two parallel lines in the position of the opening to connect its adjoining wall PPs.

Besides an opening has walls at its both sides, there also exist two or more openings adjoining side by side in real architectural floor plans, which means, opening A adjoins opening B, or even B adjoins another opening C. If there are more than one opening adjoining, we need to merge them first to take them as a whole for follow-up processing.

Creating wall equivalent lines for an opening can be achieved by calculating its nearest PPs. Every opening keeps its nearest PPs in a set NP. If the number of PPs in the NP set of the opening is greater than 2, extra operation needs to be carried out by our following priority-based principles. 1). If the opening is between two parallel PPs which are in the same line (Fig. 3(a)), create the wall equivalent lines by extending the two lines of one PP to the other as shown in Fig. 3(f) 2). If the opening is between two parallel PPs which are not in the same line (Fig. 3(b)), the center point of the bounding box of the opening is first calculated, followed by creating two parallel edges which are half of wall's thickness away from the center point and perpendicular to the parallel PPs (Fig. 3(g)).

3). If the opening is between two perpendicular PPs and the projection of P1 to P2 is in P2 (Fig. 3(c)), extend P1 until it meets P2 (Fig. 3(h)). 4). If the opening is between two perpendicular PPs whose intersection is in their extended lines (Fig. 3(d)), extend both of the PPs until they intersect (Fig. 3(i)).

The wall equivalent lines added are shown in red in Fig. 3(f)-Fig. 3(j). The priorities of the above situations are decreasing by the narrating order, that is, only if there are no PPs satisfying the first type, the second type could be considered. For example, Fig. 3(e) satisfies both type 1) and 3), but we handle it as type 1) just because its priority is higher.

P1 P2 (a) (b) (c) (d) (e) (f) (g) (h) (i) (j)
Fig. 3: Examples of openings and their surrounding PPs, and the corresponding wall equivalent lines.

The algorithm of recognizing walls and creating wall equivalent lines can be described as follows.

Algorithm1: WallRecoAndWallEquivalentLines Input: recognized opening set OS and shape set SS in the drawing. Output: all the wall lines. 1: Set every opening in set OS and every shape in set SS unmarked; 2: Select an opening from OS to be the first node of graph SOG;

3: for each unmarked S i in SOG do 4:

Find its adjacent openings and adjoining shapes; 5:

Create nodes for the found openings and shapes; 6:

Create edges between the nodes just created and S i ; If searching loops directly among the wall lines and WELs, different types of loops may be detected: loops of functional spaces (rooms, corridors, outer contour), wall contour (redundant loops) and loops with no semantic information (error loops). But some loops, which should be searched, couldn't be found out. For example, in Fig. 4(c), the left red loop presents a room. The left green loop is a wall contour which is redundant. The outer contour of the building couldn't be found because of the dangling edge.

In order to ensure that all the searched loops have semantic meaning, e.g. each loop is a functional space, we preprocess the wall lines and wall equivalent lines got in Section 3 if the intersections of them are not their endpoints (see Fig. 5) or there exists dangling wall lines which means the degree of one endpoint of a wall line is 1 as Fig. 6 shows. After the preprocessing, the edges and vertices satisfy the following two conditions:

x Adjacent edges only intersect at their start or end points. x

The degree of each vertex is 2, i.e. every vertex connects two edges.

In order to remove the InnerPoint, we propose an odd-even-based method to break wall lines. For the case of odd InterPoint(s), as shown in Fig. 5(a), if wall line W1 intersects with other wall lines at P1 and E1, line segment P1E1 should be deleted in order to eliminate the InnerPoint P1, as Fig. 5(b) shows. If the number of interPoints in a wall line WL is n and n is odd, the number of walls crossing WL is (n+1)/2. n/2 walls have two InnerPoints in WL and one wall has an InnerPoint wall thickness away from one of the endpoints.

For the case of even InterPoint(s), as shown in Fig. 5(c), if wall line W1 intersects with wall line W2 and W4 at the InnerPoints P1 and P2, line segment P1P2 should be deleted and wall line W1 is separated into two wall lines, as Fig. 5(d) shows. If the number of interPoints in a wall line WL is n and n is even, the number of walls crossing WL can be n/2 or n/2+1. The former one means that all the walls crossing WL has two interPoints in WL. The latter one means that besides n/2-1 number of walls having two interPoints with WL, there are also two walls crossing WL with one interPoint.

For each wall line, the interPoints array VR is first calculated. According to the number of VR, we implement the algorithm 2. if (the number of VR is even) then 5:

for each vr i in VR do 6: if there exists a vertex vr j t away from vr i then 7:

Create an edge e from vr i to the endpoint near it The time complexity of Algorithm 2 is O(L 2 ), where L is number of wall lines in the drawing.

If the degree of one endpoint of a wall line is 1 as Fig. 6(a) shows, we create a wall-thickness edge to connect the two wall lines, as the green line shown in Fig. 6

Searching Loop

After preprocessing, there are two kinds of loops in the floor plan: inner loop, which indicates spaces, typically rooms and corridors, and the outer contour. Because the degree of each vertex is 2, using any vertex that has not been traversed as the first vertex, travelling in the counterclockwise direction, all the loops can be obtained. The loop containing the minimum value of x or y is the outer loop. Fig. 7(b) shows an example of searched loops. The red loop is the outer loop and the blue loops are the inner loops. The time complexity of searching loops T4 is O(L).

Semantic Analy sis Of Space

Definition 4 (Adjacent Space): If two spaces have a common wall and they can be accessed through a door, they are Adjacent Spaces. For example, in Fig. 7(b), the Adjacent Spaces of inner space S1 are S2, S3, S4, S5, S6, S8. Definition 5 (Space Distance): For two spaces S1 and S2, their Space Distance SD = SD1 + SD2. SD1 is the distance between the center point of S1 and their common door. SD2 is the distance between the center point of S2 and the door. Specially, if a space A has a door to outside, its distance to outside area is the distance between the center point of A and the door.

With the text in the drawing, we can get the semantic meaning of each space like parlor, dining room and bedroom. A hierarchical component tree is established to describe the topological relations of the building and the root is the building itself. The second layer of the tree is semantic spaces, such as rooms and corridors, and the outer contour. Each space contains a pointer pointing to its Adjacent Spaces. The third layer of the tree is walls and openings. Each wall contains the openings in it.

The hierarchy tree is useful in many applications. It can be saved and put to other software such as REVIT to construct 3D models. It also can be used to generate target path for fire evacuation system. To find the shortest path from an inner space to outside, a travel-graph TG = (N, E) is created, where N is a node set and E is an edge set. Each node presents an inner space or the outside area. If two spaces are Adjacent Spaces, an edge is created between the two corresponding nodes. The weight of each edge is the Space Distance of the two spaces. The nearest path from an inner space to the outer area can be obtained using the Dijkstra algorithm.

3D EXTRUSION AND EXPERIMENTAL RESULTS

Single Floor Extrusion

The final 3D model can be obtained by the following steps:

(1) Extruding the outer loop to the wall height to form the original 3D model.

(2) Cutting the inner loops from above 3D model.

(3) Building the floor according to the inner loops.

(3) Cutting openings from the model.

(4) Building the 3D models of doors, slide doors, windows, bay windows as follows:

x The 3D model of door is created by extruding its 2D rectangle loop model from the bottom of the space to the default height of door. x

The 3D model of slide door is created by extruding its 2D rectangle loop model from the bottom of the space to the default height of slide door. x

The 3D model of window is created by extruding its two 2D rectangle loops from the window base to the window ceil. x

The 3D model of bay window is created by extruding it outer loop and minus the inner loop.

Multi-Floor Model Reconstruction

The 3D structure of a building can be obtained by analyzing the 2D architectural drawings of its floors. Every floor is aligned to the first floor by matching their axes in the drawing. An axis has one axis line connected to a circle with text, e.g. Axis (line, circle, text). There are four types of axes:

x Horizontal-left: The line of the axis is horizontal and the text of the axis is on the left of the drawing.

x

Horizontal-right: The line of the axis is horizontal and the text of the axis is on the right of the drawing.

x Vertical-up: The line of the axis is vertical and the text of the axis is on the upside of the drawing.

x Vertical-down: The line of the axis is vertical and the text of the axis is under the drawing.

Definition 6 (Equal Axes): Two axes in different floor plans are equal axes if and only if they are of the same type and their texts are the same.

To align more than one floor plan is to match the Equal Axes in these floor plans. Take two floors as the example, the steps of aligning floor F2 to F1 is as follows:

(1) Find all the axes of each floor plan.

(2) Determine the type of each axis.

(3) Select a horizontal axis h1 in F1, find its equal axis h2 in F2.

(4) Select a vertical axis v1 in F1, find its equal axis v2 in F2.

(

CONCLUSION

In this paper, we present a method to analyze 2D architectural floor plans, get the topological and semantic information of spaces and reconstruct the corresponding 3D models.

The reconstruction process is very fast and it can reconstruct a floor plan containing thousands of geometric primitives in several minutes because of using the loop extruding method rather than extruding each wall separately. As we analyzed in the earlier section, the time complexity of reconstructing a floor plan is O(N 2 ). The working space needed for the reconstruction is O(N). Second, the 3D reconstructed model contains not only geological but also semantic information, the comprehensive structure information of buildings can help the research of other related work. Moreover, the topological information of the whole building are generated using a tree. The topological tree can be put to other architectural software such as REVIT to generate 3D models. Finally, multi-storey building can make the overall structure of the building more clearly unfolded.

As we analyzed in the earlier section, the time complexity of reconstructing a floor plan is O(N Many existing methods need semantic information in the drawing when recognizing architectural components such as walls [START_REF] Lewis | Generation of 3D building models from 2D architectural plans[END_REF] , in [START_REF] Dom´önguez | Semiautomatic detection of floor topology from CAD architectural drawings[END_REF] the openings should be in blocks. Instead, our method can handle drawings without any additional information when recognizing walls in Section 3.2. After recognition of components, the 3D extrusion using loop extrusion method is faster than many of the existing algorithm, such as [START_REF] Lewis | Generation of 3D building models from 2D architectural plans[END_REF] who extruded each wall respectively. The time complexity of extra loop searching step is O(W), which is much smaller than extrusion and bollean operation.

Further research includes recognizing isolated walls not adjacent with any components, handling drawings with columns and beams, improving the efficiency of the algorithm and matching different floors with no axes.

Fig. 1 :

 1 Fig. 1: An example of architectural floor plan.

Fig. 2 (

 2 Fig. 2(b) is a slide door symbol. The 2D model of slide door is two adjoining rectangles which share a vertex and have two edges on the same line as Fig. 2(f) shows. The length of each rectangle is half length of the slide door and the width is half the thickness of the wall.

Fig. 2 (

 2 Fig.2(b) is a window symbol. The orientation is the semantic information of window. We just use two rectangles to represent window sashes as shown in Fig.2(g). The window sashes must be facing the outside of the room it's in. The length of each rectangle is half length of the window and the width is a default value.

Fig. 2 (

 2 Fig. 2(g) is a bay window and its 2D model is two rectangles as Fig. 2(f) shows. The two rectangles are overlapping with the lines of bay window.

Fig. 2 :

 2 Fig. 2: Semantic information of key symbols

Fig. 4 Definition 3 (

 43 Fig. 4 Examples of recognized walls and wall equivalent lines.

Fig. 5 : 3 :

 53 Fig. 5: Examples of preprocess for loop searching

Fig. 6 :

 6 Fig. 6: An example of dangling wall line.

  (b). Fig. 7(a) is the preprocessing result of Fig. 4(c).

Fig. 7 :

 7 Fig. 7: The result of preprocessing and loop searching.

Fig. 8 (Fig. 8 Fig. 9 A

 889 Fig. 8(a) is the wall extrusion result. Fig. 8(b) is the 3D model after cutting openings. Fig. 8(c) is the final model of the Fig. 4(a). Fig. 9(a) is a bigger floor plan and Fig. 9(b) is its corresponding 3D model.

  ) Move (x2-x1, y2-y1) for F2 to F1, where y1 and y2 are the y coordinate values of h1 and h2, x1 and x2 are the x coordinate values of v1 and v2. The time complexity of matching different floors is O(N2). Fig. 10 is a 2D drawing with four floor plans. Fig. 8(d) is the corresponding 3D model.

Fig. 10 A

 10 Fig. 10 A drawing with several floor plans..

  2 ) + O(T 2 ) + O(D*W 2 )+ O(L 2 ) + O(N 2 ) <O(N 2 ) + O(N 2 ) + D*O(N 2 ) + O(N 2 ) + O(N 2 ) = (D+4)* O(N 2 ). Because D Design & Applications, 10(a), 2013, bbb-ccc © 2013 CAD Solutions, LLC, http://www.cadanda.com usually a much smaller number than N (usually 100*D<N), so the time complexity of reconstructing a floor plan is O(N2). The working space needed for the reconstruction is O(N 2 ).

  Definition 2 (Basic Structural Element): The four types of wall shapes and openings are defined as Basic Structural Elements. Shape and Opening Adjacent (SOA). The shape S and opening O are adjacent if and only if their distance Dis(S, O)d L diagonal . L diagonal is the diagonal length of the bounding box of O. Dis(S,O) is defined as: Dis(S,O)=min{Dis(L i , P Center )}, L i is the PP line of S, i ranges from 1 to the number of lines in S , P center is the center point of the bounding box of O. x Opening and Opening Adjacent (OOA). Two openings O 1 and O 2 are adjacent if and only if their distance Dis(P Center1 , P Center2 ) d L diagonal2. P Center1 and P Center2 are the center point of the bounding box of O 1 and O 2 respectively, L diagonal2 is the sum of the diagonal length of the two bounding boxes

	In this paper, Between the Basic Structural Elements there are three relationships:
	x	Shape and Shape Intersecting (SSI). For shapes S 1 and S 2 , if there exists a PP which is belong to
		both S 1 and S 2 , then S 1	and S 2	are SSI.
	x

Computer-Aided Design & Applications, 10(a), 2013, bbb-ccc © 2013 CAD Solutions, LLC, http://www.cadanda.com

© 2013 CAD Solutions, LLC, http://www.cadanda.com

ACKNOWLEDGMENTS

This work was supported by the 973 Program of China (2010CB328001), the National Nature Science Foundation of China (60903106, 61035002), the 863 Program of China (2012AA040902) and Tsinghua University Initiative Scientific Research Program (2012Z02170).


Guy Perrier

Bruno Guillaume

Frigram: a French Interaction Grammar

Keywords: Formal Grammar, Model Theoretic Syntax, Polarity, Interaction Grammar

We present Frigram, a French grammar with a large coverage, written in the formalism of Interaction Grammars. The originality of the formalism lies in its system of polarities, which expresses the resource sensitivity of natural languages and which is used to guide syntactic composition. We focus the presentation on the principles of the grammar, its modular architecture, the link with a lexicon independent of the formalism and the companion property, which helps to guarantee the consistency of the whole grammar.

Introduction

The aim of our work is to show that it is possible to build a realistic computational grammar of French, which integrates fine linguistic knowledge with a large coverage. As a framework, we have chosen the formalism of Interaction Grammar (IG) [START_REF] Guillaume | Interaction Grammars[END_REF]. IG combines a flexible view of grammars as constraint systems with the use of a polarity system to control syntactic composition. The system of polarities expresses the saturation state of partial syntactic structures and their ability to combine together.

The main challenge is to guarantee and to maintain the consistency of the grammar while aiming at the largest coverage. We resort to several means:

a modular organization of the grammar in a hierarchy of classes, which is able to capture the generalizations of the language, -principles of well-formedness for the elementary structures of the grammar, -a separation of the grammar itself from the lexicon, which is independent of any grammatical formalism, -the use of the companion property to help the checking of the grammar consistency. Starting with a brief presentation of IG, we continue with an explanation of the different points mentioned above and with a comparison with other French grammars and a discussion about the evaluation of the grammar.

Interaction Grammars

IG is a grammatical formalism which is devoted to the syntax of natural languages using two notions: tree description and polarity. For a complete presentation of the formalism, the reader can refer to [START_REF] Guillaume | Interaction Grammars[END_REF].

Tree Descriptions

The notion of a tree description [START_REF] Rogers | Obtaining trees from their descriptions: an application to tree-adjoining grammars[END_REF] is related to a model theoretic view of the syntax of natural languages [START_REF] Pullum | On the Distinction between Model-Theoretic and Generative-Enumerative Syntactic Frameworks[END_REF]. In this view, the basic objects of the grammar are not trees but properties that are used to describe them, in other words tree descriptions. This approach is very flexible allowing the expression of elementary properties in a totally independent way, and their combination in a free manner. A tree description can be viewed either as an underspecified tree, or as the specification of a tree family, each tree being a model of the specification. Figure 1 gives an example of the tree description, which is associated with the sentence "montrez-le !" ["show it !"]. Even if the description is composed of three parts associated with the three words of the sentence (punctuation signs are considered as words), it must be considered as a unique tree description.

nPred cat → s funct ← void nHead cat ↔ v funct ↔ head nSubj cat ↔ np empty_type = arg funct ↔ subj nObj cat ← np funct → obj nVanch montrez cat ↔ v funct ↔ head nS cat ~ap|s nVmax cat ~v nCompl cat → np empty_type = track funct ← obj|subjpred ref = [[9]]? nVclit cat ~v funct ~head nClit cat ↔ pro funct ↔ void ref = [[9]]? nClit0 le cat ↔ pro funct ↔ head nPunct cat ↔ punct funct ↔ void nPunctSign ! cat ↔ punct funct ↔ head nS cat ↔ s funct ↔ void nS0 cat ← s funct → void
A tree description is a finite set of nodes structured by two kinds of relations: dominance and precedence. Dominance relations can be immediate or large. In the example, there are only immediate dominance relations represented with solid lines. Precedence relations can also be immediate or large. They are represented with arrows in Figure 1; these arrow are solid and black or dashed and green, depending on whether the dependencies are immediate or large.

Nodes, which represent constituents, are labelled with features describing their morpho-syntactic properties. Feature values are atoms or atom disjunctions. When a feature value is the disjunction of all elements of a domain, this value is denoted with "?". A mechanism of co-indexation between feature values (a common index [[n]] is put before their values) allows for sharing.

It is possible to add constraints on the phonological form and on the daughters of nodes: a node is declared to be empty if its phonological form is empty and it is graphically represented with a white rectangle; at the opposite, it is declared to be full, and it is represented with a light-yellow rectangle; it is declared to be closed, if the set of its daughters is fixed and it is represented with a double rectangle; finally, a node is declared to be an anchor, if it is a full leaf, and it is used to anchor a word of the language. An anchor is represented with a canary yellow rectangle.

IG uses three kinds of empty nodes:

when an argument has moved from its canonical position, this position is marked with a trace, an empty node with the feature empty type = track; this covers all cases of extraction, subject inversion and cliticization of arguments; in Figure 1, node nCompl is the empty trace of the object represented with the clitic pronoun "le"; -when an argument is not expressed with a phonological form, it is represented with an empty node carrying the feature empty type = arg; this is the case for subjects of adjectives, infinitives and imperatives, as well as some objects of infinitives (tough movement); in Figure 1, node nSubj represents the nonexpressed subject of the imperative verb "montrez"; -in presence of an ellipsis, the head of the elided expression may be represented with an empty node carrying the feature empty type = ellipsis.

Polarities

Polarities are used to express the saturation state of syntactic trees. They are attached to features that label description nodes with the following meaning:

a positive feature f → v expresses an available resource, which must be consumed; -a negative feature f ← v expresses an expected resource, which must be provided; it is the dual of a positive feature; one negative feature must match exactly one corresponding positive feature to be saturated and conversely; -a saturated feature f ↔ v expresses a linguistic property that needs no combination to be saturated; -a virtual feature f ∼ v expresses a linguistic property that needs to be realized by combining with an actual feature (an actual feature is a positive or saturated feature).

In Figure 1, node nObj carries a negative feature cat ← np and a positive feature funct → obj, which represents the expected object noun phrase for the transitive verb "montrez".

The virtual features of the second part of the tree description represent the syntactic context required by the clitic pronoun "le": a verb nVclit put immediately before the pronoun to build the node nVmax with it.

Only resource sensitive features are polarized. Other features are called neutral features and denoted f = v. For instance, agreement properties are expressed with neutral features.

The descriptions labelled with polarized features are called polarized tree descriptions (PTDs) in the rest of the article.

Grammars as constraint systems

An interaction grammar is defined by a finite set of Elementary PTDs, named EPTDs in the following, and it generates a tree language. A tree belongs to the language if it is a model of a finite set of EPTDs in the sense given by [START_REF] Guillaume | Interaction Grammars[END_REF]. Each node of the EPTDs is mapped to a node of the model through an interpretation function. Properties of models include:

-A model is saturated : every positive feature f → v is matched with its dual feature f ← v in the model and vice versa. Moreover, every virtual feature has to find an actual corresponding feature in the model. -A model is minimal : it has to add a minimum of information to the initial descriptions (it cannot add immediate dominance relations or features that do not exist in the initial descriptions).

Parsing a sentence with a grammar G consists first in selecting an appropriate set of EPTDs from G. The selection step is facilitated if G is lexicalized: each EPTD has an anchor associated with a word of the language. It strongly reduces the search space for the EPTDs. Then, the parsing process itself reduces to the resolution of a constraint system. It consists in building all models of the selected set of EPTDs.

Figure 1 represented a possible selection of EPTDs from Frigram to parse the sentence "montrez-le !". The selection includes three EPTDs1 , which are gathered in a unique PTD. Figure 2 shows the unique minimal and saturated model of the PTD. It is an ordered tree where nodes are labelled with non polarized features in the form f : v, where v is an atomic value. In the head of each node, a list gives the nodes of the PTD that are interpreted in the node of the model.

In an operational view of parsing, the building of a saturated and minimal model is performed step by step by refining the initial PTD with a merging operation between nodes, guided by one of the following constraints:

neutralise a positive feature with a negative feature having the same name and carrying a value unifiable with the value of the first feature; -realize a virtual feature by combining it with an actual feature (a positive or saturated feature) having the same name and carrying a value unifiable with the value of the first feature. The constraints of the description interact with node merging to entail a partial superposition of their contexts represented by the tree fragments in which they are situated. So the model of Figure 2 can be obtained from the PTD of Figure 1 with a sequence of three node merging operations: nVanch with nVclit, nObj with nCompl and nPred with nS0.

To summarize, IG combine the strong points of two families of formalisms: the flexibility of Unification Grammars and the saturation control of Categorial Grammars.

The Principles of the Grammar Frigram

Frigram is a IG for the French language; it contains 3 794 EPTD templates.

Frigram follows a set of principles which express formally the chosen linguistic modeling. These principles are also used to automatically check the consistency of the grammar and its conformity to linguistic principle. The constituant to dependency transformation used with Frigram also strongly relies on this set of principles. Definition 1. A node with a positive or saturated cat feature is called a concrete node.

Principle 1 (cat-funct) In an EPTD, any node has a cat feature and if it is concrete, it has also a funct feature.

The consequence is that any node of a model has a cat feature and a funct feature. Another consequence is that any node of a model has a unique concrete antecedent in the original PTD, because two concrete nodes of a PTD cannot merge in the model, according to the composition rules of polarities.

Principle 2 (strict lexicalisation) Any EPTD has exactly one anchor node. This anchor node has a saturated cat feature with an atomic feature value. Definition 2. A spine in an EPTD is a list of nodes N 1 , N 2 , . . . , N p such that:

for any i such that 1 < i ≤ p, node N i is a daughter node of N i-1 ; -for any i such that 1 < i ≤ p, node N i has a saturated feature cat and a feature funct ↔ head; -node N 1 is a concrete node and its feature funct has a value different from head; it is called the maximal projection of all nodes belonging to the spine; -node N p is either an anchor or an empty leaf; in the first case, the spine is called a main spine; in the second case, it is called an empty spine; in both cases, node N p is called the lexical head of all nodes belonging to the spine.

Principle 3 (spine) Any concrete node of an EPTD belongs to exactly one spine.

An important corollary of the spine principle is that every node N of a PTD model has exactly one lexical head in this model, denoted head(N ) and defined as follows: the concrete antecedent of N in the initial PTD belongs to exactly one spine and head(N ) is the interpretation in the model of the leaf ending the spine.

A second important corollary is that every node in a PTD model which is not a leaf has exactly one daughter node with the feature funct : head. By following all nodes with this feature, we have a more direct way of finding the lexical head of every node in a PTD model.

A third corollary is that each model node with a positive feature cat is the maximal projection of some spine.

From the strict lexicalisation and spine principles, we can also deduce that every EPTD has exactly one main spine.

To illustrate the concept of a spine, let us consider the EPTDs of Figure 1. The EPTD associated with the verb "montrez" has two spines: the main spine nPred, nHead, nVanch with its lexical head nVanch, and an empty spine reduced to a single node nSubj. The formalism of IG is situated in the constituency approach to syntax, as opposed to the dependency approach but the principles of Frigram allow for an automatic transformation of any parse made with IG from a constituency setting into a dependency setting. Our purpose here is not to describe the transformation in detail but to give an outline of it. The dependencies are generated by the interactions between the polarized features cat and funct of the different nodes of the initial PTD and they are projected on the full and empty words of the sentence through the notion of lexical head.

For the sentence "montrez-le !", from the PTD of Figure 1 and its model from Figure 2, we compute the dependency graph on the left of Figure 3. It has two empty words, the subject of "montrez", named ǫ a (which corresponds to the node with feature empty type = arg), and its object ǫ t (which corresponds to the node with feature empty type = track), which is the trace of the clitic pronoun "le". Traces are linked to their antecedent with the relation AN T .

In a second step, the empty words are removed and their incident dependencies are transferred to their full antecedent, when it exists. In our very simple example, the resulting dependency graph reduces to the tree on the right of Figure 3, but in more complex sentences, the dependency graph includes cycles and nodes with several governors. When there is more than one solution, handcrafted rules are used to compute a weight for each solution in order to rank them. [START_REF] Crabbé | XMG : eXtensible MetaGrammar[END_REF] The Architecture of the Grammar

The Modular Organisation of the Grammar

It is unthinkable to build a grammar with about 4000 EPTD templates manually, considering each one individually. Even if it were possible, to maintain the consistency of such a grammar would be intractable. Now, the EPTD templates of Frigram share a lot of fragments and it is possible to organize the grammar as a class hierarchy. A tool, XMG [START_REF] Crabbé | XMG : eXtensible MetaGrammar[END_REF], was specially designed to build such kind of grammars. XMG provides a language to define a grammar as a set of classes. A class can be defined directly but also from other classes by mean of two composition operations: conjunction and disjunction.

Each class is structured according to several dimensions. Frigram uses two dimensions: the first one is the syntactic dimension, where objects are EPTD templates, and the second one is the dimension of the interface with the lexicon, where objects are feature structures.

The terminal classes of the hierarchy define the EPTD templates of the grammar that are computed by the XMG compiler. Figure 4 The current grammar Frigram is composed of 428 classes, including 179 terminal ones, which are compiled into 3 794 EPTD templates. Of course, some general classes can be used in several different contexts. For instance, adjectives, nouns and verbs description all inherit from the same subclasses related to complements of predicative structures. The set of classes is organized in a module hierarchy 5.

There is another hierarchy related to the different forms of extraction, in relative, interrogative and cleft clauses. The root module of the hierarchy is the ExtractGramWord module. Three modules depend on it: Complementizer, Interrogative and Relative. Moreover, there are isolated modules related to specific categories.

The link with a lexicon independent of the formalism

The full grammar is produced from the set of EPTD templates and a lexicon. Each EPTD template is associated to a feature structure (called its interface) which describes a syntactic frame corresponding to lexical units able to anchor it; lexicon entries are also described through features structures. Unification between interface of the EPTD template and lexicon feature structure is used to control the combination of a lexical unit description and the template. Thanks to the strict lexicalisation principle, each EPTD of the grammar has a unique anchor node linked with a lexical unit of the language. Since there is a coindexation between features of the EPTD template and features of the interface, a side effect of anchoring is the instantiation of some feature values in the EPTD.

In our system, the lexicon used is Frilex2 which combines morphological information taken in ABU3 and in Morphalou [START_REF] Romary | Standards going concrete: from LMF to Morphalou[END_REF] with syntactical information for verbs from Dicovalence [START_REF] Van Den Eynde | La valence : l'approche pronominale et son application au lexique verbal[END_REF]. Frilex contains 530 000 entries. To avoid size explosion, the full grammar is built on the fly on each input sentence.

The Companion Property and the Consistency of the Grammar

Our ambition is to build a grammar with a coverage of all of the most frequent phenomena of French syntax. Even if the hierarchical structure of the grammar makes it more compact ans eases the maintenance of its consistency, the size of the grammar may be important and the grammar offers no global view of its contents.

To verify the consistency of the grammar, it is necessary to check the behavior of each EPTD in the composition process with other EPTDs. A way of doing it is to parse corpora with the grammar but this is a very partial checking. Now, the formalism of IG provides a mechanism to verify the consistency of a grammar in a static way based on the EPTDs of the grammar without using parsing. The mechanism uses the Companion Property.

Originally, this property was introduced by [START_REF] Bonfante | Polarization and abstraction of grammatical formalisms as methods for lexical disambiguation[END_REF] to perform lexical disambiguation with IG. Let us consider an interaction grammar. Definition 3. A companion of a polarized feature in an EPTD E 1 of the grammar is a polarized feature of an EPTD E 2 such that the first feature is saturated by the second feature in a merging of their nodes leading to a consistent PTD.

What we mean with "a consistent PTD" is that the PTD resulting from the node merging has at least one model, which is a tree but not necessarily minimal and saturated.

For instance, consider the EPTD associated with the verb "montrez" in Figure 1. A companion of the positive feature funct → obj is the negative feature funct ← obj|subjpred of the EPTD associated with the clitic pronoun "le". The notion of companion can be expressed a the template level: we compute systematically the companions of all polarized features of the EPTDs templates of the grammar. In this way, we limit the number of companions to compute.

So, for the EPTD template E 0 corresponding to the EPTD anchored with "montrez" in Figure 1 and for the positive feature funct → obj , we find 97 companions: 85 are right companions, that is, companions coming from EPTD templates for which the anchor is on the right of the anchor of E 0 after merging, and 12 are companions without order constraints on the anchor of their EPTD.

Among all the information given by the computation of all the companions, a particular part is immediately usable: the polarized features without companions. If they have no companion, their EPTDs cannot enter any parsing, which means that the EPTD template must be removed from the grammar or that there is some mistake in their definition.

Comparison with other French Grammars and Evaluation of the Grammar

There is very little work on the construction of French computational grammars from linguistic knowledge using semi-automatic tools. Historically, a very fruitful work was the PhD thesis of Candito [START_REF] Candito | Organisation modulaire et paramétrable de grammaires électroniques lexicalisées[END_REF] about the modular organization of TAGs, with an application to French and Italian. This thesis was a source of inspiration for the development of several French grammars.

A first grammar produced according to this approach and able to parse large corpora was FRMG [START_REF] De | Building factorized TAGs with meta-grammars[END_REF]. FRMG falls within the TAG formalism and its originality lies in the use of specific operators on nodes to factorize trees: disjunction, guards, repetition and shuffling. As a consequence, the grammar is very compact with only 207 trees. Moreover, these trees are not written by hand but they are automatically produced from a multiple inheritance hierarchy of classes.

Another French grammar inspired by [START_REF] Candito | Organisation modulaire et paramétrable de grammaires électroniques lexicalisées[END_REF] is the French TAG developed by [START_REF] Crabbé | Représentation informatique de grammaires fortement lexicalises : application à la grammaire d'arbres adjoints[END_REF]. Like Frigram, this grammar was written with XMG. Contrary to FRMG, it is constituted of classical TAG elementary trees, hence its more extensive form: it includes 4200 trees and essentially covers verbs. It was a purely syntactic grammar and then it was extended in the semantic dimension by [START_REF] Gardent | SemTAG: a platform for specifying Tree Adjoining Grammars and performing TAG-based Semantic Construction[END_REF] for generation.

To evaluate the soundness of Frigram and to compare its coverage with other French grammars is problematic. The first difficulty is that there is no robust parser able to deal with IG. The tool developed so far (Leopar [START_REF] Guillaume | A Toolchain for Grammarians[END_REF]) was designed to experiment, to test and to help grammar development. It was latter enriched with filtering algorithms to improve the supertagging stages of the parsing process. Nevertheless, it does not have any robust mechanism to deal with sentences that are not completely covered by the grammar. After filtering steps, deep parsing relies on an exhaustive search of tree description models which is an NP-hard task. As a consequence, Leopar can be used to parse sentence of length up to 15 words. FTB contains 3398 sentences of length lower than 15. Moreover, all linguistic phenomena present in real corpora, like the FTB, cannot be modeled through a lexicalized grammar: dislocation, coordination of non constituents, parenthetical clauses . . . These phenomena require an extra-grammatical treatment, which is not yet implemented in Leopar. Thus, we consider the subset of sentence without explicit extra-grammatical phenomenon (parenthesis, reported speech); there are 2166 such sentences. The parser Leopar with the Frigram resource is able to parse 56.4% of the sentences considered.

Another way to evaluate a grammar coverage is to use test suites. Such suites must include not only positive examples but also negative examples to test the overgeneration of the grammar. There exists such a suite for French, the TSNLP [START_REF] Lehmann | tsnlp -Test Suites for Natural Language Processing[END_REF], but unfortunately, it ignores a lot of phenomena that are very frequent in French. On the set of grammatical sentences of the TSNLP, Leopar and Frigram is able to parse 88% of the sentences. This is equivalent to the number achieved in [START_REF] Perrier | A French interaction grammar[END_REF] but the remaining sentences correspond to sentences that should be covered by the robustness of the parser rather than by the detailled grammar (unusual kind of coordination, sentence with incomplete negations, . . . )

To try to deal with TSNLP drawbacks, we have designed our own test suite which si complementary to the TSNLP; it contains 874 positive sentences and 180 negative ones. 93% of the grammatical sentences are parsed and the ratio is 21% for ungrammatical sentences. The reader can find the test suite on a web page 4 . For the positive sentences, there is also the result of parsing in the form of a dependency graph. The variety of the examples gives a good idea of the coverage of Frigram and the richness of dependency graphs helps to understand the subtlety of the grammar.

Conclusion

The next step to go ahead with Frigram is to solve the bottleneck of the parser Leopar in order to parse raw corpora. We need to improve the efficiency of the parser to contain the possible explosion resulting from the increase of the grammar size in combination with the increased sentence length. It is also necessary to take robustness into account in the parsing algorithm and to add extra-grammatical procedures to deal with phenomena that go beyond the lexicalized grammar. For English, [START_REF] Seifi | An interaction grammar for English verbs[END_REF] is a first attempt to build a IG grammar that should be extended in order to have a coverage equivalent to the one of Frigram.

Fig. 1 .

 1 Fig. 1. PTD associated with the sentence "montrez-le !" by the grammar Frigram.

Fig. 2 .

 2 Fig. 2. Model of the PTD shown in Figure 1 representing the syntax of the sentence "montrez-le !".

Fig. 3 .

 3 Fig. 3. The dependency graphs representing the syntax of the sentence "montrez-le !".

Fig. 4 .

 4 Fig. 4. The hierarchy of classes used to define the NP0 V NP1 PP2 class of transitive verbs with an indirect complement

Fig. 5 .

 5 Fig. 5. The main hierarchy of modules

The EPTDs are labelled by the name of the class of the grammar generating them followed by a number. In the order of the sentence, we have NP0 V NP1 134, PROclit compl impers pos 38 and PUNCTstop S1inter imper 1.

http://wikilligramme.loria.fr/doku.php?id=frilex

http://abu.cnam.fr/DICO/mots-communs.html

http://wikilligramme.loria.fr/doku.php?id=hmge_2013


Benoît Camenen
email: benoit.camenen@irstea.fr

Magnus Larson
email: magnus.larson@tvrl.lth.se

On the accuracy of equivalent roughness height formulas in practical applications

Keywords: Roughness height, friction factor, plane bed, sheet flow, experimental data, predictive formula, iterative formula

This paper presents a discussion on the application and accuracy of roughness height formulas from a practical point of view. Such formulas have been proposed to describe the equivalent roughness height for plane bed conditions based on the Shields parameter. The application of these relationships requires an iterative solution technique. However, as this note demonstrates, the roughness estimates are not always reliable since the application of the formulas yield large discrepancies in the results.

Introduction

Estimating bedload transport is of great importance for engineering design and morphodynamic modelling; yet bedload transport rate predictions are based on insufficient understanding of the resistance to flow in alluvial channels. Although the roughness height or resistance coefficient are quite difficult to estimate, they remain fundamental parameters in bed shear stress and sediment transport calculations. Total resistance to the flow in a river includes grain resistance, bedform resistance, resistance due to lateral and vertical channel irregularities, as well as dissipation due to the solid transport [START_REF] Recking | Feedback between bed load transport and flow resistance in gravel and cobble bed rivers[END_REF]. [START_REF] Meyer-Peter | Formulas for bed-load transport[END_REF] introduced a linear decomposition of the total resistance coefficient, which may be rewritten as a linear decomposition of the total bed roughness [START_REF] Soulsby | Dynamics of marine sands, a manual for practical applications[END_REF][START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF].

Excluding form drag, the value of the equivalent roughness height k s still varies considerably depending on the configuration of the grains forming the bed roughness or the dissipation due to sediment transport. If k s is generally assumed to be proportional to a characteristic bed grain size (Bathurst, 2 1985), several authors showed a significant increase in k s when bedload transport occurs, even for coarse sediments [START_REF] Campbell | Bed-load effects on hydrodynamics of rough-bed open-channel flows[END_REF][START_REF] Recking | Feedback between bed load transport and flow resistance in gravel and cobble bed rivers[END_REF]. This increase in roughness is often explained for fine sediments by the dissipation of energy in the sheet flow layer that appears for large Shields parameter values (dimensionless bed shear stress defined such as θ = RI/[(s -1)d 50 ], with R: hydraulic radius, I: energy slope, s: relative density of the sediment to the fluid, and d: grain size). Sediments move collectively along the bottom mainly in a layer and k s ≈ δ s , where δ s is the thickness of the sheet flow layer [START_REF] Wilson | Mobile bed friction at high shear stress[END_REF]. This movement induces an effective roughness ratio k s /d, where d is the grain size diameter, up to 50 [START_REF] Wilson | Bed-load transport at high shear stress[END_REF][START_REF] Nnadi | Motion of contact-load particules at high shear stress[END_REF][START_REF] Sumer | Velocity and concentration profiles in the sheet-flow layer of movable bed[END_REF]. Based on a large data set, [START_REF] Recking | Feedback between bed load transport and flow resistance in gravel and cobble bed rivers[END_REF] found a significant difference in the fit of a logarithmic law for the friction coefficient depending on the presence of sediment movement, which can be described in terms of a roughness, such as the k s /d-ratio, that varies from approximately 1 for a fixed bed to 3 for a moderate sediment transport rate.

Generally, this phenomenon was expressed using a Shields parameter value θ over a critical value for the upper plane bed regime, where k s is not only a function of the median grain size d 50 but also of θ [START_REF] Wilson | Bed-load transport at high shear stress[END_REF][START_REF] Nnadi | Motion of contact-load particules at high shear stress[END_REF][START_REF] Yalin | River mechanics[END_REF][START_REF] Van Rijn | Principles of sediment transport in rivers, estuaries and coastal seas[END_REF][START_REF] Sumer | Velocity and concentration profiles in the sheet-flow layer of movable bed[END_REF][START_REF] Bayram | Equivalent roughness under sheet flow conditions[END_REF][START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] or of bedload transport rate, if the latter is assumed to be directly related to the Shields parameter [START_REF] Meyer-Peter | Formulas for bed-load transport[END_REF]. Most of the formulas were validated for fine sediments and high shear stresses. [START_REF] Sumer | Velocity and concentration profiles in the sheet-flow layer of movable bed[END_REF] observed that the roughness height may be a function of a dimensionless settling velocity ̟ s = W s /u * (where W s is the settling velocity and u * the shear velocity). [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] Froude number and coarse sediment, large effective roughness ratios are also observed. The flow seems to be affected by the bed load transport for these particular cases as much as in the sheet flow transport cases.

However, one important aspect of these previous studies is that all the equations presented in [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] have been fitted knowing the total shear stress, since it is directly computed from energy slope measurements. Therefore, in practical applications, as the total Shields parameter is an unknown, these relationships induce an iterative method for the computation of the roughness height and the total Shields parameter. Two main problems may occur: (1) a solution does not always exist depending on the proposed equation (or more than one solution exist), and (2) the 4

Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE) HY.1943-7900.0000670 iterative approach in itself induces a large discrepancy in the results. The main objective of the present study is to highlight these problems induced by the iterative method. Although similar problems occur for oscillatory flows [START_REF] Camenen | Equivalent roughness height for plane bed under oscillatory flow[END_REF], this paper is dealing with unidirectional flows only.

As a consequence, this paper corresponds to an extension to [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] dealing with the application of the previously proposed formulas.

Iterative calculation of the roughness height

Since experimental data implicate a relationship where roughness height is a function of the total shear stress, an iterative calculation is needed to compute the roughness. Indeed, from a practical point of view, the Shields parameter θ is an unknown.

Iterative procedure

The iterative solution can be expressed using the relationship for the friction coefficient (see Eq. 12 in [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] and the definition of the Shields parameter (see Eq. 2 in [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF]. Assuming the hydraulic radius R, median grain size d 50 , relative density of sediments s, and depth averaged velocity U c as input parameters, the only unknown parameter to estimate the Shields parameter is the roughness height k s or roughness length z 0 = k s /30. Thus, the Shields parameter can be expressed 5

Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE) HY.1943-7900.0000670 as a function of k s /d 50 :

θ = F k s d 50 = κ (R + z 0 )/R ln ((R + z 0 )/z 0 ) -1 2 U c 2 (s -1)gd 50 (1)
Employing the relationships proposed by different authors [START_REF] Wilson | Bed-load transport at high shear stress[END_REF][START_REF] Yalin | River mechanics[END_REF][START_REF] Van Rijn | Principles of sediment transport in rivers, estuaries and coastal seas[END_REF][START_REF] Sumer | Velocity and concentration profiles in the sheet-flow layer of movable bed[END_REF][START_REF] Bayram | Equivalent roughness under sheet flow conditions[END_REF][START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF], which can be expressed as k s /d 50 = f (θ), equation 1 can easily be solved using an iterative technique. The function f may often be written according to:

k s d 50 = f (θ) = a 1 + a 2 θ b (2)
where a 1 , a 2 and b are constants (0 The iterative procedure may be summarized as follows:

≤ a 1 ≤ 5, 1 ≤ b ≤ 2.
-fix a first value for k s : k s,p1 = αd 50 (α = 2 may be used assuming skin roughness), -compute θ p using Eq. 1 with

k s = k s,p1 , -compute a new value for k s : k s,p2 using Eq. 2 with θ = θ p , -while |1 -k s,p1 /k s,p2 | > ǫ, fix k s,p1 = k s,

Graphical interpretation of the iterative procedure

It is also possible to graphically represent this iterative procedure. las). This effect is not as strong for the Wilson formula since the power on θ is not as large as for the other equations (1 compared to 1.5 or 2.5). The iterative method will never induce a better result compared to the fitted curve because the two curves f and F -1 are increasing functions of θ. In Fig. 2 are two different situations presented that illustrates this point: 7 1. A slight underestimation is observed using the fitted curve. The experimental point is E 1 with the coordinates (θ 1 ,(k s /d 50 ) 1e ). The estimated value of (k s /d 50 ) from the fitted curve is such that (k s /d 50 ) 1p < (k s /d 50 ) 1e (point P 1 ). From the iterative method (point I 1 ), the predicted value of θ is necessarily smaller (θ 1i < θ 1 ). Thus, (k

s /d 50 ) 1i < (k s /d 50 ) 1p < (k s /d 50 ) 1e .
2. A slight overestimation is observed using the fitted curve. The experimental point is E 2 with the coordinates (θ 2 ,(k s /d 50 ) 2e ). The estimated value of (k s /d 50 ) from the fitted curve is such that (k s /d 50 ) 2p > (k s /d 50 ) 2e (point P 2 ). From the iterative method, the predicted value of θ is necessarily larger (θ 2i > θ 2 ). Thus, (k

s /d 50 ) 2i > (k s /d 50 ) 2p > (k s /d 50 ) 2e .

Fig. 2 here

In conclusion, it appears that the iterative method is not very accurate from a practical point of view. A solution does not always exist, and most of the time, two solutions coexist. If there is an error between the data and the fitted curve, it will necessarily be larger after employing the iterative method.

Results obtained from the iterative methods

Prediction of the roughness height

In order to discuss the iterative method, several empirical formulas for Eq. 2 presented in [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF] were tested using the same data set for plane bed conditions also introduced in [START_REF] Camenen | Equivalent roughness height for plane bed under steady flow[END_REF]. In Table 1 are

Tab. 1 here

Although good agreement is found towards the data using the experimental total shear stress values, the iterative solution for a pair (k s , θ)

9

Author-produced version of the article published in J. Hydraul. Eng. ( 2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE) HY.1943-7900.0000670 induces large discrepancies in the results. As a matter of fact, the accuracy of the results (P 2) drops with 10% to 30% depending on the formula used (cf. table 1 andFig (k s ≈ 2d 50 ), to use the skin roughness height yields nearly as good result as the more complex formulas. The Rickenmann and Recking formula yields slightly better results but very similar as for the skin roughness. No formula gives good predictions for the roughness height when k s > 10d 50 , but the Wilson formula yields much better results than the other formulas. Finally, the Wilson formula (with a minimum value k s /d 50 ) produces the best results among the studied formulas, although the scatter is significant. Shields parameter, which are underestimated.

Tab. 2 here

Conclusions

Many formulas have been proposed to estimate the roughness height in the case of plane beds. All the previous authors proposed equations assuming that the total Shields parameter is already known. Although these formulas present interesting results for the understanding of the physics, and reveal the main factors governing roughness, they are not applicable from an engineering point the view. The iterative formulas resulting from these equations yields very large scatter in the results. Finally, the use of the skin Shields parameter produces nearly as good results, apart for large values of the total Shields parameter, which are underestimated. There is thus a strong need for a new method to correctly predict the total Shields parameter for the upper regime where the roughness height is no more a function of the grain size only (k s /d 50 > 5).

Promotion of Sciences.

Notation

The following symbols and subscripts are used in this paper:

a 1 ,
.5 < θ < 1 1 < θ < 2 2 < θ < 5 θ > 5
.5 < θ < 1 1 < θ < 2 2 < θ < 5 θ > 5

Figures

Table 1 317

  also showed that large values on the effective roughness ratio k s /d 50 can be observed for lower values of the Shields parameter. They proposed a new relationship for the critical Shields parameter for the upper plane regime, which is a function of a dimensionless settling velocity W s * = [(s -1) 2 /(gν)] 1/3 W s (where g the acceleration due to gravity, and ν the kinematic viscosity of the fluid) and a Froude number F r = U c / √ gh (where U c the steady current velocity and h the water depth). Then, for a low

  5 and a 2 varies with b and authors; b can also be a function of the settling velocity, shear velocity or/and the Froude number).

  p2 and iterate the previous two operations Of course, the choice of α and ǫ (ǫ = 0.01 was used) may slightly influence the results. 6Author-produced version of the article published in J.Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

  Fig. 1 presents curves of the effective roughness ratio plotted against the total Shields parameter obtained from various equations k s /d 50 = f (θ) and the equation k s /d 50 = F -1 (θ) (represents calculation of k s /d 50 from the total Shields parameter, see Eq. 1) for two particular cases: figure (a) corresponds to an experimental case from Smart (1984); figure (b) corresponds to an experimental case from[START_REF] Nnadi | Motion of contact-load particules at high shear stress[END_REF].

Fig. 1 here

 1 Fig. 1 here

Fig. 1

 1 Fig. 1(a) for the formula proposed by Camenen et al. or (b) for all formu-

  the predictions of equivalent roughness height within a factor of 2 (P 2 in %) and 5 (P 5 in %) of the measured values presented for the different formulas, as well as the mean value (mr) and standard deviation (sr) of the ratio r = k s,pred /k s,expe . The term "Er log " (logarithmic error index, in %) is defined as, /d 50 ) pred (k s /d 50 ) expe (3) in which n denotes the number of observations. When no solution existed, a value k s /d 50 = 250 (maximum roughness height ratio observed experimentally) was chosen, and when several solutions coexisted, the smallest value was chosen. As a comparison, results using the grain related roughness (k s = 2d 50 ) and a recently published formula by Rickenmann and Recking (2011) are also presented (U c /u * = 4.416(R/d 84 ) 1.904 {1 + [R/(1.283d 84 )] 1.618 } -1.083 ).

  . 3). A large increase in Er log and sr is also observed for all the formulas. It clearly appears that the discrepancy of the iterative methods depends mainly on the value of the coefficient b proposed in each formula (b = 1.0 for the Wilson formula, b = 2.5 for the Sumer et al. formula and b = 1.7 for the Bayram et al. and Camenen et al. formulas). Indeed, the larger the coefficient b is, the closer are the two slopes of the functions F -1 (θ) and f (θ), and the larger the uncertainties induced by the iterative solution. As a result, the obtained k s /d 50 values often correspond to the minimum value imposed by the formula (skin roughness). This observation is clearly confirmed by the graphs in Fig. 3. It also explains the relatively better results observed for the Sumer et al. formula since there is a higher minimum value (k s /d 50 = 4.5) when ̟ = W s /u * ≤ 0.9 (u * = τ /ρ is the shear velocity, where τ is the bottom shear stress and ρ the density of the fluid). In Fig. 3, it appears that the Sumer et al. and Bayram et al. formulas yield unrealistic results corresponding to their minimum value (2 or 4.5 for the Sumer et al. formula depending on ̟) for most of the cases. If the Camenen et al. formula yields the best result using the measured Shields parameter, the obtained result from the iterative solution is quite poor and it yields large uncertainties. As many of the experimental cases correspond to a roughness height close to the skin roughness height 10Author-produced version of the article published in J.Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3 here

 3 Fig. 3 here

  and standart deviation , P 1.2 , P 2 , P 5 : predictions within a factor of 1.2, 2 and 5, respectively (in %) of the measured values,R: hydraulic radius, s : relative density of the sediment to the fluid (s = 2.65 for silica in water), 13Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900: nondimensionnal settling velocity (W * = (s -1) 2/3 /(gν) 1/3 W s ).

  (z 0 = k s /30), α : constant used for the first estimation of k s in the iterative procedure, κ : von Karman constant (κ = 0.41), ν : kinematic water viscosity (ν = 10 -6 m 2 /s), θ : total Shields parameter due to steady current, ̟ s : suspension parameter (̟ s = W s /u * ).

Table 1 :

 1 Prediction of the equivalent roughness height within a factor of 2 and 5 of the measured values together with a logarithmic error index, and the mean value and standard deviation of the ratio r = k s,pred /k s,expe for the studied formulas (R. & R.: Rickenmann & Recking) and all data, and data where (k s /d 50 ) expe > 10 (influence of the iterative method on the results).

  Fig. 1a Fig. 1b

Figure 1 :

 1 Figure 1: Graphical illustration of the iterative method for two specific cases

Figure 2 :

 2 Figure 2: Graphical illustration of the iterative method for the two main

Figure 3 :

 3 Figure3: Effect on the results using an iterative method for theWilson (a)

Fig. 1a

 1a Fig. 1a Click here to download Figure: testks3.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 1b

 1b Fig. 1b Click here to download Figure: testks5.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3a1

 3a1 Fig. 3a1 Click here to download Figure: ksd50-Wil-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3a2

 3a2 Fig. 3a2 Click here to download Figure: ksd50i-Wil-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3b1

 3b1 Fig. 3b1 Click here to download Figure: ksd50-Sum-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3b2

 3b2 Fig. 3b2 Click here to download Figure: ksd50i-Sum-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3c1

 3c1 Fig. 3c1 Click here to download Figure: ksd50-CBL-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Fig. 3c2

 3c2 Fig. 3c2 Click here to download Figure: ksd50i-CBL-theta.eps Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

  a 2 , b : constants depending on authors for the function f , d, d 50 , d 84 : sand diameter, median sand diameter and diameter for which 84% of sediment by weight is smaller, respectively,

	Er log	: logarithm error index (in %),

f : empirical functions used to estimate k s /d 50 , F : function of k s /d 50 used to calculate the Shields parameter,

Table 2 :

 2 Author-produced version of the article published in J.Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670 Prediction of total Shields parameter within a factor of 1.2 and 2 of the measured values together with a logarithmic error index, and the mean value and standard deviation of the ratio r = θ pred /θ expe for the studied formulas (and the skin Shields parameter, as well as the Rickenmann &Recking formula) and all data.Author-produced version of the article published in J.Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

						all data
			experimental value of θ			iterative method
	Author(s)	P 2 P 5 Er log	mr	sr	P 2 P 5 Er log	mr	sr
	k s = 2d 50		73	49	-0.3 0.57			-
	R. & R.		81	44	-0.03 0.55			-
	Wilson		90	33	0.01 0.45 44 76	50	0.08 0.67
	Sumer et al.		87	34	-0.09 0.50 45 79	46	-0.09 0.62
	Bayram et al.		88	34	-0.02 0.47 39 74	53	0.09 0.72
	Camenen et al. 97	23	-0.01 0.30 36 66	61	-0.01 0.81
					data where (k s /d 50 ) expe > 10
			experimental value of θ			iterative method
	Author(s)	P 2 P 5 Er log	mr	sr	P 2 P 5 Er log	mr	sr
	k s = 2d 50	0	0	120	-1.2 0.23			-
	R. & R.	0	2	80	-0.8 0.25			-
	Wilson		70	47	-0.4 0.55 33 53	69	-0.5 0.71
	Sumer et al.		60	64	-0.6 0.57	4	36	85	-0.8 0.57
	Bayram et al.		67	52	-0.5 0.54	9	31	91	-0.4 0.54
	Camenen et al. 96	27	-0.2 0.29 11 30	93	-0.6 0.83
					17

Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE)HY.1943-7900.0000670

Acknowledgments

This work was in part conducted under the Inlet Modeling System Work Unit of the Coastal Inlets Research Program, U.S. Army Corps of Engineers, and in part (B.C.) under the sponsorship of the Japanese Society for the

Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE) HY.1943-7900.0000670 List of Figures A. First count the longest line in each column across adding two characters between each column and one character between each word to obtain total characters. The maximum length of a technical paper is 10,000 words and word-equivalents or 8 printed pages. A technical note should not exceed 3,500 word-equivalents in length or 4 printed pages. Approximate the length by using the form below to calculate the total number of words in the te adding it to the total number of word-equivalents of the figures and tables to obtain a grand total of words for the paper/note to fit ASCE forma Overlength papers must be approved by the editor; however, valuable overlength contributions are not intended to be discouraged by this proce Author-produced version of the article published in J. Hydraul. Eng. (2013), 139(3), 331-335. The original publication is available at http://ascelibrary.org DOI : 10.1061/(ASCE) HY.1943-7900.0000670

Estimating Length of Tables &

2-column table = 61 to 120 characters wide


Guy Perrier and Bruno Guillaume LORIA, Université de Lorraine, Nancy, France

Overview

Leopar1 is a parser for natural languages which is based on the formalism of Interaction Grammars. The parsing principle (called "electrostatic parsing") consists in neutralizing opposite polarities: a positive polarity corresponds to an available linguistic feature and a negative one to an expected feature. The structures used in IG are underspecified syntactic trees decorated with polarities and called Polarized Tree Descriptions (PTDs)".

During the parsing process, PTDs are combined by partial superposition guided by the aim of neutralizing polarities: two opposite polarities are neutralized by merging their support nodes. Parsing succeeds if the process ends with a minimal and neutral tree.

The figure below describes Leopar and the toolchain around it (EPTD stands for Elementary Polarized Tree Descriptions).

Main modules

Anchoring: each lexicon entry is described with an hypertag (i.e. a feature structure which describes morpho-syntactic information on the lexical unit); in order to preserve tokenization ambiguities, tokenization is represented as a Direct Acyclic Graph (DAG) of hypertags; for each hypertag describing a lexical unit, the relevant EPTDs are build by instanciation of template EPTDs defined in the grammar.

Filtering: paths in the DAG produced by the anchoring represented the set of lexical selections that should be considered by the parsing process. In order to reduce the number of paths and so to speed up the deep parsing, the next step in Leopar is to filter out paths that are doomed to fail. Two kinds of filters are used: polarity filters remove lexical selections for which the set of polarities in not well-balanced and companion filters remove lexical selections for which it can be predicted (from knowledge on the template EPTDs) that some polarity will fail to find a dual polarity (called a companion) able to saturate it.

Deep parsing: the atomic operation used during deep parsing is the node merging operation. At each step, two dual polarities are chosen; the two nodes carrying these polarities are merged and tree description around the two are superposed. Of course, in case of dead-lock, backtracking is used to chose another pair of polarities.

Phrase-structure trees and dependency graphs: (E)PTD are tree descriptions which describes constraints on the phrase-structure tree. The parsing process aims to build a phrase structure tree which is a model the EPTDs chosen for each lexical unit. Dependency graphs are build from the phrase structure tree but also with information about taken from the parsing process itself.

http://leopar.loria.fr


Benoît Le Lepvrier
email: benoit.le-lepvrier@insa-rennes.fr

Renaud Loison
email: renaud.loison@insa-rennes.fr

Raphaël Gillard
email: raphael.gillard@insa-rennes.fr

Laurent Patier
email: laurent.patier@cnes.fr

Patrick Potier
email: patrick.potier@dga.defense.gouv.fr

Philippe Pouliguen
email: philippe.pouliguen@dga.defense.gouv.fr

¶ P Pouliguen

Hybridization of the Dual-Grid FDTD with the Physical Optics to Analyze Antennas Mounted on Large and Complex Platforms

published or not. The documents may come

L'archive ouverte

INTRODUCTION

The increasing of telecommunication systems requirements for modern land vehicules, aircrafts and satellites implies a growing number of electronic radiating systems on board. Due to the limitation of available physical space, antennas must be mounted close to complex environment. It results in strong electromagnetic interactions between the antenna and the platform. Therefore, it becomes of great importance to have appropriate tools to quantify the distorsion of on-board antennas parameters.

The problem described above is very challenging for at least three reasons. First of all, the analysis of an antenna mounted on a platform requires to simulate an electrically large structure taking into account very small details compared to the wavelength (geometrical details of the antenna for example). These multi-scale problems are by nature very consuming in terms of computing ressources. Secondly, as already said above, the nearby surrounding environnement of the antennas tends to be more and more complex and close to the antenna. This makes necessary to analyse this domain rigorously in order to correctly take into account the strong near field interactions. The third aspect is related to the wide frequency band over which the antennas have to be analysed nowadays. This is mainly due to the evolution of the applications toward increased bandwith and frequency reconfigurability.

One possible way to simulate antennas on structure without requiring massive computing ressources is to use hybrid methods. They associate a traditional full wave method and an asymptotic one. This approach has been extensively followed over the last decades. Several examples of hybrid methods working in the frequency domain can be found in the litterature [START_REF] Obeilleiro | Hybrid moment-method physical-optics formulation for modeling the electromagnetic behavior of onboard antennas[END_REF][START_REF] Burkholder | A hybrid framework for antenna/platform analysis[END_REF]. Time domain hybrid methods have also been developped in order to solve large band problems [START_REF] Bolzer | A time domain hybrid method suitable for small antennas close to large scatterers[END_REF][START_REF] Yang | FDTD/TDPO hybrid approach for analysis of the EM scattering of combinative objects[END_REF]. However, these methods do not provide a satisfactory answer for the computation of modern problems of antennas on platforms. The main limitation deals with the computation of the complex nearby surrounding environment of the antenna. It is both too complex to be solved with the asymptotic method and too large to be computed efficiently with the full wave method.

In this article we present a new computational method well suited to the computation of modern problems of antennas on platform. This method is based on the hybridization of the Dual-Grid FDTD (DG-FDTD) [START_REF] Pascaud | Dual-Grid Finite Difference Time Domain scheme for the fast simulation of surrounded antennas[END_REF] and the frequency-domain Physical Optics (PO). The DG-FDTD method has been proved to be well suited to analyse rigorously and efficiently antennas and their complex nearby surrounding environment over a wide band of frequency [START_REF] Lepvrier | Rigorous analysis of a satellite antenna including its surrounding environment with the Dual-Grid FDTD method[END_REF]. The hybridization of the DG-FDTD with the PO allows to extend the range of application of the full wave multi-scale method in order to compute the radiation of antennas mounted on electrically very large structures.

This paper is organised as follows. In section 2, the principle of the hybrid DG-FDTD/PO method is presented. In section 3, the DG-FDTD/PO is validated using a monopole mounted on a canonical structure. The accuracy and performance of the new approach are demonstrated by comparison with complete full wave simulations of the problem.

DG-FDTD/PO PRINCIPLE

Antenna to analyze

Metallic structure welcoming the antenna element close to the antenna In order to illustrate the principle of the DG-FDTD/PO hybrid method, a basic antenna on platform problem is considered (Figure 1). In this problem, an antenna with a nearby surrounding environment is mounted on a vehicule. The approach is based on the decomposition of the initial electromagnetic problem into two simulations. First, the DG-FDTD is used to compute rigorously and efficiently the antenna and its nearby surrounding environment. Then, a PO simulation of the metallic structure hosting the antenna is performed. These two DG-FDTD/PO steps are presented in Figure 2.

First step

Second step

⃗ J s ⃗ M s ⃗ J PO

DG-FDTD simulation PO simulation

Near-field surface (DG-FDTD)

Excitation surface (DG-FDTD) Huygens' surface

DG-FDTD simulation

The DG-FDTD simulation of the antenna and its nearby surrounding environment is divided into two successive FDTD simulations [START_REF] Pascaud | Dual-Grid Finite Difference Time Domain scheme for the fast simulation of surrounded antennas[END_REF]. The first step aims at accurately characterizing the antenna alone. Therefore a very fine FDTD mesh is used during this simulation. The near field radiated by the antenna is stored during this step by the means of a near-field surface placed around it. In the second step, the antenna and its nearby surrounding environment are described using a coarser FDTD mesh. The near field stored in the previous step is used as the excitation. During this FDTD simulation, the tangential fields over a closed Huygens' surface including the antenna and its nearby surrounding environment are recorded. This surface later plays the role of interface between the DG-FDTD simulation and the PO one.

PO simulation

The PO simulation starts by calculating, in the frequency domain, the equivalent surface currents J s and M s over the Huygens' surface. The tangential fields coming from the coarse FDTD simulation are used to calculate these currents. Then, equivalent currents are used in near field Kirchoff approximation to compute the incident magnetic field over the metallic structure. The induced currents J P O are then calculated thanks to the traditional PO approximation. Finally, the last step consists in adding up the fields radiated respectively by the equivalent currents J s and M s of the Huygens' surface and the induced currents J P O on the structure. To conclude, the proposed method allows to compute the radiation pattern of an antenna mounted on an electrically large metallic structure rigorously taking into account its complex nearby surrounding environment.

VALIDATION OF THE DG-FDTD/PO METHOD

Description of the scenario

The DG-FDTD/PO approach is validated considering the radiation of a monopole antenna mounted on an electrically large canonical structure (Figure .  3). More precisely, a monopole whose central frequency is 1 GHz is placed at the center of a ground plane. This ground plane is loaded by a vertical metallic plate in order to form a dihedral structure. Finally, a lossless dielectric cube is placed close to the antenna.

DG-FDTD/PO decomposition of the E.M. problem

The overall problem is splitted into two successive simulations. First, the DG-FDTD is used to simulate the monopole with the dielectric cube. This DG-FDTD simulation is done in two steps. The monopole lying on an infinite ground plane is first simulating in a FDTD volume with a fine description (λ 1GHz /60 mesh). Then, the antenna is simulated taking into account the dielectric material. A coarser FDTD mesh (λ 1GHz /30 mesh) is used to model the elements. In this simulation it is still assumed that the antenna and its nearby surrounding environment lie on an infinite ground plane. Once the DG-FDTD simulation is finished, a PO simulation of the metallic structure is performed. A coarse λ 1GHz /6 mesh is used to model the structure hosting the antenna. It can be noted that the antenna and its nearby surrounding environment are replaced by a flat metallic plate in this simulation.

DG-FDTD simulation

Reference simulations

The overall validation test case is also computed with two full wave methods : the FDTD method and the Method of Moment (MoM). By doing those simulations, we intend to get reference results for the validation of the new hybrid method. In order to increase the reliability of the validation, we choose one time-domain volume method (FDTD) and one frequency-domain surface method (MoM).

The FDTD code used to simulate the entire validation case is an in house code which does not set up parallel calculation. The scenario has been meshed with cubic elements of λ 1GHz /30 side length. MoM simulation has been performed with FEKO [START_REF] Software | FEKO (www.feko.info)[END_REF] software using a λ 1GHz /16 mesh. Moreover, parallel computation and Multi Level Fast Multipole Method (MLFMM) algorithm have been used to speed up the computation.

It must be noted that the dimensions of the validation test case have been choosen in order to compute the overall problem with the full wave methods in a reasonable time.

Numerical results

Figures 5 and6 show the normalised E θ far-field radiation pattern in the (x0z) and (y0z) planes computed with the DG-FDTD/PO and the two reference methods. We can observe that the results obtained with the hybrid DG-FDTD/PO method are in very good agreement with those coming from the full wave methods. These results tend to demonstrate that the DG-FDTD/PO approach allows to analyse antenna on platform problems with a very good accuracy even if strong near-field antenna/structure interactions are involved.

Figures 5 and6 also present the radiation pattern of the antenna with its nearby surrounding environment without taking into account the contribution of the structure (antenna and dielectric block on an infinite ground plane). It corresponds to the diagrams obtained after the second step of the DG-FDTD. Results clearly show the necessity to take into account the overall antenna environment of integration.

Computation time

The computation time associated with each simulation is reported in Table 1. Those simulations have been carried out on a six core Intel Xeon machine (2.4 GHz) with 48 Gb RAM. FEKO results assume calculation have been distributed over the six cores. We also recall that DG-FDTD and DG-FDTD/PO code have not been parallelized. First, we can see that hybrid DG-FDTD/PO method allows to reduce significantly the computation time compared to a full wave FDTD simulation. The FDTD method is penalised here by its volumetric meshing. Then, DG-FDTD/PO code turns out to be faster than FEKO software for the computation of 11 frequency points taken on the [0.8;1]GHz band. The new hybrid method takes advantage of the wide band caracteristic of the DG-FDTD and the fastness of the PO computation.

CONCLUSION

A new hybrid method associating DG-FDTD and frequency-domain PO has been proposed. This method called DG-FDTD/PO allows fast and re-

Figure 1 :

 1 Figure 1: Antenna mounted on a vehicule.

Figure 2 :

 2 Figure 2: DG-FDTD/PO principle.

Figure 3 :

 3 Figure 3: Canonical scenario used for the validation.

Figure 4 :

 4 Figure 4: DG-FDTD/PO decomposition of the electromagnetic problem.

Figure 5 :

 5 Figure 5: Far-fiel E θ in the (x0z) plane at 1GHz.

Figure 6 :

 6 Figure 6: Far-fiel E θ in the (y0z) plane at 1GHz.

  liable computations of wide band antennas with a very close surrounding environment and mounted on large metallic platforms. The method has been validated by comparison with two different full wave methods (FDTD and MoM).

Table 1 :

 1 Computation time for the validation test case.

		1 GHz	[0.8;1] GHz
			11 points
	FDTD	43h 20min 43h 21min
	MoM (FEKO)	6min	1h 07min
	DG-FDTD/PO 13min 42s	20min 42s

Acknowledgments

This work was supported by the French armaments procurement agency (Direction Générale de l'Armement, DGA) and the French space agency (Centre National des Etudes Spatiales, CNES).