Patent Description:
Known systems for multi-level control, e.g. volume control or screen/light brightness control in consumer electronics products, use circular touch-pads or capacitive linear sliders (frequently mounted above the keyboard in notebooks), or they are using the touch information from a generic notebook touchpad when the finger is moving in a dedicated slider area, for example, on the right border of the touchpad. These sensors provide absolute position information (possibly ambiguous position information as in the case of many circular touch pads) about the fingertip, and hence the finger tip's angle on the circular touchpad or the position on the slider - information that can be mapped directly or differentially to a control level in a straight forward way. In particular for the touch wheel it is important that the fingertip and the wheel's geometric center build an angle with a reference point on the wheel, and this angle can be evaluated.

US Patent Application Publication <CIT> discloses a method and device for determining rotation gestures. International Application <CIT> discloses an operation detection device.

When it comes to the recognition of circle gestures without fix reference position, determining an angle in the circle movement is no longer straight forward. This is the case, for example, for a generic non-circular touchpad, with two-dimensional/three dimensional (2D/3D) free-air gestures using near-field capacitive sensor systems, or with mid/far field sensor systems like video or infrared camera systems.

Considering a circle or circular movement, which can either be clockwise or counter-clockwise, and not limiting it to have a fix start or stop position, at each time during the circle movement, for real-time application one can only evaluate data acquired up to the presence, i.e. only partial gesture patterns. Without knowing the drawn circle's center, in the beginning of the movement the detection unit cannot tell the direction of the circle: For example, a left-right movement appears in the top of a clockwise circle but also in the bottom of a counter-clockwise circle. A circle gesture is to be understood in this disclosure to mean any type of circular movement. It does not require to have a constant radius but the radius and center point may vary over time as typical for any free movement of a hand or finger describing a circle without having a reference point or a prescribed path to follow.

There are several known methods to map a 2D circular movement onto one-dimensional (1D) data.

Circular Touch-Pad: A 1D capacitive slider <NUM>, as for example shown in <FIG>, comprises a plurality of linearly arranged sensor elements <NUM>, <NUM>. Such a sensor can also be arranged in a circle as shown with sensor <NUM> in <FIG>, in order to detect circular movement, certain MP3 music players use this technology.

Fix Center Position: Any point in 2D Cartesian coordinates can be bijectively mapped to a distance from a fixed reference position (center point) and the angle between a line through this point and the reference position and a reference direction vector, e.g. the direction of the positive x-axis, yielding the point in polar coordinates. Here, the named angle is the desired 1D data. Provided an input position pnew on a circle C and a fix center position pc of C, as shown in <FIG>, with x and y component of pnew being p(new,x) and p(new,y) , respectively, the angle α of pnew relative to the positive x-axis can be uniquely determined by computing the four quadrant inverse tangent function atan2 of vector connecting pnew and pc, i.e. α=atan2(p(new,y)-p(c,y) , p(new,x)-p(c,x)). Compared to the single-argument inverse tangent function whose output is periodic with π, atan2 additionally evaluates the signs of p(new,x)-p(c,x) and p(new,y)-p(c,y) and hence can map α to one of the four quadrants. Clearly, this method is not restricted to input positions on a circle, but can take any 2D position as input and will output an angle. Naturally, in addition to this absolute angle output, given two input position vectors pold and pnew, two output angles can be computed, their difference being a measure for the movement of the input position.

According to co-pending US patent application <CIT>, entitled "Continuous circle gesture detection for a sensor system", filed by Applicant, a method is proposed where angles (or approximations therefrom) between successive velocity vectors are accumulated over time, hence performing differential updates of an accumulator, where a velocity vector is defined as the difference between two position vectors being successive in time. This is illustrated in <FIG>. Depending on the rotating direction between an old and a new velocity vector (it is assumed that that amount of rotation is less than π/<NUM>), the 1D accumulator is either increased or decreased. The amount by which the accumulator is changed is the angle between the two velocity vectors or an approximation thereof. This approach is tolerant to translation and scaling, i.e. for example when the 2D input positions are acquired with a touch pad, it does not matter in what area of the touchpad a certain pattern is drawn, e.g. in the bottom left or top right, or how big it is drawn - the effect on the 1D output measure is the same. However, this approach does not provide the angle of a position moving smoothly on a circle. While theoretically it is possible to integrate differential angles between successive velocity vectors, there would still lack the constant of integration. Further, with approximations and filtering/smoothening, a (small) error is introduced at each differential update of the angle estimate which would accumulate as well. Neither can α be computed from the angle of an input velocity vector, as this would be ambiguous mapping, cf. <FIG>: A velocity vector at angle ϕ to the top right can either origin from a position in quadrant II rotating clockwise - corresponding to angle α<NUM> of this position - or it can origin from a position rotating counter-clockwise in quadrant IV, corresponding to angle α<NUM>, where α<NUM> and α<NUM> differ by π. Even when the rotating direction would be known, e.g. from the history of velocity vectors, a map from ϕ to α would imply jumps by π whenever the rotating direction changes - which is certainly not a smooth measure. This is illustrated in <FIG> which shows the trajectory of an upward movement, first rotating clockwise and then changing the rotating direction.

According to US Patent <CIT>, which discloses a "Method and apparatus for initiating one-dimensional signals with a two-dimensional pointing device", the sign of the angle between two successive motion vectors determines the sign/polarity of the (differential) update value of the 1D data. The amount of 2D movement scales the magnitude of the update value. The polarity of the 1D data is changed with delay to the angle sign change, or upon abrupt stop. Start detection: Detection of finger motion within a defined target zone, e.g. right edge of a touchpad. This approach does not provide absolute angle information.

Above solutions provide for a mapping of a 2D (circular) movement to 1D data, but they do not account for an estimate of the absolute angle of the point/finger's position on a virtual circle.

Therefore, there exists a need for an improved method for mapping a 2D (circular) movement onto 1D data. This and other objects can be achieved by a method as defined in the independent claim. Further enhancements are characterized in the dependent claims.

The invention is best understood in light of the what is described below as Approach A. Approach B is an alternative that is not claimed but useful for understanding the invention as claimed.

A circular gesture (rotational finger movement, hereinafter also called "AirWheel") can be used in a gesture detection system to control a variety of different parameter, e.g. volume or light dimming control, etc.. However, movements in a non-touching system are often not consistent and may be difficult to detect which can often lead to a bad user experience. The various embodiments of detection methods disclosed in this application are designed to overcome this possible disadvantage.

The disclosed methods are not limited to any type of user input device. Thus, it may apply to any 2D or 3D detection system. A non-touching gesture detection system is shown in <FIG>. Such a three-dimensional gesture detection systems uses a quasi-static alternating electric field with a <NUM>-frame receiving electrode layout. A transmitting electrode (not shown) may be, for example arranged under these four electrodes <NUM>, <NUM>, <NUM>, and <NUM> and cover the entire area of or encircled by the receiving electrodes <NUM>, <NUM>, <NUM>, and <NUM>. Other arrangements may be used. The velocity vectors vk as shown in <FIG> may be determined by measurement values from the receiving electrodes1510, <NUM>, <NUM>, and <NUM>, which increase (or decrease - depending on the measurement system) with decreasing finger-to-electrode distance. In such a system, generally a transmission electrode (not shown) is used to generate an electric field, for example using a <NUM>-<NUM> square wave signal generated by a microcontroller port, and the plurality of receiving electrodes <NUM>, <NUM>, <NUM>, and <NUM> which detect a disturbance in the field when an object enters the quasi-static electric field. The signals from the receiving electrodes are fed to an evaluation device which is configured to determine a three-dimensional position from these signals. The transmission signal for generating the quasi static field is typically continuously fed to the transmitting electrode during a measurement, contrary to capacitive touch measurements which typically may use pulses. The method discussed herein may be particularly beneficial in such a three-dimensional non-touch gesture detection system. Further, gesture detection samples where the data from all electrodes <NUM>, <NUM>, <NUM>, and <NUM> have the same sign, i.e. the finger is approaching/leaving all electrodes, may be ignored for updating the circle counter. However, as mentioned above, the method may apply to various other two- or three dimensional gesture detection systems.

A gesture detection system determines a movement of an object, for example a finger between a start and stop event. For purposes of detecting a circular movement of the object, during the start and stop event a plurality of position measurement may be made and the positions may be converted into x-y coordinates of a two-dimensional coordinate system even if the system is capable of detecting three-dimensional positions. The sampling time may be preferably <NUM> samples per second and the system can determine vector values from the determined position values and from the associated sampling times.

<FIG> shows a trace of a 2D position estimate for circular hand movement in front of a near field gesture detection using an electrode arrangement as shown in <FIG>. <FIG> shows the trace of a 2D position estimate of a circular finger movement in front of a near-field gesture detection system in x- and y-direction. In this figure, the positions are shown in the top right part of the detection area. However, depending on the hand posture, the estimated position may also lie in another part of the detection area, e.g. in the bottom left, or the size of the detected trace is larger or smaller depending on an individual's shape of finger or hand. However, independent of the hand posture, this movement shall still be detected as circular movement. Another reason for different positioning results can be that a default parameter set is used for a multitude of sensors, e.g. differing in size, and there shall be no need for the customer to re-parameterize the system, but functionality shall be provided out-of-the-box.

An example for the need of absolute angle information for visualization purposes is the following: A circular movement of a touching finger on the translucent cover plate of a light switch shall illuminate one LED of a set of LEDs arranged in a circle underneath the cover, whereas the lightened LED shall be the one placed at the position or at the angle corresponding to the finger's current position, i.e. the illumination follows the finger's position on a virtual circle.

Summarizing, tolerance to different hand postures or to scaling and translation of the circle gesture, as well as robustness to inaccurate parameterization - while providing a means of absolute angle information - makes the main motivation for the subject matter claimed in this application.

According to various embodiments, a circular movement can be detected by evaluating the rotating direction of input positions, and a virtual circle center is updated depending on the history of input positions, serving as a reference for output angle computation.

The computation of the output angle is straight forward: For each new input position <MAT>, the angle α between the vector from the current virtual center point pc to pnew and the positive x-axis is returned. It is obtained, for example, by computing the four-quadrant inverse tangent of (pnew - pc). This output angle may be further filtered, e.g. in order to reduce jitter.

The core of this disclosure is to update a virtual circle's center position - relative to which an angle of a position is computed - depending on the input positions' history. Two approaches are proposed.

The center position is updated by combining several characteristic positions along a circular trajectory, e.g. by averaging). These positions are stored in a buffer where each of the buffer entries corresponds to a specific characteristic position along the circular trajectory. A possible set of characteristic positions are the local extrema in X or Y coordinates, as shown in <FIG>. Each time a characteristic position is detected, first the corresponding entry in the buffer is updated with this position and then the center position. This is illustrated in <FIG>.

The characteristic positions (hereinafter also called extrema) are found by computing the current velocity vector υnew= pnew- pold, and the previous velocity vector υold, where pold is the previous input position. If the angle of υnew takes or exceeds (is below) a defined angle and the angle of υold is below (exceeds) the same defined angle, pold is considered to be a characteristic position, it is stored in its corresponding entry in the buffer and the center position pc is updated. A list of defined angles determines the list of characteristic positions used to compute pc.

The extrema may be updated during each full circle movement performed by an object such as a finger or a hand. Thus, the value of the new extremum can be both, larger or smaller <FIG> illustrates this process, with four extrema, for a trajectory where the virtual center point changes position and the rotation changes direction, starting with clockwise rotation. The numbering indicates the time instances in the sequence where the extrema positions are detected and stored in the buffer and in which pc is updated. The crosses indicate the changing position of the circle center position. As can be seen, the most left position changes from point <NUM> to point <NUM> to point <NUM>. The most top position changes from point <NUM> to point <NUM> to point <NUM>. The most right position changes from point <NUM> to point <NUM> and the most bottom position from point <NUM> to point <NUM> to point <NUM>.

In fact, there are additional conditions for updating the position buffer and the center position: The update does only take place at the named time instances if a new input position pnew is classified as being part of a circular movement and if the velocity ∥υnew∥ is high enough, e.g. higher than a threshold.

Classification of circular movement is done for every input position by computing the angle Θ between the current velocity vector υnew and its low passed filtered version lpυ = lpf(υold). In circular movement, the angle of υnew is continuously changing and due to the filtering delay, there is an angular difference between the two vectors. If the movement is non-circular, but rather linear, the direction of υnew hardly changes over time and |Θ| is typically small. |Θ| can be used as a continuous measure of the likelihood that the sample belongs to a circular movement or it can be compared with a fixed threshold for binary classification. <FIG> illustrates an example of the circular classification process where the trajectory is changing from a circular to, for example, linear and where the decrease of the angular separation between υnew and lpυ is visible.

While drawing a circle with a single rotating direction, the center should be always on the same side of the velocity vector, i.e. to its right for clockwise rotation and to its left for counter-clockwise rotation. The side only changes if the direction of rotation changes as well. Quick shift in position can lead to failure of the center position estimation, thus inverting the direction of rotation in the reported output. As shown in <FIG> (top), two consecutive circles have a large position offset and the second circle can be completed while the estimated center position is still to the left and outside the circle. This may lead to an unintended output angle. In fact, the output angle will actually suggest that there was a circular movement, but in the opposite direction. This situation is expected to occur only in very particular cases as in normal usage the user will tend to rotate around the same point.

Direction validation is a feature to prevent inversions of direction due to such fast position shifts. In a real direction change, the movement typically first decelerates and then inverts the rotating direction. For a direction change of the output angle which is caused by erroneous estimation of the center position, the movement typically does hardly decelerate. Hence, each time the center position is in a different side relative to the velocity vector, as shown in <FIG>, and the velocity did not decrease, erroneous center estimation is detected.

Direction validation assumes erroneous center estimation when the center position changes side relative to the velocity vector, but the velocity has not significantly decreased. In this case the two oldest positions in the extrema buffer are immediately updated, replacing both of them with pnew, which quickly adjusts the estimated center position back to the correct side of the velocity vector. The point substitution is shown in <FIG> (bottom), where, after extremum <NUM>, bottom and left extrema (in the buffer) are replaced by the current position, yielding a new virtual center. The replacement corrects the effect of false direction change that occurred previously in <FIG> (top) where the virtual centers <NUM> and <NUM> are clearly outside the circle.

Using this approach, the output angle is not smooth, as the center position is changed abruptly, but with filtering, the effects of erroneous center estimation can be successfully mitigated.

The center position is updated when the distance between a new position and the center point is smaller than the distance between a previous position and the center point, i.e. when the circle's radius is decreased in an update step.

The center position pc is updated if the radius of the virtual circle is decreased, i.e. if the center position's distance (Euclidean distance) rnew to the current input position pnew is smaller than its distance rold to the former input position pold. This is illustrated in <FIG>. In the before mentioned case, i.e. if rnew < rold, the intersection point pIS of the perpendicular bisector PB of the line between current input position pnew and previous input position pold with the line through pc and pold lies between pc and pold. The center point pc is then updated by moving it towards pIS, for example by adding a fraction of (pIS - pc) to pc, e.g. by employing a 1st order IIR low-pass filter, i.e. <MAT> where M is the IIR filter's memory factor.

<FIG> illustrates the update of the center position pc for an example trajectory starting at (x,y)=(<NUM>,<NUM>).

Output values may be generated between a start and a stop event. A start event may be defined by a circular trajectory and when for example a predefined threshold angle has been exceeded. An angle may be accumulated over multiple measurement points and a start event generated when the threshold has been exceeded.

Other start criteria may apply. Particularly, for 3D touchless sensor systems, the start can be triggered once movement is detected.

The algorithm considers every new input position to compute the absolute angle α and, if it is found to be an extremum, to update the virtual center position pc. Outputs are only reported if the start conditions are met.

To detect a start a minimum rotation angle must be reached and the trajectory must be circular. This rotation angle is a simple accumulation of the angular changes between successive α since the first two input positions, or for a certain amount of time.

Circular trajectory classification uses the circular movement classification (described above) to fill a buffer, preferably a first-in-first-out buffer of limited length. The likelihood that a trajectory is circular is obtained by averaging the classifications stored in the buffer, e.g. with a binary movement classification, it is defined as the number of buffer entries indicating circular movement over the total buffer length. The trajectory is considered as circular if the likelihood is above a predefined threshold.

Additionally, different functionalities can be mapped to the AirWheel depending on the position where the circular movement is started. For example, with a generic 2D touchpad, when starting the movement at the left edge of the touchpad AirWheel can do volume control, and when starting at the right edge AirWheel can control a display's brightness.

Possible stop detection techniques include the detection of the release of a touch, or the detection of a non-moving finger for a certain amount of time, or the removal of the finger/hand detected by other means than the release of a touch, e.g. hand removal from a 3D sensor system.

A stop can also be detected if the trajectory ceases to be circular, i.e. if the likelihood of a circular trajectory becomes lower than a defined threshold.

Start and/or stop detection can also be triggered by external means, e.g. by pressing/releasing a button of a keyboard.

Listing <NUM> sketches the resulting algorithm of Approach A with four extrema points.

In order to reduce computational complexity, when the required angular resolution allows the invers tangent function used to compute the output angle can be approximated for which we propose two methods.

The invers tangent function is approximated by linear segments. As the function is pointsymmetric around the origin, it is sufficient to approximate the function for positive values y and x only, i.e. for the first quadrant or quarter circle, and to change the sign of the output angle and/or add multiples of π depending on the signs of y and x. This is illustrated in <FIG> where the segment borders are (y/x) ∈ {<NUM>,<NUM>,<NUM>,<NUM>}, leading to a maximum error of π/<NUM> on the output angle.

When the requirements for resolution or granularity of the inverse tangent function are even lower, an efficient approach is to segment the quarter-circle and introduce thresholds for the ratio between coordinates (y/x) in order to determine the segment and its associated angle as output value.

The idea is to create a pre-computed lookup table with threshold values of mk = tan (δk), δk being the angles separating the segments of the quarter-circle. Evaluating the signs of x and y yields the quadrant, and comparing y/x with the stored thresholds mk yields sub-quadrant precision.

For example, when segmenting a full circle into <NUM> segments of equal size with the x and y axis representing segment borders, each quadrant contains four segments. The remaining borders within the first quadrant at angles <MAT> correspond to the values mk = y/x ∈ {<NUM>, <NUM>, <NUM>}. As these threshold values are rather close to powers of two, they can be approximated by m̃k ∈ {<NUM>, <NUM>, <NUM>}, and comparisons of the kind <MAT> can be further simplified by replacing the multiplication with m̃k by bit shift operations.

According to other embodiments, given a standard 2D touch pad or equivalent positioning device, an artificial, fix center position could be introduced, e.g. in the touch pad's geometric center, and the estimated/detected finger position could be considered relative to this center position, yielding a unique angle (e.g. to the positive x-axis). A drawback of such an implementation could be that proper functionality is only provided when the selected center position is within the drawn circle. Thus for example a small circle drawn in the upper right corner of the touch pad may not be recognized.

According to various embodiments, the method discussed above can be implemented into a wide variety of devices. For example, the circular gesture may be used to resemble the control of a virtual Volume control wheel of a HiFi set: Clockwise movement increases the volume, counter-clockwise movement decreases the volume.

According to another embodiment, any type of media-player control functionality known from, for example, a circular touchpad can be implemented.

According to yet another embodiment, control of a dimmer in a light switch or various other appliance functions such as, for example, speed control, air condition temperature, mechanical movement functions, etc. can be implemented by the methods disclosed in this application.

According to another embodiment, a replacement for a PC mouse's scroll wheel can be implemented.

Claim 1:
A method for detecting a continuous circular gesture performed by an object, preferably a finger, a hand, or a pen, the method comprising
detecting a movement of an object performing a circular movement by scanning the movement and determining subsequent position points (pk) of the object,
characterized by
initializing a center position (pc);
determining a circular movement if an angle of the movement exceeds a threshold; determining from the subsequent position points (pk) left, right, top and bottom extrema positions, of the circular movement relative to the center position (pc) and updating a buffer with the center position (pc) and the extrema positions when a movement is determined to be part of a circular movement and when a velocity vector (vk) is higher than a predetermined velocity threshold, wherein positions are computed from a current velocity vector (vk) and a previous velocity vector (vk-<NUM>),
wherein for each updated position the center position (pc) is updated from the buffered positions, wherein the center position (pc) is a circle center position;
and
adjusting a control variable based on the continuous circular gesture.