Nicolò Zereik and Luca Roverelli put together a neat tool for creating the JSON template files for the MultistrokeGestureRecognizer library:
It’s a small JAVA app — check it out if you’re looking for a simple way to create basic JSON template files for the gesture recognizer.
Thanks, Nicolò and Luca!
Speaking of coordinate systems, the following 3 part primer from the Wolfire Dev Team is an excellent refresher on linear algebra. I studied this in school, but having been out of the engineering game for a while I find my “bow staff skillz” are shamefully rusty.
Fortunately, Cocos2d takes care of a lot of this for you with their CGPoint Extensions. But, it’s still good to understand the basics.
Lately, I find myself spending more of my free time working on a little game using Cocos2d. One of the things I was surprised to discover is that there’s not just a single coordinate system — there are four (that I know of — please correct me if I’m wrong).
The four I know of:
Core Graphics spaceOpen GL spaceNode spaceNode space relative to anchor pointI wasn’t totally clear on these going in, and I regret it. I ended up writing a lot of code that mish-mashed these and had to refactor it all.
Most likely you’re going to be processing a touch input on an iOS device and translating that to a coordinate system inside of a Cocos2d node (most likely a CCLayer) as such:
UITouch *touch = [touches anyObject];
CGPoint point = [touch locationInView: [touch view]];
CGPoint glPoint = [[CCDirector sharedDirector] convertToGL:point];
CGPoint nodePoint = [self convertTouchToNodeSpace:touch];
CGPoint nodePointAR = [self convertTouchToNodeSpaceAR:touch];
With that in mind, here’s how I understand them:
Core Graphics (point) — This is what you normally work in if you’re accustomed to iOS development with UIKit and similar APIs. CGPoint(0, 0) is in the top left corner of the screen and ascending Y values go down towards the bottom of the screen.
Open GL (glPoint) — This coordinate system has (0, 0) in the bottom left of the screen, and ascending Y values go up towards the top of the screen.
Node space (nodePoint) — This space is relative to the origin of the reference node with which you are observing the point, and follows the same rules as the Open GL system. If your node is full-screen and unshifted (e.g. a default CCLayer), this coordinate system is exactly the same as the Open GL system.
Node space relative to anchor point (nodePointAR) — In Cocos2d, the default anchor point of any node is its center point. This coordinate system is relative to that center point. If you redefine the anchor point, this system is adjusted.
The big gotcha that I ran into was that I was doing something frowned upon in Cocos2d: shifting Layers! I was then using the Node space throughout my code but expecting points to resolve to Open GL space. So, word to wise: understand these coordinate systems going in, and don’t shift the position of your Layers!
A small update to New Relic Menu Bars has been approved and is live on the app store. Update away!
What’s new? There were some requests for an icon-only option, so to accommodate that there’s now a “metric’ selector” (see below). Want just the icon? Deselect all the metrics, and bam you’ve got an icon-only New Relic menu bar.
Oh, and I’ve also added an option to start the menu bar on startup. It defaults to off.
Also, clicking on the menu bar item will display your metrics in the menu now regardless of which you have displayed in the bar.
Enjoy! Click here to get New Relic Menu Bars through the App Store.
The top navigation bar now floats and remains visible as users . The poke is a relic of the earliest versions of Facebook.
What about adding server monitoring options such as CPU usage? That would be a major help to many server admins.
I’ve had a few inquiries about the score that’s passed to the glyph detection delegate via
-(void)glyphDetected:(WTMGlyph *)glyph withScore:(float)score
in the MultistrokeGestureRecognizer iOS library.
Here are a few key points about the score and the recognizer in general:
Lulubysg, and 
Ed, and 
detectGlyph will always return a match!As an example, if your only template glyph is a circle and the user draws a squiggly line, a call to detectGlyph will still return a match to your only template. The score will most likely be very low since the two gestures don’t resemble each other. Ultimately, it’s up to you and your application to determine what is a good match and whether to accept the input as a match or not.
Behind the scenes, the N Dollar Recognizer is assigning a score to every template, but only the highest score is returned to the delegate.
So, there’s no magical threshold in the score that determines a match. You’ll have to seed your templates and then do some testing, and your particular implementation will have to define score thresholds.
Great content.Its really helpful.Keep sharing on..
Great content.Its really helpful.Keep sharing on..
Well, it took a little longer than I had hoped, but I finally got around to implementing the N-Dollar Gesture Recognizer in Objective-C for iOS. If you remember, this all started with a need for an iOS implemenation of a good multi-stroke gesture (I call them glyphs) recognizer. N-Dollar was the clear winner in my research, so without further ado I present my attempt at implementing it.
Grab the source here…
To summarize how to use this library in a few bullet points:
Initializing the detector is a simple affair:
It’s important to note that the detector is pretty useless unless you seed it with some templates to match against. Here I add a template of a gesture with [glyphDetector addGlyphFromJSON:].
The JSON representation of these gestures are simply arrays of X,Y coordinate points. For instance, here’s a JSON array-of-points of a gesture that resembles the letter ‘D’. You can choose to use multiple strokes, or a single stroke with all of the points combined. Honey badger The detector doesn’t care!
It’s really up to you how you want to capture the user input. The UIResponder Class is a good start, but I’m personally using Cocos2d, so the following code makes use of their abstraction of touch events:
Note that at each firing of the touch event handler, I take the corresponding point and add it to the recognizer through the [glyphDetector addPoint:] message.
Once you’re satisfied with the user input, you can call [glyphDetector detectGlyph]. This will use the N-Dollar/Protractor algorithm to compare the user input with the templates you defined. For each template, the detector determines a score — higher is better. It’ll return the pre-defined gesture with the highest score to its delegate and from there it’s up to you whether to trust the match, or wait for more user input!
Update: Here’s more info on interpreting the score that’s returned.
Don’t expect it any time soon, but I hope to put together an example app that demonstrates this library in its entirety. Please feel free to contact me at brit (at) this domain with any questions, or just shoot me a message on the GitHub repo!
hjkhjgkhk
Hi,
Great work, and thanks for the tutorial!!
Any chance to get an iphone app implementing this library?
Thanks
Thanks! I’ve got an app in the works but it’s slow going. I hope to have it done soon, and I’ll definitely make a post about it.
Woww, great news !
I hope this application will be open source…
Thanks for your work !!
Hi, I’m so happy I found your site. I looked at N$ about a year ago but couldn’t find an objective c implementation. One question, whats the best way to create these JSON template files? Specifically I plan to be creating template files for characters “a, b, c, etc…”
Thanks again!
@ Schiesty Have you find a way to create the JSON template files?
Woww, great news !
Hi! Thank you for your work. I’m trying to use the WTMGlyphDetector in my own cocos2d Project and I’m experiencing some difficulties. I don’t know how to correctly import your library in my project. I’ve added the .xcodeproj file to my project and added WTMGlyph library in target dependencies of my project and then added to it the header search path for WTMGlyph files. When I import “WTMGlyphDetector.h” and when I set a property for my class variable WTMGlyphDetector all works fine. But when I write glyphDetector = [WTMGlyphDetector detector] as you suggest in the init method xcode returns a linker error: “Undefined symbols for architecture i386:
“_OBJC_CLASS_$_WTMGlyphDetector”, referenced from:”.
Can you explain me what I’m doing wrong? Thank you.
i was forgetting to link in the project setting the framework libWTM.a.
Now all is working.
Looks like an old comment but…
I print the touch location to the debug console whenever the touch begins, moves and ends. Then I manually copy/paste it to a text editor…
When touch begins:
printf(“[ [%d,%d]“,(int)(touchLocation.x), ((int) touchLocation.y));
When touch moves:
printf(“,[%d,%d]“,(int)(touchLocation.x), ((int)touchLocation.y));
When touch ends:
printf(“,[%d,%d] ],n”,(int)(touchlocation.x), ((int)touchlocation.y));
(as you see this is c++, but you get the idea)
hi thank u for the implementation file,so please send me with example app its very useful for all..
Shouldn’t the line : [self addGlyphFromJSON:jsonData name:@"D"];
really be [glyphDetector addGlyphFromJSON:jsonData name:@"D"];
CCLayer doesn’t implement addGlyphFromJSON:
My glyphDetector is return the same score for all possible glyphs (0.00000000) Therefore it selects the same glyph (the first one loaded) everytime regardless of what I draw on the screen. Any ideas ?
This was because the json files weren’t getting loaded.
How exactly did you fix this?
I am having the same issue and can’t figure out what the problem is.
I’m loading up the whole alphabet via json files and it takes almost 20 seconds !! I’m looking for a way to speed up this process. Object serialization, static json data in my code ? thanks.
Hello. It’s a great tutorial. I am a beginner. I have got the project itself to run. But where is the library that I can import? Is it there, or do I have to build it from the project? Thanks in advance
Hi! can u please share the json files for all the other letters..
Given that touch-based input has become a staple of mobile devices, I was surprised to find a dearth of good, open source complex gesture recognition libraries in the wild.
Well, maybe I should explain what I’m referring to when I say, “complex gesture.” I’m not talking about the swipes and pinches that dominate our current interactions with touch devices. I’m more interested in what I like to call “glyphs” – a series of strokes that form a symbol.
A good example of what I consider a glyph is something like a letter in the alphabet. A ‘Q’ glyph is the circle stroke and the southeast stroke positioned in such a way that it’s recognizable. But, OCR is not quite what I’m looking for because it’s specific to text. The ideal solution should also recognize abstract glyphs — symbols that aren’t hard coded into a lookup dictionary.
Like all foolhardy, naive developers, I initially tried to just wing it. Research shmeshmearch. This would be easy — just take user input, break it down into individual strokes and then compare the input to a template for a glyph.
Here are the primary challenges I ran in to while trying to implement this approach:
Just some of the stroke combinations to create a ‘Q’
I spent a few hours hacking away at different solutions to these problems, but ultimately decided this sub-stroke comparison approach wasn’t going to cut it.
I found two projects that attempt to approach recognition the same way I had — sub-stroke combinations:
Ultimately, like my approach they were too limiting and didn’t address key issues. Both allowed for abstract gestures, but in testing they didn’t allow for the variance you’d find in real-world user input scenarios.
Then, I stumbled on the 1-Dollar Recognizer. Its unique way of comparing input to a pre-defined template (more on this later) made it very good at error correcting, and it’s order/direction agnostic. But, unfortunately it’s also uni-stroke only. The user would have to make one continuous stroke to ensure recognition. Close, but not quite there.
Fortunately, the same group who developed 1-Dollar extended it to include multi-stroke detection and called it the N-Dollar Recognizer1.
Multistroke? Check. Order and direction agnostic? Check. Error tolerant? Check. Fast and easy to implement? Check. High pun potential? Check. Well, N Dollar certainly has the biggest bang for the buck, but can it put its money where its mouth is?
If you’re interested in the specifics, I recommend reading the N Dollar research paper. I’ll keep it high-level here.
N Dollar, and its predecessor 1 Dollar, both use the nearest neighbor approach to recognition. It compares user input to each of a set of pre-defined templates and gives each a score. The highest score wins if it is within a certain margin of error. This allows sub-strokes in a glyph to be sloppy, as long as the overall glyph is closest to the intended template.
N Dollar creates a vector from all of the input points and interpolates additional points if necessary. Since sub-strokes are not as important in its algorithm, the final glyph just has to be closest to the intended template regardless of the number of data points.
N Dollar doesn’t care how many strokes the user inputs to create a glyph. Before comparing against templates, all sub-strokes are connected into a uni-stroke. The illustration to the right (from the N Dollar limitations page) shows that although the user input two horizontal lines, N Dollar connected them before it ran its matching algorithm. This turns out to be one of N Dollar’s biggest limitations, but also the key to its speed and multi-stroke support. In my testing, this drawback was outweighed by N Dollar’s other factors.
N Dollar calculates all the permutations of the generated uni-stroke before matching. The illustration below (taken from the research paper) shows how a user-drawn X gets defined 8 different ways regardless of the original input order. The comparison between the input and template is actually direction dependent, but N Dollar overcomes this by including all the possible directions in its calculation.
There’s a lot more to N Dollar than what I describe above, and its authors are nothing short of brilliant. Playing with the javascript implementation, I’m amazed at how quickly and accurately it’s able to calculate and compare even the most complex glyphs I throw at it.
Implementation is the other half. That’s how that goes, right? I’ve started a basic iOS implementation here (the original is in javascript), and once I finish I’ll put together a summary in part 2 of this series. Stay tuned!
Update: I’ve finished the implementation here. Read about it here
———-
1 Anthony, L. and Wobbrock, J.O. (2010). A lightweight multistroke recognizer for user interface prototypes. Proceedings of Graphics Interface (GI ’10). Ottawa, Ontario (May 31-June 2, 2010). Toronto, Ontario: Canadian Information Processing Society, pp. 245-252.
What a GREAT post! I think I am going to try and incorporate this into my password gesture framework.
I would like to try this.Thanks for sharing this post..
I would like to try this.Thanks for sharing this post..
I would like to try this.Thanks for sharing this post..
Brilliant. I thank you for your hard work, and for documenting it, wich is another very important step.
I’ll put the library to good use for my games, thank you 
Srideep202, 
Rma, 
Tavis Gustafson and 10 others are discussing. 
Loïc Prieto, 
Web design London 7:42 pm on December 29, 2011 Permalink
Cocos2D has an inverted coordinate system to what you’re used to – the … Now before we can see this running, we first need to tell Cocos2D to run our …..the entire game scene, more information is available in this thread.
Lulubysg 9:05 am on March 1, 2012 Permalink
Many thanks regarding an additional helpful site.
Anonymous 9:06 am on March 1, 2012 Permalink
Its like you examine my thoughts! You appear to understand so a lot about this, like you wrote the book in it or anything.