Hubert Cecotti
email: cecotti@loria.fr

Abdel Belaïd
email: abelaid@loria.fr

Hierarchical Behavior Knowledge Space

In this paper we present a new method for fusing classifiers output for problems with a number of classes M > 2. We extend the well-known Behavior Knowledge Space method with a hierarchical approach of the different cells. We propose to add the ranking information of the classifiers output for the combination. Each cell can be divided into new sub-spaces in order to solve ambiguities. We show that this method allows a better control of the rejection, without using new classifiers for the empty cells. This method has been applied on a set of classifiers created by bagging. It has been successfully tested on handwritten character recognition allowing better-detailed results. The technique has been compared with other classical combination methods.

Introduction

In any recognition system, an optimal reliability is one of the main requirements. In order to obtain such high reliability, the system must be able to consider the rejection. We distinguish three main ways to build a system able to reject:

-A single classifier, which also considered a rejection class (trained with junk patterns for example). -A single classifier, which does not consider a rejection class, but uses some rejection rules for rejecting or not the results. -A multi-classifiers system (MCS), where the rejection is processed by the module that fuses each classifier output.

Among these solutions, we consider in this paper the third solution for several reasons. We consider that for a high reliability several classifiers must take part into the recognition, to have several points of view of the problem. In this work, we will consider a specific MCS type: MCS with a parallel topology. In this case, the outputs of each classifier are combined thanks to a fusing module [?,?]. Usually, classifiers are combined by voting methods, belief functions, statistical techniques or Dempster-Shafer evidence theory. We distinguish several types of fusing rules:

-Fixed rules: majority voting, Borda count method... These rules are usually simple, fast and they are well-suite for classifiers ensembles that have similar performances and low correlated errors.

-Trained rules: Bayesian, behavior knowledge space, neural network,... These rules are potentially better than the fixed rules as they use knowledge about how to combine. These rules allow taking more into account the complementarities between classifiers.

This paper will focus on the behavior knowledge space method and its potential issues [?,?]. We will show that it is possible to improve this method by adding information about the ranking output of each classifier. Accordingly, in the first part, the initial fusing rule using the behavior knowledge space will be defined. Then the hierarchical behavior knowledge space is described in the second section. The third section will present the different classifiers. Finally, we exhibit the improvement given by the method with several experiments.

Behavior Knowledge Space

We consider a problem with M classes:

C i , 1 ≤ i ≤ M and D classifiers: e i , 1 ≤ i ≤ D.
For applying the Bayes rule, classifiers must be independent. Each classifier must act separately in a total independent way. This condition cannot be always verified. The method using the history of the classifiers behavior allows getting free from this condition. The BKS (Behavior-Knowledge Space) method allows to determine a belief degree of a proposition x ∈ C i based on the combination of the first best answer of each classifier e k = j k , k ∈ {1, . . . , D} : bel(C i ) =

P (e 1 (x) = j 1 , . . . , e D (x) = j D , x ∈ C i ) P (e 1 (x) = j 1 , . . . , e D (x) = j D )

This equation corresponds to the degree of belief definition by a Bayesian approach. It can be represented in a behavior knowledge space (BKS) [?]. This space represents the behavior for all the possible combinations in the training database. The BKS is a D dimensional space where each dimension represents the decision of a classifier. Each classifier has M + 1 possible outputs (M classes and 1 rejection class). The intersection of the decision of each classifier corresponds to a cell of the BKS. This method will estimate M D posterior probabilities.

Each cell of the space is noted by BKS(j 1 , j 2 , . . . , j D ) with j i ∈ {1, . . . , M + 1} ∀i ∈ {1, . . . , D}. Each cell of the BKS is defined by 3 features:

n(j 1 , . . . , j D )(i): the total number of samples x such that e 1 (x) = j 1 , . . . , e D (x) = j D and x ∈ C i i ∈ {1, . . . , M }. -S(j 1 , . . . , j D ): the total number of samples x such that e 1 (x) = j 1 , . . . , e D (x) = j D and

S(j 1 , . . . , j D ) = M i=1
(n(j1, . . . , jD)(i)) S(j 1 , . . . , j D ) corresponds to the total sum of the samples that have as combination result the configuration j1, . . . , jD.

-B j1,...,jD is the best representative class of the cell j 1 , . . . , j D of the BKS then:

n(j 1 , . . . , j D )(B(j 1 , . . . , j D )) = max i (n(j 1 , . . . , j D )(i)) B(j 1 , . . . , j D ) = Argmax i (n(j 1 , . . . , j D )(i))
with i ∈ {1, . . . , M }.

In an implementation view, the BKS space can be represented by a space BKS of dimension D + 1, where D dimensions correspond to the classifiers outputs and the last dimension represents the final optimal result of the combination. The BKS is a space where all the extracted results are represented. In this case, each cell of BKS (j 1 , . . . , j D+1 ) is a natural positive number such that:

BKS (j 1 , . . . , j D+1 ) = n(j 1 , . . . , j D )(j D+1 )
The degree of belief that a sample x belongs to the class

C i denoted by bel(C i ) i ∈ {1, . . . , M } is defined by: bel(C i ) = P (e 1 (x) = j 1 , . . . , e D (x) = j D , x ∈ C i ) P (e 1 (x) = j 1 , . . . , e D (x) = j D ) = BKS (j 1 , . . . , j D , i) M k=1 BKS (j 1 , . . . , j D , k) = n(j 1 , . . . , j D )(i) S(j 1 , . . . , j D )
Finally, the combination E of the classifiers will give to the input x the following class:

E(x) =    R(j 1 , . . . , j D ) if (S(j 1 , . . . , j D ) > 0) and (bel(C R j1,...,jD ) ≥ α) M + 1 else
where α is a rejection threshold; 0 ≤ α ≤ 1.

During the test phase, it is possible to access to an empty cell. In this case, it means that the classifiers output combination has been never seen during the creation of the space. The input x is rejected.

In a statistical point of view, the BKS method tries to estimate the probability distribution of the classifiers outputs thanks to the frequencies of its occurrences. Although the BKS does not require a special dependency between each classifier, several observations can be made for this method.

Possible improvements

The BKS method suffers of several defaults [?]:

-The size of the database is one issue. In order to estimate the distribution of each classifier output, a large database is needed for representing all the possible combinations. However, this observation is mostly valid for weak classifiers that cannot offer a good recognition. For strong classifiers, all the non-empty cells are expected to stay close to the diagonal of the behavior space. Weak classifiers may lead to a better generalization thanks to their cover of the input space, but they will require much more samples to fill the space. Because of the statistical nature of the BKS, the quality of the database is very important for obtaining a good generalization. -The confusion of BKS cells where the representative class R has a very low probability. If such cell exists, the result remains ambiguous. Although this cell will propose the best solution, many patterns will obtain a bad class.

For the training database, in each cell, S(j 1 , . . . , j D )-max i (n(j 1 , . . . , j D )(i)) samples, with i ∈ {1, . . . , M }, will not be recognized correctly. In order to solve this problem, it is possible to add a new classifier specialized for dealing with the confusion problem involved by the ambiguous cell. Instead of using such process, we propose to extract more knowledge contained in the classifiers outputs: the ranking.

In the BKS method, only the first result of each classifier is considered during the combination. The confidence value and the ranking of the different classes are unfortunately not considered. We propose to use more information in order to improve the description of the ideal combination.

Hierarchical Behavior Knowledge Space

The Hierarchical Behavior Knowledge Space is based on the hypothesis that the ranking of the different classes for each classifier may bring relevant information for improving the quality of the combination. During the creation of the behavior space, the only information is the first best answer. The addition to new information to the space will lead to the creation of new cells. The HBKS is strongly equivalent to the BKS space for 2 classes. Indeed, for a two classes problem, with C 0 and C 1 , we have P (C 0 ) = 1 -P (C 1 ). Thus there is no information in the second best answer as it is dependent of the first. For taking advantage of the cell splitting, we must have M > 2. The new space becomes a tree of sub-space. The root of space is defined by the initial BKS. For each cell j 1 , . . . , j D if bel(C R j1,...,jD ) ≥ α then the cell is split into (M -i + 1) D cells where i is the actual rank of the cell. Each cell of the space is noted by HBKS((j 1,1 , . . . , j 1,k ), . . . , (j D,1 , . . . , j D,k )) with j i,k ∈ {1, . . . , M + 1} ∀(i, k) ∈ ({1, . . . , D} × {1, . . . , M -1}). k is the rank of the output.

For the following definition, we note by J the cell (j 1,1 , . . . , j 1,k ), . . . , (j D,1 , . . . , j D,k ) Each cell of the HBKS is defined by 3 features:

n (J)(i): the total number of samples x such that the best answer of e d (x) is j d,1 , the k th best answer of e d (x) is j d,1 with d ∈ {1, . . . , D} and x ∈ C i i ∈ {1, . . . , M }. We note e d,k (x) the k th best answer of e d (x). -S (J): the total number of samples x such that e d,1 (x) is j d,1 and e d,k (x) is j d,k .

S (J) = M i=1
(n (J)(i))

S (J) corresponds to the total sum of the samples that have as outputs the configuration J. -B (J) is the best representative class of the cell J of the HBKS then:

n (J)(B (J)) = max (i∈{1,...,M }) (n (J)(i)) B (J) = Argmax (i∈{1,...,M }) (n (J)(i))
The creation of such sub-spaces can denoise the initial cells and discover evidence of confusion between classes. For example, the rejection of a cell can be due to the noise of the different outputs. It is the case where always the same 2 classes are confused and the combination can solve the ambiguity. If a couple of classes is confused, which have never happened, the creation of sub-spaces in the BKS may solve this problem.

E(x) =    R (j 1 , . . . , j D ) if (S (j 1 , . . . , j D ) > 0)
and (bel(C R j1,...,jD ) ≥ α) Split the cell else bel(C i ) =

P (e 1 (x) = j 1,1 , . . . , e D (x) = j D , x ∈ C i ) P (e 1 (x) = j 1 , e 2 (x) = j 2 , . . . , e D (x) = j D ) = BKS (j 1 , . . . , j D , i)

M k=1 BKS (j 1 , . . . , j D , k) = n(j 1 , . . . , j D )(i) S(j 1 , . . . , j D )
The number of cells of the HBKS is defined by:

M D + M -1 k=1 l k ((M -k) D )
where l k is the number of new sub-spaces at the step k or the number of ambiguous cells at the step k -1.

The maximum number of cells of the HBKS is defined by:

M D + M -1 k=1 (M -k + 1) D * (M -k) D -(M -k + 1) D
When a sub-space is created for a cell, the sub-space replaces its corresponding cell.

The creation of the HBKS can be built this way: k ← 1 Fill the HBKS with the training database While (∃J|((S (J) > 0) and (bel

(C R (J) ) ≤ α)) { For all J|((S (J) > 0) and (bel(C R (J) ) ≤ α))
Create a sub-space for the cell J Fill the new HBKS sub-spaces with the training database

k ← k + 1 }
The table ?? presents an example for a problem with 2 classifiers and 3 classes (A,B and C). Each cell of the table represents n(j 1 , . . . , j D )(i). In the BKS cell AB, there is an ambiguity between the answers A and B. In the classical BKS, this cell could have been considered as being too ambiguous. The table ?? shows the subspace involved by the split of the cell AB. In these new cells, some cells remain ambiguous (c1,c4) but for some others the problem may be solved (c2,c3).

Classifiers

In this section, the different classifiers used for the combination are described. They are based on the same architecture: a convolutional neural network. This type of classifier has been already successfully used on handwritten digits recognition and word recognition [?].

Convolutional Neural Network

The neural network used is composed of 5 layers, it is based on the topology given in [?]:

- √ N share where N share represents the number of neurons that share the same set of weights.

Creation of the classifiers

Each classifier is built on the same architecture, described previously. D classifiers are created, each classifier being trained on a different versions of the initial database. For creating the ensemble of classifiers, we did use the bagging technique [?]. This method is based on obtaining different training sets of equal size as the original one, by using the statistical bootstrap method.

Experiments

Database description

The system has been tested on the MNIST handwritten digits database [?]. This database contains separated handwritten digit images of 28 * 28 in gray level. The learning set contains 60000 images and the test set contains 10000 images. In the learning set, 50000 images are used for real learning; 10000 images are used to find the best parameters. For the experiments, 3 classifiers have been created. Each one is trained with 33151 images.

Results

The results obtained on each classifier are presented in the table ??. We present the best result on the test database and the results obtained with the same network on the training database. For a single classifier or MCS, the results are defined by a triplet τ r /τ s /τ q where τ r , τ s and τ q are the recognition rate, the error rate and the rejection rate respectively.

The results obtained on the whole training database and test database are presented in the table ??. For each classifier, the correspond to the network that gives the best result on the validation database. Although these classifiers do not offer the best results on this database function to the state-of-theart [?,?], they still provide all a high accuracy. The table ?? illustrates the results on the test database for the different tops. The good result is almost always in the first three best answers, which justifies the choice of our approach for the problem. The results of these combinations on the test database are shown in the table ??. The Borda Count method, which uses rank-level information, gives one of the best results. It is again a proof for considering the ranking during the combination for our problem.

  The first one corresponds to the input image. The image is normalized by its center and reduced to a size of 29*29 [?]. -The next two layers corresponds to the information extraction, performed by convolutions. The second layer is composed of 10 maps, each one corresponds to a specific image transformation by convolution and sub-sampling reducing its size. The third layer is composed of 50 maps. For these 2 layers, the activation function is f (σ) = 1.7159 * tanh((2.0/3.0) * σ) [?] -The last two layers are fully connected. For these 2 layers, the activation function is f (σ) = 1/(1 + exp(-σ)). -The last one corresponds to the output: 10 neurons, for the number of classes. For a neuron n, weights are initialized with values w such that |w| ≤ 1/ N input where N input represents the number of inputs to the neuron n. During the back propagation, shared weights are corrected by the factor 2/

The 3

 3 classifiers have been combined with classical fixed rules: -The Majority Voting; 2 classifiers must agree to accept the answer. -The Oracle illustrates the result of an optimal output selection. -The Maximum rule. -The combination by outputs sums. -The combination by outputs products. -The Borda Count method, which takes into account the outputs ranking [?,?].

Table 1 .

 1 Example of some cells in a BKS.

	top 1 AA AB AC BA BB BC CA CB CC
	A 90 50 80 40 9 30 20 0 0
	B	5 51 12 60 80 30 20 30 0
	C	5 0 8 0 11 40 60 70 100

Table 2 .

 2 Example for a subspace in a HBKS.

	cell c1 c2 c3 c4
	top 1 AB AB AB AB
	top 2 BA BC CA CA
	A 21 20 5 1
	B 20 2 20 2
	C	0 4 3 2

Table 3 .

 3 Results. Training Test C1 99.28 / 0.72 / 0 98.51 / 1.49 / 0 C2 99.32 / 0.68 / 0 98.56 / 1.44 / 0 C3 99.27 / 0.73 / 0 98.61 / 1.39 / 0

Table 4 .

 4 Recognition rate. Top 1 Top 2 Top 3 Top 4 Top 5 Top 6 C1 98.51 99.63 99.83 99.92 99.99 100 C2 98.56 99.63 99.90 99.94 99.97 99.98 C3 98.61 99.58 99.89 99.96 99.97 99.99

For the learning database, we did observe that the HBKS is an optimal combination: each sub-spaces lead to the good answer. It may lead to the creation of a sub-space one pattern in the space. Such sub-spaces have however no generalization power. The table ?? presents for different thresholds the results with the BKS and HBKS methods. For the HBKS, we give the number of sub-spaces and non-empty cells. The sub-spaces results describe the special effect of the HBKS. These results are defined by a triplet (ξ r , ξ s , ξ q ) where ξ r , ξ s and ξ q are the number of well recognized patterns, errors and rejected patterns respectively. For a low threshold (0.4), the HBKS has no effect compared to the BKS. When the threshold is higher, the number of processed patterns by the HBKS is higher. Although the addition of information may be risky, we show that information can be added by the sub-spaces while keeping a good reliability.

Conclusion

In this paper, a new fusing method has been presented for multi-classifiers systems with a parallel topology for problems of M classes (M > 2). It corresponds to an improvement of the existing BKS method by adding knowledge about the rank of the results. Function to a fixed confidence threshold value, each cell is divided into sub-spaces in order to solve ambiguities. We have shown that the proposed method can allow an optimal rejection control for the training database. It also provides new information for some ambiguous cells, without using new classifiers for the empty cells. For an optimal use of this method classifiers must provide ranking results, which have a real sense. Further works would deal with the optimal use of the HBKS method and the threshold selection for getting the best generalization.


A Belaïd

T Moinel

Y Rangoni

Improved CHAID Algorithm for Document Structure Modelling

Keywords: Document Image Analysis and Recognition, Physical and logical layout analysis, OCR, Improved CHAID Algorithm, XML based formats

This paper proposes a technique for the logical labelling of document images. It makes use of a decision-tree based approach to learn and then recognise the logical elements of a page. A state-of-the-art OCR gives the physical features needed by the system. Each block of text is extracted during the layout analysis and raw physical features are collected and stored in the ALTO format. The data-mining method employed here is the "Improved CHi-squared Automatic Interaction Detection" (I-CHAID). The contribution of this work is the insertion of logical rules extracted from the logical layout knowledge to support the decision tree. Two setups have been tested; the first uses one tree per logical element, the second one uses a single tree for all the logical elements we want to recognise. The main system, implemented in Java, coordinates the third-party tools (Omnipage for the OCR part, and SIPINA for the I-CHAID algorithm) using XML and XSL transforms. It was tested on around 1000 documents belonging to the ICPR'04 and ICPR'08 conference proceedings, representing about 16,000 blocks. The final error rate for determining the logical labels (among 9 different ones) is less than 6%.

INTRODUCTION

Reverse engineering is becoming a common tool for document structure recognition of raw images capable of reaching good recognition results. [START_REF] Nagy | Twenty Years of Document Image Analysis in PAMI[END_REF] This task involves an implicit document structure modelling, whose construction is made difficult due to the complexity of the mapping between physical and logical structures. Both structures are rarely unique, and in most of the cases, there is no unambiguous mapping between them. Some works proposed automatic procedures for modelling [START_REF] Akindele | Construction of Generic Models of Document Structures using Inference of Tree Grammars International Conference on Document Analysis and Recognition[END_REF][START_REF] Bapst | Reconnaissance de documents assistée : architecture logicielle et intégration de savoir-faire[END_REF] or formats as DAFS 6 have been developed for this purpose, but, it seems that none of them have been generally adopted, indicating that they may not be extensible and general enough to comply with the requirements.

In this paper, we assume that the physical layout analysis is performed by a state-of-the-art OCR, and we propose a generic data-mining approach to tackle the problem of the logical structure recognition. The kernel of the system relies on a decision tree: the "Improved CHi-squared Automatic Interaction Detection" (I-CHAID) algorithm. It uses results of the OCR converted in ALTO format to create a model of the physical layout. On top of the syntactic rules generated from the document description, we add structural and logical rules to support the original tree for finding the final logical structure of the document.

IMPROVED CHAID ALGORITHM

The Improved CHAID Algorithm, [START_REF] Kass | An exploratory technique for investigating large quantities of categorical data[END_REF] is based on data discrimination by trees. Decision tree is one common method used in data mining to extract predicted information. The pioneers of this work were Morgan and Sonquist. 11 They used the regression trees in a prediction and explanation process: AID (Automatic Interaction Detection). Several discrimination and classification methods followed, based on the same representation paradigm by trees: THAID (Theta AID) and CHAID (CHi-squared Automatic Interaction Detection). [START_REF] Kass | An exploratory technique for investigating large quantities of categorical data[END_REF] In machine learning, most of the techniques are based on information theory. The first method was ID3 proposed by Quinlan (Induction of decision tree). [START_REF] Quinlan | Discovering rules by induction from large collections of examples[END_REF] Many heuristics were proposed in Nineteenth Century to improve the behaviour of the Quinlan's system, leading to the famous C4.5 method. This mobility emerged the concept of lattice graphs [START_REF] Terrenoire | Un modèle mathématique de processus d'interrogation: les pseudoquestionnaires[END_REF] which was popularised by the induction graphs of the SIPINA method. [START_REF] Chauchat | Targeting customer groups using gain and cost matrix: a marketing application[END_REF] In his SIPINA software, Rokotamalala exposes the principle of the decision tree construction for classification and discrimination problems. The problem is to predict the output value (or the class) of an object from a set of variables, discretes or continuous. It is a question of finding a partitioning of the individuals that we can represent by a decision tree. The objective is to produce individual groups, the most homogeneous as possible from the point of view of the variable to be predicted. The idea is to represent the empirical distribution of the attribute to be predicted by each node of the tree. Thus, the tree build favours the more "discriminating" attributes.

Here, the difficulty is to choose among N attributes characterising the structure elements that made it possible to have the best discrimination rate. There is a great number of information or statistical criteria, the most used is the entropy of Shannon and its alternatives. Another way of characterising the segmentation is to measure the causality between the variable candidate and the variable to be predicted.

For the process comprehension, it should be noted that a segmentation makes it possible to define a contingency table crossing the variable to be predicted and the descriptor candidate. In the following, we will adopt the notations to describe the numbers resulting from the crossing of the attribute class with K modalities and a descriptor with L methods. To evaluate the relevance of a variable in the segmentation, CHAID proposes the independence deviation χ 2 defined by Eqn. 1.

χ 2 = Σ K k=1 Σ L l=1 (n kl -n k ×n l n ) 2 n k ×n l n (1)
The values of χ 2 are not bounded, they are in the range [0, +∞[. The main drawback is the high emphasis of the descriptors having a high number of modalities. To reduce this negative impact, it is much more suitable to normalise by the number of freedom degrees. The formula T of Tschuprow (Eqn. 2) has values now in a range [0, 1]. This new equation gives the Improved CHAID algorithm.

T = χ 2 n √ (K -1) × (L -1) (2)
.

The I-CHAID used in this paper has the following parameters:

• "P-level" for splitting nodes: The computed p-value of the χ 2 statistic is compared to this threshold. When it is greater, the split process is not performed. If we decrease the "P-level" threshold, we obtain a shorter tree.

• "P-level" for merging nodes: The merging process compares the class distribution in the leaves. It searches for the two most similar leaves. They are merged together if the difference between distributions is not significant enough. The statistical significance is determined by comparing the computed P-value of the test with this "P-level" threshold defined by the users. If we decrease the threshold, we obtain larger trees.

If we increase the threshold, we obtain a more compact tree.

• Bonferroni adjustment: as we are multiplying the tests at each node to find the best solutions, we increase in the same time the probability of finding a good solution. The true "P-value" of these tests must be suitable with this kind of adjustment.

APPLICATION TO DOCUMENT ZONE LABELLING

Based on the Improved CHAID algortihm for the document model generation, we propose a flexible and generic approach to deal with several document classes (Fig. 1)

Figure 1.
Reverse engineering overview using physical information in ALTO format producing the final logical structure

Feature extraction

Document images are first recognized by an OCR. In this work, we employed the commercial OCR Omnipage 16 from the Nuance company. [START_REF]Nuance[END_REF] It is one of the leader softwares to handle OCR and document conversion of home office processes.

On the dataset we used, this OCR reaches almost perfect results in both physical layout analysis and text transcription. There are few errors, and hopefully, only in the character recognition. All the physical attributes of the blocks, that we really rely on, can be always considered as correct.

Note that we concretely use the ALTO (Analyzed Layout and Text Object) 2 XML schema to read our input. Other OCR can be used to replace Omnipage. Most of the time, a XSL is enough to make the conversion from a proprietary format to the standard ALTO.

On top of the individual raw attributes of each block of text, we completed them with some statistics concerning the hole set blocks. This is the case, for example, of the space-size-average which describes the mean empty zone size between each pair of blocks.

The table 2 shows 20 of the 45 possible features for the I-CHAID algorithm. Each line represents a block and each column depicts an attribute. This table is generated automatically from the ALTO document, then edited manually by the expert to put the logical tag (Title, Author, Address, Abstract, Keywords, SubTitle, Caption, Footer, Other). Our groundtruth is composed of this kind of table.

Decision tree construction

The goal is to construct the decision tree which will be as shallow as possible. Indeed, with a deep tree, the decision may be too specific and too close to the learning data. A shallow tree favours the most discriminative attributes and can have high generalisation capabilities. The difficulty lies in choosing among n attributes characterizing the blocks, the one allowing the highest discrimination rate, and having the maximum individuals per node. This process is repeated after each segmentation i.e. each node of the tree. The formal mechanism follows these steps:

• Create the root The more we go down in the tree, the more complex is the criterion comparison. The number of entries and the number of criteria are also complexity factors. SIPINA allows us to automate the searching process for discriminating criteria performed by T .

•
The figure 2 shows the decision corresponding to the "Abstract" tag. The first node (the root) indicates 4301 blocks where 39 represent abstracts and 4262 other possibilities. These 39 abstracts are then shared into two sets: 10 and 29, thanks to the attribute "Content Abstract" using the segmentation criteria T (equal to 0.6132 in the table 3.a). The other attributes, in the left side, are successively: the relative position in the page ("relativeHpos"), the page number ("page"), and for the right side: the line number ("Nb Line"). These attributes correspond to: "Hpos", "Pag", "NbL" mentioned in the table 2. We can observe that there are uncertainties in the tree concerning the distribution and thus there will be errors during the recognition.

Deduction and coding rules

From this decision tree, SIPINA provides in addition the optimal physical rules to discriminate the sample blocks for each tag. These rules are then translated and coded in a JAVA class model, which aim is to establish the probability that a block will have a specific tag. At each leave of the tree, a correlation index (i.e. χ 2 ) is performed for each attribute of the father. We consider this correlation index enough discriminant when its value is greater than 0.5. In this case, the condition on the attribute is considered sufficient to discriminate a large number of blocks. It can be seen as an exclusive OR and not as a logical AND which expresses more the child nesting.

The source code stemmed from the previous decision tree (Fig. 2) is given in the figure 4. From the root, we establish the first condition on the block ("isContentAbstractWord") to determine if it is a "Content Abstract" or not. Then, going down in the tree, we iterate with another condition concerning the horizontal position ("getRelativeHeight"), etc. A strength test is performed for each attribute. The corresponding value assigned in the variable point is provided by the strength value of table 3.b and table 3.c. The sum of the point values represents the probability that the block represents an "Abstract".

Logical rules

The logical rules are defined by the operator for a given document class and for each tag. They consolidate and reinforce the tag probability when it is logically well located, and decrease the probability of the other tags which do not correspond to the logical model. The table 3 indicates the correction weights (translated in probabilities). These gains or corrections are set empirically.

Structure recognition

Two methods have been experimented. The first one uses a decision tree per tag. For each block, the physical and logical rules are applied. Each rule stemmed from each decision tree provides a specific tag which leads to a multi-tagging for each block. The tag with the highest strength is selected as the winner. The tag strength is the weighted sum of the physical and logical probabilities. These probabilities are weighted considering the empirical ratios 2/3 for the physical and 1/3 for the logical.

The second method uses a single decision tree which is global to all the tags. As previously, for each block, corresponding physical and logical rules are applied. Each block is labelled only once.

EXPERIMENTS AND DISCUSSIONS

We have experimented this approach on around 1000 documents containing about 16,000 blocks. They are stemmed from ICPR04 7 and ICPR08 8 proceedings. The documents are in PDF and can be directly read by Omnipage OCR 16. The two approaches are compared using the measures: recall, precision, insertion rate and error rate. Globally, the results are satisfactory. In the first approach (i.e. with one tree by tag), the average recall is around 95.7%, the average precision is around 93.5% and the average error rate is 5.9%. In the second approach (i.e. with one global tree), the average recall is around 93.0%, the average precision is around 94.0% and the average error rate is 6.4%. Figure 5 details the percentages for each tag. The chart on the left side shows the precision and recall measurements of both methods while the chart on the right side shows error rates for both methods. The multi-tagging method is more flexible to add new tags type and obtain better results. However the results of both methods are close.

CONCLUSION AND PERSPECTIVES

We have presented in this paper a new method for logical document structure labelling. It is based on decision tree which learn the relationships between the physical features given by commercial OCR on each block of text and the logical labels given by an expert during the training step. The decision tree is consolidated by logical rules, also given by the expert, which are simply deduced from the hierarchical organisation of the blocks. Although all the different steps of the system are not yet fully automatic, we conducted experimentation on 1000 real documents picked from the ICPR 2004 and 2008 proceedings. The first results showed that the error rates are in average less than 6% for the 9 possible labels.

--

  If all the examples belong to the same class or if the number of examples is less than the threshold, then return the class • Let a * be the best attribute • For each value v of a * Add a branch below a * labelled by a * = v -Let S v the example subset where a * = v Apply recursively the algorithm on S v

Figure 2 .Figure 3 .

 23 Figure 2. Decision tree of the tag "Abstract"

Figure 4 .

 4 Figure 4. Source Code generated from the "Abstract" decision tree

Figure 5 .

 5 Figure 5. Result comparison between the two approaches.

Table 1 .

 1 Number table during the crossing of two variables

	Y /X x 1	x l	x L Σ
	y 1
		.
		.
		.
	y k	... n kl ...	n l
		.
		.
		.
	y K
	Σ	n k	n

Table 2 .

 2 Some block features and their values

	Doc Hpos	Vpos	Height Width Size	Align	Style	WS	Iline	Pag Pos CAbs SWUp EWP	SWNb FLUp	Alph	TNb	MTag
	1	103	88	19	788	23	Center	Bold	14.0	100	1	1	false	true	false	false	true	true	false	TITL
	1	386	119	24	221	23	Center	Bold	14.0	425	1	2	false	false	false	false	false	true	false	TITL
	1	230	163	14	531	11	Center	NULL	6.0	251	1	3	false	true	false	false	true	true	false	AUTH
	1	220	198	65	545	10	Center	NULL	6.0	100	1	4	false	false	false	true	true	true	true	ADDR
	1	312	278	52	364	10	Center	NULL	6.0	100	1	5	false	false	false	true	true	true	true	ADDR
	1	94	374	278	385	11	Block	NULL	10.0	100	1	6	true	true	true	false	true	true	false	ABST
	1	94	673	44	384	11	Block	NULL	9.0	100	1	7	false	true	true	false	true	true	false	KEYW
	1	514	374	78	385	12	Left	NULL	7.0	100	1	8	false	false	false	true	true	true	true	STIT
	1	640	487	8	49	7	Left	NULL	1.0	148	1	9	false	true	false	false	true	true	false	OTHR
	1	724	634	8	86	7	Left	NULL	5.0	143	1	10	false	true	false	false	true	true	false	OTHR
	1	643	700	6	73	7	Left	NULL	5.0	130	1	11	false	true	false	false	true	true	false	OTHR
	1	746	529	8	126	7	Left	NULL	5.0	143	1	12	false	true	false	false	true	true	false	OTHR
	1	95	756	9	178	12	Left	NULL	7.0	100	1	13	false	false	false	true	true	true	true	STIT
	1	94	791	128	387	11	Block	NULL	9.0	100	1	14	false	true	false	false	true	true	false	OTHR

Table 3 .

 3 Reinforcement and weakening of the tag probabilities

	Tag	Father	Gain	Son	Gain
	Abstract	Abstract/Address Otherwise	+2 -2	Abstract/Keyword Otherwise	+2 -2
	Address	Address/Author Otherwise	+2 -1	Address/Abstract Author	+2 +1
	Author	Author/Title Otherwise	+2 -2	Author/Address Otherwise	+1 -2
	Caption	Others/Sect Title	+1	Others/Sect Title	+1
	Keyword	Abstract	+2	Keyword/Sect Title	+1
	Footer	Others/Sect Title	+2	Null	+1
		Others/keyword	+1	Others/Sect Title	+2
	Sect Title	Sect Title	+2	Reference	+1
		Otherwise	-3	Otherwise	-3
		Null	+2	Title/Author	+2
	Title	Title	+2
		Otherwise	-1
	Others	Others/Sect Title Otherwise	+2 -4	Others/Sect Title Otherwise	+2 -4