Member, IEEE Qiang Yin
email: yinq@mail.buct.edu.cn

Senior Member, IEEE Wen Hong
email: whong@mail.ie.ac.cn

Senior Member, IEEE Fan Zhang
email: zhangf@mail.buct.edu.cn

Fellow, IEEE Eric Pottier
email: eric.pottier@univ-rennes1.fr

Optimal Combination of Polarimetric Features for Vegetation Classification in PolSAR Image

Keywords: Classification, feature combination, nearestregularized subspace (NRS), PolSAR, support vector machine (SVM)

Polarimetric features of PolSAR images include inherent scattering mechanisms of terrain types, which are important for classification and other Earth observation applications. By using target decomposition methods, many polarimetric scattering components can be obtained. Besides, the elements of a coherency/covariance matrix, as well as polarimetric descriptors, such as SPAN, single-bounce eigenvalue relative difference/double-bounce eigenvalue relative difference, etc., can also provide characteristic information. In fact, more and more polarimetric decomposition components and descriptors have been proposed; the computation cost increases if all of them are employed as the input of the classification process. Although all these features obtained from the coherency/covariance matrix are not independent, still, finding out which ones are significant for the classification of different terrain types will improve the understanding of scattering mechanisms. In this article, the effective polarimetric feature combination is studied based on the vegetation classification performance of support vector machine (SVM) and nearest-regularized subspace (NRS) machine learning approaches, as well as their combinations with a Markov random field (MRF). A framework on the basis of similarity and the orthogonal subspace projection (OSP) method in a hyperspectral area is used to select the polarimetric features. For the airborne PolSAR data in Flevoland, The Netherlands, 107 polarimetric features are extracted, including matrix elements, target decomposition components, and polarimetric descriptors. A subset is selected by using the proposed and OSP methods. They have a good classification accuracy evaluated by SVM+MRF and NRS+MRF classifiers. However, when the SVM and the NRS are used without combining spatial information of the MRF, the features selected by the proposed framework with correlation coefficient criteria have much better classification performance than those of OSP and principal component analysis.

I. INTRODUCTION

P OLARIMETRIC features provide scattering mechanisms of land cover, which make unsupervised classification possible. Many studies focusing on polarimetric features can be found in the literature; however, the main role of different features has not been revealed. More and more polarimetric decomposition components and descriptors have been proposed; the computation cost increases if all of them are employed as the input of the classification process. Meanwhile, there is no direct answer about their importance and specific roles in different applications yet. It is meaningful to study which features are important for certain applications. Some of the features may be irrelevant to the classification task, and others may be redundant. Thus, it is useful to exploit the discriminative power offered by the selection and combination of these features [START_REF] Bai | Supervised feature selection for polarimetric SAR classification[END_REF]. The idea of this article is to find out whether a small subset of features could achieve similarly good classification results as the whole feature sets. Actually, it depends on the features of specific data as well as the classifier, but there might also exist some regular patterns underlying.

The scheme of normal supervised classification includes two parts: feature extraction/selection and machine learning classifiers. The focus of this article is on the polarimetric features of PolSAR images, rather than the classifiers. We employ some classifiers for evaluating the performance of feature combinations.

Several groups work on the optimal feature selection for PolSAR image classification. Feature reconstruction methods, such as independent component analysis [START_REF] Wang | Unsupervised classification of polarimetric SAR images based on ICA[END_REF] and principal component analysis (PCA) [START_REF] Chamundeeswari | An analysis of texture measures in PCA-Based unsupervised classification of SAR images[END_REF], have been found applicable, but they will change the physical meaning of the original data because new channels do not correspond to an original polarimetric feature, but their linear combinations. In this way, we cannot figure out which polarimetric features play a significant role in applications. Chen et al. [START_REF] Chen | Feature evaluation and selection for polarimetric SAR image classification[END_REF] applied a convex framework for joint learning of the optimal feature weights and support vector machine (SVM) parameters. Haddadi et al. [START_REF] Haddadi | Polarimetric SAR feature selection using a genetic algorithm[END_REF] used a combination of a genetic algorithm and an artificial neural network for extracting optimized features of PolSAR images that are required for classification. Some methods need to rearrange the PolSAR image to vectors, which may lose the spatial information of neighboring pixels. For this consideration, Tao et al. proposed a tensor-based dimension reduction technique, using 48 polarimetric decomposition features of synthesized PolSAR data [START_REF] Tao | Tensor based dimension reduction for polarimetric SAR data[END_REF]. Based on the Touzi decomposition parameters, A c c e p t e d M a n u s c r i p t Banerjee et al. [START_REF] Banerjee | A generic landcover classification framework for polarimetric SAR images using the optimum Touzi decomposition parameter subset-An insight on mutual information-based feature selection techniques[END_REF] proposed a third-order class-dependent mutual information (MI) method and another eigenspace decomposition of the conditional MI matrix method to select a feature subset. Besides, a feature selection separability index criterion with the naive Bayes classifier was utilized in [START_REF] Gupta | Class wise optimal feature selection for land cover classification using SAR data[END_REF], where ten polarimetric features and 27 other features were examined.

The analysis on polarimetric features is necessary for classification and other related applications, since machine learning as well as deep learning classifiers have been used a lot; however, their requirement on input features is not clear. Several classifiers such as nearest neighbor, naive Bayes, and neural network (NN) have been successfully used in the literature for characterizing SAR data [START_REF] Fukuda | Support vector machine classification of land cover: Application to polarimetric SAR data[END_REF], [START_REF] Koetz | Multi-source land cover classification for forest fire management based on imaging spectrometry and LiDAR data[END_REF]. The SVM has outperformed the traditional classifiers in almost all the domains in terms of the generalization accuracy as well as time and space complexities. The SVM has been used in this article, as it has a convex formulation, requires lesser numbers of training samples, and has a simple but mathematically sound statistical learning-based background theory. In some cases, the recently proposed representation-based classifications provide better performance than the classic NN [START_REF] Pajares | Improving Wishart classification of polarimetric SAR data using the Hopfield neural network optimization approach[END_REF] and SVM [START_REF] Fukuda | Support vector machine classification of land cover: Application to polarimetric SAR data[END_REF] in that they require few labeled data instead of the traditional training-testing mode. Representation-based classification is essentially based on the concept that a pixel can be represented as a linear combination of labeled samples via the sparse regularization methods, such as the l 0 -norm, l 1 -norm, and l 2 -norm regularization. In this manner, an approximation of the pixel is generated from labeled samples of each class independently, and the class label is then derived according to the class of the minimum representation error. In this article, the supervised classifiers of SVM, nearest-regularized subspace (NRS), as well as SVM+MRF [START_REF] Masjedi | Classification of polarimetric SAR images based on modeling contextual information and using texture features[END_REF] and NRS+MRF [START_REF] Zhang | Nearest-regularized subspace classification for PolSAR imagery using polarimetric feature vector and spatial information[END_REF] are used. By the way of involving the MRF model, the spatial information between pixels is reserved. The Markov random field (MRF) approach is a popular model for incorporating spatial information into image classification [START_REF] Masjedi | Classification of polarimetric SAR images based on modeling contextual information and using texture features[END_REF], [START_REF] Schick | Improving foreground segmentations with probabilistic superpixel Markov random fields[END_REF], [START_REF] Ghamisi | Spectral-spatial classification of hyperspectral images based on hidden Markov random fields[END_REF].

In this article, we focused on the polarimetric feature analysis and its effective combinations for the classification of PolSAR data. The classifiers are employed only for the performance evaluation of the features' capability on terrain classification. They are independent of the feature selection process. A set of 107 polarimetric features is extracted, and the polarimetric feature vector is constructed, which cover almost all the representative and recent ones [START_REF] Lee | Polarimetric Radar Imaging: From Basics to Applications[END_REF]. A polarimetric feature selection method based on the similarity between each two features is proposed, which takes into consideration of both representatives of highly related features and the unrelated ones. As summarized in the review of [START_REF] Li | Feature selection: A data perspective[END_REF], the current feature selection methods based on the similarity all use a criterion or a parameter, such as Laplacian Score, SPEC, Fisher Score, Trace ratio, Relief F, etc., to compute the weight of each feature. Afterward, with the obtained weights, all the features are ranked, so the important ones can be selected out. However, the key point of our suggested method is to compute the similarity between each pair of features, for example, the correlation coefficient (CR). Hence, what we got is the correlation between each pair of two features, rather than the weight of each feature. In the obtained feature subset, the features with different kinds of scattering mechanisms are preserved. In addition, another similarity-based band selection method proposed for a hyperspectral image is introduced to the PolSAR image for the first time. Experiments are implemented to assess these two methods, as well as to compare them with the principal components constructed by the PCA approach. It is shown that the feature subset obtained by the proposed CR criteria keeps better polarimetric scattering information at the pixel level for the application of vegetation classification.

The rest of this article is organized as follows. In Section II, the basic of polarimetric features of SAR data is briefly introduced. Afterward, in Section III, two feature selection methods are presented. The first proposed criterion is based on CR and the second one is introduced from hyperspectral image processing called similarity-based band selection. Supervised classifiers used for classification are briefly introduced in Section IV. Then, the experiment data, extracted polarimetric features, as well as the corresponding classification results with different selection methods are shown in Section V. For the aim of comparison, the PCA method is also employed to form the same number of new features and then to be used for the classification application. Finally, the conclusion is given in Section VI.

II. POLARIMETRIC FEATURE EXTRACTION

The information of the PolSAR data is contained in four channels, respectively, HH, HV , V H, and V V , which indicate four linear orthogonal polarization combinations. Assuming that the data are processed with spatial average under a monostatic mode, the complex backscattering matrix [S] for each image pixel at a specific incidence angle can be expressed as

[S] = S hh S hv S vh S vv (1)
where the subscript h indicates the horizontal polarization channel, and the subscript v represents the vertical polarization channel. Under the monostatic backscattering case, there exists a reciprocity theorem, i.e., S hv = S vh . We discuss this backscattering case in the following part of this article. From the scattering matrix [S], polarimetric information is usually interpreted by the second-order polarimetric descriptor coherent and covariance matrices. The multilook coherent matrix [T ] and covariance matrix [C] can be expressed as follows:

[T ] = k • k H (2) [C] = Ω • Ω H (3)
where • denotes the ensemble average, the superscript H indicates the complex conjugation and transpose of vector and matrix, k is the Pauli-based scattering vector, and Ω is the Lexicographic scattering vector. These two vectors can be specified by vectorizing the scattering matrix [S] and are defined in the backscattering case as follows:

k = 1 √ 2 [S hh + S vv , S hh -S vv , 2S hv ] T (4) Ω = [S hh , √ 2S hv , S vv ] T (5)
A c c e p t e d M a n u s c r i p t where the superscript T indicates the transpose of the vector. Accordingly, the coherency matrix [T ] and the covariance matrix [C] are 3 × 3 in the monostatic backscattering case.

Three categories of polarimetric features are used in this article: matrix elements, decomposition components, and polarimetric descriptors, as shown in Table I. The first category includes ten elements of coherency and covariance matrices. The second category includes 79 decomposition components of different target decomposition methods. In addition, the third category has 18 polarimetric descriptors, such as SPAN, polarimetric fraction, polarimetric asymmetry (PA), scattering predominance, etc.

In the first category of polarimetric features, seven elements of the coherency matrix are extracted, which are T 11 , T 22 , T 33 , and the amplitude and phase of T 13 and T 23 . Other three elements are obtained from the covariance matrix, which are the amplitude of C 12 , C 13 , and C 23 .

Within the second category, there have been many proposed target decomposition theorems that can be classified into four main types, which are those based on the Kennaugh matrix, those using an eigenvector or eigenvalues analysis of the covariance matrix or coherency matrix, those based on a model-based decomposition of the covariance matrix or the coherency matrix, and those employing coherent decomposition of the scattering matrix [START_REF] Lee | Polarimetric Radar Imaging: From Basics to Applications[END_REF]. Among these four types of target decomposition algorithms, the former three belong to the incoherent decomposition, which is usually used to process the coherency matrix, the covariance matrix, and the Kennaugh matrix for representing them as a linear combination. The coherent target decomposition algorithm is used to process the scattering matrix for representing the polarimetric information of the point target and the distributed target [START_REF] Huynen | Phenomenological theory of radar targets[END_REF]- [START_REF] Touzi | Target scattering decomposition of one-look and multilook SAR data using a new coherent scattering model: The TSVM[END_REF].

In the third category of polarimetric descriptors, most are developed based on the eigenvalues and eigenvectors of the coherency matrix, such as SPAN, single-bounce eigenvalue relative difference (SERD), double-bounce eigenvalue relative difference (DERD), Shannon entropy, polarization fraction, PA, target randomness, radar vegetation index, pedestal height, etc. These new parameters have been proved to be useful when analyzing scattering characteristics of PolSAR data, together with other polarimetric features [START_REF] Allain | A polarimetric classification from PolSAR data using SERD/DERD parameters[END_REF]- [START_REF] Zyl | Imaging radar polarization signatures: Theory and observation[END_REF].

All these 107 polarimetric features are in fact extracted originally from the coherency matrix [T ], or the equivalent covariance matrix [C], which means they are not independent. However, different features can reflect scattering mechanism details from different perspectives, so we can study about which features are significant for land classifications.

III. FEATURE SELECTION METHOD

The proposed method for polarimetric feature selection is based on the similarity measured by the CR; then, the orthogonal subspace projection (OSP) similarity-based approach in the hyperspectral area is introduced into the polarimetric feature. Besides, PCA is applied to form the same number of principal components for comparison. The data processing flowchart is shown in Fig. 1.

A. Proposed Framework Based on Similarity

Our suggested method is based on the similarity between each pair of features. For instance, the CR can be employed to measure the similarity between every two features. Hence, what we got is the correlation between each pair of two features, rather than the weight of each feature. This is the main difference compared to other existing methods, which usually use a criterion or a parameter, such as Laplacian Score, SPEC, Fisher Score, Trace ratio, Relief F, etc., to compute the weight of each feature. The difference leads to the following steps of the feature selection process. It is because we cannot simply rank the correlation of each pair. Our strategy in the following steps is: on one hand, with the similarity between each pair of features, above a certain threshold, those pairs containing the same feature are put into one group. By this step, several groups are formed, within which the highly related features are put together. Then, in each group, the appearance frequency of each feature is calculated, and the one with the maximum frequency in each feature group is selected out. It means that the representative features are kept from each group for classification. On the other hand, the features under the threshold are also kept, since the unrelated ones may contain specific information, which may be useful for the discrimination of classes. The whole framework is shown in One of the basic criteria of measuring the similarity between a pair of features is the CR, when it is employed to evaluate the similarity among different features. First, the CR between any pair of two features is calculated by the following equation: where Cov(X, Y ) is the covariance between the single feature vectors X and Y , and Var is the variance of the feature vector.

Coef(X, Y ) = Cov(X, Y ) Var(X)Var(Y ) (6)
Second, a proper threshold should be set. Thereafter, the feature pairs with the CR above this threshold are examined. Those pairs containing the same feature are put into one group, and the one with the maximum appearance frequency in each group is chosen into the feature subset. Meanwhile, the features under the threshold, which has not appeared above the threshold, are kept into the subset as well.

In our suggested framework, besides the CR, any criterion measuring the similarity could be used, such as Euclidean distance, Minkowski distance, Manhattan distance, and so on. Therefore, it is possible to change the criterion for similarity under the general framework. It provides a scheme to select feature subsets based on the similarity between two features. Some classic distances are listed as follows:

EuDist(X, Y ) = (X -Y ) 2 (7) MinkDist(X, Y ) = ((X -Y ) p ) 1/p (8) ManhDist(X, Y ) = |(X -Y )| . ( 9
)
In this article, the Euclidean distance is also used for data experiments, which is shown and analyzed in Section V. When the distance is used to obtain the similarity among features, the computed values are not the same as with the correlation, which lies between 0 and 1. So, it is necessary to do normalization Require: Extracted polarimetric features of the SAR image Ensure: Selected features in the subset 1: Feature vector construction← stacking all the categories of polarimetric features; 2: Choose an initial pair of features; 3: Find a third one feature that is the most dissimilar to all others in the current subset by using the OSP criterion; 4: Continue on Step 3 until the number of features is large enough.

before setting the threshold. In addition, the indication of distance is opposite to correlation. The larger the distance, the lower the similarity. Usually, the negative sign can be added to the normalized distances for next selection steps. In this way, the pairs above the threshold have higher similarity, while the pairs under have lower correlation.

B. Similarity-Based Band Selection (OSP)

In this article, we introduce the similarity-based band selection method, which is widely used in hyperspectral image processing into polarimetric SAR feature selections. Generally, there are two well-known algorithms, which are unsupervised fully constrained least-squares linear unmixing in [START_REF] Heinz | Fully constrained least squares linear spectral mixture analysis method for material quantification in hyperspectral imagery[END_REF] and OSP in [START_REF] Ren | Automatic spectral target recognition in hyperspectral imagery[END_REF]. Due to a large number of original bands, the exhaustive search for optimal band combinations is computationally prohibitive. For this group of similarity-based approaches, the band similarity is evaluated jointly instead of pairwisely. The sequential forward search can save significant computation time. It begins with the best two-band combination, and then, this two-band combination is subsequently augmented to three, four, and so on until the desired number of bands is selected [START_REF] Du | Similarity-based unsupervised band selection for hyperspectral image analysis[END_REF].

Here, the OSP band selection is used to compute the similarity between a single feature and multiple features in step 3. Assume that there are two features B 1 and B 2 in Φ. To find a feature that is the most dissimilar to B 1 and B 2 , an orthogonal subspace of B 1 and B 2 is constructed as

P = I -Z(Z T Z) -1 Z T ( 10
)
where I is an N × N identity matrix, and Z is an N × 2 matrix, whose first column includes all the pixels in B 1 and the second column includes all the pixels in B 3 . Then, the projection y o = P T y is computed, where y includes all the pixels in B and y o is the component of B in the orthogonal subspace of B 1 and B 2 . The feature that yields the maximum orthogonal component y o is considered as the most dissimilar band to B 1 and B 2 and will be selected as B 3 for Φ.

The initial two features of M feature dataset whose dissimilarity is the largest can be found with the following steps.

1) Randomly select a band A 1 , and project all the other M -1 bands to its orthogonal subspace A 1 ⊥ . 2) Find the band A 2 with the maximum projection in A 1 ⊥ , which is considered as the most dissimilar to A 1 .

3) Project all the other M -1 bands to the orthogonal subspace A 2 ⊥ , and find the band A 3 with the maximum projection. 4) If A 3 = A 1 , A 1 and A 2 are confirmed to be the pair with the most significant dissimilarity, and the algorithm is terminated; if A 3 = A 1 , go to the next step. 5) Continue the algorithm until A i + 1 = A i -1 ; then, either A i-1 or A i can be used as the band selection initial B 1 .

IV. SUPERVISED CLASSIFIER

The classification methods employed in this article are SVM, NRS, as well as their corresponding combinations with the MRF method, i.e., SVM+MRF and NRS+MRF, under the consideration of reserving spatial information of pixels in images. The performance of these latter two classifiers have been studied in [START_REF] Zhang | Nearest-regularized subspace classification for PolSAR imagery using polarimetric feature vector and spatial information[END_REF]

y l = X l • α l (11)
where X l is a matrix with size of d × n l , n l is the number of available training samples for class l, C l = 1 n l = n, and α l represents the weight vector coefficients with size of n l × 1 for the linear combination. Suppose we have obtained the weight vector; the label of the test sample is determined by the residual between y and y l , which is represented as

r l (y) = y -y l 2 = y -X l • α l 2 . ( 12
)
Then, the class label is derived according to the class of the most accurate representation (i.e., the minimum value of the residuals for all the classes) as class (y) = arg min l=1,2,...,C r l (y) .

(

) 13
In NRS [START_REF] Li | Nearest regularized subspace for hyperspectral classification[END_REF], the weight vector for the linear combination is solved as follows:

α l = arg min y -X l • α l 2 2 + λ Γ l,y • α l 2 2 (14)
where Γ l,y is a biasing Tikhonov matrix specific to each class l and test sample y, and λ is a global regularization parameter, which is used to balance the minimization between the residual and regularization terms. For the NRS classifier, we design the diagonal elements of matrix Γ l,y in the form of

Γ l,y = ⎡ ⎢ ⎢ ⎣ y -x l,1 2 • • • 0 . . . . . . . . . 0 • • • y -x l,n l 2 ⎤ ⎥ ⎥ ⎦ (15)
where x l,1 , x l,2 , . . . . . . , x l,n l are the columns of X l for the class l. Commonly, the Euclidean distance will be used for measuring the similarity between the testing sample and the training sample and then to vote for the test sample belong to the proper label. According to formulas defined in ( 14) and ( 15), the approximation y l of each test sample y can be expressed as

y l = X l X T l X l + λΓ T l,y Γ l,y -1 X T l y. ( 16
)
The pixelwise NRS classifier has been demonstrated to be effective [START_REF] Li | Nearest regularized subspace for hyperspectral classification[END_REF]; however, for the PolSAR classification, the image representation of the same category object is always the blockwise manner, under which the spatial information may have the potential to further improve the classification accuracy.

In the MRF model, we have the probability of the test pixel y p (note that y p has the same meaning as aforementioned y) for each class, and the energy function E(•) of y p for class l can be represented as

E (y p |w p = l ) = μE data (y p |w p = l ) + Esmooth (y p |w p = l ) ( 17
)
Edata (y p |w p = l ) = p∈P Dp (y p |w p = l ) ( 18
)
where Dp is the spectral energy function for y p , and μ is the balance parameter. E smooth (y p |w p = l) means the extent on piecewise smoothness:

Esmooth (y p |w p = l ) = q∈N p B p,q (1 -δ (w p , w q )) (19)
where w p and w q are the labels, δ is the Kronecker delta function (δ(w p , w q ) = 1 if w p = w q , and δ(w p , w q ) = 0 otherwise), B p,q is viewed as the penalty between y p and y q [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in ND images[END_REF], y q represents the adjacent pixel to y p , and N p is the set of neighbors for the given pixel y p . Commonly, the more similar these neighboring pixels are, the larger the value it will be. If they are totally different, B p,q will be definitely zero. The performance of these four supervised classifiers has been demonstrated in [START_REF] Zhang | Nearest-regularized subspace classification for PolSAR imagery using polarimetric feature vector and spatial information[END_REF]. In general, the MRF can greatly decrease the misclassifications based on the good homogeneousness assumption. Hence, SVM+MRF and NRS+MRF can achieve high classification accuracy than single SVM and NRS. Usually, SVM is better than NRS. But with a combination of MRF, NRS+MRF performs even better than SVM+MRF.

V. EXPERIMENT

A. Datasets

The PolSAR dataset is the widely used L-band data acquired by the NASA/JPL AIRSAR system in Flevoland, The Netherlands, in August 1989. There are 11 different terrain types marked in ground truth, most of which are agricultural classes, such as stem beans, forest, wheat, bare land, rapeseed, pea, and so on. The size of this dataset is 750 × 1024 pixels, in which the ground truth data have around 68 188 pixels. The Pauli image and the ground truth image are shown in Fig. 3. The ground truth region mask is generated manually. To avoid the edge effect between different agricultural areas caused by the speckle filtering process, the mask of each region is set a bit smaller than the natural borders. Accordingly, the pixels in the mask region

B. Polarimetric Features

After the speckle filtering process with the refined Lee method of a 7 × 7 window size, all of these features are extracted through the recent version of open-source software PolSARpro v5.0 funded by the European Space Agency [START_REF][END_REF]. This set of 107 features includes almost all the polarimetric characteristics for classification, as listed in Table I. The polarimetric properties and statistical correlation between channels filtered by the refined Lee filter are well preserved, through the experimentation of many airborne and spaceborne polarimetric SAR data experiments in the literature of last 20 years. The filtering is applied to each term of the covariance matrix, including all the matrix elements. According to Lee et al., to preserve the polarimetric signatures, all elements are filtered in the same way by the same amount. The span image is used to compute the weight in a selected edge aligned window [START_REF] Lee | Polarimetric SAR speckle filtering and its implication for classification[END_REF].

Again, these 107 polarimetric features are not independent, since they are extracted originally from the coherency matrix [T ] or the equivalent covariance matrix [C]. However, we can still investigate on which ones play important role for land classifications.

C. Feature Combinations 1) Feature Combination by the Proposed Method:

With the proposed selection strategy based on the CR, ten features are chosen out of the total 107 features under the correlation threshold of 50%, as shown in Table II. In fact, for the Flevoland data, different threshold has been studied between 0.5 and 0.8. Although the obtained feature subset changes a bit, the whole classification performances basically keep the same level. In our proposed method, the idea to set this threshold is to find out the representative features in the highly related feature groups and, meanwhile, keep the unrelated features. As shown in Fig. 4, the number of feature groups containing more than 20 feature pairs above the threshold changes from 6 to 4 as the threshold changes from 0.5 to 0.8. Considering both the representative related and unrelated features inside the whole feature set, the threshold is set to 0.5 in this article, in order to keep six features above it and four features below it. It can be seen that the subset contain eight decomposition components (Yang3 Odd, Cloude T33, Combination HA, Entropy, Freeman Odd, VanZyl3 Odd, Yamaguchi3 Dbl, and Yamaguchi3 Vol) and two polarimetric descriptors (Scattering mech. Entropy and Shannon Entropy I). Within these eight target decomposition components, different kinds of scattering mechanisms are preserved. Yang Odd, Freeman Odd, and VanZyl Odd refer to single bounce or surface scattering, Yamaguchi Dbl corresponds to double bounce scattering, and Cloude T33 and Yamaguchi Vol are volume scattering. Besides, Entropy and Combination HA are the important parameters of eigenvalue decomposition. For this feature selection method, if the threshold is lower, the fewer features are preserved.

Yang decomposition is based on the Huynen decomposition, which is proposed as phenomenological theory. From this theory, it is possible for a single stationary target to define the "target structure diagram" and the nine "Huynen parameters," which are all tied to a physical property of the target. The basic idea of the Huynen target decomposition theorem is to separate from the incoming data stream apart, which would be identified with a single average target and a residue Since the eigenvalue problem is automatically basis invariant, such decompositions have been suggested as alternatives to the Huynen approach. This decomposition shows that the first two eigenvectors represent equivalent scattering matrices that can be interpreted in terms of odd and even numbers of reflections, so the odd component corresponds to the multiscattering with odd times. As to Freeman decomposition, which is one of the scattering-model-based decompositions, the three components correspond to three scattering mechanism models. The first component is described by the first-order Bragg surface scattering model of a slightly rough surface, in which the cross-polarized component is negligible. Because the above three decomposition methods belong to three types of methods, their odd components have some differences. Hence, it is possible to be kept in our selected feature subsets.

Besides the CR, the criterion of the Euclidean distance is also employed in our proposed framework to choose a polarimetric feature subset. When we use distance as the similarity measurement, it should be noted that normalization is very important in two aspects. On one hand, since the previous CR is a normalized parameter, which lies between 0 and 1, there is no need to do normalization. But for various distances, the values sometimes are very large. It is necessary to do normalization before setting the threshold of distances. In addition, the indication of distance is opposite to correlation. The larger the distance, the lower the similarity. Usually, the negative sign can be added to the normalized distances for next selection steps. On the other hand, while the distance is used, the features input to the classifiers should be normalized before the computation of distances. This is due to the fact that the distance is obtained between different pairs of features. Finally, ten features are chosen out of total 107 features under the threshold of 40%, as shown in Table III.

In this feature subset chosen by our proposed framework with the Euclidean distance, there are two matrix elements (C13 real and T22), seven decomposition components (VanZyl3 Dbl, Yamaguchi Y4O Dbl, Holm2 T22, Barnes1 T22, Krogager Kd, and MCSM Vol), and two polarimetric descriptors (SPAN and Combination HA). Different scattering mechanisms could be observed in this feature combination.

2) Feature Combination by the OSP Method: In order to compare different feature selection approaches, the same number of features is kept in the subset in the following experiments. With the introduced selection approach based on OSP, ten features are chosen out of the total 107 features, as shown in Table IV. Here, the subset contains eight decomposition components (MCSM Vol, Gamma, Huynen T11, Holm2 T22, MCSM Hlx, Neumann delta mod, MCSM Wire, and Krogager Ks) and two polarimetric descriptors (Polarization fraction and Pedestal). Again, different scattering mechanisms are preserved. Huynen T11 and Kragager Ks are single-bounce scattering; Holm T22 refers to double-bounce scattering. MCSM Vol, Hlx, and Wire corresponds to volume, helix, and wire scattering. There are also the components of eigenvalue decomposition and Neumann decomposition kept in the subset. Since there is a sequence of the selected features in this band selection method, once the number of required features is set, the selection process stops until the number reaches to the required number.

In the step of feature selection, the CR method mainly computes the correlation between each pair of two features, and it costs 184 s for the Flevoland data. The time for choosing features under a threshold is very short-less than 1 s, so as to be neglected. Compared to it, the OSP method costs 1190 s to select ten features for the same data.

D. Classification Results

First, the polarimetric SAR feature space is constructed by 107 features for each pixel. In the SVM classifier, sigma is equal to 0.1. In the NRS, the regularization parameter is 2.5, and the tuning parameter is -0.5. For all the classification experiments in this article, the number of training samples is set to 300 for each class. And the number of test samples is shown in Table V.

1) Classification of the Whole Feature Set: In Fig. 5, the classification results of all 107 features using four classifiers are given. Using the SVM, the classification results is 81.31%, while the NRS gets lower accuracy of 77.68%. Both SVM+MRF and NRS+MRF classifiers have very fine overall classification accuracies of 96.1% and 99.58%, respectively, on the condition of training ratio lower than 4.5%.

2) Classification of Feature Combination by the Proposed Method: The classification results of the feature subset selected by CR criteria are shown in Fig. 6. It can be seen that for all these four classifiers, this feature combination can achieve similar classification performances. Using the SVM, the classification result is 81.20%, while the NRS gets the accuracy of 75.56%. Both SVM+MRF and NRS+MRF classifiers have very fine overall classification accuracies of 89.78% and 95.76%, respectively. Especially, for NRS+MRF, except that only a part of an area covered by wheat is wrongly classified into grassland, almost all pixels in other areas are classified correctly.

It should be noted that without MRF improvement, only SVM or NRS can still get good results from this feature subset. For the NRS, the classification accuracy is even higher than the result of 107 features. This means that the feature subset preserves the polarimetric scattering information at the pixel level very well. Therefore, these ten polarimetric features can be considered as the effective feature combinations for this certain dataset.

The classification experiments with the Euclidean distance in our proposed framework are also implemented. The result can be seen in Fig. 7. We can see that by using the Euclidean distance, the selected feature subset has a bit lower classification performance compared to the CR. When the classifiers are SVM, NRS, SVM+MRF, and NRS+MRF, their overall classification accuracy is 74.16%, 68.89%, 87.02%, and 98.67%, respectively.

3) Classification of Feature Combination by OSP: The classification results of the feature subset selected by OSP band selection criteria are shown in Fig. 8. One obvious property of this feature combination is that the classification results by SVM+MRF and NRS+MRF are very high even up to those with input of the whole feature set. However, by use of the simple classifiers SVM and NRS, the results are around 50% or lower than that. It means that at the pixel level, the features selected by the OSP method contain less discriminative information for classifications than the CR approach.

4) Classification of Constructed Feature Combination by PCA: For the aim of comparison, we also constructed feature combinations using the PCA method, although in this way there is no corresponding direct feature related to certain scattering components. The classification results of the feature subset selected by PCA are shown in Fig. 9. The performance of this feature subset is close to the one chosen by OSP when using SVM+MRF and NRS+MRF, but a bit better when employing SVM or NRS. The classification results of above four feature combinations with various classifiers are displayed in Table VI. To conclude, with complex classifiers like NRS+MRF/SVM+MRF, which utilize spatial information, the feature subset selection by OSP and constructed features by PCA get very good performance, while, on the other hand, with simple classifiers using pixel-level polarimetric information, the feature combination obtained by CR criteria performs better. It means the CR approach keeps more polarimetric scattering properties useful for classifications.

Another PolSAR dataset is acquired in the same area by the NASA/JPL AIRSAR system in June 1991. There are 14 different terrain types measured with ground truth, which are rapeseed, lucerne, peas, wheat, grass, oats, onions, potato, beet, maize, fruit, barley, beans, and background. The size of this dataset is 1024 × 1279 pixels, and the number of pixels with the ground truth data is around 122 928. The Pauli image and the ground truth image are shown in Fig. 10.

Similar data processing steps are implemented in this dataset, including speckle filtering and polarimetric feature extraction. First, the polarimetric SAR feature space is constructed by 107 features for each pixel. Then, the classification experiments with the whole feature space are done. The parameters inside the classifiers are basically the same with the first dataset. The difference is that the number of training samples is set to 1% for each class, instead of 300 for each class. This is because there are some small classes containing less pixels than 300. The number of test samples is shown in all 107 features using four classifiers are given in Fig. 11. Using the SVM, the classification result is 95.47%, while the NRS gets lower accuracy of 91.07%, SVM+MRF and NRS+MRF classifiers have better overall classification accuracies of 97.07% and 92.97%, respectively.

Following that, feature combination by the CR method is implemented. Nine features are chosen out of the total 107 features under the correlation threshold of 50%, as shown in Table VIII. Here, in this experiment, nine instead of ten features are kept due to the fact that there are nine independent elements of the coherency or covariance matrix, hence nine independent components of the whole extracted feature groups. It can be seen that the subset contains seven decomposition components (lamda, Huynen T33, MCSM wire, MCSM Odd, VanZyl3 Odd, Yamaguchi3 Odd, and Yamaguchi4 Odd), one matrix element T22, and one polarimetric descriptor SPAN. Within these nine features, different kinds of scattering mechanisms are preserved. Odd components refer to single bounce or surface scattering, T22 corresponds to double bounce scattering, Huynen T33 is volume scattering, and MCSM wire refers to wire scattering. SPAN is the whole scattering power, while lamda is an important parameter of eigenvalue decomposition.

The classification results of the feature subset selected by CR criteria are shown in Fig. 12. It can be seen that for all these four classifiers, this feature combination can achieve good classification performances. Even a bit lower than the results of 107 features, however, it should be noted that here only nine features are used as input of the classifiers. Using the SVM, the classification result is 83.40%, while NRSs gets the accuracy of 84.03%. SVM+MRF and NRS+MRF classifiers have a bit better classification accuracy of 87.12% and 88.32%, respectively.

Even without MRF improvement, only SVM or NRS can still get good results from this feature subset. This means that the feature subset preserves the polarimetric scattering information at the pixel level very well. Therefore, these nine polarimetric features can be considered as the effective feature combinations for this certain dataset.

VI. CONCLUSION AND FUTURE WORK

Studying the selection strategy of the polarimetric feature combination is of significance, since the computation cost can be reduced a lot. In fact, it depends on both the features of specific datasets and the classifier. In this article, we focused on the polarimetric features of PolSAR data. A set of 107 polarimetric features is extracted, and the polarimetric feature vector is constructed, which almost covers all the representative and recent ones. Two polarimetric feature selection methods are used to obtain a subset of ten features, which preserve the information of different scattering mechanisms. The proposed framework uses the CR and the Euclidean distance as criteria for similarity measurement and selects the representative ones within each feature group above the threshold; meanwhile, it keeps the unrelated features under the threshold. Besides, the influence of the threshold is also analyzed. OSP is introduced to PolSAR data from the hyperspectral area, but the performance is not as good as the proposed one. Besides, the computation time is longer. As to PCA, it is not the kind of method to keep the features with physical meaning, because the constructed feature corresponds to no scattering mechanisms. Experiments are implemented to assess these two methods, as well as to compare them with the principal components constructed by the PCA approach. With the subset of ten features, good classification results are achieved by using SVM+MRF and NRS+MRF classifiers. However, when the SVM and NRS are used as classifiers without combining spatial information by using the MRF, the ten features selected by CR criteria have a much better classification performance than that of the other OSP criteria. It means that better polarimetric scattering information at the pixel level is preserved through the proposed selection method for the application of vegetation classification. Another dataset in Flevoland area is tested using the proposed method to select nine polarimetric features, and the experiments show that less than 9% of features could achieve the comparable classification accuracy with the whole feature set.

A c c e p t e d M a n u s c r i p t

In the future, other similarity criteria could be tested in our proposed framework, in order to find out the best ones especially for describing the relations among lots of polarimetric features. Besides, new polarimetric features inside PolSARpro v.5.1 will be included in experiments. The experiments on other datasets will also be shown in future work, in order to see the difference in feature combinations for various data, and to reveal the underlying reason due to scattering mechanisms.

Fig. 1 .Algorithm 1 : 5 :Fig. 2 .

 1152 Fig. 1. Flowchart of data processing.

Fig. 2 .

 2 Fig. 2. Framework of the proposed method.

Algorithm 2 :

 2 A c c e p t e d M a n u s c r i p t OSP Similarity Band Selection.

A c c e p t e d M a n u s c r i p t

Fig. 3 .

 3 Fig. 3. Flevoland dataset: (left) Pauli image and (right) ground truth image.

A c c e

  p t e d M a n u s c r i p t

Fig. 5 .

 5 Fig. 5. Classification results using 107 features: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

  A c c e p t e d M a n u s c r i p t

Fig. 6 .

 6 Fig. 6. Classification results using ten features selected by the proposed method with the CR: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

Fig. 7 .

 7 Fig. 7. Classification results using ten features selected by the proposed method with the Euclidean distance: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

Fig. 8 .

 8 Fig. 8. Classification results using ten features selected by OSP: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

Fig. 9 .

 9 Fig. 9. Classification results using ten features constructed by PCA: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

  A c c e p t e d M a n u s c r i p t

Fig. 10 .

 10 Fig. 10. Flevoland dataset II: (left) Pauli image and (right) ground truth image.

Fig. 11 .

 11 Fig. 11. Classification results of dataset II using 107 features: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

  A c c e p t e d M a n u s c r i p t

Fig. 12 .

 12 Fig. 12. Classification results of dataset II using nine features selected by the CR: (top left) SVM, (top right) SVM+MRF, (bottom left) NRS, and (bottom right) NRS+MRF.

A c c e

  p t e d M a n u s c r i p t

  with different datasets. The principles of NRS and MRF are stated in the following. Assume a given dataset with training samples X = {x i } n i = 1 in d and the class label w i ∈ {1, 2, . . . , C}, where d is the number of spectral variables (bands), C is the number of classes, and n is the total number of the training samples. An approximation of the test sample y is represented via a linear combination of available training samples per class. For each class, we can calculate the approximation y l as

TABLE II TEN

 II FEATURES SELECTED BY THE CR Fig.4. Feature group number changes as the threshold increases.

TABLE III TEN

 III FEATURES SELECTED BY THE EUCLIDEAN DISTANCE component called "N-target." But if only the Odd component is observed, actually it is the T11 element itself, while VanZyl is one of the eigenvector-based target decomposition models.

TABLE V NUMBER

 V OF TEST SAMPLES FOR EACH CLASS

Table VII .

 VII The classification results of

TABLE VII NUMBER

 VII OF TEST SAMPLES FOR EACH CLASS IN FLEVOLAND II DATA

TABLE VIII NINE

 VIII FEATURES SELECTED BY THE CR WITH DATASET II

This work was supported in part by the National Natural Science Foundation of China under Grants 61801015, 61871413, and 61431018, and in part by the Beijing Natural Science Foundation under Grant 4184094.


Jérôme Blanchard
email: jerome.blanchard@fairandsmart.com

] Smart

Yolande Belaïd
email: yolande.belaid@loria.fr

Abdel Belaïd
email: abdel.belaid@loria.fr

Automatic generation of a custom corpora for invoice analysis and recognition

Keywords: Invoice generator, GEDI format, Graph Convolutional Neural Network

In this paper, we present a bill-type document generator capable of supplying on demand all the mass of documents that a learning system needs. The lack of administrative documents has long been a handicap because of the confidentiality of this type of document. In addition, this generator allowed us to solve the problem of annotations since they are done automatically during the generation and put directly in XML-GEDI form. Then, to show the interest of the generator, we proposed a system of invoice recognition based on graph convolutional neural network. The experiments took place in excellent conditions since we had all the possibilities to vary the classes, the samples in the classes, and their parameters.

I. INTRODUCTION

In order to extract named entities from scanned invoice's documents, we are using an Artificial Intelligence (AI) system that has been trained on annotated invoices taken from real life. We faced a common problem in AI training due to the fact that our invoices corpora was not big enough to produce relevant results using deep learning neural network. We realized that building a well annotated corpora is very costly, generates intellectual property problems and is not easy to customize when you want to add or modify some annotations. We decided to built a software to automate the generation of a custom corpora, based on an invoice data model made of real data. Our methodology could be used for any other data set that need an automated annotation based ground truth. The generated data (images and annotations) can be used solely or mixed with real life data in order to improve an existing dataset, especially for AI training.

This generation of on-demand documents goes with the idea of wanting to process streaming data without class limits. However, most existing systems like Intellix [START_REF] Schuster | Intellix-end-user trained information extraction for document archiving[END_REF], ITESOFT [START_REF] Rusinol | Andecy: Field extraction from administrative documents by incremental structural templates[END_REF], [START_REF] Hamza | A case-based reasoning approach for invoice structure extraction[END_REF], smartFIX [START_REF] Dengel | smartfix: A requirements-driven system for document analysis and understanding[END_REF] and others [START_REF] Cesarini | Analysis and understanding of multi-class invoices[END_REF], [START_REF] Andecy | Field extraction by hybrid incremental and a priori structural templates[END_REF] create specific models limited to the data they have. Due to their dependence on seeing the template beforehand, these systems cannot accurately extract information from unseen layouts of invoices. CloudScan [START_REF] Palm | Laws: Cloudscan-a configuration-free invoice analysis system using recurrent neural networks[END_REF] is perhaps the only model so far which can handle unseen layout invoices quite well. It is based on classification of word n-grams into entities of interest instead of mapping of words to fields.

We propose a generic approach to deal with all the entities in the invoice in or outside table. We model the whole invoice document as a document graph of words, then we classify each word in the document into classes of interest to extract through a graph convolutional network (GCN) and finally we group the words of same classes together to obtain the final entities. The power of our system lies in the graph modeling and GCN, which takes into account the features of its neighboring words and their inter-relationships to decide the class of a word [START_REF] Lohani | An Invoice Reading System using a Graph Convolutional Network[END_REF].

The paper is organized as follows: Section II presents the generator and its different possibilities. Section III shows the invoice analysis approach. Finally, we give some conclusion remarks in IV.

II. INVOICE GENERATION

By analyzing real invoices, determined that it was nearly always composed of the same elements, some mandatory or always present like: a Head zone containing Company Informations, Client Informations, Invoice Numbers and Dates; a central zone containing Products, Payment Infos and some ID Numbers and a Footer zone containing various informations but at least the Totals. Others elements are optional or their position can vary a lot like: Company Logo, some Company Informations like VAT Number, SIRET, Expedition Type and Shipping Cost, etc.

In order to be able to produce any kind of invoice, we first defined a model containing all possible invoice data (see Figure 1). Model structure is critical for the accuracy of the training and for the final usage. It must be fine grain enough to ensure good annotation accuracy. We defined classes that we want to extract or classify using the AI process. We decided to use an object based model to define all the components of an invoice. All those objects are organized in a tree where root node is the invoice itself.

All objects that compose the data tree have to provide a generator for its own type. This generator can use several kinds of data source: random generation, data source based generation, set of values, set of regular expressions. Thus, generation of an invoice data results in crawling the tree to generate each node using its own generation implementation. Container nodes are responsible for propagating the

A. Context generation

For each invoice generation, some definitive choices are made during tree generation and those choices have impact on the rest of the generation: for example, the generation language, currency or date format. As soon as the currency is chosen it has to be taken into consideration for many elements of the tree. To enforce this coherency across all nodes of the invoice, we are using a dedicated structure, the Generation Context, which is propagated to all nodes during the tree generation. Some context choices can have impact where it seems it should not: the choice of the company logo can be directly linked with the country previously set in the context avoiding inconsistency on logo slogan that are not in the same language than the rest of the invoice. Thus, the generators of some model nodes can be increased with newly discovered context dependencies by adding heuristics in this node generator based on context values.

B. Data generation strategies

The first strategy for generation is to use a set of regular expressions to produce data. This works well for invoice numbers or invoice dates. Those nodes are using predefined regular expression based on real life invoice data observation. Then, we use a library (https://github.com/mifmif/Generex) that is able to randomly generate any value in the whole regular expression domain possibilities. The regular expressions can also be conditioned with some generation context's choices, some are dedicated to specific language or country for example.

A second strategy for generation is to use real life open databases. For example, addresses are randomly generated using public base for all countries that we want to support. This can create more realistic invoice using, for a Belgium invoice, real Belgium addresses. We also use, for labels or some textual parts of an invoice, predefined set of all values that we already observed on real invoices. Those samples are ordered by language and/or by country.

Another generation strategy is to include some pseudo random in some heuristic choices, sometimes with a statis-tical distribution of results. For example, the client's billing address is often the same than the client's shipping address so we used a generation proportionality of 80% the same and 20% another adress. In the same way, command date, shipping date and billing date are generated using some heuristics that avoid a shipping date prior or too far of the command date. We also use some heuristics for the generation of the products included in the invoice: depending on the product category, the product random quantity is not the same (it is reasonably possible to buy 10 ink cartridge but not to buy 10 microwaves).

C. Global generation process

The global generation process consists of fixing or randomizing some context elements (country, language) and of starting an iterative process to be able to generate as much as invoice data we need.

The generation strategies as much as the data sources (products, addresses, companies logos, etc.) and the regular expressions for elements generation can be easily expended and included in a new generation cycle by improving node generators heuristics or data sources.

D. Graphical representation of the invoice model

Once the data model is generated, we can build a graphical representation of that invoice. We decided to generate invoices in PDF that we can export in an image format (TIFF or JPG). The graphical generation consists in drawing all pieces of invoice data model onto a single page using a dedicated Layout. The layout is responsible of placing model data on the sheet but also to produce the annotations corresponding to the graphical position and size of all elements; image is generated in a PDF flow and annotations in an XML flow (in the GEDI format (https://sourceforge.net/projects/gedigroundtruth/)). As for the invoice model, layout elements are built in a tree structure.

E. Graphical elements generation

We created a set of graphical components with basic behavior of typical graphical toolkits but also with the annotation process built-in. We started by implementing the smallest object of our kit: the Text Box. This basic component consist of a part of text which can be drawn into the picture. More complexity is added to this simple behavior like, the desired font, the padding, the box size (allowing to split text if end of line is reached), color, background color, line height. More than only graphical consideration, we give also annotation consideration like the entity name that corresponds to this text.

F. Annotation generation

The annotation generation consists of creating an XML element based on GEDI schema. The annotation is included in an XML stream and include position and box size of the text zone but also the text itself and the annotation class that we want to learn. Layout is also responsible, by using invoice model data, to fix annotation classes.

G. Layout for invoices

In order to produce invoices with complex layouts, we have developed graphical objects that acts as containers for Text Box. Thus, we have Horizontal Container, Vertical Container, Table Row, etc. We also defined some specific elements for graphical purpose only like Graphic Lines, Images, Borders, etc.

H. Fixed based layout

Fixed based layout are a simple static based combination of existing elements to produce a "clone" of a real invoice and to use it for the generation of many invoices with various data. This allows to have a ground truth very close to the reality but with a bigger number of invoices. Nevertheless, we need to have many existing samples in order to have a varied ground truth and layout integration can be costly in this case.

I. Generic layout

We decided also to work on generic layout by defining parts of an invoice that could produce random behavior. We defined Global Zones (Header, Product Table, Product Footer, Global Footer). Header Zone will be divided in four regions allowing to place randomly global components: Company Information, Order information, Billing Address, Shipping Address. The rendering of all components and regions will be randomized using specific graphical representation (background color, font size, border, etc.). This will allow to have mixed rendering layout based on a rich graphical library. The Table 3 shows the different element location and neighbor relationships, while the Table I highlights the elements appearing in the different blocks, indicating whether they are mandatory or optional relationships

The Figure 4 shows an example of generated invoices, one from actual invoice (a) and one generated randomly (b).

III. INVOICE ANALYSIS

The global system has been published in [START_REF] Lohani | An Invoice Reading System using a Graph Convolutional Network[END_REF]. We are going to just summarize here the main idea of the system. The image is run through an OCR engine (Tesseract). From this output, we only take word zones and ignore all other zones such as graphic line, area, image, etc., because the higher up zones are composed of word zones and accumulate more ocr segmentation errors. Then, features are calculated for each word. These words are used to model the complete document as a graph with words as nodes and edges depicting neighborhood relationships. This document graph is fed to a graph node classifier which classifies each word into classes of interest. Finally words belonging to same classes are grouped together following left to right ordering to form entities.

Text feature calculation is basically converting the word text into a meaningful vector representation. For this task, we use BPEmb [START_REF] Heinzerling | BPEmb: Tokenization-free Pretrained Subword Embeddings in 275 Languages[END_REF]. We obtain a 317 dimensional feature vector of every word in the document. The last 17 elements are reserved for the existence of keywords like date, zipcode, city, etc.

The whole document is modeled as a graph with words as nodes and edges denoting nearest neighbors of a word in 4 major directions. This is different from, for example, the system of ITESOFT [START_REF] Rusinol | Andecy: Field extraction from administrative documents by incremental structural templates[END_REF] using a star graph for each important word. For modeling, we were inspired by the system of [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] who used a Graph Convolutional Networks (GCN). We used more than 3000 images generated by our generator, by selecting those which seemed to us quite representative of the sought variations. In current system, we scan each image in 300 dpi. The invoices are annotated at word level by providing each word a ground truth class.

IV. CONCLUSION

In this paper, we presented two ways to automatically generate invoices, inspired by actual invoices to which we applied random variations of a few elements. The other is completely free, by simply considering the elements that must appear in the invoice, but by introducing inter and intra-element relations. The organization scheme of the elements in the page was complex because the constraints are numerous. We opted for reasonable constraints leading to the production of fairly realistic bills. This work has allowed us to generate enough well annotated invoice samples to allow learning and recognition in good conditions.

Figure 1 :

 1 Figure 1: Invoice Model Schema.

Figure 2 :

 2 Figure 2: Annotation generation schema.

Figure 3 :

 3 Figure 3: Main table elements and their location and interrelationships.

Figure 4 :

 4 Figure 4: Examples of generated invoices: (a) from actual invoice by varying the information inside the blocks, and (b) randomly generated.

Table I :

 I Intra-element constraints

	Type	Delivery / Billing	Invoice information	Order Information Product table	Summary table / totals
		Last name / First Name Company Name	Invoice number	Order number	Quantity
	Mandatory	No. and street	No. and street	Date		Name
		ZipCode, City name	ZipCode, City name			Unit Price excl tax
						Total Price excl tax
		Country	Country	Location	Order date	Product reference
		Tel number	Tel number	Client number	Client number	Unit price incl tax
		@mail	Fax N°Company Name	Payment mode Discount
	Optional		@mail		Payment Total	Final unit price incl tax
			@site		Sending date	Eco participation
					Sending mode	VAT
					Parcel number


Chemseddine Neche
email: neche.chemseddine@gmail.com

Abdel Belaïd
email: abdel.belaid@loria.fr

Afef Kacem-Echi

Arabic Handwritten Documents Segmentation into Text-lines and Words using Deep Learning

One of the most important steps in a handwriting recognition system is text-line and word segmentation. But, this step is made difficult by the differences in handwriting styles, problems of skewness, overlapping and touching of text and the fluctuations of text-lines. It is even more difficult for ancient and calligraphic writings, as in Arabic manuscripts, due to the cursive connection in Arabic text, the erroneous position of diacritic marks, the presence of ascending and descending letters, etc. In this work, we propose an effective segmentation of Arabic handwritten text into text-lines and words, using deep learning. For text-line segmentation, we used an RU-net which allows a pixel-wise classification to separate text-lines pixels from the background ones. For word segmentation, we resorted to the text-line transcription, as we have not got a ground truth at word level. A BLSTM-CTC (Bidirectional Long Short Term Memory followed by a Connectionist Temporal Classification) is then used to perform the mapping between the transcription and text-line image, avoiding the need of the input segmentation. A CNN (Convolutional Neural Network) precedes the BLST-CTC to extract the features and to feed the BLSTM with the essential of the text-line image. Tested on the standard KHATT Arabic database, the experimental results confirm a segmentation success rate of no less than 96.7% for text-lines and 80.1% for words.

I. INTRODUCTION

Text-line and word segmentation is the process by which the basic entities in a text document image are localized and extracted. It is an important step for off-line handwritten text recognition because inaccurate segmentation will cause errors in the recognition step. However, locating text-lines and words in Arabic manuscripts remains a challenge. In fact, the Arabic manuscripts are considered to be more complex than other manuscripts written in other languages. This complexity comes first from handwritten text characteristics which can vary in writing style, size, orientation, alignment and where adjacent text-lines can be touching or overlapped, and second from the Arabic writing nature: cursiveness of the text, character overlapping, diacritic, variety of calligraphic, words are often divided into letters and sub-words and the spaces between them are variable.

The existing handwritten text-line segmentation methods can be categorized as top-down, bottom-up methods or machine learning methods. Top-down methods process the whole image and recursively subdivide it into smaller blocks to isolate the desired part [START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF]. They resort to projection profile, Hough transform, Gaussian filters and generally assume that gap between adjacent text-lines is significant and the textlines are reasonably straight, which may not be faithful in handwritten texts. They are also known to be sensitive to the topological changes in handwritten documents. Bottomup methods use simple rules, analyzing the geometric relationships between neighboring blocks such as the distance or the overlap. They have the merit to deal with noise problems and writing variation [START_REF] Belaïd | Segmentation of Ancient Arabic Documents[END_REF]. The common bottom-up method is based on the connected components [START_REF] Boulid | Arabic handwritten text line extraction using connected component analysis from a multi agent perspective[END_REF], [START_REF] Rajput | Text-Line Extraction from Handwritten Document images using Histogram and Connected Component Analysis[END_REF]. But, as most of top-down methods, bottom-up methods require prior knowledge about the documents, such as text-line inter-spaces, its orientation, etc. to guide the segmentation. Systems must therefore combine different image processing techniques to consider all possible features. Conversely, machine learning methods, which are free-segmentation, treat the image as a whole without any prior knowledge. During the last years the segmentation free methods, based on machine learning, has been used in different domains and achieved promising results. Some of the existing systems are end-to-end systems, with no further post or pre-processing [START_REF] Renton | Handwritten Text Line Segmentation Using Fully Convolutional Network[END_REF], [START_REF] Chen | Convolutional Neural Networks for Page Segmentation of Historical Document Images[END_REF], while others use deep learning like one step among other processing [START_REF] Grüning | A Two-Stage Method for Text Line Detection in Historical Documents[END_REF], [START_REF] Pastor-Pellicer | Complete System for Text Line Extraction Using Convolutional Neural Networks and Watershed Transform[END_REF].

As text-line and word segmentation tasks are often separated because of the differences in text-line and word features, the global processing for both tasks can be tough. Notice also that deep learning is much less used in word segmentation than in text-line segmentation. The commonly used methods for word segmentation are rather bottom-up methods, based on connected components analysis [START_REF] Louloudis | Text Line and Word Segmentation of Handwritten Documents[END_REF], structural feature extraction [START_REF] Aouadi | Word Extraction and Recognition in Arabic Handwritten Text[END_REF] or even both of them [START_REF] Elzobi | Off-line Handwritten Arabic Words Segmentation Based on Structural Features and Connected Components Analysis[END_REF]. They show interesting results on documents written in Latin or Germanic languages. On the other hand, deep learning based semantic segmentation methods have been providing state-of-the-art performance in the last few years. More specifically, these techniques have been successfully applied to image classification, segmentation, and detection tasks. One deep learning technique, U-Net, has become one of the most popular for these applications.

In this work, we propose a text-line segmentation system using an RU-net, and an end-to-end system for word segmentation, using a CNN (Convolutional Neural Network) followed by a BLSTM (bidirectional Long Short Term Memory) and a CTC function (Connectionist Temporal Classification) [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF] which is used to automatically learn the alignment between text-line images and the words in the transcription. Note that the proposed system can overcomes the problem of overlaps between adjacent text-lines, words or sub-words.

The paper is organized as follows: Section II gives an overview of some related works. Section III presents the proposed system for the text-line and word segmentation. Section IV reports the experimental results and section V concludes the work.

II. RELATED WORKS

A wide variety of text-line and word segmentation methods have been proposed in the literature. For text-line segmentation, Cohen & al. [11] used a bottom-up method. Their system starts by applying a multi-scale anisotropic second derivative of Gaussian filter bank to enhance text regions. It then applies a linear approximation to merge connected components of the same text-line using the K-Nearest Neighbors function. The authors proposed a generic system that may be used for any language, and obtained interesting results on Hebrew with 98% for text region detection.

In [START_REF] Arvanitopoulos | Seam Carving for Text Line Extraction on Color and Grayscale Historical Manuscripts[END_REF], the authors used rather a top-down method, called seam carving method. They first compute medial seams on the text-lines, using a projection profile matching approach. Then, they compute separating seam, using a modified version of seam carving procedure [START_REF] Avidan | Seam Carving for Content-aware Image Resizing[END_REF]. Their method showed good results on the Arabic dataset they used (99.9%), but coarse results on our dataset (see Figure 1).

Renton & al. [START_REF] Renton | Handwritten Text Line Segmentation Using Fully Convolutional Network[END_REF] used a modified version of the FCN (Fully-connected Convolutional neural Network) [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF], as deep learning based method for text-line segmentation,. The FCN, used for semantic segmentation and "skip" steps, between first and last layers, were introduced to avoid the coarse results due to many pooling layers. But, the authors in [START_REF] Renton | Handwritten Text Line Segmentation Using Fully Convolutional Network[END_REF] thought that this is not enough for the text-line segmentation task which should be more accurate. So, they proposed a new architecture where the layer convolution and max pooling is replaced by dilated convolutions. Their network has been trained on xheight labeling, reaching up to 75% of F-measure on the cBad dataset [START_REF] Diem | ICDAR 2017 Competition on Baseline Detection in Archival Documents (cBAD)[END_REF].

Grüning & al. [START_REF] Grüning | A Two-Stage Method for Text Line Detection in Historical Documents[END_REF] proposed a two steps method to segment text-lines. The first step is an ARU-net which is a U-net extended with an attention model (A) and a residual structure (R). Note that the U-net is a variant of FCN [START_REF] Ronneberger | U-Net: Convolutional Networks for Biomedical Image Segmentation[END_REF] which introduces shortcuts between layers of the same spatial dimension to have features from higher level and to reduce the vanishing gradient problem. The authors added residual blocks [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] to the U-net and an attention model that works simultaneously with the RU-net at multi-scale level. The output of the network is two maps: one related to the detected baselines, and another to the beginning and end of the text-lines. In the second step, a set of super pixels was calculated from the baseline map, then the state of these super pixels was estimated by computing their orientation and interline distance. Finally, using a Delaunay neighborhood system and calculating some functions like the projection profile, the data energy and the data cost, the super pixels clusters were found which represent the text-lines. Their system reaches 95% of good detection of text-lines on the whole cBad dataset, but the many processing and computations used, especially on the second stage, makes it a heavy procedure.

For word segmentation, Papavassiliou & al. [START_REF] Papavassiliou | Handwritten document image segmentation into text lines and words[END_REF] proposed an SVM-based gap metric for adjacent connected components at text-line level. Then, they used a threshold to classify gaps as "within" or "between" words. They tested their method on the datasets from the ICDAR 2007 Handwriting Segmentation Contest [20] and reached an F-measure of 93%.

Al Khateeb & al. [START_REF] Alkhateeb | Component-based Segmentation of Words from Handwritten Arabic Text[END_REF] applied a component-based method to segment words in Arabic handwritten texts. They analyzed the connected components, using the baselines and reached 85% of correct segmentation rate.

In [START_REF] Al-Dmour | Word Extraction from Arabic Handwritten Documents Based on Statistical Measures[END_REF], Al-Dmour & al. proposed a method based on two spatial measures: connected component length and gaps between them. Lengths are clustered to separate between the groups of letters, sub-words and words. Gaps are clustered to figure out whether the gap occurs "between words" or "within a word". These measures are clustered using a SOM (Self-Organizing Map) algorithm [START_REF] Kohonen | The self-organizing map[END_REF]. The method has been tested on the AHDB dataset [START_REF] Al-Ma'adeed | A data base for Arabic handwritten text recognition research[END_REF] and achieved 86.3% of correct segmentation rate.

III. PROPOSED SYSTEM

In segmentation methods, text-lines are generally represented by their baselines or bounding boxes. The x-height represents the area corresponding to the core of the text without ascenders and descenders and seems to be a suitable text-line representation for text recognition, while the baseline represents the main orientation of a text-line and is mainly used for the performance evaluation. An example of x-height and baseline labeling is provided in the Figure 2.

Inspired by the research of [START_REF] Grüning | A Two-Stage Method for Text Line Detection in Historical Documents[END_REF], we investigated the use of an RU-net for text-line segmentation, based on an x-height labeling, followed by a simple post-processing which allows baselines extraction. Note that U-Net is considered one of the standard CNN architectures for image classification tasks, when we need not only to define the whole image by its class but also to segment areas of an image by class, that is to produce a mask that will separate an image into several classes.

For word segmentation, we used a CNN followed by a BLSTM (forward and backward) and a CTC decoder at the end. The following subsections provide the architectural details of both text-line and word segmentation.

A. Text-line Segmentation

For text-line segmentation, we extracted the x-heights of text-lines, by the use of a ground truth that separates the input images into three classes: 1) background, 2) paragraphs and 3) text-lines x-heights in each paragraph, as shown in Figure 8(b). It is about a semantic segmentation problem where the objective is to achieve fine-grained inference by making dense predictions inferring labels for every pixel, so that each pixel is labeled with the class of its enclosing region. With the popularity of deep learning in recent years, this has been done using deep architectures, most often Convolutional Neural Networks (CNNs), which surpass other approaches, in Machine Learning, by a large margin in terms of accuracy and efficiency.

As Fully Convolutional Networks (FCNs) [START_REF] Long | Fully Convolutional Networks for Semantic Segmentation[END_REF] can efficiently learn to make dense predictions for per-pixel tasks like semantic segmentation, we proposed a FCN for the specific task of text-line segmentation. Note that FCN is an extension of the classical CNN. The main idea is to make the classical CNN take as input arbitrary-sized images. The restriction of CNNs to accept and produce labels only for specific sized inputs comes from the fully-connected layers which are fixed. Contrary to them, FCNs only have convolutional and pooling layers which give them the ability to make predictions on arbitrary-sized inputs. Thus, FCN structure can be described as a symmetric encoder/decoder where the encoder convolves and down samples the input via a number of convolution blocks and pooling. Then, the decoder re-samples the result by the same sub-sampling factor. Thus, the output will be a map with the same size as that of the input and where each pixel is assigned a probability of belonging to a class.

In this work, we used an RU-net as FCN model, extended with residual connections. Note that RU-net is a Recurrent Convolutional Neural Network model based on U-Net which [START_REF] Ronneberger | U-Net: Convolutional Networks for Biomedical Image Segmentation[END_REF] allows an easier combination of low level features and high level ones by introducing shortcuts between the same level blocks. The residual connections greatly reduce the vanishing gradient problem [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]. The proposed RU-Net architecture is illustrated in Figure 3 where the blue boxes denote multi-channel feature maps. The number of channels is provided on the top of each box while sizes are provided on the bottom-left of the boxes. The output of the RU-net is a prediction map with the same size of the input. The network is then followed by a post-processing to extract the baselines from the x-heights.

As it can be seen, we resized the input images to 720 pixels for the largest side and kept the same ratio between height and width for all the images to reduce the memory footprint. The encoder part of the proposed network is composed of three convolution and max-pooling blocks and a 4 th convolution layer, whereas the decoder part includes three convolution and un-pooling blocks. The network output consists of a map of three classes which will be dilated then eroded to smooth the border of x-heights and merge the over-segmented text-lines. Afterwards, polynomial regression is applied on the connected components, which are the x-heights here, to extract baselines.

1) Word Segmentation: For word segmentation, we firstly used a CNN to extract the most important features from the text-line images, extracted by the previous network. All images have a normalized size of 48×1600. Every convolutional block is followed by a batch normalization [START_REF] Ioffe | Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift[END_REF] that greatly reduces the vanishing gradient problem and makes the use of dropout unnecessary [START_REF] Li | Understanding the Disharmony between Dropout and Batch Normalization by Variance Shift[END_REF]. The output of the CNN is then sequentially passed to a BLSTM (Bidirectional Long Short Term Memory) having 100 neurons for each LSTM and followed by a CTC function [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF], as shown in Figure 4 and explained later.

Let us consider the two classes: word (1) and space (2). The provided ground truth is the text-lines Unicode transcription where each word is labeled 1 and each space 0, as displayed in Figure 5. The CTC decoder output is the found sequence wordspace. After the training step, the projection of the probabilities of class space (output of the BLSTM) is made on the image. a) BLSTM: LSTMs and GRUs (Gated Recurrent Units) are the best known and efficient RNNs (Recurrent Neural Networks). While LSTM has three gates (input, forget, output) and a memory cell, GRU has only two gates (reset and update) and no memory cell, thus less parameters. No study has proven which one is better [START_REF] Chung | Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling[END_REF], and it all depends on one's case, so the two networks have been tested for comparison. Figure 6 shows the difference between LSTM's and GRU's accuracy through epochs, and LSTMs showed the better results. On the other hand, the the bidirectional LSTM (BLSTM), instead of unidirectional one, show very good results as they can understand context better.

b) CTC function:: As there is no obvious alignment between the network's output and the ground truth's input, the CTC function is used to do that automatically. Graves & al. [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF] initially introduced the CTC to address the problem of alignment in speech recognition. Given the output of an RNN (a sequence of probabilities), the CTC loss function computes the probability of an alignment per each time-step using a dynamic programming algorithm. A beam search decoder is then used to extract the top paths, that are the paths with the greatest probability values.

IV. EXPERIMENTS & RESULTS

To evaluate the text-line and word segmentation performance, we carried experiments on KHATT [START_REF] Mahmoud | KHATT: Arabic Offline Handwritten Text Database[END_REF] database which is composed of handwritten Arabic images, written by 1000 persons from different age, gender and nationality. This database provides two sets of 2000 short handwritten paragraphs. The first set groups the images of the same paragraph, written twice by each person. The second set groups images of free paragraphs, each person having also written two paragraphs. The database also provides text-line segmentation and a Unicode transcription for each text-line (see Figure 7).

From the KHATT database, we labeled 325 paragraph images following the pattern shown in Figure 8(b): 175 for the training set and 150 for the testing set. For all our experiments, a learning rate of 10 -4 and the Adam Optimizer [START_REF] Kingma | Adam: A Method for Stochastic Optimization[END_REF] are used. The network has been trained for 100 epochs. Table I summarizes the parameter settings. To evaluate the baseline extraction, we used the metric in [START_REF] Grüning | READ-BAD: A New Dataset and Evaluation Scheme for Baseline Detection in Archival Documents[END_REF] and computed the F-measure. Table II displays results from some machine learning methods, used for text-line extraction and tested on KHATT dataset. The system, in [START_REF] Grüning | A Two-Stage Method for Text Line Detection in Historical Documents[END_REF], has not been tested, because the code of the second stage is not provided. The results in [START_REF] Renton | Handwritten Text Line Segmentation Using Fully Convolutional Network[END_REF] are evaluated on the x-heights, while those in [START_REF] Grüning | A Two-Stage Method for Text Line Detection in Historical Documents[END_REF] and RU-net are evaluated on the baselines. Obtained results are illustrated in Figure 8.

The proposed RU-net is shown to improve the text-line segmentation rate relative to methods mentioned above. Moreover, it is simple, requires less parameters and processing steps and trained on just a small set. A larger training set should lead to better results, but that needs a manual labeling of the images which could be the brake of this system.

For word segmentation, we used 5000 text-line images, 4800 for the training set and 200 for the testing set. A learning rate of 10 -4 with an Adam optimizer are also used. Table III summarizes the parameter settings.

Figure 9 gives the curve of loss and Figure 10 gives the Figure 11 shows an example of the obtained results and Table IV displays the F-measure values of our system and other works. Since the prediction is done on a down-scaled image, the output needs to be up-scaled to fit the original image. The F-measure was calculated manually by comparing the words on the transcription and the resulting segmentation. The most common segmentation errors are misplaced segmentations, like shown in Figure 12 where the segmentation is between sub-words.

Compared to some works on Arabic word segmentation, the proposed system achieves less good results. But, note that our system is a data-driven language independent word segmentation system. That is, no language dependent features are applied for tuning or improving the accuracy. In addition, it has has been trained and tested on KHATT database which involves more complex writings than IFN/ENIT and AHDB databases.

V. CONCLUSION

In this work, we proposed a novel approach to carry out the segmentation of Arabic manuscripts into text-lines and words, using deep learning. The proposed text-line segmentation system uses an RU-net to extract x-heights from text images, then a post-processing step extracts baselines. The word segmentation system uses a CNN with a BLSTM, then a CTC to find the alignment between the text-line transcription and the text-line image. The results show that text-line and word segmentation problems can be solved with no lexicons or language-dependent resources. The obtained results are promising, but still need to be improved, especially for

Fig. 1 .

 1 Fig. 1. Results of [6]: a) on their dataset(Al-Majid), b) on our dataset.

Fig. 2 .

 2 Fig. 2. X-height (green) and baseline (red) of a text-line.

Fig. 3 .Fig. 4 .

 34 Fig. 3. RU-Net architecture consisted with convolutional encoding and decoding units that take image as input and produce the segmentation feature maps with respective pixel classes

Fig. 5 .

 5 Fig. 5. Ground truth provided to the CTC (1: word; 0: space).

Fig. 6 .

 6 Fig. 6. Obtained results using LSTM and GRU.

Fig. 7 .

 7 Fig. 7. Example of a text-line and its transcription in the KHATT database.

  Image pre-processing : 325 paragraph images: 175 for training and 150 for testing. Images are normalized to a size of 720 px for the largest side. No further processing. RU-net: See Figure 3 for the detailed number of filters, kernels size and pool size. Strides : 2. Dropout : 0.5 (after every convolutional layer). Training settings: Initial weights: 1.0 for the 3 classes. Initial learning rate: 10 -4 . Optimizer : Adam. Initial number of epochs: 100.

Fig. 8 .

 8 Fig. 8. Results of text-line segmentation: a) the original image, b) the ground truth composed of three classes (background: red; paragraph: blue; x-height: green), c) the output of the RU-net, d) the final result after post-processing.

Fig. 9 .

 9 Fig. 9. Loss function.

Fig. 10 .

 10 Fig. 10. Accuracy measurements.

Fig. 11 .

 11 Fig.11. Results of the proposed system. The lower image is the output of the BLSTM for the class space (0), the 200 probabilities has been up-scaled ×8 to recover the original shape. The upper image is the segmented line after the projection of the probabilities.

Fig. 12 .

 12 Fig. 12. Example of wrong segmentations. The red box denotes one word and an over-segmentation is made on the sub-words.

TABLE I PARAMETER

 I SETTINGS OF THE TEXT-LINE SEGMENTATION ARCHITECTURE. THE 4 NEAREST GRAPH MODELING FURTHER CONNECTED THESE PRICES TO FORM A STRUCTURE.

	Architecture	Dataset	F-measure
	[29]	KHATT cBad	81% 75%
	[15]	cBad	95%
	RU-Net(ours) KHATT	96.71%

TABLE II RESULTS

 II FROM TEXT-LINE SEGMENTATION.

TABLE III PARAMETER

 III SETTINGS OF THE WORD SEGMENTATION ARCHITECTURE.

TABLE IV RESULTS

 IV FROM WORD SEGMENTATION.

word segmentation. As future work, we plan to improve this approach by the use of some post-processing to correct the wrong segmentation.