Reading 32 : $P Recognizer

Citation:

Vatavu, Radu-Daniel, Lisa Anthony, and Jacob O. Wobbrock. "Gestures as point clouds: a $ P recognizer for user interface prototypes." Proceedings of the 14th ACM international conference on Multimodal interaction. ACM, 2012.

Publication Link 

 

Summary:

The $P algorithm is a gesture matching algorithm that follows in the family of $1 and $N algorithms. It is able to compare a candidate gesture with a predefined template, by treating the gestures as point clouds, while removing the timing information.  This ensures that the algorithm is invariant to multi-stroke data.

Discussion:

The key approach in the algorithm is to match each point in the candidate to some point in the template. This matching is done by using a matching function.  The goodness of the matching is defined using the follow equation:

 

The Hungarian algorithm is used to find the best matching, by treating this candidate-template point matching as an assignment problem. 

The authors feel that this algorithm cannot be classified a $ family algorithm as it is fairly complex and requires us to solve an optimization problem. Some of the heuristics adopted by the authors are: 

(1) Find all the Euclidean distances between points in C and T, and then sort thme, and choose the first n points that can yield a valid match.

(2) Use Greedy heuristics