Extracting finite automata from hand-drawn images

No Thumbnail Available

Date

2020

Authors

Aruleba, Kehinde Daniel

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The recognition of shapes in graphical and handwritten documents (such as architectural drawings, mathematical notations, and engineering drawings) is an intensive re-search activity in the field of pattern recognition and document analysis. The process of recognising hand-drawn diagrams is an easy task for humans, but a challenging task for the computer to process automatically due to many factors like the variation in individual handwriting, writing style, and pen ball tip. In this work, we focus on how to use an offline recognition approach to describe, classify, recognise and generate transition tables for finite automaton (FA) diagrams drawn by students. To do this, we have investigated the different areas of handwriting recognition, with the aim of gaining a better understanding of this research area. Based on our findings, there is no existing dataset or system that uses offline recognition for recognising FA diagrams. This has led to the creation of our datasets (i.e. DBa and DBb) of hand-drawn FA diagrams. These datasets were used for the entire recognition process. In this thesis, we have introduced a multi-phase recognition algorithm. At each phase, the system takes as input the output from the previous phase. Different pre-processing techniques were performed on an input FA diagram. We showed how bounding box segmentation using the structure of an FA diagram and the relationship that exists between the components of an FA diagram can be done. Also, this thesis explains why the bounding box segmentation approach will give a better result compared to segmentation at the stroke level. We went further to classify the components of an FA diagram to their unique classes. Evaluation of the recognition process was done at the structure level (i.e. stroke and symbol levels). At the stroke level, the algorithm achieved an accuracy of 95.4% and 94.0% at the symbol level on DB awhile it achieved an accuracy of 89.8% and 87.6% at both levels respectively on DBb. Also, the system transition table generator achieved an accuracy of 86.1% and 84.4% on DBa and DBb respectively. The idea presented in this study can aid academics teaching Automata Theory in assessing students’ exercises and examinations if implemented as a software prototype

Description

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the Degree of Doctor of Philosophy, 2020

Keywords

Citation

Collections

Endorsement

Review

Supplemented By

Referenced By