Bart Lamiroy
email: bart.lamiroy@loria.fr

Laurent Wendling
email: laurent.wendling@parisdescartes.fr

DTW for Matching Radon Features: A Pattern Recognition and Retrieval Method

Keywords: Radon Transform, DTW, Pattern Recognition and Retrieval

In this paper, we present a method for pattern such as graphical symbol and shape recognition and retrieval. It is basically based on dynamic programming for matching the Radon features. The key characteristic of the method is to use DTW algorithm to match corresponding pairs of histograms at every projecting angle. This allows to exploit the Radon property to include both boundary as internal structure of shapes, while avoiding compressing pattern representation into a single vector and thus miss information, thanks to the DTW. Experimental results show that the method is robust to distortion and degradation including affine transformations.

Introduction

Given patterns such as symbols of any kind, cursive characters but also forensic elements like human faces, shoe-or finger-prints, recognition or classification can be done using structural [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF], statistical [START_REF] Jain | Statistical pattern recognition: A review[END_REF] as well as hybrid approaches. In structural approaches, graph based methods have been widely used [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. They provide a powerful relational representation. However, they suffer from intense computational complexity due to the general NP-hard problem of sub-graph matching resulting from the variation of graph structure with the level of noise, occlusion, distortion etc. In some cases, however, matching optimisation can be obtained, but is strongly based on how the image is described [START_REF] Wendling | Using spatial relations for graphical symbol description[END_REF]. Besides, structural approaches do not have rich set of mathematical tools [START_REF] Bunke | Recent advances in graph-based pattern recognition with applications in document analysis[END_REF] unlike in statistical approaches [START_REF] Jain | Statistical pattern recognition: A review[END_REF]. We therefore emphasise in the rest of this paper on statistical pattern analysis representation and recognition.

Shape representation has been an important issue in pattern analysis and recognition [START_REF] Loncaric | A survey of shape analysis techniques[END_REF][START_REF] Zhang | Review of shape representation and description techniques[END_REF]. In this context, features are often categorised as regionbased as well as contour-based descriptors. Generally, contour-based descriptors include Fourier Descriptors (FD) [START_REF] Zhang | Study and evaluation of different fourier methods for image retrieval[END_REF][START_REF] El-Ghazal | Farthest point distance: A new shape signature for fourier descriptors[END_REF]. Contour information can also come from polygonal primitives [START_REF] Attalla | Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching[END_REF], or curvature information [START_REF] Bandera | Non-parametric planar shape representation based on adaptive curvature functions[END_REF][START_REF] Bernier | A new method for representing and matching shapes of natural objects[END_REF]. In the case of the latter, the shape is described in the scale space by the maximum number of curvatures. Other methods, like Shape Context (SC) [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] or skeleton approaches [START_REF] Zhu | Forms: A flexible object recognition and modelling system[END_REF] are based on contour information. In short, contour-based descriptors are appropriate for silhouette shapes since they cannot capture the interior content as well as disconnected shapes or shapes with holes where boundary information is not available. On the other side, region-based descriptors account all pixels within patterns. Common methods are based on moments [START_REF] Teh | On image analysis by the methods of moments[END_REF][START_REF] Bailey | Orthogonal moment features for use with parametric and non-parametric classifiers[END_REF][START_REF] Flusser | On the independence of rotation moment invariants[END_REF] including geometric, Legendre, Zernike, and Pseudo-Zernike moments. Comparative studies [START_REF] Bailey | Orthogonal moment features for use with parametric and non-parametric classifiers[END_REF][START_REF] Teh | On image analysis by the methods of moments[END_REF] have demonstrated the interest on improving invariance properties and reducing computational time of the Zernike moments [START_REF] Chong | A comparative analysis of algorithms for fast computation of zernike moments[END_REF]. On the other side, to overcome the drawbacks of contour-based Fourier descriptors, Zhang and Lu [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF] have proposed a region-based Generic Fourier Descriptor (GFD). To avoid the problem of rotation in the Fourier spectra, the 2D Fourier Transform (FT) is applied on a polar-raster sampled shape. This approach outperforms common contourbased (classical Fourier and curvature approaches) and region-based (Zernike moments) shape descriptors. Region-based descriptors on the whole, can be generally applied. However, high computational complexity needs to be considered. Besides, use of normalisation in order to satisfy common geometric invariance properties introduces errors as well as they are sensitive to noise, eventually affecting the whole recognition process.

Pattern representation must be sufficiently enriched with important information. Moreover, global pattern representation is the premier choice due to its simplicity that avoids extra pre-processing and segmentation process as in local pattern representation. To accomplish recognition, matching is another concern. In other words, feature selection corresponds to the matching techniques, eventually affects the overall performance of the method. For instance, compressing pattern information into a single vector as in global signal based descriptors provide immediate matching, while not offering complete shape information. In those respects, we take advantage of radon transform [START_REF] Deans | Applications of the Radon Transform[END_REF] to represent pattern and DTW is used to match patterns of any size that avoids compressing pattern representation into a single vector unlike the use of R-transform [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], for instance. The work is inspired from previous works such as 2D shape categorisation [START_REF] Leavers | Use of the two-dimensional radon transform to generate a taxonomy of shape for the characterization of abrasive powder particles[END_REF], gait recognition [START_REF] Boulgouris | Gait recognition using radon transform and linear discriminant analysis[END_REF], off-line signature verification [START_REF] Coetzer | Off-line Signature Verification[END_REF][START_REF] Kolhe | Dynamic time warping based static hand printed signature verification[END_REF] and orientation estimation as in [START_REF] Jafari-Khouzani | Radon transform orientation estimation for rotation invariant texture analysis[END_REF]. We have examined the method over two different datasets: graphical symbol [START_REF]GREC: International symbol recognition contest at grec2003[END_REF] and shape [START_REF] Sebastian | Recognition of shapes by editing shock graphs[END_REF].

The remaining of the paper is organised as follows. We start with detailing the proposed method in Section 2, which mainly includes pattern representation and matching. Section 3 provides a series of tests. In Section 4, analysis of the results are observed or examined and discussed thoroughly. The paper is concluded in Section 5 along with future perspectives.

In this work, we use the Radon transform to represent patterns [START_REF] Deans | Applications of the Radon Transform[END_REF], Radon based descriptors do not only encode contour information ( [START_REF] Fränti | Content-based matching of line-drawing images using the hough transform[END_REF][START_REF] Leavers | Use of the two-dimensional radon transform to generate a taxonomy of shape for the characterization of abrasive powder particles[END_REF], for instance), they also encode internal structure. Radon transforms are essentially a set of parametrized histograms. We apply Dynamic Time Warping to align every histogram for each projecting angle to absorb varying histogram sizes resulting from image signal variations.

Pattern Representation

The Radon transform consists of a collection of projections of a pattern at different angles [START_REF] Deans | Applications of the Radon Transform[END_REF]. This is illustrated in 1. In other words, the radon transform of a pattern f (x, y) and for a given set of angles can be thought of as the projection of all non-zero points. This resulting projection is the sum of the non-zero points for the pattern in each direction, thus forming a matrix. The matrix elements are related to the integral of f over a line L(ρ, θ) defined by ρ = x cos θ + y sin θ and can formally be expressed as,

R(ρ, θ) = ∞ -∞ ∞ -∞ f (x, y)δ(x cos θ + y sin θ -ρ)dxdy where δ(.) is the Dirac delta function, δ(x) = 1, if x = 0 and 0 otherwise. Also, θ ∈ [0, π[ and ρ ∈] -∞, ∞[. For radon transform, L i be in normal form (ρ i , θ i ).
Following Fig. 1 (c), for all θ i , the Radon transform now can be described as the length of intersections of all lines L i . Note that the range of ρ i.e., -ρ min < ρ ≤ ρ max is entirely based on the size of pattern.

Since the Radon transform itself does not satisfy invariance properties, we consider the following affine transformation properties to adapt it for recognition. In case of translation, we use image centroid (x c , y c ) such that translation vector is u = (x c , y c ): R(ρx c cos θy c sin θ, θ). Therefore, translation of f results in the shift of its transform in ρ by a distance equal to the projection of translation vector of the line L (see Fig. 1 (c)). For rotation, we approximate rotation angle orientation as implemented in [START_REF] Jafari-Khouzani | Radon transform orientation estimation for rotation invariant texture analysis[END_REF]. Orientation can be estimated as,

α = arg min θ d 2 σ 2 θ dθ 2 where σ 2 θ = 1 P ρ (R(ρ, θ) -µ θ ) 2 is the variance of projection at θ, µ θ = 1 P ρ R(ρ, θ) and P , the number of samples. If angle of rotation is α, then R α (ρ, θ) = R(ρ, θ + α).
This simply implies a circular shift of the histograms such that it does not require histograms duplication from [0, π[ to [π, 2π[ as in [START_REF] Coetzer | Off-line Signature Verification[END_REF] to make rotation invariant. For scaling, we simply normalise histograms into [0, 1] at every projecting angle.

Fig. 2 shows radon features for reference, rotation, scaling, as well as degradation instances from a known class of graphical symbol [START_REF]GREC: International symbol recognition contest at grec2003[END_REF]. In all cases, radon histograms from their corresponding sample images are similar to each other. Fig. 2. Radon features for ideal (reference), rotation, scaling as well as noisy samples.

Pattern Matching

As explained in Section 2.1, the Radon transform matrix R(ρ, θ) can represent any pattern P. Given two patterns P q and P d , matching can be obtained between corresponding histograms R q (ρ, θ) and R d (ρ, θ). Radon transforms generate different ρ sizes depending on the image contents' size. In order to be able to adapt to these differences in size, we develop the following approach:

Dynamic Time Warping [START_REF] Kruskall | The symmetric time warping algorithm: From continuous to discrete[END_REF], allows us to find the dissimilarity between two non-linear sequences potentially having different lengths. In radon matrix R(ρ, θ), column refers to the histogram of radon for each projecting angle. Let us say histograms {H θi } i=0,...,Θ-1 (see Fig. 3). In this illustration, vertical lines represent radon histograms at every projecting angle. Let us consider two column vector sequences from R(ρ, θ), representing histograms H q and H d of length K and L, respectively. H q = {h q k } k=1,...,K and H d = {h d l } l=1,...,L . At first, a matrix M of size K × L is constructed. Then for each element in matrix M, local distance metric δ(k, l) between the events e k and e l is computed. δ(k, l) can be expressed as, δ(k, l) = (e ke l ) 2 , where e k = h q k and e l = h d l . Let D(k, l) be the global distance up to (k, l),

D(k, l) = min [D(k -1, l -1), D(k -1, l), D(k, l -1)] + δ(k, l)
with an initial condition D(1, 1) = δ(1, 1) such that it allows warping path going diagonally from starting node (1, 1) to end (K, L). The main aim is to find the path for which the least cost is associated. The warping path therefore provides the difference cost between the compared sequences. Formally, the warping path is, W = {w t } t=1...T where max(k, l)

≤ T < k + l -1 and t th element of W is w(k, l) t ∈ [1 : K] × [1 : L] for t ∈ [1 : T ].
The optimised warping path W satisfies the following three conditions. c1. boundary condition: w 1 = (1, 1) and w T = (K, L) c2. monotonicity condition:

k 1 ≤ k 2 ≤ • • • ≤ k K and l 1 ≤ l 2 ≤ • • • ≤ l L c3. continuity condition: w t+1 -w t ∈ {(1, 1)(0, 1), (1, 0)} for t ∈ [1 : T -1]
c1 conveys that the path starts form (1, 1) to (K, L), aligning all elements to each other. c2 restricts allowable steps in the warping path to adjacent cells, never be back. And monotonicity condition forces the path advances one step at a time. Note that c3 implies c2.

We then define the global distance between H q and H d as,

∆ H q , H d = D(K, L) T .
The last element of the K × L matrix, normalised by the T provides the DTWdistance between two sequences where T is the number of discrete warping steps along the diagonal DTW-matrix.

Matching Score Aggregating distances between histograms in all corresponding projecting angles θ i between P q and P d yields a global pattern-matching score,

Dist(P q , P d ) = Θ-1 i=0 ∆(H q θi , H d θi ).
Scores are normalised into [0, 1] by, Dist(.) = Dist(.)-Dist min. (.) Dist max. (.)-Dist min. (.) . As shown in Fig. 2, it is important to notice that there may be significant the amplitude differences between radon histograms, from one sample to another. These amplitude differences are very well handled by the DTW algorithm. In addition, Fig. 4 gives an overview of matching score values of the proposed method to affine transformations, noise addition and stretching.

Pattern Recognition and Retrieval

We can now use the previously described approach as a global pattern matching score. This score expresses the similarity between database patterns and query. Our problem is: given a set of points S in a metric space M s and a query point q ∈ M s , find the closest point in S to q. Now, we express similarity as, Similarity(P q , P d ) = 1 -Dist(P q , P d ) = 1 for the closest candidate 0 for the farthest candidate.

Ranking can therefore be expressed on the decreasing order of similarity. In our experiments, we will distinguish "recognition" (search for the closest candidate) from "retrieval" (where closest candidates are retrieved for a given short-list).

3 Experiments

Benchmarking Methods

We confront D-Radon method with well-known descriptors: R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], GFD [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF], SC [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] and Zernike [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF]. For those descriptors, it is important to fit the best parameters. For GFD, we have tuned the parameters, radial (4 : 12) and angular (6 : 20) frequencies to get the best combinations. For SC, we follow [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF].

In case of Zernike, we have used 36 Zernike functions of order less than or equal to 7. For radon, projecting range is [0, π[.

Experimental Results

We work on several different datasets in different contexts. However, we primarily focus on A. distorted and degraded symbols in document analysis -graphics recognition and retrieval, and then B. shape retrieval as a CBIR application.

In order to test the robustness of the methods, we work on raw data, no prefiltering (de-noising, for instance) has been applied.

A. Symbol Recognition and Retrieval

GREC2003 dataset symbol recognition contest [START_REF]GREC: International symbol recognition contest at grec2003[END_REF] -In this dataset, we have used the following different categories: ideal, scaling, distortion as well as degradation. Altogether, there are 50 different model symbols. Those symbols are grouped into 3 sets, containing 5, 20 and 50 model symbols. Each model symbol has 5 test images in every category except the ideal one. Ideal test images are directly taken from the set of model symbols and therefore the test is to evaluate the ability of simple shape discrimination, as the number of symbols increases. Since vectorial distortion works only with symbols with straight lines, and not arcs, it is applied to a subset of 15 model symbols. Besides, there are 9 models of degradation, aiming to evaluate the robustness to the scalability with degradation. Fig. 5 shows a few samples of GREC2003 dataset. To evaluate the method, each test image is matched with the model symbols to get the closest model. Experimental results for all types of aforementioned categories of datasets are shown in Table 1. Note that since there are 9 models of degradations (m1 to m9), there are nine tests in every sample in each set (see Fig. 5 (d)).

Based on the results from ideal test images, one cannot judge the superiority of the methods. Only running time comparison would be an alternative. For scaled images, R-signature lags far behind. Our method achieves 100% recognition rate while not offering substantial difference with GFD, SC and Zernike. Also, results from test images with vectorial distortions shows identical behaviour as in scaled as well as rotated samples. However, we receive noteworthy differences in case of binary degradations. Overall, D-Radon performs the best of all.

CVC hand-drawn symbol dataset -As in [START_REF] Wendling | Selection of suitable set of decision rules using choquet integral[END_REF], we have used 10×300 sample images i.e., 10 different known classes of hand-drawn architectural symbols with 300 instances in each. Samples are having distortions, gaps, overlapping as well as missing parts within the shapes. Fig. 6 shows a few samples of it. In this dataset, we aim to retrieve all 300 instances for every chosen query. Table 2 shows the average retrieval rate for all requested short-lists (e.g., top-20, top-40 and so on). Up to top-60, one cannot make decision that which method performs well since there exists no notable differences in retrieval rate. It is only determined after top-60. To be precise, the aim of the test is to evaluate retrieval stability of the methods. D-Radon provides the rate of 86% in top-300 while more than 16% difference (fairly in large amount) has been made with SC. SC lags GFD by approximately 9%. R-signature provides an average results compared to Zernike. Compared to all, D-Radon outperforms.

B. Shape Retrieval

We have used two different shape datasets [START_REF] Sebastian | Recognition of shapes by editing shock graphs[END_REF]: Kimia's Shapes99 and Shapes216. Shapes99 dataset consists of 9 classes, each one is having 11 samples. In another dataset, there are 18 classes and each one contains 12 samples. Fig. 7 shows a few samples of both datasets. As in [START_REF] Sebastian | Recognition of shapes by editing shock graphs[END_REF], we have used the dataset for recognition purpose. For retrieval rate, since there are N instances from each class, we have increased proximity search from 1 to N with the step of +1. In addition, we have tested Bull's eye score [START_REF] Latecki | Shape descriptors for non-rigid shapes with a single closed contour[END_REF][START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. Bull's eye score is the ratio of the number of correct matches up to proximity search space of 2N to the possible number of matches in the dataset. Table 3 shows the experimental results for both datasets. Compared to Zernike and R-signature, our method outperforms with significant difference while it goes almost equally with GFD and SC.

Discussions

We analyse behaviour of the methods based on the key characteristics as well as major challenges of test images. In graphical symbol datasets, samples are distorted, embedded with different levels of noise and even degraded. In particular, there exists missing parts including severe vectorial distortions in hand-drawn symbol dataset in addition to a significant size variation as well as multi-class similarity between the classes. Besides, occlusion exists more in hand-drawn and shape datasets.

Of course, global signal based descriptors are easy to implement as explained in Section 1. However, they are generally not well adapted for capturing precisely small detail changes as well as this tends to make them fault tolerant to image distortions, noise as well as missing parts. We have examined such a behaviour throughout the tests. Considering GREC2003 dataset for instance, for degradation models R-signature is affected from every dot (from noise) due to the square effect (via R-transform). Similarly, SC is affected where the level of noise (see m2 to m7 in Fig. 5) is high since it accounts those pixels while sampling. For Zernike, the disadvantage (in particular if high degree polynomials are involved) is the unequal distribution of nodal lines over the unit disk. We have observed the effect in case of degradation models: m8 and m9 in Fig. 5. Similar situations occur in the CVC hand-drawn symbols. GFD on the whole, provides average results. Those descriptors provide interesting results for silhouette shapes. Considering such datasets, our method performs reasonably better. More specifically, it can optimally handle noisy, degraded as well as distorted samples as well as where internal content is necessary to be considered. Running time complexity is usually high since it uses DTW for matching radon histograms, however it is largely depend on how big the image is. As far as concern to computational cost, the observed average running time for all methods is given in Table 4. We have used MATLAB 7.8.0 in Linux platform.

Conclusions

We have presented a method for graphics recognition under document analysis and shape retrieval under CBIR applications. The method is basically based on dynamic programming for matching radon features. The method is quite simple and easy to implement since it is parameter free. Computing radon transform is quite immediate. But the running time complexity lies in matching. However, it could be substantially reduced by using optimised DTW [START_REF] Salvador | Toward accurate dynamic time warping in linear time and space[END_REF] -a step to go further.

Fig. 1 .

 1 Fig. 1. Radon transform

  (a) reference (b) rotation (c) scaling (d) degradation (noise)

Fig. 3 .

 3 Fig. 3. Radon histogram at every projecting angle θi.

Fig. 4 .

 4 Fig. 4. Matching scores between samples shown above. It provides the differences exist between the samples due to noise, translation, rotation as well as scaling.

Fig. 5 .

 5 Fig. 5. GREC2003 samples -graphical symbol.

Fig. 6 .

 6 Fig. 6. 2 hand-drawn samples from 10 different known classes.

Fig. 7 .

 7 Fig. 7. 2 samples from each class of (a) shapes99 and (b) shapes216 datasets.

Table 1 .

 1 Recognition rate in % for GREC2003 dataset Test images R-sign. GFD Zernike SC D-Radon

	ideal	set1 set2 set3	5×1 20×1 50×1	100 100 100	100 100 100	100 100 100	100 100 100	100 100 100
		Average -ideal	100	100	100	100	100
	scale	set1 set2 set3	5×5 20×5 50×5	45 36 28	100 100 98	100 98 96	100 100 98	100 100 100
		Average -scale	37	99	98	99	100
		distort1-set1	5×5	20	100	100	100	100
	distort	distort2-set1 distort3-set1 distort1-set2 distort2-set2	5×5 5×5 15×5 15×5	8 8 8 4	100 100 100 100	100 100 100 100	100 100 100 100	100 100 100 100
		distort3-set2	15×5	4	100	100	100	100
		Average -distort	7	100	100	100	100
	degrade	set1 set2 set3	5×5× 9 20×5× 9 50×5× 9	12 07 07	86 93 89	79 79 77	87 76 70	95 96 93
		Average -degrade	08	89	78	77	95

Table 2 .

 2 Average retrieval rate in % for CVC hand-drawn symbol dataset Test top top top top top top top top top top top top top top top images 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300

	Zernike R-sign. GFD SC	10×300	48 42 39 37 35 34 33 32 30 30 29 28 28 27 26 82 75 69 65 62 59 56 54 51 49 48 46 45 43 42 96 93 90 88 85 83 81 78 76 73 71 68 66 63 61 98 95 95 92 91 88 87 85 83 81 78 78 75 73 70
	D-Radon		99 99 98 97 97 96 95 94 93 92 91 90 89 87 86

Table 3 .

 3 Average retrieval rate and Bull's eye score in % for kimia's dataset

			Test top top top top top top top top top top top top bull's eye
			image	1	2	3	4	5	6	7	8	9	10 11 12	score
	shapes99	Zernike R-sign. SC GFD D-Radon	9×11	100 74 66 59 53 48 45 42 40 37 35 100 83 73 66 60 56 51 49 47 45 43 100 97 95 92 89 87 85 84 82 80 77 100 97 96 92 90 87 83 80 77 73 70 100 97 95 94 92 91 86 81 80 79 77	48 59 84 86 87
	shapes216	Zernike R-sign. GFD SC D-Radon	18×12	100 81 71 63 57 53 50 48 45 43 41 39 100 86 80 76 71 67 65 62 59 57 54 52 100 97 93 91 87 85 84 81 79 78 76 73 100 99 97 95 93 91 90 89 88 86 83 80 100 99 95 93 91 90 89 86 85 84 83 81	48 64 83 87 88

Table 4 .

 4 Average running time for generating features and matching for a single pair.

		R-sign. GFD Zernike SC D-Radon
	Time (sec.)	1.5	15	20	43	77


Bart Lamiroy
email: bart.lamiroy@loria.fr

Laurent Wendling
email: laurent.wendling@parisdescartes.fr

Spatio-structural Symbol Description with Statistical Feature Add-on

Keywords: Graphical Symbol, Vocabulary, Spatial Relations, ARG, Shape Descriptors

In this paper, we present a method for symbol description based on spatio-structural as well as statistical features of visual elementary parts called 'vocabulary'. The extracted vocabulary is first organised into different groups based on their types (e.g., circle, corner). This vocabulary is used as a basis for an Attributed Relational Graph (ARG) where spatial relational descriptors formalise the links between the types, labelled with global shape descriptors. The description is used to globally recognise structure by comparing the signatures. The method is experimentally validated in the context of electrical symbol recognition from wiring diagrams.

I. INTRODUCTION

Graphics recognition has an extremely rich state-of-theart literature in symbol recognition and localisation. However, most methods are particularly suited for isolated line symbols, not for composed symbols connected to a complex environment [START_REF] Cordella | Symbol recognition in documents: a collection of techniques?[END_REF], [START_REF] Lladós | Symbol Recognition: Current Advances and Perspectives[END_REF]. Considering the problem of symbol localisation in real documents, composed of individual parts constrained by spatial relations for instance, one needs to be able to extract visual parts and formalise the possible links that exist between them, in addition to the possible use of shape description on visual parts. This integration of spatial relations and shape description of the extracted visual parts is going to be the core of this paper. The method is very much inspired by a real world industrial problem [START_REF] Tombre | Pattern recognition methods for querying and browsing technical documentation[END_REF], [START_REF] Lamiroy | Inductive logic programming for symbol recognition[END_REF]. Fig. 1 shows a few samples of it. A few symbols in FRESH dataset. Both linear as well as symbols in the composite form are enlisted.

Global signal based descriptors [START_REF] Zhang | Review of shape representation and description techniques[END_REF] present a number of inconvenients in our context. They difficultly accommodate with connected as well as composite symbols. They are generally not well adapted for capturing small detail changes. In statistical approaches, signatures are simple with low computational cost. However, discriminative power and robustness strongly depend on the optimal selection of features [START_REF] Barrat | A bayesian network for combining descriptors: application to symbol recognition[END_REF] as well as fusion of classifiers [START_REF] Terrades | Optimal classifier fusion in a non-bayesian probabilistic framework[END_REF] partially based on the idea presented in [START_REF] Tombre | Stable, robust and off-the-shelf methods for graphics recognition[END_REF] that off-the-shelf methods are primarily designed for applications where line symbols are isolated. Besides global signal based descriptors, another idea is to decompose the symbols into either vector based primitives like points, lines and arcs or, on the other hand, meaningful parts like circles, triangles and rectangles. They are then represented as Attributed Relational Graphs (ARG) [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF], Region Adjacency Graphs (RAG) [START_REF] Lladós | Symbol recognition by error-tolerant subgraph matching between region adjacency graphs[END_REF], as well as deformable templates [START_REF] Valveny | A model for image generation and symbol recognition through the deformation of lineal shapes[END_REF]. In addition to the common drawback i.e., errorprone raster-to-vector conversion, variability of the size of graphs leads to computational complexity in matching. Structural approaches however, provide a powerful relational representation, conveying how parts are connected to each other, while also preserving generality and extensibility.

In this paper, we aim to combine the best of both structural and statistical approaches, and try to avoid the shortcomings of each of them. To do so, we decompose symbols by expressing their various parts in a fixed visual vocabulary, using spatial relations, graphs and signal based descriptors to describe the whole shape. Our symbol description is clearly explained in Section II. Thanks to the use of fixed and completely labelled attributes, we can avoid the NPhardness of the matching problem. Overall, symbols can be compared by fusion of matching scores from every corresponding vertex and edge alignment (cf., Section III). In Section IV, we validate that our method. The paper concludes in Section V.

II. SYMBOL DESCRIPTION

We have a set of well controlled visual elementary parts as a vocabulary [START_REF] Tombre | Pattern recognition methods for querying and browsing technical documentation[END_REF], [START_REF] Lamiroy | Inductive logic programming for symbol recognition[END_REF] (see Fig. 2). We denote the type set as, T = {T thick , T circle , T corner , T extremity }. Now, we represent whole symbol by a complete ARG as a 4-tuple G = (V, E, F A , F E ) where V is the set of vertices, E ⊆ V × V is the set of graph edges, F A : V → A V is a function assigning attributes to the vertices and A V representing a set of vocabulary type set T as well as their global shape signatures S, and F E : E → ℜ E is a function assigning labels to the edges where ℜ represents spatial relations of the edge E. Following Fig. 2 and its resulting graph in Fig. 3 whose attribute type set is {T 1 , T 2 , T 3 }, its ARG representation can be expressed as G = { V = {T1, T2, T3}, E = {(T1, T2), (T1, T3), (T2, T3)}, FA = {((T1, T circle ), S(T1)), . . . , ((T3, Textremity), S(T3))} FE = {((T1, T2), ℜ(T1, T2)), . . . , ((T2, T3), ℜ(T2, T3))}}.

Since this forms a complete graph, it is obvious that there exist r = t(t-1) 2 edges for t attribute types.

S(T1) S(T2) S(T3) ℜ(T 1 , T 2 ) ℜ(T 1 , T 3 ) ℜ(T 2 , T 3 )

A. Edge Signature

Choice of spatial relation models rely on behaviour of the studied objects. If the objects are far enough from each other, their relations can be approximated by their centres based on the discretised angle [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF]. Otherwise, if they are neither too far nor too close, relations can be approximated by their Minimum Bounding Rectangle (MBR) [START_REF] Papadias | Spatial relations, minimum bounding rectangles, and spatial data structures[END_REF] as long as they are regular. Approaches like histograms of angle [START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF], tends to be more capable of dealing with overlapping. However, since they consider all pixels, their computational cost increases dramatically. Our work is inspired by the concept of fuzzy relationsthat takes degree of truth which is more natural than using standard, all-or-none relations [START_REF] Freeman | The modelling of spatial relations[END_REF].

Our model can be explained as follows. For a given reference point R p , we cover the surrounding space at regular radial intervals of Θ = 2π/m by using a radialline. We set up a unique reference point R p computed from centroids C A and C B of given pairs R p = C A +C B 2 . R p thus, avoids erroneous choice of referencing one from a pair. As in Fig. 4, the line rotates over a cycle, and intersecting with object X (A or B), generates a boolean histogram H,

H(X, Rp) = [I(Rp, jΘ)]j=0..m-1,
where

I(Rp, θi) = 1 if line(Rp, θi) ∩ X = ∅ 0 otherwise.
This is extended wlog to the sector defined by two successive angle values (θ i and θ i+1 ) and is normalised with respect to the total area of the studied object such that HX(.) = 1. It applies to both spatial objects.

Following Fig. 4, any angle made by R p and C X is re-projected on the horizontal axis such as to make the histogram rotation invariant. Also, translation does not affect at all, since it uses C X . Fig. 5 shows an example. In a similar manner, scaling does not produce any difference in H as it is normalised in every sector made by θ i and θ i+1 .

B. Vertex Signature

Each vertex has a distinct vocabulary type containing different shape and size information. Since spatial relations only encode relative positioning and point distributions, and do not completely exploit global shape information, we study the pertinence of R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], region based Zernike Moments [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], Generic Fourier Descriptors (GFD) [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF] and Shape Context (SC) [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF].

III. SYMBOL RECOGNITION

Based on our symbol description, matching of two symbols is done by matching their corresponding ARGs. Let us consider two ARGs, query G q = (V q , E q , F q A , F q E ) and database

G d = (V d , E d , F d A , F d E )
, where the set of vertices V = {T 1 , . . . , T t }, and the set of edges E = {E 1 , . . . , E r }.

Our matching is straightforward i.e., matching has been made between the candidates only having the exact same set of vertices as well as exact labels. To generalise it, we define a binary indicator function τ V A : Σ T → {0, 1} to check the presence of vertices in the ARG, where the value of τ V A (T) is 1 if T is present in V and 0, otherwise. Now, we can then set up bijective matching functions: σ : V q → V d and ϕ : E q → E d , respectively for vertices and edges. Now, the fusion of both alignments provides the distance between two matched graphs G q and G d ,

D(G q , G d ) = t∈V δ(F q A (t), F d A (σ(t))) + r∈E δ(F q E (r), F d E (ϕ(r))),
where δ(a, b)

= L l=1 ||a l -b l || 2 .
IV. EXPERIMENT

A. Dataset, Ground-truth and Evaluation Metric

Fig. 1 gives some examples of very similar and very different symbols. Symbols may either be very similar in shape -and only differ by slight details -or either be completely different from a visual point of view. Symbols may also be composed of other known and significant symbols and need not necessary be connected. The global dataset is composed of roughly 500 different known symbols.

Since there is no absolute ground-truth associated to our dataset, we have asked 6 volunteers to manually select what they consider as "similar" symbols. They have chosen the candidates which have similar visual overall appearance or contain significantly similar parts with respect to the chosen query. In our testing protocol, we consider that a result returned from an algorithm is correct if at least one evaluator has selected the same result among the similar items.

For every query, we rank the symbols at the output based on distance measure as described in Section III. Since the number of ground-truths varies from one query to another, we use retrieval efficiency [START_REF] Kankanhalli | Clusterbased color matching for image retrieval[END_REF]. For a chosen query and for a given short-list of size K, it can be expressed as,

ηK = n/N if N ≤ K n/K otherwise,
where n is the number of returned relevant symbols and N the total number of relevant symbols. The aim of the metric is not to miss similar candidates in the short-list since η K computes the traditional recall if N ≤ K and precision measure otherwise.

B. Results and Discussions

We perform a series of tests, focussing on three major issues one-after-another as shown in Fig. 6.

Test 1. We consider the influence of different resolutions Θ in our edge signature. Its value represents the trade-off between the optimal choice of resolution -and thus precision of spatio-structural information capture -and time/space requirements. Following results in Fig. 6 (a), and given the relatively low gain of efficiency between 3 • and 1 • , we adopt the former for the rest of our experiments. Our spatial relation is then compared with spatial relation models: Coneshaped [START_REF] Miyajima | Spatial Organization in 2D Segmented Images: Representation and Recognition of Primitive Spatial Relations[END_REF], Angle Histogram [START_REF] Wang | Human-Based Spatial Relationship Generalization Through Neural/Fuzzy Approaches[END_REF] and MBR [START_REF] Papadias | Spatial relations, minimum bounding rectangles, and spatial data structures[END_REF] as shown in Fig. 6 (b). Our edge signature outperforms them with a substantial difference.

Test 2. We employ a major set of global signal based descriptors: R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], Zernike [START_REF] Kim | A region-based shape descriptor using zernike moments[END_REF], GFD [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF] and SC [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. We first employ them as vertex signatures only and then confront them with the same shape descriptors, applied to the overall shape. This comparison is illustrated in Fig. 6 (c) and (d), respectively. On the whole, GFD provides interesting results in both cases. SC is restricted by the number of sample points i.e., we have images ranging from a few tens of pixels to thousands of pixels.

Test 3. We integrate edge and vertex signature keeping ARG as described in Section II. While integrating, use of signatures on all vertices is not wise since our relation carries sufficient information for a few vocabulary types in a pair. Therefore, we have examined the use of signature from one type to another as well as their possible combinations. In our tests, substantial advancement is achieved from the combination of vertices, labelled with thick and circle vocabulary types. Fig. 6 (e) shows results from using different shape signatures integrating with edge signature at 3 o resolution.

In Fig. 6 (f), a comparison is made among the best of all experiments: MBR from the basic spatial relation model and GFD from shape descriptors. Our method outperforms all. For a few queries, visual illustration is shown in Fig. 7.

V. CONCLUSIONS AND FURTHER WORK

We have presented an ARG based symbol description method, where relational signatures formalise all possible connections between the vocabulary types which are labelled with global shape signatures. Our method has proven to significantly outperform state-of-the-art basic spatial relation models as well as global signal based descriptors. 2.

3.

4.

5.

6.

7.

8. 9.

10. Comparison to a few more methods like [START_REF] Yang | Symbol recognition via statistical integration of pixel-level constraint histograms: A new descriptor[END_REF], [START_REF] Zhang | Symbol recognition with kernel density matching[END_REF], is our next step.

Figure 1 .

 1 Figure 1.A few symbols in FRESH dataset. Both linear as well as symbols in the composite form are enlisted.

Figure 2 .

 2 Figure 2. Visual elementary parts from corresponding symbol.

Figure 3 .

 3 Figure 3. ARG description for a symbol in Fig. 2 -an example.

ΘFigure 4 .

 4 Figure 4. Computing spatial relations using radial-line rotation .

Figure 5 .

 5 Figure 5. identical histograms at 3 o resolution for original, translation and rotation between circle and corner from symbol in Fig. 2.

  Edge Signature: {1 • , 3 • , 5 • , 9 • }.

  Integration (Vertex + Edge Signature).

Figure 6 .

 6 Figure 6. Average Retrieval Efficiency over 30 queries.

Figure 7 .

 7 Figure 7. Visual illustration of symbol ranking at the output for a few queries: Q1, Q2 and Q3, showing for true retrieval and false, otherwise. The first symbol on the top always corresponds to the chosen query. Symbols are ranked from top to bottom based on decreasing order of similarity.


Julien Fréchet
email: jfrechet@unistra.fr

François Thouvenot

Michel Frogneux

Nicolas Deichmann

Michel Cara

The M W 4.5 Vallorcine (French Alps) earthquake of 8 September 2005 and its complex aftershock sequence

Keywords:

On 8 September 2005 a moderate M W 4.5 earthquake occurred in the north-western Alps midway between Chamonix (France) and Martigny (Switzerland). The focal mechanism corresponds to a right-lateral strike-slip on a N60°E fault plane. The foreshock-mainshockaftershock sequence is investigated on the basis of data recorded by a temporary network of 28 stations deployed for one month just after the mainshock, and data from permanent, regional seismic networks. Absolute and relative locations of more than 400 events are obtained with a mean uncertainty of approximately 0.2 km. Small foreshocks, the mainshock and early and late aftershocks are located relative to the main aftershock set. The seismic sequence exhibits a surprisingly complex structure, with at least five clusters on distinct fault planes. The main elongated cluster agrees with the location of the mainshock, its hypocentre being 4.3 km below sea level. We discuss the relationship between the right-lateral fault beneath the Loriaz peak (the source of the Vallorcine event), the nearby normal Remuaz fault, and the regional seismotectonic stress field.

Introduction

The Vallorcine earthquake (M W 4.5, M L 4.9) occurred on 8 September 2005 at 11:27 UTC in the French Alps near the Swiss border (Fig. 1). Its epicentre was located in the Aiguilles Rouges massif, some 10 km north of Chamonix and the Mont Blanc massif. Though widely felt, it produced only slight damage in the epicentral zone, with a maximum intensity of V on the EMS-98 scale [START_REF] Bcsf | Séisme de Vallorcine (Savoie) du 8 septembre 2005. Note préliminaire BCSF2005-NP4[END_REF][START_REF] Cara | Observations sismologiques: sismicité de la France en 2003[END_REF]. Just one century earlier, on 29 April 1905, this zone was hit by the Chamonix earthquake, which caused significant damage, with a magnitude M W = 5.5-5.6 and a maximum intensity VII-VIII MSK64 [START_REF] Alasset | Sismotectonique et identification des sources sismiques en domaine à déformation lente: cas des Pyrénées orientales et des Alpes du Nord (France)[END_REF]Cara et al. 2008). A few kilometres to the southwest another earthquake causing slight damage occurred on 11 March 1817 (M W = 4.8) with a maximum intensity VII MSK64 (ECOS 2009;SisFrance 2010). The Aiguilles Rouges massif is located at the western end of the Rhone fault zone in the Swiss Valais, one of the seismically active regions of the western Alps [START_REF] Maurer | Active tectonism in the central Alps: contrasting stress regimes north and south of the Rhone Valley[END_REF][START_REF] Pfiffner | Deep Structure of the Swiss Alps: Results of NRP 20[END_REF]. Five historical earthquakes causing severe damage and reaching intensity VIII on the EMS-98 scale have occurred in the Valais over the last five centuries (ECOS 2009): Ardon (April 1524, M W = 6.4), Aigle (11 March 1584, M W = 6.4), Brig (9 December 1755, M W = 6.1), Visp (25 July 1855, M W = 6.4), and Ayent (25 January 1946, M W = 6.1). On the French side, the level of historical seismic activity is lower, with a maximum intensity VII-VIII for two events only, while on the Italian side the level is even lower with only one known event exceeding intensity VI (at Pont-Saint-Martin on 5 March 1892, VII-VIII, M W = 4.8). All known historical earthquakes with epicentral intensity above VI are plotted in Fig. 1. With the exception of the 1855 Visp and the 1892 Pont-Saint-Martin events, all the events are located in the external Alps, i.e. to the north-west of the Frontal Pennine Thrust, the major structural limit which represents the scar of the former Tethys in the northwestern Alps.

The recent microseismicity as recorded by regional seismic networks is plotted in Fig. 1 for the period 1992-2004. Its distribution differs noticeably from the major historical earthquakes. The Frontal Pennine Thrust also appears today as a major boundary between different seismic domains. The external north-western zone exhibits a scattered seismicity throughout the domain, with a clear SW-NE alignment in the Valais. The internal south-eastern zone exhibits a wide, elongated seismic zone following the Penninic front, a zone often called the Briançonnais seismic arc in the French section. The 1892 Pont-Saint-Martin earthquake lies within the south-easternmost seismic zone, called the Piedmontese seismic arc [START_REF] Thouvenot | Seismicity along the northwestern edge of the Adria microplate[END_REF].

It has recently been demonstrated that the Briançonnais seismic arc corresponds to an extensional present-day stress regime, whereas the external zone is dominated by a strike-slip or, more rarely, a compressionalregime (e.g. [START_REF] Maurer | Active tectonism in the central Alps: contrasting stress regimes north and south of the Rhone Valley[END_REF][START_REF] Sue | Widespread extension in the core of the western Alps revealed by earthquake analysis[END_REF][START_REF] Delacou | Present-day geodynamics in the bend of the western and central Alps as constrained by earthquake analysis[END_REF][START_REF] Kastrup | Stress field variations in the Swiss Alps and the northern Alpine foreland derived from inversion of fault plane solutions[END_REF][START_REF] Thouvenot | Seismicity along the northwestern edge of the Adria microplate[END_REF]. However, within the Aiguilles Rouges massif where the Vallorcine 2005 earthquake took place, the tectonic pattern could be more complex. A recent investigation of a Variscan fault, currently activated as a normal left-lateral fault on the eastern flank of the Aiguilles Rouges massif (the Remuaz fault) surmised that this fault might be responsible for the Chamonix 1905 earthquake [START_REF] Alasset | Sismotectonique et identification des sources sismiques en domaine à déformation lente: cas des Pyrénées orientales et des Alpes du Nord (France)[END_REF][START_REF] Alasset | An active normal fault NW of the Mont Blanc massif, France: sign of extensive tectonics near the main thrust zone of the Chamonix valley?[END_REF][START_REF] Cara | The Chamonix, 1905, earthquake: focal mechanism determination based on two Göttingen Wiechert records[END_REF][START_REF] Van Der Woerd | The Remuaz fault in the Aiguilles Rouges massif (France): evidence for an active normal fault NW of the Mont Blanc? EGU General Assembly[END_REF].

To obtain a detailed description of the fault segment that ruptured in 2005 and investigate its relation to the Mont Blanc -Aiguilles Rouges tectonics, we installed a temporary seismic network in the epicentral region the day after the Vallorcine event and operated it for about one month thereafter. This paper documents the numerous aftershocks recorded by the network, and analyses the complete foreshock-mainshock-aftershock sequence.

Mainshock

The Vallorcine mainshock occurred on 8 September 2005 at 11:27 UTC (13:27 local time). Its epicentre was located in the vicinity of Vallorcine, a village situated in the northern French Alps next to the Swiss border, at a distance of approximately 13 km from the two nearest large towns, Chamonix-Mont-Blanc (France) and Martigny (Switzerland). Its magnitude reached M L 4.9 (after RENASS and SED, the French and Swiss national networks) and M W 4.5±0.1 (Global CMT;SED 2005a[START_REF] Pfiffner | Deep Structure of the Swiss Alps: Results of NRP 20[END_REF][START_REF] Delouis | Groupe de travail: magnitude de moment[END_REF][START_REF] Delouis | A method for rapid determination of moment magnitude Mw for moderate to large earthquakes from the near-field spectra of strongmotion records (MWSYNTH)[END_REF]. It was felt over a broad area with a radius of more than 200 km in the adjacent regions of France, Italy, and Switzerland. The maximum intensity reached a value of V EMS-98 with only slight damage in the Vallorcine (France) -Martigny (Switzerland) area [START_REF] Bcsf | Séisme de Vallorcine (Savoie) du 8 septembre 2005. Note préliminaire BCSF2005-NP4[END_REF][START_REF] Cara | Observations sismologiques: sismicité de la France en 2003[END_REF]. It also triggered a number of rock falls in the Mont Blanc and Aiguilles Rouges massifs, one of them hurting a rock climber in the vicinity of Vallorcine. The earthquake affected springs in Vallorcine, inducing flow modifications, impurity content and a change in the colour of the water that persisted for several days.

Location

Preliminary locations provided by the French and Swiss agencies were all within 2 km of the village of Vallorcine (Table 1 and Fig. 2). As will be shown in a later section, the mainshock has been relocated by a joint hypocenter determination including foreshocks, mainshock and aftershocks. The procedure is based on the double-difference algorithm implemented in the HypoDD software [START_REF] Waldhauser | A double-difference earthquake location algorithm: Method and application to the northern Hayward fault[END_REF][START_REF] Waldhauser | HypoDD -A Program to Compute Double-Difference Hypocenter Locations[END_REF]).

Since many aftershocks were simultaneously recorded by the local temporary network and the permanent networks, station corrections related to velocity model uncertainties can be derived. These in turn allow the mainshock to be relocated relative to the well-located aftershocks. The resulting coordinates of the mainshock delivered by HypoDD are reported in Table 1. Its hypocenter is located at a depth of 4.3 km below sea level, corresponding to approximately 6.8 km below the surface. The hypocentre is thus located within the Aiguilles Rouges crystalline massif, 2.5 km west of Vallorcine, just below the Loriaz peak (Aiguille de Loriaz).

Focal mechanism

The focal mechanism of the mainshock was derived from the first-motion data recorded at 277 stations in France, Switzerland, Italy, Germany, Austria, and Slovenia.

Epicentral distances range from 3 km (station EMV, Vieux-Emosson Reservoir) to 811 km (station ROSF, Brittany). The azimuthal coverage is good (Fig. 3), with a maximum gap of 14° in the NW quadrant. We used the focal position provided by the relocation procedure, and the [START_REF] Sellami | Initial reference velocity model for seismic tomography in the western Alps[END_REF] The mainshock had a pure strike-slip mechanism. The N60°E-striking nodal plane dips 65° to the SE, while the N150°E-striking plane is vertical. The N60°E direction corresponds to the main aftershock swarm as discussed in the next sections, which implies that motion on the N60°E-striking fault plane is right-lateral. Both the P-and T-axes plunge 18°. The P-axis trends WNW, and the T-axis NNE (Table 2). These results agree relatively well with the moment tensor derived from a full-waveform inversion of broad-band records, which gives a strike of 57°, a dip of 84°, and a rake of 178° for the nodal plane, based on 33 stations in Switzerland and neighbouring countries [START_REF] Deichmann | Earthquakes in Switzerland and surrounding regions during 2005[END_REF]. Similar results were obtained by [START_REF] Delouis | Le séisme du 8 septembre 2005 (11h27 UTC) à la frontière franco-suisse[END_REF] using only three French strong-motion stations in the 10-60 km distance and 178-324° azimuth ranges: strike 56°, dip 83°, rake 175°. The main difference between the first-motion and broad-band focal mechanisms is a higher 83-84° dip for the 56-60° striking plane. The seismic moment value given by the Swiss Seismological Service SED is M 0 = 5.74 x 10 15 N•m and the moment magnitude M W = 4.47 -exactly the same value as that found by [START_REF] Delouis | A method for rapid determination of moment magnitude Mw for moderate to large earthquakes from the near-field spectra of strongmotion records (MWSYNTH)[END_REF]. The seismic moment from the Global CMT catalogue is 9.34 x 10 15 N•m (M W = 4.6), with a nodal plane very similar to that obtained from first motions (strike 60°, dip 66°, rake 169°).

Data acquisition and processing

Beginning the day after the mainshock, we deployed 28 mobile stations in the epicentral zone (Fig. 2). This complete network was maintained for one month, while 4 stations were operated for an additional period of two and a half months. One station, 4 km from the epicentre, was kept operating even longer, until May 2006. The stations were installed and maintained by teams from the three participating geophysical institutes (IPGS in Strasbourg, LGIT in Grenoble, and SED in Zurich), and hence were rather heterogeneous. All stations were high-dynamic digital recorders equipped with three-component seismometers and GPS time receivers. Table 3 gives detailed information on the stations and sensors used.

During the one-month recording period starting on 9 September and ending on 10 October 2005, over 300 aftershocks were recorded, with magnitudes ranging from 2.4 (on 18 September) down to -0.7. As will be seen in the next section, 289 of these events were recorded by a sufficiently large number of stations and could be precisely located. Given the heterogeneous recording systems, the original data were recorded in several different formats.

During the first processing stage, all available data was converted into two common data formats, SAC (Seismic Analysis Code) and Sismalp, allowing us to create a homogeneous database. The temporary network had an extension of approximately 20 km. Two permanent stations are located within the temporary network (EMV-SED network-and OG03-Sismalp network-), while nine other permanent stations are located within 50 km of the temporary network and the mainshock epicentre (OG01,OG02, OG04, and RSL from the Sismalp/Rénass network, AIGLE, DIX, GRYON, SALAN, and SENIN from the SED network). The seismograms of these 11 permanent stations were merged with the data of the 28 temporary stations.

All recorded events were then picked using the Pickev2000 software [START_REF] Fréchet | Pickev 2000: Software for seismogram picking and processing, earthquake location, and mapping[END_REF]. A total of 9630 P and S arrival times were read, along with over 1600 duration readings used for magnitude estimates. We firstly located all the events using the Hypref program [START_REF] Fréchet | Hypref[END_REF], an improved version of Hypo71 [START_REF] Lee | HYP071 (Revised): A computer program for determining hypocenter, magnitude, and first motion pattern of local earthquakes[END_REF]. Hypref handles higher time precision (millisecond accuracy), computes travel times taking into account station elevations, and allows users to specify the lowest turning-point layer reached by the ray (a feature enabling secondary arrivals to be processed, but which was not used here).

A second dataset was prepared in the same way, adding the four foreshocks that occurred on 3 and 5 September, the mainshock, and the first ten aftershocks recorded on 8 September. These 15 events were only recorded by the permanent networks. We also added the 100 late aftershocks that occurred between 11 October and 31 December 2005 to this dataset. The late aftershocks were recorded by both the permanent networks and the remaining one to five temporary stations. This heterogeneous dataset was then relocated in a second phase by means of the double-difference algorithm implemented in the HypoDD software [START_REF] Waldhauser | A double-difference earthquake location algorithm: Method and application to the northern Hayward fault[END_REF][START_REF] Waldhauser | HypoDD -A Program to Compute Double-Difference Hypocenter Locations[END_REF]). This joint hypocenter relocation aims at two different goals: 1) high-resolution relocation of aftershock clusters, and 2) relocation of the fore-, main-and early after-shocks.

For both location procedures (Hypref and HypoDD), several tests were performed in order to find the most effective velocity model and program parameters. Two very different velocity models were compared: the first consisted of the [START_REF] Sellami | Initial reference velocity model for seismic tomography in the western Alps[END_REF] minimum 1-D model (8-layer crust with 38-km-deep Moho) used for the focal mechanism study above, and representing the optimal 1D-model for the western Alps. The second was a simple half-space with a P-velocity of 6 km/s. No significant change in absolute position or depth was found using either model, while cluster structure was better resolved with the simple one-layer model. P-and S-wave arrival times were used, assigning half-weight to the latter. With Hypref, we obtained a mean RMS of 0.050 s and average relative horizontal and vertical uncertainties (ERH and ERZ) of 0.2 km. With HypoDD, the mean RMS could be reduced to 0.019 s.

The aftershocks recorded by the temporary network

Figure 4 presents the absolute locations (Hypref) of the 289 aftershocks recorded by the full temporary network during its one-month deployment. The prominent feature is an elongated cluster of aftershocks with an azimuth of 60° (named C1), approximately 2.5 km long. This main cluster of aftershocks was the only one active during the first seven days after the mainshock (with one exception on day 4, see below); 78 events in this cluster occurred during the first week and 81 thereafter. On 15 September at 09:33, a second cluster C2 became active, located 1.5 km north-northwest of the main cluster and comprising a total of 105 events. Two other smaller clusters were activated 4 and 12 days after the mainshock.

Cluster C3 located 5 km north-west of the main cluster comprises 20 events; it became active on 12 September at 10:20 with the only event in the first 7 days that was not located in the main cluster, the next event occurring on 20 September. Cluster C4 located between clusters C1 and C2 comprises 12 events with its first event occurring on 20 September at 06:44.

The transverse cross-section shown in Fig. 5 is computed along the azimuth 150°. On this section, the main cluster C1 is sub-vertical, slightly dipping to the south-east. It defines a fault patch, approximately 2.5 km long and 2 km deep, with its top at a depth of 3 km below sea level, i.e. 4.5 km beneath the mean ground surface. Clusters C2 and C4 are located at about the same depth as the main cluster C1, while cluster C3 is located a little deeper, at an average depth of 6 km below sea level. with the HypoDD program, which results in a high-resolution relocation of the hypocenters.

Figure 6 shows a close-up of the clusters on a map and in a cross-section. In the map view (Fig. 6a), the main cluster C1 is a well-defined linear feature, but divided into two subclusters separated by a 0.5 km long gap. The longitudinal cross-section AA' (Fig. 6b) includes only the aftershocks that are in the 0.7 km wide box sketched on the map view (Fig. 6a). It shows that the main aftershock cluster comprises several sub-clusters or asperities. The map view also shows that the second cluster (C2) is resolved into two sub-clusters C2a and C2b, also clearly visible on the transverse cross-section BB' (Fig. 6c). The southernmost subcluster C2a defines a sharp sub-vertical alignment oriented N70°E. The northernmost one (C2b) is less well defined; however, based on the relocation of the later aftershocks between 11 October and 31 December (Fig. 7) and other cross-sections, it defines an alignment oriented N80°E gently dipping to the south. Time-wise, sub-cluster C2a was active mainly during the first 20 days, while later activity was concentrated in sub-cluster C2b. The two smaller clusters C3 and C4 are highly concentrated within 150 m diameter volumes and do not have any preferred orientation.

The foreshock-mainshock-aftershock sequence

In order to study the relationship of the events recorded by the temporary network, described in the previous section, to the four foreshocks, the mainshock and the ten early aftershocks preceding deployment of the temporary network, we merged all data into a single dataset, which was then reprocessed with the HypoDD software. The relocated foreshocks, mainshock and early aftershocks are shown in Fig. 7 with the aftershock clusters as background. The mainshock is located right in the middle of the main cluster C1, while the early aftershocks are scattered around the central and eastern part of this cluster. One early aftershock could be associated with the small cluster C4. Three out of the four foreshocks took place exactly at the mainshock hypocenter position on 3 September, i.e. 5 days before the mainshock. On the other hand, the fourth and last foreshock occurred on 5 September at the position of cluster C3, 5 km north-west of the mainshock.

Thus the temporal and spatial coincidence of the mainshock and cluster C1 as well as the strike and dip of fault defined by the hypocenter distribution of this cluster allow us to identify the N60°E nodal plane of the mainshock focal mechanism as the actual fault plane.

After the 10 October, most temporary stations were withdrawn. However, more than 100 late aftershocks were recorded by the few remaining temporary stations and the permanent stations. They were included in the complete foreshock-mainshock-aftershock dataset. The global HypoDD inversion allowed us to relocate 94 of the late aftershocks. The resulting hypocenters are also plotted in Fig. 7. They all occurred within the main cluster C1 and sub-cluster C2b.

The time history of activity is plotted in Fig. 8 as a time-section along line BB'. To assess whether the earthquake clusters active immediately before and after the Vallorcine event were also active in the years before and after 2005, we searched the Swiss Seismological Service (SED) database for additional events that could be associated to these clusters since 1991. Because of the poor azimuthal station distribution, the routine locations of the SED network are not precise enough for such an analysis. We have therefore resorted to an assessment of the signal similarities between events known to be associated to these clusters based on the HypoDD relocations and events recorded before September 2005 and after December 2005 at selected stations. The vertical components at stations EMV and SALAN were band-pass filtered between 1 and 20 Hz. Visual inspection of the filtered traces allowed us unequivocally to identify families of similar events, making computation of crosscorrelations unnecessary (Fig. 9). The summary of events detected by the permanent network of the SED over different time periods and associated to each cluster is summarized in Table 4.

Due to the size of cluster C1 as well as the large number and magnitude range of the events, the signal character is somewhat heterogeneous. Nevertheless, as shown in Fig. 9a, there are families of similar earthquakes within this large cluster that constitute unequivocal evidence of repeated sporadic activity of cluster C1, dating at least as far back as the year 2001 and extending well into 2009. But the main activity of cluster C1 is clearly linked to the ML 4.9 mainshock and for the most part constitutes an aftershock activity that will probably persist beyond the year 2009.

Cluster C2, in contrast, is quite different. The activity of this cluster started several days after the mainshock and, although it was very active in September and October 2005, activity declined rapidly thereafter and seems to have come to a complete stop in late 2006.

As shown by some representative seismogram examples in Fig. 9b, the signals of the events within each sub-cluster (C2a and C2b) exhibit a high degree of similarity, but differ somewhat between the two sub-clusters, so that they can be clearly distinguished. From this it is clear that the activity of cluster C2 started in sub-cluster C2a, located closer to the mainshock, and then moved to sub-cluster C2b located slightly more to the NW (this is also visible from the temporal evolution shown in Fig. 8). A causal relation between cluster C2 and the mainshock and aftershocks in cluster C1 is therefore very likely.

Only four of the 20 events in cluster C3 recorded by the temporary network were strong enough also to be detected by the permanent network of the SED. The signals of these events recorded at station EMV are nearly identical, not only among these four events, but also to three other events that occurred in 2000 as well as two events in 2006 and one in 2007.

So in contrast to cluster C2, which was only active over a short time period after the Vallorcine mainshock, cluster C3 constitutes a site of ongoing sporadic activity. Moreover, given the distance of about 5 km from the mainshock and the fact that in 2005 it became active before the occurrence of the mainshock, a causal link between the two is not immediately evident, although the increased activity in September and October 2005 might not be entirely fortuitous.

The events associated to cluster C4 were too weak to be detected by the permanent network of the SED. However, the temporal evolution of the activity recorded by the temporary network, as shown in Fig. 8, indicates that the activity of this cluster was limited to a few weeks. This temporal coincidence together with its location in between clusters C1 and C2 suggests that the activity in cluster C4 was probably linked in some way to the Vallorcine mainshock.

Discussion and conclusions

From the evidence presented above, we have found that the Vallorcine earthquake corresponds to the rupture of a fault segment located beneath the Loriaz peak, thereafter named the Loriaz fault. The rupture area is approximately 2.5 x 2 km 2 if we identify it with the main cluster of aftershocks, which is consistent with the moment magnitude M W = 4.5.

For example, using the relation between moment magnitude and rupture area log(A) = 0.9 M W -3.42 given by [START_REF] Wells | New empirical relationships among magnitude, rupture length, rupture width, rupture area, and surface displacement[END_REF] for strike-slip earthquakes, this results in a value of 4.4 km 2 . It was unexpected that a moderate earthquake of this magnitude could generate such a complex pattern of secondary faulting within the aftershock sequence involving five fault segments, the furthest being at a distance of 5 km from the mainshock segment. This may suggest that the Loriaz seismic zone is highly fractured, with no major fault involved. This observation agrees with the mapped surface faults sketched in Fig. 10 (after [START_REF] Ayrton | Feuille Chamonix[END_REF]). In the Aiguilles Rouges massif, numerous short fault segments are mapped, with lengths of less than 2 km and strikes in the N20°E-N70°E range, i.e. sub-parallel to oblique to the N23°E-striking Remuaz Fault.

At a distance of 40 and 70 km to the south-west of Vallorcine, two other earthquakes were studied by means of temporary networks in recent years (Fig. 1): the Grand-Bornand earthquake on 14 December 1994 [START_REF] Fréchet | Le séisme du Grand-Bornand (Haute-Savoie) du 14 décembre 1994: un coulissage dextre dans le socle subalpin[END_REF]) and the Epagny earthquake on 15 July 1996 [START_REF] Thouvenot | The ML 5.3 Épagny (French Alps) earthquake of 1996 July 15: a long-awaited event on the Vuache fault[END_REF]. The Epagny earthquake-M L 5.3-had a strike-slip mechanism and produced a profuse and protracted aftershock sequence, with more than 1000 aftershocks lasting for several months, and even years, a feature resembling the Vallorcine aftershock sequence. In contrast, the Grand-Bornand earthquake-M L 5.1-was followed by a surprisingly low activity, fewer than 20 small aftershocks. The Grand-Bornand event was located at a depth of 8 to 10 km and its focal mechanism involved strike-slip motion with a significant thrust component. The P-axes of the three events-Grand-Bornand, Epagny, and Vallorcine-are remarkably coherent, their azimuths ranging from 274° to 282°, and their plunges from 16° to 22°.

The strike of the Loriaz fault, N60°E, is well defined by the main aftershock cluster and perfectly agrees with the nodal plane from first motions (Fig. 3) or from Global CMT.

However, the dip of the nodal plane obtained from the same methods, 65-66°, differs significantly from the apparent dip of the aftershock cluster, which is close to 80°. [START_REF] Deichmann | Earthquakes in Switzerland and surrounding regions during 2005[END_REF] and [START_REF] Delouis | Le séisme du 8 septembre 2005 (11h27 UTC) à la frontière franco-suisse[END_REF] found a dip of 83-84° much closer to the dip of the aftershock cluster. The strike values they found (N57°E and N56°E respectively) do not significantly differ from the direction of cluster C1 (N60°E). This uncertainty on the dip of the fault plane makes it difficult to trace the position of the Loriaz fault at the surface precisely. The measured direction of the Loriaz fault parallels a set of small faults in the core of the Aiguilles Rouges massif, west of and oblique to the Remuaz fault (Fig. 10). The top of the aftershock zone its located at a depth of 4.5 km below the ground surface, making its correlation with surface faults difficult. It is also possible that the Loriaz fault is a hidden fault without any extension to the surface. However, it is tempting to associate the Loriaz fault plane at depth with one of the several small faults visible at the surface. Incidentally, field investigations by one of us (M. C.) have revealed small ground fissures in a sedimentary slope at the bottom of a long fracture striking N60°E and descending from the summit of the Gros Nol peak (Fig. 11). Field observations, combined with aerial photographs, provide evidence of other fractures striking N60°E in the same zone. The main lineament, beginning a few hundred meters north of the Gros Nol and 1.4 km long, is drawn on the detailed geological map of von [START_REF] Raumer | Mont Blanc and Aiguilles Rouges: Geology of their polymetamorphic Basement (External Massifs, France-Switzerland)[END_REF] as a tectonic line. However, if we assume a mean dip of 75° for the ruptured fault plane, its surface trace could correspond to the westward extension of a clear surface fault located 2 km further north that runs from the Cheval Blanc peak towards the Emosson lake and dam (Fig. 10). Von [START_REF] Raumer | Mont Blanc and Aiguilles Rouges: Geology of their polymetamorphic Basement (External Massifs, France-Switzerland)[END_REF] mapped this fault extending eastward right to the dam's west bank and crossing it towards its east bank. This 4 km long fault offsets the pre-Mesozoic basement metamorphic rocks in an apparent right-lateral displacement.

The hypocenter of the Vallorcine earthquake is definitely not located on the Remuaz fault (Fig. 10) located 4 km to the south-east and investigated by [START_REF] Alasset | Sismotectonique et identification des sources sismiques en domaine à déformation lente: cas des Pyrénées orientales et des Alpes du Nord (France)[END_REF], [START_REF] Alasset | An active normal fault NW of the Mont Blanc massif, France: sign of extensive tectonics near the main thrust zone of the Chamonix valley?[END_REF], [START_REF] Cara | The Chamonix, 1905, earthquake: focal mechanism determination based on two Göttingen Wiechert records[END_REF], and [START_REF] Van Der Woerd | The Remuaz fault in the Aiguilles Rouges massif (France): evidence for an active normal fault NW of the Mont Blanc? EGU General Assembly[END_REF]. Its focal mechanism, which corresponds to a strike-slip fault, seems at first sight to be incompatible with their assumed mechanism for the Remuaz fault, since its P-axis oriented N102°E is almost perpendicular to the Remuaz fault. On the other hand, the Vallorcine mechanism agrees well with the assumed transpressive state of stress of the external zone attested to by several recent studies (e.g. [START_REF] Maurer | Active tectonism in the central Alps: contrasting stress regimes north and south of the Rhone Valley[END_REF][START_REF] Sue | Widespread extension in the core of the western Alps revealed by earthquake analysis[END_REF][START_REF] Delacou | Present-day geodynamics in the bend of the western and central Alps as constrained by earthquake analysis[END_REF][START_REF] Kastrup | Stress field variations in the Swiss Alps and the northern Alpine foreland derived from inversion of fault plane solutions[END_REF][START_REF] Thouvenot | Seismicity along the northwestern edge of the Adria microplate[END_REF]. Figure 12 presents all previously published reliable fault plane solutions in the region. The transpressive regime of the external zone is observed for a large number of earthquakes in the neighbouring regions of the Mont Blanc and Aiguilles Rouges massifs.

Several recent observations confirm this regime, be it the aforementioned broadly felt earthquakes of Grand-Bornand 1994 andEpagny 1996, the two Chablais events in 1990 and 2000 studied by [START_REF] Delacou | Active strike-slip faulting in the Chablais area (NW Alps) from earthquake focal mechanisms and relative locations[END_REF], or the smaller 2001 sequence in the region of Martigny [START_REF] Deichmann | Earthquakes in Switzerland and surrounding regions during 2001[END_REF], which all exhibit strike-slip motion-with a small component of thrust for some of them. It is not uninteresting to observe that the difference between external and internal zones is not only exhibited by the stress regime, but also by the seismic regime.

Indeed, as noted in the introduction, the internal zones are characterized by a lack of major historical earthquakes despite the strong activity of small magnitude earthquakes, almost the reverse of the external zones (Fig. 1).

Two hypotheses could explain the assumed conflicting motion on the Remuaz fault.

The strike-slip mechanism of the Loriaz fault combined with the normal mechanism of the Remuaz fault may suggest that the Aiguilles Rouges massif is in a transtensive stress state, thus corresponding to a transition zone between the transpression in the external zone and the extension in the internal one. A similar apparent discrepancy was observed by [START_REF] Baer | Earthquakes in Switzerland and surrounding regions during 2002[END_REF] in the Swiss Valais. Alternatively, the scarp with apparent normal faulting mapped by [START_REF] Alasset | An active normal fault NW of the Mont Blanc massif, France: sign of extensive tectonics near the main thrust zone of the Chamonix valley?[END_REF] on the Remuaz fault may correspond to a local gravitational slope instability or a postglacial differential uplift as modelled by [START_REF] Ustaszewski | Composite faults in the Swiss Alps formed by the interplay of tectonics, gravitation and postglacial rebound: an integrated field and modelling study[END_REF] in Switzerland. In the latter case, the Remuaz fault would not be the source zone of the Chamonix 1905 earthquake. Instead, the Chamonix 1905 event might have occurred on the same fault system as the Vallorcine 2005 earthquake. Re-evaluation of historical seismograms and bulletin data is necessary to find new evidence in favour of either hypothesis. Data taken from [START_REF] Fréchet | Le séisme du Grand-Bornand (Haute-Savoie) du 14 décembre 1994: un coulissage dextre dans le socle subalpin[END_REF], [START_REF] Thouvenot | The ML 5.3 Épagny (French Alps) earthquake of 1996 July 15: a long-awaited event on the Vuache fault[END_REF], [START_REF] Sue | Widespread extension in the core of the western Alps revealed by earthquake analysis[END_REF][START_REF] Deichmann | Earthquakes in Switzerland and surrounding regions during 1999[END_REF], [START_REF] Deichmann | Earthquakes in Switzerland and surrounding regions during 2001[END_REF], [START_REF] Baer | Earthquakes in Switzerland and surrounding regions during 2002[END_REF], [START_REF] Thouvenot | The Belledonne Border Fault: identification of an active seismic strike-slip fault in the western Alps[END_REF]), Deichmann et al. (2004), [START_REF] Kastrup | Stress field variations in the Swiss Alps and the northern Alpine foreland derived from inversion of fault plane solutions[END_REF][START_REF] Baer | Earthquakes in Switzerland and surrounding regions during 2004[END_REF], [START_REF] Delacou | Active strike-slip faulting in the Chablais area (NW Alps) from earthquake focal mechanisms and relative locations[END_REF]

Figure captions

  velocity model (8-layer crust with 38 km deep Moho). Out of the seismograms recorded in the 277 stations, we retained 222 polarities because of the low signal-to-noise ratio in the other 55 stations. The fault-plane solution is well constrained: changing the velocity model or the focal depth does not modify the strike and dip values of the nodal planes. However, a few discrepant observations can be noted in the southern azimuth; in the WSW azimuth (dilatation quadrant), two stations in the French Pyrenees inexplicably recorded clear compressions.

Fig. 1 Fig. 2 Fig. 4 Fig. 5 Fig. 7 Fig. 8 Fig. 9 Fig. 12

 124578912 Fig. 1 Situation map of the Vallorcine earthquake. Geology: grey = external Alps, pink = external crystalline massifs, yellow = internal Alps, orange = internal crystalline massifs. Seismicity: star = Vallorcine 2005 epicentre, red = microseismicity 1992-2004 from SED and Sismalp, open circles = historical earthquakes with intensity above VI, red open circles = Epagny and Grand-Bornand earthquakes (see text)

  Fault plane solution of the Vallorcine earthquake is shown in red. Otherwise, same as Fig. 1 Click here to download high resolution image

Acknowledgements

The field experiment benefited from a financial support by Institut National des Sciences de l'Univers (CNRS). We thank the field teams that helped to install and maintain the temporary network. Thanks to the two reviewers for their helpful suggestions. The Réseau National de Surveillance Sismique (RéNaSS), the Observatoire de Grenoble, and several Conseils généraux (Isère, Alpes-de-Haute-Provence, Hautes-Alpes, Haute-Savoie, Savoie, Ain) support the running costs of French seismic stations in the study area.