Motion pattern classification and gesture recognition

• US 9,110,510 B2
• Filed: 06/03/2011
• Issued: 08/18/2015
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Moore, Christopher, Tu, Xiaoyuan, Vieta, William Matthew
• Primary Examiner(s): Chang, Kent
• Assistant Examiner(s): ROSARIO, NELSON M
• Application Number:
  US13/153,374
• Publication Number:
  US 20120306745A1
• Time in Patent Office: 1,537 Days
• Field of Search: 345156-184, 178 1801- 1809, 178/18.11
• US Class Current: 1/1
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06V 40/28 Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113

Abstract

Methods, program products, and systems for gesture classification and recognition are disclosed. In general, in one aspect, a system can determine multiple motion patterns for a same user action (e.g., picking up a mobile device from a table) from empirical training data. The system can collect the training data from one or more mobile devices. The training data can include multiple series of motion sensor readings for a specified gesture. Each series of motion sensor readings can correspond to a particular way a user performs the gesture. Using clustering techniques, the system can extract one or more motion patterns from the training data. The system can send the motion patterns to mobile devices as prototypes for gesture recognition.

Claims

1. A method performed by one or more computers, comprising:

receiving a plurality of motion features, each of the motion features including a respective time series of motion vectors and a first label or a second label;

determining a respective distance between each pair of the motion features that includes a first motion feature having the first label and a second motion feature having the second label;

clustering the motion features into one or more motion clusters based on the distance and a quality threshold, the quality threshold being determined based at least in part on a smallest distance between a motion feature having the first label and a motion feature having the second label; and

representing each of the one or more motion clusters using a motion pattern for recognizing a gesture on a mobile device, the motion pattern including a time series of calculated motion vectors.

2. The method of claim 1, wherein each motion vector includes at least one of:

a linear acceleration value on each of a plurality of motion axes;

an angular rate value each of a plurality of motion axes;

magnetometer data;

or

proximity sensor data.

3. The method of claim 2, wherein receiving the motion features comprises:

receiving a time series of motion sensor readings from a mobile device; and

generating the time series of motion vectors of each motion feature from the motion sensor readings using a high-pass filter.

4. The method of claim 1, wherein determining the respective distance includes determining a distance between a time series of motion vectors in a first motion example in the pair and a time series of motion vectors in a second motion example in the pair using dynamic time warping.

5. The method of claim 1, wherein the first label is a positive label indicating that the motion feature is associated with a given gesture, and the second label is a negative label indicating that the motion feature is not associated with the given gesture.

6. The method of claim 5, wherein determining the quality threshold is based at least in part on

a positive multiplier.

7. The method of claim 5, comprising:

identifying an outlier from the motion patterns based on a number of motion features clustered in each of the motion clusters and the labels associated with the motion features; and

excluding the outlier from gesture recognition operations.

8. The method of claim 7, wherein identifying the outlier comprises:

identifying an outlier cluster from the one or more motion clusters, wherein;

the outlier cluster is associated with the first label;

a number of the motion features contained in the outlier cluster is less than an outlier threshold; and

a motion pattern representing a cluster that is closest to the outlier cluster is associated with the second label; and

designating the motion pattern representing the outlier cluster as the outlier.

9. The method of claim 1, wherein clustering the motion features into one or more motion clusters comprises:

identifying a first cluster of motion features, the motion features in the first cluster having a same label, wherein distances between pairs of the motion features in the first cluster satisfy the quality threshold;

removing the first cluster from the motion features; and

repeating the identifying and removing operations until a termination condition is satisfied.

10. The method of claim 1, comprising determining a sphere of influence of each motion pattern based on the motion patterns and the distances between the pairs of the motion features, wherein a motion is designated as matching the motion pattern when a distance between the motion and the motion pattern is within the sphere of influence.

11. The method of claim 10, wherein determining the sphere of influence includes determining the sphere of influence based at least in part on one of a classification radius or a density radius, wherein:

the classification radius is determined based on a distance from the motion pattern within which a threshold portion of motion features have a same label, and

the density radius is determined based on a distance from the motion pattern within which a variance of distances between motion features and the motion pattern satisfies a specified variance threshold.

12. The method of claim 1, comprising:

sending the motion pattern to a mobile device for recognizing a gesture of the mobile device.

13. A non-transitory storage device storing a computer program product configured to cause one or more computers to perform operations comprising:

receiving a plurality of motion features, each of the motion features including a respective time series of motion vectors and being associated with a first label or a second label;

determining a respective distance between each pair of the motion features that includes a first motion feature having the first label and a second motion feature having the second label;

clustering the motion features into one or more motion clusters based on the distance and a quality threshold, the quality threshold being determined based at least in part on a smallest distance between a motion feature having the first label and a motion feature having the second label; and

representing each of the one or more motion clusters using a motion pattern for recognizing a gesture on a mobile device, the motion pattern including a time series of calculated motion vectors.

14. The non-transitory storage device of claim 13, wherein each motion vector includes at least one of:

a linear acceleration value on each of a plurality of motion axes;

an angular rate value each of a plurality of motion axes;

magnetometer data;

or

proximity sensor data.

15. The non-transitory storage device of claim 14, wherein receiving the motion features comprises:

receiving a time series of motion sensor readings from a mobile device; and

generating the time series of motion vectors of each motion feature from the motion sensor readings using a high-pass filter.

16. The non-transitory storage device of claim 13, wherein determining the respective distance includes determining a distance between a time series of motion vectors in a first motion example in the pair and a time series of motion vectors in a second motion example in the pair using dynamic time warping.

17. The non-transitory storage device of claim 13, wherein the first label is a positive label indicating that the motion feature is associated with a given gesture, and the second label is a negative label indicating that the motion feature is not associated with the given gesture.

18. The non-transitory storage device of claim 17, wherein determining the quality threshold is based at least in part on

a positive multiplier.

19. The non-transitory storage device of claim 17, the operations comprising:

identifying an outlier from the motion patterns based on a number of motion features clustered in each of the motion clusters and the labels associated with the motion features; and

excluding the outlier from gesture recognition operations.

20. The non-transitory storage device of claim 19, wherein identifying the outlier comprises:

identifying an outlier cluster from the one or more motion clusters, wherein;

the outlier cluster is associated with the first label;

a number of the motion features contained in the outlier cluster is less than an outlier threshold; and

a motion pattern representing a cluster that is closest to the outlier cluster is associated with the second label; and

designating the motion pattern representing the outlier cluster as the outlier.

21. The non-transitory storage device of claim 13, wherein clustering the motion features into one or more motion clusters comprises:

identifying a first cluster of motion features, the motion features in the first cluster having a same label, wherein distances between pairs of the motion features in the first cluster satisfy the quality threshold;

removing the first cluster from the motion features; and

repeating the identifying and removing operations until a termination condition is satisfied.

22. The non-transitory storage device of claim 13, the operations comprising determining a sphere of influence of each motion pattern based on the motion patterns and the distances between the pairs of the motion features, wherein a motion is designated as matching the motion pattern when a distance between the motion and the motion pattern is within the sphere of influence.

23. The non-transitory storage device of claim 22, wherein determining the sphere of influence includes determining the sphere of influence based at least in part on one of a classification radius or a density radius, wherein:

the classification radius is determined based on a distance from the motion pattern within which a threshold portion of motion features have a same label, and

the density radius is determined based on a distance from the motion pattern within which a variance of distances between motion features and the motion pattern satisfies a specified variance threshold.

24. The non-transitory storage device of claim 13, the operations comprising:

sending the motion pattern to a mobile device for recognizing a gesture of the mobile device.

25. A system, comprising:

one or more computers;

a non-transitory storage device storing instructions configured cause the one or more computers to perform operations comprising;

receiving a plurality of motion features, each of the motion features including a respective time series of motion vectors and a first label or a second label;

determining a respective distance between each pair of the motion features that includes a first motion feature having the first label and a second motion feature having the second label;

clustering the motion features into one or more motion clusters based on the distance and a quality threshold, the quality threshold being determined based at least in part on a smallest distance between a motion feature having the first label and a motion feature having the second label; and

representing each of the one or more motion clusters using a motion pattern for recognizing a gesture on a mobile device, the motion pattern including a time series of calculated motion vectors.

26. The system of claim 25, wherein each motion vector includes at least one of:

a linear acceleration value on each of a plurality of motion axes;

an angular rate value each of a plurality of motion axes;

magnetometer data;

or

proximity sensor data.

27. The system of claim 26, wherein receiving the motion features comprises:

receiving a time series of motion sensor readings from a mobile device; and

generating the time series of motion vectors of each motion feature from the motion sensor readings using a high-pass filter.

28. The system of claim 25, wherein determining the respective distance includes determining a distance between a time series of motion vectors in a first motion example in the pair and a time series of motion vectors in a second motion example in the pair using dynamic time warping.

29. The system of claim 25, wherein the first label is a positive label indicating that the motion feature is associated with a given gesture, and the second label is a negative label indicating that the motion feature is not associated with the given gesture.

30. The system of claim 29, wherein determining the quality threshold is based at least in part on

a positive multiplier.

31. The system of claim 29, the operations comprising:

identifying an outlier from the motion patterns based on a number of motion features clustered in each of the motion clusters and the labels associated with the motion features; and

excluding the outlier from gesture recognition operations.

32. The system of claim 31, wherein identifying the outlier comprises:

identifying an outlier cluster from the one or more motion clusters, wherein;

the outlier cluster is associated with the first label;

a number of the motion features contained in the outlier cluster is less than an outlier threshold; and

a motion pattern representing a cluster that is closest to the outlier cluster is associated with the second label; and

designating the motion pattern representing the outlier cluster as the outlier.

33. The system of claim 25, wherein clustering the motion features into one or more motion clusters comprises:

identifying a first cluster of motion features, the motion features in the first cluster having a same label, wherein distances between pairs of the motion features in the first cluster satisfy the quality threshold;

removing the first cluster from the motion features; and

repeating the identifying and removing operations until a termination condition is satisfied.

34. The system of claim 25, the operations comprising determining a sphere of influence of each motion pattern based on the motion patterns and the distances between the pairs of the motion features, wherein a motion is designated as matching the motion pattern when a distance between the motion and the motion pattern is within the sphere of influence.

35. The system of claim 34, wherein determining the sphere of influence includes determining the sphere of influence based at least in part on one of a classification radius or a density radius, wherein:

the classification radius is determined based on a distance from the motion pattern within which a threshold portion of motion features have a same label, and

the density radius is determined based on a distance from the motion pattern within which a variance of distances between motion features and the motion pattern satisfies a specified variance threshold.

36. The system of claim 25, the operations comprising:

sending the motion pattern to a mobile device for recognizing a gesture of the mobile device.