The $1 algorithm is a "cheap trick" to achieve single-stroke gesture recognition in almost any setting. The code is simple enough to write in any language and run on any platform. After all, that was the whole point of the algorithm. Even though it was originally intended for interface prototyping, there have been many applications built using the $1 as the core recognition engine.
$1 is a template matching algorithm. It performs the same pre-processing on training and testing examples:
- Resample the stroke to have PPS points
- Calculate the centroid and the indicative angle (angle from centroid to 1st point)
- Standardize: translate centroid to (0,0), scale to standard bounding box, rotate indicative angle to 0
I really like $1 as a platform to build cool stuff with. People have used it for games. I used it to build an almost-as-simple free sketch recognizer. Its simplicity makes it really easy to customize to your exact needs.
For some reason, it's taken me until now to wonder, what about k-NN instead of 1-NN. I wonder if there's any benefit to that. I would guess you'd need more than the 1-2 examples per class featured on the website version for it to be effective.
The $1 emphasizes itself on simplicity. That is probably the reason why it uses 1-NN instead of k-NN. k-NN would require more complexity in the algorithm; if I were to use k-NN in the $1, I would would to increase the overall recognition capabilities (that would include removing the pre-processing standardization like rescaling) and thus turn the $1 into the $10, or even $100.
ReplyDeleteI've a stupid question, could you guys remind me what are K-NN and 1-NN?
ReplyDelete