Julien Ros

Christophe Laurent
email: christophe2.laurent@orange-ftgroup.com

Jean-Michel Jolion
email: julien.ros|jean-michel.jolion@liris.cnrs.fr

A Bag of Strings Representation for Image Categorization

This paper presents an architecture well suited for natural images classification or visual object recognition applications. The method proposes to integrate a spatial representation into the well known "bag of local signatures" approach. For this purpose, it combines the power of a string representation which provides an ordered view of local features with the vectorial histogram representation allowing to recognize efficiently and quickly an image by using a machine learning classifier.

To reach this goal, we propose to represent an image by a set of strings of local signatures obtained by tracking the detected salient points along image edges. We propose here to conjointly use the Hölder exponents and the direction of minimal regularity of the bidimensionnal signal singularities to compute a signature describing precisely a region of interest centered on an interest point. As we will see, an alphabet of strings is easily obtained by using a typical self organizing map architecture. As a consequence, a "bag of strings" representation is used, providing a compact representation encoding both local signatures and spatial information. This representation is particularly well suited to train a support vector machine classifier used for the last classification step. This architecture obtains good classification rates on different well known datasets.

Introduction

With the increasing availability of digital images shot by mobile phones and digital cameras (Infotrends 3 expects that the number of images captured on camera phones will reach 227 billion by 2009), efficient image management solutions should be built. Their goal is to group images into semantic categories giving thus the opportunity of fast and accurate image search. Until now, most of these systems use textual information to index images (as Google images system does) and as a consequence, it imposes a human intervention not conceivable in the case of large databases. Using computer vision algorithm can greatly help and it is why providing efficient algorithms for image content analysis applications is one of the most important research field in the computer vision area. Nevertheless, analyzing an image is difficult because it is a very complex structure. Indeed, images from the same categories can be very different in term of geometric transformations, illumination conditions, resolution or size leading to the difficulty to classify an image into a unique category. Since 90's, a lot of methods have been proposed in order to be integrated in suitable solutions and they can be divided into two categories:

1. Content-based image retrieval (CBIR) systems were the first applications proposing solutions to the problem of searching for digital images in large image databases [START_REF] Wang | SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries[END_REF]. For this purpose, they first index each image in a database by a feature vector representing low level features. This vector permits to reduce the quantity of information to be later processed by discarding irrelevant information contained in each image. When a user queries the system with an image, the application searches within the whole database for similar images thanks to the feature vectors by using some similarity measures. However, CBIR systems are very inconclusive in results because there 2. Supervised natural image classification systems are now more and more studied because they are more efficient due to the introduction of a statistical learning step. This one allows to deduce the feature vector components that should be used to discriminate the semantic concept interesting for the user and described by a training dataset. In spite of the limited vocabulary of the training dataset and of the different semantic concept within an image, supervised natural image classification systems were first successfully applied to group images into a limited number of semantic meaningful categories and recent works [START_REF] Vasconcelos | From pixels to semantic spaces: Advances in content-based image retrieval[END_REF][START_REF] Li | Real-time computerized annotation of pictures[END_REF] have shown their ability to capture several concepts within one image allowing their use for semantic labelling and automatic annotation.

This article addresses the problem of supervised natural image classification consisting of automatically recognizing scenes and object categories in natural photographs. In practice, a supervised image classification solution requires three main steps [START_REF] Duda | Pattern Classification[END_REF]: pre-processing, feature extraction and classification. Based on this architecture, many image classification systems have been proposed, each one distinguished from the others by the method used to compute the image signature and/or the decision method used in the classification step. Regarding the signature computation, the most efficient methods are probably the local approaches firstly introduced in [START_REF] Schmid | Local Grayvalue Invariants for Image Retrieval[END_REF]. In this case, local signatures are computed around some interest points and their values are chosen in a dictionary obtained from the training database. Once the image is locally described, two major problems should be underlined. First, the inherent local representation results in a lack of ordering between signatures and consequently fundamental information about the image content is lost. Secondly, it is difficult to directly classify this orderless representation because the image is no longer considered as a vector.

To overcome these disadvantages, different solutions have been proposed in the literature.

The first one consists in representing the image as a string of local signatures by adding an implicit order between salient points and then to compare them with classical string-based distances [START_REF] Robles-Kelly | Edit Distance From Graph Spectra[END_REF][START_REF] Laurent | Comparing String Representations and Distances in a Natural Images Classification Task[END_REF][START_REF] Jolion | Représentation d'images par des chaînes de symboles : application la recherche par le contenu[END_REF]. Although it is an interesting approach, it does not allow to embed an image into a vectorial space due to the non-vectorial nature of the string representation. Consequently, the only classifier that can be used is a k-nn classifier but its high computing time restricts the approach to small datasets.

A second solution is to represent the image by a distribution of local image features easily classifiable as in [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF][START_REF] Jurie | Creating Efficient Codebooks for Visual Recognition[END_REF]: this is the "bag of local signatures" representation and its computation is directly inspired from the text categorization domain. This analogy can be justified by observing that image classification using local approaches are closely related to the text categorization problem when local signatures have been quantized into visual keywords. These visual keywords have the ability to summarize well the image content providing thus a compact representation. The advantage is that by embedding images into a high dimensional vectorial space, this representation is well suited to be processed by a fast machine learning classifier instead of a computationally expensive k-nn algorithm. These methods have been successfully applied all along the different PASCAL challenges to detect and categorize images in a difficult datasets.

However, it has been emphasized that this monodimensional representation does not consider any spatial information between subregions omitting an important quantity of information about the image content.

As a consequence, an interesting way investigated in this paper consists in exploiting the complementary capabilities of both approaches by merging them.

It is not the first attempt in the computer vision community to integrate spatial relation between local signatures or to consider the position of them when computing a model subsequently used for the last classification step. However, while most approaches integrate the mutual relations between interest points directly into a probabilistic part-based model [1,[START_REF] Lyu | Mercer Kernels for Object Recognition with Local Features[END_REF][START_REF] Bouchard | Hierarchical Part-Based Visual Object Categorization[END_REF][START_REF] Fergus | A Sparse Object Category Model for Efficient Learning and Exhaustive Recognition[END_REF], some other encode locations of the interest points in the model [START_REF] Burl | Recognition of Planar Object Classes[END_REF][START_REF] Weber | Unsupervised Learning of Models for Recognition[END_REF][START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF][START_REF] Leibe | Scale Invariant Object Categorization Using a Scale-Adaptive Mean-Shift Search[END_REF][START_REF] Fei-Fei | Learning Object Categories from Google's Image Search[END_REF][START_REF] Fei-Fei | One-Shot Learning of Object Categories[END_REF]. Finally the last approaches proposed in the literature describe coocurences between local features [START_REF] Lazebnik | A maximum entropy framework for partbased texture and object recognition[END_REF] or subdivide the image into several regions [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]. Excepting the recent work of [START_REF] Ferrari | Groups of adjacent contour segments for object detection[END_REF], none attempt has been made to incorporate spatial relations between local signatures or their positions within the image in a "bag of salient features" framework. This is due to the fact that a structure easily identifiable and quantizable should be defined in order to compute a kind of "bag of structures" representation. Whereas, the definition of a structure can be easily done by using a graph or a string approach, the design of a dictionary of graphs (or strings) is not straightforward.

We propose in this paper to use a self organizing map for structured data [START_REF] Hagenbuchner | A Self-Organizing Map for Adaptive Processing of Structured Data[END_REF] to produce a large dictionary of strings. This dictionary can be subsequently used to describe images by "bag of strings" representations. Finally, this representation is employed to learn a support vector machine classifier. The solution presented have been tested on three well know datasets described in Appendix A. The SIMPLICTY and Scene datasets contain images of natural scenes whose background information is essential to recognize the category. The PASCAL dataset is composed of object images with useless background for the categorization. The novelty of our work is (1)to propose a method to extract string of local feature vectors from an image; (2)to use a self organizing map for structured data [START_REF] Hagenbuchner | A Self-Organizing Map for Adaptive Processing of Structured Data[END_REF] to produce a large dictionary of strings; (3)to employ this dictionary to embed images into "bag of strings" representations well suited to train a support vector machine classifier and (4) to compare the method proposed with state of the art approaches of supervised image classification.

Paper Organization This paper is organized as follows: Section 2 describes the method which was introduced earlier in [START_REF] Laurent | In Depth Analysis and Evaluation of Saliency-based Color Image Indexing Methods using Wavelet Salient Features[END_REF] to detect interest points. This section ends by describing the descriptor that characterizes both orientation and regularity of the singularities in a region of interest. The construction of strings is presented in section 3 and the clustering algorithm used to generate a dictionary of strings is deeply described in section 4. Section 5 presents the method used to generate the final feature vector representing the image. Experiments testing this approach with a support vector machine classifier are presented in section 6 and finally section 7 concludes the paper.

Local Features Extraction

The goal of feature extraction is to reduce the amount of data contained in an image by extracting relevant and discriminating features. In local approaches, this extraction phase results in feature vectors computed around interest points and an image I is thus represented by a set of local signatures S(I) = {s(1), . . . , s(n)}.

It is important to mention here that local approaches result in a lack of ordering between signatures.

Interest Points Detection

The goal of interest point detectors is to find image locations that are perceptually relevant for the next recognition step. Many detectors have been proposed in the literature, each one focusing on a particular local property of the image content such as contrast [3], corners [START_REF] Harris | A Combined Corner and Edge Detector[END_REF][START_REF] Gouet | Object-Based Queries Using Color Points of Interest[END_REF][START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF], edges [START_REF] Laurent | In Depth Analysis and Evaluation of Saliency-based Color Image Indexing Methods using Wavelet Salient Features[END_REF][START_REF] Loupias | Wavelet-based salient points for image retrieval[END_REF], etc.

The salient points detector presented in [START_REF] Laurent | In Depth Analysis and Evaluation of Saliency-based Color Image Indexing Methods using Wavelet Salient Features[END_REF] uses a wavelet analysis in order to find relevant pixels located on sharp region boundaries. The use of wavelet analysis is motivated by observing that multi-resolution, orientation and frequency analysis are of prime importance for the human visual system during the recognition step. This detector has proven its efficiency in many vision applications [START_REF] Laurent | In Depth Analysis and Evaluation of Saliency-based Color Image Indexing Methods using Wavelet Salient Features[END_REF] and thus will be used in the present work.

Finally, it is important to note that the number of points to be detected can be automatically tuned by using an energy threshold. It allows to consider only interest points with large saliency value obtained from the wavelet coefficients.

Consequently, it is possible to extract a number of salient points which depends on the complexity of the image content.

Description of Local Singularities

Most local descriptors describe the local neighborhood of salient points by characterizing edges in this area. Edge information thus appears fundamental in the process of local neighborhood description. To describe edges, gradient orientation and magnitude are generally used. Nevertheless, from a mathematical point of view, an edge or more generally a singularity can also be efficiently characterized by considering its Hölder exponents. We propose to use this mathematical notion to design our local descriptor.

Definition 1. f : [a, b] → R is Hölder α ≥ 0 at x 0 ∈ R if ∃K > 0, δ > 0 and a polynom P of degree m = ⌊α⌋: ∀x, x 0 -δ ≤ x ≤ x 0 + δ, |f (x) -P (x -x 0 )| ≤ K|x -x 0 | α . Definition 2. The Hölder exponent h f (x 0 ) of f at x 0 is the superior bound value of all α. h f (x 0 ) = sup{α, f is Hölder α at x 0 }.
The local regularity of a function at a point x 0 is thus measured by the value h f (x 0 ). It is worth noting that the smaller h f (x 0 ), the more singular is the signal at the point considered. For example, the Hölder exponent of a Dirac impulse is -1 and 0 for a step function. For an image, the Hölder exponent is measured in the direction of the minimal regularity of the singularity (in the gradient direction). The different singularities met in an image are shown on figure 1.

Original Image -0.2 ≤ h ≤ 0.2 -1.2 ≤ h ≤ -0.8

Fig. 1. different kind of singularities

To describe an ROI associated to an interest point in an image I, both orientation and Hölder regularity of singularities contained in that ROI are characterized. For this purpose, orientation θ(x, y) and gradient magnitude m(x, y) at each pixel location (x, y) of the ROI are first computed. Then, for each singularity, the Hölder exponent h is estimated with foveal wavelets as presented in [START_REF] Mallat | Foveal Approximations for Singularities[END_REF].

Orientations and Hölder exponents maps are then conjointly used to construct different 3D histograms. To build such histograms, each ROI is first partitioned into 4 × 4 blocks and each histogram is computed in a particular block before being normalized by the block size (See figure 2). This last step of the signature design is realized in the same spirit as the construction of the SIFT descriptor presented in [START_REF] Lowe | Distinctive Image Features from Scale-Invariant Keypoints[END_REF].

Finally, the signature is obtained by concatenating the different 3D his- It is worth noting that we have chosen to not select a representative scale for each keypoint when computing the descriptor. Indeed, there are currently some algorithms showing that using interest points is as efficient as using random points [START_REF] Maree | Random subwindows for robust image classification[END_REF] due to the large training that can anyway capture the relevant information. In the same way, we have observed that using orientation and scale normalization is not shown crucial because the relevant information is also captured in the training step without this computational stage.

String Construction

In this section, we keep the local approach in which an image is still represented by a set of local signatures S(I) = {s(1), . . . , s(n)}. Now, we focus on grouping some of these signatures in order to represent an image by a set of strings. The difficulty resides in the construction of these strings. If we consider the major psycho-visual work of Biederman presented in [2] called the theory of recognition by components, the human decomposes an object into a subset of elementary cones called geons (geometry ions). These ones are the boundary fragments of the object to be recognized and thus the recognition is performed by assembling these different components.

Moreover, in [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF], the authors present a framework in the field of object detection. The proposed architecture represents an object by a set of boundary fragments used for the next detection step.

Consequently, we have decided to generate strings from the set of salient points by tracking edges. The process is composed of three major steps:

1. computation of the minimal regularity direction for each salient point. This direction is used to group salient points that are on the same edge; 2. salient point tracking algorithm where the salient point strings are constructed;

3. suppression of small strings in the images which are considered as noise.

Direction of Minimal Regularity Computation

Salient points considered in this work are located on sharp region boundaries due to the use of a wavelet analysis to detect them. For each salient point (x 0 , y 0 ), a direction of minimal regularity, say θ(I, x 0 , y 0 ), exists and is the gradient direction at this point. To compute this direction, we used Sobel filters. The convolution of the image by these kernels is then used to compute the direction of minimal regularity.

On figure 3, we illustrate the direction of minimal regularity computed from salient points. In this figure, an energy threshold of 0.3 is used to detect salient points. It can be observed that salient points are located on the singularities and that the directions of minimal regularity are correctly computed with Sobel

Salient Points Tracking

In this section, we present a method that aims at chaining the detected salient points to build a set of strings. The proposed method links points if they are sufficiently close in the image space and if the directions of the associated min-imal regularities are also sufficiently close. This algorithm is inspired from the work presented in [START_REF] Marcel | Détection de contours et de lignes dans les procédures de bas-niveau[END_REF] aiming at tracking edge pixels.

This algorithm has two parameters:

-The first NB NEIGHBORS is used to choose the number of nearest neighbors that should be considered to link salient points. Indeed, when a point is processed, the candidates that can be linked with it are chosen among its NB NEIGHBORS closest neighbors in the image.

-The second parameter ANGLE THRESHOLD defines the maximum value authorized between the two directions of normal regularity to link salient points. AN GLET RESHOLD ) to discriminate edges. Indeed, the number of angles is very important because, the fewer the angles are, the longer the strings are. For example, it can be seen on figure 5 that when only four angles are used, some strings don't follow correctly the contour of the Lenna's hat. On the contrary, when eight angles are used, the strings are reduced to one point on the cameraman trench coat. As a consequence, it seems that choosing six angles is visually better.

About Small Strings Suppression

Small strings can be viewed as noise because they don't represent structural value added information. It can thus be interesting to eliminate them. To suppress small strings, only a threshold on the string length can be used. However, we have experimentally seen that it does not permit to improve classification results when the representation is used in a natural image classification task. The work four angles six angles eight angles Fig. 5. strings representations on well known images presented in [1] has lead to the same observation. Indeed, the authors try to eliminate signatures corresponding to small clusters in a kind of bag of key points approach and they have also seen that it does not improve results and that sometimes, it decreases it. As a consequence, in the following, all strings are kept in the final representation.

Discussions

At the beginning of this section, an image I was represented by a set of n local signatures denoted by S(I) = {s(1), . . . , s(n)}. In order to add spatial information to this orderless representation, we have presented a simple method to describe I by a set of m strings Λ(I) = {λ(1), . . . , λ(m)}. We hope that this representation will improve the recognition process by providing a better description of the image content. However, there is always a lack of ordering between the constructed strings. Consequently, it cannot be used immediately by a machine learning classifier. To solve this problem, a vectorial representation of strings should be elaborated.

As far as we know, no similar case of string representations was proposed in the literature. However, there were some attempts to add spatial information into the local representations. For example in [START_REF] Lazebnik | A maximum entropy framework for partbased texture and object recognition[END_REF], the coocurrence of local signatures are used to encode the final image signature. In [START_REF] Schmid | Local Grayvalue Invariants for Image Retrieval[END_REF] and [START_REF] Gouet | Object-Based Queries Using Color Points of Interest[END_REF], neighborhood constraints are added. The most similar approach is probably the one presented in [START_REF] Opelt | A Boundary-Fragment-Model for Object Detection[END_REF] representing an image by a set of edges. However, it does not use interest points but employs directly an edge detector to extract boundary fragments.

Unsupervised Classification of Strings

As previously emphasized, we aim at merging a string representation with the "bag of local signatures" representation introduced in [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF]. For this purpose, we have to cluster strings in order to represent an image as a "bag of strings". This approach permits to add local information to the representation while preserving the advantages of the "bag of local signatures" approach. For this purpose, a clustering algorithm able to deal with structured data (i.e. strings) should be used.

Many solutions have been proposed to cluster structured data. The K-medoid algorithm, which is an adaption of the k-means algorithm to data which do not live in a vectorial space, is probably the simplest way to cluster non vectorial data. This algorithm constrained the codewords to take value in the training dataset such that each cluster is represented by a medoid. The medoids are members of the learning dataset. However, it suffers from the same drawbacks than the k-means (the convergence into local minima).

In [START_REF] Laurent | A Cascade of Unsupervised and Supervised Neural Networks for Natural Image Classification[END_REF], a classical Self-Organizing Map (SOM) has been used to cluster the local signatures in order to construct a "bag of local signatures" representation.

The SOM aims at projecting the input data space D into a lower dimensional space (1D, 2D,. . . ) defined by a regular discrete lattice L composed of N L nodes.

Therefore, it is a vector quantization algorithm which preserves the topology of the input space because each node c of the lattice is a neuron with a codebook vector w(c) ∈ R n such that if c 1 and c 2 are close then w(c 1 ) and w(c 2 ) are close in R n . We will see in this section that we can use some existing extensions of the SOM to cluster the strings of local signatures.

SOM Clustering of Structured data -A State of the Art

In their original form, the Self-Organizing Map can only deal with vectorial data.

Thus, more complex data such as graphs or strings (or more generally temporal sequences) cannot be fed into a SOM. However, different solutions have been proposed to extend the SOM capabilities to process more complex data.

Temporal Kohonen Map Temporal Kohonen Map (TKM) have been introduced in [START_REF] Chappell | The Temporal Kohonen Map[END_REF] and are probably the earliest extension of SOM to the structured data. It can only process temporal sequences X = (x(1), . . . , x(n)) (thus strings)

and can be viewed as a classical SOM with different output neurons. Indeed, when an input x(t) is fed into a classical SOM, the processing of the next input

x(t + 1) by the SOM does not consider the previous state of the network (the value of the N L output neurons in the lattice). To overcome this drawback, TKM proposes to consider the previous state of the map. For this purpose, when an input x(t) is presented to a TKM, the output value y i of the neuron i in the lattice is computed as follows:

y i (t) = d × y i (t -1) - 1 2 ||x(t) -w(i, t)|| 2 (1)
⇒ y i (t) = d n y i (0) - 1 2 t-1 k=0 d k ||x(t -k) -w(i, t -k)|| 2 (2)
where 0 < d < 1 is a time constant. At time t, the best matching unit is chosen such that it maximizes y i (t), i ∈ {1, . . . , N L }. As a consequence, the output of previously activated neurons decrease with time and loose their activity. It is worth noting that the TKM differs only in the competitive rule because according to [START_REF] Koskela | Temporal Sequence Processing Using Recurrent SOM[END_REF], a classical SOM update rule is used to adapt the weights associated to the nodes. This update rule uses only the last elements x(t + 1) presented and does not consider the entire sequence.

Recurrent Self-Organizing Map Recurrent Self-Organizing Map (RSOM) has been proposed as an improvement of the TKM in [START_REF] Koskela | Temporal Sequence Processing Using Recurrent SOM[END_REF]. It proposes to consider the sequence processed in the update rule. For this purpose, the output y i of the node i in the lattice is now a vector. This output is computed as follows:

y i (t) = (1 -ǫ)y i (t -1) + ǫ(x(t) -w(i, t)) (3)
⇒ y i (t) = ǫ t k=1 (1 -ǫ) t-k (x(k) -w(i, k)) (4)
where 0 < ǫ ≤ 1 is the "leaky coefficient". It is worth noting the closer ǫ is from zero, the longer the memory of the RSOM is. The best matching unit y c (t) at step t is chosen by searching the node having the minimum output norm:

c = min i {||y i (t)||} (5)
and the update rule is then:

w(i, t + 1) = w(i, t) + α(t)h ci (t)y i (t). ( 6
)
where α(t) is the learning rate 0 < α(t) < 1 that monotonically decreases.

Furthermore, h ci denotes a neighborhood function that governs the strength of weight adaptation as well as the number of reference vectors to be updated.

Generally, a Gaussian function is used:

h ci (t) = exp - ||r c -r i || 2 2δ(t) 2 . ( 7
)
where r c and r i are the coordinates of the cells c and i in the lattice L and δ(t)

governs the width of the neighborhood function.

However, the RSOM suffers from the same drawback that the TKM: the context is only examined during the competitive and update rule. The SOM itself does not learn context because as emphasized in [START_REF] Strickert | Unsupervised recursive sequence processing[END_REF], a sequence is coded with a vector of the same dimension than its node attributes. It could be criticism when long sequences are considered.

Richer methods have thus been proposed in order to better represent the context. They propose to encode the context of a string node directly into the weight vector of the node lattice. For this purpose, several methods have been investigated, based on the same principle: increasing the dimension of the weight vector by a value encoding the previous state of the network.

Recursive Self-Organizing Map The Recursive Self-Organizing Map (Rec-SOM) introduced in [START_REF] Voegtlin | Recursive Self-Organizing Maps[END_REF] proposes to associate two vectors to each node 1 ≤ c ≤ N L of the discrete lattice. The first one is the classical weight vector denoted by w(c, t) ∈ R n (the codeword associated to each cluster of the input data space at time t). The second vector C(c, t) ∈ R NL is the context vector at time t that encodes the previous state of the RecSOM. This principle is shown on figure 6.

Fig. 6. RecSOM principle

At each iteration, the RecSOM algorithm computes the state y i (t) of each cell:

y i (t) = α||x(t) -w(i, t)|| 2 + β||F (y i (t -1)) -C(i, t)|| 2 . ( 8
)
The vector y(t) = (y 1 (t), . . . y NL (t)) encodes thus the RecSOM state at time t.

It is worth noting that for the stability of the representation, y(t) is not directly used as the context vector. Instead, F (y(t)), where F is a tranfert function, is employed. In [START_REF] Voegtlin | Recursive Self-Organizing Maps[END_REF], the author proposes to use the following transfert function:

F (y(t)) = (exp(-y 1 (t)), . . . , exp(-y NL (t))) . (9)
During the competitive rule, the best matching unit is chosen such that it minimizes y i (t). The update rule is a little bit more different than the classical Hebbian rule used in the SOM algorithm because it considers both vectors associated to a node of the lattice. For this purpose, it updates the weights of the SOM as follows:

w(i, t + 1) = w(i, t) + α(t)h ci (t)[x(t) -w(i, t)] (10)
C(i, t + 1) = C(i, t) + α(t)h ci (t)[F (y i (t -1) -C(i, t)] (11)
It has been shown that the RecSOM permits to obtain a good quantization of time series [START_REF] Voegtlin | Recursive Self-Organizing Maps[END_REF]. It is worth noting that this result has been obtained thanks to a new definition of the quantization error adapted to the time series. However, the context vector has the same dimension than the lattice resulting in a computational inefficiency [START_REF] Strickert | Unsupervised recursive sequence processing[END_REF].

Self-Organizing Map for Structured Data SOM for structured data (SOM-SD) have been introduced in [START_REF] Hagenbuchner | A Self-Organizing Map for Adaptive Processing of Structured Data[END_REF] and can be viewed as a simplification of the RecSOM by reducing its complexity. However, it is still a powerful alternative and, compared to other approaches, it has the advantage of dealing not only with sequential data but also with more complex structures such as Direct Acyclic Graphs.

SOM-SD is in the same spirit than RecSOM in the sense that it associates two vectors to each node of the discrete lattice. The first one is still the classical weight vector denoted by w(i, t) ∈ R n whereas the second one C(i, t) is the location in the map of the best matching unit at the previous step. Obviously, this difference permits to drastically reduce the complexity of the RecSOM because the SOM is often two dimensional and so is the context vector. The principle of the SOM-SD is shown on figure 7.

At each iteration t, the best matching unit denoted by bmu(t) = (x bmu (t), y bmu (t)) Fig. 7. principle of SOM-SD has to be found by computing:

bmu(t) = argmin 1≤i≤NL α||x(t) -w(i, t)|| 2 + β||bmu(t -1) -C(i, t)|| 2 . ( 12
)
An important emerging problem (also inherent in the RecSOM algorithm) is the choice of both α and β because they balance the importance of the label versus the importance of the context vector. Moreover, it has been experimentally

shown in [START_REF] Hagenbuchner | A Self-Organizing Map for Adaptive Processing of Structured Data[END_REF] that the final clustering is very sensible to these values.

In SOM-SD, the update rule is the same than the Hebbian rule used in both SOM and RecSOM:

w(i, t + 1) = w(i, t) + α(t)h ci (t)[x(t) -w(i, t)]; (13)
C(i, t + 1) = C(i, t) + α(t)h ci (t)[bmu(t -1) -C(i, t)]. (14)
It is worth noting that compared to the RecSOM, several extensions have been proposed in the field of the SOM-SD. These extensions concern the supervised classification already proposed in the classical SOM algorithm with LVQ (Learning Vector Quantization) algorithm. For example in [START_REF] Hagenbuchner | A Supervised Self-Organizing Map for Structured Data[END_REF] and [START_REF] Hagenbuchner | A Supervised Self-Organizing Map for Structures[END_REF], the authors propose to extend the weight vector associated to each node by a target label denoting the cluster of the string considered. More recently, in [START_REF] Hagenbuchner | A Supervised Training Algorithm for Self-Organizing Maps for Structures[END_REF] an LVQ algorithm using SOM-SD has been proposed.

Discussions and Selected Approach

In [START_REF] Strickert | Neural Gas for Sequences[END_REF] and [START_REF] Hammer | A General Framework for Unsupervised Processing of Structured Data[END_REF], the different SOM architectures have been compared and one of the major conclusions is that RecSOM and the SOM-SD are the best unsupervised way to discover clusters in a structured space. However, as underlined above, the RecSOM is computationally expensive representing thus a major drawback for the applications considered in this work. Indeed, an image is composed of hundreds strings and an efficient approach, both with regard to computing times and cluster quality, should be used.

As a consequence, we have chosen to use the SOM-SD to learn string prototypes that will be later used for the "bag of strings" representation.

The "Bag of Strings" Representation

We have shown that it is possible to cluster structured data such as attributed strings with an adapted self organizing map algorithm. It is thus possible to construct similar representations than those presented in [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF][START_REF] Jurie | Creating Efficient Codebooks for Visual Recognition[END_REF] in order to represent an image by a unique vector easily classifiable and that consider the spatial information contained in the image.

Presentation

Similarly to [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF], we propose to represent the image content by the probabilistic distribution denoted H over local strings. This distribution is numerically easy to compute because the space embedding strings has been quantized by using the SOM-SD algorithm. Consequently, each string activates a particular cell of the SOM-SD representation (the best matching unit called bmu), increasing thus the activity histogram of the SOM-SD H(Λ(I)) = [h 1 , . . . , h NL ] (where Λ(I) is the set of strings representing I) such that:

h l (I) = Card{λ(k) ∈ Λ(I)|l is the SOM-SD bmu associated to λ(k)}. ( 15
)
The

Experiments

We have experimented the "bag of strings" approach on different well known databases splitted into a training set and a testing set as presented in Appendix A. The main goal of the experiments is to determine if the representation proposed is better than the classical "bag of local signatures" representation because previous works [START_REF] Lazebnik | A maximum entropy framework for partbased texture and object recognition[END_REF] have shown that the use of spatial information is not very important in the case of natural image classification. Consequently, results and discussions concerning these experiments are presented in this section.

Due to the size of the discrete SOM-SD lattice used in the experiments (a rectangular 50 × 50 map), the final signatures obtained are embedded into a high dimensional space. As a consequence, the classification results shown in this section are obtained with a basic linear SVM classifier. Indeed, SVM classifiers are more adapted for dealing with high dimensional data and this is obviously the case here.

Finally, the detection of salient points has been performed by setting the energy threshold of the detector to 0.5 because experiments have shown this value leads to good classification results. Moreover, it permits to adapt automatically the number of salient points to the complexity of the image.

Study of Classification Results

When testing the approach, we have found that the global classification rates obtained depend strongly on the edge tracking algorithm and on the choice of the SOM-SD parameters (α and β). We will discuss in this section the influence of these parameters on the final results.

Influence of the SOM-SD Parameters As previously emphasized, the choice of the values of α and β is related to the importance of the label versus the importance of the context vector. At the present time, there does not exist a generic method to find them automatically and as a consequence, only an experimental study can be done in order to find the optimal values. For this purpose, we have chosen to vary β from 0.00001α to α with a logarithmic step.

Moreover, the edge tracking algorithm uses five neighbors and six angles because we will see in the section 6.1 that this is the best parameters.

The global classification rates obtained with this setup and a 50 × 50 SOM-SD for the databases presented in appendix A are presented on figure 9.

The curves show that for the configuration considered (the regularity descriptor with five neighbors and six angles), the best choice for the SOM-SD parameters α and β is to take β = 0.0001α for all databases.

A deeper study permits to say that this value seems logical because it corresponds to a kind of normalization between the context vector and the regularity descriptor element. Indeed, due to its normalization and its high dimension, the signature values are very low whereas the context vector takes value in the range [0, 50] which is the size of the SOM-SD. As a consequence, to take into account the signatures in the distance computed in the competitive step α should be larger than β.

In the following experiments, we will thus use β = 0.0001α because we consider it as a kind of optimal value.

Salient Point Tracking Algorithm

The salient point tracking algorithm presented in section 3.2 uses two parameters. The first NB NEIGHBORS is used to choose the number of nearest neighbors that should be considered to link salient points. We have experimentally observed that it has not a great influence on classification results. Moreover, the greater NB NEIGHBORS is, the larger are the computing times. Consequently, we use NB NEIGHBORS= 5 here because it permits to reach good classification rates in reasonable computing times.

The second parameters ANGLE THRESHOLD defines the maximum value authorized between the two directions of normal regularity to link salient points.

As presented in section 3.2, this threshold influences the length of the generated strings. Indeed, the strings are long when this value is small and as a consequence they do not follow edges. On the contrary, salient points are rarely linked, strings are thus very short and a kind of "bag of local signatures" representation is obtained if a large value is chosen. We present on figure 10, the global classification rates obtained for an ANGLE THRESHOLD of 4, 6 and 8.

We can see on this diagram that for all databases, choosing four angles leads for the scenes dataset. In the following we will thus use six angles as the optimal configuration for the salient points tracking algorithm.

Comparison with Other Approaches As previously emphasized, we would like to know if adding spatial constraints between salient points can improve classification results. For this purpose, we directly compare the best results obtained with a "bag of local signatures" approach using a classical self organizing map of size 50 × 50 to generate the dictionary to those obtained with a "bag of strings" approach with the optimal configuration found in the previous sections. 1. comparison of the "bag of local signatures" and the "bag of strings" approaches see that for all databases, the global classification results obtained with the "bag of strings" approach are better than those obtained with the "bag of local signatures" approach. As a consequence, it proves that adding spatial constraints brings some information in the final signature describing the image considered.

However, the improvement is not so important proving that the essential information contained in an image is encoded in the local signatures and not between them. This could be explain by the fact that spatial information is already partly taken into account when computing the local descriptor over the region of interest centered on the keypoint. The spatial information brought by our method is more a whole information that depending on the query, on the object, on the images, does not always brings significant information. Indeed, a deeper study has shown that the images newly well classified with our proposed approach always exhibits a significant spatial organization. For the Pascal dataset, classification results is really improved by more than 5% for the cars categorie but remains the same for the people categorie. It is due to the fact that contrarly to people, cars are hand manufactured objects whose images exhibit strong long edges well described by our method. For the SIMPLICITY dataset and according to [START_REF] Maree | Random subwindows for robust image classification[END_REF], the worst classification rate ever met is 37.5%. The best results found are those presented in [START_REF] Maree | Random subwindows for robust image classification[END_REF] and [START_REF] Deselaers | Features for Image Retrieval -A Quantitative Comparison[END_REF] with a global classification rate of 84.1%. It is better than our classification rate of 80.6%. However in these papers, the experiments are made with a leaving-one-out cross validation method. It consists of testing each image with a classifier trained with the remaining 999 images of the whole database. We have also tested our methods with the same approach and we obtain a global classification rate of 82%. Consequently, it could be said that our method is one of the best on this dataset.

On the difficult scenes dataset, we obtain a classification rates of 70.6%. In [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF], the authors obtain 72.2% with a bag of features approach similar to ours and 81.4% by adding to this approach global constraints which are shown important for this kind of database where global invariance is not needed. For the 13 categories used firstly in the paper [START_REF] Fei-Fei | A Bayesian Hierarchical Model for Learning Natural Scene Categories[END_REF], we attain 73.5% of correctly classified instances compared to 65.2% in [START_REF] Fei-Fei | A Bayesian Hierarchical Model for Learning Natural Scene Categories[END_REF] and 74.7% in [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]. Consequently, the architecture presented in this paper gives also good results. Nevertheless, adding global constraint as in [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF] seems essential to improve classification results.

Computing Times

The examination of computing times is very important in the evaluation of a natural image classification algorithm. Indeed, a commercial application should be user friendly and it is thus difficult to envisage that a user waits ten seconds to get the classification results. Due to the architecture of a supervised image classification application, most of the computing times used is due to:

1. the training step which is in fact the computation of the feature vectors for the whole training set and the learning of the classifier. It is often realized offline and can thus be long. As a consequence, it is thus not discussed here.

Conclusions and Discussions

In this paper, we have proposed an image representation whose goal is to overcome the major drawback of the "bag of local signatures" representation that does not consider any spatial ordering between interest points. For this purpose, we have proposed to link interest points and thus local signatures with an edge tracking algorithm in order to represent an image by a set of strings whose nodes are the local signatures. This set of strings has then been used in order to summarize the image content into a unique but large feature vector that encodes the frequency of appearance of the different strings. For this purpose, the string space has been quantized with a dedicated self organizing map.

We have shown that this monodimensional representation of the image can be easily integrated in a natural image classification environment and that a SVM classifier is suitable for classifying these high dimensional data. The representation achieves promising results on different well known databases. Indeed, the results obtained are slightly better that those obtained with a "bag of local signatures" representation proving thus that it is important to consider the mutual information between interest points in order to better represent the image content. The computing times are important in a natural image classification system and at the present time several seconds are necessary for our system to classify one image depending on its size. We currently work on the algorithm optimisation.

To improve classification performance, it can be interesting to implement a star model [START_REF] Fei-Fei | Learning Object Categories from Google's Image Search[END_REF] instead of a string model. Indeed, an image can be also represented by a set of stars representing close interest points and the star space can also be easily discretized by using a SOM-SD algorithm.

Finally, as in the "bag of local signatures" representation, the string dictionary size can be reduced by using a feature selection algorithm and other kernels can be used in the SVM classifier in order to take into account the topological ordering property of the SOM-SD.

3

  http://www.infotrends-rgi.com/home/Press/itPress/2005/1.11.05.html is an important difference between what the user wants and what the feature vectors really describe. This is the well known semantic gap problem.

Fig. 2 .

 2 Fig. 2. principle of the singularity descriptor

Fig. 3 .

 3 Fig. 3. original image (a) salient points (b) directions of minimal regularity

Figure 4 Fig. 4 .

 44 Figure 4 illustrates our method. In this figure, two regions are represented and salient points are drawn as circles. First and without loss of generality, the algorithm starts with p 1 (cf. figure 4(a)) and it searches the first neighbor which is p 2 and compare the direction of minimal regularity and the normal of the segment [p 1 , p 2 ]. If the comparison exhibits a small angle difference (below a threshold denoted ANGLE THRESHOLD), the points are linked (cf. figure 4(b)). Next,the point p 2 is considered and with the same process explained above, the point p 3 is added to the string (cf. figure4(c)). p 3 is then considered, but its neighbors are not compatible with regard to the angle tolerance. As a consequence, p 3 is an extremity of the string and p 1 is considered another time. p 4 is the next closest neighbor of p 1 not already processed and compatible with p 1 , resulting in its concatenation at the beginning of the string (cf. figure4(d)). Finally, on figure4(e), the first string is completely built and other points can be considered to construct new strings. The final image is shown on figure4(f) and contains two strings S 1 and S 2 .On figure5, the strings obtained from real images are shown. These representations are obtained using five nearest neighbors (i.e. N B N EIGHBORS = 5)

  2π

Fig. 8 .

 8 Fig. 8. computation of the "bag of strings" representation

1 Fig. 9 .

 19 Fig. 9. evolution of the global classification rate with β α

Fig. 10 .

 10 Fig. 10. influence of the edge tracking algorithm on the global classification rates

2 .

 2 The classification of a new image depending on the computation of the signatures and on the classification algorithm. Yet, the representation of an image by a set of strings whose node attributes are local salient signatures is more computationally difficult than representing an image by a set of local salient signatures due to the addition of the string creation algorithm and the SOM-SD projection employed to construct the histogram representation. However the SOM-SD projection is negligible because compared to a classical self organizing map, it only adds two values representing the context vector and increases slightly the time required for the competitive and the adaptation steps. On the opposite, the string construction imposes to compute a matrix storing distances between all interest points in the image considered and its computational complexity is O(n 2 ) where n is the number of interest points extracted. A deeper analysis of our implementation has shown that it increases the computing times of the classical bag of local signatures representation by approximately 50%.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. PASCAL 2005 Dataset

Fig. 13 .

 13 Fig. 13. SIMPLIcity Dataset

table 2 .

 2 Developing new methods for natural image classification is interesting and relevant for the computer vision domain if and only if the approaches proposed can be compared with other major methods presented in the literature. For the Pascal dataset, the methods are often evaluated by measuring the Area Under the ROC curve (Receiver Operating Characteristic curve) denoted AUC in the following. The comparison of classification results presented during the PASCAL 2005 recognition challenge with our results are presented on Compared to the results obtained during the challenge, we are ranked 6/18

	Class	Method Proposed Worst Best Mean
	Bicycles	0.957	0.724 0.982 0.905
	Cars	0.961	0.578 0.992 0.916
	Motorbikes	0.992	0.722 0.998 0.956
	People	0.926	0.597 0.979 0.901

Table 2 .

 2 comparison for the PASCAL dataset on the motorbikes class, 5/16 on bicycles class, 9/16 on people class and 9/18 on the cars class. Consequently, our method perform well but is not the best on this database. However, we have not searched to tune our parameters to obtain the best results on this particular dataset because we would like to exhibit a generic architecture whose aim is to perform well on different datasets. It is motivated by the fact that in a professional application, the parameters are initially fixed to reach good classification rates for different kind of databases.

http://www-cvr.ai.uiuc.edu/ponce grp/data/scene categories/scene categories.zip

http://wang.ist.psu.edu/ jwang/test1.tar

A Databases Presentation

In this paper, different datasets have been used to perform experiments and we propose in this chapter to briefly present them. It is worth noting that all datasets involved in this paper have been divided into two parts. Indeed, our work concerns supervised natural image classification and as a consequence a training set and a testing set are needed to test the algorithms presented.

A.1 PASCAL Dataset

The PASCAL dataset has been built for the PASCAL 2005 recognition challenge 4 . The goal of this challenge was to invite various research teams to compare 4 http://www.pascal-network.org/challenges/VOC/voc2005/index.html their object recognition methods on a common new dataset. More information about this challenge are presented in [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF]

A.2 Scene Dataset

The scene dataset 5 is a difficult dataset due to the totally subjective frontier between clusters. It contains fifteen scene categories: bedroom, suburb, industrial, kitchen, livingroom, coast, forest, highway, insidecity, mountain, opencountry, street, tall building, office and store. Each category contains 200 to 400 images and the average image size is 300 pixels. Several images of this dataset are shown on figure 12, and it is worth noting that this dataset is only composed of graylevel images. For the experiments, the same procedure is used than in [START_REF] Fei-Fei | A Bayesian Hierarchical Model for Learning Natural Scene Categories[END_REF]. It proposes to use 100 images per class for training and there are 3000 test images.