Abstract
Machine recognition of mathematical expressions is not trivial even when all the individual characters and symbols in an expression can be recognized correctly. In this paper, we propose to use Definite Clause Grammar (DCG) as a formalism to define a set of replacement rules for parsing mathematical expressions. With DCG, we are not only able to define the replacement rules concisely, but their definitions are also in a readily executable form. However, backtracking parsers like Prolog interpreters, which execute DCG directly, are by nature inefficient. Thus we propose some methods here to increase the efficiency of the parsing process. Experiments done on some typical mathematical expressions show that our proposed methods can achieve speedup ranging from 10 to 70 times, making mathematical expression recognition more feasible for real-world applications.
Chapter PDF
Keywords
References
R. H. Anderson. Syntax-directed recognition of hand-printed 2-D mathematics. In M. Klerer and J. Reinfelds, editors, Interactive Systems for Experimental Applied Mathematics, pages 436–459. Academic Press, New York, 1968.
A. Beláid and J.-P. Haton. A syntactic approach for handwritten mathematical formula recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1), Jan. 1984.
K. F. Chan. and D. Y. Yeung. Elastic structural matching in recognizing on-line handwritten alphanumeric characters. Technical Report HKUST-CS98-07, Dept. of Computer Science, Hong Kong University of Science and Technology, Mar. 1998.
S. K. Chang. A method for the structural analysis of 2-D mathematical expressions. Information Sciences, 2(3):253–272, 1970.
Y. A. Dimitriadis and J. L. Coronado. Towards an ART based mathematical editor, that uses on-line handwritten symbol recognition. Pattern Recognition, 28(6):807–822, 1995.
F. Grossman, R. J. Klerer, and M. Klerer. A language for high-level programming of mathematical applications. Proceedings of the International Conference on Computer Languages, pages 31–40, Miami Beach, FL, 1988.
L. Lamport, editor. LATEX — A Document Preparation System — User's Guide and Reference Manual. Addison-Wesley, Reading, MA, 1985.
H.-J. Lee and M.-C. Lee. Understanding mathematical expressions using procedure-oriented transformation. Pattern Recognition, 27(3):447–457, 1994.
M. Okamoto and A. Miyazawa. An experimental implementation of a document recognition system for papers containing mathematical expressions. In H. S. Baird, H. Bunke, and K. Yamamoto, editors, Structured Document Image Analysis, pages 36–53. Springer-Verlag, Berlin, 1992.
F. Pereira and D. Warren. Definite clause grammars for language analysis — a survey of the formalism and comparison with augmented transition networks. Artificial Intelligence, 13, 1980.
J. J. Pfeiffer, Jr. Parsing graphs representing two dimensional figures. Proceedings of the IEEE Workshop on Visual Languages, pages 200–206, Seattle, WA, 1992.
S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, N.J., 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, KF., Yeung, DY. (1998). Towards efficient structural analysis of mathematical expressions. In: Amin, A., Dori, D., Pudil, P., Freeman, H. (eds) Advances in Pattern Recognition. SSPR /SPR 1998. Lecture Notes in Computer Science, vol 1451. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0033264
Download citation
DOI: https://doi.org/10.1007/BFb0033264
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64858-1
Online ISBN: 978-3-540-68526-5
eBook Packages: Springer Book Archive