Handwritten Character Segmentation

Introduction

The purpose of this blogpost is to be briefly summarize the first progresses and intermediary results of our project.

Progresses

The group members for this project changed at the beginning of the semester but the project is well on its way now. These first two weeks were dedicated to the theoretical fundamentals that lie underneath the solution of our problem. We had a first meeting with the assistants to launch our project about handwritten character segmentation. Here is what they explained us about the problem we are trying to solve. We assume that we have some handwritten text from which the lines have already been extracted. Our task is then to figure out where we should cut the line into characters. This translates immediately into a binary classification problem, because at each position in the line we try to answer the question whether we should cut or not cut. Part of the project has to do with feature extraction (we will code in C++ and use the computer vision library OpenCV) and testing a binary classifier. We also learned that doing character segmentation is easier if we have information about the trajectory of the writing. For example, it is possible to do character segmentation and recognition on modern gadgets like tablets because you can take into account information about the speed and the acceleration at each point in time when the person was writing the text. Of course the material we deal with is just a 2D image where temporal information is lost. It is just static test, also called offline writing as opposed to online writing for the tablet example. Studies and experiments have proven the difficulties to successfully segment an offline text. This is the reason why a different approach is currently under investigation. Such approach consists in bringing a writing from offline to online. This is what we will be basically working on during this semester. It is important to point out once again that this is still a field of research where no universal solution has been found yet. A potential solution is discussed by Yoshiharu Kato and Makoto Yasuhara [1]. Their strategy relies on a strong and rigorous graph theory. To keep things simple, we are now dealing with text written in a single stroke. By stroke we mean a trace of pen-tip movement which starts at pen-down and ends at pen-up. We read an interesting article explaining a method to recover the drawing order. In graph theory this corresponds to a semi-Eulerian graph. Semi-Eulerian DHgraphs are well understood. Their main property is indeed the fact that the two endpoints of the stroke can be connected traversing all of the edges exactly once. However, such path is not unique and our goal is to identify the ‘right’ one among all possible alternatives. There many way to approach this problem. Considering all possible paths has been proven to be computationally too expensive as it often leads to combinatory explosions. The Basic Trace Algorithm looks like a simpler and more elegant solution, and claims to solve even complicated graphs. It takes advantage of the property of semi-Eulerian graphs, in which internal vertices always DH2have exactly 4 lines. Then the idea is to start from an endpoint, follow the edges, and when encountering an intersection, simply go straight, which means to choose the middle edge. Clearly it is not as simple as that, as may encounter double-traced lines and other special cases that are not easy to deal with.

Future Plans

We know aim to follow the calendar we set in December, and start implementing all we have learnt so far. In these two weeks we already started to get familiarity with OpenCV library, and especially with those commands that let us take a scan and transform it first to a binary black and white image, and then to skeletonize it. However, we already had the chance to see some of the problems we may encounter: among DH3Dh4the others, undesired lines or cluster at intersection points . So there really many issues we have to deal with. Fortunately, there is also much literature and tools in the field of image processing that can help us with that. Hopefully, we will be able to obtain some good result by the end of the month, so that we’ll be able to report it in our next blogpost.


[1] Yoshiharu Kato and Makoto Yasuhara, Recovery of Drawing Order from Single-Stroke Handwriting Images, IEEE, 2000
[2] Anuj Sharma, Recovery of drawing order in handwritten digit images , IEEE, 2013