A Shape Analysis Model with Applications to a Character Recognition System
April 1994 (vol. 16 no. 4) pp. 393-404
A method for the recognition of multifont printed characters is proposed, giving emphasis to the identification of structural descriptions of character shapes using prototypes. Noise and shape variations are modeled as series of transformations from groups of features in the data to features in each prototype. Thus, the method manages systematically the relative distortion between a candidate shape and its prototype, accomplishing robustness to noise with less than two prototypes per class, on average. The method uses a flexible matching between components and a flexible grouping of the individual components to be matched. A number of shape transformations are defined, including filling of gaps, so that the method handles broken characters. Also, a measure of the amount of distortion that these transformations cause is given. Classification of character shapes is defined as a minimization problem among the possible transformations that map an input shape into prototypical shapes. Some tests with hand-printed numerals confirmed the method's high robustness level.
[1] 393S. Mori, C. Y. Suen, and K. Yamamoto, "Historical review of ocr research and development,"Proc. IEEE, vol. 80, no. 7, pp. 1029-1058, July 1992.
[2] S. Kahan, T. Pavlidis, and H. S. Baird, "On the recognition of printed characters of any font and size,"IEEE Trans. Patt. Anal. Machine Intell., vol. PAMI-9, pp. 274-288, 1987.
[3] M. Bokser, "Omnidocument technologies,"IEEE Proc., vol. 80, pp. 1066-1078, July 1992.
[4] S. Rice, J. Kanai, and T. Nartker, "A report on the accuracy of OCR devices," Information Science Research Inst., Univ. of Nevada, Las Vegas, Tech. Rep., 1992.
[5] L. Lam and C. Y. Suen, "Structural classification and relaxation matching of totally unconstrained handwritten Zip-code numbers,"Patt. Recogn., vol. 21, no. 1, pp. 19-31, 1988.
[6] J. Hopcroft and J. Wong, "Linear time algorithm for isomorphism of planar graphs," inProc. 6th Annual ACM Symp. Theory of Computing, New York, pp. 172-184, April, 1974.
[7] S. L. Xie and M. Suk, "On machine recognition of hand-printed Chinese characters by feature relaxation,"Patt. Recogn., vol. 21, no. 1, pp. 1-7, 1988.
[8] S. Lu, Y. Ren, and C. Suen, "Hierarchical attributed graph representation and recognition of handwritten Chinese characters,"Pattern Recogn., vol. 24, no. 7, pp. 617-632, 1991.
[9] H. Yamada, "Contour DP matching method and its application to handprinted Chinese character recognition," inProc. 7th Int. Conf. Pattern Recognition, Montreal, Canada, July, 1984, pp. 389-392.
[10] L. Wang and T. Pavlidis, "Direct gray scale extraction of features for character recognition,"IEEE Trans. Pattern Anal. Machine Intell., vol. 15, no. 10, pp. 1053-1067, Oct. 1993.
[11] G. T. Toussaint, "The relative neighbourhood graph of a finite planar set,"Pattern Recogn., vol. 12, pp. 261-268, 1980.
[12] A. Sanfeliu and K. Fu, "A distance measure between attributed relational graphs for pattern recognition,"IEEE Trans. Syst., Man, Cybern., vol. 13, no. 3, pp. 353-362, May 1983.
[13] D. Burr, "Elastic matching of line drawings," inProc. 5th Int. Conf. Pattern Recognition, Miami Beach, FL, Dec. 1980, pp. 223-228.
[14] L. Shapiro and R. Haralick, "Structural descriptions and inexact matching,"IEEE Trans. Pattern Anal. Machine Intell., vol. 3, no. 5, pp. 504-519, Sept. 1981.
[15] F. Haray,Graph Theory. New York: Addison-Wesley, 1972, p. 107.
[16] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.
[17] N. Robertson and P. D. Seymour, "Disjoint paths--A survey,"SIAM J. Algebraic Discrete Methods, vol. 6, pp. 300-305, 1985.
[18] J. Pearl,Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, Mass: Addison-Wesley, 1984.
[19] L. Pintsov, "One view of the methodology in handwriting character recognition,"SPIE/IS&T's Symp. Electronic Imaging, Science and Technology, San Jose, CA, Feb. 9-14, 1992, p. 115.
[20] W. J. Sakoda, J. Zhou, and T. Pavlidis, "Feature extraction directly from gray scale with applications to an address recognition system,"Postal Service, 5th. Advanced Technology Conf., Washington, DC, Nov. 30-Dec. 2, 1992, pp. 727-741.
Index Terms:
character recognition; noise; image sequences; shape analysis model; character recognition system; multifont printed characters; structural descriptions; character shapes; relative distortion; robustness; flexible matching; flexible grouping; shape transformations; distortion; minimization problem; hand-printed numerals
Citation:
J. Rocha, T. Pavlidis, "A Shape Analysis Model with Applications to a Character Recognition System," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 4, pp. 393-404, Apr., 1994
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb