Trong-Ton Pham
email: ttpham@imag.fr

Philippe Mulhem
email: mulhem@imag.fr

Loïc Maisonnasse

Eric Gaussier

Joo-Hwee Lim

T.-T Pham

J.-H Lim

Visual graph modeling for scene recognition and mobile robot localization

Keywords: Graph theory, Information retrieval, Language model, Scene Recognition, Robot localization

Image retrieval and categorization may need to consider several types of visual features and spatial information between them (e.g., different point of views of an image). This paper presents a novel approach that exploits an extension of the language modeling approach from information retrieval to the problem of graphbased image retrieval and categorization. Such versatile graph model is needed to represent the multiple points of views of images. A language model is defined on such graphs to handle a fast graph matching. We present the experiments achieved with several instances of the proposed model on two collections of images: one composed of 3,849 touristic images and another composed of 3,633 images captured by a mobile robot. Experimental results show that using visual graph model (VGM) improves the

Introduction

Still image understanding and retrieval for computers are about combining multiple points of views. A broader perspective for multimedia document indexing and retrieval is given by R. Datta et al. in [START_REF] Datta | Image retrieval: ideas, influences, and trends of the new age[END_REF]:

"The future lies in harnessing as many channels of information as possible, and fusing them in smart, practical ways to solve real problems. Principled approaches to fusion, particularly probabilistic ones, can also help provide performance guarantees which in turn convert to quality standards for publicdomain systems."

This reflexion also holds in the specific context of image documents. The points of views of images rely on different regions extracted, different features generated and different ways to integrate these aspects in order to annotate or retrieve images based on their visual similarity. Let us present a short overview of the diversity of approaches encountered in the image annotation and retrieval domain. Image annotation and retrieval may use predefined segmentation in blocks [START_REF] Chua | Fast signature-based color-spatial image retrieval[END_REF], or try to consider segmentation techniques based on color/texture [6] or regions of interest like the well-known work of D. Lowe [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The feature considered are mostly represented using histograms of features (colors, textures or shapes) or of bag-of-word (BOW) proposed initially in [START_REF] Sivic | Video google: a text retrieval approach to object matching in videos[END_REF]. Other approach may consider spatial relationships between regions as in [START_REF] Smith | Visualseek: a fully automated content-based image query system[END_REF]. When considering more complex representations, approaches may use graph representations like in [START_REF] Ounis | Relief: combining expressiveness and rapidity into a single system[END_REF].

Despite the fact that selecting relevant regions and extracting good features are per se very difficult tasks, we believe that the way we represent different points of views of the image (like several segmentations and/or several features for instance) also has a great impact on image annotation and image retrieval. Our interest in this paper is twofold. First, we focus on a representation of image content, more precisely graph-based representation, which is able to represent different points of views (namely several visual representations and spatial relationships between regions). Second, we define a language model on such graphs that tackles the problem of retrieval and classification of images. Considering a graph to represent the features intends to preserve the diversity of content when needed. In fact, such graphs are versatile, because they can handle early fusion-like approaches when considering several representations in an integrated matching process as well as late fusionlike approaches when considering matching on specific sub-graphs before fusion. The interest of considering language models for such graphs lies in the fact that it benefits from this successful research field of information retrieval since the end of the 90s and in particular the seminal work of Ponte and Croft in [START_REF] Ponte | A language modeling approach to information retrieval[END_REF]. Such language models are well-defined theoretically, and also have shown interesting experimental results as synthesized in [START_REF] Manning | Language models for information retrieval[END_REF]. Therefore, our main focus in this paper is to propose an extension of language models [START_REF] Pham | Integration of spatial relationship in visual language model for scene retrieval[END_REF] in the context of graph-based representation for image content.

Related works

We consider here first the integration of relationships during the processing and/or the representation of images. When focusing on still images, the obvious kinds of relations are spatial relationships between image regions. For instance, image descriptions expressed by 2D-strings used in the Visualseek system [START_REF] Smith | Visualseek: a fully automated content-based image query system[END_REF]r e f l e c tt h e sequences of object occurrences along one or several reading directions. In this case an integration of visual feature of regions and spatial relationships is achieved. Retrieval on 2D-strings is complex: substring matching is a costly operation. However, heuristics to speed up the process do exist, as described in [START_REF] Chang | A unique-id-based matrix strategy for efficient iconic indexing of symbolic pictures[END_REF], which allows reduce the processing time by a factor of 10. Several works have considered visual features and relationships between image regions integrated into probabilistic models, e.g., through the use of 2D HMMs [START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF], through the use of normalized configuration vectors in [START_REF] Pham | Learning spatial relations in object recognition[END_REF], or graphical generative models and overlapping relationships in [START_REF] Han | Semantic image classification using statistical local spatial relations model[END_REF], but these works do not consider the relations during the retrieval process. Relationships between the elements of an image may also be expressed explicitly through naming conventions, as in [START_REF] Papadopoulos | Combining global and local information for knowledge-assisted image analysis and classification[END_REF] where the relations are used for indexing. Other attempts have integrated relationships in graphs like [START_REF] Mulhem | A framework for mixed symbolic-based and feature-based query by example image retrieval[END_REF] for indexing and retrieval. Nevertheless, considering the explicit relationships may generate complex graphs representations, an the retrieval process is likely to suffer from the complexity of the graph matching [START_REF] Ounis | Relief: combining expressiveness and rapidity into a single system[END_REF]. One of our aims here is to be able to represent the different points of views of images using graphs, without suffering from the burden of computationally expensive matching procedures.

Language models for information retrieval exist since the end of the 90s [START_REF] Ponte | A language modeling approach to information retrieval[END_REF]. In these generative models, the relevance status value of one document d for a query q is estimated using the probability P(q|d) of document d to generate query q.In [START_REF] Ponte | A language modeling approach to information retrieval[END_REF] the language model was based on a multiple Bernoulli distribution. Nevertheless, the predominant modeling assumption is now centered on multinomial distribution [START_REF] Song | General language model for information retrieval[END_REF]. Such models can use unigram (terms taken one by one) or n-grams (sequences of n terms) [START_REF] Song | General language model for information retrieval[END_REF]. However, these models lack an easy extension to integrate explicit relationships between terms. A core issue in language model is to estimate the probability when terms are absent in the documents due to the data sparseness. This may cause an inaccurate estimation of the overall probability (a.k.a. zero probability problems). To overcome this probability estimation problem, different smoothing methods [START_REF] Zhai | A study of smoothing methods for language models applied to ad-hoc information retrieval[END_REF] (such as Jelinek-Mercer, Dirichlet, etc.) have been proposed to adjust the maximum likelihood estimator of the language modeling. We will detail this technique in Section 3 using the Jelinek-Mercer smoothing technique.

Simple language models have been used for image indexing and retrieval [START_REF] Jeon | Automatic image annotation and retrieval using crossmedia relevance models[END_REF] without incorporating relationships between image regions. Some works applied language models for image annotation incorporated bigrams [START_REF] Wu | Visual language modeling for image classification[END_REF]a n dt r i g r a m s [START_REF] Gao | Automatic image annotation through multi-topic text categorization[END_REF] model, where these n-grams are built from spatially connected regions. Tirilly et al. in [START_REF] Tirilly | Language modeling for bag-of-visual words image categorization[END_REF] proposed to generate "sentences" built from projecting visual words on one given axis (according to the idea similar to the 2D-strings described above), in a way to generate from unigram to 4-grams language models on these visual "sentences". In this case, the spatial relationships are the precedence along the projection axis. Named relationships with generative models have been used in [START_REF] Boutell | Scene parsing using region-based generative models[END_REF] for image scenes, but the complexity of the learning of scene is prohibitive and experiments were achieved on small image sets.

Another work [START_REF] Maisonnasse | Revisiting the dependence language model for information retrieval[END_REF] has proposed to extend language models with relationships but focusing on texts. These approaches consider features and relationships, but do not consider several points of views according to several features extracted. Our work concentrates on modeling visual graphs composed of several types of concepts (i.e., visual words) and named relationships, which correspond to a different point of view of the images.

Our approach

We present in this paper the system architecture that consists of three main steps (see Fig. 1). The first step is to extract a set of visual concepts from each image feature considered, such as color, edge histogram or local features. The second step represents each image as a graph generated by a set of weighted concepts and a set of weighted relations. The third step is related to the fact that we want to retrieve relevant images to a given query. Therefore, we extend the work in [START_REF] Pham | Integration of spatial relationship in visual language model for scene retrieval[END_REF][START_REF] Pham | Spatial relationships in visual graph modeling for image categorization[END_REF]bytaking into account the different types of image representations and spatial relations during matching by computing likelihood of two graphs using a language model framework.

The contributions of this work are twofold. First, we present an unified graphbased framework for image representation which allows us to integrate different types of visual concepts and different spatial relations among them. Second, we extensively study the extension of language model for graph matching which allows a more reliable matching based on a well studied theory of information retrieval. The experimental results, performed on STOIC-101 and RobotVision '09 image collections, confirm the effectiveness of our visual graph model.

Outline of the paper

The remainder of this paper is structured as follows. We first present the visual graph model used to describe the image content in Section 2. Then, Section 3 discusses the matching of a trained graph given a query graph. Section 4 details our experimental results on two image collections. More precisely, the experiments focused on a relation between different types of concepts. Finally, we conclude the paper with a discussion in Section 5.

Image modeling

Inspired by the bag-of-word model in [START_REF] Hironobu | Image-to-word transformation based on dividing and vector quantizing images with words[END_REF], images are modeled as a set of visual concept (or concept in short) coming from different visual features. Our goal is to automatically induce, from a given image, a graph that represents the image content. Such a graph will contain concepts directly associated with the elements present in the image, as well as spatial relations which express how concepts are related in the image. To do so, our procedure is based on four main steps:

1. Identify regions within the image that will form the basic blocks for concept identification. 2. Index each region with a predefined set of visual features. 3. Cluster all the regions found in the collection into K classes, each class representing one concept. 4. Finally, extract relations between concepts.

As described before, several segmentation approaches already existed in the literature [START_REF] Smeulders | Content based image retrieval at the end of the early years[END_REF]. For the first step, we focus on three segmentation methods to define an image region: sampling pixel, grid partitioning and keypoint detection. The second step aims at representing each region as set of feature vectors for clustering purposes. We consider here several visual features (i.e., several points of views) extracted from one image region. For the pixel sampling method, each region is represented by its central pixel. The HSV color value of this pixel can be used as visual feature to represent images. We choose to focus on the HSV color space because of its robustness against illumination changes. In the case of grid partition, in our experiments, visual features extracted from the patches are color histograms and edge descriptors [START_REF] Won | Efficient use of mpeg-7 edge histogram descriptor[END_REF]. For the keypoint extraction, SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] are extracted within a given radius around the keypoint. The dimensionality for each feature is summarized in Table 1.

Next step consists of building visual concept vocabulary for each type of image representation (i.e., for each type of visual feature f ) as follows: (1) Unsupervised learning with k-means clustering groups similar feature vectors into the same cluster (each cluster corresponds to a visual concept c). Clustering transforms the continuous feature space into a discrete number of clusters. (2) Image is then represented by the number of occurrences for each concept in this image. Each type of image representation for a specific visual feature corresponds to a concept C f . Once these visual concepts are defined and characterized independently, the last step is to integrate the relationships between them. Existing work has proposed the use of topological relations between regions or between points in a 2D space [START_REF] Egenhofer | A framework for the definition of topological relationships and an approach to spatial reasoning within this framework[END_REF]. Based on this work, we will define the relationships between segmented regions. Figure 2 gives an example of spatial relations between visual concepts used in our experiment with STOIC collection. Relation sets left_of and top_of are extracted from the two connected concepts. These relations help to capture the spatial cooccurrence information of two visual concepts. For example, instances of the concept "sky" are usually on the top_of instances of the concept "tree", while instances of concept "tree" is more frequently on the left_of instances of concept "bridge". If the number of training image is large enough, the graph framework will capture the statistical consistency for this type of relation.

At the end of this procedure, we obtain a set of visual concepts C f and a set of predefined relations E for each type of concept and relation. Each concept is associated with a weight that represents its number of occurrences in the image. Similarly, each relation is also given a weight corresponds to the number of times this relation has occured in the image. We will denote the weighted concepts set by WC f and the weighted relations set by WE. As we may have several image representations (or point of views) and different kind of spatial relationships between them, in the end, we denote a set of weighted concept sets as S I WC f = f WC I f and a set of weighted relation sets as S I WE = WE I for an image I. Note that we tend to choose different types of visual features (i.e., color, edge, SIFT) which are visually independent [START_REF] Smeulders | Content based image retrieval at the end of the early years[END_REF] from each other to represent image content. Therefore, concept sets WC f are disjoint (e.g., WC color WC edge WC sift = ∅). From this observation, we could make an independent assumption based on the set of weighted concept set S I WC f . The similar assumption is also applied for weighted relation sets S I WE .

Graph definition

Given a set of weighted concept sets S I WC f and a set of weighted relation sets S I WE , the visual graph representing an image I is defined by:

G I =< S I WC f , S I WE >
where each concept c of concept set WC I f corresponds to a visual concept used to represent the image according to the feature f associated to it. The weight of concept captures the number of times of this concept appears in the image. Denoting C f a set of concepts for one feature over the whole collection, WC I f is a set of pairs (c, #(c, I))

WC I f ={(c, #(c, I))|c ∈ C f }
where c is an element of C f and #(c, I) is the number of times c occurs in the document image I. Any labeled relation between any pair of concepts

(c, c ′ ) ∈ C f × C f ′ is represented by a triple ((c, c ′ ), l, #(c, c ′ , l, I))
,wherel is an element of L, the set of possible labels for the relation, and #(c, c ′ , l, I) is the number of times c and c ′ are related with label l in image I. WE I is then defined as: Finally, this representation of graph will be used for the graph matching in the next step.

WE I ={((c, c ′ ), l, #(c, c ′ , l, I))|(c, c ′ ) ∈ C f × C f ′ , l ∈ L}

Language model for graph matching

Based on the language model defined over the graph proposed in [START_REF] Maisonnasse | Model fusion in conceptual language modeling[END_REF], we present in this paper an extension that handles set of concept sets and set of relation sets. The probability for a query image graph G Iq = < S Iq WC f , S Iq WE > to be generated from one document image graph G Id can be written as:

P(G Iq |G Id ) = P(S Iq WC f |G Id ) × P(S Iq WE |S Iq WC f , G Id ) (1)
where P(S Iq WC f |G Id ) is the probability of generating set of concept sets of the query graph from the document graph, and P(S

Iq WE |S Iq WC f , G Id )
is the probability of generating set of relation sets of the query graph from the document graph.

Concept set generation

For generating the probability of query concept sets from the document model P(S q WC f |G d ), we assume a concept set independence hypothesis (see our explanation in Section 2.1). The probability can thus be written as:

P(S Iq WC f |G Id ) = WC f Iq ∈S Iq WC f P(WC f Iq |G Id ) (2)
Assuming concept independence, which is standard in information retrieval, the number of occurrences of the concepts (i.e., the weights considered previously) are integrated through the use of a multinomial model. We compute P(WC f Iq |G Id ) as follows:

P(WC f Iq |G Id ) ∝ c∈C f P(c|G Id ) #(c,Iq) (3)
where #(c, Iq) denotes the number of times concept c occurs in the image query graph. This contribution corresponds to the concept probability as proposed in [START_REF] Maisonnasse | Model fusion in conceptual language modeling[END_REF]. Similar to the previous work, the quantity P(c|G Id ) is estimated through maximum likelihood using Jelinek-Mercer smoothing:

P(c|G Id ) = (1 -λ c ) #(c, Id) #( * , Id) + λ c #(c, D) #( * , D) (4)
where λ c is the smoothing parameter for each concept set C f . The quantity #(c, Id) represents the number of times c occurs in the document image Id and #( * , Id) is equal to c #(c, Id). The quantities #(c, D) and #( * , D) are similar, but defined over the whole collection D (i.e., over the union of all images in the collection).

Relation set generation

Assuming the relation set independence, as shown in previous section, we follow a similar process for generating the probability of the relation sets from document image graph, this leads to:

P(S Iq WE |S Iq WC f , G Id ) = W Iq E ∈S Iq WE P(W Iq E |S Iq WC f , G Id ) (5)
For the probability of generating query relation from the document, we assume that a relation depends only on the two linked sets. Assuming that the relations are independent and following a multinomial model, we compute:

P(W Iq E |S Iq WC f , G Id ) ∝ (c,c ′ ,l)∈C f ×C f ′ ×L P(L(c, c ′ ) = l|WC Iq f , WC Iq f ′ , G Id ) #(c,c ′ ,l,Iq) where c ∈ C f , c ′ ∈ C f ′
P(L(c, c ′ ) = l|WC Iq f , WC Iq f ′ , G Id ) = (1 -λ l ) #(c, c ′ , l, Id) #(c, c ′ , * , Id) + λ l #(c, c ′ , l, D) #(c, c ′ , * , D) (6)
#(c, c ′ , l, Id) #(c, c ′ , * , Id) = 0
Again, the quantities #(c, c ′ , l, D) and #(c, c ′ , * , D) are counted in a similar way but computed on the whole collection D (i.e., over the union of all the graphs from all the documents in the collection). This graph model is a generalization of the model defined in [START_REF] Pham | Integration of spatial relationship in visual language model for scene retrieval[END_REF] which corresponds to the special case where only one concept set and one relation set are used. In some special cases, our model corresponds to the standard language model (LM) used in [START_REF] Maisonnasse | Model fusion in conceptual language modeling[END_REF][START_REF] Pham | Visual language modeling for mobile localization: Lig participation in Robotvision'09[END_REF] where relations are not considered (i.e., documents and queries correspond to multiple bag-of-words model) .

In a more practical way, as done in [START_REF] Pham | Visual language modeling for mobile localization: Lig participation in Robotvision'09[END_REF], we compute the relevance status value (RSV) of a document image Id for query image Iq in the log-probability domain. Such domain, in the context of multinomial distributions, leads to the same ranking as the probability computed for G Id and G Iq . For image categorization, a query image Iq is then classified to a class of closest document image Id that estimated as follows:

class(Iq) = class(arg max Id∈D RSV(G Iq |G Id )) (7)
First, we describe the collections used to carry out our experimentation. Then, we present the results obtained with our model based on this collection. Our objective is to demonstrate that the visual graph model, as presented in previous section, is well adapted in representing image content. Furthermore, the integration of relationships to the graph helps to improve the image representation using only visual concepts. Finally, we give some discussions on our experimental results.

Scene recognition

STOIC-101 collection

The Singapore Tourist Object Identification Collection (STOIC) is a collection of 3,849 images containing 101 popular tourist landmarks (mainly outdoor). These images were taken, mostly with consumer digital cameras in a manner typical of a casual tourist, from three distances and four angles in natural light, with a mix of occlusions and cluttered background to ensure a minimum of 16 images per scene (see Fig. respectively. In the test set, the minimum number of images per class is 1, and the maximum is 21.

The main application of STOIC collection is for mobile image search. A user can upload an image taken with a hand-phone and post it as a query to the system. On the server-side, the images from the 101 scenes of the STOIC collection are matched against the user query. The server-side of this search engine architecture is two-tiers: (a) the query processing server takes a query image as input and generates a query graph file and (b) the language model server receives the query graph and computes the matching function based on graphs built from training images. Finally, textual information related to the matched scenes will be sent back to the user.

As a user can take one or several images of the same scene and query the system accordingly, we have considered several usage scenarios. Table 2 summarizes these different scenarios (a scene (S) corresponds to a group of images and a single image (I)). Note that some images in the collection have been rotated into the correct orientation (for both portrait and landscape layouts).

Proposed models

Several studies on the STOIC collection have shown that color plays a dominant role, and should be preferred to other visual features such as edge or texture [START_REF] Lim | Scene recognition with camera phones for tourist information access[END_REF]. Furthermore, color histogram can be easily and efficiently extracted. For these reasons, we rely only on HSV color features in our experiments. In order to assess the validity of our methodology, we followed different ways to divide each image into regions and we retained:

1. A division of medium grain, where blocks of 10 × 10 pixels are used, the center pixel being considered as a representative for the region. We refer to this division as mg. 2. A patch division where the image is divided into 5 × 5 regions of equal size. We refer to this division as gg.

For mg divisions, we used the (H, S, V) values as a feature vector for each pixel. Similary, each patch in gg division is quantized by a HSV histogram (4 bins/channel) that yields a 64-dimension vector for each region. We then clustered the HSV feature vectors of all regions into k = 500 classes with k-means clustering algorithm. This results in a hard assignment of each region to one concept. The set of weighted concepts, W C , is then obtained by counting how many times a given concept occurs in the image. The choice of k = 500 is motivated by the fact that we want a certain granularity in the number of concepts used to represent an image. With too few concepts, one is likely to miss important differences between images, whereas too many concepts will tend to make similar images look different. We will refer to the indexing obtained in this way as mg-LM and gg-LM, respectively for "division mg with automatically induced concepts" and "division gg with automatically induced concepts".

In addition, for the methods mg-LM and gg-LM, we extracted the spatial relations between concepts as mentioned previously: left_of and top_of, and counted how many times two given concepts are related through a particular relation in order to obtain the weights for our relations. This last step provides a complete graph representation for images. We will refer to these two complete methods as mg-VGM and gg-VGM. To summarize, we have constructed four models based on the visual concept sets and the relation sets:

1. mg-LM=< {W Cmg }, ∅ >, that used only mg division concepts. Last but not least, to classify query images in the 101 scenes, we used the language model for visual graphs presented in [START_REF] Gao | Automatic image annotation through multi-topic text categorization[END_REF]. When there is no relation, as in the cases of mg-LM and gg-LM,t h et e r mP(S q WE |S q WC , G d ) = 1 so that only concepts are taken into account to compare images.

Results

The performance of the different methods was evaluated using the accuracy, per image and per scene. They are defined as the ratio of correctly classified images or scenes. More precisely:

Image accuracy = TP i N i , Scene accuracy = TP s N s
where TP i and TP s represent the number of images and the number of scenes (respectively) correctly classified. N i is the total number of test images (i.e., 660 images), and N s the total number of scenes (i.e., 101 locations). Table 3 shows the results we obtained when using automatically induced (through clustering) concepts. As one can see, automatically inducing concepts with a medium grain division of the image yields the best results (the difference with the patch division for the S-I scenario being marginal). Overall, the mg division outperforms the gg division in most of the cases. Especially in the S-S scenario, the mg models obtained the best performance. One possible reason is that in mg division the number of concepts is far more than the one in the gg division. This being said, there is a difference between the I-S and S-I scenarios: The system is queried with more information in the I-S scenario than in the S-I scenario. This difference results in a performance which is, for all methods, worse for the S-I scenario than for the other ones. We conjecture that this is why the results obtained for the mg-VGM method on S-I are not as good as the ones for I-I. There seems to be a plateau for this scenario around 0.6, a hypothesis we want to explore in future work.

We finally assessed the usefulness of spatial relationships by comparing the results obtained with the different methods that include or not such relations. These results are displayed in Table 3. As one can note, except for the S-S scenario with the mg division, the use of spatial relations always improves the accuracy of the classifier. This justifies the framework we developed in Section 3 of language model for visual graphs including automatically induced concepts and spatial relations among them.

Mobile robot localization

The RobotVision'09 collection

The image collection came from the RobotVision'09 competition1 task (part of ImageCLEF campaign) aiming to address the problem of topological localization of a mobile robot using only visual information. The difficulty of this task is that the robot has to recognize the correct room in different illumination conditions and adapt as objects, new furniture, etc. are added over the time.

The RobotVision collection contains a sequence of 1,034 images for training and a sequence of 909 images for validation. Training and validation sets (see Fig. 5)were captured within an indoor laboratory environment consists of five rooms across a span of 6 months. Then, the official test has been carried out on a list of 1,690 images (recorded 20 months later). The collection comprises five annotated rooms (corridor-CR, printer area-PA, kitchen-KT, one-person office-BO, two-persons office-EO) and an unknown room from test set.

Proposed models

The system we used for the RobotVision competition was composed of two processes: a recognition step and a post-processing step. However, we describe and evaluate here only the recognition step, in such a way to assess the impact of the model proposed. The robot was trained with a sequence of images taken in the night condition. Then, we used a validation set captured in sunny condition to estimate the system parameters. The different concept sets and relation sets were extracted from the collection of images as follows:

1. Each image was divided into 5 × 5 patches. We extracted for each patch a HSV color histogram and an edge histogram as in Section 2.1. Then, the visual vocabulary of 500 visual concepts was constructed by using k-means clustering algorithm. From this vocabulary, we built the weighted concept set W Cpatch . 2. Similar to the previous step except that the visual features were extracted from the local keypoints. To be more precise, we detected scale invariant keypoints using SIFT detector [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] for each images. Local features were then used to create the weighted concept set W Csift . Similar to above, we referred to the model without relation as LM (simply the production of probability generated by different concept sets) and the graph model with the spatial relation as VGM (with the contributing of relation probability to graph model). Based on this definition, we have implemented several graphs to measure the performance of our proposed model:

1. LM P =< {W Cpatch }, ∅ >, that used only patch concepts. 2. LM S =< {W Csift }, ∅ >, that used only SIFT feature concepts. 3. LM S.P =< {W Csift , W Cpatch }, ∅ >, that used both patch and SIFT feature concepts. 4. VGM S→P =< {W Csift , W Cpatch }, {W Einside } >, that used patch concepts, SIFT feature concepts and the inside relations between them. Figure 6 gives an example of the graph extracted from the concept sets and relation sets defined above. In fact, the first three models were estimated following the equation presented in Section 3.1. The fourth model is the fusion graph combined with spatial relation. Its probability was computed according to the equation defined in Section 3.2.

Results

The evaluation measured the differences between the actual room id and the one classified by the systems. The following rules were used when calculating the official score for a test sequence: +1.0 points for each correctly classified image; -0.5 points for each misclassified image. So, higher score means higher accuracy.

Table 4 describes the results in terms of score value for each model. As expected, the two basic models LM P and LM S gave a good score for the validation set. However, the model LM P did not perform well on the test set due to the introduction of new room and new arrangement of interior furniture. The simple fusion model LM S.P underperformed the best results of LM P and LM S . However, this result was more robust in the sense that it leveraged on the spurious effects of each visual feature (i.e., LM S.P outperformed the averaged result of LM P and LM S in both cases). Moreover, the introduction of inside relations to the completed graph VGM S→P boosted its results respectively by 39.5 and 40.1% comparing to the fusion graph LM S.P for both validation set and test set. This fact confirmed that the integration of relations played a significant role to improve the results. In addition, it showed that the link between object details and its global presentation provides a better abstraction for image content.

We present in detail the classification accuracies for each class (represented by its room id) as categorized by our algorithms in Table 5. For each class, the accuracy is computed by the number of correctly labeled images divided by the total number of images belonging to this class. Here, we only consider the classification accuracies of five rooms as we did not treat the unknown room in the test sequence at this step. Due to the paper constrains, the reader may refer to [START_REF] Pham | Visual language modeling for mobile localization: Lig participation in Robotvision'09[END_REF] for more infomation on the post-processing step of the results.

Generally, the graph model for SIFT concepts LM S performs better than the graph model for patch concepts LM P . This leads us to a conclusion that the details of object are important clues for scene recognition. In addition, the simple fusion model LM S.P tried to leverage the effect on both model LM S and LM P and improved the results only in the case of two-person office (EO). All four models gave good accuracies for the corridor (CR) regardless of brutal changes in light conditions. We also noted that the number of training images for corridor (CR) was the highest (483/1,034 images) comparing to other classes. It suggests that the higher the number of image samples, the more robust the performance is.

Overall, the fusion graph combined with spatial relations VGM S→P gave better accuracies in the major cases except in the case of corridor (CR) for test set. However, the difference was not significant comparing to other models (only 2% less than the LM S.P graph model). Furthermore, the mean accuracy of model VGM S→P achieved on the test set and the validation set were the best of four models, with more than 7% better than the simple fusion model VGM S.P . This result confirms again the strength of spatial relationships contributed in our graph model.

Disscussions

Cross validation optimization with STOIC collection

The results presented above are optimized a posteriori, i.e., we exhaustively tested the parameters on the test set to get the best configuration. This approach overestimates the proposed algorithms, by giving an upper bound of the evaluation results and not a correct estimation. In a way to estimate more precisely the results, we optimized the smoothing parameters on a validation set for the mg-LM method, because this approach gives the best results. To achieve this optimization, a threefold cross validation was performed. Once the parameters were optimized for each of the three training/validation sets, we processed the test set using the whole training set. Table 6 shows the average (Avg) and standard deviation (Std-dev) of the three results obtained. The last column of Table 6 exhibits the difference in percentage for the evaluation measurement between the three-fold results and the a posteriori optimization.

As shown by Table 6, the results obtained by the cross validation and by a posteriori optimization are very similar. If we focus on the results of the I-I, S-I and S-S configurations, the differences are smaller than 1%, and for the configuration I-S the three-fold results are 4.46% lower. So, the optimization used on the validation sets provides satisfying results for a medium grain and for automatically defined visual concepts. We also tested three-fold cross validation with relationships, as presented in Table 7. Here again the results with the cross validations are very close to the a posteriori optimized results: the S-I and S-S results are almost equal.

Another conclusion drawn from Tables 6 and7 is that, with a cross validation procedure, the usage of relationships still outperforms the results without relationships: +0.5%forthecaseI-I,+19.6% for I-S, and +12.3% for S-I. For the case S-S no improvement is achieved, which is also consistent with the a posteriori optimized results.

Comparing to SVM method

In order to assess the validity of our methods, we have compared the results with the state-of-the-art method in image categorization such as SVM classification method (implemented thanks to the libsvm2 ). We applied the same visual features used for graph model in our experiment. The input vector in SVM classifier is the early fusion of the multiple bag-of-word models. Then, each image class was trained with a corresponding SVM classifier using radial basis function (RBF). To optimize the kernel parametters, we train SVM classifiers with three-fold cross validation on the training set. Finally, these classifiers are used to classify the new query image.

Similar to above, we refer to the model with only the contribution of concept as LM and model with the spatial relation as VGM. For STOIC collection, we choose the mg division as a comparison model. Likewise for RobotVision collection, we choose the model LM S.P as LM and VGM S→P as VGM.

Implementation

The system is implemented in C/C++ with the LTI-Lib3 and compiled on a Linux platform. Image indexing and querying are performed on a 3.0 GHz quad-core computer with 8.0 Gb of memory. Training step takes about 2 h for the whole training images set from extracting visual features, clustering the concepts and modeling trained graphs. For the query step, it takes about 0.22 s on average (or 5 images/second) for computing the likelihood of graph query with all the graphs stored in database. However, the computation is highly parallelizable given graph models are stored and are processed independently. It shows that the graph matching step is very reliable for image matching comparing to classical graph matching algorithm.

Conclusion

We have introduced in this paper a graph-based model for representing image content. This graph captured the spatial relations among visual concepts associated with extracted regions of images. Theorically, our model fits within the language modeling approach for information retrieval, and extends previous proposals based on graph representation. On a more practical aspect, the consideration of regions and associated concepts allows us to gain generality in the description of images, a generality which may be beneficial when the usage of the system slightly differs from its training environment. This is likely to happen with image collections that, for example, use one or several images to represent a scene. On the other hand, querying a specific location with a group of images is very promising in future application (such as mobile localization) that allows higher accuracy rate with less computational effort comparing to video sequence. In addition, as demonstrated in the case of RobotVision, the way of combining of different image representations/features in the graph framework is more versatile comparing to other fusion approaches.

On the experimental side, we have conducted the test on two image collections (STOIC-101 and RobotVision'09). The experiments aim at assessing the validity of our approach in certain aspects. In particular, we showed that integrating spatial relations to represent images led to a significant improvement in the results. The model we have proposed is able to adequately match images and sets of images represented by graphs. As we conjectured, being able to abstract from a low level description allows robustness with respect to the usage scenarios. We also discussed on optimimizing the smoothing parameters of the language model with the cross validation technique based on training image set. We also demonstrated that our graph models outperformed the current state-of-the-art SVM method for image classification.

To summarize, the major contributions of our approach are: (1) a well-founded graph model for image indexing and retrieval, (2) with a smooth integration of spatial relations and visual concepts in the framework and (3) with a simpler and more effective graph matching process based on the language model.

In the future, many aspects can be considered to extend our graph model. First of all, as the language model is coming from textual domain, we could combine the graph representation of image with the graph representation of the annotated text as done in ImageCLEF photographic retrieval track. In our case, this could be integrated smoothly as they shared the same probabilistic framework. There is also the need to study different visual concepts and their spatial relations. This should be adapted following a specific image context or towards a typical scenario of image retrieval. Moreover, experiment on a large collection of images (such as ImageCLEF or VOC collection) could be interesting to test the scalability of our method. Last but not least, we also wish to investigate different possible couplings of the low level and high level representations, with the hope to come up with a single representation that could be used in a general case.

Fig. 1

 1 Fig. 1 System architecture of the graph-based model for scene retrieval/annotation

Fig. 2

 2 Fig. 2 Example of spatial relations extracted from image. a Scene of a bridge, b visual concept extraction, c relations left_of and top_of extracted from concepts

  If a pair of concepts (c, c ′ ) come from the same concept set (i.e., C f = C f ′ ), we refer this relation as intra-relation. Otherwise, we refer it as inter-relation.

Figure 3

 3 shows an example of our graph constructed from an image of a bridge scene. This example corresponds to a visual graph containing one visual concept set (C color ) and two intra-relation sets (E left_of and E top_of ). Each node corresponds to a concept and the number of time it occurs in the image. For example, concept c1 appeared two times in the image and is denoted by (c1,#2) in the figure. Likewise, the relation between a couple of concepts is also captured by the directed arcs in this graph. Here, the blue arcs express the relation left_of and the green arcs express the relation top_of of two connected concepts. For example, concept c1 is related to concept c2 with the relation top_of two times and is related to itself by the relation left_of two times. It is denoted by (c1, c2, top_of, #2)a n d( c 1 ,c 1 ,left_of, #2).

Fig. 3

 3 Fig. 3 Example of a visual graph extracted from an image. Concepts are represented by nodes and spatial relations are expressed by directed arcs. Nodes and links are weighted by the number of times they appear in the image

  and L(c, c ′ ) are variables which values in L and which reflect the possible relation labels between c and c ′ , in this relation set. As before, the parameters of the model P(L(c, c ′ ) = l|WC Iq f , WC Iq f ′ , G Id ) are estimated by maximum likelihood with Jelinek-Mercer smoothing, giving:

where λ l

  is the smoothing parameter for each relation set E. The quantity #(c, c ′ , l, Id) represents the number of times concepts c and c ′ are linked with label l in the document image Id,a n d#(c, c ′ , * , Id) is equal to l∈L #(c, c ′ , l, Id).B y convention, when one of the two concepts does not appear in the image d,weset:

Fig. 4

 4 Fig. 4 Images of STOIC-101 collection are taken from different angles, viewpoints and weather conditions

Fig. 5

 5 Fig. 5 Example images from RobotVision'09 collection: a training set in night condition, b validation set in sunny condition, c test set in unknown condition, d the local area map

Fig. 6

 6 Fig. 6 Graph model constructed for RobotVision includes two type of image representation and one type of relation

Table 1

 1 Visual features used for each type of image representation

	Region type	Features	Dimensions
	Pixel	(H,S,V) value	3
	Patch	HSV histogram	64
	Patch	Edge histogram	80
	Keypoint	(5 scales × 16 orientations) SIFT descriptor

Table 2

 2

	Summary of experiments on STOIC-101 collection	Query by (I) Query by (S)	Training by (I) √√ Training by (S) √√

  2. mg-VGM=< {W Cmg }, {W Ele f t_of , W Etop_of },t h a tu s e dmg division concepts and two intra-relation sets left_of and top_of. 3. gg-LM=< {W Cgg }, ∅ >, that used only gg concepts. 4. gg-VGM=< {W Cgg }, {W Ele f t_of , W Etop_of },t h a tu s e dgg concepts and two intrarelation sets left_of and top_of.

Table 3

 3 Impact of spatial relations on the performance (best results are in bold, relative improvement over the method without relations is in parentheses)

	Training	Query	mg-LM	mg-VGM	gg-LM	gg-VGM
	I	I	0.789	0.794 (+0.6%)	0.484	0.551 (+13.8%)
	I	S	0.822	1.00 (+21.6%)	0.465	0.762 (+63.8%)
	S	I	0.529	0.594 (+12.3%)	0.478	0.603 (+26.1%)
	SS	1.00	1.00	0.891	0.920 (+3.2%)

Table 4

 4 Results of different graph models

	Graph model	LM P	LM S	LM S.P	VGM S→P
	Validation set	345	285	334.5	466.5 (+39.5%)
	Test set	80.5	263	209.5	293.5 (+40.1%)

Table 5

 5 Classification accuracies of graph models for each room

		BO	CR	EO	KT	PA	Mean
	Validation set
	LM P	0.257	0.779	0.524	0.450	0.434	0.489
	LM S	0.354	0.658	0.581	0.426	0.402	0.484
	LM S.P	0.398	0.679	0.613	0.519	0.426	0.527
	VGM S→P	0.416	0.829	0.702	0.550	0.492	0.598
	Test set
	LM P	0.163	0.701	0.385	0.236	0.279	0.353
	LM S	0.331	0.721	0.478	0.509	0.348	0.477
	LM S.P	0.206	0.756	0.484	0.410	0.286	0.428
	VGM S→P	0.369	0.736	0.540	0.516	0.344	0.501

Table 6

 6 Comparison of the results mg-LM-val on three-fold cross validation, and percentage of difference in accuracy compared to the a posteriori optimization model mg-LM

	Training	Query	mg-LM	mg-LM-val		Diff (%)
				Avg	Std-dev
	I I S	I S I	0.789 0.822 0.529	0.784 0.785 0.529	5.8 × 10 -3 5.8 × 10 -3 0.0	-0.68 -4.46 0
	S	S	1.00	0.990	1.7 × 10 -2	-0.01

Table 7

 7 Comparison of the results mg-VGM-val on three-fold cross validation, and percentage of difference in accuracy compared to the a posteriori optimization model mg-VGM

	Training	Query	mg-VGM	mg-VGM-val		Diff (%)
				Avg	Std-dev
	I I S	I S I	0.794 1.00 0.594	0.788 0.939 0.594	6.4 × 10 -3 5.3 × 10 -2 0.0	-2.64 -6.07 0
	S	S	1.00	0.990	1.7 × 10 -2	-0.01

Table 8

 8 Results on categorizing STOIC-101 and RobotVision'09 collections comparing to SVM method

		#class	SVM	LM	VGM
	STOIC-101	101	0.744	0.789 (+6.0%)	0.794 (+6.3%)
	RobotVision'09
	Validation	5	0.535	0.579 (+8.2%)	0.675 (+26.2%)
	Test	6	0.439	0.416 (-5.2%)	0.449 (+22.8%)

Table 8

 8 summarizes the results obtained from both collection STOIC-101 and RobotVision'09. We can see that in all cases our VGMs outperform other methods. More precisely, with the integration of spatial relation into VGM helps improving the accuracy of classical approaches of LM by at least 2.5%. Especially with the Robot-Vision collection, VGMs increase roughly the accuracies of 22.8-26.2% comparing to SVM respectively for both test and validation set. Lastly, the VGMs retain medium to large improvements over the standard LMs in both image collections as confirmed in previous section.

http://imageclef.org/2009/robot

http://www.csie.ntu.edu.tw/cjlin/libsvm/

http://ltilib.sourceforge.net/

Acknowledgements This work was supported by the French National Agency of Research (ANR-06-MDCA-002). Pham Trong-Ton would like to thank Merlion programme of the French Embassy in Singapore for their supports during his Ph.D study.


Michalis Christou
email: [michalis.christou@dcs.kcl.ac.uk

Maxime Crochemore
email: maxime.crochemore@dcs.kcl.ac.uk

Costas S Iliopoulos

Marcin Kubica
email: [kubica@mimuw.edu.pl

Solon P Pissis
email: solon.pissis]@dcs.kcl.ac.uk

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Tomasz Waleń
email: walen]@mimuw.edu.pl

Efficient Seeds Computation Revisited ⋆

.

Introduction

The notion of periodicity in strings is widely used in many fields, such as combinatorics on words, pattern matching, data compression and automata theory (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Lothaire | Applied Combinatorics on Words[END_REF]). It is of paramount importance in several applications, not to talk about its theoretical aspects. The concept of quasiperiodicity is a generalization of the notion of periodicity, and was defined by Apostolico and Ehrenfeucht in [START_REF] Apostolico | Efficient detection of quasiperiodicities in strings[END_REF]. In a periodic repetition the occurrences of the period do not overlap. In contrast, the quasiperiods of a quasiperiodic string may overlap.

We consider words (strings) over a finite alphabet Σ, u ∈ Σ * ; the empty word is denoted by ε; the positions in u are numbered from 1 to |u|. By Σ n we denote the set of words of length n. By u R we denote the reverse of the string u. For u = u 1 u 2 . . . u n , let us denote by u[i . . j] a factor of u equal to u i . . . u j (in particular u[i] = u[i . . i]). Words u [1 . . i] are called prefixes of u, and words u[i . . n] are called suffixes of u. Words that are both prefixes and suffixes of u are called borders of u. By border(u) we denote the length of the longest border of u that is shorter than u. We say that a positive integer p is the (shortest) period of a word u = u 1 . . . u n (notation: p = per(u)) if p is the smallest positive number, such that u i = u i+p , for i = 1, . . . , np. It is a known fact [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF] that, for any string u, per(u) + border(u) = |u|.

We say that a string s covers the string u if every letter of u is contained in some occurrence of s as a factor of u. Then s is called a cover of u. We say that a string s is: a seed of u if s is a factor of u and u is a factor of some string w covered by s; a left seed of u if s is both a prefix and a seed of u; a right seed of u if s is both a suffix and a seed of u (equivalently, s R is a left seed of u R ). Seeds were first defined and studied by Iliopoulos, Moore and Park [START_REF] Iliopoulos | Covering a string[END_REF], who gave an O(n log n) time algorithm computing all the seeds of a given string u ∈ Σ n , in particular, the shortest seed of u.

By cover(u), seed(u), lseed(u) and rseed(u) we denote the length of the shortest: cover, seed, left seed and right seed of u, respectively. By covermax(u) and lseedmax(u) we denote the length of the longest cover and the longest left seed of u that is shorter than u, or 0 if none.

For a string u ∈ Σ n , we define its: period array P[1 Table 1. An example string together with its periodic and quasiperiodic arrays. Note that the left-seed array and the seed array are non-decreasing.

P[i] = per(u[1 . . i]), B[i] = border(u[1 . . i]), P ′ [i] = per(u[i . . n]), C[i] = cover(u[1 . . i]), C M [i] = covermax(u[1 . . i]), Seed[i] = seed(u[1 . . i]), LSeed[i] = lseed(u[1 . . i]), LSeed M [i] = lseedmax(u[1 . . i]).
The border array, suffix border array and period array can be computed in O(n) time [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF]. Apostolico and Breslauer [START_REF] Apostolico | Of periods, quasiperiods, repetitions and covers[END_REF][START_REF] Breslauer | An on-line string superprimitivity test[END_REF] gave an on-line O(n) time algorithm computing the cover array C[1 .

. n] of a string. Li and Smyth [START_REF] Li | Computing the cover array in linear time[END_REF] provided an algorithm, having the same characteristics, for computing the longest cover array C M [1 .

. n] of a given string. Note that the array C M enables computing all covers of all prefixes of the string, same property holds for the border array B.

Unfortunately, the LSeed M array does not share this property. Table 1 shows the above defined arrays for u = abaabaaabbaabaab. For example, for the prefix u[1 . . 13] the period equals 11, the border is ab, the cover is abaabaaabbaab, the left seed is abaabaaabba, the longest left seed is abaabaaabbaa, and the seed is baabaaab.

We list here several useful (though obvious) properties of covers and seeds.

Observation 1 (a) A cover of a cover of u is also a cover of u. (b) A cover of a left (right) seed of u is also a left (right) seed of u.

(c) A cover of a seed of u is also a seed of u. For example maxgap({1, 3, 8, 13, 17}) = 5. For a factor v of u, let us define Occ(v, u) as the set of starting positions of all occurrences of v in u. By first(v) and last (v) we denote min Occ(v, u) and max Occ(v, u) respectively. For the sake of simplicity, we will abuse the notation, and denote maxgap(v) = maxgap(Occ(v, u)). Notions of maxgaps and border seeds provide a useful characterization of seeds. Observation 3 Let s be a factor of u ∈ Σ * . The word s is a seed of u if and only if |s| ≥ maxgap(s) and s is a border seed of u.

(d) If u is a factor of v then seed(u) ≤ seed(v). (e) If u is a prefix of v then lseed(u) ≤ lseed(v). (f
Several new and efficient algorithms related to seeds in strings are presented in this paper. Linear time algorithms computing left-seed array and longest left-seed array are given in Section 2. In Section 3 we show a linear time algorithm finding seed-of-a-given-length and apply it to computing the seed array of a string in O(n 2 ) time. Finally, in Section 4 we describe an alternative simple O(n log n) time computation of the shortest seed, from which we obtain an O(n log (n/m)) time algorithm checking if the shortest seed has length at least m (described in Section 5).

Computing Left-Seed Arrays

In this section we show two O(n) time algorithms for computing the left-seed array and an O(n) time algorithm for computing the longest left-seed array of a given string u ∈ Σ n . We start by a simple characterization of the length of the shortest left seed of the whole string u -see Lemma 5. In its proof we utilize the following auxiliary lemma which shows a correspondence between the shortest left seed of u and shortest covers of all prefixes of u. Lemma 4. Let s be a prefix of u, and let j be the length of the longest prefix of u covered by s. Then s is a left seed of u if and only if j ≥ per(u).

In particular, the shortest left seed s of u is the shortest cover of the corresponding prefix u[1 . . j].

Proof. (⇒) If s is a left seed of u then there exists a prefix p of s of length at least nj which is a suffix of u (see Fig. 2). We use here the fact, that u[1 . . j] is the longest prefix of u covered by s. Hence, p is a border of u, and consequently border(u) ≥ |p| ≥ nj. Thus we obtain the desired inequality j ≥ per(u). (⇐) The inequality j ≥ per(u) implies that v = u[1 . . j] is a left seed of u (see Fig. 3). Hence, by Observation 1b, the word s, which is a cover of v, is also a left seed of u.

Finally, the "in particular" part is a consequence of Observation 1, parts b and f. ⊓ ⊔ . n] be its cover array. Then:

lseed(u) = min{C[j] : j ≥ per(u)}. (1

⊓ ⊔

Clearly, the formula (1) provides an O(n) time algorithm for computing the shortest left seed of the whole string u. We show that, employing some algorithmic techniques, one can use this formula to compute shortest left seeds for all prefixes of u, i.e., computing the left-seed array of u, also in O(n) time.

Theorem 1. For u ∈ Σ n , its left-seed array can be computed in O(n) time.

Proof. Applying (1) to all prefixes of u, we obtain:

LSeed[i] = min{C[j] : P[i] ≤ j ≤ i}. (2)
Recall that both the period array P[1 .

. n] and the cover array

C[1 . . n] of u can be computed in O(n) time [1, 4, 6, 8].
The minimum in the formula (2) could be computed by data structures for Range-Minimum-Queries [START_REF] Fischer | A new succinct representation of RMQ-information and improvements in the enhanced suffix array[END_REF][START_REF] Sadakane | Succinct data structures for flexible text retrieval systems[END_REF], however in this particular case we can apply a much simpler algorithm. Note that P[i -1] ≤ P[i], therefore the intervals of the form [P[i], i] behave like a sliding window, i.e., both their endpoints are nondecreasing. We use a bidirectional queue Q which stores left-minimal elements in the current interval [P[i], i] (w.r.t. the value C[j]). In other words, elements of Q are increasing and if Q during the step i contains an element j then j ∈ while

[P[i], i] and C[j] < C[j ′ ] for all j < j ′ ≤ i.
(not empty(Q)) and (C[back (Q)] ≥ C[i]) do popBack (Q); 6: pushBack (Q, i); 7: LSeed[i] := C[front (Q)]; 8: { Q stores left-minimal elements of the interval [P[i], i] } 9: return LSeed[1 . . n];
Now we proceed to an alternative algorithm computing the left-seed array, which also utilizes the criterion from Lemma 4. We start with an auxiliary algorithm ComputeR-Array. It computes an array R[1 . . n] which stores, as R[i], the length of the longest prefix of u for which u[1 . . i] is the shortest cover, 0 if none.

ALGORITHM ComputeR-Array(u) 1: C[1 . . n] := cover array of u; 2: for i := 1 to n do R[i] := 0; 3: for i := 1 to n do R[C[i]] := i; 4: return R[1 . . n];
The algorithm Alternative-ComputeLeftSeedArray computes the array LSeed from left to right. The current value of LSeed[i] is stored in the variable ls, note that this value never decreases (by Observation 1e). Equivalently, for each i we have

LSeed[i -1] ≤ LSeed[i] ≤ i.
The particular value of LSeed[i] is obtained using the necessary and sufficient condition from Lemma 4:

LSeed[i] = ls if ls is the smallest number such that |w| ≥ per(u[1 . . i]) = P[i],
where w is the longest prefix of u[1 . . i] that is covered by u[1 . . ls]. We slightly modify this condition, substituting w with the longest prefix w ′ of the very word u that is covered by u[1 . . ls]. Thus we obtain the condition R[ls] ≥ P[i] utilized in the pseudocode below. . n] can be computed in linear time [START_REF] Apostolico | Of periods, quasiperiods, repetitions and covers[END_REF][START_REF] Breslauer | An on-line string superprimitivity test[END_REF][START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF]. The array R[1 . . n] is obviously also computed in linear time.

It suffices to prove that the total number of steps of the while-loop in the algorithm Alternative-ComputeLeftSeedArray is linear in terms of n. In each step of the loop, the value of ls increases by one; this variable never decreases and it cannot exceed n. Hence, the while-loop performs at most n steps and the whole algorithm runs in O(n) time.

⊓ ⊔

Concluding this section, we describe a linear-time algorithm computing the longest left-seed array, LSeed M [1 .

. n], of the string u ∈ Σ n . The following lemma gives a simple characterization of the length of the longest left seed of the whole string u.

Lemma 6. Let u ∈ Σ n . If per(u) < n then lseedmax(u) = n -1, otherwise lseedmax(u) = 0.
Proof. First consider the case per(u) = n. We show that lseed(u) = n, consequently lseedmax(u) equals 0. Assume to the contrary that lseed(u) < n. Then, a non-empty prefix of the minimal left seed of u, say w, is a suffix of u (consider the occurrence of the left seed that covers u[n]). Hence, n -|w| is a period of u, a contradiction. Assume now that per(u) < n. Then u is a prefix of the word u[1 . .

per(u)] • u[1 . . n -1] which is covered by u[1 . . n -1]. Therefore u[1 . . n -1] is a left seed of u, lseedmax(u) ≥ n -1, consequently lseedmax(u) = n -1.
⊓ ⊔

Using Lemma 6 we obtain LSeed M [i] = i -1 or LSeed M [i] = 0 for every i, depending on whether P[i] < i or not. We obtain the following result.

Theorem 3. Longest left-seed array of u ∈ Σ n can be computed in O(n) time.

Computing Seeds of Given Length and Seed Array

In this section we show an O(n 2 ) time algorithm computing the seed array Seed[1 .

. n] of a given string u ∈ Σ n , note that a trivial approach -computing the shortest seed for every prefix of u -yields O(n 2 log n) time complexity. In our solution we utilize a subroutine: testing whether u has a seed of a given length k. The following theorem shows that this test can be performed in time.

Theorem 4. It can be checked whether a given string u ∈ Σ n has a seed of a given length k in O(n) time.

Proof. Assume we have already computed in O(n) time the suffix array SUF and the LCP array of longest common prefixes, see [START_REF] Crochemore | Algorithms on Strings[END_REF]. In the algorithm we start by dividing all factors of u of length k into groups corresponding to equal words. Every such group can be described as a maximal interval [i . . j] in the suffix array SUF, such that each of the values

LCP[i + 1], LCP[i + 2], . . . , LCP[j] is at least k.
The collection of such intervals can be constructed in O(n) time by a single traversal of the LCP and SUF arrays (lines 1-9 of Algorithm SeedsOfAGiven-Length). Moreover, using Bucket Sort, we can transform this representation into a collection of lists, each of which describes the set Occ(v, u) for some factor v of u, v ∈ Σ k (lines 10-11 of the algorithm). This can be done in linear time, provided that we use the same set of buckets in each sorting and initialize them just once. Now we process each of the lists separately, checking the conditions from Observation 3: in lines 14-18 of the algorithm we check the "maxgap" condition, and in line 19 the "border seed" condition, employing Fact 2.

Thus, having computed the arrays SUF and LCP, and the period arrays P[1 .

. n] and P ′ [1 . . n] of u, we can find all seeds of u of length k in O(n) total time.

⊓ ⊔ ALGORITHM SeedsOfAGivenLength(u, k) We compute the elements of the seed array Seed[1 .

. n] from left to right, i.e., in the order of increasing lengths of prefixes of u. Note that

Seed[i + 1] ≥ Seed[i] for any 1 ≤ i ≤ n -1, this is due to Observation 1d. If Seed[i + 1] > Seed[i]
then we increase the current length of the seed by one letter at a time, in total at most n -1 such operations are performed. Each time we query for existence of a seed of a given length using the algorithm from Theorem 4. Thus we obtain O(n 2 ) time complexity.

Theorem 5. The seed array of a string u ∈ Σ n can be computed in O(n 2 ) time.

In this section we present a new approach to shortest seeds computation based on very simple independent processing of disjoint chains in the suffix tree. It simplifies the computation of shortest seeds considerably.

Our algorithm is also based on a slightly modified version of Observation 3, formulated below as Lemma 7, which allows to relax the definition of maxgaps. We discuss an algorithmically easier version of maxgaps, called prefix maxgaps, and show that it can substitute maxgap values when looking for the shortest seed.

We start by analyzing the "border seed" condition. We introduce somewhat more abstract representation of sets of factors of u, called prefix families, and show how to find in them the shortest border seeds of u. Afterwards the key algorithm for computing prefix maxgaps is presented. Finally, both techniques are utilized to compute the shortest seed.

Let us fix the input string u ∈ Σ n . For v ∈ Σ * , by PREF (v) we denote the set of all prefixes of v and by PREF (v, k) we denote PREF (v) ∩ Σ k Σ * (limited prefix subset ).

Let F be a family of limited prefix subsets of some factors of u, we call F a prefix family. Every element PREF (v, k) ∈ F can be represented in a canonical form, by a tuple of integers: (first (v), last (v), k, |v|). Such a representation requires only constant space per element. By bseed(u, F ) we denote the shortest border seed of u contained in some element of F . Note that F = {abaa, abaab, baba, babaa}. Then bseed(u, F ) = abaa.

The proof of the following fact is present implicitly in [START_REF] Iliopoulos | Covering a string[END_REF] (type-A and type-B seeds). Theorem 6. Let u ∈ Σ n and let F be a prefix family given in a canonical form. Then bseed(u, F ) can be computed in linear time.

Alternative proof of Theorem 6.

There is an alternative algorithm for computing bseed(u, F ), based on a special version of Find-Union data structure. Recall that B[1 . . n] is the border-array of u. Denote by FirstGE(I, c) (firstgreater-equal ) a query:

FirstGE(I, c) = min{i : i ∈ I, B[i] ≥ c},
where I is a subinterval of [1 . . n]. We assume that min ∅ = +∞. A sequence of linear number of such queries, sorted according to non-decreasing values of c, can be easily answered in linear time, using an interval version of Find-Union data structure, see [START_REF] Crochemore | Extracting powers and periods in a string from its runs structure[END_REF][START_REF] Gabow | A linear-time algorithm for a special case of disjoint set union[END_REF]. The following algorithm applies the condition for border seed from Fact 2 to every element of F , with P[first(s) + |s| Computation of the shortest seeds via prefix maxgaps. Let T (u) be the suffix tree of u, recall that it can be constructed in O(n) time [START_REF] Crochemore | Algorithms on Strings[END_REF][START_REF] Crochemore | Jewels of Stringology[END_REF]. By Nodes(u) we denote the set of factors of u corresponding to explicit nodes of T (u), for simplicity we identify the nodes with the strings they represent. For v ∈ Nodes(u), the set Occ(v, u) corresponds to leaf list of the node v (i.e., the set of values of leaves in the subtree rooted at v), denoted as LL(v). Note that first(v) = min LL(v) and last (v) = max LL(v), and such values can be computed for all v ∈ Nodes(u) in O(n) time. For v ∈ Nodes(u), we define the prefix maxgap of v as:

∆(v) = max{maxgap(w) : w ∈ PREF (v)}.
Equivalently, ∆(v) is the maximum of maxgap values on the path from v to the root of T (u). We introduce an auxiliary problem:

Prefix Maxgap Problem: given a word u ∈ Σ n , compute ∆(v) for all v ∈ Nodes(u).

The following lemma (an alternative formulation of Observation 3) shows that prefix maxgaps can be used instead of maxgaps in searching for seeds. This is important since computation of prefix maxgaps ∆(v) is simple, in comparison with maxgap(v) -this is due to the fact that the ∆(v) values on each path down the suffix tree T (u) are non-decreasing. Efficient computation of maxgap(v) requires using augmented height-balanced trees [START_REF] Brodal | Finding maximal quasiperiodicities in strings[END_REF] or other rather sophisticated techniques [START_REF] Berkman | The subtree max gap problem with application to parallel string covering[END_REF]. The shortest-seed algorithm in [START_REF] Iliopoulos | Covering a string[END_REF] also computes prefix maxgaps instead of maxgaps, however this observation is missing in [START_REF] Iliopoulos | Covering a string[END_REF].

Lemma 7. Let s be a factor of u ∈ Σ * and let w be the shortest element of Nodes(u) such that s ∈ PREF(w). The word s is a seed of u if and only if |s| ≥ ∆(w) and s is a border seed of u.

Proof. If s corresponds to an element of Nodes(u), then s = w. Otherwise, s corresponds to an implicit node in an edge in the suffix tree, and w is the lower end of the edge. Note that in both cases we have ∆(w) ≥ maxgap(w) = maxgap(s). By Observation 3, this implies part (⇐) of the conclusion. As for the part (⇒), it suffices to show that |s| ≥ ∆(w).

Assume, to the contrary, that |s| < ∆(w). Let v ∈ PREF (w) ∩ Nodes(u) be the word for which maxgap(v) = ∆(w), and let a, b be consecutive elements of the set Occ(v, u) for which a + maxgap(v) = b.

Let us note that no occurrence of s starts at any of the positions a+1, . . . , b-1. Moreover, none of the suffixes of the form u[i . . n], for a + 1 ≤ i ≤ b -1, is a prefix of s. Indeed, v is a prefix of s of length at most nb + 1, and such an occurrence of s (or its prefix) would imply an extra occurrence of v. Note that at most |s| ≤ ba -1 first positions in the interval [a, b] can be covered by an occurrence of s in u (at position a or earlier) or by a suffix of s which is a prefix of u. Hence, position b -1 is not covered by s at all, a contradiction.

⊓ ⊔ By Lemma 7, to complete the shortest seed algorithm it suffices to solve the Prefix Maxgap Problem (this is further clarified in the ComputeShortestSeed algorithm below). For this, we consider the following problem. By SORT (X) we denote the sorted sequence of elements of X ⊆ {1, 2, . . . , n}.

Chain Prefix Maxgap Problem

Input: a family of disjoint sets X 1 , X 2 , . . . , X k ⊆ {1, 2, . . . , n} for all i in Xj-1 do 6:

together with SORT (X 1 ∪ X 2 ∪ . . . ∪ X k ). The size of the input is m = |X i |. Output: the numbers ∆ i = max j≤i maxgap(X j ∪ X j+1 ∪ . . . ∪ X k ).
p := pred (pos[i]); q := suc(pos[i]); 7:

if (p = nil) and (q = nil) and (not marked (p)) and (not marked (q)) then 8: ∆j := max(∆j, value(q)value(p)); Then we perform the computation recursively for the hanging subtrees, previously sorting LL(T ′ ) for each hanging subtree T ′ . Such sorting operations can be performed in O(n) total time for all hanging subtrees.

At each level of recursion we need a linear amount of time, and the depth of recursion is logarithmic. Hence, the total size of invoked Chain Prefix Maxgap Problems is O(n log n).

⊓ ⊔

Now we proceed to the shortest seed computation. In the algorithm we consider all factors of u, dividing them into groups corresponding to elements of Nodes(u).

Let w ∈ Nodes(u) and let v be its parent. Let s ∈ PREF (w) be a word containing v as a proper prefix, i.e., s ∈ PREF (w, |v| + 1). By Lemma 7, the word s is a seed of u if and only if |s| ≥ ∆(w) and s is a border seed of u.

Using the previously described reductions (Theorems 6-8), we obtain the following algorithm: Observe that the workhorse of the algorithm is the chain version of the Prefix Maxgap Problem, which has a fairly simple linear time solution. The main problem is of a structural nature, we have a collection of very simple problems each computable in linear time but the total size is not linear. This identifies the bottleneck of the algorithm from the complexity point of view.

Long Seeds

Note that the most time-expensive part of the ComputeShortestSeed algorithm is the computation of prefix maxgaps, all the remaining operations are performed in O(n) time. Using this observation we can show a more efficient algorithm computing the shortest seed provided that its length m is sufficiently large. For example if m = Θ(n) then we obtain an O(n) time algorithm for the shortest seed. By Observation 1g, the longest overlap between consecutive occurrences of s in u is at most m 2 , therefore the number of occurrences of s in u is at most 2n m . Hence, searching for the shortest seed of length at least m, it suffices to consider nodes v of the suffix tree T (u) for which: |v| ≥ m and |LL(v)| ≤ 2n m . Thus, we are only interested in prefix maxgaps for nodes in several subtrees of T (u), each of which contains O(n/m) nodes. Thanks to the small size of each subtree, the algorithm ComputeShortestSeed finds all such prefix maxgaps in O(n log (n/m)) time. Please note that using this algorithm for each node we obtain a prefix maxgap only in its subtree (not necessarily in the whole tree), however Lemma 7 can be simply adjusted to such a modified definition of prefix maxgaps.

⊓ ⊔

  ) If s and s ′ are two covers of a string u, |s ′ | < |s|, then s ′ is a cover of s. (g) If s is the shortest cover or the shortest left seed or the shortest seed of a string u then per(s) > |s|/2. For a set X of positive integers, let us define the maxgap of X as: maxgap(X) = max{ba : a, b are consecutive numbers in X} or 0 if |X| ≤ 1.

Fig. 1 .

 1 Fig. 1. The word s = abaa is a border seed of u = aabaababaabaaba.

Fact 2

 2 Let s be a factor of u ∈ Σ * . The word s is a border seed of u if and only if |s| ≥ max(P [first(s) + |s| -1], P ′ [last(s)]).

Fig. 2 .

 2 Fig. 2. Illustration of part (⇒) of Lemma 4.

Fig. 3 .

 3 Fig. 3. Illustration of part (⇐) of Lemma 4.

)

  Proof. By Lemma 4, the length of the shortest left seed of u can be found among the values C[per(u)], . . . , C[n]. And conversely, for each of the values C[j] for per(u) ≤ j ≤ n, there exists a left seed of u of length C[j]. Thus lseed(u) equals the minimum of these values, which yields the formula (1).

  We obtain an O(n) time algorithm ComputeLeftSeedArray. ⊓ ⊔ ALGORITHM ComputeLeftSeedArray(u) 1: P[1 . . n] := period array of u; C[1 . . n] := cover array of u; 2: Q := emptyBidirectionalQueue; 3: for i := 1 to n do 4: while (not empty(Q)) and (front (Q) < P[i]) do popFront (Q); 5:

ALGORITHM

  Alternative-ComputeLeftSeedArray(u) 1: P[1 . . n] := period array of u; R[1 . . n] := ComputeR-Array(u); 2: LSeed[0] := 0; ls := 0; 3: for i := 1 to n do 4: { An invariant of the loop: ls = LSeed[i -1]. } 5: while R[ls] < P[i] do ls := ls + 1; 6: LSeed[i] := ls; 7: return LSeed[1 . . n]; Theorem 2. Algorithm Alternative-ComputeLeftSeedArray runs in linear time. Proof. Recall that the arrays P[1 . . n] and C[1 .

Example 1 .

 1 Let u = aabaababaabaaba be the example word from Fig. 1. Let: F = {PREF (abaab, 4), PREF (babaa, 4)} = {(2, 10, 4, 5), (6, 6, 4, 5)}.

  -1] substituted by first(s) + |s| -1 -B[first(s) + |s| -1]. We omit the details. ⊓ ⊔ ALGORITHM ComputeBorderSeed(u, F) 1: bseed := +∞; 2: for all (first (v), last (v), k, |v|) in F, in non-decreasing order of first (v) do 3: k := max(P ′ [last (v)], k); 4: I := [first (v) + k -1, first (v) + |v| -1]; 5: pos := FirstGE(I, first (v) -1); 6: bseed := min(bseed , posfirst (v) + 1); 7: return bseed ;

Theorem 7 .

 7 The Chain Prefix Maxgap Problem can be solved in O(m) time using an auxiliary array of size n.Proof. Initially we have the list L = SORT (X 1 ∪ X 2 ∪ . . . ∪ X k ). Let pred and suc denote the predecessor and successor of an element of L. The elements of L store a Boolean flag marked , initially set to false. In the algorithm we use an auxiliary array pos[1 . . n] such that pos[i] is a pointer to the element of value i in L, if there is no such element then the value of pos[i] can be arbitrary. Obviously the algorithm takes O(m) time. ⊓ ⊔ ALGORITHM ChainPrefixMaxgap(L) 1: ∆1 := maxgap(L); { naive computation } 2: for j := 2 to k do 3: ∆j := ∆j-1; 4:for all i in Xj-1 do marked (pos[i]) := true; 5:

Theorem 8 .

 8 The Prefix Maxgap Problem can be reduced to a collection of Chain Prefix Maxgap Problems of total size O(n log n).Proof. We solve a more abstract version of the Prefix Maxgap Problem. We are given an arbitrary tree T with n leaves annotated with distinct integers from the interval[1, n], and we need to compute the values ∆(v) for all v ∈ Nodes(T ), defined as follows: maxgap(v) = maxgap(LL(v)), where LL(v) is the leaf list of v, and ∆(v) is the maximum of the values maxgap on the path from v to the root of T . We start by sorting LL(root (T )), which can be done in O(n) time. Throughout the algorithm we store a global auxiliary array pos[1 . . n], required in the ChainPrefixMaxgap algorithm.Let us find a heaviest path P in T , i.e., a path from the root down to a leaf, such that all hanging subtrees are of size at most |T |/2 each. The values of ∆(v) for v ∈ P can all be computed in O(n) time, using a reduction to the Chain Prefix Maxgap Problem (see Fig.4).

Fig. 4 .

 4 Fig.4. A tree with an example heaviest path P (in bold). The values ∆(v) for v ∈ P can be computed using a reduction to the Chain Prefix Maxgap Problem with the sets X1 through X4.

ALGORITHM ComputeShortestSeed(u) 1 :

 1 Construct the suffix tree T (u) for the input string u; 2: Solve the Prefix Maxgap Problem for T (u) using the ChainPrefixMaxgap 3: algorithm -in O(n log n) total time (Theorems 7 and 8); 4: F := { PREF (w, max(|v| + 1, ∆(w))) : (v, w) is an edge in T (u) }; 5: return bseed(u, F); { Theorem 6 }

Theorem 9 .

 9 One can check if the shortest seed of a given string u has length at least m in O(n log (n/m)) time, where n = |u|. If so, a corresponding seed can be reported within the same time complexity. Proof. We show how to modify the ComputeShortestSeed algorithm. Denote by s the shortest seed of u, |s| = m.

⋆ The authors thank an anonymous referee for proposing several insightful remarks.⋆⋆ The author is supported by grant no. N206 568540 of the National Science Centre. ⋆ ⋆ ⋆ The author is supported by grant no. N206 566740 of the National Science Centre.