Marc Baboulin
email: marc.baboulin@inria.fr

Joel Falcou
email: joel.falcou@lri.fr

Ian Masliah
email: ian.masliah@lri.fr

Towards an automatic generation of dense linear algebra solvers on parallel architectures

Keywords: Numerical libraries, generative programming, active libraries, GPU computing, dense linear systems, mixed precision algorithms calcul numérique, programmation générative, bibliothèques actives, calcul sur GPU, systèmes linéaires denses, algorithmes en précision mixte

The increasing complexity of new parallel architectures has widened the gap between adaptability and efficiency of the codes. As high performance numerical libraries tend to focus more on performance, we wish to address this issue using a C++ library called N T 2 . By analyzing the properties of the linear algebra domain that can be extracted from numerical libraries and combining them with architectural features, we developed a generic approach to solve dense linear systems on various architectures including CPU and GPU. We have then extended our work with an example of a least squares solver based on semi-normal equations in mixed precision that cannot be found in current libraries. For the automatically generated solvers, we report performance comparison with state-of-the-art codes, showing that it is possible to obtain a generic code with a high-level interface (similar to Matlab) that can run either on CPU or GPU and that does not generate significant overhead.

Introduction

A major concern when developing dense linear algebra software is to propose a user-friendly Application Programming Interface (API) that can retain performance of BLAS-like [START_REF] Dongarra | Basic Linear Algebra Subprograms Technical Forum Standard[END_REF] optimized routines. Moreover, with the increase in parallelism and heterogeneity as well as the ever increasing data-communication costs, numerical libraries often require to be modified or redesigned in order to take advantage of new features in parallel architectures [START_REF] Luszczek | Looking back at dense linear algebra software[END_REF]. In our study we consider more specifically the dense linear algebra libraries LAPACK [START_REF] Anderson | LAPACK Users' Guide[END_REF] (serial library for CPU processors) and MAGMA [START_REF] Tomov | Towards dense linear algebra for hybrid GPU accelerated manycore systems[END_REF] (for Graphics Processing Units). The disparity between these libraries that are targeting different architectures illustrate one of the issues in designing optimized linear algebra software. While being able to maintain a similar interface for the routines, the code and structure of all algorithms ported from LAPACK to MAGMA had to be rewritten to match the architectural features and the programming language of the accelerator. Furthermore, these libraries are implemented using low-level languages like C or FORTRAN and thus cannot provide a high-level interface that would be closer to the specification language of the numerical linear algebra practitioner without losing in performance. This issue is represented by the abstraction/efficiency trade-off problem where raising the abstraction level with object-oriented and generic programming techniques is obtained at the cost of performance, which inhibits the flexibility and adaptability of libraries. Some solutions have been proposed in recent years but they tend to solve partially the abstraction/efficiency trade-off problem. The method followed by the Formal Linear Algebra Methods Environment (FLAME) with the Libflame library [START_REF] Van Zee | The libflame library for dense matrix computations[END_REF] is a good example. It offers a framework to develop dense linear solvers through the use of algorithmic skeletons [START_REF] Cole | Algorithmic skeletons: structured management of parallel computation[END_REF] and an API which is more user-friendly than LAPACK while giving satisfactory performance results. Another approach is the one followed in recent years by C++ libraries built around expression templates [START_REF] Veldhuizen | Expression templates[END_REF] or other generative programming [START_REF] Czarnecki | Generative programming[END_REF] principles for high-performance computing. Examples of such libraries are Armadillo [START_REF] Conrad | Armadillo: An open source C++ linear algebra library for fast prototyping and computationally intensive experiments[END_REF] and MTL [START_REF] Gottschling | Representation-transparent matrix algorithms with scalable performance[END_REF]. Armadillo provides good performance with BLAS and LAPACK bindings and an API close to Matlab [36] for simplicity. However it does not provide a generic solver like the Matlab routine linsolve that can analyze the matrix type and choose the correct routine to call from the LAPACK library. It also does not support GPU computations which are becoming mandatory for medium to large dense linear algebra problems. In a similar way, while MTL can topple the performance of vendor-tuned codes, it does not offer linsolves-like implementation or GPU support. Other examples of libraries with similar content include Eigen [30] , Flens [START_REF] Lehn | FLENS[END_REF], Ublas [START_REF] Walter | The boost uBLAS library[END_REF] and Blaze [START_REF] Iglberger | Expression templates revisited: a performance analysis of current methodologies[END_REF].

Our objective in this paper is to provide a solution to the problems of portability and adaptability on new computer architectures. It is designed on top of N T 2 [START_REF] Esterie | The numerical template toolbox: A modern C++ design for scientific computing[END_REF][START_REF] Falcou | Meta-programming applied to automatic SMP parallelization of linear algebra code[END_REF], a scientific library written in C++. N T 2 provides a Matlab-inspired API and its implementation is based on a meta-programming technique known as "expression templates" [START_REF] Veldhuizen | Expression templates[END_REF]. The contributions of this paper are the following.

• We propose an architecture aware binding between N T 2 and LAPACK/MAGMA based on markers to dispatch between the different architectures and runtime back-ends in a extensible way.

• We provide an implementation of linsolve (in reference to the Matlab routine) that takes into account both hardware and algorithmic features to select and generate the proper chain of calls of optimized LAPACK/MAGMA routines from the high-level C++ code, mapping over 160 kernels. Note that the support for different factorizations (QR, Cholesky, LU, SVD) is also provided in N T 2 to facilitate the development of new solvers.

• An example of automatically generated solver (for different architectures) that does not exist in current libraries is given. This is illustrated by a linear least squares solver in mixed-precision arithmetic that achieves performance similar to optimized routines. For this solver, we show that linsolve does not generate a size-able overhead compared to direct calls to LAPACK or MAGMA.

This paper is organized as follows: in Section 1, we describe various programming techniques that can be found to combine algorithmic and architectural features in libraries. The methods that we used in N T 2 are then introduced. They enable us to achieve re-use and adaptability of library codes while preserving performance. In Section 2.1, we demonstrate how to combine these techniques in developing efficient dense linear algebra software. Then, as an example of application, we present in Section 2.3 the code generation of a mixed-precision linear least squares solver for which we give performance comparisons on CPU and GPU using respectively the QR routines from LAPACK and MAGMA. To our knowledge such a solver does not exist in public domain libraries LAPACK, PLASMA [START_REF]PLASMA users' guide, parallel linear algebra software for multicore architectures[END_REF] and MAGMA. Concluding remarks are given in Section 3.

1 Generative programming for designing numerical libraries

Optimization approaches based on a configuration space

As stated in Section , developing complex linear algebra software is a non trivial task due to the large amount of both algorithmic and architectural requirements. These combined factors create a configuration space containing the various configurations available for a given system. Deciding the correct combination of factors from a configuration space will then ensure optimal performance.

Compiler techniques based on iterative compilation [START_REF] Triantafyllis | Compiler optimization-space exploration[END_REF], where several optimizations from a configuration space are tested and the best one is selected, is a classical technique to improve performance. Similarly, such methods also exist at the library level.

An example of these methods can be found in the ATLAS [START_REF] Whaley | Automatically tuned linear algebra software[END_REF] library which is based on using optimized binaries. Each function's binary is generated during the installation phase with the iterative compilation technique. The generation process is accelerated by a hierarchical tuning system. In this system, the lower level functions are subject to a large selection process ensuring their optimal performance. High-level functions like BLAS 3 can then exploit feedback from the previous steps of the configuration process.

A second method is based on a performance analysis at runtime. For instance, a system like StarPU [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF] uses a monitored runtime system in which the performance of each function on a given hardware configuration is monitored in real-time. This monitoring allows StarPU to select the most optimized version of the algorithm by changing its parameters (tiling size, number of iterations,. . . ) or the targeted architecture (CPU, GPU, hybrid). Both methods described above are valid approaches in the field of high performance computing. However, in our case, we aim at providing a library level system for such exploration [START_REF] Veldhuizen | Active libraries: Rethinking the roles of compilers and libraries[END_REF] that will complement the compilers work. One way to do this is to use generative programming.

Inria

Generative programming in software development

Generative programming consists of bringing the benefits of automation to software development. Following this paradigm, a model can be drawn to implement the different components [START_REF] Czarnecki | Components and generative programming[END_REF] of a system. It is then possible to build a generator that will combine these components based on a generative domain model. This generator (or configuration knowledge) will ensure the transition from a configuration space with domain-specific concepts [START_REF] Gregor | Concepts: linguistic support for generic programming in C++[END_REF] and features to a solution space that encapsulates expertise at the source-code level. The code generation process will be hidden from the end-user by various meta-programming techniques which turn the user interface into a simple and clean API where few to none details about the algorithms and structures are visible.

Template meta-programming is a classical generative programming technique in which templates are used by a compiler to generate temporary source code. It is then merged with the rest of the source code and then finally compiled. The output of these templates includes compiletime constants, data structures, and complete functions. The use of templates can be thought of as compile-time execution that enables us to implement domain-specific optimizations. The technique is used by a number of languages, the most well-known being C++ [START_REF] Abrahams | C++ template metaprogramming: concepts, tools, and techniques from Boost and beyond[END_REF], D [START_REF] Bright | D language Templates revisited[END_REF], Haskell [START_REF] Sheard | Template Meta-programming for Haskell[END_REF] and OCaml [START_REF] Taha | A gentle introduction to multi-stage programming[END_REF].

Domain engineering methods for active libraries

We call active libraries [START_REF] Czarnecki | Generative programming and active libraries[END_REF] a technique which structures a set of generative programming and meta-programming methods to solve the abstraction/efficiency trade-off problem mentioned in Section . The main idea is to perform high-level optimization based on a semantic analysis of the code before any real compilation process. Such informations and transformations are then carried on by a meta-language that allows the developer to embed meta-informations in the source code itself, helping compilers to generate a better code by using these semantic informations. Active libraries are often implemented as Domain specific embedded language (or DSEL), which are languages implemented inside another host language. Designing DSEL is often easier as they reuse existing compilers and rely on domain dependent analysis to generate efficient code.

Czarnecki proposed a methodology called Domain Engineering Method for Reusable Algorithmic Libraries [START_REF] Czarnecki | Generative Programming: Methods, Tools, and Applications[END_REF] (or DEMRAL) based on the techniques described previously. DEMRAL can be seen as a specialization of a paradigm like object-oriented programming, aspect programming or model driven engineering [START_REF] Schmidt | Guest editor's introduction: Model-driven engineering[END_REF]. While we can find a large number of algorithms (N ) and implementations for distinct architectures (P ), the problem is that combining them can result in a large number of code to write (N * P ). Using DEMRAL, only N generic algorithms and P data structure descriptions are needed since the generator will choose the correct domainspecific implementation from the configuration space with the help of the configuration knowledge.

The DEMRAL methodology provides a high re-usability, allowing components to be customized while retaining the efficiency of statically configured code [START_REF] Musser | STL tutorial and reference guide: C++ programming with the standard template library[END_REF]. We extend it by adding an architectural-aware design (or AA-DEMRAL, depicted in Figure 1) with a domain specific architecture description and a specialized generator. This enables us to properly dispatch the various parametric sub-components by first generating them with an architectural marker (see Architecture generative component in Figure 1) In this section, we describe our approach to automatically generate linear algebra solvers on parallel architectures. Our answer stems from the programming techniques combined with a proper configuration space and smart containers for data management on GPU.

Linear system solvers

The first step to build linsolve is to identify the key properties of the configuration space and how to represent them. Once this analysis is done, we can refine these properties into high-level abstractions that will parameterize linsolve. These abstractions will then be used to define the configuration knowledge necessary to ensure the transition to the solution space. Concerning dense linear systems, we can identify 3 main properties that need to be taken into account: matrix structure, condition number, and targeted architecture.

A matrix structure can be divided into subcategories that can be identified statically (data type, storage scheme, matrix type and storage format). The data type and storage scheme parameters are already identified through the problem domain, respectively being scalar entries (real, double or single/double complex) and a dense matrix. The storage format is defined by N T 2 and shares a common interface with FORTRAN77 (column-major arrays). The matrix types correspond to the different ones available in the numerical libraries LAPACK and MAGMA (e.g., general, symmetric, hermitian...).

From the analysis of these subcategories, we consider the data and matrix types as important parameters. As they impact the underlying function call that needs to be generated, they will Inria both represent a level of the configuration space.

The second domain corresponds to the conditioning of the system. In current numerical libraries, the linear solvers are usually based on LU or QR factorizations in fixed precision, or mixed-precision algorithms [START_REF] Baboulin | Accelerating scientific computations with mixed precision algorithms[END_REF] with iterative refinement. It is not possible to identify statically if a system is ill-conditioned since it requires expensive computations which are not manageable at compile-time. Furthermore, it would be too costly to estimate the condition number at runtime for mixed-precision routines since it requires the factored form of the matrix (the LAPACK function gecon estimates the reciprocal condition number but requires the LU form bringing the cost to θ(n 3 ) for an n * n matrix). However, since current dense linear algebra libraries propose mixed precision routines, it needs to be part of the configuration space.

The last key domain of our solver is the dispatch between different architectures. As explained in Section , the architectural features of a GPU result in a very different language compared to a CPU. The solution we used to solve this abstraction problem is to provide through the use of a DSEL (Section 1.2) a common syntax between CPU and GPU routines. Using architecture aware binding, we can then freely choose between N T 2 and LAPACK/MAGMA to dispatch on the different back-ends in an extensible way. It is now possible to define a grammar that encapsulates these ideas into a configuration space (see Section 1.1). Most of the parameters we can access are defined by the user and therefore configurable at the API level. In MATLAB, the linsolve routine does not take into account the data type, and the matrix type needs to be defined in a parameter structure containing the different matrix properties recognized (lower/upper triangular, upper Hessenberg, symmetric, positive definite, rectangular). While creating a matrix in N T 2 , the user has the possibility to define the matrix and data type which are optimized as meta-data properties of the matrix, using the following instruction: nt2::table<double,nt2::symmetric_> a;

When calling linsolve, he will then have the possibility to give additional information on the conditioning of the matrix either as a parameter of the system:

x = nt2::linsolve(a,b,nt2::ill_conditioned_); or of the matrix: It is also possible to ask for complementary information as output like the reciprocal condition number returned by LAPACK :

RR n°8615

Once this is done, linsolve will be able to parse the configuration space by reading out the nested domain-specific features while assigning default values to the unspecified ones.

Memory management for hybrid computation

When using GPU-based systems, we need ensuring data consistency between the different physical memories. In this section, we discuss how these techniques are used jointly with linsolve. We can discern the two most common approaches to CPU and GPU containers. The first one is to statically define the locality of the container which is done in the Thrust library [START_REF] Bell | Thrust: A productivity-oriented library for CUDA[END_REF], while the second uses a dynamic approach like in SkePU [START_REF] Enmyren | SkePU: a multi-backend skeleton programming library for multi-GPU systems[END_REF].

The memory management mechanism in a dynamic approach allows to change the locality of a container and reallocate the data. The container then needs to manage the memory and ensure consistency between data and locality. In this situation, it is not possible to statically define the locality of a container and therefore doing a dispatch using the locality in our generation phase. Therefore, our approach consists of adding an architectural tag similarly to the matrix type tag on our container (default locality is CPU). The purpose of this method is to enable the user to write programs using GPU to GPU functions in a transparent way. It is then possible to ensure the transitions from CPU to GPU memory by using explicitly the tag. This does not prevent the decision-making process of the solver when no locality tag is given by the user. The solver can generate a GPU code performing data transfers from CPU to GPU and the reverse. The generation process will choose the architecture based on a combination of factor being mainly the matrix size and the algorithm. The GPU tag can also hold complementary informations passed as template parameters of the tag.

The definition of container locality being static, it is easier to define a data efficient memory management unit. Let's use the following scenario as an example :

x = nt2::linsolve(a,b);

From here, we can apply different strategies depending on the locality of x, a and b. In a situation where all three containers are on GPU/CPU memory there will be no locality problem as various data are located on the same device. However, the scenario where x is on the GPU (respectively CPU) while a and b are on the CPU (resp. GPU) will generate a conflict. The rules to solve locality conflicts are static and do not depend on a runtime. Therefore, the priority will be given to the locality of the result x to ensure consistency between the data locality and container locality.

Experiments were carried out on a system using 2 sockets of Intel Xeon E5645 2.40GHz and a Tesla C2075. We consider single precision random square matrices of size 2000, 10000 and 20000 and we solve a system of linear equations Ax = b using the LU factorization. The light grey bars in Figure 2 correspond to the following call made in N T 2 through linsolve that can run either on CPU or GPU. The dark grey bars correspond to C++ calls to either the LAPACK function sgesv or the MAGMA function magma_sgesv. These results show that automatically generated routines do not exhibit any overhead compared to direct calls to LAPACK or MAGMA. Note that the performance of all others generated routines also does not incur any overhead.

Application to linear least squares

In this section we illustrate how the generative programming method described in Section 1 can be used to generate automatically new implementations of algorithms that do not exist in current libraries and achieve satisfactory performance compared with existing solvers.

Solving least squares by semi-normal equations

We consider the overdetermined full rank linear least squares (LLS) problem

min x∈R n Ax -b 2 , with A ∈ R m×n , m ≥ n and b ∈ R m .
The most classical methods for solving linear least squares problems are based on the QR factorization or the normal equations. The latter method is twice cheaper (mn 2 vs 2mn 2 operations) but the condition number is then proportional to cond(A) 2 [13, p. 49]). However if A can be saved, we can also use the semi-normal equations (SNE) method where we solve the system

R T Rx = A T b,
where R is the triangular factor from the QR factorization of A (this is a straightforward reformulation of the normal equations). It is shown in [START_REF] Björck | Stability analysis of the method of semi-normal equations for least squares problems[END_REF] that, similarly to the normal equations method, the forward error bound involves a factor cond(A) 2 , even if we use a R-factor that is of better quality than the Cholesky factor because it has been computed via a backward stable algorithm. However, as explained in [13, p. 126 and p. 250], the accuracy of the SNE method can be improved by using the corrected semi-normal equations method (CSNE) that consists in adding one step of fixed precision iterative refinement to the SNE as follows:

1. Let x solve R T Rx = A T b 2. Compute r = b -Ax 3. Solve R T Rw = A T r 4. Corrected solution y = x + w
It is shown in [31, p. 392] that, if cond(A) 2 u ≤ 1 (u being the unit roundoff), then the forward error bound for the CSNE method is similar to that of a backward stable method (and even smaller when r = Axb is small). In that case, the CSNE method is more satisfactory than the SNE method but this is not true for all A. In the following we propose to use the CSNE method to solve LLS in mixed precision.

Mixed-Precision Corrected Semi-Normal Equation

The efficiency of mixed precision algorithms has been proved on linear systems based on the LU factorization with results that can reach up to 90% [START_REF] Baboulin | Accelerating scientific computations with mixed precision algorithms[END_REF] of floating point computational rate in the lowest precision on current architectures. The method to solve mixed precision CSNE (or MCSNE) consists of first solving the factorization in single precision (ε s ) (if the matrix is not too ill-conditioned) with the computational cost of θ(mn 2 ) and then refine the solution in double precision (ε d ) where operations cost θ(n 2 ). Iterative refinement [START_REF] Demmel | Error bounds from extra-precise iterative refinement[END_REF] is a method that produces a correction to the computed solution by iterating on it. Each k th iteration in this process consists of computing the residual r k = b -Ax k-1 , solving the new system Ad k = r k , and adding the correction x k+1 = x k +d k . Mixed precision iterative refinement will work as long as the condition number of the least squares problem [START_REF] Baboulin | Computing the conditioning of the components of a linear least-squares solution[END_REF] is smaller than the inverse of the lower precision used (i.e. here 10 8 ).

Algorithm 2.1 Mixed precision CSNE Compute

A = QR (ε s ) Solve R T x = A T b (ε s ) Solve Rx 0 = x (ε s ) do k = 1,2,... r k = b -Ax k-1 (ε d ) Solve R T x = r k (ε s ) Solve Rd k = x (ε s ) x k = x k-1 + d k (ε d ) check convergence
The purpose of having an automatic generation is to be able to keep the expressiveness of the algorithmic version of a code while achieving high performance that can topple state of the art libraries. The MCSNE routine has been generated using the following NT2 instructions.

The first step of Algorithm 2.1 in N T 2 is implemented in line 8 of Listing 1, while the second and third steps are performed by two calls to linsolve in lines 11 and 12. Note that the code is similar in terms of syntax and number of instructions to what would be written in Matlab.

Inria

Listing 1: NT2 implementation for MCSNE Once the solver for MCSNE has been coded using N T 2 , it becomes possible to add it to linsolve as a dispatch case of mixed precision solver for overdetermined linear systems. This would result in the following call :

1 table < double > mcsne ( table < double > const & A , table < double > const & B )
x = nt2::linsolve(a,b,nt2::mixed_precision_);

2.3.3

Performance results for MCSNE Benchmarks were carried out using 2 sockets of Intel Xeon E5645 2.40GHz (peak Gflop/s is 230) and a Tesla C2075 (peak Gflop/s is 1030.4). We used Intel MKL [START_REF]Intel. Math Kernel Library (MKL)[END_REF] version 10.2.3, MAGMA 1.3 with CUDA 5.0 [START_REF]NVIDIA CUDA C Programming Guide[END_REF] and gcc 4.8 [START_REF] Gough | An Introduction to GCC[END_REF]. The random test problems were generated using the method described in [START_REF] Paige | LSQR: An algorithm for sparse linear equations and sparse least squares[END_REF]. Performance results include data transfers between CPU and GPU and data are stored on the GPU memory.

In Figure 3 we compare the performance on the CPU for MCSNE with the LAPACK routine xgels that solves the LLS problem with a QR factorization without column pivoting. The results show that performance of MCSNE is only 10% less that the rate of sgels. Note that this represents around 75% of the peak performance of a matrix-matrix multiply in single precision (routine sgemm). We use random matrices and the iterative refinement converged in less than 4 iterations.

On the GPU, the performance of MCSNE in N T 2 is depicted in Figure 4. It also approaches 90% of the performance of magma_sgels on GPU while being near twice faster than the routine

Inria 3 Conclusion

Combining the large number of algorithms available in numerical libraries and architectural requirements into a generic solver for dense linear systems is a complex task. We showed that generative programming is a valid software development approach for addressing these issues while maintaining a high level of performance. Our contribution furthers the work in active libraries by providing a viable way to render our software architecture-aware. Performance results illustrate that for both existing routines like those in linsolve and new ones such as MCSNE, the delivered performance is close to what state of the art libraries achieve.

The other interesting result is that software like N T 2 can quickly prototype new algorithms while providing support for various architectures. With N T 2 , we reach a good combination of high-level codes for linear algebra problems that gives good speedups and offers the users enough expressiveness to describe the problem in the most efficient way.

Future work includes support for more architectures like Intel Xeon Phi, with work on new algorithms that provide good performances while not being available in numerical libraries like randomized algorithms [START_REF] Baboulin | A Parallel Tiled Solver for Dense Symmetric Indefinite Systems on Multicore Architectures[END_REF][START_REF] Baboulin | Accelerating linear system solutions using randomization techniques[END_REF] or communication-avoiding algorithms [START_REF] Baboulin | A class of communication-avoiding algorithms for solving general dense linear systems on CPU/GPU parallel machines[END_REF] for dense linear systems. Moving to sparse problems is also a possibility where libraries like Cups [START_REF] Bell | Cusp: Generic parallel algorithms for sparse matrix and graph computations[END_REF] or VexCL [START_REF] Demidov | VexCL: Vector expression template library for OpenCL[END_REF] provide an interesting approach. Raising the level of expressiveness stays a major concern while trying to add content in N T 2 .

Figure 1 :

 1 Figure 1: Overview of the AA-DEMRAL process

x

  = nt2::linsolve(nt2::ill_conditioned_(a),b);

  nt2::tie(x,r) = nt2::linsolve(a,b);

  nt2::table<double,nt2::gpu_> a;

xFigure 2 :

 2 Figure 2: Performance comparaison between LAPACK/MAGMA routines and generated codes via NT2 for general dense linear system solution

2 { 3

 23 double anrm = lange (A , 'I ') ; 4 double cte = anrm * Eps < double >() * nt2 :: sqrt ( width ( a ) ) ;

5 6

 5 table < float > SA = cast < float >( A ) ;

Figure 3 :

 3 Figure 3: Performance results of Generated code on CPU of gels (QR solver) and mcsne

Figure 4 :

 4 Figure 4: Performance results of Generated code on GPU of gels (QR solver) and mcsne

Table 1 :

 1 Configuration space parameters levels

	0-Matrix type	general | band | diagonal | symmetric | positive definite
	1-Data type	float | double | single/double complex
	2-Precision	fixed | mixed-precision
	3-Conditioning	no information | ill-conditioned
	4-Storage scheme	general | packed
	5-Architecture	CPU | GPU

RR n°8615

rue Honoré d'Estienne d'Orves Bâtiment Alan Turing Campus de l'École Polytechnique 91120 Palaiseau Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399


Damien Nouvel
email: damien.nouvel@limsi.fr

Jean-Yves Antoine
email: jean-yves.antoine@univ-tours.fr

Adapting Data Mining for German Named Entity Recognition

HAL is

Introduction

In the 90's and until now, several symbolic systems have been designed that make intensive use of regular expressions formalism to describe Named Entities (NEs). Those systems combine external and internal evidences [START_REF] David | Internal and external evidence in the identification and semantic categorization of proper names[END_REF], as patterns describing contextual clues and lists of names per NE category. Those systems achieve high accuracy for NE Recognition (NER), but, because they depend on the handcrafted definition of lexical ressources and detection rules, their coverage remains an issue. This work is licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0).

Page numbers and proceedings footer are added by the organizers.

License details:

http://creativecommons.org/licenses/by/4.0/

To address NER, machine learning usually states the problem as categorizing words that belong to a NE, taking into account various clues (features) in a model that is automatically parametrized by leveraging statistics from a training corpus. Among these methods, some only focus on the current word under examination (maximum entropy, SVM) [START_REF] Borthwick | Exploiting diverse knowledge sources via maximum entropy in NER[END_REF], while others also evaluate stochastic dependencies (HMM, CRF) [START_REF] Mccallum | Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons[END_REF][START_REF] Ratinov | Design challenges and misconceptions in NER[END_REF]. Most of the time, those approaches output the most probable sequence of labels for a given sentence. This is generally known as the "labeling problem", applied to NER.

Many approaches rely on pre-processing steps that provide additional information about data, often Part-Of-speech (POS) tagging and proper names lists, to determine how to automatically tag texts [START_REF] Ratinov | Design challenges and misconceptions in NER[END_REF]. Recently, data mining techniques [START_REF] Freitag | Boosted wrapper induction[END_REF] have been experimented, but we are not aware of work that goes beyond the step of extracting patterns for NER.

Our system, mXS1 [START_REF] Nouvel | Pattern mining for named entity recognition[END_REF], automatically mines patterns and use them as features for machine learning. It focuses on boundaries of NEs, as beginning or ending tags to be inserted. Internally, the system considers each tag delimiting a NE as an item of interest and extracts detection rules (which may be used as feature but also may be read by humans). To the best of our knowledge, this way of combining symbolic and machine learning approaches is original in the framework of NER. It obtained satisfying results during the ANR ETAPE of the ANR French research agency evaluation campaign, ranked 3rd or 2nd among 10 particpants. This paper presents our adaptation of mXS to German.

2 Coding, Preprocessings and Lexicon

Coding NEs beyond BIO Format

As previously mentioned, most of the approaches for doing NER rely on labelling tokens of a text. This leads to representations as illustrated in Figure 1 where each token is assigned a dedicated class. Machine learning approaches are known to be efficient to solve this kind of problem. Our main concern about this representation is that it is now mandatory to classify all tokens within a named entity, even underspecific tokens such as für/I-ORG.

As a result, mXS uses internally a different coding to represent NE tokens: only beginning and ending of NEs are explicitly mentionned, in a XML-like fashion, e.g. <PER> Cartier </PER>. Our goal is then to discover the correct positions where NE tags have to be inserted, as showed in Figure 2. This approach doesn't prevent to use machine learning techniques, avoids the artificial split of NE classes (e.g. B-XXX and I-XXX) and can be used in combination with sequential data mining techniques.

Morphosyntax

Initial preprocessings and linguistic analysis are done using TreeTagger [START_REF] Schmid | Probabilistic POS tagging using decision trees[END_REF], that conjointly tokenizes, lemmatizes and assigns POS to each token. Our first experiments demonstrate that this software gives sufficient clues, especially by identifying proper names, to ground our system. We use this information, as gradual generalizations for building representation of texts. Consider for instance this sentence from the Ger-mEval training corpus:

Der <LOC> Queen <PER> Sirikit </PER> Park </LOC> ist ein Botanischer Garten
Here, Botanischer is progressively generalized as botanisch (lemma) then ADJA (adjective POS). This incremental generalization is described by ADJA/botanisch/Botanischer where the / symbol is used as a specialization operator.

Our text mining process is able to consider for any token all possible generalizations over this hierarchy2 . The sentence is now represented as: The French version of mXS includes many dedicated adaptations to improve recognition of specific linguistic expressions. The German version of mXS that participates to GermEval does not include such useful improvements.

Lexicon

In the experiments presented in Section 4, the baseline system does not use any lexicon, and thus only relies on morphosyntax analysis. To improve performance, we also considered three proper noun lexicons as additional resources (Table 1): ST is extracted from FreeBase ; IP and IW are gross-grained and fine-grained versions of a lexicon extracted from Wikipedia [START_REF] Savary | Populating a multilingual ontology of proper names from open sources[END_REF]. They implement usual classes for NER as antrhroponyms, toponyms, first names, last names, organizations, etc. Those lexicons provide another possible level of generalization. As it is more related to semantic properties of tokens, this information will be considered as the top level to generalize tokens. mXS also supports multiword expressions and ambiguity at any level: semantic categories This also illustrates how hierarchical sequential mining can easily fit special needs (e.g. language or task adaptation of preprocessings).

Sequential Data Mining to extract Patterns as Features

Mining techniques are applied on the information provided by preprocessings. The data miner within mXS proceeds in a supervised level-wise fashion to extract generalized sequential patterns [START_REF] Agrawal | Mining sequential patterns[END_REF] that are correlated to NE tags. To limit complexity, the search is limited by criterions such as minimum support (frequency), minimum confidence (regarding the presence of NE tags) and redundancy within patterns. Extracted patterns are supposed to be valu-able clues for detecting NE boundaries. Due to a lack of space, the mining process will not be detailed in this paper, further information can be found in [START_REF] Nouvel | Pattern mining for named entity recognition[END_REF]. mXS implements hierarchical mining: patterns are sequences of diversely generalized natural language tokens and enriched data and NE tags. The extracted patterns are used as features by a maxent classifier, provided by the scikit-learn toolkit [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] that estimates, at any position of a sentence, the probability to insert tags given the patterns. using a Viterbi algorithm, the decoding step combines individual probabilities to select annotation that maximizes likelihood. The advantage of this approach, besides avoiding the artificial split of B-and I-of BIO format, is that it can insert multiple tags at a given position, enabling recursive annotation as required by the GermEval campaign.

Experiments and Results

We assess the usefulness of the extracted patterns for NER, by selecting them at different thresholds of support and confidence. Table 2 shows that best score are obtained with low support (5) and medium confidence (10%). Around 17000 patterns are extracted with these parameters. The comparison with situations where pattern features are not used ("inf") shows that patterns always lead to better performances, reaching a maximum increase of +2.5% of the overall f-score. We investigated the benefits of using three lexicons, separately or jointly. As displayed in Table 3, using them always lead to significant improvement. Unfortunately, combining them degrades performances (we assume that those resources are not as complementary as expected). We built our final system using only the ST lexicon, which provided the best score (63.16), each run being a combination of frequency and confidence parameters. Official results in Table 4 are close to what has been obtained on the development dataset and unfortunately confirmed our very high precision but unsufficient recall: our system is ranked 7th out of 11. We suspect overfitting and conducted additional experiments for fine-tuning maxent regularization parameter. For the moment, this leads to a better f-score (64.19) over the official test data, without clarifying the question of the strong difference between precision (80.76) and recall (53.26).

Conclusion

This paper shows how to use data mining in an original way (separate detection of NE boundaries instead of BIO tagging) to implement a rather efficient multilevel named entity recognition system. Adapting mXS from French to German was quite easy, thanks to the availability of resources. Obviously, this version of mXS lacks linguistic adaptations specific to German, what prevent us to reach an optimal level of performance. Nevertheless, we reached our main goal, which was to assess the reliability of our original approach on another language using similar preprocessings steps and our generic pattern mining implementation.

  ART/die/Der <LOC> NN/Queen/Queen <PER> NN/Sirikit/Sirikit </PER> NN/Park/Park </LOC> VAFIN/sein/ist ART/eine/ein ADJA/botanisch/Botanischer NN/Garten/Garten As data mining process is aimed at extracting generic patterns, we exclude surface variations (but keep their lemmas) and lexicalization of proper names (to avoid overfitting) when preprocessing training corpus: ART/die <LOC> NN/Queen <PER> NN/Sirikit </PER> NN/Park </LOC> VAFIN/sein ART/eine ADJA/botanisch NN/Garten

Figure 2 :

 2 Figure 1: Annotation as a labelling task

  Here are some examples of extracted patterns: <PER> NE ART NN/SUFF:ung <LOC> CITY/NN APPR/in REGION/NE </LOC> <PER> NE NN APPR CITY </LOC>

Table 1 :

 1 System lexicons number of classes and entries

	Lexicon Categories Entries
	ST	5	497 093
	IP	7	33 167
	IW	118	33 167

Table 2 :

 2 Score without lexicon

	supp	conf%	rules	fscore% prec%	rec%
	5	5	21 620	59.50	76.44	48.71
	5	10	17 268	59.91	76.76	49.13
	5	50	7 512	58.87	76.87	47.70
	10	5	9 505	59.62	76.82	48.71
	10	10	7 460	59.55	76.68	48.67
	10	50	3 108	58.53	76.80	47.28
	50	5	1 283	59.41	77.37	48.22
	50	10	972	59.35	77.42	48.11
	50	50	359	58.35	77.03	46.96
	inf	inf	0	57.41	76.01	46.12

Table 3 :

 3 Score depending on lexicon

Table 4 :

 4 Final scores

	supp conf% fscore%	prec% rec%
	5	10	61.63	79.05	50.5
	10	50	62.29	80.46	50.81
	50	50	62.39	80.62	50.89

https://github.com/eldams/mXS

Besides, as it is not a column format, the number of possible generalizations may vary from one token to another

Acknowledgments

Thanks to people from LIMSI-CNRS and ANR ETAPE for endorsing our work on NER.


Judith Muzerelle
email: judith.muzerelle@etu.univ-tours.fr

Anaïs Lefeuvre
email: anais.lefeuvre@univ-tours.fr

Emmanuel Schang
email: emmanuel.schang@univ-orleans.fr

Jean-Yves Antoine
email: yves.antoine@univ-tours.fr

Aurore Pelletier
email: aurore.pelletier-2@etu.univ-tours.fr

Denis Maurel
email: denis.maurel@univ-tours.fr

Iris Eshkol
email: iris.eshkol@univ-orleans.fr

Jeanne Villaneau
email: jeanne.villaneau@univ-ubs.fr

ANCOR_Centre, a Large Free Spoken French Coreference Corpus: Description of the Resource and Reliability Measures

Keywords: coreference, French spoken language, free annotated corpus

This article presents ANCOR_Centre, a French coreference corpus, available under the Creative Commons Licence. With a size of around 500,000 words, the corpus is large enough to serve the needs of data-driven approaches in NLP and represents one of the largest coreference resources currently available. The corpus focuses exclusively on spoken language, it aims at representing a certain variety of spoken genders. ANCOR_Centre includes anaphora as well as coreference relations which involve nominal and pronominal mentions. The paper describes into details the annotation scheme and the reliability measures computed on the resource.

Introduction

Information Retrieval and documents indexing should certainly be accounted for one of the most promising application areas of Natural Language Processing (NLP). These tasks require a large resort to NLP treatments, among which the resolution of coreference and anaphoric relations plays a crucial role. It allows indeed various lexical mentions that are present in texts to be clustered with the single discourse entity they refer to. Several evaluation campaigns (MUC, ACE, SemEval) have demonstrated the existence of operative solutions to coreference resolution, which is nowadays extended to the question of entity linking [START_REF] Rao | Entity Linking: Finding Extracted Entities in a Knoledge Base[END_REF]. However, the lack of large annotated corpora still restricts the achievement of efficient resolution systems. In this paper, we present ANCOR_Centre (ANCOR as an abbreviated form), the first French corpus which is freely available and is large enough to serve the needs of data-driven approaches in NLP. With a total of 488,000 lexical units, ANCOR is among the largest coreference corpora available at present 1 (Table 1). 1 The DEDE corpus [START_REF] Gardent | Création d'un corpus annoté de traitement des descriptions définies[END_REF], which was until now the largest coreference corpus freely available on French, focuses only on definite description. It sizes restricts to 48,000 words.

Table1 -Largest manually annotated coreference corpora (more than 325,000 words) To the best of our knowledge, ANCOR represents the largest corpus that concerns specifically spoken language. ANCOR follows a rich annotation scheme to fulfil the needs of NLP machine learning as well as linguistic investigations. This paper presents into details this resource. First, we present the speech corpora on which the annotation was conducted. We then describe our annotation procedure.

Section 3 gives some distributional information on the data that are present in the corpus. The next section addresses the question of the estimation of data reliability on coreference annotation and gives the results obtained on the ANCOR corpus. In conclusion, we discuss the availability of the corpus.

Source spoken corpora

The ANCOR corpus focuses exclusively on spoken French. Although it cannot be considered as a balanced corpus, it aims at representing a certain variety of spoken types. It consists of four different spoken corpora that were already transcribed during previous research projects (Table 2). Two of them have been extracted from the ESLO corpus, which collects sociolinguistic interviews with a restricted interactivity (Schang et al., 2012). On the opposite, OTG and Accueil_UBS concern highly interactive Human-Human dialogues [START_REF] Nicolas | Towards a large corpus of spoken dialogue in French that will be freely available: the "Parole Publique" project and its first realisations[END_REF]. These last two corpora differ by the media of interaction: direct conversation or phone call. All of these corpora are freely distributed under a Creative Commons license. Conversational speech only represents 7% of the total corpus because of the scarcity of such free resources in French.

Corpus

Annotation procedure and annotation scheme

Although we have conducted some experiments on the automatic detection of nominal groups and named entities on the ESLO corpus, we finally decided to fully annotate by hand these corpora on the GLOZZ platform [START_REF] Mathet | The Glozz Platform: A Corpus Annotation and Mining Tool[END_REF]. Glozz produces a stand-off XML file structured after a DTD that was specifically designed for ANCOR. This stand-off annotation allows a multilayer work on the data and potential enrichments through time.

In order to restrict the cognitive load of the coders and to favour intra-coder coherence, the annotation process was split into four successive phases: 1. Mention borders marking (coders: Master or PhD students in linguistics) 2. Adjudication of phase 1 by a super-annotator 3. Marking of coreference or anaphora relations (same coders) 4. Adjudication of phase 3 by a super-annotator The scope of annotation covers all noun phrases including pronouns but restricts strictly to them. For instance, a noun phrase like le lendemain (the day after) is considered a legitimate mention, while t h e a d v e r b i a l demain (tomorrow) will be ignored. This precise delimitation favours the annotation reliability since it provides coders with objective rules to characterize what should be considered or not during the annotation. As a result, the annotation scheme discards coreferences involving verbal or propositional mentions. These relations contain abstract anaphoras, which are beyond the aims of our project and would have required a very specific annotation scheme [START_REF] Dipper | Towards a standard for annotating abstract anaphora[END_REF]. We follow a detailed annotation scheme in order to provide useful data for deep linguistic studies and machine learning. Every nominal group is thus associated with the following features:

• Gender, Number, Part of Speech, •
Definition (indefinite, definite, demonstrative or expletive form),

• PP: inclusion or not in a prepositional phrase, • NE: Named Entity Type, as defined in the Ester2 coding scheme [START_REF] Galliano | The ESTER 2 Evaluation Campaign for the Rich Transcription of French Radio Broadcast[END_REF],

• NEW: discourse new mention vs. subsequent mention.

There is no real consensus on the way coreferent mentions should be related in the annotation. In the ANCOR project, we asked coders to link always subsequent mentions with the first mention of the corresponding entity (discourse new). Alternative coding schemes have however their own relevancy. This is why the corpus is distributed with three alternative representations:

• Discourse-new coding scheme: relations from subsequent to first mentions, • Coreference chain coding scheme: relations from one coreferent mention to the next one,

• Cluster coding scheme: sets of coreferent mentions.  Pronominal anaphora: the subsequent coreferent mention is a pronoun.

• Bridging anaphora: non coreference, but the subsequent mention depends on its antecedent for its referential interpretation (meronomy for i n s t a n c e : the schooner … its bowsprit).

• Bridging pronominal anaphora: specific bridging anaphora where the subsequent mention is a pronoun. We distinguished this type in order to emphasize metonymic situations (Avoid the Grand Central Hotel … they are unpleasant) which occur frequently in conversational speech.

This annotation scheme is quite similar to previous works on written language [START_REF] Van Deemter | On Coreferring: Coreference in MUC and related annotation schemes[END_REF][START_REF] Vieira | Multilingual corpora annotation for processing definite descriptions[END_REF]. Since ANCOR represents the first large coreference corpus available for French, it is important that the resource should concern researchers that are working on written documents too. Unlike (Gardent and Manuélian, 2005), we didn't distinguish between several sub-categories of bridging anaphora. We consider such a refined taxonomy to exceed the present needs of NLP while introducing a higher subjectivity in the annotation process. For the same reasons, we didn't consider the relation of near-identity proposed in [START_REF] Recasens Potau | Coreference: Theory, Annotation, Re s o l u t i o n a n d Ev a l u a t i o n . Ph D Th e s i s[END_REF]. Recent experiments have shown that near-identity leads to a rather low inter-coders agreement [START_REF] Ogrodniczuk | Polish coreference corpus, submitted at LTC[END_REF]. Section 5 details the data reliability measures obtained on our corpus.

Corpus description: distributional data

Although ANCOR clusters valuable information for deep linguistic analyses, this section gives only a general outline of the annotated data, to show roughly what should be found in the resource 2 . 6 presents the distribution of coreference/anaphora relations. Once again, strong regularities between the sub-corpora are observed. In particular, direct coreference and pronominal anaphora are always prevalent. ANCOR clusters around 20,000 occurrences of these two relations.

Corpus

Nb. of mentions

Nb. of relations

Mention

Annotation reliability estimation

The estimation of data reliability is still an open issue on coreference annotation. Indeed, the potential discrepancies between coders lead frequently to alignment mismatches that prevent the direct application of standard reliability measures [START_REF] Passoneau | Computing reliability for Co-Reference Annotation[END_REF][START_REF] Artstein | Inter-Coder agreement for Computational Linguistics[END_REF]Matthet & Widlöcher, 2011). We propose to overcome this problem by assessing separately the reliability of 1) the delimitation of the relations and 2) the annotation of their types. More precisely, three experiments have been conducted: 1. Firstly, we've asked 10 experts to delimitate the relations on an extract of ANCOR. These coders were previously trained on the annotation guide. We computed, on the b a s i s o f a l l p o t e n t i a l p a i r o f mentions, standard agreement measures: κ [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF], α [START_REF] Krippendorff | Content Analysis: an Introduction to its Methodology[END_REF] and π [START_REF] Scott | Reliability of content analysis: the case of nominal scale coding[END_REF]. This experiment aims above all at evaluating the degree of subjectivity of the task rather than the reliability of the annotated data, since the experts were not the coders of the corpus. 2. On the contrary, the second experiment concerned the annotators and the supervisor of the corpus. We asked them to re-annotate an extract of the corpus. Then we computed intra-coders agreement through a comparison to what they really performed on the actual corpus. This experiment aims at providing an estimation of the coherence of data. 3. Finally, we asked our 10 first experts to attribute one type to a selection of relations that were previously delimited in the ANCOR corpus. We then computed agreement measures on the resulting type annotation. We observe on table 7 very close results with the three considered reliability metrics (no difference before the 4 th decimal). This is not surprising since we consider a binary distance between classes [START_REF] Antoine | Weighted Krippendorff's alpha is a more reliable metrics for multi-c o d e r s o r d i n a l a n n o t a t i o n s : experimental studies on emotion, opinion and coreference annotation[END_REF]. The intercoder agreement on delimitation is rather low (0.45). One should however note that this measure should be biased by our discourse-new coding scheme. Indeed, if a disagreement concerns only the first mention of a coreference chain, all the subsequent relations will unjustifiably penalize the reliability estimation. Further measures to come with the chain coding scheme will give soon an estimation of this potential bias. Anyway, this rather low agreement suggests that the delimitation task is highly prone to subjectivity, even when coders are trained.

In particular, a detailed analysis of confusion matrices shows that most discrepancies occur b e t w e e n t h e delimitation of a bridging anaphora and the decision to not annotate a relation. Besides, this kind of disagreement appears to be related to personal idiosyncrasies. On the contrary, the results become very satisfactory when you consider intra-coders agreement (0.91). This means that our coders followed a very coherent strategy of annotation, under the control of the supervisor. This coherence is, in our opinion, an essential guarantee of reliability.

Lastly we observed very good agreements on the categorisation task (0.80), which reinforce our decision not to consider near-identity or detailed bridging types.

Conclusion: corpus avalaibility

The inter-coder agreement observed on the ANCOR corpus suggests that it represents a reliable annotated resource. With a size approaching 500,000 words, ANCOR has no equivalent for French and represents one of the largest coreference corpora on spontaneous speech. It is freely distributed under a CC-BY-NC-SA Creative Commons licence. The version 1.0 of the resource, which only handles a discourse-new coding scheme, can be downloaded from the webpage of the ANCOR project (http://tln.li.univ-tours.fr/Tln_Corpus_Ancor.html). The final version of ANCOR (three coding scheme) will be available on the Speech and Language Data Repository (http://crdo.up.univ-aix.fr) on mid-2014.

Acknowledgments

The development of the ANCOR_Centre corpus was conducted in the framework of the CO2 project (joint founding of Orléans U. and François Rabelais Tours U.) and mainly of the ANCOR project, founded by the Centre Region.

  Marked relations are additionally classified among five different types of coreference or anaphora:  Direct coreference: coreferent mentions are NP with the same lexical head.  Indirect coreference: coreferent mentions are NP with distinct lexical head (schooner… vessel).

Parole Speech type Words number Duration

	ESLO_	Interview	417,000	25 hours
	ANCOR
	ESLO_	Interview	35,000	2.5 hours
	CO2
	OTG	Task-oriented	26,000	2 hours
		conversational
		speech
	Accueil_UBS Phone	10,000	1 hour
		conversational
		speech

Table 2 -

 2 Source corpora of ANCOR_Centre

Table 3 -

 3 Content of the different annotated sub-corpora

	Table 3 details the distribution of the mentions and
	relations among the sub-corpora. With more than 50,000
	relations and 100,000 mentions, ANCOR should fulfil the
	needs of representative linguistic studies and machine
	learning.
	Table 4 shows that the repartition of nominal and
	pronominal entities presents a noticeable stability among
	the four corpora and leads to a very balanced overall
	distribution (51.2% vs. 48.8%).

2 People interested in a qualitative approach of the resource can consider (Lefeuvre e t a l . , 2 0 1 4 ) f o r a n i l l u s t r a t i o n o f comprehensive linguistic studies that should be conducted on the resource.

Table 4

 4

		-Mentions: distributional information
	This observation results certainly from a general
	behaviour of spoken French: pronominal anaphora is
	indeed an easy way for French speakers to avoid
	systematic repetitions in a coreference chain. On the
	contrary, the use of Named Entities (NE) 3 is strongly
	related to the discourse domain. This explains that we
	observe significant variations of their relative frequency
	from one corpus to another 4 . ANCOR clusters around
	45000 annotated Named Entities (table 5) Therefore, it
	should stand for a valuable resource for named entities
	recognition applications.
	PERS	LOC	ORG AMOUNT TIME	PROD
	26,722	3,815	1,746	1,496	1,390	1,185

Table 5 -

 5 Most frequent named entities in ANCOR (number of occurrences -Ester2 Types)

	Corpus	ESLO	ESLO	OTG	Accueil	Total
		_	_		_UBS
		Ancor	CO2
	Direct	41,1%	35,2%	39,7%	40,5%	38,2%
	Indirect	7,3%	11,2%	6,1%	7,5%	6,7%
	Pronoun	43,9%	38,2%	46,4%	46,0%	41,1%
	anaphora
	Bridging	10,4%	14,4%	13,5%	11,0%	9,8%
	anaphora
	Pronoun	0,9%	1,0%	3,3%	0,6%	1,0%
	&
	Bridging

Table 6 -

 6 Coreference / anaphora: distributional information Finally, Table

Table 7 -

 7 Agreement measures for the ANCOR corpus

Following the ESTER 2 Evaluation Campaign[START_REF] Galliano | The ESTER 2 Evaluation Campaign for the Rich Transcription of French Radio Broadcast[END_REF], we have used 7 categories: PERS stands for person, LOC for location, ORG for organization, AMOUNT for amount, TIME for time, PROD for product, in addition to FUNCT for functions which represents 0,5 % of the NE in the corpus.

For instance, locations (LOC) represent only 8,1% of the observed named entities in the Accueil_UBS corpus, while this ratio increases up to 19,4% on the OTG one: tourists information involves indeed frequent references to locations.


Miloud Kidiyo Kpalma
email: kidiyo.kpalma@insa-rennes.fr

Chikr El-Mezouar
email: chikrelmezouar@univ-sba.dz

Nasreddine Taleb
email: ne_taleb@univ-sba.dz

M Chikr El-Mezouar

Miloud Chikr

El Mezouar

Recent Trends in Satellite Image Pan-sharpening techniques

Keywords: Panchromatic images, multispectral images, pan-sharpening, NSCT, IHS, quality assessment, vegetation detection …. I

Aperture Radar (SAR) images and Light Detection And Ranging (LiDAR) images.

Radio Detection and Ranging (Radar) is an objectdetection system developed in the 1950s that uses radio waves to determine the range, altitude, direction, or speed of objects. Synthetic Aperture Radar (SAR) is a technique for obtaining high-resolution images of the earth's surface. In SAR imaging, microwave pulses are transmitted by an antenna towards the earth surface. Then the SAR system detects the reflected microwave energy and forms an image using the time delay of the backscattered signals. Over the area of the surface being observed, these images represent the backscattered microwave energy, the characteristics of which depend on the properties of the surface, such as its slope, roughness, humidity, textural inhomogeneities and dielectric constant.

LiDAR (Light Detection And Ranging1 or a portmanteau derived from Light and raDAR) systems are based on the light pulses to observe the earth. By analyzing the time elapsed between the pulsed light and the light reflected by a target. This gives a high-quality 3D information about surface of the target. It enables to capture the height of both the terrain and objects such as buildings, in amazingly fine resolution details: it provides a rapid and accurate terrain mapping system. The frequency range of the laser light used in LiDAR lays in the ultra-violet, visible or near infrared bands [START_REF] El-Mezouar | Image fusion in satellite remote sensing[END_REF]. Due to its capability to detect multiple echoes of the same pulse the LiDAR can see through water, canopies and trees on the ground to map surface terrain and to estimate the depth of the water body or plantation.

For the rest of the paper, we will focus on the optical images as we are only concerned by the visible spectral bands. For more details concerning the other systems, we urge the reader to refer to [START_REF] El-Mezouar | Image fusion in satellite remote sensing[END_REF].

II. OPTICAL IMAGES

Remote sensing optical images are captured over the earth surface in visible, near infrared and short-wave infrared bands. The wavelengths of the bands in an optical remote sensing system ranges from 0.30mm to 15.00mm. Depending on the number of spectral bands used, optical images are classified into four broad categories, Panchromatic (PAN), Multi-Spectral (MS), Super-Spectral (SS) and Hyper-Spectral (HS). Radiometric, spectral, textural, geometric and contextual information contained in an optical image, is very useful for its understanding.

A. Panchromatic image

A panchromatic sensor consists of a single band detector sensitive to radiation within a wide spectral range covering visible as well as IR wavelengths. If the wavelength range lies within the visible range, then the resulting image will appear as a black and white photograph taken from space. The color of the targets is not available. It is usually displayed as a grey scale image as in figure 1 that shows PAN image of Yokohama, Japan acquired October 5, 2007 by WorldView-1. Though it is also different in a way that unlike black and white photograph, PAN sensors of some satellites also cover the infrared wavelengths and in some satellites, these do not cover the blue wavelengths. The PAN images always have greater resolutions than the MS images from the same satellite. It is due to the much more energy per unit area gathered by a PAN sensor due to its wider bandwidth. Refer to figure 2

B. Multi-spectral image

The sensor of a multi-spectral imaging system is obtained from a set of multi-band sensors (less than 10 bands). Compared to panchromatic imaging system, the recorded radiation of a multispectral imaging system is within a narrow range of wavelength for each band. Both brightness and spectral (color) information of the targets being observed are available on the resulting image. Whatever, multispectral images have a low resolution they can cover the visible as well as infrared range of wavelengths. In figure 3 the responses of the PAN as well as the 8 multispectral sensors of WorldView-2 satellite are shown to illustrate the used range of the electromagnetic spectrum from the visible to the infrared part. The three visual primary color bands (red, green, blue) of MS image may be combined to produce a "true color" image. However, one can assign any MS image to any color band in an entirely arbitrary manner. In this case, the color of a target in the displayed image differs from its actual color. The resulting product is known as a "false color" image. Figure 4 illustrates a scene from the Hajj pilgrimage area in Mecca at Saudi Arabia acquired November 2, 2011, with a true color image having 0.5m resolution captured by WorldView-2. This image is a pan-sharpening result of the original multispectral bands (of 2m resolution) with the corresponding panchromatic image having 0.5m resolution.

Pan-sharpening is a process of fusing PAN and MS images to create a single high spectral and spatial resolution image.

In case of satellite that does not have the three true color bands: Red, Green and Blue, it is recommended to use a false color representation. SPOT-5 is an example, where blue band is not available. This missing band can be replaced by the NIR band and then displayed as red channel. The red and green bands are displayed as green and blue channels, respectively, generating a false color image representation (see figure 5 left picture). Moreover, by combining multispetral bands, it is possible to get a natural color appearance of the image, as it is shown at the right of figure 5. Super-spectral and Hyper-spectral images: an imaging system is considered super-spectral if it acquires more than ten spectral bands. It will be hypersepctral if the number of the captured spectral bands is more than one hundred. Bandwidths are narrower when the number of spectral bands increases. Thus, sensors will be able to capture the finer spectral characteristics of the features of the targets. These types of systems will improve understanding of global dynamics and processes occurring on the land, in the oceans, and in the lower atmosphere. It finds a potential applications in such fields as precision agriculture (e.g. monitoring the types, health, moisture level and maturity of crops), coastal management (e.g. monitoring of phytoplankton, pollution, bathymetry changes) etc. Examples of superspectral optical remote sensing systems are MODIS (36 spectral bands) and MERIS (15 programmable spectral bands), and of a hypespectral is Hyperion (242 spectral bands).

Example of MODIS image is illustrated on the left of figure 6. This natural color image acquired on April 2012 and issued from the combination of bands 1, 4 and 3, shows a dust storm over Egypt. The middle and right images of this figure, captured on October 23, 2007 using Hyperion spectrometer, show wildfire areas in Southern California. The middle data visualization represents the scene, as the human eye would see it. Using three of shortwave infrared bands gives a better view of the burning fire, as illustrated in the right side of figure 6.

A. Motivation of pan-sharpening

The quality of images, provided by earth observation satellites systems, is directly linked to their spatial and spectral resolutions [START_REF] El-Mezouar | A Pan-Sharpening Based on the Non-Subsampled Contourlet Transform: Application to Worldview-2 Imagery[END_REF]. The images produced by these sensors allow the discrimination of geometric structures according to the spatial resolution. When the sensor is able to integrate the incident radiation energy over a wide range of wavelength band, as the case of panchromatic image, it offers little information on the spectral level, but at the same time, it offers a high spatial resolution. In contrast, some sensors capture energy over a set of much narrower bands of spectrum to produce multispectral images. Then their spectral resolution is much higher, but at the cost of a low spatial resolution. Note that the terms of resolution 'high' or 'low' are relative terms to describe different resolutions between images acquired by a single observation system for PAN and MS images [START_REF] El-Mezouar | Image fusion in satellite remote sensing[END_REF].

The advantage of using MS images with a high spatial resolution has already been demonstrated in many remote sensing applications. The color information helps in the distinction of different regions of the image compared to the grayscale PAN image. Therefore, if we can use these spectral contents while taking advantage of a better spatial resolution, the identification of objects in a scene will be enriched and more accurate [START_REF] El-Mezouar | Image fusion in satellite remote sensing[END_REF].

The question is why manufacturers have not directly built sensors able to provide images with high spatial and high spectral resolutions?

In fact, these notions are contradictory from a technical point of view for a given technology; when the acquisition spectrum of a sensor is large the incident light flux on a pixel of the image is great. The pixel size is then lower and therefore the image has better spatial resolution. At the opposite, a narrow acquisition spectrum, including a restricted incident light flux on a pixel, produces a low spatial resolution.

To overcome this problem, it is possible to combine these data, PAN and MS, and produce MS imagery with a higher spatial resolution by using suitable algorithms. This concept is known as multispectral or multisensor merging, fusion or pan-sharpening [START_REF] Schowengerdt | Remote Sensing: Models and Methods for Image Processing[END_REF]. Pan-sharpening can be defined as a pixel level fusion technique used to synthesize the MS images to a higher resolution using spatial information from the PAN image.

Pan-sharpening techniques increase the spatial resolution while simultaneously preserving the spectral information in the final produced MS image, giving the best of the two worlds: high spectral resolution and high spatial resolution. Wald in [START_REF] Wald | Some terms of reference in data fusion[END_REF] defines image fusion as: "a formal framework in which are expressed means and tools for the alliance of data originating from different sources. It aims at obtaining information of greater quality; the exact definition of 'greater quality' will depend upon the application".

B. Methods and trends in pan-sharpening

A large collection of pan-sharpening techniques have been proposed in the literature. Among the huge number of these techniques, the widely used methods include intensityhue-saturation (IHS), high-pass filtering (HPF), principal component analysis (PCA), Brovey and wavelet transforms [START_REF] Dong | Survey of Multispectral Image Fusion Techniques in Remote Sensing Applications, Image Fusion and Its Applications[END_REF]. In [START_REF] Pohl | Multi-sensor image fusion in remote sensing: Concepts, methods, and applications[END_REF], a review of these classical methods is provided. The launch of the SPOT satellite in 1986 has allowed civilian community of remote sensing to use high resolution MS images. The IHS transform was used in [START_REF] Welch | Merging multiresolution SPOT HRV and landsat TM data[END_REF] to merge MS and PAN images of the SPOT satellite. Chavez et al. [START_REF] Chavez | Comparison of the spectral information content of Landsat Thematic Mapper and SPOT for three different sites in the Phoenix, Arizona region[END_REF] used the high-pass filtering (HPF) method of minimizing the spectral distortion in the resulting images. This algorithm was applied to sharpen Landsat Thematic Mapper (TM) images with SPOT PAN images. The high-frequency information of the PAN image, related to spatial information, is extracted using a high-pass filter and then injected into the MS image. The HPFs were mainly used in several pan-sharpening methods, using different tools for extracting spatial information and injecting it in MS images as: the discrete wavelet transform [START_REF] Garguet-Duport | The use of multiresolution analysis and wavelets transform for merging SPOT panchromatic and multispectral image data[END_REF], [START_REF] Zhou | A wavelet transform method to merge Landsat TM and SPOT panchromatic data[END_REF], [START_REF] Ranchin | Fusion of high spatial and spectral resolution images: The ARSIS concept and its implementation[END_REF], [START_REF] Da Yocky | Image merging and data fusion by means of the discrete twodimensional wavelet transform[END_REF], the generalized Laplacian pyramid algorithms [START_REF] Aiazzi | Context-driven fusion of high spatial and spectral resolution images based on oversampled multiresolution analysis[END_REF], [START_REF] Garzelli | Interband structure modeling for pansharpening of very high-resolution multispectral images[END_REF], or "à trous" wavelet transforms [START_REF] Nuñez | Multiresolution-based image fusion with additive wavelet decomposition[END_REF], [START_REF] Chibani | The joint use of IHS transform and redundant wavelet decomposition for multispectral and panchromatic image[END_REF]. Recently, authors in [START_REF] Al Da Cunha | The nonsubsampled contourlet transform: Theory, design, and applications[END_REF] introduced the Contourlet transform and showed that it is better than the Wavelet transform. Hence Contourlet was used in the pan-sharpening process like in [START_REF] Gonzalo | Multispectral images fusion by a joint multidirectional and multiresolution representation[END_REF] and [START_REF] Amro | Multispectral image pan-sharpening based on the contourlet transform[END_REF].

Image fusion methods have been classified in several ways. The authors in [START_REF] Pohl | Multi-sensor image fusion in remote sensing: Concepts, methods, and applications[END_REF] proposed to classify pansharpening in three categories corresponding to three different processing levels, i.e., pixel level, feature level, and the decision level. Many other authors shared this idea, however author in [START_REF] Stubberud | Data Fusion: A Conceptual Approach to Level 2 Fusion (Situational Assessment)[END_REF] emphases that the boundaries between the three levels are unclear. So in some situations, it becomes controversial to decide the level of the fusion to perform. Moreover, the author in [START_REF] Wald | Some terms of reference in data fusion[END_REF] declared that this categorization may be misleading and it may falsely imply that fusion processes do not deal simultaneously with these different levels. Hence, he proposed another categorization, where three types of methods have been identified: projection and substitution methods, relative spectral contribution methods and those linked to the ARSIS concept (from its French acronym "Amélioration de la Résolution Spatiale par Injection de Structures" which means "Enhancement of the spatial resolution by structure injections").

The authors in [START_REF] Bretschneider | Image fusion in remote sensing[END_REF] sort the methods into groups with respect to their main design idea. The following groups were defined.

-Transformation based fusion: like IHS and PCA.

-Addition and multiplication fusion: like the method (P+XS). -Filter fusion: like HPF method.

-Fusion based on inter-band relations.

-Wavelet decomposition fusion -And finally further fusion methods: like those based on statistical properties. The HPF and wavelet methods can be classified into the ARSIS group [START_REF] Ranchin | Image fusion: The ARSIS concept and some successful implementation schemes[END_REF]; however the authors in [START_REF] Tu | A new look at IHS-like image fusion methods[END_REF] claim that these methods could belong to an IHS-like image fusion method group.

Another classification given in [START_REF] Schowengerdt | Remote Sensing: Models and Methods for Image Processing[END_REF] defines three categories: spectral domain, spatial domain and scale-space techniques.

The authors in [START_REF] Wang | A comparative analysis of image fusion methods[END_REF], [START_REF] Aiazzi | A comparison between global and context-adaptive pan-sharpening of multispectral images[END_REF] proposed two generalized frameworks for methods such as IHS, PCA, HPF or AWT and provided detailed relationships between them.

Recently, the authors in [START_REF] Amro | A survey of classical methods and new trends in pan-sharpening of multispectral images[END_REF] provide a review of many pan-sharpening methods with their categorization. We fully agree with this categorization and think that it is more accurate and include the most known pan-sharpening methods:

- Algorithms based on IHS produce high spatial resolution MS images but with color distortion, especially in vegetation areas. The proposed method in [START_REF] El-Mezouar | A new intensity-hue-saturation fusion technique imagery with color distortion reduction for IKONOS[END_REF] uses the Normalized Difference Vegetation Index (NDVI) to correct pan-sharpened images. In [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF], the authors have introduced a new high-resolution NDVI (HRNDVI) index based on which they proposed a method to reduce color distortion and to enhance the vegetation. Like IHS, the main drawback of the PCA-based fusion is the distortion of the spectral information.

The recently proposed pan-sharpening methods are based on multi-resolution approaches of the Laplacian pyramid, the wavelet transform, and the Contourlet Transforms (CT).

As can be seen on figure 7, the obtained images show clearly that methods based on multiresolution give better results compared with the other pan-sharpening techniques.

Indeed, methods belonging to multiresolution category provide actually the most significant pan-sharpened images. The wavelet transform is widely used in pan-sharpening thanks to its properties such as multi-resolution, localization, critical sampling, and limited directionality (horizontal, vertical, and diagonal directions) [START_REF] Amro | A survey of classical methods and new trends in pan-sharpening of multispectral images[END_REF]. However, it fails to capture the smoothness along the contours [START_REF] Vp | An efficient pan-sharpening method via a combined adaptive PCA approach and contourlets[END_REF]. CT seems to overcome this drawback [START_REF] Do | The contourlet transform: an efficient directional multiresolution image representation[END_REF]. In fact, CT is a multiresolution transform which provides an efficient directional representation and takes into consideration wavelet properties. Thus CT has been used for image fusion and pan-sharpening in [START_REF] Vp | An efficient pan-sharpening method via a combined adaptive PCA approach and contourlets[END_REF] and in [START_REF] Amro | A survey of classical methods and new trends in pan-sharpening of multispectral images[END_REF]. The Non-Subsampled Contourlet Transform (NSCT) is a shift invariant version of CT. Figure 8 illustrates the performance of multiresolution pan-sharpening and the effect of applying IHS or PCA after multiresolution transform. Figure 9 represents the bloc diagram of a recent method based on NSCT to pan-sharpen MS images [START_REF] El-Mezouar | A Pan-Sharpening Based on the Non-Subsampled Contourlet Transform: Application to Worldview-2 Imagery[END_REF]. This method was tested on WorldView-2 images and was found to provide pan-sharpened images with very good quality compared to the state-of-the-art methods based on multiresolution (see Table I).

C. Assessment of pan-sharpening

The quality assessment of the pan-sharpened MS images presents a problem since no reference image exists at the pan-sharpened resolution. Even when reference MS images are available, the assessment of faithfulness to the reference usually requires computation of a number of different indexes. In this paper, we have selected the following widely used indexes for assessing the quality:

The correlation coefficient (CC) [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF]: it is the most popular. It measures the similarity between the fused and original images. A CC value of +1 indicates that the two images are highly correlated or similar.

The correlation between high frequencies (sCCz) based on [START_REF] Zhou | A wavelet transform method to merge Landsat TM and SPOT panchromatic data[END_REF]: a high-pass filter is applied to the fused bands and the PAN image. Then, the CC coefficient between the resulting images is computed.

The correlation between high frequencies (sCCo) based on [START_REF] Otazu | Introduction of sensor spectral response into image fusion methods. Application to wavelet-based methods[END_REF]: in this case high-pass filtered versions of the pansharpened bands are compared with the high-pass filtered versions of the original MS bands.

The relative bias (BIAS): it is the difference between the mean of the original image and that of the fused one, divided by the mean of the original image [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF].

The relative variance (VAR): it represents the difference in variance between the original and fused images, divided by the variance of the original image [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF].

The standard deviation (SD) of the difference image in relation with the mean of the original image: it indicates the level of the error at any pixel [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF].

The Structural SIMilarity (SSIM) index: it measures the similarity between two images [START_REF] Wang | Image quality assessment: From error visibility to structural similarity[END_REF]. The SSIM index can be viewed as a quality measure of one of the images being compared, provided the other image is regarded as of perfect quality.

MS image PAN image

Standard NSCT method result Proposed NSCT method result Fig. 10: NSCT-based pan-sharpening.

The universal objective image quality index (Q) [START_REF] Wang | A Universal Image Quality Index[END_REF]: it models distortion as a combination of three different factors: loss of correlation, luminance distortion, and contrast distortion.

The relative average spectral error (RASE): it is used to characterize the average performance of the pan-sharpening method in spectral bands [START_REF] Choi | A New Intensity-Hue-Saturation Fusion Approach to Image Fusion with a Tradeoff Parameter[END_REF].

The root-mean-square error (RMSE) [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF].

The average spectral angle mapper (SAM): it computes the change in angle of spectral vectors [START_REF] Rh | Discrimination among semi-arid landscape endmembers using the spectral angle mapper (SAM) algorithm[END_REF].

The relative dimensionless global error in synthesis (ERGAS): it provides a single quantity synthesizing the quality of the fused data set [START_REF] Wald | Quality of high resolution synthesized images: Is there a simple criterion?[END_REF].

The QNR index [START_REF] Alparone | Multispectral and panchromatic data fusion assessment without reference[END_REF]: it is used to assess fusion quality without requiring reference images. It is based on the universal quality index Q proposed in [START_REF] Wang | A Universal Image Quality Index[END_REF], and includes two indexes, one for spectral distortion and the other for spatial distortion. In the QNR approach, it is assumed that the inter bands spectral quality of the pan-sharpened images is unchanged after the fusion process.

The best value for indexes CC, sCCz, sCCo, SSIM, Q and QNR is 1, whereas it is 0 for indexes BIAS, VAR, SD, RASE, RMSE, SAM and ERGAS.

The protocol of Wald described in [START_REF] Wald | Fusion of satellite images of different spatial resolutions: assessing the quality of resulting images[END_REF] is usually used to evaluate pan-sharpened images. It consists of three properties but only the first one can always be assessed since the two others need the reference. In order to apply the whole protocol, two approaches must be conducted. In the first approach the pan-sharpening is performed at the full scale. In this approach the reference is not available; for this reason it is possible to directly assess only the first property of Wald's protocol. The second and the third properties of Wald's protocol can be indirectly verified by using the QNR and sCCz indexes. The second approach, instead, allows directly verifying also the second and the third properties. It consists of down-sampling all the dataset (panchromatic and multispectral), making pan-sharpening at lower scale and using the original multispectral as reference [START_REF] Zhang | An IHS and wavelet integrated approach to improve pan-sharpening visual quality of natural colour IKONOS and QuickBird images[END_REF]. This approach is used to compute indexes sCCo, CC, Bias, VAR, SD, SSIM, Q, ERGAS, RASE, RMSE and SAM. In this way the protocol is entirely applied. In the first approach, the second and the third property of Wald's protocol are indirectly assessed by using the QNR and sCCz indexes; while in the second approach the indexes the CC, SSIM, Q and sCCo indexes verify the second property; and finally indexes ERGAS and SAM verify the third property. In general, the two fusions must be conducted: one at full scale and the other at lower scale. The former is used for computing the sCCz and QNR indexes. The latter is used to compute the rest of the indexes: sCCo, CC, Bias, VAR, SD, SSIM, Q, ERGAS, RASE, RMSE and SAM.

Figure 10 shows two examples of NSCT-based fusion methods. From left to right are shown the MS image, the PAN image, the fused image using the standard NSCTbased method and a recent NSCT-based pan-sharpening with a different number of decomposition levels [START_REF] El-Mezouar | A Pan-Sharpening Based on the Non-Subsampled Contourlet Transform: Application to Worldview-2 Imagery[END_REF].

In the traditional pan-sharpening based on NSCT (we call it "Standard NSCT"), the MS images and the PAN image are first decomposed up to the same number N of levels. Then the coarse level of PAN image decomposition is replaced with that of MS image to apply backward NSCT transform. But one can observe that: in a multiresolution process, the MS image of size T is equivalent to reducing the resolution of the PAN image of size 4T down to 2 levels; so decomposing PAN and MS images to the same number of levels and combining the coarse level of MS and the fine levels of PAN in the backward NSCT transform appears to be unjustified: there is a mix of resolutions. So the idea to overcome this drawback is to decompose the MS image to 1 level and decompose the PAN image to 3 levels. By doing this, the 3-level NSCT PAN image and the 1-level NSCT MS image are of equivalent resolutions. Now, one can apply the backward NSCT transform after replacing the coarse level of PAN image with that of MS image. Some indexes, assessing the quality of the fused images, are computed and shown in Table I. This table demonstrates the efficiency of the proposed method. Spatial quality is measured by sCCz and sCCo, while spectral quality is evaluated using the rest of the indexes. From Table I, it is obvious that the proposed method, based on different number of decomposition levels, gives better results, in terms of most of the indexes, compared to the standard method based on a fixed number of decomposition levels for both the MS and the PAN images.

IV. APPLICATION TO VEGETATION ASSESSMENT

One of the main applications of pan-sharpening is the assessment of the vegetation conditions. As it has been shown in [START_REF] El-Mezouar | An IHS-Based Fusion for Color Distortion Reduction and Vegetation Enhancement in IKONOS Imagery[END_REF], vegetation detection can be improved by using pan-sharpened images in the computation of the vegetation index. Hence, a new NDVI, the HRNDVI, has been proposed that integrates pan-sharpened bands instead of the corresponding original ones.

This statement is confirmed by the recent study [START_REF] Johnson | Effects of Pansharpening on Vegetation Indices[END_REF] about the effect of pan-sharpening on vegetation indices. In this study, some pan-sharpening methods are applied before computing the vegetation indices. This study concluded that it may be desirable to apply pan-sharpening prior to vegetation indices computation.

V. CONCLUSION

Image pan-sharpening is a process of fusing low spatial resolution but high spectral resolution MS images with the high spatial resolution but low spectral resolution PAN image to produce high spatial and high spectral resolution multispectral image. This provides high quality color image for better visualization of remote sensing images.

This paper has presented an overview of pan-sharpening methods. It is observed that the trends in pan-sharpening are to use multiresolution methods.

We have also shown that using different number of decomposition levels gives better pan-sharpening quality than when using the same number of decomposition levels.

Though pan-sharpening may affect the vegetation indexes, it has been shown that the distortions are insignificant in the assessment of the vegetation conditions.

  that shows the frequency response of the PAN sensor of WorldView-1. Examples of panchromatic imaging system are Ikonos Pan, QuickBird PAN and WorldView PAN.

Fig. 1 : 2 Fig. 2 :

 122 Fig. 1: A WorldView-1 Panchromatic image of Yokohama, Japan acquired October 5, 2007 2

Fig. 3 :Fig. 4 :

 34 Fig. 3: Spectral Response of the WorldView-2 panchromatic and multispectral imager [2]

Fig. 5 :

 5 Fig. 5: SPOT 5: left image: Naples 4 at 5 m resolution and right image: Paris 5 at 2.5 m resolution

Fig. 6 :

 6 Fig. 6: Left: MODIS image 6 , middle: Hyperion image 1 7 and right Hyperion image 2 8

Fig. 9 :Fig. 8 :

 98 Fig. 7: pan-sharpening examples for component substitution, relative spectral contribution and high-frequency injection categories.

TABLE I QUANTITATIVE

 I ASSESSMENT OF PAN-SHARPENED IMAGES

					Quality assessment indexes
	Fusion method
		sCCz	sCCo	CC	SSIM	Q	ERGAS	SAM	QNR
	NSCT with fixed number of decomposition levels	0.9957	0.7819	0.9258	0.8388	0.7349	7.8062	14.5579 °	0.7143
	NSCT with different number of decomposition levels	0.9956	0.7821	0.9267	0.8429	0.7384	7.7528	14.5184 °	0.7158

http://www.webcitation.org/6H82i1Gfx (visited June

2014)

http://www.satimagingcorp.com/galleryimages/worldview-2-mecca-

http://modis.gsfc.nasa.gov/gallery/individual.php?db_date=2012-04-22 (visited June 2014)

http://www.nasa.gov/images/content/194419main_eo-1_RGB.jpg (visited June 2014)

http://www.nasa.gov/images/content/194420main_eo-1_SWIR.jpg (visited June 2014)

ACKNOWLEDGMENT This work was supported in part by the Franco-Algerian cooperation program PHC TASSILI grants. Entitled "Système Conjoint de Compression et d'Indexation Basé-Objet pour la Vidéo (SCCIBOV)", the project gathers members of Institut National des Sciences Appliquées (INSA) de Rennes, Université de Technologie de Compiègne (UTC), the University of Sidi Bel Abbès and the University of Mascara.