Prajol Shrestha
email: prajol.shrestha@etu.univ-nantes.fr

Alignment of Monolingual Corpus by Reduction of the Search Space

Keywords: corpus comparable monolingue, alignement, similarité monolingual comparable corpus, alignment, similarity

Les corpus comparables monolingues, alignés non pas au niveau des documents mais au niveau d'unités textuelles plus fines (paragraphe, phrases, etc.), sont utilisés dans diverses applications de traitement automatique des langues comme par exemple en détection de plagiat. Mais ces types de corpus ne sont pratiquement pas disponibles et les chercheurs sont donc obligés de les construire et de les annoter manuellement, ce qui est un travail très fastidieux et coûteux en temps. Dans cet article, nous présentons une méthode, composée de deux étapes, qui permet de réduire ce travail d'annotation de segments de texte. Cette méthode est évaluée lors de l'alignement de paragraphes provenant de dépêches en langue anglaise issues de diverses sources. Les résultats obtenus montrent un apport considérable de la méthode en terme de réduction de temps d'annotation. Nous présentons aussi des premiers résultats obtenus à l'aide de simples traitements automatiques (recouvrement de mots, de racines, mesure cosinus) pour tenter de diminuer encore la charge de travail humaine.

Introduction

Monolingual comparable corpora from its name can be understood to be a collection of electronic text documents in a single language collected on the basis of comparability. The characteristics of comparability has not been explained and analyzed in many literature and the ones that explain are made for bilingual comparable corpora [START_REF]What are comparable corpora ?[END_REF]. Comparability depends on the application for which the documents are collected for instance, for information retrieval, comparable corpora would be documents that are related to a set of other documents whereas for detecting and measuring reused text, the comparable corpora are documents that have been rewritten from a set of previously written documents [START_REF] Gaizauskas R | The meter corpus : A corpus for analysing journalistic text reuse[END_REF].

In the field of Natural Language Processing (NLP), monolingual comparable corpora are used to build and test a wide range of applications such as information retrieval, summarization, plagiarism detection, dictionary building and so on. With a number of application to be built, the field of NLP requires a wide range of monolingual comparable corpus with different annotations. The annotations can be at different levels starting from word to document level and different types of annotations such as Part-of-Speech annotation of words to annotations of related documents. In this paper, our focus of annotation is the annotation of alignment between text segments based on similarity and from here onwards annotation will refer to alignment. There are some standard monolingual comparable corpus available, created manually by collecting existing documents written by humans or artificially by generating machine made text. These corpora are annotated on the level of :

-Documents, TDT corpus 1 , for Topic detection and tracking applications created manually.

-Text segments, PAN-PC-09 (Barrón-Cedeño et al., 2010), for plagiarism detection and are artificially created due to the fact that natural text on plagiarism are hard to collect. -Documents as well as text segments, METER corpus [START_REF] Gaizauskas R | The meter corpus : A corpus for analysing journalistic text reuse[END_REF], for the detection of text reuse created manually.

From the list above, we can realize that for each NLP task, that use comparable corpus, we will require a corpus with specific annotations. There aren't many corpus like these that are available and as the field of NLP expands, more corpus with specific annotations would be required. Other NLP activities that do not make use of these annotations made in the standard monolingual comparable corpus make their own specific annotations. These corpus are not available for the public and therefore for NLP tasks that does not have a standard annotated corpus, a new corpus with annotations has to be built.

Most of the annotation are made manually by two or more professional annotators who search for alignments on all possible alignment pairs. In monolingual corpora, the alignments annotated are very few compared to the total possible alignment searched by the annotators. We propose a method to reduce this search space of the total possible alignments so that this task becomes much less time consuming and costly. This method can be used to align a wide range of text segments as we show how it helps in aligning similar paragraphs in monolingual comparable corpus and also present some methods that will help automatize it to some extent.

We will start in section 2 by describing the alignment process in which the reduction of space is explained in section 2.1 and the creation of the gold corpus in section 2.2. In section 3, we present the experiments carried out and their results. We finally conclude and present our future work in section 4.

Alignment

Alignment, in general, could be seen as a problem in which segments of text are grouped or linked to each other based on some relations like synonymy, translation, similarity and so on [START_REF] Indurkhya | Handbook of natural language processing[END_REF]. The granularity of the segments for alignment may vary : characters, words, phrases, sentences, paragraphs, or documents. The relation for alignment and the granularity of the segments depend on the application for which alignment is being done. Alignment is used in many different applications of NLP : machine translation, dictionary building, summarization, information retrieval and many more.

Our alignment process focuses between text segments within a document, for instance paragraphs or sentences, and is based on the similarity between these text segments. The alignment of these text segments is a tedious work even for a corpus containing few hundred of text segments. For n number of text segments the total number of comparisons between them, to decide if an alignment exists or not, equals to :

n(n -1) 2 (1)
For instance, the corpus we use has 239 paragraphs, explained in section 3.1, for alignment which makes a total of 28,441 compar-1. http ://projects.ldc.upenn.edu/TDT-Pilot/ isons. Usually, all of these comparisons are done manually by two or more annotators which is time consuming and therefore, we propose a method to reduce this effort by reducing the number of comparisons before giving them to the annotators.

Reducing the search space

Annotating is a tedious task searching for alignments through all the possible pairs of text unit. To reduce the amount of search we make the alignment process in two phases by breaking the problem into two parts. The first phase is the part in which the total combination of alignment pairs are reduced by selecting candidate alignment pairs such that the actual alignment pairs are the subset of this candidate alignment pairs.

ActualAlignmentP airs ⊂ CandidateAlignmentP airs

With these candidate alignments the annotators have a smaller set of paragraph pairs to work with and can be more effective as well as efficient. In the next phase, the annotators select the actual alignments from these candidate alignment pairs. This is possible because in comparable corpora there are many text segment pairs that are not similar and therefore, it is possible to filter these pairs of text segments.

Selecting the candidate alignment pairs is the first phase where, we select all the pairs of text segments that has the possibility of being similar and therefore aligned. The main objective of this phase is to reduce the size of the initial total amount of alignment pairs in such a way that the actual alignments are not missed out. This selection is done when a criteria is met. To follow the criteria, we first divide each text segments into entities. According to these entities the candidate alignment pairs are selected. The entities are listed and explained below :

-Noun Entities : These are parts of the text segments that represents the important nouns or noun phrases of the text segments. Importance depends on how much meaning does this entity bear to convey the meaning of the whole text segment. -Verb Entities : These are the parts of the sentences that represents the main intransitive verbs of the text segments. Intransitive verbs are verbs that shows action of some sort but does not have a direct object [START_REF] Loberger | Websters New World English Grammar Handbook[END_REF]. As the verb is related to one noun or noun phrase the importance of this verb tends to be higher for selecting similar text segments which will be evident when alignment is done.

Here is an example of two text segments that are compared using their entities :

Text Segment I :

William and Harry, with their father Prince Charles and their grandmother Queen Elizabeth, are thought likely to remain in seclusion at Balmoral Castle in Scotland until Saturday's ceremony.

Entities :

-William -Harry -Father Prince Charles -grandmother Queen Elizabeth -seclusion -Balmoral Castle -Scotland -Saturday's ceremony Similarly, we extract entities from the second text segment with which we want to compare the previous text segment. The second text segment is given below :

Text Segment II :

One is the state funeral, normally staged only for sovereigns, although the reigning king or queen, with the approval of Parliament, can order one for others. Churchill, Britain's prime minister during World War II, is one who received such treatment in 1965.

Entities :

-state funeral -sovereigns -reigning king or queen -approval of Parliament -Churchill -Britain's prime minister -World War II Once this is done for both the text segments we select this alignment as one of the candidate alignments if the following condition is satisfied :

The concept of at least one entity should be common to the entity set of the text segments.

Comparing text segments I and II, we can see that we have a common element between these text segments which are the entities 'Queen Elizabeth' and 'king or queen'. These two elements are same obviously not because of common terms but because of the concept of 'queen' which is Queen Elizabeth. This concept can be easily known using the context in the paragraph text segments. This comparison of common entities in the text segments are easier to determine than to decide if these two text segments are similar or not and therefore can be done faster than the traditional method of directly finding similar pair of text segments.

As we can see that the text segments aren't similar with any logical definition of similarity, given that the text segments convey different information, yet these are selected because of our selection criteria. This criteria that we present will theoretically guarantee that the actual aligned text segment pairs will be present in the candidate alignments.

To make it clearer about the concept of the element here are some examples of concept of entities : word possible concepts crashed rammed into a wall, fatal impact prince Charles heir to the British throne grief sadness, mourn high speed 121 mph, flying by This method of selection is easy and could be done by a non professional annotator on different lengths of text segments. Once these candidate alignments are collected, they can be given to the annotators for annotating the alignments by finding the actual alignments. The number of candidate alignments will be less than the original combination of pair of text segments and therefore many annotators can work efficiently on the small set in less human hours. The next section describes how we created our gold corpus from the set of candidate alignments selected by our selection criteria.

Creation of Gold Corpus

We built the gold corpus annotated with aligned paragraphs to build and test algorithms for automatic alignment of paragraphs.

To build the gold corpus, two annotators selected the actual alignment pairs from the candidate alignments which were selected as explained in the previous section 2.1. Two paragraphs are annotated as aligned in the gold corpus on the basis of similarity. To show how the annotators annotated the gold corpus we first define the term similarity.

Similarity is a difficult concept to define in general because the definition of this term depends on the application for which this measure is intended. Even with this difficulty, there are many similarity measures (Barron-Cedeno et al., 2009) like cosine similarity measure, with which similar texts are measured but these measures do not define similarity, they rather assign a value of similarity.

Here are some of the definitions of similarity between two texts :

1. Two sentences are similar if they contain at least one clause that expresses the same information. [START_REF] Barzilay | Sentence alignment for monolingual comparable corpora[END_REF] 2. Two paragraphs are similar if they contain "common information". This was defined to be the case if the paragraphs referred to the same object and the object either (a) performed the same action in both paragraphs, or (b) was described in the same way in both paragraphs. [START_REF] Hatzivassiloglou | Simfinder : A flexible clustering tool for summarization[END_REF]) [START_REF] Hatzivassiloglou | Detecting text similarity over short passages : exploring linguistic feature combinations via machine learning[END_REF] 3. Two text are similar on the basis of these intuitions : [START_REF] Lin | An information-theoretic definition of similarity[END_REF] -Intuition 1 : The similarity between A and B is related to their commonality. The more commonality they share, the more similar they are.

-Intuition 2 : The similarity between A and B is related to the differences between them. The more differences they have, the less similar they are. -Intuition 3 : The maximum similarity between A and B is reached when A and B are identical, no matter how much commonality they share.

All the definitions presented above focus on what is common between the text segments to call them similar. This focus on what is common is also the difference between them. Definition 1 and 2 states what should be common where as definition 3 gives no information about it and therefore, is the most general definition among them. The more general the definition is, the more difficult the annotation process becomes because of the different interpretation of the definition and in turn more disagreements between annotators. Definition 1 and 2 is difficult to apply to all the paragraphs that we see in our corpus. Definition 1 is specific to sentences and paragraphs with more than one sentence cannot be considered similar on the basis of the same information within clauses. Definition 2 considers similarity on the basis of objects and there may exist paragraphs for which the information about the objects alone do not represent the meaning of the paragraph as in the following paragraph :

French television said Diana was being pursued by paparazzi when the crash occurred, and French Interior Minister Jean-Pierre Chevenement said police were questioning seven photographers as part of a criminal investigation into the accident.

In this paragraph, the object, paparazzi, doesn't perform any action nor does the description of the paparazzi as photographers represents the paragraph.

We will define our similarity definition with the intuition 1 of definition 3 by defining the term commonality. We define the term 'commonality' in the definition on the basis of common sub-topic. The explication of sub-topic is also intuitive as we define subtopic as the main ideas that the paragraph gives. Intuition 2 considers the differences being a basis of similarity but we only require how similar they are and the differences between paragraphs could be considered as how much the paragraphs are not similar and so we ignore this intuition. Intuition 3 is partially correct as identical paragraphs are definitely similar to it's maximum as they will share the same sub-topic but we ignore it because it is possible that two non-identical paragraphs may consist of the same sub-topic.

A paragraph may have more than one sub-topic and for us a minimal of one common sub-topic would make the paragraph similar.

Here is an example where we compare two paragraphs for similarity :

Paragraph I (PI) :

At Kensington Palace, the flowers covered an area estimated at 50 by 30 feet. There were more flowers as well at Harrods department store, which is owned by Dodi Fayed's father, billionaire Egyptian businessman Mohamed Fayed.

Paragraph II (PII) :

Mounds of flowers marked the sidewalk near one gate at Kensington Palace, where Diana resided, and along the main gates of the palace. There were flowers as well at Buckingham Palace, at St. James' Palace, at Harrod's department store, which is owned by Fayed's father, the Egyptian born business tycoon Mohamed Al Fayed. There were even flowers outside the gym where Diana regularly worked out.

The main ideas from Paragraph I are :

1. Flowers were present at Kensignton Palace 2. Flowers were present at Harrods department store

The main ideas from Paragraph II are :

1. Flowers were present at Kensington Palace 2. Flowers were placed at the palace 3. Flowers were placed at Buckingham Palace 4. Flowers were present at Harrods department store 5. Flowers were present at the gym Once we have the main ideas that are present, we try to find at least one overlap between them. In paragraphs I and II we find the following overlaps between them :

PI.1 with PII.1 PI.2 with PII.4

Here is another example of finding the similarity between paragraphs which is less intuitive at the first glance : Paragraphs to compare are :

Paragraph III (PIII) :

Dodi Al Fayed's father, Harrods Department Store owner Mohammed Al Fayed, arrived here immediately after learning of his son's death.

Paragraph IV (PIV) :

Bernard Dartevelle, a lawyer for Mohamed Al Fayed, Dodi Fayed's wealthy businessman father and also the owner of the Hotel Ritz, said the revelation "changes absolutely nothing." He spoke of an "ambience of harassment" created around Diana and Fayed by the constant presence of paparazzi.

The main ideas from Paragraph III are :

-Dodi Al Fayed's father arrived here after learning his son's death.

The main ideas from Paragraph IV are :

-Bernard Dartevelle said the revelation "changes absolutely nothing." -He spoke of an "ambience of harassment" created around Diana and Fayed by the constant presence of paparazzi.

In these two paragraphs, there is no common idea and therefore they are not selected for the actual alignment. In all of the four paragraphs in the examples given above, there is an information that are in common about Dodi Al Fayed's father but is not placed as the main idea because we believe these informations are present to support the main idea given by the paragraph and not the main idea itself. For this paper, we consider our similarity to be a binary relationship showing two paragraphs have at least one sub-topic in common or none. This binary measure can be easily changed into a continuous measure as the number of sub-topic present in the paragraphs can be counted.

3 Experiments and Results

Corpus

The corpus we used to run our experiments are taken from the Linguistic Data Consortium, LDC2 . LDC is an organization that has a collection of a wide range of corpus for different purposes. We have selected the LDC's North American News Text Corpus3 which is a monolingual corpus that consists of news articles from a spectrum of sources which includes New York Times ,Word Press, Associated Press, Washington post and some more. Among all these articles we selected 12 articles which were published within two consecutive days and which share the same topic to make a small monolingual comparable corpus. Our characteristics of comparability lies on the topic of the articles selected. The topic is the death of Princess Diana. These articles are from The Washington Post, Los Angeles Times, and New York Times. In these 12 articles, there are in total 239 paragraphs which will be aligned to each other on the basis of similarity.

Manual Alignment

We have manually aligned 28,441 paragraph pairs that have been selected from the corpus as explained in the previous section. The alignment process is of two parts, the first in which we select the candidate alignments and in the second part we select the actual alignments from the candidate alignments. The first part of the alignment process was done by a single annotator to reduce the total inital alignments to only 3,416 candidate alignments. In this phase, the annotator can be flexible to decide if a candidate alignment pair is really helpful to be a candidate alignment pair or not. If this decision can be taken easily and with out doubt then the candidate alignments that is valid by our selection criteria can be ignored. This flexibility is possible because of the fact that some paragraphs may have some common concepts of the entities and yet not have anything in common other than that and as it is manually done the annotator can decide not to align them. This phase is easy and therefore fast to do. It took about 71 hours to find the set of 3,416 candidate alignments from the set of 28,441 paragraph pairs.

The second phase of finding the actual alignment was done by two annotators independently and any differences among these selection of alignments were discussed together and a decision was taken with reasoning. The alignment task took about 20 hours for both annotators and a total of 429 actual alignments were selected. The total time that took us to annotate our corpus was 91 hours.

If we had directly tried to find the actual alignments without phase one, with an assumption that the time taken per paragraph pair (about 21 sec) is the same as in this second phase, it would take about 166 hours. The total time saved is 75 hours of work.

These actual alignments will be used as our gold corpus for building our algorithm for similarity. We used kappa statistics [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF][START_REF]Assessing agreement on classification tasks : The kappa statistic[END_REF] to evaluate our second phase annotation. Kappa statistics is defined as :

k = P A -P E 1 -P E (3)
where P A is the probability of two annotators agreeing in practice and P E is the expected probability of the two annotators agreeing.

In our case P A = 0.959, P E = 0.780 and K = 0.813, indicating the agreement on annotations are significant.

Automatizing the Alignment

Our manual alignment method is still time consuming and difficult as manual effort has to be done so we tried to use some simple automatic methods to see how they do against the manual process. We tried stem overlap, word overlap and cosine similarity measures (Barron-Cedeno et al., 2009) to find the actual alignments between similar paragraphs on the corpus we manually annotated. Before the experiments on each method we removed the stop words using a stop word list and except when using word overlap method we stemmed the remaining words using a snowball stemmer4 . We used two types of weights for the cosine similarity measure, one the frequency of the stem within the paragraph, TF, and the second one was the TF-IDF, which is used in information retrieval (Salton & McGill, 1983). We considered a pair of paragraphs to be aligned if the threshold value was crossed. Table 1 gives the best results from these methods along with their threshold value. table gives the number of actual alignments included in the candidate alignment which were selected by the different methods along with their threshold These methods that have been used isn't enough to automatically select the actual alignments as the precision of these methods are very low with none of them reaching a recall of 1. The best result in terms of including the actual alignments was given by the stem overlap and cosine similarity measure, which uses TF as weights, with 420 of the actual alignments retrieved. The cosine similarity measure is based on stem overlap as shown in the equation 4

Methods

cos(p 1 , p 2 ) = Σ s∈p1∩p2 (T F s,p1 .T F s,p2 ) Σ s∈p1 (T F s,p1 ) 2 .Σ s∈p2 (T F s,p2 ) 2 (4)
where, s is the stem, p is the paragraph and TF is the stem frequency of that stem. As this method is based on stem overlap it won't do better than stem overlap in terms of the number of actual alignments included but is better in improving the precision.

Even though these methods can't be used to find actual alignments we can use them to reduce the total initial paragraph pairs that have to be checked for candidate alignments. From the table 4 we can determine that the method which uses stem overlap and cosine similarity measure, which uses TF as weights, include 420 actual alignments and can be used to reduce the search space for finding candidate alignments if the few alignments that was not included can be ignored. Considering the time taken for the first phase, if we could ignore these undetected alignments we could save a considerable amount of time as the initial set of paragraphs are almost halved and so is the time taken to select the candidate alignments.

Some of the concepts of the alignments that were not captured by the one stem overlap method are presented below in table 2 and can be seen that some similar concepts like flower and bouquets could be shown they are similar using some knowledge source such as a dictionary while others would be a complex task. Looking into the actual alignments that were captured by the method of stem overlap and the cosine similarity measure, which uses TF as weights, we saw that most of the detected alignment pairs was because of the overlap of the context of the concept rather than the concept itself which puts a question about how effective this method would be while using a small size of text segments. In the news paper corpus that we use, a large portion of paragraphs have a length of a sentence which indicates that the context of the same concept within a sentence is enough for finding the candidate alignments.

Concept

Conclusions and Future Work

The total number of actual aligned text segments in the gold corpus shows that only 1.5% of the 28,441 initially paired paragraphs are aligned and the effort to check the other 98.5% of the paired paragraphs is wasted in terms of the difference between the end number of actual alignments and the total number of initial paired paragraphs. Our manual alignment method can reduce this wasted effort and have saved us about 75 hours of work. This method of manual alignment by reducing the search space is better than existing methods of manual annotation as the annotators have less candidate alignment pairs to annotate. These candidate alignments are easier and faster to select than the actual similar pair of text segments because of the complex nature of the definition of similarity in terms of analyzing the text according to the definition.

Even though our method is easier, it still requires much effort to select the candidate alignments. We can further reduce this effort by reducing the original set of text segment pairs using stem overlap or cosine similarity measure for choosing the candidate alignments from which the original alignments are selected to make the gold corpus. The different methods we used also showed that simple method of stem or word overlap and even cosine similarity measure are not enough to capture text segment similarities but has given a view that cosine similarity measure increases the precision. The context is also an important part in finding the actual alignments as we see with the stem overlap method that some actual alignments are captured using the context which gives us motivation in trying to use the context, like co-occurrence, in a vector space model [START_REF] Kaufmann | Second-order cohesion[END_REF]. This hypothesis will be used in the future to make our automatic alignment algorithm.

Références

  BARRON-CEDENO A., EISELT A. & ROSSO P. (2009). Monolingual text similarity measures : A comparison of models over wikipedia articles revisions. In Proceedings of the ICON : 7th International Conference on NLP, p. 29-38. BARRÓN-CEDEÑO A., POTTHAST M., ROSSO P., STEIN B. & EISELT A. (2010). Corpus and Evaluation Measures for Automatic Plagiarism Detection. In N. CALZOLARI, K. CHOUKRI, B. MAEGAARD, J. MARIANI, J. ODIJK, S. PIPERIDIS, M. ROSNER

TABLE 1 -

 1 The

		Threshold Aligned from Actual Alignments
			the method	included
	Stem Overlap	> 0	15,276	420
	Word Overlap	> 0	12,116	407
	Cosine Similarity (weight as TF)	>0.025	14,989	420
	Cosine Similarity (weight as TF*IDF)	>0.025	7,351	376

TABLE 2 -

 2 Concepts that could not be found similar using stem overlap

	I	Concept II
	100 miles per hour	flying by
	Flower	Bouquets
	spun into the wall	a tragic end
	spun into the wall	crashed
	following	pursuit
	William,Charles, and Queen Elizabeth Royal Family
	causal	cause

http ://www.ldc.upenn.edu/Catalog/byType.jsp

LDC Catalog number : LDC95T21

http ://snowball.tartarus.org/


Prajol Shrestha
email: prajol.shrestha@etu.univ-nantes.fr

Corpus-Based methods for Short Text Similarity

Keywords: Similarité, Modèle Vectoriel, Mesure de Similarité Similarity, Vector Space Model, Similarity metric

published or not. The documents may come

Introduction

Many natural language processing applications use similarity between short text (e.g. sentences, paragraphs) such as text summarization [START_REF] Hovy | Automatic evaluation of summaries using n-gram co-occurrence statistics[END_REF], which works on sentence or paragraph level ; question answering, which uses similarity between the question answer pairs [START_REF] Mohler | Text-to-text semantic similarity for automatic short answer grading[END_REF] ; and image retrieval, where an image is retrieved by finding the similarity between the query and the image caption [START_REF] Coelho | Image retrieval using multiple evidence ranking[END_REF].

In general, existing methods view the short text similarity problem as a classification task, where one-to-one text similarity decision is made, or as an alignment task, where many-to-many text similarity decision is also made. Most of the existing methods treat this problem as a classification task which use similarity metrics [START_REF] Abdalgader | Short-text similarity measurement using word sense disambiguation and synonym expansion[END_REF] [START_REF] Cordeiro | Learning paraphrases from wns corpora[END_REF] [START_REF] Mihalcea | Corpus-based and knowledge-based measures of text semantic similarity[END_REF] [START_REF] Hatzivassiloglou | Detecting text similarity over short passages : Exploring linguistic feature combinations via machine learning[END_REF]. These similarity metrics give a value of similarity between pairs of short text which can then classify the pairs as similar or not using a threshold. This threshold value is usually empirically fixed for each similarity metric. These existing methods use external knowledge like WordNet [START_REF] Miller | Wordnet : An on-line lexical database[END_REF] to find lexical similarity or some corpora like the British National Corpus for optimizing parameters. These methods are not suitable for languages that do not have resources like WordNet or large corpora. This leads to find similarity measures that use no resources or resources that are easily buildable. There are few methods that treat the similarity problem as an alignment task [START_REF] Barzilay R | Sentence alignment for monolingual comparable corpora[END_REF] [START_REF] Nelken | Towards robust context-sensitive sentence alignment for monolingual corpora[END_REF]. These methods also use similarity metrics like the classification methods but the value from these metrics are not used directly for alignment. The alignment in these methods are based on supervised methods and use dynamic programming which includes the context of the sentences and are designed for comparable monolingual text.

We take the similarity problem between short text as a classification task. This task is based on corpus-based unsupervised methods which do not use external resources to compute the similarity value unlike existing classification methods. One of the earliest and well known classification method for text similarity is the Vector Space Model (VSM) for information retrieval, where similar documents in a collection is chosen by a similarity value computed using a similarity metric, the cosine similarity, between the vectors of term weights representing documents [START_REF] Salton | A vector space model for automatic indexing[END_REF]. This measure is based on the overlap of terms in the document pair whose similarity is being measured.

The VSM assumes that the vectors of terms are independent, pairwise orthogonal, to each other which is unrealistic. There exist other vector space models like the Generalized Vector Space Model (GVSM) [START_REF] Wong | On modeling of information retrieval concepts in vector spaces[END_REF] which does not assume this independence and although this model claims to be more effective than the standard implementation of the VSM, it is computationally expensive and therefore VSM is widely used despite its unrealistic assumption. The VSM for information retrieval is modified and used for short text similarity by treating the short text as documents and computing the idf value using external resources like the British National Corpus. This VSM cosine similarity measure is the baseline for most of the similarity studies [START_REF] Mihalcea | Corpus-based and knowledge-based measures of text semantic similarity[END_REF].

Our similarity measure is based on VSM but is adopted in such a way that the assumption of term independence is excluded and the short text vectors incorporates the sense and correlation of the terms. This is done by taking into account the overlap of the terms in all the short text of the corpus rather than only the short text pair between which the similarity is measured. Along presenting a new method to find similar short text we evaluate the performance of two other information retrieval methods which use term overlaps namely Dice measure [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF] and Resemblance measure1 [START_REF] Lyon | Detecting short passages of similar text in large document collections[END_REF]. We also show that using stems instead of words can improve the baseline VSM model for short text similarity.

Related Works

In information retrieval, there are many methods to find similarity between documents and one of the most well known method is the VSM which uses cosine similarity measure [START_REF] Barron-Cedeno A | Monoligual text similarity measures : A comparison of models over wikipedia articles revisions[END_REF]. This vector based method is also used to measure similarity between sentences as done by [START_REF] Barzilay R | Sentence alignment for monolingual comparable corpora[END_REF]. They view the problem of finding similar sentences as an alignment problem, where they align similar sentences between two monolingual comparable documents. In their method, the paragraphs are first aligned by a trained classifier and once the paragraphs are aligned the sentences within them are aligned using vector based cosine similarity and dynamic programming. Rani et al. [START_REF] Nelken | Towards robust context-sensitive sentence alignment for monolingual corpora[END_REF] took the same problem as Barzilay et al. and proposed an improved robust method. This method also uses dynamic programming for alignment but uses cosine similarity measure in a logistic regression to provide a score to aid the alignment. Both of these methods use context around the sentences, the following and preceding sentences, to aid in alignment. These methods for alignment make many-to-many sentence alignment and do not provide a similarity value between sentences indicating that these methods are suitable to find similar sentences only in comparable monolingual corpora.

Another method that uses the concept of overlap like the cosine measure is the fingerprinting method. It takes into account the overlap of bigrams or trigrams between the text to calculate a value of resemblance as shown in [START_REF] Lyon | Detecting short passages of similar text in large document collections[END_REF] which is the basis of classifying similar text and has been used to detect plagiarism. [START_REF] Cordeiro | Learning paraphrases from wns corpora[END_REF] has also proposed a similarity metric to identify similarity between texts and to identify paraphrase based on word overlap. It computes a similarity value by combining the ratio of common words in each sentence and is focused on capturing paraphrases which makes it unsuitable to find other types of similar sentences for example, this metric gives a similarity value zero to identical sentences. Linguistic features has also been used to find similarity between short text as in [START_REF] Hatzivassiloglou | Detecting text similarity over short passages : Exploring linguistic feature combinations via machine learning[END_REF]. They build linguistic feature vectors to build rules in a supervised manner to classify paragraph pairs. The features used to build rules are noun phrase matching, WordNet synonyms, common word class of verbs, shared common noun and their combinations. Even though it performs better than the vector based cosine similarity measure, it requires resources like Wordnet which are not present and are hard to build for other resource less languages.

Recent researches are focused on finding the similarity between lexical items in short text to find the similarities between these text. There exist corpus-based approaches to find the lexical similarity, some of which use text pattern analysis, Pointwise mutual information (PMI) and Latent Semantic Analysis (LSA). We will not focus on WordNet based approaches to find lexical similarity [START_REF] Abdalgader | Short-text similarity measurement using word sense disambiguation and synonym expansion[END_REF]. Mihalcea et al. [START_REF] Mihalcea | Corpus-based and knowledge-based measures of text semantic similarity[END_REF] use PMI and LSA to compute the text semantic similarity using a wrapper given in equation 1.

sim(T1, T2) = 1 2 ( Σw∈T 1 maxSim(w, T2) * idf (w) Σw∈T 1 idf (w) + Σw∈T 2 maxSim(w, T1) * idf (w) Σw∈T 2 idf (w) ) (1)
maxSim(w, T 2(1) ) is the maximum lexical similarity between the word w in sentence T 1(2) and all the words in sentence T 2(1) and idf (w) is the inverse document frequency of the word w calculated from the British National Corpus. The similarity metric, STS, proposed by Islam et al. [START_REF] Islam | Semantic text similarity using corpus-based word similarity and string similarity[END_REF], unlike other metrics, use string similarity along with corpus-based word similarity. Corpus-based word similarity is measured using two measures that includes second order co-occurrence pointwise mutual information and common word order similarity. The string similarity is measured using the concept of Longest Common Sequence. All these three measures are combined to determine the similarity between two short text. All the mentioned corpus-based method have the same drawback of using external resources.

Short Text Similarity

In this section, we present a new method to find similarity between short text. For simplicity reasons, we explain the method using sentence as our short text. Our similarity method is based on VSM but is different in the way the sentence vectors are created. The dimensions in sentence vectors do not represent the terms in the collection of sentences as in the bag of words model (Baeza-Yates & Ribeiro-Neto, 1999) but rather created from term vectors. Given a corpus C of n sentences and m unique terms, the term vector for term t j is created with n number of dimensions in which the presence and absence of the term in each sentence is indicated by a boolean value x :

tj = [x1, x2, x3, x4, ..., xn] xi ∈ 0, 1; i ∈ 1 to n; 0 = absent, 1 = present (2)
This term vector representation is similar to the wordspace model [START_REF] Schutze | Automatic word sense discrimination[END_REF] where the distribution of the terms are stored. These representation of term vectors together will form a m x n term-sentence matrix and as the number of sentence increases the size of the matrix will also increase. This huge dimension of the matrix can be reduced to some extent by removing stopwords and stemming2 . There are also mathematical procedures for the reduction of the matrix like Latent Semantic Analysis [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF] which uses singular value decomposition, SVD, or Principle Component Analysis [START_REF] Jolliffe | Principal component analysis[END_REF] which represents the matrix in different coordinates. We have used the simple technique of removing the stopwords and stemming words but none of the mathematical procedures to reduce the dimension during our experiments. This representation of term vector will consist of many zero values which will take a lot of memory. To reduce this space, we represent the vector in a reduced form where only the dimensions having value 1 are kept as shown in Equation 3where we assume that the term t j is present in sentence numbers 1,5, and 8 : tj = [(S1, 1), (S5, 1), (S8, 1)] Si is the sentence number i where the term tj is present ; i ∈ 1 to n (3)

This term vector shows the different senses that the term may have. Here, the sense of the term means the idea with which it can be related to. Our assumption is that sentences are independent to each other making each sentence presenting a unique idea and therefore, each term present in a sentence is related to this idea. This assumption like the assumption of VSM is unrealistic but the effect of this assumption can be reduced using clustering techniques like hierarchical clustering [START_REF] Kamber | Data Mining : Concepts and Techniques[END_REF] to group sentences that give the same idea or in other words similar sentences. Clustering has not been used in the experiments. Once we have the term vectors we can create sentence vectors by adding the term vectors of the terms present in the sentence making the number of dimension of their sentence vector equal to the term vector. The term vector consists of only the boolean value to be added which doesn't provide much information about the term so while adding the term vector we add the inverse document frequency, idf, value of the term which in our case is the inverse sentence frequency. This idf value is computed from the sentences present in the corpus. For a sentence consisting of terms t 1 , t 2 , .., t n , the dimension, i, corresponding to the sentence S i of the sentence vector will be :

di = Σ n j=1;t j ∈S i idfj idfj is the idf value of the term j ; i ∈ 1 to n (4)
This method is similar to the method of second-order similarity [START_REF] Kaufmann | Second-order cohesion[END_REF] and includes more information other than cohesion of text by encoding three different information in the sentence vector which are i) the importance of each term using its idf ii) the co-occurrence of terms by adding up the idf values of all the terms that occur in a sentence and iii) the distribution of term along various sentences as the dimensions of the sentence vector is equal to the number of sentences present in the corpus. Using these sentence vectors we can now compute the similarity value between two sentences using the cosine similarity measure. We name our method Short text based Vector Space Model, SVSM, to distinguish it from the other vector based models. This method can be easily used to find similarity between other types of short text by directly using the new type of short text instead of sentences.

Experiments and Results

We used the Microsoft Research Paraphrase Corpus(MSRPC) [START_REF] Dolan | Unsupervised construction of large paraphrase corpora : Exploiting massively parallel news sources[END_REF] to evaluate our sentence similarity method which consists of 5801 pairs of sentences collected from a range of online newswire over a period of 18 months for experiments. This dataset is divided into 4076 training pairs and 1725 test pairs. The training pairs consist of 3900 paraphrases and the test pairs consist 1147 paraphrase. The remaining sentence pairs in the corpora are not paraphrases. We test our method on these test pairs and compare results with other methods which are tested on the same corpus. We also evaluated the performance of Dice measure, Resemblance measure and an adaptation of the VSM cosine similarity measure on the same test corpus. Resemblance is the method explained in section 2 and the Dice measure follows the same principle of term overlaps whose similarity value is given by the ratio between twice the number of term overlaps and the total number of terms in both the sentences [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. The adopted VSM cosine similarity measure, vector-based (A), is explained in section 1 and uses stems instead of words and calculating the idf value from the given corpus rather than using some external one. The evaluations of these methods are given in Table 1 where the evaluation value named accuracy represents the number of correctly identified true or false classifications [START_REF] Mihalcea | Corpus-based and knowledge-based measures of text semantic similarity[END_REF] and the rest of the evaluation values bare their traditional meaning. In Table 1, the first two section of the table presents the best results according to the highest accuracy achieved by increasing the threshold by 0.1. The remaining results from the other three sections are taken from Abdalgader et al. [START_REF] Abdalgader | Short-text similarity measurement using word sense disambiguation and synonym expansion[END_REF].

Table 1 shows two baseline methods. The random method is the method which randomly assigns similarity values to the sentence pairs and the vector-based method is the VSM based cosine similarity measure between two sentences with tf*idf term weights computed using external corpus. All our experiments were done with stems as terms and without stopwords. The results for our SVSM shows improvement over the baselines with higher recall but are not better than existing methods. Our SVSM method uses the distribution of terms across sentences from which it captures the sense of the term and the correlation between other terms which leads us to believe that the more sentences we have in our corpus the better it will perform. We evaluated this method on a larger set of sentence pairs by using the complete MSRP corpus and found that the method does perform better. The result is shown in the The Dice measure and Resemblance measure perform better than the baseline methods and have similar F-measure values with the existing methods. The evaluation of the vector-based (A) method shows that this method is among the best corpus-based sentence similarity methods with higher precision and recall values and Table 2 shows that even with larger collection of text this method performs equally well.

Conclusion and Discussion

In this paper we introduce a new method (SVSM) to compute the similarity between short text which takes the similarity problem as a classification task. This new method is a modified version of VSM and is similar to the second-order similarity method [START_REF] Kaufmann | Second-order cohesion[END_REF]. This method is able to capture the similarity between short text by using short text vectors which encodes three corpus-based information which are the importance of the term as idf, the distribution of terms in the short text of the corpus which represent the sense of the terms and the correlation between terms present in the pair of short text. SVSM performs better than the baseline methods with high recall and has the potential to perform better with more text available to be able to model the language by encoding the three information it utilizes. Even though this method assumes that the short text are independent of each other, which is unrealistic, we believe that the effect of this assumption can be reduced by using stems and clustering techniques. This belief has not been tested and will be incorporated in our future work.

We also show that stemming increases the performance of vector-based baseline and is one of the best corpusbased sentence similarity method that exist at least for english. We also use two other information retrieval measures, Dice and Resemblance, to find similar sentences and see that they do perform better than the baseline methods. All these experiments have been done on the MSR paraphrase corpus which does not contain other types of similar short text other than paraphrase and therefore, the results only partially represent the ability of the techniques to determine similarity. Further experiments of other types of short text pairs must be done to understand the full extent of the ability of our method.

TABLE 1 -

 1 Different methods to detect similarity between sentences and their performance according to the accuracy, precision, recall, and F-score on the MSR paraphrase detection test set are shown for the given thresholds.

Table 2 .

 2

	Methods	Threshold Accuracy	Precision Recall	F-measure
			Proposed Method
	SVSM	0.6	68.3	70.25	91.7	79.6
			IR Methods
	Vector-based (A)	0.4	70.8	71.2	94.9	81.4

TABLE 2 -

 2 SVSM and VSM based cosine similarity results on the complete MSRP corpus with their performance evaluated according to the accuracy, recall, and F-score for the given thresholds.

also known as the Jaccard or Tanimoto coefficient[START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]

http ://snowball.tartarus.org/


Gui-Song Xia
email: xia@enst.fr

GUI-SONG XIA ET AL.: TEXTURE SEGMENTATION BY GROUPING ELLIPSE ENSEMBLES 1

We address the problem of unsupervised segmentation of textural images by relying on morphological image representations and active contours. More precisely, starting with the assumption that textures are statistical ensembles of local image structures, known as textons, we first suggest to represent a texture image through a tree of ellipses, which are derived from the level lines of the image; we then investigate the statistical properties on the tree of ellipses and finally achieve a segmentation of the texture image by grouping all the ellipses into several subsets according to some statistical measurements. The grouping process is formulated as an energy minimizing problem and the solution is obtained by evolving an active contour based on Kullback-Leibler (KL) divergence through a fast global minimization method. Thanks to the proposed ellipsebased features, the segmentation method can integrate local and global information in the image. The experiments on both synthesized and natural texture images validate the approach.

Introduction

Texture plays an important role in human visual perception and offers crucial cues for solving a wide range of computer vision problems, such as image segmentation or scene analysis. The segmentation of texture is a key problem in computer vision and image understanding, the objective of which is to partition an image into several regions characterized by homogeneous texture attributes. Over the course of the past 40 years, numerous studies have been performed for texture segmentation, see [START_REF] Beck | Similarity grouping of curves[END_REF][START_REF] Beck | A theory of textural segmentation[END_REF][START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF][START_REF] Malik | Contour and texture analysis for image segmentation[END_REF][START_REF] Todorovic | Texel-based texture segmentation[END_REF][START_REF] Tuceryan | Moment-based texture segmentation[END_REF]. In this paper, we address the issue of structured texture segmentation, starting with the assumption that textures are statistical ensembles of local image structures, also known as textons [START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF][START_REF] Zhu | What are textons?[END_REF].

In the literatures, many models have been proposed to analyze and segment textures by using structured approaches. Among those, the early work of Beck et al. [START_REF] Beck | Similarity grouping of curves[END_REF] argued that textural segmentation occurs on the basis of the distribution of simple properties, such as brightness, color, size, the slopes of contours and lines of the elemental descriptors, of "texture elements". Julesz [START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF] proposed to use textons, a set of empirical texture features including elongated blobs, line ending or terminators, for computational texture modeling, and the segmentation of texture was consequently achieved through these features. In [START_REF] Zhu | What are textons?[END_REF],

Zhu et al. provided a computational model of textons by relying on Gabor base functions and a specified vocabulary of texton templates. Recently, Todorovic et al. [START_REF] Ahuja | Extracting texels in 2.1d natural textures[END_REF][START_REF] Todorovic | Texel-based texture segmentation[END_REF] suggested to extract explicit textural elements from hierarchical segmentation tree and made use of them for texture segmentation. These approaches provide impressive segmentation results on highly structured texture images. However, one main disadvantage of such methods is that the computation or detection of such textons is not trivial itself. Moreover, modeling the interactions between textons may involve heavy computation.

The study presented in this paper is inspired by works in mathematic morphology, more precisely, by granulometry [START_REF] Maragos | Pattern spectrum and multiscale shape representation[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF], which characterize textures relying on responses to morphological filtering with user-specified structuring elements of increasing size. The segmentation of synthetic and simple textural images can be achieved by partitioning the image according to some statistics of the granulometry [START_REF] Chen | Gray-scale morphological granulometric texture classification[END_REF][START_REF] Fletcher | Texture segmentation using area morphology local granulometries[END_REF][START_REF] Maragos | Pattern spectrum and multiscale shape representation[END_REF], but it fails at describing complicated and highly structured textures [START_REF] Fletcher | Texture segmentation using area morphology local granulometries[END_REF]. Instead of using structuring elements and improving the discriminative powerful, alternative approaches have been proposed to analyze textures based on connected operators which perform directly on the level lines of images, see [START_REF] Gousseau | Texture synthesis through level sets[END_REF][START_REF] Hamdan | Texture classification through level lines[END_REF][START_REF] Xia | Shape-based invariant texture indexing[END_REF]. The main motivation of this paper is to investigate the granulometry-like approach in the context of texture segmentation. Along the line of textons, we first suggest to represent textures by a tree of ellipses, which are derived from the level lines of images and can be regarded as explicit textons, see Figure 1 for a preliminary graphical illustration. Observe that the ellipse-based representation in Figure 1(c) has very similar visual appearance to the original image. As we shall see in the following sections, the tree of ellipses of an image can be computed rapidly and efficiently, thus the proposed approach can overcome difficulties in the detection of texture primitives or texture elements as encontered in [START_REF] Ahuja | Extracting texels in 2.1d natural textures[END_REF][START_REF] Todorovic | Texel-based texture segmentation[END_REF]. Based on this representation, textures are subsequently characterized by geometric properties of and by relationships between these ellipses. Texture segmentation is performed by grouping these properties in a unsupervised way. Specifically, the grouping step benefits from an active contour model based on Kullback-Leibler (KL)-divergence similar to the one of [START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF].

The contribution of this paper is to propose a new texture segmentation approach by relying on an ellipse-based texture representation, where ellipses are regarded as texture elements. We argue that natural texture images can be approximated well by a tree of ellipses and the boundaries between two texture regions can be identified by grouping these ellipse ensembles according to some statistical properties with an active contour model. This work somehow fills the gap between granulometry and texton theory on segmentation. Thanks to the ellipse-based features, which might be non-local, the segmentation method can integrate local and global information in the image. Furthermore, the proposed approach is flexible: it allows to segment images subjected to scaling and rotations and it is robust to illumination changes inside the image. In this paper, we also adapts the KL-divergence based active contour model to multi-features, which enables us to take into account different texture cues for segmentation.

The remainder of the paper is organized as follows. In Section 2, we present the ellipsebased texture representation. We then describe in detail the unsupervised texture segmentation with active contours in Section 3. In Section 4, we provide experimental results and finally conclude the paper in Section 5.

Texture representation by a tree of ellipses

In this section, we first recall the basics of the topographic map representation of images and then describe the ellipse-based texture representation

Topographic map of an image: a tree of shapes

The topographic map representation of images has been first introduced by Caselles et al. [7] in computer vision. It is a hierarchical structure composed of shapes and relying on connected components of level sets. It is a powerful way to represent the geometrical content of an image [6, [START_REF] Caselles | Geometry and color in natural images[END_REF][START_REF] Xia | Shape-based invariant texture indexing[END_REF].

For a gray-scale image u : Ω → R, the upper and lower level sets are defined respectively as χ λ (u) = {x ∈ Ω; u(x) ≥ λ } and χ λ (u) = {x ∈ Ω; u(x) ≤ λ }, for λ ∈ R. The topographic map of the image u is made of the connected components of the topological boundaries of the upper level sets (equivalently of lower level sets) of the image. Both the connected components of upper level sets and those of the lower level sets are embedded in a tree structure. These two tree structures are redundant and can be combined into a single one, by drawing on the notion of shape defined as the interior of a level line, i.e. the boundary of a level set. An efficient way to compute the tree of shapes of images is developed in [START_REF] Monasse | Fast computation of a contrast invariant image representation[END_REF], named fast level set transformation (FLST). (The codes of FLST can be downloaded at http://megawave.cmla.ens-cachan.fr/.) Figure 2(a) and 2(b) respectively show the topographic map of a synthetic image and a real image.

The tree of shapes of an image has many interesting properties: (1) it yields a scale space without any geometrical degradation; (2) it is a complete image representation (the image can be reconstructed from it) that encodes both the geometric and radiometric information simultaneously; (3) it is also invariant to any local contrast changes, as defined in [START_REF] Caselles | Shape preserving local histogram modification[END_REF].

Texture modeling through the tree of ellipses

Figure 1(b) suggests that topographic maps reflect the structures of texture. This observation has first been addressed in [7] and has been widely used as a basic assumption by followings [START_REF] Gousseau | Texture synthesis through level sets[END_REF][START_REF] Xia | Shape-based invariant texture indexing[END_REF] on texture analysis relying on topographic maps.

Here, we suggested that, indeed, textures can be well approximated and represented by using a tree of ellipses. It implies that each shape on the topographic map is replaced by an ellipse with the same second-order moments. In Figure 3, we show the ellipse-based texture representation of several natural textures1 , observing how textures are approximated by ellipses. These textures, including textures with elongated structures (the textures in the middle of Figure 3), appear to be well described by a tree of ellipses.

Thus, the modeling of a texture u is reduced to the modeling of the tree of ellipses (E, T ), as

p(u) = p(S, T ) ≈ p(E, T ) (1)
where S := {s i } N i=1 is the set of shapes, E := {e i } N i=1 is the set of ellipses and T : E × E is the tree structure describing the relationships between ellipses. In our case, we use following attributes to describe each ellipse e: where α, ε, κ and θ are respectively defined as log-size, elongation, compactness and orientation of the ellipses, µ pq is the (p + q)-order moment and λ 1 and λ 2 (with λ 1 ≥ λ 2 ) are the two eigenvalues of the inertia matrix of the corresponding shape s.

(α, ε, κ, θ ) := log 4πλ 1 λ 2 , λ 2 λ 1 , 4π √ λ 1 λ 2 µ 00 , 1 2 arctan 2µ 11 µ 20 -µ 02 (2)
Other important texture cues are of course contained in the tree structure. according to the relationships between ellipses. We take these into account by considering local statistics on the tree. More precisely, we use the scale ratio γ, the ratio between the area of an ellipse and the area of its parent on the tree, which is similar to [START_REF] Xia | Shape-based invariant texture indexing[END_REF].

As the use of gray-level information is beneficial for texture discrimination [14, 20, 22] and the above features only describe the geometric aspects of textures, here we make use of the contrast information by considering the normalized gray-level value ρ of pixels in each ellipse. More precisely, for each pixel in an ellipse, its gray level value is normalized by the average and standard derivation of all the pixels inside this ellipse.

Segmentation by grouping ellipses with active contours

Partitioning an image into different regions of homogeneous texture with active contours has been widely studied [START_REF] Aujol | Wavelet-based level set evolution for classification of textured images[END_REF][START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF][START_REF] Sagiv | Integrated active contours for texture segmentation[END_REF]. Here, we make use of it to identify the boundaries between different texture regions. First, in order to obtain local texture features, we cast the model in Section 2.2 to each pixel of the image, which implies that a pixel x from the image u is described by the features of e(x), the smallest ellipse on the tree containing the pixel2 . Thus, a vector ν = (α, ε, κ, θ , γ, ρ) of length 6 is attached to each pixel x. The segmentation then amounts to partition the resulting vectorial image. We chose to use an active contour model based on the Kullback-Leibler (KL) divergence to make a 2-phase partition of the image into the background and the objects of interest.

A recent active contour model has been proposed in [START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF] to find, within an image, two regions with two probability density functions (PDFs) of texture features as disjoint as possible. We chose to adapt this scheme to our framework because it is adapted to histogram-based texture characterization and efficient. Suppose for the moment that each pixel of the image is characterized be a texture feature f . Let p in be the inside PDF, p out the outside PDF, C := C in be the evolving region and Ω/C := C out its complementary set in Ω. The method of [START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF] suggests to maximize the KL-divergence between the PDFs of the regions inside and outside the evolving active contour C. The PDF corresponds to the random variable made of the texture feature f . The p in and p out associated with a region C are evaluated thanks to a Parzen window as

p in ( f ,C) = 1 |C| C G σ ( f -f (x))dx and p out ( f ,C) = 1 |Ω/C| Ω/C G σ ( f -f (x))dx,
where | • | is the area of a region and G σ (•) is a Gaussian kernel with zero-mean and standard deviation σ , which controls the smoothness of the approximation. The symmetric KLdivergence between p in and p out is defined as

KL p in ( f ,C) p out ( f ,C) = ∞ -∞ p in ( f ,C) • p in ( f ,C) p out ( f ,C) + p out ( f ,C) • p out ( f ,C) p in ( f ,C) d f . (3)
The segmentation then consists in maximizing the difference between the PDFs inside and outside a contour C, as arg min

C L(C) -λ KL p in ( f ,C) p out ( f ,C) , (4)
where L(C) is the length of the contour, and λ is a regularization parameter. After computing the shape derivative, Bresson et al. [START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF] showed that the minimization of the energy in Equation ( 4) can be solved by a variational model, enabling the fast computation of a global optimum.

In our case, according to the texture modeling in Section 2.2 and making an assumption that the components of ν = (α, ε, κ, θ , γ, ρ) are independent, together with the additive property of KL-divergence on independent variables, we have,

KL p in (ν,C) p out (ν,C) = ∑ υ∈{α,ε,κ,θ ,γ,ρ} KL p in (υ,C) p out (υ,C) , and arg min C L(C) -λ ∑ υ∈{α,ε,κ,θ ,γ,ρ} KL p in (υ,C) p out (υ,C) , (5)
whose minimization is achieved by the variational method proposed in [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF].

Experimental Results

In this section, several examples of the resulting segmentation scheme are displayed. Figure 4 shows segmentation results on several composite texture images. Each image is composed of two different textures, which have been radiometrically corrected in order to share the same global mean and standard deviation. To compare with the state-of-the-art results, we also show the segmentation results obtained on these images using the texture features based on shape operators proposed by Houhou et al [START_REF] Houhou | Fast texture segmentation model based on the shape operator and active contour[END_REF], which are reported to outperform other methods, such as the model of Savig et al. [START_REF] Sagiv | Integrated active contours for texture segmentation[END_REF] using the vectorial Chan-Vese model and an edge detector function based on Gabor responses. These features heavily rely on contrast information, and therefore may fail in cases where both textures share the same mean and variance. In comparison, we are able to correctly discriminate between both regions. We also experiment on several natural images. The best segmentation results obtained with this method are shown on Figure 5. By "best", we refer to the best choice for the reg-ularization parameter λ in Equation ( 5)). This parameter has been fixed for all experiments. Moreover, observe that the texton extraction step involves no parameter.

Figure 6 illustrates the segmentation results of two Julesz textures, which are composed of simple shapes or terminators. The segmentations are satisfying. However, observe that the obtained segmentations are inconsistent with human texture perception, since these two textures are not distinguishable by pre-attentive vision [START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF].

Although this approach may yield excellent results, it is important to notice that those results highly depend on the regularization parameter λ in the energy, as it is usual with active contour models and other energy minimization based segmentation models. These results could certainly benefit from recent developments in global minimization for active contour models such as those of [START_REF] Bresson | Fast global minimization of the active contour/snake model[END_REF].

Conclusion

In this paper, we proposed a new texture segmentation approach by relying on the granulometrylike texrture analysis method. where ellipses are regarded as texture elements and textures are characterized by statistics from the ellipse ensembles. We argue that the boundaries between two natural texture regions can be identified well by grouping these ellipse ensembles according to some statistical properties with an active contour model. In general, this work somehow fills the gap between granulometry and texton theory on segmentation. It is convinced by the experimental results that the proposed texture segmentation approach is efficient for texture segmentation and is also available for textures with geometric transformations. Notice that this method is very related to the work of Lazebnik et al. [START_REF] Lazebnik | A sparse texture representation using local affine regions[END_REF], who used ellipse-shaped regions extracted by interest points/regions detectors to form a sparse texture representation. But they did not consider the geometric properties of the regions and did not take into account the relationships between them for texture analysis.

Figure 1 :

 1 Figure 1: Represent an image by a tree of ellipse. (a) an original texture image; (b) a subset of its level lines; (c) the image reconstructed from the tree of ellipses, where each shape, i.e. the interior of a level line, is replaced by an ellipse.

  (a) The tree of shapes representation (right) of a synthetic image (left). (b) The tree of shapes representation of the texture image in Figure 1. Left: the shapes displayed by their boundaries; Right: the tree structure, i.e. relationships between shapes.

Figure 2 :

 2 Figure 2: The tree of shapes representation of images. In order to show the tree structure, in the left graphs of (b), shapes are indicated by points and the parent-child relationships between two shapes are expressed by line segments. The root of the tree is the image frame, denoted by a small circle in red.

  (a) Four natural texture images (b) The ellipse-based representation of the textures in (a).

Figure 3 :

 3 Figure 3: Ellipse-based texture representation. Top : original texture images; Bottom : represented textures using ellipse-based textons, where each shape is replaced by an ellipse but the tree structure is kept. Refer to the text for more details.

Figure 4 :

 4 Figure 4: Segmentations of composite texture images made of two textures, radiometrically normalized to share the same mean and standard derivation. The segmentation boundaries (in red) overlay the original images. Left column: original textures; Middle column: the segmentations obtained by the method of Houhou et al. [14]. Right column: the segmentations obtained by the proposed method.

Figure 5 :

 5 Figure 5: Segmentations of natural texture images. The segmentation boundaries overlaying the original images are displayed in red. Top row: real textures; Middle row: the segmentations obtained by the method of [14]. Bottom row: the segmentations obtained by the proposed method.

Figure 6 :

 6 Figure6: Experiments on the segmentation of two synthetic Julesz textures. The segmentation boundaries overlaying the original images are displayed in red. The segmentations are satisfying. However, observe that the obtained segmentations in the middle and on the right are inconsistent with human texture perception, since these two textures are not distinguishable by pre-attentive vision[START_REF] Julesz | Textons, the elements of texture perception, and their interactions[END_REF].

(a) (b) (c)

Remark that after replacing each shape in the tree by an approximating ellipse, the inclusion relationships between shapes may be destroyed. The displayed images are obtained by superimposing ellipses on a blank background with a large-first order.

The smallest ellipse of each pixel is assigned when the topographic map is computed by FLST.

Acknowledgement The authors like to express their thanks to, Yann Gousseau and Julie Delon for their discussions and suggestions on this work, Nawal Houhou for kindly sharing his codes on texture segmentation, and the anonymous reviewers for their helpful comments.