Handwritten mathematical expression recognition using graph grammars

Abstract

Bu tez elyazısı matematik ifadelerin tanınmasında çizge grameri kullanımını sunmaktadır. Bu problemin zorluğu normal optik ifade tanıma işleminin sahip olduğu problemlerin üzerine matematik ifadelerin 2 boyutlu yapısının anlamlandırılmasından gelmektedir.Çözümleme işlemi sırasında mümkün olduğunca çok veriyi ifade edebilmek için çizge gramerlerini kullanıyoruz. Yöntemimizin bir diğer yönü de alternatif çözümlemelerin korunup bunlar arasında ön yüksek olabilirliğe sahip olanın kastedilen ifade olarak belirlenmesidir. Olabilirlik değerleri ifadelerin yapısal istatistiklerinden yaklaşık olarak hesaplanmaktadır.Sistemin bölütleme adımı zaman bilgisi ile çizgileri ayırmakta, mesafe bilgini kullanarak gruplandırmaktadır. Daha sonra semboller zaman boyutunda esneklik sağlayabilmek için çevrimdışı özelliklerin kullanıldığı tanıma motorunda tanımlanmaktadır. Tanıma motoru bir destek vektör makinesi ve yapay sinir ağının bir araya getirilmesi olup en iyi 3 tanıma sonucunu döndürmektedir.Çözümleme süreci gramer içerisinde tanımlanmış kuralların ardı ardına uygulanması ile girdiyi temsil eden çizgeye yeni düğümler eklemektedir. İşlem tamamlandığında bir ya da daha fazla düğüm tanımlamış ifadeyi teslim etmektedir.Kullanıcı arabirimimiz karakter tanıma hatalarının düzeltilebilinmesine olanak veren araçları da içermektedir. Arabirim LaTeX MathML ve girdi ifadenin makine yazısı çizimini üretebilmektedir.15 kullanıcıdan 57 farklı ifadeyi ve 70 karakterli bir alfabe için örnek ifadeler ve bir başına karakterler toplanmıştır. Toplam 1710 matematik ifade ve 10500 bir başına karakter bulunmaktadır. Tüm bu örnekler kullanıcıların doğal el yazıları şeklinde toplanmıştır.

This thesis presents a graph grammar approach for the recognition of handwritten mathematical expressions. The problem is challenging, as it includes the sub-problems of character recognition (OCR) on top of 2-dimensional structure understanding of mathematical expressions.We use graph grammars for structural understanding of the expressions in order to represent as much information as possible in the parse process. Another important aspect of our system is the fact that all alternative parses are evaluated and the one with maximum likelihood is selected as the intended expression. The likelihoods are estimated according to structural relationships statistics.The segmentation step segments and groups strokes according to timestamps and distance in space respectively. Then, symbols are recognized by the OCR engine which uses offline features to allow for flexibility in time dimension. The extracted features are used in an ANN and SVM combination engine returning top-3 character alternatives and confidence values.The parse process expands the graph by generating new tokens with repeated application of grammar rules. At the end, one or more tokens contain the full expression.Our user interface gives tools to the user to correct OCR errors and it can generate LaTeX and MathML codes and graphical rendering of the input handwritten mathematical expression.An extensive collection of mathematical expression and isolated symbols are collected from 15 users for 57 different expressions from a 70-character alphabet. There are, in total, 1710 mathematical expressions and 10500 isolated characters. All samples are in the natural writing styles of the users.