Gesture Recognition On Computing Device Correlating Input to a Template

• US 20130114901A1
• Filed: 12/18/2012
• Published: 05/09/2013
• Est. Priority Date: 09/16/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Li, Yang
• Granted Patent: US 9,805,241 B2
• Time in Patent Office: Days
• US Class Current: 382/189
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 10/242 by image rotation, e.g. by 90 degrees
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A computer-implemented user interface method and apparatus are disclosed. A user input signal corresponding to a drawn gesture is received and sampled. If the input signal is orientation invariant, the sampled, spaced points are rotated in accordance with an indicative angle to generate an input vector. If the input signal is orientation sensitive, the sampled, spaced points are rotated to align with a base orientation to generate the input vector. The gesture is recognized based on a comparison of the input vector to a plurality of templates.

Claims

1. A method, comprising:

receiving, at a processor, an input signal that corresponds to a gesture drawn by a user at a touchscreen of a computing device;

sampling the input signal as spaced points within a coordinate space, the spaced points being of a defined number;

if a designation of the input signal is orientation invariant, rotating the spaced points around a point of the coordinate space in accordance with an indicative angle of the spaced points to generate an input vector;

if the designation of the input signal is orientation sensitive, rotating the spaced points to align the spaced points with one of multiple base orientations in the coordinate space to generate the input vector; and

recognizing the gesture based on a comparison of the input vector to a plurality of templates.

2. The method of claim 1 wherein recognizing the gesture comprises:

for each stored template of the plurality of templates;

calculating a rotation angle for the stored template that minimizes an angular distance between the input vector and an initial vector of the stored template;

rotating the stored template in accordance with the rotation angle to generate a template vector; and

calculating a similarity score from the input vector and the template vector;

wherein a top choice for recognizing the gesture drawn by the user is a single stored template of the plurality of templates having a highest value for the similarity score.

3. The method of claim 2 wherein each stored template is generated by:

receiving a training sample input signal that corresponds to a template gesture;

sampling the training sample input signal as spaced points within the coordinate space, the spaced points being of the defined number;

if a designation of the template input signal is orientation invariant, rotating the spaced points around the point of the coordinate space in accordance with an indicative angle of the spaced points to generate an input vector;

if the designation of the template input signal is orientation sensitive, rotating the spaced points to align the spaced points with one of the multiple base orientations in the coordinate space to generate the input vector; and

storing the input vector as the initial vector of the stored template.

4. The method of claim 2 wherein the input vector comprises the defined number of two-dimensional coordinate pairs, each two-dimensional coordinate pair associated with a respective one of the spaced points.

5. The method of claim 3 wherein the similarity score comprises an inverse cosine distance between each two-dimensional coordinate pair of the input vector and a respective two-dimensional coordinate pair of the template vector.

6. The method of claim 2 wherein calculating the similarity score comprises executing an equation including an arc cosine function.

7. The method of claim 2 wherein rotating the template comprises rotating the template to result in a minimum angular distance with the input vector based on a solution to a single closed-form equation.

8. The method of claim 7 wherein the single closed-form equation is an arc tangent function.

9. The method of claim 1 wherein the indicative angle is an angle in a direction from the point to a first point of the spaced points.

10. The method of claim 1 wherein rotating the spaced points to align the spaced points with one of the multiple base orientations in the coordinate space comprises aligning the spaced points with the one of the multiple base orientations requiring a least rotation of the spaced points.

11. The method of claim 1 wherein the spaced points comprise a fixed number of equidistantly-spaced points.

12. The method of claim 1, further comprising:

translating the spaced points to place a centroid of the spaced points at an origin of the coordinate space before rotating the spaced points to generate the input vector, wherein rotating the spaced points around the point comprises rotating the spaced points around the centroid.

13. An apparatus, comprising:

a memory; and

a processor configured to execute instructions stored on the memory to;

receive an input signal that corresponds to a gesture drawn by a user at a touchscreen;

sample the input signal as spaced points within a coordinate system, the spaced points being of a defined number;

if a designation of the input signal is orientation invariant, rotate the spaced points around a point of the coordinate system in accordance with an indicative angle of the spaced points to generate an input vector;

if the designation of the input signal is orientation sensitive, rotate the spaced points to align the spaced points with one of multiple base orientations in the coordinate space to generate the input vector; and

recognize the gesture based on a comparison of the input vector to a plurality of templates.

14. The apparatus of claim 13, further comprising:

the touchscreen configured to present at least a portion of a graphical user interface.

15. The apparatus of claim 13 wherein the processor is configured to recognize the gesture by:

for each stored template of the plurality of templates;

calculating a rotation angle for the stored template that minimizes an angular distance between the input vector and an initial vector of the stored template;

rotating the stored template in accordance with the rotation angle to generate a template vector; and

calculating a similarity score from the input vector and the template vector;

wherein a top choice for recognizing the gesture drawn by the user is a single stored template of the plurality of templates having a highest value for the similarity score.

16. The apparatus of claim 15 wherein the processor is configured to calculate the rotation angle by executing an equation including an arc tangent function and a plurality of coordinate pairs forming the input vector and a corresponding plurality of coordinate pairs forming the initial vector of the stored template.

17. The apparatus of claim 15 wherein the processor is configured to calculate the similarity score by executing an equation including an arc cosine function and a plurality of coordinate pairs forming the input vector and a corresponding plurality of coordinate pairs forming the template vector.

18. The apparatus of claim 15 wherein the similarity score comprises an angle between the input vector and the template vector in N-dimensional space, and wherein N is the defined number.

19. The apparatus of claim 13 wherein the processor is configured to translate the spaced points to place a centroid of the spaced points at an origin of the coordinate space before generating the input vector, and to generate each stored template of the plurality of templates, when operating in a training mode, by:

receiving a training sample input signal that corresponds to a gesture drawn by the user at the touchscreen;

sampling the training sample input signal as spaced points being of the defined number;

translating the spaced points of the training sample input signal to place a centroid of the points at the origin of the coordinate space;

if a designation of the training sample input is orientation invariant, rotating the translated points around the centroid in accordance with an indicative angle of the translated points to generate a training sample input vector;

if the designation of the training sample input is orientation sensitive, rotating the translated points to align the translated points with one of the multiple base orientations in the coordinate space to generate the training sample input vector; and

storing the training sample input vector as an initial vector of a stored template.

20. The apparatus of claim 19 wherein the indicative angle is an angle in a direction from the centroid to a first point of the sampled training sample input;

and wherein the controller is configured to rotate the translated points to align with one of the multiple base orientations in the coordinate space by aligning the translated points with the one of the multiple base orientations requiring a least rotation of the translated points.