Generalize MovingMedianFilter to MovingPercentileFilter
* Make `percentile` configurable and rename class.
* Introduce convenience type `MovingMedianFilter` that
maintains the behaviour of the old class with that name.
* Move home grown moving 95th percentile filter in
`JitterEstimator` to this new utility class.
Bug: webrtc:14151
Change-Id: I17d525b6e0bc98c28568c7dfe94b72eeab4a1ca2
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/275311
Commit-Queue: Rasmus Brandt <brandtr@webrtc.org>
Reviewed-by: Åsa Persson <asapersson@webrtc.org>
Reviewed-by: Philip Eliasson <philipel@webrtc.org>
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Cr-Commit-Position: refs/heads/main@{#38082}
diff --git a/modules/rtp_rtcp/include/remote_ntp_time_estimator.h b/modules/rtp_rtcp/include/remote_ntp_time_estimator.h
index e45ee39..01d0c85 100644
--- a/modules/rtp_rtcp/include/remote_ntp_time_estimator.h
+++ b/modules/rtp_rtcp/include/remote_ntp_time_estimator.h
@@ -16,7 +16,7 @@
#include "absl/types/optional.h"
#include "api/units/time_delta.h"
#include "api/units/timestamp.h"
-#include "rtc_base/numerics/moving_median_filter.h"
+#include "rtc_base/numerics/moving_percentile_filter.h"
#include "system_wrappers/include/rtp_to_ntp_estimator.h"
namespace webrtc {
diff --git a/modules/video_coding/timing/jitter_estimator.cc b/modules/video_coding/timing/jitter_estimator.cc
index f5d6fdf..cc8680c 100644
--- a/modules/video_coding/timing/jitter_estimator.cc
+++ b/modules/video_coding/timing/jitter_estimator.cc
@@ -92,7 +92,9 @@
config_.frame_size_window.value_or(kDefaultFrameSizeWindow))),
max_frame_size_bytes_percentile_(
config_.max_frame_size_percentile.value_or(
- kDefaultMaxFrameSizePercentile)),
+ kDefaultMaxFrameSizePercentile),
+ static_cast<size_t>(
+ config_.frame_size_window.value_or(kDefaultFrameSizeWindow))),
fps_counter_(30), // TODO(sprang): Use an estimator with limit based
// on time, rather than number of samples.
clock_(clock) {
@@ -108,7 +110,6 @@
var_frame_size_bytes2_ = 100;
avg_frame_size_median_bytes_.Reset();
max_frame_size_bytes_percentile_.Reset();
- frame_sizes_in_percentile_filter_ = std::queue<int64_t>();
last_update_time_ = absl::nullopt;
prev_estimate_ = absl::nullopt;
prev_frame_size_ = absl::nullopt;
@@ -168,14 +169,6 @@
avg_frame_size_median_bytes_.Insert(frame_size.bytes());
}
if (config_.MaxFrameSizePercentileEnabled()) {
- frame_sizes_in_percentile_filter_.push(frame_size.bytes());
- if (frame_sizes_in_percentile_filter_.size() >
- static_cast<size_t>(
- config_.frame_size_window.value_or(kDefaultFrameSizeWindow))) {
- max_frame_size_bytes_percentile_.Erase(
- frame_sizes_in_percentile_filter_.front());
- frame_sizes_in_percentile_filter_.pop();
- }
max_frame_size_bytes_percentile_.Insert(frame_size.bytes());
}
@@ -232,12 +225,16 @@
// delayed. The next frame is of normal size (delta frame), and thus deltaFS
// will be << 0. This removes all frame samples which arrives after a key
// frame.
- double max_frame_size_bytes = GetMaxFrameSizeEstimateBytes();
+ double filtered_max_frame_size_bytes =
+ config_.MaxFrameSizePercentileEnabled()
+ ? max_frame_size_bytes_percentile_.GetFilteredValue()
+ : max_frame_size_bytes_;
if (delta_frame_bytes >
- GetCongestionRejectionFactor() * max_frame_size_bytes) {
+ GetCongestionRejectionFactor() * filtered_max_frame_size_bytes) {
// Update the Kalman filter with the new data
kalman_filter_.PredictAndUpdate(frame_delay.ms(), delta_frame_bytes,
- max_frame_size_bytes, var_noise_ms2_);
+ filtered_max_frame_size_bytes,
+ var_noise_ms2_);
}
} else {
double num_stddev = (delay_deviation_ms >= 0) ? num_stddev_delay_outlier
@@ -268,16 +265,6 @@
return config_;
}
-double JitterEstimator::GetMaxFrameSizeEstimateBytes() const {
- if (config_.MaxFrameSizePercentileEnabled()) {
- RTC_DCHECK_GT(frame_sizes_in_percentile_filter_.size(), 1u);
- RTC_DCHECK_LE(frame_sizes_in_percentile_filter_.size(),
- config_.frame_size_window.value_or(kDefaultFrameSizeWindow));
- return max_frame_size_bytes_percentile_.GetPercentileValue();
- }
- return max_frame_size_bytes_;
-}
-
double JitterEstimator::GetNumStddevDelayOutlier() const {
return config_.num_stddev_delay_outlier.value_or(kNumStdDevDelayOutlier);
}
@@ -357,8 +344,12 @@
config_.avg_frame_size_median
? avg_frame_size_median_bytes_.GetFilteredValue()
: avg_frame_size_bytes_;
+ double filtered_max_frame_size_bytes =
+ config_.MaxFrameSizePercentileEnabled()
+ ? max_frame_size_bytes_percentile_.GetFilteredValue()
+ : max_frame_size_bytes_;
double worst_case_frame_size_deviation_bytes =
- GetMaxFrameSizeEstimateBytes() - filtered_avg_frame_size_bytes;
+ filtered_max_frame_size_bytes - filtered_avg_frame_size_bytes;
double ret_ms = kalman_filter_.GetFrameDelayVariationEstimateSizeBased(
worst_case_frame_size_deviation_bytes) +
NoiseThreshold();
diff --git a/modules/video_coding/timing/jitter_estimator.h b/modules/video_coding/timing/jitter_estimator.h
index bbb148d..d7561c2 100644
--- a/modules/video_coding/timing/jitter_estimator.h
+++ b/modules/video_coding/timing/jitter_estimator.h
@@ -24,8 +24,7 @@
#include "modules/video_coding/timing/frame_delay_variation_kalman_filter.h"
#include "modules/video_coding/timing/rtt_filter.h"
#include "rtc_base/experiments/struct_parameters_parser.h"
-#include "rtc_base/numerics/moving_median_filter.h"
-#include "rtc_base/numerics/percentile_filter.h"
+#include "rtc_base/numerics/moving_percentile_filter.h"
#include "rtc_base/rolling_accumulator.h"
namespace webrtc {
@@ -133,7 +132,6 @@
private:
// These functions return values that could be overriden through the config.
- double GetMaxFrameSizeEstimateBytes() const;
double GetNumStddevDelayOutlier() const;
double GetNumStddevSizeOutlier() const;
double GetCongestionRejectionFactor() const;
@@ -176,10 +174,7 @@
double max_frame_size_bytes_;
// Percentile frame sized received (over a window). Only used if configured.
MovingMedianFilter<int64_t> avg_frame_size_median_bytes_;
- // TODO(webrtc:14151): Make `MovingMedianFilter` take a percentile value and
- // switch `max_frame_size_bytes_percentile_` over to that class.
- PercentileFilter<int64_t> max_frame_size_bytes_percentile_;
- std::queue<int64_t> frame_sizes_in_percentile_filter_;
+ MovingPercentileFilter<int64_t> max_frame_size_bytes_percentile_;
// TODO(bugs.webrtc.org/14381): Update `startup_frame_size_sum_bytes_` to
// DataSize when api/units have sufficient precision.
double startup_frame_size_sum_bytes_;
diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 12676a0..efd6388 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -763,7 +763,7 @@
"numerics/math_utils.h",
"numerics/moving_average.cc",
"numerics/moving_average.h",
- "numerics/moving_median_filter.h",
+ "numerics/moving_percentile_filter.h",
"numerics/percentile_filter.h",
"numerics/running_statistics.h",
"numerics/sequence_number_util.h",
@@ -1682,7 +1682,7 @@
"numerics/event_based_exponential_moving_average_unittest.cc",
"numerics/exp_filter_unittest.cc",
"numerics/moving_average_unittest.cc",
- "numerics/moving_median_filter_unittest.cc",
+ "numerics/moving_percentile_filter_unittest.cc",
"numerics/percentile_filter_unittest.cc",
"numerics/running_statistics_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
deleted file mode 100644
index 2a8ea7d..0000000
--- a/rtc_base/numerics/moving_median_filter.h
+++ /dev/null
@@ -1,90 +0,0 @@
-/*
- * 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 <stddef.h>
-
-#include <cstddef>
-#include <list>
-
-#include "rtc_base/checks.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);
-
- MovingMedianFilter(const MovingMedianFilter&) = delete;
- MovingMedianFilter& operator=(const MovingMedianFilter&) = delete;
-
- // Insert a new sample.
- void Insert(const T& value);
-
- // Removes all samples;
- void Reset();
-
- // Get median over the latest window.
- T GetFilteredValue() const;
-
- // The number of samples that are currently stored.
- size_t GetNumberOfSamplesStored() const;
-
- private:
- PercentileFilter<T> percentile_filter_;
- std::list<T> samples_;
- size_t samples_stored_;
- const size_t window_size_;
-};
-
-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();
-}
-
-template <typename T>
-void MovingMedianFilter<T>::Reset() {
- percentile_filter_.Reset();
- samples_.clear();
- samples_stored_ = 0;
-}
-
-template <typename T>
-size_t MovingMedianFilter<T>::GetNumberOfSamplesStored() const {
- return samples_stored_;
-}
-
-} // namespace webrtc
-#endif // RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_
diff --git a/rtc_base/numerics/moving_percentile_filter.h b/rtc_base/numerics/moving_percentile_filter.h
new file mode 100644
index 0000000..d68814a
--- /dev/null
+++ b/rtc_base/numerics/moving_percentile_filter.h
@@ -0,0 +1,103 @@
+/*
+ * 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_PERCENTILE_FILTER_H_
+#define RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_
+
+#include <stddef.h>
+
+#include <cstddef>
+#include <list>
+
+#include "rtc_base/checks.h"
+#include "rtc_base/numerics/percentile_filter.h"
+
+namespace webrtc {
+
+// Class to efficiently get moving percentile filter from a stream of samples.
+template <typename T>
+class MovingPercentileFilter {
+ public:
+ // Construct filter. `percentile` defines what percentile to track and
+ // `window_size` is how many latest samples are stored for finding the
+ // percentile. `percentile` must be between 0.0 and 1.0 (inclusive) and
+ // `window_size` must be greater than 0.
+ MovingPercentileFilter(float percentile, size_t window_size);
+
+ MovingPercentileFilter(const MovingPercentileFilter&) = delete;
+ MovingPercentileFilter& operator=(const MovingPercentileFilter&) = delete;
+
+ // Insert a new sample.
+ void Insert(const T& value);
+
+ // Removes all samples;
+ void Reset();
+
+ // Get percentile over the latest window.
+ T GetFilteredValue() const;
+
+ // The number of samples that are currently stored.
+ size_t GetNumberOfSamplesStored() const;
+
+ private:
+ PercentileFilter<T> percentile_filter_;
+ std::list<T> samples_;
+ size_t samples_stored_;
+ const size_t window_size_;
+};
+
+// Convenience type for the common median case.
+template <typename T>
+class MovingMedianFilter : public MovingPercentileFilter<T> {
+ public:
+ explicit MovingMedianFilter(size_t window_size)
+ : MovingPercentileFilter<T>(0.5f, window_size) {}
+};
+
+template <typename T>
+MovingPercentileFilter<T>::MovingPercentileFilter(float percentile,
+ size_t window_size)
+ : percentile_filter_(percentile),
+ samples_stored_(0),
+ window_size_(window_size) {
+ RTC_CHECK_GT(window_size, 0);
+}
+
+template <typename T>
+void MovingPercentileFilter<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 MovingPercentileFilter<T>::GetFilteredValue() const {
+ return percentile_filter_.GetPercentileValue();
+}
+
+template <typename T>
+void MovingPercentileFilter<T>::Reset() {
+ percentile_filter_.Reset();
+ samples_.clear();
+ samples_stored_ = 0;
+}
+
+template <typename T>
+size_t MovingPercentileFilter<T>::GetNumberOfSamplesStored() const {
+ return samples_stored_;
+}
+
+} // namespace webrtc
+#endif // RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_
diff --git a/rtc_base/numerics/moving_median_filter_unittest.cc b/rtc_base/numerics/moving_percentile_filter_unittest.cc
similarity index 61%
rename from rtc_base/numerics/moving_median_filter_unittest.cc
rename to rtc_base/numerics/moving_percentile_filter_unittest.cc
index 12c1114..30c0ebb 100644
--- a/rtc_base/numerics/moving_median_filter_unittest.cc
+++ b/rtc_base/numerics/moving_percentile_filter_unittest.cc
@@ -8,15 +8,42 @@
* be found in the AUTHORS file in the root of the source tree.
*/
-#include "rtc_base/numerics/moving_median_filter.h"
+#include "rtc_base/numerics/moving_percentile_filter.h"
#include <stdint.h>
+
#include <algorithm>
#include "test/gtest.h"
namespace webrtc {
+// 25th percentile can be exactly found with a window of length 4.
+TEST(MovingPercentileFilter, Percentile25ReturnsMovingPercentile25WithWindow4) {
+ MovingPercentileFilter<int> perc25(0.25f, 4);
+ const int64_t kSamples[10] = {1, 2, 3, 4, 4, 4, 5, 6, 7, 8};
+ const int64_t kExpectedFilteredValues[10] = {1, 1, 1, 1, 2, 3, 4, 4, 4, 5};
+ for (size_t i = 0; i < 10; ++i) {
+ perc25.Insert(kSamples[i]);
+ EXPECT_EQ(kExpectedFilteredValues[i], perc25.GetFilteredValue());
+ EXPECT_EQ(std::min<size_t>(i + 1, 4), perc25.GetNumberOfSamplesStored());
+ }
+}
+
+// 90th percentile becomes the 67th percentile with a window of length 4.
+TEST(MovingPercentileFilter, Percentile90ReturnsMovingPercentile67WithWindow4) {
+ MovingPercentileFilter<int> perc67(0.67f, 4);
+ MovingPercentileFilter<int> perc90(0.9f, 4);
+ const int64_t kSamples[8] = {1, 10, 1, 9, 1, 10, 1, 8};
+ const int64_t kExpectedFilteredValues[9] = {1, 1, 1, 9, 9, 9, 9, 8};
+ for (size_t i = 0; i < 8; ++i) {
+ perc67.Insert(kSamples[i]);
+ perc90.Insert(kSamples[i]);
+ EXPECT_EQ(kExpectedFilteredValues[i], perc67.GetFilteredValue());
+ EXPECT_EQ(kExpectedFilteredValues[i], perc90.GetFilteredValue());
+ }
+}
+
TEST(MovingMedianFilterTest, ProcessesNoSamples) {
MovingMedianFilter<int> filter(2);
EXPECT_EQ(0, filter.GetFilteredValue());
