Pierre Héroux
email: pierre.heroux@univ-rouen.fr

Sébastien Diana
email: sebastien.diana@univ-rouen.fr

Arnaud Ribert
email: arnaud.ribert@univ-rouen.fr

Eric Trupin
email: eric.trupin@univ-rouen.fr

Classification Method Study for Automatic Form Class Identification

In this paper we present three classifiers used in automatic forms class identification. A first category of classifier includes the k-Nearest Neighbours (kNN) and the Multi-Layer Perceptron (MLP) classifiers. A second category corresponds to a new structural classifier based on tree comparison. On one hand, a low level information based on a pyramidal decomposition of the document

image is used by the kNN and the MLP classifiers. On the other hand, a high level information represents the form content with a hierarchical structure used by the new structural classifier. Experimental results are presented. Some strategies of classifier co-operation are proposed.

Introduction

A form processing system automatically extracts and understands the content of the forms. Such a system is based on the knowledge of location and meaning of areas on the form and consistency links between them which define the reading model. Most of form processing systems have to be set up by the reading model to process a given form. Our approach is based on an automatic form class identification to select the reading model (Figure 1). In section 2, the information extraction module is developed. Classification methods using the low level information is presented in section 3. Section 4 presents a new structural classification method based on tree comparison. Experimental results concerning each classifier are detailed in section 5. Finally, strategies of hybrid approaches are presented in section 6.

Information extraction

In this section we present the two kinds of information extracted by the identification module.

Image pyramidal decomposition

This pyramid construction is based on a recursive cut of the binary image into rectangular regions in which black pixel density is calculated. The pyramid presents several cut levels with a different granularity. The first level corresponds to the black pixel density in the whole image, the second level gives black pixel density in 4 rectangular cuts, the third level cuts the image in 16 parts… A 5 level cut returns a 341 (1+4+16+64+256) feature vector used by the MLP and kNN classifiers.

Hierarchical structure extraction

A high level information describes the organisation of the form content with a hierarchical structure (modelled by a tree) which represents the hierarchical links between each element of the form (Figure 3). ). The textblocks are segmented in sub-blocks representing textlines. The relative location of text-lines in the block allows to perform a logical labelling of the text-blocks (paragraph first line, paragraph line, paragraph last line…). The extracted elements are organised in order to obtain a tree structure in which nodes are labelled (location, dimension, layout and logical attribute). For more detailed information on structure extraction see [START_REF] Diana | An Assistant to the Modelisation of Forms[END_REF] et [START_REF] Diana | From Acquisition to Modelisation of a Form Base to Retrieve Information[END_REF].

Text Graphic

Two classic classification methods

The k-Nearest Neighbours [START_REF] Cover | Nearest Neighbour Pattern Recognition[END_REF] and the Multi-Layer Perceptron use as an input the feature vector expressing the pixel density at different resolution. The principle of classifiers are reminded in the following paragraphs

K-Nearest Neighbours

The kNN classifier is based on the fact that if two elements are close in their representation space, they probably belong to the same class. As mentioned before, each form is represented by a feature vector which represents its co-ordinates in a multi-dimensional representation space. In order to identify the class of a form, the form class of its k nearest points in the representation space is a significant information.

It is commonly admitted that the reliability increases with k. A strict rule is to impose that the k nearest neighbours belong to the same class to take a decision. This rule reduces the number of errors, but it leads to many rejects. It can be smoothed by weighting the voting of each neighbour according to its rank or distance. The main drawback of this classifier is the number of calculations needed to find the k nearest neighbours. Some improvements are proposed in [START_REF] Fukunaga | Introduction to Statistical Pattern Recognition[END_REF].

Multi Layer Perceptron

The MLP is a layer-organised neural network. Only connections between neurones of two consecutive layers are allowed. The neurone output is calculated as the weighted sum of its inputs to which is applied a nonlinear sygmoid function. Synaptic weights are usually determined in a learning phase using back-propagation algorithm [START_REF] Rumelhart | Parallel Distributed Proc. :Explorations in the Microstructure of Cognition[END_REF]. The MLP is known for its decision speed and its good generalisation capacity.

Structural classification method

This method performs the form class identification by comparing a tree representing the form (section 2.2) with tree representation of the form classes.

Many tree comparison methods exist. Some of them (Selkow's algorithm [START_REF] Miclet | Méthodes structurelles pour la reconnaissance des formes[END_REF], Thomasson and Gonzalez [START_REF] Thomasson | Syntactic Recognition of Imperfectly Specific Patterns[END_REF]) are based on an isomorphism and label similarity measurement. Others are graph matching algorithms [START_REF] Ishitani | Model Matching Based on Association Graph for Form Image Understanding[END_REF] [START_REF] Budin | On the Problem of Attributed Relational Graph Matching[END_REF] which can be applied to trees (particular cases of graphs).

Finally, we propose an iterative algorithm. Roots of the trees to be compared are first examined. If they are equal, equality is looked for among their sons. Then the sub-trees whose roots are equal are compared, and so on… Nodes are considered as equal if the difference between their label does not exceed a threshold. Finally, this gives the largest tree common to the compared trees.

Section 4.1 presents the form class identification method. The construction of trees representing form classes is detailed in section 4.2. An organisation of model tree database which improve identification in term of computation time is presented in section 4.3.

Form class identification

To identify the class of a given form, comparisons between the tree representing the form and the model trees representing all classes are performed. Each comparison returns the common tree between the specific and the model tree. Three features are extracted at each comparison : the number of nodes of the common tree and the overlap rates of the common tree in the compared trees. These rates limit the density variation influence between classes and the variability problem in each class. The examination of these features allows to determine the nearest model tree. The features of the selected model tree are submitted to a threshold presented in 4.2. When the features extracted from the tree comparison do not satisfy the threshold, the form is considered as belonging to an unknown class.

Model trees construction

Each form class is represented by a model tree. It includes the most frequently encountered features in trees representing forms from the considered class.

The forms are hand-filled. Hand-written data are added in predefined areas called « active areas ». Data variations and writers multiplicity involve a low stability on corresponding nodes contrary to passive areas. Model trees are constructed in a learning supervised phase. In a first step, the most frequently encountered nodes in a training set containing trees from the same class are listed. Nodes which are not significant enough (low appearance frequency) are removed from the list. In a second step, model trees are constructed from this list by linking nodes of two consecutive levels with compatible labels.

Once constructed, the features presented in section 4.1 are extracted from comparisons of trees of the training set with the model tree obtained. A statistical study has shown that the features follow a Gaussian law. For each model tree, mean m and standard deviation σ are calcu- lated. The identification process determines the class for which the model tree is the nearest from the input tree. The returned class is kept as the identification result if the features are over m-2σ, else, the form is rejected as belonging to an unknown class. The automatically computed threshold differs for each class and represents the difference of density and stability in and among the classes.

The hierarchy of models

The form class identification is improved with a hierarchical organisation of the model tree database which reduces computations. The hierarchy is constructed by recursively grouping common features in meta-models. The obtained hierarchy is a binary tree where the nonterminal nodes correspond to meta-models and the terminal nodes correspond to models.

The form class identification is performed by finding a path leading to a terminal node. The path search is performed at each node of the hierarchy by comparing the input tree with the two meta-models to find the nearest one. An algorithm which allows to simultaneously explore the k best paths is used to make the identification more reliable.

The path search involves a lower comparison number than for the whole model database exploration. Moreover, because of its lower number of nodes, comparing a tree with a meta-model is faster than with a model.

Experimental results

In this section, the experimental results concerning the discussed classifiers are presented.

Classical classifiers

The results (Table 1) concern 570 forms from 27 different classes. This set has been cut in equally sized learning and test sets. For each form 2, 3, 4 and 5 level pyramids have been generated. The kNN classifier has been set with k=1 and uses Euclidean distance. The MLP has been set with 1 hidden layer containing 27 neurones.

Structural classifier

The results (Table 2) have been observed on a 1420 form set. 1300 of these belong to 26 learned classes and 120 belong to unlearned classes. Otherwise, the learning phase has been performed with 10, 20, 30 or 40 forms per class. These results show a good capacity in rejecting unknown forms and no error in the identification of forms from known classes with an interesting recognition rate. The number of forms used in the model tree construction seems to be an important parameter (better performances when it grows).

Conclusion

In this paper, we have presented three different classifiers used in form class identification. Classical classifiers (k-Nearest Neighbours and Multi-Layer Perceptron) use a low level information on the binary image of the form. A new structural classifier exploits a tree structure representing the form content organisation. This classifier is based on tree comparison.

The three classifiers show good recognition rates. Moreover, these results highlight the pertinence of the used features even if it will be necessary to test their performances on more representative test set.

Finally, our prospects are based on the set up of a classification strategy which consists in combining both classifier types. A first strategy corresponds to use the classical classifiers as pre-classifier to reduce the number of candidate classes. Then, the structural classifier will be applied to find the correct class. A second approach consists in co-operation where both classifiers suggest an ordered list of candidate classes from which correct class is then selected by a vote.

Figure 1 :

 1 Figure 1 :Form processing system evolution The identification module extracts a low level information used by classical classifiers, and a structural representation of the form content used by a new classifier.In section 2, the information extraction module is developed. Classification methods using the low level information is presented in section 3. Section 4 presents a new structural classification method based on tree comparison. Experimental results concerning each classifier are detailed in section 5. Finally, strategies of hybrid approaches are presented in section 6.

Figure 2 :

 2 Figure 2 : a form and its 5 level cut

Figure 3 :

 3 Figure 3 : hierarchical structure The extraction is organised in five main processes. A segmentation phase is performed on the form image and returns homogenous blocks [1] [2]. Then, the blocks are labelled (text, graphic, line segment, table). The textblocks are segmented in sub-blocks representing textlines. The relative location of text-lines in the block allows to perform a logical labelling of the text-blocks (paragraph first line, paragraph line, paragraph last line…). The extracted elements are organised in order to

Table 1 :Classical classifier results

 1

	Pyramid	Recognition (%)	Reject (%)	Error (%)
	Level	kNN	MLP	kNN	MLP	kNN	MLP
	2	96.84	94.04	0.00	1.75	3.16	4.21
	3	99.65	99.65	0.00	0.00	0.35	0.35
	4	100.00	99.65	0.00	0.35	0.00	0.00
	5	100.00	100.00	0.00	0.00	0.00	0.00

Table 2 :Results of the structural classifier

 2

Acknowledgements

This study was performed in the ADI (Intelligent Archiving and Documentation) project context in association with DPCi, a company specialised in document scanning, printing and processing.


Pharm.D. Mr Yves Liem

Pharm.D. Yves ; Liem
email: y.liem@umcutrecht.nl

R Eibert

PhD ; Heerdink

C Toine

PharmD, PhD; Carin M Egberts

PharmD Rademaker

PharmD Carin M A Rademaker

T B Y Liem

Keywords: antibiotic use, Defined Daily Dose (DDD), neonates antibiotic use, Defined Daily Dose (DDD), neonates 19

Purpose

The Defined Daily Dose (DDD) as defined by the World Health Organization (WHO) has been the most frequently used unit of measurement to measure antibiotic use. However, measuring antibiotic use in paediatrics is a problem as the WHO DDD methodology is not applicable in children (aged > 1 month), because the large variation in body weight within this population. Based on the narrow range of body weights in the neonatal population, we therefore aimed to develop a set of neonatal DDDs for antibiotics.

Methods

Eight well-respected (inter)national sources for dosage recommendations of antibiotics in children and neonates were consulted for the assumed maintenance dose of the 10 most frequently used antibiotics in neonatal intensive care units in its main indication for neonates.

Results

A set of neonatal DDDs for ten commonly used antibiotics in neonates based on an assumed neonatal weight of 2 kg was proposed.

Conclusions

Primarily in children DDDs are not applicable to quantify antibiotic use since there is large variation in body weight. In the neonatal population, however, based on its narrow range of body weights and when access to patient level data is not available, neonatal DDDs can be used as unit of measurement.

Dear Dr Van Belkum, Thank you very much for the comments on our manuscript, which helped us to improve our manuscript.

We are very pleased that our manuscript is considered interesting and that we have been given the opportunity to revise the document.

We highlighted all changes in yellow in the revised manuscript and mentioned the referring line numbers in our answers to you.

We have carefully studied the comments and included a point by point summary of our response on the comments (see below).

Answer to the comments of the reviewer:

Major remarks 1.

The reliability of the proposal of DDDs can be improved considerably by including more details about the exact proposed dose given by each of the eight 'well-respected' sources and by adding this information to table 1.

We added the exact proposed dosages of the ten antibiotics given by each of the eight reference sources to table 1.

2.

You mentioned to present DDDs for 'the 10 most frequently used antibiotics in NICUs'. What sources did you use to identify these 10 antibiotics? Did you also include international sources?

For the selection of the 10 most frequently used antibiotics in neonates, we used data of our study as recently published in the Journal of Antimicrobial Chemotherapy (Liem et al. J. Antimicrob. Chemother. 2010; 65: 1270-1275; doi:10.1093/jac/dkq107) in which we showed the variation in antibiotic use in all ten tertiary care neonatal intensive care units in the Netherlands. In addition, we also included data of international studies on the antibiotic use in NICUs for this selection of 10 antibiotics, such as: The 'Instructions for authors', however, don't permit us to add all these articles to the reference list, as a maximum of 10 references is allowed for a 'Brief report'.

o Du W, Warrier I, Tutag L, V, Salari V,

3.

In your report, you motivated why you developed DDDs for neonates. As long as comparisons are geographically limited to one country however, other methods to approach the volume of consumed antibiotics can be used. You forgot however to mention that the use of DDDs is particularly recommended for international comparisons.

We agree with the reviewer's comment that the use of DDDs is mainly recommended for international comparisons. Therefore, we rephrased lines 61-62 and 67 in our revised manuscript.

You mentioned the link between antibiotic use and resistance. I am wondering however if a relationship between neonatal antibiotic use and resistance has been demonstrated

, as yet. If so, references need to be added. If not, please speak about resistance in a more generalized way, clearly stating that there is still a lack of knowledge in this field.

There certainly have been studies showing a relationship between antibiotic use and resistance in neonates. Therefore, we added some information (including a reference) regarding this issue in lines 129-133 in our revised manuscript.

Editing remarks 1.

I do not know if form requirements exist for the publication of a Brief Report in the journal. It looks rather strange however, that on the one hand a well-structured abstract was added to your report and that on the other hand, the body of the report lacks any structure.

Although we submitted our manuscript as a 'Brief Report', the 'Instructions for authors' of the European Journal of Clinical Microbiology and Infectious Diseases stated that we are obliged to submit a structured abstract of 150 to 250 words which should be divided into the following sections: Purpose (stating the main purposes and research question), Methods, Results, Conclusions.

The complete references of the 'well-respected' sources should be added to the reference list with only reference numbers in table 1.

We added the complete references of the eight reference sources to the reference list of our revised manuscript. As a consequence we exceed the maximum of 10 references as stated for a 'Brief report'. 1). [START_REF] Liem | Variation in antibiotic use in neonatal intensive care units in the 175 Netherlands[END_REF] Considering these 107 antibiotics we did not found discrepancies in the dosage recommendations between 108 the various evaluated sources. In addition, this overview of assumed maintenance

  Dose (DDD) as defined by the World Health Organization (WHO) 32 has been the most frequently used unit of measurement to measure antibiotic use. 33 However, measuring antibiotic use in paediatrics is a problem as the WHO DDD 34 methodology is not applicable in children (aged > 1 month), because the large 35 variation in body weight within this population. Based on the narrow range of body 36 weights in the neonatal population, we therefore aimed to develop a set of neonatal 37 DDDs for antibiotics. 38 39 Methods 40 Eight well-respected (inter)national sources for dosage recommendations of 41 antibiotics in children and neonates were consulted for the assumed maintenance 42 dose of the 10 most frequently used antibiotics in neonatal intensive care units in its 43 main indication for neonates. neonatal DDDs for ten commonly used antibiotics in neonates based on an 47 assumed neonatal weight of 2 kg was proposed. DDDs are not applicable to quantify antibiotic use since there is 51 large variation in body weight. In the neonatal population, however, based on its 52 narrow range of body weights and when access to patient level data is not available, 53 neonatal DDDs can be used as unit of measurement.

  on body weight. Therefore, in order to calculate a paediatric DDD, 84 an average body weight for the paediatric population needs to be assumed. 85 However, in our opinion, this methodology is questionable as there is a large 86 variation in body weight within the paediatric population. This view is supported by 87 the WHO International Working Group for Drug Statistics Methodology's publication 88 'Guidelines for ATC classification and DDD assignment'.[START_REF]Guidelines for ATC classification and DDD assignment[END_REF] In this, the WHO states 89 that it is impossible to define paediatric DDDs because dose recommendations for 90 use in children vary according to age and body weight (and setting). Furthermore, 91 many drugs used in paediatrics are not even approved for such use and dosing 92 information is not available. In response to the WHO's negative comments about 93 paediatric DDDs, several alternative measurement systems for antibiotic use in 94 children have been proposed, e.g. an estimation of antibiotic exposure by controlling 95 for patient weight and amount of wasted drug. [9;10] 96 Nevertheless, regarding the issue on variation in body weight, one should distinguish 97 children (>1 month of age) from neonates (<1 month of age) as the variation in body 98 weight in children (mean body weight at age 1 month: 4.2 kg [11]; mean body weight 99 at age of 17 years: 60 kg [12]) is larger compared to the neonatal population (mean 100 body weight: 2.1 kg ± 1.0, based on own data). Consequently, in our view the 101 disadvantage of the DDD methodology in paediatrics is more relevant for children 102 than for neonates. Therefore, we aimed to devise a set of neonatal DDDs for 103 antibiotics. We consulted eight well-respected (inter)national sources for dosage 104 recommendations of antibiotics in children and neonates for the assumed 105 maintenance dose of the 10 most frequently used antibiotics in NICUs in its main 106 indication for neonates (i.e. neonatal sepsis) (Table

109

  dosages was evaluated and approved by two external experts: a hospital pharmacist 110 and a paediatrician-infectious disease specialist. As a result, we propose a set of neonatal DDDs for commonly used antibiotics in neonates based on an assumed 112 neonatal weight of 2 kg. (Table 1) Regarding these proposed neonatal DDDs, one 113 should, however, take into account the general limitations of the DDD but also 114 limitations specific to this patient group such as the policy on handling of waste of 115 unused antibiotics in a NICU setting. After all, waste of unused antibiotics would not 116 reflect a real estimate of neonatal DDDs.117 Obviously, our proposed neonatal DDDs do not alter the fact that there is a lack of 118 data on antibiotic use on the individual patient level. Yet, with the increasing use of 119 computerised medical information systems it will be considerably easier to get 120 access to data on the level of the individual patient, such as days of therapy (DOT). 121 DOT is not influenced by discrepancies between the DDD and the PDD, by changes 122 in the WHO assigned DDD and is independent of age-and weight-related 123 differences in dosage. [7;14] A major disadvantage of this parameter is, however, 124 that currently such detailed data on the individual patient level are not readily 125 available. Moreover, if one would like to link data on antibiotic use to resistance, 126 preferably both units of measurement, DOT (independent of dosage) and DDD 127 (dependent of dosage), should be used, since it is unidentified which of these 128 measurement methods is most predictive of resistance. [7] A recent study has shown 129 that repeated and/or prolonged antibiotic use in neonates resulted in an increase of 130 hospital-acquired, antibiotic-resistant organisms such as methicillin-resistant 131 Staphylococcus aureus, vancomycin-resistant Enterococcus, and multidrug-resistant 132 Gram-negative rods. [15] 133 In conclusion, in order to quantify antibiotic use the DDD methodology is not 134 applicable in the paediatric population, mainly in children aged between 1 month-18 135 years, because the large variation in body weight within this population. Although in 136 the neonatal population, until patient level data are widely available and based on its 137 narrow range of body weights, we suggest, illustrated by the example of antibiotics, 138 that the neonatal DDD (nDDD) is a good alternative unit of measurement, both in 139 research and for benchmarking purposes.

  Gortner L. Drug utilisation in preterm and term neonates.

	o Clark RH, Bloom BT, Spitzer AR, Gerstmann DR. Reported medication use
	in the neonatal intensive care unit: data from a large national data set.
	Pediatrics 2006; 117(6):1979-1987.
	Ostrea E, Aranda JV. Changing
	patterns of drug utilization in a neonatal intensive care population. Am J
	Perinatol 2006; 23(5):279-285.
	Pharmacoeconomics 1993; 4(6):437-445.
	o Grohskopf LA, Huskins WC, Sinkowitz-Cochran RL, Levine GL, Goldmann
	DA, Jarvis WR. Use of antimicrobial agents in United States neonatal and
	pediatric intensive care patients. Pediatr Infect Dis J 2005; 24(9):766-773.
	o Lesko SM, Epstein MF, Mitchell AA. Recent patterns of drug use in
	newborn intensive care. J Pediatr 1990; 116(6):985-990.
	o Warrier I, Du W, Natarajan G, Salari V, Aranda J. Patterns of drug
	utilization in a neonatal intensive care unit. J Clin Pharmacol 2006;
	46(4):449-455.

o

Table 1 . Overview neonatal DDDs top 10 antibiotics NICUs 148

 1

		Maintenance dose in mg/kg/day in its main indication for neonates
										Assumed	Neonatal
										maintenance	DDD (g)	Adult DDD
										dose in	(assumed	(WHO 2005)
										mg/kg/day in	average	(g)	Factor
										its main	body	(assumed	(adult vs
	Name of									indication for	weight of	body weight	neonatal
	antibiotic	[16]	[17]	[18]	[12]	[11]	[19]	[20]	[21]	neonates	2 kg)	of 70 kg)	DDD)
	Ampicillin	n.a.	100	100	100	100-200	100-200	100	200	100	0.2	2	10
	Amoxicillin	75-100	n.a.	n.a.	n.a.	100-150	n.a.	n.a.	n.a.	100	0.2	1	5
	Amoxicillin and
	enzyme
	inhibitor	100	n.a.	n.a.	n.a.	90	n.a.	n.a.	n.a.	100	0.2	3	15
	Flucloxacillin	100	n.a.	n.a.	n.a.	100	n.a.	n.a.	n.a.	100	0.2	2	10
	Ceftazidime	150	150	150	150	75	150	150	150	150	0.3	4	13
	Cefotaxime	150	150	150-200	150-200	75-100	150-200	150-200	150	150	0.3	4	13
	Meropenem	60	60	60	60	60	60	60	60	60	0.12	2	17
	Erythromycin	30	n.a.	n.a.	30	50	n.a.	n.a.	n.a.	30	0.06	1	17
	Gentamicin	4	5	5	5	4	5	5	5	4	0.008	0.24	30
	Vancomycin	30	30	30	30-60	45	30-60	30	30	30	0.06	2	33
	149
	n.a. not available

Acknowledgments


Eugen Barbu
email: eugen.barbu@univ-rouen.fr

Pierre Héroux

Sébastien Adam

Éric Trupin

Using Bags of Symbols for Automatic Indexing of Graphical Document Image Databases

A database is only usefull if it is associated a set of proce-dures allowing to retrieve relevant elements for the users' needs. A lot of IR techniques have been developed for automatic indexing and retrieval in document databases. Most of these use indexes depending on the tex-tual content of documents, and very few are able to handle graphical or image content without human annotation.

This paper describes an approach similar to the bag of words technique for automatic indexing of graphical document image databases and diferent ways to consequently query these databases. In an unsupervised manner, this approach proposes a set of automatically discovered sym-bols that can be combined with logical operators to build queries.

Introduction

A document image analysis (DIA) system transforms a document image into a description of the set of objects that constitutes the information on the document in a way that can be processed and interpreted by a computer [START_REF] Antonacopoulos | Introduction to Document Image Analysis[END_REF]. Documents can be classified in mostly graphical or mostly textual documents [START_REF] Nagy | Twenty years of document analysis in pami[END_REF]. The mostly textual documents also known as structured documents respect a certain layout and powerful relations exist between components. Examples of such documents are technical papers, simple text, newspapers, program, listing, forms. . . Mostly graphical documents do not have strong layout restrictions but usually relations exist between diferent document parts. Examples of this type of documents are maps, electronic schemas, architectural plans. . . For both categories of documents, graph based representations can be used to describe the image content (e.g. region adjacency graph [START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF] for graphical and Voronoi-based neighbourhood graph [START_REF] Bagdanov | Fine-grained document genre classification using first order random graphs[END_REF] for textual document images).

This paper presents an approach similar with the "bag of words" method from Information Retrieval (IR) field applied to graphical document images. A ocument representation is built based on a bag of symbols found automatically using graph mining [START_REF] Washio | State of the art of graph-based data mining[END_REF] techniques. In other words, we consider as "symbols", the frequent subgraphs of a graph-based document representation and we investigate if the description of a document as a bag of "symbols" can be profitably used in an indexing and retrieval task.

The approach has the ability to process document images without knowledge of models for document content. Frequent items are used in clustering of textual documents [START_REF] Fung | Hierarchical document clustering using frequent items[END_REF], or in describing XML documents [START_REF] Termier | Mining xml data with frequent trees[END_REF], but we do not know any similar approach in the DIA field.

In the area of research for document image indexing, approaches based on partial document interpretation exist [START_REF] Doermann | The indexing and retrieval of document images : A survey[END_REF]. The images are automatically indexed using textual and graphical cues. The textual cues are obtained from the results proposed by an OCR system. The graphical indices are obtained by user anno-tation, or by an automatic procedure. In [START_REF] Lorenz | Automatic indexing for storage and retrieval of line drawings[END_REF], Lorenz and Monagan present an automatic procedure. Junctions of adjacent lines, parallel lines, collinear lines and closed polygons are used as image features for indexing. Then, a weighting schema is used to reflect the descriptive power of a feature. In our paper, we also use term weighting but on a representation from a higher semantic level than the simple features used in [START_REF] Lorenz | Automatic indexing for storage and retrieval of line drawings[END_REF].

The outline of this paper is as follows. Section 2 presents the graph represen-tation used and shows how we create this representation from a document image. Section 3 presents the graph-mining method used. In Sect. 4, we describe how we search documents based on dissimilarities between bags of objects. Section 5 shows experimental results. We conclude the paper and outline perspectives in Sect. 6.

Graph Representation

Eight levels of representation for document images are proposed in [START_REF] Blostein | Document representations[END_REF]. These levels are ordered according to their aggregation relations. Data array, primitive, lexical, primitive region, functional region, page, document, and corpus level are the representation levels proposed.

Without loosing generality, in the following paragraphs we focus on a graph-based representation build from the primitive level. The primitive level contains objects such as connected components (set of adjacent pixels with the same color) and relations between them. From a binary (black and white) document image we extract connected components. The connected components are represented by graph nodes. On each connected component we extract features. In the cur-rent implementation, the extracted characteristics are rotation and translation invariant features based on Zernike moments [START_REF] Khotazad | Invariant image recognition by zernike moments[END_REF]. These invariants represent the magnitudes of a set of orthogonal complex moments of a normalized image.

Let I be an image and C(I) the connected components from I, if c ∈ C(I) , c is described as c = (id, P ), where id is a unique identifier and P the set of pixels the component contains. Based on this set P , we can compute the center for the connected component bounding box and we can also associate a feature vector to it. Based on that, c = (id, x, y, v), v ∈ R n . Subsequently, using a clustering procedure on the feature vectors, we can label the connected component and reach the description C = (id, x, y, l) where l is a nominal label. The graph G(I) representing the image is G = G(V (I), E(I)). Vertices V (I) correspond to connected components and are labelled with component labels. An edge between vertex u and vertex w exists if and only if (u.xw.x) 2 + (u.yw.y) 2 < t, where t is a threshold that depends on the global characteristics of image I (size, number of connected components,. . . ).

The following paragraph presents the clustering procedure used to associate a label to each connected component.

Clustering methods can by categorized into partitional and hierarchical tech-niques. Partitional methods can deal with large sets of objects ("small" in this context means less than 300) but needs the expected number of clusters in input. Hierarchical methods can overcome the problem of number of clusters by using a stopping criterion [START_REF] Milligan | An examination of procedures for determining the number of clusters in a data set[END_REF] but are not applicable on large sets due to their time and memory consumption.

In our case the number of connected components that are to be labelled can be larger than the limit of applicability for hierarchical clustering methods. On the other hand, we cannot use a partitional method because we do not know the expected number of clusters. Based on the hypothesis that a "small" sample can be informative for the geometry of data, we obtain in a first step an estimation for the number of clusters in data. This estimation is obtained using an ascendant clustering algorithm with a stopping criterion. The number of clusters found in the sample is used as input for a partitional clustering algorithm applied on all data.

We tested this "number of cluster estimation" approach using a hierarchical ascendant clustering algorithm [START_REF] Gordon | Classification[END_REF] that employs Euclidean distance to com-pute the dissimilarity matrix, complete-linkage to compute between-clusters dis-tances, and Calinsky-Harabasz index [START_REF] Milligan | An examination of procedures for determining the number of clusters in a data set[END_REF] as a stopping criterion. The datasets (T 1 , T 2 , T 3 ) (see Table 1) are synthetically generated and contain well separated (not necessary convex) clusters. Considering S the sample extracted at random from a test set, in Table 2, we present predicted cluster numbers obtained for diferent sample sizes. After repeating the sampling procedure several times, we obtain a set of estimations for the number of clusters. We can see that by using a majority voting decision rule we can find the good number of clusters in most of the cases and even when the sample size is very small (50 or 100) compared to the data set size.

We used our sampling approach combined with the k-medoids clustering algo-rithm [START_REF] Kaufmann | Clustering by means of medoids[END_REF] on the connected components data set from images in our corpus (see Sect. 5). The k-medoids clustering algorithm is a more robust version of the well known k-means algorithm. The images from our corpus contain 6730 connected components. The proposed number of clusters using ten samples of size 600 is [START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF][START_REF] Kaufmann | Clustering by means of medoids[END_REF][START_REF] Kuramochi | An efcient algorithm for discovering frequent subgraphs[END_REF][START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF][START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF][START_REF] Platt | Fast training of support vector machines using sequential minimal optimization[END_REF][START_REF] Termier | Mining xml data with frequent trees[END_REF][START_REF] Kuramochi | An efcient algorithm for discovering frequent subgraphs[END_REF][START_REF] Tabbone | Matching of graphical symbols in linedrawing images using angular signature information[END_REF][START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF] and by considering the majority voting, we use 16 clusters as input to the partitional clustering algorithm. connected components) and there can be relations of spatial proximity, based on "forces" [START_REF] Tabbone | Matching of graphical symbols in linedrawing images using angular signature information[END_REF], orientation or another criterion. In our current implementation the distance between centers of connected components is used (see Fig. 1). If the distance between two connected component centers is smaller than a threshold, then an edge will link the two components (nodes).

3 Graph Mining "The main objective of graph mining is to provide new principles and efcient algorithms to mine topological substructures embedded in graph data" [START_REF] Washio | State of the art of graph-based data mining[END_REF].

Mining frequent patterns in a set of transaction graphs is the problem of finding in this set of graphs those subgraphs that occur more times in the trans-actions than a threshold (minimum support). Because the number of patterns can be exponential, the complexity of this problem can also be exponential. An approach to solve this problem is to start with finding all frequent patterns with one element. Then, these patterns are the only candidates among which we search for frequent pattens with two elements, etc. in a level-by-level setting. In order to reduce the complexity, diferent constraints are used: the minimum support, the subgraphs are connected, and do not overlap.

The first systems emerged from this field are SUBDUE and GBI [START_REF] Washio | State of the art of graph-based data mining[END_REF]. These approaches use greedy techniques and hence can overlook some patterns. The SUBDUE system searches for subgraphs in a single graph using a minimum de-scription lengthbased criterion. Complete search for frequent subgraphs is made in an ILP framework by WARMR [START_REF] Washio | State of the art of graph-based data mining[END_REF]. An important concept is that of maximal subgraph. A graph is said to be maximal if it does not have a frequent super-graph [START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF]. The graph-mining systems were applied to scene analysis, chemical components databases and workflows. A system that is used to find frequent pat-terns in graphs is FSG (Frequent Subgraph Discovery) that "finds patterns cor-responding to connected undirected subgraphs in an undirected graph database" [START_REF] Kuramochi | An efcient algorithm for discovering frequent subgraphs[END_REF].

In our document image analysis context we are interested in finding maximal frequent subgraphs because we want to find symbols but to ignore their parts.

The input for the FSG program is a list of graphs. Each graph represents a transaction. FSG is efective in finding all frequently occurring subgraphs in datasets containing over 200,000 graph transactions [START_REF] Kuramochi | An efcient algorithm for discovering frequent subgraphs[END_REF]. We present sub-sequently how we construct the transaction list starting from a set of document images. Using the procedure presented in Sect. 2, we create for each document an undirected labelled graph.

Every connected component of this graph represents a transaction. We can further simplify the graphs by removing vertices that cannot be frequent and their adjacent edges. Using FSG we extract the frequent subgraphs and we con-struct a bag of graphs occurring in each document. In the following paragraphs, we consider that the frequency condition is sufcient for a group of connected components to form a symbol and we will conventionally make an equivalence between the frequent subgraphs found and symbols. As we can see in the exam-ple (Fig. 2), the proposed symbols are far from being perfect due to the image noise, connected components clustering procedure imperfections. . . however we can notice the correlation between this artificial symbol and the domain symbols.

Fig. 2. Occurences of a frequent subgraph in an image

In conclusion, the subgraphs proposed as frequent are used to model a docu-ment as a bag of symbols. Because some documents may not contain any sym-bols, the document representation is based on two vectors containing connected components labels, and symbols labels.

A : (c 1 , c 2 , . . . , c n ) , (s 1 , s 2 , . . . , s m )
where c i is the number of connected components labelled as i and s j is the number of occurences of symbol j in document A.

Dissimilarity Between Document Descriptions

In this paragraph, we present the measure employed to qualify the dissimilarity between the descriptions of two document images.

A collection of documents is represented by a symbol-by-document matrix A, where each entry represents the occurrences of a symbol in a document image, A = (a ik ), where a ik is the weight of symbol i in document k. Let f ik be the frequency of symbol i in document k, N the number of documents in the collection, and n i the total number of times symbol i occurs in the whole collection. In this setting, according to [START_REF] Dumais | Improving the retrieval information from external ressources, behaviour research methods[END_REF], one of the most efective weighting scheme is entropy-weighting. The weight for symbol i in document k is given by:

⎛ ⎞ n 1 a ik = log (1 + f ik ). ⎝1 + log N f ij log f ij ⎠ j=1 n i n i
Now, considering two documents A and B with the associated weights A = (a 1 , a 2 , . . . , a t ), B = (b 1 , b 2 , . . . , b t ) where t is the total number of symbols, then

d(A, B) = 1 - t i=1 a i .b i t i=1 a 2 . i t i =1 b i 2
represents a dissimilarity measure based on the cosine correlation.

Experiments

The corpus used for evaluation contains 60 images from 3 categories: electronic (25 images) and architectural schemas (5 images) and engineering maps (30 images) (see Fig. 3). In order to present a corpus summary we employed a mul-tidimensional scaling algorithm to represent in a two dimensional plot the dissim-ilarities between documents (see Fig. 4). Each document image is described with one of the following types of features: simple density and surface based charac-teristics (a vector with 30 components) or the connected components and symbol lists described above. In Fig. 4(a) we present the dissimilarities between images represented using simple features. In Fig. 4(b) are plotted the dissimilarities be-tween the document images computed using the cosine correlation presented in Sect. 4. The engineering maps are plotted using '*' symbols, electronic schemas with '+' , and the architectural schemas with 'x'. We further test the two representations in a classification context. Using a 10 fold stratified cross validation procedure and John C. Platt's sequential minimal optimisation algorithm for training a support vector classifier [START_REF] Platt | Fast training of support vector machines using sequential minimal optimization[END_REF], we obtained the following results given in Tab. 3 We can see in Fig. 4 and the classification results (3) that the bag of symbols representation allows a better separation beetween image classes. This fact has an important influence on the quality of the query results.

A query can be an image, a list of symbols and connected components, or only one of the later lists. (s 1 , 1)(s 2 , 2)(s 3 , 3)(s 4 , 1)(s 5 , 4)(s 6 , 3)(s 7 , 2)(s 8 , 2)(s 9 , 2)(s 13 , 1)(s In order to extract the formal description of a given query image we label the connected components of the query image, construct the graph, and em-ploy graph matching to detect which symbols occur in the query image. At the end of this process the query image is described by the two lists of connected components and symbols. In order to evaluate experimental results we used precision and recall mea-sures. If A is the set of relevant images for a given query, and B is the set of retrieved images then :

precision = | A∩ B | |B | recall = | A∩ B | | A|
As shown on Fig. 3, the corpus contains images that are scanned and contain real and artificial noise.

Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 9 Q
10 recall 0.75 0.5 0.48 0.55 0.56 0.76 0.6 0.4 0.32 0.16 precision 0.6 0.31 0.8 0.73 0.87 0.95 0.88 0.5 0.42 0.4 Table 4 gives 5 most relevant documents relative to the query. Table 5 gives the recall and precision for 10 diferent queries. Queries Q1-4 represents symbol queries, i.e. as input is a list of symbols. The other queries are document images.

Conclusion

The research undertaken represents a novel approach for indexing document images. Our approach uses data mining techniques for knowledge extraction. It aims at finding image parts that occur frequently in a given corpus. These frequent patterns are part of the document model and can be put in relation with the domain knowledge.

Using the proposed method we reduce in an unsupervised manner the semantic gap between a user representation for a document image and the indexation system representation.

The exposed method can be applied to other graph representations of a doc-ument. In the near future, we will apply this approach to layout structures of textual document images.

Another follow up activity is to quantify the way noise afects the connected components labelling, and the manner in which an incorrect number of clusters can afect the graph mining procedure. Based on this error propagation study we can further improve our method. Other possible improvements can be obtained if we would use a graph-based technique that can deal with error tolerant graph matching.

Fig. 3 .

 3 Fig. 3. Corpus images

  query: (c 1 , c 2 , . . . , c n ) , (s 1 , s 2 , . . . , s m ) query: (s 1 , s 2 , . . . , s m ) query: (c 1 , c 2 , . . . , c n ) After using the graph mining algorithm on the presented corpus we obtain 52 frequent subgraphs. This subgraphs are the symbols that will be used in queries, and are numbered from 1 to 52. The description of the first 4 documents (in terms of what symbols and what are their corresponding frequencies) is subsequently presented :

Fig. 4 .

 4 Fig. 4. Document representations presented in a two dimensional space with respect to their reciprocal dissimilarities

Table 1 .

 1 Data sets description

	T |T | number of clusters
	T 1
	24830	5
	T 2
	32882	15
	T 3
	37346	24

Table 2 .

 2 Proposed cluster numbers

	|S|

Table 3 .

 3 Classification results using the simple characteristics

	Features	number of correctly classification
		classified instances	rates
	only simple features		55
			91.67
	% only bag of symbol representation		57
			95 %
	simple features and
	bag of symbol		58 96.67
	%

  14 , 1)(s 16 , 3) d 1 : (s 17 , 2)(s 18 , 1)(s 19 , 4)(s 20 , 6)(s 21 , 1)(s 22 , 4)(s 23 , 2)(s 24 , 4)(s 25 , 2)(s 26 , 2) (s 35 , 1)(s 36 , 1)(s 37 , 1)(s 41 , 1)(s 45 , 1)(s 46 , 1)(s 49 , 1)(s 51 , 1)(s 52 , 1)

	(s 36 ,, 1) (s 37 1)(s 39 2)(s 40 2)(s 41 1)(s 42 1)(s 44 1)(s 46 1)(s 47 2)(s 48 2)(s 49 1)
	(s 51 , 2)(s 52 , 2)
	d 2 : (s 1 , 1)(s 2 , 3)(s 3 s3),(s 4 ,s2)(,s1),(2)(s,61)1)s(s 7 ,,1)((ss 16 ,,1) (s 19 , 1)(s 20 , 3)
	(s 22 , 1)	,	5	,	1) 48 2)
	(s 23 , 2)(s 25 , 2)( 39 1)( 42	s 43 ( 47
	d 3 : (s 1 , 1)(s 2 , 1)(s 3 s4),(s 4 ,s1)(,s5),(1)
	(s,81)1)s(s 11 1)1)s(s 12 1)1)s(s 13 1)1)s(s 16 1)1)(s 19 , 2)
		,			7 ,
					, ,
					, ,
	(s 20 , 4)(s 21 , 1)( 22 3)( 25	s 35 ( 39 , ( 47 , ( 48 , ( 52 ,

(s 1 , 4)(s 2 , 4)(s 3 , 3)(s 4 , 2)(s 5 , 2)(s 6 , 3)(s 7 , 1)(s 8 , 2)(s 9 , 2)(s 11 , 3)(s 12 , 1)(s 16 , 1) d 4 : (s 18 ,, 1)(s 19 ,, 4)(s 20 ,, 4)(s 21 ,, 2)(s 22 ,, 1)(s 23 ,, 3)(s 24 ,, 4)(s 25 ,, 2)(s 26 ,, 2)

Table 4 .

 4 Examples of queries and results , 1)(s 7 , 1)(s 16 , 2)(s 19 , 1)(s 20 , 3)1) d 22 dissimilarity=0.2136 (s 22 , 1) (s 23 , 2)(s 25 , 2)(s 39 , 1)(s 42 , d 26 dissimilarity=0.2241 (s 43 , 1)(s 47 , 1)(s 48 , 1) d 21 dissimilarity=0.2362

	query	answer to query
		d 37 dissimilarity=0.6782
		d 15 dissimilarity=0.7843 d 4
	(s 1 , 4)	dissimilarity=0.8070 d 13 dissimilarity=0.8450 d 27
		dissimilarity=0.8452
		d 2 dissimilarity=0.4233
		d 7 dissimilarity=0.4722 d 22
	(s 1 , 4)(s 2 , 4)(s 3 , 3)(s 4 , 2)	dissimilarity=0.4864 d 25 dissimilarity=0.5046 d 14
		dissimilarity=0.5054
	(s 1 , 1)(s 2 , 3)(s 3 , 3)(s 4 , 2)(s 5 , 2)	d 2 dissimilarity=0.0065 d 25 dissimilarity=0.1949
	d 2 : (s 6

Table 5 .

 5 Queries recall and precision

After labelling the connected components (nodes in the graph), we now de-scribe the way these nodes are linked. The edges can be labelled or not (if unla-beled, the significance is Boolean: we have or don't have a relation between two (a) Initial image (b) Connected components labelling (c) Graph construction (d) Graph transaction Fig. 1. An image and its associated graph transaction


Herve Locteau
email: herve.locteau@univ-rouen.fr

Romain Raveaux

Sebastien Adam

Yves Lecourtier

Pierre Heroux

Eric Trupin

Polygonal Approximation of Digital Curves Using a Multi-objective Genetic Algorithm

In this paper, a polygonal approximation approach based on a multiobjective genetic algorithm is proposed. In this method, the optimization/exploration algorithm locates breakpoints on the digital curve by minimizing simultaneously the number of breakpoints and the approximation error. Using such an approach, the algorithm proposes a set of solutions at its end. This set which is called the Pareto Front in the multi objective optimization field contains solutions that represent trade-offs between the two classical qual-ity criteria of polygonal approximation : the Integral Square Error (ISE) and the number of vertices. The user may choose his own solution according to its objective. The proposed approach is evaluated on curves issued from the literature and compared with many classical approaches.

Introduction

Polygonal approximation of digital planar curves is an important issue in pattern recognition and image processing. It is a classical way to represent, store and process digital curves. For example, its results are frequently used for shape recogni-tion. The problem can be stated as follows: Given a curve C consisting of N ordered points C = {C i ≡ (x i , y i )}N= 1 , the goal is to find a subset S of M ordered points i S = {S i ≡ (x i , y i )}M= 1 with M ≤ N and S ⊆ C . These points constitute the exi tremities of line segments so that the polygon constructed by directly connecting these line segments best fits the given digital curve. Figure 1, issued from [START_REF] Salotti | An efficient algorithm for the optimal polygonal approximation of digitized curves[END_REF], illustrates such a process for two different curves. Many paradigms have been proposed in the literature to solve the problem of polygonal approximation, what leads to a great number of published papers. Among these approaches, one can cite split or split and merge techniques [START_REF] Ramer | An iterative procedure for the polygonal approximation of plane curves[END_REF][3] [START_REF] Wall | A fast sequential method for polygonal approximation of digitized curves[END_REF], Hough transform [START_REF] Gupta | A new approach for aggregating edge points into line segments[END_REF], perceptual organization [START_REF] Hu | Polygonal approximation of digital curves based on the principles of perceptual organization[END_REF], domi-nant points detection [START_REF] Teh | On the detection of dominant points on digital curves[END_REF][8] [START_REF] Ray | An algorithm for detecting dominant points and polygonal approximation of digitized curves[END_REF] [10] [START_REF] Cornic | Another look at the dominant point detection of digitized curves[END_REF] [START_REF] Marji | A new algorithm for dominant points detection and polygonization of digital curves[END_REF], competitive Hopfield neural networks [START_REF] Chung | Polygonal approximation using a competitive Hopfield neural network[END_REF] or dynamic programming [START_REF] Perez | Optimum polygonal approximation of digitized curves[END_REF][1] [START_REF] Horng | An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves[END_REF]. Another paradigm has been recently pro-posed in [START_REF] Yin | A new method for polygonal approximation of digital curves[END_REF] [START_REF] Huang | Polygonal approximation using genetic algorithm[END_REF] [START_REF] Sarkar | Approximation of digital curves with line segments and circular arcs using genetic algorithms[END_REF]. It consists in using Genetic Algorithms in order to find a near-optimal polygonal approximation. In such an approach, as in dynamic programming methods, the polygonal approximation technique is considered as an optimization process and the algorithm automatically selects the best points of the polygon by minimizing a given criterion. Two kinds of configuration may be distinguished in the published papers. In the first case, the number of vertices to be obtained is fixed and the method uses the concept of genetic evolution to obtain a near-optimal polygon [START_REF] Yin | A new method for polygonal approximation of digital curves[END_REF] [START_REF] Huang | Polygonal approximation using genetic algorithm[END_REF]. In the second case, a maximal approximation error is fixed and the algo-rithm minimizes the number of vertices of the polygon [START_REF] Yin | A new method for polygonal approximation of digital curves[END_REF]. One can note that this kind of approach has also been used in order to approximate curves with circular arcs or ellipses [START_REF] Sarkar | Approximation of digital curves with line segments and circular arcs using genetic algorithms[END_REF] [START_REF] Yin | A new circle/ellipse detector using genetic algorithm[END_REF].

In this paper, we adopt the same paradigm and we propose a new algorithm for polygonal approximation using genetic algorithms. The originality of the described approach is the factorization of the two kinds of configuration mentioned above through the use of a multi-objective optimization process whereas existing approaches minimize an unique criterion as explained before. Such a new viewpoint enables the user of the system to choose a trade-off between different quality criteria, according to its objectives of use of the results (recognition, interpretation, storage...).

Fig. 1.

Results provided by a polygonal approximation [START_REF] Salotti | An efficient algorithm for the optimal polygonal approximation of digitized curves[END_REF]. On the top left, a curve composed of 992 points. On the top right, its polygonal approximation (15 line segments). At the bottom left, a free curve of 3222 points, on the right, its polygonal approximation (16 line segments).

The remainder of the paper is organized as follows. In section 2, an introduction to the multi-objective optimization problem is proposed and our algorithm is detailed. In section 3, the application of this algorithm to the polygonal approximation problem is shown. Section 4 presents the experimentally obtained results, a comparison with classical approaches and a discussion concerning the interests of such an approach. Section 5 summarizes the concluding remarks and proposes some perspectives for this work.

A Genetic Based Multi-objective Optimization Algorithm

When an optimisation problem involves more than one objective function (a very frequent context in the document analysis field -one can cite recognition rate/reject rate, precision rate/recall rate, compression / quality), the task of finding one or more optimum solutions is known as multi-objective optimization. Some classical text-books on this subject have been published, e.g. [START_REF] Deb | Multi-Objective optimization using Evolutionary algorithms[END_REF]. We just recall here some essen-tial notions in order to introduce the proposed algorithm. The main difference between single and multi-optimization task lies in the requirement of compromises between the various objectives in the multi-optimization case. Even with only two objectives, if they are conflicting, the improvement of one of them leads to a deterioration of the other one. For example, in the context of polygonal approximation, the decrease of the approximation error always leads to an increase of the vertices num-ber. Two main approaches are used to overcome this problem in the literature. The first one is to combine the different objectives in a single one (the simpler way being to use a linear combination of the various objectives), and then to use one of the well-known techniques of single objective optimization (like gradient based methods, simulated annealing or classical genetic algorithm). In such a case, the compromise between the objectives is a priori determined through the choice of the combination rule. The main critics addressed to this approach are the difficulty to choose a priori the compromise and the fact that some objective points can not be reached. It seems a better idea to postpone this choice after having several candidate solutions at hand. This is the goal of Pareto based method using the notion of dominance between can-didate solutions. A solution dominates another one if it is better for all the objectives. This dominance concept is illustrated on figure 2. On this example, two criteria J 1 and J 2 have to be minimized. The set of non-dominated points that constitutes the Pareto-Front appears as 'O' on the figure, while dominated solutions are drawn as 'X'.

Using such a dominance concept, the objective of the optimization algorithm be-comes to determine the Pareto front, that is to say the set of non-dominated points. Among the optimization methods that can be used for such a task, genetic algorithms are well-suited because they work on a population of candidate solutions. They have been extensively used in such a context, with many variants. The most common algo-rithms are VEGA -Vector Evaluated Genetic Algorithm - [START_REF] Schaffer | Multiobjective learning via genetic algorithms[END_REF], MOGA -Multi Objective Genetic Algorithm -approach [START_REF] Fonseca | Genetic algorithm for multi-objective optimization: formulation, discussion and generalization[END_REF], NSGA -Non-Dominated Sorting Ge-netic Algorithm - [START_REF] Srinivas | Multiobjective optimization using nondominated sorting in genetic algorithm[END_REF], NSGA II [START_REF] Deb | A fast and elitist multi-objective genetic algorithm: NSGA-II[END_REF], PAES -Pareto Archived Evolution Strategy - [START_REF] Knowles | Approximating the nondominated front using the Pareto archived evolution strategy[END_REF] and SPEA -Strength Pareto Evolutionary Algorithm - [START_REF] Zitzler | Multiobjective evolutionary algorithms : a comparative study and the strength pareto approach[END_REF]. The strategies used in these contributions are different, but the obtained results mainly vary from the convergence speed point of view. A good review of the existing approaches can be found in [START_REF] Coello | A short tutorial on Evolutionary Multiobjective Optimisation[END_REF].

J 2 X X X X J 1

Fig. 2. Illustration of the Pareto Front concept

The proposed genetic algorithm is elitist and steady-state. This means that (i) it man-ages two populations and (ii) the replacement strategy of individuals in the popula-tions is not made as a whole, but individual per individual. The two populations are a classical population, composed of evolving individuals and an "archive" population composed of the current Pareto Front approximation elements. These two populations are mixed during the genetic algorithm. The first population guarantees space explo-ration while the archive guarantees the exploitation of acquired knowledge and the convergence of the algorithm.

Based on such concepts, our optimization method uses the algorithm #1. In this section, we only describe the optimization algorithm, without applying it to the po-lygonal approximation problem. The particular application to the polygonal approxi-mation problem is described in the following section. This algorithm has been designed in order to be applied to various problems (see section 5). The design of a new application only consists in the choice of a coding scheme for individuals, in the design of the evaluation method and in the choice of the genetic parameters values.

While the maximal generation number has not been reached

In the current implementation of this algorithm, the coding of an individual is a classical bit set, the crossover is a well-known 2-point crossover, and the mutation is a simple transformation of a gene value by its complementary value. Concerning the replacement strategy, several choices can be made for the integration of a candidate individual in the archive. The simplest is a dominance test between the candidate and the archive elements. The candidate is inserted within the archive if no archive ele-ment dominates it. In the same time, archive elements dominated by the candidate are eliminated from the archive. A problem reported in the literature on evolutionary multiobjective optimization is the possible bad exploration of Pareto front: the ar-chive population elements concentrate on only some parts of the front. This difficulty is overcome in our approach by defining a minimal distance between two points in the objective space. This algorithm has been tested on classical multi-objective problems such as BNH, TNK or OSY [START_REF] Chafekar | Constrained Multi-objective Optimization Using Steady State Genetic Algorithms[END_REF] problems and the results have shown the quality of the proposed approach.

A Genetic Based Multi-objective Optimization Algorithm

In order to apply the algorithm presented above to the polygonal approximation prob-lem, an individual has to represent a possible solution to the polygonal approximation problem. That is why an individual is composed of N genes, where N is the number of points in the initial curve. A gene is set to '1' if the point is kept as a breakpoint, '0' if it is not. An example of an individual coding is given in figure 3. Each point C i of the curve S corresponds to a bit in the chromosome. In the example of figure 3, the individual is a binary string of 14 genes corresponding to the initial C 0. -C 13. . The example polygon is composed of 4 vertices whose extremities are C 0 , C 4 , C 7 and C 11 . Such a polygonal approximation corresponds to the individual "10001001000100".

Fig. 3. An example of the coding scheme applied on a simple curve

Concerning the computation of the criterion to be optimized, two objectives have been included in the current version. The first one is the Integral Square Error (ISE) and the second one is the vertices number. Such a choice enables to have a trade-off between the precision of the result and the number of line segments, thanks to ele-ments of the Pareto front. One can note that the use of a discrete objective (vertices number) guarantees itself the diversity on the Pareto front, we do not need to specify any minimal distance between any couples of solutions of the Pareto Front.

Experimental Results and Performance Analysis

In order to assess the performances of the proposed algorithm, it has been applied to the four digital curves presented in [START_REF] Teh | On the detection of dominant points on digital curves[END_REF]. Fig. 4a is a chromosome shaped curve with 60 points, Fig. 4b is a leaf-shaped curve with 120 points, Fig. 4d is a curve containing four semicircles with 102 points and Fig. 4c is a figure-eight curve with 45 points. These curves have been broadly used in the literature. Such tests allow to test the performances of the proposed algorithm versus those of published approaches. For each of these curves, the program has been run for 2000 generations, using a population size of 100 individuals. Such a parameter set involves about 8000 calls to the evaluation method (see the algorithm below). The mutation rate has been fixed to 0.05 and the crossover rate to 0.6. As said before, the output of the presented algo-rithm is not a single ISE for a number of vertices given a priori. It consists in the whole Pareto front of the optimization problem. That is why the result is a set of cou-ple (ISE -number of vertices). As an example, figure 5 shows the set of couple obtained at the end of one run on a "map of France" curve and the corresponding polygons. Another remark has to be done. Since GA are stochastic, results may be different at independent runs. That is why, in these experiments, we present the best and the worst ISE for each number of vertices obtained after 5 independent runs. Using such a strategy, obtained results are compared for each curve with the results proposed in the literature using the following scheme:

-A table containing the results obtained by several approaches from the literature on the given figure; -The results (comparable points on the Pareto Front) obtained by the proposed algorithm on the same curve compared with the best ISE found in the literature; -A figure representing the whole Pareto Front and showing a visual performance comparison between our results and the results issued from the state of the art. 7. Results obtained with several existing methods on the curve with 4 semi-circles Table 8. Results obtained using 5 runs of the described approach on the curve with 4 semicircles compared with best results found in the literature Fig. 9. Comparison between performances obtained using several approaches issued from the literature ( ); our best result (o) and our worst result (+) for 5 runs

Discussion

Many observation can be drawn from the results presented above. Concerning the obtained performances for a given number of vertices, one can see that the proposed approach provides results that are only outperformed by optimal methods [14] [START_REF] Horng | An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves[END_REF]. These results are logical since GA are known to be near-optimal. On the contrary, the non-optimal or suboptimal approaches are outperformed by the proposed algorithm.

Another advantage of our approach is the fact that no input parameters concerning the initial curve or the desired results have to be defined a priori. All the tests mentioned above have been led with exactly the same configuration of the program. The most important in this context is that our approach does not need the number of vertices to be obtained as an a priori parameter. Furthermore, the algorithm gives the user a bet-ter information on the solved problem as it proposes as output a set of solutions con-taining a wide range of values for the number of vertices and the corresponding ISE. The user of the system can choose the better solution regarding its application constraints, as shown in Fig. 4. Concerning the complexity, our algorithm has an important computational cost (comparable to Yin's one) but for a pool of solutions. Moreover, this computational cost may be reduced using a parallelization since ge-netic algorithms are parallel by nature.

Another solution to reduce this complexity is to consider an evolution of the genetic parameters (mutation and crossover rates) during the algorithm. This point is actually under consideration.

Conclusion and Future Works

In this paper, we have proposed a new approach for the polygonal approximation of curves. This approach considers the polygonal approximation as an optimization process. The fundamental difference with existing approaches lies in the fact that we use a multiobjective optimization process while other contributions only optimize a unique objective. One can see several interests in such an approach. As many solu-tions are proposed, the user may choose the optimal solution regarding its constraints. Another interest is that it is easy to add a new objective. For example, our current work concerns the maximization of the parallel line segments, in order to apply con-tour matching in a vectorization process. Another future work concerns the integra-tion of the detection of circular arcs in our approximation system, using an approach inspired from [START_REF] Sarkar | Approximation of digital curves with line segments and circular arcs using genetic algorithms[END_REF]. A more global objective is to generalize the principles of multi-objective optimization to the different steps constituting the chain of a document image analysis system. The aim is to build a multi-objective document analysis sys-tem which adapts its objective thanks to a dialog with the user.

Algorithm # 1 . 4 - 4 - 4 - 8 - 8 -

 144488 The multi objective algorithm in use Population Initialization Archive Initialization (selection of the non dominated element in the population) do -Random selection of two individuals I 1 and I 2 in the current population -Crossover between the selected individuals to generate I 3 and I Mutation applied to the generated children I 3 and I Evaluation of children I 3 and I Selection either of the dominant individual I 5 between mutated children (if it exists) or random selection of I 5 between I 3 and I 4 -Random selection of an individual in the archive population (I 6 ) -Crossover between I 5 and I 6 to generate children I 7 and I Evaluation of children I 7 and I Test for the integration of I 7 and I 8 in the archive -Test for the integration of I 7 and I 8 in the current population -Incrementation of the generation number

Fig. 4 .Fig. 5 .

 45 Fig. 4. Test curves: (a) chromosome-shaped curve: 60 points; (b) leaf-shaped curve: 120 points; (c) curve with four semi-circles: 102 points and (d) figure-of-eight curve: 45 points

Fig. 8 . 4 . 4

 844 Fig.8. Comparison between performances obtained using several approaches issued from the literature ( ); our best result (o) and our worst result (+) for 5 runs on the curve with 4 semicircles

Table 1 .

 1 Results obtained with several existing methods on the chromosome-shaped curve

Table 2 .

 2 Results obtained using 5 runs of the described approach on the chromosome-shaped curve compared with best results found in the literature

	Fig. 6. Comparison between performances obtained using several approaches issued from the
	literature ( ); our best result (o) and our worst result (+) for 5 runs on the chromosome-shaped
	curve

Results Obtained on the Leaf-Shaped CurveTable 3 .

 3 Results obtained with several existing methods on the leaf-shaped curve

Table 4 .

 4 Results obtained using 5 runs of the described approach on the leaf-shaped curve compared with best results found in the literature

	Fig. 7. Comparison between performances obtained using several approaches issued from the
	literature ( ); our best result (o) and our worst result (+) for 5 runs on the leaf-shaped curve

Results Obtained on the Curve with 4 Semi-circlesTable 5 .

 5 Results obtained with several existing methods on the curve with 4 semi-circles

Table 6 .

 6 Results obtained using 5 runs of the described approach on the curve with 4 semicircles compared with best results found in the literature


Eugen Barbu

Pierre Heroux

Sebastien Adam

Eric Trupin

Indexation of document images using frequent items

Documents exist in different formats. When we have document images, in order to access some part, preferably all, of the information contained in that images, we have to deploy a document image analysis application. Document images can be mostly textual or mostly graphical. If, for a user, a task is to retrieve document images, relevant to a query from a set, we must use indexing techniques. The documents and the query are translated in a common representation. Using a dissimilarity measure (between the query and the document representations) and a method to speed-up the search process we may find documents that are from the user point of view relevant to his query. The semantic gap between a document representation and the user implicit representation can lead to unsatisfactory results. If we want to access objects from document images that are relevant to the document semantic we must enter in a document understanding cycle. Understanding document images is made in systems that are (usually) domain dependent, and that are not applicable in general cases (textual and graphical document classes). In this paper we present a method to describe and then to index document images using frequently occurences of items. The intuition is that frequent items represents symbols in a certain domain and this document description can be related to the domain knowledge (in an unsupervised manner). The novelty of our method consists in using graph summaries as a description for document images. In our approach we use a bag (multiset) of graphs as description for document images. From the document images we extract a graph based representation. In these graphs, we apply graph mining techniques in order to find frequent and maximally subgraphs. For each document image we construct a bag with all frequent subgraphs found in the graph-based representation. This bag of "symbols" represents the description of the document.

Introduction

A document image analysis (DIA) system transforms a document image into a description of the set of objects that constitute the information on the document and which are in a format that can be further processed and interpreted by a computer [START_REF] Antonacopoulos | Introduction to Document Image Analysis[END_REF]. Documents can be classified in mostly graphical or mostly textual documents [START_REF] Nagy | Twenty years of document analysis in PAMI[END_REF]. The mostly textual documents also known as structured documents respect a certain layout and powerful relations exist between components. Examples of such documents are technical papers, simple text, newspapers, program, listing, forms,… Mostly graphical documents do not have strong layout restrictions but usually relations exist between different document parts. Examples of this type of documents are maps, electronic schemas, architectural plans … For this two categories of documents graph based representations can be used to describe the image content (e.g. region adjacency graph [START_REF] Pavlidis | Algorithms or Graphics and Image Processing[END_REF] for graphical and Voronoi-based neighborhood graph [START_REF] Bagdanov | Fine-grained Document Genre Classification Using First Order Random Graphs[END_REF] for textual document images). This paper presents an approach similar with the "bag of words" method from Information Retrieval (IR) field. We describe a document using a bag of symbols found automatically using graph mining [START_REF] Washio | State of the art of graph-based data mining[END_REF] techniques. In other words, we consider as "symbols" the frequent subgraphs of a graph-based document representation and we investigate if the description of a document as a bag of "symbols" can be profitably used in a indexation and retrieval task. The approach has the ability to process document images without knowledge of, or models for document content. Frequent items are used in clustering of textual documents [START_REF] Fung | Hierarchical Document Clustering Using Frequent Itemsets[END_REF], or in describing XML documents [START_REF] Termier | Mining XML Data with Frequent Trees[END_REF] , but we do not know any similar approch in the DIA field. This paper is one step from a plan that has as aim to study if the bag of symbols approach can be successfully used in document image supervised classification, indexation and clustering (see Fig. 1).

Figure 1. The " bag of symbols" applications on document images

The outline of this paper is as follows. In section 2 we present a graph representation and how we create this representation from a document image. Section 3 presents the graph-mining method used, in section 4 we describe how we search documents based on dissimilarities between bags of objects. Section 5 shows experimental results. We conclude the paper and outline perspectives in section 6.

Graph representation

Eight levels of representation for document images are proposed in [START_REF] Blostein | Document Representations[END_REF]. These levels are ordered in accordance with their aggregation relations. Data array, primitive, lexical, primitive region, functional region, page, document, and corpus level are the representation levels proposed.

Without loosing generality, in the following paragraphs we fix our attention on a graph-based representation build from the primitive level. The primitive level contains objects such as connected components (set of adjacent pixels with the same color) and relations between them. From a binary (black and white) document image we extract connected components. The connected components will represent the graph nodes. On each connected component we extract features. In the actual implementation the extracted characteristics are rotation and translation invariant features based on Zernike moments [START_REF] Khotazad | Invariant Image recognition by Zernike Moments[END_REF]. The invariants represents the magnitudes of a set of orthogonal complex moments of a normalized image.

Let I be an image and C(I) the connected components from I, if

) (I C c∈ , c is described as ) , ( P id c=
, where id is a unique identifier and P the set of pixels the component contains. Based on this set P, we can compute the center for the connected component bounding box and also we can associate a feature vector to it. Based on that, The following paragraph presents the clustering procedure used to associate each connected component a label.

n R v v y x id c ∈ = ), , , , ( . Subsequently

Labeling connected components

The two main categories of clustering methods are partitional and hierarchical. Partitional methods can deal with large sets of objects ("small" in this context means less than 300) but needs the expected number of clusters in input. Hierarchical methods can overcome the problem of number of clusters by using a stopping criterion [START_REF] Milligan | An Examination of Procedures for Determining the Number of Clusters in a Data Set[END_REF] but are not applicable on large sets due to their time and memory consumption.

In our case the number of connected components that are to be labeled can be larger than the limit of applicability for hierarchical clustering methods. In the same time we cannot use a partitional method because we do not know the expected number of clusters. Based on the hypothesis that a "small" sample can be informative for the geometry of data, we obtain in a first step an estimation for the number of clusters in data. This estimation is made using an ascendant clustering algorithm with a stopping criterion. The number of clusters found in the sample is used as input for a partitional clustering algorithm applied on all data.

We tested this "number of cluster estimation" approach using a hierarchical ascendant clustering algorithm [START_REF] Gordon | Classification 2ndEdition[END_REF] that employes Euclidean distance to compute the dissimilarity matrix, complete-linkage to compute between-clusters distances, and Calinsky-Harabasz index [START_REF] Milligan | An Examination of Procedures for Determining the Number of Clusters in a Data Set[END_REF] as a stopping criterion. The datasets ( Considering S the sample extracted at random from a test set, in Table 2 we present predicted cluster numbers obtained for different sample sizes. After repeating the sampling procedure for 10 times if the test set is for example |S|=50, we obtain a set of estimations for the number of clusters. We can see that by using a majority voting decision rule we can find the good number of clusters in most of the cases and even when the sample size is very small (50 or 100) compared to the data set size.

We employed our sampling approach combined with the k-medoids clustering algorithm [START_REF] Kaufmann | Clustering by means of medoids[END_REF] on the connected components data set from images in our corpus (see section 5). The k-medoids clustering algorithm is a more robust version of the well known k-means algorithm. The images from our corpus contain 6730 connected components. The proposed number of clusters using ten samples of size 600 is [START_REF] Dumais | Improving the retrieval information from external resources[END_REF][START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF]17,[START_REF] Dumais | Improving the retrieval information from external resources[END_REF][START_REF] Dumais | Improving the retrieval information from external resources[END_REF]19,[START_REF] Termier | Mining XML Data with Frequent Trees[END_REF]17,[START_REF] Seno | A Pattern Finding Toolkit[END_REF][START_REF] Dumais | Improving the retrieval information from external resources[END_REF] and by considering the majority we use 16 clusters as input to the partitional clustering algorithm.

After labeling the connected components (nodes in the graph) subsequently we describe the way we add edges to the graph. The edges can be labeled or not (if unlabeled the significance is Boolean: we have or have not a relation between two connected components) and can be relations of spatial proximity, based on "f orces" [START_REF] Tabbone | Mat ching of graphical symbols in line-drawing images using angular signature information[END_REF], orientation or another criterion.In our actual implementation the distance between centers of connected components is used (see Fig. 2). If the distance between two connected components centers is smaller than a threshold, then an edge will link the two components (nodes).

Graph mining

"The main objective of graph mining is to provide new principles and efficient algorithms to mine topological substructures embedded in graph data" [START_REF] Washio | State of the art of graph-based data mining[END_REF].

Mining frequent patterns in a set of transaction graphs is the problem of finding in this set of graphs those subgraphs that occur more times in the transactions than a threshold (minimum support). Because the number of patterns can be exponential this problem complexity can also be exponential. An approach to solve this problem is to start with finding all frequent patterns with one element, then all patterns with two elements, etc in a level-by-level setting . In order to reduce the complexity different constraints are used: the minimum support, the subgraphs are connected, and not overlapped.

The first systems emerged from this field are SUBDUE and GBI [START_REF] Washio | State of the art of graph-based data mining[END_REF]. These approaches use greedy techniques and hence can overlook some patterns. The SUBDUE system search subgraphs in a single graph using a minimum description length-based criterion. Complete search for frequent subgraphs is made in an ILP framework by WARMR [START_REF] Washio | State of the art of graph-based data mining[END_REF]. An important advance is the introduction of the concept of closed subgraph. A graph is said to be closed or maximal if it does not have a super-graph with the same number of apparitions in the dataset [START_REF] Yan | Closegraph: mining closed frequent graph patterns[END_REF]. The graphmining systems were applied to scene analysis, chemical components databases and workflows. A system that is used to find frequent patterns in graphs is FSG (Frequent Subgraph Discovery) that "finds patterns corresponding to connected undirected subgraphs in an undirected graph database" [START_REF] Seno | A Pattern Finding Toolkit[END_REF]. In our document image analysis context we are interested in finding maximal frequent subgraphs because we want to find symbols but to ignore their parts.

The input for the FSG program is a list of graphs. Each graph represents a transaction. We present subsequently how we construct the transactions list starting from a set of document images. Using the procedure presented in section 2 we create for each document an undirected labeled graph. Every connected component of this graph represents a transaction. We can further simplify the graphs by removing vertices that cannot be frequent and their adjacent edges. Using FSG we extract the frequent subgraphs and we construct a bag of graphs occurring in each document. In the following paragraphs we consider that the frequency condition is sufficient for a group of connected components to form a symbol and we will conventionally make an equivalence between the frequent subgraphs found and symbols. As we can see in the example (Fig. 2) the proposed symbols are far from being perfect due to the image noise, connected components clustering procedure imperfections, … however we can notice the correlation between this artificial symbol and the domain symbols. In conclusion, the subgraphs proposed as frequent are used to model a document as a bag of symbols. Because some documents may not contain any symbols the document representation is based on two vectors containing connected components labels, and symbols labels.

(

)( ) . ... , ... , ,..., , , ,..., , :

2 1 2 1 2 1 2 1 m n j j j i i i j j j i i i s s s c c c A m n ≤ ≤ ≤ ≤

Dissimilarity between document descriptions

In this paragraph we present the dissimilarity measure employed between the documents descriptions that we used.

A collection of documents is represented by a symbol-by-document matrix A, where each entry represents the occurrences of a symbol in a document image, A= ) ( ik a , where ik a is the weight of symbol i in document k. Let ik f be the frequency of symbol i in document k, N the number of documents in the collection, and i n the total number of times symbol i occurs in the whole collection. In this setting conform with [START_REF] Dumais | Improving the retrieval information from external resources[END_REF] one of the most effective weighting scheme is entropyweighting. The weight for symbol i in document k is given by :

) ) log( ) log(

Experiments

The corpus used for evaluation contains 60 images from 3 categories: electronic (25 images) and architectural schemas (5 images) and engineering maps (30 images) (see Fig. 5). In order to present a corpus summary we employed a multidimensional scaling algorithm to represent in a two dimensional plot the dissimilarities between documents (see Fig. 4). Each document image is described with one of the following types of features : Zernike moments for the whole image (a vector with 16 components) or the connected components and symbols lists described above. In Fig. 4.a) we present the dissimilarities between images represented by Zernike moments. In Fig. 4.b) are plotted the dissimilarities between the document images computed using the cosine correlation presented in section 4. Each image from the corpus has an id from 1 to 60. The engineering maps have identifiers from 1 to 30, electronic images from 31 to 55, and the arhitectural schemas from 56 to 60. We can see in Fig. 6 that the bag of symbols representation separate better the image classes. This fact has an important influence on the quality of the query results.

≤ ≤

In order to extract the formal description of a given query image we label the connected components of the query image, construct the graph, and employ graph matching to detect which symbols occur in the query image. At the end of this process the query image is described by the two lists of connected components and symbols. In order to evaluate experimental results we used precision and recall measures. If A is the set of relevant images for a given query, and B is the set of retrieved images then :

B B A precision ∩ = , A B A recall ∩ =

Conclusions

The research undertaken represents a novel approach for indexing document images. The approach uses data mining techniques for knowledge extraction. It aims at finding image parts that occurs frequently in a given corpus. These frequent patterns are part of the document model and can be put in relation with the domain knowledge.

Using the proposed method we reduce in an unsupervized manner the semantic gap between a user representation for a document image and the indexation system representation.

The exposed method can be applied to other graph representations of a document. In the near future, we will apply this approach to layout structures of textual document images.

Another follow up activity is to quantify the way noise affects the connected components labeling, and the manner in which an incorrect number of clusters can affect the graph mining procedure. Based on this error propagation study we can ameliorate our method. Other possible improvements can be obtained if we would employ a graph-based technique that can deal with error tolerant graph matching.

.

  using a clustering procedure on the feature vectors we can label the connected component and reach the description l is a nominal label . The graph G(I) representing the image is Vertices V(I) correspond to connected components and are labeled with component labels. An edge between vertex u and vertex w exists iff t is a threshold that depends on the image I global characteristics (size, number of connected components,…).

Figure 2 .

 2 Figure 2. An image (width=123, height=96) and associated graph transaction

Figure 3 .

 3 Figure 3. Frequent subgraph and its occurences in an image

  measure based on the cosine correlation.

Figure 4 .

 4 Figure 4. Documents ids presented in a two dimensional space with respect to their reciprocal dissimilarities

Figure 5 .

 5 Figure 5. Corpus images This corpus contains images that are scanned and contain real and artificial noise.

Table 1 .

 1 Data sets description

	1 T	3 , T 2 , T	) (see

Table 2 .

 2 Proposed number of clusters

	T \ |S|	50	100	300		500	600	700
	T1	[6, 8, 7, 6, 5, 6, 6, 6, 5, 5]	[5, 7, 9, 7, 5, 5, 7, 5, 5, 7]	[7, 5, 7, 8, 7, 5, 5, 5, 7, 7]	[8, 7, 5, 5, 5, 5, 5, 5, 5, 5]	[5, 5, 5, 5, 5, 7, 7, 7, 7, 5]	[5, 5, 7, 5, 7, 5, 5, 7, 5, 5]
		6	5	7		5	5	5
	T2	[9, 15, 15, 14, 13, 15,	[15, 15, 13, 15, 15, 15,	[15, 15, 15, 15, 15, 15,	[15, 15, 15, 15, 15, 15,	[15, 15, 15, 15, 15, 15,	[15, 15, 15, 15, 15, 15,
		13, 13, 14,	15, 15, 15,	15, 15, 15,	15, 15, 15,	15, 15, 15,	15, 15, 14,
		15]	15]	14]		15]	15]	15]
		15	15	15		15	15	15
	T3	[11, 7, 9, 18, 7, 7, 6, 4,	[6, 14, 23, 21, 7, 17,	[22, 24, 23, 19, 23, 24,	[21, 25, 25, 24, 22, 24,	[20, 25, 21, 24, 19, 23,	[23, 20, 21, 20, 25, 24,
		14, 8]	23, 16, 12,	24,	21,	23, 24, 24,	24, 25, 24,	24, 21, 25,
			11]	21,24,] 24]	24]	22]	24]
		7	23	24		24	24	24

Table 3 .

 3 Queries recall and precisionQueries Q1-4 represents symbol queries , i.e. as input is a list of symbols. The other queries are document images.

		Q1	Q2	Q3	Q4	Q5	Q6	Q7	Q8	Q9	Q10
	recall	0.75 0.5	0.48 0.55 0.56 0.76 0.6	0.4	0.32 0.16
	precision 0.6	0.31 0.8	0.73 0.87 0.95 0.88 0.5	0.42 0.4