Benjamin Lecouteux

Pascal Nocera

Georges Linarès

SEMANTIC CACHE MODEL DRIVEN SPEECH RECOGNITION

Keywords: speech recognition, driven decoding, Latent Semantic Analysis, cache model

This paper proposes an improved semantic based cache model: our method boils down to using the first pass of the ASR system, associated to confidence scores and semantic fields, for driving the second pass. In previous papers, we had introduced a Driven Decoding Algorithm (DDA), which allows us to combine speech recognition systems, by guiding the search algorithm of a primary ASR system by the one-best hypothesis of an auxiliary system. We propose a strategy using DDA to drive a semantic cache, according to the confidence measures. The combination between semantic-cache and DDA optimizes the new decoding process, like an unsupervised language model adaptation. Experiments evaluate the proposed method on 8 hours of speech. Results show that semantic-DDA yields significant improvements to the baseline: we obtain a 4% word error rate relative improvement without acoustic adaptation, and 1.9% after adaptation with a 3xRT ASR system.

INTRODUCTION

Although n-gram models have demonstrated their efficiency in speech recognition systems, they are known to be able to capture, neither long-term dependencies nor semantic level information. Many papers addressed this issue in the past, mainly by modifying ngram probabilities according to long-term statistics or topic-specific models [START_REF] Rosenfeld | Two decades of statistical language modeling: where do we go from here ?[END_REF]. The main approaches are:

• The cache model: introduced by [START_REF] Kuhn | A cache-based natural language model for speech recognition[END_REF], it proposes to increase the probability of the words that have occurred recently. The assumption behind this model is that if a word is used in a context, then this word is likely to be used again.

• The trigger model, as explored by [START_REF] Rosenfeld | A maximum entropy approach to adaptive statistical language modeling[END_REF][START_REF] Ney | On structuring probabilistic dependences in stochastic language modeling[END_REF]: the long-distance dependency problem is addressed by interpolating n-grams with trigger pairs selected according to their mutual information. This approach could be thought of as a generalization of cache models.

• The topic mixture model: [START_REF] Gotoh | Topic-based mixture language modelling[END_REF][START_REF] Gildea | Topic-based language models using em[END_REF][START_REF] Singh-Miller | Trigger-based language modeling using a loss-sensitive perceptron algorithm[END_REF][START_REF] Chin | Word topical mixture models for dynamic language model adaptation[END_REF][START_REF] Martins | Dynamic language modeling for a daily broadcast news transcription system[END_REF] propose techniques to use mixtures of language models according to topics. The training data are partitioned into a small set of topic clusters, which are used for adaptation. [START_REF] Bellegarda | Exploiting latent semantic information in statistical language modeling[END_REF] introduce a framework for constructing language models by exploiting both local and global constraints based on Latent Semantic Analysis (LSA). This approach proposes to compute two models based on LSA and n-grams. The models are combined, which leads to the integration of semantic information in n-gram models, with respect to LSA-found topics.

• Combination between cache and mixtures models: In [START_REF] Clarkson | Language model adaptation using mixtures and an exponentially decaying cache[END_REF][START_REF] Iyer | Modeling long distance dependence in language: topic mixtures versus dynamic cache models[END_REF], the authors propose to combine these approaches to capture distant dependencies in language.

However, cache models lack robustness, because boosted words are depending on the current hypothesis: an error can easily spread. Furthermore, these models rely only on the past (current hypothesis history) and too many hypotheses can be made with all trigger pairs: they are not easy to tune. Topic-based language models generally estimate weights on a first pass transcription or current hypothesis, without special word confidence selection. Moreover, the main issue of these models is the topic selection/detection for training.

In these papers additional information provided by the ASR system itself (confidence measures etc.) is not used. More generally, confidence measures are used for acoustic models adaptation and unsupervised training, but not for language model adaptation. Some papers propose to use confidence measures for dynamically changing the weighting between the acoustic and the language model during the search process, depending on the confidence of the current language model history. In [START_REF] Fetter | Word graph rescoring using confidence measures[END_REF][START_REF] Wessel | Using word probabilities as confidence measures[END_REF], the authors use word confidence or posteriors directly into the graph exploration, which yields improvements in the system performance.

Our objective is to exploit all the potential of a first decoding pass into the next search process and to provide an unsupervised language model adaptation. We propose to apply a suitable cache model during the decoding process, exploiting both LSA information and previous pass confidence measures.

In this paper, we present an integrated method to drive an ASR system with its confidence measures associated to an LSA-cache model. Our strategy focuses only on words poorly recognized, in order to reduce the noise introduced. In a previous paper [START_REF] Lecouteux | Generalized driven decoding for speech recognition system combination[END_REF], we had proposed an algorithm which consisted in integrating the output of an auxiliary ASR system into the search algorithm of a primary system. We present an extension of this algorithm, devoted to the decoding process itself, by using the output of the first pass to drive the second pass according to word confidence scores and to the semantic information associated. The first section presents the entire system. In the second section, we present the experimental framework on 8 hours extracted from the ESTER campaign [START_REF] Galliano | The ester phase 2 evaluation campaign for the rich transcription of french broadcast news[END_REF]. The last section presents experiments on our semantic driven decoding. Finally, we conclude and suggest some potential applications and improvements.

INTEGRATED APPROACH: DDA DEVOTED TO LSA CACHE

The initial Driven Decoding Algorithm (DDA) consists in integrating the output of an auxiliary system in the search algorithm of a primary system. This integration relies on two steps. Firstly, the current hypothesis of the primary system and the auxiliary transcript are aligned by minimizing the edit distance. Then, linguistic probabilities are combined, according to posteriors and to an hypothesisto-transcript matching score. We propose to modify the DDA, in order to obtain an improved driven cache language model. The next sub-sections provide details on the system parts.

A* search algorithm in the Speeral system

The LIA speech recognizer is used as a primary system. It is based on the A* search algorithm operating on a phoneme lattice. The decoding process relies on the estimate function F (hn), which evaluates the probability of the hypothesis hn crossing the node n:

F (hn) = g(hn) + p(hn),
(1) where g(hn) is the probability of the current partial hypothesis up to node n, which results from the partial exploration of the search graph, and p(hn) is the probe that estimates the remaining probability from the current node n to the last node. In order to be able to take into account information resulting from the output of an auxiliary system, the linguistic part of g in ( 1) is modified according to the auxiliary hypothesis as described below.

Driven Decoding Algorithm

The Speeral ASR system generates word hypotheses as the phoneme lattice is explored. The best hypotheses at time t are extended according to the current hypothesis probability and the probe results.

In order to combine the information provided by the injected transcript Haux and the main search process, a synchronization point has to be found for each word node that the engine evaluates. These points are found by dynamically mapping the provided transcripts to the current hypothesis; this is accomplished by minimizing the edit distance between the provided transcripts and the current hypothesis. This process allows one to identify, in the injected transcript Haux, the best sub-sequence that matches the current hypothesis hcur. This sub-sequence, denoted by haux, is used for a new estimation of the linguistic score, according to posteriors φ(wi):

L(wi|wi-2, wi-1) = P (wi|wi-2, wi-1) 1-β .φ(wi) β β = 0 if wi does not belong to Haux (2)
where L(wi|wi-2, wi-1) is the resulting linguistic score, P (wi|wi-2, wi-1) the initial probability of the trigram, β an empirical fudge factor and φ(wi) is the confidence score of wi.

Confidence measures

For LSA-DDA, we use our own confidence measures. They are computed in two stages. The first one extracts low-level features related to the acoustic and search graph topology, and high-level features related to linguistic information. Then, a first bad word detection hypothesis is produced by a classifier that is based on the boosting algorithm. Each word from the hypothesis is represented by a feature vector composed of 23 features, that are grouped into 3 classes. We use acoustic features that consist of the acoustic loglikelihood of the word, the average log-likelihood per frame, the difference between the word log-likelihood and the unconstrained acoustic decoding score of the corresponding speech segment. The linguistic features are based on probabilities estimated by the 3gram language model used in the ASR system. We use the 3-gram probability, the perplexity of the word in the window, and the unigram probability. We also add an index that represents the current back-off level of the target word. The graph features are based on the analysis of the word confusion networks: the number of alternative paths in the word section and values related to the distribution of posterior probabilities in the word section.

We use a boosting classification algorithm in order to combine word features, as detailed in [START_REF] Moreno | A boosting approach for confidence scoring[END_REF]. The algorithm consists in an exhaustive search for a linear combination of classifiers by overweighting misclassified examples.

The classifier is trained on a specific training corpus, that was not included in the ASR system training. Each word from this corpus is tagged as not ok or ok word, according to the ASR system reference. The classification results in two classes for each word: not-ok words and ok words.

Confidence Error Rate is 19.5% on dev and 18.6% on test for a 0.5 score threshold, while Normalized Cross Entropy is respectively 0.373 and 0.282. A 0.85 threshold will be used for high confidence decision-making in the LSA module: 55% of good words are selected, with 2.7% of mis-selected words.

Latent Semantic Analysis module

Latent Semantic Analysis [START_REF] Bellegarda | Exploiting latent semantic information in statistical language modeling[END_REF] is a technique that allows one to associate words that tend to co-occur within documents with a semantic relation. The assumption is that co-occurring words within the same document are semantically related. LSA takes the vector space representation of documents based on term frequencies as a starting point and applies a dimension reducing linear projection. The mapping is determined by a given document collection and is based on a Singular Value Decomposition (SVD) of the corresponding term/document matrix.

In our system, a semantically consistent word sequence may be considered as unexpected by the ASR language model due to the limitations of the n-gram language models. Moreover, n-gram models are unable to take advantage of long-range dependencies in natural language.

In our experiments, Latent Semantic Analysis fields are trained on the corpus used for language model estimation. For better coverage, the entire corpus is lemmatized, and its vocabulary is limited to the ASR system lemmatized lexicon (about 33K words). Moreover, a stop-list removes all non relevant words.

When a word is requested, the LSA module returns the top 100 words associated to their LSA confidence score.

Word selection for LSA

In order to make the ASR system sensitive to good semantic fields, words are selected according to their confidence score. In the next experiments, the threshold is fixed to 0.85. At 0.85, about 55% of the corpus is selected, while the confidence error rate on the detected good words is about 3%. Then, for each selected word, the top 100 words are extracted with the LSA system. For each segment a bag of words is computed, in order to be used by the search algorithm.

DDA combination with LSA

Driven decoding is relevant in the context of our discussion, because a simple trigger LSA model introduces a lot of noise. Then, the system is driven by its previous hypothesis to avoid deviations for correct words. The LSA trigger is applied when the word confidence score of the previous hypothesis is less than 0.5: correct words are well preserved. Moreover, words associated to low confidence scores are undervalued: this allows the ASR system to explore other paths.

The final system, as detailed in Figure 1, works as an improved cache model. The LSA-DDA becomes:

φ(w i) ≥ 0.5 : j L(wi|wi-2..) = P (wi|wi-2..) 1-β .φ(wi) β β = 0 if φ(wi) belong to to Haux (3) φ(cwi) < 0.5 : j L(wi|wi-2..) = P (wi|wi-2..) 1-α .θ(wi) α α = 0 if θ(wi) not found in word bag
where L(wi|wi-2, wi-1) is the resulting linguistic score, P (wi|wi-2, wi-1) the initial probability of the trigram, β and α are empirical fudges factor, φ(wi) is the confidence score of wi word, cwi is the aligned word after history (wi-2, wi-1) in auxiliary transcript, and θ(wi) is the LSA score of wi.

The LIA broadcast news transcription system

The LIA broadcast news transcription system relies on the Speeral decoder and the Alize-based segmenter. Cross-word contextdependent acoustic models with 230k Gaussians are used. State tying is achieved by decision trees. The language models are classical 3-grams with a vocabulary of 65K words. The system runs two passes. The first one (3xReal Time) provides intermediate transcripts, which are used for MLLR adaptation. The second one is 3xRT or 10xRT, according to the level of pruning.

EXPERIMENTS

ASR system driven by its first pass

We have tested a second pass driven by the first one associated to confidence measures. The result was not surprising: the ASR system converges to the first pass and there is no significant change. This is because there are no alternatives proposed to the search algorithm.

LSA-cache without driven decoding

These experiments investigate the use of the LSA trigger without constraints. For each speech segment, a bag of words is associated.

We have implemented a simple cache: during the search process, each hypothesis word is searched for in the LSA packet. When a match is found, the word is boosted according to the LSA confidence score. Experimental results are not interesting, because a general degradation is observed, despite of the LSA-specific information.

One reason could explain this disappointing loss: too many words are boosted, and the introduced noise impacts on the final result. This aspect highlights the difficulty to easily tune a cache model.

LSA trigger with driven decoding

These experiments are carried out without performing any acoustic adaptation, with a 3xRT ASR system. The system uses the previous one-best hypothesis associated to confidence scores. The trigger process is only applied to low-confidence words. We expect to drive the system with correct words of the one-best hypothesis, while wrong words are potentially rescored with the LSA cache. The results reported in Table 1 show that a significant gain can be obtained using the LSA Driven decoding system. The Word Error Rate (WER) is reduced by 4% relatively, compared to the first pass: the DDA allows the LSA-cache model to focus only on previous errors. This strategy avoids the introduction of too much noise. We observe better improvement (5% relative) for the worst show.

Show

#Hours P1 3RT The LSA-DDA allows for significant improvements on the 3xRT system, especially on the RTM show. With the 10xRT system, the WER improvement is slight, except on RTM. Unlike others shows, RTM is a Moroccan broadcast news: the training data for the language model are derived from a French newspaper. Hence, the model coverage is lower for RTM. This aspect explains the most significant gains and shows the contribution of the LSA model.

CONCLUSION

We proposed a semantic-driven decoding that allows for the integration of the first pass of the ASR system into the search algorithm in order to apply a semantic cache model. Our strategy focuses a Latent Semantic Analysis (LSA) cache model only on previous errors: according to the confidence scores, the LSA cache is applied or not. Experiments show that this integrated LSA-driven decoding improves the initial system and complements the acoustic adaptation. The enrichment of the first pass with confidence scores is useful for fine-tuning the search algorithm, while LSA enrichment allows one to select alternative paths when confidence scores are low: the strategy can be likened to an unsupervised language model adaptation. Moreover, due to the driven decoding, the tuning for a well working system is light. Finally, this method allows for a gain of 4% of relative WER on the first pass without acoustic adaptation, 1.9% on the 3xRT system, after acoustic adaptation and 1.1% on the 10xRT system. Nevertheless, these results show that the strategy is interesting for the 3xRT system where the WER is close to the 10xRT baseline system, resulting in a highly reduced computational cost. Moreover, the most constant gains are observed with the show farthest from training datas.

Presently, these experiments are limited to the segment granularity. We plan to extend this approach to sets of segments (discussion between two speakers, etc). We also plan to integrate external semantic data, such as abstracts of spoken documents, or meta-data (titles, speaker, etc.). Furthermore, we would also like to apply this method to more particular domains (e.g. medical surgeries)

Fig. 1 .

 1 Fig. 1. Principle of the LSA Driven Decoding Algorithm

Table 1 .

 1 LSA

			P2 3RT P2-LSA DDA 3RT
	Classique 1h	21.4 % 20.8 % 20.9 %
	Culture	1h	34.0 % 31.9 % 33.3 %
	INTER	1h	22.7 % 22.0 % 21.6 %
	INFO	2h	25.8 % 24.6 % 25.0 %
	RFI	1h	28.6 % 26.0 % 27.1 %
	RTM	2h	35.4 % 32.3 % 33.6 %
		-driven decoding without acoustic adaptation: Base-
	line first pass (P1 3RT), baseline second pass with acoustic adapta-
	tion (P2 3RT) and second pass with LSA cache-model driven by the
	first pass (P2-LSA DDA 3RT) without acoustic model adaptation
	4.4. LSA-DDA and acoustic adaptation (3xRT)
	These experiments combine acoustic adaptation for the second pass
	(3xReal Time) with LSA-driven decoding. These experiments test
	the complementarity of LSA-DDA with the acoustic adaptation. Re-
	sults are reported in Table 2: the WER is reduced by 1.9% relative,
	but less than without acoustic adaptation. LSA driven complements
	the Maximum Likelihood Linear Regression (MLLR) process, as a
	language model adaptation. We observe again better improvement
	(4.6% relative) for the worst show.
	4.5. LSA-DDA and acoustic adaptation (10xRT)
	These last experiments test the system with full graph exploration in
	second pass (10xRT). Results are reported in Table 3: the WER is re-
	duced by only 1.1% relative: the complementarity between acoustic
	model adaptation and language model adaptation is small. However,
	the worst show present a 3.8% relative improvement. These results
	show that LSA-DDA strategy is more interesting in the context of a
	3xRT ASR system where results are very closed to the 10xRT ASR
	system.

Table 2 .

 2 Baseline

		second pass 3xRT (P2 3RT), LSA-driven decoding
	with acoustic adaptation 3xRT (P2-LSA DDA 3RT)
	Show	#Hours	P2 10RT P2-LSA	P2-LSA
				DDA 3RT	DDA 10RT
	Classique 1h	20.2 %	20,5 %	20.0 %
	Culture	1h	31.7 %	31.8 %	31.5 %
	INTER	1h	21.6 %	21.6 %	21.6 %
	INFO	2h	24.0 %	24.5 %	23.9 %
	RFI	1h	25.4 %	25.5 %	25.3 %
	RTM	2h	31.7 %	30.8 %	30.5 %

Table 3 .

 3 Baseline

	second pass with acoustic model adaptation
	10xRT (P2 10RT), LSA-driven decoding with acoustic adaptation
	3xRT (P2-LSA DDA 3RT), LSA-driven decoding with acoustic
	adaptation (P2-LSA DDA 10RT)

This research is supported by the ANR (Agence Nationale de la Recherche), AVISON project.


Benjamin Lecouteux
email: benjamin.lecouteux@univ-avignon.fr

Raphaël Rubino
email: raphael.rubino@univ-avignon.fr

Georges Linarès
email: georges.linares@univ-avignon.fr

Improving back-off models with bag of words and hollow-grams

Keywords: language model, low-order interpolation, backoff

Classical n-grams models lack robustness on unseen events. The literature suggests several smoothing methods: empirically, the most effective of these is the modified Kneser-Ney approach. We propose to improve this back-off model: our method boils down to back-off value reordering, according to the mutual information of the words, and to a new hollow-gram model. Results show that our back-off model yields significant improvements to the baseline, based on the modified Kneser-Ney back-off. We obtain a 0.6% absolute word error rate improvement without acoustic adaptation, and 0.4% after adaptation with a 3xRT ASR system.

Introduction

Although n-gram models have demonstrated their efficiency in speech recognition systems, they are known to be correlated to the Word Error Rate (WER) in the case of unseen events [START_REF] Berdy | Confidence metrics based on n-gram language model backoff behaviors[END_REF]. The smoothing n-gram model was developed in order to solve the issues associated to the sparse training data. The back-off model addresses this problem by discounting the probability of low-count events and distributing the freed probability mass among unseen events. Many back-off methods have been proposed: additive smoothing [START_REF] Lidstone | Note on the general case of the bayes-laplace formula for inductive or a posteriori probabilities[END_REF], which assigns the same probability to all unseen words that follow a particular history; loworder back-off [START_REF] Katz | Estimation of probabilities from sparse data for the language model component of a speech recognizer[END_REF] and low-order interpolation [START_REF] Kneser | Improved backing-off for m-gram language modeling[END_REF].

In [START_REF] Chen | An empirical study of smoothing techniques for language modeling[END_REF] the authors present an empirical study of smoothing techniques; this work shows that Kneser-Ney and their modified Kneser-Ney smoothing outperform all other algorithms. However, traditional back-off models tend to overestimate some events: [START_REF] Rosenfeld | Improvements in stochastic language modeling[END_REF] propose different ways to tackle this issue, by recalculating back-off and interpolating trigger pairs with the language model.

In [START_REF] Schwenk | Connectionist language modeling for large vocabulary continuous speech recognition[END_REF], the authors address the back-off problem by carrying out the values estimation in a continuous space, allowing for a smooth interpolation of the probabilities. Then, a better generalization to unknown n-grams is expected. However required computations are prohibitive and many optimization techniques are necessary.

Other approaches are based on word similarity. The word similarity is used for language modeling by [START_REF] Rosenfeld | A maximum entropy approach to adaptive statistical language modeling[END_REF], as a constraint in a maximum entropy model which reduces the perplexity and the WER on the test set. However, this model is more adequate for capturing long-distance language dependencies, rather than short dependencies.

In [START_REF] Brown | Class-based n-gram models of natural language[END_REF], the authors use a word similarity measure for language modeling in an interpolated model, grouping similar words into classes. Another approach [START_REF] Zitouni | Backoff hierarchical class n-gram language models: effectiveness to model unseen events in speech recognition[END_REF] is the back-off estimation based on hierarchical class n-grams. This method allows one to use a hierarchy of classes that lead to a better estimation of the likelihood of unseen events, based on syntactic This research is supported by the ANR (Agence Nationale de la Recherche), ASH project (ANR-09BLAN-0161-02).

or semantic groups. Unfortunately, class-based and similaritybased methods require prior knowledge on the words.

However, all these proposed methods do not take into account the errors generated by the Automatic Speech Recognition (ASR) system itself, and the back-off values are not context-dependent. For example, with a Kneser-Ney back-off, the unseen 3-grams: "explosion de pneu" [tire explosion] = α(explosion de)p(de pneu) and "explosion de peu" [explosion of minor] = α(explosion de)p(de peu) share the same α() backoff value. We assume that it is necessary to sort this type of back-off out according to their short context (3-gram).

In the approach introduced by [START_REF] Dagan | Similarity-based models of word cooccurrence probabilities[END_REF], the authors propose a similarity-based model to assign probabilities to unseen 2grams. They use similar 2-grams computed on the corpus itself, without relying on taxonomic information. Their approach allows one to improve a Katz back-off model, using for each word a list of similar words. However, some additional disambiguation process is required for unseen or low-frequency events.

In [START_REF] Bilmes | Factored language models and generalized parallel backoff[END_REF], the authors introduce Factored Language Models (FLM), where the probability model can be seen as a directed graphical model. A back-off graph is introduced (parallel backoff) allowing to take many paths depending of each gram. This parallel back-off is presented as a generalization of the standard back-off equation. These models allow to compute several back-off paths; then the back-off can be based on linguistic knowledge, a statistical criteria or a combination of multiple paths. Our work lies in this approach where several back-offs compete.

In this paper we propose a simple and efficient back-off model, based on word co-occurrences and distant-gram models (introduced in this paper as hollow-gram model). Our method can be applied easily to traditional n-gram language models. In the first section we present our approach. In the second section, we present the experimental framework. Experiments on our back-off model are presented in the last two sections. Finally, we conclude and suggest some perspectives.

Proposed approaches

In [START_REF] Berdy | Confidence metrics based on n-gram language model backoff behaviors[END_REF], the correlation between back-off behavior and WER is proven. The table 1 contains the WER arising from the specific back-off on training corpora. The language model coverage is obviously not the only issue, but a biased language model built with tests data improves dramatically the recognition.

Currently, in state-of-the-art ASR systems, the most popular back-off model is the (modified) Kneser-Ney, which outperforms other smoothing techniques. However, the classical smoothing algorithms do not take into account the shortcontext, as the example presented in introduction. We propose alternative measures allowing to determine the likelihood of a word combination.

We also propose to regulate the back-off values against the possibility of the unseen events: our method is used to check if a word sequence exists. In the case of unobserved word cooccurrences, the value is slightly altered.

The backoff is then re-estimated according to the equation:

α(wi-n, .., wi) = α(wi-n, .., wi-1) 1-β p φ (wi-n, wi) β
Where α is the updated back-off value, α is the initial back-off value, p φ (wi, wi-n) is the smoothing back-off function based on co-occurrence (section 2.2) or hollow-gram (section 2.1). p φ (wi-n, wi) = δ if (wi, wi-n) co-occurrence is unobserved. β is an empirical fudge factor and δ is an empirical penalty value based on the binary possibility of the current ngram. β and α are tuned with a grid based approach on the dev corpora. We introduce the hollow-gram-based model paradigm in the next section. In the case of a 3-gram model, the probability p(w3|w1, w2) of an unseen words sequence (w1, w2, w3), is computed with the back-off value of (w1, w2), and the conditional probability of p(w3|w2). This method considers an independence assumption on the co-occurrence of w3 and w1. We introduce a hollow-gram model p φ (w3|w1) providing an alternative to the independence assumption, allowing relationship between shortdistant words. The method is handy: a 2-gram model based on the pairs (start, end) of each 3-gram is trained. This model can be assimilated to a regular expression: (w1, * , w3) where * is an unobserved word.

In the case of an unseen event, the model backs off on a 2-gram using the back-off value: p(w3|w1, w2) = α(w1, w2)p(w3|w2). With our hollow-gram model, the equation becomes: p(w3|w1, w2) = α(w1, w2) 1-β p φ (w3|w1) β p(w3|w2) [START_REF] Berdy | Confidence metrics based on n-gram language model backoff behaviors[END_REF] Where p(w3|w1, w2) is the resulting updated probability of the 3-gram, α(w1, w2) is the initial back-off value of the word pair (w1, w2), p φ (w3|w1) is the hollow-gram probability and β is an empirical fudge factor. However, in our hollow-grambased model, back-off always depends on observed events. Then, we propose a generalization to improve the prediction of the back-off on unobserved events.

Back-off using word co-occurrence

The main idea in the word co-occurrence approach is to combine a word association score to the back-off based on classical n-gram language model. A number of measures have been proposed in the past to evaluate the strength of word cooccurrences. For example, based on mutual information, conditional probabilities or standard statistical measures like the chi-square. In this work, we decide to use the likelihood ratio proposed by [START_REF] Dunning | Accurate methods for the statistics of surprise and coincidence[END_REF]. This measure is theoretically the most appropriate with sparse data, and can be used to find pairs of words that occur next to each other with a significantly higher frequency than it would be expected. It allows us to eliminate word frequency effects and to emphasize relations between significant word co-occurrences. The log likelihood ratio between two words wa and w b is described in equation 2.

ψ(wa; w

b ) = ij∈{1;2} log kijN CiRj = k11log k11N C1R1 + k12log k12N C1R2 + k21log k21N C2R1 + k22log k22N C2R2 (2)
Where: In order to count the co-occurrences of two words, we use a sliding window of a fixed size s. In our experiments, the windows size is fixed to five words. Word ordering in the window is not taken into account, it can be seen as a bag of words. However, we weight the count of co-occurrences of wa and w b by the number of words between them in the window:

C1 = k11 + k12, C2 = k21 + k22 R1 = k11 + k21, R2 = k12 + k22 N = k11 + k12 + k21 + k22 k11 = count
k11 = 1 d(wa;w b ) k11.
The log likelihood ratio is computed with all the lexicon on the whole corpora. Then, values are normalized in order to compute probabilities. The obtained model p ψ () is used to weight back-off, as in equation 1. Unlike the hollow-gram model, this approach can be applied to all back-off (2-gram and 1-gram), and in the case of a full back-off behavior the updated probability of the 3-gram becomes: p(w3|w1, w2) = α(w1, w2) 1-β p ψ (w1, w3) β α(w2) 1-β p ψ (w2, w3) β p(w3)

Where α(w1, w2) is the initial back-off value of the words, β is an empirical fudge factor and p ψ () is the back-off smoothing function based on word co-occurrences obtained by equation 2.

Combination of word co-occurrence and hollow-gram model

Naturally, our hollow-gram model is unable to work on unseen values, but its strength lies on observed events. However, in the case of unobserved events, we propose to back-off on word co-occurrences. Then the model is based on a double back-off depending on fuzzy-observed events:

α(w1, w2) = α(w1, w2) 1-β p φ (w3|w1) β if h-gram exists α(w1, w2) 1-β p ψ (w1, w3) β else (4)

Compact model approach

The drawback of the co-occurrence method is the memory consumption (the co-occurrence matrix size is |V | 2 2 where V is the vocabulary size). In order to tackle this issue, we propose a low-memory model version of our approach, based on the binary existence of words co-occurrences. If wa and w b have been observed in the window, the back-off is used as such, else a penalty is applied.

Experimental framework 3.1. The LIA broadcast news system

Experiments are carried out by using the Laboratoire Informatique d'Avignon (LIA) broadcast news (BN) system which was used in the ESTER evaluation campaign [START_REF] Galliano | The ester 2 evaluation campaign for the rich trancription of french radio broadcasts[END_REF]. This system relies on the HMM-based decoder developed at the LIA: Speeral [START_REF] Linares | The lia speech recognition system : from 10xrt to 1xrt[END_REF]. Speeral is an asynchronous decoder operating on a phoneme lattice; acoustic models are HMM-based, context dependent with cross word triphones. The language model is a classical 3-gram model, estimated on about 1,3G words from the French newspaper Le Monde, the ESTER broadcast news corpus (about 1M words) and Gigaword corpus, without cuts. The lexicon contains 86K words. In these experiments, the first pass is performed in 3x Real Time (RT), while the second one is assessed after an MLLR acoustic adptation in 5xRT.

The ESTER-2 corpus

The

Results

Throughout experiments, we present three results facets. The first one is the classical WER, while the second is the SER and the last one is the CWR. Using this new back-off, the language model dynamics is altered. In our case, we observe especially an increase of insertions. The CWR allows us to show the real rate of corrected words, and the real impact of our approach.

Back-off based on hollow-grams

This approach is based on unobserved unigram in a 3-gram (w1, * , w3). The order of the words in the 3-gram is taken into account. This model has two advantages: it allows one to use a regular expression based model and to capture hollow-grams events into the training corpora. Results of the hollow-grambased back-off are reported in Table 3. These first results show a slight improvement both on WER and CWR, compared to the classical back-off. We can see that global CWR improvement is twice the WER improvement. These results show that the new back-off corrects a lot of errors, but also introduce new ones.

These experiments show that a simple reordering of the back-off values allows one to improve the language model behavior: the back-off weighting disambiguates close assumptions (in terms of back-off values). However, because of the model topology, it is applied only on 2-gram back-offs. In the next section, we present the results based on word cooccurrence.

Back-off based on word co-occurrences

In these experiments, we combine the back-off values with the word co-occurrence probabilities. In practice, a word cooccurrence symmetric matrix (order is not taken into account) is built on the whole training corpora, using the method presented in section 2.2 with a window size of five words. In order to compute probabilities, we normalize the values. Then, we interpolate them with the initial modified Kneser It seems that this approach leads to a higher WER and SER improvement compared to the previous one, based on the hollow-gram model. This may be due to the fact that the method is applied both on 2-gram and unigram back-offs. Once more, this handy model is able to improve a classical back-off. In the next section, we propose to combine the two methods.

Combination of word co-occurrences and hollowgrams

In these experiments, we propose to test the complementarity of the hollow-gram and the word co-occurrence models. The hollow-gram model is used if (w1, * , w3) exists. In other cases, the co-occurrence model is applied as presented in section 2.3. Results of the combination are reported in Table 5. We observe a significant improvement of the results compared to the two previous methods individually. These results show the complementarity of the two models.

Shows

Compact model approach

The compact model depicts the binary possibility of a back-off. This binary possibility is computed from the co-occurrence matrix: if the value is not null, we consider as true the possibility of the combination. Results of our compact model are reported in Table 6 As expected we observe a degradation of the results compared to the combination approach. Nevertheless, with one bit per word-pair, the original back-off is slightly improved.

ASR system behavior and second pass

In this section, we propose to analyze the global behavior of our new language model in its best configuration. Table 7 shows insertions, substitutions and deletions on the whole test. We observe that the substitution rate is kept while the insertion rate increases highly and the deletion rate decreases. Globally, we observed that CWR improvement is twice the WER improvement: the high insertion rate shows an issue that can be handled by an accurate stop-list and a higher word penalty. Further investigations are required to understand the model behavior. This aspect show that we don't use in an optimal way our back-off model, and some tuning is possible.

After this set of experiments, we have tested several β values in order to maximize gains both on train and test data, with our co-occurrence and hollow-gram models individually. We observe important disparity on the results (sometimes slightly better than ones resulting from models combination) without stability. However, with the model combination, a better robustness of the ASR system is observed. We propose to apply our back-off model on the secondpass, using the first-pass transcript (Table 5) for MLLR adaptation. Results are reported in We observe an improvement on the three shows: this aspect highlights the reliability of our approach, a simple back-off values reordering can improve a Kneser-Ney based model.

Show

Conclusion and future work

In this paper, we propose a new back-off model based on hollow-gram and word co-occurrence models. The proposed back-off is relevant with classical n-gram language models, without major changes. It consists in interpolating a classical (Kneser-Ney) back-off model with word co-occurrence probabilities and a model based on distant 2-grams (w1, * , w2) (hollow-grams).

  of co-occurrences of word wa and word w b k12 = count of occurrences of word wa -k11 k21 = count of occurrences of word w b -k11 k22 = count of tokens in the corpus -k12 -k21 + k11

7 Table 3 :

 73 WER, SER, CWR using the hollow-gram-based model

Table 1 :

 1 WER according to the back-off level

	case of back-off	1-best
	3-gram exists	17.7%
	back-off 2-gram	28.5%
	back-off 1-gram	50.0%

2.1. Back-off based on hollow-gram model

Table 2 :

 2 ESTER-2 corpus consists of French radio broadcasts of the Radio-France group. The training and development parts of the data set are based on the training corpus provided for the ESTER-2 (100 hours manually annotated) evaluation campaign.We test our approach on 6 hours of speech, extracted from the ESTER-2 test set. The mean baseline WER is 30,4% in the first pass and 27.3% after the MLLR adaptation. Mean results are normalized by the number of words per show. Baseline WER, SER and CWR Table2contains the baseline Word Error Rate (WER), Sentence Error Rate (SER) and Correct Word Rate (CWR). By using these three measures, we observe the global behavior of the ASR system. We present the shows separately in this Table, because each of them depicts different performance of the ASR system: journalistic speech for the RFI show while the INTER and TVME shows contain more spontaneous speech (phone calls).

	Shows	WER	SER	CWR
	Inter (4h)	33.1	75.0	69.7
	Tvme (1h)	31.3	67.6	71.2
	Rfi (1h)	18.7	66.6	84

Table 4 :

 4 -Ney backoff model. This model is applied both on 2-gram and unigram back-offs. Results of the co-occurrence-based back-off are reported in Table 4. WER, SER, CWR using the co-occurrence-based model

	Shows	WER	SER	CWR
	Inter (4h)	32.7 (-0.4)	74.5 (-0.5)	70.5 (+0.8)
	TVME (1h)	31.0 (-0.3)	66.8 (-0.8)	71.8 (+0.6)
	RFI (1h)	18.4 (-0.3)	65.6 (-1)	84.5 (+0.5)
	Mean	-0.4	-0.6	+0.7

Table 5 :

 5 WER, SER, CWR using combination between cooccurrence-based back-off and hollow-gram models

		WER	SER	CWR
	Inter (4h)	32.4 (-0.7)	74.6 (-0.4)	70.8 (+1.1)
	Tvme (1h)	30.9 (-0.4)	67.2 (-0.4)	72.0 (+0.8)
	RFI (1h)	18.4 (-0.3)	65.6 (-1.0)	84.5 (+0.5)
	Mean	-0.6	-0.5	+0.9

Table 6 :

 6 . WER, SER, CWR using the compact back-off model

	Shows	WER	SER	CWR
	Inter (4h)	32.7(-0.3)	74.8(-0.2)	70.3(+0.6)
	Tvme (1h)	31.1(-0.2)	67.5(-0.1)	71.6(+0.3)
	Rfi (1h)	18.6(-0.1)	65.7(-0.9)	84.2(+0.2)
	Mean	-0.25	-0.3	+0.5

Table 7 :

 7 Behavior of insertions, substitutions and deletions

		ins	del	sub
	baseline	2.73	8.58	18.86
	combination	3.14	7.57	18.98
	GLOBAL	+15%	-12%	+0.6%

Table 8

 8

	Shows	basewerBC	baseser BC	basecwrBC
	Inter	30.4 29.9 73.1 72.3 72.2 73
	Tvme	25.3 24.8 62.8 62.5 77.8 78.6
	Rfi	17.0 16.9 64.4 64.0 85.6 86.1
	Mean	-0.4	-0.6	+0.7

Table 8 :

 8 WER, SER, CWR after the MLLR adaptation on the baseline (base) and the back-off model combination (BC)

We evaluate our method on 6 hours of French broadcast news, with many strategies. Changing only back-off implementation, this method allows for a 0.6% absolute gain of WER and 0.9% of correct word rate (CWR) on the first pass without acoustic adaptation. Also, a 0.4% absolute gain of WER and 0.7% of WCR on the second pass after acoustic adaptation. Better results are obtained using both the hollow-gram and the co-occurrence models.

We also present a compact version of our model combination, with very low memory consumption: one bit for each word pair possibility. This approach leads to a slight improvement of the classical back-off.

These preliminary experiments demonstrate that the representation of unseen events is not a fully-solved issue yet. We plan to extend this approach to more sophisticated heuristics/algorithms where co-occurrence values are depending on the word distances, and hollow-gram model extended to ngrams.


B Lecouteux
email: benjamin.lecouteux@univ-avignon.fr

G Linarès

Frédéric Beaugendre
email: frederic.beaugendre@voiceinsight.com

Pascal Nocera
email: pascal.nocera@univ-avignon.fr

Text island spotting in large speech databases

Keywords: speech recognition, closed captioning, corpus building

This paper addresses the problem of using journalist prompts or closed captions to build corpora for training speech recognition systems. Generally, these text documents are imperfect transcripts which suffer from the lack of timestamps. We propose a method combining a driven decoding algorithm and a fastmatch process allowing to spot text-segments. This method is evaluated both on the French ESTER ([4]) corpus and on a large database composed of records from the Radio Television Belge Francophone (RTBF) associated to real prompts. Results show very good performance in terms of spotting; we observed a Fmeasure of about 98% on spotting the real text island provided by the RTBF corpus. Moreover, the decoding driven by the imperfect transcript island outperforms significantly the baseline system.

Introduction

HMM based automatic speech recognition (ASR) systems require very large amounts of annotated training data, especially on LVCSR tasks where acoustic models are composed of several millions of parameters. Moreover, discriminative methods such as MMIE or MPE are now widely integrated in speech recognition systems. This kind of methods brings significant performance gains as far as sufficient amount of annotated data are available for model estimate. Thus, recent state-of-the-art ASR systems are typically based on corpora composed of more than 1000 hours of training data [START_REF] Prasad | The 2004 BBN/LIMSI 20xRT English Conversational Telephone Speech Recognition System[END_REF]. Such a constraint constitutes a major limit in applying speech technology to low resourced languages and might increase dramatically the cost of LVCSR systems construction.

Nevertheless, low cost transcripts could be available when text sources are associated to speech materials. Especially, the prompting or the captioning of broadcast news could provide approximated transcripts of large speech recordings.

Unfortunately, two major difficulties limit the use of prompts or closed captions as training corpora.

The first is that they are generally imperfect transcripts, as speakers may not strictly follow the prompter. [START_REF] Placeway | Cheating with imperfect transcripts[END_REF] reports about 10% WER (Word Error Rate) in TV closed captions; some authors proposed methods for taking advantage of these imperfect transcripts for acoustic models training or adaptation. [START_REF] Chan | Improving broadcast news transcription by lightly supervised discriminative training[END_REF] and [START_REF] Lamel | Lightly supervised and unsupervised acoustic models training[END_REF] have shown that lightly supervised adaptation to closedcaptions could improve significantly acoustic models precision. Previously, we proposed a Driven Decoding Algorithm (DDA) which is able to simultaneously align and correct the imperfect transcripts [START_REF] Lecouteux | Imperfect transcript driven speech recognition[END_REF].

The second problem is that closed captions usually suffer from both time lag due to the lack of post-synchronization on the audio material and that numerous speech segments of variable lengths are not prompted; this particularly occurs when speakers alternate between read talks (following a prompter for example) and more spontaneous comments or interviews (not transcribed).

This problem has been tackled by some authors under the more general topic of text-to-speech alignment ([3], [START_REF] Photina | Improving acoustic models with captioned multimedia speech[END_REF]). Most of the proposed methods rely on DTW algorithm where the available word utterance is synchronized to the outputs of a speech recognition system. Due to the intrinsic complexity of the DTW algorithm, these methods are efficient if the two following constraints are satisfied : (1) the size of speech segments to be processed must match the computer capabilities. This means that speech streams must be segmented into trackable parts into which the selected text map onto the corresponding speech signal; (2) a typical way to improve DTW efficiency consists in pruning paths which correspond to high temporal distortions between signal and transcript. These heuristics fail when large transcripts or speech segment are missed.

Other related works propose to solve this problem of presynchronization using multi-pass strategies. Reported results show a high efficiency in terms of alignment scores, at the cost of a relatively heavy iterative process.

In this paper, we address the problem of spotting of transcript islands, in the general framework of driven decoding methods.

The next section describes the proposed approach. We first present the principle of the driven decoding algorithm (DDA). Then, we focus on our fast-match algorithm for transcripts spotting. We show how this method deals with missing transcripts and we describe it's integration into the DDA global scheme Section 3 reports and comments experiments. We present the RTBF and ESTER databases on which the experiments are carried out; then, the proposed method is evaluated both in terms of transcript spotting and error corrections.

Finally, section 4 concludes and suggests new applications of the proposed method for spotting and correcting transcript island.

Spotting transcript Islands

Imperfect transcript Driven decoding

A driven decoding algorithm aims to align and correct imperfect transcripts by using a speech recognition engine. The algorithm proceeds in two steps. Firstly, the provided transcripts h p and the current hypothesis h c are synchronized by a DTW algorithm. When the anchorage points are found, an hypothesisto-transcript matching score is computed and used for linguistic rescoring. This algorithm improves dramatically the system performance by taking advantage of the availability of the approximative transcripts. Moreover, our evaluation on the ES-TER corpus has shown that driven decoding improves significantly the quality of the initial transcripts. Our previous experiments have shown that corrected transcripts outperforms the initial ones by about 25% relative WER.

Nevertheless, the lack of significant parts of transcripts causes failures in the search of anchorage points. Therefore, the algorithm is not really relevant for the spotting of text island in large speech records. A second experimental outcome shows that when the decoder is driven by irrelevant transcripts, the search algorithm slows down by a factor from 2 to 3, depending of the system configuration, while the WER remains unchanged.

In order to apply DDA to transcript island spotting we add a fast-match process which aims to find on-the-fly the transcript islands which are relevant to the current state of the search algorithm. This method is described in the next section.

Fast-match to transcript island

The goal of our method is to take advantage of imperfect transcripts when they are available, while no timing information is available for the localization of transcript island.

On the other hand, DDA is able to integrate, in the search algorithm, some information related to the prompts. The aim is to combine to DDA an island detector which would be able to decide, at each node of the search graph, when the recognizer is crossing a transcript island. As the search graph is developed dynamically, this must be achieved by an on-the-fly spotting process.

The principle of the proposed method is close to approaches used in the field of information retrieval. In our case, the hypothesis is a query which may be answered by one of the transcript island. Typically, search engines try to find the most relevant documents by comparing the query to the indexed collection of stored documents. Most of the algorithms consist in building a set of ranked document lists. Here, we follow a similar scheme, while focusing on the efficiency of the algorithm.

The lexicon is represented by a lexical space L s where each dimension is associated to a word. All documents, including the hypothesis itself, are represented in this lexical space by wordfrequency vectors. The coefficients of these vectors represent the frequencies of words in the document.

As the current hypothesis is developed, a set of word clusters Ci is built and updated. These clusters result from the intersection of h c and the transcript island I i . For each new word added to the hypothesis h c , transcript islands are considered as candidates for guiding the search. This competition is arbitrated by a matching score W i which is computed as follow :

Wi(hc) = | Ci(t) | | h c (t) | * n X i=0 Idf (wi)
where

| C i (t) | and | h c (t)
| are the cardinality of respectively the cluster C i and the current hypothesis h c . Idf (w) represents the classical measure of the relative word frequency :

idf (w) = 1 f requency w
Therefore, this matching score represents a level of similarity between the hypothesis and the transcript island considered. This measure takes into account the semantic weight of the word, which depends from it's relative frequency in the document.

If the higher weight is greater than an a priori fixed threshold, the algorithm considers that it is on a transcript island and the search algorithm is driven by the corresponding word utterance.

Figure 1: Scheme of principle of spotter integration to Driven decoding. Transcript island are detected by the spotter which compute an hypothesis-to-island matching score. According to it, the spotter set the decoder in driven decoding mode. Then, linguistic probabilities are rescored according to the guiding word-utterance.

Experiments

Experimental framework

The LIA broadcast news system

Experiments are carried out by using the LIA broadcast news (BN) system which was used in the ESTER evaluation campaign. This system relies on the HMM-based decoder developed at the LIA (Speeral, [START_REF] Nocera | The LIA's French broadcast news transcription system[END_REF]). The segmentation tools come from the Alize toolbox ( [START_REF] Bonastre | ALIZE, a free toolkit for speaker recognition[END_REF]).

Speeral is an asynchronous decoder operating on a phoneme lattice; acoustic models are HMM-based, contextdependent with cross word triphones. These models are composed of about 230000 gaussian components and 3600 tied states estimated on the ESTER materials (about 80 hours of annotated speech).

The language models are classical trigrams estimated on about 200M words from the French newspaper Le Monde and from the ESTER broadcast news corpus (about 1M words).

The full BN system runs two passes. The first one provides intermediate transcripts which are used for MLLR adaptation.

The first pass takes about 3xRT and the second one about 5xRT on a standard desktop computer (with an Opteron at 2Ghz). In these experiments, only one pass is performed, according to our initial goal of a fast word-sequence spotting. Moreover, experiments show that driving the decoding during the first pass allows to reach performance close to the one obtained by performing 2 passes [START_REF] Lecouteux | System combination by driven decoding[END_REF].

Evaluation corpora

Two corpora are used for evaluation. The first one is based on the corpus provided for the ESTER evaluation campaign; we modified transcripts in order to simulate the fragmented closed captions which correspond to the targeted task. The second corpus is a real-world database composed of recording of RTBF broadcasts in which some segments were prompted.

ESTER corpus

The first test is based on the corpus provided for the ESTER evaluation campaign. The ESTER corpus consists of French radio broadcasts of the Radio-France group. It has been designed to evaluate transcription systems; therefore, it contains high quality transcripts, as opposed to the RTBF database.

ESTER broadcasts are essentially composed of news; nevertheless, some segments are recorded in more difficult acoustic conditions, such as ad-hoc interviews, talk of non-native speakers, on-the-fly translations... We use a test corpus composed by 3 hours from the ESTER development set. Imperfect transcripts are generated by adding errors manually in the initial transcripts, while ensuring a correct journalistic form in order to respect the traditional style of a radio broadcast: 10% WER is introduced in 2 hours of transcripts, and 20% WER in the last one. Moreover, about 50% of transcript segments are removed in order to simulate the lack of transcript parts.

RTBF corpus

The second corpus has been collected in the framework of the AIDAR project ([?]). It contains about 1000 hours of radio programs from the Radio Television Belge, in French and mostly recorded under clean conditions. Those programs mainly consist of news whose topics and linguistic style are rather close to the ones of the ESTER corpus. Among those 1000 hours, prompts (provided in XML files) are available for about 60 hours of news program and the proportion of actual speech exceeds 300 hours. These prompts were effectively used by the journalists. No further refinement on transcripts was done after recording and no timestamp is available in order to precisely locate the speech segments corresponding to the provided transcripts. In order to evaluate our algorithm on this database, we have manually annotated he timestamps related to prompted segments for 11 hours of the corpus.

Results

These experiments aim to evaluate the performance of the proposed method for building a speech corpus of decent quality using the closed-captions associated to the speech signals. The system performance on the spotting task is evaluated in terms of precision/recall rates, on ESTER and RTBF corpora. Fmeasures are also reported.

We first test alignment and correction performed on the ES-TER corpus, using the exact and the degraded transcripts. Then, we consider the WER of corrected transcripts, according to the quality of text sources involved in the decoding process. Finally, we evaluate our method on the RTBF corpus based of real close captioning.

Spotting exact transcript island on ESTER database

Here, we evaluate the performance of our spotter using the exact transcript. The removed transcripts have been chosen according to the reference speech segmentation, by deleting randomly 50% of the speech segments. The average duration of remaining segments is about 6 minutes.

Results are reported in Table 1. We can see that, in these simulated conditions, spotting performance is good; more than 95.3% of segments have been found, with a precision of about 96.7%. Results seem relatively independent from the performance of the ASR systems which are varying, in this test, from 27.2% (RFI show) to 22.6 (France Inter show).%.

Radio station

Spotting imperfect transcripts on ESTER database

The second experiment aims at evaluating how errors in transcript impact the system performance. Results are reported in Table 2. We observe that the obtained precision and recall rates are very close to the ones obtained on perfect transcripts. Nevertheless, this experiment is achieved by setting a transcript word error rate of about 10%; this rate corresponds to the one reported in the literature (about 10%). A strong increase of transcripts WER should impact dramatically the spotter performance. An extreme situation would consist in submitting to the spotter a totally erroneous transcript, in which no information could allow spotting.

Radio station

Transcript island Driven decoding

DDA method allows to improve recognition rates by taking benefit of the available transcripts, even if they are not perfect.

Here, we evaluate the quality of transcripts provided by the Speeral decoder guided by the transcripts themselves. Three tests have been performed and compared to the baseline system. This last one consists in a classical Speeral run, without any helpful transcript. We first evaluates WER by using segments of exact transcripts; then, the same experiment is achieved on imperfect transcripts. Results are reported in Table 3 Results show that the driven recognizer takes advantage of spotted transcripts. Of course, the correct prompts remain more efficient that imperfect ones; nevertheless, approximative transcripts bring a WER gain of about 14% relative, while exact ones allows a WER gain close to 24% relative. Here, we test our spotting technique on the RTBF database. Experiments are performed on the 11 hours on which time stamps were manually added. The estimated WER of RTBF transcripts is lower than 5% while the base is only partially annotated, the quality of transcripts remains relatively high.

Spotting real prompts on RTBF corpus

Results are quite good, and significantly better than the ones observed on the ESTER corpus. 10 from the 22 (of 30 minutes each) audio segments are fully timestamped, and the averaged F-Measure is around 98%. These better results are probably due to the fact that the prompts mapping is usually related to the global structure of the document, including speaker and speech/non-speech turns, etc. Then, transcript island match to this natural segmentation of the document. We also can observ that well segmented transcripts are easier to spot. Moreover, the number of text segments is significantly higher in the RTBF corpus : we have about 20 annotated prompt parts per audio segment, for a total of about 400 ; this probably decreases the risk to miss an island which should be spotted.

Conclusion and future work

In this paper, we proposed a method dedicated to the spotting of transcript island in large speech databases. This method aims to recover the missing timestamps of closed captions, allowing to build low-cost databases for speech recognizer training. This spotter is integrated in the general scheme of driven decoding. Its role consists in dynamically detecting the transcript island, at the moment where the recognizer crosses it. Our experiments have shown that the proposed technique reaches very good results by using the real prompts provided with the RTBF database. Moreover, this method seems to be quite robust to the imperfect transcripts.

We plan now to extend our experiments to evaluate this technique on a citation spotting task, which corresponds to the particular case where only one word-utterance is spotted. This targeted task involves strong efficiency constraints, as all relevant speech segments must be decoded for spotting the targeted word-utterance. We plan to investigate a two-level method where a first very fast-match pass selects relevant areas, before re-evaluation by the proposed driven spotting technique.

Moreover, we should evaluate this algorithm in the general framework of low-cost corpus building for low-resourced languages. We actually plan to train acoustic models on a subcorpus composed of spotted and corrected RTBF prompts. We will study how the particularities of such a corpus could be advantageously integrated in the general scheme of lightly supervised training.

Table 1 :

 1 Transcript island spotting on the ESTER database. Experiments are performed on 3 hours of the development set, from France Inter radio (INTER), France Info (INFO) and Radio France International (RFI). The targets of spotting are exact transcript island.

		Precision Recall	F-measure Seg.
					number
	INTER	90.9%	98.89% 94.8%	478
	INFO	93.7%	92.9%	91.5%	468
	RFI	98.9%	97.8%	98.4%	812
	Mean	95.3%	97.3%	95.5%	1758

Table 2 :

 2 Spotting on the ESTER database. Experiments are performed on 3 hours of the development set, using imperfect transcripts of about 10% Word Error Rate. As in Table1, 50% of transcript segments have been removed for spotting evaluation.

			Recall	F-measure Seg.
					number
	FrInter	90.7%	96.9%	93.7%	478
	FrInfo	93.4%	89.7%	91.5%	468
	RFI	98.8%	97.8%	98.4%	812
	Mean	94.3%	94.8%	94.5%	1758

Table 3 :

 3 . Word error rates of the systems involved in the exper-

	System	Baseline	DDA+IT DDA+PT
	INTER	22.6 %	17.9%	17.1%
	INFO	23.4 %	21.7%	18.3%
	RFI	27.2 %	23.0%	20.3 %
	Mean	24.4 %	20.9 %	18.6 %
	iments; the baseline system is the standard LIA speech recog-
	nition system (Speeral) without using any text sources for help-
	ing the search, using only one decoding pass; DDA+IT consists
	in driven decoding by imperfect transcripts; DDA+PT is DDA
	search algorithm driven by the correct word utterance. Experi-
	ments are performed on 3 hours of the development set, by us-
	ing imperfect transcripts of about 10% Word Error Rate. As in
	Table 1, 50% of text-segments have been removed for spotting
	evaluation.

Table 4 :

 4 Precision/recall and F-measure of transcript island spotting. Experiment is performed on broadcast news shows from RTBF, by using the real journalist prompts.

		Precision Recall	F-	Seg.
				measure	number
	RTBF	99.28 %	97.13 %	98.41 %	501
	shows


Made Windu

Antara Kesiman

Jean-Christophe Burie
email: jcburie@univ-lr.fr

Jean-Marc Ogier
email: jean-marc.ogier@univ-lr.fr

A New Scheme for Text Line and Character Segmentation from Gray Scale Images of Palm Leaf Manuscript

Keywords: line segmentation, character segmentation, Balinese script, palm leaf manuscript, image I

Most of text line and character segmentation methods for handwritten document image basically still depend on the binary image of the document. Unfortunately, for palm leaf manuscript images, the binarization process is a real challenge. We proposed a new binarization free scheme for text line and character segmentation for palm leaf manuscript images. Our scheme consists of 4 sub-tasks: brushing character area of gray level images with minimum filtering, average block projection profile of gray level images, selection of candidate area for segmentation path, and construction of nonlinear segmentation path. For evaluation, we compared our method with the shredding method which is applied in three different schemes of experiment. The experimental results showed that the proposed method performed optimal on the palm leaf manuscript images which contain discolored parts, with low intensity variations or poor contrast, random noises, and fading.

INTRODUCTION

Segmentation of document image into text lines, words, and characters is oftenly performed prior to recognition step of an OCR system [START_REF] Nicolaou | Handwritten Text Line Segmentation by Shredding Text into its Lines[END_REF][START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF][START_REF] Arica | Optical character recognition for cursive handwriting[END_REF][START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF][START_REF] Ramteke | Invariant Moments Based Feature Extraction for Handwritten Devanagari Vowels Recognition[END_REF][START_REF] Blumenstein | A novel feature extraction technique for the recognition of segmented handwritten characters[END_REF][START_REF] Shi | Text extraction from gray scale historical document images using adaptive local connectivity map[END_REF]. In general, text recognition method vary in the need of segmentation process. Therefore, each text recognition method can be categorized as segmentation based or segmentation free method. The segmentation based text recognition method need prior segmentation process of the document image into text line segments, word segments, or character segments. The performance of OCR system is greatly influenced by the result of the segmentation process.

Many methods of text line and character segmentation for handwritten document image were already proposed [START_REF] Nicolaou | Handwritten Text Line Segmentation by Shredding Text into its Lines[END_REF][START_REF] Louloudis | Text line and word segmentation of handwritten documents[END_REF][START_REF] Chamchong | Character segmentation from ancient palm leaf manuscripts in Thailand[END_REF][START_REF] Santos | Text Line Segmentation Based on Morphology and Histogram Projection[END_REF][START_REF] Zhang | Text Line Segmentation for Handwritten Documents Using Constrained Seam Carving[END_REF][START_REF] Yin | Handwritten Chinese text line segmentation by clustering with distance metric learning[END_REF][START_REF] Kumar | Handwritten Arabic text line segmentation using affinity propagation[END_REF]. Some works deal directly with the text line and character segmentation and recognition [START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF][START_REF] Arica | Optical character recognition for cursive handwriting[END_REF][START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF]. But most of those methods basically still depend on the binary image of the document. Some other methods used the combined information from both binary and gray scale image [START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF][START_REF] Arica | Optical character recognition for cursive handwriting[END_REF]. In this case, a good initial binarization process is required. Unfortunately, for some type of historical document image, for example the palm leaf manuscript images from Southeast Asia, the binarization process to separate the ancient text from the background is a real challenge [START_REF] Fung | A Review of Evaluation of Optimal Binarization Technique for Character Segmentation in Historical Manuscripts[END_REF][START_REF] Kesiman | An Initial Study On The Construction Of Ground Truth Binarized Images Of Ancient Palm Leaf Manuscripts[END_REF][START_REF] Kesiman | An Analysis of Ground Truth Binarized Image Variability of Palm Leaf Manuscripts[END_REF]. A review of evaluation of optimal binarization technique for character segmentation in historical manuscripts was presented in [START_REF] Fung | A Review of Evaluation of Optimal Binarization Technique for Character Segmentation in Historical Manuscripts[END_REF]. In our previous work [START_REF] Kesiman | An Initial Study On The Construction Of Ground Truth Binarized Images Of Ancient Palm Leaf Manuscripts[END_REF], we already experimented and compared several alternative well-known binarization algorithms on the palm leaf manuscript images. We showed that those binarization methods do not give a good binary image for palm leaf manuscript images. All methods extract unrecognizable characters on palm leaf manuscripts with noise. In addition of the varying space between letters, and varying space between lines, the binary image of the manuscript contains the merges, fractures and other deformations of the character shapes. Consequently, the text line and character segmentation method which based on the binary image will not provide a good result for this kind of document image. Therefore, a new scheme for text line and character segmentation for palm leaf manuscript images is required.

Some methods for text line or character segmentation from gray scale image were already proposed [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF][START_REF] Shi | Text extraction from gray scale historical document images using adaptive local connectivity map[END_REF][START_REF] Bar-Yosef | Line Segmentation for Degraded Handwritten Historical Documents[END_REF][START_REF] Garz | Binarization-Free Text Line Segmentation for Historical Documents Based on Interest Point Clustering[END_REF]. A survey of text line segmentation methods for historical documents was given in [START_REF] Likforman-Sulem | Text line segmentation of historical documents: a survey[END_REF]. In this paper, we propose a new scheme for text line and character segmentation from gray scale images of palm leaf manuscript. This scheme is based on the work of [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF], [START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF] and [START_REF] Arica | Optical character recognition for cursive handwriting[END_REF]. It consists of 4 subtasks: brushing character area of gray level images with minimum filtering, average block projection profile of gray level images, selection of candidate area for segmentation path, and construction of nonlinear segmentation path. But instead of using the projection profile described in [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF], our scheme proposed to use the average block projection profile. We also defined the rule to select candidate areas for segmentation path, instead of using the topographic features described in [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF] or using the local maxima of the outer counter of the binary image described in [START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF] and [START_REF] Arica | Optical character recognition for cursive handwriting[END_REF]. Our scheme is a binarization free scheme for text line and character segmentation.

This paper is organized as follow: Section II gives a brief description about Balinese palm leaf manuscripts and the challenges for text line and character segmentation. Section III presents the detail description about the proposed scheme. The result and evaluation of the proposed scheme is presented in Section IV. Conclusions with some prospects for the future works are given in Section V.

II. PALM LEAF MANUSCRIPTS

A. The Balinese Palm Leaf Manuscripts

Many literary texts of the Balinese were written on dried and treated palm leaves, called Lontar. The Balinese palm leaf manuscripts were written in Balinese script in Balinese language. Writing in Balinese script, there is no space between words in a text line. Some characters are written on upper baseline or under the baseline of text line (Fig. 1). Lontars were written in the ancient literary texts composed in the old Javanese language of Kawi and Sanskrit. Balinese script is considered to be one of the complex scripts from Southeast Asia. The alphabet and numeral of Balinese script is composed of ±100 character classes including consonants, vowels, diacritics, and some other special compound characters. The number of compound characters can not be counted precisely because it depends on the writing style of the writers. Two basic characters are sometimes written in their compound character. There is only a limited access to the content of the manuscripts, because of the linguistic difficulties and the fragility of the documents. The majority of Balinese has never read any lontar because of language obstacles as well as tradition which perceived them as a sacrilege. Many discovered lontars are now part of collections of museums and private families. They are in a state of disrepair due to age and due to inadequate storage conditions. Therefore, the digitization and indexing projects for palm leaf manuscripts were proposed. They work not only to digitize the palm leaf manuscripts, but also to develop an automatic analysis, transcription and indexing system for the manuscripts, to make palm leaf manuscripts more accessible, readable and understandable to a wider audience and to scholars and students all over the world.

B. The Challenges for Text Line and Character

Segmentation Due to its specific characteristics, palm leaf manuscripts are providing new challenges in document analysis. Usually, palm leaf manuscripts are of poor quality since the documents have degraded over time due to storage conditions (Fig. 2). Natural materials from palm leaves certainly cannot fight against time, and therefore the processes of digitizing and indexing Lontars are very important. The palm leaf manuscripts contain discolored parts and artefacts due to aging and low intensity variations or poor contrast, random noises, and fading [START_REF] Kesiman | An Initial Study On The Construction Of Ground Truth Binarized Images Of Ancient Palm Leaf Manuscripts[END_REF]. Several deformations in the character shapes are visible due to the merges and fractures of the characters, varying space between letters, and varying space between lines. The overlaps, and interconnection of the neighboring characters further complicate the work of the OCR systems [START_REF] Arica | Optical character recognition for cursive handwriting[END_REF]. The

朌 ⷵ ⷮ ⦃ ⬾ 잷 소 ᅬ 늾 켊찝 ଛ 䖣 颜䝚 _ 鱁紀 砝行聐 抃 矧行 滸
盐 潥拃  so segmentation, for example skewed and fluctuating text lines, and irregularity in geometrical properties of the line, such as line width, height, and distance in between lines [START_REF] Nicolaou | Handwritten Text Line Segmentation by Shredding Text into its Lines[END_REF]. These characteristics provide a suitable challenge for text line and character segmentation. Our proposed scheme (Fig. 3) consists of 4 sub-tasks: brushing character area of gray level images with minimum filtering, average block projection profile of gray level images, selection of candidate area for segmentation path, and construction of nonlinear segmentation path. To deal with some slight skew angles on the text line, first, we divided the manuscript into vertical zones. The approximated zone width was calculated from the average width of 11,496 word segments (patch image of group of characters) which are obtained from our previous work on word annotation ground truthing process and fixed to a value of 400 pixels.

A. Brushing Character Area of Gray Level Images

Most of the Balinese character forms consist of some holes and some semi-spaced areas between their two or more main curve strokes. These semi-space areas are normally found between two vertical strokes within a character and they have almost the same width with the real space between two characters. To segment the character in a text line, it is not easy to differentiate these semi-spaced intra-character areas with the real spaced inter-character areas (Fig. 4).

Even though that, under assumption we have a good binarized image for the characters. The method which try to detect the local minima and maxima on the characters, will fail to differentiate the candidate area for segmentation between the two local minima or maxima of intra-character and inter-character areas. To overcome this problem, we applied a minimum filtering to cover the holes and the intra-character areas by brushing the areas. We used the minimum filtering with a horizontal or vertical filter. This brushing technique with minimum filtering is the application of a morphological operator dilation with a horizontal/vertical structuring element. It replaces the pixel value with the minimum pixel value within the vertically/horizontally defined neighbor pixels (defined as brush width). Minimum filter is used because in our manuscripts the character pixels are always darker than the background pixels. The gray values in our gray scale images are defined from 0 (for black pixels) to 255 (for white pixels).

Brushing for gray level images is defined as follows: Let g(r,c) be the intensity of a pixel (r,c) in a gray scale image, and w be the brush width.

Brushing vertical:

_ ( , ) min{ ( , )}, 2 2 brush v w w g r c g i c r i r = -£ £ + Brushing horizontal: _ ( , ) min{ ( , )}, 2 2 brush h w w g r c g r j c j c = -£ £ +
The spaces between text lines are also difficult to determine because many characters in Balinese script have ascender or descender parts, written in the area between text lines. To detect the main text line areas in the manuscript, first, we applied the brushing horizontal. The brush width is defined as the approximated character width in the manuscript, so it can cover horizontally the holes, the semi-spaced intra-character, and also the real-spaced intercharacter areas, to connect the main text line (Fig. 5). The approximated character width and height was calculated from the average width and height of 4,975 character segments which are obtained from our previous work on character annotation ground truthing process and fixed respectively to 50 and 35 pixels. To segment the characters, first, we applied the brushing vertical (Fig. 6). The brush width is simply defined as the height of the text line segment (or the approximated character height) because this step is normally done in the main text line areas (see Section IIIC).

B. Average Block Projection Profile of Gray Level Images

A definition of projection profile for gray level images was described in [START_REF] Shi | Text extraction from gray scale historical document images using adaptive local connectivity map[END_REF][START_REF] Bar-Yosef | Line Segmentation for Degraded Handwritten Historical Documents[END_REF]. But inspired by the work of [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF], the projection profile for gray level images in our work is defined as follows: Let g(r,c) be the intensity of a pixel (r,c) in a gray-scale image. Then g(r,c) is in the following range : 0 ( , ) 1 g r c L £ £ -, where L is the level of intensity. Let Hr(g) and Hc(g) be the histograms of row r and column c with intensity of g, respectively. The vertical projection profile in column c, P(c) can be defined as follows: To detect a zone area of the characters or the text lines, we calculated the average of projection profile in some equal sized overlapped blocks. The average block projection profile is defined as follows: Let bw be the block width, AP(c) be the vertical average block projection profile in column c, and AP(r) be the horizontal average block projection profile in row r.

C. Selection of Candidate Area for Segmentation Path

To detect the candidate area for segmentation path, the average block projection profile is used. The horizontal average block projection profile is used to find the horizontal candidate area to segment the main text line areas and inter text line areas. The horizontal average block projection profile APnorm(r) with block width bw is firstly sorted for all row r, 1 _ r nb row £ £ , from the minimum to the maximum value. In this case, we consider the minimum value because in our palm leaf manuscript images, the character strokes are represented in darker pixels, so the main text line area which contains more character pixels has a smaller value of horizontal average block projection profile. Let r1,r2,r3...rnb_textline be the sorted row position of APnorm(r). The nb_textline candidate areas for main text line are then constructed with bw rows on the manuscript, which started from row r th . To detect the main text line areas, bw is defined as the approximated character height in the manuscript. The inter text line areas are simply extracted from the areas between the main text line areas (Fig. 7). By using the same definition, the vertical average block projection profile is used to find the vertical candidate area to segment the characters in text line. The vertical average block projection profile APnorm(c) with block width bw is firstly sorted for all column c,1 _ c nb col £ £ . Here, bw is defined as the approximated character width in the manuscript (Fig. 8).

D. Construction of Nonlinear Segmentation Path

The objective is to find a nonlinear segmentation path of one pixel wide in each candidate area of segmentation. Finding a nonlinear segmentation path can be defined as a problem of finding the shortest path which (in our case) maximizes the accumulated intensity in the candidate area of segmentation. We implemented the multistage graph search algorithm to find the nonlinear segmentation path. The multistage graph search algorithm was described and used in [START_REF] Arica | A new scheme for off-line handwritten connected digit recognition[END_REF][START_REF] Arica | Optical character recognition for cursive handwriting[END_REF][START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF].

Let carea be a candidate area of segmentation. To find a horizontal minimum nonlinear segmentation path from left to right, we consider each pixel in carea as a graph node (Fig. 9). A node of pixel carea(r,c) has (at most) three vertices directed to the right, which connect to the next three neighbor pixels: node of pixel carea(r-1,c+1), carea(r,c+1), and carea(r+1,c+1). From each pixel in first column (left most pixel), we generate a nonlinear segmentation path to the right most pixel, by consecutively choosing the pixel with minimum intensity value between the three neighbor nodes of pixel. The minimum nonlinear segmentation path in carea is finally defined as the nonlinear segmentation path which is started from a certain pixel, with a minimum accumulated intensity value of pixels on their path. To segment the characters, we can apply the vertical nonlinear segmentation path on each segment of text line, in similar way. The vertical nonlinear segmentation path should be calculated on the complement of original image to find the minimum path between the characters (Fig. 10 We finally apply the horizontal nonlinear segmentation path on each vertical segment in the inter text line areas. This path will segment each inter text line areas into two separated areas which belong to two different text lines (Fig. 12).

IV. RESULTS AND EVALUATIONS

We evaluated our proposed method on a set of 35 palm leaf manuscript images which contains 140 text lines in total. Those images were randomly collected and selected from corpus of palm leaf manuscript images from different locations (regions) in Bali, Indonesia. The text line ground truth images were manually segmented from the binary ground truth images of the manuscripts. The binary ground truth images were obtained from our previous ground truthing process [START_REF] Kesiman | An Analysis of Ground Truth Binarized Image Variability of Palm Leaf Manuscripts[END_REF].

We also compared our method with the shredding method proposed in [START_REF] Nicolaou | Handwritten Text Line Segmentation by Shredding Text into its Lines[END_REF]. This method works on binary image. We performed three different experiments to evaluate this method. First, we tested this method directly on our ground truth binary image (Experiment 1). In this case, this method was evaluated with the best binary image of our manuscript. To see the real challenge for our manuscripts, secondly, we tested this method with the binary image which were obtained from Otsu's binarization method (Experiment 2). And thirdly, we tested a small proposed modification for this method by replacing the bluring process from binary image with the brushing gray scale image used in our proposed method (Experiment 3).

We used the evaluation criteria and tool provided by ICDAR2013 Handwritting Segmentation Contest [START_REF] Stamatopoulos | ICDAR 2013 Handwriting Segmentation Contest[END_REF]. First, the one-to-one (o2o) match score is computed for a region pair based on the evaluator's acceptance threshold. With the o2o score, the three metrics are calculated: detection rate (DR), recognition accuracy (RA), and performance metric (FM). The result is presented on Table I.

We can see that the method of [START_REF] Nicolaou | Handwritten Text Line Segmentation by Shredding Text into its Lines[END_REF] depends greatly on the quality of the binary image. Eventhough this method was tested on the best binary image from our ground truth binary image, it only achieved 80.13% for FM score, and it decreased significantly when it was applied to the real binarization method results (Exp. 2). Our small proposed modification gave a promising result from gray scale images (Exp. 3). It means that our brushing images already provide a preliminary information about the main text line positions. Our proposed method achieved a good FM score by using gray scale processing scheme. It is performed optimally on the palm leaf manuscript images which contain discolored parts, with low intensity variations or poor contrast, random noises, and fading (Fig. 13).

V. CONCLUSIONS AND FUTURE WORKS

We presented a new binarization free scheme for text line and character segmentation for palm leaf manuscript images. The experimental results showed that the proposed method performed optimal on the palm leaf manuscript images which contain discolored parts, with low intensity variations or poor contrast, random noises, and fading. For the future works, we will integrate this method with a character or text recognition module so it can perform mutually as the verification and correction module for the segmentation and also for the final text recognition task.

Figure 1 .

 1 Figure 1. Balinese script on palm leaf manuscripts

Figure 2 .Figure 3 .

 23 Figure2. The degradations on palm leaf manuscripts[START_REF] Kesiman | An Initial Study On The Construction Of Ground Truth Binarized Images Of Ancient Palm Leaf Manuscripts[END_REF]

Figure 4 .

 4 Figure 4. Similar semi-spaced intra-character areas and real spaced intercharacter areas

  a) Sample of original image, b) Brushing horizontal of a)

Figure 6 .

 6 Figure 6. Brushing vertical of image in Fig. 4

  ratio contributing to the projection with intensity of g, 0 ( ) 1 c g £ £ . In similar way, the horizontal projection profile in row r, P(r) can be defined by

  a) Candidate areas (white zones) for main text line areas of Fig. 5, b) Blending of a) & Fig. 5a, c) Blending with candidate areas for inter text line areas of Fig. 5a

  a) Candidate areas (white zones) for characters of Fig.4 and 6, b) Blending of a) & Fig.4

Figure 9 .

 9 Figure 9. Multistage graph representation

  Figure 10. a) Candidate areas for character segmentation (white zones) of Fig. 4, b) Complement image of Fig. 4, c) Nonlinear character segmentation path of b) based on a), e) Blending of Fig. 4 & c)

  & 11).

  Figure 11. a) Nonlinear character segmentation path of Fig. 7b, b) Nonlinear character segmentation path of Fig. 7c, c) Horizontal nonlinear segmentation path in the inter text line areas of b) a) Extracted text line 1, b) Extracted text line 2, c) Extracted text line 3, d) Extracted text line 4.

Figure 13

 13 Figure 13. a) Original image, b) Extracted text line 1, c) Extracted text line 2, d) Extracted text line 3, e) Extracted text line 4

TABLE I

 I

		. RESULT OF PERFORMANCE EVALUATION
	Exp.	M	o2o	DR (%)	RA (%)	FM (%)
	Exp. 1	167	123	87.85	73.65	80.13
	Exp. 2	1418	14	10	0.98	1.79
	Exp. 3	199	70	50	35.17	41.29
	Proposed method	140	110	78.57	78.57	78.57

ACKNOWLEDGMENT

The authors would like to thank Museum Gedong Kertya, Museum Bali, and all families in Bali, Indonesia, for providing us the samples of palm leaf manuscripts, and the students from the Department of Informatics Education and the Department of Balinese Literature, Ganesha University of Education for helping us in ground truthing process for this research project. This work is also supported by the DIKTI BPPLN Indonesian Scholarship Program and the STIC Asia Program implemented by the French Ministry of Foreign Affairs and International Development (MAEDI).