1/* 2** 3** Copyright 2014, The Android Open Source Project 4** 5** Licensed under the Apache License, Version 2.0 (the "License"); 6** you may not use this file except in compliance with the License. 7** You may obtain a copy of the License at 8** 9** http://www.apache.org/licenses/LICENSE-2.0 10** 11** Unless required by applicable law or agreed to in writing, software 12** distributed under the License is distributed on an "AS IS" BASIS, 13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14** See the License for the specific language governing permissions and 15** limitations under the License. 16*/ 17 18#ifndef CLOCK_ESTIMATOR_H_ 19 20#define CLOCK_ESTIMATOR_H_ 21 22 23#include <utils/RefBase.h> 24#include <utils/Vector.h> 25 26namespace android { 27// --------------------------------------------------------------------------- 28 29struct ClockEstimator : RefBase { 30 virtual double estimate(double x, double y) = 0; 31 virtual void reset() = 0; 32}; 33 34struct WindowedLinearFitEstimator : ClockEstimator { 35 struct LinearFit { 36 /** 37 * Fit y = a * x + b, where each input has a weight 38 */ 39 double mX; // sum(w_i * x_i) 40 double mXX; // sum(w_i * x_i^2) 41 double mY; // sum(w_i * y_i) 42 double mYY; // sum(w_i * y_i^2) 43 double mXY; // sum(w_i * x_i * y_i) 44 double mW; // sum(w_i) 45 46 LinearFit(); 47 void reset(); 48 void combine(const LinearFit &lf); 49 void add(double x, double y, double w); 50 void scale(double w); 51 double interpolate(double x); 52 double size() const; 53 54 DISALLOW_EVIL_CONSTRUCTORS(LinearFit); 55 }; 56 57 /** 58 * Estimator for f(x) = y' where input y' is noisy, but 59 * theoretically linear: 60 * 61 * y' =~ y = a * x + b 62 * 63 * It uses linear fit regression over a tapering rolling window 64 * to get an estimate for y (from the current and past inputs 65 * (x, y')). 66 * 67 * ____________ 68 * /| |\ 69 * / | | \ 70 * / | | \ <--- new data (x, y') 71 * / | main | \ 72 * <--><----------><--> 73 * tail head 74 * 75 * weight is 1 under the main window, tapers exponentially by 76 * the factors given in the head and the tail. 77 * 78 * Assuming that x and y' are monotonic, that x is somewhat 79 * evenly sampled, and that a =~ 1, the estimated y is also 80 * going to be monotonic. 81 */ 82 WindowedLinearFitEstimator( 83 size_t headLength = 5, double headFactor = 0.5, 84 size_t mainLength = 0, double tailFactor = 0.99); 85 86 virtual void reset(); 87 88 // add a new sample (x -> y') and return an estimated value for the true y 89 virtual double estimate(double x, double y); 90 91private: 92 Vector<double> mXHistory; // circular buffer 93 Vector<double> mYHistory; // circular buffer 94 LinearFit mHead; 95 LinearFit mMain; 96 LinearFit mTail; 97 double mHeadFactorInv; 98 double mTailFactor; 99 double mFirstWeight; 100 size_t mHistoryLength; 101 size_t mHeadLength; 102 size_t mNumSamples; 103 size_t mSampleIx; 104 105 DISALLOW_EVIL_CONSTRUCTORS(WindowedLinearFitEstimator); 106}; 107 108}; // namespace android 109 110#endif 111