VelocityTracker incorrect velocity calculation on few events
Sandblad, Andreas
Hi,
In Icecream the android.view.GestureDetector Java class uses the native VelocityTracker class (frameworks/base/libs/ui/input.cpp) to detect if a touch swipe movement is a fling. In the onFling callback the calculated x and y velocities are supplied. The native VelocityTracker implementation (from commit b59ab9f41faafb358afb4f951de96f34a656e0b4) samples the maximum last 20 (HISTORY_SIZE) events occurred within 100 (DEFAULT_HORIZON) ms. On the sample it solves a linear least squares problem to obtain a second degree polynomial (DEFAULT_DEGREE), which can be described as y(x) ~= B0 + B1*x + B2*x^2 representing the values in the sample. It then finally takes the B1 and let it represent the velocity of the fling (only the last part of the swipe gesture is used as the sample is restricted to 100 ms). This gives good values if the number of values in the sample are high and the motion is quite straight, but for a few events in the sample or if there is both a motion in x and y this can give unwanted results as the polynomial fit may look like a x^2 curve. This means that even if e.g. dy is negative for all events, the outcome velocity can be in the incorrect opposite direction, putting a lot of constraints on the device generating the motion event and the actual user gesture. I have attached two screenshots where this can be seen (fling1.png and fling2.png).
The main solution which I would like to contribute is simply to change the default degree from 2 to 1, but I could see some variants such as only using degree 1 for hover events (which VelocityTracker has support for) or when the number of events in the sample is low. For normal touch usage I have not seen any actual difference between degree 1 and 2, but for e.g. hover devices where the motion can occur within a quite large z range changing to degree 1 gives much better results. Anyway, I want your feedback before going into the contribution steps. I may be missing something which you had in mind when designing this (e.g. some user behavior you optimized for).
/Andreas Sandblad, developer at Sony Mobile Communications
Jeffrey Brown
The problem here is quite a subtle one and the effect observed varies
due to many parameters, some of which are hardware dependent.
To give you an example of the problem, here are a couple of ways that
touchscreens can vary which cause VelocityTracker (and applications)
some grief.
Problem 1. Late lift-off events. Some touch controllers report the
lift-off signal of a touch quite late, even up to 30ms after the last
movement was reported. When this happens, the finger looks like it
was immobile for some time towards the end of the sequence of events.
Problem 2. Jittery lift-off events. Some touch controllers do not
filter lift-off events very well. As the finger is released from the
touch screen, the observed position of the finger may jitter around by
a few pixels in a very short period of time.
Both of these problems can be solved through improved filtering in the
touch controller firmware. Although less preferable, changes can also
be made to the InputReader component to perform additional filtering
to compensate.
That said, it has become apparent that the VelocityTracker needs
further improvement so that it can better tolerate situations like
these and also avoid statistical problems that result from overfitting
the curve. I plan to make improvements to the algorithm soon. If
they are good enough, then I will submit them to AOSP.
I do want to address one specific algorithm design point here, which
is the choice of a quadratic polynomial. This has come up several
times in different forums, along with a question as to whether we
could use a linear polynomial instead.
We could use a linear polynomial but the results are not as good.
Using a quadratic polynomial substantially improves the smoothness of
accelerating flings because the estimated velocity at the time when
the finger is released more accurately reflects the finger's final
velocity at lift-off.
I'm not sure I follow what you're saying with respect to hover events.
How are they different?
Jeff.
Sandblad, Andreas
Thank you for the detailed and quick response. I am very interested in the changes you plan to make and is willing to help you out testing and reviewing them. I think the main problem here is as you write the statistical problems that result from overfitting the curve, at least from my observations.
As a phone manufacture you are kind of stuck with the implementation in the VelocityTracker. There is always a risk that you tune the behavior too much to specific hardware, giving a hard time for the touch firmware to adopt to a specific implementation in the VelocityTracker (which may change in the future). And we are not just talking about phones here, people are putting Android in a lot of different strange devices.
One way to give some flexibility is to make this configurable in the .idc configuration file of the input device, e.g. the choice of the degree (1 or 2) or some other parameter which may be hardware dependent.
References:
http://source.android.com/tech/input/touch-devices.html
http://source.android.com/tech/input/input-device-configuration-files.html
/Andreas Sandblad, developer at Sony Mobile Communications
Jeffrey Brown
the touch screen.
I bet if you sent me a trace of the touch events we would see the
touch moving smoothly through a fling and then at the end there would
be two or three nearly identical samples spaced tens of milliseconds
apart. In other words, according to the touch event stream, the
finger juddered to a halt and jittered around a bit just before
release.
I'm working on improvements to velocity tracker to better handle
sudden changes in direction or stopping.
I should note that using a degree 1 polynomial will produce bad
results in this case too. The computed velocity is likely to have the
wrong direction (turned somewhat sideways from what was expected),
although it likely won't reverse on itself. That's better but still
bad.
Ideally, the touch screen should report a clean liftoff at the end of the touch.
Jeff.
On Tue, Apr 24, 2012 at 12:56 AM, Sandblad, Andreas
Jeffrey Brown
Would you be willing to help me collect some data about the problem?
Here's how.
On one of your devices, run the following command:
adb shell getevent -p >info.txt
adb shell getevent -t >>info.txt
While the second command is running, perform a dozen or two swipes including some that exhibit the problem.
Then send me the resulting info.txt file privately off-list.
Thanks,
Jeff.