FRANC ¸OIS BOUTERUCHE Solen Quiniou
email: solen.quiniou@irisa.fr

Eric Anquetil
email: eric.anquetil@irisa.fr

WORD EXTRACTION ASSOCIATED WITH A CONFIDENCE INDEX FOR ON-LINE HANDWRITTEN SENTENCE RECOGNITION

Keywords: Word extraction, confidence index, segmentation hypothesis generation, word graph, online sentence recognition

This paper presents a word extraction approach based on the use of a confidence index to limit the total number of segmentation hypotheses in order to further extend our on-line sentence recognition system to perform "on-the-fly" recognition. Our initial word extraction task is based on the characterization of the gap between each couple of consecutive strokes from the on-line signal of the handwritten sentence. A confidence index is associated to the gap classification result in order to evaluate its reliability. A reconsideration process is then performed to create additional segmentation hypotheses to ensure the presence of the correct segmentation among the hypotheses. In this process, we control the total number of segmentation hypotheses to limit the complexity of the recognition process and thus the execution time. This approach is evaluated on a test set of 425 English sentences written by 17 writers, using different metrics to analyze the impact of the word extraction task on the whole sentence recognition system's performances. The word extraction task using the best reconsideration strategy achieves a 97.94 % word extraction rate and a 84.85 % word recognition rate which represents a 33.1 % word error rate decrease relatively to the initial word extraction task (with no segmentation hypothesis reconsideration).

Introduction

Handwriting recognition has been a subject of intensive research for many years. Whereas the recognition of isolated characters and words already achieves high recognition rates [START_REF] Plamondon | On-line and off-line handwriting recognition: a comprehensive survey[END_REF] , handwritten text recognition is still a challenging task involving open issues. Among these problems are the integration of syntactic and semantic information during the recognition process or the segmentation problem since the number of words is unknown as well as their position in the text.

In the context of on-line handwriting recognition on pen-based devices such as personal digital assistants (PDAs) or Tablet PCs, input methods are needed. Handwriting input methods are designed to enter text on these pen-based devices, using a pen to write on the sensitive screen. The recognition of the strokes a corresponding to the text is thus performed "on-the-fly" i.e. as they are written. Fig. 1 shows an example of an "on-thefly" recognition on a PDA, using our input method DIGIME [START_REF] Bouteruche | Design and evaluation of handwriting interfaces for small-size mobile devices[END_REF] which allows the input of isolated characters in a word context. The interface is designed to be as user friendly as Input method Application Fig. 1. Example of an "on-the-fly" recognition with the DIGIME input method. possible. That is why the recognized characters are directly displayed in the input area, in addition to being transmitted to the target application. Our goal is actually to further extend our on-line handwritten sentence recognition system [START_REF] Quiniou | A priori and a posteriori integration and combination of language models in an on-line handwritten sentence recognition system[END_REF] to an "on-the-fly" recognition process to allow the input of text on TabletPCs. Fig. 2 shows an example of such a sentence input method based on the principles of the DIGIME method. The input area displays a sliding window of the most recently recognized words as well as strokes not yet recognized and whose recognition depends on the most recently written stroke. The will to further extend our sentence recognition system to an "on-the-fly" recognition process sets some constraints on the word extraction task in terms of the complexity of the methods used (which has an impact on the execution time) as well as toward the available information (not all the words of a text line are available but only the previously written ones).

In most of the works, lines are firstly detected before being segmented into words. In off-line recognition systems, the classic approaches are based on connected components [START_REF] Kim | An architecture for handwritten text recognition systems[END_REF][START_REF] Manmatha | A scale space approach for automatically segmenting words from historical handwritten documents[END_REF] or on y-axis projection profiles [START_REF] Kavallieratou | An integrated system for handwritten document image processing[END_REF][START_REF] Yu | A robust and fast skew detection algorithm for generic documents[END_REF] ; recent works on the identification of regions and text lines on pages of on-line freeform handwritten notes also make use of the projection technique. [START_REF] Jain | Structure in on-line documents[END_REF][START_REF] Namboodiri | Online handwritten script recognition[END_REF][START_REF] Ratzlaff | Inter-line distance estimation and text line extraction for unconstrained online handwriting[END_REF] Other approaches to detect regions and text lines on on-line freeform handwritten notes are based on Probabilistic Feature Grammars [START_REF] Blanchard | On-line handwritten documents segmentation[END_REF] , on classifiers [START_REF] Ye | Learning to group text lines and regions in freeform handwritten notes[END_REF] or on dynamic programming [START_REF] Shilman | Discerning structure from freeform handwritten notes[END_REF] but they need whole handwritten note pages and the detection algorithm is often a multi-pass one: this is not suited for an "on-the-fly" segmentation task. In off-line handwritten text recognition [START_REF] Marti | Text line segmentation and word recognition in a system for general writer independent handwriting recognition[END_REF] as well as in on-line handwritten text recognition [START_REF] Oudot | An activation-verification model for on-line texts recognition[END_REF] , rather simple methods using learnt thresholds on gaps between consecutive lines can also be applied.

Word extraction approaches are generally based on the following scheme. From a decomposition of a text line into components (in on-line recognition, the components generally correspond to the strokes whereas in off-line recognition they correspond to connected components), a classification of the gaps between these components is done in order to identify the words, by using a gap metric. Generally, the gap metrics used are the bounding box distance, the convex hull distance or the white run-length distance. Using the chosen gap metric, inter-component gaps are then classified into either inter-word gaps or intra-word gaps. This characterization can be done by comparing the gaps to a threshold [START_REF] Kavallieratou | An integrated system for handwritten document image processing[END_REF][START_REF] Liwicki | Word extraction from on-line handwritten text lines[END_REF][START_REF] Mahadevan | Gap metrics for word separation in handwritten lines[END_REF][START_REF] Marti | Text line segmentation and word recognition in a system for general writer independent handwriting recognition[END_REF][START_REF] Park | Use of adaptive segmentation in handwritten phrase recognition[END_REF][START_REF] Seni | External word segmentation of off-line handwritten text lines[END_REF][START_REF] Varga | Tree structure for word extraction[END_REF] . Most of the thresholds used are not fixed but are computed from some features of the text line, like the median gap size or the line width: the whole text line is thus needed. Other methods use hierarchical clustering [START_REF] Kim | Word segmentation of printed text lines based on gap clustering and special symbol detection[END_REF][START_REF] Mahadevan | Hypotheses generation for word separation in handwritten lines[END_REF] or classifiers to discriminate intra-word and inter-word gaps. In Ref. 19, Hidden Markov Models are used to model space and non-space characters whereas a neural network classify the type of each inter-component gap in Refs. 9, 14, 27 (in Ref. 9, semantic information are also used in addition to the image features).

In this paper, we present a word extraction task based on the characterization of the gap between each couple of consecutive strokes, using a Radial Basis Function Network (RBFN). Unlike most of the works on word extraction, our proposed approach also detects the text lines simultaneously and doesn't perform any pre-processing steps typically used to normalize lines with respect to slant, skew or character height. Moreover, this approach is designed to be further used in an "on-the-fly" segmentation and recognition context, which limits the available knowledge to information about the strokes on the left of the most recently written stroke. In order to ensure the presence of the correct segmentation, we generate multiple segmentation hypotheses. Nevertheless, we want to limit the overall execution time which makes it important to choose the added segmentation hypotheses to only keep the most pertinent ones. To do this selection, we use a confidence index on the inter-stroke gap characterization results: this confidence index is then compared to a learnt threshold which enables us to control the total number of segmentation hypotheses by focusing on the less reliable segmentation points. All the segmentation hypotheses are finally organized into a word graph on which the sentence recognition is performed, using our word recognition system RESIFMot 8 as well as a language model. It should be noted that the word extraction task is independent of the sentence recognition step so any other word recognition system may be used. Our word extraction task is evaluated according to different reconsideration thresholds as well as towards a straightforward "oversegment & merge" approach (each stroke is considered to be a word and up to nmax strokes strokes can be merged to form a word) which shows the efficiency of our approach.

In Sec. 2, the whole sentence recognition system is introduced. Then, our initial word extraction task is first described in Sec. 3 and its extension for the generation of additional segmentation hypotheses based on a confidence index is presented in Sec. 4. Finally, experimental results are discussed in Sec. 5 while Sec. 6 draws some conclusions.

Overview of the Sentence Recognition System

The whole recognition system illustrated by Fig. 3 extends our on-line sentence recognition system previously presented in Ref. 30. This system consists of three parts: segmentation of the sentence into its words, recognition of the extracted words and recognition of the sentence. We introduce these three steps and we will present the word extraction part in further details in Sections 3 and 4, since this is the object of this article.

Word extraction

As an on-line handwritten text is represented by a list of chronologically sorted strokes, the word extraction task consists of extracting each sublist of strokes corresponding to the words. Thus, the first sub-module of the word extraction task aims at gathering the parts of the input handwritten sentence that correspond to each handwritten word, to initialize the word graph (see Sec. 3). The nodes of this graph represent the segmentation frontiers between two consecutive words and the edges stand for the hypothetical handwritten words (initial edges are shown in bold in the word graph of Fig. 3). The task of the following submodule is to generate additional segmentation hypotheses (represented by dotted edges in Fig. 3). These edges and nodes are created in the word graph in order to ensure the correct segmentation to appear in the word graph, thus dealing with potential under-and over-segmentation problems that may appear in the initial word graph (see Sec. 4).

Word recognition

Our word recognition system RESIFMot 8 takes each previously extracted word as an input and outputs a list of 20 candidate words: this list is then associated to each edge of the word graph, as shown in figure Fig. 3.

RESIFMot is a word recognition system based on an analytic approach. Words are segmented according to different hypotheses of letter allographs b , based on specific knowledge of the structure of handwritten characters. The fundamental structure corresponds to pertinent downstrokes: one character is made of one to three pertinent downstrokes (independently of the writing style). The allograph hypotheses are organized into a segmentation graph and an adapted version of our character recognition system RESIFCar 2 is used to b Allographs are variant shapes of the same letter. validate the correct segmentation hypotheses and to generate each allograph hypothesis. Then, the exploration of this graph produces a list of character strings. Finally, a lexical post-processing step is performed to retrieve the nearest word of each string hypothesis, according to a dictionary. The word recognition system thus outputs a list of candidate words, ranked according to a score depending on edit operations used to transform the character string into its corresponding word 7 .

Sentence recognition

The sentence recognition is finally performed to retrieve the N -best sentences Ŵ that maximize the a posteriori probability among all the sentences W k = w k,1 . . . w k,n k , given the handwritten signal S:

Ŵ = arg max W k score(W k ) = arg max W k score(S|W k ) + γ log P (W k ) + δ n k (1)
where score(S|W k ) is estimated by the word recognition system RESIFMot and P (W k ) is estimated thanks to a language model (since our word recognition system is not probabilistic, the output is not a probability but this output score can be interpreted as a likelihood and then combined to a language model probability). To optimize the integration of the language model into the sentence recognition system, two additional parameters γ and δ are introduced. The parameter γ (called the Grammar Scale Factor) is used to balance the relative impact of the language model toward the word recognition system whereas δ (called the Word Insertion Penalty) is used to deal with the whole sentence recognition system tendency to make over-or under-segmentations. When the recognition system has a tendency to under-segmentation, setting δ < 0 can compensate it whereas setting δ > 0 can deal with a tendency to over-segmentation.

A beam search algorithm [START_REF] Ney | Dynamic programming search for continuous speech recognition[END_REF] is actually performed on the word graph to efficiently retrieve the N -best sentences Ŵ (corresponding to paths in the graph), by combining the graphic and linguistic information as given by Eq. ( 1). This search strategy is timesynchronous and can be viewed as an approximation of the Viterbi algorithm 10 where, at each node of the word graph, only the sentence hypotheses whose scores within a fixed radius (called the beam) are kept: this enables the pruning of the most unlikely hypotheses. The size of the beam is set empirically (at most 5 000 hypotheses are kept in our system). This recognition scheme can be performed during the writing of the sentence, which is suitable for an "on-the-fly" recognition. Therefore, the recognized sentence can be displayed as the sentence is being written and will be updated each time the most recently written strokes have been analyzed and recognized (as shown by Fig. 2).

After presenting the whole sentence recognition system, we will focus on the word extraction task, in the two following sections.

Initial Word Extraction

Our word extraction scheme consists of a characterization of the inter-stroke gaps of the on-line signal representing the considered handwritten sentence. Since our data are English handwritten sentences without any punctuation mark, we consider three kinds of gaps:

• intra-word gap: gap between two strokes from the same word • inter-word gap: gap between two strokes from two consecutive words • inter-line gap: gap between two strokes from two consecutive words written on two consecutive lines.

Fig. 4 gives an example of a handwritten sentence to recognize where intra-word, interword and inter-line gaps are shown.

Inter-stroke gap characterization

The inter-stroke gap characterization algorithm process the strokes as they are written (see Algorithm 1). For each newly written stroke S new the gap between this stroke and the Algorithm 1: Algorithm for the characterization of inter-stroke gaps.

Input: strokes of the handwritten sentence to recognize;

Output: inter-stroke gaps characterized as intra-word, inter-word or inter-line gaps; In the following subsections, we detail the steps of our gap characterization algorithm.

Initialization

At the beginning of the word extraction task, the Baseline Reference Group BRG is initialized with the firstly written strokes of the sentence (see Sec. 3.1.5 for greater details on the number of strokes used to initialize the BRG).

Lower and upper baseline detection

The lower and upper baselines we detect delimit a more restricted zone than the text body classically used. This zone is defined as the vertical zone covering the maximal number of pertinent downstrokes. This maximal covering is computed as in our word recognition system 1 : an histogram distribution of the projection of the text on the y-axis is used but where only the pertinent downstrokes are being projected (instead of considering all the points of all the characters). This zone actually corresponds to the one where letters like a or e are written: this zone is the most stable zone of the writing and is less sensitive to skew problems.

To detect the lower and upper baselines, we run the algorithm also used in our word recognition system. The baseline detection is thus carried out on a group of strokes representing a "virtual word": it corresponds to the BRG previously presented. To ensure the robustness of the baseline detection, this "virtual word" has to contain three or four characters. Thus, since a character is composed of one to three pertinent downstrokes (see Sec. 2.2), we keep enough strokes in the BRG to ensure it contains at least 10 pertinent downstrokes. We could have kept more previously written strokes in the BRG to make the baseline detection the most reliable possible but this detection would have been too sensitive to skew problems. Indeed, since the gap characterization algorithm is designed to be further extended to an "on-the-fly" recognition, we want to avoid costly pre-processing steps that are generally performed on the signal to correct slant, skew or character size problems. That's why we limit the number of strokes in the BRG.

∆x new ref = x P mtl new -x P mtr ref ( 2
)
where P mtl new is the most-on-the-left point of S new and P mtr ref is the most-on-the-right point of S ref . These points are chosen among the points between the lower and the upper baselines in order to deal with slant problems. Indeed, this kind of problem is not corrected by pre-processing steps performed on the sentence before the extraction of its words. In the example given by Fig. 6, we can see that if these points weren't chosen between the baselines, the computed distance would have been the bounding box distance ∆x BB and an intra-word gap would have been detected between the words said and again whereas our restriction allows the correct detection of the inter-word gap between these words. The inputs of this classifier are the following:

• the size of the current inter-stroke gap, relatively to the previous strokes: it corresponds to the distance ∆x new ref ;

• information on the relative sizes of the previous inter-stroke gaps: this is given by the maximum and the median ∆x new ref in the BRG; • information for inter-line gaps identification: this is given by the distance between the top of the S new bounding box and the lower baseline.

The outputs of the RBFN are the scores associated with each of the three classes corresponding to the intra-word gap, the inter-word gap and the inter-line gap. Finally, the type of the considered inter-stroke gap corresponds to the class with the highest score.

BRG update

Once the gap E new ref is classified, the stroke S new is added to the BRG. The temporally oldest stroke of the BRG can then be deleted but only if at least 10 pertinent downstrokes still remain in the BRG. The BRG can be seen as a sliding window, moving with the writing and the processing of the strokes: this is particularly adapted for an "on-the-fly" word extraction.

To start the inter-stroke gap characterization, the baseline detection needs to have enough written strokes to ensure the first BRG to contain at least 10 pertinent downstrokes. This initial BRG is also used to characterize the first inter-stroke gaps even if the considered strokes belong to this BRG. As can be seen in Fig. 5, the BRG used to characterize the gap between the strokes gener and ally contains these two strokes.

Word graph creation

The initial word graph is built from the results of the inter-stroke gap classification task. For each inter-line or inter-word gap detected, a node is created: each node thus represents a segmentation frontier between two words. Edges are created by gathering strokes such that each inter-stroke gap between two consecutive strokes of an edge is an intra-word gap. They thus represent the extracted handwritten words. Fig. 7 shows an example of a word graph built from the characterization of the interstroke gaps of the sentence "generally the same level of living costs less in the country than in the city". We can see that the words living and country are over-segmented whereas the words "than in" are under-segmented. We now extend our inter-stroke gap characterization algorithm to deal with potential Word Extraction for On-Line Handwritten Sentence Recognition 11 under-and over-segmentations, by creating additional segmentation hypotheses while controlling the size of the word graph.

Confidence Index Based Word Extraction

To ensure the presence of the correct segmentation of the sentence, one straightforward solution would be to consider all the possible segmentation hypotheses (it corresponds to an "oversegment & merge" approach). This is not reasonable since it would dramatically increase the size of the word graph and thus considerably increase the recognition time. Furthermore, it would mostly introduce some noise i.e. incorrect segmentation hypotheses. This could then bring errors during the sentence recognition step performed on the word graph. The experiments presented in Sec. 5 will confirm this idea.

The key aspect of the generation of additional segmentation hypotheses lies in the choice of these additional hypotheses which should be the most pertinent. To create these hypotheses, we rely on an index evaluating the confidence in the result of the inter-stroke gap classification.

In the following subsections, we present the computation of this confidence index as well as its use to deal with potential under-and over-segmentations.

Confidence index on the inter-stroke gap characterization

In order to evaluate the reliability in the first answer of the inter-stroke gap classification, we associate a confidence index to the result of the RBFN. If this confidence is too low, the second answer of the classifier is also considered.

The confidence index we use corresponds to the relative difference dif f top2 between the scores of the two best classes. The confidence index dif f top2 is then compared to a learnt threshold σ reconsider : if the confidence index is below the threshold, the first answer of the RBFN can be reconsidered and additional segmentation hypotheses may then be created.

To set the threshold σ reconsider on these confidence indexes, we use an ambiguity reject [START_REF] Mouchère | A unified strategy to deal with different natures of reject[END_REF] . The use of this kind of reject allows us to learn the threshold by setting the percentage of elements that have to be rejected i.e. the percentage of inter-stroke gap classifications that have to be reconsidered, in our case.

Generation of additional segmentation hypotheses

Confidence indexes associated to each of the inter-stroke gaps now allow the creation of additional segmentation hypotheses (represented by edges in the word graph).

To control the size of the final word graph (in terms of number of edges), we set some limitations. Firstly, inter-line gaps are supposed to be correctly identified and will thus not be reconsidered. The other restrictions aim at dealing with either under-segmentations or over-segmentations and will be further explained in the following subsections. In Sec. 5, we will see that these limitations are not too restrictive since almost all the segmentations can be retrieved, in the test set.

Under-segmentation processing

To limit the creation of additional edges, we consider that at most nmax under words may be grouped into a same word (thus represented by one edge), after the initial word extraction. An initial edge could then be further separated into nmax under parts, at most.

In order to chose the points of the potential separations of an edge, its intra-word gaps with a positive distance ∆x new ref and an associated confidence index dif f top2 below the reconsideration threshold σ reconsider are sorted according to their ascending confidence indexes. Then, at most the nmax under -1 first intra-word gaps are considered as potentially misrecognized inter-word gaps. Additional edges and nodes are then created from the current edge, as shown in Fig. 8 by dotted edges and their corresponding nodes (here, nmax under = 3).

Edge and node generation

Fig. 8. Example of additional edge and node creation, to deal with under-segmentations.

Over-segmentation processing

In the same way as the processing of under-segmentations, we consider that a word may be over-segmented into at most nmax over parts. At most nmax over initial edges could then be further gathered into additional edges.

To deal with these potential over-segmentations, we consider each group of nmax over consecutive edges. At most nmax over -1 inter-word gaps with a confidence index dif f top2 below the reconsideration threshold σ reconsider can be considered as potentially misrecognized intra-word gaps: additional edges are then created as shown in Fig. 9 (here, nmax over = 3).

Moreover, to limit the length of edges in terms of the number of dowstrokes, we consider that additional edges can only be created if their total number of downstrokes is at most nmax downstr .

Creation of the final word graph

The final word graph is created after the processing of every potential under-and oversegmentations. Fig. 10 shows the full word graph resulting in the whole word extraction task based on the use of confidence indexes, for the sentence already presented in Fig. 7. Edges and nodes in dotted lines were created to deal with the initial under-and oversegmentations. We can see that a path corresponding to the correct segmentation now appears in the word graph.

Experiments and Results

In this section, we present the experiments conducted to evaluate our word extraction approach. We first describe the databases we use and then discuss the parameter optimization in Sec. 5.2 before presenting the results in Sec. 5.3.

Databases

The handwritten material consists of English sentences without any punctuation marks, written from 2,598 sentences of the Brown corpus [START_REF] Francis | Brown Corpus Manual[END_REF] . In these first experiments on word extraction, we wanted to evaluate our approach without adding the difficulty of processing punctuation marks, as this is the case in the work presented in Ref. 18 where punctuation marks were removed from the data using some heuristics (the processing of punctuation marks will be investigated in future works, which will be further discussed in Sec. 6). The training set includes 517 sentences (8,047 words) written by 25 writers whereas the test set includes 425 sentences (6,362 words) written by 17 writers. The training set is used to learn the RFBN for the inter-stroke gap classification task as well as the reconsideration thresholds σ reconsider . The writers of the test set are different from those of the training set.

The language model used during the sentence recognition step (see section 2) is a bigram model. A bigram model gives the probability of a word w i by only considering its previous word w i-1 : the probability P (w k,i |w i-1 k,i-n+1 ) is thus approximated by P (w k,i |w k,i-1 ). The bigram language model used in our experiments is built from the Brown corpus, with the SRILM toolkit [START_REF] Stolcke | SRILM -an extensible language modeling toolkit[END_REF] . The Brown corpus contains 52,954 English sentences (1,002,675 words) where 46,836 sentences (900,108 words) were actually kept to learn the language model (the 2,598 remaining ones are used for the acquirement of the handwritten material). During the lexical post-processing 8 , we use an associated lexicon including 13,748 words.

Parameter optimization

Since we don't have a validation set, the training set is also used to optimize the integration of the language model (i.e. the values of the grammar scale factor, and of the word insertion penalty) as well as to tune the parameters for our complete word extraction approach based on confidence indexes. In the following sub-sections, we present the results of the optimization of the parameters used in the confidence index based word extraction approach, to generate additional segmentation hypotheses.

Number of segmentation parts: setting nmax under and nmax over

The generation of additional segmentation hypotheses aims at dealing with over-and under-segmentation errors that could appear when using the initial word extraction approach. To do so, the number of parts in which a word may be over-segmented has to be set as well as the number of words considered as one word: it corresponds to the parameters nmax under and nmax over . The aim is thus to maximize the presence of the whole correct segmentation hypothesis (i.e. EP R) while minimizing the total number of segmentation hypotheses (i.e. GD).

The values of the EP R and the GD are maximal bounds since we consider here that each inter-stroke gap characterization can be reconsidered to generate additional segmentation hypotheses. In fact, these values will be lower because an optimized reconsideration threshold σ reconsider is used to further limit the number of generated hypotheses (it will be discussed in the following sub-section). Therefore, we consider that the best trade-off between the considered indicators is achieved for nmax under = 3 and nmax over = 3. With these values, the generation of additional segmentation hypotheses could allow the correct extraction of words over-segmented into at most three parts as well as of words under-segmented with at most three words considered as one word. Moreover, the maximal number of downstrokes contained in a word has to be set: its computation on the training set sets the value of nmax downstr to 25. Using the optimized values of these three segmentation parameters, the maximal EP R we can achieve on the test set is 99.76 %.

Reconsideration threshold: optimizing σ reconsider

To generate additional segmentation hypotheses, a reconsideration threshold σ reconsider also needs to be chosen: the value of this threshold is automatically learnt from the percentage of inter-stroke gaps whose characterization has to be reconsidered (see Sec. 4.1). Fig. 12 shows the impact of different reconsideration thresholds on the creation of additional segmentation hypotheses, according to the edge presence rate EP R and the graph density GD defined in Sec. 5. percentage of inter-stroke gap classifications that are reconsidered when the corresponding threshold is learnt. As previously, the aim is thus to minimize the GD while maximizing the EP R. The reconsideration threshold that leads to the best trade-off between these indicators is the one reconsidering 10 % of the inter-stroke gap classifications (the corresponding value is σ reconsider = 0.71): the graph density increases a little (from 0.99 to 1.54) whereas the edge presence rate rises greatly (by 8 %), as compared to the initial word extraction approach. Whereas the improvement from no reconsideration threshold to the 10 % reconsideration threshold is statistically significant, the small increase in the edge presence rate when going from the 10 % reconsideration threshold to the 20 % reconsideration threshold is not statistically significant (measured at the word level using a paired t-test at the 0.01 significance level).

Experimental results

The aim of these experiments is to show the efficiency of our word extraction approach based on the characterization of inter-stroke gaps as well as of our extended approach where additional segmentation hypotheses are generated using the optimized reconsideration threshold (see Sec. 5.2.2). Our approaches are also compared to a manual word extraction task (representing the ground truth) as well as to a straightforward "oversegment & merge" approach. In the latest approach, each stroke is considered to be a word and words can also be created from up to nmax strokes consecutive strokes. Four metrics are used to compare these approaches. We use the edge presence rate EP R and the graph density GD defined in Sec. 5. The word extraction rate W ER and the word recognition rate W RR are computed on the recognized sentences whereas the edge presence rate EP R and the graph density GD are computed on the word graphs. The graph density allows the comparison between the number of words that have to be extracted (i.e. the number of words to recognize) and the number of words extracted by the considered approach. Since the word recognition system is called on each edge and the recognition of words represents the main part of the overall processing time of a sentence, the graph density gives an indication on the increase of the overall recognition time towards a correct segmentation approach (i.e. that only generates segmentation hypotheses corresponding to words to recognize). Indeed giving real execution time wouldn't be meaningful since our word recognition system is not yet optimized to really perform "on-the-fly". The results on the comparison of the different word extraction strategies on the test set are summarized in Table 1. As already seen with the EP R on the training set, the performances are greatly improved when additional segmentation hypotheses are generated, based on confidence indexes. Indeed, with the optimal confidence index based word extraction approach (with the optimal reconsideration threshold presented in Sec. 5.2.2), the W RR is increased by 7.5 % (corresponding to a 33.1 % relative reduction of the word error rate), the W ER by 6.2 % (corresponding to a 66.7 % relative reduction of the word extraction error rate) and the EP R by 8.1 %, as compared to the initial word extraction approach. These rates are also quite close to the ground truth (less than 4 % below). Moreover, the GD only rises a little and is about 1.5 times the GD of the initial extraction approach. The GD is also about 1.5 times the GD of the ground truth: it means that the overall execution time with the confidence index based word extraction approach doesn't increase too much as compared to the execution time when the segmentation is entirely correct, represented by the ground truth.

Two straightforward "oversegment & merge" approaches are considered, depending on the value of the parameter nmax strokes . These values were chosen so as to have edge presence rates close to the one achieved with our initial word extraction approach (corresponding to nmax strokes = 6) and close to the one for our confidence index based word extraction approach (corresponding to nmax strokes = 10). The graph densities obtained with the "oversegment & merge" methods are much higher than the ones achieved with our approaches: when nmax strokes = 6, the GD is increased by more than a 20 factor (relatively to the complexity for our initial word extraction method) and when nmax strokes = 10, this factor is also a little more than 20 (relatively to the complexity achieved with our confidence index based word extraction approach). It shows the efficiency of our word extraction approaches since we achieve comparable EP R but with lower GD which implies lower execution times. Moreover, the W ER and W RR are below the ones achieved with our approaches (more than 20 % and 15 % lower, respectively). Having lower W ER and W RR whereas having close EP R can be explained by the fact that the size of the search space has been considerably increased with the "oversegment & merge" methods (as illustrated by their GD): it makes the recognition of the correct sentences harder (the W ER and W RR are computed on the recognized sentences). Indeed, there is a very high number of incorrect segmentation hypotheses that are generated to ensure the correct one to appear in the word graph and it makes it more difficult to identify the correct sentence between all the possible sentences of the graph. This shows the importance of the selection of the generated segmentation hypotheses not only with respect to the execution time but also towards the overall performance of the recognition system.

These results cannot be directly compared to existing works since the databases are different from each other. However, in Ref. 18, the W ER achieved on a subset of the IAM-OnDB database [START_REF] Liwicki | Handwriting recognition of whiteboard notes -studying the influence of training set size and type[END_REF] with a threshold based approach is 86.6 %. It can be compared to the W ER achieved with our initial word extraction approach since no sentence recognition step is involved in the cited work whereas the W ER for our confidence index based approach is computed on recognized sentences. Nonetheless, even if the handwritten texts of the subset of the IAM-OnDB database do not contain punctuation marks (that were manually removed), these data were written on a whiteboard which makes the segmentation process more difficult than using texts written on a TabletPC like our data. Future works will involve the evaluation of our word extraction approach on this IAM-OnDB database.

Conclusion and Future Work

In this paper, we have presented an automatic word extraction mechanism based on the classification of inter-stroke gaps, using a RBFN. In order to ensure the presence of the correct segmentation, a step was added to allow the generation of other segmentation hypotheses into the word graphs on which the sentence recognition is performed. Their creation relies on a confidence index associated with the inter-stroke gaps classification results. This confidence index is used to detect the less reliable segmentation points by comparing it to a learnt threshold. Thanks to it, we were able to limit the total number of segmentation hypotheses and thus the overall execution time since we want to further extend our sentence recognition system to perform "on-the-fly" recognition.

Experimental results have shown significant improvements on the performances of the recognition system when additional segmentation hypotheses were created, based on the use of confidence indexes. Indeed, when 10 % of the gap classification results may be reconsidered, the word recognition rate went from 77.35 % to 84.85 % whereas the word extraction rate went from 89.86 % to 96.01 %. Our word extraction approaches were also compared to a straightforward "oversegment & merge" method. The graph densities achieved with our approaches were thus shown to be more than 20 times lower than those of the considered "oversegment & merge" methods. It is important to take into account the size of the word graph generated by a word extraction approach since the overall recognition time is directly linked to it and one of our objectives was to limit this recognition time to further perform "on-the-fly" recognition. Furthermore, we have also enlightened the importance of the choice of the generated segmentation hypotheses. Indeed, the word recognition rates dropped significantly when a too large number of incorrect segmentation hypotheses were added to the word graphs.

In order to take advantage of segmentation information to further optimize the sentence recognition, future works will investigate the integration of the segmentation score associated with each inter-stroke gap (see Sec. 3.1.4) into the sentence score which already uses graphic and linguistic information (see Eq. ( 1)). Moreover, we will carry on our first experiments by evaluating our word extraction task on other on-line handwritten sentence databases, like the IAM-OnDB database [START_REF] Liwicki | Handwriting recognition of whiteboard notes -studying the influence of training set size and type[END_REF] . In order to extend our word extraction task

Fig. 2 .

 2 Fig. 2. Illustration of an "on-the-fly" sentence input method.

WordFig. 3 .

 3 Fig. 3. Sentence recognition system.

Word 7 InterFig. 4 .

 74 Fig. 4. Handwritten sentence with examples of the three kinds of inter-stroke gaps.

  begin Initialization initialization of BRG with the firstly written strokes (temporally sorted); while a stroke S new is written do detection of the writing baselines; computation of the distance ∆x new ref between S ref and S new ; classification of the gap E new ref between the strokes S ref and S new ; update of BRG; end previously written one S ref (also called the reference stroke) is characterized into one of the three considered kinds of gaps. This gap characterization is based on the computation of the distance ∆x new ref between these two strokes. In fact, for this distance computation, not only the previously written stroke S ref is used but also a group of more previously written strokes called the Baseline Reference Group (BRG): this group of strokes represents a relative spatial context toward which the distance ∆x new ref can be compared. Fig. 5 illustrates the distance ∆x new ref computation as well as the corresponding BRG used. A classifier is finally used to characterize the inter-stroke gap, based on the computed distance ∆x new ref as well as other information.

Fig. 5 .

 5 Fig. 5. Example of a distance ∆x new ref computation.

3. 1 . 3 .

 13 Distance ∆x new ref computation Since our data are English handwritten sentences, the first stroke of a new word is more likely to be on the right of the last stroke of the previous word. To compute the distance ∆x new ref (see Fig. 5) between the most recently written stroke S ref and the newly written Word Extraction for On-Line Handwritten Sentence Recognition 9 stroke S new , we use the distance in x-coordinate between the most-on-the-right point of S ref and the most-on-the-left point of S new :

Fig. 6 .

 6 Fig. 6. Illustration of the choice of the points P mtl new and P mtr ref to deal with slant problems.

Fig. 7 .

 7 Fig. 7. Example of a word graph, built from the initial extraction of the words of a handwritten sentence.

WordFig. 9 .

 9 Fig. 9. Example of additional edge creation, to deal with over-segmentations.

Fig. 10 .

 10 Fig. 10. Example of a full word graph (additional edges and nodes are illustrated by dotted lines).

Fig. 11 (Fig. 11 .

 1111 Fig. 11. Optimization of the segmentation parameters nmax under and nmaxover, on the training set.

2 . 1 .Fig. 12 .

 2112 Fig. 12. Optimization of the reconsideration threshold σ reconsider , on the training set.

  2.1 as well as the word extraction rate and the word recognition rate defined as follows: • Word extraction rate: W ER = number of correctly extracted words number of words • Word recognition rate: W RR = number of correctly recognized wordsinserted words number of words

Table 1 .

 1 Comparison of different word extraction strategies (on the test set).

	Word Extraction for On-Line Handwritten Sentence Recognition 17
	Word extraction strategy	W RR	W ER	EP R	GD
	Manual (ground truth)	88.46 %	100 %	100 %	1.00
	Initial word extraction (0 % reconsider.)	77.35 % 89.86 % 89.86 %	0.99
	Confidence index based word extraction (10 % reconsider.)	84.85 % 96.01 % 97.94 %	1.58
	"Oversegment & merge" (nmax strokes = 6)	57.48 % 66.44 % 89.09 %	20.32
	"Oversegment & merge" (nmax strokes = 10)	73.42 % 78.58 % 98.29 %	32.53

S. Quiniou, F. Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F. Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

S. Quiniou, F.Bouteruche & E. Anquetil

Word Extraction for On-Line Handwritten Sentence Recognition 19 to real use cases, we will need to process punctuation marks. In Ref. 6, we have already presented an approach which allows the recognition of punctuation marks in a character recognition context: the same approach can be used in our sentence recognition context. Finally, since our word extraction task was designed to be further used for "on-the-fly" recognition, it would be interesting to investigate its performance in a real "on-the-fly" recognition context. This will also require an optimization of our word recognition system.


Solen Quiniou
email: solen.quiniou@synchromedia.ca

Mohamed Cheriet
email: mohamed.cheriet@etsmtl.ca

Eric Anquetil
email: eric.anquetil@irisa.fr

Design of a Framework Using InkML for Pen-Based Interaction in a Collaborative Environment

Keywords: Digital ink, InkML, annotations, collaborative environments

We present a framework based on the standard InkML format to represent digital ink in a collaborative environment using pen-based interaction functionalities. This framework includes the capture, the rendering and the interpretation of the digital ink. In the proposed framework, we focus more particularly on the representation of the contextual environment of the ink and used it for its interpretation (as drawing, for example) as well as on the representation of semantic information attached to the ink after its interpretation.

Introduction

With the emergence of pen-based devices such as PDAs, Tablet PCs or whiteboards, pen-based input methods are becoming relevant in collaborative environments. Indeed, they allow users to input elements like text or drawings in a more natural way to communicate with each other. Pen-based interactions are thus useful in domains like remote healthcare, collaborative document annotation or active learning in classrooms where applications like whiteboard sharing allow several users to write or draw on a virtual shared whiteboard (blank or containing documents like images that can be annotated, for example).

The digital ink data used for this interaction thus needs to be represented in some format to be exchanged among the users. This format should also be able to represent other contextual information that may be needed to interpret the digital ink as text, drawing or annotations, for example, and should be able to represent the result of this interpretation process. To do so, the Ink Markup Language (InkML) [START_REF] Chee | Ink Markup Language (InkML)[END_REF] has been proposed by the W3C Multimodal Interaction Activity as an open standard for representing both the ink data (entered with some electronic device) and the inking environment. Furthermore, as InkML is an XML-based language, it is easily extensible to add specific information needed by any developed application.

The context of this paper is the addition of pen-based interaction functionalities into the collaborative environment Synchromedia. Synchromedia is a consortium regrouping Canadian Universities (ÉTS, Concordia, Waterloo, UQÀM or Teluq), companies like Inocybe Technologies Inc. and other partners such as the Hôpital du Sacré-Coeur in Montreal. The aim of this consortium is to develop a collaborative environment integrating different media (texts, sounds, videos…). The current phase of this project focuses on methods to improve the communication between users and to include functionalities that take advantage of pen-based interactions and more particularly on the interpretation of digital ink to attach semantic information to it. For this purpose, we propose a framework based on the InkML format, where we focus more particularly on the representation of the contextual environment of the digital ink as well as on the representation of its interpreted elements. Previous works [START_REF] Keshari | Sharing Digital Ink in Heterogeneous Collaborative Environments[END_REF] and [START_REF] Neddenriep | RiverInk -an Extensible Framework for Multimodal Interoperable Ink[END_REF] also use InkML to represent digital ink in a collaborative environment but they focused more on dealing with interoperability problems to send digital ink and to render it on heterogeneous devices and platforms.

The rest of this paper is organized as follows. In Section 2, we present the basic elements of InkML and, in Section 3, we describe the framework and more particularly the use of InkML to represent the aforementioned elements. Finally, we draw some conclusions in Section 4.

Overview of the Ink Markup Language (InkML)

InkML [START_REF] Chee | Ink Markup Language (InkML)[END_REF] is a markup language for representing digital ink which has been proposed by the W3C as an alternative to proprietary ink data formats (e.g. Microsoft's Ink Serializable Format (ISF)). Its specification defines a set of primitive elements for all basic ink applications. Furthermore, since it is an XML-based language, it is easily extensible to add application-specific information to suit the needs of the applications.

We present here the basic elements of InkML (see [START_REF] Chee | Ink Markup Language (InkML)[END_REF] for further details). The fundamental elements in InkML are traces (defined between <trace> elements, which are contained within a single <ink> element). A trace represents a sequence of contiguous ink points between a pen-down and a pen-up. Each point is represented by values depending on the pen's position, such as its X and Y coordinates (the <traceFormat> element describes the quantities that may be considered for the points and may also include the tip force or the angle). The following code shows an example of a simple InkML file containing the X and Y coordinates of the points of two traces: Information about the digitizer device can be recorded in the <inkSource> element and may include the sample rate, the resolution or the model of the device. The <context> element enables the ink context to be taken into account and may include information about the writer or about the graphical context (using the <brush> element to record the color and the width of the ink). InkML also allows logical regrouping of ink using either <traceGroup> or <traceView> elements referring to <trace> elements. These groups of traces can also be semantically labeled using <annotationXML> elements.

Furthermore, InkML allows digital ink to be represented into two styles. The streaming style is more appropriate for applications that deal with transmission of ink because it allows the ink to be considered as it is entered, relatively to a current state (context modifications are given according to this state). The archival style is more relevant for applications that store ink or process stored ink because the contextual information is separated from the traces (organized and annotated hierarchically).

Framework of an Ink Processor Based on InkML

In this section, we present the framework that uses the previously presented InkML elements to process digital ink.The ink processor consists of three modules to capture, render and interpret the digital ink (see Fig. 1). In a collaborative environment, each user has its own ink processor both to deal with its own digital ink and with the ink from the other users. These three modules are presented in the following sub-sections.

Ink Capturer

The aim of this module is to capture ink data from a digitizer and to represent these data in the Streaming InkML style by creating <trace> elements, where each point coordinates are generated according to the <traceFormat> element. This module also receives context change events from the Graphical User Interface (GUI) and generates <context> elements. Among these context events are changes on the width or color of the ink (that may be specified by the <brush> element). Other information may be useful for the interpretation of the ink data and may be added to the InkML format, like a change of mode (a mode corresponds to the nature of the ink which may correspond to gestures, annotations, texts, drawings or even to a search mode where the ink may be used as a request). Furthermore, in collaborative environments, useful information may include the ID of the ink owner or the protection level of the ink (eg public or private depending on if the data can be shared with other users). This InkML fragment shows examples of created context changes: <context id=''context1''> <brush id=''black15pen''><width>15</width><color>#FFFFFF</color> </brush> <mode type=''drawing''/> <owner id=''writer1''/> <protection>private</protection> </context> All these InkML generated elements are then sent to the ink interpreter module.

Ink Interpreter

The ink interpreter module receives ink data and context information both from the user and from the other users. It then sends its interpretation information to the renderer module as well as to the other users (which may depend on whether or not the ink is public). The aim of this module is thus to interpret the received ink using the corresponding context information, received as well. The interpretation process mainly consists in associating semantic information to the ink data like, for example, the type of the ink (corresponding to the previously mentioned modes). To do so, the ink interpreter module may use specific interpreter sub-modules like handwriting, gesture or drawing recognizers. This overall interpretation process can be done in a synchronous way, thus generating context elements for changes of modes, before sending the corresponding ink, as shown in the given fragment code (a change to a gesture mode has been detected by the interpreter and is sent before sending the ink traces): The interpretation can also be done in an asynchronous way, as a background process, and the interpretation results will thus refer to previously entered and displayed ink, using <traceView> and <annotationXML> elements, as shown below (previous trace referenced by ''#L1'' has been interpreted as an annotation):

<traceView id=''L7'' traceDataRef=''#L1''> <annotationXML type=''annotation''/> </traceView>
Moreover, in order to allow the ink and its interpretation to be further used, the corresponding information is stored in a database, after being converted to the Archival InkML style (using the conversion algorithm given in [START_REF] Keshari | Streaming-Archival InkML Conversion[END_REF]). Thus, when the search mode is activated, the entered ink can be used as a request to retrieve corresponding documents, with ink documents being converted back to the Streaming style (the database may also contained documents without ink data).

Ink Renderer

The aim of this module is to render ink on the display area of the device, using the information given by the interpreter module, from the current user as well as the other ones. Ink rendering is an important aspect of pen-based applications because a nonsatisfactory rendering, for a given user, may lead to a rejection of the corresponding application by this user.

To perform this rendering, <trace> elements sent by the interpreter module as well as <context> elements are processed; properties of the display device may also be taken into account to correctly render the ink. Furthermore, as the ink interpretation may be asynchronous, this module may also have to process <traceView> elements and thus change the rendering of already displayed ink data, according to the corresponding interpretation (ink data interpreted as annotations may be displayed with a different color, for example).

Conclusion and Future Works

In this paper, we have presented a framework based on the standard InkML format for representing digital ink in a collaborative context. We have focused more particularly on the representation of various context elements as well as on how to attach semantic information to the digital ink (the information being given by interpreter modules).

In future works, we will integrate the proposed framework in the Synchromédia collaborative environment to add pen-based functionalities into it. Given the domain applications, other extensions to InkML may also be needed. For example, we may want to further categorize annotations like in [START_REF] Wang | Parsing Ink Annotations on Heterogeneous Documents[END_REF] as well as to specify different types of indexes to add search functionalities on documents (containing or not annotations).

  <ink> <trace>10 0, 9 14, 8 28, 7 42, 6 56, 6 70</trace> <trace>282 45, 281 59, 284 73</trace> </ink>

Fig. 1 .

 1 Fig. 1. Ink processor framework.

  <context id=''context3''> <mode type=''gesture''/> </context> <trace>10 5, 10 7,...</trace>


Solen Quiniou
email: solen.quiniou@synchromedia.ca

Mohamed Cheriet
email: mohamed.cheriet@etsmtl.ca

Eric Anquetil
email: eric.anquetil@irisa.fr

Handling out-of-vocabulary words and recognition errors based on word linguistic context for handwritten sentence recognition

In this paper we investigate the use of linguistic information given by language models to deal with word recognition errors on handwritten sentences. We focus especially on errors due to out-of-vocabulary (OOV) words. First, word posterior probabilities are computed and used to detect error hypotheses on output sentences. An SVM classifier allows these errors to be categorized according to defined types. Then, a post-processing step is performed using a language model based on Part-of-Speech (POS) tags which is combined to the n-gram model previously used. Thus, error hypotheses can be further recognized and POS tags can be assigned to the OOV words. Experiments on on-line handwritten sentences show that the proposed approach allows a significant reduction of the word error rate.

Introduction

Most of the handwritten text recognition systems are using a closed vocabulary. While this is suitable for tasks like recognizing literary handwritten texts, it is not well-adapted for new applications like recognizing freeform notes written on a TabletPC [START_REF] Shilman | Discerning Structure from Freeform Handwritten Notes[END_REF] or on a whiteboard [7]. Indeed, for this task, the vocabulary is generally infinite due to the use of personal abbreviations. Thus, when using a recognition system with a closed vocabulary, it is interesting to add a mechanism to detect out-of-vocabulary words. On one hand, these words might be further reconsidered using a recognition based on sub-word units like characters or strokes, for example. On the other hand, as the OOV words are not correctly recognized, they are substituted by words from the vocabulary, which has been shown to cause recognition errors on neighboring words due to the use of language models [START_REF] Bisani | Open vocabulary speech recognition with flat hybrid models[END_REF]. Thus, detecting and processing the OOV words could also allow the correction of other recognition errors and increase the performance of the whole system.

In some handwritten text recognition systems like [START_REF] Vinciarelli | Offline Recognition of Unconstrained Handwritten Texts using HMMs and Statistical Language Models[END_REF], OOV words may occur but, to our knowledge, no strategy has been proposed to deal with them. Some recognition systems associate confidence scores to the output sentences to allow the rejection of some of the words. In [START_REF] Marukatat | Rejection Measures for Handwriting Sentence Recognition[END_REF], anti-letter models are used and, in [START_REF] Pitrelli | Confidence Modeling for Handwriting Recognition: Algorithms and Applications[END_REF], different confidence measures both at the letter and at the word levels are compared. Nevertheless, no linguistic information is used at the sentence level. A rejection strategy based on varying the weight of a language model (LM) is presented in [START_REF] Bertolami | Rejection strategies for offline handwritten text recognition[END_REF] and relies on the assumption that non-recognized words are more sensitive to this variation. Nonetheless, the handwritten texts do not contain OOV words.

In the field of speech recognition, most recognition systems deal with OOV words. Among approaches to detect and recognize these words are phone-based models [START_REF] Bazzi | Modelling Out-Of-Vocabulary Words for Robust Speech Recognition[END_REF] (with specific models that may depend on the category of the OOV words) or recognition systems based on sub-word units [START_REF] Bisani | Open vocabulary speech recognition with flat hybrid models[END_REF]. In [START_REF] Hillard | Compensating for Word Posterior Estimation Bias in Confusion Networks[END_REF], an approach based on word posterior probabilities computed on a confusion network is proposed to detect OOV words. Finally, works on tagging texts containing OOV words rely on POS categories which are used in conjunction with n-gram LMs to achieve better results [START_REF] Niesler | Category-Based Statistical Language Models[END_REF].

In this paper, we focus on the detection and on the postprocessing of OOV words in an on-line handwritten sentence recognition system. Since these words may also cause other recognition errors, our proposed approach allows the detection of different kinds of recognition errors (including OOV words) and is performed on output sentences given by our baseline sentence recognition system [START_REF] Quiniou | Word Extraction Associated with a Confidence Index for On-Line Handwritten Sentence Recognition[END_REF]. We thus extend our previous works [START_REF] Quiniou | Use of a Confusion Network to Detect and Correct Errors in an On-line Handwritten Sentence Recognition System[END_REF] using posterior probabilities as confidence scores on words of output sentences. We then use a classifier to identify the type of each error hypothesis thus detected. To allow the correction of errors that may be due to unrecognized neighboring words, we add a postprocessing step using a word-to-POS backoff LM whose aim is two-fold: improving the recognition of in-vocabulary words and associating OOV words with their POS category.

The remaining parts of this paper are as follows. In section 2, an overview of the whole recognition system is given. The proposed approach for detecting and characterizing error hypotheses is then presented in section 3. Section 4 describes the construction of the POS-based LM and its use to correct error hypotheses and to retrieve the categories of OOV words. Finally, experimental results are discussed in section 5 while section 6 draws some conclusions.

Recognition system overview

In this section, we present the different steps of our whole sentence recognition system (see figure 1). Given an input handwritten sentence, the sentence recognition system first builds a graph containing handwritten word segmentation hypotheses. To identify these hypotheses, a Radial Basis Function Network (RBFN) is used to classify inter-stroke gaps. A confidence index associated to each of these classification results is also used to create additional segmentation hypotheses (see [START_REF] Quiniou | Word Extraction Associated with a Confidence Index for On-Line Handwritten Sentence Recognition[END_REF] for further details). A Maximum A Posteriori (MAP) decoding is then performed on this graph to find the likeliest sentence Ŵ (called MAP sentence), using graphic and linguistic information on words as given by equation 1:

Ŵ = arg max W k score(S|W k ) + γ log [p(W k )] + δn k (1)
where score(S|W k ) is the score of the handwritten signal S for the given sentence W k , estimated by the recognition system: it combines graphic and lexicon scores given by our word recognition system [START_REF] Carbonnel | Lexicon Organization and String Edit Distance Learning for Lexical Post-Processing in Handwriting Recognition[END_REF]. The graphic score includes adequation measures between each character and its corresponding model as well as spatial and statistical information between characters and the lexicon score de-pends on edit operations performed during the lexical postprocessing step. p(W k ) is the a priori probability of the sequence W k , given by a bigram LM and n k is the number of words in W k . The weight γ is used to balance the influence of the LM against the score from the recognition system whereas δ controls the deletion and insertion of words.

Error hypotheses are then detected using the posterior probabilities of the MAP sentence words. A classifier is then used to characterize each so-detected error hypothesis into four types (OOVword, segErr, absErr and substErr). This whole approach is presented in section 3.

Finally, a post-processing step using a word-to-POS backoff LM is performed on the MAP sentence given the error hypotheses types. It allows the correction of some of the errors as well as the identification of the POS category of the OOV words (in figure 1, the OOV word is identified as an adjective). This is described in section 4.

Identification of OOV words and other recognition errors

In this section, we describe how error hypotheses are detected on MAP sentences and how they are further characterized into four different error types. Word posterior probabilities are computed on a confusion network representation of the word graph [START_REF] Mangu | Finding Consensus in Speech Recognition[END_REF]; figure 2 shows an example of a confusion network (edges in bold correspond to the MAP sentence). In this representation, nodes represent confusions between word hypotheses, for a given position in the input sentence, and adjacent nodes are linked by as many edges as word hypotheses and define confusion sets. Each word is associated with a posterior probability corresponding to the sum of the probabilities of all the graph paths that contain this word. The word posterior probabilities are computed as described in [START_REF] Quiniou | Use of a Confusion Network to Detect and Correct Errors in an On-line Handwritten Sentence Recognition System[END_REF].

The word posterior probabilities thus integrate graphic and linguistic information and can be used as confidence score on the words. To detect error hypotheses on a MAP sentence, we compare the posterior probability of each of its words to a learnt threshold σ err : words whose probability is below σ err are considered as error hypotheses. In fact, in our approach, we use the difference between the posterior probabilities of the considered MAP word and of the second likeliest word in the corresponding confusion set (in these sets, words are ranked according to these probabilities).

Characterization of error hypotheses

Now that error hypotheses have been detected, it is interesting to identify why the corresponding MAP word has not been correctly recognized and especially to know if it corresponds to an OOV word. Moreover, this characterization can further allow different strategies to try to correct these errors. Here, we considered four error types: (i) OOV words, (ii) segmentation errors i.e. the MAP word does not correspond to a correctly segmented part of the sentence, (iii) absent words i.e. the correct word does not appear in the confusion set where the word MAP belongs, and (iv) substitution errors i.e. the correct word appears in the confusion set but does not correspond to the MAP word (respectively named OOVword, segErr, absErr and substErr).

To categorize error hypotheses, we use a Support Vector Machine (SVM) with a gaussian kernel. SVMs have been chosen because of their efficiency and their capacity to deal with unbalanced classes (in terms of training examples). Here, we consider two sets of features. The baseline set corresponds to the one used in our previous work [START_REF] Quiniou | Use of a Confusion Network to Detect and Correct Errors in an On-line Handwritten Sentence Recognition System[END_REF] and includes 6 features: 3 for the considered MAP word and the same 3 for the second likeliest word of its corresponding confusion set. These 3 features are the posterior probability of the word, its normalized graphic score and its normalized lexicon score (see section 2 for a description of these two latter scores). In the extended set, 4 additional features are considered: the length of the MAP word, a boolean feature indicating if the word segmentation was initially created (or if it was additionally generated, as presented in section 2) and 2 boolean features indicating whether or not the neighboring words (on the left and on the right) are detected as error hypotheses. The two latter features were inspired by [START_REF] Hillard | Compensating for Word Posterior Estimation Bias in Confusion Networks[END_REF].

Identification of OOV word categories and correction of substitution errors

Error hypotheses are now reconsidered using a word-to-POS backoff LM; this post-processing only deals with substitution errors and OOV words. In this section, we describe how this LM is created and used to correct error hypotheses.

Adapting a POS-based LM to handle OOV words

Category-based LMs provides the probability of a word w i , given its previous words on the sentence and according to the classes of each word. When POS categories are considered, a word may belong to several ones because they represent the grammatical nature of the words which depends on the context of the word. Two approaches can be used to take into account the classes of words by either considering all the possible class sequences of a given word sequence or by only considering the likeliest class sequence.

Since we want to retrieve the classes corresponding to OOV words, we choose the latter approach. Equation 2 gives the probability of a word w i with its context h i :

p(w i |h i ) = max c i i-n+1 ∈Ci×...×Ci-n+1 p(w i |c i ) p(c i |c i-1 i-n+1 ) (2)
where n is the order of the LM, h i = w i-1 i-n+1 is the history of word w i and C j is the class set of each word w j .

To handle OOV words in the POS-based LM, POS categories for these words have first to be determined. One straightforward solution would be to allow these words to belong to any POS category but, since there are more than one hundred POS classes (see section 5), the computation of the whole sentence probability would be hardly manageable. To define the class set of OOV words, we allow them to only belong to open classes such as nouns, adjectives, verbs or adverbs. Indeed, since OOV words are in perpetual creation in a given language, they are most likely to correspond to one of these open classes words (as opposed to closed classes including determiners, pronouns, prepositions, conjunctions and auxiliary verbs, which are in a limited number in a given language). Now, for each OOV word, the probability in each of its classes has to be determined. As no a priori knowledge on belonging to one particular class is given, these probabilities are equal, as given by equation 3:

(∀w OOS ) (∀c i ∈ C OOS ) p c (w OOS |c i ) = K OOV (3)
where w OOV is an OOV word, C OOS is the class set for the OOV words and K OOV is a constant. Whereas the initial probabilities p(c i |c i-1 i-n+1 ) remain the same in the extended POS-based LM, the initial probabilities p(w i |c i ) have to be modified for the classes c i ∈ C OOV . Indeed, to ensure wj p c (w j |c i ) = 1 (∀c i ∈ C OOS ), the probability of each in-vocabulary word belonging to one of the C OOS classes is reduced according to the K OOV constant. The modified probability is given by equation 4:

p c (w i |c i ) = p(w i |c i ) - K OOV n i . ( 4
)
where n i is the number of in-vocabulary words in class c i .

Post-processing using a word-to-POS backoff LM

The aim of this post-processing step is both to correct substitution error hypotheses and to assign POS categories to OOV words. To do so, we use the POS-based LM previously presented and we combine it to an n-gram language model, based on [START_REF] Niesler | Category-Based Statistical Language Models[END_REF] (the whole LM is called word-to-POS backoff LM). Thus, we use the POS-based LM instead of the n-gram LM when the history of the current word w i contains at least one detected OOV word. The probability of a word w i is then given by equation 5:

p wc (w i |h i ) =    p w (w i |Φ(h i )) if w i-1 i-n+1 ∈ V n-1 p c (w i |Φ(h i )) else (5)
where V is the vocabulary, p w (.) is the probability given by the n-gram LM and p c (.) is the probability given by the POS-based LM. Φ(h i ) is the history reduced to the n ′ last words (n ′ ≤ n-1) so it does not contain any error hypotheses identifying as absent words or segmentation errors.

To use the probability defined by equation 5, we generate a simplified word graph from the MAP sentence, using the error types previously detected. Since segmentation errors are not taken into account, the segmentation of the MAP sentence is not reconsidered. In this simplified graph, words identified as segmentation errors or OOV or absent words are replaced by their error type whereas, for substitution errors, all the words of the corresponding confusion set are added to the graph. For other words of the MAP sentence, i.e. not detected as error hypotheses, only the MAP word is added to the graph. Finally, the path corresponding to the likeliest sentence is retrieved on this graph, using equation 1 where the word-to-POS backoff LM gives the probability p(W k ) for each sentence. Segmentation errors and absent words remain in this final sentence whereas OOV are replaced by their POS categories (see figure 1).

Experiments and results

In this section, we first describe the experimental setup and then we present the results of the experiments on the detection and characterization of error hypotheses as well as on the use of the designed word-to-POS backoff LM.

Experimental setup

The language models are built on the Brown corpus [START_REF] Francis | Brown Corpus Manual[END_REF] using the SRILM toolkit [START_REF] Stolcke | SRILM -An Extensible Language Modeling Toolkit[END_REF]. This corpus contains 52,954 sentences (1,002,675 words) where 46,836 sentences (900,108 words) were used to learn the LMs. For the POS-based LM, we use the tagged version of the Brown corpus, containing 145 POS tags. 25 of these POS tags were considered as possible classes for the OOV words.

The handwritten material consists of sentences written from 2,598 sentences of the Brown corpus (corresponding to the sentences not considered for the LMs learning). The training set includes 557 sentences (8,769 words) written by 25 writers (it is used to learn the SVMs, to tune the parameters σ err , γ, δ and to compute the word posterior probabilities) whereas the test set contains 460 sentences (7,080 words) written by 17 writers. The writers of the test set are different from those of the training set.

To consider OOV words, we use a lexicon reduced to the 5,000 most frequent words of the vocabulary closed on the Brown corpus (containing 44,101 words). The words of the handwritten sentences that do not belong to this lexicon are then considered as OOV words. Thus, the OOV word rate is 5.5% on the training set and 5.6% on the test set.

Detection of error hypotheses

The parameters used to compute word posterior probabilities are optimized toward the normalized cross-entropy (NCE), commonly used to measure the quality of confidence scores. With confidence values clipped at 0.05 and 0.95 (to avoid negative NCE values, as suggested by [START_REF] Hillard | Compensating for Word Posterior Estimation Bias in Confusion Networks[END_REF]), the NCE is 0.25. The difference between the posterior probabilities of the MAP word and of the second likeliest word is then used as a confidence score to detect error hypotheses. True Acceptance Rate (TAR %)

False Acceptance Rate (FAR %)

ROC curve for the detection of word error hypotheses.

Figure 3 plots the ROC curve for different thresholds σ err on this confidence score: it shows the compromise between correctly recognized words whose confidence score is above σ err (TAR) and error hypotheses whose confidence score is above σ err (FAR). The chosen threshold σ err = 0.3 corresponds to a 88.2% TAR and a 33.0% FAR and allows the detection of 71.4% of the OOV words.

Characterization into error types

Table 1 gives the rates of correct characterization of the detected error hypotheses into the four error types considered, using either the baseline or the extended feature set. These rates are given on the test set where only error hypotheses are considered (thus corresponding to the ground truth of a perfect detection step). Using the extended feature set highly improves the characterization of OOV words which are twice as less mistaken for absent words or segmentation errors than when using the baseline set. Furthermore, absent words are less mistaken for segmentation errors. Nonetheless, the characterization rate of substitution errors is slightly reduces (with more confusion with absent words or substitution errors). Finally, the global characterization rate, among all the error hypotheses, is 65.2% with the extended feature set and 49.2% with the baseline set.

Evaluation of the overall postprocessing strategy

Table 2 gives the word recognition rate as well as the word error rates on error hypotheses identified using the proposed approach and on residual errors (corresponding to error hypotheses not detected by the approach). Relatively to the baseline system (using only the MAPbased recognition approach), the recognition rate achieved with the error detection approach is decreased but the remaining word error rate is greatly reduced, corresponding to a 61.3% relative reduction. The detected error hypotheses are distributed as follows: 17.0% of segmentation errors, 30.9% of absent words, 40.2% of substitution errors and 11.9% of OOV words. When the post-processing step is added (using a 4-class LM based on POS categories, combined to the bigram LM used in the baseline system), the word recognition rate is increased by 5% thanks to the recognition of 42.5% of the substitution errors previously identified. Furthermore, the POS categories of 33.8% of the OOV words are correctly retrieved.

Conclusion

In this paper, we have presented an approach to identify word error hypotheses on sentences (given by a MAP recognition approach) and to further correct or associate them with their POS categories. Word posterior probabilities are used as confidence scores to detect error hypotheses and to characterize them into four types with an SVM (using also other features). A post-processing step using a word-to-POS backoff LM is then performed to correct substitution errors and to associate POS categories to the OOV words detected. This approach allows the reduction of the word error rate and the correct identification of the POS categories of some of the OOV words.

Future works will investigate using additional features to better characterize the error types. Furthermore, segmentation errors will be considered (using alternate segmentation hypotheses in the simplified word graph) as well as errors due to absent words. Moreover, POS categories of OOV words will be used to try to recognize these words (to select an appropriate lexicon, for example).

Figure 1 .

 1 Figure 1. Sentence recognition system.

3. 1 .Figure 2 .

 12 Figure 2. Example of a confusion network.

Table 1 . Characterization rates by error type.

 1

	Feature	OOV	Subst.	Absent Segment.
	set	words	errors	words	errors
	Baseline	18.8 % 62.5 % 63.9 %	41.8 %
	Extended 56.1 % 59.2 % 73.7 %	65.5 %

Table 2 . Recognition and error rates for the overall approach.

 2

	Strategy	Recognition Identified Residual
		rate	error rate error rate
	MAP	77.7 %	0.0 %	22.3 %
	Error ident.	68.4 %	23.1 %	8.5 %
	Error ident.	73.8 %	14.5 %	11.7 %
	+ correction