Pen stroke recognition

A couple of months back, before I bought my Tablet PC, I tried to understand how pen input recognition works.
Not being overly ambitious I looked at single stroke character or Graffiti-like recognizers. The result of a week-end of tweaking is a C# winforms recognizer, that only requires the .NET SDK (no Tablet PC).

Run the .Net demo.

Intro
The two main categories of handwritting recognizers are single-stroke (unistroke) and multi-stroke.
Palm and PocketPC only support a simplified unistroke alphabet, as it is easier to recognize.
If you don't have Palm you can try the online Graffiti demo (requires Java).
On the other hand, Tablet PC has a multi-stroke regognizer, that support real-life handwritting (at least with my handwritting ;-).

Google
After some search on the subject, I was able to find at least two documented methods of recognizing unistroke alphabets.
One is base on the Rubine algorithm, which I didn't get to understand very well.
The other is based on the representation of a stroke as a serie of directions. I don't know the name for this algorithm, I call it the gesture recognizer, as I found it used for this purpose.

The gesture recognizer
In this model, a stroke is represented by a serie of directions (Up, Up-and-Left, Left,...).
The reference strokes are represented as a sequence of directions as well, or even as a regex of directions (Up Up-and-Left? Left).

After being normalized to this format, it is easy to compare an input with each reference letter to find out which one matches.

The Mozilla gesture recognizer uses this model and its source code can be found on the Mozilla CVS web. The code contains some good info in gestures.js and gestimp.js.

I did not experiment with this method, but would expect it to be rather cheap computationally. Also I wonder if it is powerful enough to recognize a full Graffiti-like alphabet.

Graffiti demo
After finding the Graffiti demo applet I started reverse engineering it and decompiling it.
The demo is simple enough and it doesn't contain many classes. So method by method I went through the decompiled code and figured out the algorithm, commenting out the code and renaming variables to make sense.

The principle for the Graffiti demo is that every stroke is normalized by bringing it back into a unit square and with a constant number of interpolations. The reference alphabet is also normalized.
Then the input stroke is compared to each reference stroke, by computing the distance between them, point by point.
The reference stroke that is found to be the closest is the match.
A manual refinement step is then applied to improve the result for letters that looks alike (like L and h, or D and P).

Installing C# Graffiti
First, if you want to try my version of the Graffiti recognizer, go to my cvs repository and download MainForm.cs. Update: CVS is down (I only have a web hosting solution for now), so I made a copy of MainForm.cs, that you can download.

Then run csc MainForm.cs.
You'll get a MainForm.exe executable that you can run. Try drawing Graffiti symbols in the form.
The Graffiti alpahabet that I used is slightly different than Palm's, but most letters are the same. The C# Graffiti also contains a digit recognizer but you need to change the code a little bit to use it.

C# Graffiti code details
In terms of improvements, I cleaned up the code so that it should be easier to have a recognizer for letters, one for digits and also to add custom alphabets.

There is also one thing that is bad with the Graffiti demo: it always finds a match, whatever you draw in. To resolve this, I added a constraint verification phase at the end of the recognition phase, that verifies that if an A was matched, the ends of the stroke should be in the lower left quadrant and in the lower right quadrant, for example. Other types of constraints are applied on a case by case basis, like the directory of the ends: the ends of C should point toward the right, for example.
Also there is another restriction on the quality of the matches: if the distance between the stroke and the matched letter is greater than a certain threshold, the match is discarded.

Future
Overall I am pretty happy with the result. But I recently got a Tablet PC, which includes the PocketPC recognizer in addition the multi-stroke recognizer, and for some reason I find it pretty inaccurate and uncomfortable.
So I plan on porting my C# recognizer to the Ink API for custom recognizers for Tablet PC, someday.
The ultimate feature that I find missing for Tablet PCs is some way of actually programming using the pen. Using heavy auto-completion with some heuristics and improved UI (most common completions should be easy to reach), automatic code beautifying and some smart shortcuts (IF should directly display an extra pair of parenthesis and curly brackets), it should be possible to minimize the typing required.

I hope you have fun with stroke recognition,
Dumky

Some more related links:
Another stroke recognition engine, used in Emacs

Update: Here's the location for the new Palm Graffiti page. It has a demo applet for Graffiti 2 as well.

The Metropolis keyboard, another stylus based text input solution, based on an optimized virtual keyboard:
http://www.almaden.ibm.com/u/zhai/papers/Softkeyboard/UISTCamera.pdf

Other papers by Shumin Zhai:
http://www.almaden.ibm.com/u/zhai/publications.html

Here is another unistroke alphabet similar to Graffiti, called EdgeWrite. Its specificity is that it constraints the alphabet into a square, by adding a square hole on the input surface. http://www.cs.cmu.edu/~jrock/pubs/uist-03.pdf

Hello,

I would like to download your Graffiti-like application. But I can't ! Please help me...

Thanks

CVS is down for now (I don't have a hosting solution yet). I copied MainForm.cs so it is now directly available via http://blog.monstuff.com/archives/images/MainForm.cs

Cheers,
Dumky

Hi Dumky
Indeed you have a nice work in developing this MainForm.cs! Well, I would be really thankful to you if you could make me available the .class file of the Graffiti demo applet.I am comfortable with java but can't understand C#.
Looking forward for your help...
Thanks

Palm’s Java applet has moved to http://www.palmone.com/us/products/input/
Unfortunately I haven’t kept the de-compiled java source code. But any java decompiler ( http://www.google.com/search?q=java+decompiler ) will do the trick. With the decompiled source, you need to figure out what each method does and rename the variables to something meaningful.

I suggest you give a look at the C# code if you want to avoid this hassle, as C# really is very close to Java.
The algorithm is simple: normalize (break down into a given number of sub-parts fitting in a 1x1 square) a reference alphabet, do the same with the input stroke, compute the distance (sum of distances between the nth part of the reference letter with the nth part of the input stroke) and find which reference letter has the minimal distance. Then apply some manual tweaks/hacks to improve the recognition and eliminate letters than don’t make sense using some constraints.

Hi Dumky,

I can't seem to figure out how to decompile the java applet from the Palm page... and I don't know how to convert the C# code in java...

Could you please help??

Thanks

I am also intrested in obtaining or decompiling the java source code from the Graffiti applet but I am unable to retrive the code from the web site... PLEASE HELP
Thank YOu

Hi Lisa and Adrian,

Searching on Google with http://www.google.com/search?q=java+decompiler you can find a couple of good de-compilers.
I think that I used DJ.
You first need to download the class or jar file from the Grafitti demo page. Then you run the decompiler on that file and you should get some java code. The code won't have nice function names or variable names though... so you have to figure out what each method is for, but the Grafitti 1 demo code is not very complex.

I'm sorry i should have made myself more clear. I could not find the location of the Graffiti 1 demo code (class or jar). I was able to find the jar for the Graffiti 2 demo at www.palmone.com/us/images/products/basics/graffiti2/PalmG2Demo.jar
and I decompiled the classes. The java code had several goto errors in it but i got what seems like a crippled version to run. I would much rather look at the code for the Graffiti 1 demo though as it seems to be somewhat simpler. If you know where the .jar is located now that would be wonderful. Otherwise I think i will try to use the C# code to write a java program.

Thanks Again

Adrian, I tried to repeat my steps and de-compile the demo again (using DJ) and I ran into the same problem, trying to figure out which class implements the demo.
It turns out that the Graffiti 1 demo class is not in the jar file. Instead it is located at http://www.palmone.com/us/products/basics/graffiti/GraffitiRecognizer.class (the url of the demo page is used as the base for the GraffitiRecognizer.class applet).

Hope that helps,
Julien

Julien,

You said, "So I plan on porting my C# recognizer to the Ink API for custom recognizers for Tablet PC, someday." in this blog. Have you made any attempts at porting to the Tablet PC SDK? I read the article by Casey Chestnut that you referenced, where he extends the RecoDLL example distributed with the SDK. http://www.tabletpctalk.com/developer/tabletReco/index.shtml

The full source code is not listed, and a lot is left to inference with statements like: "Coded it to do a full recognition with sample code available from the SDK documentation."
I can't get the CreateContext() and AddStroke() methods to fire. It's a nice backgrounder on Custom Recognizers.

Larry O'Brien has another excellent "How To" article on Shape Recognition. Again, "(Source code included.)" is stated at the beginning of the article. Apparently the link to the source at the end of the article has been removed.

The Leszynski Group probably has the best, freely available recognizer engine -- inShape. Only, you have to bug them everytime you want a new shape. They maintain a proprietary library. Also, it's totally not supported. The download says the eval period has expired after only 1 day! I have yet to get a response back for a new evaluation or even to purchase a license for the thing.

hello sir,

I, yaser irfan, am studying final year engineering in the feild of I.T.
I am doing my final year project,which consists of writing a software program to detect shapes and thus objects in images using C#.net.
I named the project as Robo-Vista. I am new to C#.

My approach for the project is as follows:
we need to train the system with the image of the shape to be identified using neural network and then provide the sytem with the image from which the trained shape is to be recognised.

The deadlines for my project are near. The recognition part is ok but still i do not have a neural net to train the images. thus i request you to help me out with such kind of neural net.

with lot of hope,
yaser irfan
yaserirfan@gmail.com

Yaser,
I won't be able to help you much, as my knowledge of neural networks is still limited and I have little spare time.
You should check out The Code Project, which is a cool website with a lot of good articles. I seem to remember a couple of them related to neural networks in C#.

Hi I'm working on a project, which has involved developing a gesture engine, and I think what you have done sounds interesting and very useful.

I have tried your graffiti C# code. Excellent.
Myself, I have been using JavaStroke, which is a version of Libstroke which I ported to VB6 :/ so I could use the engine native on the win32 platform. I also ported the gesture engine to C# (Java and C# are very similar so it was very straightforward). But your version of Graffiti is much more robust and accurate than the versions I have been using.

Anyway wanted to acknowledge your efforts. Also you to have an interest in gesture so I though I'd drop in my ten penneth.

There is a company called Sensiva.com that do a program called symbol commander, I love it and use it lots. Also there is Stroke It. But I guess you know about these.