diff options
Diffstat (limited to 'ml/dlib/dlib/filtering')
-rw-r--r-- | ml/dlib/dlib/filtering/kalman_filter.cpp | 104 | ||||
-rw-r--r-- | ml/dlib/dlib/filtering/kalman_filter.h | 382 | ||||
-rw-r--r-- | ml/dlib/dlib/filtering/kalman_filter_abstract.h | 492 | ||||
-rw-r--r-- | ml/dlib/dlib/filtering/rls_filter.h | 198 | ||||
-rw-r--r-- | ml/dlib/dlib/filtering/rls_filter_abstract.h | 171 |
5 files changed, 1347 insertions, 0 deletions
diff --git a/ml/dlib/dlib/filtering/kalman_filter.cpp b/ml/dlib/dlib/filtering/kalman_filter.cpp new file mode 100644 index 000000000..5d47793a9 --- /dev/null +++ b/ml/dlib/dlib/filtering/kalman_filter.cpp @@ -0,0 +1,104 @@ +// Copyright (C) 2018 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_KALMAN_FiLTER_CPp_ +#define DLIB_KALMAN_FiLTER_CPp_ + +#include "kalman_filter.h" +#include "../global_optimization.h" +#include "../statistics.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<std::vector<double>>& sequences, + const double smoothness + ) + { + DLIB_CASSERT(sequences.size() != 0); + for (auto& vals : sequences) + DLIB_CASSERT(vals.size() > 4); + DLIB_CASSERT(smoothness >= 0); + + // define the objective function we optimize to find the best filter + auto obj = [&](double measurement_noise, double typical_acceleration, double max_measurement_deviation) + { + running_stats<double> rs; + for (auto& vals : sequences) + { + momentum_filter filt(measurement_noise, typical_acceleration, max_measurement_deviation); + double prev_filt = 0; + for (size_t i = 0; i < vals.size(); ++i) + { + // we care about smoothness and fitting the data. + if (i > 0) + { + // the filter should fit the data + rs.add(std::abs(vals[i]-filt.get_predicted_next_position())); + } + double next_filt = filt(vals[i]); + if (i > 0) + { + // the filter should also output a smooth trajectory + rs.add(smoothness*std::abs(next_filt-prev_filt)); + } + prev_filt = next_filt; + } + } + return rs.mean(); + }; + + running_stats<double> avgdiff; + for (auto& vals : sequences) + { + for (size_t i = 1; i < vals.size(); ++i) + avgdiff.add(vals[i]-vals[i-1]); + } + const double scale = avgdiff.stddev(); + + function_evaluation opt = find_min_global(obj, {scale*0.01, scale*0.0001, 0.00001}, {scale*10, scale*10, 10}, max_function_calls(400)); + + momentum_filter filt(opt.x(0), opt.x(1), opt.x(2)); + + return filt; + } + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<double>& sequence, + const double smoothness + ) + { + return find_optimal_momentum_filter({1,sequence}, smoothness); + } + +// ---------------------------------------------------------------------------------------- + + rect_filter find_optimal_rect_filter ( + const std::vector<rectangle>& rects, + const double smoothness + ) + { + DLIB_CASSERT(rects.size() > 4); + DLIB_CASSERT(smoothness >= 0); + + std::vector<std::vector<double>> vals(4); + for (auto& r : rects) + { + vals[0].push_back(r.left()); + vals[1].push_back(r.top()); + vals[2].push_back(r.right()); + vals[3].push_back(r.bottom()); + } + return rect_filter(find_optimal_momentum_filter(vals, smoothness)); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_KALMAN_FiLTER_CPp_ + diff --git a/ml/dlib/dlib/filtering/kalman_filter.h b/ml/dlib/dlib/filtering/kalman_filter.h new file mode 100644 index 000000000..30289fa42 --- /dev/null +++ b/ml/dlib/dlib/filtering/kalman_filter.h @@ -0,0 +1,382 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_KALMAN_FiLTER_Hh_ +#define DLIB_KALMAN_FiLTER_Hh_ + +#include "kalman_filter_abstract.h" +#include "../matrix.h" +#include "../geometry.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + template < + long states, + long measurements + > + class kalman_filter + { + public: + + kalman_filter() + { + H = 0; + A = 0; + Q = 0; + R = 0; + x = 0; + xb = 0; + P = identity_matrix<double>(states); + got_first_meas = false; + } + + void set_observation_model ( const matrix<double,measurements,states>& H_) { H = H_; } + void set_transition_model ( const matrix<double,states,states>& A_) { A = A_; } + void set_process_noise ( const matrix<double,states,states>& Q_) { Q = Q_; } + void set_measurement_noise ( const matrix<double,measurements,measurements>& R_) { R = R_; } + void set_estimation_error_covariance( const matrix<double,states,states>& P_) { P = P_; } + void set_state ( const matrix<double,states,1>& xb_) + { + xb = xb_; + if (!got_first_meas) + { + x = xb_; + got_first_meas = true; + } + } + + const matrix<double,measurements,states>& get_observation_model ( + ) const { return H; } + + const matrix<double,states,states>& get_transition_model ( + ) const { return A; } + + const matrix<double,states,states>& get_process_noise ( + ) const { return Q; } + + const matrix<double,measurements,measurements>& get_measurement_noise ( + ) const { return R; } + + void update ( + ) + { + // propagate estimation error covariance forward + P = A*P*trans(A) + Q; + + // propagate state forward + x = xb; + xb = A*x; + } + + void update (const matrix<double,measurements,1>& z) + { + // propagate estimation error covariance forward + P = A*P*trans(A) + Q; + + // compute Kalman gain matrix + const matrix<double,states,measurements> K = P*trans(H)*pinv(H*P*trans(H) + R); + + if (got_first_meas) + { + const matrix<double,measurements,1> res = z - H*xb; + // correct the current state estimate + x = xb + K*res; + } + else + { + // Since we don't have a previous state estimate at the start of filtering, + // we will just set the current state to whatever is indicated by the measurement + x = pinv(H)*z; + got_first_meas = true; + } + + // propagate state forward in time + xb = A*x; + + // update estimation error covariance since we got a measurement. + P = (identity_matrix<double,states>() - K*H)*P; + } + + const matrix<double,states,1>& get_current_state( + ) const + { + return x; + } + + const matrix<double,states,1>& get_predicted_next_state( + ) const + { + return xb; + } + + const matrix<double,states,states>& get_current_estimation_error_covariance( + ) const + { + return P; + } + + friend inline void serialize(const kalman_filter& item, std::ostream& out) + { + int version = 1; + serialize(version, out); + serialize(item.got_first_meas, out); + serialize(item.x, out); + serialize(item.xb, out); + serialize(item.P, out); + serialize(item.H, out); + serialize(item.A, out); + serialize(item.Q, out); + serialize(item.R, out); + } + + friend inline void deserialize(kalman_filter& item, std::istream& in) + { + int version = 0; + deserialize(version, in); + if (version != 1) + throw dlib::serialization_error("Unknown version number found while deserializing kalman_filter object."); + + deserialize(item.got_first_meas, in); + deserialize(item.x, in); + deserialize(item.xb, in); + deserialize(item.P, in); + deserialize(item.H, in); + deserialize(item.A, in); + deserialize(item.Q, in); + deserialize(item.R, in); + } + + private: + + bool got_first_meas; + matrix<double,states,1> x, xb; + matrix<double,states,states> P; + + matrix<double,measurements,states> H; + matrix<double,states,states> A; + matrix<double,states,states> Q; + matrix<double,measurements,measurements> R; + + + }; + +// ---------------------------------------------------------------------------------------- + + class momentum_filter + { + public: + + momentum_filter( + double meas_noise, + double acc, + double max_meas_dev + ) : + measurement_noise(meas_noise), + typical_acceleration(acc), + max_measurement_deviation(max_meas_dev) + { + DLIB_CASSERT(meas_noise >= 0); + DLIB_CASSERT(acc >= 0); + DLIB_CASSERT(max_meas_dev >= 0); + + kal.set_observation_model({1, 0}); + kal.set_transition_model( {1, 1, + 0, 1}); + kal.set_process_noise({0, 0, + 0, typical_acceleration*typical_acceleration}); + + kal.set_measurement_noise({measurement_noise*measurement_noise}); + } + + momentum_filter() = default; + + double get_measurement_noise ( + ) const { return measurement_noise; } + + double get_typical_acceleration ( + ) const { return typical_acceleration; } + + double get_max_measurement_deviation ( + ) const { return max_measurement_deviation; } + + void reset() + { + *this = momentum_filter(measurement_noise, typical_acceleration, max_measurement_deviation); + } + + double get_predicted_next_position( + ) const + { + return kal.get_predicted_next_state()(0); + } + + double operator()( + const double measured_position + ) + { + auto x = kal.get_predicted_next_state(); + const auto max_deviation = max_measurement_deviation*measurement_noise; + // Check if measured_position has suddenly jumped in value by a whole lot. This + // could happen if the velocity term experiences a much larger than normal + // acceleration, e.g. because the underlying object is doing a maneuver. If + // this happens then we clamp the state so that the predicted next value is no + // more than max_deviation away from measured_position at all times. + if (x(0) > measured_position + max_deviation) + { + x(0) = measured_position + max_deviation; + kal.set_state(x); + } + else if (x(0) < measured_position - max_deviation) + { + x(0) = measured_position - max_deviation; + kal.set_state(x); + } + + kal.update({measured_position}); + + return kal.get_current_state()(0); + } + + friend std::ostream& operator << (std::ostream& out, const momentum_filter& item) + { + out << "measurement_noise: " << item.measurement_noise << "\n"; + out << "typical_acceleration: " << item.typical_acceleration << "\n"; + out << "max_measurement_deviation: " << item.max_measurement_deviation; + return out; + } + + friend void serialize(const momentum_filter& item, std::ostream& out) + { + int version = 15; + serialize(version, out); + serialize(item.measurement_noise, out); + serialize(item.typical_acceleration, out); + serialize(item.max_measurement_deviation, out); + serialize(item.kal, out); + } + + friend void deserialize(momentum_filter& item, std::istream& in) + { + int version = 0; + deserialize(version, in); + if (version != 15) + throw serialization_error("Unexpected version found while deserializing momentum_filter."); + deserialize(item.measurement_noise, in); + deserialize(item.typical_acceleration, in); + deserialize(item.max_measurement_deviation, in); + deserialize(item.kal, in); + } + + private: + + double measurement_noise = 2; + double typical_acceleration = 0.1; + double max_measurement_deviation = 3; // nominally number of standard deviations + + kalman_filter<2,1> kal; + }; + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<std::vector<double>>& sequences, + const double smoothness = 1 + ); + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<double>& sequence, + const double smoothness = 1 + ); + +// ---------------------------------------------------------------------------------------- + + class rect_filter + { + public: + rect_filter() = default; + + rect_filter( + double meas_noise, + double acc, + double max_meas_dev + ) : rect_filter(momentum_filter(meas_noise, acc, max_meas_dev)) {} + + rect_filter( + const momentum_filter& filt + ) : + left(filt), + top(filt), + right(filt), + bottom(filt) + { + } + + drectangle operator()(const drectangle& r) + { + return drectangle(left(r.left()), + top(r.top()), + right(r.right()), + bottom(r.bottom())); + } + + drectangle operator()(const rectangle& r) + { + return drectangle(left(r.left()), + top(r.top()), + right(r.right()), + bottom(r.bottom())); + } + + const momentum_filter& get_left () const { return left; } + momentum_filter& get_left () { return left; } + const momentum_filter& get_top () const { return top; } + momentum_filter& get_top () { return top; } + const momentum_filter& get_right () const { return right; } + momentum_filter& get_right () { return right; } + const momentum_filter& get_bottom () const { return bottom; } + momentum_filter& get_bottom () { return bottom; } + + friend void serialize(const rect_filter& item, std::ostream& out) + { + int version = 123; + serialize(version, out); + serialize(item.left, out); + serialize(item.top, out); + serialize(item.right, out); + serialize(item.bottom, out); + } + + friend void deserialize(rect_filter& item, std::istream& in) + { + int version = 0; + deserialize(version, in); + if (version != 123) + throw dlib::serialization_error("Unknown version number found while deserializing rect_filter object."); + deserialize(item.left, in); + deserialize(item.top, in); + deserialize(item.right, in); + deserialize(item.bottom, in); + } + + private: + + momentum_filter left, top, right, bottom; + }; + +// ---------------------------------------------------------------------------------------- + + rect_filter find_optimal_rect_filter ( + const std::vector<rectangle>& rects, + const double smoothness = 1 + ); + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_KALMAN_FiLTER_Hh_ + diff --git a/ml/dlib/dlib/filtering/kalman_filter_abstract.h b/ml/dlib/dlib/filtering/kalman_filter_abstract.h new file mode 100644 index 000000000..cdac2c569 --- /dev/null +++ b/ml/dlib/dlib/filtering/kalman_filter_abstract.h @@ -0,0 +1,492 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_KALMAN_FiLTER_ABSTRACT_Hh_ +#ifdef DLIB_KALMAN_FiLTER_ABSTRACT_Hh_ + +#include "../serialize.h" +#include "../matrix.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + template < + long states, + long measurements + > + class kalman_filter + { + /*! + REQUIREMENTS ON states + states > 0 + + REQUIREMENTS ON measurements + measurements > 0 + + WHAT THIS OBJECT REPRESENTS + This object implements the Kalman filter, which is a tool for + recursively estimating the state of a process given measurements + related to that process. To use this tool you will have to + be familiar with the workings of the Kalman filter. An excellent + introduction can be found in the paper: + An Introduction to the Kalman Filter + by Greg Welch and Gary Bishop + + !*/ + + public: + + kalman_filter( + ); + /*! + - #get_observation_model() == 0 + - #get_transition_model() == 0 + - #get_process_noise() == 0 + - #get_measurement_noise() == 0 + - #get_current_state() == 0 + - #get_predicted_next_state() == 0 + - #get_current_estimation_error_covariance() == the identity matrix + !*/ + + void set_observation_model ( + const matrix<double,measurements,states>& H + ); + /*! + ensures + - #get_observation_model() == H + !*/ + + void set_transition_model ( + const matrix<double,states,states>& A + ); + /*! + ensures + - #get_transition_model() == A + !*/ + + void set_process_noise ( + const matrix<double,states,states>& Q + ); + /*! + ensures + - #get_process_noise() == Q + !*/ + + void set_measurement_noise ( + const matrix<double,measurements,measurements>& R + ); + /*! + ensures + - #get_measurement_noise() == R + !*/ + + void set_estimation_error_covariance ( + const matrix<double,states,states>& P + ); + /*! + ensures + - #get_current_estimation_error_covariance() == P + (Note that you should only set this before you start filtering + since the Kalman filter will maintain the value of P on its own. + So only set this during initialization unless you are sure you + understand what you are doing.) + !*/ + + void set_state ( + const matrix<double,states,1>& xb + ); + /*! + ensures + - This function can be used when the initial state is known, or if the + state needs to be corrected before the next update(). + - #get_predicted_next_state() == xb + - If (update() hasn't been called yet) then + - #get_current_state() == xb + !*/ + + const matrix<double,measurements,states>& get_observation_model ( + ) const; + /*! + ensures + - Returns the matrix "H" which relates process states x to measurements z. + The relation is linear, therefore, z = H*x. That is, multiplying a + state by H gives the measurement you expect to observe for that state. + !*/ + + const matrix<double,states,states>& get_transition_model ( + ) const; + /*! + ensures + - Returns the matrix "A" which determines how process states change over time. + The relation is linear, therefore, given a state vector x, the value you + expect it to have at the next time step is A*x. + !*/ + + const matrix<double,states,states>& get_process_noise ( + ) const; + /*! + ensures + - returns the process noise covariance matrix. You can think of this + covariance matrix as a measure of how wrong the assumption of + linear state transitions is. + !*/ + + const matrix<double,measurements,measurements>& get_measurement_noise ( + ) const; + /*! + ensures + - returns the measurement noise covariance matrix. That is, when we + measure a state x we only obtain H*x corrupted by Gaussian noise. + The measurement noise is the covariance matrix of this Gaussian + noise which corrupts our measurements. + !*/ + + void update ( + ); + /*! + ensures + - propagates the current state estimate forward in time one + time step. In particular: + - #get_current_state() == get_predicted_next_state() + - #get_predicted_next_state() == get_transition_model()*get_current_state() + - #get_current_estimation_error_covariance() == the propagated value of this covariance matrix + !*/ + + void update ( + const matrix<double,measurements,1>& z + ); + /*! + ensures + - propagates the current state estimate forward in time one time step. + Also applies a correction based on the given measurement z. In particular: + - #get_current_state(), #get_predicted_next_state(), and + #get_current_estimation_error_covariance() are updated using the + Kalman filter method based on the new measurement in z. + !*/ + + const matrix<double,states,1>& get_current_state( + ) const; + /*! + ensures + - returns the current estimate of the state of the process. This + estimate is based on all the measurements supplied to the update() + method. + !*/ + + const matrix<double,states,1>& get_predicted_next_state( + ) const; + /*! + ensures + - returns the next expected value of the process state. + - Specifically, returns get_transition_model()*get_current_state() + + !*/ + + const matrix<double,states,states>& get_current_estimation_error_covariance( + ) const; + /*! + ensures + - returns the current state error estimation covariance matrix. + This matrix captures our uncertainty about the value of get_current_state(). + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + void serialize ( + const kalman_filter& item, + std::ostream& out + ); + /*! + provides serialization support + !*/ + + void deserialize ( + kalman_filter& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + class momentum_filter + { + /*! + WHAT THIS OBJECT REPRESENTS + This object is a simple tool for filtering a single scalar value that + measures the location of a moving object that has some non-trivial + momentum. Importantly, the measurements are noisy and the object can + experience sudden unpredictable accelerations. To accomplish this + filtering we use a simple Kalman filter with a state transition model of: + + position_{i+1} = position_{i} + velocity_{i} + velocity_{i+1} = velocity_{i} + some_unpredictable_acceleration + + and a measurement model of: + + measured_position_{i} = position_{i} + measurement_noise + + Where some_unpredictable_acceleration and measurement_noise are 0 mean Gaussian + noise sources with standard deviations of get_typical_acceleration() and + get_measurement_noise() respectively. + + To allow for really sudden and large but infrequent accelerations, at each + step we check if the current measured position deviates from the predicted + filtered position by more than get_max_measurement_deviation()*get_measurement_noise() + and if so we adjust the filter's state to keep it within these bounds. + This allows the moving object to undergo large unmodeled accelerations, far + in excess of what would be suggested by get_typical_acceleration(), without + then experiencing a long lag time where the Kalman filter has to "catch + up" to the new position. + !*/ + + public: + + momentum_filter( + ) = default; + /*! + ensures + - #get_measurement_noise() == 2 + - #get_typical_acceleration() == 0.1 + - #get_max_measurement_deviation() == 3 + !*/ + + momentum_filter( + double meas_noise, + double acc, + double max_meas_dev + ); + /*! + requires + - meas_noise >= 0 + - acc >= 0 + - max_meas_dev >= 0 + ensures + - #get_measurement_noise() == meas_noise + - #get_typical_acceleration() == acc + - #get_max_measurement_deviation() == max_meas_dev + !*/ + + + double get_measurement_noise ( + ) const; + /*! + ensures + - Returns the standard deviation of the 0 mean Gaussian noise that corrupts + measurements of the moving object. + !*/ + + double get_typical_acceleration ( + ) const; + /*! + ensures + - We assume that the moving object experiences random accelerations that + are distributed by 0 mean Gaussian noise with get_typical_acceleration() + standard deviation. + !*/ + + double get_max_measurement_deviation ( + ) const; + /*! + ensures + - This object will never let the filtered location of the object deviate + from the measured location by much more than + get_max_measurement_deviation()*get_measurement_noise(). + !*/ + + void reset( + ); + /*! + ensures + - Returns this object to the state immediately after construction. To be precise, we do: + *this = momentum_filter(get_measurement_noise(), get_typical_acceleration(), get_max_measurement_deviation()); + !*/ + + double operator()( + const double measured_position + ); + /*! + ensures + - Updates the Kalman filter with the new measured position of the object + and returns the new filtered estimate of the object's position, now that + we have seen the latest measured position. + - #get_predicted_next_position() == the prediction for the *next* place we + will see the object. That is, where we think it will be in the future + rather than where it is now. + !*/ + + double get_predicted_next_position ( + ) const; + /*! + ensures + - Returns the Kalman filter's estimate of the next position we will see the object. + !*/ + }; + + std::ostream& operator << (std::ostream& out, const momentum_filter& item); + void serialize(const momentum_filter& item, std::ostream& out); + void deserialize(momentum_filter& item, std::istream& in); + /*! + Provide printing and serialization support. + !*/ + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<std::vector<double>>& sequences, + const double smoothness = 1 + ); + /*! + requires + - sequences.size() != 0 + - for all valid i: sequences[i].size() > 4 + - smoothness >= 0 + ensures + - This function finds the "optimal" settings of a momentum_filter based on + recorded measurement data stored in sequences. Here we assume that each + vector in sequences is a complete track history of some object's measured + positions. What we do is find the momentum_filter that minimizes the + following objective function: + sum of abs(predicted_location[i] - measured_location[i]) + smoothness*abs(filtered_location[i]-filtered_location[i-1]) + Where i is a time index. + The sum runs over all the data in sequences. So what we do is find the + filter settings that produce smooth filtered trajectories but also produce + filtered outputs that are as close to the measured positions as possible. + The larger the value of smoothness the less jittery the filter outputs will + be, but they might become biased or laggy if smoothness is set really high. + !*/ + +// ---------------------------------------------------------------------------------------- + + momentum_filter find_optimal_momentum_filter ( + const std::vector<double>& sequence, + const double smoothness = 1 + ); + /*! + requires + - sequence.size() > 4 + - smoothness >= 0 + ensures + - performs: find_optimal_momentum_filter({1,sequence}, smoothness); + !*/ + +// ---------------------------------------------------------------------------------------- + + class rect_filter + { + /*! + WHAT THIS OBJECT REPRESENTS + This object simply contains four momentum_filters and applies them to the + 4 components of a dlib::rectangle's position. It therefore allows you to + easily filter a sequence of rectangles. For instance, it can be used to + smooth the output of an object detector running on a video. + !*/ + + public: + rect_filter( + ) = default; + /*! + ensures + - The four momentum_filters in this object are default initialized. + !*/ + + rect_filter( + const momentum_filter& filt + ); + /*! + ensures + - #get_left() == filt + - #get_top() == filt + - #get_right() == filt + - #get_bottom() == filt + !*/ + + rect_filter( + double meas_noise, + double acc, + double max_meas_dev + ) : rect_filter(momentum_filter(meas_noise, acc, max_meas_dev)) {} + /*! + requires + - meas_noise >= 0 + - acc >= 0 + - max_meas_dev >= 0 + ensures + - Initializes this object with momentum_filter(meas_noise, acc, max_meas_dev) + !*/ + + drectangle operator()( + const drectangle& r + ); + /*! + ensures + - Runs the given rectangle through the momentum_filters and returns the + filtered rectangle location. That is, performs: + return drectangle(get_left()(r.left()), + get_top()(r.top()), + get_right()(r.right()), + get_bottom()(r.bottom())); + !*/ + + drectangle operator()( + const rectangle& r + ); + /*! + ensures + - Runs the given rectangle through the momentum_filters and returns the + filtered rectangle location. That is, performs: + return drectangle(get_left()(r.left()), + get_top()(r.top()), + get_right()(r.right()), + get_bottom()(r.bottom())); + !*/ + + const momentum_filter& get_left() const; + momentum_filter& get_left(); + const momentum_filter& get_top() const; + momentum_filter& get_top(); + const momentum_filter& get_right() const; + momentum_filter& get_right(); + const momentum_filter& get_bottom() const; + momentum_filter& get_bottom(); + /*! + Provides access to the 4 momentum_filters used to filter the 4 coordinates that define a rectangle. + !*/ + }; + + void serialize(const rect_filter& item, std::ostream& out); + void deserialize(rect_filter& item, std::istream& in); + /*! + Provide serialization support. + !*/ + +// ---------------------------------------------------------------------------------------- + + rect_filter find_optimal_rect_filter ( + const std::vector<rectangle>& rects, + const double smoothness = 1 + ); + /*! + requires + - rects.size() > 4 + - smoothness >= 0 + ensures + - This routine simply invokes find_optimal_momentum_filter() to find the + momentum_filter that works best on the provided sequence of rectangles. It + then constructs a rect_filter using that momentum_filter and returns it. + Therefore, this routine finds the rect_filter that is "optimal" for filtering + the given sequence of rectangles. + !*/ + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_KALMAN_FiLTER_ABSTRACT_Hh_ + + diff --git a/ml/dlib/dlib/filtering/rls_filter.h b/ml/dlib/dlib/filtering/rls_filter.h new file mode 100644 index 000000000..4481ab3f4 --- /dev/null +++ b/ml/dlib/dlib/filtering/rls_filter.h @@ -0,0 +1,198 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_RLS_FiLTER_Hh_ +#define DLIB_RLS_FiLTER_Hh_ + +#include "rls_filter_abstract.h" +#include "../svm/rls.h" +#include <vector> +#include "../matrix.h" +#include "../sliding_buffer.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + class rls_filter + { + /*! + CONVENTION + - data.size() == the number of variables in a measurement + - data[i].size() == data[j].size() for all i and j. + - data[i].size() == get_window_size() + - data[i][0] == most recent measurement of i-th variable given to update. + - data[i].back() == oldest measurement of i-th variable given to update + (or zero if we haven't seen this much data yet). + + - if (count <= 2) then + - count == number of times update(z) has been called + !*/ + public: + + rls_filter() + { + size = 5; + count = 0; + filter = rls(0.8, 100); + } + + explicit rls_filter ( + unsigned long size_, + double forget_factor = 0.8, + double C = 100 + ) + { + // make sure requires clause is not broken + DLIB_ASSERT(0 < forget_factor && forget_factor <= 1 && + 0 < C && size_ >= 2, + "\t rls_filter::rls_filter()" + << "\n\t invalid arguments were given to this function" + << "\n\t forget_factor: " << forget_factor + << "\n\t C: " << C + << "\n\t size_: " << size_ + << "\n\t this: " << this + ); + + size = size_; + count = 0; + filter = rls(forget_factor, C); + } + + double get_c( + ) const + { + return filter.get_c(); + } + + double get_forget_factor( + ) const + { + return filter.get_forget_factor(); + } + + unsigned long get_window_size ( + ) const + { + return size; + } + + void update ( + ) + { + if (filter.get_w().size() == 0) + return; + + for (unsigned long i = 0; i < data.size(); ++i) + { + // Put old predicted value into the circular buffer as if it was + // the measurement we just observed. But don't update the rls filter. + data[i].push_front(next(i)); + } + + // predict next state + for (long i = 0; i < next.size(); ++i) + next(i) = filter(mat(data[i])); + } + + template <typename EXP> + void update ( + const matrix_exp<EXP>& z + ) + { + // make sure requires clause is not broken + DLIB_ASSERT(is_col_vector(z) == true && + z.size() != 0 && + (get_predicted_next_state().size()==0 || z.size()==get_predicted_next_state().size()), + "\t void rls_filter::update(z)" + << "\n\t invalid arguments were given to this function" + << "\n\t is_col_vector(z): " << is_col_vector(z) + << "\n\t z.size(): " << z.size() + << "\n\t get_predicted_next_state().size(): " << get_predicted_next_state().size() + << "\n\t this: " << this + ); + + // initialize data if necessary + if (data.size() == 0) + { + data.resize(z.size()); + for (long i = 0; i < z.size(); ++i) + data[i].assign(size, 0); + } + + + for (unsigned long i = 0; i < data.size(); ++i) + { + // Once there is some stuff in the circular buffer, start + // showing it to the rls filter so it can do its thing. + if (count >= 2) + { + filter.train(mat(data[i]), z(i)); + } + + // keep track of the measurements in our circular buffer + data[i].push_front(z(i)); + } + + // Don't bother with the filter until we have seen two samples + if (count >= 2) + { + // predict next state + for (long i = 0; i < z.size(); ++i) + next(i) = filter(mat(data[i])); + } + else + { + // Use current measurement as the next state prediction + // since we don't know any better at this point. + ++count; + next = matrix_cast<double>(z); + } + } + + const matrix<double,0,1>& get_predicted_next_state( + ) const + { + return next; + } + + friend inline void serialize(const rls_filter& item, std::ostream& out) + { + int version = 1; + serialize(version, out); + serialize(item.count, out); + serialize(item.size, out); + serialize(item.filter, out); + serialize(item.next, out); + serialize(item.data, out); + } + + friend inline void deserialize(rls_filter& item, std::istream& in) + { + int version = 0; + deserialize(version, in); + if (version != 1) + throw dlib::serialization_error("Unknown version number found while deserializing rls_filter object."); + + deserialize(item.count, in); + deserialize(item.size, in); + deserialize(item.filter, in); + deserialize(item.next, in); + deserialize(item.data, in); + } + + private: + + unsigned long count; + unsigned long size; + rls filter; + matrix<double,0,1> next; + std::vector<circular_buffer<double> > data; + }; + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_RLS_FiLTER_Hh_ + diff --git a/ml/dlib/dlib/filtering/rls_filter_abstract.h b/ml/dlib/dlib/filtering/rls_filter_abstract.h new file mode 100644 index 000000000..0a932cb87 --- /dev/null +++ b/ml/dlib/dlib/filtering/rls_filter_abstract.h @@ -0,0 +1,171 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_RLS_FiLTER_ABSTRACT_Hh_ +#ifdef DLIB_RLS_FiLTER_ABSTRACT_Hh_ + +#include "../svm/rls_abstract.h" +#include "../matrix/matrix_abstract.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + class rls_filter + { + /*! + WHAT THIS OBJECT REPRESENTS + This object is a tool for doing time series prediction using linear + recursive least squares. In particular, this object takes a sequence + of points from the user and, at each step, attempts to predict the + value of the next point. + + To accomplish this, this object maintains a fixed size buffer of recent + points. Each prediction is a linear combination of the points in this + history buffer. It uses the recursive least squares algorithm to + determine how to best combine the contents of the history buffer to + predict each point. Therefore, each time update() is called with + a point, recursive least squares updates the linear combination weights, + and then it inserts the point into the history buffer. After that, the + next prediction is based on these updated weights and the current history + buffer. + !*/ + + public: + + rls_filter( + ); + /*! + ensures + - #get_window_size() == 5 + - #get_forget_factor() == 0.8 + - #get_c() == 100 + - #get_predicted_next_state().size() == 0 + !*/ + + explicit rls_filter ( + unsigned long size, + double forget_factor = 0.8, + double C = 100 + ); + /*! + requires + - 0 < forget_factor <= 1 + - 0 < C + - size >= 2 + ensures + - #get_window_size() == size + - #get_forget_factor() == forget_factor + - #get_c() == C + - #get_predicted_next_state().size() == 0 + !*/ + + double get_c( + ) const; + /*! + ensures + - returns the regularization parameter. It is the parameter that determines + the trade-off between trying to fit the data points given to update() or + allowing more errors but hopefully improving the generalization of the + predictions. Larger values encourage exact fitting while smaller values + of C may encourage better generalization. + !*/ + + double get_forget_factor( + ) const; + /*! + ensures + - This object uses exponential forgetting in its implementation of recursive + least squares. Therefore, this function returns the "forget factor". + - if (get_forget_factor() == 1) then + - In this case, exponential forgetting is disabled. + - The recursive least squares algorithm will implicitly take all previous + calls to update(z) into account when estimating the optimal weights for + linearly combining the history buffer into a prediction of the next point. + - else + - Old calls to update(z) are eventually forgotten. That is, the smaller + the forget factor, the less recursive least squares will care about + attempting to find linear combination weights which would have make + good predictions on old points. It will care more about fitting recent + points. This is appropriate if the statistical properties of the time + series we are modeling are not constant. + !*/ + + unsigned long get_window_size ( + ) const; + /*! + ensures + - returns the size of the history buffer. This is the number of points which + are linearly combine to make the predictions returned by get_predicted_next_state(). + !*/ + + void update ( + ); + /*! + ensures + - Propagates the prediction forward in time. + - In particular, the value in get_predicted_next_state() is inserted + into the history buffer and then the next prediction is estimated + based on this updated history buffer. + - #get_predicted_next_state() == the prediction for the next point + in the time series. + !*/ + + template <typename EXP> + void update ( + const matrix_exp<EXP>& z + ); + /*! + requires + - is_col_vector(z) == true + - z.size() != 0 + - if (get_predicted_next_state().size() != 0) then + - z.size() == get_predicted_next_state().size() + (i.e. z must be the same size as all the previous z values given + to this function) + ensures + - Updates the state of this filter based on the current measurement in z. + - In particular, the filter weights are updated and z is inserted into + the history buffer. Then the next prediction is estimated based on + these updated weights and history buffer. + - #get_predicted_next_state() == the prediction for the next point + in the time series. + - #get_predicted_next_state().size() == z.size() + !*/ + + const matrix<double,0,1>& get_predicted_next_state( + ) const; + /*! + ensures + - returns the estimate of the next point we will observe in the + time series data. + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + void serialize ( + const rls_filter& item, + std::ostream& out + ); + /*! + provides serialization support + !*/ + + void deserialize ( + rls_filter& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ + +// ---------------------------------------------------------------------------------------- + + +} + +#endif // DLIB_RLS_FiLTER_ABSTRACT_Hh_ + + |