Handwritten Character Recognition: Machine Learning Algorithms and Programming Languages

HANDWRITTEN CHARACTER RECOGNITION Logan Porter Amari Vaughn Li Xiuyu IRES Summer 2018 Nanjing University of Science and Technology

OUTLINE Introduction Objective Machine Learning Algorithms Programming Languages (C++, Python, R Studio) Approach Experiments Results Conclusion Future Works Acknowledgements

Introduction OCR is an application that processes and converts handwritten images into a machine-encoded text by way of computer Character recognition is an effective approach to the validation of printed data records invoices, license plates, bank statements, receipts, cell phones, keypads, passports, etc., OCR is used to appropriate workflows in various fields and improves the processes of them. Our group used various machine learning algorithms to classify and recognize the handwritten characters.

Objectives Use various machine learning algorithms to classify and recognize handwritten characters. Utilize 3 different programming languages to compare results Apply classifiers to two separate datasets.

Machine Learning Algorithms KNN (k-nearest neighbor) Na ve Bayes SVM (support vector machine) Random Forest

Programming Languages C++ Python R Studio 6

Approach To handle perform tests on data we will use three tools for machine learning classification: C++, Python Sklearn library, R-Studio Perform classifiers on two datasets: UCI Machine Learning Repository Handwritten Digits and UJI Pen Characters dataset 7

Approach Datasets: Optical Recognition of Handwritten Digits 5,620 images, 3,823 training, 1,797 testing. Digits 0-9 , calculated as a grayscale value with the range 0 (white) to 16 (black) Represented as 32 by 32 matrices where each pixel is binarised as a 1 or 0 8

Approach Datasets: UJI Pen Characters dataset 1,364 samples split into 35 classes 26 characters (A-Z) , 9 characters (0-9) zero s and o s are classified together Gathered on a Toshiba Port g M400 Tablet PC 9

Approach The data imported within R Studio displays as one image per row 64 columns representing the pixel totals of each of the 8 by 8 blocks. The 65th row contains the target label (actual digit) of that image. 10

Experiments KNN with R Studio We applied k-nearest neighbor to the digit dataset in R-Studio. KNN is a non-parametric learning algorithm and stores all cases to classify new cases based on similar parameters. Dataset used was the UCI Optical Handwritten Character Digit dataset A code was generated to test for all k-values. An optimal k- value was calculated and an accuracy result of 97.99% was reached. 11

Experiments KNN with R Studio # View 31st image digit 7 row.id <- 31 m <- matrix(as.numeric(traindata[row.id, 1:64]), nrow=8, ncol=8) matrix(as.numeric(traindata[row.id, 1:64]), nrow = 8, ncol = 8) : image(m[,8:1], col=grey(seq(0, 1, length=16))) 12

Experiments KNN with R Studio #k value of 1 pred <- knn(optdigits[,1:64], optdigits.tes[,1:64],optdigits[,65], k=1) #compute accuracy of knn mean(pred == optdigits.tes[,65]) ## accuracy = 97.99% 13

Experiments KNN with R Studio #find optimal k value res = matrix(nrow=100,1) for (k in 1:100) + {pred <- knn(optdigits[,1:64], optdigits.tes[,1:64], optdigits[,65], k) + res[k] <- mean(pred == optdigits.tes[,65])} 14

Experiments KNN with R Studio We computed a code to get the precision and recall values. Precision is the fraction of correct predictions for a certain class. Recall is the fraction of instances of a class that were correctly predicted. A confusion matrix was also generated to show error percentages. 15

Experiments n = table(pred, optdigits.tes[,65]) nc = nrow(n) KNN with R Studio diag = diag(n) rowsums = apply(n, 1, sum) colsums = apply(n, 2, sum) p = rowsums / n q = colsums / n precision = diag / colsums reecall = diag / rowsums f1 = 2 * precision * recall / (precision + recall) data.frame(precision, recall, f1) 16

Experiments KNN with C++ The distance was calculated between every test sample and all the training samples 17

Experiments KNN with C++ Every instance in the datasets is a 32x32 bitmaps, the program reserves every sample into a 32x32 matrix,and then change it into a 1024- dimensional vector. Every vector and its real value are reserved into a struct named Digit Create a struct named Distance ,with a float value distance and an int value value . Read trainfile and store all the train samples into Digit digit[2000] 18

Experiments KNN with C++ #include <stdlib.h> using namespace std; struct Digit { int dig[1024]; int value; }; struct Distance{ float distance; int value; }; Digit digit[1934]; Digit testDigit[946]; Distance distance[2000]; 19

Experiments KNN with C++ Calculate the distances between every test sample and all the train samples,and store into Distance distance[2000]. Compare the distances and choose the smallest n distances. Vote to elect the most suitable class. 20

Experiments KNN with C++ float calDistance(Digit digit1, Digit digit2) { int i, squareSum = 0.0; for (i = 0; i<1024; i++) { squareSum += pow(digit1.dig[i] - digit2.dig[i], 2.0); } return sqrtf(squareSum); } 21

Experiments KNN with C++ int prediction(int K, Digit in, Digit *train, int nt)/* digit*/ { int i, it; Distance distance[1934]; for (it = 0; it<nt; it++) { distance[it].distance = calDistance(in, train[it]); distance[it].value = train[it].value; } int predict = 0; int b0[10] = { 0 }; selectSort(distance, nt); for (i = 0; i<K; i++) . if (b0[m] >= max) { max = b0[m]; predict = m; } } return predict; 22

Experiments SVM with R Studio SVM is a supervised associative algorithm that analyzes data with regression analysis and other features. Non-problalistic binary linear classifier SVM separates data into different categories and divides by gaps within data. 23

Experiments SVM with R Studio We generated, trained an ran an SVM model on the test data. A model was created using a svm function with several parameters: selected training data, the scale and the response vector. The classification accuracy result was 96.77% 24

Experiments SVM with R Studio #train SVM model svm.model <- svm(trn[,ndx], factor(trn[,65])) print(svm.model) #run svm model on test data pred <- predict(svm.model, tst[,ndx]) mean(pred == tst[,65]) ## accuracy for svm = 96.77% 25

Experiments Random Forest with R Studio Random forest is a flexible, easy to use - supervised learning algorithm. RF is fast to train but very powerful. The algorithm actually creates a forest created of trees and makes the data random. This algorithm was applied to the dataset to set a comparison to the other methods used. 26

Experiments Random Forest with R Studio We generated a code that calls print on on random forest to give information about the method and create confusion matrices. There were 8 variables tested at each split and 500 decision trees used. The training error was 1.73% and the test error was 2.62%. The accuracy result was 97.38% 27

Experiments Random Forest with R Studio # Random Forest Classifier rf <- randomForest(trn[,1:64], factor(trn[,65]), tst[,1:64], factor(tst[,65]), ntree=500, proximity=TRUE, importance=TRUE, keep.forest=TRUE, do.trace=TRUE) print(rf) # run randomforest pred <- predict(rf, tst[,1:64]) mean(pred == tst[,65]) #accuracy for randomforest = 97.38% 28

Experiments Naive Bayes with Python Sklearn A probabilistic classifier which use Bayes theorem to determine the probability of correct or misclassification. Is supervised ,meaning that we use information we know to determine a probability 29

Experiments Naive Bayes with Python Sklearn Simple and efficient tools for data mining and data analysis Accessible to everybody, and reusable in various contexts Built on NumPy, SciPy, and matplotlib Open source, commercially usable - BSD license 30

Experiments Naive Bayes with Python # Create a classifier: a support vector classifier classifier=make_pipeline(LinearDiscriminantAnalysis(), GaussianNB()) classifier.fit(data[:(3**n_samples)//4], cdata.target[:(3**n_samples)//4]) expected = cdata.target[n_samples//4+(3**n_samples)//4):] predicted = classifier.predict(data[n_samples//4+(3**n_samples)//4)]) An example in python with the sklearn library generating a naive Bayes classifier with a 75% training and 15% testing split. 31

Experiments Random Forest with Python clf = make_pipeline(LinearDiscriminantAnalysis(),RandomForestClassifier(max_depth=20, random_state=0)) RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini', max_depth=2, max_features='auto', max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, min_samples_leaf=1, min_samples_split=2, min_weight_fraction_leaf=0.0, n_estimators=10, n_jobs=1, oob_score=False, random_state=0, verbose=0, warm_start=False) An example of A random forest model built in Python (Accuracy 92%) 32

Experiments SVM with Python classifier2 = make_pipeline(LinearDiscriminantAnalysis(),svm.SVC(gamma=0.001)) classifier.fit(data[:(n_samples//4+(3**n_samples)//4)], digits.target[:(n_samples//4+(3**n_samples)//4)]) An example of A random forest model built in Python (Accuracy 95%) 33

Experiments Expanding data in Python Although these resulting accuracies are viable, the dataset used only included samples of numeric written characters. To further test ML models, we included an additional 120 samples of alphabetical character images into our data. 34

Experiments Expanding data in Python We transformed the alphabetical characters images into 32 by 32 matrices. This matrix is created by firstly retrieving RGB values from the image using the PIL(Python Imaging Library) which allows image manipulation and pixel data extraction from images. 35

Experiments Expanding data in Python def evalpixel(a): #get black pixels if((a[0]==0) and (a[1]==0) and (a[2]==0)): return 1 else:return 0 36

Experiments Expanding data in Python Image as Binary Matrix 37

Experiments Expanding data in Python Previous data set 1797 New dataset 1892 Final matrix 8x8 matrix of the lowercase handwritten letter b . Accuracy is 95% with a 90%/10% train-test split 38

Results Training digits 39

Results To further test ML models, we included an additional 120 samples of alphabetical character images into our data. We transformed the alphabetical characters images into 32 by 32 resolution images. 40

Results Classifiers in Python Naive bayes with Linear discriminant analysis shows 92% accuracy with 91% recall and 91% precision. PCA applied to naive Bayes has a lesser accuracy of 85%. 41

Results KNN R Studio The figure shows the optimal k value for knn is 1. With a k value of 1 the accuracy result equals 97.99% ~ 98%. 42

Results Random Forest R Studio The graph displays the number of decision trees used and the error percentage associated with the amount of trees. The larger the number of trees, the lower the error percentage. 43

Results Average Accuracy, Recall, Precision The table shows the average accuracy results between each algorithm used and the language it performed the best in. 44

Conclusions We combined two feature vectors, pixel intensity and stroke traces, and four classifiers. The accuracy results were higher than expected compared to other research reports. Results are competitive with one another within each programming language used. The highest performing classifier was KNN with C++, 98.8%. Limitations include the character dataset size and features extracted.

Future Works Create an algorithm that will train and test handwritten English alphabetic characters Use deep neural networks and learning quadratic discriminant functions to work on improving accuracy results Build a framework to identify difficult characters within dataset (e.g., !, #, $, %) Utilize a more advanced character recognition system

Acknowledgements Nanjing University of Science & Technology Professor Zhong Jin and his team Professor Jian Yang, Dean, School of Computer Science & Engineering Key Laboratory of Intelligent Perception and Systems for High- Dimensional Information (KLIPSHDI) of Ministry of Education, China National Science Foundation under Grants HRD-1623358 and HRD-1719498 47

Thank you! Emails: lnporter@aggies.ncat.edu aavaughn@aggies.ncat.edu lixiuyu905@163.com