Αναγνώριση Χειρόγραφων Μαθηματικών Εκφράσεων Εντός Γραμμής (online)

Abstract

Αντικείμενο της διατριβής είναι η αναγνώριση χειρόγραφων μαθηματικών εκφράσεων (ΜΕ). Η κύρια συνεισφορά της παρούσας εργασίας αφορά στο σχεδιασμό και στην υλοποίηση ενός συστήματος αναγνώρισης ΜΕ που λειτουργεί σε τρία στάδια στάδια: α) την ομαδοποίηση των κονδυλιών σε σύμβολα και ταυτόχρονη αναγνώριση των συμβόλων, β) την αναγνώριση των σχέσεων μεταξύ δύο μαθηματικών συμβόλων ή υπο-εκφράσεων και γ) την ανασύσταση της μαθηματικής έκφρασης και η αναπαράστασή της με βάση το μορφότυπο MathML (Παράρτημα Β), με δεδομένη την αναγνώριση και την σχέση μεταξύ των συμβόλων που την απαρτίζουν. Στο πρώτο στάδιο, προτείνεται η κωδικοποίηση της ακολουθίας των συντεταγμένων των συμβόλων σε ακολουθίες κωδικών Freeman-8 επιπέδων συνοδευόμενων με το ποσοστό του επιμέρους μήκους μεταξύ δύο διαδοχικών σημείων. Η σύγκριση των υπό εξέταση συμβόλων με τα πρότυπα αναφοράς γίνεται με την τεχνική της απόστασης του κοντινότερου γείτονα με βάση το ταίριασμα στα δείγματα (template matching) των προτύπων αναφοράς. Στο δεύτερο στάδιο χρησιμοποιούνται τα γεωμετρικά χαρακτηριστικά των συμβόλων της μαθηματικής έκφρασης (π.χ. κεντροειδές, πλαίσιο οριοθέτησης) για την εύρεση των σχέσεων μεταξύ των συμβόλων (π.χ. εκθέτης, δείκτης) και την κατανομή τους σε επιμέρους υποεκφράσεις (sub-expressions) της ΜΕ. Στην παρούσα εργασία αναπτύχθηκαν δύο τεχνικές. Στην πρώτη τεχνική χρησιμοποιήθηκε ο γεωμετρικός ταξινομητής για την εύρεση της τοπολογικής σχέσης μεταξύ των συμβόλων που απαρτίζουν την ΜΕ και την τοποθέτηση αυτών στα αντίστοιχα επίπεδα της ΜΕ. Τα σύμβολα που ανήκουν σε διαφορετικά επίπεδα ενώνονται με σύμβολα άλλων επιπέδων βάση της τοπολογικής σχέσης που υπάρχει μεταξύ τους. Τέλος, αφού όλα τα σύμβολα έχουν τοποθετηθεί στα αντίστοιχα επίπεδα και οι σχέσεις μεταξύ των συμβόλων έχουν οριστεί, παράγεται ένα MathML αρχείο για την αναπαράσταση της ΜΕ. Οι μαθηματικές εκφράσεις που μπορούν να αναγνωριστούν με αυτή την τεχνική είναι μέχρι ενός επιπέδου πάνω (εκθέτης) και ενός επιπέδου κάτω (δείκτης). Στην δεύτερη τεχνική χρησιμοποιήθηκε ένας ταξινομητής βασισμένος σε SVM για την εύρεση της τοπολογικής σχέσης μεταξύ των συμβόλων που απαρτίζουν την ΜΕ. Στο τρίτο στάδιο, αναπτύχθηκε μία στοχαστική γραμματική (SCFG) για την περιγραφή της σύνταξης των ΜΕ. Αφού ορίσουμε την γραμματική, μπορούμε πλέον να ψάξουμε για την πιο πιο πιθανή υποψήφια μαθηματική έκφραση λαμβάνοντας υπόψη τις τοπολογικές σχέσεις μεταξύ των συμβόλων και/ή των υπό-εκφράσεων. Για να αναλύσουμε αποτελεσματικότερα μια ΜΕ, πρέπει πρώτα να όρισουμε ένα αλγόριθμο ανάλυσης (parsing algorithm) της ΜΕ. Σε αυτή την εργασία χρησιμοποιήσαμε τον αλγόριθμο Cocke-Younger-Kasami (CYK) κατάλληλα τροποποιημένο ώστε να μπορεί να αντιμετωπίσει το πρόβλημα της ανάλυσης των μαθηματικών εκφράσεων.Τέλος, αναπτύχθηκε ένα πρόγραμμα συλλογής χειρόγραφων μαθηματικών εκφράσεων για την δημιουργία βάσης χειρόγραφων μαθηματικών συμβόλων. Η βάση που δημιουργήθηκε αποτελείται από 186 σύμβολα που συλλέχτηκαν από 50 γραφείς. Κάθε γραφέας έγραψε κάθε σύμβολο 5 φορές. Επιπλέον, κάθε γραφέας έγραψε 54 εξισώσεις οι οποίες περιέχουν τουλάχιστον από μία φορά όλα τα σύμβολα που προαναφέρθηκαν.Για την αξιολόγηση του αλγορίθμου αναγνώρισης των χειρόγραφων μαθηματικών συμβόλων χρησιμοποιήθηκαν δύο βάσεις χειρόγραφων μαθηματικών συμβόλων, η βάση LaViola και η βάση CROHME2014. Το ποσοστό ορθής αναγνώρισης είναι 92% στην βάση LaViola και 77.25% στη βάση CROHME2014. Για την αξιολόγηση του αλγορίθμου εύρεσης των σχέσεων μεταξύ συμβόλων χρησιμοποιήθηκε η βάση χειρόγραφων μαθηματικών εκφράσεων MathBrush, με μέσο ποσοστό λάθους 2.87%. Τέλος, για την αξιολόγηση του αλγορίθμου ανασύστασης της μαθηματικής έκφρασης χρησμιποποιήθηκαν οι βάσεις CROHME2012 και 2013. Οι βάσεις CROHME2012 και 2013 αποτελούνται από 4 μέρη: Μέρος-I, Μέρος-II, Μέρος-III και Μέρος-IV. Το ποσοστό ορθής αναγνώρισης του προτεινόμενου αλγορίθμου είναι 78.70%, 65.78%, 56.37% και 50.22% για τα τέσσερα μέρη των βάσων CROHME2012 και 2013.