| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Survey of Methods and Strategies in Character Segmentation
July 1996 (vol. 18 no. 7)
pp. 690-706
Abstract—Character segmentation has long been a critical area of the OCR process. The higher recognition rates for isolated characters vs. those obtained for words and connected character strings well illustrate this fact. A good part of recent progress in reading unconstrained printed and written text may be ascribed to more insightful handling of segmentation.
This paper provides a review of these advances. The aim is to provide an appreciation for the range of techniques that have been developed, rather than to simply list sources. Segmentation methods are listed under four main headings. What may be termed the "classical" approach consists of methods that partition the input image into subimages, which are then classified. The operation of attempting to decompose the image into classifiable units is called "dissection." The second class of methods avoids dissection, and segments the image either explicitly, by classification of prespecified windows, or implicitly by classification of subsets of spatial features collected from the image as a whole. The third strategy is a hybrid of the first two, employing dissection together with recombination rules to define potential segments, but using classification to select from the range of admissible segmentation possibilities offered by these subimages. Finally, holistic approaches that avoid segmentation by recognizing entire character strings as units are described.
[1] 690 H.S. Baird, S. Kahan, and T. Pavlidis, "Components of an Omnifont Page Reader," Proc. Eighth Int'l Conf. Pattern Recognition,Paris, pp. 344-348, 1986.[2] T. Bayer, U. Kressel, and M. Hammelsbeck, "Segmenting Merged Characters," Proc. 11th Int'l Conf. Pattern Recognition, vol. 2. conf. B: Pattern Recognition, Methodology, and Systems, pp. 346-349, 1992.[3] E.J. Bellegarda, J.R. Bellegarda, D. Nahamoo, and K.S. Nathan, "A Probabilistic Framework for On-line Handwriting Recognition," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 225, May 1993.[4] S. Bercu and G. Lorette, "On-line Handwritten Word Recognition: An Approach Based on Hidden Markov Models," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 385, May 1993.[5] M. Berthod and S. Ahyan, "On Line Cursive Script Recognition: A Structural Approach with Learning," Proc. Fifth Int'l Conf. Pattern Recognition, p. 723, 1980.[6] M. Bokser, “Omnidocument Technologies,” Proc. IEEE, vol. 80, no. 7, pp. 1,066-1,078, July 1992.[7] R. Bozinovic and S.N. Srihari, "String Correction Algorithm for Cursive Script Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 4, no. 6, pp. 655-663, June 1982.[8] R. Bozinovic and S.N. Srihari, “Off-Line Cursive Script Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 1, pp. 68-83, 1989.[9] T. Breuel, "Design and Implementation of a System for Recognition of Handwritten Responses on US Census Forms," Proc. IAPR Workshop Document Analysis Systems,Kaiserlautern, Germany, Oct. 1994.[10] C.J.C. Burges, J.I. Be, and C.R. Nohl, "Recognition of Handwritten Cursive Postal Words using Neural Networks," Proc. USPS Fifth Advanced Technology Conf., p. A-117, Nov./Dec. 1992.[11] R.G. Casey and G. Nagy, "Recursive Segmentation and Classification of Composite Patterns," Proc. Sixth Int'l Conf. Pattern Recognition, p. 1,023, 1982.[12] R.G. Casey, "Text OCR by Solving a Cryptogram," Proc. Eighth Int'l Conf. Pattern Recognition,Paris, pp. 349-351, Oct. 1986.[13] R.G. Casey, "Segmentation of Touching Characters in Postal Addresses," Proc. Fifth US Postal Service Technology Conf.,Washington D.C., 1992.[14] M. Cesar and R. Shinghal, "Algorithm for Segmenting Handwritten Postal Codes," Int'l J. Man Machine Studies, vol. 33, no. 1, pp. 63-80, July 1990.[15] M.Y. Chen and A. Kundu, "An Alternative to Variable Duration HMM in Handwritten Word Recognition," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 82, May 1993.[16] C. Chen and J. DeCurtins, "Word Recognition in a Segmentation-Free Approach to OCR," Proc. Int'l Conf. Document Analysis and Recognition,Tsukuba City, Japan, pp. 573-576, Oct. 1993.[17] M. Cheriet, Y.S. Huang, and C.Y. Suen, "Background Region-Based Algorithm for the Segmentation of Connected Digits," Proc. 11th Int'l Conf. Pattern Recognition, vol. 2, p. 619, Sept. 1992.[18] M. Cheriet, "Reading Cursive Script by Parts," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 403, May 1993.[19] G. Dimauro, S. Impedovo, and G. Pirlo, "From Character to Cursive Script Recognition: Future Trends in Scientific Research," Proc. 11th Int'l Conf. Pattern Recognition, vol. 2, p. 516, Aug. 1992.[20] C.E. Dunn and P.S.P. Wang, “Character Segmenting Techniques for Handwritten Text—A Survey,” Proc. 11th Int'l Conf. Pattern Recognition, vol. 2, pp. 577-580, The Hague, Netherlands, 1992.[21] L.D. Earnest, "Machine Recognition of Cursive Writing," C. Cherry, ed., Information Processing, pp. 462-466.London: Butterworth, 1962.[22] R.W. Ehrich and K.J. Koehler, "Experiments in the Contextual Recognition of Cursive Script," IEEE Trans. Computers, vol. 24, no. 2, p. 182, Feb. 1975.[23] D.G. Elliman and I.T. Lancaster, "A Review of Segmentation and Contextual Analysis Techniques for Text Recognition," Pattern Recognition, vol. 23, no. 3/4, pp. 337-346, 1990.[24] R.J. Evey, "Use of a Computer to Design Character Recognition Logic," Proc. Eastern Joint Computer Conf., pp. 205-211, 1959.[25] R.F.H. Farag, "Word-Level Recognition Recognition of Cursive Script," IEEE Trans. Computers, vol. 28, no. 2, pp. 172-175, Feb. 1979.[26] J.T. Favata and S.N. Srihari, "Recognition of General Handwritten Words Using a Hypothesis Generation and Reduction Methodology," Proc. Fifth USPS Advanced Technology Conf., p. 237, Nov./Dec. 1992.[27] R. Fenrich, "Segmenting of Automatically Located Handwritten Numeric Strings," From Pixels to Features III, S. Impedovo and J.C. Simon, eds., Chapter 1, p. 47, Elsevier, 1992.[28] P.D. Friday and C.G. Leedham, "A Pre-Segmenter for Separating Characters in Unconstrained Hand-Printed Text," Proc. Int'l Conf. Image Proc.,Singapore, Sept. 1989.[29] H. Fujisawa, Y. Nakano, and K. Kurino, “Segmentation Methods for Character Recognition: From Segmentation to Document Structure Analysis,” Proc. IEEE, vol. 80, no. 7, pp. 1079-1092, 1992.[30] R. Fukushima and T. Imagawa, "Recognition And Segmentation of Connected Characters With Selective Attention," Neural Networks, vol. 6, pp. 33-41, 1993.[31] P. Gader, M. Magdi, and J-H. Chiang, "Segmentation-Based Handwritten Word Recognition," Proc. USPS Fifth Advanced Technology Conf., Nov./Dec. 1992.[32] A.M. Gillies, "Cursive Word Recognition Using Hidden Markov Models," Proc. USPS Fifth Advanced Technology Conf., Nov./Dec. 1992.[33] M. Gilloux, J.M. Bertille, and M. Leroux, "Recognition of Handwritten Words in a Limited Dynamic Vocabulary," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 417, 1993.[34] M. Gilloux, "Hidden Markov Models in Handwriting Recognition," Fundamentals in Handwriting Recognition, S. Impedovo, ed., NATO ASI Series F: Computer and Systems Sciences, vol. 124, Springer Verlag, 1994.[35] N. Gorsky, "Off-line Recognition of Bad Quality Handwritten Words Using Prototypes," Fundamentals in Handwriting Recognition, S. Impedovo, ed., NATO ASI Series F: Computer and Systems Sciences, vol. 124, Springer Verlag, 1994.[36] L.D. Harmon, "Automatic Recognition of Print and Script," Proc. IEEE, vol. 60, no. 10, pp. 1,165-1,177, Oct. 72.[37] K.C. Hayes, "Reading Handwritten Words Using Hierarchical Relaxation," Computer Graphics and Image Processing, vol. 14, pp. 344-364, 1980.[38] R.B. Hennis, "The IBM 1975 Optical Page Reader: System Design," IBM J. Research and Development, pp. 346-353, Sept. 1968.[39] C.A. Higgins and R. Whitrow, "On-Line Cursive Script Recognition," Proc. Int'l Conf. Human-Computer Interaction—INTERACT '84, Elsevier, 1985.[40] W.H. Highleyman, "Data for Character Recognition Studies," IEEE Trans. Electrical Computation, pp. 135-136, Mar. 1963.[41] T.K. Ho, J.J. Hull, and S.N. Srihari, "A Word Shape Analysis Approach to Recognition of Degraded Word Images," Pattern Recognition Letters, no. 13, p. 821, 1992.[42] M. Holt, M. Beglou, and S. Datta, "Slant-Independent Letter Segmentation for Off-line Cursive Script Recognition," From Pixels to Features III, S. Impedovo and J.C. Simon, eds., p. 41, Elsevier 1992.[43] R.L. Hoffman and J.W. McCullough, "Segmentation Methods for Recognition of Machine-Printed Characters," IBM J. Research and Development, pp. 153-65, Mar. 1971.[44] J.J. Hull and S.N. Srihari, "A Computational Approach to Visual Word Recognition: Hypothesis Generation and Testing," Proc. Computer Vision and Pattern Recognition, pp. 156-161, June 1986.[45] J. Hull, S. Khoubyari, and T.K. Ho, "Word Image Matching as a Technique for Degraded Text Recognition," Proc. Int'l Conf. Pattern Recognition, The Hague, pp. B665-B668, Sept. 1992.[46] F. Kimura, S. Tsuruoka, M. Shridhar, and Z. Chen, "Context-Directed Handwritten Word Recognition for Postal Service Applications," Proc. Fifth US Postal Service Technology Conf.,Washington, D.C., 1992.[47] F. Kimura, M. Shridhar, and N. Narasimhamurthi, "Lexicon Directed Segmentation-Recognition Procedure for Unconstrained Handwritten Words," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 122, May 1993.[48] V.A. Kovalevsky, Character Readers and Pattern Recognition.Washington, D.C.: Spartan Books, 1968.[49] F. Kuhl, "Classification and Recognition of Hand-Printed Characters," IEE Nat'l Convention Record, pp. 75-93, Mar. 1963.[50] A. Kundu, Y. He, and P. Bahl, “Recognition of Handwritten Word: First and Second Order Hidden Markov Model Based Approach,” Pattern Recognition, vol. 22, no. 3, pp. 283-297, Mar. 1989.[51] E. Lecolinet and J-V. Moreau, "A New System for Automatic Segmentation and Recognition of Unconstrained Zip Codes," Proc. Sixth Scandinavian Conf. Image Analysis,Oulu, Finland, p. 585, June 1989.[52] E. Lecolinet, "Segmentation d'images de mots manuscrits," PhD thesis, UniversitéPierre et Marie Curie, Paris, Mar. 1990.[53] E. Lecolinet and J-P. Crettez, "A Grapheme-Based Segmentation Technique for Cursive Script Recognition," Proc. Int'l Conf. Document Analysis and Recognition,Saint Malo, France, p. 740, Sept. 1991.[54] E. Lecolinet, "A New Model for Context-Driven Word Recognition," Proc. Symp. Document Analysis and Information Retrieval,Las Vegas, p. 135, Apr. 1993.[55] E. Lecolinet and O. Baret, "Cursive Word Recognition: Methods and Strategies," Fundamentals in Handwriting Recognition, S. Impedovo, ed., NATO ASI Series F: Computer and Systems Sciences, vol. 124, pp. 235-263, Springer Verlag, 1994.[56] M. Leroux, J-C. Salome, and J. Badard, "Recognition of Cursive Script Words in a Small Lexicon," Int'l Conf. Document Analysis and Recognition,Saint Malo, France, p. 774, Sept. 1991.[57] S. Liang, M. Ahmadi, and M. Shridhar, "Segmentation of Touching Characters in Printed Document Recognition," Proc. Int'l Conf. Document Analysis and Recognition,Tsukuba City, Japan, pp. 569-572, Oct. 1993.[58] G. Lorette and Y. Lecourtier, "Is Recognition and Interpretation of Handwritten Text: A Scene Analysis Problem?" Pre-Proc. IWFHR III, p. 184,Buffalo, N.Y., May 1993.[59] Y. Lu, "On the Segmentation of Touching Characters," Int'l Conf. Document Analysis and Recognition,Tsukuba, Japan, pp. 440-443, Oct. 1993.[60] S. Madhvanath and V. Govindaraju, "Holisitic Lexicon Reduction," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 71, May 1993.[61] M. Maier, "Separating Characters in Scripted Documents," Proc. Eighth Int'l Conf. Pattern Recognition,Paris, p. 1,056, 1986.[62] J-V. Moreau, B. Plessis, O. Bourgeois, and J-L. Plagnaud, "A Postal Check Reading System," Int'l Conf. Document Analysis and Recognition,Saint Malo, France, p. 758, Sept. 1991.[63] R. Nag, K.H. Wong, and F. Fallside, "Script Recognition Using Hidden Markov Models," IEEE ICASSP,Tokyo, pp. 2,071-2,074, 1986.[64] T. Nartker, ISRI 1992 Annual Report, Univ. of Nevada, Las Vegas, 1992.[65] T. Nartker, ISRI 1993 Annual Report, Univ. of Nevada, Las Vegas, 1993.[66] K. Ohta, I. Kaneko, Y. Itamoto, and Y. Nishijima, Character Segmentation of Address Reading/Letter Sorting Machine for the Ministry of Posts and Telecommunications of Japan, NEC Research and Development, vol. 34, no. 2, pp. 248-256, Apr. 1993.[67] H. Ouladj, G. Lorette, E. Petit, J. Lemoine, and M. Gaudaire, "From Primitives to Letters: A Structural Method to Automatic Cursive Handwriting Recognition," Proc. Sixth Scandinavian Conf. Image Analysis,Finland, p. 593, June 1989.[68] T. Paquet and Y. Lecourtier, "Handwriting Recognition: Application on Bank Cheques," Proc. Int'l Conf. Document Analysis and Recognition,Saint Malo, France, p. 749, Sept. 1991.[69] S.K. Parui, B.B. Chaudhuri, and D.D. Majumder, "A Procedure for Recognition of Connected Handwritten Numerals," Int'l J. Systems Science, vol, 13, no. 9, pp. 1,019-1,029, 1982.[70] B. Plessis, A. Sicsu, L. Heute, E. Lecolinet, O. Debon, and J-V. Moreau, "A Multi-Classifier Strategy for the Recognition of Handwritten Cursive Words," Proc. Int'l Conf. Document Analysis and Recognition,Tsukuba City, Japan, pp. 642-645, Oct. 1993.[71] J. Rocha and T. Pavlidis, "New Method for Word Recognition Without Segmentation," Proc. SPIE Character Recognition Technologies, vol. 1,906, pp. 74-80, 1993.[72] K.M. Sayre, "Machine Recognition of Handwrittten Words: A Project Report," Pattern Recognition, vol. 5, pp. 213-228, 1973.[73] J. Schuermann, "Reading Machines," Proc. Sixth Int'l Conf. Pattern Recognition,Munich, Germany, 1982.[74] G. Seni and E. Cohen, "External Word Segmentation of Off-Line Handwritten Text Lines," Pattern Recognition, vol. 27, no. 1, pp. 41-52, Jan. 1994.[75] A.W. Senior and F. Fallside, "An Off-line Cursive Script Recognition System Using Recurrent Error Propagation Networks," Pre-Proc. IWFHR III,Buffalo, N.Y., p. 132, May 1993.[76] M. Shridhar and A. Badreldin, “Recognition of Isolated and Simply Connected Handwritten Numerals,” Pattern Recognition, vol. 19, no. 1, pp. 1-12, 1986.[77] J.C. Simon, “Off-Line Cursive Word Recognition,” Proc. IEEE, vol. 80, no. 7, pp. 1,150-1,160, 1992.[78] R.M.K. Sinha, B. Prasada, G.H. Houle, and M. Sabourin, “Hybrid Contextual Text Recognition with String Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 9, pp. 915-923, Sept. 1993.[79] M.E. Stevens, "Automatic Character Recognition—A State of the Art Report," MES National Bureau of Standards Technical Note no. 112, 1961.[80] C.C. Tappert, "Cursive Script Recognition by Elastic Matching," IBM J. Research Development, vol. 26, pp. 765-771, Nov. 1982.[81] C.C. Tappert, C.Y. Suen, and T. Wakahara, “The State of the Art in On-Line Handwriting Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 8, pp. 179-190, Aug. 1990.[82] I. Taylor and M. Taylor, The Psychology of Reading. Academic Press, 1983.[83] S. Tsujimoto and H. Asada, "Major Components of a Complete Text Reading System," Proceedings IEEE, vol. 80, no. 7, pp. 1,133-1,149, July 1992.[84] J. Wang and J. Jean, "Segmentation of Merged Characters by Neural Networks and Shortest Path," Pattern Recognition, vol. 27, no. 5, pp. 649-658, May 1994.[85] J.M. Westall and M.S. Narasimha, "Vertex Directed Segmentation of Handwritten Numerals," Pattern Recognition, vol. 26, no. 10, pp. 1,473-1,186, Oct. 1993.[86] R.A. Wilkinson, Proc. First Conf. Census Optical Character Recognition System, Report No. PB92-238542/XAB, National Institute of Standards and Tech nology, Gaithersburg, Md., May 1992.[87] R.A. Wilkinson, "Comparison of Massively Parallel Segmenters," National Institute of Standards and Technology technical report, Gaithersburg, Md., Sept. 1992.[88] R.A. Wilkinson, Proc. Second Conf. Census Optical Character Recognition Systems, National Institute of Standards and Tech nology, Gaithersburg, Md., Feb. 1993.[89] B.A. Yanikoglu and P.A. Sandon, "Recognizing Off-Line Cursive Handwriting," Proc. Computer Vision and Pattern Recognition, 1994.
Index Terms:
Optical character recognition, character segmentation, survey, holistic recognition, Hidden Markov Models, graphemes, contextual methods, recognition-based segmentation.
Citation:
Richard G. Casey, Eric Lecolinet, "A Survey of Methods and Strategies in Character Segmentation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 7, pp. 690-706, July 1996, doi:10.1109/34.506792
