Levenshtein-based Handwriting Recognition

Fujimoto Seiji <fujimoto@ceptord.net>

This article demonstrates how you can use Levenshtein distance to recognize handwriting characters.

Demonstration

Draw a single digit number from 1 to 9 on the canvas. To clear the canvas, please click "Reset Canvas".


How it works

This software does the following to recognize the character you draw.

  1. Capture the mouse movement as an array of XY coordinates.
  2. Compress the gist of the array into a short string.
  3. Performs the nearest neighborhood search against the character models.
  4. Return the model with the best score.

For more details, please read the code and explanation below.

Download

charec-0.3.zip (2020-07-05, 4.8kb)

charec-0.2.zip (2017-10-06, 47.9kb)

You can view the latest code on cgit (also on GitHub)

Intersting, but is it actually useful?

Not much, but I think this software is very useful to illustrate how widely applicable the Levenshtein distance is.

More generally, I think there is two distinct views about the Levenshtein distance. Popular but narrow-in-scope one, and alternative but more interesting one. Each view provides a different vision of what the Levenshtein distance is about, and what it can accomplish.

Popular View

The popular view is that the Levenshtein distance is a similarity metric for strings. If you input two strings, it will return a number that shows how alike they are -- the smaller, the more similar. This metric is, people say, useful for linguistic tasks.

For instance, suppose you're trying to find the correct spelling of a mistyped word. You feel the spelling is not correct, but not far off. In theory, you can filp through an English dictionary to find out the correct spelling, but it is rather tiresome to do so.

So instead, you teach computers to iterate over the dictionary. Since computers do not have an innate understanding of "similarity", you tell computers to use the Levenshtein distance and bring back the word with the best score.

The basic point here is that Levenshtein distance works as a rough approximation of the human perception of string similarity, in particular, in such a form that computers can understand.

Alternative View

There is nothing wrong about the view described above. Indeed, this is mostly how the Levenshtein distance is used in real world.

However, there is a more interesting (albeit less common) view of Levenshtein distance. To put it short, we can think of it as a similarity metric for everything.

That is, the Levenshtein Distance is a universal similarity metric that is applicable to a wide range of objects (e.g. images, graphs or handwritings). The catch is that you need to find some way to represent these objects as strings. If your string representation is reasonably good, you can use the Levenshtein distance to measure the similarity of these objects.

Here is how it typically goes like:

  1. Take an object X that you want to measure the similarity.
  2. Find some way to convert X into a sequence of characters.
  3. Measure the Levenshtein distance.
  4. Now you have similarity metrics for X.

This is essentially how charec works. It takes a set of strokes traced by a pointer, and compare their similarity by passing them to a Levenshtein distance function.

For encoding, I used the Schimke-Vielhauer-Dittman technique[1] and it turned out to work surprisingly well.

References

  1. Schimke, Sascha, Claus Vielhauer, and Jana Dittmann. "Using adapted levenshtein distance for on-line signature authentication." Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004.. Vol. 2. IEEE, 2004.
    http://zeus.fh-brandenburg.de/~vielhaue/jabreflib/[ScVD2004].pdf

License

I hereby place my work "charec" into the public domain. All my copyrights, including related and neighbouring rights, of this work are abandoned.

2019 Fujimoto Seiji <fujimoto@ceptord.net>