Abstract:
A user performs a gesture with a hand-held or wearable device capable of sensing its own orientation. Orientation data, in the form of a sequence of rotation vectors, is collected throughout the duration of the gesture. To construct a trace representing the shape of the gesture and the direction of device motion, the orientation data is processed by a robotic chain model with four or fewer degrees of freedom, simulating a set of joints moved by the user to perform the gesture (e.g., a shoulder and an elbow). To classify the gesture, a trace is compared to contents of a training database including many different users&#39; versions of the gesture and analyzed by a learning module such as support vector machine.

Description:
RELATED APPLICATIONS 
       [0001]    None 
       FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT 
       [0002]    None 
       APPENDICES 
       [0003]    None 
       FIELD 
       [0004]    Related fields include smart-system inputs using wearable or handheld devices (W/HHD), and more particularly the tracing and recognition of gestures made with a W/HHD. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0005]      FIG. 1  is a conceptual illustration of a simple gesture being made with a hand-held device. 
           [0006]      FIGS. 2A-C  are charts and illustrations of one method of synthesizing orientation data from the measurements of other sensors. 
           [0007]      FIGS. 3A-D  are example diagrams of 3D orientation data and transformation into 2D data. 
           [0008]      FIGS. 4A-C  illustrate the use of a robotic chain model for joints of the user&#39;s arm, both to transform angles into positions for the trace and to remove the sensitivity to user motion with respect to the world. 
           [0009]      FIGS. 5A-E  illustrate the limits on wrist and hand movement when the shoulder and the elbow supply the permitted 4 degrees of freedom. 
           [0010]      FIG. 6  is a flowchart of an example process for tracing and classifying (i.e. recognizing) the trajectory of a W/HHD during a gesture. 
           [0011]      FIGS. 7A-B  demonstrates transformation of a 3-D trace to a 2-D trace by PCA. 
           [0012]      FIGS. 8A-B  demonstrate the effects of sub-sampling and curve fitting. 
           [0013]      FIG. 9  is a flowchart of command execution by the classified gesture. 
       
    
    
     DETAILED DESCRIPTION 
       [0014]    Gesturing with a wearable or handheld device is an alternative to tapping keyboard keys, speaking into a speech-recognition microphone, or tapping, swiping, or drawing on a touchscreen. The gesturing approach offers several potential advantages. Compared to touch screens and miniaturized keyboards, gesturing is insensitive to hand size, fine dexterity, visual acuity, or the wearing of gloves. Compared to spoken input, gesturing can be more private for the user and less obtrusive to people nearby because it need not make a sound. Gesturing is also agnostic to the user&#39;s language, accent, vocal timbre, and other individual speech factors. 
         [0015]    W/HHDs include smart phones, tablets, remote controls, smart pens and pointers, and wearable devices for movable parts of the body such as the arms, legs, hands, feet, or head. Wearable devices for the arms, often well-suited for gesture communication, include, without limitation, bracelets and smart watches. With the advent of smart appliances, cooking or eating utensils and cleaning implements may also be fashioned as W/HHDs. 
         [0016]    Desirable qualities in a W/HHD gesturing interface may include the following:
       Recognition of a large gesture vocabulary, including gestures that are sufficiently complex to be meaningful to users (letters, numbers, symbols and the like). Ideally, a standard library of gestures will develop to perform analogous functions in multiple applications (similar to standard libraries of graphic icons such as those widely understood to mean “add,” “delete,” “cut,” “paste,” and other tasks common to multiple applications running on an operating system).   Trajectory estimation capability for trace reconstruction.   Gesture reconstruction capability, providing feedback for the user on what gesture he or she actually made and/or providing a record for diagnostics by IT support professionals.   The processing algorithm preferably avoids double integration and other operations that tend to compound errors, while not overtaxing the computing power of today&#39;s small devices. Gesture analysis using accelerometers alone typically requires double integration.   Linear movement of the user&#39;s entire body, such as walking or riding, should not affect the accuracy of the gesture recognition.       
 
         [0022]    The following description and the accompanying drawings describe embodiments of gesture recognition systems that sense the changes in orientation of the W/HHD as the user makes the gesture, then use anthropomorphic kinematics to estimate the gesture trajectory. The system tolerates mild deviations from ideal gesture trajectories, making the gestures easier to learn and use, as long as the general shape and readability is sufficient to identify an unambiguous closest match in the store database of input gestures. The system generates a parametric trace of each gesture the user makes. Besides providing visual feedback for the user and diagnostic data for user support, the traces can be added to a database to educate the recognition model. 
         [0023]      FIG. 1  is a conceptual illustration of a simple gesture being made with a hand-held device. The device  102  is held in the user&#39;s hand  104  of and swept through a simple arc from left to right. 
         [0024]    Initially, hand  104  holds device  102  at angle  110   a . Optionally, dot  113  appears on the screen of device  102  to acknowledge that the system is ready to receive a gesture. Any other visible, audible, or haptic acknowledgment may be used. Hand  104  then sweeps device  102  in arc  106  so that a reference point on the device moves from position  108   a  to position  108   b . At the end of the gesture, hand  104  holds device  102  at angle  110   b . Trace  112  appears on the screen of device  102 , showing the shape and direction of the gesture. If this is the end of the gesture, the user may communicate this to device  102 , for example by shaking device  102  or by pushing a button somewhere on device  102 . 
         [0025]    During the gesture, orientation sensors inside device  102  measured the progression of device orientation angles from  110   a  to  110   b . While some devices may be able to sense orientation directly, a wider range of devices (such as nearly all smartphones) measure orientation by analyzing the simultaneous signals from one or more other sensor types. Trace  112 , however, is preferably a reconstruction of the series of positions occupied by the device while traveling through arc  106 . As these positions are not directly sensed, the positions corresponding to the orientations will need to be calculated. 
         [0026]    Alternatively, device  102  may be a wearable device worn on the hand, wrist, or forearm while making the gesture. 
         [0027]      FIGS. 2A-C  are charts and illustrations of one method of synthesizing orientation data from the measurements of other sensors.  FIG. 2A  is a flowchart of an example process for synthesizing orientation data. The illustrated process is similar to that used in the current version of Android OS™. A measurement signal  202  from a gyroscope is combined with a contemporaneous measurement signal  204  from a magnetometer and a contemporaneous measurement signal  206  from one or more accelerometers. The signals are processed through an extended Kalman filter  208  to yield a series of rotation vectors  210 . Each rotation vector  210  corresponds to an orientation of the device. 
         [0028]      FIG. 2B  represents the coordinate system of the W/HHD with reference to the world  224 . Origin  222  is the position of the device, just above the earth&#39;s surface. The magnetometer finds the y w  axis (north) while the gyroscope finds the z w  axis (up). The x w  axis is orthogonal to both y w  and z w  (east, to form a right-handed system). 
         [0029]      FIG. 2C  represents the local coordinate system of the W/HHD. Here, origin  232  is shown at the center of device  234  and the x D -y D  plane coincides with the device midplane, but alternatively any other landmarks of the device may be used. The accelerometers sense when the device moves through space. Similar coordinate systems could be applied to a smart watch or bracelet on a user&#39;s forearm, or a smart ring on a user&#39;s hand. 
         [0030]    Reconstructing the series of device positions involved in the gesture, if only the world coordinate system of  FIG. 2B  and the device coordinate system of  FIG. 2C  are compared, would require the user to remain stationary with respect to the world while making the gesture. If the device coordinate system were to move with respect to the world coordinate system due to causes other than the user&#39;s performing the gesture (for example, the user is simultaneously walking or riding in a vehicle), errors would be introduced into the measurement and the trace would be distorted. 
         [0031]      FIGS. 3A-D  are example diagrams of 3D orientation data and transformation into 2D data.  FIG. 3A  defines the attributes of a point  304  in an x-y-z coordinate system  300  with origin  302  at (0,0,0). The position of point  304  is (x 1 ,y 1 ,z 1 ). A line  306  drawn from origin  302  to point  304  makes an angle α with the x-axis, and angle β with the y-axis, and an angle γ with the z-axis. To derive the position (x 1 ,y 1 ,z 1 ) from the angles (α,β,γ), the length of line  306 , √{square root over ((x 1   2 +y 1   2 +z 1   2 ))}, must also be known. 
         [0032]      FIG. 3B  represents the variation of α, β, and γ with time for an arc gesture similar to that in  FIG. 1 . This is the raw data collected by the device. Given enough other information, the data in the three graphs of  FIG. 3B  could be converted into the three-dimensional trace  342  in coordinate system  340  of  FIG. 3C  (preserving the direction  344  of the gesture). In some embodiments, reconstructing a three-dimensional trace could be advantageous (such as recording limb movements while practicing ballet or tai-chi). However, because people accustomed to writing and drawing in flat surfaces may be more comfortable with two-dimensional gestures, in some embodiments it may be more advantageous to further transform the three-dimensional trace  342  into the two-dimensional trace  362  in flattened coordinate system  360  (preserving the direction  364  of the gesture). 
         [0033]      FIGS. 4A-C  illustrate the use of a robotic chain model for joints of the user&#39;s arm, both to transform angles into positions for the trace and to remove the sensitivity to user motion with respect to the world.  FIG. 4A  shows the skeletal structure of the human arm and hand with part of the torso.  FIG. 4B  shows the articulations of a robotic arm. The robotic arm has a joint  412  that moves similarly to the human shoulder  402 ; a hinge joint  414  that move similarly to the human elbow  404 ; and an end-effector  416  that performs the desired task, similarly to the hand-held or wearable device  406  when the user performs a gesture. Calculation of the joint angles that position the end effector at a desired point in space, in a desired orientation, are known in the robotics field.  FIG. 4C  shows a framework for a robotic chain model of the human arm, not including the hand. For a 1:1 mapping, a robotic arm is limited to, at most, 4 degrees of freedom: for instance, one ball joint (3 degrees of freedom) and one hinge joint (1 degree of freedom). 
         [0034]    The human arm and hand would provide many more than 4 degrees of freedom if the ball joint of the shoulder, the compound joint of the wrist, and the hinge joints in the elbow, thumb, and fingers were to all participate in making the gesture. Therefore, to reconstruct the trace accurately, some of the joints must be held still while making the gesture. The shoulder and the elbow, or alternatively the elbow and the wrist, in combination provide 4 degrees of freedom. Performing a gesture with these joints in isolation will allow the movement to be accurately reproduced in the trace. 
         [0035]    Moreover, the model moves the frame of reference from “the world” to the user&#39;s body. For example, in a shoulder-elbow model, the user&#39;s shoulder becomes the origin of the coordinate system. In these coordinates, any linear motion of the user&#39;s entire body with respect to the world (e.g. walking or riding) does not affect the accuracy of the gesture trace and recognition. 
         [0036]      FIGS. 5A-E  illustrate the limits on wrist and hand movement when the shoulder and the elbow supply the permitted 4 degrees of freedom.  FIG. 5A  shows a straight wrist  501  that maintains its position with respect to the device plane  511  during the entire gesture. Experiments showed that users quickly became accustomed to this constraint so that holding the wrist and hand motionless at the end of the arm became natural and comfortable while using the gesture interface. 
         [0037]      FIGS. 5B ,  5 C and  5 D summarize “forbidden” wrist motions; the wrist should not bend forward  502  or backward  512  and the forearm should not twist  522 . To be clear, wrist bends and twists should not develop or change during a shoulder-elbow gesture. If the wrist is bent or twisted at the beginning of the gesture and maintains the same bend or twist until the end of the gesture, the accuracy of the trace will not be affected. However, the straight position of  FIG. 5A  is generally thought to place the least strain on the wrist. 
         [0038]      FIG. 5E  demonstrates another solution to the degrees-of-freedom challenge. If the device is a watch or bracelet  504  worn on the forearm  506 , its motion will be completely controlled by the shoulder and elbow automatically; wrist  508  and hand  510  are downstream of watch or bracelet  504  and thus cannot participate in its motion. 
         [0039]      FIG. 6  is a flowchart of an example process for tracing and classifying (i.e. recognizing) the trajectory of a W/HHD during a gesture. Throughout the gesture, rotation vector samples  610  are generated by the client device (the W/HHD), either by a software process analogous to that illustrated in  FIG. 2B , a direct measurement with a MEMS or other orientation sensor, or any other suitable means. The sampling rate may be very fast (e.g. 90 Hz) compared to the speed of the gesture, so it is not necessary to process every sample. The rest of the processing may optionally be done on a remote server after sending the rotation vectors from the client device (e.g. over WiFi). 
         [0040]    Either on the client device or on the server, the rotation vector data is sub-sampled (step  622 ). For example, the sub-sampling rate may be between 0.5 and 2 Hz. The sub-sampled data is then input to a robotic chain model with 4 degrees of freedom (shoulder-elbow or elbow-wrist; step  624 ). Even if some of the calculations  624  are done on the client device, the stored constraint parameters  674  may be pulled from a server. In some embodiments, calculations  624  include two passes through the joint hierarchy. First, a set of inverse-kinetic calculations derives the set of joint angles necessary to place the device at the measured orientation. Second, a set of forward-kinetic calculations applies the set of joint angles to estimated or measured lengths of the forearm and upper arm to derive the position of the device with respect to the shoulder (now the origin of the local coordinate system). Position results for the sub-samples are points along a 3-D gesture trace. 
         [0041]    While some embodiments may immediately quantize and scale (step  642 ) and display (step  612 ) the 3-D trace, some embodiments will apply a flattening algorithm such as Principal Component Analysis (PCA, step  632 , which projects the trace along the axis of least variance) to convert the 3-D trace to a 2-D trace. The 2-D trace is scaled and framed within a pixel frame of fixed dimensions (step  642 ), fit to a curve to produce a parametric trace with fewer points (step  644 ), and displayed to the user on the client device (step  612 ). In some embodiments, the data are fit to a Bezier curve. Some embodiments may solve for the minimum number of curve control points needed to reproduce the trace within a predetermined threshold accuracy. Alternatively, some embodiments may use a fixed number of control points for every trace. 
         [0042]    After this step, the entire trace may be reproducible from less than 20 points. Identifying features  660  of the best-fit curve are extracted and input to a gesture classification algorithm (step  662 ), preferably using a statistically robust model such as a support vector machine (SVM)  682  informed by a training database  692 . In some preferred embodiments, a large training data base  692  includes many variations on the gestures made by many different users, to provide statistics on the possible deviations from the ideal trace that nevertheless result in a classifiable trace (i.e. one that is more like one particular gesture in the command library than it is like any of the others). SVM  682  may include adaptive, artificially intelligent or “learning” modules. 
         [0043]      FIGS. 7A-B  demonstrates transformation of a 3-D trace to a 2-D trace by PCA. In  FIG. 7A , 3-D trace  702  shows the results of other robotic chain model after the inverse-kinetic and forward-kinetic calculations. This is expected to be a fairly realistic representation of the device&#39;s path through the air while the user was making the gesture. In  FIG. 7B , trace  702  is projected along the axis of least variance, producing 2-D trace  712 . 
         [0044]      FIGS. 8A-B  demonstrate the effects of sub-sampling and curve fitting.  FIG. 8A  illustrates how sub-sampling and curve-fitting, besides reducing the number of points to be processed by the SVM, may also cause different users&#39; variations on gestures to converge. For simplicity, all the stages are shown as 2-D traces, rather than going into and then coming out of orientation space as in  FIG. 7 . Input traces  802  and  822  are two different users&#39; rendering of the number “2” as a device gesture.  804  and  824  are the respective samples (the spaces between samples are exaggerated for visibility).  806  and  826  are the respective sub-samples.  808   a  and  828   a  are Bezier curve fits with “corner” control points and the number of control points minimized (to 5 in this case).  808   b  and  828   b  are Bezier curve fits with “smooth” control points and the number of control points predetermined and fixed (to 8 in this case).  810   a ,  810   b ,  830   a , and  830   b  are the resulting traces from the Bezier fit. These would be the traces submitted to the SVM for processing 
         [0045]    Note that the number and type of control points seems to have a second-order effect on the resulting trace, but in all cases the processed traces look much more alike than the input traces. The two quite different renderings of the number “2” by different users converge after processing to something like a backward “S.” The identifying features in this example are the large top and bottom curves, rather than the smaller-scale features that differed between the two input traces  802  and  812 . 
         [0046]      FIG. 8B  shows how a 10-point Bezier curve can closely replicate a complex gesture such as the treble clef Input trace  854  and Bezier fit  852  are virtually coincident except in the tightest loop. 
         [0047]      FIG. 9  is a flowchart of command execution by the classified gesture. Although some applications may produce a trace as an end product, some applications may use the trace as a command to trigger a particular action by the W/HHD or by another device and a wireless communication with a W/HHD. Just as some mobile applications display the same virtual keyboard for input, a number of applications may accept the same set of gestures. Other, more specialized applications may have their own idiosyncratic gesture vocabularies. Thus, some of these processes may take place in shared gesture software, and others may occur within the particular application in use. 
         [0048]    The described algorithms and processes may be implemented in software, in hardware logic, or in a combination of both. The hardware logic may reside on a dedicated chip or may be included as circuitry in a general-purpose chip. 
         [0049]    A classified gesture  910 , produced by the process of  FIG. 7  or a different process producing similar results, is compared to the stored examples of command gestures in a command database  914 . The most similar stored gesture is identified (step  912 ) and the corresponding command is executed (step  916 ). Ideally, the executed command is the command the user intended and the device only needs to wait for the next user input (step  922 ). If it is not, one option is for the user to try the gesture again from the beginning. Another option is for the user to notify the device of the error (step  918 ). In some embodiments, the error report and the unsuccessful trace may be sent to an administrator, to the authors of the application, or (step  928 ) to the training database. In some embodiments, the application responds by executing (or simply displaying) the command corresponding to the next-best-fit gesture (step  924 ). If this command is not correct either, the process may be iterated (step  926 ) repeating as necessary until the intended command is identified. 
         [0050]    The preceding Description and accompanying Drawings describe example embodiments in some detail to aid understanding. However, the scope of the claims may cover equivalents, permutations, and combinations that are not explicitly described herein.