It only works if the starting point of a gesture is as expected. If I start a rectangle in the top right corner then it is characterized as a caret. Only a start in the top left results in a rectangle.
Right, this is expected. I would think of a "gesture" as a series of points over time (relative to the starting point) - it is path dependent, so a clockwise circle is recognized differently from a counter-clockwise circle.
The paper (citation 11 for the $1 version) goes into more detail. One neat feature is rotation invariance, where you can draw a tilted version and still have it be recognized.
I added a second rectangle as an example starting from a different point, and it never misrecognized any of my rectangles for carets or square brackets again.
Adding left and right parenthesis started messing up with the square brackets, but then I added a couple more of each square and round brackets and it worked perfectly.
Differentiating from lowercase y and g was next to impossible, though...
This varied a lot for me during testing - It looks like it's actually comparing rotations of the gesture to find a match
It would nail the zigzag and most of the star/box shapes even if I intentionally started in a different place (Very first thing I tested, I'm left handed and start characters/shapes in different places)
It did not handle shapes that are rotationally similar - ex: right square bracket starting from the bottom is always detected as left square bracket, probably because the gesture matches the left bracket, rotated 180 degrees.
It also flubs arrows going right to left (they always come up as v for me)
Palm apparently had to change graffiti later to use multiple strokes for some letters, as someone had a patent on letter-recognition via single-stroke letters.
Unistroke recognizer are super easy to write and a nice little afternoon project:
Take the time derivative of the trajectory, and ignore it until it's "large"
Once it becomes "large" normalize it to one of 8 directions (N NE E SE S SW W NW) and push the direction into a list then repeat until the derivative becomes "large" in a new direction or you stop getting input.
At the end you have a string you can look up in a table to get the character.
EDIT: after reading the comments apparently the algorithm PalmOS uses is slightly different.
There's a good reason for that. Graffiti was....derivative of Unistroke, which was developed at PARC as, IIRC, part of the Parctab project. Xerox even sued.
Sorry, correction: «which works really well right now».
I still use Graffiti, on Android, as the only keyboard on almost all of my devices. (Exceptions are relevant to technical constraints - no touch, low framerate screens etc.)
There is an improved version of this algorithm called $Q Super-Quick Recognizer [0] which allows multi-stroke gesture and drawing stroke in different direction, a demo I implemented before [1]
The $1 algorithm could be used to implement gesture typing keyboard like SwiftKey/Swype, where direction matters, eg another project of mine [2]
I'm a big fan of the $1 Unistroke Recognizer - it's just so cool that it works so well with minimal training. I was itching for a reason to use it and threw it into a flag semaphore decoder. Then I realized it was completely the wrong tool for drawings with only (8 choose 2) combinations where rotation does matter, and did something else instead. So, I'm still itching for a good reason to use it.
I played around with it last few days and I'm impressed by how capable thing is for its size / simplicity.
It is actually cheap enough to run per-frame in real-time, which is a fun way to see it in action and to check how soon it arrives at correct answer.
Other commenters focused on 'issue' of gestures being directional. This is a great feature as you can fit more gestures into a set with correct recognition. For example you can have space and backspace as lines in different directions. It is also trivial to just add the reversed variants if needed.
I had bigger problem with the algorithm being rotation-invariant. This means that '7' will easily be recognized as 'L'. Thankfully this is easy to fix.
The recognizer can quite reliably recognize whole alphabet. I used Palm Graffiti designs as reference for training. One training sample was always enough.
I checked out other multi-stroke recognizers on that page. They don't seem any more reliable, but all add more complexity. You have to detect when multi-stroke gesture is over which is not trivial. This uni-stroke version works wonderfully because gesture is done as soon as mouse button is released.
Thank you for this submission! As say in the published article, this is often needed functionality and most of us think it's too complex to be worth it. Turns out the algorithm is quite simple and reliable.
I recall experimenting with similar approaches about 2 decades ago; depending on your gestures you can actually simplify a lot:
- normalize the draw height/width
- use polar coordinates before normalizing
- normalize the length of the drawn path
- DAG to recognize shapes faster, using partial paths
- only taking into account corners with angles over a certain treshold
- ...
The possibilities are endless, and this is a good exercise to explain that slight alterations on your problem space can have a huge impact on your solution space.
This might be obvious to everyone but me, but how do you read "$1" in this context? Do I read it as "one-dollar", or "dollar-sign one", something else? Thank you in advance
I used it to integrate sketching into a web-based diagram editor ~10 years ago and it was a breeze. OK, I had to train it myself. But it takes only minutes to draw all the shape variants needed. In practice I used 6 shapes and about 5 variants per shape. I conducted a usability test and the $1 recognizer only failed to recognizes the sketches 2-3 times out of ~300 shapes drawn by different users with no additional training.
In case anyone is interested, the $N-Protractor algorithm was ported to Python for use in the Kivy framework [0]. Unfortunately it's tied to kivy's clock among other things, but easy to rip it out should you need it in a different context. There is also anexample application that can be used to create gesture templates [1]
I remember porting this to Objective-C for an iPhone project forever ago. That was fun exercise, and the algorithm works surprisingly well for how simple it is.
Is this roughly how the various swipe-typing apps on phones work? Use the shape traced to do a range query in a table of words, and use textual context to prioritize the guesses?
They all need to be drawn in the same direction of the demo. If I draw them in the opposite direction ( example the circle instead of counter-clockwise, I draw it clockwise ), another shape is recognised:
When I was a teenager playing Dr Kawashima's Brain Training on DS, I had to completely change how I drew my 9s in order to get it to recognise them (it turned out I started in the wrong place for it to recognise the number).
I only played that game for a month or two, but it stuck with me and now more than a decade later I still draw my 9s differently.
Well, it's not magic. It probably recognizes direction of strokes. I imagine that you can start from scratch and train both directions to be valid, but then you will find more mismatches.