1 // Copyright 2013 The ChromiumOS Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <gtest/gtest.h> // for FRIEND_TEST 6 #include <map> 7 8 #include "include/filter_interpreter.h" 9 #include "include/finger_metrics.h" 10 #include "include/gestures.h" 11 #include "include/prop_registry.h" 12 #include "include/tracer.h" 13 #include "include/util.h" 14 15 #ifndef GESTURES_TREND_CLASSIFYING_FILTER_INTERPRETER_H_ 16 #define GESTURES_TREND_CLASSIFYING_FILTER_INTERPRETER_H_ 17 18 namespace gestures { 19 20 // This interpreter checks whether there is a statistically significant 21 // evidence showing that a finger is non-stationary (i.e. moving along a 22 // direction). We utilizes a variation of the Kendall's Tau test to 23 // achieve the purpose. For the interested, please may refer to the following 24 // links for more details: 25 // 26 // [1] http://en.wikipedia.org/wiki/Kendall_tau_rank_correlation_coefficient 27 // [2] http://www.stats.uwo.ca/faculty/aim/vita/pdf/McLeod95.pdf 28 // 29 // The Kendall's Tau test is a method to measure the degree of association 30 // between two random variables. Specifically, it tries to assess if one's 31 // value has a tendency to change when the other one changes. Given the 32 // trajectory on the (X, Y) plane of a finger over some period of time, one may 33 // view the problem of deciding stationary fingers as to assess whether there 34 // is any association between either X and time or Y and time. The advantage of 35 // Kendall's test is that it is non-parametric, i.e. it uses the ranking of 36 // data instead of the data values themselves. In this way, it enjoys better 37 // robustness to outliers, random noises as well as non-linear relationships. 38 // 39 // Given a time-series (t1, d1), (t2, d2) .... (tn, dn), the Kendall's Tau 40 // coefficient is defined as: 41 // 42 // (# of concordant pairs) - (# of discordant pairs) 43 // Tau = ----------------------------------------------------- (1) 44 // n * (n - 1) / 2 45 // 46 // , where n is the total number of samples and concordant/discordant pairs are 47 // [(ti, di), (tj, dj)] whose ti < tj and di < dj or di > dj. The above 48 // definition is only valid when there is no ties in the sample. In the case 49 // that ties are present, as in our case, various adjustments need to be made. 50 // 51 // The denominator part in the formula (1) is sometimes called the Kendall's 52 // score or simply the Kendall's S-statistic. Study has shown that its 53 // distribution approximately follows the normal distribution when n is large 54 // (e.g. > 6) no matter whether there are ties or not. The detailed proof could 55 // be found in [2]. Here, we simply give the expression for the variance of S in 56 // the case that there may only be ties in one variable (our application) as 57 // follows: 58 // 59 // n * (n - 1) * (2n + 5) 2 60 // Var(S) = ---------------------- - Σ (--- * C(ui, 3) + C(ui, 2)) (2) 61 // 18 i 3 62 // 63 // , where ui is the number of samples in the i-th ties group and C(x, y) is 64 // the binomial coefficient notation. 65 // 66 // For each finger, we maintain a buffer of past coordinates and compare the 67 // normalized Z-value S/sqrt(Var(S)) to a pre-set threshold Zα as in standard 68 // statistical hypothesis tests. If the Z-value is outside of the region 69 // [-Zα, Zα], we can conclude that the instance is too rare to happen simply by 70 // chance and we reject the null hypothesis that there is no association 71 // between two random variables. We use a two-tailed test here because the 72 // finger could move in either the positive or the negative direction. The 73 // interpreter then marks each identified finger with the flags 74 // GESTURES_FINGER_TREND_*_X or GESTURES_FINGER_TREND_*_Y respectively which 75 // would be further used in the ImmediateInterpreter to identify resting 76 // thumbs. 77 78 class TrendClassifyingFilterInterpreter: public FilterInterpreter { 79 FRIEND_TEST(TrendClassifyingFilterInterpreterTest, SimpleTest); 80 81 public: 82 TrendClassifyingFilterInterpreter(PropRegistry* prop_reg, Interpreter* next, 83 Tracer* tracer); ~TrendClassifyingFilterInterpreter()84 virtual ~TrendClassifyingFilterInterpreter() {} 85 86 protected: 87 virtual void SyncInterpretImpl(HardwareState& hwstate, stime_t* timeout); 88 89 private: 90 struct KState { KStateKState91 KState() { Init(); } KStateKState92 KState(const FingerState& fs) { Init(fs); } 93 94 // Init functions called by ctors. We don't use constructors directly since 95 // we have to init classes by ourselves for MemoryManaged types. 96 void Init(); 97 void Init(const FingerState& fs); 98 99 // Element struct for tracking one finger property (e.g. x, y, pressure). 100 struct KAxis { KAxisKState::KAxis101 KAxis(): val(0.0), sum(0), ties(0), score(0), var(0.0) {} 102 InitKState::KAxis103 void Init() { 104 val = 0.0; 105 sum = 0, ties = 0; 106 score = 0; 107 var = 0.0; 108 } 109 110 // The data value to track of the finger at a given timestamp 111 float val; 112 113 // Temp values to speed up the S and Var(S) computation. For more detail, 114 // please look at the comment for UpdateKTValuePair. 115 int sum, ties; 116 117 // The S and Var(S) computed for this timestamp 118 int score; 119 double var; 120 }; 121 static const size_t n_axes_ = 6; 122 KAxis axes_[n_axes_]; 123 XAxisKState124 KAxis* XAxis() { return &axes_[0]; } DxAxisKState125 KAxis* DxAxis() { return &axes_[1]; } YAxisKState126 KAxis* YAxis() { return &axes_[2]; } DyAxisKState127 KAxis* DyAxis() { return &axes_[3]; } PressureAxisKState128 KAxis* PressureAxis() { return &axes_[4]; } TouchMajorAxisKState129 KAxis* TouchMajorAxis() { return &axes_[5]; } 130 IsDeltaKState131 static bool IsDelta(int idx) { return (idx == 1 || idx == 3); } IncFlagKState132 static unsigned IncFlag(int idx) { 133 static const unsigned flags[n_axes_] = { 134 GESTURES_FINGER_TREND_INC_X, 135 GESTURES_FINGER_TREND_INC_X, 136 GESTURES_FINGER_TREND_INC_Y, 137 GESTURES_FINGER_TREND_INC_Y, 138 GESTURES_FINGER_TREND_INC_PRESSURE, 139 GESTURES_FINGER_TREND_INC_TOUCH_MAJOR }; 140 return flags[idx]; 141 } DecFlagKState142 static unsigned DecFlag(int idx) { 143 static const unsigned flags[n_axes_] = { 144 GESTURES_FINGER_TREND_DEC_X, 145 GESTURES_FINGER_TREND_DEC_X, 146 GESTURES_FINGER_TREND_DEC_Y, 147 GESTURES_FINGER_TREND_DEC_Y, 148 GESTURES_FINGER_TREND_DEC_PRESSURE, 149 GESTURES_FINGER_TREND_DEC_TOUCH_MAJOR }; 150 return flags[idx]; 151 } 152 }; 153 154 typedef List<KState> FingerHistory; 155 156 // Trend types for internal use 157 enum TrendType { 158 TREND_NONE, 159 TREND_INCREASING, 160 TREND_DECREASING 161 }; 162 163 // Detect moving fingers and append the GESTURES_FINGER_TREND_* flags 164 void UpdateFingerState(const HardwareState& hwstate); 165 166 // Push new finger data into the buffer and update values 167 void AddNewStateToBuffer(FingerHistory& history, const FingerState& fs); 168 169 // Assess statistical significance with a classic two-tail hypothesis test 170 TrendType RunKTTest(const KState::KAxis* current, const size_t n_samples); 171 172 // Given a time-series (t1, d1), (t2, d2) .... (tn, dn), a naive 173 // implementation to compute the Kendall's S-statistic as in (1) would take 174 // O(n^2) time, which might be too much even for a moderate size of n. To 175 // speed it up, we save temp values sum_i and ties_i for each item and 176 // incrementally update them upon each new data point's arrival. For each 177 // item (ti, di), sum_i and ties_i stand for: 178 // 179 // sum_i = (# of concordant pairs w.r.t. (ti, di)) - 180 // (# of discordant pairs w.r.t. (ti, di)) 181 // ties_i = (# of other equal value items where dj == di) 182 // 183 // within the range (ti, di) .... (tn, dn). 184 // 185 // The S-statistic, C(ui, 3) and C(ui, 2) in (2) can then be computed as 186 // 187 // S = Σsum_i , C(ui, 2) = Σ ties_j 188 // i j∈i-th ties group 189 // 190 // C(ui, 3) = Σ (ties_j * (ties_j - 1) / 2) 191 // j∈i-th ties group 192 // 193 // The sum_i and ties_i can be updated in O(1) time for each item, thus 194 // reducing the total time complexity to compute S and Var(S) from O(n^2) to 195 // O(n). UpdateKTValuePair(KState::KAxis * past,KState::KAxis * current,int * t_n2_sum,int * t_n3_sum)196 inline void UpdateKTValuePair(KState::KAxis* past, KState::KAxis* current, 197 int* t_n2_sum, int* t_n3_sum) { 198 if (past->val < current->val) 199 past->sum++; 200 else if (past->val > current->val) 201 past->sum--; 202 else 203 past->ties++; 204 current->score += past->sum, (*t_n2_sum) += past->ties; 205 (*t_n3_sum) += ((past->ties * (past->ties - 1)) >> 1); 206 } 207 208 // Compute the variance of the Kendall's S-statistic according to (2) 209 double ComputeKTVariance(const int tie_n2, const int tie_n3, 210 const size_t n_samples); 211 212 // Append flag based on the test result 213 void InterpretTestResult(const TrendType trend_type, 214 const unsigned flag_increasing, 215 const unsigned flag_decreasing, 216 unsigned* flags); 217 218 // A map to store each finger's past coordinates and calculation 219 // intermediates 220 typedef std::map<short, FingerHistory> FingerHistoryMap; 221 FingerHistoryMap histories_; 222 223 // Flag to turn on/off the trend classifying filter 224 BoolProperty trend_classifying_filter_enable_; 225 226 // Flag to turn on/off the support for second order movements. Our test can 227 // capture any kind of monotonically increasing/decreasing trends, but it 228 // may fail on functions that contain extrema (e.g. a parabolic curve where 229 // the finger first moves toward the -X direction and then goes toward the 230 // +X). We can run the same test on the 1-st order differences of data to 231 // handle second order functions. Higher order functions are not considered 232 // here. 233 BoolProperty second_order_enable_; 234 235 // Minimum number of samples required (must be >= 6 for a 236 // meaningful result) 237 IntProperty min_num_of_samples_; 238 239 // Number of samples desired 240 IntProperty num_of_samples_; 241 242 // The critical z-value for the hypothesis testing. For a test statistic that 243 // follows the normal distribution, we can compute the probability as the 244 // area under the probability density function. A two-sided test may be 245 // illustrated as follows: 246 // 247 // ..|.. 248 // ..xx|xx.. Two-tailed test 249 // |xxxx|xxxx| 250 // .|xxxx|xxxx|. 251 // .. |xxxx|xxxx| .. 252 // .... |xxxx|xxxx| .... 253 // ------------------------------------------- 254 // -∞ -Zα 0 +Zα +∞ 255 // 256 // Given the desired false positive rate (α), the threshold Zα is computed 257 // so that the area in [-Zα, Zα] is 1-α and the areas in [-∞, -Zα] and 258 // [Zα, +∞] are α/2 respectively. If the z-value of test statistic locates 259 // outside of the region [-Zα, Zα], we may conclude that the instance is rare 260 // enough to demonstrate statistical significance. 261 // 262 // We provide a few sample Zα values for different α's here for reference. 263 // A custom Zα value can be readily computed by most math packages (e.g. 264 // the Python scipy). To compute Zα for a specific α (assume scipy was 265 // installed): 266 // 267 // $ python 268 // >>> from scipy.stats import norm 269 // >>> norm.interval(1 - 0.01) # This computes the interval for α = 0.01 270 // (-2.5758293035489004, 2.5758293035489004) 271 // >>> norm.interval(1 - 0.05) # This computes the interval for α = 0.05 272 // (-1.959963984540054, 1.959963984540054) 273 // 274 // The default value is chosen to correspond to the case where α = 0.01. 275 // 276 // α | two-sided test z-value 277 // ---------------------------------- 278 // 0.001 | 3.2905267314919255 279 // 0.005 | 2.8070337683438109 280 // 0.01 | 2.5758293035489004 281 // 0.02 | 2.3263478740408408 282 // 0.05 | 1.959963984540054 283 // 0.10 | 1.6448536269514722 284 // 0.20 | 1.2815515655446004 285 DoubleProperty z_threshold_; 286 }; 287 288 } 289 290 #endif 291