Handwritten Text Line Detection and Classification based on HMMs

UNIVERSITAT POLITÈCNICA DE VALÈNCIA DEPARTAMENTO DE SISTEMAS INFORMÁTICOS Y COMPUTACIÓN PATTERN RECOGNITION AND HUMAN LANGUAGE TECHNOLOGY GROUP IARFID Master Thesis Handwritten Text Line Detection and Classification based on HMMs Author: Vicente Bosch Campos Advisor: Enrique Vidal Ruiz Co-advisor: Alejandro Héctor Toselli June 28, 2012 ii ACKNOWLEDGEMENTS Many people have helped me out in order to let me conclude this research. Thanks to my parents for teaching me the value of hard work, to my friends in the PRHLT lab for making the journey much more enjoyable and finally to Enrique Vidal and Alejandro Héctor Toselli for their time, patience and knowledge without which this work could not have been completed. The research leading to these results has received funding from the MIPRCV "Consolider Ingenio 2010" program (CSD2007-00018), MITTRAL (TIN2009-14633-C03-01) and also Univ. Politécnica Valencia (PAID-05-11). Vicente Bosch Handwritten Text Line Detection based on HMMs CONTENTS 1 Introduction 1 1.1 Introduction ...................................... 2 1.2 Motivation ....................................... 3 1.3 Related Works ..................................... 3 1.4 Overview of the Proposed Approach ......................... 4 1.5 Context of Application and Assumptions ....................... 4 1.6 Expected Outcomes/Results ............................. 5 Bibliography ........................................ 5 2 Fundaments 7 2.1 Hidden Marcov Models (HMMs) ........................... 8 2.1.1 Definition ................................... 8 2.1.2 Basic algorithms for HMMs ......................... 10 2.2 Language models: N-grams ............................. 14 2.3 HTK ToolKit ..................................... 15 Bibliography ........................................ 16 3 HMM-Based Text Line Detection System 17 3.1 System Architecture .................................. 18 3.2 Modelling ....................................... 19 3.2.1 Statistical Framework Contextualization ................... 19 3.2.2 Morphological Models ............................ 20 3.2.3 Language Model ............................... 22 3.3 Preprocessing Module ................................ 24 3.4 Feature Extraction ................................... 26 3.5 Evaluation Measures ................................. 27 3.6 Conclusions ...................................... 30 Bibliography ........................................ 31 4 Experiments and Results 33 4.1 Experimental Set-up and Baseline .......................... 34 4.2 Corpora Description .................................. 35 4.3 Results ......................................... 36 4.3.1 Detection Experimentation .......................... 36 4.3.2 Classification Experimentation ........................ 40 4.3.3 Vertical Region Models Experimentation .................. 42 Bibliography ........................................ 43 Vicente Bosch Handwritten Text Line Detection based on HMMs CONTENTS 5 General Conclusions and Future Work 45 5.1 Conclusions ...................................... 46 5.2 Publications ...................................... 46 5.3 Future Work ...................................... 46 Bibliography ........................................ 47 vi LIST OF FIGURES 2.1 Examples of n-grams represented using a SFSA. .................. 15 3.1 HLD System Schematics ............................... 18 3.2 Feature Extraction - Vertical regions ......................... 20 3.3 Vertical Region Classes - Examples of all vertical region types ........... 21 3.4 HMM Topology - Strictly Linear Model Example .................. 21 3.5 HMM Topology - Ranged Linear Model Example .................. 22 3.6 SFSG - Prior Language Model Example ....................... 23 3.7 SFSG - Conditional Language Model Example ................... 23 3.8 SFSG - Line-number constrained Language Model Example ............ 24 3.9 Page level preprocessing ............................... 25 3.10 Feature Extraction - Vertical regions ......................... 26 3.11 Feature Extraction - Vertical projection profile calculation schematics ....... 27 3.12 Feature Extraction - Vertical projection profile calculation sample ......... 28 3.13 Alingment Cost .................................... 30 4.1 Examples of page images from CS corpus. ...................... 35 4.2 Prior Language ModelDetection error study for varying HMMs Number of States and Gaussians per State ................................ 37 4.3 Prior Language ModelDetection error study for varying extracted columns and overlap ........................................ 38 4.4 Prior Language Model - Detection error study for varying WIP and GSF values for one extracted column ................................. 39 4.5 Prior Language Model - Detection error study for varying WIP and GSF values for two extracted columns ................................ 39 4.6 Image shows the difference between our proposed method (upper side of each coloured region ) and the histogram projection method (lower side) ......... 40 4.7 Prior Language ModelClassification error study for varying HMMs Number of States and Gaussians per State ............................ 40 4.8 Prior Language ModelClassification error study for varying extracted columns and overlap ...................................... 41 Vicente Bosch Handwritten Text Line Detection based on HMMs List of Figures viii LIST OF TABLES 4.1 Basic statistics of the Cristo-Salvador corpus “book” partition. ........... 36 4.2 Best detection figures of LER(%) and AAR(%) obtained for our statistical text line analysis approach (STLAD) and the heuristic one (HEUR), using different kind of language models: Prior (PRI), Conditional (CND) and Line-Number Constrained (LN-C). ........................................ 39 4.3 Best classidication figures of LER(%) and AAR(%) obtained for our statistical text line analysis approach (STLAD) and the heuristic one (HEUR), using different kind of language models: Prior (PRI), Conditional (CND) and Line-Number Constrained (LN-C). ................................. 42 Vicente Bosch Handwritten Text Line Detection based on HMMs Bibliography [5] Lu, Z., Schwartz, R., and Raphael, C. (2000). Script-independent, hmm-based text line finding for ocr. In Pattern Recognition, 2000. Proceedings. 15th International Conference on, volume 4, pages 551 –554 vol.4. [6] Sánchez-Cortina, I., Serrano, N., Sanchis, A., and Juan, A. (2012). A prototype for interactive speech transcription balancing error and supervision effort. In Proceedings of the 2012 ACM international conference on Intelligent User Interfaces, pages 325–326. [7] Toselli, A. H., Juan, A., Keysers, D., González, J., Salvador, I., H. Ney, Vidal, E., and Casacuberta, F. (2004). Integrated Handwriting Recognition and Interpretation using Finite-State Models. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(4):519–539. [8] Toselli, A. H., Romero, V., Pastor, M., and Vidal, E. (2009). Multimodal interactive transcription of text images. Pattern Recognition, 43(5):1824–1825. [9] Toselli, A. H., Romero, V., and Vidal, E. (2011). Language Technology for Cultural Heritage, chapter Alignment between Text Images and their Transcripts for Handwritten Documents., pages 23–37. Theory and Applications of Natural Language Processing. Springer,. Caroline Sporleder, Antal van den Bosch y Kalliopi Zervanou (Eds.). [10] Vinciarelli, A., Bengio, S., and Bunke, H. (2004). Off-line recognition of unconstrained handwritten texts using hmms and statistical language models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(6):709–720. [11] Öztop, E., Mülayim, A., Atalay, V., and Yarman-Vural, F. (1999). Repulsive attractive network for baseline extraction on document images. Signal Processing, 75(1):1 – 10. 6 CHAPTER 2 FUNDAMENTS Chapter Outline 2.1 Hidden Marcov Models (HMMs) ......................... 8 2.2 Language models: N-grams ........................... 14 2.3 HTK ToolKit .................................... 15 Bibliography ....................................... 16 Vicente Bosch Handwritten Text Line Detection based on HMMs Chapter 2. Fundaments 2.1 Hidden Marcov Models (HMMs) A Hidden Markov Models (HMM) is an statistical Markov model where only the emissions and not the states are visible. A HMM can be represented by: A finite set of states each of which is associated with a continuous probability distribution that defines or rules the "emissions" in that state. Transitions probability which governs the transitions among the states of the HMM. HMMs are considered the most successful model used for Automatic Speech Recognition (ASR) due to the results obtained with them during the past decades. This successes are due to the models ability to represent the problem and its sequential nature in a formal way , hence mathematically tractable, the discrete time sequences of the extracted acoustic feature vectors. HTR shares one major similarity with ASR as the discrete time sequences that define the continuous writing can be considered also as emissions from an HMM. For HTR the observed emissions represent line-image features and point coordinates of the handwritten pen strokes. Due to this similarity and the success of HMM for the ASR task the application of these statistical models has gained popularity for the resolution of HTR tasks. For layout detection the same similarity can be considered as the vertical regions that define the page can be considered as emissions from an HMM. 2.1.1 Definition One possible classification of HMMs can be performed according to the nature of the observed emissions [2][1] •If the observed emissions are represented by a vector of symbols in a finite alphabet the HMM can be considered discrete •When emissions are vectors of reals the HMM is defined as continuous •semi-continuous is used when the emissions are of a discrete nature but are modelled using continuous probability density functions. Since in our research we will work only with continuous HMMs we will provide a summarized formal definition of this kind of HMM using the notation represented in [4]. Following assumptions are considered for our continuous HMMs: •Emissions are only performed in states and not in transitions •An additional initial state similar to the end state, which can not perform emissions, has been defined 8 2.1. Hidden Marcov Models (HMMs) Both in ASR and HTR, HMMs are used to compute the probability of the input signal represented as a sequence of feature vectors. Let be x=x1x2...xT, a sequence of real vectors, a HMM Mapproximates the probability of this sequence; that isa: Pr(x)≈PM(x)(2.1) Formally, a continuous HMM is a finite state machine defined by the sextuple (Q, I, F, X, a, b) where: •Qis a finite set of states. In order to avoid confusions with the indexation of the different states, we denote the states of the model as q0, ..., q|Q|−1, whereas a sequence of states that generates the vector sequence x=x1x2...xTwill be denoted as z1z2...zT. •Iis the initial state, an element of Q:I∈Q.I=q0 •Fis the final state, an element of Q:F∈Q.F=q|Q|−1 •Xis a real d-dimensional space of observations: X⊆ <d. •ais the state-transition probability functionb: a(qi, qj) = P(zt+1 =qj|zt=qi)qi∈(Q− {F}), qj∈(Q− {I}) Transition probabilities should satisfy a(qi, qj)≥0and X qj∈(Q−{I}) a(qi, qj)=1 ∀qi∈(Q− {F}) •bis a probability distribution functionc: b(qi,x) = P(xt=x|zt=qi)qi∈(Q− {I, F }),x∈X The following stochastic constraints must be satisfied: b(qi,x)≥0and Zx∈X b(qi,x)dx= 1 ∀qi∈(Q− {I, F }) As the observations are continuous we must therefore use a continuous probability density function. In this case it is defined as a weighted sum of GGaussian distributions: b(qj,x) = G X g=1 cjgbg(qj,x) where, bg(qj,x) = 1 p(2π)d|Σjg|e(−1 2(x−µ0 jg)Σ−1 jg (x−µjg)) a“True” probabilities are written as Pr(. . .), in contrast with model approximations such as PM(z|. . .)which, to simplify notation, will be denoted as P(z|. . .)whenever Mcan be understood bzt=qimeans that the HMM is in the state qiat time t cxt=xmeans that the HMM in the state ztgenerates xat time t 9 Chapter 2. Fundaments •µjg is the mean vector for the component gof the state qj •Σjg is the covariance matrix for the component gof the state qj •cjg is the weighting coefficient for the component gof the state qj, and should satisfy the stochastic constrain cjg ≥0and G X g=1 cjg = 1 For the sake of mathematical and computational tractability, the following assumptions are made in the theory of HMMs: 1. The Markov assumption. As given in the definition of HMMs, transition probabilities are defined as: a(qi, qj) = P(zt+1 =qj|zt=qi). In other words it is assumed that the next state is dependent only upon the current state; that is, Pr(zt+1|z1...zt)≈P(zt+1|zt) Which is called the Markov assumption and when applying it to the generalized HMM the resulting model becomes actually a first order HMM. 2. The stationary assumption. Assumes that state transition probabilities are independent of the actual time at which the transitions take place. Mathematically, P(zt1+1 =qj|zt1=qi) = P(zt2+1 =qj|zt2=qi) for any t1and t2 3. The output independence assumption. The probability distribution function is defined as: b(qi,x) = p(xt=x|zt=qi). This means that the current output (observation) is statistically independent of the previous outputs (observations) and it only depends of the current state; that is, Pr(xt|x1...xt−1, z1...zt)≈P(xt|zt) 2.1.2 Basic algorithms for HMMs Once we have a HMM, there are three problems of interest. The evaluation problem, the decoding problem and the learning problem. •The Evaluation Problem. This problem consist in computing the probability P(x); that is, the probability that the observations are generated by the model. •The Decoding Problem. Given a HMM and a sequence of observations x, the problem is to find the most likely state sequence in the model which produced the observations. In other words, the problem consists on finding the hidden part of the HMM. 10 2.1. Hidden Marcov Models (HMMs) •The Learning Problem. Given a HMM and a sequence of observations x, how should we adjust the model parameters in order to maximize the probability P(x). To simplify the notation, in the next sections, a(qi, qj)will be written as aij and b(qi, x)as bi(x)d. The Evaluation Problem and the Forward and Backward Algorithms Let xbe a sequence of real vectors and Z={z=z1z2...zT:zk=qi∈(Q− {I, F }),1≤i≤ |Q| − 2}a set of state sequences associated with the vector sequence x. Then, the probability that xbe generated by the HMM is: P(x) = X z∈Z T Y i=1 azi−1zibzi(xi)!azTF where z0is the initial state I:z0=q0=I. This calculation involves a number of operations that is in the order of NT, where Nis the number of states of the model excluding the initial state, N=|Q| − 1 (Q={q0=I, q1, ..., qN−1, qN=F}), and Tis the number of vectors of the sequence. This is very large even if the length of the sequence, Tis moderate. Hence, for practical reasons, we must look for another method to perform this calculation. The Forward algorithm is an efficient algorithm which computes P(x). The time complexity order of this algorithm is: O(|Q|2·T); however, if we further restrict the HMM topology to using a left-to-right HMM the complexity falls to O(|Q| · T). In the left-to-right HMM topology a transition between two states qi, qj∈Qfrom the HMM, it is only possible if j≥i. The forward function αj(t)for 0< j < N, is defined as the probability of the partial observation sequence x1x2...xt, when it terminates at the state j. Mathematically, αj(t) = P(xt 1, qj)and it can be expressed in the following recursive manner: αj(t) =      a0jbj(x1)t= 1 PN−1 i=1 αi(t−1)aijbj(xt) 1 < t ≤T with the initial condition that α0(1) = 1. Using this recursion we can calculate the probability that the sequence xbe emitted by the model Mas: P(x) = P(xT 1) = αN(T) = N−1 X i=1 αi(T)aiN dFrom now on, any kind of subsequence will be represented as li...ljor as lj i, whenever it is convenient. 11 Chapter 2. Fundaments In a similar way we can define the Backward function βi(t)for 0< i < N, as the probability of the partial observation sequence xt+1xt+2...xT, given that the current state is i. Mathematically, βi(t) = P(xT t+1|qi)and it can be expressed on a recursive way: βi(t) =    aiN t=T PN−1 j=1 aijbj(xt+1)βj(t+ 1) 1 ≤t<T with the initial condition that βN(T) = 1. Using this recursion the probability that the sequence x be emitted by the model Mcan be calculated as: P(x) = P(xT 1) = β0(1) = N−1 X j=1 a0jbj(x1)βj(1) As in the forward algorithm the time complexity is: O(|Q|2·T), and using a left-to-right HMM the complexity falls to O(|Q| · T). The Decoding Problem and the Viterbi Algorithm In this case we want to find the most likely state sequence, z=z1z2...zT, for a given sequence of observations, x. The algorithm used here is commonly known as the Viterbi algorithm, which maximizes the joint probability of the observations and all possible sequence of states; that is maxzP(x,z). This algorithm is similar to the forward algorithm, but replacing the sum by the dominating term. vj(t) =    a0jbj(x1)t= 1 maxi∈[1,N−1] vi(t−1)aijbj(xt) 1 < t ≤T with the condition that v0(1) = 1.vN(T)is the probability maxzP(x,z)and using this recursion it can be calculated as: vN(T) = max i∈[1,N−1] vi(T)aiN ≤ N−1 X i=1 αi(T)aiN =αN(T) The time complexity of the Viterbi algorithm is: O(|Q|2·T), and using a left-to-right HMM the complexity falls to O(|Q| · T). The Learning Problem and the Baum-Welch Algorithm The learning problem is how to adjust the HMM parameters (aij, bi(x), cjg, µjg and Σjg), so that a given set of observations (called training set) is generated by the model with maximum likelihood. 12 2.1. Hidden Marcov Models (HMMs) The Baum-Welch algorithm [3] (also known as Forward-Backward algorithm), is used to find these unknown parameters. It is an expectation-maximization (EM) algorithm. Let E={xr=xr1xr2...xrTr:xrk ∈X, 1≤k≤Tr∧1≤r≤R}a set of Rvector sequences, used to adjust the HMM parameters. The basic formula to estimate the state-transition probability aij is: ˆaij =PR r=1 1 PrPTr−1 t=1 αr i(t)aijbj(xrt+1)βr j(t+ 1) PR r=1 1 PrPTr t=1 αr i(t)βr i(t) where 0< i < N,0< j < N and Pr=P(xr)is the total probability of the sample rfrom the set E. If the probability density function of each state on the HMM is approximated by a weighted sum of GGaussian distributions we must find the unknown parameters cjg, µjg and Σjg. With this purpose we define Lr jg(t)as the probability that the vector xrt ∈ <dbe generated by the Gaussian component gin the qjstate: Lr jg(t) = 1 Pr Ur j(t)cjgbjg(xrt)βr j(t) where Ur j(t) =    a0jif t = 1 PN−1 i=1 αr i(t−1)aij otherwise Taking into account the previous definitions, the parameters cjg, µjg and Σjg can be estimated as: ˆµjg =PR r=1 PTr t=1 Lr jg(t)xrt PR r=1 PTr t=1 Lr jg(t) ˆ Σjg =PR r=1 PTr t=1 Lr jg(t)(xrt −ˆµjg)(xrt −ˆµjg)0 PR r=1 PTr t=1 Lr jg(t) cjg =PR r=1 PTr t=1 Lr jg(t) PR r=1 PTr t=1 Lr j(t) The time complexity of one iteration of the Baum-Welch algorithm is: O(R·|Q|2·T); however, using a left-to-right HMM the complexity falls to O(R· |Q| · T). This algorithm is iterated until some convergence criterion is reached. Sometimes, it is necessary to have a composition of CHMM joined sequentially, for example in the case of the different vertical regions that conform a page. In this case, the “embedded training Baum-Welch” algorithm, which re-estimates the parameters of the composition of Csequentially concatenated HMMs, can be used. This algorithm enables to train the HMM without any prior segmentation of the training page images into vertical regions. In [4] we can find all the formula to compute the unknown parameters in this case but more specifically for the HTR case (lines and morpheme). 13 Chapter 2. Fundaments 2.2 Language models: N-grams Language models (LMs) are usually used to model text properties, like syntax and semantic, independently from the character morphology modelled by HMMs. They are used in many natural language processing applications such as speech recognition, machine translation or handwritten recognition. These models can be used to predict the next word in a word sequence. In our research LMs are used in order to model the structure of a page as described by the composition of the different regions / text sections that can compose it. Language models assign a probability to a sequence of regions w=w1, w2, ..., wl, which can be expressed as: Pr(w) = Pr(w1)· l Y i=2 Pr(wi|wi−1 1) where Pr(wi|wi−1 1)is the probability of the region wiwhen we have already seen the sequence of regions w1...wi−1. The sequence of regions prior to wiis called history. In practice ,for HTR, estimating the probability of sequences can become difficult since sentences can be arbitrarily long and hence many sequences are not observed during LM training. It is necessary to note that for a vocabulary with |V|different words, the number of different histories is |V|i−1. So, the estimation of Pr(w)can be unworkable. For that reason these models are often approximated using smoothed n-gram models, which obtains surprisingly good performance although they only captures short term dependencies. In the case of layout detection, considering the allowed region types, it is more unusual as pages usually have a similar number of lines and samples of transitions from one region to the rest can be found. An n-gram defines a function: Φn:V∗→Vn−1in which, all sequences finishing with the same n−1words belong to the same equivalence class. Now, Pr(w)can be approximated as: Pr(w)≈ l Y i=1 P(wi|Φn(wi−1 1)) = l Y i=1 P(wi|wi−1 i−n+1)(2.2) Owing to the fact that i−n≤0for the first n−1words in w, Eq. (2.2) must be written as: Pr(w)≈P(w1)· n−1 Y i=2 P(wi|wi−1 1)· l Y i=n P(wi|wi−1 i−n+1)) (2.3) Given a vocabulary Vand a transcribed training data or text corpora represented by w= w1w2...wl, the estimated probability of the word v∈V, having seen a sequence of n−1words v∈Vn−1, is computed as: P(v|v) = C(vv) C(v) where C(v)is the number of times that the sequence vhas appeared in the training sequence w. This is a maximum likelihood (ML) estimate. 14 2.3. HTK ToolKit Unigrams Bigram: wi−1wiTrigram: wi−2wi−1wi Figure 2.1: Examples of n-grams represented using a SFSA. n-grams modelled by a stochastic finite state automaton Along this work, stochastic finite state automata (SFSA) are often used to represent HMMs, lexical models and language models. Thanks to the homogeneous finite-state nature of all these models, they can be easily integrated into a single global finite state model. A n-gram can be represented using a SFSA [5,6], defined as a sextuple A= (Q, V, δ, q0, P, F), where: •Vis non-empty finite set of symbols •Q⊆Vn−1∪q0is a finite, not-empty set of states. Each state is defined using the vocabulary symbols Vas q= (vi−n+1...vi−2vi−1)∈Q •δ⊂Q×V×Qis the state-transition function. A transition is denoted as: (vi−n+1...vi−2vi−1, v, vi−n+2...vi−1v) where (vi−n+1...vi−2vi−1)∈Q,(vi−n+2...vi−1v)∈Q, and v∈V •q0is the initial state (q0∈Q) •P:δ→ <+is the probability transition function. We are using deterministic SFSA, so each transition is identified with only the source state q∈Vn−1and the transition symbol v∈V. Therefore, P(q, v, q0) = P(v|q) •F:Q→ <+is the final state probability function. 2.3 HTK ToolKit The Hidden Markov Model Tool-kit (HTK) [7] is an Open Source tool-kit developed and maintained at the Cambridge University Engineering Department (CUED). Development started in 1989 by the Speech Vision and Robotics Group as a set of modules developed in C to perform speech recognition research using HMMs as the statistical model. During its lifetime the HTK licensing and distribution form and owning company has had changes. As of 1999 Microsoft through the acquisition Entropic Research Laboratories (ERL) had the license rights to HTK. As of 2000 Microsoft has licensed back HTK to CUED so that it can maintain it and distribute it. In our research we have used HTK (v3.4) in order to: 15 Chapter 3. HMM-Based Text Line Detection System •Minimum transitions stage - where the states are only allowed to transition to the next state hence setting a hard limit on the minimum number of frames. •Maximum variable transitions stage - where the states are allowed to transition to the next state or the final state of the model. •Final state stage - the final state allows a loop to itself in order to accommodate larger samples. Figure 3.5: Example of a trained 8 state ranged linear model. This model forces a minimum of 3 transitions to be performed. Once an HMM “topology” (number of states and structure) has been adopted, the model parameters can be easily trained from instances (sequences of features vectors) of full images containing a sequence of line-regions (without any kind of segmentation) accompanied by the reference labels of these images that correspond to the actual sequence of line-region classes. This training process is carried out using a well known instance of the EM algorithm called forward-backward or Baum-Welch re-estimation [2]. 3.2.3 Language Model The syntactic modelling level , expressed as the P(h)term (see Eq.(3.2) and Eq.(3.5)), is responsible for defining the way that the different line regions can be concatenated in order to produce a valid page structure. It is worth noting that at this level, NL, PL, SL and NT line regions are always forced to be followed by IL region: NL+IL, PL+IL, SL+IL and NT+IL. We can also use the LM to impose restrictions about the minimum or maximum number of lineregions to be detected. The LM for our text line detection approach, is implemented as a stochastic finite state grammar (SFSG) which recognizes valid sequences of elements (line regions). In our research we considered the following language models: prior (PRI), conditional (CND) and linenumber constrained (LN-C) language models, each represented by topological different SFSGs. The PRI LM transition probabilities are estimated from the training set as the fraction of the number of appearances of each line region label over the whole count of labels. An example can be seen in Fig. 3.6. 22 3.2. Modelling Figure 3.6: Example of a Prior Language Model.. The CND LM also considers context of the previous line region label in order to perform the estimation. An example can be seen in Fig. 3.7. Figure 3.7: Example of a Conditional Language Model. An initial ergodic model was considered and the probabilities where recalculated dropping all non-used transitions. It is important to note that the way the PRI and COND LMs are built somewhat resemble the uni-gram and bi-gram LMs calculations, except no smoothing strategy is implemented here. 23 Chapter 3. HMM-Based Text Line Detection System Finally we defined for each test page a LN-C LM, which also uses the CND LM probabilities to populate the model, that enforces a total number of possible line-regions (line or blank space) to detect as per the number of reference line-region labels of that test page. LN-C is conceived for its utilization in (parts of) documents or document collections that present a homogeneous number of lines per page. An example of this LM can be seen in Fig. 3.8. Figure 3.8: Example of a Line-constrained Language Model. Model created by replicating a Conditional Language Model 5 times. 3.3 Preprocessing Module Our base scanned input images of the handwritten documents require that it’s visual characteristics are improved/corrected in order to not impact adversely on the subsequent feature extraction and line detection processes. This process is done due to the known issues of handwritten historical documents: 24 3.3. Preprocessing Module •Low quality •Stains and faint letters •Loose formatting •Narrow spaced lines •Connected and Overlapping components •Writing of the verso appearing on the recto due to bleed through The following preprocessing techniques are applied: Figure 3.9: Figure shows the effects of each of the preprocessing phase subprocesses on a sample text region. Background removal and noise reduction We start from the original image (step 1 of Fig. 3.9) that contains stains, writing on the verso appearing on the recto and non uniformity of the background colour which makes it difficult to process. In order to eliminate these issues we first perform a grey-level normalization ( step 2 Fig. 3.9) and apply on the resulting image a bi-dimensional median filter [3]; we subtract the result of the filter from the original image and obtain the result displayed in step 3 of Fig. 3.9. 25 Chapter 3. HMM-Based Text Line Detection System Skew correction Once the background is cleaned we can proceed to correct the skew. Skew is a distortion introduced during the document scanning process. It is understood as the angle of the document paper with respect to the scanner coordinates system. Skew must therefore be corrected one page image at a time, by aligning the text lines present with the horizontal axis. Skew correction is carried out by searching for the angle which maximizes the variance of the vertical projection profile and then applying a rotation operation with the calculated angle [1]. We first execute the run length smear algorithm (RLSA) [6] to enhance the vertical projection profile ( step 4 of Fig. 3.9) and then we calculate the angle which we use to correct the skew by applying a rotation operation. We obtain the final clean and skew corrected seen in step 5 of Fig. 3.9. 3.4 Feature Extraction Since our TLAD approach is based on HMMs, each preprocessed image I(dimensions M× L) must be represented as a sequence of feature vectors. This is done by dividing the already preprocessed image into Dnon-overlapping rectangular regions (from left-to-right) with height equal to the image-height Land calculate the projection profiles in each region (see Fig. 3.10). 12345 Figure 3.10: Partial page image visualization of 5 (D= 5) rectangular regions across over 3 handwritten text lines. For each region, its vertical projection profile is also plotted. In oder to calculate the projection profile we must first binarize the image in order to differentiate foreground from background. We perform an Otsu binarization on the original image I obtaining the binarized image B. For each of the pixel lines of the region d: 1 ≤d≤Dof width m,where m=M /Dwe compute the vertical projection profile value for an specific line l: 1 ≤l≤Lon the image B: odl =X ∀j: ((d−1)·m)<j≤(d·m) B(i, j) X ∀k: 1≤k≤LX ∀j: ((d−1)·m)<j≤(d·m) B(k, j)(3.6) where all feature vectors −→ odcan be calculated with a time computational complexity of Θ(n+ (L· D)), where nis the number of pixels in B. 26 3.5. Evaluation Measures With the calculated projection profiles, the D-dimensional feature vector is constructed for each page/block image row of pixels, by stacking the Dprojection profile values corresponding to that row. Hence, at the end of this process, a sequence of L D-dimensional feature vectors is obtained (see Fig. 3.2). In order to improve the features extracted from the page image we used the RLSA algorithm to smear the lines prior to the vertical projection profile calculation to produce a more emphasized projection. Additionally, we decided to smooth the profile with the help of a rolling average filter [4] in order to eliminate noisy local maxima. Schematics of the resulting effects of the application of these methods can be seen in Fig. 3.11 and also in a real sample in Fig. 3.12 Standard Histogram RLSA Rolling Average Method Applied Handwritten text RLSA smeared pixels Projection profile value Figure 3.11: Schematics of the impact of the RLSA and rolling median filter on the vertical projection profile calculation. 3.5 Evaluation Measures In order to assess the quality of the proposed TLAD approach, two kinds of measures have been adopted: “line error rate” (LER), considered a qualitative measure, which is calculated as the number of incorrectly assigned line labels divided by the total correct line regions; and the “alignment accuracy rate” (AAR) which, addressing the evaluation more from a quantitative point of view, measures the geometrical accuracy of the detected baseline coordinates in respect to the corresponding (correct) reference marks. 27 Chapter 3. HMM-Based Text Line Detection System Figure 3.12: View of the impact of the RLSA and rolling median filter on the vertical projection profile calculation of a sample line. The LER is obtained by comparing the sequences of automatically obtained region labels (ˆ hin eq. 3.5) with the corresponding sequences. This is computed in the same way as the well known WER, with equal editing-costs assigned to deletions, insertions and substitutions [5]. LER is computed for two cases: •Detection - All types of text lines are considered equal and we only measure the accuracy of the system in differentiating text lines from blank spaces. •Classification - The full line type set indicated in subsec. 3.2.2 are maintained and we consider the miss-classification between the different text line types and the reference labels. The AAR evaluation measure is calculated in three phases. First, for each page, we find the best alignment between the system-proposed baseline coordinates (ˆ bin eq. 3.5) and the page reference baseline coordinates (r) by minimizing the accumulated absolute difference. This minimization can be performed by means of dynamic programming. We define Pas a possible alignment (list of operations) between two list of baselines (band r)i: ˆ b=hˆ b1,ˆ b2,..., ˆ bni(3.7) r=hr1, r2, . . . , rmi(3.8) P={pk= ( ˆ bik, rjk) : ˆ bik ∈ˆ b∧rjk ∈r∧1≤k≤n+m}(3.9) 28 3.5. Evaluation Measures We define the cost c(k)of the alignment kas: c(k) = |bik −rjk| · wk. Hence we can define W(P)as the ponderated total cost of the sequence of operations in the following manner: W(P) = |P| X k=1 c(k)(3.10) where wkis the specific ponderation weight associated to the alignment operation k, which takes the following values: 1 for insertion and deletion and 2 for substitution. The alingment cost of two list of baselines band rcan be calculated by means of the unnormalized edit distance d(b,r): d(ˆ b,r) = min P W(P) L(P)(3.11) where L(P)is defined as the number of elementary ponderated edit operations described by P. As we assume the cost of substitution to be double the cost of insertion or deletion L(P)is actually a constant K, for all possible alignment paths. Thus, we ensure that substitution is not favoured over insertion and deletion, therefore allowing us to simplify the last equation to: d(ˆ b,r) = 1 KW(ˆ P)(3.12) where ˆ P= minPW(P)which can be easily resolved by traditional dynamic programming technique. Finally as we want the actual non-ponderated difference between the reference and hypothesis coordinates we define the real cost dr(b,r)as the non ponderated sum of differences of the minimum cost alignment ˆ P. dr(b,r) = |ˆ P| X k=1 |bik −rjk|: (bik, rjk)∈ˆ P(3.13) A graphical representation of an alignment cost calculation can be seen in figure 3.13. In the second phase in order to obtain a global measure, we calculate the mean value (and standard deviation) of the real cost per text line for the total number pages G. In order to do this we define lgas the subsequence of text line reference labels of the corpus page g: lg=hl1, l2, . . . , ls:∀1≤i≤s:li∈ {NL,PL,SL}i (3.14) with which we calculate our global measures: µ= G X g=1 dr(bg,rg) G X g=1 |lg| (3.15) 29 Chapter 3. HMM-Based Text Line Detection System Original Text Extracted Histograms Hypothesis Ground Truth 1 2 X1XL b2b3b4b5b6b7b8b9b10 b11 b12 b13 b14b15 b16 b17 b18 b1 Cost r1r2r3r4r5r6r7r8r9r10 r11 r12 r13 r14 r15 r16 r17 r18 c1c2c3c4c5c6c7c8c9c10 Figure 3.13: Figure shows the schematics of the alignment cost calculation for a single page. σ= v u u u u u u u u t G X g=1 (dr(bg,rg)−µ)2 G X g=1 |lg| (3.16) The resulting mean and standard deviation of the second phase measure the deviation of in pixels. In order to make this measure independent of the page resolution we present it as a percentage of the average height of a text line (in pixels) h: µr=µ h×100 (3.17) σr=σ h×100 (3.18) 3.6 Conclusions During the course of this past chapter we have: 30 Bibliography •Provided an in depth description of our detection and classification system •Detailed the procedure to preprocess the pages and lines to enhance the performance •Described the feature vector extraction process •Defined the required modelling to represent the types of vertical regions and how they are composed to define a page •Presented two types of evaluation measures required to evaluate the performance of our system Bibliography [1] i Gadea, M. P. (2007). Aportaciones al reconocimiento automático de texto manuscrito. PhD thesis, Universidad Politécnica de Valencia. Advisors: Enrique Vidal and Alejandro H. Toselli. [2] Jelinek, F. (1998). Statistical Methods for Speech Recognition. MIT Press. [3] Kavallieratou, E. and Stamatatos, E. (2006). Improving the quality of degraded document images. In Document Image Analysis for Libraries, 2006. DIAL ’06. Second International Conference on, pages 10 pp. –349. [4] Manmatha, R. and Srimal, N. (1999). Scale space technique for word segmentation in handwritten documents. In Proceedings of the Second International Conference on Scale-Space Theories in Computer Vision, SCALE-SPACE ’99, pages 22–33, London, UK. Springer-Verlag. [5] McCowan, I. A., Moore, D., Dines, J., Gatica-Perez, D., Flynn, M., Wellner, P., and Bourlard, H. (2004). On the use of information retrieval measures for speech recognition evaluation. Idiap-RR Idiap-RR-73-2004, IDIAP, Martigny, Switzerland. [6] Wong, K. Y., Casey, R. G., and Wahl, F. M. (1982). Document Analysis System. IBM J.Res.Devel, 26(6):647–656. 31 Chapter 4. Experiments and Results 0 2 4 6 8 10 0 10 15 20 25 30 LER (%) Overlap of columns Number of columns extracted 1 2 3 4 5 Figure 4.3: Plot shows the LER(%) for different number of columns extracted as a function of the region overlap percentage. Plot is performed for an specific number of HMM-states (4), Gaussians per state (8), WIP (-32) and GSF (1). As we can see in Fig. 4.3 the best results for line detection are obtained when considering a low number of horizontal regions for feature extraction (one or two). This is expected as we have simplified the vertical region types: with a small number of features we can easily differentiate a text line from a blank space or non textual region. Regarding the overlap within regions we can see that it impacts the end accuracy and we consider 25% as the best value. Next we will review the impact of the GSF and WIP. It is shown in Fig. 4.4 and Fig. 4.5 that the smaller the GSF value is the more sparse the results are. The best possible value is reached in the zone of 8 to 16 GSF and afterwards it increases. Regarding WIP we can see that with greater insertion penalties we get better detection performance up to −32. We have obtained the best result for the prior LM with the following configuration: HMM states (4), Gaussians per state (8), columns extracted (2), region overlap (25%), GSF (16) and WIP (−32). We perform the same process for the conditional LM and the line-number constrained LM. 38 4.3. Results 0 1 2 3 4 5 6 7 1 2 4 8 16 32 64 LER (%) GSF WIP 0 -2 -4 -8 -16 -32 -64 Figure 4.4: Plot shows the LER (%) for different number of WIP values as a function of the GSF value. Plot is performed for an specific number of HMM-states (4), Gaussians per state (8), columns extracted (1) and region overlap (25%) 0 1 2 3 4 5 6 7 8 9 1 2 4 8 16 32 64 LER (%) GSF WIP 0 -2 -4 -8 -16 -32 -64 Figure 4.5: Plot shows the LER (%) for different number of WIP values as a function of the GSF value. Plot is performed for an specific number of HMM-states (4), Gaussians per state (8), columns extracted (2) and region overlap (25%) In Table 4.2 we report the best figures for LER and AAR achieved through the indicated experimentation process for the three LMs and the heuristic baseline method. The AAR mean and std-dev are given in this case in percentage of the text line average width (80 pixels). Table 4.2: Best detection figures of LER(%) and AAR(%) obtained for our statistical text line analysis approach (STLAD) and the heuristic one (HEUR), using different kind of language models: Prior (PRI), Conditional (CND) and Line-Number Constrained (LN-C). Approach LM LER(%) AAR(%) µrσr STLAD PRI 0.86 9.04 15.91 CND 0.70 8.81 15.40 LN-C 0.34 8.75 13.15 HEUR LN-C – 9.94 29.84 Although the HEUR method does not formally use a LM it requires as input the number of text lines (NL) present in the page thus for comparison reasons we consider it to be using a LN-C model. We observe a trend in Table 4.2: the more restrictive the LM is, the better accuracy is achieved. Similarly the quantitative evaluation shows that more construed LMs provide better baseline coordinate hypotheses (closer to the ground truth ones). In the case of the HEUR method, the obtained AAR (std) is not as good as the STLAD’s with a much higher std-dev. In image 4.6 we can also see the quantitative difference through visual comparison of our proposed method and the base projection method. Is this intuitive visualization we can observe that our method provides a frontier much closer to the bulk of the text thus effectively detecting better the baseline than the histogram projection method. 39 Chapter 4. Experiments and Results Figure 4.6: Image shows the difference between our proposed method (upper side of each coloured region ) and the histogram projection method (lower side) 4.3.2 Classification Experimentation For the classification experimentation the same process as for detection was applied. There are some specific aspects of the classification task that we will now illustrate. 6 8 10 12 14 16 18 1 2 4 8 16 32 64 128 LER (%) Gaussians per state States 1 2 4 6 8 Figure 4.7: Plot shows the LER (%) for different HMMs number of states as a function of the number of Gaussians per state. Plot is performed for an specific number of columns extracted (8), overlap (20%) WIP (-32), GSF (1) with the Prior LM. In Fig. 4.7 we note one of the main differences between the classification and detection tasks: the optimal number of Gaussians per state is reduced from 8 to 4. This reduction is due to the fact 40 4.3. Results that we have added more classes thus also reducing the amount of training data for the text line vertical regions classes. 2 4 6 8 10 12 14 16 0 10 15 20 25 30 LER (%) Overlap of columns Number of columns extracted 1 2 4 6 8 Figure 4.8: Plot shows the LER (%) for different number of columns extracted as a function of overlap percentage between the regions. Plot is performed for an specific number of states in HMM (4), Gaussians per state (4), WIP (-128), GSF (32) with the Prior LM. In Fig. 4.8 we observe that when we evaluate text line classification better results are obtained when we consider a higher amount of page horizontal regions for the feature vector extraction in comparison to the detection task. This is logical as the only way to differentiate between the different text line types is to consider features which allow us to discriminate through the length or indentation of the lines. We show in Table 4.3 the best figures for LER and ARR achieved for the classification task by the three LMs and the heuristic baseline. We can observe in Table 4.3 that the LER values are higher than the ones of the detection task. This is mainly due to the increase in vertical region types, for which the amount of training samples is smaller due to the redistribution. In the classification task we can also see the positive effect of applying more restrictive LMs as they make a positive impact in the overall system accuracy. 41 Chapter 4. Experiments and Results Table 4.3: Best classification figures of LER(%) and AAR(%) obtained for our statistical text line analysis approach (STLAD) and the heuristic one (HEUR), using different kind of language models: Prior (PRI), Conditional (CND) and Line-Number Constrained (LN-C). Approach LM LER(%) AAR(%) µrσr STLAD PRI 6.44 9.22 27.71 CND 4.7 8.92 23.25 LN-C 4.2 8.88 20.25 HEUR LN-C – 9.94 29.84 The AAR measure is also impacted adversely by the reduction of training samples, specially in std-dev, but the system still outperforms the HEUR method. 4.3.3 Vertical Region Models Experimentation Several test where performed with the best configurations of the LMs where the HMMs where changed as to use a linear ranged topology. The range of the topology was learnt from the training data and several values where tried for: •Minimum range: –Mean length of a text line –Mean length of a text line minus standard deviation –First percentile •Maximum range: –Mean length of a text line –Mean length of a text line plus standard deviation –Third percentile All combinations of both values where tested and the results provided did not provide any significant variation from the original results ( with out linear ranged HMMs) for the same training and decoding parameters. Although restricting the HMM topology did not provide an improvement on the classification and detection accuracy for this specific task the technique does seem to be promising and we expect it to have a positive impact in more complex corpus. 42 Bibliography Bibliography [1] Romero, V., Toselli, A. H., Rodríguez, L., and Vidal, E. (2007). Computer Assisted Transcription for Ancient Text Images. In International Conference on Image Analysis and Recognition (ICIAR 2007), volume 4633 of LNCS, pages 1182–1193. Springer-Verlag, Montreal (Canada). 43 CHAPTER 5 GENERAL CONCLUSIONS AND FUTURE WORK Chapter Outline 5.1 Conclusions ..................................... 46 5.2 Publications .................................... 46 5.3 Future Work .................................... 46 Bibliography ....................................... 47 Vicente Bosch Handwritten Text Line Detection based on HMMs Chapter 5. General Conclusions and Future Work 5.1 Conclusions We have shown a new way of addressing text line analysis and detection by using a statistical framework, similar to the already employed in many popular ASR and HTR tasks, that avoids the traditional heuristics approaches generally used to solve this problem. In comparison to the currently more widely used projection approach: •Our approach requires a training phase and supervised data thus it is mostly suitable for large volumes with consistent page structure. •Detection and classification with the new approach is performed in polynomial time thus being up to par in this aspect with the heuristic approaches. •Not only does our method not require the input of the number of lines to detect in the page to work adequately, but also, through the language model, it provides us an easy way to introduce any structural information we may know. •The proposed approach not only detects the baselines but is able to label the text lines; In this aspect surpassing current approaches. •Our system yields baseline coordinates of better quality than the heuristic method. 5.2 Publications The work presented in this paper has been submitted and accepted in: •The sixth workshop on Language Technology for Cultural Heritage, Social Sciences and Humanities (LaTeCH) held in Avignon April 24th, 2012 [1]. LaTeCH is an international workshop associated to the European Chapter of the Association for Computational Linguistics. •The thirteenth International Conference on Frontiers in Handwriting Recognition (ICFHR) that will be held in Bari on September 18-24, 2012. 5.3 Future Work Even though a considerable amount of time and work has gone into the realization of this research, there are still many aspects to explore. The following extensions could be performed: Explore other options for line detection: Currently our approach requires that the images passed contain roughly horizontal text lines in order work adequately. This assumption causes our approach to not be feasible for some historical documents and also for free form text a user might write in an notepad. 46 Bibliography Conduct more experiments on other corpora: Our approach has only been tested on the “CristoSalvador” corpus. It would be interesting to use others to verify that our obtained data/results are reliable. It is envisioned that the proposed stochastic framework serves as a cornerstone to implementing interactive approaches to line detection similar to those used for handwritten text transcription used in [3]. We envision to provide an e-pen interface to allow the user to correct the initial output. The user would be able to perform the following actions: •Perform a gesture to indicate that the current assigned vertical region label is incorrect at which point the system would provide a list of other possible labels found. •Correct the line detected by adding mandatory pass way-point through the e-pen which would force the line path to be recalculated to accommodate for it. •Signal the system, by selecting an area with the e-pen, where regions have not been identified forcing the refine the detection process of that zone. •Cross out detected regions that are in reality non existing in the page. •In the event of having connected components of different lines that have been wrongly segmented or assigned to a line the user could correct this through a gesture. Use Adaptive Learning to improve the recognition through user’s feedback: As the user corrects or validates the vertical regions labels and the baseline coordinates the system can use this new information to further train the statistical model or adapt it to the current task in order to the systems accuracy. In speech recognition, well known Adaptive Learning techniques exist for adapting the acoustic HMM models to the speaker [4] [2] which could be use for our intended purpose. Bibliography [1] Bosch, V., Toselli, A. H., and Vidal, E. (2012). Natural language inspired approach for handwritten text line detection in legacy documents. pages 107–111. [2] Pitz, M., Molau, S., Schlüter, R., and Ney, H. (2001). Vocal tract normalization equals linear transformation in cepstral space. In IN PROC. OF THE EUROSPEECH 01, pages 2653–2656. [3] Toselli, A. H., Romero, V., Pastor, M., and Vidal, E. (2009). Multimodal interactive transcription of text images. Pattern Recognition, 43(5):1824–1825. [4] Woodland, P. C. (2001). Speaker adaptation for continuous density HMMs: A review. In ITRW on Adaptation Methods for Speech Recognition, pages 11–19. 47