Mathematical expression recognition

Mathematical expression recognition A Degree Thesis Submitted to the Faculty of the Escola Tècnica d’Enginyeria de Telecomunicació de Barcelona Universitat Politècnica de Catalunya by Ignasi Mas Méndez In partial fulfilment of the requirements for the degree in AUDIOVISUAL SYSTEMS FOR TELECOMMUNICATIONS ENGINEERING Advisor:Antoni Gasull Barcelona, February 2016 Abstract Nowadays, technology is proposing complex solutions for daily problems. This solutions include many engines. On this project, we are developing one of this engines, the Online handwritten mathematical expression recognition. Since the first OCR were proposed, many details have been studied. One of them, focused on those cases where we are trying to recognize handwritten symbols, proposed to use as input data not only an image, but the whole path that the user has written, in order to give more useful information. In the case of mathematical expression recognition, this idea can be used to convert this data into a mathematical expression, in order to be stored or even processed (for example, to develop a handwritting calculator). This objective is too complex to be tackled in one single project. Now we are at the beginning, so this project will focus on developing the core of this system and study its possible improvements. 1 Resum Estem en un moment en que la tecnologia proposa solucions complexes per problemes quotidians. Aquestes solucions fan ús de diversos motors. En aquest projecte un d’aquests ha estat desenvolupat, el reconeixement Online d’expressions matemàtiques escrites a mà. Des del naixement dels primers OCR s’han estudiat molts detalls. Un d’ells, relacionat amb els casos on s’intenta reconèixer símbols escrits a mà, proposa en comptes d’utilitzar imatges com a informació d’entrada, utilitzar el camí recorregut per l’usuari en l’escriptura. En el cas del reconeixement d’expressions matemàtiques, aquesta idea ens ajuda a convertir aquestes dades d’entrada en expressions matemàtiques, per ser guardades o fins i tot processades (un exemple seria el desenvolupament d’una calculadora d’escriptura a mà). L’objectiu és massa complex per ser abordat per un sol projecte. Com estem a l’inici, aquest projecte es centrará en el desenvolupament del nucli del sistema i en l’estudi de les possibles millores. 2 Resumen Estamos en un momento en que la tecnología propone soluciones complejas para problemas cuotidianos. Estas soluciones usan varios motores. En este proyecto se ha desarrollado uno de estos, el reconocimiento Online de expresiones matemáticas escritas a mano. Desde que surgieron los primeros OCR se han estudiado muchos detalles. Uno de ellos, relacionado con los casos donde se pretende reconocer a símbolos escritos a mano, propone usar como información de entrada el camino recorrido por el usuario en su escritura en vez de imágenes. En el caso del reconocimiento de expresiones matemáticas, esta idea nos permite convertir estos datos de entrada en expresiones matemáticas que pueden ser guardadas o incluso procesadas (por ejemplo si se quiere desarrollar una calculadora de escritura a mano). El objetivo es demasiado complejo como para ser abordado en un solo proyecto. Al estar al comienzo, este proyecto se centra en el desarrollo del núcleo del sistema y en en el estudio de sus posibles mejoras. 3 To my parents and my sister, who are always my support. To Eric, Adri, Mario, Juan and all my friends in El Pozo, who have made my time on University something so memorable. To Monica, who always makes my life better. This work is also yours. 4 Acknowledgements First of all, I must state clearly that if I am able to develop this work as well as other creations, it is thanks to the people that somehow or other have made me learn the necessary amount of knowledge. I must thank my project advisor, Antoni Gasull, for helping me to make some decisions such as focusing in one action or another during the project. I also must thank him for getting me the initial information and suggesting me about it. I also would like to thank CROHME organizers for supplying me with scripts and tools to classify the training data, and also for posting such a public database, which can help many people, me included. Finally, I would like to thank the Open-source software in general for making me avoid an unnecessary extra issue that would be having to get code and ideas from unofficial and too lax sources. 5 Revision history and approval record Revision Date Purpose 0 21/01/2016 Document creation 1 22/01/2016 Document revision DOCUMENT DISTRIBUTION LIST Name e-mail Ignasi Mas [email protected]c.edu Antoni Gasull [email protected] Written by: Reviewed and approved by: Date 21/01/2016 Date 22/01/2016 Name Ignasi Mas Name Antoni Gasull Position Project Author Position Project Supervisor 6 Index Introduction, 11 State of the art, 19 Project development, 22 Introduction, 22 Database, 23 Segmentation, 25 Preprocessing, 28 Feature extraction, 36 Feature ponderation, 41 Template generation, 46 Classification, 51 Expression building, 56 Results, 65 Budget, 69 Conclusions and future development, 70 References, 72 Appendices, 74 7 List of Figures 1Example of an application, Web equation from Vision Objects . 20 2InkML specifications in W3C .................. 21 3Results of the 2013 CROHME edition .............. 21 4What we want from the system ................. 22 5Those traces will be joined together ............... 25 6Although division bar is close to =, we don’t want to join them because the user has written the rest of symbols after the division bar and before the =..................... 26 7Bounding box and center of a symbol .............. 27 8Effect of the smoothing step on a regular symbol ........ 29 9Effect of point clustering on a regular symbol .......... 30 10 Note the hook detection and removal of this step ........ 30 11 Effect on a regular symbol of the polygonal approximation . . . 32 12 Note how the point is removed on the second image ...... 32 13 A regular symbol resampled by a preselected number of points . 33 14 Symbol with three traces reordered, the order is green, blue, yellow ............................... 34 15 Example of the distribution of a feature of two dimensions, in this case the Quadratic error for symbols with two traces, where red samples are symbol 7and blue samples are the rest of them. .............................. 41 16 Some templates .......................... 46 17 Different ways to draw a 7, with one or two traces ....... 47 18 Effect when two traces are joined, in this case on the symbol +. The resulting shape is wrong ................. 48 19 Distance computation between a symbol and a template (Elastic matching) ........................... 51 20 Example of a character template (6) and the primal shapes that can build it .......................... 52 21 Example of some symbols and the character they are tagged on the system ............................. 54 22 Example of region delimiters for a symbol. Blue line is the bounding box, red dashed line is the outside box and black lines are the superThreshold and the subThreshold. .......... 58 23 First case ............................. 60 24 Duality on possible dominances ................. 60 25 Exponent added .......................... 61 26 Symbol out of ranges. ....................... 62 8 Project:System testing and documentation WP ref: WP10 Major constituent: Analysis and report Sheet 10 of 10 Short description: Test the system and take conclusions Start date:09/01/2016 End date:25/01/2016 Start event: Testing the whole system End event: Report performance Internal task T1: Testing scripts implementation Internal task T2: Test running and analysis Internal task T3: Report Deliverables: Report Dates:25/01/2016 15 1.4.2 Milestones WP Task Short title Milestone Date WP1 T1 Read all the pre-selected papers 18/09/2015 WP1 T2 Choose one and make a summary/scheme Summary 18/09/2015 WP2 T1 Find database Database 20/09/2015 WP2 T2 Program a text to data conversion Program 25/09/2015 WP3 T1 Translate coordinates into images Program 26/10/2015 WP3 T2 Group connected traces(after morphology) Program 6/10/2015 WP3 T3 Error analysis and correction Program 09/10/2015 WP4 T1 Symbol attributes storing Program 10/10/2015 WP4 T2 Preprocessing over the symbols Program 22/10/2015 WP4 T3 Analysis of the improvement Program 23/10/2015 WP5 T1 Program the storing of each symbol Program 30/10/2015 WP6 T1 Train/test database selection Program 01/11/2015 WP6 T2 Template generation Program 08/11/2015 WP6 T3 Feature weights dessigning Dessign 10/11/2015 WP6 T4 Feature weights implementation Program 15/11/2015 WP7 T1 Classifier selection 17/11/2015 WP7 T2 Classifier implementation Program 25/11/2015 WP7 T3 Classifier testing Program 27/11/2015 WP8 T1 Level/semantic sense definition Program 05/12/2015 WP8 T2 Procedure implementation Program 20/12/2015 WP9 T1 Noisy templates detection Program 28/12/2015 WP9 T2 Noise solving Program 08/01/2016 WP10 T1 Testing scripts implementation Program 12/01/2016 WP10 T2 Test running and analysis Program 25/01/2016 WP10 T3 Report Document 25/01/2016 16 1.4.3 Gantt diagram TODAY WEEKS: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 100% complete WP1 100% complete T1 100% complete T2 100% complete WP2 100% complete T1 100% complete T2 100% complete WP3 100% complete T1 100% complete T2 100% complete T3 100% complete WP4 100% complete T1 100% complete T2 100% complete T3 100% complete WP5 100% complete T1 100% complete WP6 100% complete T1 100% complete T2 100% complete T3 100% complete T4 100% complete WP7 100% complete T1 100% complete T2 100% complete T3 100% complete WP8 100% complete T1 100% complete T2 100% complete WP9 100% complete T1 100% complete T2 100% complete WP10 100% complete T1 100% complete T2 100% complete T3 17 1.5 Deviations and incidences Although my original plan was to implement also the system feedback, I reorganized it and focused to achieve the best possible performance implementing the system block by block. I also had to spend more time generating the templates, because the database only had tags about the whole expression on each file, so I also had to extract tags for each isolated symbol. Finally, the CROHME competition organizers gave me some scripts to solve it. My original idea also included trying some proposed classifiers, but finally I implemented a variation of one of them. Building an MST also was in my initial plan for the structural analysis, but the results suggested to improve the classification priorly than the expression building. There has been one more incidence to mention. I would like to have worked with an InkML generator, but I did not found any available. So, I had to work with the database all the time. 18 2 State of the art Nowadays we have plenty of tools for almost everything. Online handwritten math recognition is not different. Many topics leads us to this field. First of all, more than half a century ago, handwritting recognition started to be studied for security purposes. Handwritten OCRs were quickly accepted and use in some institutions such as banks or post offices. We could talk about its evolution, but in short, they evolved until nowadays, that we have plenty of OCR software alternatives. During this study over decades, some researchers found that capturing Online data (which means capturing the data in real time, while is being written, against the traditional method of Offline data) gave extra information that could be useful in order to get better results. Since then, much of the research has been about Online recognition. On the other hand, mathematical expression recognition has also evolved. Decades ago, some researchers began to wonder if it could be possible to recognize hanwritten mathematical expression from a static image. While OCR were evolving, this field also added the Online research, but there were many issues on mathematical expression recognition. First of all, there are less constraints on the mathematical alphabet that on any other language, in terms of writing linearity, segmentation patterns... There has been an increase last years of the input devices which use Online data capturing (instead of the traditional keypads), including PDAs, smartphones and tablets. That’s why, although as we have mentioned, Online data capturing gives less benefits for math recognition, the increase of the amount of applications to satisfy demands more handwritten math Online recognition nowadays. Applications such as handwriting calculators or class notes digitalizers are exaples that need handwritten Online mathematical expression recognition on the program engine. So we can find plenty of software services which offer this recognition (either for Windows, Unix, Android or any OS in general) such as the Web equation app from VisionObjects, or the Android app MyScript Calculator. 19 Figure 1: Example of an application, Web equation from Vision Objects Normally,the general approach of the system is similar (segmentation, preprocessing, classification and structural analysis). Improving the algorithms for symbol segmentation, classification and structural analysis, as well as normalizing the users handwritting differences, are the main tasks nowadays. 2.1 Formats and institutions For a generic OCR, the data would be simply an image but in our case we want something different. Online handwriting data is stored as something called digital ink. This concept refers to data that specifies written strokes, where each stroke specifies its captured samples. They depend on the path followed by the user, its writing speed and the sample rate of the device. We need a format able to store a list of traces, with a list of coordinates (X and Y components for each coordinate) on each trace. The most common format for this purpose is InkML (Ink Markup Language),which is an XML-based format to describe digital ink. It published its specification on W3C (World Wide Web Consortium) in 2011. As it is described by their own developers, InkML was developed to make digital ink data something that can be processed for any application (such as our case). InkML stores traces composed by coordinates, metainformation (such as users ID, age, gender...) and also the tag of the expression, when necessary. Another format for storing digital ink is ISF (Ink Serialized Format), developed for Microsoft TabletPC. Math expressions also need a format. As InkML files can include other XML languages, they normally use MathML (Mathematical Markup Language) to tag mathematical expressions. 20 Figure 2: InkML specifications in W3C Since 2011 there exists a competition of Online handwritten mathematical expression recognition, called CROHME (Competition on Recognition of Online Handwritten Mathematical Expressions). They have an available InkML database on their web page, and many of the mentioned softwares have participated on it. Figure 3: Results of the 2013 CROHME edition 21 3 Project development 3.1 Introduction Before the development itself, we need to fix what is going to be described on this report. We want a system able to read a handwritten mathematical input and return its meaning. To implement this, we need an input file and a system, and that will give us a L A TEX expression. We will use many InkML files as inputs to test the system, and the idea is that it will work for any external user entering another InkML file, which would return them a L A TEX expression. As the system we obviously need the code that is going to be explained at the development, but we also need a database composed by InkML files for training, what means that their symbols have to be tagged. To implement this, I did some research, and the original idea was something like Figure 36, shown on the appendices. But when I organized my time I realized I had no time enough for everything, so I decided to let some parts, such as the feedback, the testing for different classifiers and the support for matrices, for future development. Then, the result at the end of this project will be something like Figure 37, also shown on the appendices. This also will give us the same output, but obviously the results will be worse, because the system is less robust. There is an example of what we want: (a) Input (b) Output Figure 4: What we want from the system 22 3.2 Database We are at the input of the system. We must enter digital ink data, which is what will be captured on the system where the user will be working on. As we have mentioned on the State of the Art, this data is presented in InkML format. We need a large database with several repetions of at least the most used symbols. For this I used the databases given in CROHME (Competition on Recognition of Online Handwritten Mathematical Expressions) last competitions, concretely 2259 InkML files, where each file has a different number of symbols. An InkML file to train has the following structure: <ink xmlns =" http :// www.w3 .org /2003/ InkML "> <traceFormat > <channel name ="X" type =" decimal "/ > <channel name ="Y" type =" decimal "/ > </traceFormat > < annotation type =" UI " >2011 _IVC_DEPART_F002_E013 </ annotation > < annotation type =" writer "> depart002 </ annotation > < annotation type =" truth "> $y_1 (x) = x^2$ </ annotation > < annotation type =" age " >26 </ annotation > < annotation type =" gender ">M </ annotation > <annotation type =" hand ">L </ annotation > < annotation type =" copyright "> LUNAM / IRCCyN </ annotation > < annotationXML type =" truth " encoding =" Content - MathML "> <math xmlns =’ http :// www . w3 . org /1998/ Math / MathML ’> <mrow > <msub > <mi xml :id =" y_1 ">y </ mi > <mn xml :id ="1 _1 ">1 </mn > </msub > <mrow > ... </mrow > </mrow > </math > </annotationXML > <trace id ="0" > 10.0112 25.56 , 10.0112 25.56 , 10.0112 25.556 , 10.0072 25.56 , 10.0072 25.568 ,.... </ trace > <trace id ="1" > 10.0914 25.889 , 10.0914 25.889 , 10.1035 25.8931 , 10.1115 25.889 , 10.1356 25.885 ,... </ trace > .... 23 <traceGroup xml :id ="11" > <annotation type =" truth "> Segmentation </ annotation > <traceGroup xml :id ="12" > < annotation type =" truth ">y </ annotation > <traceView traceDataRef ="0"/ > < annotationXML href =" y_1 "/ > </ traceGroup > <traceGroup xml :id ="13" > <annotation type =" truth ">1 </ annotation > <traceView traceDataRef ="1"/ > < annotationXML href ="1 _1 "/> </ traceGroup > .... </ traceGroup > </ink > Note that there are defined traces but also trace groups, tags and more metadata. InkML test files have different structure, because there is no need for them to have tags or trace groups. They are something like: <ink xmlns =" http :// www .w3 .org /2003/ InkML "> < annotation type =" UI " >2011 _IVC_DEPART_F053_E040 </ annotation > < annotation type =" copyright "> LUNAM / IRCCyN </ annotation > <trace id ="0" > 6.51629 10.9224 , 6.50425 10.9265 , 6.49623 10.9586 , 6.48018 11.0027 , 6.46012 11.0428 ,... </ trace > <trace id ="1" > 6.66475 11.0107 , 6.66475 11.0187 , 6.65673 11.0348 , 6.6487 11.0749 , 6.63265 11.1391 , ... ... </ trace > </ink > To parse those files we must find the trace indicators and scan those parts of the code. When training, we must store the coordinates lists specified on the files, grouped as marked and tagged as said on the InkML files. Then the system must compute them as symbols and store them on the database. For the testing step, we only need the coordinates lists of the traces on the file, and then begin the analysis. 24 A point is considered to own a hook if two conditions are satisfied: First one: θi< θ (5) where θiis the angle located at the point i(between pi−1piand pipi+1) and θis a threshold angle(I have used 17/36π). Second one: i−1 X k=1 ||pk+1 −pk|| < αL (6) or n−1 X k=i||pk+1 −pk|| < αL (7) where Lis the trace length and αis an adjustable parameter (I have used 0.12). For each point the system looks at the segment formed with the previous and the next ones. This way it can compute the angle on the point, and if it detects a closed angle it asks if it’s happening on a trace extreme. If it is, deletes the following points (if it’s on the end) or the previous ones (if it’s on the beginning). One possible conflict is that there are some equal consecutive points. If this happens it can be an issue to take the segment between both to compute the angle, because it doesn’t exist. For this, I have made my program look if it’s on this case, and if it is, look for the consecutive points, until it finds a different one. Then it computes the segment with this different point. 3.4.2.4 Polygonal approximation As it name tells, this step consist on representing a shape simpler, approximating it to a polygon. It is also computed trace by trace. It takes at first both extremes Aand B, and draws the segment AB. Then it searches the point on the trace with the maximum euclidean distance to the segment. We can call it C. Then we have the shape approximated with two segments AC and CB. We can repeat the same step with both segments. The system repeats the step until a level of tolerance is reached, which is the maximum position difference between the original and the approximated shapes. We can see an example on the following figure. I have used a tolerance relative with the symbol size, d/25 where dis the diagonal of the symbol bounding box. 31 (a) Before polygonal approximation (b) After polygonal approximation Figure 11: Effect on a regular symbol of the polygonal approximation 3.4.2.5 Point deleting In fact, this is the first technique to use for the reason I’m going to explain, but I’m describing it now for showing you its transcendence. I’m introducing the case which consists on a trace containing one single point. Note that we can’t apply any of the previous techniques, giving many issues when computing them on it. That’s why it must be the first step. Also think that we can consider an isolated point as noisy information. If not, we obviously couldn’t remove it. But note that there is one controversial case. It is when we have a list of more than one coordinate, but they are all the same. We must also consider it an isolated point, for the same reasons. I realized of this issue empirically, while computing. (a) Symbol with points (b) Points deleted Figure 12: Note how the point is removed on the second image 3.4.2.6 Arc Length resampling This is the first normalization step. It consists on redefining the symbol shape with a concrete number of points, keeping the proportional length of every trace. This will let us compare symbols point by point. In my system I normalized it with 50 points on the symbol. Note that the number of points is not the same than the number of segments. In fact, the number of segments is the number of points minus the number 32 of traces, because we have to discount one segment for each trace (the trace extremes are not united, so this segment is missing). (a) Before resampling (b) After resampling Figure 13: A regular symbol resampled by a preselected number of points What the system does is, for each trace, to compute the location of the wanted points. Then for each current segment on the trace it looks if there should be new points, and if it’s the case it stores them. 3.4.2.7 Stroke direction and order Once we have a list of coordinates with the same length for all symbols, we must assure that we are referring to equivalent points for each symbol. That means that we must normalize the coordinates list order. Note what we have: a set of traces containg a set of points each one. So, we must order equally the coordinates inside each trace and also equally the traces on the symbol. About the points , we must decide an standard order. I have used left to right,up to down. Now, we must compare the extremes of the trace depending on the type of symbol Symbols and traces are classified as horizontal,vertical,diagonal and closed. To understand those classes we must define the distance between extremes, R, as a composition of Rxand Ry(horizontal and vertical distances), and a δthreshold (I have used a value of δ= 0.5). •Horizontal if Rx> δ and Ry< δ •Vertical if Rx< δ and Ry> δ •Diagonal if Rx> δ and Ry> δ •Closed if Rx< δ and Ry< δ This classification is stored for whole symbols, but it’s also computed for traces in the same way. This is what will let us standarize the traces direction. 33 For horizontal traces, if the first point is more on the right than the last one, it inverts the coordinates list on the trace. For vertical and diagonal traces it does the same process if it finds the first point lower than the last one. Finally this is not computed for the closed ones. About the traces , we also must decide an standard order. In this case, we order it by angle of the last extreme of the trace with the horizontal direction, from low to high angles. (a) Before normalizing traces order and direction (b) Traces order and direction normalized Figure 14: Symbol with three traces reordered, the order is green, blue, yellow Note that if we reorder the coordinates list, we also have to update the trace indicators, because now the points of a trace will be located on another part of the list. 3.4.2.8 Stroke reduction This step consist on group strokes when there are more than a wanted number. This is rarely used, but in my system it limits the traces to 3. I also implemented the option to add strokes if there are less than your wanted number, it simply divides the last points on different traces. 3.4.2.9 Size normalization We have normalized the number of points and its order, so now we can compare equivalent points between different shapes. The only thing to improve is the sense of the values of this coordinates. To compare shapes independently of its scale, which depends on the device, user, and other facts, we must normalize its size. I normalized it between −1and 1for both horizontal and vertical axis. So, the method is as easy as moving the symbol to our wanted dominion. Be careful in this step, because if we are analyzing the file, we must keep the information about its original location and size. So, we must keep the original bounding box and center although we normalize the coordinates. 34 3.4.3 Steps In my system I have used those techniques in the following order: •Point deleting •Smoothing •Point clustering •Dehooking •Polygonal approximation •Point deleting again •Arc length resampling •Stroke direction and order •Stroke reduction •Size normalization 35 3.5 Feature extraction At this point we have the coordinates list for each symbol that we will use to classify them. From this raw data we must compute some parameters that we will directly compare between the untagged symbols and the templates on the database. Taking useful features will be a key step to obtain good results. Useful features are those which discriminate a lot between symbols. For example, the first coordinate value is not a good feature, because it doesn’t matter for any symbol where it begins while any different symbols can be written starting from the same point. Remember that even selecting an appropiate set of features, there will be some better than others. That’s why after the feature extraction we have to apply also a feature ponderation. I used the features explained in [8], which I will explain more deeply later. Basically, I used features of two kinds: Local features are those which are associated to every point of the coordinates list, giving information about them as well as their relation with its neighbours, the trace they belong to or simply the whole symbol. Obviously they are vectors of single elements (or tuples when they give values for X and Y components) with the same length than the coordinates list. Global features are those which are associated to the symbol or to its traces. They are single values or tuples when they give information about the whole symbol, or vectors of them when referring to each trace. 3.5.1 Local features 3.5.1.1 Coordinates Coordinates by themselves are the first feature to extract. We don’t need to compute anything to obtain them, because on this point we already have them, but we need to store them and use them later to compare like any other feature. (xi, yi)for piin symbol coordinates (8) This feature is very important because it defines the traces path, and it’s specially sensitive to normalization. Think about an Awhere the bar in the middle -is written left to right, and think also with another one where at contrary, this bar is written right to left. They may have exactly the same 36 shape but when comparing their coordinates, we could be comparing totally different points. 3.5.1.2 Turning Angle This feature means the direction of the segment written from every point until the following one. It computes the angle of the horizontal direction and this segment and stores this value. θi= arccos xi+1 −xi q(xi+1 −xi)2+ (yi+1 −yi)2for piin symbol coordinates (9) or θi= arcsin yi+1 −yi q(xi+1 −xi)2+ (yi+1 −yi)2for piin symbol coordinates (10) It gives an idea of the patterns of his writing path. For example, if a symbol begins with a line going up it will store this pattern. For the last point of each trace I always gave the πvalue. 3.5.1.3 Turning Angle Difference This feature is related to the Turning Angle. It’s simply its difference on the studied point and the previous one. This means that it’s giving the angle of the incident segments to the point. ∆θi=θi−θi−1for piin symbol coordinates (11) It refers to the symbol shape, independently from its orientation (it’s computed only with relations, not with absolute values). That’s the main difference with the previous feature. For the first and last points of each trace I gave the value of 0. 3.5.1.4 Length Position As every symbol has a line length, this feature consists on computing the line length until each point in relation to the whole length, normalized to 1. Li= i−1 P k=1 q(xk+1 −xk)2+ (yk+1 −yk)2 Lfor piin symbol coordinates (12) 37 where L is the total line length: L= N−1 X k=1 q(xk+1 −xk)2+ (yk+1 −yk)2(13) Length Position gives an idea of where are longest segments located on the symbol writing path. Obviously, the first value will be 0and the last one will be 1. The rest of them will be between those values. 3.5.2 Global features 3.5.2.1 Center of gravity The first global feature we must implement is computed for each trace in the symbol. It is found as the average of the point coordinates in a stroke. CoG(j) = ( n X i=m xi n−m, n X i=m yi n−m)for m...n∈stroke sj(14) The meaning of this is to locate the main position of every trace, so we will compare them to find the template with the most similar trace positions. 3.5.2.2 Length in Stroke As it name suggests, it simply consists on storing the length of each trace. So we will get if a symbol is composed by long/short lines. LiS(j) = n−1 X k=mq(xk+1 −xk)2+ (yk+1 −yk)2for m...n∈stroke sj(15) 3.5.2.3 Relative Stroke Length This feature is computed for each trace as the distance between both of its extremes in relation with the stroke length. d(j) LiS(j)(16) where d(j) = q(xn−xm)2+ (yn−ym)2for m...n∈stroke sj(17) It gives an idea of how closed is a stroke. If its extremes are far from each other in relation with the stroke length, it means that this trace is clearly 38 open, similar to a line. At the contrary, long strokes with close extremes are very closed. If the Relative Stroke Length gives a value of 1, it means that the stroke is a segment. If this value is 0, we are talking about a totally closed shape. So, with this feature and the previous one we’ll know the position and the similarity to a segment against a closed shape for the traces in a symbol. 3.5.2.4 Accumulated Angle This feature is related with the segment directions again. It refers to the sum of angles in a stroke. θa(j) = 1 2π n X i=m θifor m...n∈stroke sj(18) This also gives an idea about how closed is the trace, in an angular scale. 3.5.2.5 Quadratic error It means the deviation (in sense of quadratic error) from the segment between both of the extremes of a trace to its points. It’s computed as the average of this distance for the points belonging to each trace. E(j) = 1 n−m n X i=m d2 ifor m...n∈stroke sj(19) It’s also useful to know how closed is a trace, in a sense of covered area. Segments will have low quadratic errors while closed shapes will have high ones. 3.5.2.6 Style We have already talked about this classification in the preprocessing part, and I included it as a feature. To be compared it needs a numerical value. That’s why I gave it this values: Diagonal symbols have the value of [1,1] Horizontal symbols have the value of [1,2] Vertical symbols have the value of [2,1] Closed symbols have the value of [2,2] 39 3.5.3 Feature information So, after computing all this features we will obtain the following data about the N sampled points distributed in T traces: •The point distribution, described by an Nx2vector (Coordinates) •The point orientation, described by a vector of N(Turning Angle) •The shape independently from the symbol orientation, described by a vector of N(Turning Angle Difference) •The line length evolution, described by a vector of N(Length Position) •The ubication of the traces, described by a vector of Tx2(Center of Gravity) •The total perimeter of the line in a symbol, described by a vector of T (Length in Stroke) •The shape of traces, in a sense of angles(described by a vector of T, Accumulated Angle), in a sense of written perimeter of the shape(described by a vector of T, Relative Stroke Length) and in a sense of covered area (described by a vector of T, Quadratic Error) 40 (a) One trace (b) Two traces Figure 17: Different ways to draw a 7, with one or two traces 3.7.1.1 Normalize the number of traces As the number of traces is the only thing that we have not normalized, we could solve it. As it has been mentioned before (in 3.4.2.8), the size reduction step has been build to join traces in order to reduce the number of them as well as to divide the last trace in order to have more of them. So, we can normalize the number of traces as: Its minimum , which means that if it founds (in the database) a symbol with more traces than the minimum, some of them are joined in order to have less (until this minimum). Its maximum , which means that for symbols with less traces than the maximum from the character on the database, it adds extra divisions. But this solution would have remarkable issues. The main one is that the shape will take or forget segments randomly, which would not have any similarity to the original ones. Also, local features like Turning Angle would take wrong values, and global ones like Center of Gravity would be seriously distorted. 3.7.1.2 Take those cases as different characters This method consists on give a different tag for those possible shapes. In fact, we can consider them as different symbols, because when writting it you are choosing one way to describe its shape, and they can be totally different. When building the structure, those tags will mean the same. So, for example, a 7won’t be tagged as 7, but as 71 or 72 depending on its number of traces, and after the classification they will be seen as 7again. This is the solution I used, for the reasons I have already mentioned. 47 Figure 18: Effect when two traces are joined, in this case on the symbol +. The resulting shape is wrong 3.7.2 Trace markers normalization We also have to consider that the length relation for traces on each symbol can be different, and we want to compare equivalent points. That would be an issue if we didn’t solve it, because we could be comparing points of different traces. So, we have to normalize them. That means that traces must be sampled by the same number of points for all symbols on the same character. So, we have to decide again where the traces end for each character. The simplest solution is to compute the mean between its symbols on the database. For example, imagine a character represented by a symbol with a trace between points 0 and 20 and another one between 21 and 49, and a symbol with a trace between points 0 and 30 and another one between 31 and 49. The resulting trace lengths for the character template would be two traces, one between 0 and 25 and the other one between 26 and 49, which is the mean of the symbols. When we have decided those limits we can apply an alternative arc length resampling, to adjust the traces on the samples to the decided number of points. Once we have done all this, we can compute the templates. 3.7.3 Independence from shape There are some special characters on the database. Characters which depend more on their size that on their own shape. That happens when one of the dimensions of the symbol size is very small. Think about the size normalization. When we read a very narrow symbol, we take notice of this fact instead of its local shape, considering it as a vertical line. But our system normalizes it and compares its shape. 48 Those characters are giving random shapes, or when normalizing its traces order, random orders, so the templates are averaging random traces. We must specify to the system in which cases that happens, and the way it can solve this issue. We must delete those characters from the database, and solve this following cases. 3.7.3.1 Small horizontal and vertical size If the system finds a symbol with a small bounding box for both dimensions, it must automatically consider it a dot. Later, on the structural analysis, depending on where it finds the point it can transform a symbol to another. 3.7.3.2 Small vertical size That’s the case of division bars and minus sign −. The decision of which of them is the tag is irrelevant, because it will change depending on its structural position. 3.7.3.3 Small horizontal size When the system finds a bounding box with a small width, it must look at its traces. If it only has one trace, it is considered a 1(that’s the meaning of a vertical line). If it has two traces, it depends on their length. If the highest one is long (it’s considered long if the distance between extremes is more than 1 8of the total bounding box size) it is considered a !. If the long one is the lowest it is considered an i. If any of them is long, it’s tagged as :. Else, it’s a strange case. In my system it’s tagged as :. It’s important to remove them from the database not only because their shape is random and it rarely will match them correctly, but also because a lot of false positives can be taken if the given random shape is similar to a concrete symbol. This is a step of the classification, but it has been explained here to understand why they are removed. 3.7.4 Noisy samples Noisy samples give noisy templates. That’s why we must remove those cases, beacause if not we will be storing wrong templates that will disable the 49 character itself and can give a lot of false positives. We can detect noisy samples by its number of traces. In my system, if it detects that from a single character, less than the 6% are written with a concrete number of traces, its considered a rare case, and it’s removed. The reason is that if a symbol of 100 samples only has 5of them written in one trace probably it hasn’t been done following regular patterns. We still have one more problem. There are characters that by definition are written in a concrete number of traces, but has several cases on the database where it’s written in more than this number, cut in some point. That point will be random on the shape, so we won’t compare equivalent points. I solved it with a manual selection on the database, but that’s not the best way to do it. The rest of noisy samples are also removed manually if they clearly distort the result. 50 3.8 Classification We have the following: several symbols on a database, tagged by their meaning, which also has a template, and one symbol to classify. We have the features for each of them, and their ponderation. There are many approaches to this task. 3.8.1 Proposed methods There are proposed in reference [1] some classification methods with different theoretical approaches. 3.8.1.1 Similarity methods The templates are very relevant here. This is the method that compares them to the studied symbol to simply decide its tag. There is one method called elastic matching which is something similar to what I used. It takes the templates one by one, sums the distances for each point to the studied symbol and stores the result as a cost. Then, he decides the character whose template has less cost. It’s normally computed with DTW (Dynamic Time Warping), which solves the fact that similar point paths can be sampled different, but in our case this is already covered by the arc length resampling. Figure 19: Distance computation between a symbol and a template (Elastic matching) 3.8.1.2 Statistical methods The computed features can be inputs to those classification methods. Neural Networks, HMM (Hidden Markov Models) and SVM (Support Vector Machines) are proposed. 51 Neural Networks are proposed to be computed on the structure to compute probabilities on its context, as a kind of feedback to the system. I also tried them directly over the feature vectors, but the result was bad. It’s possible that they would be better if I had applied a PCA(Principal Component Analysis), which basically is a method that removes correlated information (values on our feature vectors are probably strongly correlated). HMM are also used on segmentation, so the system would take the information and build the symbols while it’s joining the different traces. SVM would be used only for classification. 3.8.1.3 Structural methods They take each symbol as a combination of shapes. Those shapes are something like circle or -, and they are predefined on the system. For example, a 6is formed by a descending curve and a loop. (a) Template (b) Primal shapes Figure 20: Example of a character template (6) and the primal shapes that can build it 3.8.1.4 Clustering methods They are proposed to be used as an extra step, to get better results (our classification is supervised, so it wouldn’t have sense to use them to classify symbols by tags). There is an issue to classify a symbol in any conditions, which is the variability of the user handwriting. Clustering methods offer to model those variations and make a better matching. 3.8.2 Used method In my system, I used an algorithm similar to elastic matching, but using not only the coordinates but also the rest of computed features. 52 Note that before anything, we have to adapt the trace limits of the symbol to the points marked in the template (one adaptation for each template), to compare equivalent points. My idea was to compute a cost for each feature. As we have said, for coordinates this cost corresponds to the sum of distances for each point between the template and the symbol. For the other features, this cost is also defined as the distance point by point between those two elements. The assigned tag must have the same number of traces, so even in global features it can compare equivalent values (the system assumes that symbols with different number of traces can’t have the same meaning and way to be written). Once we have those costs, how can we use them to make a decision? My first approach was to sum them and look for the lowest cost. But this sum couldn’t be done directly. First of all we should apply the weight of each feature. Moreover, note that the scale of each feature is very different. For this reason, it is not fair to simply sum all the features, because there would be features more penalized than others. For example, angle related features would be more critical than position related (πagainst 1), and local features would also be more penalized than global features. One possible solution would be scale them from its maximum possible value: C(s, t) = X ∀f w(f)Cf(s, t) max Cf (32) where C(s, t)means the cost of a symbol sfor a template t, and C(s, t) means the cost of the feature fof a symbol sfor a template t. However, this can be wrong because there are maximums reached easier than other ones (for example, it is very difficult to reach the maximum of coordinates). Then we can normalize again, now by the maximum value of the feature costs found in the database. C(s, t) = X ∀f w(f)Cf(s, t) max(Cf∈dB)(33) But this comparation would still be not fair, because even normalizing by this found maximum, each feature can have its probability to reach it. So, we must compute something to make costs penalize a possible decision. What I did is to maximize the probability, understanding the probability as the sum of the inverse of the costs for each feature divided by the total cost of it (total cost as the sum of this cost for all the templates). Prob(s, t) = X ∀f w(f)1 Cf(s,t) P ∀s Cf(s,t) (34) 53 where Prob(s, t)means the probability of a symbol sto be matched with the template t. Then, we decide the character of the template with more probability. Finally we look for special characters as we mentioned before, in section 3.7.3. 3.8.3 Results On the cases I have tested, around a 50% of the symbols are perfectly recognized at this step. This result has improved, because first it was around 33%. Feature ponderation, cost rescaling redefinition and noisy database elements removal have been the main improvements to achieve this. (a) Symbol (b) Tag (c) Symbol (d) Tag (e) Symbol (f) Wrong tag Figure 21: Example of some symbols and the character they are tagged on the system This result could be improved adding a feedback to the system from the structural analysis, but it has been not implemented yet due to the lack of time of the project. The main issues are: •Small but decisive variations between two concrete characters, for example, between (and [. For us, once we decide that one symbol is one of them, we look at a concrete angle, which is a single component or a 54 few components of a single feature. Instead of that, the system compares it with all its features in the same way that the rest of symbols, and if the symbol shape is more similar to the wrong template, the decision will fail. •The way a symbol can be written, not with big differences which can be found on symbols already removed from the database, but variations like the length of a concrete trace which is enough to cause a bad normalization of the symbol. That means that we could be comparing not equivalent points. 55 3.9 Expression building From this point forward, the system can forget almost everything abut the symbols, it only needs to know their found tag and their real ubication (bounding box and center). Moreover, we don’t need all the information in our tag, but only its character, so we can remove its taces number indicator (remeber that for example, 51 means a 5written in one trace). So, we have this (a list of tags and the space they fill). What we want is to build a hierarchical structure to describe the expression. For this, is necessary to describe some theoretical concepts to be used on the expression building. 3.9.1 Concepts 3.9.1.1 Kinds of symbol Not all symbols are governed by the same rules. When we humans read, automatically associate some distribution for each symbol, to decide where the following symbols must be to be associated to it or not. And this decision depends on the symbol we are studying. For example, think about a cand a b. Note that in c2the exponent must be above the character, and if it wasn’t we probably would assume it as not associated to c, while in b2the margin is wider, note that the exponent is often located under the bsuperior limit. This is because in bthe bounding box fixes the superior limit over where the symbol really concentrates. There are more cases like this, and we can also find the opposite case (for example g). That’s why we must define differences depending on the symbol distribution. Basically we can find three cases: central symbols (like an o), ascendent symbols (like a d) and descendent symbols (like an y). There’s one other difference between characters, now more on a semantical sense. Think about a kind of association, like an exponent. Would it mean something associated to a +(+2)? Obviously it wouldn’t, so not all the characters must be treated equally. Depending on its possible distribution, we must also classify them. So, at the end we have a classification like the following, which is what I followed: 56 more a 2itself but a 2with an exponent x. And in √2x+C, assume it as a square root containing symbols of 2with an exponent x, a +and a C. Once the system has assumed that, it can assume the expression as a serie of the symbols which are on the dominant baseline, where each symbol can contain more information. This expression is easily converted to a L A TEX expression. The result would be something like the following. Figure 27: Final result 3.9.4 Results To test this single step, I faked the classification to be well done so we can focus on the expression building. Those results were not bad at all. No symbols were repeated or disappeared and normally it returned the general structure of the equation. Some symbols are assigned wrong as superscripts/subscripts/neighbours, and sometimes this means that a fraction structure is broken (for example, if a numerator is taken as a denominator superscript, it can be moved to the lower region of the structure). There are examples (on Figure 28) of inputs and results. Those results are worse when we don’t fake the tags, because the thresholds are distorted and the expression is built wrongly. We will see this results on another section. 3.9.5 Improvements on expression bulding: the MST During my research, I found that it was proposed an implementation of a MST as a probabilistic model. An MST (Minimum spanning tree) is an algorithm that builds a model of relationships that improves the probability of the resulting expression. It defines some nodes, that in this case are the symbols, and the probability of 63 (a) Input example (b) Its expression output (c) Input example (d) Its expression output Figure 28: Some inputs and their output when their tags are wright every possible relation. Then, from the most probable relationships builds the complete model. It is proposed to use the distance between the symbols to compute this probability. Concretely, the distance between the attractor points, which are points defined by the type of symbol and the candidate relationship. It would also compute a dominant baseline and then the sons of its symbols. That could be a future topic for research, because a probabilistic model could be more robust. Figure 29: Example of a MST 64 4 Results Many results for each step have been studied on previous sections, but now we must focus on the result for the whole system. Before studying those results, I want to make clear that this project doesn’t present any final version of a program, but a prototype, a first approach to this complex problem. So, the goal is not the accuracy of the results, but the detection of the main issues and the future research topics to improve them. That said, I performed a test weeks before the project end, but I detected some possible sources for the errors and I improved the system. Basically, I implemented some of the steps previously mentioned, such as disabling the shape matching for small symbols (dots, minus signs −...) or removing noisy elements from the database, in order to improve templates sense. I also had to redessign the feature ponderation to the mentioned algorithm. At the end of the project I performed a test over many cases. I can’t report them all on this document, but I will show the most representative ones. I found many issues of the system while testing it. We can begin with the following case. (a) Input (b) Output Figure 30: Wrong classification results on wrong expression The most remarkable error detected during the test is the fact that a wrong classification leads to building a wrong expression. In this case on the previous figure, we can see how the decision of tagging the second yas a 9 moves the thresholds to false values, so their related symbols are assumed with wrong relations. In this case, for example the symbols in the expression +z1−z2are assumed as exponents instead of as neighbours, as a result of this bad classification. We can see this same effect on the next figure. (a) Input (b) Output Figure 31: One bad decision is disturbing the rest of the expression 65 In this case γtakes its following symbol as a subscript. Note that bis also taking wrong its relation with its following symbol, although it has been well tagged. That is simply because as you can see, bis slightly risen from the rest of the expression, so it is considering that its following symbol is low enough for being its subindex. The problem is that, as the rest of symbols are at the same level than +(bfollowing symbol), they are assumed as right neighbours of +, so subindices of b. This is happening because once the system assumes that +is the subindex of b, its relation with the rest of the symbols is based on this previous relation (between band x). That could be improved setting the direction of the dominant baseline, or instead of directly taking cas the right neighbour of b, compute the probability of it agains the probability of being the right neighbour of b. Now we can focus in another main issue. It is shown on the following figure. (a) Input (b) Output Figure 32: Intra-class variation is one of the main issues at this point This issue refers to the fact that a single character can be written in many ways. Sometimes consciously, sometimes not, this is called Intra-Class variation. The first time I detected the errors it was causing was when I performed my first test. Then was when I made a selection of cases for some characters in the database. On this selection I removed those symbols which were not made with the regular patterns, so the template for those cases had sense again. Even after this selection, the system gave wrong tags, because if the input characters were written in one of those not regular patterns, they were not found on the database. That’s the case on the figure, where as we can see those xare wrongly tagged because their patterns are not those which define xon its template. This issue could be solved defining one template for each way of writting each character when necessary, as different symbols which mean the same. Now we can focus on the last main issue that I found. It is the case of the following figure. 66 (a) Input (b) Grouped traces (c) Output Figure 33: Wrong segmentation can ruin some cases This issue refers to the effect of bad segmentation. Note that on the figure, letters in tan are segmented, so the system is deciding a tag for each isolated symbol. We could implement that the serie of the characters t,aand n formed the symbol tan when they are found in a concrete position, but as the system is tagging them as other characters, even implementing this we couldn’t solve the issue. If we were storing a list of candidate characters instead of making an absolute decision, and also their probability of being joined against being separated, we could get the probability of tan being written against those found isolated symbols. This could be implemented using feedback on the system. We can see another example of wrong segmentation leading to wrong expression building on the following figure. (a) Input (b) Grouped traces (c) Output Figure 34: Another case of wrong segmentation effect over classification and expression building 67 Finally, we can see an example where a wrong segmentation is making the system tag unwanted symbols that, on the other hand, are wrongly tagged and that gives them a wrong relation. We also can see as subtle variations between symbols such as 2and zcan lead to bad decisions if features which are irrelevant between them but important in general are more similar to the wrong character. That example could be the summary of this project results. (a) Input (b) Output Figure 35: Example os the system results 68 5 Budget This project has been based on research over software, using Python, an Open source programming language with open libraries. The used database is the one offered by CROHME Competition, so it is also open. I have not used any external hardware aside from my personal computers. The only think to include on this budget is my work time. Salaries: Position Total number of employees Hours/month Amount of months Total amount of hours Salary (e/hour) Total Junior engineer 1 120 4 480 14 6720 Total 1 120 4 480 14 6720 So we can conclude: Type of cost Cost Salaries 6720 e Software 0 e Hardware 0 e Total 6720 e The total cost of this project has been 6720 e. 69 6 Conclusions and future development The main conclusion is something that has been mentioned previously: This project does not present a final version, and the accuracy of its results is not its goal, in fact we can see that they are not very accurate at this point. Instead, it is presented as a part of a bigger project, which is the Online handwritten mathematical expression recognition. And due to the amount of information it gives we can conclude that it has achieved its main goal. In fact, as its general performance is good in terms of blocks, it can be used as the core of this bigger project. That said, there are many topics we can develop henceforth. We have mentioned those we have found on our study, but surely there are many more ideas we have not found yet. There are basically the following kinds of improvements: completing the whole proposed system (adding feedbacks), improving the blocks with more probabilistical models (specially the classification block), defining those ways to write some symbols that have not been included, implementing the support for elements which have not support yet, such as vectors or matrices, and including those blocks not included on the OCR engine, which have not been implemented yet. It could be also interesting to find some code with the same function and compare it with ours. 6.1 Feedback This should be the following step. The first approach could be assuming the system decision not as a single tag, but as a list of possible characters with its probability. Then, with the structural information, classification could be improved. For example, if a symbol is located on a +sign superscript region, it would consider if the +maybe is another symbol (for example a t) instead of assuming this symbol as +right neighbour, depending on its probabilities. This step could be very hard because we should include many thresholds that probably we would obtain by testing the system. This idea could also be used on the segmentation, adapting the structural element of the morphology used to the probabilities of the resulting classification. We can think about the case mentioned before, where a tan was tagged as +nn, because once their symbols were segmented, the system did not consider that they could be part of a joined symbol. On my research, I also found some ideas which could be interesting to try. Some authors have used HMM to join traces while the system tries to classify 70 the symbols. Neural Networks are also mentioned in order to tag symbols using structural information. 6.2 Alternative models I focused in one type of classifier, but there are many kinds that could be tested. Some of them (the statistical models) are mentioned before and include feedback, but structural methods (symbols as composition) and handwriting normalization can also be implemented. We also can implement the MST building mentioned on the structural step, to make it more probabilistical. 6.3 Single character variation This is one important fact to improve. After the result study, it seems clear that we need to define which writing patterns could a character have, including those which are not the most common. That could also include an expansion of the database 6.4 Supporting more elements This is probably the less prior step, because before including many options we need a system working. Even that, this could be an interesting topic of research and implementation, and there are many papers related to it. 6.5 Outside the OCR engine As we have mentioned before, this project is focused on the OCR engine. When this engine is ready we will need to include it on the desired application. Depending on the application, other parts can be developed, such as solving the expressions for calculators, formatting and storing for class notes... In any case we will also need a front-end dessign. This is not directly related to this project, but we can use it to get another application. 71 References [1] Ernesto Tapia,Raúl Rojas, A survey on Recognition of On-Line Handwritten Mathematical notation, Freie Universität Berlin, 2007 [2] Kam-Fai Chan, Dit-Yan Yeung, Recognizing on-line handwritten alphanumeric characters through flexible structural matching, Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, Peoples’s Republic of China, 1998 [3] Chuanjun Li (Brown University),Robert Zeleznik (Brown University),Timothy Miller (Brown University),Joseph J. LaViola Jr. (University of Central Florida) Online Recognition of Handwritten Mathematical Expressions with Support for Matrices, 2008 [4] Kenichi Toyozumi (Nagoya Univ.), Naoya Yamada (Nagoya Univ.), Takayuki Kitasaka (Nagoya Univ.), Kensaku Mori (Nagoya Univ.), Yasuhito Suenaga (Nagoya Univ.), Kenji Mase (Nagoya Univ.), Tomoichi Takahashi (Meijo Univ.), A study of symbol segmentation method for handwritten mathematical formula recognition using mathematical structure information, 2004 [5] Francisco Álvaro, Joan-Andreu Sànchez, José-Miguel Benedí, Recognition of on-line handwritten mathematical expressions using 2D stochastic context-free grammars and hidden Markov models, Departamento de Sistemas Informáticos y Computación, Universitat Politècnica de València, Valencia, Spain, 2012 [6] Xiaofang Xie, On the Recognition of Handwritten Mathematical Symbols, The University of Western Ontario,London, Ontario, 2007 [7] Utpal Garain and B. B. Chaudhuri, Fellow, IEEE, Recognition of Online Handwritten Mathematical Expressions, IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICSâĂŤPART B: CYBERNETICS, VOL. 34, NO. 6, 2004 [8] Ernesto Tapia, Prof. Raúl Rojas,Prof. Johan van Horebeek Understanding Mathematics: A system for the recognition of on-line handwritten mathematical expressions, Freie Universität Berlin, Berlin, 2004 [9] CROHME: Competition on Recognition of Online Handwritten Mathematical Expressions,www.isical.ac.in/~crohme/ 72