Two-dimensional (2D) Grammars And Application To Online Handwritten Mathematical Expression Recognition

With the popularity of mobile terminals such as smart phones and tablets, lots of peopleuse the digital handwritten documents, leading to the birth of handwriting recognitiontechnologies. In the past few decades, Researchers have made a lot of advanced achievementsin single character recognition and text line recognition. However, such technologies arelimited only in one-dimensional documents. It is still very challenge to recognizetwo-dimensional (2D) documents such as electrical schemas, chemical equations andmathematical expressions. The recognition problem of2D documents is difficult due to thetwo dimensional layout, which contains not only syntactic but also2D spatial information. Asresearchers have found that2D grammars have great potential to cope with the structuralrelations of2D documents,2D grammars receive more and more concern. In particular,mathematical expressions are extremely common in our daily life and work. Thus, the studyof the mathematical expression recognition is of much significance.The main goal of this thesis is to study the problem of mathematical expressionrecognition based on2D grammars. This thesis focuses on using context-free grammars toanalyze the structure of mathematical expressions. The main work and contributions of thisthesis are listed as follows:1. A series of production rules of two-dimensional stochastic context-free grammar isproposed. These grammars, covering six spatial relations and190mathematical symbols,are able to describe most of the mathematical expressions.2. An improved CYK parsing algorithm based on searching area is proposed. In thisalgorithm, a searching area is used to merge the nearby sub-expressions. It is moresuitable for online handwriting recognition since there is no limitation on the order of thestrokes.3. A complete system of online handwritten mathematical expression recognition isdeveloped. This system includes five parts: symbol segmentation, symbol recognition,structural analysis,2D grammar and spatial relations model.Although the main focus of this thesis is on mathematical expression recognition, theproposed approach can be also extended to recognize other kinds of two-dimensional documents thanks to the common characteristics of the spatial structure of2D documents.