2

Detecting a shake gesture, from a collection of points, is basically looking for three changes in direction:

Example: (We need to look only at x-coordinates, as we are looking only for horizontal shakes, not vertical shakes)

1,2,3,4,5,6,7,8,[9],8,7,[6],[7]

In the above sequence of x-coords, I have marked the changes in direction with [].

The problem is, in the above case, we would detect even tiny unintentional shakes - for example, if you ask a person to drag his finger from the bottom of the screen to the top in a straight line, his hand may move a little left and right unintentionally, and we would regard this as a "shake"

Example:

1,2,[3],[2],[3].... (unintentional shake)

To avoid this, we need some kind of threshold, only above which we regard the movement as a shake. For example, the gap between changes in direction should be atleast 3 points, and the difference in value should be atleast 4.

So we should have something like:

1,2,3,4,5,6,7,8,[9],8,7,6,[5],6,7,8,[9]..... detected shake

1,2,3,4,5,6,7,8,[9],8,7,6,6,7,8,9..... ignored shake

1,2,3,2,1.... ignored shake...

This seems tricky to implement, as one would probably have to keep track of three indices. Rather than implement this myself, I was wondering if this is a known algorithm with a solution that I can look up ?

Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160
Rahul Iyer
  • 19,924
  • 21
  • 96
  • 190

1 Answers1

4

Depending on the fact that the derivative describes the change in movement of a function, you may use derivative to this solve the problem easily.

enter image description here

Let us take the first example:

1, 2, 3, 4, 5, 6, 7, 8, [9], 8, 7, [6], [7]

By finding the derivative of this sequence:

1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1
+  +  +  +  +  +  +  +   -   -   -  +

Now, it is easy to know where the shakes were happend.

Another example: 

 1, 12, 15, 8, 3, 1, 0, 5, 17, 30

1st derivative:

11, 3, -7, -5, -2, -1, 5, 12, 13
 +  +   -   -   -   -  +   +  +

Simple implementation (non-tested, non-optimized):

template <typename valueType> // http://stackoverflow.com/a/67020/4523099
bool same_sign(typename valueType x, typename valueType y){
     return (x >= 0) ^ (y < 0);
}

template <typename T>
std::vector<T> get_derivative(std::vector<T> vec_x){
    for(size_t i=0;i<vec_x.size()-1;++i){
         vec_x[i]= vec_x[i+1]-vec_x[i];
    }
    vec_x.pop_back();
    return vec_x;
}

int main(){
    std::vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 7 };
    auto first_derivative=get_derivative(x);
    std::vector<size_t> indices_of_shakes;
    for(size_t i=0;i<first_derivative.size()-1;++i){
        if(!same_sign(first_derivative[i],first_derivative[i+1])){
            indices_of_shakes.emplace_back(i);
        }

    } 
}
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160
  • Can you explain why this should work ? I see what you're doing, but was wondering if you could explain the theory. – Rahul Iyer May 10 '17 at 07:17
  • 1
    "Edge detection using derivative", "sobel", "Laplacian operator" any term of those will give you tons of resources. If you still not sure you may ask about a specific problem. – Humam Helfawi May 10 '17 at 07:22
  • Also, although in the example I have used consecutive integers, in practice the touch screen reads input only every 1/60th of a second, so the xCoordinates may not be close together at all. For example you could have 3,4,54,13,... in which case you get first derivatives of 1,50,-41, and then second derivatives of 49,91... – Rahul Iyer May 10 '17 at 07:22
  • 3
    Derivative is positive when sequence is rising, negative when it's falling. Exact values don't really matter except for threshold. – Tomasz Plaskota May 10 '17 at 07:25
  • This is hard to wrap my head around. So in my case, where I am trying to detect the zig-zag shape of a shake (left,right,left) or (right,left,right), what should I look for in the second derivative ? For example, if you have 3,4,54,13,12,11,10,36,43,66, then the first derivative is 1,50,-41,-1,-1,-1,26,7,23, and then second is,49,-91,40,0,0,27,0,-19,16... so what would I do in this case ? – Rahul Iyer May 10 '17 at 07:35
  • 1
    @KaizerSozay you are right I go a bit further which is wrong. 1st derivative is enough, I am editing my answer – Humam Helfawi May 10 '17 at 07:45
  • I see. So it seems that in addition to your code, all I have to do is group the (+) and (-) areas, and as long as I have a (+),(-),(+), or (-),(+),(-), where the number of points in each set of (+)'s and (-)'s meet my threshold (say 3 points), then I have detected a shake gesture. – Rahul Iyer May 10 '17 at 08:19
  • @KaizerSozay yes it seems like this – Humam Helfawi May 10 '17 at 08:21