Student Member, IEEE, Jón Yuliya Tarabalka
email: yuliya.tarabalka@hyperinet.eu

Fellow, IEEE Atli Benediktsson

Senior Member, IEEE Jocelyn Chanussot
email: jocelyn.chanussot@gipsa-lab.grenoble-inp.fr

Senior Member, IEEE James C Tilton
email: james.c.tilton@nasa.gov

J A Benediktsson

Multiple Spectral-Spatial Classification Approach for Hyperspectral Data

Keywords: Classification, hyperspectral images, minimum spanning forest (MSF), multiple classifiers (MCs), segmentation

A new multiple-classifier approach for spectralspatial classification of hyperspectral images is proposed. Several classifiers are used independently to classify an image. For every pixel, if all the classifiers have assigned this pixel to the same class, the pixel is kept as a marker, i.e., a seed of the spatial region with a corresponding class label. We propose to use spectral-spatial classifiers at the preliminary step of the marker-selection procedure, each of them combining the results of a pixelwise classification and a segmentation map. Different segmentation methods based on dissimilar principles lead to different classification results. Furthermore, a minimum spanning forest is built, where each tree is rooted on a classification-driven marker and forms a region in the spectral-spatial classification map. Experimental results are presented for two hyperspectral airborne images. The proposed method significantly improves classification accuracies when compared with previously proposed classification techniques.

I. INTRODUCTION

H YPERSPECTRAL imaging is a relatively recent tech- nique in remote sensing. Acquired remotely by airborne or spaceborne sensors, hyperspectral data are composed of hundreds of spatially coregistered images corresponding to different spectral channels [START_REF] Chang | Hyperspectral Data Exploitation: Theory and Applications[END_REF], [START_REF] Green | Imaging spectroscopy and the Airborne Visible Infrared Imaging Spectrometer (AVIRIS)[END_REF]. Fig. 1 shows the structure of a hyperspectral image. Every pixel is presented as a B-dimensional feature vector across the wavelength dimension, called the spectrum of the material in this pixel. This rich information in every spatial location increases the capability to distinguish different physical materials. Thus, hyperspectral imagery opens new perspectives for image classification, which is an important task for a wide variety of applications (precision agriculture, monitoring and management of the environment, and security issues).

However, such a large number of spectral channels, usually coupled with limited availability of reference data, 1 present challenges to image analysis. While pixelwise classification techniques process each pixel independently without considering information about spatial structures [START_REF] Landgrebe | Signal Theory Methods in Multispectral Remote Sensing[END_REF]- [START_REF] Yang | A nonparametric feature extraction and its application to nearest neighbor classification for hyperspectral image data[END_REF], further improvement of classification results can be achieved by considering spatial dependences between pixels, i.e., by performing spectral-spatial classification [START_REF] Kettig | Classification of multispectral image data by extraction and classification of homogeneous objects[END_REF]- [START_REF] Tarabalka | Classification of hyperspectral data using support vector machines and adaptive neighborhoods[END_REF].

Segmentation techniques, partitioning an image into homogeneous regions with respect to some criterion of interest (called homogeneity criterion, e.g., intensity or texture), are powerful tools for defining spatial dependences [START_REF] Gonzalez | Digital Image Processing[END_REF]. In previous works, we have distinguished spatial structures in the hyperspectral image by performing unsupervised segmentation [START_REF] Tarabalka | Classification of hyperspectral data using support vector machines and adaptive neighborhoods[END_REF], [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF], [START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF]. Watershed, partitional clustering, and hierarchical segmentation (HSEG) techniques have been used for this purpose. Segmentation and pixelwise classification were applied independently; then, results were combined using a majority-voting rule (see Fig. 2). Thus, every region from a segmentation map was considered as an adaptive homogeneous neighborhood for all the pixels within this region. The described technique led to a significant improvement of classification accuracies and provided more homogeneous classification maps, when compared with classification techniques using local neighborhoods in order to include spatial information into a classifier.

An alternative way to get accurate segmentation results consists in performing a marker-controlled segmentation [START_REF] Gonzalez | Digital Image Processing[END_REF], [START_REF] Soille | Morphological Image Analysis[END_REF]. The idea behind this approach is to select, for every spatial object, one or several pixels belonging to this object (called a region seed, or a marker of the corresponding region) and to grow regions from the selected seeds so that every region in the resulting segmentation map is associated with one region seed. The markers of regions can be chosen either manually or automatically. Recently, we have proposed to use probability estimates obtained by the pixelwise support vector machine (SVM) classification in order to select the most reliable classified pixels as markers, i.e., seeds of spatial regions [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. Furthermore, image pixels were grouped into a minimum spanning forest (MSF) where each tree was rooted on a classificationderived marker. The decision to connect a pixel, which is not yet in the forest, to one of the trees in the forest was based on its similarity to one of the adjacent pixels already belonging to the forest. By assigning the class of each marker to all the pixels within the region grown from this marker, a spectral-spatial classification map was obtained. The described technique led to a significant improvement of classification accuracies when compared with previously proposed methods. The drawback of this method is that the choice of markers strongly depends on the performances of the selected pixelwise classifier (e.g., the SVM classifier in our previous work [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]).

In this paper, we aim to mitigate the dependence of the marker-selection procedure from the choice of a pixelwise classifier. This can be achieved by using not a single classification algorithm for marker selection but an ensemble of classifiers, i.e., multiple classifiers (MCs). For this purpose, several individual classifiers must be chosen and combined within one system in such a way that the complementary benefits of each classifier are used, while their weaknesses are avoided.

In this paper, a new marker-selection method based on an MC system is proposed. Several classifiers are used independently to classify an image. Furthermore, a marker map is constructed by selecting the pixels assigned by all the classifiers to the same class. We propose to use spectral-spatial classifiers in the preliminary step of the marker-selection procedure, each of them combining the results of a pixelwise classification and one of the unsupervised segmentation techniques (see Fig. 2). By using spectral-spatial classifiers in this step, spatial context in the image is taken into account, and classification maps are more accurate when compared with pixelwise classification maps. This leads to more accurate marker-selection results. The proposed marker-selection method is incorporated into a new multiple spectral-spatial classification (MSSC) scheme (MSSC-MSF) based on the construction of an MSF from region markers (see Fig. 3).

In order to assess the importance of spectral-spatial approaches for marker selection, we have also implemented a multiple classification scheme (MC-MSF). Here, spectralspatial classification maps are replaced by the maps obtained using pixelwise classification techniques. Finally, a marker map is computed, and an MSF from the selected markers is constructed.

Although the classification approach proposed in this paper has been designed for hyperspectral data, the method is general and can be applied for other types of data as well. Two hyperspectral airborne images are used to demonstrate experimental results: an image recorded by the reflective optics system imaging spectrometer (ROSIS) over the University of Pavia, Italy, and an Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) image acquired over Northwestern Indiana's Indian Pines site [START_REF] Tadjudin | Covariance estimation with limited training samples[END_REF]. This paper is organized as follows. In the next section, the MC approach is briefly discussed. Section III describes the proposed classification scheme. Experimental results are discussed in Section IV. Finally, conclusions are drawn in Section V.

II. MC APPROACH

The traditional approach for a pattern recognition problem is to search for the individual algorithm giving the best possible classification performances. However, in many cases, the classification accuracy can be improved by using an ensemble of classifiers, or multiple classifiers. This is due to the fact that, although one of the classification algorithms would yield the best performance, the sets of pixels (patterns, in general) misclassified by the different algorithms would not necessarily overlap. Thus, the aim of an MC system is to determine an efficient combination method that makes use of the complementary benefits of each classifier while tackling the individual drawbacks [START_REF] Xu | Methods of combining multiple classifiers and their applications to handwriting recognition[END_REF]- [START_REF] Briem | Multiple classifiers applied to multisource remote sensing data[END_REF].

A schematic representation of an MC system is shown in Fig. 4. An important issue for an efficient MC system is that the individual classifiers should be independent. More precisely, the classifiers should not agree with each other when they misclassify a pixel [START_REF] Kittler | On combining classifiers[END_REF]. The complementary properties of the different classifiers selected for the MC system should ensure, to a certain extent, this requirement.

Another important issue is the rule for combining the individual classifiers (i.e., combination function). The individual classifier outputs, such as class labels and possible posterior probabilities, are typically combined by voting rules, belief functions, statistical techniques, the Dempster-Shafer evidence theory, and other schemes [START_REF] Xu | Methods of combining multiple classifiers and their applications to handwriting recognition[END_REF]. For a given pixel, if all the classifiers agree on the same class k, the evident combination rule consists in assigning this pixel to the class k in the final classification map. On the other side, when individual classifiers disagree in assigning the given pixel, the procedure of final decision making is not that straightforward, and different combination functions may yield different results. A typical result of the MC system is a final classification map where each pixel has a unique class label. This type of MC systems has been previously used for remote-sensing image classification [START_REF] Briem | Multiple classifiers applied to multisource remote sensing data[END_REF]- [START_REF] Tzeng | Remote sensing images classification/data fusion using distance weighted multiple classifiers systems[END_REF].

In this paper, we propose to address the combination-rule issue in the following way: According to the exclusionary rule, only the pixels where all the classifiers agree, i.e., the most reliable pixels, are kept in the classification map. The rest of the pixels are further classified by constructing an MSF rooted on the "reliable" pixels, i.e., by incorporating the spatial information into classification.

Going back to the first issue for designing an MC system, different individual classifiers must be chosen. For instance, standard pixelwise classification algorithms can be used for this purpose, such as SVM, maximum likelihood (ML), and k-nearest neighborhood (k-NN) methods (parametric and nonparametric techniques based on different principles). We have

III. PROPOSED CLASSIFICATION SCHEME

The flowchart of the proposed MSSC-MSF classification method is shown in Fig. 3. At the input, a B-band hyperspectral image is given, which can be considered as a set of n pixel vectors X = {x j ∈ R B , j = 1, 2, . . . , n}. Classification consists in assigning each pixel to one of the K classes of interest. In the following, each step of the proposed procedure is described.

Segmentation can be defined as an exhaustive partitioning of the input image into regions, each of which is considered to be homogeneous with respect to some criterion of interest. We have investigated the use of three techniques for hyperspectral image segmentation, as described hereafter.

A. Watershed Segmentation

Watershed transformation is a powerful morphological approach to image segmentation that combines region growing and edge detection. The watershed is usually applied to the gradient function, and it divides an image into regions so that each region is associated with one minimum of the gradient image [START_REF] Beucher | Use of watersheds in contour detection[END_REF].

The extension of a watershed technique to the case of hyperspectral images has been investigated in [START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF] and [START_REF] Noyel | Morphological segmentation of hyperspectral images[END_REF]. In this paper, we present watershed results obtained by the scheme we proposed and described in [START_REF] Tarabalka | Segmentation and classification of hyperspectral data using watershed[END_REF]: First, a one-band robust color morphological gradient (CMG) (RCMG) [START_REF] Evans | A morphological gradient approach to color edge detection[END_REF] for the hyperspectral image is computed.

For each pixel vector x p , let χ = [x 1 p , x 2 p , . . . , x e p ] be a set of e vectors contained within a structuring element E (i.e., the pixel x p itself and e -1 neighboring pixels). A 3 × 3 square structuring element with the origin at its center is typically used. The CMG, using the Euclidean distance, is computed as

CMG E (x p ) = max i,j∈χ x i p -x j p 2 (1)
i.e., the maximum of the distances between all pairs of vectors in the set χ. One of the drawbacks of the CMG is that it is very sensitive to noise. To overcome the problem of outliers, the RCMG has been proposed [START_REF] Evans | A morphological gradient approach to color edge detection[END_REF]. The scheme to make a CMG robust consists of removing the two pixels that are furthest apart and then finding the CMG of the remaining pixels. This process can be repeated several times until a good estimate of the gradient is obtained. Thus, the RCMG, using the Euclidean distance, can be defined as

RCMG E (x p ) = max i,j∈[χ-REM r ] x i p -x j p 2 (2)
where REM r is a set of r vector pairs removed. If E is a 3 × 3 square structuring element, r = 1 is recommended [START_REF] Evans | A morphological gradient approach to color edge detection[END_REF]. Furthermore, watershed transformation is applied on the gradient image using a standard algorithm [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF]. As a result, the image is partitioned into a set of regions and one subset of watershed pixels, i.e., pixels situated on the borders between regions. Finally, every watershed pixel is assigned to the neighboring region with the "closest" median 2 (the distance between the vector median of this region and the watershed pixel is minimal).

B. Segmentation by EM

The expectation maximization (EM) algorithm for the Gaussian mixture resolving belongs to the group of partitionalclustering techniques [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF], [START_REF] Masson | SEM algorithm and unsupervised segmentation of satellite images[END_REF]. The use of partitional clustering for hyperspectral image segmentation has been discussed in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF]. Clustering aims at finding groups of spectrally similar pixels. We assume that pixels belonging to the same cluster are drawn from a multivariate Gaussian probability distribution. Each image pixel can be statistically modeled by the following probability density function:

p(x) = C c=1 ω c φ c (xμ c , Σ c ) ( 3
)
where C is the number of clusters, ω c ∈ [0, 1] is the mixing proportion (weight) of cluster c with C c=1 ω c = 1, and φ(μ, Σ) is the multivariate Gaussian density with mean μ and covariance matrix Σ

φ c (xμ c , Σ c ) = 1 (2π) B/2 1 |Σ c | 1/2 exp - 1 2 (x -μ c ) T Σ -1 c (x -μ c ) . ( 4
)
2 A standard vector median [START_REF] Astola | Vector median filters[END_REF] for the region

S = {s j ∈ R B , j = 1, 2, . . . , l} is defined as s V M = arg min s∈S { l j=1 s -s j 1 }.
The parameters of the distributions ψ = {C, ω c , μ c , Σ c ; c = 1, 2, . . . , C} are estimated by the EM algorithm, as described in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF]. An upper bound on the number of clusters, which is a required input parameter, is recommended to be chosen as slightly superior to the number of classes.

When the algorithm converges, the partitioning of the set of image pixels into clusters is obtained. However, as no spatial information is used during the clustering procedure, pixels with the same cluster label can form a connected spatial region or can belong to disjoint regions. In order to obtain a segmentation map, a connected component-labeling algorithm [START_REF] Shapiro | Computer Vision[END_REF] is applied to the output image partitioning obtained by clustering.

The total number of parameters to be estimated by the EM algorithm is P = (B(B + 1)/2 + B + 1)C + 1, where B is a dimensionality of feature vectors. If the value of B is large, P may be quite a large number. This may cause a problem of the covariance-matrix singularity or inaccurate parameter estimation results. In order to avoid these problems, we propose to previously apply a feature reduction using the method of piecewise constant function approximations (PCFAs) [START_REF] Jensen | Fast hyperspectral feature reduction using piecewise constant function approximations[END_REF], which has shown good performances for hyperspectral data feature extraction.

C. RHSEG Segmentation

The HSEG algorithm is a segmentation technique based on iterative hierarchical stepwise optimization region-growing method. Furthermore, it provides a possibility of merging nonadjacent regions by spectral clustering [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader User's Manual (Version 1.40)[END_REF].

The following outline of the HSEG algorithm is based on the description given in [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader User's Manual (Version 1.40)[END_REF] and [START_REF] Tilton | Analysis of hierarchically related image segmentations[END_REF] 1) Initialize the segmentation by assigning for each pixel a region label. If a presegmentation is provided, label each pixel according to the presegmentation. Otherwise, label each pixel as a separate region. 2) Calculate the dissimilarity criterion value between all pairs of spatially adjacent regions. 3) Find the smallest dissimilarity criterion value dissim_val and set thresh_val equal to it. Then, merge all pairs of spatially adjacent regions with dissim_val = thresh_val. 4) If a parameter S wght > 0.0, merge all pairs of spatially nonadjacent regions with dissim_val ≤ S wght • thresh_val. 5) If convergence is not achieved, go to step 2).

In order to reduce computational demands, a recursive divide-and-conquer approximation of HSEG (RHSEG) has been developed. The NASA Goddard RHSEG software provides an efficient implementation of the RHSEG algorithm.

When determining most similar pair of regions, we propose to choose the standard Spectral Angle Mapper (SAM) between the region mean vectors and as a dissimilarity criterion [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader User's Manual (Version 1.40)[END_REF]. The SAM measure between u i and u j (u i , u j ∈ R B ) determines the spectral similarity between two vectors by computing the angle between them. It is defined as

SAM(u i , u j ) = arccos ⎛ ⎜ ⎝ B b=1 u ib u jb B b=1 u 2 ib 1/2 B b=1 u 2 jb 1/2 ⎞ ⎟ ⎠ .
(

) 5
The optional parameter S wght tunes the relative importance of spectral clustering versus region growing. If S wght = 0.0, only merging of spatially adjacent regions is performed. If 0.0 < S wght ≤ 1.0, merging between spatially adjacent regions is favored compared with merging of spatially nonadjacent regions by a factor of 1.0/S wght . As discussed in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral images using segmentation-derived adaptive neighborhoods[END_REF], the optimal parameter S wght can be chosen based on a priori knowledge about information classes contained in the image. If some classes have very similar spectral responses, we recommended to choose S wght = 0.0 or close to this value. 3 Otherwise, we recommend increasing the possibility of merging spatially nonadjacent regions. If S wght > 0.0, labeling of connected components has to be applied after RHSEG in order to obtain a segmentation map where each spatially connected component has a unique label.

RHSEG provides as output a hierarchical sequence of image partitions. In this sequence, a particular object can be represented by several regions at finer levels of details and can be assimilated with other objects in one region at coarser levels of details. This hierarchical sequence allows flexibility in choosing the appropriate level of detail for the segmentation map. When training data are available, it is a simple process to quantitatively evaluate the segmentation results at each hierarchical level versus the training data to select the appropriate level of detail. Otherwise, an appropriate level of segmentation detail can be chosen interactively with the program HSEGViewer [START_REF] Tilton | HSEG/RHSEG, HSEGViewer and HSEGReader User's Manual (Version 1.40)[END_REF], or an automated method, tailored to the application, can be developed, such as that explored in [START_REF] Plaza | Automated selection of results in hierarchical segmentations of remotely sensed hyperspectral images[END_REF].

D. Pixelwise Classification

Independent of the previous steps, a pixelwise classification of the hyperspectral image is performed. We propose to use an SVM classifier for this purpose. Other pixelwise classifiers could be used. However, SVMs perform extremely well in classifying high-dimensional data when a limited number of training samples are available [START_REF] Camps-Valls | Kernel-based methods for hyperspectral image classification[END_REF], [START_REF] Licciardi | Decision fusion for the classification of hyperspectral data: Outcome of the 2008 GRS-S data fusion contest[END_REF]. We refer the reader to [START_REF] Camps-Valls | Kernel-based methods for hyperspectral image classification[END_REF] and [START_REF] Vapnik | Statistical Learning Theory[END_REF] for details on SVM technique. This step results in a classification map where each pixel has a unique class label.

E. Majority Voting Within Segmentation Regions

Each of the obtained unsupervised segmentation maps is combined with the pixelwise classification map using the majority-voting principle: For every region in the segmentation map, all the pixels are assigned to the most frequent class within this region (see an illustrative example in Fig. 2). Thus, q segmentation maps combined with the pixelwise classification map result in q spectral-spatial classification maps (since we propose to use three different segmentation techniques, in this particular case, q = 3).

F. Marker Selection

This step consists of computing a map of markers using spectral-spatial classification maps from the previous step and the exclusionary rule: For every pixel, if all the classifiers agree, the pixel is kept as a marker with a corresponding class label. The resulting map of m markers contains the most reliably classified pixels.

G. Construction of a MSF

In the final step, image pixels are grouped into an MSF rooted on the selected markers [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF]. Each pixel is considered as a vertex v ∈ V of an undirected graph G = (V, E, W ), where V and E are the sets of vertices and edges, respectively, and W is a mapping of the set of the edges E into R + . Each edge e i,j ∈ E of this graph connects a couple of vertices i and j corresponding to the neighboring pixels. Furthermore, a weight w i,j is assigned to each edge e i,j , which indicates the degree of dissimilarity between two vertices (i.e., two corresponding pixels) connected by this edge. We propose to use an eightneighborhood and the SAM measure for computing the weights of edges, as described in [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF].

Given a graph G = (V, E, W ), the MSF rooted on a set of m distinct vertices {t 1 , . . . , t m } consists in finding a spanning forest F * = (V, E F * ) of G such that each distinct tree of F * is grown from one root t i , and the sum of the edges' weights of F * is minimal [START_REF] Stawiaski | Mathematical morphology and graphs: Application to interactive medical image segmentation[END_REF] F * ∈ arg min

F ∈SF ⎧ ⎨ ⎩ e i,j ∈E F w i,j ⎫ ⎬ ⎭ ( 6
)
where SF is a set of all spanning forests of G rooted on {t 1 , . . . , t m }.

Algorithm 1 Prim's Algorithm

Require:

Connected graph G = (V, E, W ) Ensure: Tree T * = (V * , E * , W * ) V * = {v}, v is an arbitrary vertex from V while V * = V do Choose edge e i,j ∈ E with minimal weight such that i ∈ V * and j / ∈ V * V * = V * ∪ {j} E * = E * ∪ {e i,j } end while
In order to obtain the MSF rooted on m markers corresponding to the vertices t i , i = 1, . . . , m, an additional root vertex r is added and is connected by the null-weight edges to the vertices t i . The minimum spanning tree of the constructed graph induces an MSF in G, where each tree is grown on a Prim's algorithm can be used for building the MSF (see Algorithm 1) [START_REF] Prim | Shortest connection networks and some generalizations[END_REF]. The efficient implementation of the algorithm using a binary min-heap is possible [START_REF] Cormen | Introduction to Algorithms[END_REF]; the resulting time complexity of the algorithm is O(|E| log |V |). Finally, a spectral-spatial classification map is obtained by assigning the class of each marker to all the pixels grown from this marker.

IV. EXPERIMENTAL RESULTS AND DISCUSSION

Two different hyperspectral images were used for the experiments with different contexts (one urban area and one agricultural area) and recorded by different sensors (ROSIS and AVIRIS). These data sets and the corresponding results are discussed in the next two sections.

A. Classification of the University of Pavia Image

The University of Pavia image was recorded by the ROSIS optical sensor over the urban area of the University of Pavia, Italy. The image is 610 × 340 pixels with a spatial resolution of 1.3 m/pixel. The number of data channels in the acquired image is 115 (with a spectral range from 0.43 to 0.86 μm). The 12 most noisy channels have been removed, and the remaining 103 bands were used for the experiments. Nine classes of interest are considered, which are detailed in Table I. Fig. 5 shows a three-band false color image and the reference data. The training and test sets are composed of 3921 and 40 002 pixels, respectively. More information about the image, with the number of training and test samples for each class can be found in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF].

The segmentation of the considered image was performed using the three different techniques discussed in the previous section. For the EM algorithm, the maximum number of clusters was chosen to be equal to ten (typically slightly superior to the number of classes). Before applying the EM technique, a feature extraction on the original 103-band image was applied using the method of PCFA [START_REF] Jensen | Fast hyperspectral feature reduction using piecewise constant function approximations[END_REF] to get a ten-band image Y UP . Pixels from the training set were used for selecting features. The method produced an averaging of the following groups of adjacent spectral channels: 1-4, 5-10, 11-24, 25-35, 36-43, 44-68, 69-72, 73-75, 76-79, and 80-103.

For the RHSEG algorithm, we chose S wght = 0.1 since the image of this urban area contains classes with mostly dissimilar spectral responses. A segmentation map at an appropriate level of segmentation detail was chosen interactively with the program HSEGViewer. The obtained watershed, EM, and RHSEG segmentation maps contained 11 802, 22 549, and 7575 regions, respectively.

The multiclass pairwise SVM classification, with the Gaussian radial basis function (RBF) kernel, of the original image was performed with the parameters chosen by fivefold cross validation: C = 128 and γ = 0.125. The results of the pixelwise classification were combined with the segmentation results using the majority voting approach. Finally, the marker selection (see Fig. 5(g); 132 521, i.e., 64% of pixels were selected as markers) and the construction of an MSF were performed, resulting in the MSSC-MSF spectral-spatial classification map shown in Fig. 5(h).

Table I summarizes the global and class-specific accuracies of the pixelwise SVM, segmentation plus majority voting (WH + MV, EM + MV, RHSEG + MV for three segmentation techniques, respectively), and the proposed MSSC-MSF classification methods. The following measures of accuracy were used: Overall accuracy [(OA) is the percentage of correctly classified pixels], average accuracy [(AA) is the mean of class-specific accuracies, i.e., the percentage of correctly classified pixels for each class], and kappa coefficient (κ is the percentage of agreement, i.e., correctly classified pixels, corrected by the number of agreements that would be expected purely by chance [START_REF] Richards | Remote Sensing Digital Image Analysis: An Introduction[END_REF]). In order to compare the performances of the proposed technique with the previously proposed methods, we have also included results of the well-known ECHO spatial classifier [START_REF] Kettig | Classification of multispectral image data by extraction and classification of homogeneous objects[END_REF], as well as the results obtained using the construction of an MSF from the probabilistic SVM-derived markers followed by majority voting within connected regions (SVMMSF + MV) [START_REF] Tarabalka | Segmentation and classification of hyperspectral images using minimum spanning forest grown from automatically selected markers[END_REF].

In addition, we assessed the importance of spectral-spatial approaches for marker selection. For this purpose we replaced the WH + MV, EM + MV, and RHSEG + MV classification maps by three maps obtained using standard pixelwise classification techniques (we call this modified scheme an MC-MSF classification method). SVM, ML, and three-nearest neighborhood (3-NN, using the SAM distance) methods were used for this purpose. The ML and the 3-NN techniques were applied on the ten-band image Y UP feature vectors. The accuracies of the modified MC-MSF classification as well as the pixelwise classification results are given in Table I. As can be seen from Table I, the SVM method gives the highest accuracies among all the pixelwise classification techniques. All the spectral-spatial approaches yield higher classification accuracies when compared with pixelwise methods. The proposed MC approach for marker selection improves the accuracies when compared with those obtained by classification techniques used in the preliminary step of the markerselection procedure, both for the MC-MSF and MSSC-MSF methods. The best global and the best class-specific accuracies for most classes are achieved by applying the proposed MSSC-MSF method. According to the results of the McNemar's test [START_REF] Foody | Thematic map comparison: Evaluating the statistical significance of differences in classification accuracy[END_REF], the MSSC-MSF classification map is significantly more accurate when compared with those obtained by other classification approaches, using 5% level of significance. In this case, the OA is improved by 16.9 percentage points and the AA is improved by 10.3 percentage points when compared with the SVM classification. All the class-specific accuracies are higher than 96%. Only the accuracy for the class shadows, representing small spatial structures, is slightly reduced when compared with the SVM results (the drawback of applying spectral-spatial classification to small structures was discussed, for instance, in [START_REF] Tarabalka | Spectral-spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF]). The MSSC-MSF classification accuracies are much higher than the MC-MSF accuracies.

Furthermore, the presented classification accuracies are higher than all previous results we have found in the literature for the same data.

Fig. 5 shows the MC-MSF and MSSC-MSF classification maps, as well as the SVM, ECHO, and SVMMSF + MV classification maps given for comparison. In Fig. 5(g) [MSSC-MSF marker map], it can be seen that the marker pixels, i.e., the most reliable classified pixels, are typically located at the center of spatial structures, while borders of structures are under a high risk of being misclassified. The MSSC-MSF classification map [see Fig. 5(h)] contains much more homogeneous regions when compared with the maps obtained by other pixelwise and spectral-spatial approaches. These results prove the importance of the use of MC systems and spatial information throughout the classification procedure.

B. Classification of the Indian Pines Image

The proposed scheme was also tested on the Indian Pines image of a vegetation area, acquired by the AVIRIS sensor over the Indian Pines site in Northwestern Indiana. The image has spatial dimensions of 145 by 145 pixels, with a spatial resolution of 20 m/pixel. Twenty water absorption bands (104-108, 150-163, and 220) have been removed [START_REF] Tadjudin | Covariance estimation with limited training samples[END_REF], and a 200-band image was used for the experiments. The reference data contain sixteen classes of interest, which represent mostly different types of crops and are detailed in Table II. A threeband false-color image and the reference data are shown in Fig. 6. We have randomly chosen 50 samples for each class from the reference data as training samples, except for classes "alfalfa,""grass/pasture mowed," and "oats." These classes contain a small number of samples in the reference data. Therefore, only 15 samples for each of these classes were chosen randomly to be used as training samples. The remaining samples composed the test set.

Segmentation of the Indian Pines image was performed using the three discussed techniques. For the EM technique, the upper bound on the number of classes was chosen to be equal to 17, and a feature reduction has been previously applied using the method of PCFA [START_REF] Jensen | Fast hyperspectral feature reduction using piecewise constant function approximations[END_REF] to get a ten-band image Y IN . The following groups of bands were averaged: 1-18, 19-36, 37-53, 54-57, 58-61, 62-75, 76-81, 82-99, 100-140, and 141-200.

Since some classes have very similar spectral responses in the Indian Pines image (for instance, three classes of corn and three classes of soybeans), we set S wght = 0.0 for the RHSEG method. A segmentation map at the relevant level of hierarchy was chosen with the program HSEGViewer. The resulting watershed, EM, and RHSEG segmentation maps contained 1277, 3832, and 823 regions, respectively.

A pixelwise classification on the 200-band image was performed using the multiclass one versus one SVM classifier with the Gaussian RBF kernel. The optimal parameters C and γ were chosen by fivefold cross validation: C = 128 and γ = 2 -6 . After the segmentation results were combined with the pixelwise classification map, the marker selection (14 409, i.e., 68% of the pixels, were selected as markers) and the MSF construction were applied, as described in the previous section.

Table II gives the global and class-specific accuracies of the pixelwise SVM segmentation, followed by majority voting and the proposed MSSC-MSF classification techniques. The performances of the proposed approach are compared with those obtained by the ECHO and SVMMSF + MV methods, as described in the previous section. Finally, the MC-MSF classification was applied in the same way as for the previous data set.

From the table, similar conclusions as with the previous data set can be derived. The SVM classification yields the best accuracies among all the applied pixelwise methods. The spectral-spatial classification accuracies are always higher when compared with the pixelwise accuracies. The proposed MC method succeeds in combining several classification results for further improvement of accuracies. The MSSC-MSF yields the best OA, kappa coefficient, and most of the classspecific accuracies. The AA is only slightly (nonsignificantly) lower when compared with that obtained by the recently proposed SVMMSF + MV method. Following the results of the McNemar's test, the MSSC-MSF and SVMMSF + MV accuracies are not significantly different using 5% level of significance. These two techniques significantly outperform other classification approaches.

Fig. 6 shows the SVM, MC-MSF, MSSC-MSF, and SVMMSF + MV classification maps. As can be seen, the MSSC-MSF map contains much more homogeneous spatial structures when compared with the SVM and MC-MSF maps and is comparable with the SVMMSF + MV map. Again, spectral-spatial markerbased techniques yielded the most accurate classification maps.

Although for the Indian Pines image, the MSSC-MSF and SVMMSF + MV methods yield similar results, here, we stress the advantages of the proposed MSSC-MSF approach versus the previous one for spectral-spatial classification.

1) Robustness: While for the SVMMSF + MV method, the marker selection strongly depends on the performances of the selected pixelwise classifier, the MC approach mitigates this dependence. Since in the MSSC-MSF scheme, different segmentation maps are combined with one pixelwise classification map, the choice of the classifier is also important. However, if in the SVMMSF + MV method, a pixel was wrongly classified with a high probability, it will yield a wrong marker. In the new approach, the majority voting within segmentation regions can correct the misclassification result for a particular pixel before the marker map is built. 2) Computational Complexity: In the SVMMSF + MV method, the probabilistic pixelwise SVM classification part is the most time consuming [START_REF] Cristianini | Support Vector Machines and Other Kernel-Based Learning Methods[END_REF]. In the MSSC-MSF approach, SVM classification is performed without the computation of probability estimates; this reduces the pixelwise classification-part execution time. The unsupervised segmentation techniques are much less time consuming when compared with the SVM classification. Furthermore, their efficient implementations are available, and they can be executed in parallel at the same time with the SVM classification. As a conclusion, the efficient implementation of the proposed MSSC-MSF approach is possible, which would run faster than the previously proposed MSSC-MSF method.

V. CONCLUSION Hyperspectral sensors capture images in hundreds of narrow spectral channels. The detailed spectral signatures for each spatial location provide rich information about an image scene, leading to better discrimination between physical materials and objects. However, interpretation of these high-dimensional signatures is a challenging task. Although pixelwise classification techniques have given high classification accuracies when dealing with hyperspectral data, the incorporation of the spatial context into classification procedures yields further improvement of the accuracies.

In this paper, a new method for spectral-spatial classification of hyperspectral images based on multiple classifiers has been proposed. First, a marker map is constructed by selecting the pixels assigned by several spectral-spatial classifiers to the same class. This ensures a robust and reliable selection. Then, an MSF rooted on the selected markers is built. Experimental results demonstrated that the proposed method improves classification accuracies, when compared with previously proposed classification schemes, and provides classification maps with homogeneous regions.

In conclusion, the proposed methodology succeeded in taking advantage of multiple classifiers and the spatial and spectral information simultaneously for accurate hyperspectral image classification. The method yields accurate results for different data sets, i.e., data containing large spatial structures and/or small and complex structures, with spectrally dissimilar and/or spectrally confusing classes. Furthermore, its efficient implementation is possible.

While performing particularly well for classification of homogeneous regions, the proposed approach has a drawback common to most of spectral-spatial techniques: It produces a smoother classification map when compared with pixelwise ones and therefore, it risks impairing results near the borders between regions (where mixed pixels4 are often encountered) or in textured areas. Spectral unmixing techniques [START_REF] Keshava | A survey of spectral unmixing algorithms[END_REF] can be used for accurate analysis of region borders, while segmentation in the sense of texture [START_REF] Rouquet | Region-based segmentation of textured images[END_REF] can be applied for textured regions.

In the future, we will further explore the integration of spectral-spatial approaches in MC systems for accurate and robust classification of hyperspectral images. Since the incorporation of the spatial information in classification significantly improves accuracies, it is of interest to further investigate performances of the proposed spectral-spatial approaches when a very limited number of training samples are available.

Fig. 1 .

 1 Fig. 1. Structure of a hyperspectral image.

Fig. 2 .

 2 Fig. 2. Example of spectral-spatial classification using majority voting within segmentation regions.

Fig. 3 .

 3 Fig. 3. Flowchart of the proposed MSSC-MSF classification scheme.

Fig. 4 .

 4 Fig. 4. Schematic diagram of an MC system.

  used these individual techniques in the MC-MSF classification scheme. Furthermore, we propose to use spectral-spatial classifiers as individual classifiers for the MC system (MSSC-MSF classification scheme), each of them combining the results of a pixelwise classification and one of the unsupervised segmentation techniques. Different segmentation methods based on dissimilar principles lead to different classification results. The use of spectral-spatial classifiers yields more accurate classification maps when compared with those obtained by performing pixelwise classification.

Fig. 5 .

 5 Fig. 5. University of Pavia image. (a) Three-band color composite. (b) Reference data: Asphalt, meadows, gravel, trees, metal sheets, bare soil, bitumen, bricks, and shadows. (c) SVM pixelwise classification map. (d) ECHO classification map. (e) SVMMSF + MV classification map. (f) MC-MSF classification map. (g) MSSC-MSF marker map. (h) MSSC-MSF classification map.

Fig. 6 .

 6 Fig. 6. Indian Pines image. (a) Three-band color composite. (b) Reference data: Corn-no till, Corn-min till, Corn, Soybeans-no till, Soybeans-min till, Soybeans-clean till, Alfalfa, Grass/pasture, Grass/trees, Grass/pasture-mowed, Hay-windrowed, Oats, Wheat, Woods, Bldg-Grass-Tree-Drives, Stone-steel towers. (c) SVM pixelwise classification map. (d) SVMMSF + MV classification map. (e) MC-MSF classification map. (f) MSSC-MSF classification map.

TABLE I CLASSIFICATION

 I ACCURACIES IN PERCENT FOR THE University of Pavia IMAGE: OA, AA, KAPPA COEFFICIENT (κ), AND CLASS-SPECIFIC ACCURACIES vertex t i ; the MSF is obtained after removing the vertex r.

TABLE II CLASSIFICATION

 II ACCURACIES IN PERCENT FOR THE Indian Pines IMAGE: OA, AA, KAPPA COEFFICIENT (κ), AND CLASS-SPECIFIC ACCURACIES

By reference data, we mean manually labeled pixels which are used for training classifiers followed by assessment of classification accuracies.

The analysis reported in this paper was performed with version 1.40 of the RHSEG software. The recently released version 1.50 of RHSEG produces similar segmentation results, except that it can exhibit improved results for larger values of S wght , particularly for data sets containing classes with mostly dissimilar spectral responses.

A mixed pixel is defined as a pixel whose value represents the average energy emitted or reflected from several different surfaces occurring within the spatial area represented by the pixel.

ACKNOWLEDGMENT

The authors would like to thank P. Gamba from the University of Pavia, Italy, and D. Landgrebe from Purdue University, U.S., for providing the hyperspectral data.

This work was supported in part by the Marie Curie Research Training Network "HYPER-I-NET." Y. Tarabalka is with the

He is currently a Computer Engineer with the Computational and Information Sciences and Technology Office (CISTO), Science and Exploration Directorate, NASA Goddard Space Flight Center, Greenbelt, MD. As a member of the CISTO, he is responsible for designing and developing computer software tools for space and Earth science image analysis and encouraging the use of these computer tools through interactions with space and Earth scientists. He is the holder of a patent with two other pending patent applications for his development of a recursive hierarchical segmentation algorithm.

Dr. Tilton is a Senior Member of the IEEE Geoscience and Remote Sensing Society and the IEEE Signal Processing Society and is a member of Phi Beta Kappa, Tau Beta Pi, and Sigma Xi. From 1992 to 1996, he served as a member of the IEEE Geoscience and Remote Sensing Society Administrative Committee. Since 1996, he has served as an Associate Editor of the IEEE TRANSACTIONSON GEOSCIENCE AND REMOTE SENSING.


Florent Jacquemard
email: florent.jacquemard@lsv.ens-cachan.fr

Reachability and confluence are undecidable for flat term rewriting systems

Ground reachability, ground joinability and confluence are shown undecidable for flat term rewriting systems, i.e. systems in which all left and right members of rule have depth at most one.

1 Reachability, joinability and confluence are shown NP-hard in [6].

Introduction

The confluence of a term rewriting systems (TRS) guarantees that every term has at most one normal form. This property is undecidable in general, and has been shown decidable for ground TRS in [1, 2]. The main result of [1] also implies the decidability of the reachability and joinability problems for ground TRS.

More recently, the confluence has been shown solvable in polynomial time for several classes of TRS, every class embedding the previous one: some restricted ground TRS in [3], ground TRS in [4], shallow (variables occur at depth at most 1 in rewrite rules) and rule linear (in every rewrite rule, every variable occurs at most once) TRS in [5], and shallow, linear (in every left or right member of rewrite rule, every variable occurs at most once) TRS in [6]. The polynomial time complexity result of [4] is also valid for the decision of reachability and joinability, which was already shown in [1].

Reachability, joinability and confluence are undecidable for linear (nonshallow) TRS [7], but it was not known whether we can relax the linearity assumptions on variables of the systems of [5, 6], keeping these properties decidable [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] . We answer here by the negative, showing, with a reduction of the Post Correspondence Problem, that the problems of ground reachability, ground joinability and confluence are undecidable for flat TRS (every terms in rewrite rules have depth at most 1) with non linear variables. The proof 1 for ground reachability uses the same colored techniques as an older proof of undecidability of rigid reachability [8], though this latter result could not be reused directly in this context.

Preliminaries

Given a signature Σ, and a set of variable symbols X , we note T (Σ, X ) the set of terms build with symbols of Σ and X and T (Σ) its subset of ground terms. The set of function symbols of Σ of arity i is denoted Σ i .

A term rewriting system (TRS) on Σ is defined as a finite set of rewrite rules denoted ℓ → r with ℓ, r ∈ T (Σ, X ). We note -→ R the rewrite relation (on terms of T (Σ, X )) defined by the TRS R, and -→ * R the reflexive and transitive of this relation.

Definition 1 A TRS R is called shallow (respectively flat), if all its rewrite rules have the form f (t 1 , . . . , t n ) → g(s 1 , . . . , s m ) or x → g(s 1 , . . . , s m ) or f (t 1 , . . . , t n ) → x where every t i and s i is either a variable of X or a ground term of T (Σ) (respectively a variable of X or a symbol of Σ 0 ), and where x ∈ X , and n, m can be 0 (if f or g have arity 0). We are interested in the following decision problems:

(ground) reachability. Given a TRS R on a signature Σ and two (ground) terms s, t ∈ T (Σ, X ), do we have a reduction s -→ * R t ?

(ground) joinability. Given a TRS R on Σ and two (ground) terms s, t ∈ T (Σ, X ), does there exists v ∈ T (Σ, X ) such that s -→ * R v ←- * R t ?

confluence. Given a TRS R on Σ, do we have: for all s, t ∈ T (Σ, X ) such that s ←- * R u -→ * R t for some u ∈ T (Σ, X ), does there exists v ∈ T (Σ, X ) such that s -→ * R v ←- * R t ? We shall show below that the ground reachability, ground joinability and confluence problems are undecidable for flat TRS, by reduction of the Post correspondence problem.

Post Correspondence Problem, coding and coloring

We consider an instance of the Post Correspondence Problem (PCP) given by a finite set of pairs of words:

PCP := {(u i , v i ) | u i , v i ∈ {a, b} * , 1 ≤ i ≤ N } (1)
The following problem is undecidable: Does there exist a finite sequence (i j ) 0≤j≤k with 1 ≤ i 0 , . . . , i k ≤ N , such that

u i 0 u i 1 . . . u i k = v i 0 v i 1 . . . v i k ?
We shall represent the hypothetical solutions of PCP by ground terms from the sets described in Section 2.1, and provide in Sections 3, 4, and 5 some reductions to the reachability, joinability and confluence decision. The ingredients for the construction of the TRSs used in the reductions are two automata (Section 2.2), four TRSs (beginning of Section 3) and some coloring (Section 2.3).

Product and string terms

Let be a new symbol. We shall use a product operator ⊗ which associate to two words of {a, b} * a word of {a, b, } 2 * as follows:

c 1 . . . c n ⊗ c ′ 1 . . . c ′ m := c 1 , c ′ 1 . . . c k , c ′ k where c 1 , . . . , c n , c ′ 1 , . . . , c ′ m ∈ {a, b}, k = max(n, m), and for all i with n < i ≤ k, if any, (resp. all j with m < j ≤ k), c i = (resp. c ′ j = ). Example 2 a ⊗ bab = a, b , a , b .
Let us consider the signature Γ := {a, b, ε}, where a, b and ε have the respective arities 1,1 and 0.

We write: Γ := Γ⊎{ }, where has arity 0 in Γ , and ∆ := {a, b, } 2 ∪{ε}, where ε has arity 0 in ∆, and every other symbols have arity 1 in ∆.

Remark 3

We make no distinctions below between a word c 1 . . . c n ∈ {a, b} * (resp. d 1 . . . d n ∈ {a, b, } 2 * ) and the ground term c 1 (.

. . c n (ε)) ∈ T (Γ) (resp. d 1 (. . . d n (ε)) ∈ T (∆)).
In this manner, the operator ⊗ is extended to T (Γ) × T (Γ) → T (∆).

Automata associated to PCP

Let A and B be two finite automata recognizing the respective sets:

L(A) = {u i ⊗ v i | 1 ≤ i ≤ N } * and L(B) = {a, b} * ,
and with respective state sets Q A and Q B and initial states q A and q B . Following Remark 3, we shall consider L(A) and L(B) as subsets of, respectively, T (∆) and T (Γ).

We associate to A and B two ground TRS T A and T B on the respective signatures ∆ ⊎ Q A and Γ ⊎ Q B , where the states symbols of Q A and Q B have arity 0, as follows:

T A := {q → d(q ′ ) | q, q ′ ∈ Q A , d ∈ ∆, q -→ d q ′ is a transition of A} ∪ {q → q ′ | q, q ′ ∈ Q A , q → q ′ is an epsilon-transition of A} ∪ {q → ε | q ∈ Q A is a final state of A} (2)
T B := {q → c(q ′ ) | q, q ′ ∈ Q B , c ∈ Γ, q -→ c q ′ is a transition of B} ∪ {q → q ′ | q, q ′ ∈ Q B , q → q ′ is an epsilon-transition of B} ∪ {q → ε | q ∈ Q B is a final state of B} (3)

Coloring terms and TRS

We assume given 19 disjoint copies of the above signatures, colored with color i for 0 ≤ i ≤ 18:

Γ (i) := {c (i) | c ∈ Γ }, Q (i) A := {q (i) | q ∈ Q A }, Q (i) B := {q (i) | q ∈ Q B }, ∆ (i) := { c (i) , c ′ (i) | c, c ′ ∈ ∆}.
Let Θ be the following signature Θ :

= Γ ∪ ∆ ∪ Q A ∪ Q B ,
where the symbols of Γ and ∆ keep their respective arities in Θ and the symbols of Q A and Q B have arity 0 in Θ, and let and Θ (i) (0 ≤ i ≤ 18) be the colored copies of Θ,

Θ (i) := Γ (i) ∪ ∆ (i) ∪ Q (i) A ∪ Q (i) B .
For 0 ≤ i ≤ 18, the i-coloring t (i) ∈ T (Θ (i) , X ) of a term of t ∈ T (Θ, X ) is recursively defined by: f (t) (i) := f (i) (t (i) ), and x (i) := x for all x ∈ X .

Given a set U ⊆ T (Θ), we write

U (i) := {t (i) | t ∈ U }, and given a TRS R on Θ, we let R (i,j) := {l (i) → r (j) | l → r ∈ R} and R (i) := R (i,i) .

Reduction of PCP to reachability for flat TRS

We associate a TRS R 1 to the above problem PCP in (8), see also Figure 1. Its definition refers to the following two trivial and two projections TRS:

S := {c(x) → c(x) | c ∈ Γ 1 } ∪ {ε → ε} (4)
P := {d(x) → d(x) | d ∈ ∆ 1 } ∪ {ε → ε} (5)
Π 1 := { c, c ′ (x) → c(x) | c ∈ Γ 1 , c ′ ∈ Γ } ∪ { , c ′ (x) → x | c ′ ∈ Γ 1 } ∪ {ε → ε} (6)
Π 2 := { c, c ′ (x) → c ′ (x) | c ∈ Γ , c ′ ∈ Γ 1 } ∪ { c, (x) → x | c ∈ Γ 1 } ∪ ∪{ε → ε} (7)
The identity TRS S and P shall of course be used only in their colored form S (i,j) and P (i,j) .

Example 4 Let u 1 = a, v 1 = bab, u 2 = ab, v 2 = b. (u 1 ⊗ v 1 )(u 2 ⊗ v 2 ) = a, b ( , a ( , b ( a, b ( b, (ε))))) --→ Π 1 a( , a ( , b ( a, b ( b, (ε))))) --→ Π 1 a( , b ( a, b ( b, (ε)))) --→ Π 1 a( a, b ( b, (ε))) --→ Π 1 a(a( b, (ε))) --→ Π 1 a(a(b(ε)))
The TRS R 1 is defined on an extended signature: Ξ = i=18 i=0 Θ (i) ⊎ {f, g, 0, 1} where f, g, 0, 1 are new function symbols of respective arities 8, 8, 0, 0 in Ξ.

4 0 → f ( q (3) A , q (4)
A , q

A , q

B , q

B , q

A , q

B , q

B ) T P (3,1) P (4,2) P (5,1) S (13,11) S (14,12) P (6,2) S (15,11) S (16,12) f ( Figure 1: The TRS R 1 . The placement of the rules illustrates the equivalence between the existence of a solution to PCP and the existence of a reduction 0

--→ * R 1 1. A solution is represented by a term s ∈ L(A) such that s --→ * Π 1 t ← -- * Π 2 s for some t ∈ L(B).
The terms s and t are duplicated in the reduction (with different colors), they correspond to the variables x i and y j respectively. In the reduction, the rules of the top part (above f (. . .) → g(. . .)) ensures that the (instances of) x i and y j belong respectively to L(A) and L(B) and the rules of the bottom part ensure the above relation between s and t, namely x 1 and x 2 are the same term x 0 , modulo coloring, the projection with Π 1 of x 1 is y 17 , the projection with Π 2 of x 2 is y 18 , and y 17 and y 18 are the same term y 10 modulo coloring.

R 1 := R 0 ∪      0 → f (q (3) A , q (4) A , q (5) A , q (13) B , q (14) B , q (6)
A , q (15) B , q (16) B ), f (x 1 , x 2 , x 1 , y 11 , y 12 , x 2 , y 11 , y 12 ) → g(x 1 , x 2 , x 1 , y 11 , y 12 , x 2 , y 11 , y 12 ), g(x 0 , x 0 , y 17 , y 17 , y 18 , y 18 , y 10 , y 10 ) → 1 [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] ∪ P (4,2) ∪ P [START_REF] Tiwari | Deciding confluence of certain term rewriting systems in polynomial time[END_REF][START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] ∪ S (13,11) ∪ S (14,12) ∪ P [START_REF] Godoy | On the confluence of linear shallow term rewrite systems[END_REF][START_REF] Oyamaguchi | The Church-Rosser property for ground termrewriting systems is decidable[END_REF] ∪ S (15,11) ∪ S (16,12) ∪

     R 0 := T (3) A ∪ T (4) A ∪ T (5) A ∪ T (6) A ∪ T (13) B ∪ T (14) B ∪ T (15) B ∪ T (16) B ∪ P (3,
P (1,0) ∪ P (2,0) ∪ Π (1,17) 1 ∪ S (11,17) ∪ S (12,18) ∪ Π (2,18) 2 ∪ S (11,10) ∪ S (12,10) (8)
Note that R 1 is a flat TRS.

Definition 5 A 01-derivation witness for R 1 is a tuple (s 0 , s 1 , s 2 , t 10 , t 11 , t 12 , t 17 , t 18 ) of terms of T (Ξ, X ) such that: f (q

(3) A , q (4)
A , q

A , q

B , q

B , q

A , q

B , q

(16) B ) --→ * R 1 f (s 1 , s 2 , s 1 , t 11 , t 12 , s 2 , t 11 , t 12 ) --→ R 1 g(s 1 , s 2 , s 1 , t 11 , t 12 , s 2 , t 11 , t 12 ) --→ * R 1
g(s 0 , s 0 , t 17 , t 17 , t 18 , t 18 , t 10 , t 10 ).

Lemma 6 0 --→ * R 1 1 iff there exists a 01-derivation witness for R 1 .

Lemma 7 Every 01-derivation witness for R 1 w = (s 0 , s 1 , s 2 , t 10 , t 11 , t 12 , t 17 , t 18 ) is such that:

1. s 0 ∈ L(A) (0) , s 1 ∈ L(A) [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] , s 2 ∈ L(A) [START_REF] Oyamaguchi | The Church-Rosser property for ground termrewriting systems is decidable[END_REF] , t 10 ∈ L(B) (10) , t 11 ∈ L(B) (11) , t 12 ∈ L(B) (12) , t 17 ∈ L(B) (17) and t 18 ∈ L(B) (18) , 2. s 1 ----→ * P (1,0) s 0 ← ---- * P (2,0) s 2 , and t 11 -----→ * S (11,10) t 10 ← ----- * S (12,10) t 12 , 3.

s 1 ----→ * Π (1,17) 1 t 17 ← ----- * S (11,17) t 11 , and t 12 -----→ * S (12,18) t 18 ←---- * Π (2,18) 2 s 2 .
Proof:

An analysis on the occurrences of symbols in the rules of R 1 shows that the reductions in Definition 5 contain on one hand (see also Figure 1): q

(3) A --→ * R 0 s 1 , q (4)
A --→ * R 0 s 2 , q (5)
A --→ * R 0 s 1 , q (13)
B --→ * R 0 t 11 , q (14)
B --→ * R 0 t 12 , q (6)
A --→ * R 0 s 2 , q (15)
B --→ * R 0 t 11 , q (16)
B --→ * R 0 t 12 , and on the other hand:

s 1 --→ * R 0 s 0 ← -- * R 0 s 2 , s 1 --→ * R 0 t 17 ← -- * R 0 t 11 , t 12 --→ * R 0 t 18 ← -- * R 0 s 2 , t 11 --→ * R 0 t 10 ← -- * R 0
t 12 . The use of colors in the construction of R 0 implies (1) for w. For instance, in q

(3) A --→ * R 0 s 1 ← -- * R 0 q (5)
A , because of the coloring with colors 3 and 5, the left derivation can only involve rules of the sub systems T

A , P [START_REF] Hayrapetyan | On the complexity of confluence for ground rewrite systems[END_REF][START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] , P [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF]0) , Π

(1,17) 1

, and the right derivation can only involve rules of the sub systems T

A , P [START_REF] Tiwari | Deciding confluence of certain term rewriting systems in polynomial time[END_REF][START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] , P [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF]0) , Π

(1,17) 1 . Hence, s 1 ∈ T (∆ (0) ∪ ∆ (1) ∪ Γ (17) ). Similarly, q (4) A --→ * R 0 s 2 ← -- * R 0 q (6) A implies that s 2 ∈ T (∆ (0) ∪ ∆ (2) ∪ Γ (18) ) and s 1 --→ * R 0 s 0 ← -- * R 0 s 2
implies that s 0 ∈ T (∆ (0) ), s 1 ∈ T (∆ (0) ∪ ∆ [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] ) and s 2 ∈ T (∆ (0) ∪ ∆ [START_REF] Oyamaguchi | The Church-Rosser property for ground termrewriting systems is decidable[END_REF] ).

We proceed the same way to show the other conditions of (1), reducing incrementally the possible domain of each component of w. The conditions (2) and (3) follow then from the above reductions and the colors of the terms. 2

Lemma 8 There exists a 01-derivation witness for R 1 iff there exists a solution for PCP.

Proof:

For the if direction, assume that the sequence (i j ) 0≤j≤k is a solution of PCP, and let s : [START_REF] Dauchet | Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems[END_REF] , s [START_REF] Oyamaguchi | The Church-Rosser property for ground termrewriting systems is decidable[END_REF] , t (10) , t (11) , t (12) , t (17) , t (18) ) is a 01-derivation witness for R 1 .

= (u i 0 ⊗ v i 0 )(u i 1 ⊗ v i 1 ) . . . (u i k ⊗ v i k ) and t := u i 0 u i 1 . . . u i k . By construction of R 1 , and because t = v i 0 v i 1 . . . v i k , the tuple (s (0) , s
For the only if direction, let (s 0 , s 1 , s 2 , t 10 , t 11 , t 12 , t 17 , t 18 ) be a 01-derivation witness for R 1 . By (1) and (2) of Lemma 7, there exist a sequence (i j ) 0≤j≤k such that, for each ℓ = 0, 1, 2:

s ℓ = (u (ℓ) i 0 ⊗ v (ℓ) i 0 ) • • • (u (ℓ) i k ⊗ v (ℓ) i k ).
The other conditions in (1)-(3) in Lemma 7 imply that (i j ) 0≤j≤k is a solution of PCP (see the comments in Figure 1). 2 Lemmas 6, 7 and 8 establish a reduction of the undecidable PCP into the reachability problem for (R 1 , 0, 1). Hence we can conclude with the following theorem. By Lemmas 6, 7, 8 and 11, there is a reduction of PCP into the confluence for the flat TRS R 1 ∪ R 2 .

Theorem 12 The confluence is undecidable for flat TRS.

Conclusion

We have shown that the properties of reachability, joinability and confluence are undecidable for flat (and hence shallow) TRS. This is a big contrast with the shallow linear case, for which all these properties are known to be decidable in polynomial time [6].

One can note that all the known decidability results for confluence concern classes of linear TRS. Two subclasses of (non-linear) shallow TRS remain out of the scope of the reductions constructed here: the shallow rightground TRS -reachability and joinability are decidable for right-ground rewrite systems [9], and, more generally, subclasses of shallow TRS with syntactic restriction on the relative occurrences of variables between left and right members of rules, e.g. shallow TRS such that a variable with more than one occurrence in the left member can not occur in the right member of a rewrite rule.

A similar technique is used in[START_REF] Godoy | On the confluence of linear shallow term rewrite systems[END_REF] to show the NP-hardness of confluence for shallow TRS.

Acknowledgements

The author wishes to thank Ralf Treinen who has carefully read and commented a preliminary version of this paper, and Harald Ganzinger for his useful suggestions.

Theorem 9

The ground reachability problem is undecidable for flat TRS.

Reduction of PCP to joinability for flat TRS

The undecidability for the joinability follows from a reduction presented in [7] (we can also observe that the joinability problem for R 1 , 0 and 1 is equivalent to the reachability problem for R 1 , 0 and 1).

Corollary 10

The ground joinability problem is undecidable for flat TRS.

Reduction of PCP to confluence for flat TRS

We shall modify the TRS R 1 in order to reduce PCP to confluence 2 . More precisely, we shall construct a TRS R 2 such that 0

The TRS R 2 is defined on the extended signature: Ξ ′ = Ξ ∪ {2}, where 2 has arity 0 in Ξ ′ .

one of the z i is 1, the others are distinct variables} (9) We recall that Ξ 0 and Ξ 1 denote the set of symbols of Ξ of arity respectively 0 and 1. Note that R 2 is flat.

Proof: (sketch) For the only if direction, assume that 0 --→ * R 1 1. It means that 0 and 1 are not joinable by R 1 (since 1 is in normal form for R 1 ∪ R 2 ) and hence also not joinable by

A , T

A , T

A , T

A , q

A , q (13) B , q

A , q (15) B , q

t, and one reduction involves a rule of R 4 , then u, s and t contain at least a constant symbol of Ξ 0 and then s--→ * R 2

1← -- * R 2 t. Since R 3 is terminating, we prove its confluence using Newman's lemma, by observing that all its critical pairs can be joined by R 2 .


Student Member, IEEE Mauro Dalla Mura
email: dallamura@disi.unitn.it

Student Member, IEEE Alberto Villa
email: alberto.villa@hyperinet.eu

Fellow, IEEE Jon Atli Benediktsson

Senior Member, IEEE Jocelyn Chanussot
email: jocelyn.chanussot@gipsa-lab.grenoble-inp.fr

Fellow, IEEE Lorenzo Bruzzone
email: lorenzo.bruzzone@ing.unitn.it

Classification of Hyperspectral Images by Using Extended Morphological Attribute Profiles and Independent Component Analysis

Keywords: Attribute filters, decision fusion, extended attribute profile (EAP), independent component analysis (ICA), mathematical morphology, remote sensing. I

In this letter, a technique based on independent component analysis (ICA) and extended morphological attribute profiles (EAPs) is presented for the classification of hyperspectral images. The ICA maps the data into a subspace in which the components are as independent as possible. APs, which are extracted by using several attributes, are applied to each image associated with an extracted independent component, leading to a set of extended EAPs. Two approaches are presented for including the computed profiles in the analysis. The features extracted by the morphological processing are then classified with an SVM. The experiments carried out on two hyperspectral images proved the effectiveness of the proposed technique.

The spatial characteristics of the objects in an image can be modeled with several approaches. A widely used technique for extracting spatial features is based on mathematical morphology. Among all the operators belonging to this framework, morphological connected operators [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF] proved to be suitable for extracting spatial information while preserving the geometrical characteristics of the structures in the image (i.e., without distorting the borders). In [START_REF] Benediktsson | Classification of hyperspectral data from urban areas based on extended morphological profiles[END_REF], morphological profiles (MPs), a sequence of multiscale connected operators, were applied to high-resolution hyperspectral images by reducing the high dimensionality of the data by principal component analysis (PCA) and computing the profiles on the first principal components extracted, leading to the definition of extended MPs (EMPs). Due to the limitations of PCA, when extracting the information sources from the high-dimensional data, it was proposed to perform independent component analysis (ICA) before the computation of the MPs [START_REF] Palmason | Classification of hyperspectral data from urban areas using morphological preprocessing and independent component analysis[END_REF].

The characterization of spatial information obtained by the application of an MP is particularly suitable for representing the multiscale variability of the structures in the image, but it is not sufficient to model other geometrical features. To avoid this limitation, the use of morphological attribute filters instead of the conventional operators based on the geodesic reconstruction was proposed [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF]. The application of attribute filters in a multilevel way leads to the definition of attribute profiles (APs) [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF], which permit to model other geometrical characteristics rather than the size of the objects. Moreover, APs showed interesting characteristics when extended to hyperspectral images [START_REF] Dalla Mura | Extended profiles with morphological attribute filters for the analysis of hyperspectral data[END_REF]. In greater details, analogous to [START_REF] Benediktsson | Classification of hyperspectral data from urban areas based on extended morphological profiles[END_REF], the APs were applied to the first principal components extracted from a hyperspectral image, generating an extended AP (EAP).

In this letter, we extend the work presented in [START_REF] Dalla Mura | Classification of hyperspectral images by using morphological attribute filters and independent component analysis[END_REF] by presenting a technique based on EAPs and ICA for the classification of hyperspectral images. Moreover, we investigate two approaches for combining the information extracted by EAPs computed with different attributes.

This letter is organized as follows. In Section II, the ICA is discussed, while in Section III, the concepts of morphological attribute filters and EAPs are presented. The proposed approaches for dealing with multiple EAPs are presented in Section IV. The experimental results are illustrated in Section V. Finally, conclusions are drawn in Section VI. IEEE GEOSCIENCE AND REMOTE SENSING LETTERS, VOL. 8, NO. 3, MAY 2011 II. ICA Hyperspectral sensors record images with hundreds of bands and a very high spectral resolution. The very detailed spectral description provided by these kinds of images increases the capability to distinguish between land-cover classes, thus achieving accurate classification maps. However, the analysis of this huge amount of data presents some methodological issues which need to be addressed. In particular, the high dimensionality of the data is a critical problem, due to the appearance of the Hughes phenomenon: After a certain threshold, if the number of features increases, the generalization capability of the classifier decreases when a fixed number of training samples are used. The threshold mainly depends on the number of samples used to train the classifier. Because of these reasons, feature reduction is often applied as a preprocessing step before the classification of hyperspectral data, in order to avoid the curse of dimensionality, and to reduce the computation time. Although it is not optimal for classification, the PCA is often used for such a task, due to its simplicity and ease of use. The principle of PCA is to project the data into an orthogonal space, so that the eigenvectors correspondent to the greatest eigenvalues retain the maximum variance of the data. Because the PCA is based on the analysis of covariance matrix and second-order statistics, it can neglect some important information, particularly when few components are retained. In this letter, we propose to use ICA for feature reduction, as an effective alternative to PCA. ICA consists of finding a linear decomposition of the observed data into statistically independent components (ICs). Given an observation model x = As, where x is the vector of the observed signals, A is a matrix of scalars corresponding to the mixing coefficient, and s is the vector of the source signals, the ICA finds a separating matrix W such that y = Wx = WAs, where y is a vector of ICs.

Independence is a much stronger assumption than decorrelation, which can be obtained with PCA or factor analysis. In ICA, the concept of independence can be summarized as follows: Each component should not provide any information about higher (than second) order statistics of the other components. However, there are several methods for estimating ICA. In this letter, we have used the algorithm JADE (Joint Approximate Diagonalization of Eigenmatrices), due to good results shown when used for feature reduction in hyperspectral remote sensing data [START_REF] Villa | On the use of ICA for hyperspectral image analysis[END_REF]. Due to space constraints, we refer the reader interested in more details about the general framework of ICA to [START_REF] Hyvarinen | Independent Component Analysis[END_REF].

III. EAPs

EAPs are based on the concept of the AP, which is a generalization of the widely used MPs [START_REF] Dalla Mura | Extended profiles with morphological attribute filters for the analysis of hyperspectral data[END_REF]. Analogous to the definition of the EMPs, EAPs are generated by concatenating many APs. Each AP is computed on one of the c features (FRs) extracted by a feature reduction transformation (e.g., PCA) from a multivariate image (e.g., the hyperspectral image) [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF]

EAP = {AP (F R 1 ), AP (F R 2 ), . . . , AP (F R c )} . ( 1
)
The AP is an extension of the MP, obtained by processing a scalar grayscale image f , according to a criterion T , with n morphological attribute thickening (φ T ) and n attribute thinning (γ T ) operators, instead of the conventional morphological filters by reconstruction

AP (f ) = φ T n (f ),φ T n-1 ,. . ., φ T 1 (f ),f, γ T 1 (f ),. . .,γ T n-1 (f ),γ T n (f ) . ( 2
)
Attribute filters are connected operators which operate on the connected components (i.e., regions of isointensity spatially connected pixels) that compose an image, according to a given criterion [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF]. The criterion associated to the transformation is evaluated on each connected component of the image. In general, the criterion compares the value of an arbitrary attribute attr (e.g., area, volume, standard deviation, etc.) measured on the component C against a given reference value λ (which is the filter parameter), e.g., T (C) = attr(C) > λ. If the criterion is verified, then the regions are kept unaffected; otherwise, they are set to the gray level of a darker or brighter surrounding region, according to if the transformation performed is extensive (i.e., thickening) or antiextensive (i.e., thinning), respectively. When the criterion considered in the analysis is increasing (i.e., if it is verified for a connected component, then it will also be verified by all the regions brighter or darker, according to the transformation, including the component), the attribute thinning and thickening operators are actually opening and closing transformations. Nonincreasing criteria do not have a unique definition when considering grayscale images. In fact, different effects can be obtained by the operators with a nonincreasing criterion according to the filtering rule selected [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF].

Attribute filters can be efficiently computed by taking advantage of the representation of the input image as a rooted hierarchical tree of the connected components of the image. The tree is obtained by the Max-tree algorithm [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF]. The approach based on this data representation is particularly useful when computing an AP, since the image is converted to the tree only once (this is the most demanding stage of the filtering) and processed several times with the different criteria. Examples of EAPs computed with different attributes are reported in (Fig. 1).

IV. APPROACHES TO DEAL WITH MULTIPLE EAPs

The choice of the most suitable attribute and range of thresholding values (λ's) for extracting the information on the geospatial objects is certainly a complex task, particularly when a piori information on the scene is not available. A possible approach attempting to overcome this issue relies on the computation of EAPs with different kinds of attributes. However, this leads to the problem of properly exploiting, in the analysis, the different information extracted by the computed EAPs.

A simple strategy is the stacked vector approach (SVA), which combines the EAPs by concatenating them in a single vector of features [also called extended multi-AP (EMAP) [START_REF] Dalla Mura | Extended profiles with morphological attribute filters for the analysis of hyperspectral data[END_REF]; see Fig. 2(a)]. However, even if complementary information can be extracted by considering different attributes, a great redundancy is present in the features extracted. Thus, it is advisable that a classification algorithm with excellent penalization capability is used for classifying the features in order to handle the increased dimensionality which can lead to the Hughes phenomenon.

Another approach is the fusion approach (FA) that is based on the separate classification of each EAP and on the fusion of the results obtained by the independent classifiers in order to generate the final decision map [see Fig. 2(b)]. In comparison to the SVA, the FA keeps low the dimensionality of the data and increases the robustness of the results, particularly if the different EAPs generate complementary errors.

In this letter, an SVM classifier is considered with the oneagainst-one multiclass strategy. The fusion rule considered when combining the results of the single classifiers relies on the sum of the votes of the classifiers applied to the four EAPs, assigning each pixel to a class, according to the majority voting scheme. Obviously, other decision criteria can be applied.

V. EXPERIMENTAL ANALYSIS

The experimental analysis was carried out on two hyperspectral images acquired over the city of Pavia (Italy) by the ROSIS-03 (Reflective Optics Systems Imaging Spectrometer) hyperspectral sensor. The two images have a geometrical resolution of 1.3 m. The first one shows the university campus (610 × 340 pixels), while the second one was acquired on the city center (1096 × 489 pixels). In the following, we will refer to the two data sets as "University" and "Center," respectively. The original data are composed of 115 spectral bands, ranging from 0.43 to 0.86 μm with a band of 4 nm. However, noisy bands were previously discarded, leading to 103 and 102 channels for the two images, respectively. Nine thematic land-cover classes were identified in the university campus: Trees, Asphalt, Bitumen, Gravel, Metal sheets, Shadows, Selfblocking Bricks, Meadows, and Bare soil. For this data set, a total of 3921 and 42 776 pixels were available as training and test sets, respectively. In the center area, the thematic classes found were Water, Tree, Meadow, Self-blocking Bricks, Soil, Asphalt, Bitumen, Tile, and Shadow. The training and test sets for this data set were composed of 5536 and 103 539 samples, respectively. The true color representation of the images and the test sets taken as reference are shown in Fig. 3.

In the analysis carried out, all the samples of the training set were used for the University data set, while for the Center data sets, only 50 samples (randomly chosen from the full training set for each class) were considered. All the experiments conducted on the latter data set were run ten times with a set of different training samples each time.

From both the two hyperspectral images, four components extracted by PCA and ICA were considered. The first four PCs ). The area and the length of the diagonal of the bounding box extract information on the scale of the objects. The moment of inertia and the standard deviation are not dependent on the size dimension, but they are related to the geometry of the objects and the homogeneity of the intensity values of the pixels, respectively. Each EAP is 36dimensional, i.e., it is composed of four APs with nine levels computed on each component extracted. In the sequel, the notation EAP attr denotes the EAP built with the attr attribute.

The classification maps are obtained by analyzing the features extracted by the extended profiles with an SVM classifier with a radial basis function kernel. The model selection in the training phase of the classifier was based on a gradient descent method, which proved to be computationally less demanding than the exhaustive investigation of the parameters on a grid approach, giving comparable results [START_REF] Villa | Gradient optimization for multiple kernel's parameters in support vector machines classification[END_REF]. The thematic accuracies of the obtained maps (which are presented in Tables I andII) were assessed by computing the overall accuracy (OA), the average accuracy (AA), and the Kappa coefficient (κ) on the available reference data. The statistical significance of the classification maps obtained by PCA and ICA and the same morphological processing was evaluated with the McNemar's test. All the results were statistically significant.

The obtained results are reported in Table I. It is clear, as in most of the cases, by including the features extracted by the EAPs in the analysis resulted in higher accuracies (up to almost 17% of OA) than those obtained by considering only the spectral features. The ICA proved to extract more informative components from the data, leading to better results than those generated by the PCA in all the experiments. When considering the contribution of the single EAPs, the EAPs built with area and the moment of inertia attributes performed the best with the PCA and ICA, respectively. This proves how it can be difficult to select a priori the most suitable attribute on the data. In these experiments, considering all the EAPs together, in the SVA architecture, with the ICA gives excellent results in terms of classification accuracies. As far as we know, these accuracies are higher than all those reported in the literature for this data set without postprocessing [START_REF] Fauvel | Spectral and spatial classification of hyperspectral data using svms and morphological profiles[END_REF], [START_REF] Tarabalka | Spectral & spatial classification of hyperspectral imagery based on partitional clustering techniques[END_REF]. In contrast, the SVA approach led to low accuracies for the PCA. This can be due to the high variation in terms of accuracy showed by the single EAPs (more than 20% of OA), which affects the overall performances of this approach. The FA is performing well in average and has a robust behavior since, in all the experiments, the accuracies obtained, when compared to those of the single EAPs, are slightly lower than the best case (less than 2% of OA) and better than all the others. The improved accuracies obtained by the proposed technique are also confirmed by the higher precision shown in the map obtained when considering the ICA and all the EAPs together [see Fig. 4(c)].

Table II reports the thematic accuracies obtained on the Center data set (the correspondent classification maps are not reported for space constraints). Similar considerations as for the University data set can be drawn. For this data set also, it is evident the importance of including the spatial information, which led to an increase in terms of accuracy with respect to considering the original hyperspectral data or the components obtained from the dimensionality reduction technique. The best OA obtained by using the EAPs is higher, of about 2%, than those obtained by the original spectral features and the first components. Considering the PCA and ICA transformations, the latter leads to the best results in most of the cases (except for the single components extracted and for the EAP s ). When looking at the performances obtained by considering the spatial features extracted by the EAPs, can see that the EAP with area attribute outperformed the other single EAPs with PCA, while when considering the ICA, the choice of the standard deviation performed the best among the single EAPs. Moreover, when considering the SVA strategy resulted in the best accuracies with the ICA preprocessing (which is slightly worse than the best EAP). Again, the FA led to results over the average of the accuracies obtained by the single EAPs.

VI. CONCLUSION

In this letter, we have presented a technique based on ICA and APs for the classification of hyperspectral images. In greater details, from the hyperspectral image, some ICs are extracted, and different APs are computed for each one, leading to EAPs. The features obtained by the morphological processing are then classified with an SVM classifier. We proposed two approaches for considering the features extracted by the different EAPs, one based on the concatenation of the EAPs and one based on the fusion of the classification results obtained on the single EAPs.

The experimental analysis was carried out on two wellknown hyperspectral images acquired on the city of Pavia (Italy). The results obtained on these data sets proved that the preprocessing of the hyperspectral data carried out with ICA is more suitable than the PCA for modeling the different sources of information present in the scene. Moreover, from the experiments and results, it was evident how important the spatial features extracted by the EAPs are for classification. The concatenation of the different EAPs gave excellent results in terms of classification accuracies (with respect to other works present in the literature on these data sets). This approach did not perform well only in one case with the PCA, i.e., when significantly different results were obtained from the single EAPs with different attributes (range of difference in the overall accuracies greater than 20%). However, this effect did not occur with the ICA, where the obtained results were more uniform and all statistically significant (according to the McNemar's test). The approach based on the fusion of the classification results with the majority voting strategy proved to have a robust behavior leading to accuracies slightly lower than those of the best case obtained with a single EAPs but better than all the others.

Fig. 1 .

 1 Fig. 1. Examples of EAPs computed on the first two PCs of a portion of the image Fig. 3(a). Each row shows an EAP built by different attributes. Attributes starting from the first row are area, length of the diagonal of the bounding box, moment of inertia, and standard deviation. Each EAP is composed by the concatenation of two APs computed on PC 1 and PC 2 . Each AP is composed of three levels: A thickening image φ T , the original PC, and a thinning image γ T . All the thickening and thinning transformations were computed with the following attribute values λ's. Area: 5000; length of the diagonal: 100; moment of inertia: 0.5; and standard deviation: 50.

Fig. 2 .

 2 Fig. 2. Proposed approaches for dealing with multiple EAPs. (a) SVA and (b) FA.

Fig. 3 .

 3 Fig. 3. ROSIS Pavia data sets: True color representation and test set for (a), (b) University and (c), (d) Center.

  contain more than 99% of the total variance of the data for both the data sets. The components were rescaled to the range [0, 1000] and converted to integer in order to be processed by the attribute filters. Four EAPs were computed by considering four different attributes on the components extracted by PCA and ICA: 1) a, area of the regions (λ a = [100 500 1000 5000]); 2) d, length of the diagonal of the box bounding the region (λ d = [10 25 50 100]); 3) i, first moment invariant of Hu, moment of inertia [11] (λ i = [0.2 0.3 0.4 0.5]); and 4) s, standard deviation of the gray-level values of the pixels in the regions (λ s = [20 30 40 50]

Fig. 4 .

 4 Fig. 4. ROSIS Pavia University data set. Classification maps obtained by (a) PCA with area attribute (EAPa), (b) PCA with FA, (c) ICA with SVA, and (d) ICA with FA.

TABLE I ROSIS

 I UNIVERSITY DATA SET. CLASSIFICATION ACCURACIES OBTAINED BY CLASSIFYING THE HYPERSPECTRAL IMAGE (SPECT.), THE FOUR COMPONENTS EXTRACTED (4 COMP.), EACH SINGLE EAP, AND THE DATA WITH THE PROPOSED APPROACHES: SVA AND FA

TABLE II ROSIS

 II CENTER DATA SET. CLASSIFICATION ACCURACIES OBTAINED BY CLASSIFYING THE HYPERSPECTRAL IMAGE (SPECT.), THE FOUR COMPONENTS EXTRACTED (4 COMP.), EACH SINGLE EAP, AND THE DATA WITH THE PROPOSED APPROACHES: SVA AND FA. THE RESULTS REPORTED ARE THE AVERAGE OF THE ACCURACIES OBTAINED IN 10 TRIALS WITH 50 TRAINING SAMPLES PER CLASS RANDOMLY CHOSEN FOR EACH TRIAL

DALLA MURA et al.: CLASSIFICATION OF HYPERSPECTRAL IMAGES

ACKNOWLEDGMENT

The authors would like to thank Prof. P. Gamba, University of Pavia, for providing the ROSIS data set.

This work was supported in part by the European community's Marie Curie Research Training Networks Program, Hyperspectral Imaging Network (HYPER-I-NET), under Contract MRTN-CT-2006-035927 and in part by the Research Fund of the University of Iceland and the University of Trento. M. Dalla