Gesture recognition on computing device correlating input to a template

• US 9,805,241 B2
• Filed: 12/18/2012
• Issued: 10/31/2017
• Est. Priority Date: 09/16/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Yang
• Primary Examiner(s): CHOW, DOON Y
• Assistant Examiner(s): Nicholas, Wendy
• Application Number:
  US13/717,839
• Publication Number:
  US 20130114901A1
• Time in Patent Office: 1,778 Days
• Field of Search: 345156, 382187, 382189, 382186, 715863, 715864, 715739, 715839
• 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:

outputting, for display on a touchscreen of a computing device, an arrangement of a plurality of items;

receiving, at a processor of the computing device, a first indication of a first input entered by a user at the touchscreen of the computing device, the first input comprising a first glyph of a first at least one character or symbol;

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

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

recognizing the first at least one character or symbol based on a comparison of the first input vector to at least one of a plurality of templates;

outputting, for display on the touchscreen of the computing device, one or more first items from the arrangement of the plurality of items in a location in the arrangement that corresponds to the recognized first at least one character or symbol;

receiving, at the processor of the computing device, a second indication of a second input entered by the user at the touchscreen of the computing device, the second input comprising a second glyph of a second at least one character or symbol;

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

responsive to a designation of the second input signal being orientation sensitive, determining a level of orientation sensitivity and rotating, based on the determined level of orientation sensitivity, the second spaced points to align the second spaced points with one of multiple base orientations in the coordinate space to generate a second input vector;

recognizing the second at least one character or symbol based on a comparison of the second input vector to at least one of the plurality of templates; and

wherein a user previously designated at least one of the recognized first at least one character or symbol as corresponding to the one or more first items from the arrangement that are output or the recognized second at least one character or symbol as corresponding to the one or more second items from the arrangement that are output.

2. The method of claim 1 wherein recognizing the first at least one character or symbol 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 first 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 first input vector and the template vector;

wherein a top choice for recognizing the first at least one character or symbol 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

a first stored template of the plurality of stored templates is generated by:

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

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

responsive to a designation of the first template input signal being orientation invariant, rotating the third spaced points around the point of the coordinate space in accordance with an indicative angle of the third spaced points to generate a third input vector; and

storing the third input vector as an initial vector of the first stored template, and

a second stored template of the plurality of stored templates is generated by;

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

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

responsive to a designation of the second template input signal being orientation sensitive, rotating the fourth spaced points to align the fourth spaced points with one of the multiple base orientations in the coordinate space to generate a fourth input vector; and

storing the fourth input vector as an initial vector of the second stored template.

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

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

6. The method of claim 1, wherein the level of orientation sensitivity identifies a number of base orientations in the coordinate space to which the second spaced points are aligned.

7. The method of claim 1 further comprising determining, based on at least one of a current user-interface context and a current gesture template being compared, that the designation of the first input signal is orientation invariant and the designation of the second input signal is orientation sensitive.

8. The method of claim 1 further comprising determining that the first input represents an intent of the user to enter the first glyph.

9. The method of claim 8, wherein the determining that the first input represents an intent of the user to enter the first glyph comprises:

identifying a bounding box around a portion of the first input; and

determining that the first input represents an intent of the user to enter the first glyph based on an aspect ratio of the bounding box.

10. The method of claim 8, wherein the determining that the first input represents an intent of the user to enter the first glyph comprises:

determining a speed of dragging motion of the first input; and

determining that the first input represents an intent of the user to enter the first glyph based on the speed of the dragging motion.

11. The method of claim 8, wherein the determining that the first input represents an intent of the user to enter the first glyph comprises:

determining a pressure level of the first input; and

determining that the first input represents an intent of the user to enter the first glyph based on the pressure level.

12. An apparatus, comprising:

a memory; and

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

output, for display on a touchscreen, an arrangement of a plurality of items;

receive a first indication of a first input entered by a user at the touchscreen, the first input comprising a first glyph of a first at least one character or symbol;

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

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

recognize the first at least one character or symbol based on a comparison of the first input vector to at least one of a plurality of templates; and

output, for display on the touchscreen, one or more first items from the arrangement of the plurality of items in a location in the arrangement that corresponds to the recognized first at least one character or symbol, receive a second indication of a second input entered by the user at the touchscreen, the second input comprising a second glyph of a second at least one character or symbol;

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

responsive to a designation of the second input signal being orientation sensitive, determine a level or orientation sensitivity and rotate, based on the determined level of orientation sensitivity, the second spaced points to align the second spaced points with one of multiple base orientations in the coordinate system to generate a second input vector;

recognize the second at least one character or symbol based on a comparison of the second input vector to at least one of the plurality of templates; and

output, for display on the touchscreen, one or more second items from the arrangement of the plurality of items in a location in the arrangement that corresponds to the recognized second at least one character or symbol,

wherein a user previously designated at least one of the recognized first at least one character or symbol as corresponding to the one or more first items from the arrangement that are output or the recognized second at least one character or symbol as corresponding to the one or more second items from the arrangement that are output.

13. The apparatus of claim 12 wherein the processor is configured to recognize the at least one first character or symbol 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 first 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 first input vector and the template vector;

wherein a top choice for recognizing the first at least one character or symbol is a single stored template of the plurality of templates having a highest value for the similarity score.

14. The apparatus of claim 13 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 first input vector and a corresponding plurality of coordinate pairs forming the initial vector of the stored template.

15. The apparatus of claim 13 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 first input vector and a corresponding plurality of coordinate pairs forming the template vector.

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

17. The apparatus of claim 12 wherein the processor is configured to:

translate the first spaced points to place a centroid of the first spaced points at an origin of the coordinate system before generating the first input vector;

generate a first stored template of the plurality of templates, when operating in a training mode, by;

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

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

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

responsive to a designation of the first training sample input being orientation invariant, rotating the translated third spaced points around the centroid in accordance with an indicative angle of the translated third spaced points to generate a first training sample input vector;

storing the first training sample input vector as an initial vector of the first stored template; and

generate a second stored template of the plurality of templates, when operating in the training mode, by;

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

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

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

responsive to a designation of the second training sample input being orientation sensitive, rotating the translated fourth spaced points to align the translated fourth spaced points with one of the multiple base orientations in the coordinate system to generate a second training sample input vector; and

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