Abstract
Mathematics is the cradle of all creations, without which the world cannot move an inch. Mathematical functions are ‘extensively’ used in physics, ‘structurally’ used in graphics, ‘practically’ used in civil engineering, ‘potentially’ used in mechanical engineering and in many other fields as well. One fairly common difficulty faced by the engineers and scientists is to find the right function that solves their problem. This involves a lot of time consuming tasks. The idea proposed here is an android application that captures the mathematical expression using a built-in camera which produces a java code that can be utilized for solving the inputs of their needs. Along with the code, it also displays a basic plot of the function, which will be more helpful for selecting the apt solution for any problem. There are many applications in the market which can compute the result of a mathematical equation. But, this application will give an executable java code which can be used for further problem solving. So, the application is unique in its way and this is a new dimension of using image processing for code generation. This application supports polynomial, logarithmic, trigonometric and exponential functions up to four variables.
Introduction
Today’s machines have the capability of looking and understanding things, just as humans does. This is achieved through image processing and machine learning. Optical Character Recognition is one such technology which gives the power of reading to machines and applications. This application is aimed at using this capability for solving a new age problem. Mathematical equations have become the bread and butter for engineers and scientists. Solving equations is a tedious job. Now, computer programs play a very important role in making this equation solving easy. There are multiple algorithms and different techniques for solving functions in a faster and efficient manner. Many popular programming languages give extensive support for mathematical equation solving with pre-defined functions and libraries. Here lies the actual problem that is taken in hand. On one side engineers want to solve more and more equations and select best equation for the application they want to build. On the other side, there is extensive support for solving equation in programming languages. But, not all engineers are comfortable in writing an efficient code. There are applications available in the market, which can solve a given equation and return the result. Just think about the scenario where they want to solve the same equation for various different inputs (which happens in most of the cases). In that case, they want to repeat the same process manually for different inputs. Especially when they want to select an equation for their application, they will move step ahead. They want to solve the equation / equations for a basic set of inputs, plot it and then compare them for choosing the best for their requirement. This application is an attempt to bridge this gap. The application is capable of generating a java code which can be executed directly. All the inputs can be given in and executed at once. Along with it will also give a plot of the function for aiding them in selecting appropriate equations for peculiar applications.
To be precise, our application captures a picture of printed equations. The image is preprocessed to arrive at the point of interest. Noise from the picture is removed, and the equation is tilted to get the right orientation. Any other background information is removed. Then based on clustering the characters are isolated and recognized by applying machine learning algorithm on the UCI machine learning dataset. The nearest neighbor algorithm is used for classification of the characters. Once the characters are ready, they are grouped and processed further. For grouping the equation Finite State Machines were designed and implemented. After grouping the equations are processed within the groups. Separate FSMs are built for processing and it has been designed for all basic arithmetic, logarithmic and trigonometric operations.
Finally after all the groupings, the mathematical functions are arranged according to the precedence. A Java code is generated from the result of the above operation then with that result the graphs are plotted according to number of variables present in the input (up to 4 variables) and can be exported to use for the respective application.
State of the art
Amey Chavan and Asad Naik in 2013 came up with an application that can scan mathematical equations and solve it. It uses OCR to convert the image to text content. The recognition involves some steps like blurring, cropping and threshold based pixel removal (for background removal). After the background is removed, parser is initiated. The parser converts the equation into A1x1 + B1y1 = C1. This matrix is solved by Cramer’s rule and the solution is given back. This is a comparatively simpler application that computes multiple equations, but this doesn’t solve individual equations. This application directly uses the software that is applicable and is comparatively simpler. This is one of the earliest applications in this field [1].
Haotian Xue et al. in 2014 proposed a scanning based calculator which generates results instantaneously when arithmetic expression is scanned by the Quick Scanner. A benefit of using QSC is to improve calculation accuracy by avoiding mistakes due to human action and increase efficiency in study and business. They proposed to use Optical Character Recognition (OCR) for identifying characters and symbols. Thus, an image can be converted into a string. This text can be given as input and processed by the calculator. Standard OCR was proposed for printed equations, whereas machine learning based trained OCRs were proposed for hand written equations. They have proposed two modes of implementation for the same. One is a highlighter shaped scanner which can read the inputs and send it to an actual calculator. Another mode is a mobile application where a picture of the mathematical equation can be taken and processed within the application itself for result. This was a turning point in this domain post which there were new apps being created for equation solving [2].
Tripti Goyal and Vipul Goyal in 2016 came up with an idea of implementing the OCR based equation solver in MATLAB which captures an image of an equation using mobile phone camera. The image taken is downsized to 640*480 pixels from its original size to speed up the transmission. The resulted image is subtracted with the original image to form a uniformly lighted image. The localization of image is done to remove extremely small regions and get rid of noise in the image. The region is cropped to form a bounding box and rotated. Finally clustering technique is applied to split individual characters. A cluster of connected pixels is considered as character. Now each cluster is classified into the digits (0–9), variables (a, b) and mathematical operators (+, –, x, /) applying machine learning algorithms [3].
Photomath Inc, an android app development company created an android mobile application called Photomath. The application is capable of scanning mathematical equations and solving them. It can scan both hand written and printed equations. After scanning, the application gives a detailed step by step procedure for solving the equation. Additionally, there is an interactive calculator where the scanned equation can be edited. This application can solve any model of the equation like arithmetic, logarithmic, exponential etc. Even in here the problem of repeating the process for multiple inputs occurs. Thus our application has all the updated features and adds a feather to the hat by generating codes along with it [4].
Problem statement
Android applications for solving mathematical equations are very powerful. But for more inputs the process of scanning the equation and solving it becomes a repetitive and tedious process. When an equation has to be selected for an application, more than one equation must be considered and they have to be compared with one another. In such a situation along with solving the equation for multiple inputs, their plots will be extremely useful. Solving these problems will definitely enhance the power of such equation solving applications and unleash new possibilities by saving a lot more resources.
Proposed solution
The solution proposed in here is another android application. But, instead of solving the given equation, here gets generated an executable code for the mathematical function in java. This code can be run for multiple inputs at one shot. A basic data set is fixed; the same is given as input for the above generated function and executed. Based on the outputs, a plot is generated for visualizing the function. Thus, the repetitive process is reduced to one single process, the users have the code to explore more opportunities and finally a basic visual representation of the equation is displayed. All these features will definitely fasten up the process of equation solving and equation selection for specific applications. Above all, this is a new attempt in image processing to generate executable codes from images. The architecture for the proposed solution is shared below as Fig. 1 and elaborated further.
Functional architecture.
Mobile applications these days have the capability of capturing the real time environment through its camera. This capability allows applications to work in the space of augmented reality. The proposed application requires permission for the camera to capture the image. This image is the scanned input which will be processed in the following steps.
Noise removal
Background noise is one of the deadliest backlogs for this application. When the scanned image has some additional irrelevant content, it is to be correctly identified as noise and removed out. Standard filters like Wiener filter, Gabor filter and Fourier transform [5] are used to remove background noise from the image and only the text is retained. In here, there is no prescribed algorithm for our application as both the subject and noise are in the form of text (only if any additional text is present in the image). Here gets framed a simple algorithm for identifying the text of interest and retain the same, whereas removing additional text (noise in here). This algorithm is based on simple clustering technique. Fuzzy C-means has been implemented in here [6]. The image scanned is for an equation and it will thereby be in the center of the image. Post clustering, the centroids of the clusters are analyzed as follows- The centroids of all the clusters and the coordinate center of the image are taken. The distance between each cluster and the center is computed. Based on the above fact that the equation will be in the center of the image a threshold is fixed. The cluster that is closest to the center is the required part of the image and all the other clusters can be deleted.
Now, the image has the required equation only that can be processed using OCR in the next step. A constrain that has been implied in this application is the image must be taken with equation at the center, the image should not tilted or oriented in any angle and background must be preferably in white for better efficiency (as exclusive color filters are not deployed).
Optical character recognition
OCR is used for conversion of images into text strings. Standard OCR algorithm has been implemented and it can recognize only printed text [7]. This application can be extended to hand written text using training based OCR algorithms. The whole image after noise reduction is scanned as a block. This block is divided into record based on lines. Every record is divided into words based on spaces between them. Each word is now a small image comprising one word. This is done based on space between the words. Again, OCR in the back end has a clustering algorithm. Block is a cluster of the entire image. Record is cluster of each line split based on space between the lines. Words are clusters split based on space between the words. Now, in each word individual clusters are formed for each character based on connected pixels. These clusters are then classified as characters based on the dataset. Now the characters are appended into a string. Every word is now converted into a string. The total input is returned as a SparseArray, which is an array of words. This array is appended into a single string. The special character ‘∖n’ is added at the last. This string is send to the next step for processing and from there processing continues. Thus, input is scanned successfully and passed to the next phase. Let’s assume an example at this phase to make the understanding of the following steps easily.
Grouping the characters
The string from the above step is taken and group into parts. The grouping is based on continuous characters. The main aim of this step is to group the input string into digits, letters and operators. Continuous numbers are grouped into a substring. Similarly all continuous alphabets are grouped into a substring. Unlike them, each operator is stored as a separate substring. Even the parenthesis is classified as operators. This is achieved with the help of the below designed FSM in Fig. 2. There is a notable pit fall in this solution. The application is designed to support basic mathematical functions like log, sin, cos, tan and power. All these function will take the argument in a parenthesis. But ‘pow’ is just used directly in between any two characters / numbers. Isolation of pow in the middle of a stream of characters is handled separately in the FSM as well. The output of this stage is a list of substrings which has continuous alphabets, continuous digits, operators and functions separately. A notable constrain of the application is all mathematical functions other than ‘pow’ will work only with a parenthesis for arguments. Eg. Log(n) will be treated as a log function over variable ‘n’ whereas logn will be treated as a variable. The value ‘ɛ’ in the FSM denotes null.
FSM designed for grouping the input into substrings.
For a given equation say, y = 2x+3. The RHS is only our concern. It will be grouped in a list as { ‘2’, ‘x’, ‘+’, ‘3’ }. Before the list is sent for further processing one last check is done. It is operator validation. This is done by a mere traversal through the list. If there are two or more consecutive elements of the list which has operators then the equation is stated as invalid and the application stops the whole process. The process is made because as in the result of grouping, every operator will be an individual element of the list. If the operators are found to be valid, the list is sent for further processing.
In this step the substrings in the list from the previous step will be grouped based on parenthesis. All the elements that are within a set of open and close parenthesis in the input function will be grouped into one substring, while the rest will remain unchanged. If the input equation had no parenthesis, there will be no change in the list. On the other hand, for multi-level parenthesis, a substring may in turn have more parentheses in it. The grouping is done using the below shared algorithm. While grouping the strings some intermediate checks are also done to validate if the equation is valid.
Figure 3 shows the core algorithm of the application. While grouping the parenthesis it also checks for power in between and handles it accordingly. Asterix is added places wherever applicable, like when a number follows a character. For every element in the grouped list from the previous step, it is checked if it begins with an ‘(’ then handled by “Algorithm A”. Else if the element is ‘)’ then it is handled by “Algorithm B”. All other elements are handled by “Algorithm C”. Every element after grouping based on parenthesis are pushed into a new list called parangrouped list. In “Algorithm C” there is a check if the parenthesis is balanced in the temporary buffer. It is done using a stack as follows (Figs. 4–6 reveals the Algorithms B, A and C)
Core Algorithm.
A View of Algorithm B.
A View of Algorithm A.
A View of Algorithm C.
For every element in the string, If it is a “(” push it into the stack. Else if it is a “)”, then pop one “(” out of the stack. Neglect all other characters. At the end of the string, if the stack is empty then the string has balanced parenthesis.
The step is not completed with this. Just an iteration of the algorithm will not complete the task. First iteration of the algorithm will club the only one level of parenthesis, it will not handle nest parenthesis. So the number of iteration is same as the maximum level of besting in the given equation. This decides the complexity of the overall algorithm as well. The driver of the core algorithm based on parenthesis level is shared above (Fig. 7).
Driver Algorithm.
The list is nearly in line with java syntax now. The only problem now is ‘pow’ operator. Unlike other mat function, ‘pow’ has its operands before and after the operator. So, in this phase we will re-arrange the ‘pow’ from common writing practice to programming practice. If the input is 3pow4, it will be rearranged as pow(3,4). This is done using the below algorithm (Fig. 8).
The extraction of the left and right operands is the key part in this algorithm. This process is to be well thought about. The operands may be variables, numbers or expressions itself (enclosed in parenthesis). The FSM used for grouping in initial stage shall be used in here to extract the continuous alphabets / digits. Below is the algorithm for extraction of left operand.
Power handling.
Read the letter to the left of ‘pow’.
If is it an alphabets, traverse leftwards reading all the alphabets until a digit or operator is reached.
If it is a digit, traverse leftwards reading all the digits until an alphabet or operator is reached.
If it is a closed parenthesis, create a count variable and assign it to. While count is not 0 traverse leftwards doing,
If a closed parenthesis is read increment count
If an open parenthesis is read decrement count
If anything else is read, leave count unchanged.
If it is an open parenthesis or operator, report invalid equation.
The characters that were accumulated in steps 1.1 or 1.2 or 1.3 will give the left operand. The same algorithm starting from the character to the right of ‘pow’ and traversing rightwards will give the right operand. A notable change in the right operand case is, close parenthesis will be reported as invalid equation whereas open parenthesis will be processed for sub-expression.
Now all the ‘pow’ operators inside the parenthesis are arranged. The step is not completed yet. There may be a ‘pow’ operator outside the parenthesis. Consider the equation in the example “(3x) pow 5”. Here the ‘pow’ will not be rearranged after the above algorithm as it is not enclosed within any parenthesis. The algorithm for the same is simple and straight forward which is shared below.
Traverse through the list while,
Check if the element is ‘pow’
Then take the previous and then next element completely and rearrange them. As “pow(op1,op2)”. Here, op1 is the previous element and op2 is the next element in the list.
Else, proceed with the next element
The final list at this stage is in ready to execute form in any java compiler. There are some additional steps like the creating the complete java program out of this. The initial step towards that is getting the list of all unique variables in the equation. Now, a new file is created in the internal memory and the initial header files to be included are printed into it. The class is named as ‘Math Equation’. Inside the main function, a java scanner is created to get the values for all the variables in the given equation. Then the function called ‘Math equation1’ is called with all the variables that were scanned as arguments. With that the main function ends and there comes the core part of the app. The function ‘Math Equation1’ is declared and the final list after the above processing is converted into a list and added with a ‘return’ and printed in it. Now, the file is saved as ‘Math Function.java’. This file is ready to be compiled.
The app doesn’t ends in here, as promised we also plot the function and give it. The above code is executed for constant values 0 to 100 for the variable and the output is plotted in a graph for the users. There comes a problem, how an equation with more than one variable be plotted? We have solved it by plotting individual graphs for each variable by making all other variables constant. The application supports a maximum of 4 variables and plots the function in four different graphs. These graphs will be very useful for analyzing the behavior of the equations and selecting the best on based on the scenario.
The application was built successfully and it was tested for various different cases including logarithmic and trigonometric functions. On the other hand the application was tested for performance with comparatively longer equation with higher degrees for the variables. The application worked fine in all cases. Below are some sample cases and their outputs (Figs. 9–12).
Sample output for y = 5*x.
Sample output for y = apow5 + b/2 + 7*log(x).
Sample output for z = 5*ppow2 + sin(q).
Sample output for y = (1/bpow2) - apow2 + 11*c - tan(d).
The application is just an attempt to apply machine intelligence to a new domain of problem solving. As a basic feature, we have tried only for printed equations with basic operators and math functions. The app works successfully and as expected in all the test cases. We hope that this would definitely bring in a new dimension of mathematical problem solving. It has complete scope of expansions right from hand written recognition to operator and feature addition. Another noteworthy extension is getting the input range for plotting from the function dynamically based on the number of variables in the input function. Graphs comparing two equations and plotting them in different colors in same graph may be a very helpful feature that may be added to it. Now, the application just helps in analyzing and comparing equations for selecting the best one based on the features that the user needs. Using Deep learning techniques, the application can be trained to understand the problem for which the equation is to be selected and designed to recommend equations based on the problem. This application has big doors to open in AR, VR and image processing. On the other hand image processing, AR and VR are growing in a tremendous way which can also provide new shapes to this application [8, 9].