1
$\begingroup$

I want to calculate vector paths that approximate pen strokes from handwritten documents. My tool needs to run in batch mode, unlike hand tracing or Illustrator's "Image Trace" feature.

The potrace vectorizer will only take black and white input -- but applying a color threshold to the scans destroys the useful detail in their smooth, blended edges.

I had some success with the SUSAN edge detector. It can take greyscale input and its output can be reduced to black and white. Here's a liberal set of edges found around the perimeter of the word "intention":

enter image description here

Now, how can I extrapolate the pen's possible path across the semi-enclosed area? I am aware that there will be ambiguities; potrace has several strategies for resolving them.

More broadly, are there better approaches to this problem?

$\endgroup$
1
$\begingroup$

...how can I extrapolate the pen's possible path across the semi-enclosed area?

There are infinitely many ways that this path could have been generated. Therefore, you will either have to make assumptions or use extraneous information for something that resembles "...the pen's possible path..." (which would not be too far away from the way potrace does it).

In any case, instead of applying edge detection, I would suggest that you apply skeletonisation first to get rid of the stroke's width and then try to work out the "evolution" of a much simpler path. The stroke's width generates what looks like a closed path which is incredibly hard to work out because of ambiguities (do I trace this clockwise or counter clockwise?)

Even when the skeletonised output is given, you still need extraneous information.

For example:

  1. Where did the pen land on the paper for the first time?

    • You could select the "left-most" pixel for that but cursive writing can result in heavily slanted letters where this assumption is false. Checkout the "y" on the word "yesterday" in this image for example (image taken from the Wikipedia article linked earlier).
  2. "Which process generated this curve?"

    • This is basically what you are looking for and possibly cursive writing could be expressed as some form of minimisation problem. That is: Find the shortest length curve that links as many of the given points as it is possible. Notice here, "curve", singular, one curve.
    • An algorithm that does this is Alpha Star. Alpha star operates over a graph data structure and finds a path that is optimal given a heuristic. Usually, this heuristic is an expression of "cost". Say for instance, the "cost" of establishing an edge between two points is proportional to their distance (definitely) but also how close that edge would bring us to the final destination. The algorithm basically calculates this for all transitions and then works out the path with the highest combined heuristics.
    • In your case, the graph data structure are all the points that result from skeletonisation connected at least with the very simple rule of shortest distance. So, you start at your "starting point", scan its neighbourhood for the nearest ink point, connect it, jump to the nearest and repeat. More than one pixels could be "nearest" in this case, which is fine at this stage, you connect them and then let A* tell you how to resolve a "fork".
    • In your case, the cost is obvious: The distance between pixels. But the heuristic is possibly where the game is won or lost. You can use the "how close it brings us to the end of the curve" but this means that you have an idea of where the curve ends.... Which brings us to even more assumptions:
  3. "Where did the pen lift from the paper?"

    • You can possibly identify far enough sequential points and mark them as the "end points". This would give you rudimentary start-end points for tracing the curve but where does this leave the dot above the "i"? Was it added while writing the "i" or at the end of a given "curve"?

For these reasons, I do not think that you would be able to recover the pen's movement without any extraneous data.

It would help even if you could make an assumption on the pen nib that the writing was made with because if it was a flat nib and it was held at an angle, it can give you information about its "orientation" and it is safe to assume that the writer was not rotating the pen in their hands. This gives you an additional criterion to that of the nearest distance. Nearest distance and smooth angle transition.

A more accurate method would be to record cursive writing movements for each letter and then recognise each (visually) and "fit" the movements to the point data with "transition curves" between the letters. This would give you the possible way a given writer could have written a particular script. You can capture this data with lots of different devices (tablets, e-notebooks).

Hope this helps.

$\endgroup$
  • $\begingroup$ Excellent, this gives me a lot to work with. Thank you for taking the time to write it up! $\endgroup$ – Aaron Brick Apr 4 at 17:16
  • $\begingroup$ @AaronBrick You are welcome, good luck with your project. $\endgroup$ – A_A Apr 5 at 9:24
  • $\begingroup$ Anyone else looking into this may want to investigate the Stroke Width Transform and the International Conference on Frontiers in Handwriting Recognition (ICFHR). $\endgroup$ – Aaron Brick Apr 6 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.