Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc

Index: webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
diff --git a/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc b/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..e8fc032ef109930955d4fb3ebc3b734091f49eaf
--- /dev/null
+++ b/webrtc/modules/audio_processing/echo_detector/echo_detector_unittest.cc
@@ -0,0 +1,130 @@
+/*

[hlundin-webrtc, 2016/10/17 18:49:42]

None of the tests in this file test the EchoDetector class. They should all be
moved to other test files, corresponding to the class they are actually testing.

[ivoc, 2016/10/18 15:20:20]

Done.

+ *  Copyright (c) 2016 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 <vector>
+
+#include "webrtc/modules/audio_processing/echo_detector/circular_buffer.h"
+#include "webrtc/modules/audio_processing/echo_detector/mean_variance_estimator.h"
+#include "webrtc/modules/audio_processing/echo_detector/normalized_covariance_estimator.h"
+#include "webrtc/test/gtest.h"
+
+namespace webrtc {
+
+TEST(EchoDetectorTests, CircularBufferTest) {

[hlundin-webrtc, 2016/10/17 18:49:41]

This tests the CircularBuffer class. Move to circular_buffer_unittest.cc.

[ivoc, 2016/10/18 15:20:19]

Done.

+  CircularBuffer test_buffer(3);

[hlundin-webrtc, 2016/10/17 18:49:43]

Test a few other cases too, like reading from an empty buffer, inserting less
than max number of elements, etc.

+  test_buffer.Insert(1.f);
+  test_buffer.Insert(2.f);
+  test_buffer.Insert(3.f);
+  test_buffer.Insert(4.f);
+  // Because the circular buffer has a size of 3, the first insert should have
+  // been forgotten.
+  EXPECT_EQ(2.f, test_buffer.GetValue());
+  EXPECT_EQ(3.f, test_buffer.GetValue());
+  EXPECT_EQ(4.f, test_buffer.GetValue());
+}
+
+TEST(EchoDetectorTests, MeanVarianceEstimatorInsertTwoValues) {

[hlundin-webrtc, 2016/10/17 18:49:42]

Move to mean_variance_estimator_unittest.cc.

[ivoc, 2016/10/18 15:20:19]

Done.

+  MeanVarianceEstimator test_estimator;
+  // Insert two values.
+  test_estimator.UpdateEstimate(3.f);
+  test_estimator.UpdateEstimate(5.f);
+
+  EXPECT_GT(test_estimator.mean(), 0.f);

[hlundin-webrtc, 2016/10/17 18:49:41]

Can't you EXPECT_EQ instead?

[ivoc, 2016/10/18 15:20:19]

I could, but then the value depends on the exact implementation of the
MeanVarianceEstimator, in particular the alpha value. I thought it would be
useful to have one test just to see that it changes in the right direction, as
well as to see if Clear() is doing its job. The other tests are already testing
if the value converges to the correct value, so I'm not sure if it adds value to
also do that here. If you don't think it's a useful test I can remove it and
move the Clear() part to one of the others.

[hlundin-webrtc, 2016/10/18 20:52:21]

This is fine.

+  EXPECT_GT(test_estimator.std_deviation(), 0.f);

[hlundin-webrtc, 2016/10/17 18:49:43]

And here.

+  // Test Clear method
+  test_estimator.Clear();
+  EXPECT_EQ(test_estimator.mean(), 0.f);
+  EXPECT_EQ(test_estimator.std_deviation(), 0.f);
+}
+
+TEST(EchoDetectorTests, MeanVarianceEstimatorInsertZeroes) {
+  MeanVarianceEstimator test_estimator;
+  // Insert the same value many times.
+  for (int i = 0; i < 10000; i++) {

[hlundin-webrtc, 2016/10/17 18:49:42]

size_t

Several places.

[ivoc, 2016/10/18 15:20:19]

Done, but the style guide says not to use size_t everywhere:
https://google.github.io/styleguide/cppguide.html#Integer_Types

[hlundin-webrtc, 2016/10/18 20:52:21]

I think the restriction applies to the fixed-width types, e.g., int16_t,
uint32_t. These should only be used when really needed and motivated. size_t
should be used whenever counting bytes, items, samples, etc. But in this case, I
got a bit carried away – the index variable is only used to specify the for
loop, and it is not used to index into an array or vector, so an int would have
been fine too. Trigger happy reviewer.

+    test_estimator.UpdateEstimate(0.f);
+  }
+  EXPECT_EQ(test_estimator.mean(), 0.f);
+  EXPECT_EQ(test_estimator.std_deviation(), 0.f);
+}
+
+TEST(EchoDetectorTests, MeanVarianceEstimatorConstantValueTest) {
+  MeanVarianceEstimator test_estimator;
+  for (int i = 0; i < 10000; i++) {
+    test_estimator.UpdateEstimate(3.f);
+  }
+  // The mean should be close to three, and the standard deviation should be
+  // close to zero.
+  EXPECT_LT(std::abs(test_estimator.mean() - 3.f), 0.01f);

[hlundin-webrtc, 2016/10/17 18:49:42]

Use EXPECT_FLOAT_EQ if the values are close enough, or EXPECT_NEAR otherwise.
https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid...

Here, and several places below.

[ivoc, 2016/10/18 15:20:20]

Done.

+  EXPECT_LT(std::abs(test_estimator.std_deviation()), 0.01f);
+}
+
+TEST(EchoDetectorTests, MeanVarianceEstimatorAlternatingValueTest) {
+  MeanVarianceEstimator test_estimator;
+  for (int i = 0; i < 10000; i++) {
+    test_estimator.UpdateEstimate(1.f);
+    test_estimator.UpdateEstimate(-1.f);
+  }
+  // The mean should be close to zero, and the standard deviation should be
+  // close to one.
+  EXPECT_LT(std::abs(test_estimator.mean()), 0.01f);
+  EXPECT_LT(std::abs(test_estimator.std_deviation() - 1.f), 0.01f);
+}
+
+TEST(EchoDetectorTests, NormalizedCovarianceEstimatorIdenticalSignalTest) {

[hlundin-webrtc, 2016/10/17 18:49:42]

Move to normalized_covariance_estimator_unittests.cc

[ivoc, 2016/10/18 15:20:19]

Done.

+  MeanVarianceEstimator mean_variance_estimator;

[hlundin-webrtc, 2016/10/17 18:49:41]

You don't need this object, right? The test will be cleaner if you just feed the
test_estimator directly with the input numbers.

[ivoc, 2016/10/18 15:20:19]

Ok, I can remove it and use the true values. This should make it a bit easier
for the NormalizedCovarianceEstimator as it no longer has to rely on estimates.

+  NormalizedCovarianceEstimator test_estimator;
+  for (int i = 0; i < 10000; i++) {
+    mean_variance_estimator.UpdateEstimate(1.f);
+    test_estimator.UpdateCovarianceEstimate(
+        1.f, mean_variance_estimator.mean(),
+        mean_variance_estimator.std_deviation(), 1.f,
+        mean_variance_estimator.mean(),
+        mean_variance_estimator.std_deviation());
+    mean_variance_estimator.UpdateEstimate(-1.f);
+    test_estimator.UpdateCovarianceEstimate(
+        -1.f, mean_variance_estimator.mean(),
+        mean_variance_estimator.std_deviation(), -1.f,
+        mean_variance_estimator.mean(),
+        mean_variance_estimator.std_deviation());
+  }
+  // A normalized covariance value close to 1 is expected.
+  EXPECT_LT(std::abs(test_estimator.normalized_cross_correlation() - 1.f),
+            0.01f);
+  test_estimator.Clear();
+  EXPECT_EQ(0.f, test_estimator.normalized_cross_correlation());
+}
+
+TEST(EchoDetectorTests, NormalizedCovarianceEstimatorOppositeSignalTest) {
+  MeanVarianceEstimator mean_variance_estimator1;
+  MeanVarianceEstimator mean_variance_estimator2;
+  NormalizedCovarianceEstimator test_estimator;

[hlundin-webrtc, 2016/10/17 18:49:42]

Same comments apply to this as to the previous test.

[ivoc, 2016/10/18 15:20:19]

Done.

+  // Insert the same value many times.
+  for (int i = 0; i < 10000; i++) {
+    mean_variance_estimator1.UpdateEstimate(1.f);
+    mean_variance_estimator2.UpdateEstimate(-1.f);
+    test_estimator.UpdateCovarianceEstimate(
+        1.f, mean_variance_estimator1.mean(),
+        mean_variance_estimator1.std_deviation(), -1.f,
+        mean_variance_estimator2.mean(),
+        mean_variance_estimator2.std_deviation());
+    mean_variance_estimator1.UpdateEstimate(-1.f);
+    mean_variance_estimator2.UpdateEstimate(1.f);
+    test_estimator.UpdateCovarianceEstimate(
+        -1.f, mean_variance_estimator1.mean(),
+        mean_variance_estimator1.std_deviation(), 1.f,
+        mean_variance_estimator2.mean(),
+        mean_variance_estimator2.std_deviation());
+  }
+  // A normalized covariance value close to -1 is expected.
+  EXPECT_LT(std::abs(test_estimator.normalized_cross_correlation() + 1.f),
+            0.01f);
+}
+
+}  // namespace webrtc