Add MovingMedianFilter to rtc_base/numerics
This class will be used for filtering remote clock offset in rtp streams.
It is a separate wrapper around PercentileFilter because it will be used
in that form in several places.
Bug: webrtc:8468
Change-Id: If1f6c38ac1ffa02232c1aed5512b92878b1c346a
Reviewed-on: https://webrtc-review.googlesource.com/17841
Commit-Queue: Ilya Nikolaevskiy <ilnik@webrtc.org>
Reviewed-by: Tommi <tommi@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#20531}diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 775fd14..400efb6 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -402,6 +402,7 @@
sources = [
"numerics/exp_filter.cc",
"numerics/exp_filter.h",
+ "numerics/moving_median_filter.h",
"numerics/percentile_filter.h",
"numerics/sequence_number_util.h",
]
@@ -997,6 +998,7 @@
}
sources = [
"numerics/exp_filter_unittest.cc",
+ "numerics/moving_median_filter_unittest.cc",
"numerics/percentile_filter_unittest.cc",
"numerics/sequence_number_util_unittest.cc",
]
diff --git a/rtc_base/numerics/moving_median_filter.h b/rtc_base/numerics/moving_median_filter.h
new file mode 100644
index 0000000..4b42d4a
--- /dev/null
+++ b/rtc_base/numerics/moving_median_filter.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
+#define RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
+
+#include <list>
+
+#include "rtc_base/checks.h"
+#include "rtc_base/constructormagic.h"
+#include "rtc_base/numerics/percentile_filter.h"
+
+namespace webrtc {
+
+// Class to efficiently get moving median filter from a stream of samples.
+template <typename T>
+class MovingMedianFilter {
+ public:
+ // Construct filter. |window_size| is how many latest samples are stored and
+ // used to take median. |window_size| must be positive.
+ explicit MovingMedianFilter(size_t window_size);
+
+ // Insert a new sample.
+ void Insert(const T& value);
+
+ // Get median over the latest window.
+ T GetFilteredValue() const;
+
+ private:
+ PercentileFilter<T> percentile_filter_;
+ std::list<T> samples_;
+ size_t samples_stored_;
+ const size_t window_size_;
+
+ RTC_DISALLOW_COPY_AND_ASSIGN(MovingMedianFilter);
+};
+
+template <typename T>
+MovingMedianFilter<T>::MovingMedianFilter(size_t window_size)
+ : percentile_filter_(0.5f), samples_stored_(0), window_size_(window_size) {
+ RTC_CHECK_GT(window_size, 0);
+}
+
+template <typename T>
+void MovingMedianFilter<T>::Insert(const T& value) {
+ percentile_filter_.Insert(value);
+ samples_.emplace_back(value);
+ ++samples_stored_;
+ if (samples_stored_ > window_size_) {
+ percentile_filter_.Erase(samples_.front());
+ samples_.pop_front();
+ --samples_stored_;
+ }
+}
+
+template <typename T>
+T MovingMedianFilter<T>::GetFilteredValue() const {
+ return percentile_filter_.GetPercentileValue();
+}
+
+} // namespace webrtc
+#endif // RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
diff --git a/rtc_base/numerics/moving_median_filter_unittest.cc b/rtc_base/numerics/moving_median_filter_unittest.cc
new file mode 100644
index 0000000..5a6eb3d
--- /dev/null
+++ b/rtc_base/numerics/moving_median_filter_unittest.cc
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2017 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "rtc_base/numerics/moving_median_filter.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+
+TEST(MovingMedianFilterTest, ProcessesNoSamples) {
+ MovingMedianFilter<int> filter(2);
+ EXPECT_EQ(0, filter.GetFilteredValue());
+}
+
+TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow5) {
+ MovingMedianFilter<int> filter(5);
+ const int64_t kSamples[5] = {1, 5, 2, 3, 4};
+ const int64_t kExpectedFilteredValues[5] = {1, 1, 2, 2, 3};
+ for (int i = 0; i < 5; ++i) {
+ filter.Insert(kSamples[i]);
+ EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue());
+ }
+}
+
+TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow3) {
+ MovingMedianFilter<int> filter(3);
+ const int64_t kSamples[5] = {1, 5, 2, 3, 4};
+ const int64_t kExpectedFilteredValues[5] = {1, 1, 2, 3, 3};
+ for (int i = 0; i < 5; ++i) {
+ filter.Insert(kSamples[i]);
+ EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue());
+ }
+}
+
+TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow1) {
+ MovingMedianFilter<int> filter(1);
+ const int64_t kSamples[5] = {1, 5, 2, 3, 4};
+ const int64_t kExpectedFilteredValues[5] = {1, 5, 2, 3, 4};
+ for (int i = 0; i < 5; ++i) {
+ filter.Insert(kSamples[i]);
+ EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue());
+ }
+}
+
+} // namespace webrtc
