This is the last of the three blog posts in which we briefly summarize the progresses and intermediary results we obtained in the last few weeks.
For the last part of our project we focus on implementing the recovery of the drawing order of a text to the best of our abilities. Since the method described in the article is quite difficult to reproduce, especially for some complicated and critical cases, we will approach the upcoming part of our work by initially focusing on easier simplified problems. For example we will only allow for a single stroke and simple intersections of lines. Although this might seem very restrictive it indeed allows us to retrace some curves who might seem complicated at first sight. This simple operation, if used properly, can even become a very useful and powerful tool to recover the drawing of some letters that can be found in handwritten scripts. Eventually we expect to move onto more general cases to be able to recover the drawing of a wider range of scripts.
The implementation has started already. We decided to change our platform, in the sense that we will no longer write c++ code using the OpenCV libraries, but we will use MATLAB language. There are two reasons for such decision. First, writing on MATLAB is much easier, more intuitive, and there are fewer chances of bugs. Secondly, and most importantly, MatLab actually possesses a well-documented and efficient image processing toolbox that perfectly fits our needs. In particular the tool comes with an already built-in thinning function that therefore can be used as a pre-processing step of the drawing order recovery algorithm. Especially, the thinning algorithm in Matlab behaves much better than the one we had been using so far with the OpenCV libraries. More particularly, it is more accurate at the intersection points, whereas the OpenCV algorithm was often creating clusters. Avoiding cluster makes our life much easier when we try simulate the movement of a particle along the skeleton. Indeed, when arriving at a point belonging to a cluster, all possible directions are available, and is hard to find the right one, or also to avoid entering a loop.
No we briefly describe our algorithm to recover the drawing order. It basically follows the notions of graph theory we explained in the first blogpost. We first analyze every single pixel belonging to the skeleton, and we store some properties. So far we extract the coordinates and the degree, i.e. the number of neighboring pixels belonging to the skeleton ( clearly it can range from 1 to 8 ). So far we are assuming we only have pixels with degree 2 or 4. For the pixels of degree 2, the job is easy: just pass to the following pixel. For the pixel of degree 4, we choose to smoothest past, i.e. the one in the middle. With this algorithm we are able to recover the drawing order from any curve that does not intersect itself. The algorithm also works in case of intersection, with the restriction that the two lines crossing each other form a 90 degree angle. Clearly this is a strong limitation to the range of all possible cases.
We plan to extend our code to more complicated cases. This of course will be more difficult, as a bigger number condition will have to be analyzed. We also have another good news: we received a reply by Dr. Sharma, author of “Recovery of drawing order in handwritten digit images”. He implemented the recovery also in MatLab, and he will hopefully let us have access to his code as soon as possible. This would be a great inspiration for our project.