AGC1 add clipping predictor evaluator Observes clipping predictions and detections and computes evaluation metrics for the predictor. Bug: webrtc:12774 Change-Id: I83f5942a3b6491de288510f2200f2f5c0e099bf2 Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/221619 Reviewed-by: Hanna Silen <silen@webrtc.org> Commit-Queue: Alessio Bazzica <alessiob@webrtc.org> Cr-Commit-Position: refs/heads/master@{#34305}
diff --git a/modules/audio_processing/agc/BUILD.gn b/modules/audio_processing/agc/BUILD.gn index 3b2b205..ca6d9bd 100644 --- a/modules/audio_processing/agc/BUILD.gn +++ b/modules/audio_processing/agc/BUILD.gn
@@ -58,6 +58,18 @@ absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] } +rtc_library("clipping_predictor_evaluator") { + sources = [ + "clipping_predictor_evaluator.cc", + "clipping_predictor_evaluator.h", + ] + deps = [ + "../../../rtc_base:checks", + "../../../rtc_base:logging", + ] + absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] +} + rtc_library("clipping_predictor_level_buffer") { sources = [ "clipping_predictor_level_buffer.cc", @@ -66,6 +78,7 @@ deps = [ "../../../rtc_base:checks", "../../../rtc_base:logging", + "../../../rtc_base:rtc_base_approved", ] absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] } @@ -128,6 +141,7 @@ testonly = true sources = [ "agc_manager_direct_unittest.cc", + "clipping_predictor_evaluator_unittest.cc", "clipping_predictor_level_buffer_unittest.cc", "clipping_predictor_unittest.cc", "loudness_histogram_unittest.cc", @@ -138,15 +152,19 @@ deps = [ ":agc", ":clipping_predictor", + ":clipping_predictor_evaluator", ":clipping_predictor_level_buffer", ":gain_control_interface", ":level_estimation", "..:mocks", "../../../rtc_base:checks", + "../../../rtc_base:rtc_base_approved", + "../../../rtc_base:safe_conversions", "../../../test:field_trial", "../../../test:fileutils", "../../../test:test_support", "//testing/gtest", ] + absl_deps = [ "//third_party/abseil-cpp/absl/types:optional" ] } }
diff --git a/modules/audio_processing/agc/clipping_predictor_evaluator.cc b/modules/audio_processing/agc/clipping_predictor_evaluator.cc new file mode 100644 index 0000000..2a4ea92 --- /dev/null +++ b/modules/audio_processing/agc/clipping_predictor_evaluator.cc
@@ -0,0 +1,175 @@ +/* + * Copyright (c) 2021 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 "modules/audio_processing/agc/clipping_predictor_evaluator.h" + +#include <algorithm> + +#include "rtc_base/checks.h" +#include "rtc_base/logging.h" + +namespace webrtc { +namespace { + +// Returns the index of the oldest item in the ring buffer for a non-empty +// ring buffer with give `size`, `tail` index and `capacity`. +int OldestExpectedDetectionIndex(int size, int tail, int capacity) { + RTC_DCHECK_GT(size, 0); + return tail - size + (tail < size ? capacity : 0); +} + +} // namespace + +ClippingPredictorEvaluator::ClippingPredictorEvaluator(int history_size) + : history_size_(history_size), + ring_buffer_capacity_(history_size + 1), + ring_buffer_(ring_buffer_capacity_), + true_positives_(0), + true_negatives_(0), + false_positives_(0), + false_negatives_(0) { + RTC_DCHECK_GT(history_size_, 0); + Reset(); +} + +ClippingPredictorEvaluator::~ClippingPredictorEvaluator() = default; + +absl::optional<int> ClippingPredictorEvaluator::Observe( + bool clipping_detected, + bool clipping_predicted) { + RTC_DCHECK_GE(ring_buffer_size_, 0); + RTC_DCHECK_LE(ring_buffer_size_, ring_buffer_capacity_); + RTC_DCHECK_GE(ring_buffer_tail_, 0); + RTC_DCHECK_LT(ring_buffer_tail_, ring_buffer_capacity_); + + DecreaseTimesToLive(); + if (clipping_predicted) { + // TODO(bugs.webrtc.org/12874): Use designated initializers one fixed. + Push(/*expected_detection=*/{/*ttl=*/history_size_, /*detected=*/false}); + } + // Clipping is expected if there are expected detections regardless of + // whether all the expected detections have been previously matched - i.e., + // `ExpectedDetection::detected` is true. + const bool clipping_expected = ring_buffer_size_ > 0; + + absl::optional<int> prediction_interval; + if (clipping_expected && clipping_detected) { + prediction_interval = FindEarliestPredictionInterval(); + // Add a true positive for each unexpired expected detection. + const int num_modified_items = MarkExpectedDetectionAsDetected(); + true_positives_ += num_modified_items; + RTC_DCHECK(prediction_interval.has_value() || num_modified_items == 0); + RTC_DCHECK(!prediction_interval.has_value() || num_modified_items > 0); + } else if (clipping_expected && !clipping_detected) { + // Add a false positive if there is one expected detection that has expired + // and that has never been matched before. Note that there is at most one + // unmatched expired detection. + if (HasExpiredUnmatchedExpectedDetection()) { + false_positives_++; + } + } else if (!clipping_expected && clipping_detected) { + false_negatives_++; + } else { + RTC_DCHECK(!clipping_expected && !clipping_detected); + true_negatives_++; + } + return prediction_interval; +} + +void ClippingPredictorEvaluator::Reset() { + // Empty the ring buffer of expected detections. + ring_buffer_tail_ = 0; + ring_buffer_size_ = 0; +} + +// Cost: O(1). +void ClippingPredictorEvaluator::Push(ExpectedDetection value) { + ring_buffer_[ring_buffer_tail_] = value; + ring_buffer_tail_++; + if (ring_buffer_tail_ == ring_buffer_capacity_) { + ring_buffer_tail_ = 0; + } + ring_buffer_size_ = std::min(ring_buffer_capacity_, ring_buffer_size_ + 1); +} + +// Cost: O(N). +void ClippingPredictorEvaluator::DecreaseTimesToLive() { + bool expired_found = false; + for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_; + ++i) { + int index = i >= 0 ? i : ring_buffer_capacity_ + i; + RTC_DCHECK_GE(index, 0); + RTC_DCHECK_LT(index, ring_buffer_.size()); + RTC_DCHECK_GE(ring_buffer_[index].ttl, 0); + if (ring_buffer_[index].ttl == 0) { + RTC_DCHECK(!expired_found) + << "There must be at most one expired item in the ring buffer."; + expired_found = true; + RTC_DCHECK_EQ(index, OldestExpectedDetectionIndex(ring_buffer_size_, + ring_buffer_tail_, + ring_buffer_capacity_)) + << "The expired item must be the oldest in the ring buffer."; + } + ring_buffer_[index].ttl--; + } + if (expired_found) { + ring_buffer_size_--; + } +} + +// Cost: O(N). +absl::optional<int> ClippingPredictorEvaluator::FindEarliestPredictionInterval() + const { + absl::optional<int> prediction_interval; + for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_; + ++i) { + int index = i >= 0 ? i : ring_buffer_capacity_ + i; + RTC_DCHECK_GE(index, 0); + RTC_DCHECK_LT(index, ring_buffer_.size()); + if (!ring_buffer_[index].detected) { + prediction_interval = std::max(prediction_interval.value_or(0), + history_size_ - ring_buffer_[index].ttl); + } + } + return prediction_interval; +} + +// Cost: O(N). +int ClippingPredictorEvaluator::MarkExpectedDetectionAsDetected() { + int num_modified_items = 0; + for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_; + ++i) { + int index = i >= 0 ? i : ring_buffer_capacity_ + i; + RTC_DCHECK_GE(index, 0); + RTC_DCHECK_LT(index, ring_buffer_.size()); + if (!ring_buffer_[index].detected) { + num_modified_items++; + } + ring_buffer_[index].detected = true; + } + return num_modified_items; +} + +// Cost: O(1). +bool ClippingPredictorEvaluator::HasExpiredUnmatchedExpectedDetection() const { + if (ring_buffer_size_ == 0) { + return false; + } + // If an expired item, that is `ttl` equal to 0, exists, it must be the + // oldest. + const int oldest_index = OldestExpectedDetectionIndex( + ring_buffer_size_, ring_buffer_tail_, ring_buffer_capacity_); + RTC_DCHECK_GE(oldest_index, 0); + RTC_DCHECK_LT(oldest_index, ring_buffer_.size()); + return ring_buffer_[oldest_index].ttl == 0 && + !ring_buffer_[oldest_index].detected; +} + +} // namespace webrtc
diff --git a/modules/audio_processing/agc/clipping_predictor_evaluator.h b/modules/audio_processing/agc/clipping_predictor_evaluator.h new file mode 100644 index 0000000..e76f25d --- /dev/null +++ b/modules/audio_processing/agc/clipping_predictor_evaluator.h
@@ -0,0 +1,102 @@ +/* + * Copyright (c) 2021 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 MODULES_AUDIO_PROCESSING_AGC_CLIPPING_PREDICTOR_EVALUATOR_H_ +#define MODULES_AUDIO_PROCESSING_AGC_CLIPPING_PREDICTOR_EVALUATOR_H_ + +#include <vector> + +#include "absl/types/optional.h" + +namespace webrtc { + +// Counts true/false positives/negatives while observing sequences of flag pairs +// that indicate whether clipping has been detected and/or if clipping is +// predicted. When a true positive is found measures the time interval between +// prediction and detection events. +// From the time a prediction is observed and for a period equal to +// `history_size` calls to `Observe()`, one or more detections are expected. If +// the expectation is met, a true positives is added and the time interval +// between the earliest prediction and the detection is recorded; otherwise, +// when the deadline is reached, a false positive is added. Note that one +// detection matches all the expected detections that have not expired - i.e., +// one detection counts as multiple true positives. +// If a detection is observed, but no prediction has been observed over the past +// `history_size` calls to `Observe()`, then a false negative is added; +// otherwise, a true negative is added. +class ClippingPredictorEvaluator { + public: + // Ctor. `history_size` indicates how long to wait for a call to `Observe()` + // having `clipping_detected` set to true from the time clipping is predicted. + explicit ClippingPredictorEvaluator(int history_size); + ClippingPredictorEvaluator(const ClippingPredictorEvaluator&) = delete; + ClippingPredictorEvaluator& operator=(const ClippingPredictorEvaluator&) = + delete; + ~ClippingPredictorEvaluator(); + + // Observes whether clipping has been detected and/or if clipping is + // predicted. When predicted one or more detections are expected in the next + // `history_size_` calls of `Observe()`. When true positives are found returns + // the prediction interval between the earliest prediction and the detection. + absl::optional<int> Observe(bool clipping_detected, bool clipping_predicted); + + // Removes any expectation recently set after a call to `Observe()` having + // `clipping_predicted` set to true. + void Reset(); + + // Metrics getters. + int true_positives() const { return true_positives_; } + int true_negatives() const { return true_negatives_; } + int false_positives() const { return false_positives_; } + int false_negatives() const { return false_negatives_; } + + private: + const int history_size_; + + // State of a detection expected to be observed after a prediction. + struct ExpectedDetection { + // Time to live (TTL); remaining number of `Observe()` calls to match a call + // having `clipping_detected` set to true. + int ttl; + // True if an `Observe()` call having `clipping_detected` set to true has + // been observed. + bool detected; + }; + // Ring buffer of expected detections. + const int ring_buffer_capacity_; + std::vector<ExpectedDetection> ring_buffer_; + int ring_buffer_tail_; + int ring_buffer_size_; + + // Pushes `expected_detection` into `expected_matches_ring_buffer_`. + void Push(ExpectedDetection expected_detection); + // Decreased the TTLs in `expected_matches_ring_buffer_` and removes expired + // items. + void DecreaseTimesToLive(); + // Returns the prediction interval for the earliest unexpired expected + // detection if any. + absl::optional<int> FindEarliestPredictionInterval() const; + // Marks all the items in `expected_matches_ring_buffer_` as `detected` and + // returns the number of updated items. + int MarkExpectedDetectionAsDetected(); + // Returns true if `expected_matches_ring_buffer_` has an item having `ttl` + // equal to 0 (expired) and `detected` equal to false (unmatched). + bool HasExpiredUnmatchedExpectedDetection() const; + + // Metrics. + int true_positives_; + int true_negatives_; + int false_positives_; + int false_negatives_; +}; + +} // namespace webrtc + +#endif // MODULES_AUDIO_PROCESSING_AGC_CLIPPING_PREDICTOR_EVALUATOR_H_
diff --git a/modules/audio_processing/agc/clipping_predictor_evaluator_unittest.cc b/modules/audio_processing/agc/clipping_predictor_evaluator_unittest.cc new file mode 100644 index 0000000..1eb83ea --- /dev/null +++ b/modules/audio_processing/agc/clipping_predictor_evaluator_unittest.cc
@@ -0,0 +1,568 @@ +/* + * Copyright (c) 2021 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 "modules/audio_processing/agc/clipping_predictor_evaluator.h" + +#include <cstdint> +#include <memory> +#include <tuple> +#include <vector> + +#include "absl/types/optional.h" +#include "rtc_base/numerics/safe_conversions.h" +#include "rtc_base/random.h" +#include "test/gmock.h" +#include "test/gtest.h" + +namespace webrtc { +namespace { + +using testing::Eq; +using testing::Optional; + +constexpr bool kDetected = true; +constexpr bool kNotDetected = false; + +constexpr bool kPredicted = true; +constexpr bool kNotPredicted = false; + +int SumTrueFalsePositivesNegatives( + const ClippingPredictorEvaluator& evaluator) { + return evaluator.true_positives() + evaluator.true_negatives() + + evaluator.false_positives() + evaluator.false_negatives(); +} + +// Checks the metrics after init - i.e., no call to `Observe()`. +TEST(ClippingPredictorEvaluatorTest, Init) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +class ClippingPredictorEvaluatorParameterization + : public ::testing::TestWithParam<std::tuple<int, int>> { + protected: + uint64_t seed() const { + return rtc::checked_cast<uint64_t>(std::get<0>(GetParam())); + } + int history_size() const { return std::get<1>(GetParam()); } +}; + +// Checks that after each call to `Observe()` at most one metric changes. +TEST_P(ClippingPredictorEvaluatorParameterization, AtMostOneMetricChanges) { + constexpr int kNumCalls = 123; + Random random_generator(seed()); + ClippingPredictorEvaluator evaluator(history_size()); + + for (int i = 0; i < kNumCalls; ++i) { + SCOPED_TRACE(i); + // Read metrics before `Observe()` is called. + const int last_tp = evaluator.true_positives(); + const int last_tn = evaluator.true_negatives(); + const int last_fp = evaluator.false_positives(); + const int last_fn = evaluator.false_negatives(); + // `Observe()` a random observation. + bool clipping_detected = random_generator.Rand<bool>(); + bool clipping_predicted = random_generator.Rand<bool>(); + evaluator.Observe(clipping_detected, clipping_predicted); + + // Check that at most one metric has changed. + int num_changes = 0; + num_changes += last_tp == evaluator.true_positives() ? 0 : 1; + num_changes += last_tn == evaluator.true_negatives() ? 0 : 1; + num_changes += last_fp == evaluator.false_positives() ? 0 : 1; + num_changes += last_fn == evaluator.false_negatives() ? 0 : 1; + EXPECT_GE(num_changes, 0); + EXPECT_LE(num_changes, 1); + } +} + +// Checks that after each call to `Observe()` each metric either remains +// unchanged or grows. +TEST_P(ClippingPredictorEvaluatorParameterization, MetricsAreWeaklyMonotonic) { + constexpr int kNumCalls = 123; + Random random_generator(seed()); + ClippingPredictorEvaluator evaluator(history_size()); + + for (int i = 0; i < kNumCalls; ++i) { + SCOPED_TRACE(i); + // Read metrics before `Observe()` is called. + const int last_tp = evaluator.true_positives(); + const int last_tn = evaluator.true_negatives(); + const int last_fp = evaluator.false_positives(); + const int last_fn = evaluator.false_negatives(); + // `Observe()` a random observation. + bool clipping_detected = random_generator.Rand<bool>(); + bool clipping_predicted = random_generator.Rand<bool>(); + evaluator.Observe(clipping_detected, clipping_predicted); + + // Check that metrics are weakly monotonic. + EXPECT_GE(evaluator.true_positives(), last_tp); + EXPECT_GE(evaluator.true_negatives(), last_tn); + EXPECT_GE(evaluator.false_positives(), last_fp); + EXPECT_GE(evaluator.false_negatives(), last_fn); + } +} + +// Checks that after each call to `Observe()` the growth speed of each metrics +// is bounded. +TEST_P(ClippingPredictorEvaluatorParameterization, BoundedMetricsGrowth) { + constexpr int kNumCalls = 123; + Random random_generator(seed()); + ClippingPredictorEvaluator evaluator(history_size()); + + for (int i = 0; i < kNumCalls; ++i) { + SCOPED_TRACE(i); + // Read metrics before `Observe()` is called. + const int last_tp = evaluator.true_positives(); + const int last_tn = evaluator.true_negatives(); + const int last_fp = evaluator.false_positives(); + const int last_fn = evaluator.false_negatives(); + // `Observe()` a random observation. + bool clipping_detected = random_generator.Rand<bool>(); + bool clipping_predicted = random_generator.Rand<bool>(); + evaluator.Observe(clipping_detected, clipping_predicted); + + // Check that TPs grow by at most `history_size() + 1`. Such an upper bound + // is reached when multiple predictions are matched by a single detection. + EXPECT_LE(evaluator.true_positives() - last_tp, history_size() + 1); + // Check that TNs, FPs and FNs grow by at most one. `max_growth`. + EXPECT_LE(evaluator.true_negatives() - last_tn, 1); + EXPECT_LE(evaluator.false_positives() - last_fp, 1); + EXPECT_LE(evaluator.false_negatives() - last_fn, 1); + } +} + +// Checks that `Observe()` returns a prediction interval if and only if one or +// more true positives are found. +TEST_P(ClippingPredictorEvaluatorParameterization, + PredictionIntervalIfAndOnlyIfTruePositives) { + constexpr int kNumCalls = 123; + Random random_generator(seed()); + ClippingPredictorEvaluator evaluator(history_size()); + + for (int i = 0; i < kNumCalls; ++i) { + SCOPED_TRACE(i); + // Read true positives before `Observe()` is called. + const int last_tp = evaluator.true_positives(); + // `Observe()` a random observation. + bool clipping_detected = random_generator.Rand<bool>(); + bool clipping_predicted = random_generator.Rand<bool>(); + absl::optional<int> prediction_interval = + evaluator.Observe(clipping_detected, clipping_predicted); + + // Check that the prediction interval is returned when a true positive is + // found. + if (evaluator.true_positives() == last_tp) { + EXPECT_FALSE(prediction_interval.has_value()); + } else { + EXPECT_TRUE(prediction_interval.has_value()); + } + } +} + +INSTANTIATE_TEST_SUITE_P( + ClippingPredictorEvaluatorTest, + ClippingPredictorEvaluatorParameterization, + ::testing::Combine(::testing::Values(4, 8, 15, 16, 23, 42), + ::testing::Values(1, 10, 21))); + +// Checks that, observing a detection and a prediction after init, produces a +// true positive. +TEST(ClippingPredictorEvaluatorTest, OneTruePositiveAfterInit) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kDetected, kPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that, observing a detection but no prediction after init, produces a +// false negative. +TEST(ClippingPredictorEvaluatorTest, OneFalseNegativeAfterInit) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_negatives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); +} + +// Checks that, observing no detection but a prediction after init, produces a +// false positive after expiration. +TEST(ClippingPredictorEvaluatorTest, OneFalsePositiveAfterInit) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that, observing no detection and no prediction after init, produces a +// true negative. +TEST(ClippingPredictorEvaluatorTest, OneTrueNegativeAfterInit) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_negatives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that the evaluator detects true negatives when clipping is neither +// predicted nor detected. +TEST(ClippingPredictorEvaluatorTest, NeverDetectedAndNotPredicted) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_negatives(), 4); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that the evaluator detects a false negative when clipping is detected +// but not predicted. +TEST(ClippingPredictorEvaluatorTest, DetectedButNotPredicted) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_negatives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 3); + EXPECT_EQ(evaluator.false_positives(), 0); +} + +// Checks that the evaluator does not detect a false positive when clipping is +// predicted but not detected until the observation period expires. +TEST(ClippingPredictorEvaluatorTest, + PredictedOnceAndNeverDetectedBeforeDeadline) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that the evaluator detects a false positive when clipping is predicted +// but detected after the observation period expires. +TEST(ClippingPredictorEvaluatorTest, PredictedOnceButDetectedAfterDeadline) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 0); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 1); +} + +// Checks that a prediction followed by a detection counts as true positive. +TEST(ClippingPredictorEvaluatorTest, PredictedOnceAndThenImmediatelyDetected) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that a prediction followed by a delayed detection counts as true +// positive if the delay is within the observation period. +TEST(ClippingPredictorEvaluatorTest, PredictedOnceAndDetectedBeforeDeadline) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that a prediction followed by a delayed detection counts as true +// positive if the delay equals the observation period. +TEST(ClippingPredictorEvaluatorTest, PredictedOnceAndDetectedAtDeadline) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_positives(), 0); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that a prediction followed by a multiple adjacent detections within +// the deadline counts as a single true positive and that, after the deadline, +// a detection counts as a false negative. +TEST(ClippingPredictorEvaluatorTest, PredictedOnceAndDetectedMultipleTimes) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + // Multiple detections. + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_positives(), 1); + // A detection outside of the observation period counts as false negative. + evaluator.Observe(kDetected, kNotPredicted); + EXPECT_EQ(evaluator.false_negatives(), 1); + EXPECT_EQ(SumTrueFalsePositivesNegatives(evaluator), 2); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); +} + +// Checks that a false positive is added when clipping is detected after a too +// early prediction. +TEST(ClippingPredictorEvaluatorTest, + PredictedMultipleTimesAndDetectedOnceAfterDeadline) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); // ---+ + evaluator.Observe(kNotDetected, kPredicted); // | + evaluator.Observe(kNotDetected, kPredicted); // | + evaluator.Observe(kNotDetected, kPredicted); // <--+ Not matched. + // The time to match a detection after the first prediction expired. + EXPECT_EQ(evaluator.false_positives(), 1); + evaluator.Observe(kDetected, kNotPredicted); + // The detection above does not match the first prediction because it happened + // after the deadline of the 1st prediction. + EXPECT_EQ(evaluator.false_positives(), 1); + + EXPECT_EQ(evaluator.true_positives(), 3); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that multiple consecutive predictions match the first detection +// observed before the expected detection deadline expires. +TEST(ClippingPredictorEvaluatorTest, PredictedMultipleTimesAndDetectedOnce) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); // --+ + evaluator.Observe(kNotDetected, kPredicted); // | --+ + evaluator.Observe(kNotDetected, kPredicted); // | | --+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ <-+ + EXPECT_EQ(evaluator.true_positives(), 3); + // The following observations do not generate any true negatives as they + // belong to the observation period of the last prediction - for which a + // detection has already been matched. + const int true_negatives = evaluator.true_negatives(); + evaluator.Observe(kNotDetected, kNotPredicted); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_negatives(), true_negatives); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that multiple consecutive predictions match the multiple detections +// observed before the expected detection deadline expires. +TEST(ClippingPredictorEvaluatorTest, + PredictedMultipleTimesAndDetectedMultipleTimes) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); // --+ + evaluator.Observe(kNotDetected, kPredicted); // | --+ + evaluator.Observe(kNotDetected, kPredicted); // | | --+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ <-+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ + EXPECT_EQ(evaluator.true_positives(), 3); + // The following observation does not generate a true negative as it belongs + // to the observation period of the last prediction - for which two detections + // have already been matched. + const int true_negatives = evaluator.true_negatives(); + evaluator.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(evaluator.true_negatives(), true_negatives); + + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that multiple consecutive predictions match all the detections +// observed before the expected detection deadline expires. +TEST(ClippingPredictorEvaluatorTest, PredictedMultipleTimesAndAllDetected) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); // --+ + evaluator.Observe(kNotDetected, kPredicted); // | --+ + evaluator.Observe(kNotDetected, kPredicted); // | | --+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ <-+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ + EXPECT_EQ(evaluator.true_positives(), 3); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +// Checks that multiple non-consecutive predictions match all the detections +// observed before the expected detection deadline expires. +TEST(ClippingPredictorEvaluatorTest, + PredictedMultipleTimesWithGapAndAllDetected) { + ClippingPredictorEvaluator evaluator(/*history_size=*/3); + evaluator.Observe(kNotDetected, kPredicted); // --+ + evaluator.Observe(kNotDetected, kNotPredicted); // | + evaluator.Observe(kNotDetected, kPredicted); // | --+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ <-+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ + evaluator.Observe(kDetected, kNotPredicted); // <-+ + EXPECT_EQ(evaluator.true_positives(), 2); + EXPECT_EQ(evaluator.true_negatives(), 0); + EXPECT_EQ(evaluator.false_positives(), 0); + EXPECT_EQ(evaluator.false_negatives(), 0); +} + +class ClippingPredictorEvaluatorPredictionIntervalParameterization + : public ::testing::TestWithParam<std::tuple<int, int>> { + protected: + int num_extra_observe_calls() const { return std::get<0>(GetParam()); } + int history_size() const { return std::get<1>(GetParam()); } +}; + +// Checks that the minimum prediction interval is returned if clipping is +// correctly predicted as soon as detected - i.e., no anticipation. +TEST_P(ClippingPredictorEvaluatorPredictionIntervalParameterization, + MinimumPredictionInterval) { + ClippingPredictorEvaluator evaluator(history_size()); + for (int i = 0; i < num_extra_observe_calls(); ++i) { + EXPECT_EQ(evaluator.Observe(kNotDetected, kNotPredicted), absl::nullopt); + } + absl::optional<int> prediction_interval = + evaluator.Observe(kDetected, kPredicted); + EXPECT_THAT(prediction_interval, Optional(Eq(0))); +} + +// Checks that a prediction interval between the minimum and the maximum is +// returned if clipping is correctly predicted before it is detected but not as +// early as possible. +TEST_P(ClippingPredictorEvaluatorPredictionIntervalParameterization, + IntermediatePredictionInterval) { + ClippingPredictorEvaluator evaluator(history_size()); + for (int i = 0; i < num_extra_observe_calls(); ++i) { + EXPECT_EQ(evaluator.Observe(kNotDetected, kNotPredicted), absl::nullopt); + } + EXPECT_EQ(evaluator.Observe(kNotDetected, kPredicted), absl::nullopt); + EXPECT_EQ(evaluator.Observe(kNotDetected, kPredicted), absl::nullopt); + EXPECT_EQ(evaluator.Observe(kNotDetected, kPredicted), absl::nullopt); + absl::optional<int> prediction_interval = + evaluator.Observe(kDetected, kPredicted); + EXPECT_THAT(prediction_interval, Optional(Eq(3))); +} + +// Checks that the maximum prediction interval is returned if clipping is +// correctly predicted as early as possible. +TEST_P(ClippingPredictorEvaluatorPredictionIntervalParameterization, + MaximumPredictionInterval) { + ClippingPredictorEvaluator evaluator(history_size()); + for (int i = 0; i < num_extra_observe_calls(); ++i) { + EXPECT_EQ(evaluator.Observe(kNotDetected, kNotPredicted), absl::nullopt); + } + for (int i = 0; i < history_size(); ++i) { + EXPECT_EQ(evaluator.Observe(kNotDetected, kPredicted), absl::nullopt); + } + absl::optional<int> prediction_interval = + evaluator.Observe(kDetected, kPredicted); + EXPECT_THAT(prediction_interval, Optional(Eq(history_size()))); +} + +// Checks that `Observe()` returns the prediction interval as soon as a true +// positive is found and never again while ongoing detections are matched to a +// previously observed prediction. +TEST_P(ClippingPredictorEvaluatorPredictionIntervalParameterization, + PredictionIntervalReturnedOnce) { + ASSERT_LT(num_extra_observe_calls(), history_size()); + ClippingPredictorEvaluator evaluator(history_size()); + // Observe predictions before detection. + for (int i = 0; i < num_extra_observe_calls(); ++i) { + EXPECT_EQ(evaluator.Observe(kNotDetected, kPredicted), absl::nullopt); + } + // Observe a detection. + absl::optional<int> prediction_interval = + evaluator.Observe(kDetected, kPredicted); + EXPECT_TRUE(prediction_interval.has_value()); + // `Observe()` does not return a prediction interval anymore during ongoing + // detections observed while a detection is still expected. + for (int i = 0; i < history_size(); ++i) { + EXPECT_EQ(evaluator.Observe(kDetected, kNotPredicted), absl::nullopt); + } +} + +INSTANTIATE_TEST_SUITE_P( + ClippingPredictorEvaluatorTest, + ClippingPredictorEvaluatorPredictionIntervalParameterization, + ::testing::Combine(::testing::Values(0, 3, 5), ::testing::Values(7, 11))); + +// Checks that, when a detection is expected, the expectation is removed if and +// only if `Reset()` is called after a prediction is observed. +TEST(ClippingPredictorEvaluatorTest, NoFalsePositivesAfterReset) { + constexpr int kHistorySize = 2; + + ClippingPredictorEvaluator with_reset(kHistorySize); + with_reset.Observe(kNotDetected, kPredicted); + with_reset.Reset(); + with_reset.Observe(kNotDetected, kNotPredicted); + with_reset.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(with_reset.true_positives(), 0); + EXPECT_EQ(with_reset.true_negatives(), 2); + EXPECT_EQ(with_reset.false_positives(), 0); + EXPECT_EQ(with_reset.false_negatives(), 0); + + ClippingPredictorEvaluator no_reset(kHistorySize); + no_reset.Observe(kNotDetected, kPredicted); + no_reset.Observe(kNotDetected, kNotPredicted); + no_reset.Observe(kNotDetected, kNotPredicted); + EXPECT_EQ(no_reset.true_positives(), 0); + EXPECT_EQ(no_reset.true_negatives(), 0); + EXPECT_EQ(no_reset.false_positives(), 1); + EXPECT_EQ(no_reset.false_negatives(), 0); +} + +} // namespace +} // namespace webrtc