HK1169909B - Directional tap detection algorithm using an accelerometer - Google Patents

Description

Directional tap detection algorithm using accelerometer

Background

1. Field of the invention

The present invention relates generally to a system and method in which a directional tap detection algorithm and tri-axial accelerometer extend the number of unique button-less inputs available for small mobile devices, such as cell phones and MP3 players. The algorithm analyzes the acceleration data from a single accelerometer to detect the direction (X +, X-, Y +, Y-, Z +, Z-) and number (single or double) of taps, resulting in 12 unique inputs.

2. Background of the invention

Mobile devices are becoming increasingly portable today. The reduction in size limits the space for input devices such as buttons and keyboards. Many researchers are developing gesture recognition to remove traditional input devices. In certain circumstances, a simple action may be a more efficient input. The advent of MEMS (micro electro mechanical systems) technology has significantly reduced the size of accelerometers that can detect motion of an object. A tap is a very simple action. This is intuitive and does not require learning. This can be a unique input method if the device can be controlled using tapping anywhere on the surface of the device.

Preliminary tap detection generally allows for two different input commands. This is commonly referred to as a tap and double tap. However, it is necessary to provide multiple tap commands in the aforementioned small mobile devices.

Summary of The Invention

The present invention addresses the aforementioned needs through the combined use of a tap detection algorithm and a tri-axial accelerometer that not only enables differentiation between single and double taps, but also enables differentiation based on the direction of the tap. Careful analysis of the acceleration characteristics (signature) of a flick allows determination of which side or sides of the object are being flicked (direction of the flick). The inclusion of directional information extends the possible available input commands to a 12, six fold progression.

The system and method of the present invention are particularly useful for generating button-less input for small mobile electronic devices such as cell phones and MP3 players. A variety of input commands may be created with the number and direction of taps detected. For example, a menu may be scrolled up or down or items in a menu may be selected. The single sensor required to detect these 12 unique inputs does not require surface area on the exterior of the mobile device since the accelerations due to the tap are transmitted to the interior of the mobile device.

Once a tap has been detected, the determination of the tap direction is accomplished through a detailed analysis of the acceleration data. A single tap is a single blow of a particular device with a portion of a human body or a stylus. A double tap is two single taps in rapid succession.

The acceleration is located inside the device so that when the device is tapped the shock is properly transferred to the accelerometer. Since the device can be tapped on either side, the preferred location for the accelerometer is the center of the device. Using a tri-axial accelerometer, the device can be tapped on each of its faces to provide 12 combinations of tap input events.

When a tap occurs, the impact of the tap is transmitted through the body of the device to the accelerometer.

The peak rises to a maximum in 0.005 seconds and rebounds slightly slower. Regardless of the direction from which the tap is made, the maximum acceleration reaches 0.5 g. The total acceleration is the magnitude of the accelerationWherein: ax: x-axis acceleration; ay: y-axis acceleration; and Az: z-axis acceleration.

Sometimes the rebound can be more than half of the original peak and the correlation to the other axis can be seen. If the device is tapped in a particular direction, the other axes respond. Therefore, all axes should be observed to clarify whether a tap occurred.

A double tap means tapping the same dot in a row twice in quick succession. The second tap followed the first tap for less than 0.5 seconds. Each individual tap does not show any acceleration difference from a single tap. The timing relationship (timing) of the two taps determines whether the command is a double tap or two independent single taps.

A key feature of this algorithm is the Performance Index (PI) which is used to provide a characteristic feature of a tap event. The PI is the sum of the absolute values of the magnitudes of the jitter of each axis that is due to the movement of the device, such as by a user tapping on a side or face of the device. The derivative of the jerk acceleration with respect to time (i.e., the change in acceleration). In general, the jitter curve gives information about very fast and sloppy (shake) movements. The power on all axes is summed using absolute values. The performance index of the flick is significantly greater than the level of background noise. Thus, a threshold technique is then applied to the performance index to distinguish between possible tap events and noise. In addition, the length of time that the PI is greater than the threshold and the length of time between two occurrences of high PI (or no second PI peak) may be used to distinguish between single and double taps.

Once a tap or double tap is determined, additional scrutiny provides the direction of the tap event. First, it is determined which axis is the largest component of the performance index at the beginning of the tap (which axis has the largest jitter). The axis with the largest jitter coincides with the axis along which the flick is applied to the axis of the device. Finally, after this axis is determined, the dithered signal on the tapping axis is used to provide tap direction information. If the peak is negative, then the flick is in a positive direction; whereas tapping is in the negative direction.

In the manner described above, the present invention provides an apparatus and method that can detect 12 different tap commands. Thresholding and timing relationships of the performance index take into account that taps are identified and single or double taps that provide two different commands are distinguished. The maximum component of the initial performance index provides the axis of the tap, thus tripling the number of different commands. Finally, the initial marking of the flick axis provides a flick direction, which doubles the available commands.

In a preferred embodiment, a 3-axis accelerometer chip of MEMS type is preferably provided in a device which is controlled to implement the above method. The accelerometer chip preferably includes its own dedicated processor that executes the tap detection algorithm described above and produces 12 outputs that are used as input commands to the main processor of the device. Optionally, the host processor itself may be programmed to receive 3 inputs from the accelerometer and execute the tap detection algorithm.

Brief Description of Drawings

The above and other features and advantages of the present invention will become apparent from the following detailed description of the preferred embodiments of the invention, which is to be read in connection with the accompanying drawings, which are briefly described below.

FIG. 1 is a schematic diagram of a device having an accelerometer chip disposed therein for detecting taps on different faces or sides of the device.

FIG. 2 is a schematic diagram of the device of FIG. 1 showing 12 possible tap inputs that may be detected with the present invention.

Fig. 3 is a graph showing the magnitude of the Performance Index (PI) as a function of time, where the PI is calculated by summing the absolute values of the jitter (derivative of acceleration) applied by the tap along each axis of the device, as a function of time.

FIG. 4 is a graph showing PI over time for a single tap on a device.

FIG. 5 is a graph showing PI as a function of time for a double tap on a device.

FIG. 6 is a graph showing jitter (acceleration derivative) magnitude versus time for each axis of the accelerometer in response to a single tap along the X-axis of the device.

FIG. 7A is a block diagram of the general steps performed by the algorithm employed by the method of the present invention for detecting a single or double tap on a device.

FIG. 7B is a block diagram of the detailed steps performed with the algorithm of FIG. 7A.

Figure 8 is a block diagram of an accelerometer chip employed in accordance with a preferred embodiment of the present invention.

Detailed description of the invention

A more detailed description of preferred embodiments of the invention will now be presented. First, a process for identifying a flick is described. A single tap is a single blow of a particular device with a portion of a human body or a stylus. The double tap is formed by two single taps in rapid succession.

As shown in fig. 1, an accelerometer 10 of the 3-axis (X, Y, Z) MEMS type is preferably mounted in a device 12, this device 12 being controlled such that when the housing 13 of the device 12 is tapped on any six sides or faces 14 of the device, the shock is suitably transferred to the accelerometer 10. The device 12 may be any type of electronic device that requires commands to be input therein to be controlled, although the present invention is particularly suitable for use with small mobile devices such as cell phones, MP3 players, and the like, whose provision of command buttons is inherently limited by the size of the device.

Since the device 12 can be tapped on any of its six sides 14, the preferred position of the accelerometer 10 is the center of the device 12, where the 3-axis sensor of the accelerometer is disposed parallel to a corresponding pair of the six sides 14. FIG. 2 shows how device 12 may be tapped a single or double time on each side 14 to provide 12 combinations of tap input events.

When a tap occurs, the impact is transmitted to the accelerometer 10 through the body or housing 13 of the device 12. In the test with the preferred embodiment, the rise to the maximum value was within 0.005 seconds and the rebound was slightly slower. Regardless of the direction from which the tap is made, the maximum acceleration reaches 0.5 g. The total acceleration refers to the magnitude of the acceleration determined as follows:

formula 1

In equation 1, Ax ═ X-axis acceleration; ay-axis acceleration; and Az-Z axis acceleration.

Sometimes the rebound can be more than half of the original peak and the correlation to the other axis can be seen. If the device 12 is tapped in a particular direction, the other axes respond. All axes should be observed to make clear whether a tap has occurred.

A double tap means tapping the same dot in a row twice in quick succession. The second tap followed the first tap for less than 0.5 seconds. Each individual tap does not show any acceleration difference from a single tap. The timing relationship of the two taps determines whether the command is a double tap or two independent single taps.

In a preferred embodiment, a calculation called the Performance Index (PI) is used to provide a characteristic feature of a tap event. PI is the sum of the absolute values of the jitter for each axis. Jitter is the derivative of acceleration with respect to time (i.e., the change in acceleration). In general, the jitter curve gives information about very fast and sloshing movements. The performance index may be expressed by the following formula:

formula 2

The absolute values are used to sum the power on all the axes in total. The performance index of the flick is significantly greater than the level of background noise. Therefore, applying a thresholding technique on the PI distinguishes between possible tap events and noise. A flick event is detected when the sum of the previously described jitters exceeds a lower threshold of the performance index for a period of time that is greater than a flick detection low limit but less than a flick detection high limit. FIG. 3 shows an example of a single tap event that meets performance index criteria. In fig. 3, the performance index exceeds the performance index lower threshold (TDT _ L _ THRESH) for a number of time intervals of samples, but is less than the tap detection high limit value contained in TDT _ FIRST _ TIMER.

Further, the length of time that the PI is greater than the threshold and the length of time between two occurrences of high PI (or no second PI peak) distinguish between single and double taps. In a preferred embodiment, the delay timer sets a timer that a tap event can only be characterized as a single tap. The second tap must occur outside the delay timer. If a second tap occurs within this delay time, it will be ignored as occurring too quickly. A single tap reports at the end of the window timer. FIG. 4 shows a single tap event that meets the PI, delay, and window requirements. The delay TIMER is referred to as TDT _ LATENCY _ TIMER, and the WINDOW TIMER is referred to as TDT _ WINDOW _ TIMER.

An event may be characterized as a double tap only if the second tap crosses a lower threshold of performance index beyond another TIMER called TDT _ TIMER. This means that TDT _ TIMER determines the minimum time interval that exists between two taps of a double tap event. Similar to a single tap, a second tap event must exceed the performance index threshold for a time limit contained in the window timer. A double tap may be reported at the end of the second delay timer. FIG. 5 shows a double tap event that meets the PI, delay, and window requirements. In FIG. 5, the second tap crosses the performance index low THRESHOLD (TDT _ L _ THRESHOLD) outside of TDT _ TIMER. In addition, the second TAP event exceeds TDT _ L _ THRESHOLD by the time limit value contained in TDT _ TAP _ TIMER. Then, a double tap is reported at the end of the second time, TDT _ LATENCY _ TIMER.

Once a tap or double tap is determined, additional scrutiny provides the direction of the tap event. First, it is determined which axis provides the largest component of the performance parameter at the beginning of the tap (which axis has the largest jitter). The axis with the largest jitter coincides with the axis along which the flick is applied. As an example, when the device is tapped in the X + and X-directions, the X-axis is the axis of maximum response and thus has the largest dither size compared to the dither sizes of the Y and Z axes.

Once a tap is detected and the axis is determined, a dithered signal on the tap axis is used to provide directional information. If the peak is negative, then the flick is in a positive direction; whereas tapping is in the negative direction. The icon in fig. 6 shows an enlarged view of the magnitude of the shake of each axis in response to a single tap. The X-axis clearly contributes the largest component to the performance index, indicating that the tap is on the X-axis. The initial flick is in the negative direction, indicating that the flick is located on the positive X-face of the device.

Thresholding of the performance index and consideration of the length of time identifies taps and distinguishes single or double taps providing two different commands. The maximum component of the initial performance parameter provides the axis of the tap, thus tripling the number of different commands. Finally, the initial signal of the dithering of the putter provides a flick direction, which doubles the available commands.

The algorithm executed in the preferred embodiment of the present invention therefore follows the steps of the flow chart in fig. 7. Four main functions based on acceleration data are shown. After obtaining acceleration data from the accelerometer chip in step 100, the first function is to calculate a performance index in step 102. The second function is to determine whether a single or double tap at step 104. The third function is to determine in step 106 along which axis the tap occurred based on the largest component of the performance index. Finally, a directional token for the flick is determined at step 108 based on the sign of the initial flick.

Fig. 7B is a detailed flowchart illustrating how the above-described steps of fig. 7A are performed in a preferred embodiment of the present invention. In fig. 7B, the following parameter values are used:

ax, Ay, Az: current acceleration readings;

pAx, pAy, pAz: a previous acceleration reading;

dAx, dAy, dAz: the difference between the current and previous acceleration readings (jitter);

x, y, z: as dAx, dAy, dAz (for simplicity of notation);

dt: a performance index;

x0, y0, z 0: information about initial jitter above a threshold (for direction determination);

ax0, ay0, az 0: information about initial jitter above a threshold (for axis determination);

j: counting a time for how long the performance index is above a threshold;

m: counting a time for how long the performance index is below a threshold;

l: count of total time from the beginning of the first tap event; and

DT: double tap the time window.

Referring specifically to the flowchart in FIG. 7B, a first set of steps 200 is initially performed to load first acceleration data received from an accelerometer into previous acceleration data. Step 202 is then performed to check the timer value j for the over-run condition. If detected, the time value is reset to 0. Next, a difference between the current and previous acceleration values is calculated at step 204. These difference values are the amount of jitter (acceleration derivative) detected along each of the 3-axis, X, Y, and Z. The acceleration reading is then updated by uploading the previous acceleration reading to the current reading, step 206.

After the jitter value is updated at step 208, then at step 210, PI is calculated using equation 2 discussed previously. At step 212, the PI is then compared to lower and upper thresholds. If PI is between two thresholds and the time value j is 0, it is an indication of the first jitter greater than the threshold, which may be in response to a single or double tap event. If a single or double tap is indeed detected, a set of steps 214 is performed to store the acceleration information for later axis and direction determinations. Also, at step 216, the various time counts are then updated, and the process returns to the beginning (step 200), where the next sampled acceleration data is retrieved for the same analysis.

At some point, if a tap does occur, the PI value will fall below the lower threshold. If this occurs when the sum of the m and j timer values is greater than 1, step 218, the timer values are updated, step 220. Next, a series of timer analysis steps 222 are performed to determine if a single or double tap has occurred. If either m is not greater than 40 or DT is not greater than m, an analysis is performed to determine if a single tap is detected. A single tap may be determined to be detected by: if the PI is greater than the lower threshold for a duration count of between 2 and 20, and the double tap time window value reaches 160 (which confirms that no second tap has occurred). If the timer count for PI below the threshold persistence is at least m > 40, the double tap time window DT is greater than m, and PI is greater than the lower threshold persistence timer value j > m; and the total time count L from the first tap event is greater than 120, then a double tap has occurred.

Once a single or double tap is detected, the algorithm then performs a series of direction determination steps 224 that determine which of the three axes X, Y and Z the tap occurred along and the direction along that axis. In step 226, this may be determined simply by comparing the magnitude of the acceleration values along the three axes and identifying the axis with the greatest acceleration value as the axis of the flick. Finally, in step 228, the direction of the flick is detected by determining whether the detected acceleration is positive (> 0) or negative (< 0). The analysis is then complete, various timers and other values are reset at step 230, and the process then resumes at step 200.

Figure 8 is a block diagram illustrating details of a 3-axis accelerometer chip configured in accordance with a preferred embodiment of the invention. In the accelerometer processor (in this preferred embodiment, I)²C digital engine) 302 contains logic circuits that implement the algorithm of fig. 7B. The tap detection feature of the processor 302 recognizes single and double tap inputs and reports the acceleration axis and direction in which each tap occurred. Eight performance parameters as described above, as well as a user selectable ODR, are used to set the processor 302 for a desired tap detection response.

Accelerometer processor 302 receives inputs from X, Y, and Z axis gravity sensors 304, 306, and 308, respectively. Each of the sensors 304, 306, 308 produces an analog output signal that is conditioned (conditioned) by being passed through a charge amplifier 310, an a/D converter 312, and a digital filter 314 before being input to the processor 302. When the processor 302 receives a signal indicating an acceleration event, such as a tap, the signal on the interrupt pin (INT)316 of the processor 302 goes high. When the host processor (device processor) 318 recognizes this interrupt, the host processor 318 then reads the interrupt status register (via I) in the accelerometer processor 302²C communication) to obtain information about the tap event.

The status registers in the accelerometer processor 302 include the following. There are two interrupt source registers that report a functional state change. When a new state change or event occurs, this data is updated and each application result is latched until the interrupt release register is read. The first register, called INT _ SRC _ REG1, reports which axis and direction a single or double tap event was detected, as shown in table 1. Note that multiple axes may sense a flick event, and that all more than one bit may be set at the same time.

TABLE 1 flick double flick report

The second register, called INT _ SRC _ REG2, reports which function caused the interrupt. Reading the entire contents of this register from the interrupt release register may clear it.

DRDY indicates that new acceleration data is available. This bit is cleared when the acceleration data is read or the interrupt release register is read, so that when DRDY is 0, new acceleration data is not available, and when DRDY is 1, new acceleration data is available. TDTS1, TDTS0 reflects whether a tap double tap event is detected, as shown in Table 2.

TDTS1	TDTS0	Event(s)
			0	0	Without flicking
0	1	Single tap
			1	0	Double tap
1	1	DNE

TABLE 2 flick double flick description

The TPS reflects the state of the tilt position function. TPS ═ 0 indicates that the tilt position state has not changed, and TPS ═ 1 indicates that the tilt position state has changed.

A register called STATUS _ REG reports the STATUS of the interrupt.

The INT reports the combined interrupt information for all enabled functions. When the interrupt source register (1Ah) is read, this bit is released to 0. INT-0 indicates that there is no interrupt event, and INT-1 indicates that an interrupt event has occurred.

The register INT _ REL is used to release the interrupt. Specifically, when the register is read, the latched interrupt source information (INT _ SRC _ REG1 and INT _ SRC _ REG2), the status register, and the physical interrupt pin (7) are cleared.

Although the present invention has been disclosed in terms of preferred embodiments and variations thereon, it will be understood that numerous additional modifications and variations could be made thereto without departing from the scope of the invention defined by the following claims. For example, the preferred embodiment employs an accelerometer chip with its dedicated processor for executing the tap detection algorithm, however, the main processor of the controlled device may itself be programmed to receive 3 inputs from the accelerometer and execute the tap detection algorithm.

Claims (16)

1. A method for detecting a tap input on a device based on first, second and third axis outputs from a three axis accelerometer attached to the device, the method comprising the steps of:

detecting acceleration signals resulting from the first, second and third axis outputs of the accelerometer caused by movement of the device;

for each of said outputs, calculating a derivative of each acceleration signal as a function of time;

determining whether the movement of the device is caused by a tap input on a housing of the device by calculating a sum of absolute values of the acceleration derivatives resulting from the movement along each axis of the accelerometer, summing the dynamics in all axes using absolute values, and determining that the movement is a tap input if the sum of absolute values exceeds a threshold for a predetermined time;

determining an axis of the flick by determining which axis of the accelerometer produces an acceleration derivative with a maximum magnitude;

determining a direction of the flick by determining a sign of an acceleration derivative with a largest magnitude; and

generating an input command to control operation of the device using the determined flick axis and direction.

2. The method of claim 1, further comprising the step of determining whether the movement of the device is caused by a double tap.

3. The method of claim 2, wherein 12 different input commands are generated, wherein 4 input commands are generated for each of the three axes, and two of the 4 are determined based on the determined direction of the tap and the other two are determined based on whether a single tap or a double tap is detected.

4. The method of claim 2, wherein the step of determining whether the movement of the device is caused by a double tap comprises: determining that the movement is a double tap input if a sum of absolute values of the acceleration derivatives along each axis of the accelerometer resulting from the movement exceeds a threshold for a first predetermined amount of time, falls below the threshold, then exceeds the threshold for a second predetermined amount of time, wherein the second predetermined amount of time begins within a third predetermined amount of time after the value falls below the threshold.

5. The method of claim 4, wherein 12 different input commands are generated, wherein 4 input commands are generated for each of the three axes, and two of the 4 are determined based on the determined direction of the tap and the other two are determined based on whether a single tap or a double tap is detected.

6. The method of claim 1, wherein the accelerometer is centrally located in the device.

7. The method of claim 1, wherein the device is a mobile device.

8. The method of claim 7, wherein the mobile device comprises a cell phone or an MP3 player.

9. A system for providing button-less input commands to a mobile electronic device, the system comprising:

a three-axis accelerometer attached to the device;

an accelerometer output processor coupled to the 3 outputs of the accelerometer, and a device processor controlling the operation of the device, the accelerometer output processor programmed with an algorithm that performs the steps of:

detecting an acceleration signal resulting from the first, second, and third outputs of the accelerometer caused by movement of the device;

for each of said outputs, calculating a derivative of each acceleration signal as a function of time;

determining whether the movement of the device is caused by a tap input on a housing of the device by calculating a sum of absolute values of the acceleration derivatives resulting from the movement along each axis of the accelerometer, summing the dynamics in all axes using absolute values, and determining that the movement is a tap input if the sum of absolute values exceeds a threshold for a predetermined time;

determining an axis of the flick by determining which axis of the accelerometer produces an acceleration derivative with a maximum magnitude;

determining a direction of the flick by determining a sign of an acceleration derivative with a largest magnitude; and

communicating information about the axis and direction of the flick with the device processor such that the device processor may use the information as an input command.

10. The system of claim 9, wherein the algorithm further comprises the step of determining whether the movement of the device is caused by a double tap.

11. The system of claim 10, wherein 12 different input commands are generated, wherein 4 input commands are generated for each of the 3 axes, two of the 4 being determined based on the determined direction of the tap, the other two being determined based on detecting a single tap or a double tap.

12. The system of claim 10, wherein the step of determining whether the movement of the device is caused by a double tap comprises: determining that the movement is a double tap input if a sum of absolute values of the acceleration derivatives along each axis of the accelerometer resulting from the movement exceeds a threshold for a first predetermined amount of time, falls below the threshold, then exceeds the threshold for a second predetermined amount of time, wherein the second predetermined amount of time begins within a third predetermined amount of time after the value falls below the threshold.

13. The system of claim 12, wherein the 12 different input commands are generated, wherein 4 are generated for each of the 3 axes, two of the 4 being determined based on the determined direction of the tap and the other two being determined based on whether a single tap or a double tap was detected.

14. The system of claim 9, wherein the accelerometer is centrally located in the device.

15. The system of claim 9, wherein the device is a mobile device.

16. The system of claim 15, wherein the mobile device comprises a cell phone or an MP3 player.