Add algorithm for Residual Echo Detector.

webrtc/modules/audio_processing/echo_detector/echo_detector.cc

Index: webrtc/modules/audio_processing/echo_detector/echo_detector.cc
diff --git a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
index 842be9e2db3a5a999de4dd07c02c40ec41c879db..bb9d44146ea9afc913ca8f23f1a74041ce0f7b38 100644
--- a/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
+++ b/webrtc/modules/audio_processing/echo_detector/echo_detector.cc
@@ -10,21 +10,93 @@
 
 #include "webrtc/modules/audio_processing/echo_detector/echo_detector.h"
 
+#include <algorithm>
+#include <numeric>
+
+#include "webrtc/base/logging.h"
+
+namespace {
+
+float Power(rtc::ArrayView<const float> input) {
+  return std::inner_product(input.begin(), input.end(), input.begin(), 0.f);
+}
+
+}  // namespace
+
 namespace webrtc {
 
-void EchoDetector::BufferFarend(const rtc::ArrayView<const float>& /*farend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+EchoDetector::EchoDetector() = default;
+
+EchoDetector::~EchoDetector() = default;
+
+constexpr size_t EchoDetector::kLookbackFrames;
+constexpr size_t EchoDetector::kRenderBufferSize;
+
+void EchoDetector::BufferRender(rtc::ArrayView<const float> render) {
+  minimum_render_buffer_size_.AddValue(render_buffer_.buffer_size());
+  if (minimum_render_buffer_size_.GetMinimum() > 0 &&

[peah-webrtc, 2016/10/19 14:45:26]

Do you need a sliding window buffer for this?
You basically want to know whether the render_buffer_.buffer_size() has been
zero during a time period T, right? That should be sufficient by using a counter
that is reset to 0 each time buffer_size() is zero. If the counter reaches T,
then clockdrift can be flagged. If it works, that solution is cheaper and
requires less code.

[ivoc, 2016/10/20 14:04:36]

That's a good idea. My solution is a bit too general here it seems, I was also
considering the case where there could be multiple excess render buffer calls
within one monitoring period, but I guess that's actually a pretty unrealistic
amount of clock drift and that shouldn't happen in practice. 

I'll use your solution instead (too bad, I kind of liked making this sliding
window class :-))

+      render_buffer_.buffer_size() ==
+          minimum_render_buffer_size_.GetMinimum()) {
+    LOG(LS_ERROR) << "Clockdrift detected in residual echo detector. Ignoring "
+                  << render_buffer_.buffer_size() << " render frame(s).";
+    render_buffer_.Clear();
+  }
+  float power = Power(render);
+  render_buffer_.Push(power);
 }
 
-void EchoDetector::Process(const rtc::ArrayView<const float>& /*nearend*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Process(rtc::ArrayView<const float> nearend) {

[peah-webrtc, 2016/10/19 14:45:26]

I think you should use a name with something of capture rather than nearend.
That matches better with the name render used in BufferRender

[ivoc, 2016/10/20 14:04:36]

Done.

+  const float capture_power = Power(nearend);

[peah-webrtc, 2016/10/19 14:45:26]

Either more this variable closer to where it is first used, or use the output of
Power directly in the UpdateEstimate call.

[ivoc, 2016/10/20 14:04:36]

It is used in two places, to update the statistics and inside the for-loop on
line 78 (in this version). I'll move it closer to the update function.

+  const float capture_mean = capture_variance_.mean();

[peah-webrtc, 2016/10/19 14:45:26]

Move capture_mean closer to where it is used. Or is there a reason for why the
value before the updated mean from the last frame is used?

[ivoc, 2016/10/20 14:04:35]

That does seem to be a bug, I fixed it now, thanks.

+  const float capture_std_deviation = capture_variance_.std_deviation();

[peah-webrtc, 2016/10/19 14:45:26]

Same comment as for capture_mean.

[ivoc, 2016/10/20 14:04:35]

Done.

+
+  const rtc::Optional<float> buffered_render_power = render_buffer_.Pop();

[peah-webrtc, 2016/10/19 14:45:25]

I think the function  would benefit in readability if you separate the different
parts with blank lines.

[ivoc, 2016/10/20 14:04:36]

I added a few blank lines and some comments.

+  if (!buffered_render_power) {
+    // This should only happen in case of clock drift. For now we will just
+    // ignore the "extra" capture value.
+    LOG(LS_ERROR) << "Clockdrift detected in residual echo detector. Ignoring "

[peah-webrtc, 2016/10/19 14:45:26]

This will flood the log with messages if Capture is started before Render. 

[ivoc, 2016/10/20 14:04:35]

Good point, but isn't it typically the render side that starts first? Or can
both cases happen?

[peah-webrtc, 2016/10/20 15:08:24]

I don't think we can make any assumptions on that. I at least have no idea.

[ivoc, 2016/10/21 12:21:15]

I removed the log messages for now to avoid this. I will add how often this
happens to the logging in a follow-up CL.

[ivoc, 2016/10/21 15:42:08]

Sorry, I mistyped, I meant that I will add it to the stats in a follow-up CL.

+                     "capture frame.";
+    return;
+  }
+  const float latest_render_power = *buffered_render_power;

[peah-webrtc, 2016/10/19 14:45:26]

I think you can skip this local copy. Use *buffered_render_power directly
instead.

[ivoc, 2016/10/20 14:04:35]

Done.

+  capture_variance_.UpdateEstimate(capture_power);
+  render_variance_.UpdateEstimate(latest_render_power);
+  RTC_DCHECK_LT(next_insertion_index_, kLookbackFrames);
+  render_power_[next_insertion_index_] = latest_render_power;
+  render_power_mean_[next_insertion_index_] = render_variance_.mean();
+  render_power_std_dev_[next_insertion_index_] =
+      render_variance_.std_deviation();
+  echo_likelihood_ = 0.f;
+  for (size_t delay = 0; delay < covariance_.size(); ++delay) {
+    const size_t read_index =
+        (kLookbackFrames + next_insertion_index_ - delay) % kLookbackFrames;
+    RTC_DCHECK_LT(read_index, render_power_.size());
+    const float render_power = render_power_[read_index];

[peah-webrtc, 2016/10/19 14:45:25]

I think you can skip storing the buffer values in local variables before the
function call. Make the function call with the values render_power_[read_index],
render_power_mean_[read_index] and render_power_std_dev_[read_index] instead. I
think the code will be easier to read that way.

[ivoc, 2016/10/20 14:04:36]

Done.

+    const float render_mean = render_power_mean_[read_index];
+    const float render_std_dev = render_power_std_dev_[read_index];
+    covariance_[delay].UpdateCovarianceEstimate(
+        capture_power, capture_mean, capture_std_deviation, render_power,
+        render_mean, render_std_dev);
+    echo_likelihood_ = std::max(
+        echo_likelihood_, covariance_[delay].normalized_cross_correlation());
+  }
+  // Update the next insertion index.
+  ++next_insertion_index_;
+  next_insertion_index_ %= kLookbackFrames;
 }
 
-void EchoDetector::Initialize(int /*sample_rate_hz*/) {
-  // TODO(ivoc): Add implementation.
-  RTC_NOTREACHED();
+void EchoDetector::Initialize() {
+  render_buffer_.Clear();
+  std::fill(render_power_.begin(), render_power_.end(), 0.f);
+  std::fill(render_power_mean_.begin(), render_power_mean_.end(), 0.f);
+  std::fill(render_power_std_dev_.begin(), render_power_std_dev_.end(), 0.f);
+  render_variance_.Clear();
+  capture_variance_.Clear();
+  for (auto& cov : covariance_) {
+    cov.Clear();
+  }
+  echo_likelihood_ = 0.f;
+  next_insertion_index_ = 0;
 }
 
 }  // namespace webrtc