1 /*
2  *  Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
3  *
4  *  Use of this source code is governed by a BSD-style license
5  *  that can be found in the LICENSE file in the root of the source
6  *  tree. An additional intellectual property rights grant can be found
7  *  in the file PATENTS.  All contributing project authors may
8  *  be found in the AUTHORS file in the root of the source tree.
9  */
10 
11 #ifndef RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
12 #define RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
13 
14 #include <stddef.h>
15 
16 #include <cstddef>
17 #include <list>
18 
19 #include "rtc_base/checks.h"
20 #include "rtc_base/constructor_magic.h"
21 #include "rtc_base/numerics/percentile_filter.h"
22 
23 namespace webrtc {
24 
25 // Class to efficiently get moving median filter from a stream of samples.
26 template <typename T>
27 class MovingMedianFilter {
28  public:
29   // Construct filter. |window_size| is how many latest samples are stored and
30   // used to take median. |window_size| must be positive.
31   explicit MovingMedianFilter(size_t window_size);
32 
33   // Insert a new sample.
34   void Insert(const T& value);
35 
36   // Removes all samples;
37   void Reset();
38 
39   // Get median over the latest window.
40   T GetFilteredValue() const;
41 
42   // The number of samples that are currently stored.
43   size_t GetNumberOfSamplesStored() const;
44 
45  private:
46   PercentileFilter<T> percentile_filter_;
47   std::list<T> samples_;
48   size_t samples_stored_;
49   const size_t window_size_;
50 
51   RTC_DISALLOW_COPY_AND_ASSIGN(MovingMedianFilter);
52 };
53 
54 template <typename T>
MovingMedianFilter(size_t window_size)55 MovingMedianFilter<T>::MovingMedianFilter(size_t window_size)
56     : percentile_filter_(0.5f), samples_stored_(0), window_size_(window_size) {
57   RTC_CHECK_GT(window_size, 0);
58 }
59 
60 template <typename T>
Insert(const T & value)61 void MovingMedianFilter<T>::Insert(const T& value) {
62   percentile_filter_.Insert(value);
63   samples_.emplace_back(value);
64   ++samples_stored_;
65   if (samples_stored_ > window_size_) {
66     percentile_filter_.Erase(samples_.front());
67     samples_.pop_front();
68     --samples_stored_;
69   }
70 }
71 
72 template <typename T>
GetFilteredValue()73 T MovingMedianFilter<T>::GetFilteredValue() const {
74   return percentile_filter_.GetPercentileValue();
75 }
76 
77 template <typename T>
Reset()78 void MovingMedianFilter<T>::Reset() {
79   percentile_filter_.Reset();
80   samples_.clear();
81   samples_stored_ = 0;
82 }
83 
84 template <typename T>
GetNumberOfSamplesStored()85 size_t MovingMedianFilter<T>::GetNumberOfSamplesStored() const {
86   return samples_stored_;
87 }
88 
89 }  // namespace webrtc
90 #endif  // RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
91