Use of Markov Processes in Writing Recognition
Utilisation des Processus Markoviens en Reconnaissance de L'écriture
OPEN ACCESS
In this paper, we present a brief survey on the use of different types of Markov models in writing recognition. Recognition is done by a posteriori pattern class probability calculus. This computation implies several terms which, according to the dependency hypotheses akin to the considered application, can be decomposed in elementary conditional probabilities. Under the assumption that the pattern may be modeled as a uni-or two-dimensional stochastic process (random field) presenting Markovian properties, local maximisations of these probabilities result in maximum pattern likelihood . We have studied throughout the article several cases of subpattern probability conditioning. Each case is accompanied by practical illustrations related to the field of writing recognition.
Résumé
Dans cet article, nous présentons une étude sur l'emploi de différents types de modèles de Markov en reconnaissance de l'écriture. La reconnaissance est obtenue par calcul de la probabilité a posteriori de la classe d'une forme. Ce calcul fait intervenir plusieurs termes qui, suivant certaines hypothèses de dépendance liées à l'application traitée, peuvent se décomposer en probabilités conditionnelles élémentaires. Si l'on suppose que la forme suit un processus stochastique uni- ou bidimensionnel qui de plus vérifie les propriétés de Markov, alors la maximisation locale de ces probabilités permet l'atteinte d'un maximum de la vraisemblance de la forme. Nous avons étudié plusieurs cas de conditionnement des probabilités élémentaires des sous-formes. Chaque étude est accompagnée d'illustrations pratiques relatives au domaine de la reconnaissance de l'écriture imprimée et/ou manuscrite.
Markov Models, Random fields, Stochastic Processes, Writing Recognition.
Mots clés
Modèles de Markov, Champs aléatoires, Processus stochastiques, Reconnaissance automatique de l'écriture .
[Abe65] K.Abend,T. J. Harley, and L. N.Kanal.Classification of Binary Random Patterns. IEEETrans. Inform. Theory, 1(11) : 538-544, 1965.
[Aga93] O. E. Agazzi and S. Kuo. Hidden Markov Model Based Optical Character Recognition in the Presence of Deterministic Transformation . Pattern Recognition, 26(12) : 1813-1826, February 1993.
[Ani 91] J. C. Anigbogu and A. Belaïd. Recognition ofMultifont Text Using Markov Models. In 7tt` Scandinavian Conference on Image Analysis, volume I, pages 469-476, August 1991.
[Ani 95] J. C. Anigbogu and A. Belaïd. Hidden Markov Models in Text Recognition. International Journal of Pattern Recognition and Artificial Intelligence, 9(5), 1995.
[Bah 83] L. R. Bahl, F. Jelinek, and R. L. Mercer. A Maximum Likelihood Approach to Continuous Speech Recognition. IEEE Transactions on PAMI, 5(2) : 179-190, March 1983.
[Bah 86] L. R. Bahl, P. F. Brown, P. V. de Souza, and R. L. Mercer. Maximum Mutual Information Estimation of Hidden Markov Model Parameters for Speech Recognition. In IEEE-ICASSP, volume 1, pages 49-52. IEEE, 1986.
[Bah 88] L. R. Bahl, P. F. Brown, P. V. de Souza, and R. L. Mercer. A New Algorithm for the Estimation of Hidden Markov Model Parameters. In IEEE-ICASSP, volume 1, pages 493-496, 1988.
[Ban 67] L. E.Baumand J. A.Egon.An Inequality with Applications to Statistical Estimation for Probabilistic Functions of a Markov Process and to a Model for Ecology. Bull, Ants. volume 73, pages 360-363, 1967.
[Ban 68] L. E.Baumand T. Petrie. Statistical Inference for Probabilistic Functions of Finite State Markov Chains.Annals of Mathematics and Statistics, 37 1554-1563,1968.
[Bau 72] L. E. Baum. An Inequality and Associated Maximization Technique for Probabilistic Functions of Markov Process.Inequalities, 3, pages 1-8, 1972.
[Bel 94a] A. Belaïd and J. C. Anigbogu. Mise à contribution de plusieurs classifieurs pour la reconnaissance de textes multifonte. Traitement du signal, 11(1) :57-75, 1994.
[Bel94b] A. Belâid and G. Saon. Use of stochastic models in text recognition . In KOSEF-CNRS French-South Korean Workshop on Text Recognition, pages 79-98, September 1994.
[Ben 96] N. BenAmara and A. Belaïd. Printed PAW Recognition Based on Planar Hidden Markov Models. In 13th International Conference on Pattern Recognition, Viena, Austria, 1996.
[Ber92] S. Bercu, B. Delyon, and G. Lorette.Segmentation parune méthodede reconnaissance d'écriturecursive en-ligne. In A. Belaïd, editor, Traitement del'écriture etdes documents,Actesducolloque CNED'92,pages 144151, Nancy,juillet1992.
[Ber 93] S. Bercu and G. Lorette. On-line Handwritten Word Recognition an Approach Based on Hidden Markov Models. In Proc. of the 3rd International Workshop on Frontiers in Handwriting Recognition,pages 385-390,1993.
[Bos 94] C. B. Bose and S. Kuo. Connected and Degraded Text Recognition Using Hidden Markov Model. Pattern Recognition, 27(10) : 1345-1363, 1994.
[Boz 89] R. M. Bozinovic and S. N. Srihari. Off-Line Cursif Script Word Recognition. IEEE Transactions on PAMI, 11, Jan. 1989.
[Che 92] M. Y Chen, A. Kundu, J. Zhou, and S. N. Srihari. Off-Line Handwritten Word Recognition Using Hidden Markov Model. In USPS'92, 1992.
[Che 93a] M. Y Chen and A. Kundu. An Alternative to Variable Duration HMM in Handwritten Word Recognition. InProc. IWFHR-3,pages 82-91, Paris, 1993.
[Che 93b] M. Y. Chen, A. Kundu, and S. N. Srihari. Handwritten Word Recognition Using Continous Density Variable Duration Hidden Markov Model. In Second International Conference on Document Analysis and Recognition (ICDAR'93), pages 105-108, Tsukuba, Japan, 1993,
[Coh 94] E. Cohen, J. J. Hull, and S. N. Srihari. Control Structure for Interpreting Handwritten Addresses.IEEE Transactions on PAMI, 16(5): 1049-1055, 1994.
[Cre941 J.P Crettez. Premierdegré decaractérisation des écritures manuscrites : essaideregroupement des écritures enfamilles.InActesdu 3èmeColloque Nationalsur l'ÉcritetleDocument, pages 71-81, Rouen,juillet1994.
[Cre 96] J . P. Crettez, M. Gilloux, and M. Leroux. Que ditla "Main" du scripteur aux "Yeux" du lecteur. InActesdu 4ème ColloqueNationalsur l'Écritet leDocument,pages 291-296, Nantes,France, July 1996.
[Der 89] H. Derin and P. A. Kelly. Discrete-Index Markov-Type Random Processes.Proceedings of the IEEE, 77(10) : 1485-1510, 1989.
[Eph 87] Y. Ephraim, A. Dembo, and L. R. Rabiner. A Minimum Discrimination Information Approach for Hidden Markov Modeling. InIEEE-ICASSP, volume 1, pages 25-28. IEEE, 1987.
[For 73] G. D. Forney. The Viterbi Algorithm.Proceedings of the IEEE, 661(3), 1973. [Gem 84] S. Geman and D. Geman. Stochastic Relaxation, Gibbs Distributions and the Bayesian Restoration of Images. IEEE Transactions on PAMI, 6(6) : 721-741, 1984.
[Gil 92a] A. M. Gillies. Cursive Word Recognition Using Hidden Markov Models. In USPS'92, pages 557-562, 1992.
[Gil 92b] M. Gilloux and M. Leroux.Approchesmarkoviennes en reconnaissance de l'écriturecursive. In A. Belaïd, editor, Traitementde l'écriture etdes documents, Actes du colloque CNED'92, pages 152-159, Nancy, juillet 1992.
[Gil 92c] M. Gilloux and M. Leroux. Recognition of Cursive Script Amounts on Postal Cheques. In USPS advanced Technology Conference, pages 545556, 1992.
[Gil 93] M. Gilloux, M. Leroux, and J. M. Bertille. Strategies for Handwritten Words Recognition Using Hidden Markov Models. In Second International Conference on Document Analysis and Recognition (ICDAR'93), pages 299-304, Tsukuba, City Science Japan, 1993.
[Gil 94] M. Gilloux. Reconnaissance dechiffres manuscritsparmodèlede Markov pseudo-2D. InActesdu 3`"Le ColloqueNationalsur l'ÉcritetleDocument, pages l I-17, Rouen, France, 1994.
[Gop 89] P.S. Gopalakrishnan and al. A Generalization of theBaum Algorithm to Rational Objective Functions. InIEEE-ICASSP, volume 2, pages 631634. IEEE, 1989.
[Hul 83] J. J. Hull, S. N. Srihari, and R. Choudhari. An Integrated Algorithm for Text Recognition : Comparison with a Cascaded Algorithm. IEEE Transactions on PAMI, PAMI-5(4) : 384-395, July 1983.
[Jel 80] F. Jelinek and R. L. Mercer. Interpolated Estimation of Markov Source Parameters from Sparse Data. Workshop on Pattern Recognition in Practice, March 1980.
[Jen 87] F. C. Jeng and J. W. Woods. On the Relationship of the Markov Mesh to the NSHP Markov Chain.Pattern Recognition Letters, 5(4) : 273-279, 1987.
[Kri 90] A. Kriouile, J. F. Mari, and J. P. Haton. Some Improvements in Speech Recognition Algorithms Based on HMM. InIEEE-ICASSP, pages 545548. IEEE, 1990.
[Kuo 94] S. Kuo and O. E. Agazzi. Keyword Spotting in Poorly Printed Documents Using Pseudo 2-D Hidden Markov Models.IEEE Transactions on PAMI, 16(g) : 842-848, 1994.
[Lem 93] B. Lemarié. Practical Implementation of A Radial Basis Function Network For Handwritten Digit Recognition. In Second International Conference on Document Analysis and Recognition (ICDAR'93), pages 412-415, Tsukuba, Japan, 1993.
[Lem 96] B. Lemarié, M. Gilloux, and M. Leroux. Un modèleneuro-markovien contextuel pour la reconnaissance de l'écriture manuscrite. In Actes 10ème Congrès AFCET de Reconnaissance des Formes et Intelligence Artificielle,Rennes, France, 1996.
[Lev 83] S. E. Levinson, L. R. Rabiner, and M. M. Shondi. An Introduction to the Application of the Theory of Probabilistic Functions of a Markov Process to Automatic Speech Recognition. The Bell System Technical Journal, 62(4), 1983.
[Lev 92] E. Levin and R. Pieraccini. Dynamic Planar Warping for Optical Character Recognition. In IEEE-ICASSP, volume III, pages 149-152. IEEE, 1992.
[Mer 88] B. Merialdo. Phonetic Recognition Using Hidden Markov Models and Maximum Mutual Information Training. InIEEE-ICASSP, volume 9, pages 111-114. IEEE, 1988.
[Neu 75] D. L. Neuhoff. The Viterbi Algorithm as an Aid in Text Recognition. IEEE Transactions on Information Theory, pages 222-226, March 1975.
[Nor 94] Y. Normandin, R. Cardinand, and R. DeMori. High-Performance Connected Digit Recognition Using Maximum Mutual Information Estimation.IEEE Transactions on Speech andAudio Processing, 2(2):299-311, April 1994.
[Pre 75] D. Preuss. Two-Dimensional Facsimile Source Coding Based on a Markov Model .NTZ 28, 5(4) :M8-363,1975.
[Rab 89] L. R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77(2), February 1989.
[Sao 94] G. Saon, A. Belaïd, and Y. Gong. Off-line handwriting recognition by statistical correlation. In MVA'94 IAPR Workshop on Machine Vision Applications, pages 371-374, Japan, 1994.
[Sao 95] G. Saon, A. Belaïd, and Y. Gong. Stochastic Trajectory Modeling for Recognition of Unconstrained Handwritten Words. InThird International Conference on Document Analysis and Recognition (ICDAR'95), pages 508-511, Montréal,Canada, 1995.
[Sao 96a] G. Saon and A. Belaïd. High Performance Unconstrained Word Recognition System Combining HMMs and Markov Random Fields. International Journal of Pattern Recognition and Artificial Intelligence Special Issue on Automatic Bankcheck Processing, 1996. Accepted for publication.
[Sao 96b] G. Saon and A. Belaïd. Recognition of Unconstrained Handwritten Words Using Markov Random Fields and HMMs. In Fifth International Workshop on Frontiers in Handwriting Recognition (IWFHR5), University of Essex, England, September 1996. In press.
[Shi 79] R. Shinghal and G. T. Toussaint. Experiments in Text Recognition with Modified Viterbi Algorithm.IEEE Transactions on PAMI, 2(l): 184-192, March 1979.
[Sri 84] S. N. Srihari. Computer Text Recognition and Error Correction . IEEE Computer Society Press, Silver Spring, MD, 1984,
[Sri 93] S. N. Srihari, V. Govindaraju, and A. Shekhawat. Interpretation of Handwritten Addresses in US Mailstream. In Second International Conference on DocumentAnalvsis and Recognition (ICDAR'93), pages 291-294, Tsukuba,Japon, Oct. 20- 22 1993.
[Tou 78] G. T. Toussaint. The Use of Context in Pattern Recognition . Pattern Recognition, 10 : 189-204, 1978.